Coping with the Intractability of Graphical Models

December 10, 2014
Justin Domke | National ICT Australia and the Australian National University

Many potential applications of graphical models (such as Conditional Random Fields) are complicated by the fact that exact inference is intractable. This talk will describe two strategies for coping with this situation. The first is based on restricting consideration to a tractable set of parameters. Rather than tree-structured parameters, as is common, I will explore a notion of tractability where Markov chain Monte Carlo is guaranteed to quickly converge to the stationary distribution. This can be used both for inference (as a type of generalized mean-field algorithm) and for learning, where it gives a FPRAS for maximum likelihood learning when restricted to this set. The second, more pragmatic, strategy is based on empirical risk minimization, where a given approximate inference method is “baked in” to the loss function. In particular, I will also discuss a recently released open-source tool for distributed learning of such models using MPI.

Speaker Details

Justin Domke received a PhD in computer science from the University of Maryland in 2009. From 2009 to 2012, he was an Assistant Professor at Rochester Institute of Technology. Since 2012, he is a member of the Machine Learning group at NICTA.