Structured Prediction versus Multitask Learning

For a formal comparison, I will briefly define both SP and MTL:

A structured prediction problem is a distribution D over pairs (x,y), with x in X and y in Y, together with a loss function l(y,y'). Typically Y is large, and elements y have complex interdependent structured, which can be interpreted in various ways. The goal is a function f : X -> Y that minimizes the expect loss: E_{x,y ~ D}[l(y,f(x))].

A multitask learning problem is a distribution D over tuples (x,y,y1,...,yK), with x in X and (for simplicity) y,y1,...,yK all in 2={0,1}. The goal is a function f : X -> 2 that minimizes the expected loss: E_{x,y,y1,...,yK ~ D}[1(y != f(x))]. Importantly the loss doesn't care about y1...yK. However, we typically assume that y1...yK are related to the x -> y mapping.

Without assumptions on the SP loss or output space Y, SP subsumes MTL. For instance, in sequence labeling, we can think of a multitask learning problem as a sequence labeling problem where we only care about the label of the first word. This reminds me of some results that suggest that it's really not any easier to predict the first word in a translation than to solve the entire translation problem. This means that we could try to solve an MTL problem by applying, say, a CRF.

One key difference that seems quite important is that results from MTL have suggested that it is easy to get an MTL model that performs better on the first task, but its hard to get a single MTL model that performs well on all tasks simultaneously. For instance, in neural networks, one might want to run 1000 training epochs to do well on task 1, but only 10 or as many as 10000 to do well on one of the other tasks. This implies that it's probably not a good idea to naively apply something like a CRF to an MTL problem. For this reason (and the nature of the loss functions), I feel that SP and MTL are complementary problems.

The application of MTL to time-series data has been reportedly very successful. Time-series data is nice because it naturally provides additional tasks: in addition to predicting the value at time t, also predict at times t+5, t+10 and t+20. During training we have access to these values, but we don't during testing, so we don't have the option of using them as features.

One especially cool thing about this observation is that it applies directly to search-based structured prediction! That is, when attempting to make a prediction about some search step, we can consider future search steps to be related tasks and apply MTL techniques. For instance, when trying to predict the first word in a translation, we use the second and third words as related tasks. I, personally, think this would be quite a cool research project.

So my tentative conclusions are: (1) SP can solve MTL, but this is probably not a good idea. (2) MTL can be applied to search-based SP and this probably is a good idea. (3) SP and MTL should not be considered the same problem: the primary difference is the loss function, which is all important to SP, but not so important to MTL. That said, SP algorithms probably do get a bit of gain from the "good internal representation" learned in an MTL setting, but by trying to learn this representation directly, we could probably do much better.

NLP is an Engineering Discipline?

At my graduation ceremony this past week, Dean Yannis Yortsos gave a short speech, in which he quoted someone famous (I've already forgotten who it was) at the Engineering graduation segment, saying something akin to "Science is the study of what the world is; Engineering is making something the world has never seen before." This comment had a fairly significant effect on me. However, when thinking about it in the context of NLP, it seems that NLP is an Engineering discipline, not a scientific one, at least according to the above (implied) definition of the terms.

NLP lives somewhere within the realm of language, statistics, machine learning, and cognitive science (you can include signal processing if you want to account for speech). Let's suppose that NLP is a scientific discipline: then, what aspect of the world does it study? It cannot be language, otherwise we'd be linguists. It cannot be statistics or learning, lest we call ourselves mathematicians. Cognitive science is out or we'd be...well, cognitive scientists. In fact, at least as I've described it in my job talks, NLP is the field that deals with building systems to solve problems that have a language component. This seems to render NLP to fall exclusively within the realm of Engineering.

This observation seems to have several repurcussions. It means, among other things, that we should not attempt to seek theoretical results, unless we are wearing another hat (I often wear the hat of a machine learning person; other people play linguists occasionally). It also means that perhaps we shouldn't complain as much that so much of NLP is system building. It seems that almost by definition, NLP must be system building: we are out to create things that never existed before.

If one, like me, is interested in science---that is, the study of natural things in the world---it also means that we had better find some related topic (machine learning, cognitive science or linguistics) to study simultaneously.

ICML Accepted Papers Up

See here. I'm excited to see:

• Bayesian Multi-Population Haplotype Inference (Xing, Sohn, Jordan + Teh)
• Constructing Informative Priors using Transfer Learning (Raina, Ng + Koller)
• Disciminative Unsupervised Learning of Structured Predictors (Xu, Wilkinson, Southey + Schuurmans)
• Maximum Margin Planning (Ratliff, Bagnell + Zinkevich)
• Pachinko Allocation (Li + McCallum)
• Semi-supervised Learning for Structured Output Variables (Brefeld + Scheffer)
• Topic Modeling: Beyond Bag-of-Words (Wallach)

Making Humans Agree

The question of human agreement came up recently. As background, the common state of affairs in NLP when someone has decided to work on a new problem is to ask two (or more) humans to solve the problem and then find some way to measure the inter-annotator agreement. The idea is that if humans can't agree on a task, then it is not worth persuing a computational solution. Typically this is an iterative process. First some guidelines are written, then some annotation is done, then more guidelines are written, etc. The hope is that this process converges after a small number of iterations. LDC has made a science out of this. At the very least, inter-annotator agreement serves as a useful upper bound on system performance (in theory a system could do better; in practice, it does not).

There are two stances one can take on the annotator agreement problem, which are diametrically opposed. I will attempt to argue for both.

The first stance is: If humans do not agree, the problem is not worth working on. (I originally wrote "solving" instead of "working on," but I think the weakened form is more appropriate.) The claim here is that if a problem is so ill-specified that two humans perform it so differently, then when a system does it, we will have no way of knowing if it is doing a good job. If it mimics one of the humans, that's probably okay. But if it does something else, we have no idea if human N+1 might also do this, so we don't know if its good or bad. Moreover, it will be very difficult to learn, since the target concept is annotator-specific. We want to learn general rules, not rules specific to annotators.

The second stance is: If humans do agree, the problem is not worth working on. This is the more controversial statement: I have never heard anyone else ever make it. The argument here is that any problem that humans agree on is either uninteresting or has gone through so many iterations of definitions and redefinitions as to render it uninteresting. In this case, the annotation guidelines are essentially an algorithm that the annotator is executing. Making a machine execute a similar algorithm is not interesting because what it is mimicing is not a natural process, but something created by the designers. Even without multiple iterations of guidelines, high human agreement implies that the task being solved is too artificial: personalization is simply too important of an issue when it comes to language problems.

My beliefs are somewhere in the middle. If humans cannot agree at all, perhaps the problem is too hard. But if they agree too much, or if the guidelines are overly strict, then the problem may have been sapped of its reality. One should also keep in mind that personalization issues can render agreement low; we see this all the time in summarization. I do not think this necessarily means that task should not be worked on: it just means if worked on, it should be a personalized task. Measuring agreement in such cases is something I know nothing about.

Search-based Structured Prediction

I normally would not make a post such as this one (my blog is not my advertisementsphere), but given that it is unlikely this paper will appear in a conference in the near future (and conferences are just ads), I decided to include a link. John, Daniel and I have been working on an algorithm called Searn for solving structured prediction problems. I believe that it will be useful to NLP people, so I hope this post deserves the small space it takes up.

Supervised Hidden Variable Models

Hidden variable models have been extremely successful in unsupervised NLP problems, such as the famous alignment models for machine translation. Recently, two parsing papers and a textual entailment paper have applied hidden variable techniques to supervised problems. I find this approach appealing because it allows one to learn hidden variable models that are (hopefully) optimal for the end goal. This contrasts with, or example, unsupervised word alignment, where it is unclear if the same alignment is good for two different tasks, for instance translation or projection.

The question that interests me is "what exactly are hidden variables in these models?" As a simple example, let's take the following problem: we have an English sentence and an Arabic sentence and we want to know if they're aligned. Dragos has a paper that shows that we can do a good job of making this determination if we do the following: construct an alignment (using, eg., GIZA++) and then compute features over the alignment (length of aligned subphrases, number of unaligned words, etc.). One can imagine similar models for textual entailment, paraphrase identification, etc.

I would ideally like to learn the alignments as part of training the classifier, treating them essentially as hidden variables in the supervised problem.

So what happens in such a model? We learn to produce alignments and then define features over the alignments. From an information theoretic perspective, we needn't bother with the alignments: we can just define features on the original sentence pair. Perhaps these features will be somewhat unnatural, but I don't think so. To build the alignments, we'll have features like "the word 'man' is aligned to the word 'XXX'" (where 'XXX' is Arabic for 'man'). Then on top of this we'd have features that count how many words are successfully aligned. It's somewhat unclear if this is much more than just including all word pair features for a pure classification technique.

The key difference appears to be in the fact that we impose a strong constraint on the alignments. For instance, that they are one-to-one or one-to-many or something similar. This significantly reduces the number of features that are fed into the classifier.

At the same time, the hidden variable models look a lot like introducing a hidden layer into a neural network! Consider a drastic simplification of the parallel sentence detection problem (which is, in the end, just a binary classification problem). Namely, consider the XOR problem. As we all know, we can't solve this with a linear classifier. But if we add a hidden variable to the mix, we can easily find a solution (eg., the hidden variable indicates left-versus-right and then conditional on this, we learn two separate classifiers, one pointing up and one pointing down). This is exactly what a two layer neural net (i.e., one hidden layer) would do!

From this perspective, it seems one can argue that hidden variable models are simply increasing the model complexity of the underlying learner. This comes at a cost: increased model complexity means we either need more data or stronger prior information. Hidden variable models --- more precisely, the constraints present in hidden variable models --- seem to provide this prior information.

Getting Started in NLP

Since starting the blog, a few people have asked me how one can get started in NLP, while residing in a department lacking NLP researchers. This is a difficult question: I fell into NLP quite naturally when I was at CMU and made an easy transition to grad school at USC, both of which have awesome NLP groups. Lacking such internal support, one has to be much more ambitious to get to the point where one could do real research in the field. The obvious avenues for support are: reading books (which ones?) and papers (from where and by whom?), going to nearby conferences (which ones?) and experimentation (on what?). (New option: read and post to this blog!)

The four standard books in the field are Statistical NLP (Manning + Schutze), Speech and Language Processing (Jurafsky + Martin), Statistical Language Learning (Charniak) and Natural Language Understanding (Allen). The latter two are much older, though some people prefer Charniak to Manning + Schutze. I would probably pick up Manning + Schutze if I could only buy one. From this book, I think that skimming Chapters 1, 4, 6 and 13 should give a reasonable (but not uniformly sampled) representation of background knowledge everyone should know. Unfortunately, this misses many topics: information extraction, summarization, question answering, dialog systems, discourse, morphology, ontologies, pragmatics, semantics, sentiment analysis and textual entailment.

Finding good papers for beginners is hard. Without guidance, skimming titles and abstracts of papers published in ACL, NAACL, HLT or COLING since 2002 or 2003 should enable someone to find out what looks interesting to them. I know many advisors take this approach with new students. The ACL anthology is great for finding old papers. I'll probably post at a later date about what are the "must reads" for the areas I know best. Once you've found a few papers you like, I'd check out the respective author's web pages and see if they have any related work (best bet is probably to look at the advisor's page: often s/he will have multiple students working on similar topics). Also, advisor's often have course material and slides from tutorials: these are great places to get introductory-level material.

If you happen to get lucky (I never have) and one of the above conferences is located nearby, I'd just go. Presentations of papers (if they're good) are often better from the perspective of getting the high-level overview than the papers themselves, since papers have to be technically complete.

I'm perhaps overcommitting myself, given my promise to talk more about structured prediction, but over the next few weeks/months, I'll work on a "Getting Starting in X" series. X will likely range over the set { summarization, sequence labeling, information extraction, machine translation, language modeling }. Requests for other topics will be heard, keeping in mind I'm not an expert in many areas.

Google Beta SMT System

Is online, with a description here..

I can only judge fluency/reasonableness, not faithfullness to the input, but of the three AJ pages I tried, one came out reasonably (I could get the gist, sort of) and one came out quite poorly. Better, I'd say, on average than Babelfish's implementation of Asian anything to English, but probably worse than Babelfish's French to English (which has been cooking for ages).

It's unfortunate that there aren't Bleu scores posted for the standard test sets, though it wouldn't be too hard to run these, if someone has the test data. (The results Franz linked to are probably not the same system, since the system they submitted to the eval last year took fourty machine hours to translate a sentence. Google engineers are good, but...) If someone would run the test set, I'd be eternally grateful (and very curious). Given that this is free, NIST may run it as a baseline for the NIST MT eval and the GALE eval, which could have substantial impact on the community, if it is any good.

Please Pass the Pragmatics

I've spent the last few weeks (lots of plane trips) reading Pragmatics by Levinson et al. Pragmatics is a difficult to define field (like many :P), but from a linguistic perspective, it is roughly "the study of the ability of language users to pair sentences with contexts in which they would be appropriate." (pg 24)

The book talks about five aspects of pragmatics:

1. Deixis: methods of directly encoding context into language; "Meet me here a week from now with a stick about this big." (pg 55) Without knowing the context, we cannot know the meanings of me, now (and hence a week from now), this big. Diectic pronouns are pronouns that reference speaker- and hearer-known context.
   
2. Implicature: Grice's theory says that a speaker should: be cooperative, be truthful (quality), be informative (quantity), be relevant, and be perspicuous (manner: avoid obscurity and ambiguity, be brief and orderly). (pgs 101-102) This theory is insufficient, but useful. Implicature also includes notions of quantification (perhaps, some, many, etc.) and metaphors.
   
3. Presupposition: roughly describes that which is immediately inferrable but not the new information in an utterance. Eg., "Sue cried before she finished her thesis" presupposes that Sue finished her thesis, but this is not the new information (which is that she cried). (pg 187) There are both semantic and pragmatic presuppositions; the latter involve shared knowledge between speaker and hearer. (For fun, compare "Sue died before she finished her thesis.")
   
4. Speech Acts: a speech act is a statement that does something rather than just one that says something (eg., "I declare war on Zanzibar." (pg 228)). The basic question of speech acts seems to be that of identifying them and understanding how they differ from normal statements.
   
5. Conversational Structure: analysis of the sequential (and anti-sequential) nature of conversations, interruptions, etc.

I find implicature and presupposition fascinating, because this is essentially where hidden meaning comes out in text. (See, here I've presupposed that hidden meaning is fascinating!) I've really seen very few papers that look at computational aspects of these problems (speech acts and conversational structure may be exceptions). The textual entailment work, as far as I can tell, focuses on semantic implication rather than pragmatic implication, though of course this is related (but much easier, I would imagine!).

One immediate question is whether there is an appliation that demands pragmatic understanding (or, say, understanding of pragmatic implicature and presupposition). This, I'm not sure. I'm curious how divergent pragmatic issues are crosslingually. My hunch is "not much" which implies that this is not necessary for translation purposes (though Czech morphologically encodes for the new/old distinction). IR and IE also seem impervious to the pragmatic hammer. I can come up with artificial situations that suggest QA might benefit, but I feel these are too artificial (i.e., "Did Sue finish her thesis?"). Even summarization seems fairly robust to a lack of pragmatic understanding, although the "new/old" issue is important here. Perhaps what is old in the real discourse is not new for the reader of the summary. But if it just comes through as presupposition, it's unclear that anything is lost. I'm at something of a loss here, because it seems like human conversation has pragmatic influences so deeply embedded that it is surprising that I feel we can do without them for NLP problems.

Unsupervised Learning: Why?

Unsupervised learning is very popular for NLP problems, including MT, summarization, IE, etc. I've done work in this area, as have many other people. Beginning about 6 months ago, I have been asking myself: should we ever really do unsupervised learning?

This question may seem silly, but there is a fairly compelling argument. The argument is that, regarless of whether we are in academia or industry, we will have to convince someone else that our system is doing a good job. In order to do this, we need evaluation data. Which means we need to annotate. But once we've annotated, at the very least we should do semi-supervised learning, not unsupervised learning.

The problem with this argument is that it presupposes the existence of an automatic evaluation metric.

My newly formed perspective is the following. We should only do unsupervised learning if we do not have a trustworthy automatic evaluation metric (i.e., a Type III metric). I cannot currently think of a compelling argument against this.

Rexa is Live

http://rexa.info

(More info here, including a post by Andrew McCallum, the man behind the machine!)

SIGIR Program Up

The SIGIR program has been posted. I'm looking forward to:

• Learning User Interaction Models (Agichtein, Brill, Dumais, Rango)
• Improving the Estimation of Relevance Models (Diaz, Metzler)
• LDA-based Document Models (Wei, Croft)
• Tackling Concept Drift by Temporal Inductive Transfer (Forman)
• Large Scale Semi-supervised Linear SVMs (Sindhwani, Keerthi)

One thing that surprises me is the distribution of industry labs' papers. There are 12 papers with at least one Microsoft author, four for IBM, but only one each for Yahoo and Google (and the Google one was work done while the relevant author was at IBM, I believe). Does MSR just encourage publication more? Or is it more closely tied to SIGIR (SIGIR is in Seattle this year)? Or did Yahoo and Google just get unlucky with reviews?

Unlabeled Structured Data

I'll skip discussion of multitask learning for now and go directly for the unlabeled data question.

It's instructive to compare what NLPers do with unlabeled data to what MLers do with unlabeled data. In machine learning, there are a few "standard" approaches to boosting supervised learning with unlabeled data:

1. Use the unlabeled data to construct a low dimensional manifold; use this manifold to "preprocess" the training data.
2. Use the unlabeled data to construct a kernel.
3. Use the unlabeled data during training time to implement the "nearby points get similar labels" intuition.

There are basically two common uses of unlabeled data in NLP (that I can think of):

1. Use the unlabeled data to cluster words; use these word clusters as features for training.
2. Use the unlabeled data to bootstrap new training instances based on highly precise patterns (regular expressions, typically).

Why the discrepancy? I think it partially that the ML techniques are relatively new and developed without thinking about language problems. For instance, most manifold learning techniques work in mid-dimensional, continuous space, not uber-high-dimensional sparse discrete space. Moreover, most of the ML-style techniques scale as O(N^3), where N=# of unlabeled points. This is clearly far far too expensive for any reasonable data set. For the converse, NLP semi-sup techniques are very tied to their domain, and don't generalize well.

The paper that's been getting a lot of attention recently -- on both sides -- is the work by Ando and Zhang. As I see it, this is one way of formalizing the common practice in NLP to a form digestible by ML people. This is great, because maybe it means the two camps will be brought closer together. The basic idea is to take "A" style NLP learning, but instead of clustering as we normally think of clustering (words based on contexts), they try to learn a classifier that predicts known "free" aspects of the unlabeled data (is this word capitalized?). Probably the biggest (acknowledged) shortcoming of this technique is that a human has to come up with these secondary classification problems. Can we try to do that automatically?

But beyond standard notions of supervised -> semi-supervised -> unsupervised, I think that working in the structured domain offers us a much more interesting continuum. Maybe instead of having some unlabeled data, we have some partially labeled data. Or data that isn't labeled quite how we want (William Cohen recently told me of a data set where they have raw bio texts and lists of proteins that are important in these texts, but they want to actually find the names in unlabeled [i.e., no lists] texts.) Or maybe we have some labeled data but then want to deploy a system and get user feedback (good/bad translation/summary). This is a form of weak feedback that we'd ideally like to use to improve our system. I think that investigating these avenues is also a very promising direction.

What is Structured Prediction?

It is surprisingly difficult to concretely define structured prediction. The root of the question is: what does it mean for a problem to be structured. A very reasonable condition seems to be the following:

Condition 1: Output elements decompose into variable length vectors over a finite set.

This notion of decomposition is fairly ubiquitous (it subsumes things like sequence labeling, parsing, MT, protein folding, etc.). Unfortunately, it does not seem sufficient. Requiring only C1 means that problems like binary classification, multitask learning and other clearly non-structured problems fall under the heading of SP. It also doesn't stress the fact that there's some relation between the elements of these vectors.

There are, it seems, essentially two places to introduce dependence between elements in the output vectors: the features or the loss. This leads to two new conditions:

Condition 2-Feat: The feature function does not decompose over any vector representation of the output.

Condition 2-Loss: The loss function does not decompose over any vector representation of the output.

(For both of these, by "does not decompose" I mean that it is not invariant under permutations of the output vector. For example, in sequence labeling world, Hamming loss does decompose.)

In some sense, C2-Loss subsumes C2-Feat. This is because it is reasonable to believe that if the loss function doesn't decompose, then we will need/want to introduce features that span at least as much of the "nondecomposition" of the output vector as the loss. For instance, in sequence labeling under a second-order Hamming loss (accuracy on adjacent labels, which does not decompose), one would presumably want to use bigram-style features.

By mixing and matching these conditions, we obtain several different notions of structured prediction.

Condition 1 alone leads to fully decomposable problems and for these we can use independent classifiers ala Dan Roth and others.

Condition 1 and Condition 2-Feat is the standard interpretation of structure prediction and leads to, among other things, max-margin Markov nets.

Condition 1 and Condition 2-Loss is my preferred interpretation and leads to, as far as I know, no published work (though we have a paper at Snowbird on it, and something conditionally accepted at ICML).

Given that 1 and 2-Feat is standard, I have some desire to defend my interpretation. To me, the 1+2-Feat interpretation is specifying SP as a solution, not a problem. That is, the world doesn't force us to use structure: we simply do so because we believe structured features will be useful. On the other hand, when the loss function doesn't decompose, the world is essentially telling us that we had really better pay attention to the structure. We can't reasonably assume to do well otherwise. I like to define problems in terms of what the world gives us, not what we create for ourselves.

My interpretation successfully excludes problems like multiclass classification and multitask learning from the realm of structured prediction. Interestingly, it also excludes sequence labeling under Hamming loss and collective classification (ala statistical relational learning). I don't see this as necessarily a bad thing. Especially since this definition now includes problems I care about like MT, summarization, ASR, etc. under any reasonable loss function. (Any reasonable loss function will not decompose.)

Heuristics

Deepak brings up a great discussion topic that really needs its own post. Hopefully I'll catch this here before anyone continues to reply there (don't). The basic question is this:

Why cannot people simply use heuristicy and hackery approaches that have been proven over years to work well?

Deepak's point, which I think is well taken and should not be forgotten, is that a simple "hacky" thing (I don't intend "hacky" to be condescending...Deepak used it first!) often only does at most epsilon worse than a mathematically compelling technique, and sometimes even better. I think you can make a stronger argument. Hacky things allow us to essentailly encode any information we want into a system. We don't have to find a mathematically convenient way of doing so (though things are better now that we don't use generative models for everything).

