Tutorial: Integrating Learning and Search for Structured Prediction
IJCAI-2016, New York City


PDF link


Alan Fern, Oregon State University
Liang Huang, Oregon State University
Jana Doppa, Washington State University (Contact Organizer)

Time and Location

1:45 to 5:30pm in Room 2 on July 11, 2016


Structured Prediction (SP) deals with the task of mapping a structured input (e.g., sequence of words) to a structured output (e.g., sequence of part of speech tags). Many important applications in natural language processing, computer vision, and bio-informatics can be naturally formulated as structured output prediction problems. Some examples are as follows: parsing (predicting the parse tree for a given sentence); information extraction (detecting entity and event mentions from a given text); co-reference resolution (recognizing and resolving co-references of entities and events); machine translation (translating a sentence from one language to another); object detection (detecting objects in a given image); semantic segmentation (labeling each pixel in an image with the corresponding semantic label); object tracking in videos (predicting the tracks of multiple objects in a video); text-to-speech and speech-to-text mapping; and protein structure prediction (predicting the three-dimensional structure of a protein from its amino acid sequence) etc.

Each of these prediction problems has a huge number of possible interpretations or outputs (e.g., many possible part of speech taggings for a sentence). A standard approach to structured prediction is to learn a cost function for scoring a potential output for each input. Given such a cost function and a new input, the output computation involves solving the so-called ``Argmin inference problem,'' which is to find the minimum cost output for the corresponding input. Unfortunately, exactly solving the Argmin inference problem is often intractable (computationally very hard) except for some special cases.

This tutorial will focus on computational frameworks that integrate "learning" and "search" in a principled manner to solve structured prediction problems. 

Outline of the Tutorial

Part 1:  Introduction

Motivation via Diverse Application Domains

Classification to Structured Prediction
Part 2:  Cost Function Learning Framework and Argmin Inference Challenge

Cost Function Learning Algorithms: Generalizations of Classification Algorithms
Key Elements of Cost Function Learning Framework
Generic Learning Framework and Challenges
Focus of Tutorial:
Part 3:  Overview of Search Concepts: Search Space, Search Strategy, Search Control Knowledge etc.

Primitive Search Spaces:
Search Procedures: Best-First Search
Search Control Knowledge
Cost Function
Part 4:  Control Knowledge Learning Framework: Greedy Methods

Control Knowledge Learning Framework
Greedy Methods
Classifier-based Structured Prediction
Easy-First Approach
Part 5:  Control Knowledge Learning Framework: Beam Search Methods

Given a ordered or unordered search space and a cost function, how to learn a heuristic function to quickly guide the search procedure towards low cost terminal states?

General Framework: 3 Choices
Different Instantiations
Part 6:  HC-Search: A Unifying framework for Cost Function Learning and Control Knowledge Learning

Unifying View
HC-Search: Learning Approach
Search Space Design
Engineering Methodology for Applying HC-Search

Relation to Other Methods
Part 7: Future Directions

Background of Presenters

Alan Fern is an Professor of Computer Science at Oregon State University. He received his Ph.D (2004) and M.S (2000) in Computer Engineering from Purdue University under the direction of Robert Givan, and his B.S (1997) in Electrical Engineering from the University of Maine. He received a National Science Foundation CAREER award in 2006, is an associate editor of the Machine Learning Journal, and currently serves on the editorial boards of the Journal of Artificial Intelligence Research and the Artificial Intelligence Journal. His research interests span a range of topics in artificial intelligence, including machine learning and automated planning, with a particular interest in work falling at their intersection. He is also interested in applications of AI, including AI for real-time strategy games and activity recognition from videos of American football and other sports.

Liang Huang is an Assistant Professor of Computer Science at Oregon State University. He was most recently an assistant professor at the City University of New York (CUNY) and a part-time research scientist at IBM T. J. Watson Research Center. He graduated in 2008 from the University of Pennsylvania and has worked as a research scientist at Google and a research assistant professor at USC/ISI. Most of his work develops fast algorithms and provable theory to speedup large-scale natural language processing and structured machine learning. He has received a Best Paper Award at ACL 2008, several best paper nominations (ACL 2007, EMNLP 2008, and ACL 2010), two Google Faculty Research Awards (2010 and 2013), a Yahoo Faculty Research Award (2015), and a University Teaching Prize at Penn (2005). His research has been supported by DARPA, NSF, Google, and Yahoo. He also co-authored a best-selling textbook in China on algorithms for programming contests.

Jana Doppa is an Assistant Professor of Computer Science at Washington State University, Pullman. He earned his PhD working with the Artificial Intelligence group at Oregon State University (2014); and his MTech from Indian Institute of Technology (IIT), Kanpur, India (2006). His general research interests are in the broad field of Artificial Intelligence (AI) and its applications including planning, natural language processing, and computer vision. He received a Outstanding Paper Award for his structured prediction work at the AAAI (2013) conference and a Google Faculty Research Award (2015). His PhD dissertation entitled ``Integrating Learning and Search for Structured Prediction'' was nominated for the ACM Distinguished Dissertation Award (2015). He has organized a successful workshop at ICML (2013) on structured prediction and interactions between inference and learning.