Skip to main content

2014 | OriginalPaper | Buchkapitel

Semantics and Inference for Probabilistic Description Logics

verfasst von : Riccardo Zese, Elena Bellodi, Evelina Lamma, Fabrizio Riguzzi, Fabiano Aguiari

Erschienen in: Uncertainty Reasoning for the Semantic Web III

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We present a semantics for Probabilistic Description Logics that is based on the distribution semantics for Probabilistic Logic Programming. The semantics, called DISPONTE, allows to express assertional probabilistic statements. We also present two systems for computing the probability of queries to probabilistic knowledge bases: BUNDLE and TRILL. BUNDLE is based on the Pellet reasoner while TRILL exploits the declarative Prolog language. Both algorithms compute a propositional Boolean formula that represents the set of explanations to the query. BUNDLE builds a formula in Disjunctive Normal Form in which each disjunct corresponds to an explanation while TRILL computes a general Boolean pinpointing formula using the techniques proposed by Baader and Peñaloza. Both algorithms then build a Binary Decision Diagram (BDD) representing the formula and compute the probability from the BDD using a dynamic programming algorithm. We also present experiments comparing the performance of BUNDLE and TRILL.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F. (eds.): The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, Cambridge (2003) Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F. (eds.): The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, Cambridge (2003)
2.
Zurück zum Zitat Baader, F., Horrocks, I., Sattler, U.: Description logics. In: Handbook of Knowledge Representation, chap. 3, pp. 135–179. Elsevier, Amsterdam (2008) Baader, F., Horrocks, I., Sattler, U.: Description logics. In: Handbook of Knowledge Representation, chap. 3, pp. 135–179. Elsevier, Amsterdam (2008)
3.
Zurück zum Zitat Baader, F., Peñaloza, R.: Automata-based axiom pinpointing. J. Autom. Reasoning 45(2), 91–129 (2010)MATHCrossRef Baader, F., Peñaloza, R.: Automata-based axiom pinpointing. J. Autom. Reasoning 45(2), 91–129 (2010)MATHCrossRef
4.
Zurück zum Zitat Baader, F., Peñaloza, R.: Axiom pinpointing in general tableaux. J. Log. Comput. 20(1), 5–34 (2010)MATHCrossRef Baader, F., Peñaloza, R.: Axiom pinpointing in general tableaux. J. Log. Comput. 20(1), 5–34 (2010)MATHCrossRef
5.
Zurück zum Zitat Bacchus, F.: Representing and Reasoning with Probabilistic Knowledge - A Logical Approach to Probabilities. MIT Press, Cambridge (1990) Bacchus, F.: Representing and Reasoning with Probabilistic Knowledge - A Logical Approach to Probabilities. MIT Press, Cambridge (1990)
7.
Zurück zum Zitat Bellodi, E., Lamma, E., Riguzzi, F., Albani, S.: A distribution semantics for probabilistic ontologies. In: International Workshop on Uncertainty Reasoning for the Semantic Web. CEUR Workshop Proceedings, vol. 778. Sun SITE Central Europe (2011) Bellodi, E., Lamma, E., Riguzzi, F., Albani, S.: A distribution semantics for probabilistic ontologies. In: International Workshop on Uncertainty Reasoning for the Semantic Web. CEUR Workshop Proceedings, vol. 778. Sun SITE Central Europe (2011)
8.
Zurück zum Zitat Darwiche, A., Marquis, P.: A knowledge compilation map. J. Artif. Intell. Res. 17, 229–264 (2002)MATHMathSciNet Darwiche, A., Marquis, P.: A knowledge compilation map. J. Artif. Intell. Res. 17, 229–264 (2002)MATHMathSciNet
9.
Zurück zum Zitat De Raedt, L., Kimmig, A., Toivonen, H.: ProbLog: a probabilistic Prolog and its application in link discovery. In: International Joint Conference on Artificial Intelligence, pp. 2462–2467 (2007) De Raedt, L., Kimmig, A., Toivonen, H.: ProbLog: a probabilistic Prolog and its application in link discovery. In: International Joint Conference on Artificial Intelligence, pp. 2462–2467 (2007)
10.
Zurück zum Zitat Faizi, I.: A description logic prover in prolog, Bachelor’s thesis, Informatics Mathematical Modelling, Technical University of Denmark (2011) Faizi, I.: A description logic prover in prolog, Bachelor’s thesis, Informatics Mathematical Modelling, Technical University of Denmark (2011)
11.
Zurück zum Zitat Gomes, C.P., Sabharwal, A., Selman, B.: Model counting. In: Biere, A. (ed.) Handbook of Satisfiability. IOS Press, Amsterdam (2008) Gomes, C.P., Sabharwal, A., Selman, B.: Model counting. In: Biere, A. (ed.) Handbook of Satisfiability. IOS Press, Amsterdam (2008)
12.
Zurück zum Zitat Haarslev, V., Hidde, K., Möller, R., Wessel, M.: The racerpro knowledge representation and reasoning system. Semant. Web 3(3), 267–277 (2012) Haarslev, V., Hidde, K., Möller, R., Wessel, M.: The racerpro knowledge representation and reasoning system. Semant. Web 3(3), 267–277 (2012)
13.
Zurück zum Zitat Halaschek-Wiener, C., Kalyanpur, A., Parsia, B.: Extending tableau tracing for ABox updates. Technical report, University of Maryland (2006) Halaschek-Wiener, C., Kalyanpur, A., Parsia, B.: Extending tableau tracing for ABox updates. Technical report, University of Maryland (2006)
14.
Zurück zum Zitat Halpern, J.Y.: An analysis of first-order logics of probability. Artif. Intell. 46(3), 311–350 (1990)MATHCrossRef Halpern, J.Y.: An analysis of first-order logics of probability. Artif. Intell. 46(3), 311–350 (1990)MATHCrossRef
15.
Zurück zum Zitat Herchenröder, T.: Lightweight semantic web oriented reasoning in prolog: tableaux inference for description logics. Master’s thesis, School of Informatics, University of Edinburgh (2006) Herchenröder, T.: Lightweight semantic web oriented reasoning in prolog: tableaux inference for description logics. Master’s thesis, School of Informatics, University of Edinburgh (2006)
16.
Zurück zum Zitat Hitzler, P., Krötzsch, M., Rudolph, S.: Foundations of Semantic Web Technologies. CRC Press, Boca Raton (2009) Hitzler, P., Krötzsch, M., Rudolph, S.: Foundations of Semantic Web Technologies. CRC Press, Boca Raton (2009)
17.
Zurück zum Zitat Hustadt, U., Motik, B., Sattler, U.: Deciding expressive description logics in the framework of resolution. Inf. Comput. 206(5), 579–601 (2008)MATHMathSciNetCrossRef Hustadt, U., Motik, B., Sattler, U.: Deciding expressive description logics in the framework of resolution. Inf. Comput. 206(5), 579–601 (2008)MATHMathSciNetCrossRef
18.
Zurück zum Zitat Kalyanpur, A.: Debugging and repair of OWL ontologies. Ph.D. thesis, The Graduate School of the University of Maryland (2006) Kalyanpur, A.: Debugging and repair of OWL ontologies. Ph.D. thesis, The Graduate School of the University of Maryland (2006)
19.
Zurück zum Zitat Kalyanpur, A., Parsia, B., Horridge, M., Sirin, E.: Finding all justifications of OWL DL entailments. In: Aberer, K., et al. (eds.) ISWC/ASWC 2007. LNCS, vol. 4825, pp. 267–280. Springer, Heidelberg (2007)CrossRef Kalyanpur, A., Parsia, B., Horridge, M., Sirin, E.: Finding all justifications of OWL DL entailments. In: Aberer, K., et al. (eds.) ISWC/ASWC 2007. LNCS, vol. 4825, pp. 267–280. Springer, Heidelberg (2007)CrossRef
20.
Zurück zum Zitat Kalyanpur, A., Parsia, B., Sirin, E., Hendler, J.A.: Debugging unsatisfiable classes in OWL ontologies. J. Web Sem. 3(4), 268–293 (2005)CrossRef Kalyanpur, A., Parsia, B., Sirin, E., Hendler, J.A.: Debugging unsatisfiable classes in OWL ontologies. J. Web Sem. 3(4), 268–293 (2005)CrossRef
21.
Zurück zum Zitat Klinov, P.: Pronto: a non-monotonic probabilistic description logic reasoner. In: Bechhofer, S., Hauswirth, M., Hoffmann, J., Koubarakis, M. (eds.) ESWC 2008. LNCS, vol. 5021, pp. 822–826. Springer, Heidelberg (2008)CrossRef Klinov, P.: Pronto: a non-monotonic probabilistic description logic reasoner. In: Bechhofer, S., Hauswirth, M., Hoffmann, J., Koubarakis, M. (eds.) ESWC 2008. LNCS, vol. 5021, pp. 822–826. Springer, Heidelberg (2008)CrossRef
22.
Zurück zum Zitat Klinov, P., Parsia, B.: Optimization and evaluation of reasoning in probabilistic description logic: towards a systematic approach. In: Sheth, A.P., Staab, S., Dean, M., Paolucci, M., Maynard, D., Finin, T., Thirunarayan, K. (eds.) ISWC 2008. LNCS, vol. 5318, pp. 213–228. Springer, Heidelberg (2008)CrossRef Klinov, P., Parsia, B.: Optimization and evaluation of reasoning in probabilistic description logic: towards a systematic approach. In: Sheth, A.P., Staab, S., Dean, M., Paolucci, M., Maynard, D., Finin, T., Thirunarayan, K. (eds.) ISWC 2008. LNCS, vol. 5318, pp. 213–228. Springer, Heidelberg (2008)CrossRef
23.
Zurück zum Zitat Klinov, P., Parsia, B.: A hybrid method for probabilistic satisfiability. In: Bjørner, N., Sofronie-Stokkermans, V. (eds.) CADE 2011. LNCS, vol. 6803, pp. 354–368. Springer, Heidelberg (2011)CrossRef Klinov, P., Parsia, B.: A hybrid method for probabilistic satisfiability. In: Bjørner, N., Sofronie-Stokkermans, V. (eds.) CADE 2011. LNCS, vol. 6803, pp. 354–368. Springer, Heidelberg (2011)CrossRef
24.
Zurück zum Zitat Lukácsy, G., Szeredi, P.: Efficient description logic reasoning in prolog: the dlog system. TPLP 9(3), 343–414 (2009)MATH Lukácsy, G., Szeredi, P.: Efficient description logic reasoning in prolog: the dlog system. TPLP 9(3), 343–414 (2009)MATH
26.
Zurück zum Zitat Meissner, A.: An automated deduction system for description logic with alcn language. Studia z Automatyki i Informatyki 28–29, 91–110 (2004) Meissner, A.: An automated deduction system for description logic with alcn language. Studia z Automatyki i Informatyki 28–29, 91–110 (2004)
28.
Zurück zum Zitat Patel-Schneider, P.F., Horrocks, I., Bechhofer, S.: Tutorial on OWL (2003) Patel-Schneider, P.F., Horrocks, I., Bechhofer, S.: Tutorial on OWL (2003)
29.
Zurück zum Zitat Poole, D.: The Independent Choice Logic for modelling multiple agents under uncertainty. Artif. Intell. 94(1–2), 7–56 (1997)MATHMathSciNetCrossRef Poole, D.: The Independent Choice Logic for modelling multiple agents under uncertainty. Artif. Intell. 94(1–2), 7–56 (1997)MATHMathSciNetCrossRef
30.
Zurück zum Zitat Poole, D.: Probabilistic horn abduction and Bayesian networks. Artif. Intell. 64(1), 81–129 (1993)MATHCrossRef Poole, D.: Probabilistic horn abduction and Bayesian networks. Artif. Intell. 64(1), 81–129 (1993)MATHCrossRef
32.
Zurück zum Zitat Ricca, F., Gallucci, L., Schindlauer, R., Dell’Armi, T., Grasso, G., Leone, N.: Ontodlv: an asp-based system for enterprise ontologies. J. Log. Comput. 19(4), 643–670 (2009)MATHMathSciNetCrossRef Ricca, F., Gallucci, L., Schindlauer, R., Dell’Armi, T., Grasso, G., Leone, N.: Ontodlv: an asp-based system for enterprise ontologies. J. Log. Comput. 19(4), 643–670 (2009)MATHMathSciNetCrossRef
33.
34.
Zurück zum Zitat Riguzzi, F., Bellodi, E., Lamma, E.: Probabilistic Datalog+/- under the distribution semantics. In: Kazakov, Y., Lembo, D., Wolter, F. (eds.) International Workshop on Description Logics (2012) Riguzzi, F., Bellodi, E., Lamma, E.: Probabilistic Datalog+/- under the distribution semantics. In: Kazakov, Y., Lembo, D., Wolter, F. (eds.) International Workshop on Description Logics (2012)
35.
Zurück zum Zitat Riguzzi, F., Bellodi, E., Lamma, E., Zese, R.: Computing instantiated explanations in OWL DL. In: Baldoni, M., Baroglio, C., Boella, G., Micalizio, R. (eds.) AI*IA 2013. LNCS, vol. 8249, pp. 397–408. Springer, Heidelberg (2013)CrossRef Riguzzi, F., Bellodi, E., Lamma, E., Zese, R.: Computing instantiated explanations in OWL DL. In: Baldoni, M., Baroglio, C., Boella, G., Micalizio, R. (eds.) AI*IA 2013. LNCS, vol. 8249, pp. 397–408. Springer, Heidelberg (2013)CrossRef
36.
Zurück zum Zitat Riguzzi, F., Bellodi, E., Lamma, E., Zese, R.: Probabilistic description logics under the distribution semantics. Semant. Web J. (to appear, 2014) Riguzzi, F., Bellodi, E., Lamma, E., Zese, R.: Probabilistic description logics under the distribution semantics. Semant. Web J. (to appear, 2014)
37.
Zurück zum Zitat Riguzzi, F., Lamma, E., Bellodi, E., Zese, R.: Epistemic and statistical probabilistic ontologies. In: Uncertainty Reasoning for the Semantic Web. CEUR Workshop Proceedings, vol. 900, pp. 3–14. Sun SITE Central Europe (2012) Riguzzi, F., Lamma, E., Bellodi, E., Zese, R.: Epistemic and statistical probabilistic ontologies. In: Uncertainty Reasoning for the Semantic Web. CEUR Workshop Proceedings, vol. 900, pp. 3–14. Sun SITE Central Europe (2012)
38.
Zurück zum Zitat Sang, T., Beame, P., Kautz, H.A.: Performing bayesian inference by weighted model counting. In: Proceedings of AAAI, pp. 475–482. AAAI Press/The MIT Press, Palo Alto, Pittsburgh, 9–13 July 2005 Sang, T., Beame, P., Kautz, H.A.: Performing bayesian inference by weighted model counting. In: Proceedings of AAAI, pp. 475–482. AAAI Press/The MIT Press, Palo Alto, Pittsburgh, 9–13 July 2005
39.
Zurück zum Zitat Sato, T.: A statistical learning method for logic programs with distribution semantics. In: International Conference on Logic Programming, pp. 715–729. MIT Press (1995) Sato, T.: A statistical learning method for logic programs with distribution semantics. In: International Conference on Logic Programming, pp. 715–729. MIT Press (1995)
40.
Zurück zum Zitat Sato, T., Kameya, Y.: Parameter learning of logic programs for symbolic-statistical modeling. J. Artif. Intell. Res. 15, 391–454 (2001)MATHMathSciNet Sato, T., Kameya, Y.: Parameter learning of logic programs for symbolic-statistical modeling. J. Artif. Intell. Res. 15, 391–454 (2001)MATHMathSciNet
41.
Zurück zum Zitat Schlobach, S., Cornet, R.: Non-standard reasoning services for the debugging of description logic terminologies. In: International Joint Conference on Artificial Intelligence, pp. 355–362. Morgan Kaufmann (2003) Schlobach, S., Cornet, R.: Non-standard reasoning services for the debugging of description logic terminologies. In: International Joint Conference on Artificial Intelligence, pp. 355–362. Morgan Kaufmann (2003)
42.
Zurück zum Zitat Schmidt-Schauß, M., Smolka, G.: Attributive concept descriptions with complements. Artif. Intell. 48(1), 1–26 (1991)MATHCrossRef Schmidt-Schauß, M., Smolka, G.: Attributive concept descriptions with complements. Artif. Intell. 48(1), 1–26 (1991)MATHCrossRef
43.
Zurück zum Zitat Shearer, R., Motik, B., Horrocks, I.: Hermit: A highly-efficient owl reasoner. In: OWLED (2008) Shearer, R., Motik, B., Horrocks, I.: Hermit: A highly-efficient owl reasoner. In: OWLED (2008)
44.
Zurück zum Zitat Sirin, E., Parsia, B., Cuenca-Grau, B., Kalyanpur, A., Katz, Y.: Pellet: a practical OWL-DL reasoner. J. Web Sem. 5(2), 51–53 (2007)CrossRef Sirin, E., Parsia, B., Cuenca-Grau, B., Kalyanpur, A., Katz, Y.: Pellet: a practical OWL-DL reasoner. J. Web Sem. 5(2), 51–53 (2007)CrossRef
45.
Zurück zum Zitat Vassiliadis, V., Wielemaker, J., Mungall, C.: Processing owl2 ontologies using thea: an application of logic programming. In: International Workshop on OWL: Experiences and Directions. CEUR Workshop Proceedings, vol. 529. CEUR-WS.org (2009) Vassiliadis, V., Wielemaker, J., Mungall, C.: Processing owl2 ontologies using thea: an application of logic programming. In: International Workshop on OWL: Experiences and Directions. CEUR Workshop Proceedings, vol. 529. CEUR-WS.org (2009)
46.
Zurück zum Zitat Vennekens, J., Denecker, M., Bruynooghe, M.: CP-logic: a language of causal probabilistic events and its relation to logic programming. Theory Pract. Log. Program. 9(3), 245–308 (2009)MATHMathSciNetCrossRef Vennekens, J., Denecker, M., Bruynooghe, M.: CP-logic: a language of causal probabilistic events and its relation to logic programming. Theory Pract. Log. Program. 9(3), 245–308 (2009)MATHMathSciNetCrossRef
47.
Zurück zum Zitat Vennekens, J., Verbaeten, S., Bruynooghe, M.: Logic programs with annotated disjunctions. In: Demoen, B., Lifschitz, V. (eds.) ICLP 2004. LNCS, vol. 3132, pp. 431–445. Springer, Heidelberg (2004)CrossRef Vennekens, J., Verbaeten, S., Bruynooghe, M.: Logic programs with annotated disjunctions. In: Demoen, B., Lifschitz, V. (eds.) ICLP 2004. LNCS, vol. 3132, pp. 431–445. Springer, Heidelberg (2004)CrossRef
Metadaten
Titel
Semantics and Inference for Probabilistic Description Logics
verfasst von
Riccardo Zese
Elena Bellodi
Evelina Lamma
Fabrizio Riguzzi
Fabiano Aguiari
Copyright-Jahr
2014
DOI
https://doi.org/10.1007/978-3-319-13413-0_5