Source-linked AI summary
Simpler Context-Dependent Logical Forms via Model Projections
Reginald Long, Panupong Pasupat, Percy Liang
TL;DR
The paper studies how to learn context-dependent mappings from utterances to denotations when denotation-only supervision creates a combinatorially large latent logical-form search space. It projects a full semantic parser onto simpler equivalence-class models, then uses these projections alongside a new parser and three datasets. The simpler models are faster and surprisingly effective under bounded computation, and can bootstrap the full model.
Problem
Denotation-only semantic parsing with context-dependent utterances requires searching a combinatorially large space of latent logical forms, especially without an initial lexicon.
Method
The paper successively projects a full aligned semantic-parsing model onto simpler models over equivalence classes of logical forms, and develops a left-to-right parser without explicit alignment.
Results
Model C mostly surpasses the other models with a fixed beam; with infinite beam on synthetic data, Model A performs best, and projected models can bootstrap Model A under finite beams.
Takeaways & Limitations
Simpler projected models can provide computationally efficient and effective alternatives while also supplying a path to training the more expressive full model.
Takeaways & Limitations
The efficiency gain from projecting Model A to Model C comes at a cost in modeling expressivity, and the reported loss is tied to using a linear model.
Abstract
from arXiv · showhide
We consider the task of learning a context-dependent mapping from utterances to denotations. With only denotations at training time, we must search over a combinatorially large space of logical forms, which is even larger with context-dependent utterances. To cope with this challenge, we perform successive projections of the full model onto simpler models that operate over equivalence classes of logical forms. Though less expressive, we find that these simpler models are much faster and can be surprisingly effective. Moreover, they can be used to bootstrap the full model. Finally, we collected three new context-dependent semantic parsing datasets, and develop a new left-to-right parser.
1 Introduction
The paper addresses context-dependent semantic parsing from denotations, where latent logical-form search becomes combinatorially large. It projects a full aligned model onto simpler equivalence-class models, introduces a left-to-right parser and three datasets, and finds the simplest projection often effective under bounded computation.
- Denotation-only learning with no initial lexicon creates an exponential logical-form search problem that is worsened by longer context-dependent texts.
- Model A uses anchored logical forms with word-to-predicate alignments, whereas Model B removes alignments and Model C collapses logical forms with identical top-level argument denotations.
- The projections trade expressivity for efficiency: Model A supports credit assignment but has an unmanageably large search space, while Model C searches fewer forms with a harder text-to-form mapping.
- The paper contributes three context-dependent datasets—ALCHEMY, SCENE, and TANGRAMS—and a left-to-right parser that constructs logical forms without explicit alignment.
- Model C is surprisingly effective and mostly surpasses the other models with a fixed beam, while infinite-beam synthetic experiments favor Model A and finite-beam training can bootstrap Model A from projected models.
2 Task
The task maps sequences of context-dependent utterances to logical forms whose execution transforms an initial world state into the observed final state. The paper introduces three grounded datasets designed to capture ellipsis and anaphora across diverse world-state actions.
- 2.1 Setup: Context includes the initial world state and previous logical forms, so each logical form executes against both world-state and linguistic history.
- 2.1 Setup: Given an initial state, utterance sequence, and final state, the learner must infer logical forms whose execution produces the correct final state.
- 2.2 Datasets: The three datasets are ALCHEMY, SCENE, and TANGRAMS, covering ellipsis, entity anaphora, and action anaphora.
- 2.2 Datasets: ALCHEMY uses beakers and pouring, draining, and mixing; SCENE uses people and movement or hat trading; TANGRAMS uses figures and adding, removing, or swapping.
- 2.2 Datasets: The datasets are grounded in world states and offer richer context dependence than prior settings that lack world states or restrict references to narrower phenomena.
- 2.2 Datasets: Workers described automatically generated state transitions, with sampling biased toward recently used actions and arguments to encourage contextual references.
3 Model
The model represents context-dependent utterances with logical forms whose components can align to text spans and refer to prior actions or arguments. It uses features over these structures, spans, and contexts within a log-linear sequence model.
- Model representation: Logical forms contain actions and arguments, including context-dependent references such as actions[i] and args[i][j].These special tokens refer to prior actions or arguments in the context.
- Model representation: Anchored logical forms augment logical forms with alignments between sub-logical forms and utterance spans.For example, color(green) can align with “green beaker,” supporting credit assignment.
- Grammar: The grammar defines candidate values, domain actions, and special references to arguments or actions from earlier utterances.These references enable logical forms to encode context dependence.
- Model scoring: Features combine derivation conditions with aligned spans and lexical n-grams, while a standalone indicator handles condition F8.The feature design includes structural logical-form information and unigram, bigram, and trigram features inside aligned spans.
- Model scoring: Model A uses a conditional log-linear distribution over anchored logical forms given the current utterance and previous logical-form history.The feature mapping and parameter vector define the conditional distribution, which is chained across utterances.
4 Left-to-right parsing
The parser processes utterances left to right, shifting between utterances and performing build operations that create or combine logical forms. This design supports context-dependent state updates, ellipsis, and anaphora without requiring every predicate to align directly to words.
- Parser operations: The parser advances one utterance at a time, then performs build operations that create or combine logical forms on a stack.It resembles shift-reduce parsing, but each shift consumes an entire utterance.
- Context dependence: Left-to-right processing lets the parser build logical forms conditioned on the previous world state, which depends on earlier logical forms.The previous state is treated as a random variable in this setting.
- Build operations: Build operations can generate unanchored predicates, anchor predicates to spans, transform stack items, or combine two stack logical forms.These four operations cover ellipsis, lexical credit assignment, rule application, and top-level composition.
- Ellipsis and anaphora: The parser can generate an argument predicate without an explicit word reference, enabling ellipsis such as “Repeat” after an earlier command.It can also anchor actions to words while leaving referenced arguments unaligned.
- Search control: Building stops after a predicate budget B is reached or the top-level rule is applied, while search retains the K highest-scoring hypotheses.These constraints bound the parser’s search over logical forms.
5 Model Projections
The paper reduces semantic-parsing search by projecting anchored derivations into simpler equivalence classes, trading expressivity for efficiency while retaining useful denotational structure.
- Model projections: Model A can align words to compositional logical-form parts, whereas Models B and C discard alignment and increasingly collapse derivations by logical-form equivalence.Model B maps utterances to unanchored logical forms; Model C maps them to top-level actions with primitive arguments.
- Search-space reduction: 1,216,140 to 7,047 to 349 intermediate forms: successive projections from anchored derivations to logical forms and then flat logical forms dramatically shrink search.Model B removes alignment distinctions, while Model C collapses compositional forms with the same evaluated arguments, such as mix(args[1][1]) and mix(pos(2)) into mix(beaker2).
- Expressivity and scope: The projections remain expressive enough to generate logical forms for any denotation, although Model C still grows exponentially with utterance count.Its advantage depends on worlds having far fewer denotations than logical forms.
- Feature projection: Projected models are built by mapping anchored forms downward and taking component-wise maxima of the original features over forms that project to each simpler representation.Model C can reason directly over flat logical forms because many derivation conditions already depend on argument denotations.
- Expressivity and scope: Simple Model C features can simulate some compositional meanings, including color(green), and can express superlatives through conjunctions over object properties.However, exact references such as color(green)[2] are difficult to explain using those simple features.
6 Experiments
The experiments compare projected semantic parsing models under finite and effectively infinite beam settings, showing a computation–expressivity trade-off. Model C is generally strongest with constrained computation, while Model A becomes strongest with sufficient beam and can be reached by bootstrapping.
- 6.1 Real data experiments: 20% higher average accuracy and 39% higher average oracle accuracy make Model C stronger than Model B on 5-utterance real-data examples, except on TANGRAMS.Model C surpasses Model B on ALCHEMY and SCENE, whereas Model B does better on TANGRAMS.
- 6.1 Real data experiments: Model C’s finite-beam advantage reflects Model B’s larger search space, while TANGRAMS favors Model B because its smaller positional search space and required references exceed Model C’s expressivity.Model C cannot express references such as “repeat the first step” or “add it back.”
- 6.1 Real data experiments: As utterance count and search-space pressure increase, Model C increasingly outperforms Model B, although both models degrade as errors cascade across longer sequences.Longer examples also tend to have richer context dependence.
- 6.2 Artificial data experiments: The artificial-data evaluation uses 500 training and 500 test examples across beam sizes 40–260, with linguistic alignment constraints that slightly favor Model A.Model A was otherwise impractical to evaluate on real data because of its large search space.
- 6.2 Artificial data experiments: With beam size greater than 250, all models attain oracle accuracy 1, and Model A outperforms Model B, which performs similarly to Model C.Alignments give Model A a stronger learning signal, whereas Models B and C learn noisier features without alignments.
- 6.2 Artificial data experiments: Bootstrapping Model A from Model C parameters enables Model A to perform well under constrained beam settings despite their different predicted logical forms.The initialization works because Model C is a projection of Model A and shares its features.
7 Related Work and Discussion
The paper connects its approach to context-dependent semantic parsing, alignment-free logical-form generation, and relaxation or bootstrapping methods. It also discusses the computation–expressivity trade-off and possible nonlinear or continuous alternatives.
- Context-dependent semantic parsing: The system handles both linguistic and world-state context, including ellipsis and anaphora referring to previous world states and logical forms.Prior work addressed these context types separately.
- Logical form generation: Models B and C relate to prior alignment-free approaches that generate logical forms or concrete knowledge-graph paths directly.Model B resembles alignment-free logical-form generation, while Model C resembles direct path prediction.
- Relaxation and bootstrapping: The projection strategy extends earlier relaxation and bootstrapping ideas by training a simpler model before moving to a more complex one.Related work uses bootstrapping for helpful regularization and relaxation when finding denotation-reaching logical forms is difficult.
- Discussion: Projecting from Model A to Model C improves computational tractability at the cost of expressivity because Model C uses a linear model.The discussion suggests nonlinear models might recover some lost expressivity.
- Discussion: Continuous approaches could avoid the combinatorial explosion of logical forms but may introduce additional optimization challenges.The paper identifies this computation–expressivity trade-off as an avenue for further study.
Reproducibility
The paper reports that its code, data, and experiments are publicly available on CodaLab.
- Reproducibility: Code, data, and experiments are available through a CodaLab worksheet.The passage provides the worksheet URL.