Logic-based Probabilistic Modeling
Taisuke Sato
Tokyo Institute of Technology, Ookayama Meguro Tokyo Japan,
http://sato-www.cs.titech.ac.jp/

Abstract. After brieﬂy mentioning the historical background of PLL/SRL,
we examine PRISM, a logic-based modeling language, as an instance of
PLL/SRL research. We ﬁrst look at the distribution semantics, PRISM’s
semantics, which deﬁnes a probability measure on a set of possible Herbrand models. We then mention characteristic features of PRISM as atool for probabilistic modeling.

1

Introduction

Logic has long been considered as a discipline concerning certainty with major attention on deductive inference. However recent developments in machinelearning and other related areas are expanding the role of logic from a vehicle
for deductive inference to the one for probabilistic knowledge representation andstatistical inference, and has spawned an interdisciplinary subﬁeld of machinelearning called PLL (probabilistic logic learning) and/or SRL (statistical relational learning) that combine logic and probability for probabilistic modeling1 .
As its name suggests, PLL[1] has LP (logic programming) and ILP (inductive
logic programming) as its backbone. PLL however adds to LP/ILP probability
and makes logical formulas random variables taking true and false probabilistically. With such probabilistic formulas we can express logical yet probabilistic
phenomena such as gene inheritance cleanly at predicate level. Moreover probabilities statistically learned from real data makes it possible to evaluate how
probable a given formula is in the real world.
Furthermore by amalgamating with probability, LP/ILP, or more generally
logic, acquires an ability to cope with missing information. Suppose we are goingfor a picnic tomorrow (P ) if the weather is clear (W ). Also suppose we have toprepare a lunch box tonight (L) if we go for a picnic tomorrow (P ). Then it
follows by deduction that we have to prepare a lunch box tonight if the weather
is clear tomorrow (L ⇐ W ). However we do not know the truth value of W ,tomorrow’s weather. Should we prepare a lunch box tonight? In such a case apurely logical inference would completely get stuck as we do not know the truth
value of W . The amalgamated system on the other hand will be able to help
our decision on whether we should prepare a lunch box or not by looking at theprobability associated with W .
1

SRL seems more often used than PLL now.

2

Taisuke Sato

SRL [2], independently of PLL, originated from uncertainty reasoning in BNs(Bayesian networks)[3]. BNs are a graphical representation of joint distributionsin terms of directed acyclic graphs. BNs are powerful. First they can visualize complex dependencies among random variables graphically as parents-childnodes. Second they allow us to perform various types of probabilistic inference
and parameter learning such as maximum likelihood inference, MAP (maximum
a posteriori) inference and Bayes inference. These inferences are eﬃciently carried out by well-developed algorithms including the celebrated BP (belief propagation) algorithm. Also there are ones for structure learning as well that learn a
directed graph from data. As a result BNs are used as one of the standard tools
for handling uncertainty and applied to bioinformatics, natural language processing, speech recognition, planning, diagnosis, datamining, decision supportand so on.
Nevertheless from a viewpoint of knowledge representation in AI, BNs are
primitive. Basic assertions available in BNs are limited to X = x type such that
X is a random variable and x is a value. In other words, BNs are a propositional
system where X = x is a propositional variable which is true with probability
P (X = x). BNs’ lack of logical variables, relations and quantiﬁers, the hallmark
of predicate calculus, implies we have no way to express (probabilistic) rules suchas “a friend of a friend is a friend with probability 0.3.” One might say BNs isa low level language just like machine code.
The low-levelness of BNs prompted the emergence of the KBMC (knowledgebased model construction) approach in the nineties. Initially KBMC built BNs
from a knowledge base using a high level language mostly as a matter of convenience. But later it evolved to SRL which upgrades BNs themselves by explicitly introducing variables and relations and/or by embedding them in a richer
programming language be it logical or otherwise. Variables in such a language
recover an ability to express general patterns. More importantly the introductionof relations opened a new dimension for feature-based probabilistic modeling2
by using relations themselves as new features [2].
Currently SRL and PLL are moving toward uniﬁcation but it remains tobe seen whether they are eventually uniﬁed or not. In this talk, we look intosome details of PRISM [4–6]3 as an instance of ongoing PLL/SRL research.
PRISM is a probabilistic extension of Prolog with a declarative semantics called
distribution semantics which is a probabilistic generalization of the standard
least model semantics of logic programs [7]. Despite the fact that PRISM adopts
a single data structure, a single probability computation algorithm and a single
parameter learning algorithm, all independent of target models, it universallycovers generative models from Bayesian networks to probabilistic grammars with
eﬃciency supported by the PRISM architecture. In what follows we review the2

