JT

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

A weekly informal meeting of discussions of papers regarding graphical models and kernel methods, and their relatedness to statistics, machine learning, speech, langauge, and other time-series processing. We review papers from the machine learning (such as uncertainty in Artificial Intelligence, UAI, and Neural information processing systems, NIPS) and other relevant sources.

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.


Discussions, Winter 2007

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

Winter 2006: We meet every week in Sieg 424, Tuesdays from 4:30pm-6:30pm.

Topic Link Date/Time Location Discussion leader Notes
Exact Genetic linkage computatiosn for general pedigrees, by M. Fishelson and D. Geiger, 2002 (bioinformatics). link Tue, Jan 17th, 2006, 4:30-6:30 Sieg-424 Bilmes -
No Meeting - Tue, Jan 24th, 2006, 4:30-6:30 Sieg-424 - -
Optimizing Exact Genetic Linkage Computations by M. Fishelson and D. Geiger, 2004 (Journal of Comp. Bio). link Tue, Jan 31th, 2006, 4:30-6:30 Sieg-424 Bilmes -
Wolpert, D.H., "Information theory- the bridge connecting bounded rational game theory and statistical physics", in Complex Engineering Systems, D. Braha and Y. Bar-Yam(Ed.'s), Perseus books, 2004. main link (but also see here and here) Tue, Feb 7th, 2006, 4:30-6:30 Sieg-424 Asela Gunawardana -
Structured Region Graphs, by Welling, Minka, and Teh, from UAI05. link (also see here and here) Tue, Feb 14th, 2006, 4:30-6:30 Sieg-424 Chris Bartels -
Halpern & Pucella's "Evidence with uncertain likelihoods" from UAI05. link Tue, Feb 21th, 2006, 4:30-6:30 Sieg-424 Susan Shortreed -
No Meeting - Tue, Feb 28th, 2006, 4:30-6:30 Sieg-424 - -
Case Factor Diagrams by McAllester, Collins and Pereira, UAI04 link Tue, March 7th, 2006, 4:30-6:30 Sieg-424 Kevin Duh -


Next up: Amar, Patrick,

Discussions, Fall 2005

Topic Link Date/Time Location Discussion leader Notes
Finding Optimal Triangulations Via Minimal Vertex Separators (1997) by Shoikhet and Geiger. link Tue, Oct 18th, 2005, 10:30-12:30 Sieg-424 Bilmes -
The regularization path (or what is also called the accuracy-regularization frontier). Hastie's NIPS and JMLR papers on this topic for SVMs. Tue, Oct 25th, 2005, 10:00-12:00, Sieg-424 Gang Ji -
Treewidth and Min Fill-in: Grouping the Minimal Separators Bouchitte and Todinca's paper on this topic. Also see this Tue, Nov 1st, 2005, 10:00-12:00 Sieg-424 Karim Filali -
Finish last week's paper finish last week Tue, Nov 8th, 2005, 10:00-12:00 Sieg-424 Karim -
Listing all potential maximal cliques of a graph, by Bouchitte and Todinca link Tue, Nov 15th, 2005, 10:00-12:00, Sieg-424 Chris Bartels -
Kernel day: Why reproducing kernel hilbert spaces (RKHSs) Kimeldorf and Wahba's Some Results on Tchebycheffian Spline Functions (also see here for other older and clear readings on RKHSs). Other background reading: Kolmogorov/Fomin "Elements of the theory of functions and functional analysis" and Bollobas "Linear Analysis : An introductory course" Tue, Nov 22nd, 2005, 10:00-12:00, Sieg-424 Mukund Narasimhan -
Extra Kernel day, finish last time. Kimeldorf and Wahba's Some Results on Tchebycheffian Spline Functions (also see here for other older and clear readings on RKHSs). Other background reading: Kolmogorov/Fomin "Elements of the theory of functions and functional analysis" and Bollobas "Linear Analysis : An introductory course" Wed, Nov 23rd, 2005, 3:30-5:30, Sieg-424 Mukund -
- - Tue, Nov 29th, 2005, 10:00-12:00, Sieg-424 Kevin -
- - Tue, Dec 6th, 2005, 10:00-12:00, Sieg-424 Susan -
- - Tue, Dec 13th, 2005, 10:00-12:00, Sieg-424 Sangyun -


Discussions, Winter 2005

Topic Link Date/Time Location Discussion leader Notes
Kernels 11th chapter from the book Wed March 9nd, 10:00a-12:00pm Sieg-424 Jeff Bilmes (but I'm scheduled to lead MTRG this week as well, so this might change)
Kernels 10th chapter from the book Wed March 2nd, 10:00a-12:00pm Sieg-424 Mukund Narasimhan -
Kernels 9th chapter from the book Wed Feb 23rd, 10:00a-12:00pm Sieg-424 Sheila Reynolds -
Kernels 7th chapter from the book Wed Feb 16th, 10:00a-12:00pm Sieg-424 Gang Ji (we did 1/2 of this chapter before. We'll concentrate on 2nd half).
Kernels 8th chapter from the book Wed Feb 9th, 10:00a-12:00pm Sieg-424 Jeff Bilmes -

Discussions, Fall 2004

Topic Link Date/Time Location Discussion leader Notes
The convex-concave procedure Nips and Neural Computation Monday October 19th, 5:30-7:30pm Sieg-424 Mukund Narasimhan -
Kernels First chapter from: link Monday October 25th, 5:30-7:30pm Sieg-424 Chris Bartels -
Kernels - Second chapter from: link Monday Nov 1st, 5:30-7:30pm Sieg-424 Jeff Bilmes -
Kernels Third chapter from link Monday Nov 8th, 5:30-7:30pm Sieg-424 Gang Ji -
Kernels Forth chapter from Monday Nov 15th, 5:30-7:30pm Sieg-424 Yan Min -
Kernels Fifth chapter from Monday Nov 22nd, 5:30-7:30pm Sieg-424 Karim Filali -
Kernels 6th chapter from Monday Nov 29th, 5:30-7:30pm Sieg-424 Xiao Li -
Kernels 7th chapter from Monday Dec 6th, 5:30-7:30pm Sieg-424 Xin -

Discussions, Spring 2004

Topic Link Date/Time Location Discussion leader Notes
Max-product and finding the most probable distribution configurations. here or here April 9th, 9:30-11:30am EE-403 Jeff Bilmes -
Max-product and finding the most probable distribution configurations. here or here April 16th, 9:30-11:30am EE-403 Jeff Bilmes Finish discussion from last time.
Two papers on convergence results in loopy BP paper1 and paper2 (papers 6 and 7 below) April 23th, 9:30-11:30am EE-403 Mukund Narasimhan -
No meeting, EE open house day - April 30th, 9:30-11:30am EE-403 - -
No meeting, No meeting, HLT - May 7thth, 9:30-11:30am - - -
Finish the Weis paper on loopy BP. paper2 May 14th, 9:30-11:30am EE-403 Mukund Narasimhan (postponed again since speaker is sick).
No Meeting, ICASSP - May 21st, 9:30-11:30am EE-403 - -
Finish the Weis paper on loopy BP. paper2 May 28th, 9:30-11:30am EE-403 Mukund Narasimhan -
TBD - June 4th, 9:30-11:30am EE-403 - -
TBD - June 11th, 9:30-11:30am EE-403 - possible conflict with graduation.

Discussions, Winter 2004

Topic Link Date/Time Location Discussion leader Notes
K-tree approximation is hard (darnit!) Karger/Srebro on maximum bounded tree-width graphs. Jan 15th, 2004, 5:00pm AE-108 Mukund Narasimhan notes. Also see the other Srebro papers below
K-tree approximation is still hard (darnit!) Karger/Srebro on maximum bounded tree-width graphs. Jan 22th, 2004, 5:00pm AE-108 Mukund Narasimhan This is a contination of last week. updated notes.
Arnborg, Complexity of finding embeddings in a k-tree link Jan 29th, 2004, 5:00pm AE-108 Chris Bartels ppt slides and pdf
Generalized mean field in exponential families. link(paper #9 below)(and pdf) Feb 5th, 2004, 5:00pm AE-108 Ozgur Cetin notes.
W. Wiegerinck paper on variational approximations between mean field and Junction tree. link(paper #5 below) Feb 12th, 2004, 5:00pm AE-108 Gang Ji (we're going backwards in time from last week, but this is a good paper we should cover) ppt slides
Reduction of Computational Complexity in Bayesian Networks through Removal of Weak Dependences link (paper #1 below) Feb 19th, 2004, 5:00pm AE-108 Chiaping Chen -
No Meeting This week - Feb 26th, 2004 1:00pm AE-108 - -
sampling A general algorithm for approximate inference and its application to hybrid bayes nets, by Koller et. al. link(paper #1 below)(pdf link) March 4thth, 2004 1:00pm AE-108 Sanjay Chaudhuri, UW Statistics -
TBD - March 11th, 2004 1:00pm AE-108 Franz and/or Susan -

Discussions, Autumn 2003

Topic Link Date/Time Location Discussion leader Notes
Introduction Motivation, overview of inference - Oct 3, 2003, 2:30pm EE1-403 Jeff Bilmes -
Computing upper and lower bound on likelihoods in intractable networks, Jaakola&Jordan link Oct 10, 2003, 2:30pm EE1-403 Chia-ping Chen -
An Introduction to Variational Methods for Graphical Models, Jordan et. al. link Oct 17, 2003, 2:30pm EE1-403 Jeff Bilmes -
ICASSP deadline, no meeting - Oct 24, 2003, 2:30pm - - -
W. Wiegerinck paper on variational approximations, from UAI2000 + background on statistical physics. link Oct 30, 2003, 2:30pm EE1-403 Mukund Narasimhan Background on statistical physics.
Out of town, no meeting - Nov 7, 2003, 2:30pm - - -
Tutorial on statistical physics link Nov 14, 2003, 2:30pm EE1-403 Gang Ji -
Yedidia et. al. Understanding belief propagation and its generalizations link Nov 21, 2003, 2:30pm EE1-403 Ozgur Cetin -
No meeting, thanksgiving - Nov 28, 2003, 2:30pm - - -
No meeting, ASRU'2003 - Dec 5th, 2003, 2:30pm - - -
More on statistical physics random graphs and K-satisfiability problem Dec 12th, 2003, 2:30pm EE1-403 Gang Ji -
TBD - Dec 19th, 2003, 2:30pm - - -

See list of of past discussion topics from previous quarters.

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

Variational/Mean Field

  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

Sampling/Monte-Carlo

  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

Loopy-Belief Propagation

  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

Model Simplification/Restructuring

  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

Other/Hybrid/All of the above

  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.

General: realted to inference

  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

Maintained by Jeff Bilmes Last updated: $Date: 2007/03/01 02:10:57 $