Unsupervised training of Markov Random Fields with latent variables

Thanks!

About joint likelihood: how do you define that for unsupervised models (ie, where you don't have access to the ys but want to estimate them, like in unsupervised POS tagging)? I thought pseudo-likelihood was very closely related to conditional likelihood. The non-local contrastive objectives paper seems interesting, I'll read it.

The "Training conditional random fields for maximum labelwise accuracy" paper seems supervised, as well as the "alternate objective paper".

Yes, I was also looking for margin-based approaches, but it is kinda hard to visualize how they should work without supervision.

Do you care to explain a bit how colorings relate to learning in gibbs fields?

I think the hardest problem to overcome with a margin-based approach to unsupervised learning of markov random fields is what to put on the other side of the margin. If you put all other examples, you become about as efficient as EM, if you define a neighborhood it gets very similar to Smith and Eisner. One-class SVM separates points from the origin, so I guess this idea could be extended to the max-margin-markov setting, but it doesn't seem able to deal with latent variables, which is the setting I'm thinking about (ie, it seems to work perfectly in the complete-data case, but not in the incomplete-data case).

Above are just general techniques for learning P(X) where P is modelled as a Markov Field. As to how apply them to POS tagging....well....if you don't have examples of POS tags, how can you ever learn to label them? Do you perhaps mean semi-supervised learning?

Both papers on pointwise log-likelihood are applied to supervised task, but they don't have to be. Just take a dummy fixed x and then learn parameters using their technique. It'll then give you a density over y's without dependence on any x.

Without labels, margin based approaches need a new definition of "margin". For instance, like on one-class SVM.

I wrote an overview of the MRF-colorings connection on mathoverflow, but here's a brief summary: Suppose you sample uniformly from the set of proper colorings on a graph. This random variable is distributed as P(x)propto exp{sum_{ij} I(x_i=x_j)) where the sum is taken over all the edges in the graph. Combinatorics people are really interested in counting the number of proper colorings which is the same as the partition function of distribution above, and there's an equation (Gamarnik calls it "Cavity Expansion") which lets you express the number of proper colorings in terms of marginals of the distribution of the form P(x). They came up with a novel family of algorithms for finding marginal P(x_i=c) in that particular model, but they can be extended to general Gibbs fields.

The traditional approach to learn the POS tags without examples is to learn a model with latent variables that looks like a HMM (label-label features and label-word features, with observed words (and other features) and hidden labels) and label the latent variables in some way (this is sort-of cheating, yes, but some people try to minimize the cheating; see the Haghighi and Klein paper I linked in the question for more comments on this, including a strategy that leads to less cheating and more accurate estimates). The idea is to learn the distributional properties of POS tags, not necessarily their names (since this is the harder part of the problem).

If you're just learning a MRF with only observed variables (like vision people do to later use without supervision, for inpainting or whateter) the generalization of one-class SVM to M³Ns is trivial, as is adapting the Joachims cutting-plane algorithm, I think. With hidden variables the task is harder, but maybe it can be generalized to an expectation-max-margin thing (ie, minimize ||w|| - C/n sum( max(E_y[w·phi(x)] - p, 0))), where the expectation is over the hidden variables and computed with sum-product. I'm not sure the cutting plane algorithm works for this (specially since with that expectation the constraints might get too ugly), but I guess this is worth looking at.

That's a cool connection between combinatorics and graphical models. I'll read you summary and the paper more carefully, it seems interesting.

BTW, I'm having some trouble getting formatting to work... "-" looks like bulleted list in the preview, but after committing, they show up as numbered lists