Abstract

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 .