Macro Grammars and Holistic Triggering for Efficient Semantic Parsing
Table 1: A knowledge base for the question x = “Who ranked right after Turkey?”. The target denotation is y = {Sweden}.
['[EMPTY]', '[BOLD] Rank', '[BOLD] Nation', '[BOLD] Gold', '[BOLD] Silver', '[BOLD] Bronze']
In this paper, we propose macro grammars to bias the search towards structurally sensible logical forms. To illustrate the key idea, suppose we managed to parse the utterance “Who ranked right after Turkey?” Nation. Turkey, which identifies the cell under the Nation column in the row after Turkey. From this logical form, we can abstract out all relations and entities to produce the following macro: \reverse{Rel#1}.\reverseNext.{Rel#1}.{Ent#2}, which represents the abstract computation: “identify the cell under the {Rel#1} column in the row after {Ent#2}.” More generally, macros capture the overall shape of computations in a way that generalizes across different utterances and knowledge bases. Given the consistent logical forms of utterances parsed so far, we extract a set of macro rules. The resulting macro grammar consisting of these rules generates only logical forms conforming to these macros, which is a much smaller and higher precision set compared to the base grammar. A knowledge base refers to a collection of entities and relations. Table cells (e.g., \tttTurkey) and rows (e.g., r3= the 3rd row) are treated as entities. Relations connect entities: for example, the relation \tttNation maps r3 to \tttTurkey, and a special relation \tttNext maps r3 to r4. However, these coverage numbers are computed based on finding any logical form that executes to the correct denotation. This includes spurious logical forms, which do not reflect the semantics of the question but are coincidentally consistent with the correct denotation. (For example, the question “Who got the same number of silvers as France?” Nation. France, which represents the nation listed after France.) To evaluate the “true” coverage, we sample 300 training examples and manually label their logical forms. We find that on 48.7% of these examples, the top consistent logical form produced by the base grammar is semantically correct. For the macro grammar, this ratio is also 48.7%, meaning that the macro grammar’s effective coverage is as good as the base grammar.