We revisit the FAM algorithm with the aim of clarifying the inner working of the algorithm with respect to implementing it. We provide a step through the original presentation, clarifying issues that are of interest to implementors of the speci c algorithm as well as to implementors of other EM algorithms in PLP frameworks. In addition, this paper presents P epl, an implementation of the algorithm in Prolog. We describe three di erent alternatives to dealing with the expressions needed at the core of the algorithm. A number of example programs provided with P epl are explained and the application of P epl to user speci ed programs is discussed.
Failure adjusted maximization (F AM) [
P epl, which stands for parameter estimation in Prolog, is an implementation
of the failure adjusted maximisation algorithm for S LPs. S LPs are an extension
of logic programs where arithmetic labels are attached to clausal de nitions.
S LPs have well de ned log linear semantics and an extensive analysis of the
e ect of backtracking strategies on these semantics, [
The original formulation of F AM although presented in a clear and concise mathematical language can be challenging for implementors, particularly for programmers who are new to probabilistic logic programming. Here, we expose some of the intricacies of the algorithm with emphasis on practical challenges in implementing it.
Furthermore, we present a speci c implementation of F AM, P epl, which has been implemented in Prolog. Key aspects of the implementation such as the transformation of labelled clauses to Prolog and alternative methods for computing the counts used in the closed-form calculation, are also described. The implementation is tested against the examples from the F AM paper as well as on other probabilistic programs.
The remainder of the paper is structured as follows: Section 2 presents the algorithm with emphasis on implementation details, Section 3 describes P epl and Section 4 discusses a number of examples. Section 5 concludes the paper. 2
Here we present some reading notes for Failure Adjusted Maximisation (F AM)
algorithm on Stochastic Logic Programs as presented in [
S LPs are logic programs which include clauses that are labelled with arithmetic values. Predicates are de ned as either logical, or as labelled in which case all the clauses in the predicate's de nition should be labelled. The following two examples show how an unbiased coin (left) and a recursive predicate (right) can be coded.
1/2 : coin(head). 1/2 : coin(tail).
1/3 : member( H, [H|T] ). 2/3 : member( El, [H|T] ) :member( El, T ).
A pure S LP is stochastic logic program that does not contain non-labelled predicates. In contrast, an impure program contains, and potentially has call dependencies between, labelled and non-labelled predicates. A normalised predicate is a predicate de ned by labelled clauses for which the sum of the labels sum to one. F AM is a parameter estimation algorithm that learns the best values of the clausal labels from a data.
We prepend objects in the original F AM paper by ML-. Also, we use a topdown approach in presenting the algorithm. Thus we start with the de nition in ML-De nition 10 repeated here in Figure 1. (Slightly modi ed from the original.)
The objective of this algorithm is, when given the S LP program (S) in Fig. 2 (ML-Fig.9 ) and data (y) Fig. 3 (part of ML-Table II ) to produce the best set of 1; : : : 6 (where i = (logli)).
i is the label, or parameter of clause Ci and a positive number (here we mainly consider 0 < i 1).
Intuitively speaking, we want to nd ^ = h ^1; : : : ; ^6i which will reproduce the data according to the input frequencies. For example, if we run goal j? s(A; B) 120 times, and against the program in Fig. 2 (its parameters changed to ^) then we would like the results to have frequencies close to the ones in Table 1.
Assuming of course that we replace the top-to-bottom exhaustive backtrackable clause matching of Prolog by a proportional to label, non-backtrackable, choice amongst the matching clauses. 0. Let h = 0, and (0) such that Z (0) > 0. 1. For each parameterised clause Ci, compute (h) [ i j y] (h) [ i j y] using 1 (ML
Eq.8 ). 2. For each parameterised clause Ci let S(h) be the sum of the expected counts i (h)[ i0 j y] for all the clauses Ci+0 such that Ci+0 shares the predicate symbol as Ci. 3. For each parameterised clause Ci, if Si(h) = 0 then lih+1 = li(h) otherwise 4. Set h
h + 1 and go to 1 unless (h + 1) has converged. l1 : s(X,p) :- p(X), p(X). l2 : s(X,q) :- q(X).
l3 : p(a). l4 : p(b).
l5 : q(a).
l6 : q(b). l(h+1) = i (h)[ i j y]
S(h)
i FAM is an EM algorithm. An EM algorithm tries to maximise the likelihood of the data by selecting the appropriate parameters. In SLPs the probability we try to maximise is P (yj (h)). This is, the probability of the observed data (in the given frequencies) given the current parameters.
Since an SLP's parameters are its clausal probabilities, FAM works on the expected contribution a particular clause has in derivations, with relation to the data at hand. This is (h) [ i j y] and was decomposed in ML-Eq.8 (here 1 in Fig. 1)
t 1 (h) [ i j y] = X Nk k=1 (h) [ i j yk] + N (Z (1h) 1) (h) [ i j f ail] (1)
The rst part corresponds to refutations while the second term to failed derivations. Broadly speaking Eq. 1 gathers together the contributions of a par1 the rst part of the LHS of (1) has been removed here, since it was never used in the implementation, where we view unambiguous yields as a standard sub-case of the ambiguous case.
k 1 2 3 4 Atom yk s(a,p) s(b,p) s(a,q) s(b,q) Count Nk 4 2 3 3 Atom s(a,p) s(b,p) s(a,q) s(b,q) Should appear 40 20 30 30 ticular clause (Ci) to derivations against (a) the program, (b) the current parameters and (c) the data. All the constituents of Eq. 1 are listed in the Glossary. The most important components are (a) Z (h) the probability of success, (b) (h) [ i j yk] the expected number of times Ci was used in refutations yielding yk, and (c) (h) [ j f ail] the expected contribution of the clause to failed derivations. Let R the set of refutation, with Rk the refutations producing yk and F the set of failed derivations. Then (b) and (c) are :
X r2Rk
X f2Rfail X r2Rk
X f2Rfail Using this formulation gives us some extra millage, when it comes to impure S LPs, which mix labelled and unlabelled (non-probabilistic) clauses. Strictly speaking, ML-Sect.3., Defn.6 states that derivations in same equivalence class Isnhosuulcdh hcaavseestPher 2saRme(ry)i=elPd.r2TRhis(ern)s+urPesf 2thFat (Pf)r=2RPr(2r)R+ (Pr)fw2Fhich(fis) w=ha1t. would FAM normally use.
A problem arises when considering in nite computations. When there is at least one in nite branch then it is impossible to manipulate all derivations. One possible solution is to place a signi cance limit ( ) deeming any derivation with probability < as failure. In the absence of in nite branches, one might be able to generate graphs representing all possible derivations, thus making substantial time savings as there will not be a need to revisit derivations at each iteration. Note that we expect it will be very hard to combine signi cance limit and derivation as graphs.
Sampling, on the other hand, estimates the various expectations, by means of running a number of independent trials and noting the results. The process is repeated at each iteration with the updated . 2 In this case, Z (h) = Pr2R PP(rr)2+R PP(rf2)F P (f ) (2)
Similarly to the exact case, a signi cance limit can be set to deal with in nite computation. On the other hand, it is not likely that we can e ciently employ graphs.
With sampling it is more straight forward to use the bag of samples to calculate (h) [ i j yk] . Let Sk be the set of all the samples yielding yk, then Since for s 2 Sk, The FAM algorithm of Fig. 1 terminates when there is no substantial progress to be had. This is the case when the log-likelihood of the data given the current parameters is improved less than some within two iterations. The log-likelihood is 3 logL (y) =
X Nklog( k (yk j true)) 2 strictly speaking, in our sampling R; Rk and F are not sets but bug collections 3 it is also worth considering (yk j y)
In the case of sampling we have : since sampling may not yield all yk, the above will lead to logL (y) = when j Rk j= 0. Thus in that case we let (yk j true) = 1= j R j2 For the exact case (yk j true) =j Rk j = j R j (yk j true) =
P r2Rk
Z (r) inf 3
P epl is an implementation of the F AM algorithm. It consists of a set of Prolog
predicates that can be used on S LPs to learn the clausal parameters from data
and do sampling from S LPs. It is available for two Prolog systems: Yap [
A simple example is provided which can be ran with: ?- [main]. ?- main.
This example runs ve iterations on the example presented in [
Stochastic clauses are term expanded to standard Prolog ones. Unique identiers and a path argument are added to the transformation of stochastic clauses. These are used to identify the path of each derivation. In addition failure paths are also recorded by term expansion techniques. The system provides three ways for computing the counts needed for the closed-form calculation: exact, sample and store. The rst method is the straight forward approach where all solutions to the target goal are quarried at each iterative step. Sampling approximates the counts by only sampling from the target. The expressions associated with the exact computation can be stored as term structures of arithmetic expression that can be evaluated at each iteration with fresh instantiations of the labels. This trades space for speed, making the computation much faster by requiring larger amounts of memory. 4 http://www.swi-prolog.org/pack/list?p=pepl 3.1
sload pe(SlpSource),
Load an SLP to memory. If the source le has .slp as its le extension then this may be omitted. P epl looks for SlpSource in directories ., and ./slp/ In SWI-Prolog it also looks in pack(pepl/slp/). sls/0
Listing of the stochastic program currently in memory. ssave(FileName)
Save the stochastic program currently in memory to a le. fam(Options)
Run F AM on the program loaded in memory, with a number of options passed as a list that may include the following terms: { count (CountMeth), CountMeth in f*exact*, store, sampleg; { times(Tms), default is Tms = 1000 (only relevant with CountMeth=sample); { termin(TermList), currently TermList knows about the following terms *interactive*- ask user if another iteration should be run, iter(I)- I is the number of iterations, prm e( p)- parameter di erence between iterations. If the change in each and all pararameters between two iterations is less than p then the algorithm terminates due to convergence of the parameters ll e( )- likelihood convergence limit; { goal (Goal), the top goal, defaults to an version of the data predicate with all its arguments replaced by free variables; { pregoal (PreGoal), a goal that is called only once, before experiments are run. The intuition is that PreGoal will partially instantiate Goal. { data(Data), the data to use, overrides datafile/1. Data should be a list of Yield-Times pairs. (All Yields of Goal should be included in Data, even if that means some get Times = 0.) { prior (Prior), the distribution to replace the probability labels with. Default is that no prior is used, Prior=none and input parameters are used as given in Slp source le. System also knows about uniform and random. Any other distribution should come in Prolog source le named Prior.pl and de ne Prior/3 predicate. First argument is a list of ranges (Beg-End) for each stochastic predicate in source le. Second argument, is the list of actual probability labels in source le. Finally, third argument should be instantiated to the list of labels according to Prior. { data le(DataFile), the data le to use, default is SLP data.pl. DataFile should have either a number of atomic formulae or a single formula of the form: frequencies(Data).+ { complement (Complement), one of : none (with P rbSc = P rbT rue, the default), success (with P rbSc = 1 P rbF ail), or quotient (with P rbSc = P rbT rue=(P rbT rue + P rbF ail)). { setrand (SetRand), sets random seeds. SetRand = true sets the seeds to some random triplet while the default SetRand = false, does not set them. Any other value for SetRand is taken to be of the form rand (S1,S2,S3) as expected by system predicate random of the supported Prolog systems. { eps(Eps), the depth Epsilon. Sets the probability limit under which P epl considers a path as a failed one. { write iterations(Wrt) indicates which set of parameters to output. Values for Wrt are: all, which is the default, last, and none. { write ll (Bool) takes a boolean argument, indicating where log-likelihoods should be printed or not. Default is true. { debug (Dbg) should be set to on or o (later is the default). If on, various information about intermediate calculations will be printed. { return(RetOpts), a list of return options, default is the empty list. The term RetOpts contain variables which will be instantiated to the appropriate values signi ed by the name of each corresponding term. Recognised are, initial pps/1 for the initial parameters, final pps/ for the nal/learned parameters, termin/1 for the terminating reason, ll/1 for the last log-likelihood calculated, iter/1 for the number of iterations performed, and seeds/1 for the seeds used. { keep pl (KeepBool, if true, the temporary Prolog le that contains the translated SLP, is not deleted. Default is false. { exception(Handle), identi es the action to be taken if an exception is raised while running fam/1. The default value for Handle is rerun. This means the same Fam call is executed repeatedly. Any other value for Handle will cause execution to abort after printing the exception raised. switch dbg(+Switch)
Switch debugging of fam/1 to either on or off. scall(Goal,Eps,Meth,Path,Succ,BrPrb)
This is a predicate for people interested in the internals, and should only be used by experienced users. The following are the arguments to this call: { The vanilla Prolog Goal to call. { The value of Eps(ilon) at which branches are to be considered as failures. { The search Meth(od) to be used, i.e. all for all solutions or sample for a single solution. { The Path(s) of the derivation(s). { A ag indicating a Succ(essful) derivation or otherwise-Succ is bound to the atom fail if this was a failed derivation and remains unbound otherwise.
{ BrPrb the branch probability of the derivation.
See predicate main gen/1, in examples/main scfg.pl for example usage. all paths(+SlpFile,+Call)
Display to standard output all derivation paths and plenty of information associated with calling stochastic goal Call on the Slp de ned in +SlpFile. 3.2
Since FAM is an instance of the EM algorithm, initial values for the parameters must be supplied. Also, since FAM is only a parameter estimation algorithm, the structure of the SLP must be given. In our implementation the user composes an SLP with the appropriate structure and labels the clauses in this SLP with the initial values of the parameters. The rst step in running FAM is to load this SLP. Suppose the SLP with the initial parameters were saved in the le foo.slp; this SLP is loaded using sload pe/1 (detailed description in Section 3.1): ?- [pepl]. : : : ?- sload pe(foo). yes ?
To run the EM algorithm we need a target sample space, comprising from observables, and the expected number each observable should appear. Data should be represented by a Prolog le of atomic formulae or a single formula of the form : frequencies( Freqs ). where Freqs is a list of Datum-Times pairs. In the former case atomic formulae can be of arbitrary format but they should share common predicate name and arity. This is the same predicate name and arity for the top goal in the user de ned SLP. The intuition is that each formula is a point sample in the target sample space to which we wish to t the parameters of a given SLP. When frequencies( Freqs ) is used, Datum should be as the formulae just described, while Times should be the times each Datum appears in the target sample space. The target sample space can be passed to fam/1 either with the option data file/1, with its argument pointing to a data le as described above, or with the option data/1, with its argument being a frequencies list (Freqs, above). The two di erent ways to pass the target sample space and the two formats of the data le option are shown in Table 2
Assume foo_data.pl is the Prolog le containing the training data. To run FAM with default settings, do: ?- fam([]). (see Section 3.1 for how to change these settings). To save the S LP with the estimated parameters to a le fitted foo.slp, just do: ?- ssave( tted foo).
File fitted foo.slp is created in current directory.
To run fam without rst loading the S LP to memory, call ?- fam([slp(foo)]). data([s(a,p)-4,s(a,q)-3,s(b,p)-2,s(b,q)-3])
(a) s(a,p). s(a,q). s(b,p). s(b,q). s(a,p). s(a,q). frequencies([s(a,p)-4,s(a,q)-3,s(b,p)-2,s(b,q)-3]). s(b,p). s(b,q). s(a,p). s(a,q). s(b,q). s(a,p). A number of pre-canned examples are included in the P epl sources within the directory examples. Standard runs of F AM are wrapped in simple calls that can be invoked from the Prolog prompt. ! [a], s, [a]. ! [b], s, [b]. ! [a],[a]. ! [b],[b]. (a) a situation where failure is important. (b) how to produce N samples (main gen/1 ).
Again, default is main_exact and main_store with main_sample are also provided. 4.2
Bloodtype PRISM example bloodtype(a) :- genotype(a,a). bloodtype(a) :- genotype(a,o). bloodtype(a) :- genotype(o,a). bloodtype(b) :- genotype(b,b). bloodtype(b) :- genotype(b,o). bloodtype(b) :- genotype(o,b). bloodtype(o) :- genotype(o,o). bloodtype(ab) :- genotype(a,b). bloodtype(ab) :- genotype(b,a). genotype(X,Y) :- gene(X),gene(Y). 1=3 :: gene( a ). 1=3 :: gene( b ). 1=3 :: gene( o ).
The example from the Prism web-site5 can also be seen in action. The corresponding S LP can be found in the slp directory of the distribution: slp/prism bt. % cd run % prolog (where prolog is in fyap,swiplg). ?- [main prism bt]. ?- main exact. or ?- main store. or ?- main sample. after each of the above main calls, you can test accuracy by ?- test(10000).
Frequency of ground successful goals should match the frequency of Data. Note that FAM, in theoretic terms, is not strictly speaking applicable to this example since it does not observe the equivalence class criterion. However, in practice, the results of the algorithm are correct. 5 http://sato-www.cs.titech.ac.jp/prism/overview-e.html
We presented an extensive new reading of the FAM algorithm which may be
of value to implementors of EM algorithms in PLP languages. In tandem we
detailed the inner workings of an easy-to-install Prolog based implementation
of the algorithm. P epl comes with a number of canned examples that are
collected from the original FAM paper and other literature sources. Furthermore
we detailed a novel approach to re-calculating the arithmetic expressions
necessary in the estimation calculations. This is via storing variable versions of the
expressions, copies of which are instantiated at each iteration. Future work on
the system can include tabled inference which has been shown to be successful in
other PLP systems, [
Dr James Cussens helped with many clari cations and endless iterations of explanations while working on Pepl.
derivation refutation
h i k Ci F Nk N
Sequence of goals produced by applying resolution steps on an initial goal G0 and program P, ending on either true or false, p. 48. A derivation ending in true., p. 48.
Scripts the algorithm's current iteration.
Index for clauses.
Index for data.
The ith clause. For example C4 in 2 is l4 : p(b), p. 48. Set (or list) of all failed derivations, p. 49.
The number of times datum k occured in the observed data. For example in Fig. 3 N2 = 2.
The number of observed data (= Pk Nk). For example in Fig. 3 N = 12.
Set (or list) of all refutations, yielding yk, p. 49.
Set (or list) of all refutations, p. 49.
Probability of success. li y