S.R.K. Branavan

I graduated from MIT in February of 2012, and now run a small research group applying NLP and Machine Learning to the software engineering process at MillenniumIT. I am also still actively involved in NLP research for its own sake.

I did my PhD under the guidance of  Prof. Regina Barzilay.

I can be contacted at branavan@csail.mit.edu.

Grounding Linguistic Analysis in Control Applications  Ph.D. Thesis

S.R.K. Branavan. MIT, February 2012

Paper    Slides    Code & Data

Abstract: This thesis addresses the problem of grounding linguistic analysis in control applications, such as automated maintenance of computers and game playing. We assume access to natural language documents that describe the desired behavior of a control algorithm, either via explicit step-by-step instructions, via high-level strategy advice, or by specifying the dynamics of the control domain. Our goal is to develop techniques for automatically interpreting such documents, and leveraging the textual information to ectively guide control actions. We show that in this setting, langauge analysis can be learnt ectively via feedback signals inherent to the control application, obviating the need for manual annotations. Moreover we demonstrate how information automatically acquired from text can be used to improve the performance of the target control application. We apply our ideas to three applications of increasing linguistic and control complexity { interpreting step-by-step instructions into commands in a graphical user interface; interpreting high-level strategic advice to play a complex strategy game; and leveraging text descriptions of world dynamics to guide high-level planning. In all cases, our methods produce text analyses that agree with human notions of correctness, while yielding significant improvements over strong text-unaware methods in the target control application.

Learning High-Level Planning from Text  ACL 2012

S.R.K. Branavan, Nate Kushman, Tao Lei, Regina Barzilay.

Paper    Slides    Code & Data

Abstract: Comprehending action preconditions and effects is an essential step in modeling the dynamics of the world. In this paper, we express the semantics of precondition relations extracted from text in terms of planning operations. The challenge of modeling this connection is grounding language at the level of relations. This type of grounding enables us to create high-level plans based on language abstractions. Our model jointly learns to predict precondition relations from text and to perform high-level planning guided by those relations. We implement this idea in the reinforcement learning framework using feedback automatically obtained from plan execution attempts. When applied to a complex virtual world and text describing that world, our relation extraction technique performs on par with a supervised baseline, yielding an F-measure of 66% compared to the baseline's 65%. Additionally, we show that a high-level planner utilizing these extracted relations significantly outperforms a strong, text unaware baseline as measured by completed plans - successfully completing 80% as compared to 69% for the baseline.

Learning to Win by Reading Manuals in a Monte-Carlo Framework  JAIR, 2012, volume 43

S.R.K. Branavan, David Silver, Regina Barzilay.

Paper    Code & Data

Abstract: Domain knowledge is crucial for effective performance in autonomous control systems. Typically, human effort is required to encode this knowledge into a control algorithm. In this paper, we present an approach to language grounding which automatically interprets text in the context of a complex control application, such as a game, and uses domain knowledge extracted from the text to improve control performance. Both text analysis and control strategies are learned jointly using only a feedback signal inherent to the application. To effectively leverage textual information, our method automatically extracts the text segment most relevant to the current game state, and labels it with a task-centric predicate structure. This labeled text is then used to bias an action selection policy for the game, guiding it towards promising regions of the action space. We encode our model for text analysis and game playing in a multi-layer neural network, representing linguistic decisions via latent variables in the hidden layers, and game action quality via the output layer. Operating within the Monte-Carlo Search framework, we estimate model parameters using feedback from simulated games. We apply our approach to the complex strategy game Civilization II using the official game manual as the text guide. Our results show that a linguistically-informed game-playing agent significantly outperforms its language-unaware counterpart, yielding a 34% absolute improvement and winning over 65% of games when playing against the built-in AI of Civilization.

Learning to Win by Reading Manuals in a Monte-Carlo Framework  ACL 2011

S.R.K. Branavan, David Silver, Regina Barzilay.

Paper    Slides    Code & Data

Abstract: This paper presents a novel approach for leveraging automatically extracted textual knowledge to improve the performance of control applications such as games. Our ultimate goal is to enrich a stochastic player with highlevel guidance expressed in text. Our model jointly learns to identify text that is relevant to a given game state in addition to learning game strategies guided by the selected text. Our method operates in the Monte-Carlo search framework, and learns both text analysis and game strategies based only on environment feedback. We apply our approach to the complex strategy game Civilization II using the official game manual as the text guide. Our results show that a linguistically-informed game-playing agent significantly outperforms its language-unaware counterpart, yielding a 27% absolute improvement and winning over 78% of games when playing against the builtin AI of Civilization II.

Non-Linear Monte-Carlo Search in Civilization II  IJCAI 2011

S.R.K. Branavan, David Silver, Regina Barzilay.

Paper    Code & Data

Abstract: This paper presents a new Monte-Carlo search algorithm for very large sequential decision-making problems. We apply non-linear regression within Monte-Carlo search, online, to estimate a stateaction value function from the outcomes of random roll-outs. This value function generalizes between related states and actions, and can therefore provide more accurate evaluations after fewer rollouts. A further significant advantage of this approach is its ability to automatically extract and leverage domain knowledge from external sources such as game manuals. We apply our algorithm to the game of Civilization II, a challenging multiagent strategy game with an enormous state space and around 1021 joint actions. We approximate the value function by a neural network, augmented by linguistic knowledge that is extracted automatically from the official game manual. We show that this non-linear value function is significantly more efficient than a linear value function, which is itself more efficient than Monte-Carlo tree search. Our non-linear Monte-Carlo search wins over 78% of games against the built-in AI of Civilization II

Reading Between the Lines: Learning to Map High-level Instructions to Commands  ACL 2010

S.R.K. Branavan, Luke Zettlemoyer, Regina Barzilay.

Paper    Slides    Code & Data

Abstract: In this paper, we address the task of mapping high-level instructions to sequences of commands in an external environment. Processing these instructions is challenging—they posit goals to be achieved without specifying the steps required to complete them. We describe a method that fills in missing information using an automatically derived environment model that encodes states, transitions, and commands that cause these transitions to happen. We present an efficient approximate approach for learning this environment model as part of a policy gradient reinforcement learning algorithm for text interpretation. This design enables learning for mapping high-level instructions, which previous statistical methods cannot handle.

Content Modeling Using Latent Permutations  JAIR, 2009, volume 36

Harr Chen, S.R.K. Branavan, Regina Barzilay, David R. Karger.

Paper    Code & Data

Abstract: We present a novel Bayesian topic model for learning discourse-level document structure. Our model leverages insights from discourse theory to constrain latent topic assignments in a way that reflects the underlying organization of document topics. We propose a global model in which both topic selection and ordering are biased to be similar across a collection of related documents. We show that this space of orderings can be effectively represented using a distribution over permutations called the Generalized Mallows Model. We apply our method to three complementary discourse-level tasks: cross-document alignment, document segmentation, and information ordering. Our experiments show that incorporating our permutation-based model in these applications yields substantial improvements in performance over previously proposed methods.

Wikido  HotNets-VIII, 2009

Nate Kushman, Micah Brodsky, S.R.K. Branavan, Dina Katabi, Regina Barzilay, Martin Rinard

Paper

Abstract: The Internet has allowed collaboration on an unprecedented scale. Wikipedia, Luis Von Ahn’s ESP game, and reCAPTCHA have proven that tasks typically performed by expensive in-house or outsourced teams can instead be delegated to the mass of Internet computer users. These success stories show the opportunity for crowd-sourcing other tasks, such as allowing computer users to help each other answer questions like "How do I make my computer do X?". Such a system would reduce IT cost, user frustration, and machine downtime. The current approach to crowd-sourcing IT tasks, however, only allows users to collaborate on generating text. Anyone who goes through the process of searching help wikis and user forums hoping to find a solution for some computer problem knows the inefficacy and the frustration accompanying such a process. Text is ambiguous and often incomplete, particularly when written by non-experts. This paper presents WikiDo, a system that enables the mass of non-expert users to help each other answer how-to computer questions by actually performing the task rather than documenting its solution.

Reinforcement Learning for Mapping Instructions to Actions  ACL 2009  [Best paper award]

S.R.K. Branavan, Harr Chen, Luke Zettlemoyer, Regina Barzilay.

Paper    Slides    Code & Data

Abstract: In this paper, we present a reinforcement learning approach for mapping natural language instructions to sequences of executable actions. We assume access to a reward function that defines the quality of the executed actions. During training, the learner repeatedly constructs action sequences for a set of documents, executes those actions, and observes the resulting reward. We use a policy gradient algorithm to estimate the parameters of a log-linear model for action selection. We apply our method to interpret instructions in two domains—Windows trouble shooting guides and game tutorials. Our results demonstrate that this method can rival supervised learning techniques while requiring few or no annotated training examples.

Global Models of Document Structure Using Latent Permutations  NAACL/HLT 2009

Harr Chen, S.R.K. Branavan, Regina Barzilay, David R. Karger.

Paper    Code & Data

Abstract: We present a novel Bayesian topic model for learning discourse-level document structure. Our model leverages insights from discourse theory to constrain latent topic assignments in a way that reflects the underlying organization of document topics. We propose a global model in which both topic selection and ordering are biased to be similar across a collection of related documents. We show that this space of orderings can be elegantly represented using a distribution over permutations called the generalized Mallows model. Our structure aware approach substantially outperforms alternative approaches for cross-document comparison and single-document segmentation.

Learning Document-Level Semantic Properties from Free-text Annotations  JAIR, 2009, volume 34

S.R.K. Branavan, Harr Chen, Jacob Eisenstein, Regina Barzilay.

Paper    Code & Data

Abstract: This paper presents a new method for inferring the semantic properties of documents by leveraging free-text keyphrase annotations. Such annotations are becoming increasingly abundant due to the recent dramatic growth in semi-structured, user-generated online content. One especially relevant domain is product reviews, which are often annotated by their authors with pros/cons keyphrases such as "a real bargain" or "good value." These annotations are representative of the underlying semantic properties; however, unlike expert annotations, they are noisy: lay authors may use different labels to denote the same property, and some labels may be missing. To learn using such noisy annotations, we find a hidden paraphrase structure which clusters the keyphrases. The paraphrase structure is linked with a latent topic model of the review texts, enabling the system to predict the properties of unannotated documents and to effectively aggregate the semantic properties of multiple reviews. Our approach is implemented as a hierarchical Bayesian model with joint inference. We find that joint inference increases the robustness of the keyphrase clustering and encourages the latent topics to correlate with semantically meaningful properties. Multiple evaluations demonstrate that our model substantially outperforms alternative approaches for summarizing single and multiple documents into a set of semantically salient keyphrases.

Learning Document-Level Semantic Properties from Free-text Annotations  ACL 2008

S.R.K. Branavan, Harr Chen, Jacob Eisenstein, Regina Barzilay.

Paper    Slides    Code & Data

Abstract: This paper demonstrates a new method for leveraging free-text annotations to infer semantic properties of documents. Free-text annotations are becoming increasingly abundant, due to the recent dramatic growth in semistructured, user-generated online content. An example of such content is product reviews, which are often annotated by their authors with pros/cons keyphrases such as “a real bargain” or “good value.” To exploit such noisy annotations, we simultaneously find a hidden paraphrase structure of the keyphrases, a model of the document texts, and the underlying semantic properties that link the two. This allows us to predict properties of unannotated documents. Our approach is implemented as a hierarchical Bayesian model with joint inference, which increases the robustness of the keyphrase clustering and encourages the document model to correlate with semantically meaningful properties. We perform several evaluations of our model, and find that it substantially outperforms alternative approaches.

Generating a Table-of-Contents  ACL 2007

S.R.K. Branavan, Pawan Deshpande, Regina Barzilay.

Paper    Slides    Code & Data

Abstract: This paper presents a method for the automatic generation of a table-of-contents. This type of summary could serve as an effective navigation tool for accessing information in long texts, such as books. To generate a coherent table-of-contents, we need to capture both global dependencies across different titles in the table and local constraints within sections. Our algorithm effectively handles these complex dependencies by factoring the model into local and global components, and incrementally constructing the model’s output. The results of automatic evaluation and manual assessment confirm the benefits of this design: our system is consistently ranked higher than non-hierarchical baselines.

High Compression Rate Text Summarization

S.R.K. Branavan. Master's Thesis, MIT 2008

Paper