I think there are several responses to these arguments, but I don't think anything topples the basic point. But before I go into those, I want to say that I think there's a big difference between simple techniques and heuristicy techniques. I am of course in favor of the former. The question is: why shouldn't I just use heuristics. Here are some responses.

1. That's just how I am. I studied math for too long. It's purely a personal choice. This is not compelling on a grand scale, but at a personal level, it is unlikely one will do good research if one is not interested in the topic and approach.
   
2. We don't want to just solve one problem. Heuristic techniques are fantastic for solving a very particular problem. But they don't generalize to other similar problems. The extent to which they don't generalize (or the difficulty to force generalization) of course varies.
3. Similar to #2, I want a technique that can be described more briefly than simply the source code. Heuristic techniques by definition cannot. Why? I'd like to know what's really going on. Maybe there's some underlying principle that can be applied to other problems.
4. Lasting impact. Heuristics rarely have lasting (scientific) impact because they're virtually impossible to reproduce. Of course, a lasting impact for something mathematically clever but worthless is worse than worthless.

There are probably others that other people can come up with.

That's my general perspective. In response to specific issues Deepak brought up:

...a more complicated model gives very little improvements and generally never scales easily.

I think it's worthwhile separating the problem from the solution. The issue with a lot of techniques not scaling is very true. This is why I don't want to use them :). I want to make my own techniques that do scale and that make as few assumptions as possible (regarding features, loss, data, etc.). I think we're on our way to this. Together with John and Daniel, we have some very promising results.

