A Review of Bayesian Networks and Structure Learning

• Autorzy: Koski T. J. T. , Noble J. M.

Warianty tytułu

PL

Sieci bayesowskie i ropoznawanie zaleznosci strukturalnych

• Języki publikacji: EN

Abstrakty

EN

This article reviews the topic of Bayesian networks. A Bayesian network is a factorisation of a probability distribution along a directed acyclic graph. The relation between graphical d-separation and independence is described. A short article from 1853 by Arthur Cayley [8] is discussed, which contains several ideas later used in Bayesian networks: factorisation, the noisy ‘or’ gate, applications of algebraic geometry to Bayesian networks. The ideas behind Pearl’s intervention calculus when the DAG represents a causal dependence structure and the relation between the work of Cayley and Pearl is commented on. Most of the discussion is about structure learning, outlining the two main approaches, search and score versus constraint based. Constraint based algorithms often rely on the assumption of faithfulness, that the data to which the algorithm is applied is generated from distributions satisfying a faithfulness assumption where graphical dseparation and independence are equivalent. The article presents some considerations for constraint based algorithms based on recent data analysis, indicating a variety of situations where the faithfulness assumption does not hold. There is a short discussion about the causal discovery controversy, the idea that causal relations may be learned from data.

PL

Artykuł jest przeglądem problemów analizowanych przy pomocy sieci bayesowskich. Sieć bayesowska jest acyklicznym grafem skierowanym, w którym węzły oznaczają zmienne, a krawędzie prawdopodobieństwa warunkowe czyli wpływy jednych zmiennych na inne. Autor przedstawia zależność między d-separowalnościa a niezależnością. Znaczna cześć pracy poświęcona jest dyskusji idei zawartych w pracy Arthura Cayley'a [8], która zawiera szereg pojęć i pomysłów wykorzystywanych w teorii sieci bayesowskich takich jak faktoryzacja rozkładu, zaszumione bramki "LUB" oraz zastosowanie geometrii algebraicznej. Autor omawia również "calculus of intervention", pomysł pochodzący od Pearla, gdy acykliczny graf skierowany (DAG) przedstawia przyczynowo-skutkowa strukturę zależności, oraz związki pomiędzy pracami Cayley'a i Pearla. Większość zawartego w artykule materiału poświęcona jest rozpoznawaniu i wykrywaniu zależności miedzy zmiennymi w oparciu o dwie główne metodologie: przeszukiwania i klasyfikacji oraz realizacji ograniczeń. Algorytmy oparte na kontroli ograniczeń często opierają się na założeniu, że dane do których algorytm jest stosowany pochodzą z rozkładu spełniającego założenie wierności oznaczającego równoważność d-separowalności i niezależności. W pracy prezentowane są rozwiązania dla algorytmów opartych na realizacji ograniczeń w przypadkach gdy założenie wierności nie jest spełnione. Przeprowadzono krótka dyskusje kontrowersji związanych z wykrywaniem przypadkowych powiązań

Słowa kluczowe

EN

Bayesian networks; directed acyclic graph; Arthur Cayley; intervention calculus; graphical Markov model; Markov equivalence; structure learning

PL

sieci bayesowskie; graf acykliczny skierowany; wyznaczanie przyczyn; ocena przyczyny; ocena znaczenia czynnika; graficzny model Markowa; drzewo markowskie; równoważność Markowa; uczenie maszynowe; systemy uczące się; sztuczna inteligencja; systemy eksperckie; wyszukiwarki internetowe; wykrywanie zależności; rozpoznawanie struktury

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Mathematica Applicanda
• Rocznik: 2012
• Tom: Vol. 40, No. 1
• Strony: 53--103
• Opis fizyczny: Bibliogr. 98 poz., wykr.

Twórcy

autor

Koski T. J. T.

autor

Noble J. M.

• KTH Royal Institute of Technology Department of Mathematics, KTH Royal Institute of Technology, SE - 100 44 Stockholm, Sweden,

Bibliografia

