Nate Kushman's Home Page

Nate Kushman

Graduate student, CSAIL
Massachusetts Institute of Technology
32 Vassar St.
Cambridge, MA 02139

nkushman at csail DOT mit DOT edu

Office: 32-G484
Tel: (617) 253-0705



I am a Ph.D. student in Electrical Engineering and Computer Science at MIT. My research spans natural language processing and computer systems and I'm advised by both Professor Regina Barzilay and Professor Dina Katabi.

My main focus has been designing and implementing machine learning algorithms which translate natural language descriptions of computer tasks into computer programs that perform these tasks. These algorithms typically take advantage of the semantics of the underlying computer systems in order to produce precise computer programs even though the associated natural language descriptions can be quite complex and ambiguous. I've demonstrated these algorithms in multiple different types of computer systems including: graphical user interfaces, text processing systems, and mathematical data processing tools.




    Research


  • Utilizing Existing Natural Language Documents to Automate Computer Tasks

    As computers have become more powerful and more sophisticated, they have also become more complicated and difficult for humans to use. Most tasks that a user would like to perform, however, are not new, and have already been documented in web forums, wikis or some other form of natural language content. I have built systems which can utilize these existing documents by learning to perform tasks from both step-by-step instructions, as well as from general system documentation without step-by-step instructions.

    Automating Tasks from Step-by-Step
    Natural Lanugage Instructions

    Automating Tasks from Non-Task-Specific
    Natural Language Documentation




  • Performing Tasks Based on Natural Language Goal Descriptions

    When users ask a computer to perform a task, they don’t want to have to provide step-by-step instructions on how to perform it. Instead they would like to simply describe the goal of the task, and let the computer figure out how to perform the task. I have built built systems which enable this for two different domains:

  • Text Processing
    Numerical Computations

    Automating Tasks from Step-by-Step Natural Lanugage Instructions

    This system learns to automatically interpret Microsoft Windows help documents into the required set of clicks and keypresses. It uses a technique which combines reinforcement learning with active learning in order to learn effectively with minimal training data. I also built a complementary system based on programming by demonstration. This second system watches different users perform the task on their own machine, and then builds a single program that can perform that same task on a machine with any configuration. It uses an algorithm which combines static analysis with probabalistic techniques to infer the state and action dependencies and then uses these dependancies to choose the appropriate sequence of actions.



    Publications

    Automating Tasks from Non-Task-Specific Documentation:

    This system automates tasks given only natural language documentation providing a general overview of the system, without any step-by-step instructions. It utilizes the fact that this type of documentation typically describes the set of available actions one can perform, and how those actions update the state of the system. Specifically, sentences in the text are modeled as as describing precondition information. For example, the sentence “add-ons can only be installed when protected mode is turned off” tells us that in order to install an add-on we must first turn off protected mode. We combine this precondition information with classical planning algorithms from the robotics community in order to produce a detailed step-by-step plan for each task.



    Publications

    Text Processing


    This system learns to translate natural language text queries into the regular expressions which represent their meaning. The core of the system is an algorithm which enables effective learning in the face of complicated correspondences between the natural language and the resulting regular expression. When faced with such a complicated correspondence, the system uses a technique based on deterministic finite automata (DFAs) to find another semantically equivalent regular expression which admits a simple mapping to the associated natural language.



    Publications

    Numerical Computations


    This system automatically translates a natural language description of a math problem into a system of equations which can be fed into a symbolic solver. This core of the system is an algorithm which enables effective learning even when the necessary equations are implied, and can only be inferred by considering multiple sentences at once. The algorithm jointly predicts the equations and their alignment with the natural language, allowing a very general space of possible alignments including complex multi-sentence mappings. To manage the search space explosion caused by this general model, the algorithm utilizes the symbolic solver to transform each system of equations into a normal form, which significantly reduces the space of possible interpretations.





    Publications