Expressive probabilistic description logics

ABSTRACT

The work in this paper is directed towards sophisticated formalisms for reasoning under probabilistic uncertainty in ontologies in the Semantic Web. Ontologies play a central role in the development of the Semantic Web, since they provide a precise definition of shared terms in web resources. They are expressed in the standardized web ontology language OWL, which consists of the three increasingly expressive sublanguages OWL Lite, OWL DL, and OWL Full. The sublanguages OWL Lite and OWL DL have a formal semantics and a reasoning support through a mapping to the expressive description logics SHIF(D) and SHOIN(D), respectively. In this paper, we present the expressive probabilistic description logics P-SHIF(D) and P-SHOIN(D), which are probabilistic extensions of these description logics. They allow for expressing rich terminological probabilistic knowledge about concepts and roles as well as assertional probabilistic knowledge about instances of concepts and roles. They are semantically based on the notion of probabilistic lexicographic entailment from probabilistic default reasoning, which naturally interprets this terminological and assertional probabilistic knowledge as knowledge about random and concrete instances, respectively. As an important additional feature, they also allow for expressing terminological default knowledge, which is semantically interpreted as in Lehmann's lexicographic entailment in default reasoning from conditional knowledge bases. Another important feature of this extension of SHIF(D) and SHOIN(D) by probabilistic uncertainty is that it can be applied to other classical description logics as well. We then present sound and complete algorithms for the main reasoning problems in the new probabilistic description logics, which are based on reductions to reasoning in their classical counterparts, and to solving linear optimization problems. In particular, this shows the important result that reasoning in the new probabilistic description logics is decidable/computable. Furthermore, we also analyze the computational complexity of the main reasoning problems in the new probabilistic description logics in the general as well as restricted cases.

REFERENCES