• [1] Akaike, H. (1974) A new look at the statistical model identification IEEE Transactions on Automatic Control vol 19 no 6 pp 716-723.
• [2] Barros, B. (2012) Incremental Learning Algorithms for Financial Data Modelling Master Thesis, Linkoping University, Department of Mathematics LiTH-MAT-INT-A-2012/01-SE (supervisor: J.M. Noble)
• [3] Boutilier, C.; Friedman, N.; Godszmidt, M.; Koller, D. (1996) Context specific independence in Bayesian networks Proceedings of the Twelfth International Conference on Uncertainty in Artificial Intelligence pp. 115 - 123 Morgan Kaufmann Publishers Inc.
• [4] Bromberg, F.; Margaritis, D. (2009) Improving the reliability of causal discovery from small data sets using argumentation Journal of Machine Learning Research vol. 10 pp. 301 - 340
• [5] Bulashevska, S.; Eils, R. (2005) Inferring genetic regulatory logic from expression data Bioinformatics vol 21 no 11 pp 2706 - 2713
• [6] Capitanio, A.; Azzalini, A.; Stanghellini, E. (2003) Graphical models for skew-normal variates Scandinavian Journal of Statistics vol 30 pp 129 - 144
• [7] Castelo, R.; Siebes, A. (2000) Priors on network structures. Biasing the search for Bayesian networks International Journal of Approximate Reasoning vol 24 pp 39 - 57
• [8] Cayley, A. (1853) Note on a Question in the Theory of Probabilities The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science vol. VI. - fourth series July -December, 1853, Taylor and Francis. p. 259
• [9] Cayley, A. (1854) On the theory of groups as depending on the symbolic equation _n = 1 Phil. Mag. vol. 7 no. 4 pp 40 - 47
• [10] Cayley, A. (1858) A Memoir on the Theory of Matrices Phil. Trans. of the Royal Soc. Of London, vol 148 p. 24
• [11] Cayley, A. (1869) A Memoir on Cubic Surfaces Philosophical Transactions of the Royal Society of London (The Royal Society) vol 159 pp 231-326
• [12] Cayley, A. (1878) Desiderata and suggestions: No. 2. The Theory of groups: graphical representation Amer. J. Math. vol. 1 no. 2, 174-176
• [13] Cayley, A. (1889) A Theorem on Trees Quarterly Journal of Mathematics vol 23, pp 276-378
• [14] Cheng, J.; Greiner, R.; Kelly, J.; Bell, D. A.; Liu, W. (2002) Learning Bayesian networks from data: An information-theory based approach Artificial Intelligence vol 137 pp 43 - 90.
• [15] Chickering, D. M. (2002) Optimal structure identification with greedy search Journal of Machine Learning Research, 507-554.
• [16] Chow, C.K.; Liu, C.N. (1968) Approximating Discrete Probability Distributions with Dependence Trees IEEE Transactions on Information Theory, vol. IT - 14 no. 3
• [17] Cooper, G.F.; Herskovitz, E. (1992)A Bayesian Method for the Induction of Probabilistic Networks from Data Machine Learning vol. 9 pp. 309 - 347
• [18] Corander, J.; Ekdahl, M.; Koski, T. (2008)Parallel interacting McMC for learning topologies of graphical models Data mining and knowledge discovery vol 17 no. 3 pp 431-456 Springer
• [19] Corander, J.; Gyllenberg; M.; Koski, T. (2010) Learning Genetic Population Structures Using Minimization of Stochastic Complexity Entropy vol 12 no 5 pp 1102 - 1124.
• [20] Corander, J; Koski, T; Nyman, H.; Pensar, J. (2012) Stratified Graphical Models (submitted)
• [21] Dawid, A.P.; Mortera, J.; Pascali, V.L.; Van Boxel, D. (2002) Probabilistic expert systems for forensic inference from genetic markers Scandinavian Journal of Statistics vol 29 no 4 pp 577 - 595
• [22] Dean, T.; Kanazawa, K. (1989) A model for reasoning about persistence and causation Artificial Intelligence vol 93 no 1-2 pp 1-27
• [23] Drton, M.; Sturmfels, B.; Sullivant, S. (2009) Lectures on algebraic statistics Birkhüser
• [24] Durbin, A.K.R.; Eddy, S.; Mitchison, G. (1998) Biological Sequence Analysis: Probabilistic Models of Protein and Nucleic Acids Cambridge University Press
• [25] Ekdahl, M.; Koski, T. (2006) Bounds for the Loss in Probability of Correct Classification Under Model Based Approximation Journal of Machine Learning Research vol 7 pp 2449 - 2480
• [26] Fast, A. (2010) Learning the structure of Bayesian networks with constraint satisfaction Ph.D. thesis, Graduate School of the University of Massachusetts Amherst, Department of Computer Science
• [27] Flores, M.J.; Nicholson, A.E.; Brunskill, A.; Korb, K.B., Mascaro, S. (2011) Incorporating expert knowledge when learning Bayesian network structure: A medical case study Artificial Intelligence in Medicine vol 53 pp 181 - 204
• [28] Freedman, D.; Humphreys P. (1999) Are there algorithms that discover causal structure? Synthese vol 121 pp 29 - 54
• [29] Friedman, N.; Nachman, I.; Pe'er, D. (1999) Learning Bayesian network structure from massive datasets: the 'sparse candidate' algorithm Proc. Sixteenth Conference on Uncertainty in Artificial Intelligence (UAI '99) pp 196 - 205
• [30] Friedman, N.; Linial, M.; Nachman, I.; Pe'er, D. (2000) Using Bayesian Networks to Analyse Expression Data Journal of Computational Biology 7 no 3/4 pp 601 - 620
• [31] Friedman, N. (2004) Inferring Cellular Networks Using Probabilistic Graphical Models Science Vol 303 no 5659 pp 799-805, DOI: 10.1126/science.1094068
• [32] Gamerman, D.; Lopes, H.F. (2006) Markov chain Monte Carlo: stochastic simulation for Bayesian inference Chapman and Hall CRC
• [33] Garcia, L.D.; Stillman, M.; Sturmfels, B. (2005) Algebraic geometry of Bayesian networks Journal of Symbolic Computation 39 pp 331-355
• [34] Greenland, S.; Pearl, J.; Robins, J.M. (1999) Causal diagrams for epidemiologic research Epidemiology pp 37 - 48
• [35] Grim, J. (1984) On structural approximating multivariate discrete probability distributions Kybernetika vol 20, pp 1 - 17.
• [36] Hajek, P.; Havranek, T.; Jirousek, R. (1992) Processing uncertain information in expert systems CRC press
• [37] Heckerman, D.; Geiger, D.; Chickering, D.M. (1995) Learning Bayesian Networks: The Combination of Knowledge and Statistical Data Machine Learning vol. 20 pp. 197 - 243
• [38] Humphreys, P.; Freedman, D. (1996)The grand leap British Journal for the Philosophy of Science vol 47 pp 113 - 123
• [39] Jaynes, E.T. (2003) Probability Theory. The Logic of Science Cambridge University Press
• [40] Kiiveri, H.; Speed, T.P.; Carlin, J.B. (1984) Recursive Causal Models J. Austral. Math. Soc. (series A) vol. 36 pp. 30 - 52
• [41] Kellerer, H. G. (1964) Verteilungsfunktionen mit gegebenen Marginalverteilungen Zeitschrift für Wahrschenlichkeitstheorie und Verwandte Gebiete vol 3 pp 247 - 270
• [42] Kellerer, H. G. (1991) Indecomposable marginal problems in: Advances in probability distributions with given marginals: beyond the copulas, Springer Verlag, Berlin, pp 139 - 149
• [43] Kłopotek, M.A. (2002) A New Bayesian Tree Learning Method with Reduced Time and Space Complexity Fundamenta Informaticae vol. 49 pp 349 - 367
• [44] Kłopotek, M.A. (2003)Reasoning and Learning in Extended Structured Bayesian Networks Fundamentae Informaticae vol. 58 pp 105 - 137
• [45] Koivisto, M.; Sood, K. (2004) Exact Bayesian Structure Discovery in Bayesian Networks Journal of Machine Learning Research vol. 5 pp. 549 - 573
• [46] Koller, D.; Friedman, N. (2009) Probabilistic graphical models: principles and techniques The MIT Press
• [47] Korb, K.B.;Wallace, C.S. (1997)In Search of the Philosopher's Stone: Remarks on Humphreys and Freedman's Critique of Causal Discovery British Journal for the Philosophy of Science vol 48 pp 543 - 553.
• [48] Koski, T.; Noble, J.M. (2009) Bayesian Networks: An Introduction Wiley
• [49] Langseth, H.; Portinale, L. (2007) Bayesian networks in reliability Reliability Engineering and System Safety vol 92 pp 92 - 108
• [50] Lauritzen, S.L.; Spiegelhalter, D.J. (1988)Local Computations of Probabilities on Graphical Structures and their Applications to Expert Systems Journal of the Royal Statistical Society B (Methodological) vol. 50 no. 2 pp. 157 - 224
• [51] Lauritzen, S.L. (1992)Propagation of Probabilities, Means and Variances in Mixed Graphical Association Models Journal of the American Statistical Association vol. 78 no. 420 pp. 1098 - 1108
• [52] Lewis, P.M. II ( 1959) Approximating Probability Distributions to Reduce Storage Requirements Information and Control vol 2 no 3 pp 214 - 225
• [53] Lindley, D. (2002) Seeing and Doing: The Concept of Causation International Statistical Review / Revue International de Statistique vol. 70 pp 191 - 197
• [54] Madigan, D.; Andersson, S.A.; Perlman, M.D.; Volinsky, C.T. (1996) Bayesian Model Averaging and Model Selection for Markov Equivalence Classes of Acyclic Digraphs Communications In Statistics: Theory and Methods vol. 25, no. 11 pp. 2493-2519
• [55] Madigan. D.; York, J. (1995) Bayesian Graphical Models for Discrete Data International Statistical Review vol. 63 pp. 215 - 232
• [56] Malvestuto, F.M. (1988) Existence of extensions and product extensions for discrete probability distributions Discrete Mathematics vol 69 pp 61 - 77
• [57] Markowetz, F.; Spang, R. (2007)Inferring Cellular Networks - A Review BMC bioinformatics vol. 8 (Suppl 6) : S5
• [58] Meek, C. (1995) Causal inference and causal explanation with background knowledge Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence pp 403 - 410
• [59] Moore, A.; Wong, W-K. (2003) Optimal Reinsertion: A new search operator for accelerated and more accurate Bayesian network structure learning Proceedings of the Twentieth International Conference on Machine Learning (ICML - 2003), Washington DC
• [60] Murphy, K.P. (2002)Dynamic Bayesian Networks: Representation, Inference and Learning Ph.D. dissertation, computer science, University of California, Berkeley.
• [61] Neapolitan, R.E. (2004) Learning Bayesian Networks Pearson Prentice Hall, Upper Saddle River, New Jersey.
• [62] Nelson, E. (1987) Radically Elementary Probability Theory Princeton University Press
• [63] Pearl, J. (1982) Reverend Bayes on Inference Engines: A Distributed Hierarchical Approach AAAI - 82 Proceedings pp. 133 - 136
• [64] Pearl, J. (1985)A model of activated memory for evidential reasoning in Proceedings of the Cognitive Science Society (1985) pp 329 - 334
• [65] Pearl, J. (1987) Evidential Reasoning Using Stochastic Simulation of Causal Models Artificial Intelligence, vol. 32, pp. 245-257.
• [66] Pearl, J. (1990) Probabilistic Reasoning in Intelligent Systems 2nd revised printing, Morgan and Kaufman Publishers Inc., San Francisco
• [67] Pearl, J. (1995)Causal Diagrams for Empirical Research Biometrika vol. 82 pp. 669 - 710
• [68] Pearl, J. (1995)Causal Inference from Indirect Experiments Artificial Intelligence in Medicine vol. 7 pp. 561 - 582
• [69] Pearl, J. (2000) Causality: Models, Reasoning and Inference Cambridge University Press
• [70] Pearl, J.; Geiger, D.; Verma, T. (1989) Conditional Independence and its Representations, Kybernetica vol. 25 no. 2 pp. 33 - 44
• [71] Pearl, J.; Verma, T. (1987) The Logic of Representing Dependencies by Directed Acyclic Graphs Proceedings of the AAAI, Seattle, Washington pp. 374 - 379
• [72] Pearl, J. (1988) Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference Morgan Kaufmann, San Mateo, CA.
• [73] Pearl, J. (1995) Causal diagrams for empirical research Biometrika vol 82 pp 669-710
• [74] Pistone, G.; Riccomagno, E.; Wynn, H. (2001) Algebraic Statistics: Computational Commutative Algebra in Statistics Chapman and Hall, Boca Raton.
• [75] Pourret, O.; Nam, P.; Na¨ım, P; Marcot, B. (2008)Bayesian networks: a practical guide to applications Wiley
• [76] Ramoni, M.; Sebastiani, P. (1997) Parameter Estimation in Bayesian Networks from Incomplete Databases Knowledge Media Institute, KMI-TR-57
• [77] Rissanen, J. (1978) Modelling By Shortest Data Description Automatica, vol 14 pp 465-471
• [78] Robins, J.M.; Scheines, R.; Spirtes, P.; Wasserman, L. (2003) Uniform consistency in causal inference Biometrika vol 90 no 3 pp 491- 515
• [79] Robinson, R.W. (1977)Counting Unlabelled Acyclic Digraphs Springer Lecture Notes in Mathematics: Combinatorial Mathematics V, C.H.C. Little (ed.) pp. 28 - 43.
• [80] Sadeghi, K.; Lauritzen, S, (2012) Markov Properties for Mixed Graphs submitted to Bernoulli, available on arxiv arxiv.1109.5909v2
• [81] Schwartz, G.E. (1978) Estimating the dimension of a model Annals of Statistics vol 6 no 2 pp 461-464.
• [82] Schmidt, M.; Niculescu-Mizil, A.; Murphy, K. (2007) Learning graphical model structure using l1-regularization paths Proceedings of the National Conference on Artificial Intelligence vol 22 no 2 pp 12- 78
• [83] Shafer, G. (1996) Probabilistic Expert Systems Society for Industrial Mathematics
• [84] Spiegelhalter, D.J.; Dawid, A.P.; Lauritzen, S.L.; Cowell, R.G. (1993) Bayesian analysis in expert systems Statistical Science pp 219 - 247
• [85] Spirtes, P.; Glymour, C.; Scheines, R. (1993) Causation, Prediction and Search Lecture Notes in Statistics no. 81 Springer-Verlag New York
• [86] Spirtes, P.; Glymour, C.; Scheines, R. (1997) Reply to Humphrey's and Freedman's Review of Causation, Prediction, and Search British Journal for the Philosophy of Science vol 48 pp 555 - 568.
• [87] Spirtes, P.; Glymour. C.; Scheines, R. (2000) Causation, Prediction and Search second edition, The MIT press.
• [88] Studen`y, M. (2005) Probabilistic conditional independence structures Springer Verlag
• [89] Sturmfels, B. (2002) Solving Systems of Polynomial Equations In: CBMS Lectures Series, American Mathematical Society.
• [90] Tsamardinos, I.; Brown, L.E.; Aliferis, C.F. (2006) The Max - Min Hill - Climbing Bayesian Network Structure Learning Algorithm Machine Learning vol. 65 pp. 31 - 78
• [91] VanderWeele, T.J.; Robins, J.M. (2007) Directed Acyclic Graphs, Sufficient Causes, and the Properties of Conditioning on a Common Effect American Journal of Epidemiology, vol 166 no 9 pp 1096 - 1104
• [92] Wiberg, N. (1996) Codes and Decoding on General Graphs Linköping Studies in Science and Technology. Dissertation 440 Linkopings Universitet, Linkoping
• [93] Wright, S. (1921)Correlation and Causation Journal of Agricultural Research vol. 20 pp. 557 - 585
• [94] Wright, S. (1934) The method of path coefficients Ann. Math. Statist. vol 5 pp 161 - 215.
• [95] Xie, X.; Geng, Z. (2008)A recursive method for structural learning of directed acyclic graphs Journal of machine learning research vol. 9 pp. 459 - 483
• [96] Yehezkel, R.; Lerner, B. (2009)Bayesian network structure learning by recursive autonomy identification Journal of Machine Learning Research vol. 10 pp 1527 - 1570
• [97] Zhang, J; Spirtes, P. (2002)Strong faithfulness and uniform consistency in causal inference Proceedings of the nineteenth conference on uncertainty in artificial intelligence pp 632-639, Morgan Kaufmann Publishers Inc.
• [98] Zhang, S.; Song, S. (2011)A Novel Attack Graph Posterior Inference Model Based on Bayesian Networks Journal of Information Security vol 2 pp 8 - 27