Evaluation Criterea: Correlation versus Generalization

When developing a "third level" loss function (i.e., an automatic metric), one often shows that the ranking or the scores of the automatic function correlates well with the ranking or scores of the human-level function.

I'm not sure this is the best thing to do. The problem is that what correlation tell us is just that: on the data sample we have, our automatic evaluation function (AE) correlates well with the human evaluation function (HE). But we don't actually care (directly) about the correlation on past data. We are about the ability to make future predictions of quality. Namely, we often want to know:

If I improve my system by 1 point AE, will this improve my HE score?

This is a generalization question, not a correlation question. But we know how to analyze generalization questions: Machine learning theorists do it all the time!

So, what do we know: if we want AE to predict HE well in the generalization sense, then it is (with high probability) sufficient that AE predicts HE well on our observed (training) data, and that AE is not "too complex." Usually this latter holds. AE is often chosen to be as simple as possible, otherwise people probably won't buy it. Usually it's chosen from a small finite set, which means we can do really simple PAC-style analyses. So this should be enough, right: we have good prediction of the training data (the correlation) and a small hypothesis class, so we'll get good generalization. Thus, correlation is enough.

Well, not quite.

Correlation+small hypothesis class is enough only when the "training data" is i.i.d. And our problem assumptions kill both of the "i"s. First, our data is not independent. In summarization (and to a perhaps slightly lesser extent in MT), the systems are very very similar to eachother. In fact, when people submit multiple runs, they are hugely similar. Second, our data is not identically distributed to the test data. The whole point of this exercise was to answer the question: if I improve my AE will by HE improve? But, at least if I have the top system, if I improve my AE too much, my system is no longer from the same distribution of systems that generated the training data. So the data is hardly i.i.d. and easy generalization bounds cannot be had.

So what can we do about this? Well, recognizing it is a start. More practically, it might be worth subsampling from systems when deriving correlation results. The systems should be chosen to be (a) as diverse as possible and (b) as high performance as possible. The diversity helps with independence. The high performance means that we're not geting supurb correlation on crummy systems and no correlation on the great systems, leading to poor generalization as systems get better. This doesn't fix the problem, but it might help. And, of course, whenever possible we should actually run HE.

Structured Prediction 3: What's to Come

Different researchers have different priorities, and not all those listed here are things I personally plan to work on. There are many open questions about structured prediction that I'd like an answer to. Hopefully we'll make some headway at the atomic learning workshop, and I'll of course post after that.

1. Move to more complex, "intractable" structures.
2. More with less: improving with only weak feedback.
3. Learning structure: the analogue of learning graphical models.
4. Learning from heterogenous data.
5. Measuring sample complexity.
   
6. Trading off expressivity with tractability.
7. Integrated prediction and data mining.
8. Computational complexity versus sample complexity.

My short term goal is [1] and [6] (and I've worked a bit on [4], but not for SP). Andrew McCallum seems to be working hard on [1] (though using different machinery) and [7]. I think Ben Taskar has some new work on [1] and is probably closer to [5] than any of us. Thorsten Joachims has done interesting work in [1] and [2] (the latter not for SP though), but I think (hope) he might bring some of that across. I don't really know who (if anyone!) is working on the other topics.

The question that drives me is: to what extent can we let the NLPer forget about the fact that there's machine learning going on in the background. I think that, as of now, at least from my perspective, the answer is that the NLPer must be able to structure a search space for his problem, and devise a way for turning the "true output" into an "optimal policy" by breaking it down into regions. The rest is purely trivial crank turning (no math required). The answers to the questions above will help in this endeavor. A very basic question, hinted on before, is: when do we even need to consider structure? If we don't, life is much easier for the NLPer. But we need to be able to say when we do and when we don't need structure. And when we do, we want it to be as painless as possible.

Tutorial: Bayesian Techniques for NLP

I'm giving a tutorial on Bayesian methods for NLP at HLT-NAACL 2006. I gave a similar tutorial about a year ago here at ISI. This gave me a pretty good idea of what I want to keep in and what I want to cut out. The topics I intend to cover are, roughly:

1. Bayesian paradigm: priors, posteriors, normalization, etc.
2. Graphical models, expectation maximization, non-bayesian inference techniques
3. Common statistical distributions: uniform, binomial/multinomial, beta/dirichlet
4. Simple inference: integration, summaring, monte carlo
5. Advanced inference: MCMC, Laplace, Variational
6. Survey of popular models: LDA, Topics and Syntax, Words and Pictures
7. Pointers to literature

All of this is, of course, cast in the context of NLP problems: all discrete distributions, language applications, etc., that hopefully both NLP and IR people will find interesting (maybe even some speech people, too).

Does anyone have anything they'd really like to hear that's not on the list? Or anything that's on the list that they don't care about? Keep in mind several constraints: 3 hours (minus coffee time), generally accessible, focused on NLP applications, and something I know something about. (For instance, I covered expectation propagation in the tutorial last year, but decided to cut it for this to give more time to other issues.) Note that I am also preparing a written tutorial that covers roughly the same material.

Structured Prediction 2.5: Features

I decided to add an additional post on structured prediction before the final one. This is also highly related to the post on joint inference.

One can claim that when doing structured prediction, the features X never have longer range than the loss function, where X is either "need" or "should." To this day I struggle to understand this issue: I don't believe it is as simple as one would like.

Consider our old favorite: sequence labeling under Hamming (per label) loss. The arguement essentially goes: we don't care (i.e., our loss function doesn't care) about how well our labels fit together. All it cares about is getting each right individually. By essentially the same argument as the joint inference post, one can then see that one should train a single classifier that does not use any "Markov-style" features.