• [1]: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• [2]: Adams, E.W., The Logic of Conditionals. 1975. Synthese Library, 1975.D. Reidel, Dordrecht.
• [3]: Stéphane Amarger , Didier Dubois , Henri Prade, Constraint propagation with imprecise conditional probabilities, Proceedings of the seventh conference (1991) on Uncertainty in artificial intelligence, p.26-34, June 1994, Los Angeles, California, United States
• [4]: F. Baader, S. Brandt, C. Lutz, Pushing the EL envelope, in: Proceedings IJCAI-2005, 2005, pp. 364--369
• [5]: Franz Baader , Diego Calvanese , Deborah L. McGuinness , Daniele Nardi , Peter F. Patel-Schneider, The description logic handbook: theory, implementation, and applications, Cambridge University Press, New York, NY, 2003
• [6]: Baader, F. and Hollunder, B., Embedding defaults into terminological knowledge representation formalisms. J. Autom. Reasoning. v14 i1. 149-180.
• [7]: Baader, F. and Hollunder, B., Priorities on defaults with prerequisites and their application in treating specificity in terminological default logic. J. Autom. Reason. v15 i1. 41-68.
• [8]: Benferhat, S., Cayrol, C., Dubois, D., Lang, J. and Prade, H., Inconsistency management and prioritized syntax-based entailment. In: Proceedings IJCAI-1993, Morgan Kaufmann. pp. 640-645.
• [9]: Salem Benferhat , Didier Dubois , Henri Prade, Nonmonotonic reasoning, conditional objects and possibility theory, Artificial Intelligence, v.92 n.1-2, p.259-276, May 1997 [doi>10.1016/S0004-3702(97)00012-X]
• [10]: Benferhat, S., Dubois, D. and Prade, H., Representing default rules in possibilistic logic. In: Proceedings KR-1992, Morgan Kaufmann. pp. 673-684.
• [11]: S. Benferhat , A. Saffiotti , P. Smets, Belief functions and default reasoning, Artificial Intelligence, v.122 n.1-2, p.1-69, Sept., 2000 [doi>10.1016/S0004-3702(00)00041-2]
• [12]: Berners-Lee, T., Weaving the Web. 1999. Harper, San Francisco.
• [13]: Veronica Biazzo , Angelo Gilio , Thomas Lukasiewicz , Giuseppe Sanfilippo, Probabilistic logic under coherence: complexity and algorithms, Annals of Mathematics and Artificial Intelligence, v.45 n.1-2, p.35-81, October 2005 [doi>10.1007/s10472-005-9005-y]
• [14]: Bonatti, P.A., Lutz, C. and Wolter, F., Description logics with circumscription. In: Proceedings KR-2006, AAAI Press. pp. 400-410.
• [15]: Cali, A. and Lukasiewicz, T., Tightly integrated probabilistic description logic programs for the Semantic Web. In: LNCS, vol. 4670. Springer. pp. 428-429.
• [16]: Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M. and Rosati, R., DL-Lite: Tractable description logics for ontologies. In: Proceedings AAAI-2005, AAAI Press/MIT Press. pp. 602-607.
• [17]: Gregory F. Cooper, The computational complexity of probabilistic inference using Bayesian belief networks (research note), Artificial Intelligence, v.42 n.2-3, p.393-405, March 1990 [doi>10.1016/0004-3702(90)90060-D]
• [18]: B. Cuenca-Grau, O. Kutz, Modular ontology languages revisited, in: Proceedings of the IJCAI-07 Workshop on Semantic Web for Collaborative Knowledge Acquisition, 2007
• [19]: Paulo Cesar G. Da Costa , Kathryn Blackmond Laskey, Bayesian semantics for the semantic web, George Mason University, Fairfax, VA, 2005
• [20]: da Costa, P.C.G. and Laskey, K.B., PR-OWL: A framework for probabilistic ontologies. In: Proceedings FOIS-2006, IOS Press. pp. 237-249.
• [21]: P.C.G. da Costa, K.B. Laskey, K.J. Laskey, PR-OWL: A Bayesian ontology language for the Semantic Web, in: Proceedings URSW-2005, 2005, pp. 23--33
• [22]: Di Noia, T., Di Sciascio, E., Donini, F.M. and Mongiello, M., Abductive matchmaking using description logics. In: Proceedings IJCAI-2003, Morgan Kaufmann. pp. 337-342.
• [23]: Zhongli Ding , Yun Peng, A Probabilistic Extension to Ontology Language OWL, Proceedings of the Proceedings of the 37th Annual Hawaii International Conference on System Sciences (HICSS'04) - Track 4, p.40111.1, January 05-08, 2004
• [24]: Ding, Z., Peng, Y. and Pan, R., BayesOWL: Uncertainty modeling in Semantic Web ontologies. In: Ma, Z. (Ed.), Studies in Fuzziness and Soft Computing, vol. 204. Springer.
• [25]: Dubois, D., Mengin, J. and Prade, H., Possibilistic uncertainty and fuzzy features in description logic: A preliminary discussion. In: Sanchez, E. (Ed.), Fuzzy Logic and the Semantic Web, Elsevier. pp. 101-114.
• [26]: Dubois, D. and Prade, H., Conditional objects as non-monotonic consequence relationships. IEEE Trans. Systems Man Cybernet. v24. 1724-1740.
• [27]: Dubois, D. and Prade, H., Possibilistic logic, preferential models, non-monotonicity and related issues. In: Proceedings IJCAI-1991, Morgan Kaufmann. pp. 419-424.
• [28]: http://www.kr.tuwien.ac.at/staff/lukasiew/rr0704.pdf
• [29]: Thomas Eiter , Thomas Lukasiewicz, Default reasoning from conditional knowledge bases: complexity and tractable cases, Artificial Intelligence, v.124 n.2, p.169-241, Dec. 2000 [doi>10.1016/S0004-3702(00)00073-4]
• [30]: Eiter, T., Lukasiewicz, T., Schindlauer, R. and Tompits, H., Combining answer set programming with description logics for the Semantic Web. In: Proceedings KR-2004, AAAI Press. pp. 141-151.
• [31]: Eiter, T., Lukasiewicz, T., Schindlauer, R. and Tompits, H., Well-founded semantics for description logic programs in the Semantic Web. In: LNCS, vol. 3323. Springer. pp. 81-97.
• [32]: Jérôme Euzenat , Pavel Shvaiko, Ontology Matching, Springer-Verlag New York, Inc., Secaucus, NJ, 2007
• [33]: R. Fagin , Joseph Y. Halpern , Nimrod Megiddo, A logic for reasoning about probabilities, Information and Computation, v.87 n.1-2, p.78-128, July/August 1990 [doi>10.1016/0890-5401(90)90060-U]
• [34]: Dieter Fensel , James A. Hendler , Henry Lieberman , Wolfgang Wahlster, Spinning the Semantic Web: Bringing the World Wide Web to Its Full Potential, The MIT Press, 2005
• [35]: Alan M. Frisch , Peter Haddawy, Anytime deduction for probabilistic logic, Artificial Intelligence, v.69 n.1-2, p.93-122, Sept. 1994 [doi>10.1016/0004-3702(94)90079-5]
• [36]: Y. Fukushige, Representing probabilistic knowledge in the Semantic Web, in: Proceedings of the W3C Workshop on Semantic Web for Life Sciences, Cambridge, MA, USA, 2004
• [37]: In: Gabbay, D.M., Smets, P. (Eds.), Handbook on Defeasible Reasoning and Uncertainty Management Systems, Kluwer Academic, Dordrecht.
• [38]: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• [39]: Hector Geffner, Default Reasoning: Causal and Conditional Theories, MIT Press, Cambridge, MA, 1992
• [40]: Hector Geffner , Judea Pearl, Conditional entailment: bridging two approaches to default reasoning, Artificial Intelligence, v.53 n.2-3, p.209-244, Feb. 1992 [doi>10.1016/0004-3702(92)90071-5]
• [41]: George Georgakopoulos , Dimitris Kavvadias , Christos H. Papadimitriou, Probabilistic Satisfiability, Journal of Complexity, v.4 n.1, p.1-11, March 1988 [doi>10.1016/0885-064X(88)90006-4]
• [42]: Rosalba Giugno , Thomas Lukasiewicz, P-SHOQ(D): A Probabilistic Extension of SHOQ(D) for Probabilistic Ontologies in the Semantic Web, Proceedings of the European Conference on Logics in Artificial Intelligence, p.86-97, September 23-26, 2002
• [43]: M. Goldzsmidt , P. Morris , J. Pearl, A Maximum Entropy Approach to Nonmonotonic Reasoning, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.3, p.220-232, March 1993 [doi>10.1109/34.204904]
• [44]: Moisés Goldszmidt , Judea Pearl, On the consistency of defeasible databases, Artificial Intelligence, v.52 n.2, p.121-149, Dec. 1991 [doi>10.1016/0004-3702(91)90039-M]
• [45]: Moisés Goldszmidt , Judea Pearl, Qualitative probabilities for default reasoning, belief revision, and causal modeling, Artificial Intelligence, v.84 n.1-2, p.57-112, July 1996 [doi>10.1016/0004-3702(95)00090-9]
• [46]: Goldszmidt, M. and Pearl, J., Rank-based systems: A simple approach to belief revision, belief update and reasoning about evidence and actions. In: Proceedings KR-1992, Morgan Kaufmann. pp. 661-672.
• [47]: Volker Haarslev , Ralf Möller, RACER System Description, Proceedings of the First International Joint Conference on Automated Reasoning, p.701-706, June 18-23, 2001
• [48]: Hailperin, T., Boole's Logic and Probability. 1986. second ed. North-Holland.
• [49]: Alon Halevy , Michael Franklin , David Maier, Principles of dataspace systems, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-9, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142352]
• [50]: Hansen, P., Jaumard, B., Nguetsé, G.-B.D. and de Aragão, M.P., Models and algorithms for probabilistic and Bayesian logic. In: Proceedings IJCAI-1995, Morgan Kaufmann. pp. 1862-1868.
• [51]: Heinsohn, J., Probabilistic description logics. In: Proceedings UAI-1994, Morgan Kaufmann. pp. 311-318.
• [52]: Markus Holi , Eeru Hyvönen, A method for modeling uncertainty in semantic web taxonomies, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013443]
• [53]: M. Holi, E. Hyvönen, Modeling degrees of conceptual overlap in Semantic Web ontologies, in: Proceedings URSW-2005, 2005, pp. 98--99
• [54]: Horrocks, I., Using an expressive description logic: FaCT or fiction?. In: Proceedings KR-1998, Morgan Kaufmann. pp. 636-649.
• [55]: Horrocks, I. and Patel-Schneider, P.F., Reducing OWL entailment to description logic satisfiability. In: LNCS, vol. 2870. Springer. pp. 17-29.
• [56]: Horrocks, I., Patel-Schneider, P.F. and van Harmelen, F., From SHIQ and RDF to OWL: The making of a web ontology language. J. Web Sem. v1 i1. 7-26.
• [57]: Ian Horrocks , Ulrike Sattler, A Tableau Decision Procedure for $\mathcal{SHOIQ}$, Journal of Automated Reasoning, v.39 n.3, p.249-276, October 2007 [doi>10.1007/s10817-007-9079-9]
• [58]: Ian Horrocks , Ulrike Sattler , Stephan Tobies, Practical Reasoning for Expressive Description Logics, Proceedings of the 6th International Conference on Logic Programming and Automated Reasoning, p.161-180, September 06-10, 1999
• [59]: Edward Hung , Yu Deng , V. S. Subrahmanian, TOSS: an extension of TAX with ontologies and similarity queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007649]
• [60]: Jaeger, M., Probabilistic reasoning in terminological logics. In: Proceedings KR-1994, Morgan Kaufmann. pp. 305-316.
• [61]: Jaeger, M., Probabilistic role models and the guarded fragment. Int. J. Uncertain. Fuzz. v14 i1. 43-60.
• [62]: Jaumard, B., Hansen, P. and de Aragão, M.P., Column generation methods for probabilistic logic. ORSA J. Comput. v3. 135-147.
• [63]: Birgit Jenner , Jacobo Torán, Computing functions with parallel queries to NP, Theoretical Computer Science, v.141 n.1-2, p.175-193, April 17, 1995 [doi>10.1016/0304-3975(94)00080-3]
• [64]: David S. Johnson, A catalog of complexity classes, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• [65]: Koller, D., Levy, A. and Pfeffer, A., P-Classic: A tractable probabilistic description logic. In: Proceedings AAAI-1997, AAAI Press/MIT Press. pp. 390-397.
• [66]: Sarit Kraus , Daniel Lehmann , Menachem Magidor, Nonmonotonic reasoning, preferential models and cumulative logics, Artificial Intelligence, v.44 n.1-2, p.167-207, July 1990 [doi>10.1016/0004-3702(90)90101-5]
• [67]: Lehmann, D., Another perspective on default reasoning. Ann. Math. Artif. Intell. v15 i1. 61-82.
• [68]: Daniel Lehmann , Menachem Magidor, What does a conditional knowledge base entail?, Artificial Intelligence, v.55 n.1, p.1-60, May 1992 [doi>10.1016/0004-3702(92)90041-U]
• [69]: Thomas Lukasiewicz, Fuzzy Description Logic Programs under the Answer Set Semantics for the Semantic Web, Proceedings of the Second International Conference on Rules and Rule Markup Languages for the Semantic Web, p.89-96, November 10-11, 2006 [doi>10.1109/RULEML.2006.12]
• [70]: Lukasiewicz, T., Nonmonotonic probabilistic reasoning under variable-strength inheritance with overriding. Synthese. v146 i1--2. 153-169.
• [71]: Thomas Lukasiewicz, Nonmonotonic probabilistic logics under variable-strength inheritance with overriding: Complexity, algorithms, and implementation, International Journal of Approximate Reasoning, v.44 n.3, p.301-321, March, 2007 [doi>10.1016/j.ijar.2006.07.015]
• [72]: Lukasiewicz, T., Probabilistic deduction with conditional constraints over basic events. J. Artif. Intell. Res. v10. 199-241.
• [73]: Thomas Lukasiewicz, Probabilistic Default Reasoning with Conditional Constraints, Annals of Mathematics and Artificial Intelligence, v.34 n.1-3, p.35-88, March 2002 [doi>10.1023/A:1014445017537]
• [74]: Thomas Lukasiewicz, Probabilistic description logic programs, International Journal of Approximate Reasoning, v.45 n.2, p.288-307, July, 2007 [doi>10.1016/j.ijar.2006.06.012]
• [75]: Thomas Lukasiewicz, Probabilistic Logic Programming under Inheritance with Overriding, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.329-336, August 02-05, 2001
• [76]: Thomas Lukasiewicz, Probabilistic logic programming with conditional constraints, ACM Transactions on Computational Logic (TOCL), v.2 n.3, p.289-339, July 2001 [doi>10.1145/377978.377983]
• [77]: Lukasiewicz, T., Tractable probabilistic description logic programs. In: LNCS, vol. 4772. Springer. pp. 143-156.
• [78]: Thomas Lukasiewicz, Weak nonmonotonic probabilistic logics, Artificial Intelligence, v.168 n.1, p.119-161, October 2005 [doi>10.1016/j.artint.2005.05.005]
• [79]: Lukasiewicz, T. and Schellhase, J., Variable-strength conditional preferences for matchmaking in description logics. In: Proceedings KR-2006, AAAI Press. pp. 164-174.
• [80]: Thomas Lukasiewicz , Jörg Schellhase, Variable-strength conditional preferences for ranking objects in ontologies, Web Semantics: Science, Services and Agents on the World Wide Web, v.5 n.3, p.180-194, September, 2007 [doi>10.1016/j.websem.2007.06.001]
• [81]: Thomas Mantay , Ralf Möller , Alissa Kaplunova, Computing Probabilistic Least Common Subsumers in Description Logics, Proceedings of the 23rd Annual German Conference on Artificial Intelligence: Advances in Artificial Intelligence, p.89-100, September 13-15, 1999
• [82]: Mitra, P., Noy, N.F. and Jaiswal, A., OMEN: A probabilistic ontology mapping tool. In: LNCS, vol. 3729. Springer. pp. 537-547.
• [83]: Nils J. Nilsson, Probabilistic logic, Artificial Intelligence, v.28 n.1, p.71-88, Feb. 1986 [doi>10.1016/0004-3702(86)90031-7]
• [84]: Nottelmann, H. and Fuhr, N., Adding probabilities and rules to OWL Lite subsets based on probabilistic Datalog. Int. J. Uncertain. Fuzz. v14 i1. 17-42.
• [85]: Pan, R., Ding, Z., Yu, Y. and Peng, Y., A Bayesian network approach to ontology mapping. In: LNCS, vol. 3729. Springer. pp. 563-577.
• [86]: Papadimitriou, C.H., Computational Complexity. 1994. Addison-Wesley, Reading.
• [87]: http://www.mindswap.org/2003/pellet/
• [88]: Judea Pearl, System Z: a natural ordering of defaults with tractable applications to nonmonotonic reasoning, Proceedings of the 3rd conference on Theoretical aspects of reasoning about knowledge, March 04-07, 1990, Pacific Grove, California
• [89]: M. Pool, J. Aikin, KEEPER and Protégé: An elicitation environment for Bayesian inference tools, in: Proceedings of the Workshop on Protégé and Reasoning held at the 7th International Protégé Conference, 2004
• [90]: Ian Pratt-Hartmann, Complexity of the Two-Variable Fragment with Counting Quantifiers, Journal of Logic, Language and Information, v.14 n.3, p.369-395, June 2005 [doi>10.1007/s10849-005-5791-1]
• [91]: Reiter, R., A logic for default reasoning. Artif. Intell. v13. 81-132.
• [92]: Dan Roth, On the hardness of approximate reasoning, Artificial Intelligence, v.82 n.1-2, p.273-302, April 1996 [doi>10.1016/0004-3702(94)00092-1]
• [93]: Alan L. Selman, A taxonomy of complexity classes of functions, Journal of Computer and System Sciences, v.48 n.2, p.357-381, April 1994 [doi>10.1016/S0022-0000(05)80009-1]
• [94]: Smyth, C. and Poole, D., Qualitative probabilistic matching with hierarchical descriptions. In: Proceedings KR-2004, AAAI Press. pp. 479-487.
• [95]: Spohn, W., Ordinal conditional functions: A dynamic theory of epistemic states. In: Harper, W., Skyrms, B. (Eds.), Causation in Decision, Belief Change, and Statistics, vol. 2, Reidel, Dordrecht. pp. 105-134.
• [96]: Straccia, U., A fuzzy description logic for the Semantic Web. In: Sanchez, E. (Ed.), Fuzzy Logic and the Semantic Web, Elsevier. pp. 73-90.
• [97]: U. Straccia, Fuzzy description logic programs, in: Proceedings IPMU-2006, 2006, pp. 1818--1825
• [98]: S. Tobies, Complexity results and practical algorithms for logics in knowledge representation, PhD thesis, RWTH Aachen, Germany, 2001
• [99]: Tsarkov, D. and Horrocks, I., FaCT++ description logic reasoner: System description. In: LNCS, vol. 4130. Springer. pp. 292-297.
• [100]: Udrea, O., Deng, Y., Hung, E. and Subrahmanian, V.S., Probabilistic ontologies and relational databases. In: LNCS, vol. 3760. Springer. pp. 1-17.
• [101]: Maurice van Keulen , Ander de Keijzer , Wouter Alink, A Probabilistic XML Approach to Data Integration, Proceedings of the 21st International Conference on Data Engineering, p.459-470, April 05-08, 2005 [doi>10.1109/ICDE.2005.11]
• [102].: W3C. OWL web ontology language overview, 2004. W3C Recommendation (10 February 2004). Available at http://www.w3.org/TR/2004/REC-owl-features-20040210/
• [103]: Yi Yang , Jacques Calmet, OntoBayes: An Ontology-Driven Uncertainty Model, Proceedings of the International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce Vol-1 (CIMCA-IAWTIC'06), p.457-463, November 28-30, 2005
• [104]: Yelland, P.M., An alternative combination of Bayesian networks and description logics. In: Proceedings KR-2000, Morgan Kaufmann. pp. 225-234.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

General Terms:
Theory

Keywords:
Algorithms, Complexity, Conditional knowledge bases, Probabilistic default reasoning, Probabilistic description logics, Uncertainty reasoning for the Semantic Web