Generative Modeling with Failure in PRISM

1 Introduction

Modeling complex phenomena in the real world such as natural language understanding is a challenging task and PRISM is a symbolic-statistical modeling language proposed for that purpose [Sato and Kameya, 1997]. It is a relational probabilistic language for defining distributions over structured objects with arbitrary complexity. Parameters in the defined distribution (probability measure) are estimated efficiently from data using dynamic programming by a generic EM algorithm 1 called the gEM (graphical EM) algorithm. For example parameter estimation for PCFGs (probabilistic context free grammars) by PRISM is carried out with the same time complexity as the Inside-outside algorithm, a well-known EM algorithm for PCFGs [Sato and Kameya, 2001]. 2

The modeling power of PRISM comes from the fact that the user can use arbitrary definite clause programs to define distributions. There is no restriction on programs such as range-restrictedness 3 or finite domain. Hence theoretically speaking, there is no limit on the complexity of modeling targets. Nevertheless EM learning 4 is possible by the gEM algorithm for a program as long as it satisfies certain conditions. Consequently there is no or little barrier to the EM learning of new statistical models. PRISM thus offers a new and ideal tool to develop complex models that require both logical and statistical knowledge.

1 The EM algorithm is a class of statistical inference algorithms for ML (maximum likelihood) estimation which alternates expectation and maximization steps until convergence.

2 The recent refinement of PRISM implementation [Zhou et al., 2004] has made it possible to complete the parameter estimation for a PCFG containing 860 rules from 10,000 sentences in less than 10 minutes on a PC.

3 Variables appearing in the clause head must also appear in the clause body. In particular unit clauses must be ground.

PRISM is primarily designed for generative modeling where a program models a process of generating observable events as a chain of probabilistic choices. In early versions of PRISM, programs are assumed to be failure-free, which means that a process never fails 5 once a probabilistic choice is made and thus the probabilities of observable events sum to unity. Although typical statistical models such as Bayesian networks, HMMs (hidden Markov models) and PCFGs satisfy this condition, it makes constraint-based modeling, a widely used flexible methodology, impossible in which wrong solutions are filtered out by not satisfying constraints. 6

The elimination of the failure-free condition was attempted in [Sato and Kameya, 2004] but rather limited to the failure of definite clause programs. In this paper we propose to allow general programs, 7 a super class of definite clause programs, to fail. Although the introduction of general programs significantly increases the flexibility of PRISM modeling and expands the class of definable distributions, it comes with costs. First as the probabilities of observable events do not sum to unity, we have to deal with log-linear models 8 [Abney, 1997; Cussens, 2001] which require intractable computation of a normalizing constant. We do not go into the detail of this problem here though.

Second we are faced with a semantic problem. Compared to definite clause programs where the least model semantics is unanimously accepted, there is no agreed-upon semantics for general programs, 9 much less probabilistic semantics. But without such semantics, mathematically coherent modeling would be hardly possible. We fill the need by generalizing distribution semantics, the existing semantics for positive (= definite clause) PRISM programs [Sato, 1995] to a new threevalued semantics. It considers a ground atom as a random variable taking on true, false and undefined, and defines a distribution over the three-valued Herbrand interpretations of a given general PRISM program.

4 Here and henceforth EM learning is used a synonym of ML estimation by the EM algorithm.

5 A process fails if it does not lead to any observable output.

6 Constraints are relations on variables such as equality, disequality and greater-than.

7 A general program is a set of general clauses (non-Horn clauses) which may contain negation in their body.

8 A distribution has the form D4B4DCB5 BP CI A0BD CTDCD4B4  CX AN CX CU CX B4DCB5B5 where AN CX is a coefficient, CU CX B4DCB5 a feature and CI a normalizing constant. In our setting CI is the sum of probabilities of all observable events.

There remains one thing to solve however. To perform EM learning of a general PRISM program that may fail, we need a 'failure program' which positively describes how failure occurs in the original program. We show that the failure program can be synthesized mechanically by eliminating negation using FOC (first-order compiler). FOC is a deterministic program transformation algorithm that compiles negated goals into executable form with disunification constraints [Sato, 1989]. Once a failure program is obtained, or more generally negation is eliminated, efficient EM learning is possible by an appropriate modification to the gEM algorithm. Our contributions are summarized as follows.

• AF A new three-valued semantics for probabilistic logic programs with negation.
• AF A new approach to parameter learning of such programs through automated elimination of negation by FOC.

