×

A hybrid method for probabilistic satisfiability. (English) Zbl 1341.68191

Bjørner, Nikolaj (ed.) et al., Automated deduction – CADE-23. 23rd international conference on automated deduction, Wrocław, Poland, July 31 – August 5, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22437-9/pbk; 978-3-642-22438-6/ebook). Lecture Notes in Computer Science 6803. Lecture Notes in Artificial Intelligence, 354-368 (2011).
Summary: Determining satisfiability of sets of formula formulated in a Nilsson style probabilistic logic (PSAT) by reduction to a system of linear (in)equations has been extensively studied, esp. in the propositional setting. The basic technique for coping with the potentially exponentially large (in terms of the formulae) linear system is column generation, which has been successful (in various forms) in solving problems of around 1000 formulae. Common to existing techniques is that the column generation model explicitly encodes all classical, i.e., non-probabilistic, knowledge. In this paper we introduce a straightforward but new hybrid method for PSAT that makes use of a classical solver in the column generation process. The benefits of this technique are twofold: first, we can, in practice, accommodate inputs with significantly larger classical parts, and thus which are overall larger, and second, we can accommodate inputs with supra-propositional classical parts, such as propositionally complete description logics. We validate our approach with an extensive series of experiments which show that our technique is competitive with traditional non-hybrid approaches in spite of scaling the expressivity of the classical part to the description logic \(\mathcal{SROIQ}\).
For the entire collection see [Zbl 1218.68006].

MSC:

68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
03B48 Probability and inductive logic
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68T27 Logic in artificial intelligence
68T30 Knowledge representation

Software:

Pellet
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hansen, P., Jaumard, B.: Probabilistic satisfiability. In: Handbook of Defeasible Reasoning and Uncertainty Management Systems, Algorithms for Uncertainty and Defeasible Reasoning, vol. 5, pp. 321–367. Kluwer, Dordrecht (2000) · Zbl 1015.68198 · doi:10.1007/978-94-017-1737-3_8
[2] Hansen, P., Jaumard, B., Nguetsé, G.B.D., de Aragão, M.P.: Models and algorithms for probabilistic and Bayesian logic. In: International Joint Conference on Artificial Intelligence, pp. 1862–1868 (1995)
[3] Hansen, P., Perron, S.: Merging the local and global approaches to probabilistic satisfiability. International Journal of Approximate Reasoning 47(2), 125–140 (2008) · Zbl 1343.68220 · doi:10.1016/j.ijar.2007.03.001
[4] Hooker, J.N.: Quantitative approach to logical reasoning. Decision Support Systems 4, 45–69 (1988) · doi:10.1016/0167-9236(88)90097-8
[5] Horrocks, I., Kutz, O., Sattler, U.: The even more irresistible \(\mathcal{SROIQ}\) . In: KR, pp. 57–67 (2006)
[6] Jaumard, B., Hansen, P., de Aragão, M.P.: Column generation methods for probabilistic logic. In: IPCOC, pp. 313–331 (1990) · Zbl 0800.68864
[7] Jaumard, B., Hansen, P., de Aragão, M.P.: Column generation methods for probabilistic logic. INFORMS Journal on Computing 3(2), 135–148 (1991) · Zbl 0800.68864 · doi:10.1287/ijoc.3.2.135
[8] Kazakov, Y.: SRIQ and SROIQ are harder than SHOIQ. In: KR, pp. 274–284 (2008)
[9] Klinov, P., Parsia, B.: Probabilistic modeling and OWL: A user oriented introduction into P- \(\mathcal{SHIQ}\) (D). In: OWLED (2008)
[10] Klinov, P., Parsia, B.: Practical reasoning in Probabilistic Description Logic. Tech.rep., University of Manchester (2011), http://www.cs.man.ac.uk/ klinovp/pubs/2011/psroiq-eval-report.pdf · Zbl 1351.68268
[11] Klinov, P., Parsia, B., Picado-Muiño, D.: The consistency of the medical expert system CADIAG-2: A probabilistic approach. Journal of Information Technology Research 4(1), 1–20 (2011) · Zbl 1306.68205 · doi:10.4018/jitr.2011010101
[12] Lukasiewicz, T.: Expressive probabilistic description logics. Artificial Intelligence 172(6-7), 852–883 (2008) · Zbl 1182.68283 · doi:10.1016/j.artint.2007.10.017
[13] Nilsson, N.J.: Probabilistic logic. Artificial Intelligence 28(1), 71–87 (1986) · Zbl 0589.03007 · doi:10.1016/0004-3702(86)90031-7
[14] Reiter, R.: A theory of diagnosis from first principles. Artificial Intelligence 32, 57–95 (1987) · Zbl 0643.68122 · doi:10.1016/0004-3702(87)90062-2
[15] Sirin, E., Parsia, B., Grau, B.C., Kalyanpur, A., Katz, Y.: Pellet: A practical OWL-DL reasoner. Journal of Web Semantics 5(2), 51–53 (2007) · Zbl 05461213 · doi:10.1016/j.websem.2007.03.004
[16] de Souza Andrade, P.S., da Rocha, J.C.F., Couto, D.P., da Costa Teves, A., Cozman, F.G.: A toolset for propositional probabilistic logic. In: Encontro Nacional de Inteligencia Artificial, pp. 1371–1380 (2007)
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.