On the other hand, I know that I have always seen Markov-style features to help, and I believe that most people who work on SP would agree.

Just as in the joint inference case, I think that if you want to be guaranteed the same information to train a classifier on, you need to move to a cross-product feature space. Unlike John, I do fear this. I fear this for several reasons. First, we already have millions of features. Going to 10^12 features is just not practical (blah blah kernels blah blah). This can also lead to severe generalization issues, and I don't think the state of the art in machine learning is capable of dealing with this. It's trikcy, though, because I largely believe the joint inference argument, and largely don't believe this argument. Yet they are essentially the same.

But I think there might be a more fundamental issue here, beyond cross-product feature spaces, generalization bounds and so on. This is the issue of: if we know a problem has structure, even if the loss function (even the true one) doesn't reflect this, should we make use of this structure. The answer to "Why?" is that it might make it easier on our models to learn. The answer to "Why not?" is that by doing so we require more "human in the loop" than otherwise.

The Art of Loss Functions

There are roughly four types of loss functions that are used in NLP research.

1. The real loss function given to us by the world. Typically involves notions of money saved, time saved, lives saved, hopes of tenure saved, etc. We rarely have any access to this function.


2. The human-evaluation function. Typical examples are fluency/adequecy judgments, relevance assessments, etc. We can perform these evaluations, but they are slow and costly. They require humans in the loop.


3. Automatic correlation-driving functions. Typical examples are Bleu, Rouge, word error rate, mean-average-precision. These require humans at the front of the loop, but after that are cheap and quick. Typically some effort has been put into showing correlation between these and something higher up.


4. Automatic intuition-driven functions. Typical examples are accuracy (for anything), f-score (for parsing, chunking and named-entity recognition), alignment error rate (for word alignment) and perplexity (for language modeling). These also require humans at the front of the loop, but differ from (3) in that they are not actually compared with higher-up tasks.

Note that the difference between (3) and (4) changes over time: there are many (4)s that could easily become (3)s given a few rounds of experimentation. (I apologize if I called something a (4) that should be a (3).)

It is important to always keep in mind that our goal is to improve (1). The standard line is: I can't compute (1) so I approximate it with (2). I can't optimize (2) so I approximate it with (3). (Or, I don't know how to define (2) so I approximate it with (4).)

I strongly feel that the higher up on this list one is, the harder it is to actually define the evaluation metric. It is very easy to define things at the (4) level because there are essentially no requirements on such a loss function other than (A) hard to game and (B) intuitively reasonable. It is a bit harder to define things at the (3) level because an additional critereon is added: (C) must be able to convince people that this new loss function approximates an established (1) or (2). Defining something at the (2) level is shockingly difficult and (1) is virtually impossible.

There are two questions that are crutial to progress. The first is: what is the minimum acceptable evaluation. We cannot reasonably require (1) in all cases. In many cases, I think it absolutely reasonable to require (2); eg. journal papers for which a working definition of (2) is known. Conference papers can usually get by with (3) or (4). I would never accept (4) when a (3) is known. But when not (consider named entity recognition), it's all we have.

It's unclear if this is a good breakdown or not. I could argue never to accept (4): that you must show your results improve something humans care about, at least approximately. But this seems limiting. First, it means that if we want to solve a subproblem, we have to formally show that solving it will be useful before we actually solve it. This is a good thing to do a but of internally, but to do a sophisticated analysis to the point of publishable results to move something from (4) to (3) is a lot of effort for (often) little gain. Especially in the context of a larger research agenda.

I could also argue that for many results, (4) is always sufficient. The argument here is that, from a machine learning perspective, if I can optimize (4), I can optimize anything else you give me. While I've made this argument personally, it's just not true. A more complex loss function might be much harder to optimize (consider optimizing Bleu-1 without brevity penalty versus full Bleu-4). Moreover, it may turn out that whatever biases my model has are good for one (4) and not for another. This is an okay (but not great) argument in an ML conference, but I wouldn't buy it in NLP.

So how do other people rank these things? How much pressure is there to bring a (4) to a (3)? And how often should we do (2)?

Joint Inference

Joint inference is becoming really popular these days. There's even a workshop coming up on the topic that you should submit a paper to! (That is, unless your paper is more related to the computationally hard NLP workshop I'm running with Ryan McDonald and Fernando Pereira).

