PhD DEfense by Ashwin K Vijayakumar
Title: Improved Search Techniques for Structured Prediction
Ashwin K Vijayakumar
PhD Student in Computer Science
School of Interactive Computing
Georgia Institute of Technology
Date: Monday, July 6th, 2020
**Note: This defense is remote-only due to the institute's guidelines on COVID-19**
Dr. Dhruv Batra (advisor), School of Interactive Computing, Georgia Institute of Technology
Dr. Devi Parikh, School of Interactive Computing, Georgia Institute of Technology
Dr. Byron Boots, Paul G. Allen School of Computer Science and Engineering, University of Washington
Dr. Prateek Jain, Microsoft Research India,
Dr. Oleksandr Polozov, Microsoft Research AI, Redmond
Dr. Tanmay Rajpurohit, Cora AI, Genpact
Many useful AI tasks like machine translation, captioning or program synthesis to name a few can be abstracted as structured prediction problems. For these problems, the search space is well-defined but extremely large — all English language sentences for captioning or translation and similarly, all programs that can be generated from a context-free grammar in the case of program synthesis. Therefore, inferring the correct output (a sentence or a program) given the input (an image or user-defined specifications) is an intractable search problem. To overcome this, heuristics — hand designed or learnt from data — are often employed. In my work, I propose modified search procedures to output multiple diverse sequences and then, for the task of outputting programs, I propose a novel search procedure that accelerates existing techniques via heuristics learnt from deep networks. Going further, I propose to study the role of memory and search i.e. process each new query with the memory of previous queries — specifically in the context of solving mathematical problems.
In the context of sequence prediction tasks like image captioning or translation, I introduce Diverse Beam Search (DBS), an approximate inference technique to decode multiple relevant and diverse outputs. With the objective of producing multiple sentences that are different from each other, DBS modifies the commonly used Beam Search procedure by greedily imposing diversity constraints. In follow-up work, we directly formulate the task of modeling a set of sequences and propose a trainable search procedure dubbed diff-BS. While both algorithms are task-agnostic, image-captioning is used as the test-bed to demonstrate their effectiveness. In the context of program-synthesis, I propose Neural Guided Deductive Search (NGDS), that accelerates deductive search via learnt heuristics. We find that our approach results in a significant speedup without compromising on the quality of the solutions found. Further, I will discuss the application of this technique in the context of programming by examples and synthesis of hard problems for a given solver.
Next, I study the interplay between memory and search, specifically in the context of mathematical problem solving. Analogical reasoning is a strategy commonly adopted by humans while solving problems i.e. new and unseen problems are solved by drawing parallels to previously seen problems. Inspired by such an approach, I propose to learn suitable representations for “problems” that allows the reuse of solutions from previously seen problems as a building block to construct the solution for the current problem, in a lazy manner.