...working on such (SP) problems means getting married more to principles of Machine Learning than trying to make any progress towards real world problems.

I, personally, want to solve real-world problems. I cannot speak for others.

...a lot of lot of smart (young?) people in the NLP/ML community simply cannot admit the fact that simple techniques go a long way...

This is very unfortunate if true. I, for one, believe that simple techniques do go a long way. And I'm not at all in favor of using a steamroller to kill a fly. But I just don't feel like they can or will go all the way in any scalable manner (scalable in O(person time) not O(computation time)). I would never (anymore!) build a system for answering factoid questions like "how tall is the empire state building?" that is not simple. But what about the next level "how much taller is the empire state building than the washington monument?" Okay, now things are interesting, but this is still a trivial question to answer. Google identifies this as the most relevant page. And it does contain the necessary information. And I can imagine building heuristics that could answer "how much Xer is X that Y" based on asking two separate questions. But where does this process end? I will work forever on this problem. (Obviously this is just a simple stupid example which means you can find holes in it, but I still believe the general point.)

Yesterday was Structured Learning Day

I'm out in Chicago at the atomic learning workshop and yesterday was structured prediction day. There were a lot of cool talks on pretty much all the major SP techniques: Charles talked about efficient training of CRFs, Yasemin talked about semi-supervised learning in M3Ns and SVMISOs, Ben talked about efficient training of M3Ns for combinatorial-style problems (like word alignment), Drew talked about planning as a SP problem, Vasin talked about the tradeoffs of local vs. global inference in SP, and I of course talked about search.