In the remainder of this paper we discuss each of the topics after reviewing PRISM briefly. Because our subject intersects a variety of areas from logic programming, statistics, program synthesis, to relational modeling, we are unable to give a detailed and formal description due to the space limitation. Necessarily the description is mostly based on examples and proofs are omitted. The reader is assumed to be familiar with logic programming [Doets, 1994] and EM learning [McLachlan and Krishnan, 1997]. Our notation follows Prolog conventions. So we use 'BN' for conjunction and 'BN' for disjunction. Variables begin with an upper case letter and variables in clause heads are implicitly universally quantified.

2 PRISMmodeling

Informally PRISM is Prolog augmented with probabilistic built-ins and a parameter learning routine based on the gEM algorithm (the reader is referred to [Sato and Kameya, 2001] for a formal description of PRISM). The essence of PRISM modeling is to write a logic program containing random switches represented by the built-in predicate D1D7DBB4D8BN DAB5 where D8, the name of a switch and DA, a result of random choice are ground terms. 10 The sample space for D8 viewed as a random variable is declared by the predicate DACPD0D9CTD7BPBE. The probability of each outcome of a switch, i.e. that of D1D7DBB4D8BN DAB5 being true, is called a parameter. Parameters can be set by the D7CTD8 D7DBBPBE predicate or learned from sample data. The following PRISM program, which simulates a sequence of Bernoulli trials, defines a distribution of ground atoms of the form CQCTD6B4D2BN D0B5 where D0 is a list of outcomes of D2 coin tosses.

9 We can see a variety of semantics in [Apt and Bol, 1994; Fitting, 2002].

10 D1D7DB is an acronym of 'multi-ary random switch'.

target(ber,2). % observable event values(coin,[heads,tails]). % outcomes :- set_sw(coin,0.6+0.4). % parameters ber(N,[R|Y]):- N>0, msw(coin,R), % probabilistic choice N1 is N-1, ber(N1,Y). % recursion ber(0,[]).

When this program is loaded, the parameters of the switch CRD3CXD2 is set by D7CTD8 D7DB: the probability of CWCTCPCSD7 is 0.6 and that of D8CPCXD0D7 is 0.4. There are three modes of execution in PRISM, namely sampling execution, probability calculation, and learning. In sampling execution, this program is executed like in Prolog except that the built-in D1D7DBB4CRD3CXD2BN CAB5 binds probabilistically CA to CWCTCPCSD7 or D8CPCXD0D7. Probabilities are calculated by using the D4D6D3CQBPBE built-in. For example, the query ?- BZ BP CQCTD6B4BEBN CJCWCTCPCSD7BN D8CPCXD0D7CLB5BN D4D6D3CQB4BZBN B5 calculates the probability  of having D8CPCXD0D7 after having CWCTCPCSD7. Parameters are learned by using the built-in D0CTCPD6D2BPBD which takes a list of sample data as teacher data.

3 Three-valued distribution semantics 3.1 Two-valued distribution semantics

The Bernoulli program in Figure 1 is said to be positive because there is no negation in the program. For such positive PRISM programs, a formal semantics called distribution semantics is proposed [Sato, 1995] that defines a AR-additive probability measure 11 over the set of possible Herbrand interpretations from which a distribution of each predicate is derived. In the sequel 'interpretation' always means an Herbrand interpretation.

The distribution semantics is a probabilistic generalization of the standard least model semantics for definite clause programs. A positive PRISM program is written as BWBU BP CACJBY , where CA is a set of definite clauses and BY a set of ground D1D7DB atoms to which a basic distribution  D1D7DB is given. Sampling execution of BWBU w.r.t. a top-goal is considered as a partial exploration of the least model B4CA CJ BY BC B5 where BY BC is a set of true D1D7DB atoms 12 sampled from  D1D7DB . In this semantics, each ground atom is a binary random variable taking on t (true) or f (false). As there are a countably infinite number of ground atoms, we can use an infinite number of random variables in a program. This fact, for example, makes it possible to model PCFGs faithfully.

11 We use 'distribution' and 'probability measure' interchangeably for the sake of familiarity. In this paper the measurability of related functions are assumed without proofs.

12 An atom whose predicate symbol is D1D7DB is called an D1D7DB atom.

3.2 Negation and a new three-valued semantics

The moment negation is introduced, we are faced with numerous problems concerning semantics and computation [Apt and Bol, 1994; Fitting, 2002]. The biggest problem on the semantic side is the lack of the canonical semantics: there exist many competing semantics for general programs. The primary computational problem is that whatever semantics we may adopt, it is not computable in general.