Features are a function from an input to a real number that characterizes the input.
In statistical natural language proceeding for example, often an individual word isused as a feature that returns 1 if the input contains the word, else 0.
3
http://sato-www.cs.titech.ac.jp/prism/index.html

Logic-based Probabilistic Modeling3

distribution semantics in detail and then illustrate some aspects of PRISM froma machine learning point of view.

2

Probabilistic semantics

2.1

The basic principle

The distribution semantics, PRISM’s declarative semantics, is a probabilistic
generalization of the least model semantics in logic programming. Before proceeding however, we look back on a fundamental theorem which underlies it.
When logic and probability are combined, probabilities P (ϕ) are assigned toformulas ϕ. However since probabilities have to respect Kolmogorov’s axioms
while formulas obeys their own logical laws, it is not self-evident how to coherently assign probabilities to formulas4 . We here review Fenstad’s representation
theorem [8] in our context which states a formal relationship between formulas
and their probabilities.
We introduce some notations. Let L be a countable ﬁrst order language
without equality and ω be a model on a certain ﬁxed domain U5 . We assume
variables are indexed by natural numbers N. We denote by ϕ[ω] {a ∈ UN |
ω |=a ϕ(xi , . . . , xj )} where a is an assignment for the variables such that a(i) is
assigned to xi etc. ϕ[ω] denotes the set of sequences of elements from U whose
substitution for the variables in ϕ makes ϕ true in the model ω.
Theorem 1 (Fenstad 67). Let ϕ, φ be formulas in L. Suppose probabilities
assigned to formulas satisfy the following.
(i) P (ϕ ∨ φ) + P (ϕ ∧ φ) = P (ϕ) + P (φ)(ii) P (¬ϕ) = 1 − P (ϕ)(iii) P (ϕ) = P (φ), if  ϕ ↔ φ(iv) P (ϕ) = 1, if  ϕThen there is a σ-additive probability measure λ on the set Ω of models on U
for L. There is also for each ω ∈ Ω, a probability µω on the sets of ϕ[ω]’s suchthat
P (ϕ) =µω (ϕ[ω]) dλ(ω).
S

When the domain U is ﬁnite and ϕ is closed, the above theorem reduces toλ({ω}).
P (ϕ) =
ω|=ϕSo in this case, the probability is given as the sum of probabilities of the models
that satisfy the formula.
4

In addition since probabilities are supposed to be used in a probabilistic model, theyneed to be computable and learnable from data.
5
U can be taken as a Herbrand universe for L.

4

Taisuke Sato

Fenstad’s theorem strongly suggests to us that if we assign probabilities toformulas in a reasonable way, we should ﬁrst deﬁne a probability measure overmodels. The distribution semantics[4] we explain next follows this idea.

2.2

The distribution semantics

