Graphical Models

18 Mar 2012 14:52

---

A.k.a. causal models, causal graphs, Bayes graphs, Bayes networks, Bayesian networks, Markov networks... (Here "Bayes" is a metonym for "conditional probability". There are perfectly good frequentist interpretations of these models.) I'm sticking latent-variable and path-analysis models in here, too, because they all pretty much work the same way.

It's the causal modeling angle which got me interested in this originally, and which I still think is the most important, but there are many other uses.

Things I want to understand better: frequentist inference procedures. Computational learning theory for graphical models (the paper by Janzing and Herrmann is good). How to treat directed cyclic graphs? How to treat dynamical systems and time series?

Not even a conjecture. Back in the 1960s, Chow and Liu (reference below) gave a polynomial algorithm for finding the best approximation to a global joint probability distribution using only pairwise interactions among the variables, i.e., the one which minimized the Kullback-Leibler divergence between the true and the approximating distribution. I have read that extending this to even three-way interactions is NP, though I don't know if it's NP-complete. (1) How is the intractability result established? (2) Is this the same as the computational phase transition one finds in going from 2-SAT to 3-SAT, where the critical point is at two-point-something SAT? (Presumably the answer to (1) would shed some light on this.) (3) Even if not, is there an analogous phase transition, perhaps in a different universality class? (Update in 2009, several years later: Bento and Montanari, below, sounds relevant, but I haven't read it yet.)

See also: Machine Learning; Markov Models; Spatial Statistics and Spatial Stochastic Processes; Stochastic Processes

Recommended, more general:
• Michael Irwin Jordan (ed.), Learning in Graphical Models
• Jordan and Sejnowski (eds.), Graphical Models [Nice collection of papers from Neural Computation]
• Steffen Lauritzen, Graphical Models [A fairly abstract, but quite elegant, probabilistic/mathematical-statistical treatment.]
• Judea Pearl, Probabilistic Reasoning in Intelligent Systems [Though there are some ideas here about AI which seem unhelpful]

Recommended, more specialized:
• Gavin Brown, Adam Pocock, Ming-Jie Zhao, Mikel Luján, "Conditional Likelihood Maximisation: A Unifying Framework for Information Theoretic Feature Selection", Journal of Machine Learning Research 13 (2012): 27--66
• C. K. Chow and C. N. Liu, "Approximating Discrete Probability Distributions with Dependence Trees", IEEE Transactions on Information Theory 14 (1968): 462--467 [An old but very nice result on how to get the optimal approximation to a global probability distribution using only pairwise interactions among the variables]
• Finale Doshe-Velez, David Wingate, Joshua Tenenbaum and Nicholas Roy, "Infinite Dynamic Bayesian Networks", ICML 2011 [PDF]
• Ghahramani, "Learning Dynamic Bayesian Networks," in Giles and Gori (eds.), Adaptive Processing of Sequences and Data Structures
• Ghahramani and Jordan, "Factorial Hidden Markov Models," Machine Learning 29 (1997): 245--273
• Dominik Janzing and Daniel J. L. Herrmann, "Reliable and Efficient Inference of Bayesian Networks from Sparse Data by Statistical Learning Theory", cs.LG/0309015
• Han Liu, John Lafferty and Larry Wasserman, "The Nonparanormal: Semiparametric Estimation of High Dimensional Undirected Graphs", Journal of Machine Learning Research 10 (2009): 2295--2328 = arxiv:0903.0649
• John C. Loehlin, Latent Variable Models: An Introduction to Factor, Path, and Structural Analysis [An intro. to old-school linear latent-variable models, especially of the sort used by psychologists. Good in its own domain, but does not make enough contact with modern graphical models.]
• Eric Mjolsness, "Stochastic Process Semantics for Dynamical Grammar Syntax: An Overview", cs.AI/0511073
• Christopher J. Quinn, Todd P. Coleman, Negar Kiyavash, "Causal Dependence Tree Approximations of Joint Distributions for Multiple Random Processes", arxiv:1101.5108
• Pawel Wocjan, Dominik Janzing, and Thomas Beth, "Required sample size for learning sparse Bayesian networks with many variables," cs.LG/0204052

To read:
• Edoardo M. Airoldi, "Getting started in probabilistic graphical models", arxiv:0706.2040 [Tutorial aimed at biologists]
• Animashree Anandkumar, Kamalika Chaudhuri, Daniel Hsu, Sham M. Kakade, Le Song, Tong Zhang, "Spectral Methods for Learning Multivariate Latent Tree Structure", arxiv:1107.1283 [This sounds very much like Spearman's "tetrad equations" from 100 years ago!]
• Animashree Anandkumar, Vincent Y.F. Tan, Alan. S. Willsky, "High-Dimensional Gaussian Graphical Model Selection: Tractable Graph Families", arxiv:1107.1270
• Erik Aurell, Magnus Ekeberg, "Inverse Ising inference using all the data", arxiv:1107.3536 ["We show that a method based on logistic regression, using all the data, solves the inverse Ising problem far better than mean-field calculations relying only on sample pairwise correlation functions, while still computationally feasible for numbers of nodes in the range of hundreds. The largest improvement in reconstruction occurs for strong interactions..."]
• Francis R. Bach and Michael I. Jordan, "Learning Graphical Models for Stationary Time Series", UCB Statistics Tech. Rep. 650
• Onureena Banerjee, Laurent El Ghaoui, Alexandre d'Aspremont, "Model Selection Through Sparse Maximum Likelihood Estimation", arxiv:0707.0704
• Jose Bento, Morteza Ibrahimi and Andrea Montanari, "Learning Networks of Stochastic Differential Equations", NIPS 23 (2010) [PDF]
• Jose Bento, Andrea Montanari, "Which graphical models are difficult to learn?", arxiv:0910.5761
• Danny Bickson, Carlos Guestrin, "Linear Characteristic Graphical Models: Representation, Inference and Applications", arxiv:1008.5325
• David Brillinger, "Remarks Concerning Graphical Models for Time Series and Point Processes," Revista de Econometria 16 (1996): 1--23 [PS]
• Clive G. Bowsher, "Stochastic kinetic models: Dynamic independence, modularity and graphs", Annals of Statistics 38 (2010): 2242--2281
• Matthias Brocheler and Lise Getoor, "Computing Marginal Distributions over Continuous Markov Networks for Statistical Relational Learning", NIPS 23 (2010) [PDF]
• Venkat Chandrasekaran, Pablo A. Parrilo, Alan S. Willsky, "Latent Variable Graphical Model Selection via Convex Optimization", arxiv:1008.1290
• Michael Chertkov and Vladimir Y. Chernyak
  • "Loop calculus in statistical physics and information science", Physical Review E 73 (2006): 065102 = cond-mat/0601487
  • "Loop series for discrete statistical models on graphs", cond-mat/0603189
• David Maxwell Chickering, "Optimal Structure Identification With Greedy Search," Journal of Machine Learning Research 3 (2002): 507--554
• Diego Colombo, Marloes H. Maathuis, Markus Kalisch, Thomas S. Richardson, "Learning high-dimensional directed acyclic graphs with latent and selection variables", arxiv:1104.5617
• Robert G. Cowell, A. Philip Dawid, Steffen L. Lauritzen and David J. Spiegelhalter, Probabilistic Networks and Expert Systems
• David Cox and Nanny Warmuth, Multivariate Dependcencies: Models, Analysis, and Interpretation
• Mihai Cucuringu, Jesus Puente, David Shue, "Model Selection in Undirected Graphical Models with the Elastic Net", arxiv:1111.0559
• Rainer Dahlhaus, "Graphical interaction models for multivariate time series," Metrika 51 (2000): 157--172
• Gabriel C. G. de Abreu, Rodrigo Labouriau, David Edwards, "High-dimensional Graphical Model Search with gRapHD R Package", Journal of Statistical Software 37 (2010), arxiv:0909.1234
• Luis M. de Campos, "A Scoring Function for Learning Bayesian Networks based on Mutual Information and Conditional Independence Tests", Journal of Machine Learning Research 7 (2006): 2149--2187 [Sounds damn cool]
• Amir Dembo and Andrea Montanari, "Gibbs Measures and Phase Transitions on Sparse Random Graphs", arxiv:0910.5460
• Amir Dembo, Andrea Montanari, Nike Sun, "Factor models on locally tree-like graphs", arxiv:1110.4821
• Pedro Domingos and Daniel Lowd, Markov Logic: An Interface Layer for Artificial Intelligence
• Vanessa Didelez, "Graphical models for marked point processes based on local independence", arxiv:0710.5874
• Mathias Drton, Rina Foygel, and Seth Sullivant, "Global identifiability of linear structural equation models", Annals of Statistics 39 (2011): 865--886
• Michael Eichler
  • "Graphical modelling of multivariate time series", math.ST/0610654
  • "A note on global Markov properties for mixed graphs", arxiv:1107.3036
• Seif Eldawlatly, Yang Zhou, Rong Jin and Karim G. Oweiss, "On the Use of Dynamic Bayesian Networks in Reconstructing Functional Neuronal Networks from Spike Train Ensembles", Neural Computation 22 (2010): 158--189
• Gal Elidan, Iftach Nachman and Nir Friedman, "'Ideal Parent' Structure Learning for Continuous Variable Bayesian Networks", Journal of Machine Learning Research 8 (2007): 1799--1833
• Sergi Elizalde and Kevin Woods, "Bounds on the number of inference functions of a graphical model", math.CO/0610233
• Juan Ferrándiz, Enrique F. Castillo and Pilar Sanmartin, "Temporal aggregation in chain graph models", Journal of Statistical Planning and Inference 133 (2005): 69--93
• G. David Forney, Jr., Pascal O. Vontobel, "Partition Functions of Normal Factor Graphs", arxiv:1102.0316
• Frey, Graphical Models in Machine Learning and Data Communication
• Roland Fried and Vanessa Didelez, "Latent variable analysis and partial correlation graphs for multivariate time series", Statistics and Probability Letters 73 (2005): 287--296
• Cyril Furtlehner, Jean-Marc Lasgouttes, Arnaud De La Fortelle, "Belief Propagation and Bethe approximation for Traffic Prediction", physics/0703159
• Dan Geiger, David Heckerman, Henry King, and Christopher Meek, "Stratified exponential families: Graphical models and model selection", Annals of Statistics 29 (2001): 505--529
• Christophe Giraud, "Estimation of Gaussian graphs by model selection", arxiv:0710.2044
• Vibhav Gogate, William Austin Webb, and Pedro Domingos, "Learning Efficient Markov Networks", NIPS 23 (2010) [PDF]
• Green, Hjort and Richardson (eds.), Highly Structured Stochastic Systems
• Vikas Hamine and Paul Helman, "Learning Optimal Augmented Bayes Networks", cs.LG/0509055
• Patrick L. Harrington, Jr., and Alfred O. Hero III, "Spatio-Temporal Graphical Model Selection", arxiv:1004.2304
• Raymond Hemmecke, Silvia Lindner, Milan Studeny, "Learning restricted Bayesian network structures", arxiv:1011.6664
• Holger Höfling and Robert Tibshirani, "Estimation of Sparse Binary Pairwise Markov Networks using Pseudo-likelihoods", Journal of Machine Learning Research 10 (2009): 883--906
• Shiro Ikeda, Toshiyuki Tanaka and Shun-ichi Amari, "Stochastic Reasoning, Free Energy, and Information Geometry", Neural Computation 16 (2004): 1779--1810
• Manfred Jaeger & co., Primula [Java implementation of a modeling language for relational Bayesian networks; released under GPL]
• Ali Jalali, Chris Johnson, Pradeep Ravikumar, "On Learning Discrete Graphical Models Using Greedy Methods", arxiv:1107.3258
• Kohler and Friedman, Graphical Models
• Mladen Kolar, Eric P. Xing, "Estimating Networks With Jumps", arxiv:1012.3795
• Nicole Kraemer, Juliane Schaefer, Anne-Laure Boulesteix, "Regularized estimation of large-scale gene association networks using graphical Gaussian models", arxiv:0905.0603
• John Lafferty, Han Liu, Larry Wasserman, "Sparse Nonparametric Graphical Models", arxiv:1201.0794
• Sophie Lèbre, "Inferring dynamic genetic networks with low order independencies", arxiv:0704.2551
• Shai Litvak and Shimon Ullman, "Cortical Circuitry Implementing Graphical Models", Neural Computation 21 (2009): 3010--3056 [or rather, models of cortical circuitry implementing graphical models]
• Han Liu, Xi Chen, John Lafferty, Larry Wasserman, "Graph-Valued Regression", arxiv:1006.3972
• Han Liu, John Lafferty and Larry Wasserman, "Tree Density Estimation", arxiv:1001.1557
• Han Liu, Kathryn Roeder, Larry Wasserman, "Stability Approach to Regularization Selection (StARS) for High Dimensional Graphical Models", arxiv:1006.3316 == NIPS 23 (2010)
• Han Liu, Min Xu, Haijie Gu, Anupam Gupta, John Lafferty, Larry Wasserman, "Forest Density Estimation", Journal of Machine Learning Research 12 (2011): 907--951
• Stephen Luttrell, "Adaptive Cluster Expansion (ACE): A Hierarchical Bayesian Network", cs.NE/0410020
• Giovanni M. Marchetti, Nanny Wermuth, "Matrix representations and independencies in directed acyclic graphs", arxiv:0904.0333
• Lilyana Mihalkova, Lise Getoor, "Lifted Graphical Models: A Survey", arxiv:1107.4966
• Eric Mjolsness, "Labeled graph notations for graphical models", UCI School of Information and Computer science Technical Report 04-03 [PDF]
• Andrea Montanari, "Graphical Models Concepts in Compressed Sensing", arxiv:1011.4328
• Jennifer Neville and David Jensen, "Relational Dependency Networks", Journal of Machine Learning Research 8 (2007): 653--692
• Lior Pachter and Bernd Sturmfels
  • "Tropical Geometry of Statistical Models", q-bio.QM/0311009
  • "Parametric Inference for Biological Sequence Analysis", q-bio.GN/0401033
• Alessandro Pelizzola, "Cluster variation method in statistical physics and probabilistic graphical models", Journal of Physics A: Mathematical and General 38 (2005): R309--R339 = cond-mat/0508216
• Jose M. Pena, "Reading Dependencies from Covariance Graphs", arxiv:1010.4504
• Tapani Raiko, Harri Valpola, Markus Harva and Juha Karhunen, "Building Blocks for Variational Bayesian Learning of Latent Variable Models", Journal of Machine Learning Research 8 (2007): 155--201
• Johannes Rauh, Nihat Ay, "Robustness and Conditional Independence Ideals", arxiv:1110.1338
• Pradeep Ravikumar, Martin J. Wainwright, and John D. Lafferty, "High-dimensional Ising model selection using $\ell_1$-regularized logistic regression", Annals of Statistics 38 (2010): 1287--1319, arxiv:0804.4202, also arxiv:1010.0311
• Marco Reale, A Graphical Modelling Approach to Time Series, Ph.D. thesis, Lancaster University, 1998 [Reale's website]
• Marco Reale and Granville Tunnicliffe Wilson
  • "Identification of vector AR models with recursive structural errors using conditional independence graphs"
  • "The Sampling Properties of Conditional Independence Graphs for Structural Vector Autoregressions"
• T. Rizzo, B. Wemmenhove, H.J. Kappen, "On Cavity Approximations for Graphical Models", cond-mat/0608312
• Joshua W. Robinson, Alexander J. Hartemink, "Learning Non-Stationary Dynamic Bayesian Networks", Journal of Machine Learning Research 11 (2010): 3647--3680
• Philipp Rütimann and Peter Bühlmann, "High dimensional sparse covariance estimation via directed acyclic graphs", arxiv:0911.2375 = Electronic Journal of Statistics 3 (2009): 1133--1160
• Kayvan Sadeghi, Steffen L. Lauritzen, "Markov Properties for Loopless Mixed Graphs", arxiv:1109.5909
• Federico Schlüter, "A survey on independence-based Markov networks learning", arxiv:1108.2283
• Marco Scutari
  • "Learning Bayesian Networks with the bnlearn Package", arxiv:0908.3817
  • "Measures of Variability for Bayesian Network Graphical Structures", arxiv:1005.4214
• Tomi Silander, Teemu Roos, Petri Myllymaki, "Locally Minimax Optimal Predictive Modeling with Bayesian Networks", Journal of Machine Learning Research Workshop and Conference Proceedings 5 (AISTATS 2009): 504--511
• Milan Studeny, Probabilistic Conditional Independence Structures ["The main topic of the monograph is a non-graphical algebraic method for describing probabilistic CI structures. However, one of the first two chapters in the book recalls and gathers basic mathematical tools for study of probabilistic conditional independence (CI) and the other one is a sketchy overview of recent advanced graphical approaches to the desciption of CI structures. The next four chapters develop the non-graphical method. The last standard chapter is an attempt to apply the method in practice: it is devoted to learning Bayesian nets and it is more mathematical (and 'philosophical') revision of some methods for learning Bayesian networks. The main aim of that chapter is to indicate that an algebraic approach can also be applied in this area."]
• Charles Sutton, Andrew McCallum, "An Introduction to Conditional Random Fields", arxiv:1011.4088
• Charles Sutton, Andrew McCallum and Khashayar Rohanimanesh, "Dynamic Conditional Random Fields: Factorized Probabilistic Models for Labeling and Segmenting Sequence Data", Journal of Machine Learning Research 8 (2007): 693--723
• Vincent Y. F. Tan, Animashree Anandkumar, Lang Tong and Alan S. Willsky, "A Large-Deviation Analysis of the Maximum-Likelihood Learning of Markov Tree Structures", IEEE Transactions on Information Theory 57 (2011): 1714--1735, arxiv:0905.0940 [Large deviations for Chow-Liu trees]
• Vivian Viallon, Onureena Banerjee, Gregoire Rey, Eric Jougla, Joel Coste, "An empirical comparative study of approximate methods for binary graphical models; application to the search of associations among causes of death in French death certificates", arxiv:1004.2287
• Martin J. Wainwright and Michael I. Jordan, "Graphical Models, Exponential Families, and Variational Inference", Foundations and Trends in Machine Learning 1 (2008): 1--305 [PDF reprint via Prof. Jordan]
• Nanny Wermuth, "Probability distributions with summary graph structure", Bernoulli 17 (2011): 845--879, arxiv:1003.3259
• Gui-Bo Ye, Yuanfeng Wang, Yifei Chen, Xiaohui Xie, "Efficient Latent Variable Graphical Model Selection via Split Bregman Method", arxiv:1110.3076
• Jonathan S. Yedidia, William T. Freeman and Yair Weiss, "Understanding Belief Propagation and its Generalizations", Mitsubshi Electric Research Laboratories Tech. Rep. 2001-22
• Marco Zaffalon and Marcus Hutter, "Robust Inference of Trees", cs.LG/0511087
• Shuheng Zhou, John Lafferty, Larry Wasserman, "Time Varying Undirected Graphs", arxiv:0802.2758
• Piotr Zwiernik, "An Asymptotic Behaviour of the Marginal Likelihood for General Markov Models", Journal of Machine Learning Research 12 (2011): 3283--3310 [where "general Markov models" == "binary graphical tree models where all the inner nodes of a tree represent binary hidden variables"]