We adopt Fitting's three-valued semantics and extend it to a three-valued probabilistic semantics following [Sato and Kameya, 2001]. Fitting's three-valued semantics is a fixed point semantics similar to the least model semantics for positive programs but goals causing infinite computation are not considered false but considered undefined. It is simpler compared to other semantics such as stable model semantics [Gelfond and Lifshcitz, 1988] and well-founded semantics [Van Gelder et al., 1991]. Also it has an advantage that it always gives a unique denotation to any general program.

Assume that our language  has countably many predicate and function symbols for each arity. Especially it contains the predicate symbol D1D7DBBPBE. A general PRISM program BWBU BP CA CJ BY is the union of a set CA of general clauses and a set BY of ground D1D7DB atoms such that no D1D7DB atom appears as a head in CA. D1D7DB atoms are implicitly introduced by DACPD0D9CTD7BPBE declarations in the program as their ground instantiations.

We associate a probability measure  D1D7DB over the set of two-valued interpretations for BY as follows. Let D8 be a switch name, AA D8 BP CUDA BD BN BM BM BM BN DA CZ CV be a sample space for D8 declared by DACPD0D9CTD7B4D8BN CJDA BD BN BM BM BM BN DA CZ CLB5, and D4 BD BN BM BM BM BN D4 CZ are the parameters satisfying  CZ CXBPBD D4 CX BP BD. Let AM D8 be a probability measure defined over AA D8 such that AM D8 B4DA CX B5 BP D4 CX (BD AK CX AK CZ). We define an infinite product measure  BC D1D7DB of AM D8 s over AA BC D1D7DB BP D8BECB AA D8 where CB is the set of all switch names. Note that AL BE AA BC D1D7DB is considered a function such that ALB4D8B5 BE AA D8 .

Let AA BY be the set of interpretations for BY. We define a mapping B3 BM AA BC D1D7DB A0AX AA BY such that B3B4ALB5B4BTB5 = true if BT BP D1D7DBB4D8BN DAB5 and ALB4D8B5 BP DA for some D1D7DBB4D8BN DAB5. Otherwise B3B4ALB5B4BTB5 = false. Finally we define  D1D7DB as the probability measure over AA BY induced by B3. By construction it holds for the sample space CUDA BD BN BM BM BM BN DA CZ CV for D8 that  D1D7DB B4D1D7DBB4D8BN DA CX B5B5 BP  BC D1D7DB B4CUAL CY ALB4D8B5 BP DA CX BN AL BE AA BC D1D7DB CVB5 BP D4 CX and  D1D7DB B4D1D7DBB4D8BN DA CX B5BN D1D7DBB4D8BN DA CY B5B5 BP BC if CX BIBP CY.

A three-valued interpretation for  is a mapping which maps a ground atom in  to t (true), f (false) or u (undefined). 13 We denote by AA BF the set of three-valued interpretations for . Let BWBU BP CA CJ BY be a general PRISM program. For AN BE AA BY , we denote by  BF B4ANB5 the least fixed point of the Fitting's three-valued direct mapping A8  [Fitting, 2002] applied to the general program  BP CACJBY AN where BY AN BP CUBT CY AN CYBP BTBN BT BE BYCV. We consider  BF B4ANB5 as a threevalued interpretation for  where atoms not appearing in BWBU receive u. Then BF B4A1B5 is a mapping fromAA BY to AA BF .  BF B4A1B5 induces a AR-additive probability measure  BFBWBU over AA BF . We define  BFBWBU as the denotation of BWBU in our new three-valued probabilistic semantics (denotational semantics).  BFBWBU is a probabilistic extension of Fitting's three-valued semantics for general logic programs. It is also a generalization of the twovalued counter part  BWBU defined in [Sato and Kameya, 2001] with a slight complication. 14

13 The evaluation rule concerning u obeys Kleene's strong three valued logic. That is, BMD9 BP D9, DA CN D9 BP D9 CN DA BP D9 if DA BP CU D3D6 D9; otherwise D9 CN DA BP D8 if DA BP D8.

4 Failure and log-linear models

Having established a probability measure  BFBWBU in Section 3, we can now talk about various probabilities such as failure probability on a firm mathematical basis. We show here how failure in generative modeling leads to log-linear models.

4.1 Coin flipping with an equality constraint