Formally a PRISM program DB is a set of deﬁnite clauses. We write it as
DB = F ∪ R where F is a set of ground atoms corresponding to primitive
probabilistic events such as coin tossing and R is a set of rules (deﬁnite clauses).
We assume no atom in F uniﬁes with a head appearing in R.
We consider the set of Herbrand models (we often call them just worlds
for simplicity) ΩDB for DB and deﬁne a probability measure PDB over ΩDB
as follows. First enumerate ground atoms in F like A1 , A2 , . . . and identify a
Herbrand interpretation of F with a binary inﬁnite vector(1, 0, . . .) that speciﬁes
A1 is true (1), A2 is false (0) and so on. Let ΩF = i {0, 1}i be the set ofsuch binary vectors. We give ΩF a product topology where {0, 1} has a discrete
topology. Also let PF be a base distribution which is any probability measure on
the σ-algebra generated by open sets of ΩF .
Consider an arbitrary subset F  of F . DB  = F  ∪ R has the least Herbrandmodel M(DB  ) deﬁned as follows. Let T be the immediate consequence operator[7]. It is applied to a set I of ground atoms and deﬁned by T (I) = {A | A ⇐ B1 ∧· · · ∧ Bh (h ≥ 0) is a ground instance of a clause in DB  and {B1 , . . . , Bh } ⊆ I}.
k
Put I∞ = ∪∞k=0 T (∅) and verify I∞ is the least ﬁxpoint of T , i.e. T (I∞ ) = I∞ .
Deﬁne a Herbrand model M(DB  ) by a ground atom A is true in M(DB  )iﬀ A ∈ I∞ 6 . M(DB  ) is called the least Herbrand model of DB  7 . Using thisM(DB  ) = M(F  ∪ R) as a model parameterized by F  , a subset of F , we can
extend PF by Kolmogorov’s extension theorem to a probability measure PDB on
the σ-algebra generated by open sets in ΩDB with a product topology (see [5]for details). We consider PDB as the denotation of PDB (distribution semantics).
From the construction of PDB , it is easy to see every closed formula ϕ ismeasurable when considered as a function from ΩDB to {0, 1} such thatϕ(ω) =

1 if ω |= ϕ
0 elseand hence we deﬁne the probability PDB (ϕ) of ϕ as PDB (ϕ = 1). Probabilities
thus deﬁned satisfy the conditions from (i) to (iv) of Fenstad’s representation
theorem. Also we can see the distribution semantics is a generalization of theleast model semantics because if the base distribution PF puts all probability
mass on one Herbrand model making F  ⊆ F true, PDB also will put all probability mass on the least Herbrand model of F  ∪ R.
6
7

Proof theoretically DB   A iﬀ A ∈ I∞ for every ground atom A.
In logic programming, the least Herbrand model is considered as the canonical denotation of deﬁnite clause programs.

Logic-based Probabilistic Modeling

3

5

PRISM: from semantics to implementation

The distribution semantics considers PDB as the denotation of a program DB =F ∪ R. PDB always exists, uniquely, for any set F of ground atoms, any basemeasure PF on F and any set R of deﬁnite clauses. Such “semantic robustness”
is one of the unique features of PRISM compared to other systems dealing with
inﬁnite domains and inﬁnitely many random variables [2, 1].
However deﬁning a semantics is one thing and implementing it is another.
When implementing the distribution semantics as PRISM as an extension of
Prolog, we ﬁx F and restrict the base measure PF to a denumerable product ofof Bernoulli distributions to make PDB computable in probabilistic modeling.
More concretely we introduce ground atoms called msw atoms8 representing
a probabilistic choice that take the form msw(i, v) where i is a choice name andv is a chosen value and both are ground terms. We ﬁx the set Fmsw of groundmsw atoms and give a (-n inﬁnite) joint distribution Pmsw (·) in such a way that
if a probabilistic choice named i has k choices v1 , . . . , vk , correspondingly, oneof nmsw(i,v1 ), . . . , msw(i,vk ), say msw(i,vj ) is exclusively true with probabilityθvj = Pmsw (msw(i,vj )) ( j θvj = 1). msw(i,v) is the only probabilistic built-in
predicate in PRISM and used to simulate simple probabilistic events such as coin
ﬂipping and dice throwing. The role of deﬁnite clauses in R then is to organize
such simple events into a complex event corresponding to our observation in
the real world. The following is a PRISM program describing the inheritance of
ABO blood type. As you see a PRISM program is just liken an ordinary Prolog
program9 .