I really enjoyed Drew's talk. He is considering the problem of robot navigation, which is typically handled using A* search and some very crafty hand-written heuristic rules for generating the cost map over which A* search runs. He wants to get rid of the crafty part and replace it with learning. The idea is simple and cute: use observed features the robot receives to learn to produce a cost map so that when A* runs it finds the right path. Here, he defines the right path by having a human remote control the robot and drive it to the correct place. He casts this as a max-margin problem and solves it using very fast subgradient methods. There's no paper on this yet, but if all goes well there will be soon. I think there's a lot of stuff here that could strongly influence how we think about SP.

There were many questions raised at the workshop that I deserve significant thought. These include:

1. What is structured learning?
2. How does structured learning related to multi-task learning (ala Rich Caruana and others)?
3. What sort of techniques are there for dealing with un- or partially-labeled data for structured learning?
4. What can be done about featuritis (i.e., throwing in all possible features)? Also: Is this a legitimate concern?
5. How important is it what loss function we optimize?
6. When is local learning enough (ala Dan Roth) and when must you do "global learning?"
7. What training techniques scale sufficiently?

Almost all of these questions deserve separate posts, and of course they are non-independent. Modulo feedback, I'll probably start at the top and work my way down. (Of course, if John beats me to it, I'll just post on his blog and cross-link here.)

