nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Analysis of Bayesian Networks via Prob-Solvable Loops

verfasst von : Ezio Bartocci, Laura Kovács, Miroslav Stankovič

Erschienen in: Theoretical Aspects of Computing – ICTAC 2020

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

Prob-solvable loops are probabilistic programs with polynomial assignments over random variables and parametrised distributions, for which the full automation of moment-based invariant generation is decidable. In this paper we extend Prob-solvable loops with new features essential for encoding Bayesian networks (BNs). We show that various BNs, such as discrete, Gaussian, conditional linear Gaussian and dynamic BNs, can be naturally encoded as Prob-solvable loops. Thanks to these encodings, we can automatically solve several BN related problems, including exact inference, sensitivity analysis, filtering and computing the expected number of rejecting samples in sampling-based procedures. We evaluate our work on a number of BN benchmarks, using automated invariant generation within Prob-solvable loop analysis.

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 Compositionality of Safe Communication in Systems of Team Automata

Nächstes Kapitel Semantics of a Relational -Calculus

A known distribution is a distribution with known and computable moments.

subject to the restriction on structure of dynBN as discussed in Sect. 4.1.

https://github.com/probing-lab/mora.

Ai, J., et al: HackPPL: a universal probabilistic programming language. In: Proceeding of MAPL@PLDI, pp. 20–28 (2019)

Baier, C., Katoen, J.P.: Principles of Model Checking. The MIT Press, Cambridge (2008)MATH

Barthe, G., Espitau, T., Ferrer Fioriti, L.M., Hsu, J.: Synthesizing probabilistic invariants via doob’s decomposition. In: Chaudhuri, S., Farzan, A. (eds.) CAV 2016. LNCS, vol. 9779, pp. 43–61. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-41528-4_3CrossRef

Bartocci, E., Kovács, L., Stankovič, M.: Automatic generation of moment-based invariants for prob-solvable loops. In: Chen, Y.-F., Cheng, C.-H., Esparza, J. (eds.) ATVA 2019. LNCS, vol. 11781, pp. 255–276. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-31784-3_15CrossRefMATH

Bartocci, E., Kovács, L., Stankovič, M.: Analysis of bayesian networks via prob-solvable loops. arXiv preprint arXiv:2007.09450 (2020)

Bartocci, E., Kovács, L., Stankovič, M.: Mora - automatic generation of moment-based invariants. TACAS 2020. LNCS, vol. 12078, pp. 492–498. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45190-5_28CrossRef

Batz, K., Kaminski, B.L., Katoen, J.-P., Matheja, C.: How long, O Bayesian network, will I sample thee? In: Ahmed, A. (ed.) ESOP 2018. LNCS, vol. 10801, pp. 186–213. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-89884-1_7CrossRef

Bingham, E., et al.: Pyro: deep universal probabilistic programming. J. Mach. Learn. Res. 20, 1–6 (2019)MATH

Brázdil, T., Kiefer, S., Kucera, A., Vareková, I.H.: Runtime analysis of probabilistic programs with unbounded recursion. J. Comput. Syst. Sci. 81(1), 288–310 (2015)MathSciNetCrossRef

10.

Celiku, O., McIver, A.: Compositional specification and analysis of cost-based properties in probabilistic programs. In: Fitzgerald, J., Hayes, I.J., Tarlecki, A. (eds.) FM 2005. LNCS, vol. 3582, pp. 107–122. Springer, Heidelberg (2005). https://doi.org/10.1007/11526841_9CrossRef

11.

Chen, Y.-F., Hong, C.-D., Wang, B.-Y., Zhang, L.: Counterexample-guided polynomial loop invariant generation by lagrange interpolation. In: Kroening, D., Păsăreanu, C.S. (eds.) CAV 2015. LNCS, vol. 9206, pp. 658–674. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21690-4_44CrossRef

12.

Constantinou, A.C., Fenton, N.E., Neil, M.: pi-Football: a Bayesian network model for forecasting association football match outcomes. Knowl. Based Syst. 36, 322–339 (2012)CrossRef

13.

Cooper, G.F.: The computational complexity of probabilistic inference using bayesian belief networks. Artif. Intell. 42(2–3), 393–405 (1990)MathSciNetCrossRef

14.

Dagum, P., Luby, M.: Approximating probabilistic inference in bayesian belief networks is NP-hard. Artif. Intell. 60(1), 141–153 (1993)MathSciNetCrossRef

15.

Dehnert, C., Junges, S., Katoen, J.-P., Volk, M.: A storm is coming: a modern probabilistic model checker. In: Majumdar, R., Kunčak, V. (eds.) CAV 2017. LNCS, vol. 10427, pp. 592–600. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63390-9_31CrossRef

16.

Dijkstra, E.W.: Guarded commands, nondeterminacy and formal derivation of programs. Commun. ACM 18(8), 453–457 (1975)MathSciNetCrossRef

17.

Edwards, D.: Introduction to Graphical Modelling. Springer Science & Business Media, New York (2012)MATH

18.

Feng, Y., Zhang, L., Jansen, D.N., Zhan, N., Xia, B.: Finding polynomial loop invariants for probabilistic programs. In: D’Souza, D., Narayan Kumar, K. (eds.) ATVA 2017. LNCS, vol. 10482, pp. 400–416. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68167-2_26CrossRef

19.