The problem with joint inference is that while it seems like a great idea at the outset -- getting rid of pipelining, etc. -- in theory it's not always the best choice. I have a squib on the topic, titled Joint Inference is not Always Optimal and I welcome any and all comments/criticisms/etc.

Predictive Models

There are at least two reasonable goals for NLP research: (1) produce predictive systems that mimic humans; (2) produce explanatory models. (2) gets more into CL and CogSci and I may discuss it at a later date. This post is about (1), at least the machine learning approach to (1).

Our goal is to mimic a human on some task. This means we will, at the end of the day, want to measure our performance against human performance. This measurement is our loss function, and is, in my mind, the only thing that really matters. Coming up with a good loss function is really really hard and I will certainly discuss this issue in another post. But suppose we can come up with one: l(t,h) = how much it hurts to produce a hypothesis h when the true answer was t.

The subsequent question is: given some collected data, how can I minimize l. The dominant approach seems to be: approximate l by some well-known loss (binary loss, squared error, absolute loss, etc.) and then use one of the many good classifiers/regressors to solve our original problem.

This step irks me greatly. Not because this approximation is always bad, but because it is never (rarely) stated. Many papers say something like "Our task in XYZ is to minimize misclassification error of problems created by ABC." This is rarely actually true. I would be much happier with the following explanation: "Our task in XYZ is to minimize TUV loss, but we don't know how to do that, so we'll instead minimize misclassification error." This issue manifests itself commonly in another way: putting the cart before the horse. We often gather a data set, label it, solve the labeling problem (eg., by multiclass classification) and then go back and define the problem in such a way that this is an appropriate solution. This is harder to detect, but equally disingenuous.

So let's say we've done things right: we've defined our loss function and we've gotten some labeled data. Now we have to minimize our loss on this data. If we can do this directly, great. If not, we can say so and that we'll approximate it by some other loss l'.

Now we can start looking at features. We have an l' that we can minimize and we want to come up with features that are useful for this minimization. In particular, if ours is a structured problem, and l' is invariant to some change in structure, we needn't reflect this aspect of the structure in our feature functions function (the prototypical example here being Markov features in sequence labeling for Hamming [per-label] loss, though this issue itself could take a whole other post). We should set aside part of the training data for manual inspection to do feature engineering.

Experimentation is the last real step. We've split off a training set, development set and test set (*). We train a model on the training set, evaluate it on the development set. We look at the dev predictions and see what went wrong. We reengineer some features to fix these problems and repeat. Only at the end do we run on the test set and report our results in a paper.

(*) I'm not a fan of cross-validation in such a cyclic process. The features will be engineered based on the training and development data sets, and to then fold all this back into the bag and do cross-validation will give us unrealistically good results.

And as a very final step, in the case that our optimized l' is not the same as l, I would like to see some results that show that they at least correlate reasonably well. And easy way to do this is to run several versions of the model and to report both l and l' scores and let us see that improving l' does indeed improve l.

Domain Adaptation

We NLPers face this problem all the time: we have training data from one domain/genre but really want to work in another. Eg., the treebank is WSJ text but we care about email or web pages or whatever. We'd like to be able to intelligently use our annotated WSJ text to get a good statistical model for a different domain.

I've been working on this problem for a while now and have a partial solution. I'm most interested in the case that we have lots of annotated "out of domain" (OOD) data and a little annotated "in domain" (ID) data. Domain Adaptation for Statistical Classifiers is a paper that's been accepted to JAIR that presents one way to model this problem. The key idea is to model the OOD/ID data distributions as mixtures. There are three mixture components: a "truly ID" distribution, a "truly OOD" distribution and a "general" distribution. We say the OOD data comes from a mixture of "truly OOD" and "general," while the ID data comes from a mixture of "truly ID" and "general." The learning task is to tear apart our data sets to figure out what "general" (and hence relevant to the ID task) information there is in the OOD data.

The framework, when applied to maximum entropy models, gives relatively simple update equations for model parameters. The derivations take a bit of thought, but are not insane. The approach is a partial solution because it's limited to maximum entropy models. I think the problem should be amenable to a more learning theoretic analysis, but haven't had time to make much headway here.

I'm a bit surprised this problem hasn't gotten more attention in the NLP community (a similar problem -- speaker adaptation -- exists in the speech community). Or perhaps I've missed it in NLP. It seems like we, as NLPers, should really care about this issue.

Most Influential NLP Papers

I conducted a mini survey recently, asking people I knew what they thought were the most influential papers in NLP from the past two decades. Here are the wholly unscientific results, sorted from most votes and subsorted by author. Note that I only got responses from 7 people. I've not listed papers that got only one vote and have not included my personal votes.

