Tutorial: Recent Advances in Structured Prediction
AAAI-2018, New Orleans




Jana Doppa, Washington State University (Contact Organizer)
Liping Liu, Tufts University
Chao Ma, Oregon State University

Tutorial Day 

 Feb 3, 2018


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.

There are several advances in the structured prediction literature including new frameworks, algorithms, theory, and analysis. This tutorial will present a unifying view of all the existing frameworks for solving structured prediction problems; cover recent advances (e.g., search-based structured prediction, amortized inference, PAC theory for inference, multi-task structured prediction, and integrating deep learning techniques with structured prediction frameworks); and point to fertile areas of research from both technical and application point of view.

Background of Presenters

Jana Doppa is an Assistant Professor of Computer Science at Washington State University, Pullman. He earned his PhD working with the Artificial Intelligence (AI) 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 AI and its applications including planning, natural language processing, computer vision, electronic design automation, and databases. 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 Doctoral Dissertation Award (2015). He is a editorial board member of the Journal of Artificial Intelligence Research, and regularly serves on the Program Committee of top-tier conferences including AAAI, IJCAI, ICML, NIPS, AISTATS, ICAPS, and KDD. He taught a tutorial on Structured Prediction at IJCAI-2016 conference, and co-taught tutorials on Energy-Efficient and Reliable 3D Manycore Systems at ICCAD-2016 conference, Data Analytics enables Energy-Efficiency and Robustness: From Mobile to Manycores, Datacenters, and Networks and Adaptive Manycore Architectures for Big Data Computing at Embedded Systems Week-2017 conference.

Liping Liu is an Assistant Professor of Computer Science at Tufts University. He earned his PhD at Oregon State University, held a post-doctoral associate position at Columbia University working with David Blei, and also worked on commercial data analysis at IBM T.J. Watson Research Lab. His research interests include probabilistic modeling, classification, and Bayesian deep learning within machine learning. He also applies these machine learning techniques to ecology studies. He served as a reviewer and PC member for several machine learning conferences and journals.

Chao Ma is a sixth year PhD student with the Artificial Intelligence group at Oregon State University. His general research interests are in Artificial Intelligence and Machine Learning with applications to natural language processing. His PhD thesis focuses of developing computationally-efficient learning and inference techniques to solve multi-task structured prediction problems. He has developed several search-based learning algorithms and published multiple papers at AI and NLP conferences.