Computer Science ›› 2014, Vol. 41 ›› Issue (9): 1-17.doi: 10.11896/j.issn.1002-137X.2014.09.001

    Next Articles

Representation Theory of Probabilistic Graphical Models

LIU Jian-wei,LI Hai-en and LUO Xiong-lin   

  • Online:2018-11-14 Published:2018-11-14

Abstract: Probabilistic graphical models bring together graph theory and probability theory in a formalism,so the joint probabilistic distribution of variables in the model can be represented using graph.In recent years,probabilistic graphical models have become the focus of the research in uncertainty inference,because of its bright prospect for the application in artificial intelligence,machine learning,computer vision and so on.This work introduced the representations of probabilistic graphical models and discussed how to represent the joint probabilistic distribution compactly using the indepen-dences in the network.First,models of the conditional probabilistic distribution of single node and their independences were introduced,including tabular CPD,deterministic CPD,context-specific CPD,CPD of causal influence,Gaussian models and hybrid models,and a general framework called the exponential family that encompasses a broad range of distributions was defined.Then Bayesian network representation and its independence properties were described in detail,as well as the Bayesian network of Gaussian distribution and exponential family.This work also introduced Markov network representation,independence properties in Markov network and Markov network of Gaussian distribution and exponential family.We also gave two partially directed models,conditional random fields and chain graph models.In a-ddition,this work discussed template-based representations,including temporal models that contain dynamic Bayesian network and state-observation models,directed probabilistic models for object-relational domains which contain plate models and probabilistic relational models,and undirected representation for object-relational domains.Finally,this work raised some questions that probabilistic graphical models face with and discussed its development in the future.

Key words: Probabilistic graphical model,Bayesian network,Markov network,Dynamic bayesian network,Probabilistic relational model,Conditional random field,Chain graph,Exponential family,Local probabilistic model

