Probabilistic logic under coherence: complexity and algorithms. (English) Zbl 1083.03027

Summary: In previous work [“Probabilistic logic under coherence, model-theoretic probabilistic logic, and default reasoning in System P”, J. Appl. Non-Class. Log. 12, 189–213 (2002; Zbl 1038.03023)], we have explored the relationship between probabilistic reasoning under coherence and model-theoretic probabilistic reasoning. In particular, we have shown that the notions of g-coherence and of g-coherent entailment in probabilistic reasoning under coherence can be expressed by combining notions in model-theoretic probabilistic reasoning with concepts from default reasoning. In this paper, we continue this line of research. Based on the above semantic results, we draw a precise picture of the computational complexity of probabilistic reasoning under coherence. Moreover, we introduce transformations for probabilistic reasoning under coherence, which reduce an instance of deciding g-coherence or of computing tight intervals under g-coherent entailment to a smaller problem instance, and which can be done very efficiently. Furthermore, we present new algorithms for deciding g-coherence and for computing tight intervals under g-coherent entailment, which reformulate previous algorithms using terminology from default reasoning. They are based on reductions to standard problems in model-theoretic probabilistic reasoning, which in turn can be reduced to linear optimization problems. Hence, efficient techniques for model-theoretic probabilistic reasoning can immediately be applied for probabilistic reasoning under coherence (for example, column generation techniques). We describe several such techniques, which transform problem instances in model-theoretic probabilistic reasoning into smaller problem instances. We also describe a technique for obtaining a reduced set of variables for the associated linear optimization problems in the conjunctive case, and give new characterizations of this reduced set as a set of non-decomposable variables, and using the concept of random gain.


03B48 Probability and inductive logic
68T37 Reasoning under uncertainty in the context of artificial intelligence


Zbl 1038.03023
Full Text: DOI


