UW-EE SSLI-LAB Graphical/Kernel Reading Group (GRG)

This quarter, we'll continue to cover papers on a variety of topics ranging from graph theory, convexity theory, approximate inference, Kernal machines, combinatorial optimization, and recent papers from this years UAI/NIPS/ICML.

The group is part of SSLI-Lab. The Signal, Speech, and Language Interpolation (SSLI) laboratory the University of Washington, department of Electrical Engineering involves research related to all methods of working with time signals, in particular speech and language, but other forms of such signals as well.

To receive announcements for this group, send mail to bilmes AT ee D.O.T washington D.O.T edu.

If you would like to lead a discussion (and I encourage you to volunteer), please email me. While the list of papers below will give you something to choose from, you are encouraged to suggest other relevant papers in this area.

Winter 2007: We meet every week in Sieg-424, Wednesdays from 3:00pm-5:00pm.

Topic	Link	Date/Time	Location	Discussion leader	Notes
The Matroid Matching Problem, by L. Lovasz	link	Wed, Feb 7th, 2007, 3:00-5:00	Sieg-424	Bilmes	-
Discriminative Learning via Semidefinite Probabilities Koby Crammer, Amir Globerson, UAI-2006	link	Wed, Feb 14th, 2007, 3:00-5:00	Sieg-424	Kevin Duh	We will finish the Lovasz paper from last week, and get started on the discriminative paper. See slides.
A New Approach to the Maximum-Flow Problem	link	Wed, Feb 21st, 2007, 3:00-5:00	Sieg-424	Andrew Guillory	Finish last week's discriminative paper and start on the goldberg/tarjan paper. See slides.
A New Approach to the Maximum-Flow Problem	link	Wed, Feb 28st, 2007, 3:00-5:00	Sieg-424	Andrew Guillory	Finish proofs from last week's paper on max flow. See slides.
TBD, but will be kernel day.	-	Wed, March 7th, 2007, 3:00-5:00	Sieg-424	Mark Hasagawa-Johnson	TBD, but it will be a kernel paper.

Discussions, Winter 2006

Discussions, Fall 2004

Discussions, Spring 2004

See list of of past discussion topics from previous quarters.

Partial (and growing) Lists of Suggested Papers for Autumn, 2003

1. T. Jaakola and M. Jordan. Computing upper and lower bound on likelihoods in intractable networks. In Proceedings of the Twelfh Annual Conference on Uncertainty in Artificial Intelligence (UAI'96), pages 340-348, 1996. link
2. An Introduction to Variational Methods for Graphical Models, M.I. Jordan and Z. Ghahramani and T.S. Jaakkola and L.K. Saul, Learning in Graphical Models, M.I. Jordan, Kluwer Academic Publishers, 1998 link
3. T. S Jaakkola and M. Jordan. Variational probabilistic inference and the QMR--DT network. Journal of Artificial Intelligence Research, 10:291--322, 1999.
4. J.S. Yedidia, W.T. Freeman, and Y. Weiss. Understanding belief propagation adn its generalizations. In Distinguished Lecture Track, IJCAI, 2001. link
5. W. Wiegerinck. Variational approximations between mean field theory and the junction tree algorithm. In UAI-2000. link
6. T. El-Hay and N. Friemdan, Incorporating expressive graphical models in variational approximations: Chain-graphs and hidden variables. In UAI, 2001. link
7. C. Bishop, D. Spiegelhalter, and J. Winn. Vibes: A variational inference engine for Bayesian networks. In NIPS, 2002.
8. J. S. Yedidia. An idiosyncratic journey beyond mean field theory, in Advanced Mean Field Methods, Theory and Practice, eds. Manfred Opper andDavid Saad, MIT Press, June 2001. link
9. A generalized mean field algorithm for variational inference in exponential families. E.P. Xing, M.I. Jordan, and S. Russell, Uncertainty in Artificial Intelligence, 2003. (UAI2003) link

1. A General Algorithm for Approximate Inference and Its Application to Hybrid Bayes Nets (1999), Koller, Lerner, Angelov link
2. Introduction to Monte Carlo Methods, D.J.C. MacKay, Learning in Graphical Models, M.I. Jordan, Kluwer Academic Publishers, 1998

1. R. J. McEliece, D. J. MacKay and J. F. Cheng. Turbo decoding as an instance of Pearl's belief propagation algorithm, IEEE Journal of Selected Areas of Communication, pp. 140--152, Feb, 1998.
2. Tree-based reparameterization for approximate inference on loopy graphs, M. J. Wainwright and T. Jaakkola and A. S. Willsky, NIPS, 2001
3. Y. Weiss and W. Freeman. Correctness of belief propagation in gaussian graphical models of arbitrary topology. In NIPS, volume 12, 1999.
4. K. P. Murphy, Y. Weiss, and M. Jordan. Loopy belief propagation for approximate inference: an empirical study. In Proceedings of Uncertainty in AI, pages 467-475, 1999.
5. J. S. Yedidia, W. T. Freeman and Y. Weiss. Bethe free energies, Kikuchi approximations, and belief propagation algorithms. TR 2001-16, 2001. link
6. Y. Weiss. Correctness of local probability propagation in graphical models with loops. Neural Computation, 2000. link
7. S.M. Aji, G.B. Horn, and R.J. McEliece. On the convergence of iterative decoding on graphs with a single cycle. In Proc. 1998 ISIT, 1998. link

1. Reduction of computational complexity in Bayesian Networks through removal of weak dependencies. In Proc. UAI-94, pages 374-382, 1994 link
2. Maximum Likelihood Bounded Tree-Width Markov Networks, by Nathan Srebro. link (see also here)
3. Learning Markov Networks: Maximum Bounded Tree-Width Graphs, Karger & Srebro link

1. Approximating Bayesian belief networks by arc removal, Robert A. van Engelen, IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(8):916-920, 1997. link
2. F. Jensen and S. Andersen. Approximations in bayesian belief universes for knowledge-based systems. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pages 162--169, 1990.
3. A Survey of Algorithms for Real-Time Bayesian Network Inference , Haipeng Guo, William Hsu (a survey of inference techniques, both exact and approximate) link
4. P. Dagum and M. Luby. Approximating probabilistic inference in belief networks is NP-hard. Artificial Intelligence, 60:141--153, 1993.

1. An efficient algorithm for finding the M most probable configurations in probabilistic expert systems, D. Nilsson, Statistics and Computing. link A similar sequential algorithm for HMMs is described here

Relavant Calls for papers

The following sites list recent and future CFPs in the area of graphical models, Bayesian networks, and inference

1. Uncertanty in Artificial Intelligence (UAI'2004)
2. AI and Statistics (ATSTAT'2003)
3. NIPS'2003

Related links

1. Special issue of IEEE Transactions on Information Theory, codes on graphs, link (available from a UW machine)
2. UW Math seminars
3. Another reading group on approximations in graphical models.
4. NIPS workshop on Propagation Algorithms on Graphs with Cycles link
5. Chris Bartel's contraint reading page.
6. A list of other machine learning reading groups
7. Mukund's list of intereting papers.
8. Our brother reading group, the machine translation reading group here