Fioriti, L.M.F., Hermanns, H.: Probabilistic termination: soundness, completeness, and compositionality. In: Proceedings of POPL, pp. 489–501 (2015)

20.

Friedman, N., Linial, M., Nachman, I., Pe’er, D.: Using Bayesian networks to analyze expression data. J. Comput. Biol. 7(3–4), 601–620 (2000)CrossRef

21.

Ghahramani, Z.: Probabilistic machine learning and artificial intelligence. Nature 521, 452–459 (2015)CrossRef

22.

Heckerman, D.: A tutorial on learning wihtbayesian networks. In: Innovations in Bayesian Networks: Theory and Applications, Studies in Computational Intelligence, vol. 156, pp.33–82. Springer (2008). https://doi.org/10.1007/978-3-540-85066-3_3

23.

Hehner, E.: A probability perspective. Formal Aspects Comput. 23(4), 391–419 (2011). 10.1007/s00165-010-0157-0MathSciNetCrossRef

24.

Jiang, X., Cooper, G.: A Bayesian spatio-temporal method for disease outbreak detection. J. Am. Med. Inform. Assoc. 17(4), 462–471 (2010)CrossRef

25.

Kaminski, B.L., Katoen, J.-P., Matheja, C., Olmedo, F.: Weakest precondition reasoning for expected run–times of probabilistic programs. In: Thiemann, P. (ed.) ESOP 2016. LNCS, vol. 9632, pp. 364–389. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49498-1_15CrossRef

26.

Katoen, J.-P., McIver, A.K., Meinicke, L.A., Morgan, C.C.: Linear-invariant generation for probabilistic programs: automated support for proof-based methods. In: Cousot, R., Martel, M. (eds.) SAS 2010. LNCS, vol. 6337, pp. 390–406. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15769-1_24CrossRef

27.

Katoen, J., Zapreev, I.S., Hahn, E.M., Hermanns, H., Jansen, D.N.: The ins and outs of the probabilistic model checker MRMC. Perform. Eval. 68(2), 90–104 (2011)CrossRef

28.

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

29.

Korb, K., Nicholson, A.: Bayesian Artificial Intelligence, 2nd edn. Chapman and Hall, Boca Raton (2010)CrossRef

30.

Kozen, D.: Semantics of probabilistic programs. J. Comput. Syst. Sci. 22(3), 328–350 (1981)MathSciNetCrossRef

31.

Kozen, D.: A probabilistic PDL. J. Comput. Syst. Sci. 30(2), 162–178 (1985)MathSciNetCrossRef

32.

Kura, S., Urabe, N., Hasuo, I.: Tail probabilities for randomized program runtimes via martingales for higher moments. In: Vojnar, T., Zhang, L. (eds.) TACAS 2019. LNCS, vol. 11428, pp. 135–153. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17465-1_8CrossRef

33.

Kwiatkowska, M., Norman, G., Parker, D.: PRISM 4.0: verification of probabilistic real-time systems. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol. 6806, pp. 585–591. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22110-1_47CrossRef

34.

Lauritzen, S.L., Spiegelhalter, D.J.: Local computation with probabilities on graphical structures and their application to expert systems (with discussion). Roy. Stat. Soc. B (Stat. Methodol.) 50(2), 157–224 (1988)MATH

35.

Lin, G.L.: Characterizations of Distributions via Moments. Indian Statistical Institute, Kolkata (1992)MATH

36.

Mardia, K.V., Kent, J.T., Bibby, J.M.: Multivariate Analysis. Academic Press, Cambridge (1979)

37.

McIver, A., Morgan, C.: Abstraction Refinement and Proof for Probabilistic Systems. Monographs in Computer Science. Springer, New York (2005)MATH

38.

Monniaux, D.: An abstract analysis of the probabilistic termination of programs. In: Cousot, P. (ed.) SAS 2001. LNCS, vol. 2126, pp. 111–126. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-47764-0_7CrossRefMATH

39.

Neapolitan, R., Jiang, X.: Probabilistic Methods for Financial and Marketing Informatics. Morgan Kaufmann, San Francisco (2010)MATH

40.

Pearl, J.: Bayesian Networks: A model of self-activated memory for evidential reasoning. In: Proceedings of Cognitive Science Society, pp. 329–334 (1985)

41.

Russell, S.J., Norvig, P.: Artificial Intelligence - A Modern Approach. Pearson Education, London (2010)MATH

42.

Tran, D., Hoffman, M.D., Saurous, R.A., Brevdo, E., Murphy, K., Blei, D.M.: Deep Probabilistic Programming. CoRR abs/1701.03757 (2017)

43.

Yuan, C., Druzdzel, M.J.: Importance sampling algorithms for bayesian networks: principles and performance. Math. Comput. Model. 43(9), 1189–1207 (2006)MathSciNetCrossRef

44.

Zweig, G., Russell, S.J.: Speech recognition with dynamic bayesian networks. In: Proceedings of AAAI, pp. 173–180 (1998)

Titel: Analysis of Bayesian Networks via Prob-Solvable Loops
verfasst von: Ezio Bartocci
Laura Kovács
Miroslav Stankovič
Verlag: Springer International Publishing
Buch: Theoretical Aspects of Computing – ICTAC 2020
Print ISBN: 978-3-030-64275-4

Electronic ISBN: 978-3-030-64276-1

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-64276-1_12

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"

Premium Partner