values x(gene,[a,b,o],[0.5,0.2,0.3]).
bloodtype(P) :genotype(X,Y),( X=Y -> P=X ; X=o -> P=Y ; Y=o -> P=X ; P=ab ).
genotype(X,Y) :msw(gene,X), msw(gene,Y).
Fig. 1. ABO-blood type program DB1

The ﬁrst clause values x(gene,[a,b,o],[0.5,0.2,0.3]) is a PRISM declaration specifying Fmsw and Pmsw (·). It introduces a set of mutually exclusive
atoms {msw(gene, a), msw(gene, b), msw(gene, o)} corresponding to a probabilistic choice named gene having three possible outcomes a, b and o, representing
three genes determing one’s ABO blood type. They are true with 0.5, 0.2 and0.3 respectively as indicated by the values x declaration. The second clause is89

msw stands for “multi-ary random switch.”
Some familiarity with Prolog is assumed here.

6

Taisuke Satoa rule specifying the relationship between genotypes (pair of genes) and phenotypes (ABO blood type, a, b, o, ab). For example if a genotype is (a, b), theblood type is ab. The last clause simulates the inheritance of two genes, one fromeach parent. Sampling msw(gene,X) returns X = a with probability 0.5 etc. In
PRISM, textually diﬀerent occurrences of msw atoms in a program are treatedas independent. So msw(gene,X) and msw(gene,Y) are independent. This program as a whole describes how bloodtype(P), our observation, is generated bya sequential choices made by msw(gene,·) atoms.
Once loaded into computer memory by the PRISM system, DB1 can answer
various questions such as the probability of bloodtype(a). PRISM computes
it by way of search and the resulting propositional AND/OR formula called
an explanation graph. To be precise it ﬁrst performs an exhaustive SLD searchfor ?- bloodtype(a) and collects all conjunctions E1 , E2 and E3 such that
Ei , DB1  bloodtype(a) (i = 1, 2, 3) where E1 = msw(gene, a) ∧ msw(gene, a),E2 = msw(gene, a) ∧ msw(gene, o) and E3 = msw(gene, o) ∧ msw(gene, a). We
call each Ei an explanation for bloodtype(a). Since the search is exhaustive,
bloodtype(a) ⇔ E1 ∨ E2 ∨ E3 holds with probability one in terms of PRISM’s
semantics. In addition since E1 , E2 and E3 are obtained by mutually exclusive
proof paths, they are mutually exclusive as well. Also recall that msw atoms are
independent. Putting these together PDB1 (bloodtype(a)) is calculated as
PDB1 (bloodtype(a) | θa , θb , θo ) = PDB1 (E1 ∨ E2 ∨ E3 )= PDB1 (E1 ) + PDB1 (E2 ) + PDB1 (E3 )= θa2 + θa θo + θo θa= 0.45where θa = Pmsw (msw(gene, a)) = 0.5, θb = Pmsw (msw(gene, b)) = 0.2 and θo =Pmsw (msw(gene, o)) = 0.310 as speciﬁed by values x(gene,[a,b,o],[0.5,0.2,0.3]).

4

Statistical abduction

Although PRISM is an extension of Prolog, their inferences are of diﬀerent type.
Prolog is a logical language for (controlled) deduction whereas PRISM is a logicallanguage for (controlled) abduction. In general abduction refers to “inference
to the best explanation.” Given a knowledge base K, a set of formulas, andan observation O, we seek for the best explanation E in abduction such thatK ∧ E  O and K ∧ E is consistent. The exhaustive search for explanations forthe given goal in PRISM is exactly an abductive inference. One of the problems
in abduction is that there can be many explanations just like a student has many
excuses for not doing homework. In the blood type example, PRISM abduces
three explanations E1 , E2 , and E3 for the observation bloodtype(a) but in
10

