CSE 254: Papers

A useful reference for the basics of inference is Appendix B of Kevin Murphy's thesis.

[1] Quadratic assignment problems (Oct)

1.1 Yuri Boykov, Olga Veksler and Ramin Zabih.
Fast Approximate Energy Minimization via Graph Cuts.
IEEE Transactions on PAMI, vol. 23, no. 11, pp. 1222-1239.

1.2 Vladimir Kolmogorov and Ramin Zabih.
What Energy Functions can be Minimized via Graph Cuts?
IEEE Transactions on Pattern Analysis and Machine Intelligence, February 2004.

1.3 J. Kleinberg and E. Tardos.
Approximation algorithms for classification problems with pairwise relationships.
40th IEEE Symposium on Foundations of Computer Science, 1999.

1.4 N. Bansal, A. Blum, and S. Chawla.
Correlation Clustering.
Machine Learning, 56(1-3): 89-113, 2004.

1.5 M. Charikar, V. Guruswami, and A. Wirth.
Clustering with qualitative information.
44th Annual IEEE Symposium on Foundations of Computer Science, 2003.

[2] Variational methods (Oct)

2.1 M.I. Jordan, Z. Ghahramani, T.S. Jaakkola, and L.K. Saul.
An introduction to variational methods for graphical models
Machine Learning 37:183-233, 1999.

2.2 Z. Ghahramani and M.J. Beal.
Graphical models and variational methods.
In Saad & Opper (eds) Advanced Mean Field Method---Theory and Practice. MIT Press, 2000.

2.3 M.J. Kearns and L.K. Saul.
Inference in Multilayer Networks via Large Deviation Bounds.
Advances in Neural Information Processing Systems, 1999.
See also the following paper by the same authors:
Large Deviation Methods for Approximate Probabilistic Inference, with Rates of Convergence.
Uncertainty in Artificial Intelligence, 1998.

[3] Belief propagation (Oct)

3.1 Kevin Murphy, Yair Weiss, and Michael Jordan.
Loopy-belief Propagation for Approximate Inference: An Empirical Study
Uncertainty in AI, 1999.
Pedro Felzenszwalb and Daniel Huttenlocher.
Efficient Belief Propagation for Early Vision.
IEEE Conference on Computer Vision and Pattern Recognition, 2004.

3.2 Tom Minka.
Expectation Propagation for approximate Bayesian inference.
Uncertainty in AI, 2001.
also: The Expectation Propagation energy function and minimization schemes. Note, 2001.
and: list of references on EP.

3.3 J.S. Yedidia, W.T. Freeman, and Y. Weiss.
Understanding Belief Propagation and Its Generalizations.
Exploring Artificial Intelligence in the New Millennium, Chap. 8, pp. 239-236, January 2003 (Science & Technology Books).

[4] Sampling techniques (Nov)

4.1 D. Geman and S. Geman.
Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images.
IEEE-PAMI, 6, 1984, 721-741.

4.2 E. Sudderth, A. Ihler, W. Freeman, and A. Willsky.
Nonparametric Belief Propagation
Conference on Computer Vision and Pattern Recognition, June 2003.

[5] Various general methods (Nov)

5.1 M.J. Wainwright, T. Jaakkola and A.S. Willsky.
Tree-based reparameterization framework for analysis of sum-product and related algorithms.
IEEE Transactions on Information Theory, 45(9): pages 1120--1146.

5.2 M.J. Wainwright, T. Jaakkola and A.S. Willsky.
Tree consistency and bounds on the performance of the max-product algorithm and its generalizations.
Statistics and Computing, April 2004, Vol. 14, 143--166.

5.3 M.J. Wainwright and M.I. Jordan.
A variational principle for graphical models.
New Directions in Statistical Signal Processing: From Systems to Brain. Cambridge, MA: MIT Press, 2005.

5.4 M.J. Wainwright, T.S. Jaakkola and A.S. Willsky.
MAP estimation via agreement on (hyper)trees: Message-passing and linear-programming approaches.
To appear in IEEE Transactions on Information Theory, November 2005.

5.5 V.N. Kolmogorov and M.J. Wainwright.
On optimality of tree-reweighted max-product message-passing.
Uncertainty in Artificial Intelligence, July 2005.