# How to train in models, with efficient inferences, like belief-propagation ?

There are many papers that are devoted to efficient inference in graphical models. Though many of these paper don't explicitly talk about the learning (training, etc) problem. For example:

http://videolectures.net/mlss09uk_minka_ai/

I am a little confused on how these models being trained. I thought they are probably doing an EM-like algorithm, i.e.

1. Inference (and calculating all marginals, using VB or EP)

2. Maximizing the likelihood using some blackbox optimization toolboxes using the marginals in the previous case

For example, consider different variants of Belief-Propagation. There are HUGE number of variants for BP, but how a graphical model could be trained?

I'm a little confused by your question. Tom Minka's tutorial you are referring to is completely devoted to inference in graphical models. Learning the parameters of a graphical model is an inference problem, and, therefore, methods explained in the tutorial such as expectation propagation or variational inference can be applied to it. In fact, all of the examples in the tutorial show how to learn parameters in various graphical models.

EM algorithm can be applied to this problem as well. It should be, however, noted the the EM algorithm delivers point estimates for the parameters of interest, and, therefore, can be inferior to the approximate Bayesian inference methods discussed in the tutorial, since these methods aim to capture all the uncertainty present in the posterior distribution over parameters.

• Oh, I see. I think I was confusing these two: { 1. Finding the most probable "output label/value" given "input observation" 2. Finding the most probable "parameters of the model", given pairs of training data.} By "inference" I usually refer to 1(and "train" refers to 2), but apparently Minka refers to 2, by "inference" (as in inferring the efficient parameters). Right? – Daniel Oct 29 '13 at 1:10
• The word 'inference' means finding posterior distribution (not the most probable value!) on some variables of the model, given values of some other variables. Variables of interest can be output labels or model parameters, or latent variables. In Bayesian inference there is no explicit distinction between different kinds of variables. – hr0nix Oct 29 '13 at 10:25
• @Daniel. In Jordan & Wainwright's book, parameter learning has its own chapter, Chapter 6 called "Variational Methods in Parameter Estimation" and they make the distinction between "EM estimation" and "Variational Bayes" which is the application of message passing methods to parameter learning in a bayesian setting. That said, I think they mention that unfortunately the term "Variational Bayes" has been reserved to "mean-field" approximations, even though, you could technically apply other methods such as Expectation Propagation, Bethe-Kikuchi & Sum-Product to parameter estimation – Josh Oct 29 '13 at 16:18
• BTW, one thing I don't understand myself is why Expectation Propagation is not seen as an example of Variational Bayes. Don't all these models operate in a Bayesian setting using message-passing to approximate the posterior? – Josh Oct 29 '13 at 16:22
• No, sorry, you got it wrong. It's not that the posterior distribution over parameters does not exist or is improper. It's just that BP is a weak method which can handle very limited number of models only, because it attempts to compute marginals exactly. It can be possible for discrete or Gaussian models, but that's pretty much it. EP, on the other hand, approximates marginals and, therefore, is out of trouble. And in discrete and Gaussian models EP will work exactly as BP. – hr0nix Oct 30 '13 at 0:18

Training is done by EM, repeating the E-step and M-step until convergence.

1. E-step: calculate sufficient statistics using the posterior over the hidden variables given the observed variables.
2. M-step: update the parameters using the sufficient statistics computed in the E-step

For example, see this paper on how it proves learning parameters of HMM is also a belief propagation. http://homepages.inf.ed.ac.uk/csutton/notes/sutton04fbbp.pdf

• I see your point. This is almost something that I've mentioned in my question body. But what @hr0nix mentioned is more interesting me. As I understand, he is treating training the parameters just like an inference problem. – Daniel Oct 29 '13 at 1:09

BP like methods find the optimal parameters for maximizing posterior. This is basically the parameter estimation. Inference can also be done in a similar way. Prediction of the new label could be cast as maximizing a posterior given the optimal parameters of the new model. This is a fully Bayesian approach to estimation, in contrary to directly doing EM steps. For more details see section 4 @ http://www.eecs.berkeley.edu/~wainwrig/Papers/Wainwright06_JMLR.pdf