概率图模型推理方法的研究进展

doi:10.11896/j.issn.1002-137X.2015.04.001

摘要/Abstract

摘要： 近年来概率图模型已成为不确定性推理的研究热点,在人工智能、机器学习与计算机视觉等领域有广阔的应用前景。根据网络结构与查询问题类型的不同,系统地综述了概率图模型的推理算法。首先讨论了贝叶斯网络与马尔可夫网络中解决概率查询问题的精确推理算法与近似推理算法,其中主要介绍精确推理中的VE算法、递归约束算法和团树算法,以及近似推理中的变分近似推理和抽样近似推理算法,并给出了解决MAP查询问题的常用推理算法；然后分别针对混合网络的连续与混合情况阐述其推理算法,并分析了暂态网络的精确推理、近似推理以及混合情况下的推理；最后指出了概率图模型推理方法未来的研究方向。

关键词: 概率图模型,VE算法,团树算法,变分推理,抽样推理,MAP推理,混合网络推理,暂态网络推理

Abstract: In recent years,probabilistic graphical models have become the focus of the research in uncertainty inference,because of their bright prospect for the application in artificial intelligence,machine learning,computer vision and so forth.According to different network structures and query questions,the inference algorithms of probabilistic graphical models were summarized in a systematic way.First,exact and approximate inference algorithms for solving the probabili-ty queries in Bayesian network and Markov network were discussed,including variable elimination algorithms,conditioning algorithms,clique tree algorithms,variational inference algorithms and sampling algorithms.The common algorithms for solving MAP queries were also introduced.Then the inference algorithms in hybrid networks were described respectively for continuous or hybrid cases.In addition,this work analyzed the exact and approximate inference in temporal networks,and described inference in continuous or hybrid cases for temporal networks.Finally,this work raised some questions that the inference algorithms of probabilistic graphical models are facing with and discussed their deve-lopment in the future.

Key words: Probabilistic graphical model,Variable elimination,Clique tree,Variational inference,Sampling inference,MAP inference,Hybrid network inference,Temporal network inference

刘建伟,崔立鹏,黎海恩,罗雄麟. 概率图模型推理方法的研究进展[J]. 计算机科学, 2015, 42(4): 1-18. https://doi.org/10.11896/j.issn.1002-137X.2015.04.001

LIU Jian-wei, CUI Li-peng, LI Hai-en and LUO Xiong-lin. Research and Development on Inference Technique in Probabilistic Graphical Models[J]. Computer Science, 2015, 42(4): 1-18. https://doi.org/10.11896/j.issn.1002-137X.2015.04.001

参考文献

