Tabling for infinite probability computation
Taisuke Sato1 and Philipp Meyer212Tokyo Institute of Technology
2-12-1 Ookayama, Meguro, Tokyo, Japansato@mi.cs.titech.ac.jp
Technische Universität München
Arcisstrasse 21, 80333 München, Germany
meyerphi@in.tum.de

Abstract
Tabling in logic programming has been used to eliminate redundant computation and also to stop
infinite loop. In this paper we add the third usage of tabling, i.e. to make infinite computation
possible for probabilistic logic programs. Using PRISM, a logic-based probabilistic modelinglanguage with a tabling mechanism, we generalize prefix probability computation for PCFGs toprobabilistic logic programs. Given a top-goal, we search for all SLD proofs by tabled search
regardless of whether they contain loop or not. We then convert them to a set of linear probability
equations and solve them by matrix operation. The solution gives us the probability of the topgoal, which, in nature, is an infinite sum of probabilities. Our generalized approach to prefix
probability computation through tabling opens a way to logic-based probabilistic modeling ofcyclic dependencies.
1998 ACM Subject Classification D.3.3 Language Constructs and Features
Keywords and phrases probability, tabling, PRISM
Digital Object Identifier 10.4230/LIPIcs.xxx.yyy.p abling, probability computation, prefix

1

Introduction

Combining logic and probability in a logic programming language provides us with a powerfulmodeling tool for machine learning. The resulting language allows us to build complex yet
comprehensible probabilistic models in a declarative way. PRISM [12, 13, 14] is one of theearliest attempts to develop such a language. It covers a large class of known models including
BNs (Bayesian networks), HMMs (hidden Markov models) and PCFGs (probabilistic context
free grammars) and computes probabilities with the same time complexity as their standard
algorithms1 , as well as unexplored models such as probabilistic graph grammars [11].
The efficiency of probability computation in PRISM is attributed to tabling [16, 17, 10,
20, 19]2 that eliminates redundant computation. Given a top goal G, we search for all SLD
proofs of G by tabled search and translating them to a set of propositional formulas with agraph structure called an explanation graph for G [13]. By applying dynamic programming
to the explanation graph which is acyclic and partially ordered we can efficiently computethe probability of G in proportion to the size of the graph. The use of tabling also gives us
another advantage over non-tabled computation: it stops infinite loop by detecting recurrence1

For example, the junction tree algorithm for BNs, the forward-backward algorithm for HMMs and theinside-outside algorithm for PCFGs.
2
Tabling is also employed in other probabilistic logic programming languages such as ProbLog [5] andPITA [9].
© John Q. Open and Joan R. Access;licensed under Creative Commons License NC-ND
Conference title on which this volume is based on.
Editors: Billy Editor, Bill Editors; pp. 1–11
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

2

Tabling for infinite probability computation

patterns of goals. Tabled logic programs thus allow us to directly use left recursive rules in
CFGs without the need of converting them to right recursive ones.
In this paper we pursue yet the third advantage of tabling that has gone unnoticed in
the non-probabilistic setting. We apply tabling to compute an infinite sum of probabilities
that typically appears in the context of prefix probability computation in PCFGs. PCFGs(probabilistic context free grammars) are a probabilistic extension of CFGs in which CFG
rules have probabilities and the probability of a sentence is computed as a sum-product ofprobabilities assigned to the rules used to derive the sentence [1, 4]. A prefix w is an initialsubstring of a sentence. Then the probability of the prefix w given by a PCFG is a sum of
probabilities of infinitely many complete sentences of the form wv for some string v [3, 15, 7].
Prefix probabilities are useful in speech recognition as discussed in [3]. We generalize thisprefix probability computation that originated in PCFGs to probability computation on
cyclic explanation graphs which are generated by tabled search in PRISM. We emphasize that
this approach, i.e. probability computation via cyclic explanation graphs, makes it possible
to model probabilistic cyclic dependencies abundant in real life from economics to biologicalsystems by probabilistic logic programs.
Technically the generation of cyclic explanation graphs is not difficult in PRISM. Justsetting appropriately a certain PRISM flag that controls tabled search is enough. Howevercomputing probabilities from such graphs is difficult in general except for the case of linear
cyclic explanation graphs that can be turned into a set of linear probability equations
straightforwardly solvable by matrix operation. So the real problem is to guarantee thelinearity of cyclic explanation graphs. We specifically examine a PRISM program for prefix
probability computation in PCFGs and prove that the program always generates linear cyclic
explanation graphs. We also prove that the probability equations obtained from the linear
cyclic explanation graphs are solvable by matrix operation under some mild assumptions on
PCFGs.