Viterbi Search is Not Magic

This post is about the use of Viterbi search in NLP applications. Skip the next paragraph if you recall readily how VS works.

The easiest formulation of VS is for a sequence labeling problem: given an input x, find a label vector y1,...,yN that maximizes the score [ f(x,y0,y1) + f(x,y1,y2) + ... + f(x,y{N-1},yN) ]. (Here, y0 is some special <s> symbol.) When there are K possible values for each label, VS solves this by filling in a dynamic programming matrix a of size (N+1)*K, where a(0,k) is zero if k is <s> and negative infinity otherwise. Recursively, a(n+1,k') is [ max_k [ a(n,k) + f(x,k,k') ] ]. The largest a(N+1, . ) gives the highest score; by storing backpointers (which k was the largest) in another matrix, we can recover the whole sequence once we reach the end. This runs in time O(NK^2), as opposed to O(N^K) as a naive implementation would run.

I am becoming somewhat notorious for not using Viterbi search, even for sequence labeling problems (ironic, given that I am part of the Viterbi School of Engineering). The purpose of this post is to show that this is not unreasonable.

My evolving feeling on this has two angles:

1. Viterbi is good for something like an HMM where we can't model the whole input as features and so we need to talk back-and-forth via Viterbi. But when we get to use any feature at any time (as in any modern model), this advantage goes away.
2. I think people ascribe some "magic" to Viterbi. At least in NLP, the Viterbi algorithm and its generalizations (inside-outside, etc.) are treated as stand alone units. They're not. They're simply based on the observation that under certain constraints, when executing search, one can do efficient memoization. If you throw away the "magic" of Viterbi and treat it as jsut another search algorithm, you see that there's nothing special there.

