Modeling Scienti c Theories as PRISM
Programs
Taisuke SATO1
Abstract. PRISM is a new type of symbolic-statisticalmodeling language which integrates logic programming andlearning seamlessly2. It is designed for the symbolic-statisticalmodeling of complex phenomena such as genetics and economics where logical/social rules and uncertainty interact,thus expected to be a valuable tool for scienti c discovery.
In this paper, we rst give a detailed account of PRISM
at propositional logic level. Then we concentrate, instead oflooking over various elds, on one subject, the inheritancemechanism of blood types. We show with experimental resultsthat various theories of blood type inheritance are describedas PRISM programs. Finally we suggest possible extensionsof PRISM. The reader is assumed to be familiar with logic
programming [8].

1Introduction

Scienti c discovery goes through a cycle of collecting observations, building a hypothesis and verifying it one way or
another. Oftentimes, observations are given as numbers anda hypothesis is expressed as a mathematical formula. Whenobservations include non-numeric aspects such as causal relationship among events however, we need a symbol manipulation language to be able to express our hypotheses. We alsoneed to cope with noise or uncertainty in the observations
that is inevitable in the real world.
PRISM is a formal knowledge representation language

for modeling scienti c hypotheses about discrete phenomena
which are governed by rules and probabilities [18, 19]. It isalso a programming language containing both logical elements
and probabilistic elements. Syntactically PRISM programs
are just an extension of logic programs in which the set offacts in a program has a probability distribution.
Semantically though, PRISM programs have a probabilistic version of possible worlds semantics (termed distributionalsemantics [18]) de ned on a certain probability space (of in nite dimension). Distributional semantics extends a standard
xed point semantics and views a PRISM program as specifying an in nite joint distribution for all possible xed points.3
1 Dept. of Computer Science, Tokyo Institute of Technology, 2-12-1^
Ookayama
Meguro-ku Tokyo Japan 152

2 An overview of PRISM was presented in [19]. It was based on

the rst implementation of PRISM and programming examples
were chosen from various elds.
xed point of a program is theset of all ground atoms provable from the program.

3 In logic programming, the (least)

ECAI 98 Workshop Programme.

Although PRISM has the ability of computing all computable functions, it must be emphasized that it is not justanother programming language but a programming languagewith learning ability, and it is this learning ability that distinguishes PRISM from other existing programming languages[19].
When given goals, i.e. conjunctive ground atoms which express our observations together with a program that models
them, PRISM tries to maximize the probability of the goals,
by rst identifying the relevant facts through backward reasoning from the goals, and then adjusting the statistical parameters associated with the facts, by a learning algorithm
based on the EM algorithm [20]. Although our learning isjust parameter learning by MLE (Maximum Likelihood Estimate) applied to computer programs, and already found in,for instance, HMM (hidden Markov model) in speech recognition and their applications to genetic information processing [17, 2], the point is that unlike the case of HMM where
the underlying model is restricted to probabilistic automata(type 3 grammars in the Chomsky hierarchy), PRISM applies MLE to the whole class of programs (type 0 grammars),and hence it covers not only HMMs but other well-known
symbolic-statistical model such as Bayesian network [14] andPCFG (Probabilistic Context Free Grammars) [3].
After getting parameter learning done, we let the program
compute, through forward reasoning from the learned distribution and facts, probabilities of atoms that represent phenomena we are interested in. This way PRISM provides us
with a tool to build a symbolic model of probabilistic phenomena and, after statistical tests, allows us to calculate reliablevalues of probabilities of their behaviors for the purposes ofprediction.
In the rest of this paper, we rst explain what PRISM is
like in detail (this is because the combination of symbolic execution and statistical learning looks new to the reader), thenproceed to describing a series of examples of scienti c theories
taken from the area of blood gene inheritance. We begin by asimple one, an ABO blood type program, then proceed to more
complex ones, for instance, the interplay of a social structure
and the genetic inheritance mechanism found in the Kariera
tribe which lived 80 years ago in the west Australia [21]. Finally we suggest future directions such as rule extraction fromdata which can be made possible by extending PRISM. The
reader is assumed to be familiar with logic programming [8].

22.1hx1 ; x2 ; y1; y2 i P

The basic idea of PRISM(D = x1 ; C = x2 ;H = y1 ; F = y2 )
0:72
0:18
0:08
0:02
0:0

DB

h0; 0; 0; 0i
h1; 0; 1; 0i
h0; 1; 1; 1i
h1; 1; 1; 1i

Modeling and forward reasoning

