NLP and NIPS

Several people have already posted what they thought were the coolest NIPS papers this year elsewhere. Instead of saying what I thought were necessarily the best, I'll say what I thought were most interesting from an NLP perspective.

Max Margin Semi-Supervised Learning for Structured Variables. (Yasemin Altun, David McAllester, Mikhail Belkin) This paper talks about the problem of using unlabeled data to learn structured prediction models, in the style of M3Ns. The idea is the same as manifold-based semi-supervised learning in standard classification, extended to structure: penalize disagreement of "nearby" labels (where nearby is defined in feature space, not structure space). They work in the very low data setting and find that (a) unlabeled data helps and (b) structure helps. Neither is surpising, but both are good. I wonder how to scale this to large data sets: all these manifold-based SS techniques require matrix operations on the gram matrix from the unlabeled data, which must be at least O(n^2) but is often worse (n = # of unlabeled points). In NLP, we have bajillions of unlabeled points. There's got to be a good way to do this that will scale, but I haven't see anything yet.

Group and Topic Discovery from Relations and Their Attributes. (Xuerui Wang, Natasha Mohanty, Andrew McCallum) This is a multi-clustering (cluster multiple things at once) paper, where they simultaneously identify clusters of groups and clusters of topics. E.g., they want to cluster senators by how they vote and bills by what they are about. If you do these two things simultaneously, you can get better statistics and thus do better overall.

Structured Prediction via the Extragradient Method. (Ben Taskar, Simon Lacoste-Julien, Michael Jordan) This is a clever solution to extending structured prediction outside the world of Markov fields to the world of quadratic cost min-flow problems (think matching). They get big speedups over previous optimization techniques and can handle a larger set of problems. I plan on writing a separate post on structured prediction, where I'll discuss this and related papers in more detail. But I thought it was cool enough to mention here anyway.

Interpolating between types and tokens by estimating power-law generators. (Tom Griffiths, Sharon Goldwater, Mark Johnson) Despite the scariness of the name, this paper is very interesting to NLP folk. Everything in language looks like a Zipf/power-law distribution, and this paper shows that the Pitman-Yor process models this very well. This is the same model that Yee Whye suggested for modeling Kneser-Ney smoothing, so it's clearly something that has some real weight in NLP.

Context as Filtering. (Daichi Mochihashi, Yuji Matsumoto) Discusses the issue of long-range dependencies in language modeling, breaking out of the bag of words-style histories paradigm. They use both an LDA-like and Dicihlet-mixture topic model that "shifts" through time and can perform inference by treating it as a particle filter problem. The results are on 11m words of data, which is reasonable, and seem promising, though I'd like to see more comparative results.

And that's it! Feel free to post other cool NIPS papers.