Computational approaches to problems in Natural Language Understanding and Information Extraction are often modeled as structured predictions – predictions that involve assigning values to sets of interdependent variables. Over the last few years, one of the most successful approaches to studying these problems involves Constrained Conditional Models (CCMs), an Integer Learning Programming formulation that augments probabilistic models with declarative constraints as a way to support such decisions.

I will present research within this framework, focusing on learning and inference issues and, in particular, will present recent results on amortized inference – learning to accelerate inference during the life time of the learning system.

Discriminative methods for learning structured models have enabled wide-spread use of very rich feature representations. However, the computational cost of feature extraction is prohibitive for large-scale or time-sensitive applications, often dominating the cost of inference in the models. Significant efforts have been devoted to sparsity-based model selection to decrease this cost. Such feature selection methods control computation statically and miss the opportunity to fine-tune feature extraction to each input at run-time. We address the key challenge of learning to control fine-grained feature extraction adaptively, exploiting non-homogeneity of the data. We propose an architecture that uses a rich feedback loop between extraction and prediction. The run-time control policy is learned using efficient value-function approximation, which adaptively determines the value of information of features at the level of individual variables for each input. We demonstrate significant speedups over state-of-the-art methods on two challenging datasets. For articulated pose estimation in video, we achieve a more accurate state-of-the-art model that is simultaneously many times faster while using only a small fraction of possible features, with similar results on an OCR task.

Inference tasks over probabilistic graphical models can be reduced to either maximization queries such as “most probable explanation” (MPE) that seek a high probability configuration of the model, or summation queries that compute the marginal distribution over the variables, or a combination such as the MAP queries. These queries are instrumental for both learning the models and for applications using it and while all are NP-hard they are normally solved (mostly approximately) using either message-passing schemes (e.g., the junction-tree algorithm, generalized belief propagation, variable-elimination) or by search (e.g., AND/OR search, MCMC schemes) or by a hybrid of the two.

The focus of this talk is on an extending the single-solution maximization queries into m-best queries. These queries seek to find several high-probability configurations of the model, which can be used to assess the stability or robustness of the “best” configuration and give an idea of the uncertainty associated with optimal solutions. This task is apparently highly relevant in various applications including speech-recognition and vision.

Following a brief overview of state-of the art AND/OR search schemes for MPE and on their use of mechanically generated heuristics such a mini-buckets and linear-relaxation-based soft-arc-consistency ( a version that won the 2011 Pascal competition), I will describe recent m-best algorithms extending both variable-elimination and AND/OR graph search schemes (e.g. AND/OR Branch and Bound). I will analyze, compare and contrast the various schemes and will show, a) that search is superior to pure variable-elimination and b) that Best-First schemes (e.g., m-A*), maintain their principled superiority compared with other search schemes, but practically can fail whenever not sufficient memory is available thus making depth-first branch and bound (m-BB) overall more robust. Finally, c) a simple hybrid of variable-elimination and search is superior from a worst-case analysis point of view. I will discuss extensions of these schemes to approximations and to anytime methods.

Collaboration with: Natasha Flerova, Radu Marinescu and Emma Rollon

Viewed abstractly, many classic problems in natural language processing can be cast as trying to map a complex input (e.g., a sequence of words) to a complex output (e.g., a syntax tree or semantic graph). This task is challenging both because language is ambiguous (learning difficulties) and represented with discrete combinatorial structures (computational difficulties). I will discuss some approaches we've been developing to build learning algorithms that explicitly learn to trade-off accuracy and efficiency, applied to a variety of language processing phenomena. Moreover, I will show that in some cases, we can actually obtain a model that is faster and more accurate by exploiting smarter learning algorithms. And yes, those algorithms come with stronger theoretical guarantees too. This is joint work with Jason Eisner, Jiarong Jiang, He He, Adam Teichert and Tim Vieira.

Researchers in Artificial Intelligence have long studied heuristically guided search in combinatorial search spaces for optimization and constraint satisfaction problems. However, little has been done in the area for structured prediction to leverage those ideas. This talk will review recent work in that direction that develops a new framework for structured prediction called HC-Search. Given a structured input, the framework uses a search procedure guided by a learned heuristic H to uncover high quality candidate outputs and then uses a separately learned cost function C to select a final prediction among those outputs. We can decompose the regret of the overall approach into the loss due to H not leading to high quality outputs, and the loss due to C not selecting the best among the generated outputs. Guided by this decomposition, we minimize the overall regret in a greedy stage-wise manner. Experiments on several benchmark domains show that our approach significantly outperforms the state-of-the-art methods.