(7 votes): Brown et al., 1993; The Mathematics of Statistical Machine Translation
(5 votes): Collins, 1997; Three Generative, Lexicalised Models for Statistical Parsing
(4 votes): Marcus, 1993 Building a large annotated corpus of English: the Penn Treebank
(3 votes): Berger et al., 1996; A maximum entropy approach to natural language processing
(2 votes): Bikel et al., 1997; An Algorithm that Learns What's in a Name
(2 votes): Collins, 2002; Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms
(2 votes): Lafferty et al., 2001; Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data
(2 votes): Och, 2003; Minimum Error Rate Training for Statistical Machine Translation
(2 votes): Papineni et al., 2001; Bleu: a method for automatic evaluation of machine translation
(2 votes): Ratnaparkhi, 1999; Learning to Parse Natural Language with Maximum Entropy Models
(2 votes): Yarowsky, 1995; Unsupervised Word Sense Disambiguation Rivaling Supervised Methods

This seems to be dominated by parsing and techology/machine learning papers, with a smattering of MT thrown in for good measure. I feel that the former represent a sort of "lowest common demoninator." There were several singleton votes for various papers in summarization, language modeling, IR, and other fields, but, with the exception of the MT papers, getting >1 vote meant that you had to be useful to more than just your one community. It's also a bit surprising that Collins' parser is so high, but no other parsers got any votes (Charniak, Lin, etc.).

Feel free to say what you think is missing!

Structured Prediction 2: My Perspective

In Structured Prediction 1: What's out there?, I discussed current SP technology: Markov fields, CRFs, M3Ns and SVMISOs. Here I'll discuss my work briefly. I'll come back to SP once more to discuss what seems to be on the horizon.

With so many options, why bother with a new one? There are problems that are not solved by the standard approaches. The biggest problem is the "argmax assumption," which states that you can solve the following problem:

arg max_{y in Y} f(x,y; w) = arg max_{y in Y} w*Phi(x,y)

Where the equality is under the standard linear predictor assumption. This maximization requires that, for an input x, we are able to compute the highest scoring possible output (efficiently).

The problem is that for many (most?) NLP problems, without making completely unreasonable assumptions, this maximization is intractable. The standard assumptions that make this operation polynomial time are the Markov assumption for sequences and the context-free assumption for trees. But we know that both of these assumptions are invalid, and a few papers have tried to deal with this by using sampling, reranking or approximate inference techniques.

On the other hand, if you look at what people in NLP actually do to solve problems, they use approximate search (MT is a good example). In this way, the search space can be tuned to precisely capture the functional (feature) dependencies needed.

My perspective is that if we're going to use search anyway, we should take this into account while learning. There is no point to learning a model that ranks the best output highest if we cannot actually find this output. And once we start using approximate search, any performance guarantees related to learning pretty much go out the window.

The really cool thing is that a completely different brand of machine learning people have considered learning in the context of search, but they call it reinforcement learning. The key difference between SP and RL, as I see it, is that in RL you can affect the world whereas in SP you cannot. In the standard "action/state/observation" terminology, in SP you only get one observation at the very beginning (the input x), while in RL the observations keep coming in as you take more actions. This seems to be the fundamental difference between the two problems.

So, by treating SP in a search framework, what we basically want is a function that takes our input x, a partial output represented by a state in our search space s, and predicts the best action to take: the best thing to add onto the partial output. For instance, in sequence labeling with left-to-right decoding, we might predict the label of the next word. In MT, we might predict a French phrase the translate and its English translation and append this to a translation prefix. The action set is potentially large, but not impossibly so (if it were, the problem would be intractable anyway).

The great thing is that this enables us to formally cast structured prediction as a cost-sensitive multiclass classification problem. Lots of algorithms have been developed for the multiclass problem, and we can seek to apply these to the SP problem through this reduction. This gives us simple, efficient algorithms with good practical performance and strong theoretical guarantees. The key requirement that makes all this work (essentially my version of the arg max assumption) is that for a given input x, true output y and state s in the search space, we can compute the action a that is optimal to execute from s. This is the "optimal policy assumption." (We can actually weaken this assumption to require only a bound on the optimal policy, which is necessary for optimizing things like BLEU or ROUGE, at least under interesting models.) It is provably a strictly weaker assumption than the assumptions made by CRFs and M3Ns, essentially because it doesn't care about the feature space, which means we can have whatever the heck features we want (a good thing for NLP).

The MT Blues: Would a program get its facts right?

I just came across an article on Slate entitled The Translator's Blues: Will I get replaced by a computer program?, written by Jesse Browner, a human translator. I've no idea how wide-read Slate is, and I think Browner is correct that his job is not (yet) in jeopardy, there are several common misconceptions in the article that really shouldn't be there.

First, the results of his example sentence are atrocious. I see no reason why even the rule-based systems should get this wrong (though I suspect his poor results had to do largely with the difficulty of inputting accented characters). Language Weaver stood out, which is good, because it's a good system. In fact, in all the news texts he tried, it is reported to fare well.