I have a hard time convincing people of 2. I'm not quite sure why. I almost liken it to trying to convince a classically trained logician the ways of constructive logic are right (being one of the former, I'm not yet convinced). The problem is that we're so used to seeing VS as this very special array-filling operation that we forget what's really going on. We could just as easily do search and store stuff in a hash table. It wouldn't be quite as efficient, but complexity wise (assuming O(1) access to the table), it would be the same.

The "magic" of Viterbi is that it efficiently integrates all information from the different sources assuming that the conditional independences hold and assuming that all conditional probabilities are correctly estimated. But we know this is not the case.

That said, I think there is something to be said for later decisions being able to influence earlier ones. But I don't take this as given. And I don't think it's always the case. This is a big open question for me. By using a more complex search algorithm, you're forcing more decisions to be made but are (we hope) making these decisions easier. This is a trade-off. One angle is not a priori better than the other.

Snowbird Accepted Papers Up

The list of accepted papers for the Snowbird Learning Workshop is up. I'm interested to see:

• Training CRFs with SMD (Vishwanathan, Shraudolph, Schmidt + Murphy)
  
• Sub-gradient method structured learning (Bagnell, Ratliff + Zinkevich)
• AdaBoost is MaxEnt over the error distribution (Haffner)
• Structural correspondences for transfer learning (Blitzer, Crammer, McDonald + Pereira)
• Rule-extraction from SVMs (Braun + Buhmann)
• Prior beliefs in SSL (Luxburg + Ben-David)
• Model compression (Caruana, Bucila + Niculescu-Mizil)

