×

The Bayesian ontology language \(\mathcal {BEL}\). (English) Zbl 1409.68278

Summary: We introduce the new probabilistic description logic (DL) \(\mathcal {BEL} \), which extends the light-weight DL \(\mathcal {EL}\) with the possibility of expressing uncertainty about the validity of some knowledge. Contrary to other probabilistic DLs, \(\mathcal {BEL}\) is designed to represent classical knowledge that depends on an uncertain context; that is, some of the knowledge may hold or not depending on the current situation. The probability distribution of these contexts is expressed by a Bayesian network (BN). We study different reasoning problems in \(\mathcal {BEL}\), providing tight complexity bounds for all of them. One particularly interesting property of our framework is that reasoning can be decoupled between the logical (i.e., \(\mathcal {EL}\)), and the probabilistic (i.e., the BN) components. We later generalize all the notions presented to introduce Bayesian extensions of arbitrary ontology languages. Using the decoupling property, we are able to provide tight complexity bounds for reasoning in the Bayesian extensions of many other DLs. We provide a detailed analysis of our formalism w.r.t. the assumptions made and compare it with the existing approaches.

MSC:

68T27 Logic in artificial intelligence
68T30 Knowledge representation
68T37 Reasoning under uncertainty in the context of artificial intelligence

Software:

