×

zbMATH — the first resource for mathematics

Probabilistic sentence satisfiability: an approach to PSAT. (English) Zbl 07153705
Summary: Information analysis often involves heterogeneous sources expressed as logical sentences, numerical models, sensor data, etc. Each of these has its own way to describe uncertainty or error; e.g., frequency analysis, algorithmic truncation, floating point roundoff, Gaussian distributions, etc. A unifying framework is proposed here to represent this information as logical sentences with associated probabilities in order to allow the inference of the probability of a query sentence.
Given such a knowledge base in Conjunctive Normal Form (CNF) for use by an intelligent agent, with probabilities assigned to the conjuncts, the probability of any new query sentence can be determined by solving the Probabilistic Satisfiability Problem (PSAT). This involves finding a consistent probability distribution over the atoms (if they are independent) or complete conjunction set of the atoms. For each sentence in the knowledge base, we propose to produce an equation in terms of atoms and conditional probabilities. This system of equations is then solved numerically to get a solution consistent with the sentence probabilities. Finding such a solution is called the Probabilistic Sentence Satisfiability (PS-SAT) problem. In particular, findings include:
1.
For independent logical variables:
(a)
atom probabilities which solve PS-SAT also provide a PSAT solution.
(b)
numerical experiments demonstrate a q-superlinear convergence rate for most test cases.
(c)
problems with up to 1,000 variables and 300 sentences are solved.
2.
For general knowledge bases (i.e., variables not independent):
(a)
both atom and a subset of conditional probabilities must be found,
(b)
a solution to PS-SAT does not guarantee a solution to PSAT, but most empirical results provide such a solution.
(c)
The convergence rate for equations with non-independent variables also appears q-superlinear.
MSC:
68T Artificial intelligence
Software:
BLOG; BRECCIA; GenPSAT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Sacharny, D.; Henderson, T.; Simmons, R.; Mitiche, A.; Welker, T.; Fan, X., BRECCIA: a novel multi-source fusion framework for dynamic geospatial data analysis, (Proceedings of the IEEE Conference on Multisensor Fusion and Integration for Intelligent Systems. Proceedings of the IEEE Conference on Multisensor Fusion and Integration for Intelligent Systems, Daegu, South Korea (2017))
[2] Flum, J.; Grohe, M., Parameterized Complexity Theory (2006), Springer Verlag: Springer Verlag Berlin, Germany
[3] Hansen, P.; Perron, S., Merging the local and global approaches to probabilistic satisfiability, Int. J. Approx. Reason., 47, 125-140 (2008) · Zbl 1343.68220
[4] Boole, G., An Investigation of the Laws of Thought (1857), Walton and Maberly: Walton and Maberly London, UK
[5] Bacchus, F., Representing and Reasoning with Probabilistic Knowledge (1990), MIT Press: MIT Press Cambridge, MA
[6] Halpern, J., An analysis of first-order logics of probability, Artif. Intell. J., 46, 3, 311-350 (1990) · Zbl 0723.03007
[7] Nilsson, N., Probabilistic logic, Artif. Intell. J., 28, 71-87 (1986) · Zbl 0589.03007
[8] Hailperin, T., Best possible inequalities for the probability of a logical function of events, Am. Math. Mon., 72, 4, 343-359 (1965) · Zbl 0132.13706
[9] Hailperin, T., Probability logic, Notre Dame J. Form. Log., 25, 3, 198-212 (1984) · Zbl 0547.03018
[10] Georgakopoulos, G.; Kavvadias, D.; Papadimitriou, C., Probabilistic satisfiability, J. Complex., 4, 1-11 (1988) · Zbl 0647.68049
[11] Henderson, T.; Mitiche, A.; Simmons, R.; Fan, X., A Preliminary Study of Probabilistic Argumentation (February 2017), University of Utah, Tech. Rep. UUCS-17-001
[12] Adams, E., A Primer of Probability Logic (1998), CLSI Publications: CLSI Publications Stanford, CA · Zbl 0910.68202
[13] Hailperin, T., Boole’s Logic and Probability (1976), North Holland Publishing Company: North Holland Publishing Company Amsterdam, the Netherlands · Zbl 0352.02002
[14] Hailperin, T., Sentential Probability Logic (1996), Lehigh University Press: Lehigh University Press Cranbury, NJ · Zbl 0922.03026
[15] Hunter, A., A probabilistic approach to modelling uncertain logical arguments, Int. J. Approx. Reason., 54, 47-81 (2013) · Zbl 1266.68176
[16] Ognjanovic, Z.; Raskovic, M., Some first-order probability logics, J. Theor. Comput. Sci., 247, 191-212 (2000) · Zbl 0954.03024
[17] Abadi, M.; Halpern, J., Decidability and expresiveness for first-order logics of probability, J. Inf. Comput., 112, 1-36 (1994) · Zbl 0799.03017
[18] Bacchus, F.; Halpern, J.; Levesque, H., Reasoning about noisy sensors and effectors in the situation calculus, Artif. Intell. J., 111, 1-2, 171-208 (1999) · Zbl 0996.68192
[19] Belle, V.; Lakemeyer, G., Reasoning about probabilities in unbounded first-order dynamical domains, (Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence. Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, Melbourne, Australia (2017))
[20] Fierens, D.; van den Broack, G.; Renkens, J.; Shterionov, D.; Gutmann, B.; Thon, I.; Janssens, G.; de Raedt, L., Inference and learning in probabilistic logic programs using weighted Boolean formulas, Artif. Intell. J. Theory Pract. Logic Program., 15, 3, 358-401 (2015) · Zbl 1379.68062
[21] Chavira, M.; Darwiche, A., On probabilistic inference by weighted model counting, Artif. Intell. J., 172, 772-799 (2008) · Zbl 1182.68297
[22] Milch, B.; Marthi, B.; Sontag, D.; Russell, S.; Ong, D.; Kolobov, A., BLOG: probabilistic models with unknown objects, (Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland (2005))
[23] Milch, B., Probabilistic Models with Unknown Objects (2006), University of California: University of California Berkeley, Berkeley, CA, Ph.D. thesis
[24] Chakraborty, S.; Fremont, D.; Meel, K.; Seshia, S.; Vardi, M., Distribution-aware sampling and weighted model counting for SAT, (Proceedings of the Twenty-Eigth AAAI Conference on Artificial Intelligence. Proceedings of the Twenty-Eigth AAAI Conference on Artificial Intelligence, Quebec City, Canada (2014)), 1722-1730
[25] Roth, D., On the hardness of approximate reasoning, Artif. Intell. J., 82, 273-302 (1996)
[26] Dal, G.; Michels, S.; Lucas, P., Reducing the cost of probabilistic knowledge compilation, Proc. Mach. Learn. Res., 73, 141-152 (2017)
[27] Darwiche, A.; Marquis, P., A knowledge compilation map, J. Artif. Intell. Res., 17, 229-264 (2002) · Zbl 1045.68131
[28] Getoor, L.; Taskar, B., Introduction to Statistical Relational Learning (2007), MIT Press: MIT Press Cambridge, MA · Zbl 1141.68054
[29] Koller, D.; Friedman, N., Proabilistic Graphical Models: Principles and Techniques (2009), MIT Press: MIT Press Cambridge, MA
[30] Biba, M., Integrating Logic and Probability: Algorithmic Improvements in Markov Logic Networks (2009), University of Bari: University of Bari Bari, Italy, Ph.D. thesis
[31] Domingos, P.; Lowd, D., Markov Logic: An Interface Layer for Artificial Intelligence (2009), Morgan and Claypool: Morgan and Claypool San Rafael, CA · Zbl 1202.68403
[32] Gogate, V.; Domingos, P., Probabilistic theorem proving, Commun. ACM, 59, 7, 107-115 (2016)
[33] Seidenfeld, T., Why I am not an objective Bayesian, Theory Decis., 11, 413-449 (1979)
[34] Thimm, M., Measuring inconsistency in probabilistic knowledge bases, (Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, Montreal, Quebec, Canada (2009)), 530-537
[35] Thimm, M., A probabilistic semantics for abstract argumentation, (Proceedings of the 20th European Conference on Artificial Intelligence. Proceedings of the 20th European Conference on Artificial Intelligence, Montpellier, France (2012)) · Zbl 1327.68290
[36] Hansen, P.; Jaumard, B., Probabilistic Satisfiability (March 1996)
[37] Finger, M.; de Bona, G., Probabilistic satisfiability: logic-based algorithms and phase transitions, (Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, Barcelona, Spain (2011))
[38] Finger, M.; de Bona, G., Probabilistic satisfiability: algorithms with the presence and absence of a phase transitions, Ann. Math. Artif. Intell., 75, 3-4, 351-389 (2015) · Zbl 1347.68331
[39] Caleiro, C.; Casal, F.; Mordido, A., Generalized probabilistic satisfiability, Electron. Notes Theor. Comput. Sci., 332, 39-56 (2017) · Zbl 1401.68113
[40] Downey, R.; Fellow, M., Parameterized Complexity (1999), Springer Verlag: Springer Verlag Berlin, Germany
[41] Wozniaskowski, H., Numerical stability for solving nonlinear equations, Numer. Math., 27, 4, 373-390 (1976)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.