Suppose we have two biased coins CRD3CXD2B4CPB5 and CRD3CXD2B4CQB5. Also suppose we repeatedly flip them and record the outcome only when both coins agree on their outcome, i.e. both heads or both tails. 15 The task is to estimate probabilities of each coin showing heads or tails from a list of records such as CJ CPCVD6CTCTB4CWCTCPCSD7B5BN CPCVD6CTCTB4D8CPCXD0D7B5BN BM BM BM CL.

We generatively model this experiment by a PRISM program CA CPCVD6CTCT shown below where D1D7DBB4CRD3CXD2B4CPB5BN BTB5 instantiates BT to CWCTCPCSD7 or D8CPCXD0D7 with probabilities specified elsewhere. Assuming Prolog execution, CPCVD6CTCTBPBD describes the process of flipping two coins that fails if their outcomes disagree. D7D9CRCRCTD7D7 means there is some output whereas CUCPCXD0D9D6CT means there is no output. We denote by  CPCVD6CTCT B4A1B5 the defined distribution.

failure :- not(success). success :- agree(_). agree(A):- % flip two coins and output msw(coin(a),A), % the result only when msw(coin(b),B), % both outcomes agree A=B. % (equality constraint).

We say a logic program is terminating if an arbitrary ground atom has a finite SLDNF tree [Doets, 1994]. Since  CPCVD6CTCT BP CA CPCVD6CTCT CJBY BC is terminating for an arbitrary set BY BC of D1D7DB atoms, no atom in the least model defined by the Fitting's A8  CPCVD6CTCT operator receives u (u implies an infinite computation). Consequently  CPCVD6CTCT B4D7D9CRCRCTD7D7B5 B7  CPCVD6CTCT B4CUCPCXD0D9D6CTB5 BP BD holds for any parameter setting of D1D7DB atoms. On the other hand if some ground atom BT receives u in our semantics, we may not be able to compute  BFBWBU B4BTB5 due to infinite computation. We therefore focus on terminating programs in the following so that no ground atom receives u and  BFBWBU B4BTB5 is computable for every ground atom BT.

14 Suppose that BWBU is a definite PRISM program and let BT be a ground atom. We have  BWBU B4BT BP D8B5 BP  BFBWBU B4BT BP D8B5 but not necessarily  BWBU B4BT BP CUB5 BP  BFBWBU B4BT BP CUB5. The reason is that when BT causes only an infinite loop, it is false in the least model semantics whereas it is undefined in Fitting's three-valued semantics.

15 This model is a very simplified model of linguistic constraints such as agreement in gender and number [Abney, 1997].

4.2 ML estimation for failure models

When we attempt ML estimation from observed data such as CJ CPCVD6CTCTB4CWCTCPCSD7B5BN CPCVD6CTCTB4D8CPCXD0D7B5BN BM BM BMCL, we must recall that our observation is conditioned on D7D9CRCRCTD7D7 because we cannot observe failure. Therefore the distribution to be used is a log-linear model  CPCVD6CTCT B4A1 CY D7D9CRCRCTD7D7B5 (=  CPCVD6CTCT B4A1B5BP CPCVD6CTCT B4D7D9CRCRCTD7D7B5) in which the normalizing constant  CPCVD6CTCT B4D7D9CRCRCTD7D7B5 is not necessarily unity.

Generally speaking ML estimation of parameters for loglinear models is computationally intractable. On the other hand if they are defined by generative processes with failure like  CPCVD6CTCT B4A1 CY D7D9CRCRCTD7D7B5 in our example, a simpler estimation algorithm called the FAM algorithm is known [Cussens, 2001]. It is an EM algorithm regarding the number of occurrences of failure as a hidden variable. Recently, it is found that it is possible to combine the FAM's ability of dealing with failure and the gEM's dynamic programming approach and an amalgamated algorithm called the fgEM algorithm is proposed as a generic algorithm for EM learning of generative models with failure [Sato and Kameya, 2004]. It however requires a positive program that describes how failure occurs in the model. We next explain such a failure program can be automatically synthesized by FOC (first-order compiler).

5 FOC for probabilistic logic programs

5.1 Compiling universally quantified implications

FOC (first-order compiler) is a logic program synthesis algorithm which deterministically compiles negation, or more generally 16 universally quantified implications of the form BKDD B4D4B4DCBN DDB5 AX D5B4DDBN DEB5B5 into definite clauses with disequality (disunification) constraints such as BMBLDCB4D7 BP D8CJDCCLB5 [Sato, 1989]. Since what FOC does is deductive unfold/fold transformation, the compiled code is a logical consequence of the source program. More precisely we can prove from [Sato, 1989]

