The Living Thing / Notebooks :

Undirected graphical models

a.k.a Markov random fields, Markov random networks. (other types?)

I would like to know about spatial Poisson random fields, Markov random fields, Bernoulli (or is it Boolean?) random fields, esp for discrete multivariate sequences. Gibbs and Boltzman dist inference.

A smartarse connection to neural networks is in Ranz13.

To learn:

When can you do observational study inference with undirected graphs? Given the powerful and fast tools for this (e.g. the ‘nonparanormal Skeptic’ of LHYL12 etc) it would be good to know if you can leverage them to produce directed causal graphs, or something.

Implementations of MRF methods


Altun, Y., Smola, A. J., & Hofmann, T. (2004) Exponential Families for Conditional Random Fields. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence (pp. 2–9). Arlington, Virginia, United States: AUAI Press
Baddeley, A. J., Lieshout, M. N. M. V., & Møller, J. (1996) Markov Properties of Cluster Processes. Advances in Applied Probability, 28(2), 346–355. DOI.
Baddeley, A. J., & Lieshout, M. N. M. van. (1995) Area-interaction point processes. Annals of the Institute of Statistical Mathematics, 47(4), 601–619. DOI.
Baddeley, A. J., Møller, J., & Waagepetersen, R. (2000) Non- and semi-parametric estimation of interaction in inhomogeneous point patterns. Statistica Neerlandica, 54(3), 329–350. DOI.
Baddeley, A., & Møller, J. (1989) Nearest-Neighbour Markov Point Processes and Random Sets. International Statistical Review / Revue Internationale de Statistique, 57(2), 89–121. DOI.
Bartolucci, F., & Besag, J. (2002) A recursive algorithm for Markov random fields. Biometrika, 89(3), 724–730. DOI.
Besag, J. (1974) Spatial Interaction and the Statistical Analysis of Lattice Systems. Journal of the Royal Statistical Society. Series B (Methodological), 36(2), 192–236.
Besag, J. (1975) Statistical Analysis of Non-Lattice Data. Journal of the Royal Statistical Society. Series D (The Statistician), 24(3), 179–195. DOI.
Besag, J. (1986) On the Statistical Analysis of Dirty Pictures. Journal of the Royal Statistical Society. Series B (Methodological), 48(3), 259–302.
Blake, A., Kohli, P., & Rother, C. (Eds.). (2011) Markov Random Fields for Vision and Image Processing. . Cambridge, Mass: MIT Press
Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011) Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends® in Machine Learning, 3(1), 1–122.
Celeux, G., Forbes, F., & Peyrard, N. (2003) EM procedures using mean field-like approximations for Markov model-based image segmentation. Pattern Recognition, 36(1), 131–144. DOI.
Cevher, V., Duarte, M. F., Hegde, C., & Baraniuk, R. (2009) Sparse Signal Recovery Using Markov Random Fields. In Advances in Neural Information Processing Systems (pp. 257–264). Curran Associates, Inc.
Clifford, P. (1990) Markov random fields in statistics. In G. R. Grimmett & D. J. A. Welsh (Eds.), Disorder in Physical Systems: A Volume in Honour of John Hammersley. Oxford England : New York: Oxford University Press
Crisan, D., & Míguez, J. (2014) Particle-kernel estimation of the filter density in state-space models. Bernoulli, 20(4), 1879–1929. DOI.
Della Pietra, S., Della Pietra, V., & Lafferty, J. (1995) Inducing Features of Random Fields. arXiv:cmp-lg/9506014.
Forbes, F., & Peyrard, N. (2003) Hidden Markov random field model selection criteria based on mean field-like approximations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(9), 1089–1101. DOI.
Fridman, A. (2003) Mixed Markov models. Proceedings of the National Academy of Sciences, 100(14), 8092–8096. DOI.
Friel, N., & Rue, H. (2007) Recursive computing and simulation-free inference for general factorizable models. Biometrika, 94(3), 661–672. DOI.
Geyer, C. J.(1991) Markov chain Monte Carlo maximum likelihood.
Geyer, C. J., & Møller, J. (1994) Simulation procedures and likelihood inference for spatial point processes. Scandinavian Journal of Statistics, 359–373.
Gogate, V., Webb, W., & Domingos, P. (2010) Learning efficient Markov networks. In Advances in Neural Information Processing Systems (pp. 748–756).
Goldberg, D. A.(2013) Higher order Markov random fields for independent sets. arXiv:1301.1762 [math-Ph].
Grenander, U. (1989) Advances in Pattern Theory. The Annals of Statistics, 17(1), 1–30. DOI.
Griffeath, D. (1976) Introduction to Random Fields. In Denumerable Markov Chains (pp. 425–458). Springer New York
Häggström, O., Van Lieshout, M.-C. N., & Møller, J. (1999) Characterization results and Markov chain Monte Carlo algorithms including exact simulation for some spatial point processes. Bernoulli, 5(4), 641–658.
Heckerman, D., Chickering, D. M., Meek, C., Rounthwaite, R., & Kadie, C. (2000) Dependency Networks for Inference, Collaborative Filtering, and Data Visualization. Journal of Machine Learning Research, 1(Oct), 49–75.
Hinton, G. E., Osindero, S., & Bao, K. (2005) Learning causally linked markov random fields. In Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics (pp. 128–135). Citeseer
Jensen, J. L., & Møller, J. (1991) Pseudolikelihood for Exponential Family Models of Spatial Point Processes. The Annals of Applied Probability, 1(3), 445–461.
Jordan, M. I.(1999) Learning in graphical models. . Cambridge, Mass.: MIT Press
Jordan, M. I.(2004) Graphical Models. Statistical Science, 19(1), 140–155.
Jordan, M. I., Ghahramani, Z., Jaakkola, T. S., & Saul, L. K.(1999) An Introduction to Variational Methods for Graphical Models. Machine Learning, 37(2), 183–233. DOI.
Jordan, M. I., & Weiss, Y. (2002a) Graphical models: Probabilistic inference. The Handbook of Brain Theory and Neural Networks, 490–496.
Jordan, M. I., & Weiss, Y. (2002b) Probabilistic inference in graphical models. Handbook of Neural Networks and Brain Theory.
Khoshgnauz, E. (2012) Learning Markov Network Structure using Brownian Distance Covariance. arXiv:1206.6361 [cs, Stat].
Kindermann, R. P., & Snell, J. L.(1980a) On the relation between Markov random fields and social networks. The Journal of Mathematical Sociology, 7(1), 1–13. DOI.
Kindermann, R., & Snell, J. L.(1980b) Markov Random Fields and Their Applications. (Vol. 1). Providence, Rhode Island: American Mathematical Society
Krämer, N., Schäfer, J., & Boulesteix, A.-L. (2009) Regularized estimation of large-scale gene association networks using graphical Gaussian models. BMC Bioinformatics, 10(1), 384. DOI.
Krause, A., & Guestrin, C. (2009) Optimal value of information in graphical models. J. Artif. Int. Res., 35(1), 557–591.
Kschischang, F. R., Frey, B. J., & Loeliger, H.-A. (2001) Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47(2), 498–519. DOI.
Lauritzen, S. L.(1996) Graphical Models. . Clarendon Press
Lauritzen, S. L., & Spiegelhalter, D. J.(1988) Local Computations with Probabilities on Graphical Structures and Their Application to Expert Systems. Journal of the Royal Statistical Society. Series B (Methodological), 50(2), 157–224.
Lavrenko, V., & Pickens, J. (2003a) Music modeling with random fields. In Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval (p. 389). ACM Press DOI.
Lavrenko, V., & Pickens, J. (2003b) Polyphonic music modeling with random fields. In Proceedings of the eleventh ACM international conference on Multimedia (p. 120). ACM Press DOI.
Lee, S.-I., Ganapathi, V., & Koller, D. (2006) Efficient Structure Learning of Markov Networks using $ L_1 $-Regularization. In Advances in neural Information processing systems (pp. 817–824). MIT Press
Liu, H., Han, F., Yuan, M., Lafferty, J., & Wasserman, L. (2012) The Nonparanormal SKEPTIC. arXiv:1206.6488 [cs, Stat].
Liu, H., Lafferty, J., & Wasserman, L. (2009) The Nonparanormal: Semiparametric Estimation of High Dimensional Undirected Graphs. J. Mach. Learn. Res., 10, 2295–2328.
Liu, H., Roeder, K., & Wasserman, L. (2010) Stability Approach to Regularization Selection (StARS) for High Dimensional Graphical Models. In J. D. Lafferty, C. K. I. Williams, J. Shawe-Taylor, R. S. Zemel, & A. Culotta (Eds.), Advances in Neural Information Processing Systems 23 (pp. 1432–1440). Curran Associates, Inc.
Loeliger, H.-A. (2004) An introduction to factor graphs. IEEE Signal Processing Magazine, 21(1), 28–41. DOI.
Maddage, N. C., Li, H., & Kankanhalli, M. S.(2006) Music structure based vector space retrieval. In Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval (p. 67). ACM Press DOI.
Malioutov, D. M., Johnson, J. K., & Willsky, A. S.(2006) Walk-Sums and Belief Propagation in Gaussian Graphical Models. Journal of Machine Learning Research, 7, 2031–2064.
McCallum, A. (2012) Efficiently Inducing Features of Conditional Random Fields. arXiv:1212.2504 [cs, Stat].
Meinshausen, N., & Bühlmann, P. (2006) High-dimensional graphs and variable selection with the lasso. The Annals of Statistics, 34(3), 1436–1462. DOI.
Mihalkova, L., & Mooney, R. J.(2007) Bottom-up learning of Markov logic network structure. In Proceedings of the 24th international conference on Machine learning (pp. 625–632). ACM
Montanari, A. (2011) Lecture Notes for Stat 375 Inference in Graphical Models.
Morgan, J. S., Barjasteh, I., Lampe, C., & Radha, H. (2014) The entropy of attention and popularity in youtube videos. arXiv:1412.1185 [physics].
Murphy, K. P.(2012) Undirected graphical models (Markov random fields). In Machine Learning: A Probabilistic Perspective (1 edition.). Cambridge, MA: The MIT Press
Osokin, A., Vetrov, D., & Kolmogorov, V. (2011) Submodular decomposition framework for inference in associative Markov networks with global constraints. In 2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (pp. 1889–1896). DOI.
Pickens, J. (2004) Harmonic modeling for polyphonic music retrieval. . Citeseer
Pickens, J., & Iliopoulos, C. S.(2005) Markov Random Fields and Maximum Entropy Modeling for Music Information Retrieval. In ISMIR (pp. 207–214). Citeseer
Pollard, D. (2004, February 15) Hammersley-Clifford theorem for Markov random fields.
Rabbat, M. G., Figueiredo, M., & Nowak, R. (2006) Inferring network structure from co-occurrences. In Advances in Neural Information Processing Systems (pp. 1105–1112). MIT Press
Ranzato, M. (2013) Modeling natural images using gated MRFs. IEEE Trans. Pattern Anal. Machine Intell., 35(9), 2206–2222. DOI.
Ravikumar, P., Wainwright, M. J., & Lafferty, J. D.(2010) High-dimensional Ising model selection using ℓ1-regularized logistic regression. The Annals of Statistics, 38(3), 1287–1319. DOI.
Reeves, R., & Pettitt, A. N.(2004) Efficient recursions for general factorisable models. Biometrika, 91(3), 751–757. DOI.
Richardson, M., & Domingos, P. (2006) Markov logic networks. Machine Learning, 62(1-2), 107–136.
Ripley, B. D., & Kelly, F. P.(1977) Markov Point Processes. Journal of the London Mathematical Society, s2-15(1), 188–192. DOI.
Schmidt, M. W., & Murphy, K. P.(2010) Convex structure learning in log-linear models: Beyond pairwise potentials. In International Conference on Artificial Intelligence and Statistics (pp. 709–716).
Studený, M. (1997) A recovery algorithm for chain graphs. International Journal of Approximate Reasoning, 17(2–3), 265–293. DOI.
Sutton, C., & McCallum, A. (2010) An Introduction to Conditional Random Fields. arXiv:1011.4088.
Tansey, W., Padilla, O. H. M., Suggala, A. S., & Ravikumar, P. (2015) Vector-Space Markov Random Fields via Exponential Families. (pp. 684–692). Presented at the Proceedings of The 32nd International Conference on Machine Learning
Vetrov, D., & Osokin, A. (2011) Graph Preserving Label Decomposition in Discrete MRFs with Selfish Potentials. In NIPS Workshop on Discrete Optimization in Machine learning (DISCML NIPS).
Visweswaran, S., & Cooper, G. F.(2014) Counting Markov Blanket Structures. arXiv:1407.2483 [cs, Stat].
Wainwright, M. J., & Jordan, M. I.(2008a) Graphical models, exponential families, and variational inference. Foundations and Trends® in Machine Learning, 1(1-2), 1–305. DOI.
Wainwright, M. J., & Jordan, M. I.(2008b) Graphical Models, Exponential Families, and Variational Inference. Found. Trends Mach. Learn., 1(1-2), 1–305. DOI.
Wainwright, M., & Jordan, M. (2005) A variational principle for graphical models. In New Directions in Statistical Signal Processing (Vol. 155). MIT Press
Wang, C., Komodakis, N., & Paragios, N. (2013) Markov Random Field modeling, inference & learning in computer vision & image understanding: A survey. Computer Vision and Image Understanding, 117(11), 1610–1627. DOI.
Wasserman, L., Kolar, M., & Rinaldo, A. (2013) Estimating Undirected Graphs Under Weak Assumptions. arXiv:1309.6933 [cs, Math, Stat].
Wu, R., Srikant, R., & Ni, J. (2012) Learning graph structures in discrete Markov random fields. In INFOCOM Workshops (pp. 214–219).
Wu, R., Srikant, R., & Ni, J. (2013) Learning Loosely Connected Markov Random Fields. Stochastic Systems, 3(2), 362–404. DOI.
Yedidia, J. S., Freeman, W. T., & Weiss, Y. (2003) Understanding Belief Propagation and Its Generalizations. In G. Lakemeyer & B. Nebel (Eds.), Exploring Artificial Intelligence in the New Millennium (pp. 239–236). Morgan Kaufmann Publishers
Yedidia, J. S., Freeman, W. T., & Weiss, Y. (2005) Constructing free-energy approximations and generalized belief propagation algorithms. IEEE Transactions on Information Theory, 51(7), 2282–2312. DOI.
Zhao, T., Liu, H., Roeder, K., Lafferty, J., & Wasserman, L. (2012) The Huge Package for High-dimensional Undirected Graph Estimation in R. J. Mach. Learn. Res., 13, 1059–1062.