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. 


*

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

*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? 
Any comments? 
 A: 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.
A: Training is done by EM, repeating the E-step and M-step until convergence.


*

*E-step: calculate sufficient statistics using the posterior over the hidden variables given the observed variables.

*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
A: 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 