Is X useful for Y?

This post has two parts, both addressing the issue of showing that one task (X) is useful for another task (Y); eg., syntax is useful for MT, or WSD is useful for IR, or ....

The first question is: on whom is the onus of making such an argument. (I'm presupposing that it makes sense to make such an argument.) There are three options: (1) a person who does X; (2) a person who does Y; a third party. Arguments in favor of 1: if I work on a task, I am likely to want to justify its importance. For 2: I know the most about Y, so if X is useful, I can probably get it to work; also, other (2)s are more likely to buy my results. For 3: ???.

One could argue (3) to be (more) unbiased, but I'll make an idealized assumption that (1) and (2) care about furthering science, not some personal research program. Given that, I think the best case scenario is to have a joint authored paper between a (2) and a (1); that failing, I'd probably prefer a paper by a (2). I'd prefer it not from a potential bias perspective, but because a (2) is more likely to produce a Y-system that's state-of-the-art, so showing that X improves on this is going to be more convincing. Of course if a (1) can do that, that's fine too.

The second issue that I see is that in a lot of cases it's not cut and dry. Take for example a recent paper that showed that syntax is useful for EDT. I believe this paper is probably right, given the maturity of the system into which syntax was added. However, take my EDT system. I worked on this for about 15 months not using syntax. I used all sorts of crazy features. If I add syntax (which I've done), it improves things a little. Not a lot. And only for coref, not for mention tagging. Why? Likely, I've engineered around having syntax. If I had added syntax at the beginning, maybe I could have done away with many of the other features I have. We see the same thing in IR: if some complex NLP technique seems to improve IR systems but is expensive to run, then often people will keep tearing it apart until they find some tiny little feature that's doing all the important work. If so, can we still say that the original task helped?

I think, given this, there is a better way to measure the usefulness of X to Y other than: X improved Y's performance. Consider someone setting out to build an EDT system. They want to know whether they should include syntax or not. The real question is: assuming I get comparable performance, is it easier to include syntax or to engineer around it. I don't know how to measure this automatically (lines of code is perhaps a reasonable surrogate, assuming the same coder writes both), but it seems like such a measure would be much more useful and telling than whether or not performance on an arbitrary system goes up.

HLT-NAACL Program Up

The program for HLT-NAACL 2006 has been posted (I didn't submit anything). I'm partcularly looking forward to:

• A fast finite-state relaxation method (Tromble + Eisner)
• Name matching in English and Arabic (Freeman, Condon + Ackerman)
• Do we need phrases? (Quirk + Menezes)
• Using syntax for false entailment (Snow, Vanderwende + Menezes)
• Grammatical machine translation (Riezler + Maxwell)
• SRL, Wornet and Wikipedia for Coreference (Ponzetto + Strube)

I'm sure others will be good too. Anyone see anything else especially intruiging?