Theorem 1 Let CB be a source program consisting of clauses whose bodies include universally quantified implications. Suppose CB is successfully compiled into CB BC by FOC and CB BC is terminating. Then for a ground atom BT,

Figure 3 is a small example of negation elimination by FOC. As can be seen, 'D2D3D8' in the source program is compiled away and a new function symbol CUBC and a new predicate symbol CRD0D3D7D9D6CT CTDACTD2BCBPBE are introduced during the compilation process. They are introduced to handle so called continuation. Usually the compilation adds disunification constraints but in the current case, they are replaced by a normal unification using sort information DC BP BC CN BLDD B4DC BP D7B4DDB5B5 declared for FOC (not included in the source program). Since the compiled program is terminating, Theorem 1 applies.

5.2 Modifying FOC for msw

FOC was originally developed for non-probabilistic logic programs. When programs contain D1D7DB atoms and hence

16 BMBT BP B4BT AX falseB5

17 compB4CBB5 denotes the union of CB and some additional formulas reflecting Prolog's top-down proof procedure [Doets, 1994].

% source program even(0). even(s(X)):- not(even(X)). % compiled program even(0). even(s(A)):- closure_even0(A,f0). closure_even0(s(A),_):- even(A).

probabilistic however, compilation is still possible. Suppose we compile a universally quantified implication

into an executable formula where D7 and D8 are terms and AU is some formula such that D8 and AU possibly contain DD. Although D1D7DBBPBE is a probabilistic predicate, our (three-valued) distribution semantics allows us to treat it as if it were a nonprobabilistic predicate defined by some single ground atom, say D1D7DBB4D7BN D8 BC B5. We therefore modify FOC so that it complies 18 the above formula into

where CF is a new variable. We can prove this compilation preserves our three-valued semantics when the compiled program is terminating using Theorem 1 (proof omitted). Figure 4 shows the compiled code produced by the modified FOC for CUCPCXD0D9D6CT in the CA CPCVD6CTCT program in Figure 2.

failure:- closure_success0(f0). closure_success0(A):-closure_agree0(A). closure_agree0(_):- msw(coin(a),A), msw(coin(b),B), \+A=B.

Because this program is terminating for any sampled D1D7DB atoms, it exactly computes  BFCPCVD6CTCT B4CUCPCXD0D9D6CTB5.

In what follows we show two examples of generative modeling with failure. They are available at CWD8D8D4 BM BPBPD7CPD8D3A0DBDBDBBMCRD7BMD8CXD8CTCRCWBMCPCRBMCYD4BPD4D6CXD7D1BP.

6 Dieting professor

In this section, we present a new type of HMMs: HMMs with constraints which may fail if transition paths or emitted symbols do not satisfy given constraints. Here is an example.

18 We here assume that D7 is instantiated to some switch name at execution time.

Suppose there is a professor who takes lunch at one of two restaurants 'D6BC' and 'D6BD' everyday and probabilistically changes the restaurant he visits. As he is on a diet, he tries to satisfy a constraint that the total calories for lunch in a week are less than 4000 calories. He probabilistically orders pizza (900) or sandwich (400) at D6BC, and hamburger (500) or sandwich (500) at D6BD (numbers are calories). He records what he has eaten in a week like CJD4BN D7BN D7BN D4BN CWBN D7BN CWCL and preserves the record if and only if he has succeeded in satisfying the constraint. We have a list of the preserved records and we wish to estimate his behavioral probabilities from it.

The behavior of the dieting professor is modeled by a constrained HMM described above and coded as a PRISM program below where failing to satisfy the calorie constraint on the seventh day causes failure thereby producing no output.

failure:- not(success). success:- hmmf(L,r0,0,7). hmmf(L,R,C,N):- N>0, msw(tr(R),R2), msw(lunch(R),D), ( R == r0, % pizza:900, sandwich:400 ( D = p, C2 is C+900 ; D = s, C2 is C+400 ) ; R == r1, % hanburger:400, sandwich:500 ( D = h, C2 is C+400 ; D = s, C2 is C+500 ) ), L=[D|L2], N2 is N-1, hmmf(L2,R2,C2,N2). hmmf([],_,C,0):- C < 4000.

We verified the correctness of our modeling empirically by checking if the sum of probabilities of D7D9CRCRCTD7D7 and CUCPCXD0D9D6CT becomes unity. We used the 'original value' given in Table 1 as checking parameters.