A PRISM program DB is written as F [ R where F is a setof unit clauses and R is a set of de nite clauses4. One salientfeature of PRISM is that F is given a probability distribution. We call it a basic distribution (of the DB).

othersOnce this distribution is obtained, we are able to calculate
whatever statistics we want. If we are interested in the joint
distribution of H and F , it becomes

The purpose of PRISM programs is to represent computational models of our observations by logical statistical means.
The R part is used to describe logical rules working behindthe observations whereas the F part models their uncertainty
as a probability distribution. Our assumption is that what we
observe is representable as an instance of some clause head in
the program.

hy1; y2 i P
h0; 0ih1; 0ih0; 1ih1; 1iDB

Suppose, for example, we observe phenomena concerning
our health, say a headache and a fever. We know from experience that drinking too much causes a headache while acold causes a headache and a fever simultaneously. If we use
ground atom H for having a headache, F for having a fever,
D for drinking too much and C for a cold, respectively, ourcausal knowledge about headaches and fever is formalized as
DB listed below5.

(H = y1 ; F = y2 )
0:72
:
0:18
0:0
0:10

This tells us for instance the probability of simultaneously
having a headache (H ) and a fever (F ) is 0:10.
2.2

Backward reasoning and statisticalparameters

In the previous example, PF was given a priori. In reality however, constructing reliable PF is a major problem. We showthat this can be done by statistical learning based on the combination of backward reasoning and the EM algorithm [20] as
follows.

DB = F [ RF = fD; C g
R = fH ( D; H ( C; F ( C g

We also know that drinking too much has little to do with acold, logically speaking. We therefore, instead of further seeking for a logical relationship between them, just introduce a
joint probability distribution (basic distribution) PF for them.

First we suppose, to make matters simple that drinking too
much and having a cold are statistically independent events.
So we write PF (D = x1 ; C = x2 ) = PF (D = x1 )PF (C = x2 ).
Second, we introduce statistical parameters i (i = 1; 2) suchthat PF (D = 1) = 1 and PF (C = 1) = 2 .

hx1; x2i P (D = x1; C = x2 )h0; 0i0:72
h1; 0i0:18
h0; 1i0:08
h1; 1i
0:02
FNow suppose we have observed, randomly, the state ofheadache (H ) and a fever (F ) three times and have recorded
them as h:H; :F i, hH; :F i and hH; F i. The probability ofthese observations happening is PDB (H = 0; F = 0)PDB (H =1; F = 0)PDB (H = 1; F = 1). We express this probability interms of 1 and 2 by using backward reasoning.

Here we think of ground atoms as random variables taking on
1 when they are true and 0 when they are false, and we use xi
for the value of an atom. The basic distribution is extended
to a one for all ground atoms D; C; H and F in the programby taking the i de nition of DB [8]Take for example PDB (H = 0; F = 0), the probability ofsimultaneously having no headache and no fever. Since distributional semantics allows us to logically reduce H to D _ C
and F to C respectively (this is backward reasoning), theprobability of hH = 0; F = 0i, i.e. that of :H ^ :F is equal
to the probability of :(D _ C ) ^ :C (, :D ^ :C ), which is(1 0 1 )(1 0 2 ). Likewise, the probability of hH = 1; F = 0i
is 1 (1 0 2 ) and that of hH = 1; F = 1i is 2 . Accordingly,
PDB (H = 0; F = 0)PDB (H = 0; F = 1)PDB (H = 1; F = 1) is
calculated as (1 0 1 )1 (1 0 2 )2 2 .

i (DB) = fH , D _ C; F , C g
and then by calculating the truth values of H and F fromthose of D and C 6. For example, when D is true and C isfalse, H is true and F is false. This forward reasoning gives
rise to the following joint distribution PDB for hD; C; H; F i
where yi denotes the sampled value of H or F .
4 To be precise, the program has three parts, the modeling part,2.3

the utility part and the control directives. We are talking here
only about the modeling part for simplicity.
5 We assume that rules in R are always correct.
6 The use of the i de nition is justi able because our semantics,
distributional semantics, is a probabilistic generalization of theleast model semantics of logic programs in which the i de nition
always holds. See [8, 18]
Machine Discovery

MLE and the EM algorithm

To statistically learn reliable values of 1 and 2 from theobservations, we appeal to the principle of maximizing theprobability of what we observed, i.e. MLE (Maximum Likelihood Estimate). So, we maximize (1 0 1 )1 (1 0 2 )2 2 bychoosing appropriate 1 and 2 , in this case 1 = 1=2 and
2T.SatoProb(bsw(coin, ,0)) = 1 0  because only two values, 1 and0, are allowed in the third argument of the bsw atom. Statistical parameters are set manually by a built-in predicate orare adjusted in the learning step by the EM algorithm.

2 = 1=3.

Unfortunately, generally speaking, MLE is a complex optimization problem and there is no easy way to calculate theparameter values giving the optimum, especially when there
are a large number of random variables. So when designing
PRISM , we decided to be satis ed with a local maximum,
and to apply the EM algorithm [20] to a class of basic distributions of very simple type (the EM algorithm is an iterativealgorithm for MLE which ts particularly well when somedata are missing).

In the learning step, the user is required to prepare teacher
data in the form of ground atoms. They must be randomly
sampled ones. Presently, two built-in predicates, learn/0 andlearn/1, are available. learn/0 is used when teacher data
are stored on a le, while learn/1 is used when teacher data
are supplied as a list of ground atoms. They all execute the
EM learning algorithm until saturation by repeatedly adjusting statistical parameters associated with bsw/3 and msw/3
atoms in a program to achieve a local maximum of the probability of the conjunction of teacher atoms.

Note that we have a kind of data missing situation in which
we observe only atoms that appear as a clause head but facts(sampled according to the basic distribution PF ) are neverknown, i.e. missing. We thus applied the EM algorithm to thisdata missing situation and derived a new learning algorithm
for our MLE problems [18].
This new learning algorithm can apply to any logic programs as long as each observation (ground atom) has a nite
number of explanations (proofs) from the DB7.

For the testing and calculation steps, prob/2 and cprob/3
are available as built-in predicates. prob(<f>,<p>) is used to
calculate the probability p of the positive boolean formula f.
cprob(<f-1>,<f-2>,<p>) is used for the conditional probability p of f-1 when f-2 is true.

Getting back to the observation of H and F , if we have alarge number of random samples of H and F , reliable valuesof 1 and 2 are obtainable by applying the MLE (our EM
learning algorithm) to the observed samples. And once thesereliable values have been obtained, we can calculate probabilities such as PDB (H = 1 j F = 1).
2.4

We now look at concrete PRISM programs. We show however only the modeling part of them, omitting the utility partand the control directives as they are of secondary importancecompared to the modeling part.
3

Our rst example is about ABO blood type [5, 6]. Let us explain modeling, sampling and learning in PRISM with thisexample.

PRISM programming

PRISM programming has the following four steps.
(1) Modeling We build a logical-statistical model, assum-

We already know that a child inherits genes, one from eachparent, and the pair (genotype) determines the child's blood
type (phenotype). In the case of ABO blood type, three genes(a, b and o) are involved; if the child inherits b from thefather and o from the mother, his/her blood type is B andso on (see Figure 1). We also know that the inheritanceis by chance. That is, for a randomly sampled child, whichgene is inherited from his/her parent is probabilistic, and theinheritance from the father and that from the mother are
statistically independent.

ing a basic distribution over facts.
(2) Learning Given (random) observations as ground atoms,
we adjust parameters associated with the basic distribution
by the EM learning algorithm.
(3) Testing After learning, we check our model against theobservations by statistical tests.
(4) Calculation (Prediction) We use our model to calculate various statistics, for instance, for predication.
Various built-in predicates are available for these steps. To
write a basic distribution in the modeling step, we use bsw/3
and msw/3. bsw(coin,2,1) for instance behaves as a randombinary switch named coin which is true (resp. false) if andonly if sampling coin at 2nd time returns 1 (resp. 0). Likewise msw(<name>,<time>,<value>) acts as a random multiple switch. These atoms are statistically independent randomvariables8.

3.1

Modeling

This inheritance mechanism that models random mating [6]is succinctly described as a PRISM program in Figure 2.
Practically speaking, PRISM programs are just Prolog
programs with special built-in predicates. So, the upper caseletters X,Y and P are logical variables and the rest are constants. More importantly, PRISM execution follows Prolog
convention9. top-to-bottom, clause-wise, and left-to-right goalwise. Although it happens that this program is non-recursive,
PRISM allows for recursion (see an HMM program in [19])10.

PRISM associates a statistical parameter with each bsw(and msw) atom as the probability of the atom being true.
Let  be such a statistical parameter for bsw(coin, ,1). It
means Prob(bsw(coin, ,1)) =  which also implicitly means
7 This restriction seems reasonable. In the real world, it is usual

9 PRISM has three execution modes: sampling mode, answer withthat we don't need to consider in nitely many causes of phenomena in question.
8 To be exact, if their names are di erent, they are independent. Ifthey have the same name but di erent times, they are independent
but identically distributed.

Machine Discovery

ABO blood type program

probability mode and answer with formula mode. We are focusing
on the sampling mode here.
10 Recursion introduces an in nite number of random variables,
even in such a simple case as modeling a Bernoulli sequence,
3

T.Satoa

In general, the sampling execution of a PRISM program

motherfatherab

DB = F [ R is stated as the sampling of DB as a (countably

in nite) random vector de ned by distributional semantics[18]11. However, since our random variables are just the namesake of ground atoms, we state a sampling process in termsof ground atoms for the sake of intuitiveness.

oAB

The sampling process starts with that of PF , the basic distribution over F . In the blood type example, F consists ofmsw(gene, ,a), msw(gene, ,b) and msw(gene, ,o). PRISM
implicitly associates two statistic parameters, 1 and 2 asfollows. They are initialized before computation by a built-in
predicate.

A

atom

child

b

msw(gene, ,a)msw(gene, ,b)msw(gene, ,o)

o

prob.
1
2
1 1 2

0 0

B
3.3
Figure 1.

ABO blood type model

A sampling of PF determines a set of true ground atoms
F 0  F , and the least model of F 0 [ R determines all truth
values of ground atoms appearing in DB. Thus, all groundatoms are sampled.

blood_type(a):- (gtype(a,a); gtype(a,o); gtype(o,a)).
blood_type(b):- (gtype(b,b); gtype(b,o); gtype(o,b)).
blood_type(o):- gtype(o,o).
blood_type(ab):- (gtype(a,b); gtype(b,a)).

This sampling process suggests bottom-up computation;
rst sample all bws/3 or msw/3 ground atoms (even if there arein nitely many of them) and then with the set of true atoms,
compute the least model. This is however not very amenable
to Prolog on top of which PRISM is currently implemented.
So while adopting Prolog's top-down execution order, we let
PRISM pretend that the sampling from PF has been done
before any computation starts and results are stored somewhere for retrieval.

gtype(X,Y):- gene(father,X),gene(mother,Y).
gene(P,a):- msw(gene,P,a).
gene(P,b):- msw(gene,P,b).
gene(P,o):- msw(gene,P,o).

Figure 2.

ABO blood type program

The declarative content of this program seems self-evident.
We have only to note that blood type(a) says a child has
blood type a, gtype(X,Y) says a child has the genotype <X,Y>
and gene(P,a) says gene a is inherited from P. The last threeclauses use msw atoms. In the current case, msw(gene,P,V)
stands for a statistically independent and identically distributed
ternary random switch named gene such that V takes on oneof fa, b, og as a sampled value at Pth time. If P = father
and V = a, it means the child happened to inherit gene a fromfather.
3.2

Sampling execution

Putting declarative content aside, there is a little intricacy inoperational semantics. Although PRISM has three execution
modes, we pay attention only to the sampling execution.

With this in mind, let us trace a computation process starting from a call to gtype(b,o). Like Prolog, the call unique
invokes the clause for gtype/2 with instantiations X=b and
Y=o, and a call to subgoal gene(father,b) occurs which theninvokes gene/2 clauses in turn from top-to-bottom. When the
topmost clause gene(P,a):- msw(gene,P,a) is invoked withP instantiated to father, a call to msw(gene, , ) takes place
for the rst time. PRISM samples the truth value of theatom, or more precisely, it samples a random variable whosename is gene and whose value is one of a, b or o. If the sampled value is b, PRISM memorizes msw(gene,father,b) as
the result of the sampling at the time father.
This sampling determines msw(gene,father,a) to be false
as side e ect (any later call to it will fail). So the second clausegene(P,b):- msw(gene,P,b) is invoked with P = father. The
call to msw(gene,father,b) ensues and succeeds because PRISM
remembers that msw(gene,father,b) was true on the rst
sampling. This success completes the goal gene(father,b).

DB as representing thein nite set of ground instantiations of clauses in DB.

11 In the formal setting, we always consider

which necessitates the construction of a probability space withan in nite dimension [18].
Machine Discovery

Top-down execution as sampling

4

T.SatoPRISM then tackles the second subgoal gene(mother,o).
This subgoal eventually causes a second sampling of the random variable gene, because time stamp mother is di erent
from father used before. If this sampling returns o, gene(mother,o)will be exclusively true, resulting in the success of the call to
gtype(b,o). Else gene(mother,o) will fail and so will gtype(b,o).
This way we are able to sample the truth value of groundatom gtype(b,o). When goals contains variables, uni cation
occurs as usual, and when goals succeed, we will have variablebindings (answer substitutions) just like Prolog.

3.4

atom

parametermsw(gene, ,a)msw(gene, ,b)msw(gene, ,o)

1
2
1

Learning and testing

Suppose that we randomly observed people's blood types andobtained the following table12.
atom

blood type(a)blood type(b)blood type(o)blood type(ab)(total)Table 1.

count

195
97
159
49
500

10

(total)atom

computed prob.

Table 3.

4

Sample observations

0.39700.20150.31190.08961.0000Computed probabilities

Blood type model for children of cousin
parents

When parents are cousins, we have to take the fact into account to build a proper model of genetic inheritance of blood
genes. This is because a child has the chance of inheriting
copies of the same gene from one of the grand-grand parents(see Figure 3). The probability of its happening is calculated
as 1=16 and is called a coecient of inbreeding [5].

For the ABO blood type program to be a good scienti cmodel, the probability distribution speci ed by the program
should be close to the observed distribution. Hence, we adjust
statistical parameters associated with msw/3 that determine
the probabilities of gene(P,a), gene(P,o) and gene(P,b) sothat the resulting distribution gets closer to the above table.
The adjustment is carried out by statistical learning basedon the EM algorithm [20, 18]. We run the command learn/1
with the list of ground atoms that represent our observations
as follows.

siblings| ?- learn([blood_type(a),blood_type(a),blood_type(o),blood_type(b),...]).
learn/1 starts the EM learning algorithm, and iteratively
adjusts parameters associated with msw/3 to maximize theprobability of blood type(a) ^ blood type(a) ^ blood type(o)^ blood type(b) . . . After 11 iterations, the learning stopped. father
Table 2 shows learned parameter values.

mothercousins

Finally, the distribution of blood type/1 speci ed by theseparameters is computed by prob/2 built-in predicate, giving
Table 3.

child

Since the Table 3 is just a theoretically computed distribution, we need to check by the -square method how wellit ts what we observed, i.e. Table 1. By calculation, we get2 = 0:6545. For degrees of freedom 1 (we have two parameters 1 and 2 ), this happens with probability > 0:4. So Table
3 cannot be rejected, which indirectly supports, together with
Table 2, the correctness of ABO blood type program that produced it.

Figure 3.

Cousin model

Figure 4 is part of a program that models the blood
type inheritance mechanism for children of cousin parents.
child of cousin(a) says that a child of cousin parents has
a blood gene a and cousin(X,Y) says randomly chosen two

12 This data set is generated by a program. It re ects the blood type

distribution in Japan. The ratio is almost A:B:O:AB = 4:2:3:1.

Machine Discovery

0 2

Learned parameters(total)

0.390
0.194
0.318
0.098
1.000

0.28350.15800.55851.0000

Table 2.

blood type(a)blood type(b)blood type(o)blood type()

ratio

learned value

5

T.Satocousins have gene X and Y.

5

Yet another blood type theory

Here we describe yet another blood type theory that lost to
ABO blood type theory [6]. This theory, AaBb blood type theory, assumes two loci. Blood type is determined by alleles at
each locus according to Table 5.

inherit(from(XP),pair(sibling parent,other),1)

describes gene inheritance that occurs between the cousin andthe cousin's parents. XP denotes the cousin's parent who is thesource of gene X. The atom says as the result of gene inheritance at 1st trial, XP becomes, with prob. 1=2, either a siblingparent or the other non-sibling parent. siblings(X,Y) says
randomly chosen two siblings have gene X and Y respectively.

type

O
A
B
AB

We assume that as far as non-sibling parents are concerned,
the distribution of their blood types are determined by random mating. In other words, we use the ABO program shownin Figure 2 as a program to determine the blood type distribution of non-sibling parents.

Table 5.

locus-1

aa
Aaa
A-

locus-2

bb
bb
BB-

AaBb blood type theory

child_of_cousin(a):(cousin(a,a); cousin(a,o); cousin(o,a)).
child_of_cousin(b):(cousin(b,b); cousin(b,o); cousin(o,b)).
child_of_cousin(o):- cousin(o,o).
child_of_cousin(ab):(cousin(a,b); cousin(b,a)).

Here A,B are dominant genes whereas a,b are recessive
genes. - is a don't care symbol. This theory was once oneof the competing theories for explaining the ABO blood type[6] but failed to pass a statistical test and eventually was rejected. We trace this whole scienti c process of proposing ahypothesis, checking it with data, determining acceptance orrejection, in the framework of PRISM programming.

cousin(X,Y):- % randomly chosen two cousins have
% gene X and gene Y
inherit(from(XP),pair(sibling_parent,other),1),
inherit(from(YP),pair(sibling_parent,other),2),( XP==sibling_parent, YP==sibling_parent,
siblings(X,Y) % randomly chosen two siblings; ...
% have gene X and gene Y

We rst write a program shown in Figure 5. Note thatin the program, \-" is represented as an anonymous logicalvariable \ ". Next by using the same data, i.e. Table 1 used
for ABO blood type theory, we let it learn statistical parametersin the program. Then we calculate the distribution of blood
types determined from the learned parameters. Finally wecheck them against the observed data Table 1 by -square
tting test.

Figure 4.

Program for children of cousin parents

blood_type(o):gtype(1,[a,a]),gtype(2,[b,b]).
blood_type(a):(gtype(1,['A',_]); gtype(1,[_,'A'])),
gtype(2,[b,b]).
blood_type(b):gtype(1,[a,a]),(gtype(2,['B',_]); gtype(2,[_,'B'])).
blood_type(ab):(gtype(1,['A',_]); gtype(1,[_,'A'])),(gtype(2,['B',_]); gtype(2,[_,'B'])).

After writing down the whole program, we provide it withparameters in Table 2, i.e. parameters for the blood type
distribution of general people, and calculate the distributionof blood type for children of cousin parents. This is a predication step. We compute an unobserved distribution by using
our cousin model. The result is shown in Table 4. The next
step would be comparing these probabilities with observationsof blood types of children whose parents are cousins.

gtype(N,[X,Y]):- gene(N,father,X),gene(N,mother,Y).
atom

child of cousin(a)child of cousin(b)child of cousin(o)child of cousin(ab)(total)Table 4.

gene(1,P,G):-(bsw(0,P,1), G=a; bsw(0,P,0), G='A').
gene(2,P,G):-(bsw(1,P,1), G=b; bsw(1,P,0), G='B').
gene('A'):- gene(1,father,'A').
gene(a):- gene(1,father,a).
gene('B'):- gene(2,father,'B').
gene(b):- gene(2,father,b).

prob.

0.38990.19880.32730.08401.0000Predicted probabilities
Figure 5.

AaBb blood type program

The probabilities of gene/1 and blood type/1 computed
Machine Discovery

6

T.Satofrom the learned parameters are summarized in Table 6.

atomgene(A)gene(a)gene(B)gene(b)Table 6.

prob.

0.28450.71550.1586
0.8414atom

blood type(a)blood type(b)blood type(o)blood type(ab)(total)Karieramarrige

prob.

0.34550.14950.36250.14251.0000BanakaComputed probabilities for AaBb theory

child

Comparing the observed data in Table 1 with the computed data in Table 6, we nd 2 = 19:16486. With degrees
of freedom 1 (again, we have two parameters), this happens
with probability < 0:001. So AaBb theory should be rejected.
6

BurungPalyeri

Karimera

A case of anthropological study { theKariera tribe

To explore the descriptive power of a rst-order computational language combined with a statistical learning method,
we take up the Kariera tribe from anthropology where social
rules interact with a genetic inheritance mechanism.

Figure 6.

gtype(C,[X,Y],N):N>0,
children(C,parents(FC,MC)),
inherit(genes,from(X1,Y1),pair(X,Y),N),
cousins(clan(FC,X1),clan(MC,Y1),N).

In the beginning of the 20th century, the Kariera tribe lived
along the coast of West Australia which had the territory of
about 3500 square miles. A special type of cross-cousin marriage (bilateral cross-cousin marriage) was a norm in theirsociety. It states that a husband H and his wife W must be
cousins such that H's father and W's mother are siblings (Hand W are patrilateral cross-cousins), and at the same time
H's mother and W's father are siblings as well (H and W are
matrilateral cross-cousins) [21].

clan C has genotype <X,Y> at the N-th generation, we de ne
gtype(C,[X,Y],N) as follows.
inherit(genes,from(X1,Y1), pair(X,Y), N) says the parents have genes fX1,Y1g as a set and the child's genotype<X,Y> coincides with either <X1,Y1> or <Y1,X1> with probability 1=2. cousins(clan(FC,X1),clan(MC,Y1),N) says a randomly chosen two cousins, one (male) in clan FC and the other(female) in clan MC, have gene X1 and Y1 respectively at theN-th generation.

The tribe was divided into four clans 'Palyeri', 'Karimera','Banaka' and 'Burung'. 'Palyeri' and 'Karimera' form a marriage pair, and so do 'Banaka' and 'Burung' (Figure 6). A
husband and his wife must come respectively from each of thepaired clans. Their children however belong to the third clan
uniquely determined by the parents' clans.

Since all married couples are cousins in this society, cousins'ancestors are also cousins. This brings unbound recursion
through generation into the program. And a sucient number of recursion through generations are expected to lead theblood gene distribution computed by the program to a stable state. In actual computation however, computational costof recursion was so high that recursion depth was limited to 2.

The blood type inheritance mechanism in this society which
was complicated by the social rules mentioned above can be
described as a PRISM program. We rst include in the following facts about the Kariera clans.
child('Banaka', parents('Palyeri','Karimera')).
child('Burung', parents('Karimera','Palyeri')).
child('Palyeri', parents('Banaka','Burung')).
child('Karimera',parents('Burung','Banaka')).

We here describe one of the several learning experimentswith arti cial data. We rst randomly sampled 100 groundblood type/1 atoms (the sampling ratio was A:B:O:AB =4:2:3:1)
and obtained Table 7.

Here child(C, parents(FC,MC)) for instance means if thefather's clan is FC and the mother's clan is MC then the childbelongs to clan C. We then add the usual ABO blood program (Figure 2) appropriately modi ed to the Kariera case.
For instance, to say a randomly chosen two individual in
Machine Discovery

Clans in the Kariera tribe

In the learning step, we let the program learn statisticalparameters from this data set in which we assumed the ratioof clan population is 'Palyeri':'Karimera':'Banaka':'Burung'= 2:2:1:1. The table Table 8 of probabilities computed from
7

T.Satoatom

countsblood type(a)blood type(b)blood type(o)blood type(ab)(total)Table 7.

34
27
33
6
100

Next step seems diverse. One is rule extraction from a basic
distribution. First we augment PRISM with a more powerful class of basic distributions such as Boltzmann distributions than random switches. We then maximize the probability of given goals (random samples) by the Boltzmann machine learning method [1]. Since the learned distribution reects probabilistic correlations between atoms, we may havea good chance of extracting logical rules from it.

ratio

0.340
0.270
0.330
0.060
1.000

Sample observations

Another is modeling dynamic temporal phenomena suchas cooperation among agents with logical reasoning ability.
This seems to require an on-line learning mechanism unlike
the current o -line learning mechanism of PRISM. Researchin the area of reinforcement learning will be of much help.

the program using learned parameters (and this passed successfully -square tting test).
atom

blood type(a)blood type(b)blood type(o)blood type(ab)(total)Table 8.

Last but not least, it is also important to explore new areas
which PRISM modeling can contribute to. We are currently
looking into the possibility of applying PRISM modeling to
the area of marketing.

prob.

0.33820.26900.3312
0.06161.0000We state related work.
Ng and Subrahmanian combined (function free) logic programs with probability ranges (upper and lower bounds) toexpress uncertainty [12]. After assigning probability ranges toatoms in the logic program, they checked if probabilities satisfying those ranges actually exist or not by the technique of
linear programming. The use of linear programming however
con nes their approach to a nite domain. Learning was notconsidered. Recent development is described in [7].

Learned results

Unfortunately, due to the lack of conrete data and for otherreasons, this learning experiment can only be theoreticallymeaningful. It however exempli es that PRISM programming can still work for such complicated phenomena as theinteraction between social rules and a genetic mechanism.
7

Probabilistic Horn abduction [15] also combined logic programs with probabilities, in which Poole showed, for example,
how to express Bayesian networks. His semantics on the other
hand excludes large part of usual logic programs because of
the requirement of acyclicity of programs (programs must be
strati able by the assignment of integers to ground atoms)[15]. His recent publication [16] focused on modeling dynamic
behavior such as that of agents and dealt with decision/gametheoretic means based on acyclic logic programs (with negation as failure). Neither of the frameworks mentioned how tolearn probabilities.

Discussion and related work

Modeling is an indispensable step in the process of scienti c
discovery and PRISM was designed exactly for this purpose[18, 19].
Since PRISM integrates a general logic programming language and the statistical learning by the EM algorithm atsemantic level and at procedural level, not only can it declaratively describe and simulate complex phenomena governed
by rules and probabilities, but can learn from data (goals),and hence, can change the behavior of programs adaptively.
In this paper, we have presented the basic idea of PRISM
and its modeling examples taken from the area of blood gene
inheritance.

Charniak and Goldman proposed a special language FRAIL3
for construction of Bayesian networks [4]. Although their rules
look much like de nite clauses annotated with probability dependencies, the semantics is not very clear and no learning
mechanism is provided for their programs.

It should be mentioned however that PRISM programming tends to be more dicult as we have to consider logicalmeaning and probabilistic relationship at the same time, andencode them, coherently, into a single program. This means
if we want to verify our program, we need the logical andstatistical veri cation of the denotation of the program, i.e. a
joint distribution of all ground atoms. Little is known aboutsuch veri cation however. Despite these diculties, we haveshown by examples that PRISM can be a valuable tool with
rst-order descriptive power and learning ability for modelingcomplex phenomena from HMM to Bayesian nets [18, 19] tothe ones presented in this paper.
Machine Discovery

Hashida [9] proposed a rather general framework for natural language processing as probabilistic constraint logic programming. He assigned probabilities to between literals andlet them denote the degree of the probability of invocation.
He has shown constraints are eciently solvable by making
use of these probabilities.
Koller [10] deals with the problem of gene inheritance. Knowledge about gene inheritance is encode by a rst order language
and then translated into a Bayesian network. The EM learning algorithm adapted for Bayesian networks is applied to statistically estimate parameters in the network. It is not clear
8

T.Satohowever how to extend this approach to a general programming language with Turing computation power. She also proposed a functional probabilistic programming language [11]for stochastic processes.
ACKNOWLEDGEMENTS

We would like to thank the referees for their comments which
helped improve this paper.
REFERENCES[1] Ackley,D.H., Hinton,G.E. and Sejnowski,T.J., A learning algorithm for Boltzmann machines, Cognitive Sci. 9, pp147-169,
1985.
[2] Asai,K., Hayamizu,S. and Handa,K., Prediction of protein
secondary structure by the hidden Markov model, CABIOS 9
No.2 pp141-146, 1993.
[3] Charniak,E., Statistical Language Learning, The MIT Press,
1993.
[4] Charniak,E. and Goldman,R.P., A Language for Constructionof Belief Networks, IEEE PAMI 15 No 3, pp196-208, 1993[5] J.F.Crow, Genetics Notes (8th ed.)(translated into J),
Burgess Publishing Company, Minneapolis, 1983.
[6] J.F.Crow, Basic Concepts in Population, Quantitative andEvolutionary Genetics (translated into J), W.H.Freeman andCompany, New York, 1988.
[7] Dekhtyar,A. and Subrahmanian,V.S., Hybrid Probabilistic
Programs, Proc. of Fourteenth ICLP, pp391-405, 1997.
[8] Doets,K., From Logic to Logic Programming, MIT Press,
Cambridge, 1994.
[9] Hashida,K., Dynamics of Symbol Systems, NGC 12, pp285310, 1994.
[10] Koller,D. and Pfe er,A., Learning probabilities for noisy rstorder rules, Proc. of IJCAI'97, Nagoya, pp1316-1321, 1997.
[11] Koller,D., McAllester,D. and Pfe er,A., E ective Bayesian Inference for Stochastic Programs, Proc. of AAAI'97, Rhode
Island, pp740-747, 1997.
[12] Ng,R. and Subrahmanian,V.S., Probabilistic Logic Programming, Information and Computation 101, pp150-201, 1992.
[13] Ng,R., Haddawy,P. and Helwig,J., A Theoretical Framework for Context-Sensitive Temporal Probability Model Construction with Application to Plan Projection, Proc. of theeleventh UAI,Montreal, pp419-429, 1995.
[14] Pearl,J., Probabilistic Reasoning in Intelligent Systems, Morgan Kaufmann, 1988.
[15] Poole,D., Probabilistic Horn abduction and Bayesian networks, Arti cial Intelligence 64, pp81-129, 1993.
[16] Poole,D., The independent choice logic for modeling multiple
agents under uncertainty, Arti cial Intelligence 94, pp7-56,
1997.
[17] Rabiner,L.R., A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, Proc. of the IEEE
77, No. 2, pp257-286, 1989.
[18] Sato,T., A Statistical Learning Method for Logic Programswith Distribution Semantics, Proc. of ICLP'95, pp715-729,
1995.
[19] Sato,T., and Kameya,Y. PRISM:A Language for SymbolicStatistical Modeling, Proc. of IJCAI'97, pp.1330-1335, 1997.
[20] Tanner,M., Tools for Statistical Inference (2nd ed.), SpringerVerlag, 1986.
[21] H.C.White, An Anatomy of Kinship, Prentice-Hall INC.,
1963.

Machine Discovery

9T.Sato