[1] Estabragh,Shojaei Z,et al.Bayesian network model for diagnosis of Social Anxiety Disorder[C]∥IEEE International Confe-rence on Bioinformatics and Biomedicine Workshops.2011:639-640
[2] Bickson D,Baron D,Ihler A,et al.Fault Identification Via Nonparametric Belief Propagation[J].IEEE Transactions on Signal Processing,2011,59(6):2602-2613
[3] Zhang Lei,Ji Qiang.Bayesian Network Model for Automatic and Interactive Image Segmentation[J].IEEE Transactions on Ima-ge Processing,2011,20(9):2582-2593
[4] Fernandez R,Picard R.Recognizing affect from speech prosody using hierarchical graphical models[J].Speech Communication,2011,53(9/10):1088-1103
[5] Badiu M A,Kirkelund G E,Manchón C N,et al.Message-pas-sing algorithms for channel estimation and decoding using approximate inference[C]∥IEEE International Symposium on Information Theory.Cambridge,MA,USA:IEEE,2012:2376-2380
[6] Jordan M I,Ghahramani Z,Jaakkola T S,et al.An introduction to variational methods for graphical models[J].Machine lear-ning,1999,37(2):183-233
[7] Frey B J,Jojic N.A comparison of algorithms for inference and learning in probabilistic graphical models[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(9):1392-1416
[8] Guo H,Hsu W.A survey of algorithms for real-time Bayesian network inference[C]∥AAAI Workshop on Real-Time Decision Support and Diagnosis Systems.Edmonton,Canada:AAAI Press,2002:1-12
[9] 程强,陈峰,董建武,等.概率图模型中的变分近似推理方法[J].自动化学报,2012,38(11):1721-1734
[10] Jordan M I.Graphical models[J].Statistical Science,2004,19(1):140-159
[11] Koller D,Friedman N.Probabilistic graphical models:Principles and techniques[M].Cambridge,MA,USA:MIT Press,2009:1-283
[12] Dechter R.Bucket elimination:A unifying framework for rea-soning[J].Artificial Intelligence,1999,113(1/2):41-85
[13] Darwiche A.Recursive Conditioning:Any-space conditioning algorithm with treewidth-bounded complexity[J].Artificial Intelligence,2000,126(1/2):5-41
[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,1988,50:157-224
[15] Jordan M Z,Ghahramani T,et al.Introduction to variational methods for graphical models[J].Machine Learning,1999,37:183-233
[16] Wainwright M J,Jordan M I.Graphical Models,ExponentialFamilies,and Variational Inference[J].Machine Learning,2008,1(1/2):1-305
[17] Ajroud A,Omri M N,Youssef H,et al.Loopy Belief Propagation in Bayesian Networks:origin and possibilistic perspectives[J].arXiv preprint arXiv:1206.0976,2012
[18] Minka T P.Expectation propagation for approximate Bayesian inference[C]∥Proceedings of the Seventeenth conference on Uncertainty in artificial intelligence.Washington,USA:Morgan Kaufmann Publishers,2001:362-369
[19] Opper M,Winther O.Expectation consistent approximate infe-rence[J].Journal of Machine Learning Research,2005,6:2177-2204
[20] Geiger D,Meek C,Wexler Y.A variational inference procedure allowing internal structure for overlapping clusters and deterministic constraints[J].Journal of Artificial Intelligence Research,2006,27:1-23
[21] Rubinstein R Y,Kroese D P.Simulation and the Monte Carlo method[M].New Jersey,USA:Wiley Press,1981
[22] Andrieu C,De Freitas N,Doucet A,et al.An introduction to MCMC for machine learning[J].Machine learning,2003,50(1/2):5-43
[23] Casella G,Robert C P.Rao-Blackwellisation of sampling sche-mes[J].Biometrika,1996,83(1):81-94
[24] Gogate V G.Sampling Algorithms for Probabilistic GraphicalModels with Determinism[D].California:University of California,2009
[25] Weiss Y,Freeman W T.On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs[J].IEEE Transactions on Information Theory,2001,47(2):736-744
[26] Felzenszwalb P F,Huttenlocher D P.Efficient belief propagation for early vision[J].International journal of computer vision,2006,70(1):41-54
[27] Wainwright M J,Jaakkola T S,Willsky A S.MAP estimationvia agreement on trees:message-passing and linear programming[J].IEEE Transactions on Information Theory,2005,51(11):3697-3717
[28] Boykov Y,Veksler O,Zabih R.Fast approximate energy minimization via graph cuts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23(11):1222-1239
[29] Sakurikar P,Narayanan P J.Fast graph cuts using shrink-ex-pand reparameterization[C]∥Proceedings of the 2012 IEEE Workshop on the Applications of Computer Vision.Breckenridge,CO,USA:IEEE,2012:65-71
[30] Park J D,Darwiche A.Approximating MAP using local search[C]∥Proceedings of the Seventeenth conference on Uncertainty in artificial intelligence.Washington,USA:Morgan Kaufmann Publishers,2001:403-410
[31] Lerner U,Segal E,Koller D.Exact inference in networks with discrete children of continuous parents[C]∥Proceedings of the Seventeenth conference on Uncertainty in artificial intelligence.Washington,USA:Morgan Kaufmann Publishers Inc.,2001:319-328
[32] Madsen A L.Belief update in CLG Bayesian networks with lazy propagation[J].International Journal of Approximate Reaso-ning,2008,49(2):503-521
[33] Lauritzen S L,Jensen F.Stable local computation with conditional Gaussian distributions[J].Statistics and Computing,2001,11(2):191-203
[34] Moral S,Rumi R,Salmeron A.Mixtures of truncated exponentials in hybrid Bayesian networks[J].Lecture notes in computer science,2001:156-167
[35] Shenoy P P,West J C.Inference in hybrid Bayesian networksusing mixtures of polynomials[J].International Journal of Approximate Reasoning,2011,52(5):641-657
[36] Darwiche A.Constant-space reasoning in dynamic Bayesian networks[J].International journal of approximate reasoning,2001,26(3):161-178
[37] Bilmes J A,Bartels C.On triangulating dynamic graphical mo-dels[C]∥Proceedings of the Nineteenth conference on Uncertainty in Artificial Intelligence.Edmonton,Alberta,Canada:Morgan Kaufmann Publishers,2002:47-56
[38] Cohn I,El-Hay T,Friedman N,et al.Mean field variational approximation for continuous-time Bayesian networks[J].The Journal of Machine Learning Research,2010,11:2745-2783
[39] Nodelman U,Koller D,Shelton C.Expectation propagation forcontinuous time Bayesian networks[C]∥Proceedings of the Twenty-first Conference on Uncertainty in Artificial Intelligence.Edinburgh,Scotland,UK:AUAI Press,2005:421-430
[40] Koller D,Lerner U.Sampling in factored dynamic systems[M].New York:Springer,2001:445-464
[41] Lopes H F,Tsay R S.Particle filters and Bayesian inference in financial econometrics[J].Journal of Forecasting,2011,30(1):168-209
[42] Besada-Portas E,Plis S M,Jesus M,et al.Parallel subspace sampling for particle filtering in dynamic Bayesian networks[M].Springer:Berlin Heidelberg,2009:131-146
[43] Hajishirzi H,Amir E.Reasoning about Deterministic Actionswith Probabilistic Prior and Application to Stochastic Filtering[C]∥Proceedings of the Twelfth International Conference on the Principles of Knowledge Representation and Reasoning.2010:456-464
[44] Johnston L A,Krishnamurthy V.An improvement to the interacting multiple model (IMM) algorithm[J].IEEE Transactions on Signal Processing,2001,49(12):2909-2923
[45] Taghipour N,Fierens D,Davis J,et al.Lifted variable elimination with arbitrary constraints[C]∥Proceedings of the fifteenth international conference on Artificial Intelligence and Statistics.La Palma,Canary Islands:JMLR.org,2012,22:1194-1202
[46] Nima T,Jesse D.Generalized counting for lifted variable elimination[C]∥Proceedings of the Second International Workshop on Statistical Relational AI.2012:133-159
[47] Yedidia J S,Freeman W,Weiss Y.Constructing free-energy approximations and generalized belief propagation algorithms[J].IEEE Transaction on Information Theory,2005,51(7):2282-2312
[48] Dechter R,Rish I.Mini-buckets:A general scheme for approximating inference[J].Journal of the ACM,2002,50(2):107-153
[49] Bodlaender H L.Treewidth:Structure and algorithms[M]∥Structural information and communication complexity.Berlin Heidelberg:Springer,2007:11-25
[50] Shoikhet K,Geiger D.A practical algorithm for finding optimal triangulations[C]∥Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Conference on Innovative Applications of Artificial Intelligence.Providence,Rhode Island,USA:AAAI Press,1997:185-190
[51] Berry A,Heggernes P,Simonet G.The Minimum Degree Heuristic and the Minimal Triangulation Process[J].Computer Scien-ce,2003,2880:58-70
[52] Gelfand A,Kask K,Dechter R.Stopping Rules for Randomized Greedy Triangulation Schemes[C]∥Proceedings of the Twenty-Fifth AAAI Confe-rence on Artificial Intelligence.2011:1043-1048
[53] Kask K,Gelfand A,Otten L,et al.Pushing the Power of Stochastic Greedy Ordering Schemes for Inference in Graphical Models[C]∥Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence.2011:54-60
[54] Allen D,Darwiche A.New advances in inference by recursive conditioning[C]∥Proceedings of the Nineteenth conference on Uncertainty in Artificial Intelligence.2003:2-10
[55] Grant K,Horsch M C.Efficient Caching in Elimination Trees[C]∥Proceedings of the Twentieth International Florida Artificial Intelligence Research Society Conference.Key West,Florida,USA:AAI Press,2007:98-103
[56] Darwiche A.Recursive conditioning:any-space conditioning algorithm with treewidth-bounded complexity[C]∥ Proceedings of the 19th Conference on Uncertainty in Artifical Intelligence.2000:5-41
[57] Grant K,Horsch M.Conditioning graphs:practical structuresfor inference in bayesian networks[C]∥Proceedings of the 18th Australian Joint Conference on Artificial Intelligence.Sydney,Australia:Springer,2005:49-59
[58] Grant K,Horsch M C.Methods for constructing balanced elimination trees and other recursive decompositions[J].Internationaljournal of approximate reasoning,2009,50(9):1416-1424
[59] Grant K,Scholten K.On the Structure of Elimination Trees for Bayesian Network Inference[J].Advances in Soft Computing,2010,6348:208-220
[60] Kozlov A V,Singh J P.A parallel Lauritzen-Spiegelhalter algorithm for probabilistic inference[C]∥Proceedings of the 1994 ACM/IEEE conference on Supercomputing.IEEE Compu-ter Society Press,1994:320-329
[61] Xia Y,Prasanna V K.Scalable node-level computation kernels for parallel exact inference[J].IEEE Transactions on Compu-ters,2010,59(1):103-115
[62] Lu Zheng,Ole M,Jike Chong.Belief Propagation by MessagePassing in Junction Trees:Computing Each Message Faster Using GPU Parallelization[C]∥Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence.2011:1-9
[63] Xia Ying-long,Prasanna V K.Distributed Evidence Propagation in Junction Trees on Clusters[J].IEEE Transactions on Parallel and Distributed Systems,2012,23(7):1169-1177
[64] Coughlan J,Shen H.Dynamic quantization for belief propagation in sparse spaces[J].Computer Vision and Image Understan-ding,2007,106(1):47-58
[65] Sudderth E B,Freeman W T,Ihler A T,et al.Nonparametric belief propagation[C]∥Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Madison,WI,USA:IEEE,2003:605-612
[66] Noorshams N,Wainwright M J.Stochastic belief propagation:Low-complexity message-passing with guarantees[C]∥The 49th Annual Allerton Conference on Communication,Control,and Computing.Monticello,IL,USA:IEEE,2011:269-276
[67] Galinier P,Habib M,Paul C.Chordal Graphs and Their Clique Graphs[C]∥Proceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science.Springer-Verlag,1995:358-371
[68] Habib M,Limouzy V.On some simplicial elimination schemesfor chordal graphs[J].Electronic Notes in Discrete Mathema-tics,2009,32:125-132
[69] Matsui Y,Uehara R,Uno T.Enumeration of the perfect se-quences of a chordal graph[J].Theoretical Computer Science,2010,411(40):3635-3641
[70] Habib M,Stacho J.Reduced clique graphs of chordal graphs[J].European Journal of Combinatorics,2012,33(5):712-735
[71] Wainwright M J,Jaakkola T S,Willsky A S.A new class of upper bounds on the log partition function[J].IEEE Transactions on Information Theory,2005,51(7):2313-2335
[72] Wainwright M J,Jordan M I.Log-determinant relaxation for approximate inference in discrete Markov random fields[J].IEEE Transactions on Signal Processing,2006,54(6):2099-2109
[73] Globerson A,Jaakkola T.Approximate inference using planargraph decomposition[C]∥Proceedings of Advances in Neural Information Processing Systems.Vancouver,British Columbia,Canada:Curran Associates,2007:473-480
[74] Kumar P,Torr P,Zisserman A.Solving Markov random fields using second order cone programming[C]∥IEEE Computer Society Conference on Computer Vision and Pattern Recognition.New York,USA:IEEE,2006:1045-1052
[75] Dura-Bernal S,Wennekers T,Denham S L.Modelling objectperception in cortex:Hierarchical Bayesian networks and belief propagation[C]∥Proceedings of The 45th Annual Conference on Information Sciences and Systems.Baltimore,USA,2011:1-6
[76] Xiang X,Zhang M,Li G,et al.Real-time stereo matching based on fast belief propagation[J].Machine Vision and Applications,2012,23(6):1219-1227
[77] X Sheng-jun,L Guang-hui,L Xin.Image segmentation via ant colony algorithm and loopy belief propagation algorithm[C]∥Proceedings of The International Joint Conference on Neural Networks.Brisbane,Australia,2012:1-7
[78] Ihler A T,Iii J,Willsky W A .Loopy belief propagation:Convergence and effects of message errors[J].Journal of Machine Learning Research,2006,6(1):905-936
[79] Heskes T.On the uniqueness of loopy belief propagation fixed points[J].Neural Computation,2004,16(11):2379-2413
[80] Gamarnik D,Shah D,Wei Y.Belief propagation for min-costnetwork flow:Convergence and correctness[J].Operations research,2012,60(2):410-428
[81] Meshi O,Jaimovich A,Globerson A,et al.Convexifying the Bethe free energy[C]∥Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence.Montreal,Canada,2009:402-410
[82] Ihler A T,Fisher J W,Willsky A S,et al.Loopy belief propagation:convergence and effects of message errors[J].Journal of Machine Learning Research,2006,6(1):905-936
[83] Meltzer T,Globerson A,Weiss Y.Convergent message passing algorithms:a unifying view[C]∥Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence.Montreal,Canada,2009:393-401
[84] Zhou Hai-jun,Wang Chuang.Region graph partition functionexpansion and approximate free energy landscapes:Theory and some numerical Results[J].Journal of Statistical Physics,2012,148(3):513-547
[85] Seeger M,Nickisch H.Fast convergent algorithms for expectation propagation approximate Bayesian inference[C]∥Procee-dings of the 14th International Conference on Artificial Intelligence and Statistics.Lauderdale,USA,2011,15:652-660
[86] Bouchard-Cté A,Jordan M I.Optimization of structured mean field objectives[C]∥Proceedings of the Twenty-Fifth Confe-rence on Uncertainty in Artificial Intelligence.Montreal,QC,Canada:AUAI Press,2009:67-74
[87] Xing E P,Jordan M I,Russell S.A generalized mean field algorithm for variational inference in exponential families[C]∥Proceedings of the19th Conference on Uncertainty in Artificial Intelligence.Acapulco,Mexico:Morgan Kaufmann Publishers,2003:583-591
[88] Welling M,Teh Y W.Linear Response for Approximate Infe-rence[C]∥Proceedings of Advances in Neural Information Processing Systems.Vancouver,British Columbia,Canada:MIT Press,2003:361-368
[89] Roudi Y,Hertz J.Mean field theory for nonequilibrium network reconstruction[J].Physical Review Letters,2011,106(4):048702
[90] Martino L,Míguez J.A generalization of the adaptive rejection sampling algorithm[J].Statistics and Computing,2011,21(4):633-647
[91] Gogate V,Dechter R.SampleSearch:Importance sampling inpresence of determinism[J].Artificial Intelligence,2011,175(2):694-729
[92] Gogate V,Dechter R.Importance sampling-based estimationover AND/OR search spaces for graphical models[J].Artificial Intelligence,2012,184-185:38-37
[93] Yu H,van Engelen R.Arc refractor methods for adaptive impor-tance sampling on large Bayesian networks under evidential reasoning[J].International journal of approximate reasoning,2010,51(7):800-819
[94] Perilla J R,Beckstein O,Denning E J,et al.Computing ensembles of transitions from stable states:Dynamic importance sampling[J].Journal of computational chemistry,2011,32(2):196-209
[95] Yuan C,Druzdzel M J.An importance sampling algorithm based on evidence pre-propagation[C]∥Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence.Edmonton,Alberta,Canada:Morgan Kaufmann Publishers,2002:624-631
[96] Yuan C,Druzdzel M J.Importance sampling in Bayesian net-works:An influence-based approximation strategy for importance functions[C]∥Proceedings of the 21th Annual Confe-rence on Uncertainty in Artificial Intelligence.Edinburgh,Scotland:AUAI Press,2005:650-657
[97] Metropolis N,Rosenbluth A W,Rosenbluth M N,et al.Equation of state calculations by fast computing machines[J].The journal of chemical physics,1953,21(6):1087-1092
[98] Hastings W K.Monte Carlo sampling methods using Markovchains and their applications[J].Biometrika,1970,57(1):97-109
[99] Giordani P,Kohn R.Adaptive independent Metropolis-Hastings by fast estimation of mixtures of normals[J].Journal of Computational and Graphical Statistics,2010,19(2):243-259
[100] Beskos A,Stuart A.Computational complexity of Metropolis-Hastings methods in high dimensions[M].Berlin Heidelberg:Springer,2009:61-71
[101] Asmussen S,Glynn P W.A new proof of convergence of MCMC via the ergodic theorem[J].Statistics & Probability Letters,2011,81(10):1482-1485
[102] Doucet A,Gordon N J,Krishnamurthy V.Particle filters for state estimation of jump Markov linear systems[J].IEEE Transactions on Signal Processing,2001,49(3):613-624
[103] Van Dyk D A,Park T.Partially collapsed Gibbs samplers:Theory and methods[J].Journal of the American Statistical Association,2008,103(482):790-796
[104] Bidyuk B,Dechter R.Cutset sampling for Bayesian networks[J].Journal of Artificial Intelligence Research,2007,28(1):1-48
[105] Dechter R.Constraint Processing[M].Morgan Kaufmann Publishers,2003
[106] Favier A,De Givry S,Legarra A,et al.Pairwise decomposition for combinatorial optimization in graphical models[J].Artificial Intelligence,2011,22(3):21-26
[107] Sontag D,Meltzer T,Globerson A,et al.Tightening LP relaxations for MAP using message passing[C]∥Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence.Helsinki,Finland,2008:503-510
[108] Komodakis N,Paragios N.Beyond pairwise energies:Efficient optimization for higher-order MRFs[C]∥IEEE Conference on Computer Vision and Pattern Recognition.Miami,FL,USA,2009:2985-2992
[109] Werner T.A linear programming approach to max-sum problem:A review[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(7):1165-1179
[110] Globerson A,Jaakkola T.Fixing max-product:Convergentmessage passing algorithms for MAP LP-relaxations[C]∥Proceedings of Advances in Neural Information Processing Systems 21.Vancouver,British Columbia,Canada:Curran Associates,2007:553-560
[111] Zheng Yun,Chen Pei,Cao Jiang-zhong.MAP-MRF inferencebased on extended junction tree representation[C]∥IEEE Conference on Computer Vision and Pattern Recognition.IEEE,2012:1696-1703
[112] Jojic V,Gould S,Koller D.Accelerated dual decomposition for MAP inference[C]∥Proceedings of The 27th International Conference on Machine Learning.Haifa,Israel,2010:503-510
[113] Batra D,Gallagher A C,Parikh D,et al.Beyond trees:MRF inference via outer-planar decomposition[C]∥IEEE Conference on Computer Vision and Pattern Recognition.San Francisco,CA,USA,2010:2496-2503
[114] Martins A F T,Figueiredo M A T,Aguiar P M Q.An augmen-ted Lagrangian approach to constrained MAP inference[C]∥Proceedings of The 28th International Conference on Machine Learning.Bellevue,Washington,USA,2011:169-176
[115] Boykov Y,Veksler O,Zabih R.Fast approximate energy minimization via graph cuts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23(11):1222-1239
[116] Kolmogorov V,Rother C.Minimizing nonsubmodular functions with graph cuts-a review[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(7):1274-1279
[117] Fix A,Gruber A,Boros E,et al.A graph cut algorithm for higher-order Markov random fields[C]∥IEEE International Conference on Computer Vision.Barcelona,Spain:IEEE,2011:1020-1027
[118] Kumar M P,Veksler O,Torr P H S.Improved Moves forTruncated Convex Models[J].Journal of Machine Learning Research,2011,12:31-67
[119] Park J D,Darwiche A.Solving MAP exactly using systematic search[C]∥Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence.Morgan Kaufmann PublishersInc.,2002:459-468
[120] Malioutov D M,Johnson J K,Willsky A S.Walk-sums and belief propagation in Gaussian graphical models[J].The Journal of Machine Learning Research,2006,7:2031-2064
[121] El-Kurdi Y,Giannacopoulos D,Gross W J.Relaxed Gaussian Belief Propagation[C]∥IEEE International Symposium on Information Theory Proceedings.IEEE,2012:2002-2006
[122] Langseth H,Nielsen T D,Rumí R,et al.Inference in hybrid Bayesian networks[J].Reliability Engineering & System Safety,2009,94(10):1499-1509
[123] Sanner S,Abbasnejad E.Symbolic Variable Elimination forDiscrete and Continuous Graphical Models[C]∥Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence.2012:1954-1960
[124] Langseth H,Nielsen T D,Salmerón A.Parameter estimation and model selection for mixtures of truncated exponentials[J].International Journal of Approximate Reasoning,2010,51(5):485-498
[125] Shenoy P P.A re-definition of mixtures of polynomials for inference in hybrid Bayesian networks[M].Berlin Heidelberg:Springer,2011:98-109
[126] Fernández A,Rumí R,Salmerón A.Answering queries in hy-brid Bayesian networks using importance sampling[J].Decision Support Systems,2012,53(3):580-590
[127] Frogner C,Pfeffer A.Discovering weakly-interacting factors in a complex stochastic process[C]∥Advances in Neural Information Processing Systems.Vancouver,British Columbia,Canada:Curran Associates,2007:481-488
[128] Johansen A M,Doucet A.A note on auxiliary particle filters[J].Statistics & Probability Letters,2008,78(12):1498-1504
[129] Del Moral P,Doucet A,Jasra A.On adaptive resampling strategies for sequential Monte Carlo methods[J].Bernoulli,2012,18(1):252-278
[130] Lopes H F,Polson N G,Carvalho C M.Bayesian statistics with a smile:A resampling-sampling perspective[J].Brazilian Journal of Probability and Statistics,2012,26(4):358-371
[131] Cappé O,Godsill S J,Moulines E.An overview of existingmethods and recent advances in sequential Monte Carlo[J].Proceedings of the IEEE,2007,95(5):899-924
[132] Li T,Sattar T P,Sun S.Deterministic resampling:unbiased sampling to avoid sample impoverishment in particle filters[J].Signal Processing,2012,92(7):1637-1645
[133] Gogate V,Dechter R.Approximate Inference Algorithms for Hybrid Bayesian Networks with Discrete Constraints[C]∥Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence.Edinburgh,Scotland:AUSI Press,2005:209-216
[134] Ranganath R,Gerrish S,Blei D.Black Box Variational Inference[C]∥Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics.Reykjavik,Iceland:JMLR.org,2014:814-822
[135] Wang C,Blei D M.Variational inference in nonconjugate mo-dels[J].The Journal of Machine Learning Research,2013,14(1):1005-1031
[136] Kumar K S,Bach F.Maximizing submodular functions usingprobabilistic graphical models[J].arXiv preprint arXiv:1309.2593,2013
[137] Van den Broeck G,Davis J.Conditioning in first-order know-ledge compilation and lifted probabilistic inference[C]∥Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence.Toronto,Ontario,Canada:AAAI Press,2012:1-7
[138] Van den Broeck G.Lifted Inference and Learning in Statistical Relational Models[D].Leuven,Belgium:Catholic University of Leuven,2013
[139] Van den Broeck G,Darwiche A.On the complexity and approximation of binary evidence in lifted inference[C]∥ Proceedings of the Advances in Neural Information Processing Systems.Lake Tahoe,Nevada,United States,2013:2868-2876
[140] Singla P,Nath A,Domingos P.Approximate lifted belief propagation[C]∥Proceedings of the AAAI Workshop on Statistical Relational Artificial Intelligence.Atlanta,USA,2010:92-97
[141] Gordon A D,Henzinger T A,Nori A V,et al.Probabilistic programming[C]∥Proceedings of the International Conference on Software Engineering.Hyderabad,India:ACM,2014:57-70
[142] Stuhlmüller A,Goodman N D.Reasoning about reasoning bynested conditioning:Modeling theory of mind with probabilistic programs[J].Cognitive Systems Research,2014,28:80-99
[143] Yang L,Hanrahan P,Goodman N D.Generating Efficient MCMC Kernels from Probabilistic Programs[C]∥Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics.Reykjavik,Iceland:JMLR.org,2014:1068-1076
[144] Wang W Y,Mazaitis K,Lao N.Efficient Inference and Lear-ning in a Large Knowledge Base:Reasoning with Extracted Information using a Locally Groundable First-Order Probabilistic Logic[J].arXiv preprint arXiv:1404.3301,2014
[145] Moldovan B,Thon I,Davis J,et al.MCMC estimation of condi-tional probabilities in probabilistic programming languages[C]∥Proceedings of the 12th European conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty.Springer-Verlag,2013:436-448
[146] Nampally A,Ramakrishnan C R.Adaptive MCMC-Based Infer-ence in Probabilistic Logic Programs[J].arXiv preprint arXiv:1403.6036,2014
[147] Fierens D,Van den Broeck G,Renkens J,et al.Inference and learning in probabilistic logic programs using weighted boolean formulas[J].arxiv preprint arxiv:1304.6810,3,2013:1-44
[148] Sheldon D,Sun T,Kumar A,et al.Approximate Inference inCollective Graphical Models[C]∥Proceedings of the 30th International Conference on Machine Learning.Atlanta,GA,USA:JMLR.org,2013:1004-1012
[149] Praveen P,Frhlich H.Boosting Probabilistic Graphical Model Inference by Incorporating Prior Knowledge from Multiple Sources[J].PLoS ONE,2012,8(6):e67410
[150] Mohan K,Pearl J,Tian J.Graphical models for inference with missing data[C]∥Proceedings of the Advances in Neural Information Processing Systems.Lake Tahoe,Nevada,United States,2013:1277-1285
[151] Xiang R,Neville J.Collective inference for network data withcopula latent markov networks[C]∥Proceedings of the sixth ACM international conference on Web search and data mining.Rome,Italy:ACM,2013:647-656
[152] Kiselev I,Poupart P.Policy optimization by marginal-map pro-babilistic inference in generative models[C]∥Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems.International Foundation for Autonomous Agents and Multiagent Systems.Paris,France:Springer,2014:1611-1612
[153] Kappes J H,Andres B,Hamprecht F A,et al.A comparative study of modern inference techniques for discrete energy minimization problems[C]∥Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Portland,USA:IEEE,2013:1328-1335
[154] Badrinarayanan V,Budvytis I,Cipolla R.Semi-supervised videosegmentation using tree structured graphical models[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(11):2751-2764
[155] Badrinarayanan V,Budvytis I,Cipolla R.Mixture of TreesProbabilistic Graphical Model for Video Segmentation[J].International Journal of Computer Vision,2013,110(1):1-16
[156] Hoffman M D,Blei D M,Wang C,et al.Stochastic variational inference[J].The Journal of Machine Learning Research,2013,14(1):1303-1347
[157] Zeng J,Cheung W K,Liu J.Learning Topic Models by Belief Propagation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(5):1121-1134
[158] Shpitser I,Evans R J,Richardson T S,et al.Sparse Nested Markov Models with Log-linear Parameters[J].arXiv preprint arXiv:1309.6863,2013
[159] Kingma D P.Fast Gradient-Based Inference with Continuous Latent Variable Models in Auxiliary Form[J].arXiv preprint arXiv:1306.0733,2013
[160] Mezuman E,Tarlow D,Globerson A,et al.Tighter linear program relaxations for high order graphical models[J].arXiv preprint arXiv:1309.6848,2013
[161] Dworkin L,Kearns M,Xia L.Efficient Inference for Complex Queries on Complex Distributions[C]∥Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics.Reykjavik,Iceland:JMLR.org,2014:211-219
[162] Scutari M.Bayesian Network Constraint-Based StructureLearning Algorithms:Parallel and Optimised Implementations in the bnlearn R Package[J].arXiv preprint arXiv:1406.7648,2014
[163] Tristan J B,Huang D,Tassarotti J.Augur:a Modeling Lan-guage for Data-Parallel Probabilistic Inference[J].arXiv preprint arXiv:1312.3613,2013
[164] Kollar T,Tellex S,Walter M R.Approaching the SymbolGrounding Problem with Probabilistic Graphical Models[J].AI MAGAZINE,2011,32(4):64-76
[165] 石焕南.受控理论与解析不等式[M].哈尔滨:哈尔滨工业大学出版社,2012
[166] Werner T.High-arity interactions,polyhedral relaxations,and cutting plane algorithm for soft constraint optimisation (MAP-MRF)[C]∥IEEE Conference on Computer Vision and Pattern Recognition,2008(CVPR 2008).IEEE,2008:1-8
[167] Aoyama K,Kohsaka F.Fixed point theorem for a-nonexpansive mappings in banach spaces[J].Nonlinear Analysis,2011,74:4387-4391
[168] Kien B T,Wong M M,Wong N C,et al.Solution existence of variational inequalities with pseudo-monotone operators in the sense of Brbzis[J].Optimal Theory Application,2009,140:249-263
[169] Genest C,Rémillard B.Test of independence and randomnessbased on the empirical copula process[J].Test,2004,13(2):335-369
[170] 张恭庆.临界点理论及其应用[M].上海:上海科学技术出版社,1986
[171] Chen P N,Alajaji F.A Generalized Poor-Verdú Error Bound for Multihypothesis Testing[J].IEEE Transactions on Information Theory,2012,58(1):311-316

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed