Using Semantic Unification to Generate Regular Expressions from Natural Language

Proceedings of NAACL-HLT 2013, pages 826–836, Atlanta, Georgia, 9–14 June 2013. c⃝2013 Association for Computational Linguistics Using Semantic Unification to Generate Regular Expressions from Natural Language Nate Kushman Regina Barzilay Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology {nkushman, regina}@csail.mit.edu Abstract We consider the problem of translating natu- ral language text queries into regular expres- sions which represent their meaning. The mis- match in the level of abstraction between the natural language representation and the regu- lar expression representation make this a novel and challenging problem. However, a given regular expression can be written in many se- mantically equivalent forms, and we exploit this flexibility to facilitate translation by find- ing a form which more directly corresponds to the natural language. We evaluate our tech- nique on a set of natural language queries and their associated regular expressions which we gathered from Amazon Mechanical Turk. Our model substantially outperforms a state- of-the-art semantic parsing baseline, yielding a 29% absolute improvement in accuracy.1 1 Introduction Regular expressions (regexps) have proven them- selves to be an extremely powerful and versatile for- malism that has made its way into everything from spreadsheets to databases. However, despite their usefulness and wide availability, they are still con- sidered a dark art that even many programmers do not fully understand (Friedl, 2006). Thus, the ability to automatically generate regular expressions from natural language would be useful in many contexts. Our goal is to learn to generate regexps from nat- ural language, using a training set of natural lan- guage and regular expression pairs such as the one in Figure 1. We do not assume that the data includes an alignment between fragments of the natural lan- guage and fragments of the regular expression. In- 1The dataset used in this work is available at http://groups.csail.mit.edu/rbg/code/regexp/ Text Description Regular Expression three letter word starting with ’X’ \bX[A-Za-z]{2}\b Figure 1: An example text description and its associated regular expression.3 ducing such an alignment during learning is partic- ularly challenging because oftentimes even humans are unable to perform a fragment-by-fragment align- ment. We can think of this task as an instance of grounded semantic parsing, similar to the work done in the domain of database queries (Kate and Mooney, 2006; Zettlemoyer and Collins, 2005; Kwiatkowski et al., 2010). However, the current success in semantic parsing relies on two impor- tant properties of the data. First, while the past work did not assume the alignment was given, they did assume that finding a fine grained fragment- by-fragment alignment was possible. Secondly, the semantic domains considered in the past were strongly typed. This typing provides constraints which significantly reduce the space of possible parses, thereby greatly reducing the ambiguity. However, in many interesting domains these two properties may not hold. In our domain, the align- ment between the natural language and the regu- lar expressions often happens at the level of the whole phrase, making fragment-by-fragment align- ment impossible. For example, in Figure 1 no frag- ment of the regexp …

Content truncated to 500 words