Abstract
We consider the problem of learning to parse sentences to lambda-calculus representations of their underlying semantics and present an algorithm that learns a weighted combinatory categorial grammar (CCG). A key idea is to introduce non-standard CCG combinators that relax certain parts of the grammar—for example allowing flexible word order, or insertion of lexical items— with learned costs. We also present a new, online algorithm for inducing a weighted CCG. Results for the approach on ATIS data show 86% F-measure in recovering fully correct semantic analyses and 95.9% F-measure by a partial-match criterion, a more than 5% improvement over the 90.3% partial-match figure reported by He and Young (2006).
Introduction
The challenge of semantic parsing involves mapping natural language sentences, such as "flights to Boston," into machine-readable logical forms like $\lambda x.flight(x) \wedge to(x, boston)$. Combinatory Categorial Grammar (CCG) is a popular framework for this task due to its transparent interface between syntax and semantics. However, standard CCG is often too rigid to handle the "telegraphic" and ungrammatical nature of real-world spoken language, where words may be missing or reordered. This paper addresses these limitations by introducing relaxed CCG combinators and an efficient online learning algorithm.
Relaxed CCG Combinators
To handle the variability of natural language, the authors introduce non-standard grammar rules that allow the parser to "bend" when necessary. These include relaxed application and composition rules that ignore the directionality of CCG slashes, facilitating flexible word order. Additionally, type-shifting rules allow the system to hypothesize missing semantic information. For instance, in the phrase "flights boston," the word "from" is missing. A type-shifting rule ($T_R$) can shift the category of "boston" from a noun phrase (NP) to a modifier ($N\backslash N$), effectively inserting the necessary "from" semantics into the logical form.
Crucially, these relaxed rules are not free; the model learns weights (penalties) for using them, ensuring the parser only "relaxes" when standard rules fail to produce a valid meaning.
Online Learning and Lexical Induction
Traditional CCG learning methods often rely on slow batch processing. This work proposes an online perceptron-based algorithm that processes training examples sequentially. A core component is the induction of new lexical entries on the fly using a function called GENLEX. This function matches sentence fragments with sub-components of the target logical form based on a set of predefined templates.
The algorithm updates model parameters immediately if the current grammar cannot produce the correct logical form. This approach is highly efficient; once the model learns a sufficient set of rules, it can skip the expensive lexical induction step for over 80% of examples, leading to significant speedups.
Experimental Results
The approach was evaluated on two benchmarks: ATIS (4,978 flight queries) and Geo880 (880 geography queries). On the messier ATIS dataset, the model achieved an 86% F-measure for full correctness and a state-of-the-art 95.9% F-measure on a partial-match criterion, a significant jump over previous benchmarks. On Geo880, it reached 88.9% F-measure, outperforming previous batch-learning CCG methods. Furthermore, the online algorithm reduced training time from over 12 hours to under 4 hours on identical hardware.
Conclusion
By combining an over-expressive grammar with a robust statistical model, the authors demonstrate that formal grammars can be adapted to the noise of natural language without losing structural benefits. While challenges remain regarding unseen vocabulary and the need for a small initial manual lexicon, the introduction of learned costs for grammatical relaxation provides a powerful path forward for semantic parsing in real-world domains.
Summary updated