And he's right that the technology has limits: it could not translate the first sentence of Don Quixote well. This is the domain adaptation problem: Language Weaver's system was trained on news data and (surprise surprise) it performs well on news and not on fiction. I think the important point is that the problem is domain. IMO, it has nothing to do with context, which is what Browner attributes the problem to. The con/pen example is something that I believe a decent statistical MT system should and would get right; if not now, in a few years once language models are better. It's unfortunate that Browner doesn't say that Language Weaver is (largely) a statistical systems, because he seems to say that they suck, yet LW was by far the best system he tried.

My final comment is in reference to the attribution to Mike Collins, who clearly knows much more about this field than many. Most likely Mike was quoted out of context, but Language Weaver's system -- and, in fact, most good research systems out there -- are based on machine learning. That's what "statistical" means.

(Incidentally, for those less literary minded, the first sentence of Don Quixote should be translated something like "In a village of La Mancha, the name of which I have no desire to call to mind, there lived not long since one of those gentlemen that keep a lance in the lance-rack, an old buckler, a lean hack, and a greyhound for coursing." I'm not convinced that a professional translator who worked for the UN would find this easy to translate either.)

NLP as Glorified Memorization

The view of NLP as essentially a hunt-and-return technology has been gathering momentum since the burgeoning of the web. Example-based MT takes this view to machine translation, and phrase-based statisitcal MT is essentially EBMT done with statistics. In question answering (factoid style), the situation is even more dramatic. Deepak's thesis was essentially devoted to the idea that the answer to any question can be found in huge corpora by relatively simple pattern-matching. To a somewhat lesser degree, information extraction technology is something like smoothed (or backed-off) memorization, and performance is largely driving by one's ability to obtain gazeteers relevant to one's task.

Pushing such memorization technology further will doubtless lead to continued success, and there are many open research questions here. I would love others to answer these questions, but I have little interest in answering them myself. Fortunately, I think there are many interesting real-world problems for which simple memorization techniques will not work, and deeper "analysis" or "understanding" is required.

Any QA/summarization task that focuses on something other than "general world knowledge" fits into this category. I might want to ask questions to my email client about past emails I've recieved. The answer will likely exist only once, and likely not in the form I ask the question. I might want to ask questions about scientific research, either from PubMed or REXA. I might want to ask about the issues involved in the election of the Canadian PM (something I know nothing about) or the confirmation hearings of Samuel Alito (something I know comparatively more about). And I would want the answers tailored to me. If I owned a large corporation or were running a campaign, I would want to know what my supporters and detractors were saying about me, and who was listening to whom.

I could be proven wrong: maybe memorization techniques can solve some/all of these problems, but I doubt it. What other problems are people interested in that may not be solvable with memorization?

Long Distance Collaboration

For those who have engaged in such an affair, I'm curious how you make it work well. I've been working with John Langford recently, drawing out and exploiting connections between structured prediction and reinforcement learning. I'm visiting family in Chicago now and will be going to TTI tomorrow to visit. Up until this visit, we've talked mostly over email, less over phone and even less in person (some at ICML and NIPS 2005). But the rate of information transfer in such collaboration is significantly less than if John had an office down the hall from me. How do people make this work?

1. Site visits. This is/was the defacto standard in business for ages, before the internet came. People also tended to collaborate less and in business there is perhaps less of a push for collaboration rather than subcontracting. While undoubtedly the best method for interacting, there is significant overhead in terms of cost, travel time, etc., especially in different continents.
2. Telephone. Another good business standard; unfortunately, I'm really a white-board kind of guy, and it's really hard to draw on someone else's white board. Talking about math and referencing papers is also difficult over the phone. Large time differences can also be a nuisance (I recall talking to Yee Whye at about midnight my time because of the time difference to Singapore).
   
3. E-mail. This seems to be what is used most: it is cheap and doesn't suffer from the time difference, though replies are delayed. It enables you to think more about a topic before replying, but cuts down on often-constructive back-and-forth discussion (since that would take too long). The medium is also limited: typing math into email is ugly for anything complex, and you still can't draw on someone else's white board. Twice in my life I've attached .eps figures, but this is highly ineffective.
   

So, what do other people do? Is there any hope? It seems that email could theoretically be retrofitted to fix a lot of the problems I have with it (multiple media, drawing, math, etc.), but does such technology exist currently?

The Mad Paper Rush

The HLT/NAACL deadline passed last month and the ACL deadline is next month. The cluster here seems more swamped than usual, people are rushing to get experiments done and papers written. It seems that most research gets done two months prior to the due dates and papers are rarely, if ever, submitted early. (Actually, I saw a statistic from ICML that most early-submitted papers actually got rejected in the end!) As someone who is trying to organize a ski trip to Mammoth two weeks before the ACL deadline and having difficulty getting people to come, I wonder why there's always this last minute rush. The ACL deadline was published at least four months ago, and even if not, it's actually later this year than usual.

The only explanation that makes sense to me is that the rush is to run a handful of well-controlled experiments based on continuous tweaking of a system. The further you can delay running these experiments, the more you can tweak. Importantly, assuming you're a good researcher, the experiments are not to convince yourself that your approach is viable. The experiments are to convince your potential reviewers that your approach is viable.

Based on this, there seem to be two ways to cut down on this rush (assuming people don't like it). First is to reduce the amount of tweaking done. Second is to reduce the number of well-controlled experiments run. Unfortunately, both of these will probably result in lower chances of your paper being accepted (confirming the above-cited ICML statistic). But this is bad. Tweaking will improve your scores (hopefully), but will rarely be mentioned in the paper, leading to irreproducible results. Running too many experiments can cloud the point of your paper and significantly cut down on your time to work on real things.

Despite this, people continue to tweak and run too many experiments (myself included). This seems to be because the cost of failure is too high: if your paper is rejected, you basically have to wait another year to resubmit, so you want to cover all bases. Two solutions come to mind. First, we could spread our conferences further apart, meaning that you have only to wait 6 months. Second, we could try to ensure that reviewers know that with a limit of 8 pages, one cannot run all possible experiments, and that they can suggest alternative contrastive experiments to be run, but if the experiments back up the main point(s) of the paper, this should be sufficient. I don't think the "review/response" approach will fix this because running a new experiment is not what author responses are for, and this is just delaying the problem, rather than fixing it (though I do advocate the response phase).

Structured Prediction 1: What's Out There

Structured prediction (SP) -- the machine learning task of generating outputs with complex internal structure -- is near and dear to my heart. It is also a generalization of many NLP problems (summarization, MT, IE, coref, parsing, tagging, etc.). This is the first part of a multi-part post on structured prediction (first: what's out there; second: what I do; third: where we should go).

The most important aspect of the SP problem (aside from the data) is the loss function: l(y,y') gives us how much it costs us to produce y' when the correct answer is y. Our goal, as always, is to minimize the expected loss over the distribution that generated our training data. The common way of doing this is to posit a large set Y of possible outputs and to try to find a function f(x,y) on an input x and output y that ranks outputs: f(x,y) > f(x,z) if y is a better output than z. Once we've learned such a function, the only thing left is to find a way to search over all y to find the one with highest score. Aside from the parameterization of f (which is almost always taken to be linear the feature set), the only thing left that matters is how we measure one f against another. For notational covenience, let g(x,y) = exp(-f(x,y)). Here are some common ways to score f:

• Generative: f is good if g(x,y) / sum_{x',y'} g(x',y') is high for all (x,y) in the training data
  
• Conditional: f is good if g(x,y) / sum_{y'} g(x,y') is high for all (x,y) in the training data
  
• Discriminative-M: f is good if f(x,y) > f(x,y') + l(y,y') for all (x,y) in the training data and all y', where errors are punished equally
  
• Discriminative-S: f is good if f(x,y) > f(x,y') for all (x,y) in the training data and all y', where errors are punished proportional to l(y,y').

Assuming all optimizations are equally difficult (or easy), these techniques should be ranked according to how closely they match our true desire: low expected loss. To me, the Discriminative-S method is the closest. To see the distinction between D-S and D-M, consider the case where we can easily find a function that ranks the correct outputs higher than the incorrect outputs, but cannot distinguish between the incorrect outputs. From the perspective of expected loss, this is sufficient. From the perspective of D-S, this is also sufficient. But it's not good enough for D-M. D-M requires that if some really bad y' exists, then f(x,y) has to be much larger (by l(y,y')) than f(x,y'). I don't see a reason why we should care about this.

Another way of looking at these methods is how we can optimize them. Let's suppose f is just w*h(x,y), where h(x) = sum_r h(x,r) is a decomposition over regions (adjacent tags in sequences, for instance), w is a weight vector and h provides a feature vector. We can compute the gradient of the optimization criterea (using exponentiated gradients for the discriminative methods) for each of the methods on a given input (x,y) as:

sum_{r in y} h(x,r) - sum_{y'} sum_{r' in y'} X h(x,r')

This is just the difference between the true features h(x,r) and the guessed features h(x,r'), where the guesses are weighed by X. The only difference between the above techniques is how we define X.

• Conditional: X = (1/Z) exp [ sum_{r' in y'} w*h(x,r') ]
• Discriminative-M: X = (1/Z) exp [ sum_{r' in y'} e C [ (t-1) l(y,r') + w*h(x,r') ] ]
• Discriminative-S: X = (1/Z) exp [ sum_{r' in y'} e C l(y,r')^(t-1) w*h(x,r') ]
  

In all cases, Z is defined so that the sum is unity. In the latter two, e is a learning rate, C is the SVM slack hyperparameter and t is the iteration number. The conditional X can be interpreted as the posterior probability of this (incorrect) region under the current model. Going from conditional to D-M involves the insertion of the loss function, leading to a loss-augmented posterior. The (t-1) term essentially means that as more iterations are performed, the loss term becomes increasingly important. In the D-S version, we multiply by the loss rather than add it.

What does this tell us? Well, it tells us exactly what we saw before: the gradient on the D-M model is high when the loss is high, even if the (non-loss-augmented) posterior is zero. This means that even if our model would never produce a wrong region, but that region has high loss, the gradient is still high at that point. This contrasts with the D-S gradient, which, once the posterior disappears, doesn't care about the loss anymore.

The only tricky thing in any of these models is to compute the sum over y' efficiently (or, alternatively, approximate it by computing the max over y'). In well formed cases, like sequence labeling or parsing (under strict assumptions), this is possible using standard dynamic programming (or sometimes, max-flow) methods.

Incidentally, the "conditional" model refers to CRFs, the "discriminative-s" model refers to SVMISOs and the "discriminative-m" model refers to M3Ns.

Under the NLP Christmas Tree

Lance Fortnow eloquenty states that all he wants for Christmas is a proof that P != NP. This got me to thinking about what I, as an NLPer, would most like for Christmas. Unfortunately, things in AI aren't as clear-cut as things in theory because it's hard to tell if we've succeeded. That said, what one might call a Halbert's Program for NLP is a (set of) techniques for super-human aggregation of information from multiple sources, media and domains specific to a given user. There are several "enabling" technologies that (I believe) are necessary to achieve this goal (those that I actively work on are starred):

• Human-level machine translation models (data in, system out)
• Turn-key structured prediction techniques with lots of features, complex loss functions and hidden variables*
• (Weak?) semantic entailment on raw text
• Personalization that doesn't obviate privacy
• Domain adaptation of arbitrary statistical models with little new annotated data*
• Automatic speech recognition
• Graph, equation and table "understanding"
• Weakly supervised summarization, more complex than extraction*
• Database querying from natural language queries
• Social network analysis
• Plan recognition, opinion and point-of-view analysis

There are doubtless other interesting things and, of course, each of these might have its own set of enabling technologies (and there are also some cross dependencies). One perhaps controversial aspect is that I consider MT to be an enabling technology; this is because I don't necessarily care about reading Chinese documents -- I care about the information in the Chinese documents. To me, everything is about getting information, regardless of the source.

Summarization

Summarization is one of the canonical NLP problems, but of all the big ones (MT, speech, IR, IE, etc.) it is in my opinion the most difficult (let the flames begin!). The reason I think it's so hard is because it's unclear what a summary is. When one cannot define a problem well, it is impossible to solve, and difficult ⊆ impossible. There has been an enormous amount of effort to define specific summarization problems that we can solve, a comparable amount of effort on figuring out how to measure how good a solution is, and a lot of effort on building models/systems that can solve these problems. We've tried many things; see the history of DUC for a small, biased, incomplete set.

That said, I think the field has much potential, but not necessarily by trying to mimick what a human would do when asked to produce a summary. I'm interested in doing summarization-like tasks that a human would never be able to do reliably. Here are some examples to give a flavor of what I'm talking about:

• Let me go to a scientific engine like Rexa or CiteSeer and ask for a summary of "reinforcement learning." The system should know what papers I've read, what papers I've written, the relationship between all the papers in its database, an analysis of the goodness of authors and so on. What it produces for me must be markedly different from what it would produce for Satinder Singh.
  


• Let me go to Amazon and ask about new digital cameras. Maybe I'm interested in spending $200-$300. It should know that I've never bought a digital camera before, or that I've bought 4. I want a summary of important specifications, user comments and so on.
  


• Let me go to my own inbox and ask for a summary of what I've been discussing with John recently.

One can imagine many more similar tasks, but these are three obvious ones. The nice thing about these is that even partial solutions would be enormously useful (to me, at least...my mom might not care about the first). These are also things that people really can't do well. If someone asks me for something like the first one but, say, on structured prediction instead of reinforcement learning, I can give a summary, but it will be heavily biased. It is worse for the second, where I can basically only produce anecdotal evidence, and virtually impossible for the third.

The most important outstanding issue is how to measure sucess at such problems. I cannot imagine how to do this without doing user studies, but people probably felt the same way about MT a few years ago. How about now? But given the amount of personalization in these tasks, I feel that it would be harder to do automatic evaluation of them. Probably the most important things to measure in user studies are subjective satisfaction, how many times multiple searches had to be performed and so on. One could also take a TREC style approach for comparative pair-wise evaluations by marking system 2 down if it missed something system 1 found that a human thought was important.

There are also tons of subproblems that can be pulled from this tangle of tasks. Most notably, personalization methods, social network analysis methods, redundancy identification, coherence, information presentation (UI) techniques, generation of multimodal outputs (tables, graphs, etc.), dealing with imperfect input (googling for "reinforcement learning" also produces irrelevant documents), opinion identification, processing of ungrammatical input, anti-spam, and so on. I'm not a huge proponent of just solving subtasks that aren't proven to be necessary, but it is sometimes helpful to take this approach. I think we just have to keep the big picture in our minds.

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.

Bayesian Methods for NLP (summary)

I recently co-organized a BayesNLP workshop with Yee Whye. Here's a brief summary of a subset of the talks and the discussions that took place.

Topic models and language modeling: A lot of the discussion and papers were about either TMs, LMs or both. Much of the discussion of topic models was how to introduce Markov-style dependencies. There are essentially three ways to do this: (1) make word i dependent on topic i and word (i-1); (2) make topic i dependent on topic (i-1); (3) both. Basically this comes out in how you structure the "beta" language models (in LDA terminology). There is a trade-off between number of params (|vocab| * (# top)^2 versus |vocab|^2 * (# top)) and the ability to fit data. I think the general consensus is that if you have a lot of data (which you should!) then you should use the more expressive models.

The major problem with these models is that they often are evaluated by their perplexity on test data. These perplexities are significantly higher than those obtained by people in the speech community, which raises the "why should I care question" (see this other entry). There are several potential answers: (1) topics can be embeded in a task (say MT) and this leads to better performance; (2) topics are used to enable new tasks (browsing Science repositories); (3) topics can be compared with what humans do in a CogSci manner.

This topic lead into some incomplete discussion on what sorts of problems we might want to work on in the future. I don't think there was a solid decision made. In terms of what applications might be interesting, I think the agreement was that Bayesian techniques are most useful in problems for which there is insufficient data to fit all parameters well. Since "there's no data like more data" has become a mantra in NLP, this seems like it would include every problem! My opinion is that Bayesian methods will turn out to be most useful for largely unsupervised tasks, where my prior knowledge can be encoded as structure. I think there's lots of room to grow into new application domains (similar to some stuff Andrew McCallum has been working on in social network analysis). Introducing new tasks makes evaluation difficult which can make publication difficult (your eight pages have to go both to technique an evaluation), but I think it's the right way for the community to head.

I also really like Yee Whye's talk (which happened to propose basically the same model as a paper by Goldwater, Griffiths and Johnson at this same NIPS), where he basically gave an interpretation of KN smoothing as a nonparametric Bayesian model with a Poisson-Dirichlet prior. Unlike previous methods to explain why KN works, this actually give superior results to interpolated KN (though it loses to modified interpolated KN). Shaojun talked about integrating a whole bunch of stuff (Markov models, grammars and topics) into a language model using directed Markov fields as an "interface" language. This was really cute and they seem to be doing really well (going against the above comment that it's hard to get comparable perplexities). I believe there's an upcoming CL paper on this topic.

If anyone else took part in the BNLP workshop and would like to comment, you're more than welcome.

Interesting topics in NLP

Papers for HLT/NAACL are due Friday, but since I'm probably not submitting anything, I'll take this opportunity to write down some thoughts about what NLP seems to care about and what I think it might care about more. Topic-wise, we have several big areas that typically overwhelm conference proceedings:

• Machine Translation
• Summarization
• Language Modeling
• Information Extraction
• Parsing

There's obviously a lot more to NLP than these topics, but these by far recieve the highest publication rate at conferences like ACL, NAACL, HLT and COLING. I think it's fairly obvious why. Each has some strong combination of the "required" two aspects for publication at these conferences:

• Importance (or strong community beliefs thereof)
• Evaluatability (especially on common data sets with common metrics)

There is a third aspect under which contributions can be measured that doesn't seem to play a strong role in our field right now: Interestingness. The problem is that evaluating interestingness is difficult. As pointed out by Sam Roweis at a discussion at the BayesNLP workshop, this is something that SIGGRAPH is very successful at. Perhaps SIGGRAPH papers aren't on the most important or evaluatable topics, but they are certainly interesting. Putting too much weight on interestingness is probably a bad idea, especially if it completely forgoes the other two aspects. But maybe we'd be better off as a community if we had one or two tracks (or perhaps a workshop) that focused exclusively on interesting, new problems, even if they fumble a bit on evaluation and obvious short-term importance. Some topics I care about (i.e., think are interesting) that are not commonly seen at ACL-like conferences are:

• User modeling or personalization in general
  
• CogSci-oriented human-learning or -usage of language
  
• Situated language experiments, in real or simulated worlds
• Super-sentence models of coherence, cohesion, relation between documents
• Tasks involving multiple media (text + {video, images, charts/tables, ...})

I don't expect these thing to actually start appearing soon, and I know there are conferences that focus more on each aspect individually, but I think it's time that our community as a whole starts paying more serious attention to what goes on in these areas.