PDB1 (·) is an extension of Pmsw (·), so PDB1 (E1 ) = Pmsw (msw(gene, a)∧msw(gene, a)) =Pmsw (msw(gene, a))2 = θa 2 .

Logic-based Probabilistic Modeling7

the case of parsing where observations are sentences, the knowledge base is agrammar and an explanations is a parse tree, we often have tens of thousandsof parse trees for one sentence. In the face of multiple explanations, we need tochoose somehow one of them as the best one.
Statistical abduction[9] resolves the problem of multiple explanations thatarises in abduction by introducing a probabilistic model P (·) connecting explanations E, a knowledge base K and an observation O. Using P (·) we choose themost probable E giving the highest P (E | O, K) such that K ∧ E  O. In thissense PRISM is not just a language for abduction but a language for statisticalabduction, and indeed the ﬁrst one with an ability to perform statistical inference to our knowledge. In PRISM the knowledge base is a program DB for which
the distribution semantics guarantees PDB (iﬀ(DB )) = 111 [5]. Accordingly
E ∗ = argmaxE PDB (E | O, iﬀ(DB ))= argmaxE PDB (E ∧ O ∧ iﬀ(DB ))= argmaxE PDB (E ∧ iﬀ(DB ))= argmaxE PDB (E)holds. Thus seeking for the best explanation in statistical abduction is equivalent to Viterbi inference implemented in PRISM, giving E ∗ = E1 as the best
explanation for bloodtype(a).

5Probabilistic modeling

So far we have been looking at theoretical aspects of PRISM. Here we examine PRISM as a practical tool for probabilistic modeling. As a modeling tool,
the most salient feature of PRISM is model speciﬁcation by (recursive) deﬁnite
clauses12 , which results in– universality (for generative models and their parameter learning)– high level speciﬁcation (small amount of coding) and– interpretability (what the system does is readable to humans).
The ﬁrst point is due to the fact that PRISM can simulate, as an extensionof Prolog, a non-deterministic Turing machine in which non-determinacy is resolved by a probabilistic choice, and in addition, PRISM has a generic routine(the graphical EM algorithm [5]) for parameter learning. The universality covers
PCFGs (probabilistic context free grammars) [11] as well as BNs [3]. A PCFG
is a CFG with probabilities assigned to grammar rules. It generates a sentence
by repeatedly making a probabilistic choice of a grammar rule and expanding a11

iﬀ(DB ) is the if-and-only-if completion of DB . Deﬁnite clauses with a common headsuch as A ⇐ B and A ⇐ C in a program are lumped together to the if-and-only-if
form A ⇔ B ∨ C in iﬀ(DB ).
12
Actually general clauses (those that may contain negative goals in the clause body)are allowed under a certain condition[10].

8Taisuke Satononterminal with it until no nonterminal remains. Since there is no upper limiton the number of applications of grammar rules, if there is a recursive rule, we
use a countably many iid random variables. Hence ﬁnite probabilistic models
such as BNs or otherwise cannot express PCFGs though they are the most basic
class of probabilistic grammars [12].
The second point owes to the power of ﬁrst-order expressions such as variables, terms, relations and recursion. For example HMMs (hidden Markov models) which are a class of stochastic automata very popular in machine learning
can be expressed in three lines (together with three line declarations) as shownin Fig. 3.

end

a,b
s0

s1
a,b

a,b

a,b

Fig. 2. An HMM

values x(init,[s0,s1],[0.5,0.5]).
values x(out( ),[a,b],[0.5,0.5]).
values x(trans( ),[s0,s1,end],[0.7,0.2,0.1]).
hmm(L):- msw(init,S0),hmm(S0,L).
hmm(S,L):- msw(trans(S),NextS),(NextS=end -> L=[] ; msw(out(S),C), L=[C|Cs], hmm(NextS,Cs)).
Fig. 3. DB hmm for the HMM in Fig.2

