On the Relations between Probabilistic Logic and p-CMS
Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 56-62.
© 1999 International Joint Conferences on Artificial Intelligence
Abstract
We discuss the relationship between probabilistic logic and 1r-CMS. Given a set of logical sentences and their probabilities of being true, the outcome of a probabilistic logic system consists of lower and upper bounds on the probability of an additional sentence to be true . These bounds are computed using a linear programming formulation. In 1r-CMS systems, the outcome is defined by the probabilities of the support and the plausibility (with the assumptions being independent) after a first phase which consists of computing the prime implicants depending only on the variables of the assumptions. We propose to reformulate a 7rCMS system without independence conditions on the assumptions, using the linear programming framework of probabilistic logic, and show how to exploit its particular structure to solve it efficiently. When an independence condition is imposed on the assumptions the two systems give different results. Comparisons are made on small problems using the assumption-based evidential language program (ABEL) of [Anrig et al., 1998] and the PSAT program of [Jaumard et al., 1991].
- [Anrig et al., 1998] Bernhard Anrig, Roman Bissig, Rolf Haenni , Jiirg Kohlas, and Nobert Lehmann. Prob- abilistic Argumentation Systems: Introduction to Assumption-Based Modeling using ABEL. Techni- cal report, Institute of Informatics, University of Fri- bourg, September 1998.
- [Chvatal, 1983] Vasek Chvatal. Linear Programming. Freeman, New York, NY, 1983.
- [de Kleer and Williams, 1987] Johan de Kleer and Brian C. Williams. Diagnosing Multiple Faults. Artificial Intelligence, 32(1):97-130, 1987.
- [de Kleer, 1986] Johan de Kleer. An Assumption-based TMS . Artificial Intelligence, 28:127-162, 1986.
- [de Kleer, 1992] Johan de Kleer. An Improved Incre- mental Algorithm for Generating Prime Implicates. In Proc. of the 10th Nat. Conf. on Artificial Intelli- gence, pages 780-785, San Jose, California, July 1992.
- A A AI. [Fisher and Kedia, 1990]
- Marchall L. Fisher and Pradeep Kedia. Optimal Solution of Set Cover- ing/Partitioning Problems Using Dual Heuristics. Management Science, 36(6):674-688, June 1990.
- [Glover and Laguna, 1997] Fred Glover and Manuel La- guna. Tabu Search. Kluwer, 1997.
- [Hansen and Jaumard, 1990] Pierre Hansen and Brigitte Jaumard. Algorithms for the Maximum Satisfiability Problem. Computing, 44:279-303, 1990.
- [Hansen et al., 1995] Pierre Hansen, Brigitte Jaumard, and Marcus V. Poggi de Aragao. Boole's Conditions HANSEN. JAUMARD. AND PARREIRA of Possible Experience and Reasoning Under Uncer- tainty. Discrete Applied Mathematics, 60:181-193, 1995.
- Hansen et al., 1999) Pierre Hansen, Brigitte Jaumard, Anderson D. Parreira, and Marcus V. Poggi de Aragao. Difficulties of Conditioning and Con- ditional Independence in Probabilistic Satisfiabil- ity. Technical Report G-99-16, Cahiers du GERAD , February 1999.
- Jaumard et al., 1991)
- Brigitte Jaumard, Pierre Hansen, and Marcus V. Poggi de Aragao. Column Generation Methods for Probabilistic Logic. ORSA Journal on Computing, 3:135-148, 1991.
- Kohlas and Haenni, 1996) Jiirg Kohlas and Rolf Haenni. Assumption-based Reasoning and Proba- bilistic Argumentation Systems. In J. Kohlas and S. Moral, editors, Defeasible Reasoning and Uncertainty Management Systems: Algorithms. Oxford University Press, 1996.
- Lasdon, 1970)
- Leon S. Lasdon. Optimization Theory for Large Systems. MacMillan, New York, 1970.
- Liu et al., 1993) Weiru Liu, Alan Bundy, and Dave Robertson. On the Relations between Incidence Cal- culus and ATMS. In Symbolic and Quantitative Ap- proaches to Reasoning and Uncertainty (Granada, 1993 ), pages 249-256. Springer-Verlag, Berlin, 1993.
- Nilsson, 1986)
- Nils J. Nilsson. Probabilistic Logic. Ar- tificial Intelligence, 28:71-87, 1986.
- Reiter and de Kleer, 1987) Raymond Reiter and Jo- han de Kleer. Foundations of Assumption-Based Truth Maintenance Systems: Preliminary Report. In Proc. of the 6th Nat. Conf. on Artificial Intelligence, volume 1, pages 183-188, Seatle, Washington, July 1987.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Many different models have been proposed for reasoning under uncertainty in expert systems. Among those based on the use of logic and probability theory which require a moderate amount of input data, two important families are the probabilistic Clause Maintenance Systems (7r CMS) [Reiter and de Kleer, 1987; de Kleer and Williams, 1987], and the probabilistic logic models [Nilsson, 1986; Jaumard et al., 1991; Hansen et al., 1995]. While these families have been developed separately, they have much in common, with however the difference that models of the former family usually suppose independence of their assumptions, while those of the latter do not . In this
A. D. PARREIRA
Dept . Math. and Ind. Eng. Ecole Polytechnique de Montreal anderson @crt . umontreal.ca
paper, we explore 1r-CMS systems, with and without in dependence of the assumptions, from the probabilistic logic viewpoint. The main results are the following: (i) when relaxing the independence condition, two formula tions can be proposed for 1r-CMS systems; (ii) the sec ond formulation suggests an algorithm which exploits the particular structure of 1r-CMS and is , on large instances, 7000 times faster than the column generation algorithm for probabilistic logic of [Jaumard et al., 1991] applied to the first formulation; (iii) with the independence con dition, probability intervals of an additional proposition obtained by 1r-CMS may overlap with those of the corre sponding probabilistic logic model , which suggests that 1r-CMS systems do not exploit the available information to its fullest degree.
The paper is organized as follows: probabilistic logic models and 1r-CMS systems are briefly reviewed in the next two sections. The two probabilistic logic models for 1r-CMS systems are presented in Section 4. Algorithms are discussed in Section 5 and computational results in Section 6. Brief conclusions are drawn in the last section.
2 Probabilistic Logic
Nilsson [Nilsson, 1986] has presented a semantical gen eralization of propositional logic in which the truth val ues of sentences are probability values (probabilistic logic, also called probabilistic satisfiability or PSAT for short) .
Let X = { x1, x2, ... , Xn} denote a set of propositional variables and S = { S1 , S2 , . . . , Sm} a set of propositional sentences over X defined with the usual operators V (dis junction), 1\ (conjunction), and -, (negation). A literal Yk is a propositional variable (Yk = xk) or its negation (Yk = -,xk)· Propositional sentences are assumed to be written using a DNF (Disjunctive Normal Form) expres sion in this paragraph.
Let w = (w1, ... , wm) be a valuation for S , where w; is equal to 1 if si has value true, and to 0 otherwise. w is a possible world if there exists a truth assignment over X which leads to w over S and it is an impossible world otherwise. Observe that two different truth assignments on X may lead to the same possible world. Let W denote the set of possible worlds and set k to IWI (note that k ~
2n). To illustrate, if X= {x1, x2} and S = {x1, X1 Vx2}, we have W = { w 1 = (0, 0); w 2 = (0, 1); w 3 = (1, 1)}, k = 3 < 2 2 , and w 4 = (1, 0) is an impossible world.
Let p = (Pl, P2, .. . , Pk) be a probability distribution on W, with 0:::; Pj:::; 1 (j = 1, .. . ,k) and "L.jP} = 1. Let 1r = ( 1r1 , ... , 1r m) be a probability vector such that 1Ti denotes the probability of sentence si ins, i = 1, ... 'm.
The probability distribution p is consistent if it satis fies the set of logical sentences together with their prob abilities, i.e., if for each sentence Si, the sum of pj's over all truth assignment wJ that satisfy Si (i.e., wf = 1) equals 1Ti.
For a given set S of sentences, let A 5 be an m x k matrix such that a~ is equal to 1 if si is true for wJ' and equal to 0 otherwise. This leads to the following linear programming formulation of the PSAT problem (in decision form):
where n is a unit row k-vector. The problem PSAT thus reduces to determining whether there exists or not a vec tor p satisfying (1). Observe that (PSAT) is completely determined by the pair (S, 1r).
Let us assume that the PSAT problem defined by (1) is consistent. Let Sm+l denote an additional logical sen tence, with an unknown probability 1T m+l · The opti mization form of PSAT (also known as probabilistic en tailment, see [Nilsson, 1986]), is to determine the range [ZLm+l, 7f m+l] of values of the probability 1Tm+l such that (S U {Sm+l}, (1r, 1Tm+d) is consistent. Consider the ob jective function Am+lP (with Am+l = (am+l ,j), where am+l,j is equal to 1 if Sm+l is true for the possible word wJ and equal to 0 otherwise). PSAT corresponds to de ~rmining ZLmtl = min {Am+l? : constraints (1)} and 1Tm+1 =max tAm+lP: constramts (1)}.
2.1 Numerical solution of PSAT
The linear program which expresses the PSAT problem in its decision or optimization form has an exponential number of variables in the size of the input; for this reason, in the sequel we will speak of Generalized Linear Programming (GLP for short) formulation. So writing explicitly PSAT already requires exponential time. This led Nilsson [Nilsson, 1986] to suggest looking for heuristic solution methods only.
Such a view is overly pessimistic since, although writ ing large PSAT problems explicitly is impossible, they can be solved quite efficiently by keeping them implicit. This can be done using the so-called column generation technique [Lasdon, 1970]. It extends the revised simplex method, in which only a small number of columns are kept explicitly. This technique makes use of a master problem which implies an objective and constraints re lated to the probabilities of the possible worlds, and a subproblem which determines the entering column for the master problem. This last subproblem depends on the structure of the original problem and has quite often a combinatorial nature. For more details see [Jaumard et al., 1991].
3 CMS and 1r-CMS models
The Assumption-based Truth Maintenance Systems (or ATMS for short) [de Kleer, 1986] and later the CMS (Clause Maintenance Systerps) [Reiter and de Kleer, 1987] can be viewed as symbolic algebra systems for producing a set of statements (Boolean expressions) in which one can believe. A brief description of the CMS is given below; details can be found in [Reiter and de Kleer, 1987].
Given a set of propositional variables X, a CMS con sists of a set of assumptions A = { a1, a2, ... , am} sup posed to be such that A C X and a set of proposi tional sentences H = { h1 , h2, ... , hr} (also called justifi cations, see [de Kleer, 1986]) such that the hi are clauses. Propositional sentences are assumed to be written using a CNF (Conjunctive Normal Form) expression in this paragraph. Therefore, a clause is a finite disjunction of literals with no literal repeated, also represented as a set of literals.
A clause .C(h) is a support for a clause h with respect to H iff H ~ .C(h) (i.e., H U { ·.C(h)} is satisfiable) and H f= .C(h) U h (i.e., H f= ·.C(h) :J h) . .C(h) is a minimal support for h with respect to H iff no proper subset of .C(h) is a support for h with respect to H. The CMS is a database management system which, given a set H of propositional sentences computes a minimal support clause, .C(h), for a clause h . .C(h) summarizes a list of sets of nonredundant assumptions (in terms of a Boolean formula), each of which is sufficient to support a proof of h. The .C(h) for a clause his related with a prime impli cant for H. This relationship is given as follows [Reiter and de Kleer, 1987]: .C(h) is a minimal support clause for h with respect to H iff there is a prime implicant 17 for H such that h n 17 =J 0 and .C (h) = 17 \ h. Conversely, if 17 is a prime implicant for H such that h ~ 17 then 17\ h is a minimal support clause for h with respect to H.
3.1 CMS Algorithms
The prime implicants can be used to implement CMSs [Reiter and de Kleer, 1987]. The prime implicants of a set of clauses can be computed by repeatedly resolv ing pairs of clauses, adding the resulting resolvents to the set and removing subsumed clauses. This method is known to be a brute-force approach and performs far more resolution steps than necessary. The running time of this algorithm depends on the number and expense of the subsumption checks required. De Kleer [de Kleer, 1992] describes an improved algorithm for generating the prime implicants of a set of clauses.
3.2 Adding Numerical Uncertainties
From a logical viewpoint, the .C(h) that the ATMS/CMS attaches to a clause yield only three possible truth val ues for h: believed, disbelieved, and unknown. This three-value logic cannot rate the degree of uncertainty associated with unknown clauses, and thus may lead to a stalemate whenever a decision is to be made whose outcome depends critically on the truth of these proposi tions. For this and others reasons, several attempts have been made to augment ATMS/CMS with a numerical measure of uncertainty. Several authors use probability theory to deal with uncertainty associated with assump tions for ATMS (De Kleer and Williams [de Kleer and Williams, 1987] and Liu et al. [Liu et al., 1993]) or CMS (Kohlas et al. [Kohlas and Haenni, 1996]). In all ex tensions the probabilities assigned to assumptions must be independent (see [Hansen et al., 1999] for details) in order to calculate the degree of belief.
The quantitative judgment of belief can be measured by the degree of support and plausibility. The degree of support of h (dsp for short) is the probability of ar guments (.C(h)) in favor of it. Similarly, the degree of plausibility (dpl for short) of his 1 minus the probabil ity of arguments (.C( ·h) )against it.
As next shown, 1!'-CMS without independence condi tion can be reformulated using the linear programming expression of the PSAT problem.
4 Using PSAT Linear Programming expression to reformulate a 7r-CMS model
Consider the PSAT problem (S, 1!' 1 ) defined as follows: S = AUH where Si = ai (i = 1,2, ... ,m) and Si+m = hi (i = 1, 2, ... , r); 1!' 1 = (7r, :n. ), where 7r is a probability m-vector associated with the set A of assumptions and :n. is a unit r-vector (all the probabilities are equal to 1 for the setH of clauses). Note that lSI = m' with m' = m+ r. The clause h with unknown probability is associated with Sm'+I· Denote by Yi ~ Y the set of literals of clause hi, i.e., hi= V Y;EY; YJ·
First Formulation ( F1 )
The 1!'-CMS problem can be expressed using the GLP formulation of the PSAT problem: Master problem:
subject to:
Subproblem:
where u0 , uA and uH are the dual variables associated with the constraints (3)-(5), respectively.
This reformulation results in a PSAT problem with a subproblem corresponding to an unconstrained nonlin ear program in 0-1 variables.
Note that the set of propositional sentences of H has a specific structure, in that its probabilities are all equal to 1, i.e., these propositional sentences are always true. Exploring this structure leads to a second formulation.
Second Formulation ( F2 )
There is a natural partitioning of the constraints of the GLP defined by formulation F1 . Observe that satisfying the constraint (5) is equivalent to satisfying the equation:
i.e., to solving a satisfiability problem (SAT).
Hence, constraints (5) can be transferred to the sub problem, which then leads to consider in the master problem only the solutions of (5) which satisfy (3), (4), (6) and minimize or maximize (2).
We thus obtain the following GLP reformulation. Master problem:
subject to:
Subproblem:
The subproblem is now a linear program in the 2n 0-1 variables Xi, Xi (as the y1 are either variables Xt or Xt) with linear constraints.
Each column of (10) corresponds to a possible world wi, or equivalently a subset of assumptions with true/false values, which may imply Sm'+l, imply ·Sm'+l or neither. In the first two cases there is one correspond ing column in (8)-(11), and in the latter two. When minimizing Am'+lP, columns which have am'+l,j = 1 will have probability 0 if there are twin columns with am'+l,j' = 0. So 2Im+l will correspond to the sum of probabilities of those clauses which imply Sm'+l, i.e., to the degree of support of Sm'+l· When maximizing Am'HP, columns which have am'+l,j = 0 will have prob abilities 0 if there are twin columns with am'+l,J' = 1. So 7f m+I will correspond to 1 minus the sum of proba bilities of those clauses which imply ·Sm'+l, i.e., to the degree of plausibility of Sm'+l·
5 Solution Method
The method is an iterative one (in fact, the revised sim plex algorithm [Chvatal, 1983]) where at each iteration, we determine the column with the minimum (maximum) reduced cost by solving (7) in the case of F1 , i.e.,
where the uo and ui are the current dual variables asso ciated with the tautology S0 and with the propositional sentences Si, i = 1, ... , m', respectively. By associating the logical values true with 1 and false with 0 in each logical proposition, one can rewrite (13) as:
This optimization problem can be reformulated using arithmetic expressions of the propositional variables of X. This can easily be done with the convention 1 = true and 0 =false and the relations Xi Vxj =Xi +xi -x; x Xj, X; 1\ Xj = X; x Xj and 'Xi = 1 - Xi, where the left hand side variables are logical ones, and the right-hand side variables are integer ones. The choice of the enter ing column is thus reduced to a problem of minimizing (maximizing) an unconstrained nonlinear function in 0-1 variables (PNL-0/1). In formulation F2 the subproblem is a constrained linear program in 0-1 variables (CPL0/1).
5.1 Basic Algorithm
We assume that the optimization problem is a minimiza tion one. Algorithm 1 provides a description of the col umn generation method for Formulation F1 or F2 .
Phase-1 is not detailed as it proceeds in a similar way than Phase-2, i.e., through STEP 3 to STEP 7.
5.2 Solution of the Subproblems
Again assume that the optimization problem is a mini mization one. At each iteration a column with a negative reduced cost must be found by a heuristic or an exact al-. gorithm. Exact solution of the subproblem is not neces sary at each iteration to guarantee convergence. As long as a negative reduced cost is found by the heuristic an iteration of the revised simplex algorithm may be done. If a feasible solution is obtained in that way, the decision version of the satisfiability problem is solved, but finding none when choosing the entering column in a heuristic way cannot guarantee that none exists. So, when no more negative reduced cost is obtained by the heuristic it is necessary to turn to an exact algorithm to prove that there is no feasible solution for the decision version of PSAT, nor feasible solution giving a better bound than the incumbent one for the optimization version. We use a Steepest Ascent Mildest Descent (SAMD) or Tabu Search (TS) heuristic ([Hansen and Jaumard, 1990; Glover and Laguna, 1997]) for PNL-0/1, and a variant of Tabu Search for CPL-0/1 with constraints to find an approximately optimal solution. We also use a method based on linearization for PNL-0/1, and branch-and bound for CPL-0/1, to find an exact optimal solution.
Algorithm 1 Column Generation Method
- STEP 1. Using phase-1 of the simplex algorithm (see, e.g. [Chvatal, 1983] for details), build an initial matrix Eo associated with a fea sible solution.
- STEP 2. If there is no such matrix E0 then the prob lem is inconsistent: Stop.
- STEP 3. Solve the master problem to compute the dual variables (p'hase-2 of the simplex al gorithm).
- STEP 4. Solve the subproblem to compute a col umn with negative reduced cost Ct using a heuristic;
- STEP 5. If Ct < 0 then add the corresponding col umn to the master problem, reoptimize it, and go to STEP 3.
- STEP 6. Solve the subproblem to compute the col umn with the most negative reduced cost using an exact algorithm.
- STEP 7. If Ct < 0 then add the corresponding col umn to the master problem, reoptimize it, and go to STEP 3.
- STEP 8. Stop: the optimal solution has been reached.
PNL-0/1 without constraints
The Tabu Search (TS) heuristic proceeds to a local op timum by moving at each iteration from one feasible so lution to another in its neighborhood (here the vectors at Hamming distance 1 from the current one). We then pick the solution in the neighborhood that produces the best improvement in the objective function. If there is no improving solution (a local optimum was reached as suming we use aspiration, see page 50 in [Glover and Laguna, 1997]) then we choose that one which degrades the objective function least. In order to avoid return ing to the local optimum just visited, or cycling, the re verse move is forbidden for a given number of iterations (SizeM axTa!m).
The steps of TS are presented in Algorithm 2. The pa rameters Tj denote the remaining number of iterations during which a local change in direction j is forbidden. When a change in an ascent direction j is done Tj is set at the value tabu. That value is chosen by random selec tion among integers in the range (1 , SizeM axTabu]. The stopping condition may be, e.g., maximum computing time allowed, maximum number of iterations, or maxi mum number of iterations between two improvements.
The linearization method works by replacing in a stan dard way each product of variables by a new 0-1 variable and adding constraints to ensure that the values agree in 0-1 variables.
The size of the resulting linear 0-1 variables increases rapidly with m, n and the number of nonzero dual vari ables ui.
- STEP 1. Select a feasible solution x and let z(x) be the value associated with x. Set Xopt := x, Zopt := z(x), and T empty, the directions where changes are forbidden. Choose a stopping condition.
- STEP 2. Transform x into the solution Xj modified in the lh direction and evaluate Oj := z(xj) - z(x) with Tj = 0. Let Ok := min{oi : Ti = 0}. If ok :::; 0, Tk := tabu. Set x := xk.
- STEP 3. If z(xk) < Zopt then update Xopt := Xk and Zopt := z(xk)·
- STEP 4. If the stopping condition is met then
- STOP.
Otherwise, update T and return to STEP 2.
CPL-0/1 with constraints
Heuristic solution of CPL-0/1 is again done by a SAMD or TS algorithm. The idea behind this algorithm is to allow infeasibility. However it must be limited, therefore for each sequence of iterations a move is allowed only if the resulting number of unsatisfied clauses (or violated constraints) is smaller than a given threshold UnsatMax. After a number of iterations we verify if the current so lution is feasible. In the affirmative we reduce the value of UnsatMax by /3 and another sequence of iterations is performed. In the negative the value of UnsatMax is in creased by a, we apply a transformation to get a feasible solution and another sequence of iterations is performed. The overall algorithm has a maximum number of REP iterations. Steps of the TS-Constrained heuristic are pre sented on Algorithm 3.
The constrained linear 0-1 program (12) has the form of a combined set covering and set partitioning problem. Exact solution is based on the algorithm of [Fisher and Kedia, 1990]. The main feature of this algorithm is the use of dual variables in the linear programming relax ation to provide lower bounds for a branch-and-bound algorithm.
6 Computational Experiments
The algorithms for ?r-CMS/PSAT described in the pre vious sections have been coded in C and tested on a Ultra-2 SUN SPARC computer. The resulting program uses the CPLEX 6.0 package for linear programming. The problems for 1r-CMS/PSAT were randomly gener ated in the following way: (i) the numbers m of assump tions, r of justifications, which here are clauses, n of variables (assumptions and propositional symbols) are parameters; (ii) the clauses contain at most 4 literals. There is an uniform distribution of clauses with 1, 2, 3 and 4 literals as well as of uncomplemented and comple mented variables. Probabilities ?ri(A) corresponding to feasible problems were obtained by generating randomly
Algorithm 3 Tabu Search-Constrained
- STEP 1. Select a solution x (not necessarily feasi ble) and let z(x) denote the value associ ated with x. Set Xopt := x, Zopt := z(x), iter := 1 and T empty. Choose the val ues of UnsatMax, REP and a stopping condition.
- STEP 2. Transform x into the solution xi mod ified in the lh direction and evaluate Oj := z(xi) - z(x) with Tj = 0. Let ok := min{oj : Tj = 0 and unsat < UnsatMax}. If Ok :S 0, Tk := tabu. Set x := xk .
- STEP 3. If z(xk) < Zopt and xk feasible then update Xopt := xk and Zopt := z(xk).
- STEP 4. If the stopping condition is met then Stop. Otherwise, update T and return to STEP 2.
- STEP 5. If xk is feasible then U nsatM ax · U nsatM ax - /3 * U nsatM ax. Otherwise UnsatMax =a* UnsatMax.
- STEP 6. iter := iter + 1.
- STEP 7. If iter < REP then return to STEP 2. Otherwise Stop . .
max(2 10 ; 2n) Boolean vectors x, constructing the corre sponding possible worlds, associating with them positive numbers summing up to 1 (i .e., probabilities for these worlds to occur), and then summing for each clause the probabilities of the worlds in which it is true.
Results of the comparison between the two ?r CMS/PSAT models are given in Table 1 and 2, which detail problem sizes, total cpu time, number of columns generated, cpu time for the tabu search and the exact algorithms for the subproblems. Each line corresponds to averages over five problems. Note than the number of propositions m' in the first formulation is equal to the number of assumptions (propositions in the master prob lem) plus the number of justifications (considered only in the subproblems) in the second formulation. Clearly the second formulation is by far superior to the first one: computation times for the larger instances are 7000 times smaller.
If an independence condition is imposed on the as sumptions, only much smaller instances of 1r-CMS are solvable in reasonable time. If columns corresponding to feasible worlds are considered explicitly, each has a positive probability and their number increases exponen tially. This contrast with the linear programming model of PSAT, where the number of columns with positive probability in a basic, and hence in an optimal, solution is at most equal to the number of lines. Using Boolean simplifications we may reduce somewhat the computa tional burden but it often remains too high to solve large instances.
Intervals [KmH,1fmH] for 1r-CMS/PSAT and
| Problems | tcpu | Column | TS Heuristic | Exact Algorithm l | |||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| n | m' | tcpu 11 (s) | u | 11 | u | tcpu 11 (s) | u | Iter | tcpu 11 (s) | u | Iter |
| Maximization+Minimization | |||||||||||
| 100 | 100 | 17.278 | 6.376 | 712.80 | 140.599 | 1.96 | 0.41 | 714.80 | 0.01 | 0.01 | 3.60 |
| 100 | 150 | 3307.274 | 743.309 | 3863.00 | 255.948 | 12.66 | 0.95 | 3865.00 | 0.01 | 0.03 | 3.20 |
| 150 | 200 | 10890.038 | 3779.051 | 4464.00 | 208.784 | 22.51 | 1.70 | 4466.00 | 0.01 | 0.02 | 3.40 |
| Problems | tcpu | Column | TS Heuristic | Exact Algorithm | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| n | m | r | tcpu 11 (s) | tcpu 11 (s) | u | Iter | tcpu 11 (s) | u | Iter | |||
| Maximization+Minimization | ||||||||||||
| 100 | 50 | 50 | 0.532 | 0.043 | 20.20 | 1.939 | 0.41 | 0.03 | 22.20 | 0.05 | 0.15 | 2.20 |
| 100 | 50 | 100 | 0.984 | 0.183 | 26.80 | 4.308 | 0.82 | 0.12 | 28.80 | 0 .08 | 0.21 | 2.80 |
| 150 | 100 | 100 | 1.532 | 0.136 | 32.80 | 3.370 | 1.24 | 0.11 | 34.80 | 0.09 | 0.22 | 2.20 |
[dsp, dpl] for 1r-CMS with independence condition (obtained with the ABEL program [Anrig et al., 1998]) are given in Table 3. It appears that in some cases the intervals of 1r-CMS with the independence conditions overlap in part with those of 1r-CMS/PSAT instead of being included in them, as one would have expected. This indicates 1r-CMS does not exploit the available information to its fullest degree. Reasons why this is so will be explored in future work.
| I Problems | I | PSAT | ABEL | ||
|---|---|---|---|---|---|
| n | m | r I | 7r m+1-7r m+1 - | dsp-dpl | |
| 15 | 10 | 20 | 0.0000-0.5513 | 0.000-0.313 | |
| 15 | 10 | 20 | 0 .1 046-1.0000 | 0.037-1.000 | |
| 15 | 10 | 20 | 0.3666-1.0000 | 0.473-1.000 | |
| 15 | 10 | 20 | 0.4301-1.0000 | 0.601-1.000 | |
7 Conclusions
1r-CMS systems can be expressed in two ways as a PSAT problem, when the independence condition on the as sumptions is removed. Then the lower and upper bounds on the probability of the additional propositional sen tence coincide with its support and plausibility. The second formulation , which keeps the justifications im plicit (or transfer them to the subproblem when using column generation as solution method), is much more efficient than the first, direct one. If the independence condition is kept in 1r-CMS, solution becomes more cum bersome and probability intervals for the objective func tion clause provided by both methods may overlap.
Acknowledgments
Research of the authors was supported by DREV Valcartier contract. Work of the first and second au thors was supported by FCAR grants 92-EQ-1048 and 95-ER-1048. Work of the first has also been sup ported by NS.ERC grant to HEC and NSERC grant GP0105574. Work of the second author was also sup ported by NSERC grants GP0036426 and EQP0157431. Work of the third author has also been supported by CNPq (Conselho Nacional de Desevolvimento Cientifico e Tecnol6gico), Brazil, grant 200722/95-6.
@inproceedings{ijcai1999p9,
title = {On the Relations between Probabilistic Logic and p-CMS},
author = {Hansen, Pierre and Jaumard, Brigitte and Parreira, A. D.},
booktitle = {Proceedings of the Sixteenth International Joint Conference on
Artificial Intelligence, {IJCAI-99}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Thomas Dean},
pages = {56--62},
year = {1999},
note = {Automated Reasoning},
url = {https://ijcai.org/proceedings/1999/9},
}
TY - CPAPER TI - On the Relations between Probabilistic Logic and p-CMS AU - Hansen, Pierre AU - Jaumard, Brigitte AU - Parreira, A. D. T2 - Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99 PB - International Joint Conferences on Artificial Intelligence PY - 1999 SP - 56 EP - 62 UR - https://ijcai.org/proceedings/1999/9 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: