nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Counting and Conjunctive Queries in the Lifted Junction Tree Algorithm

verfasst von : Tanya Braun, Ralf Möller

Erschienen in: Graph Structures for Knowledge Representation and Reasoning

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Standard approaches for inference in probabilistic formalisms with first-order constructs include lifted variable elimination (LVE) for single queries. To handle multiple queries efficiently, the lifted junction tree algorithm (LJT) uses a first-order cluster representation of a knowledge base and LVE in its computations. We extend LJT with a full formal specification of its algorithm steps incorporating (i) the lifting tool of counting and (ii) answering of conjunctive queries. Given multiple queries, e.g., in machine learning applications, our approach enables us to compute answers faster than the current LJT and existing approaches tailored for single queries.

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Subjective Bayesian Networks and Human-in-the-Loop Situational Understanding

Nächstes Kapitel Representing and Reasoning About Logical Network Topologies

Ahmadi, B., Kersting, K., Mladenov, M., Natarajan, S.: Exploiting symmetries for scaling loopy belief propagation and relational training. Mach. Learn. 92(1), 91–132 (2013)MathSciNetCrossRefMATH

Bellodi, E., Lamma, E., Riguzzi, F., Costa, V.S., Zese, R.: Lifted variable elimination for probabilistic logic programming. Theory Pract. Log. Program. 14(4–5), 681–695 (2014)CrossRefMATH

Braun, T., Möller, R.: Lifted junction tree algorithm. In: Friedrich, G., Helmert, M., Wotawa, F. (eds.) KI 2016. LNCS (LNAI), vol. 9904, pp. 30–42. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-46073-4_3 CrossRef

Braun, T., Möller, R.: Preventing groundings and handling evidence in the lifted junction tree algorithm. In: Kern-Isberner, G., Fürnkranz, J., Thimm, M. (eds.) KI 2017. LNCS (LNAI), vol. 10505, pp. 85–98. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-67190-1_7 CrossRef

van den Broeck, G.: Lifted inference and learning in statistical relational models. Ph.D. thesis, KU Leuven (2013)

van den Broeck, G., Niepert, M.: Lifted probabilistic inference for asymmetric graphical models. In: AAAI 2015 Proceedings of the 29th Conference on Artificial Intelligence, pp. 3599–3605 (2015)

Chavira, M., Darwiche, A.: Compiling Bayesian networks using variable elimination. In: IJCAI 2007 Proceedings of the 20th International Joint Conference on Artificial Intelligence, pp. 2443–2449 (2007)

Choi, J., Amir, E., Hill, D.J.: Lifted inference for relational continuous models. In: UAI 2010 Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, pp. 13–18 (2010)

Darwiche, A.: Recursive conditioning. Artif. Intell. 2(1–2), 4–51 (2001)MathSciNetMATH

10.

Darwiche, A.: Modeling and Reasoning with Bayesian Networks. Cambridge University Press, Cambridge (2009)CrossRefMATH

11.

Das, M., Wu, Y., Khot, T., Kersting, K., Natarajan, S.: Scaling lifted probabilistic inference and learning via graph databases. In: Proceedings of the SIAM International Conference on Data Mining, pp. 738–746 (2016)

12.

Gogate, V., Domingos, P.: Exploiting logical structure in lifted probabilistic inference. In: Working Note of the Workshop on Statistical Relational Artificial Intelligence at the 24th Conference on Artificial Intelligence, pp. 19–25 (2010)

13.

Gogate, V., Domingos, P.: Probabilistic theorem proving. In: UAI 2011 Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, pp. 256–265 (2011)

14.

Jensen, F.V., Lauritzen, S.L., Olesen, K.G.: Bayesian updating in recursive graphical models by local computations. Comput. Stat. Q. 4, 269–282 (1990)MATH

15.

Kersting, K., Ahmadi, B., Natarajan, S.: Counting belief propagation. In: UAI 2009 Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, pp. 277–284 (2009)

16.

Koller, D., Friedman, N.: Probabilistic Graphical Models: Principles and Techniques. The MIT Press, Cambridge (2009)MATH

17.

Lauritzen, S.L., Spiegelhalter, D.J.: Local computations with probabilities on graphical structures and their application to expert systems. J. Royal Stat. Soc. Ser. B Methodol. 50, 157–224 (1988)MathSciNetMATH

18.

Milch, B., Zettelmeyer, L.S., Kersting, K., Haimes, M., Kaelbling, L.P.: Lifted probabilistic inference with counting formulas. In: AAAI 2008 Proceedings of the 23rd Conference on Artificial Intelligence, pp. 1062–1068 (2008)

19.

Poole, D., Zhang, N.L.: Exploiting contextual independence in probabilistic inference. J. Artif. Intell. 18, 263–313 (2003)MathSciNetMATH

20.

de Salvo Braz, R., Amir, E., Roth, D.: Lifted first-order probabilistic inference. In: IJCAI 2005 Proceedings of the 19th International Joint Conference on Artificial Intelligence (2005)

21.

Shafer, G.R., Shenoy, P.P.: Probability propagation. Ann. Math. Artif. Intell. 2(1), 327–351 (1990)MathSciNetCrossRefMATH

22.

Shenoy, P.P., Shafer, G.R.: Axioms for probability and belief-function propagation. Uncertain. Artif. Intell. 4(9), 169–198 (1990)MathSciNetCrossRef

23.

Singla, P., Domingos, P.: Lifted first-order belief propagation. In: AAAI 2008 Proceedings of the 23rd Conference on Artificial Intelligence, pp. 1094–1099 (2008)

24.

Taghipour, N.: Lifted probabilistic inference by variable elimination. Ph.D. thesis, KU Leuven (2013)

25.

Taghipour, N., Davis, J., Blockeel, H.: First-order decomposition trees. In: Advances in Neural Information Processing Systems 26, pp. 1052–1060. Curran Associates, Inc. (2013)

26.

Taghipour, N., Fierens, D., Davis, J., Blockeel, H.: Lifted variable elimination: decoupling the operators from the constraint language. J. Artif. Intell. Res. 47(1), 393–439 (2013)MathSciNetMATH

27.

Vlasselaer, J., Meert, W., van den Broeck, G., Raedt, L.D.: Exploiting local and repeated structure in dynamic Baysian networks. Artif. Intell. 232, 43–53 (2016)CrossRefMATH

28.

Zhang, N.L., Poole, D.: A simple approach to Bayesian network computations. In: Proceedings of the 10th Canadian Conference on Artificial Intelligence, pp. 171–178 (1994)

Titel: Counting and Conjunctive Queries in the Lifted Junction Tree Algorithm
verfasst von: Tanya Braun
Ralf Möller
Verlag: Springer International Publishing
Buch: Graph Structures for Knowledge Representation and Reasoning
Print ISBN: 978-3-319-78101-3

Electronic ISBN: 978-3-319-78102-0

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-78102-0_3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"