We hope the program DB hmm in Fig. 2 is self-explanatory but add comments13 .
This program generates indeﬁnitely long lists of a and b. There are two states s0
and s1 both of which can be an initial state. After choosing the initial state, itgoes into inﬁnite recursion, while outputting a or b on transition, until a choiceof transition to end, the ﬁnal state, is made probabilistically.
13

values x(out( ),[a,b],[0.5,0.5]) is a template where the underscore
replaced with any term.

can beLogic-based Probabilistic Modeling9?- prob(hmm([a,a,b])).
Probability of hmm([a,a,b]) is: 0.012345679012346?- viterbif(hmm([a,a,b])).
hmm([a,a,b]) <= hmm(s0,[a,a,b]) & msw(init,s0)
hmm(s0,[a,a,b]) <= hmm(s1,[a,b]) & msw(trans(s0),s1) & msw(out(s0),a)hmm(s1,[a,b]) <= hmm(s1,[b]) & msw(trans(s1),s1) & msw(out(s1),a)hmm(s1,[b]) <= hmm(s1,[]) & msw(trans(s1),s1) & msw(out(s1),b)hmm(s1,[]) <= msw(trans(s1),end)?- learn([hmm([a,a,b]),hmm([b,a]),hmm([b,b]),hmm([a,b,a])]).
...
#em-iterations: 0.(18) (Converged: -12.908717468)
Switch init: s0 (p: 0.000005604) s1 (p: 0.999994396)
Switch out(s0): a (p: 0.499954371) b (p: 0.500045629)
Switch out(s1): a (p: 0.500019760) b (p: 0.499980240)
Switch trans(s0): s0 (p: 0.430352826) s1 (p: 0.000001065) end (p: 0.569646108)
Switch trans(s1): s0 (p: 0.573218835) s1 (p: 0.426780543) end (p: 0.000000623)

Fig. 4. Running DB hmm

Fig. 4 is a sample session of DB hmm . After loading, we issue ?-prob(hmm([a,a,b]))to compute the probability of hmm([a,a,b]). Next we ask what is the most probable state transition sequence (Viterbi inference) for generating hmm([a,a,b]).
The answer is given as a calling sequence (in Prolog) of subgoals. Finally, we learn
parameters from a list of observations {hmm([a, a, b]), hmm([b, a]), hmm([b, b]), hmm([a, b, a])}by invoking the graphical EM algorithm using learn/1. After 18 iterations
it converged with log-likelihood −12.908717468, giving parameters as listed.
“Switch init” signiﬁes the parameters are for msw(init,·).
We remark that it is straightforward to extend and modify, say merge witha PCFG, the above skeletal program to one’s purpose. When the user modiﬁes
his probabilistic model, it often happens that he has to start from designing a
new data structure all over again. Since PRISM adopts a single data structure(explanation graphs), there is no need for a new data structure. All you need tochange when you change your model is the speciﬁcation part alone, which is alabor saving aspect of PRISM.
The third point, interpretability, is of particular importance in practice. Eventually the outcome of our analysis by probabilistic modeling must be transferred
to non-experts. However think of non-generative
probabilistic models speciﬁed
by “weights” wi like P (y | x) ∝ exp( i wi fi (x, y)). It would be very hard to
explain the meaning of those weights to non-experts, and especially so when
there are a huge number of weights like in statistical natural language processing. On the contrary, logic-based probabilistic modeling uses logical formulas to10

Taisuke Sato