2

Probability computation in PRISM

2.1

Tabling and explanation graphs

PRISM is a probabilistic extension of Prolog with built-in predicates for machine learning
tasks such as parameter learning and Bayesian inference [13, 14]. Theoretically a PRISM
program DB is a union of a set of definite clauses and a set of probabilistic atoms of theform msw(id,v) that simulate dice throwing3 . It defines a probability measure (an infinite
joint distribution) PDB (·) over possible Herbrand interpretations from which the probabilityof an arbitrary closed formula is calculated. Practically however PRISM programs are just
Prolog programs that use msw atoms as probabilistic primitives. msw atoms are introducedby special declarations values/3 specifying their properties as shown in the program DB 0 in
Figure 1.
In PRISM, probabilities of ground atoms defined by a program DB are computed indirectlyin two steps. In the first step, for a top-goal G of which we wish to compute the probability, we
logically reduce it through DB by a top-down proof procedure, SLD search, to an equivalent
propositional DNF formula E1 ∨ . . . ∨ Ek such that comp(DB) ` G ⇔ E1 ∨ . . . ∨ Ek . Here eachEi (1 ≤ i ≤ k), an explanation for G, corresponds to an SLD proof of G. It is a conjunctionof ground msw atoms that records probabilistic choices made in the construction of the SLD

3msw(id,v) reads that throwing a dice named i yields an outcome v.

Taisuke Sato and Philipp Meyer

proof4 . In the second step, using the fact that G and E1 ∨ . . . ∨ Ek denote an identicalrandom variable in terms of the distribution semantics for PRISM [13], we compute theprobability of G as PDB (G) = PDB (E1 ∨ . . . ∨ Ek ) where PDB (·) is the probability measuredefined by DB.
In general there are exponentially many SLD proofs and so are explanations which resultin an exponential size DNF. Nonetheless by introducing a tabling mechanism in the exhaustive
SLD search process, we can often produce an equivalent but much smaller boolean formulaby factoring out common sub-conjunctions in explanations as intermediate goals [13, 20].
The resulting boolean formula is expressed as a conjunctive set of defining formulas that takethe form H ⇔ B1 ∨ . . . ∨ Bh . Here H is the top-goal G or an intermediate goal. Hereafter
the top-goal and intermediate goals are collectively called defined goals. Each Bi (1 ≤ i ≤ h)is a conjunction C1 ∧ . . . ∧ Cm ∧ msw1 ∧ . . . ∧ mswn (0 ≤ m, n) of defined goals {C1 , . . . , Cm }and msw atoms {msw1 , . . . , mswn }. We say that H is a parent of Cj (1 ≤ j ≤ m). We callthe closure of this parent-child relation the ancestor relation over ground atoms in DB. The
whole set of defining formulas, denoted by Exp(G), is called the explanation graph for G.

2.2

From explanation graphs to probability computation

The probability PDB (G) of a given goal G is precisely defined in terms of the distribution
semantics for PRISM. But the problem is that the semantics is so abstractly defined and wecannot know the actual value of PDB (G) easily. Here we describe how to compute it undersome assumptions.
To compute PDB (G), we convert each defining formula H ⇔ B1 ∨ . . . ∨ Bh in Exp(G) toa set of probability equations for H:

P (H)= P (B1 ) + · · · + P (Bh )where

P (Bi )= P (C1 ) · · · P (Cm )P (msw1 ) · · · P (mswn ) (1 ≤ i ≤ h)for Bi = C1 ∧ . . . ∧ Cm ∧ msw1 ∧ . . . ∧ mswn .

We denote by Eq(G) the entire set of probability equations thus obtained. Note that theconversion assumes exclusiveness among disjuncts {B1 , . . . , Bk } and independence among
conjuncts {C1 , . . . , Cm , msw1 , . . . , mswn }5 . We consider P (H)s in Eq(G) as numerical variables
representing unknown probabilities and refer to them as P -variables. What is important
about Eq(G) is that Eq(G) always has a solution P (H) = PDB (H) for every defined goal
H[13]. So if Eq(G) has a unique solution for P (G), it coincides with PDB (G).
When defined goals appearing in Exp(G) are hierarchically ordered by the parent-childrelation (with G as top-most element) as is usually the case, the P-variables in Eq(G) arealso hierarchically ordered so that Eq(G) is uniquely and efficiently solved by dynamic
programming using the generalized IO algorithm [13] in time linear in the size of Eq(G).
There are cases however in which Exp(G) is not hierarchically ordered and some defined goals
are their own ancestors. We say Exp(G) is cyclic if there is a defined goal having itself as anancestor in Exp(G). If Exp(G) is cyclic, Eq(G) is also cyclic, and hence it is impossible to4comp(DB) is the completion of DB. It is a union of if-and-only-if form of DB and so called Clark’s
equational theory.
5
We assume in this paper that these conditions are always satisfied.

3

4

Tabling for infinite probability computation

apply dynamic programming to Eq(G), or even worse Eq(G) may not have a unique solution.
In the next section, using a concrete example, we have a close look at cyclic Eq(G)s andinvestigate their properties.

3

Prefix computation for PCFGs using PRISM

In this section, we formulate prefix computation for PCFGs using PRISM.

3.1

A prefix parser

Before proceeding we introduce some terminology about CFGs for later use. Let X be anonterminal in a CFG, α, β a mixed sequence of terminals and nonterminals. A rule for X isa production rule of the form X ⇒ α. If there is a rule of the form X → Y β, we say X andY are in the direct left-corner relation. The transitive closure of the direct left-corner relation
is called the left-corner relation and we write as X →L Y if X and Y are in the left-corner
relation. The left-corner relation is cyclic if X →L X holds for some nonterminal X. We saythat a rule is useless if it does not occur in any sentence derivation. A nonterminal is uselessif every rule for it is useless. Otherwise it is useful. In this paper we assume that CFGs have“s” as a start symbol and have no epsilon rule and no useless nonterminal.
In addition let θ1 : X → α1 , . . . , θn : X → αn be the set of rules for X in a PCFG withPn
selection probabilities θ1 , . . . , θn where i=1 θi = 1. We assume that every rule has a positive
selection probability. If the sum of probabilities of sentences derived from the start symbol is unity, the PCFG is said to be consistent [18]. We also assume that PCFGs are consistent.
Now we here look at a concrete example of prefix probability computation based on cyclic
explanation graphs. Consider a PCFG, PG0 = {0.4 : s → s s, 0.3 : s → a, 0.3 : s → b}.
Here “s” is a start symbol and 0.4 : s → s s says that the rule s → s s is selected withprobability 0.4 when “s” is expanded in a sentence derivation.
A PRISM program DB 0 in Figure 1 is a prefix parser for PG0 . It is a slight modificationof a standard top-down CFG parser and parses prefixes acceptable by PG0 such as “aab” (aslist [a,a,b]). The difference from the usual CFG parser is that it immediately terminates
successfully as soon as the input prefix is consumed even if there remain nonterminals to beprocessed.

values(s,[[s,s],[a],[b]],set@[0.4,0.3,0.3]).
pre_pcfg(L):- pre_pcfg([s],L,[]). % L is a ground list
pre_pcfg([A|R],L0,L2):% L0 ground, L2 variable when called( values(A,_)-> msw(A,RHS),% if A is a nonterminal
pre_pcfg(RHS,L0,L1) ; L0=[A|L1] ), % rule A->RHS selected( L1=[] -> L2=[] ; pre_pcfg(R,L1,L2) ).
pre_pcfg([],L1,L1).

Figure 1 Prefix parser DB 0 for PCFGs

Taisuke Sato and Philipp Meyer

values(s,[[s,s],[a],[b]],set@[0.4,0.3,0.3]) in Figure 1 is a value declaration
which encodes PG0 . pre_pcfg([A|R],L0,L2) is read that [A|R], a substring of α in somerule X → α, spans a d-list L0-L2 as a sublist of the input list [w1 , . . . , wN ]6 . We remarkthat DB 0 is general, applicable to any PCFG just by replacing values/3 with appropriate
value declarations.
When this program is run with PRISM-flag error_on_cycle set to “off” for a command ?-G where G = pre_pcfg([w1 , . . . , wN ]) and [w1 , . . . , wN ] (wi ∈ {a, b}) is a list
representing a prefix w1 , . . . , wN , the proof procedure, the SLD search, simulates the leftmost
derivation of the sentence by recursively calling the second clause. As soon as [w1 , . . . , wN ]is derived, the search terminates with success while ignoring nonterminals in R that may
be non-empty as if R were successfully expanded to the remaining sentence7 . We call thistype of success pseudo success. During the search, a call to pre_pcfg/3 is always of theform pre_pcfg(v,[wi , . . . , wN ],L2) where v is a substring of RHS of some production ruleand i ≤ N . On return of the call, the variable L2 is instantiated either to [wj , . . . , wN ](i < j ≤ N ) or to [] in the case of pseudo success. Therefore there are only a finitely many
number of calling and returning patterns of prefix_pcfg/3 and hence, the tabled search for
all proofs of the top-goal G always terminates.
After all proof search done, PRISM constructs an explanation graph for the top-goal G
by scanning the answer table in the memory. One thing to be noticed is that goals callingthemselves and thereby suspended by tabling are also recorded in the table in addition
to goals that normally succeeded. When PRISM encounters such goals, it looks at the
PRISM-flag error_on_cycle and if the value is “off”, those goals are treated as succeeded
and as a result a cyclic explanation graph is generated.

3.2

Computing prefix probabilities: an example

In this subsection, we see, using a small example, how prefix probabilities are computed fromcyclic explanation graphs. Figure 2 is the explanation graph for pre_pcfg([a]) obtainedby executing a command ?- probf(pre_pcfg([a]))8 w.r.t. DB 0 . As can be seen, there isa cyclic goal pre_pcfg([s,s],[a],[]) that calls itself. We convert the cyclic explanationgraph to the corresponding set of probability equations shown in Figure 3. Here we usedabbreviations: θs→ss = P (msw(s, [s, s])) and θs→a = P (msw(s, [a])).
6

In the following strings beginning with lower case letters are ground terms.
This is justifiable as we assume that every nonterminal is useful.
8
probf/1 is a built-in predicate in PRISM and probf(G) displays the explanation graph of G.

7

pre_pcfg([a]) <=> pre_pcfg([s],[a],[])
pre_pcfg([s],[a],[]) <=>pre_pcfg([s,s],[a],[]) & msw(s,[s,s]) v pre_pcfg([a],[a],[]) & msw(s,[a])pre_pcfg([s,s],[a],[]) <=>pre_pcfg([a],[a],[]) & msw(s,[a]) v pre_pcfg([s,s],[a],[]) & msw(s,[s,s])pre_pcfg([a],[a],[])

Figure 2 Explanation graph for prefix “a”

5

6

Tabling for infinite probability computation



 X

Y

Z


W

=
=
=
=

Y
Z · θs→ss + W · θs→a
W · θs→a + Z · θs→ss
1

where



 X

Y

Z


W

=
=
=
=

P (pre_pcfg([a]))P (pre_pcfg([s], [a], []))P (pre_pcfg([s, s], [a], []))P (pre_pcfg([a], [a], [])) = 1

Figure 3 Probability equations for prefix “a”

Although we know that the set of probability equations in Figure 3 are made true if weassign the probabilities defined by the distribution semantics[13] to X, Y, Z and W, we do notknow their actual values. To know their actual values, we need to compute them by solving
the equations. Fortunately, equations are linear in the P-variables X, Y, Z and W and easilysolvable.
By substituting θs→ss = 0.4 and θs→a = 0.39 for the equations and solving them, we
obtain X = Y = 0.5, P (pre_pcfg([s, s], [a], [])) = Z = 0.5 and W = 1, respectively. Hence theprefix probability of “a” is 0.5. Note that this prefix probability is larger than the probabilityof “a” as a sentence which is 0.3. This is because the prefix probability of “a” is the sum of
the probability of sentence “a” and the probabilities of infinitely many sentences extending“a”.
By looking at the set of probability equations in Figure 3 more closely, we can understandthe way our approach computes prefix probabilities in PCFGs. For example, consider
Z = P (pre_pcfg([s, s], [a], [])) and the equation Z = W · θs→a + Z · θs→ss . We can expand thesolution Z into an infinite series:
Z

=

1
2
W · θs→a = (1 + θs→ss + θs→ss+ · · · )W · θs→a
1 − θs→ss

It is easy to see that this series represents the probability of infinitely many leftmost
derivations of prefix “a” from nonterminals “s s” by partitioning the derivations based on
the number of applications of rule s → s s, i.e. 1 for no application (s s ⇒s→a a s), θs→ss foronce ( s s ⇒s→ss s s s ⇒s→a a s s) and so on10 .

3.3

Properties of explanation graphs generated by a prefix parser

Let PG be a PCFG and PG’ its backbone CFG. Also let DB PG be a prefix parser for PG
obtained by replacing the values/3 declaration in DB 0 in Figure 1 with an appropriate
set of values/3 declarations encoding PG. In this section, we first prove that a necessary
and sufficient condition under which a prefix parser DB PG generates cyclic explanationgraphs. We then prove that DB PG always generates a system of linear equations for prefix
probabilities. Finally we prove that the linear system is solvable by matrix operation under
our assumptions on PCFGs.

9values(s,[[s,s],[a],[b]],set@[0.4,0.3,0.3]) in the program sets θs→ss = P (msw(s, [s, s])) = 0.4,
θs→a = P (msw(s, [a])) = 0.3 and θs→b = P (msw(s, [b])) = 0.3 respectively.
10
Recall that we assume that PCFGs are consistent. So the sum of probabilities of sentences derived from“s” is 1. Consequently for example we may ignore s in “a s” when computing the probability of prefix“a” derived from “a s”.

Taisuke Sato and Philipp Meyer

7

I Theorem 1. Let G` = pre_pcfg(`) be a goal for a prefix ` = [w1 , . . . , wN ] in PG’
and Exp(G` ) an explanation graph for G` generated by DB PG . Suppose there is no uselessnonterminal in PG’. Then there exists a cyclic explanation graph Exp(G` ) if-and-only-if theleft-corner relation of PG’ is cyclic.
Proof. Suppose Exp(G` ) is cyclic. Then some defined goal pre_pcfg([a|β],`0 ,`2 ) witha nonterminal “a” must call itself as a descendant in Exp(G` ) where `0 and `2 are sublistsof `. So an SLD derivation exists from :-prefix_pcfg([a|β],`0 ,L2),K to its descendant:-prefix_pcfg([a|β],`0 ,L2’),K’ that contains no return of goals because the list `0 is∗∗preserved. Consequently there is a corresponding leftmost derivation s ⇒ aδ ⇒ aδ 0 by PG’,
the backbone CFG of PG. So the left-corner relation is cyclic.
Conversely suppose the left-corner relation of PG’ is cyclic. Then there is a nonterminal“a” such that a →L a. As there is no useless nonterminal by our assumption, there is a∗∗∗
leftmost derivation starting from “s” such that s ⇒ γaδ ⇒ γaδ 0 ⇒ w1 . . . wN for somesentence w1 , . . . , wN . In what follows, for simplicity we assume that γ is empty (butgeneralization is straightforward). Let `0 = w1 , . . . , wj (j ≤ N ) be a prefix derived from awhose partial parse tree has a as the root and no a occurs below the root a. Then it is easy
to see that the tabled search for all SLD proofs of G`0 generates Exp(G`0 ) containing a goal
prefix_pcfg([a|β],`0 ,[]) which is an ancestor of itself. So Exp(G`0 ) is cyclic.
J
Let Exp(G` ) be an explanation graph for G` . We introduce an equivalence relation A ≡ Bover defined goals appearing in Exp(G` ): A ≡ B if-and-only-if A is an ancestor of B and viceversa. We partition the set of defined goals into equivalent classes [A]≡ . Each [A]≡ is called
an SCC (strongly connected component). We say that a defining formula H ⇔ B1 ∨ . . . ∨ Bh
is linear if there is no Bi = C1 ∧ . . . ∧ Cm ∧ msw1 ∧ . . . ∧ mswn (1 ≤ i ≤ h, 0 ≤ m, n) suchthat two defined goals, Cj and Ck (j 6= k), belong to the same SCC. Also we say Exp(G` ) is
linear if every defining formula in Exp(G` ) is linear.
I Lemma 2. No two defined goals in the body of a defining formula in Exp(G` ) belong to
the same SCC.
Proof. Let H ⇔ B1 ∨ . . . ∨ Bh be a defining formula in Exp(G` ). Suppose some Bi contains
two defined goals belonging to the same SCC. Looking at DB 0 in Figure 1, we know thatthe only possibility is such that H ⇔ B1 ∨ . . . ∨ Bh is a ground instantiation of the first(compound) clause about pre_pcfg/3:

pre_pcfg([a|β],`0 ,`2 ):msw(a,α),pre_pcfg(α,`0 ,`1 ),pre_pcfg(β,`1 ,`2 )(1)

and the two defined goals, pre_pcfg(α,`0 ,`1 ) and pre_pcfg(β,`1 ,`2 ), are in the same
SCC. In this case, since pre_pcfg(α,`0 ,`1 ) is a proved goal, `1 is shorter than `0 . On theother hand since pre_pcfg(β,`1 ,`2 ) is an ancestor of pre_pcfg(α,`0 ,`1 ) in Exp(G` ), `0
is identical to or a part of `1 , and hence `0 is equal to or shorter than `1 . Contradiction.
Therefore there is no such defining formula. Hence Exp(G` ) is linear.
J
I Theorem 3. Let Exp(G` ) be an explanation graph for a prefix ` generated by DB PG .
Exp(G` ) is linear.
Proof. Immediate from Lemma 2.

J8Tabling for infinite probability computation

We next introduce a partial ordering [A]≡  [B]≡ over SCCs by [A]≡  [B]≡ if-and-only-if
A is an ancestor of B but not vice versa in Exp(G` ). We then extend this partial ordering toa total ordering [A]≡ > [B]≡ over SCCs. Likewise we partition P-variables by the equivalence
relation: P (A)≡P (B) if-and-only-if [A]≡ = [B]≡ . We denote by [P (A)]≡ the equivalenceclass of P-variables corresponding to [A]≡ . By construction [P (A)]≡ s are totally orderedisomorphically to SCCs: [P (A)]≡ > [P (B)]≡ if-and-only-if [A]≡ > [B]≡ . In the following
we treat SCCs and P-variables as isomorphically stratified by this total ordering. We use
Eq([P (A)]≡ ) to stand for the union of sets of probability equations for defined goals in [A]≡ .
Notice that Eq([P (A)]≡ ) is a system of linear equations by Theorem 3 if we consider
P-variables in the lower strata as constants. Hence Eq(G` ) is solvable inductively from lower
strata to upper strata.
Now we prove that Eq([P (A)]≡ ) is always solvable by matrix operation under ourassumptions on PCFGs. Let “a” be a nonterminal in the backbone CFG PG’ and A adefined goal in Exp(G` ). Put A = pre_pcfg([a|β],`0 ,`2 ). Since A is a proved goal, A
successfully calls some ground goals Bj = pre_pcfg(αj ,`0j ,`1j ) shown in (1) where a → αj
is a CFG rule in PG’. By repeating a similar proof for Lemma 2, we can prove that thethird goal pre_pcfg(β,`1 ,`2 ) in the clause body in (1) does not belong to [A]≡ , the SCC
containing A. Thus [A]≡ > [pre_pcfg(β,`1 ,`2 )]≡ . So only some of the Bj s can possibly
belong to [A]≡ as far as A is concerned.
Let P (A1 ), . . . , P (AK ) be an enumeration of P-variables in [P (A)]≡ . Introduce a column
vector XA = (P (A1 ), . . . , P (AK ))T . It follows from what we have argued that we canwrite Eq([P (A)]≡ ) as a system of linear equations XA = M XA + YA where M is a K × K
non-negative matrix and YA is a non-negative vector whose component is a sum of P-variablesin the lower strata multiplied by constants. M is irreducible because in Exp(G` ), every goalin [A]≡ directly or indirectly calls every goal in [A]≡ . YA is non-zero because some Ai musthave a proof tree that only contains defined goals in the lower strata. For vectors U, V , wewrite U > 0 (resp. U ≥ 0) if every component of U is positive (resp. non-negative) andU ≥ V if U − V ≥ 0 where 0 is a zero vector.
I Theorem 4. Let PG be a consistent PCFG such that there is no epsilon rule and every
production rule has a positive selection probability. Also let DB PG be a prefix parser for
PG and Exp(G` ) an explanation graph for a prefix `. Suppose Eq([P (A)]≡ ) is a system of
linear equations for a defined goal A in Exp(G` ). Put [P (A)]≡ = {P (Ai ) | 1 ≤ i ≤ K} andwrite Eq([P (A)]≡ ) as XA = M XA + YA where XA = (P (A1 ), . . . , P (AK ))T . It has a uniquesolution XA = (I − M )−1 YA .
Proof. We prove that I − M has an inverse matrix. To prove it, we assume hereafter that
P-variables in [P (A)]≡ are assigned as their values probabilities defined by the distribution
semantics and hence all equations in Eq([P (A)]≡ ) are true.
By applying XA = M XA + YA k repeatedly to itself, we have XA = M k XA + (M k−1 +· · · + I)YA for k = 1, 2, . . . Since M , XA , and YA are non-negative, we have XA ≥ M k XA
and XA ≥ (M k−1 + · · · + I)YA for every k. On the other hand since {(M k−1 + · · · + I)YA }kis a monotonically increasing sequence of non-negative vectors bounded by XA , it converges
and so does {M k XA }k .
1kLet ρ(M ) be the spectral radius of M 11 . Suppose ρ(M ) > 1. In general ρ(M ) ≤ k M k k∞

11

ρ(M ) is the largest eigenvalue of M . As M is irreducible, the right eigen vector and the left eigen vector

Taisuke Sato and Philipp Meyer

holds for every k where k · k∞ is the matrix norm induced from the ∞ vector norm. It follows
from ρ(M )k ≤ k M k k∞ that limk→∞ k M k k∞ = +∞. Consequently since XA > 0 holds
because every proved goal has a positive probability from our assumption, some element of
M k XA goes to +∞, which contradicts the convergence of 
{M k XA }k . So ρ(M ) ≤ 1.
M k−1 + · · · + I
Suppose now ρ(M ) = 1. Then in this case, we note thatconverges tok k−1 kM
+ ··· + I
k−1
a positive matrix (proof omitted), and hence (M+ · · · + I)YA =
· kYA
k
k−1
diverges as k goes to infinity, which contradicts again the convergence of {(M+· · ·+I)YA }k .
−1
Therefore ρ(M ) < 1. So (I − M ) exists.
J
Note that XA = (I − M )−1 YA = (I + M + M 2 + · · · )YA . By further analyzing thematrix M , we understand that multiplying M by YA for example corresponds to growing
partial parse trees by one step application of production rules (reduce operation in bottom-up
parsing). Hence P (Ai ), a component of XA , is an infinite sum of probabilities and so is theprobability of the top prefix goal P (pre_pcfg(`)).
Summing up, we compute prefix probabilities for a PCFG PG as follows. Let DB be aprefix parser for PG and G = pre_pcfg(`) a goal for a prefix `.
[Step 1]: From G and DB, construct an explanation graph Exp(G).
[Step 2]: Extract the set of probability equations Eq(G) from Exp(G).
[Step 3]: Solve Eq(G) inductively from lower strata by matrix operation and obtain PDB (G),the prefix probability of `.
The above procedure is general and applicable to arbitrary (cyclic) linear explanationgraphs, not restricted to those generated by a PCFG prefix parser. We computed prefix
probabilities for PLCGs (probabilistic left-corner grammars) similarly to PCFGs, but weomit the detail due to space limitations.

4

Related work

Prefix probability computation is mostly studied about PCFGs [3, 15, 7]. Jelinek and
Lafferty [3] proposed a CKY like algorithm for prefix probability computation in PCFGs
in CNF (Chomsky normal form). Their algorithm does not perform parsing but instead
uses a single matrix whose dimension is the number of nonterminals which is constructedfrom a given PCFG. It runs in O(N 3 ) where N is the length of an input prefix. Stolcke[15] applied the Earley style parsing to compute prefix probabilities. His algorithm uses
a matrix of “probabilistic reflexive, transitive left-corner relation” computed from a given
PCFG, independently of input sentences similarly to [3]. Our approach differs from themin that it works for probabilistic logic programs and it deals with explanation graphs
constructed for each input prefix. Nederhof and Satta [7] generalized prefix probability
computation for PCFGs to infix probability computation for PCFGs. They also studied
prefix probability computation for a variant of PCFGs [8]. Nederhof et al. proposed prefix
probability computation for stochastic tree adjoining grammars [6].
Approximate computation of prefix probabilities is possible for example by the iterative
deepening algorithm used in ProbLog[2], but it is out of the scope of this paper.

associated with ρ(M ) are both positive by the Perron-Frobenius theorem.

910Tabling for infinite probability computation

5

Conclusion

We have proposed an innovative use of tabling: infinite probability computation based on
cyclic explanation graphs generated by tabled search in PRISM. Our approach generalizes
prefix probability computation in PCFGs and is applicable to probabilistic models describedby PRISM programs in general as well as PCFGs. In particular it is applicable to non-PCFG
probabilistic grammars such as PLCGs though we omitted the result of prefix computation
for PLCGs due to space limitations. We are developing a tool that generates a (cyclic)
explanation graph for a given goal and computes its probability by solving the system linear
equations associated with it. We expect that our approach provides a declarative way oflogic-based probabilistic modeling of cyclic dependencies.
References
1
2

3
4
5

6

7

8

9

10
11
12

13
14

J. K. Baker. Trainable grammars for speech recognition. In Proceedings of Spring Conference of the Acoustical Society of America, pages 547–550, 1979.
L. De Raedt, A. Kimmig, and H. Toivonen. ProbLog: A probabilistic Prolog and its
application in link discovery. In Proceedings of the 20th International Joint Conference on
Artificial Intelligence (IJCAI’07), pages 2468–2473, 2007.
F. Jelinek and J. Lafferty. Computation of the probability of initial substring generation
by stochastic context-free grammars. Computational Linguistics, 17(3):315–323, 1991.
C. D. Manning and H. Schütze. Foundations of Statistical Natural Language Processing.
The MIT Press, 1999.
T. Mantadelis and G. Janssens. Dedicated tabling for a probabilistic setting. In Proceedings of the 26th International Conference on Logic Programming (ICLP’10) (TechnicalCommunications), pages 124–133, 2010.
M. Nederhof, A. Anoop Sarkar, and G. Satta. Prefix probabilities from stochastic tree
adjoining grammars. In Proceedings of the 36th Annual Meeting of the Association for
Computational Linguistics (ACL’98), pages 953–959, 1998.
M. Nederhof and G. Satta. Computation of infix probabilities for probabilistic contextfree grammars. In Proceedings of the 2011 Conference on Empirical Methods in Natural
Language Processing (EMNLP’11), pages 1213–1221, 2011.
M. Nederhof and G. Satta. Prefix probability for probabilistic synchronous context-freegrammars. In Proceedings of the 48th Annual Meeting of the Association for Computational
Linguistics (ACL’11), pages 460–469, 2011.
F. Riguzzi and T. Terrance Swift. The PITA system: Tabling and answer subsumption
for reasoning under uncertainty. Theory and Practice of Logic Programming (TPLP), 11(45):433–449, 2011.
R. Rocha, F.M.A. Silva, and V.S. Costa. On applying or-parallelism and tabling to logic
programs. Theory and Practice of Logic Programming (TPLP), 5(1-2):161–205, 2005.
T. Sato. A glimpse of symbolic-statistical modeling by PRISM. Journal of Intelligent
Information Systems, 31(2):161–176, 2008.
T. Sato and Y. Kameya. PRISM: a language for symbolic-statistical modeling. In Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI’97), pages
1330–1335, 1997.
T. Sato and Y. Kameya. Parameter learning of logic programs for symbolic-statisticalmodeling. Journal of Artificial Intelligence Research, 15:391–454, 2001.
T. Sato and Y. Kameya. New Advances in Logid-Based Probabilistic Modeling by PRISM.
In L. De Raedt, P. Frasconi, K. Kersting, and S. Muggleton, editors, Probabilistic Inductive
Logic Programming, pages 118–155. LNAI 4911, Springer, 2008.

Taisuke Sato and Philipp Meyer

15
16

17
18
19

20

A. Stolcke. An efficient probabilistic context-free parsing algorithm that computes prefix
probabilities. Computational Linguistics, 21(2):165–201, 1995.
H. Tamaki and T. Sato. OLD resolution with tabulation. In Proceedings of the 3rd International Conference on Logic Programming (ICLP’86), volume 225 of Lecture Notes in
Computer Science, pages 84–98. Springer, 1986.
D. S. Warren. Memoing for logic programs. Communications of the ACM, 35(3):93–111,
1992.
C. S. Wetherell. Probabilistic languages: a review and some open questions. Computing
Surveys, 12(4):361–379, 1980.
N.-F. Zhou, Y. Kameya, and T. Sato. Mode-directed tabling for dynamic programming, machine learning, and constraint solving. In Proceedings of the 22th International Conferenceon Tools with Artificial Intelligence (ICTAI-2010), 2010.
N.-F. Zhou, T. Sato, and Y.-D. Shen. Linear tabling strategies and optimization. Theory
and Practice of Logic Programming (TPLP), 8(1):81–109, 2008.

11