ELK; BEACON; CEL; HgMUS; ProbLog
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arif, F., Mencía, C., Ignatiev, A., Manthey, N., Peñaloza, R., Marques-Silva, J.: BEACON: an efficient SAT-based tool for debugging EL+ ontologies. In: Proceedings of the 19th International Conference on Theory and Applications of Satisfiability Testing (SAT 2016), Lecture Notes in Computer Science, vol. 9710, pp. 521-530. Springer, Berlin (2016) · Zbl 1475.68368
[2] Arif, M.F., Mencía, C., Marques-Silva, J.: Efficient MUS enumeration of Horn formulae with applications to axiom pinpointing. CoRR arXiv:1505.04365. http://arxiv.org/abs/1505.04365 (2015) · Zbl 1471.68173
[3] Baader, F., Peñaloza, R.: Automata-based axiom pinpointing. J. Autom. Reason. 45(2), 91-129 (2010) · Zbl 1213.68589 · doi:10.1007/s10817-010-9181-2
[4] Baader, F., Peñaloza, R.: Axiom pinpointing in general tableaux. J. Logic Comput. 20(1), 5-34 (2010) · Zbl 1191.68645 · doi:10.1093/logcom/exn058
[5] Baader, F., Brandt, S., Lutz, C.: Pushing the \[\cal EL\] EL envelope. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI-05). Morgan Kaufmann (2005) · Zbl 0818.68097
[6] Baader, F., Lutz, C., Suntisrivaraporn, \[B.: {\sf CEL}\] CEL—a polynomial-time reasoner for life science ontologies. In: Furbach, U., Shankar, N. (eds.) Proceedings of the 3rd International Joint Conference on Automated Reasoning (IJCAR 2006), Lecture Notes in Artificial Intelligence, vol. 4130, pp. 287-291. Springer, Berlin (2006)
[7] Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F. (eds.): The Description Logic Handbook: Theory, Implementation, and Applications, 2nd edn. Cambridge University Press, Cambridge (2007) · Zbl 1132.68055
[8] Baader, F., Peñaloza, R., Suntisrivaraporn, B.: Pinpointing in the description logic \[\cal EL^+\] EL+. In: Proceedings of the 30th German Conference on Artificial Intelligence (KI 2007), Lecture Notes in Artificial Intelligence, vol. 4667, pp. 52-67. Springer, Osnabrück, Germany (2007)
[9] Baader, F., Knechtel, M., Peñaloza, R.: A generic approach for large-scale ontological reasoning in the presence of access restrictions to the ontology’s axioms. In: Proceedings of the 8th International Semantic Web Conference (ISWC 2009), Lecture Notes in Computer Science, vol. 5823, pp. 49 -64. Springer, Berlin (2009)
[10] Baader, F., Knechtel, M., Peñaloza, R.: Context-dependent views to axioms and consequences of semantic web ontologies. J. Web Semant. 12-13, 22-40 (2012) · doi:10.1016/j.websem.2011.11.006
[11] Beigel, R., Reingold, N., Spielman, D.A.: PP is closed under intersection. J. Comput. Syst. Sci. 50(2), 191-202 (1995) · Zbl 0827.68040 · doi:10.1006/jcss.1995.1017
[12] Brandt, S.: Polynomial time reasoning in a description logic with existential restrictions, GCI axioms, and—What else? In: Proceedings of the 16th European Conference on Artificial Intelligence (ECAI-2004), pp. 298-302. IOS Press (2004)
[13] Ceylan, I.I.: Context-Sensitive Bayesian Description Logics. Master’s thesis, Dresden University of Technology, Germany (2013)
[14] Ceylan, I.I., Peñaloza, R.: The Bayesian description logic BEL. In: Proceedings of the 7th International Joint Conference on Automated Reasoning (IJCAR 2014), Lecture Notes in Computer Science, vol. 8562, pp. 480-494. Springer, Berlin (2014) · Zbl 1409.68277
[15] Ceylan, I.I., Peñaloza, R.: Bayesian description logics. In: Proceedings of the 27th International Workshop on Description Logics (DL’14), vol. 1193, pp 447-458. CEUR-WS, CEUR Workshop Proceedings (2014) · Zbl 1409.68277
[16] Ceylan, I.I., Peñaloza, R.: Tight complexity bounds for reasoning in the description logic \[\cal BEL\] BEL. In: Proceedings of the 14th European Conference on Logics in Artificial Intelligence (JELIA 2014), Lecture Notes in Computer Science, vol. 8761, pp. 77-91. Springer, Berlin (2014) · Zbl 1432.68434
[17] Ceylan, I.I., Peñaloza, R.: Probabilistic query answering in the Bayesian description logic \[\cal BEL\] BEL. In: Proceedings of the 9th International Conference on Scalable Uncertainty Management (SUM 2015), Lecture Notes in Artificial Intelligence, vol. 9310, pp. 1-15. Springer, Berlin (2015)
[18] Ceylan, I.I., Mendez, J., Peñaloza, R.: The Bayesian ontology reasoner is BORN! In: Proceedings of the 4th International Workshop on OWL Reasoner Evaluation (ORE-2015), CEUR-WS, CEUR Workshop Proceedings, vol. 1387, pp. 8-14 (2015)
[19] Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing (STOC’71), pp. 151-158. ACM, New York, NY, USA (1971). doi:10.1145/800157.805047
[20] Cooper, G.F.: The computational complexity of probabilistic inference using Bayesian belief networks (research note). Artif. Intell. 42(2-3), 393-405 (1990) · Zbl 0717.68080 · doi:10.1016/0004-3702(90)90060-D
[21] da Costa, P.C.G., Laskey, K.B., Laskey, K.J.: PR-OWL: A Bayesian ontology language for the semantic web. In: Uncertainty Reasoning for the Semantic Web I, URSW 2005-2007, Lecture Notes in Computer Science, vol. 5327, pp. 88-107. Springer, Berlin (2008)
[22] d’Amato, C., Fanizzi, N., Lukasiewicz, T.: Tractable reasoning with Bayesian description logics. In: Proceedings of the Second International Conference on Scalable Uncertainty Management (SUM 2008), Lecture Notes in Computer Science, vol. 5291, pp. 146-159. Springer, Berlin (2008) · Zbl 0717.68080
[23] Darwiche, A.: Modeling and Reasoning with Bayesian Networks. Cambridge University Press, Cambridge (2009) · Zbl 1231.68003 · doi:10.1017/CBO9780511811357
[24] De Raedt, L., Kimmig, A., Toivonen, H.: ProbLog: A probabilistic prolog and its application in link discovery. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-07). AAAI Press, pp. 2462-2467 (2007) · Zbl 1331.68216
[25] Downey, R.G., Fellows, M.: Parameterized Complexity. Monographs in Computer Science. Springer, Berlin (1999) · doi:10.1007/978-1-4612-0515-9
[26] Friedman, N., Linial, M., Nachman, I., Pe’er, D.: Using Bayesian networks to analyze expression data. J. Comput. Biol. 7, 601-620 (2000) · doi:10.1089/106652700750050961
[27] Gill, J.T.: Computatonal complexity of probabilistic turing machines. SIAM J. Comput. 6(4), 675-695 (1977) · Zbl 0366.02024 · doi:10.1137/0206049
[28] Kazakov, Y., Krötzsch, M., Simančík, F.: The incredible ELK: from polynomial procedures to efficient reasoning with \[{\cal EL}\] EL ontologies. J. Autom. Reason. 53, 1-61 (2014) · Zbl 1331.68216 · doi:10.1007/s10817-013-9296-3
[29] Koller, D., Levy, A.Y., Pfeffer, A.: P-classic: a tractable probablistic description logic. In: Proceedings 14th National Conference on Artificial Intelligence (AAAI-97). AAAI Press, pp. 390-397 (1997)
[30] Littman, M.L., Majercik, S.M., Pitassi, T.: Stochastic Boolean satisfiability. J. Autom. Reason. 27(3), 251-296 (2001) · Zbl 0988.68189 · doi:10.1023/A:1017584715408
[31] Lukasiewicz, T., Straccia, U.: Managing uncertainty and vagueness in description logics for the semantic web. J. Web Semant. 6(4), 291-308 (2008). doi:10.1016/j.websem.2008.04.001 · doi:10.1016/j.websem.2008.04.001
[32] Manthey, N., Peñaloza, R.: Exploiting SAT technology for axiom pinpointing. Tech. Rep. 15-05, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universität Dresden (2015)
[33] Mendez, J.: jcel: A modular rule-based reasoner. In: Proceedings of the 1st International Workshop on OWL Reasoner Evaluation (ORE-2012), CEUR-WS, CEUR Workshop Proceedings, vol. 858 (2012)
[34] Niepert, M., Noessner, J., Stuckenschmidt, H.: Log-linear description logics. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-11), IJCAI/AAAI, pp. 2153-2158. http://ijcai.org/papers11/Papers/IJCAI11-359.pdf (2011)
[35] Park, J.D., Darwiche, A.: Complexity results and approximation strategies for MAP explanations. J. Artif. Intell. Res. 21, 101-133 (2004) · Zbl 1080.68689
[36] Peñaloza, R., Sertkaya, B.: On the complexity of axiom pinpointing in the EL family of description logics. In: Lin, F., Sattler, U., Truszczynski, M. (eds.) Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning (KR 2010). AAAI Press (2010) · Zbl 1211.68410
[37] Pearl, J.: Probabalistic Reasoning in Intelligent Systems. Morgan Kaufmann, Los Altos (1988)
[38] Riguzzi, F., Bellodi, E., Lamma, E., Zese, R.: Epistemic and statistical probabilistic ontologies. In: Proceedings of the 8th International Workshop on Uncertainty Reasoning for the Semantic Web (URSW-12), CEUR-WS, vol. 900, pp. 3-14 (2012) · Zbl 1347.68320
[39] Riguzzi, F., Bellodi, E., Lamma, E., Zese, R.: Probabilistic description logics under the distribution semantics. Semant. Web J. 6(5), 477-501 (2015). doi:10.3233/SW-140154 · Zbl 1400.68226 · doi:10.3233/SW-140154
[40] Scutari, M., Howell, P., Balding, D.J., Mackay, I.: Multiple quantitative trait analysis using bayesian networks. Genetics 198, 129-137 (2014) · doi:10.1534/genetics.114.165704
[41] Sebastiani, R., Vescovi, M.: Axiom pinpointing in lightweight description logics via Horn-SAT encoding and conflict analysis. In: Proceedings of the 22nd International Conference on Automated Deduction, Lecture Notes in Computer Science, vol. 5663, pp. 84-99. Springer, Berlin (2009) · Zbl 1250.68246
[42] Sebastiani, R., Vescovi, M.: Axiom Pinpointing in Large \[\cal EL+\] EL+ Ontologies via SAT and SMT Techniques. Tech. Rep. DISI-15-010, University of Trento, Italy (2015). http://disi.unitn.it/
[43] Shimony, S.E.: Finding maps for belief networks is NP-hard. Artif. Intell. 68(2), 399-410 (1994) · Zbl 0818.68097 · doi:10.1016/0004-3702(94)90072-8
[44] The Gene Ontology Consortium: Gene ontology: tool for the unification of biology. Nat. Genet. 25(1), 25-29 (2000). doi:10.1038/75556
[45] Toda, S.: On the computational power of PP and +P. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science. IEEE, pp. 514-519 (1989)
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.