?- prob(success,Ps),prob(failure,Pf), X is Ps+Pf. X = 1.0 Pf = 0.348592596784 Ps = 0.651407403216

After checking that the sum is unity, we repeated learning experiments. In an experiment we generated 500 samples by the program with the same parameter values used in the checking, and then let the program estimate them using the fgEM algorithm. Table 1 shows averages of 50 experiments where numbers should be read that for example, the probability of D1D7DBB4D8D6B4D6BCB5BN D6BCB5 is originally BCBMBJ and the average of estimated ones is BCBMBIBLBJ. Estimated parameters look close enough to the original ones.

We would like to emphasize that the computational strength of our approach is that the probability of CUCPCXD0D9D6CT is computed in a dynamic programming manner with no additional cost just like ordinary HMMs thanks to the tabling mechanism of PRISM [Zhou et al., 2004].

7 Tic-tac-toe game

This example models the tic-tac-toe game by using negation and recursion. The purpose of this example is to illustrate 'EM learning through negative goals', which has never been attempted before to our knowledge. In tic-tac-toe, the 'o' player has to place three 'o's in a row, horizontally, vertically, or diagonally on the board of a 9 by 9 board before the opponent, the 'x' player, does so with 'x'. The program in Figure 7 models the game. The basic idea of modeling is expressed by the following clause:

win(X):- your_opponent(X,Y),not(win(Y)) which states that unless your opponent wins, you win (or draw). In Figure 7, '*' designates an

failure :- not(success). success :- Ini_Board = [[*,*,*],[*,*,*],[*,*,*]], tic_tac_toe(o,Ini_Board). tic_tac_toe(Turn,Board):- select_move(Turn,Board,Move), next_board(Turn,Board,Move,N_Board,S), ( S \== continue ; S == continue, opposite_turn(Turn,N_Turn), opponent_turn(N_Turn,N_Board) ). opponent_turn(N_Turn,N_Board):- not(tic_tac_toe(N_Turn,N_Board)).

empty cell. The intended meaning of D7D9CRCRCTD7D7 is 'o' wins or 'o' draws, so D7D9CRCRCTD7D7 fails if 'x' wins. D7CTD0CTCRD8 D1D3DACTB4CCD9D6D2BN BUD3CPD6CSBN D3DACTB5 probabilistically selects and returns the next move (D3DACT), given CCD9D6D2 and BUD3CPD6CS, after which D2CTDCD8 CQD3CPD6CSB4CCD9D6D2BN BUD3CPD6CSBN D3DACTBN  BUD3CPD6CSBN CBB5 judges the next board ( BUD3CPD6CS) and returns one of the outcomes (D3 DBCXD2BN CSD6CPDBBN DC DBCXD2BN CRD3D2D8CXD2D9CT) through CB. When compiled by FOC, this program yields a terminating program, and hence the probabilities of D7D9CRCRCTD7D7 and CUCPCXD0D9D6CT are correctly computed by the compiled program. 19

Negative recursion in logic programs causes well-known difficulties from the semantics to the implementation even in the non-probabilistic case. Nevertheless, this example shows that the combination of the three-valued probabilistic semantics and compilation by FOC of general PRISM programs offers a promising approach to dealing with negation in the probabilistic context.

8 Related work and conclusion

We only discuss related work combining negation and probability in the framework of logic programming due to the space limitation and other work related to stochastic logic programing, Bayesian networks and Markov random field is omitted. The most relevant one seems the formalism proposed by Ngo and Haddawy [Ngo and Haddawy, 1997]. In their approach negation is allowed in a program but restricted to non-probabilistic goals. Semantics is defined locally in relation to a given problem. So no global semantics such as a probability measure over the set of possible Herbrand interpretations is given. The problem of parameter learning is not discussed either. Poole allows negation in his ICL (independent choice logic) programs and probabilities can be computed through negative goals [Poole, 1997]. Stable model semantics is adopted as global semantics but the problem of learning is left open.

In this paper we first tackled the problem of defining declarative semantics for probabilistic general logic programs that contain negative goals, and have proposed a new threevalued semantics which is unconditionally definable for any programs unlike other approaches. We then tackled the second problem, namely parameter learning. We have shown how parameter learning is made possible by negation elimination through the modified FOC (first-order compiler) that preserves the new semantics. As a result, constraints that may cause failure can now be utilized as building blocks of even more complex symbolic-statistical models such as generative HPSG models which is to be reported elsewhere.