[1] S. Amarger, D. Dubois and H. Prade, Constraint propagation with imprecise conditional probabilities, in: Proceedings UAI-1991 (1991) pp. 26–34.
[2] S. Benferhat, D. Dubois and H. Prade, Nonmonotonic reasoning, conditional objects and possibility theory, Artificial Intelligence 92(1-2) (1997) 259–276. · Zbl 1017.68539 · doi:10.1016/S0004-3702(97)00012-X
[3] V. Biazzo and A. Gilio, A generalization of the fundamental theorem of de Finetti for imprecise conditional probability assessments, International Journal of Approximate Reasoning 24(2-3) (2000) 251–272. · Zbl 0995.68124 · doi:10.1016/S0888-613X(00)00038-4
[4] V. Biazzo and A. Gilio, On the linear structure of betting criterion and the checking of coherence, Annals of Mathematics and Artificial Intelligence 35 (2002) 83–106. · Zbl 1001.68097 · doi:10.1023/A:1014570831884
[5] V. Biazzo and A. Gilio, Some theoretical properties of interval-valued conditional probability assessments, in: Proceedings ISIPTA-2005 (2005) pp. 58–67. · Zbl 1122.68636
[6] V. Biazzo, A. Gilio, T. Lukasiewicz and G. Sanfilippo, Probabilistic logic under coherence, model-theoretic probabilistic logic, and default reasoning in System P, Journal of Applied Non-Classical Logics 12(2) (2002) 189–213. · Zbl 1038.03023 · doi:10.3166/jancl.12.189-213
[7] V. Biazzo, A. Gilio and G. Sanfilippo, Coherence checking and propagation of lower probability bounds, Soft Computing 7 (2003) 310–320. · Zbl 1088.68797
[8] V. Biazzo, A. Gilio and G. Sanfilippo, Efficient checking of coherence and propagation of imprecise probability assessments, in: Proceedings IPMU-2000 (Madrid, Spain, 2000) pp. 1973–1976.
[9] G. Boole, An Investigation of the Laws of Thought, on which are Founded the Mathematical Theories of Logic and Probabilities (Walton and Maberley, London, 1854) (reprint: Dover, New York, 1958). · Zbl 1205.03003
[10] A. Capotorti, L. Galli and B. Vantaggi, How to use strong local coherence in an inferential process based on upper-lower probabilities in: Proceedings WUPES-2000 (Jindřich \( {\mathop {\text{u}}\limits^ \cdot } \) v Hradec, Czech Republic, 2000) pp. 14–28.
[11] A. Capotorti and B. Vantaggi, An algorithm for coherent conditional probability assessments, in: Proceedings IV Congresso Nazionale SIMAI, Vol. 2 (Giardini Naxos, Messina, Italy, 1998) pp. 144–148.
[12] A. Charnes and W.W. Cooper, Programming with linear fractional functionals, Naval Research Logistics Quarterly 9 (1962) 181–186. · Zbl 0127.36901 · doi:10.1002/nav.3800090303
[13] G. Coletti, Coherent numerical and ordinal probabilistic assessments, IEEE Transactions on Systems, Man, and Cybernetics 24(12) (1994) 1747–1754. · Zbl 1371.68265 · doi:10.1109/21.328932
[14] G. Coletti and R. Scozzafava, Characterization of coherent conditional probabilities as a tool for their assessment and extension, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 4(2) (1996) 103–127. · Zbl 1232.03010 · doi:10.1142/S021848859600007X
[15] G. Coletti and R. Scozzafava, Conditional measures: Old and new, in: Proceedings of New Trends in Fuzzy Systems, Napoli, Italy, 1996, eds. D. Mancini, M. Squillante and A. Ventre (World Scientific, Singapore, 1998) pp. 107–120.
[16] G. Coletti and R. Scozzafava, Exploiting zero probabilities, in: Proceedings EUFIT-1997 (Aachen, Germany, 1997) pp. 1499–1503.
[17] G. Coletti and R. Scozzafava, Coherent upper and lower Bayesian updating, in: Proceedings ISIPTA-1999 (Ghent, Belgium, 1999) pp. 101–110.
[18] G. Coletti and R. Scozzafava, Conditioning and inference in intelligent systems, Soft Computing 3(3) (1999) 118–130.
[19] G. Coletti and R. Scozzafava, The role of coherence in eliciting and handling imprecise probability and its application to medical diagnosis, Information Sciences 130 (2000) 41–65. · Zbl 0984.68155 · doi:10.1016/S0020-0255(00)00085-2
[20] G. Coletti and R. Scozzafava, Probabilistic Logic in a Coherent Setting (Kluwer, Dordrecht, Netherlands, 2002). · Zbl 1005.60007
[21] D. Du, J. Gu and P.M. Pardalos (eds.), Satisfiability Problem: Theory and Applications, Vol. 35 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science (American Mathematical Society, 1997). · Zbl 0881.00041
[22] D. Dubois, H. Prade and J.-M. Touscas, Inference with imprecise numerical quantifiers, in: Intelligent Systems, Chapt. 3, eds. Z.W. Ras and M. Zemankova (Ellis Horwood, 1990) pp. 53–72.
[23] T. Eiter and T. Lukasiewicz, Default reasoning from conditional knowledge bases: Complexity and tractable cases, Artificial Intelligence 124(2) (2000) 169–241. · Zbl 0952.68139 · doi:10.1016/S0004-3702(00)00073-4
[24] R. Fagin, J.Y. Halpern and N. Megiddo, A logic for reasoning about probabilities, Information and Computation 87 (1990) 78–128. · Zbl 0811.03014 · doi:10.1016/0890-5401(90)90060-U
[25] A.M. Frisch and P. Haddawy, Anytime deduction for probabilistic logic, Artificial Intelligence 69 (1994) 93–122. · Zbl 0809.03016 · doi:10.1016/0004-3702(94)90079-5
[26] D.M. Gabbay and P. Smets (eds.), Handbook on Defeasible Reasoning and Uncertainty Management Systems (Kluwer, Dordrecht, Netherlands, 1998). · Zbl 0908.90002
[27] D. Gale, The Theory of Linear Economic Models (McGraw-Hill, New York, 1960). · Zbl 0114.12203
[28] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979). · Zbl 0411.68039
[29] G. Georgakopoulos, D. Kavvadias and C. Papadimitriou, Probabilistic satisfiability, Journal of Complexity 4(1) (1988) 1–11. · Zbl 0647.68049 · doi:10.1016/0885-064X(88)90006-4
[30] A. Gilio, Algorithms for precise and imprecise conditional probability assessments, in: Mathematical Models for Handling Partial Knowledge in Artificial Intelligence, eds. G. Coletti, D. Dubois and R. Scozzafava (Plenum, New York, 1995) pp. 231–254. · Zbl 0859.68042
[31] A. Gilio, Probabilistic consistency of conditional probability bounds, in: Advances in Intelligent Computing, Vol. 945 of LNCS (Springer, 1995) pp. 200–209.
[32] A. Gilio, Precise propagation of upper and lower probability bounds in System P, in: Proceedings NMR-2000 (Breckenridge, Colorado, USA, 2000).
[33] A. Gilio, Probabilistic reasoning under coherence in System P, Annals of Mathematics and Artificial Intelligence 34 (2002) 5–34. · Zbl 1014.68165 · doi:10.1023/A:1014422615720
[34] A. Gilio and R. Scozzafava, Conditional events in probability assessment and revision, IEEE Transactions on Systems, Man, and Cybernetics 24(12) (1994) 1741–1746. · Zbl 1371.60002 · doi:10.1109/21.328931
[35] M. Goldszmidt and J. Pearl, On the consistency of defeasible databases, Artificial Intelligence 52(2) (1991) 121–149. · Zbl 0749.68026 · doi:10.1016/0004-3702(91)90039-M
[36] T. Hailperin, Boole’s Logic and Probability, 2nd edition (North-Holland, Amsterdam, 1986). · Zbl 0611.03001
[37] P. Hansen, B. Jaumard, G.-B.D. Nguetsé and M.P. de Aragão, Models and algorithms for probabilistic and Bayesian logic, in: Proceedings IJCAI-1995 (1995) pp. 1862–1868.
[38] B. Jaumard, P. Hansen and M.P. de Aragão, Column generation methods for probabilistic logic, ORSA Journal on Computing 3 (1991) 135–147. · Zbl 0800.68864
[39] B. Jenner and J. Toran, Computing functions with parallel queries to NP, Theoretical Computer Science 141 (1995) 175–193. · Zbl 0873.68058 · doi:10.1016/0304-3975(94)00080-3
[40] D.S. Johnson, A catalog of complexity classes, in: Handbook of Theoretical Computer Science, Vol. A., Chapt. 2, ed. J. van Leeuwen (MIT, Cambridge, Massachusetts, 1990) pp. 67–161. · Zbl 0900.68246
[41] T. Lukasiewicz, Efficient global probabilistic deduction from taxonomic and probabilistic knowledge-bases over conjunctive events, in: Proceedings of the 6th International Conference on Information and Knowledge Management (1997) pp. 75–82.
[42] T. Lukasiewicz, Local probabilistic deduction from taxonomic and probabilistic knowledge-bases over conjunctive events, International Journal of Approximate Reasoning 21(1) (1999) 23–61. · Zbl 0961.68135 · doi:10.1016/S0888-613X(99)00006-7
[43] T. Lukasiewicz, Probabilistic deduction with conditional constraints over basic events, Journal of Artificial Intelligence Research 10 (1999) 199–241. · Zbl 0914.68178
[44] T. Lukasiewicz, Probabilistic logic programming with conditional constraints, ACM Transactions on Computational Logic 2(3) (2001) 289–339. · Zbl 1171.68762 · doi:10.1145/377978.377983
[45] T. Lukasiewicz, Probabilistic default reasoning with conditional constraints, Annals of Mathematics and Artificial Intelligence 34(1-3) (2002) 35–88. · Zbl 1002.68175 · doi:10.1023/A:1014445017537
[46] T. Lukasiewicz, Weak nonmonotonic probabilistic logics, in: Proceedings KR-2004 (2004) pp. 23–33. Artificial Intelligence 168(1–2) (2005) 119–161.
[47] T. Lukasiewicz, Nonmonotonic probabilistic logics under variable-strength inheritance with overriding: Algorithms and implementation in nmproblog, in: Proceedings ISIPTA-2005 (2005) pp. 230–239.
[48] C. Luo, C. Yu, J. Lobo, G. Wang and T. Pham, Computation of best bounds of probabilities from uncertain data, Computational Intelligence 12(4) (1996) 541–566. · doi:10.1111/j.1467-8640.1996.tb00276.x
[49] N.J. Nilsson, Probabilistic logic, Artificial Intelligence 28 (1986) 71–88. · Zbl 0589.03007 · doi:10.1016/0004-3702(86)90031-7
[50] C.H. Papadimitriou, Computational Complexity (Addison-Wesley, Reading, Massachusetts, 1994). · Zbl 0833.68049
[51] R. Pelessoni and P. Vicig, A consistency problem for imprecise conditional probability assessments, in: Proceedings IPMU-1998 (Paris, France, 1998) pp. 1478–1485.
[52] R. Scozzafava, Subjective conditional probability and coherence principles for handling partial information, Mathware & Soft Computing 3(1) (1996) 183–192.
[53] A. Selman, A taxonomy of complexity classes of functions, Journal of Computer and System Sciences 48 (1994) 357–381. · Zbl 0806.68049 · doi:10.1016/S0022-0000(05)80009-1
[54] L. van der Gaag, Computing probability intervals under independency constraints, in: Uncertainty in Artificial Intelligence 6 (North-Holland, Amsterdam, 1991) pp. 457–466.
[55] P. Vicig, An algorithm for imprecise conditional probability assessments in expert systems, in: Proceedings IPMU-1996 (Granada, Spain, 1996) pp. 61–66.
[56] K.W. Wagner, More complicated questions about maxima and minima, and some closures of NP, Theoretical Computer Science 51 (1987) 53–80. · Zbl 0653.03027 · doi:10.1016/0304-3975(87)90049-1
[57] P. Walley, Statistical Reasoning with Imprecise Probabilities (Chapman and Hall, London, 1991). · Zbl 0732.62004
[58] P. Walley, R. Pelessoni and P. Vicig, Direct algorithms for checking coherence and making inferences from conditional probability assessments, Journal of Statistical Planning and Inference 126(1) (2004) 119–151. · Zbl 1075.62002 · doi:10.1016/j.jspi.2003.09.005
[59] P.M. Williams, Notes on Conditional Previsions. Technical Report, School of Mathematical and Physical Sciences, University of Sussex (1975). · Zbl 1114.60005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.