specify models, which seem more readable and more meaningful to non-experts
than weights, though we admit logical formulas themselves might be an obstacle.
Last but not least, we comment on complexity. PRISM is a high-level modeling language and models can be described succinctly as a PRISM program.
However one might ask if the ease of modeling sacriﬁces eﬃciency. The answer ispossibly so but marginally. Due to the complexity analysis of representative models [5], HMMs, PCFGs and BNs can be computed in the same time complexity
as specialized algorithms (the Baum-Welch algorithm for HMMs, the InsideOutside algorithm for PCFGs, BP for BNs [13]). The reason is that explanationgraphs, PRISM’s data structure, realize structure-sharing and probabilities andexpectations (needed for parameter learning) are computed by dynamic programming exploiting such structure-sharing. The real issue here is the trade oﬀ
between general data structure for every model and specialized data structure
for a speciﬁc model. PRISM lies on the general end of this scale. It constructs
explanation graphs using pointers as their size depends on a model and dataand is unknown beforehand in general. This causes a disadvantage in computational eﬃciency. We believe however the ﬂexibility can compensate for such a
disadvantage and implementation eﬀorts can make it minimal.

6

Concluding remarks

We reviewed the historical background of PLL/SRL and examined PRISM as
an instance of PLL/SRL research. It is a logic-based modeling language we havebeen developing in the past decade and provides a general tool for generativemodeling in machine learning. As an extension of Prolog, it subsumes Prolog andfurthermore has the ability to learn parameters from data based on an abductive
framework called “statistical abduction.” We omitted most of computational
details but they can be reached by [4, 5, 14, 6]. Also omitted is variational Bayes
which is the latest feature of PRISM for Bayesian inference [15].

References
1. De Raedt, L., Kersting, K.: Probabilistic inductive logic programming. In De
Raedt, L., Frasconi, P., Kersting, K., Muggleton, S., eds.: Probabilistic Inductive
Logic Programming - Theory and Applications. Lecture Notes in Computer Science. Springer (2008) 1–27
2. Getoor, L., Taskar, B., eds.: Introduction to Statistical Relational Learning. MIT
Press, Cambridge, MA (2007)
3. Pearl, J.: Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann (1988)
4. Sato, T.: A statistical learning method for logic programs with distribution semantics. In: Proceedings of the 12th International Conference on Logic Programming(ICLP’95). (1995) 715–729
5. Sato, T., Kameya, Y.: Parameter learning of logic programs for symbolic-statisticalmodeling. Journal of Artiﬁcial Intelligence Research 15 (2001) 391–454

Logic-based Probabilistic Modeling11

6. Sato, T., Kameya, Y.: New Advances in Logid-Based Probabilistic Modeling by
PRISM. In De Raedt, L., Frasconi, P., Kersting, K., Muggleton, S., eds.: Probabilistic Inductive Logic Programming. LNAI 4911, Springer (2008) 118–155
7. Lloyd, J.W.: Foundations of Logic Programming. Springer-Verlag (1984)
8. Fenstad, J.E.: Representation of probabilities deﬁned on ﬁrst order languages.
In Crossley, J.N., ed.: Sets, Models and Recursion Theory. North-Holland (1967)
156–172
9. Sato, T., Kameya, Y.: Statistical abduction with tabulation. In Kakas, A., Sadri,F., eds.: Computational Logic: Logic Programming and Beyond. LNAI 2408,
Springer (2002) 567–587
10. Sato, T., Kameya, Y., Zhou, N.F.: Generative modeling with failure in PRISM.
In: Proceedings of the 19th International Joint Conference on Artiﬁcial Intelligence(IJCAI’05). (2005) 847–852
11. Wetherell, C.S.: Probabilistic languages: a review and some open questions. Computing Surveys 12(4) (1980) 361–379
12. Manning, C.D., Schütze, H.: Foundations of Statistical Natural Language Processing. The MIT Press (1999)
13. Sato, T.: Inside-Outside probability computation for belief propagation. In: Proceedings of the 20th International Joint Conference on Artiﬁcial Intelligence (IJCAI’07). (2007) 2605–2610
14. Zhou, N.F., Sato, T., Shen, Y.D.: Linear tabling strategies and optimization.
Theory and Practice of Logic Programming 8(1) (2008) 81–109
15. Sato, T., Kameya, Y., Kurihara, K.: Variational bayes via propositionalized probability computation in prism. Annals of Mathematics and Artiﬁcial Intelligence,
to appear.