[1] Langseth H,Portinale L.Bayesian networks in reliability[J].Reliability Engineering and System Safety,2007,92 (1):92-108
[2] Santana R,Shakya S.Probabilistic Graphical Models and Mar-kov Networks[J].Markov Networks in Evolutionary Computation,2012,14(1):3-19
[3] Shakya S,Santana R.A Review of Estimation of DistributionAlgorithms and Markov Networks[J].Markov Networks in Evo-lutionary Computation,2012,14(1):21-37
[4] Pal C J,Weinman J J,Tran L C,et al.On Learning Conditional Random Fields for Stereo:Exploring Model Structures and Approximate Inference[J].International Journal of Computer Vision,2012,99(3):319-337
[5] Golumbic M C,Maffray F,Morel G.A characterization of chain probe graphs[J].Annals of Operation Research,2009,188(1):175-183
[6] Sun X,Huang D.Nested Template-based Model for Chinese-Japanese Machine Translation[C]∥Proceedings of 14th International Conference on Computational Science and Engineering.2011:161-166
[7] Murphy K.Dynamic Bayesian networks:representation,infer-ence and learning[D].Berkeley:University of California,2002
[8] Getoor L,Taskar B.Introduction to Statistical Relational Lear-ning[M].MIT Press,2007
[9] Friedman N,Getoor L,Koller D,et al.Learning probabilistic relational models[C]∥Proceedings of the 16th International Joint Conference on Artificial Intelligence.1999:1300-1307
[10] Medina-Oliva G,Weber P,Levrat E,et al.Use of probabilisticrelational model (PRM) for dependability analysis of complex systems[C]∥Proceedings of 12th IFAC Symposium on Large Scale Systems:Theory and Applications.2010
[11] Shafer G,Pearl J.Readings in uncertain reasoning[M].SanFrancisco,CA:Morgan Kaufmann Publishers,1990
[12] Halpern J Y.A logical approach to reasoning about uncertainty:a tutorial[M].Netherlands:Springer,1998:141-155
[13] Pearl J.Probabilistic reasoning in intelligent systems:networks of plausible inference[M].San Mateo,California,Morgan Kaufmann Publishers,1988:117-133
[14] Lauritzen S L,Spiegelhalter D J.Local Computations with Probabilities on Graphical Structures and Their Application to Expert Systems[J].Journal of the Royal Statistical Society,Series B (Methodological),1988,50(2):157-224
[15] Dawid A P.Influence Diagrams for Causal Modelling and Inference[J].International Statistical Review,2002,70(2):161-189
[16] Geiger D,Verma T,Pearl J.Identifying independence in Bayesian networks[J].Networks,1990,20(5):507-534
[17] Verma T,Pearl J.Causal networks:semantics and expressiveness[C]∥Proceedings of the Fourth Annual Conference on Uncertainty in Artificial Intelligence.The Netherlands:North-Holland Publishing,1990:69-78
[18] Marchetti G M,Wermuth N.Matrix representations and inde-pendencies in directed acyclic graphs[J].Annals of Statistics,2009,37(2):961-978
[19] VanderWeele T J,Robins J M.Minimal sufficient causation and directed acyclic graphs[J].Annals of Statistics,2009,37(3):1437-1465
[20] Heckerman D.A Tutorial on Learning with Bayesian Networks[J].Studies in Computational Intelligence,2008,15:33-82
[21] Koller D,Friedman N.Probabilistic Graphical Models:Principlesand Techniques[M].MIT Press,2009
[22] Heckerman D E,Nathwani B N.An evaluation of the diagnostic accuracy of Pathfinder[J].Computers and Biomedical Research,1992,25(1):56-74
[23] Sajda P.Machine learning for detection and diagnosis of disease[J].Annual Review of Biomedical Engineering,2006,8:537-565
[24] Larraaga P,Moral S.Probabilistic graphical models in artificial intelligence[J].Applied Soft Computing,2011,11(2):1511-1528
[25] Chang L,Duarte M M,Sucar L E.A Bayesian approach for object classification based on clusters of SIFT local features[J].Expert Systems with Applications,2012,39(2):1679-1686
[26] Raghuram S,Xia Y,Ge J,et al.AutoBayesian:DevelopingBayesian Networks Based on Text Mining[C]∥Database Systems for Advanced Applications.Springer Berlin Heidelberg,2011:450-453
[27] Rautenberg W.Complete logical Calculi[M].A Concise Intro-duction to Mathematical Logic.New York:Springer 2010:91-134
[28] Martin R,Zhang J,Liu C.Dempster-Shafer Theory and Statistical Inference with Weak Beliefs[J].Statistical Science,2010,25(1):72-87
[29] Dubois D,Prade H.Possibility theory and formal concept analysis:Characterizing independent sub-contexts[J].Fuzzy Sets and Systems,2012,196:4-6
[30] Ognjanovi′ Z,Perovi′ A,Rakovi′ M.Logics with the Qualitative Probability Operator[J].Logic Journal of the IGPL,2008,16(2):105-120
[31] Cozman F G.Graphical models for imprecise probabilities[J].International Journal of Approximate Reasoning,2005,39(2/3):167-184
[32] Cressie N,Lele S.New Models for Markov Random Fields[J].Journal of Applied Probability,1992,29(4):877-884
[33] Geiger D,Pearl J.Logical and Algorithmic Properties of Conditional Independence and Graphical Models[J].Annals of Statistics,1993,21(4):2001-2021
[34] Wermuth N.Probability distributions with summary graphstructure[J].Bernoulli,2011,17(3):845-879
[35] Murthy V S,Gupta S,Mohanta D K.Digital image processing approach using combined wavelet hidden Markov model for well-being analysis of insulators[J].Image Processing,2011,5(2):171-183
[36] Ye J.Image Filtering with Associative Markov Networks forECT With Distinctive Phase Origins[J].IEEE Sensors Journal,2012,12(7):2435-2443
[37] Morariu V I,Davis L S.Multi-agent event recognition in structured scenarios[C]∥ IEEE Conference on Computer Vision and Pattern Recognition.IEEE,2011:3289-3296
[38] Gregor J,Thomason M G.Hybrid pattern recognition usingMarkov networks[J].IEEE.Trans.on Pattern Analysis and Machine and Intelligence,1993,15(6):651-656
[39] Xiang Y,Lesser V.A constructive graphical model approach for knowledge-based systems:a vehicle monitoring case study[J].Computational Intelligence,2003,19(3):284-309
[40] Xiang Y.Comparing alternative methods for inference in multiply sectioned Bayesian networks[J].International Journal of Approximate Reasoning,2003,33(3):235-254
[41] Richardson M,Domingos P.Markov logic networks[J].Machine Learning,2006,62(1/2):107-136
[42] Andrzejewski D,Zhu X,Craven M.A Framework for Incorporating General Domain Knowledge into Latent Dirichlet Allocation Using First-Order Logic[C]∥Proceedings of the 22nd International Joint Conference on Artificial Intelligence.AAAI Press,2011:1171-1177
[43] Rabiner L,Juang B.An introduction to hidden Markov models[J].ASSP Magazine,IEEE,1986,3(1):4-16
[44] Dean T,Kanazawa K.A model for reasoning about persistence and causation[J].Computational Intelligence,1989,5(2):142-150
[45] Saul L K,Jordan M I.Mixed Memory Markov Models:Decomposing Complex Stochastic Processes as Mixtures of Simpler Ones[J].Machine Learning,1999,37(1):75-87
[46] Ghahramani Z,Jordan M I.Factorial Hidden Markov Models[J].Machine Learning,1997,29(2/3):245-273
[47] Wainwright M J,Jordon M I.Graphical Models,ExponentialFamilies,and Variational Inference[J].Machine Learning,2008,1(1/2):1-305
[48] Fine S,Singer Y,Tishby N.The Hierarchical Hidden Markov Model:Analysis and Applications[J].Machine Learning,1998,32(1):41-62
[49] Duong T,Phung D,Bui H.Efficient duration and hierarchicalmodeling for human activity recognition[J].Artificial Intelligence,2009,173(7/8):830-856
[50] Smyth P,Heckerman D,Jordon M I.Probabilistic Independ-ence Networks for Hidden Markov Probability Models[J].Neural Computation,1997,9(2):227-269
[51] Murphy K P.Dynamic bayesian networks:Representation,inference and learning[D].Berkeley:University of California,Computer Science Division,2002
[52] Baah G K,Podgurski A,Harrold M J.The Probabilistic Program Dependence Graph and Its Application to Fault Diagnosis[J].Software Engineering,2010,36(4):528-545
[53] Gilks W R,Thomas A,Spiegelhalter D J.A Language and Program for Complex Bayesian Modelling[J].The Statistician,1994,43(1):169-177
[54] Getoor L,Friedman N,Koller D.Learning probabilistic models of link structure[J].Machine Learning,2003,3:679-707
[55] Fersini E,Messina E,Archetti F.Web page classification:a probabilistic model with relational uncertainty[C]∥Procee-dings of the Computational intelligence for knowledge-based systems design,and 13th international conference on Information processing and management of uncertainty.Dortmund,Germany:Springer Berlin Heidelberg,2010:109-118
[56] Heckerman D,Meek C,Koller D.Probabilistic entity-relation-ship models,PRMs,and plate models[C]∥Proceedings of the ICML-2004 Workshop on Statistical Relational Learning and its Connections to Other Fields.Banff,Canada:IMLS,2007:55-60
[57] Oh S,Sastry S.A polynomial-time approximation algorithm for joint probabilistic data association[C]∥Proceedings of American Control Conference.IEEE,2005:1283-1288
[58] Oh S,Russell S,Sastry S.Markov Chain Monte Carlo Data Association for Multi-Target Tracking[J].Automatic Control,2009,54(3):481-497
[59] Culotta A,Wick M,McCallum A.First-order probabilistic models for coreference resolution[C]∥Proceedings of Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics.New York,USA:the Association of Computational Linguistics,2007:81-88
[60] Wellner B,McCallum A,Peng F.An integrated,conditionalmodel of information extraction and coreference with application to citation matching[C]∥Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence.AUAI Press,2004:593-601
[61] Poon H,Domingos P.Joint inference in information extraction[C]∥Proceedings of the 22nd National Conference on Artificial Intelligence.AAAI Press,2007:913-918
[62] Milch B,Marthi B,Russell S,et al.BLOG:Probabilistic models with unknown objects[J].Statistical relational learning,2007:373
[63] Kersting K,De Raedt L.Basic principles of learning Bayesian logic programs[C]∥Probabilistic inductive logic programming.Springer Berlin Heidelberg,2008:189-221
[64] Glass D H.Likelihoods and Explanations in Bayesian Networks[J].Studies in Computational Intelligence,2008,109:325-341
[65] VanderWeele T J,Robins J M.Signed directed acyclic graphs for causal inference[J].Journal of the Royal Statistical Society:Series B (Statistical Methodology),2010,72:111-127
[66] Boutilier C,Friedman N,Goldszmidt M,et al.Context-specificindependence in Bayesian networks[C]∥Proceedings of the Twelfth international conference on Uncertainty in artificial intelligence.1996:115-123
[67] Poole D.First-order probabilistic inference[C]∥Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence.Mexico:Morgan Kaufmann,2003:985-991
[68] Li G,Gao J,Chen F.Construction of causality diagram model for diagnostics[C]∥Proceedings of Reliability and Maintainability Symposium.IEEE,2008:97-102
[69] van Gerven M A J,Lucas P J F,van der Weide T P.A generic qualitative characterization of independence of causal influence[J].International Journal of Approximate Reasoning,2008,48(1):214-236
[70] Lerner U,Segal E,Koller D.Exact inference in networks with discrete children of continuous parents[C]∥Proceedings of the 17th conference on Uncertainty in artificial intelligence.Morgan Kaufmann Publishers Inc.,2001:319-328
[71] Giang P H,Shenoy P P.Decision making on the sole basis of statistical likelihood[J].Artificial Intelligence,2005,165(2):137-163
[72] Daly R,Shen Q,Aitken S.Learning Bayesian networks:approaches and issues[J].The Knowledge Engineering Review,2011,26(2):99-157
[73] Liang P,Jordan M I,Klein D.Learning from measurements inexponential families[C]∥Proceedings of the 26th Annual International Conference on Machine Learning.ACM,2009:641-648
[74] Niepert M,Van Gucht D,Gyssens M.Logical and algorithmic properties of stable conditional independence[J].International Journal of Approximate Reasoning,2010,51(5):531-543
[75] Zhang J,Spirtes P.Detection of Unfaithfulness and RobustCausal Inference[J].Minds and Machines,2008,18(2):239-271
[76] Shachter R D.Bayes-ball:The rational pastime[C]∥Procee-dings of the Fourteenth Conference on Uncertainty in Artificial Intelligence.Morgan Kaufmann Publishers Inc.,1998:480-487
[77] Daly R,Shen Q.Learning Bayesian network equivalence classes with ant colony optimization[J].Journal of Artificial Intelligence Research,2009,35(1):391-447
[78] Pearl J,Verma T.An algorithm for deciding if a set of observed independencies has a causal explanation[C]∥Proceedings of Eighth Conference in Uncertainty in Artificial Intelligence.Morgan Kaufmann Publishers Inc.,1992:323-330
[79] Baioletti M,Busanello G,Vantaggi B.Finding P-Maps and I-Maps to Represent Conditional Independencies[J].Lecture Notes in Computer Science,2011,6717:239-250
[80] Chickering D M,Heckerman D,Meek C.A Bayesian approach to learning Bayesian networks with local structure[C]∥Procee-dings of the Thirteenth conference on Uncertainty in artificial intelligence.Morgan Kaufmann Publishers Inc.,1997:80-89
[81] Sullivant S.Algebraic geometry of Gaussian Bayesian networks[J].Advances in Applied Mathematics,2008,44(4):482-513
[82] Loeliger H A.An introduction to factor graphs[J].Signal Processing Magazine,2004,21(1):28-41
[83] Frey B J.Extending factor graphs so as to unify directed and undirected graphical models[C]∥Proceedings of the 19th confe-rence on Uncertainty in Artificial Intelligence.Morgan Kaufmann Publishers Inc.,2003:257-264
[84] Song H-R,Fuentes M,Ghosh S.A comparative study of Gaussian geostatistical models and Gaussian Markov random field models[J].Journal of Multivariate Analysis,2008,99(8):1681-1697
[85] Lindgren F,Rue H,Lindstrm J.An explicit link betweenGaussian fields and Gaussian Markov random fields:the stochastic partial differential equation approach[J].Journal of the Royal Statistical Society:Series B (Statistical Methodology),2011,73:423-498
[86] Lafferty J D,McCallum A,Pereira F C N.Conditional Random Fields:Probabilistic Models for Segmenting and Labeling Sequence Data[C]∥Proceedings of the Eighteenth International Conference on Machine Learning.ACM,2001:282-289
[87] Galley M.A skip-chain conditional random field for rankingmeeting utterances by importance[C]∥Proceedings of the 2006 Conference on Empirical Methods in Natural Language Proces-sing.Association for Computational Linguistics,2006:364-372
[88] Sutton C,Rohanimanesh K,McCallum A.Dynamic conditionalrandom fields:factorized probabilistic models for labeling and segmenting sequence data[J].Machine Learning Research,2007,8:693-723
[89] Drton M.Discrete chain graph models[J].Bernoulli,2009,15(3):736-753
[90] Studeny M,Bouckaert R R.On Chain Graph Models for Description of Conditional Independence Structures[J].The Annals of Statistics,1998,26(4):1434-1495
[91] Fersini E,Messina E,Archetti F.Probabilistic Relational Models with Relational Uncertainty:An Early Study in Web Page Classification[C]∥Proceedings of International Joint Conferences on Web Intelligence and Intelligent Agent Technologies.ACM,2009:139-142
[92] Wohlmayr M,Stark M,Pernkopf F.A Probabilistic Interaction Model for Multipitch Tracking With Factorial Hidden Markov Models[J].Audio,Speech,and Language Processing,2011,19(4):799-810
[93] Malcolm W P,Quadrianto N,Aggoun L.State EstimationSchemes for Independent Component Coupled Hidden Markov Models[J].Stochastic Analysis and Applications,2010,18(3):430-446
[94] Gales M,Young S.The application of hidden Markov models in speech recognition[J].Foundations and Trends in Signal Processing,2008,1(3):195-304
[95] Quinn J A,Williams C K I,McIntosh N.Factorial SwitchingLinear Dynamical Systems Applied to Physiological Condition Monitoring[J].Pattern Analysis and Machine Intelligence,2009,31(9):1537-1551
[96] Howard C,Stumptner M.Automated compilation of Object-Oriented Probabilistic Relational Models[J].International Journal of Approximate Reasoning,2009,50(9):1369-1398
[97] Knig J,Nordstrom L,Ekstedt M.Probabilistic RelationalModels for assessment of reliability of active distribution management systems[C]∥Proceedings of IEEE 11th International Conference on Probabilistic Methods Applied to Power Systems.IEEE,2010:454-459
[98] Wan H,Lin Y,Jia C,et al.Community-Based Relational Markov Networks in Complex Networks[J].Lecture Notes in Computer Science,2011,6954:301-310
[99] Yoshikawa K,Riedel S,Asahara M,et al.Jointly identifyingtemporal relations with Markov Logic[C]∥Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP.Association for Computational Linguistics,2009:405-413

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!