PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Dependency-Based Compositional Semantics

Percy Liang, Michael I. Jordan, Dan Klein

arXiv:1109.6841v1cs.AI

TL;DR

The paper asks whether semantic parsers can learn from question–answer pairs without expensive logical-form annotations. It introduces DCS and a log-linear latent-variable parser trained by alternating beam search and optimization, achieving state-of-the-art performance on standard benchmarks without annotated logical forms. Its scope is bounded by candidate-set and representation limitations, including lexical-trigger supervision and difficulty with some long-distance dependencies.

  • Problem

    Semantic parsing needs rich logical forms, but annotating utterance–logical-form pairs is expensive, motivating learning from question–answer pairs with latent logical forms.

  • Method

    The paper introduces DCS and models latent DCS trees with a log-linear parser trained by alternating beam search and likelihood optimization.

  • Results

    The DCS-based system outperformed previous answer-supervised work and state-of-the-art systems using annotated logical forms on the Geo benchmark, while evaluation covered Geo and Jobs.

  • Takeaways & Limitations

    The results demonstrate the viability of training accurate semantic parsers with much less supervision than annotated logical forms.

  • Takeaways & Limitations

    Performance depends on lexical-trigger choices because broader triggers enlarge candidate sets and can cause beam search to drop good DCS trees; DCS trees also cannot directly capture some long-distance dependencies such as anaphora.

Abstract

from arXiv · show

Suppose we want to build a system that answers a natural language question by representing its semantics as a logical form and computing the answer given a structured database of facts. The core part of such a system is the semantic parser that maps questions to logical forms. Semantic parsers are typically trained from examples of questions annotated with their target logical forms, but this type of annotation is expensive. Our goal is to learn a semantic parser from question-answer pairs instead, where the logical form is modeled as a latent variable. Motivated by this challenging learning problem, we develop a new semantic formalism, dependency-based compositional semantics (DCS), which has favorable linguistic, statistical, and computational properties. We define a log-linear distribution over DCS logical forms and estimate the parameters using a simple procedure that alternates between beam search and numerical optimization. On two standard semantic parsing benchmarks, our system outperforms all existing state-of-the-art systems, despite using no annotated logical forms.

1 Introduction

The paper targets semantic parsing from question–answer pairs rather than expensive logical-form annotations. It introduces DCS, a latent-logical-form approach trained with beam search and optimization, and reports state-of-the-art results without annotated logical forms.

  • Semantic parsers traditionally require questions paired with annotated logical forms, whose creation is expensive and requires formal-language expertise.
  • The paper learns a mapping from utterance x to answer y through a latent logical form z, using question–answer pairs as supervision.
  • Dependency-based compositional semantics (DCS) is introduced as a new semantic formalism with linguistic, statistical, and computational advantages.
  • The parser defines a log-linear distribution over DCS trees and alternates beam search with likelihood optimization because answer constraints make dynamic programming infeasible.
  • The system was evaluated on Geo and Jobs, and on Geo it outperformed both answer-supervised prior work and state-of-the-art systems trained with annotated logical forms.

2 Representation

DCS represents logical forms as trees and extends constraint-based semantics with mark-execute for cases where syntactic and semantic scope diverge. The paper also specifies a construction mechanism mapping utterances to candidate DCS trees.

  • DCS trees are the formal language’s logical forms, with syntax defined as straightforward tree structures and semantics evaluated against typed worlds or databases.
  • DCS represents logical forms as constraint satisfaction problems or extensions thereof, supporting compositional semantic evaluation.
  • The mark-execute construct handles cases where syntactic and semantic scope diverge, including generalized quantification and superlative constructions.
  • A construction mechanism maps natural-language utterances to sets of candidate DCS trees.

2.1 Notation

The notation introduces sequences and basic operations for their length, concatenation, projection, exclusion, and combined indexing.

  • For a sequence v = (v1, . . . , vk), |v| denotes its length, and u + v denotes concatenation of two sequences.
  • Positive indices project selected components of a sequence, while negative indices exclude components; indexed sequences can also be concatenated.

2.2 Syntax of DCS Trees

DCS syntax combines predicates and fixed relations into directed rooted trees whose predicate-labeled nodes and relation-labeled edges mirror dependency structure. This transparency is intended to support streamlined compositional semantics and program induction.

  • Syntax ingredients: DCS syntax is built from predicates and relations, with domain-specific predicates such as state, river, and border alongside domain-independent predicates.
  • Syntax ingredients: The relation set is fixed, whereas predicates include both domain-independent and domain-specific labels.
  • DCS trees: A DCS tree is a directed rooted tree with predicate-labeled nodes, relation-labeled edges, and an ordering over each node’s children.
  • DCS trees: DCS trees can be written compactly using a root predicate followed by relation–child pairs, or drawn graphically.
  • Motivation: Because DCS trees resemble syntactic dependency trees with predicates replacing words, their syntax–semantics transparency supports streamlined compositional semantics for program induction.

2.3 Worlds

A DCS world is a typed database that maps predicates to sets of tuples, including domain-specific facts and domain-independent functions. Its value system supports primitive, tuple, and set values, with predicate arities determined by the world.

  • DCS constructs values recursively from primitive values, tuples, and sets, while excluding invalid type forms.Primitive values include tagged numbers and symbols, allowing distinctions such as city versus state entities.
  • A world w maps each non-null predicate to a set of tuples and the null predicate to all values V.
  • Predicate arity is inherited from the tuples in w(p), whereas the null predicate is assigned arity 1.
  • In the US geography example, predicates represent entities and relations such as states and place-container pairs.For example, w(state) contains states, while w(loc) contains pairs such as San Francisco and California.
  • Functions such as count, average, argmin, and argmax are represented as predicates over sets of typed tuples.These predicates are domain-independent helpers; count returns cardinalities, while average and extrema predicates operate on key-value sets.

2.4 Semantics of DCS Trees: Basic Version

Basic DCS gives tree-shaped logical forms a constraint-based semantics: join relations define a CSP, and the denotation is the feasible values of the root. Aggregate relations extend this framework to sets, cardinality, averages, and disjunction.

  • 2.4.1 DCS Trees as Constraint Satisfaction Problems: A basic DCS tree with join relations encodes a constraint satisfaction problem whose denotation is the feasible values of its root node.Node predicates constrain assignments to database tuples, while join edges require equality between selected tuple components.
  • 2.4.1 DCS Trees as Constraint Satisfaction Problems: The denotation is computed by retaining values that participate in at least one feasible assignment satisfying all node and edge constraints.The equivalent lambda-calculus view existentially quantifies non-root variables and abstracts over the root.
  • 2.4.1 DCS Trees as Constraint Satisfaction Problems: Tree-structured CSPs capture recursive structures but cannot directly represent long-distance dependencies such as anaphora.The paper notes that adding non-tree edges is a possible extension, but does not pursue it here.
  • 2.4.2 Computation: Dynamic programming computes tree denotations efficiently because each subtree affects its parent through its denotation.The computation uses join and project operations, with time scaling linearly in the number of nodes apart from operation costs.
  • 2.4.3 Aggregate Relation: The aggregate relation Σ reifies a child denotation as a set-valued object that can support cardinality, averaging, and disjunctive constructions.It deterministically sets the parent to the child denotation, enabling operations such as counting major cities and averaging populations.
  • 2.4.3 Aggregate Relation: Basic DCS cannot naturally align some semantically equivalent forms with syntax, motivating mark-execute relations for scope-divergent constructions.The full formalism uses mark-execute to give syntactically scoped trees appropriate semantic scope, as in most populous city.

2.5 Semantics of DCS Trees: Full Version

Full DCS extends constraint-based tree semantics with mark-execute relations, allowing modifiers whose semantic scope diverges from their syntactic position. Its denotations retain root values and stored information for marked nodes until execution.

  • Scope divergence: Mark-execute relations let DCS represent semantic scope that diverges from syntactic scope for superlatives, quantifiers, and negation.A mark stores a modifier at a lower node, while a higher execute relation retrieves and applies it.
  • Denotations: The denotation of a DCS tree contains columns for the root and each non-executed marked node, ordered by preorder traversal.Each marked node also retains a store containing its relation and denotational information for later execution.
  • Execute relations: Execute relations process stored columns in an order specified by their distinct indices, determining how marked modifiers are applied.For example, X12 processes column 3 before column 2, whereas X21 processes column 2 before column 3.
  • Scope ambiguity: The choice between x12 and x21 resolves quantifier-scope ambiguity into narrow and wide readings without changing the pre-execution denotation.The same basic tree structure therefore supports different semantic readings through execution order.
  • Comparatives and superlatives: Mark-execute also supports comparative and superlative constructions by storing a predicate such as argmax and invoking it at the desired semantic node.In the superlative example, population is marked and city execution retrieves and applies argmax.

2.6 Construction Mechanism

The construction mechanism maps an utterance to an overapproximated set of candidate DCS trees rather than an exact set of valid logical forms. It combines lexical triggers recursively, permits trace predicates, augments trees with scope relations, and filters structurally impossible candidates.

  • Purpose and lexical triggers: The construction mechanism maps an utterance x to a set of candidate DCS trees ZL(x), using a fixed set of lexical triggers.Triggers associate word sequences with possible predicates, while trace predicates can be introduced without overt lexical triggers.
  • Purpose and lexical triggers: It intentionally overapproximates possible logical forms, leaving a separate distribution to favor better candidates.This design permits a simple lexicon and grammar despite uncertainty about lexical entries during learning.
  • Recursive construction: For each utterance span, the mechanism recursively combines subspan trees, then augments and filters the resulting candidates.The base case creates one-node trees from lexical triggers; the recursive case combines trees through T1 and may ignore words between split points.
  • Recursive construction: Tree-combination operations connect two DCS trees through relations and allow insertion of trace predicates, with either tree serving as the root.Additional relations such as e and xi are added by augmentation.
  • Trace predicates: Trace predicates add implicit predicates for unexpressed meanings, simplify treatment of semantically light words, and can supply omitted transitive-verb predicates.The mechanism therefore need not require every predicate to have an overt lexical trigger.
  • Filtering: Filtering uses abstract interpretation to discard trees whose subtrees receive empty abstract denotations, while preserving trees that may be valid in another world.This distinguishes impossible type combinations from world-specific emptiness.

3 Learning

The model defines a log-linear distribution over candidate DCS trees using feature-based compatibility scores, then learns from question-answer pairs with latent logical forms. Because candidate spaces are exponential and answer constraints impede dynamic programming, learning alternates beam-search candidate generation with parameter optimization.

  • 3.1 Model: The semantic parser assigns each candidate DCS tree a probability conditioned on the utterance using feature vector φ(x, z) and parameter vector θ.The score φ(x, z)⊤θ measures compatibility between an utterance and a DCS tree.
  • 3.1.1 Features: Feature templates count structural and lexical properties of DCS trees, including predicates, predicate relations, lexical triggers, and trace constructions.Tree-only templates support generalization, while trigger-based templates connect predicates to utterance words.
  • 3.2 Parameter Estimation: Training maximizes marginal log-likelihood over DCS trees that evaluate to the observed answer, with quadratic regularization on θ.An example is feasible when its candidate set contains at least one tree denoting the correct answer.
  • 3.2 Parameter Estimation: The objective is non-concave, so the parameters are estimated with gradient-based numerical optimization using expected feature vectors.The gradient moves parameters toward answer-producing trees and away from all candidate trees.
  • 3.2.2 Algorithm: Beam search truncates exponentially growing candidate sets, and the algorithm alternates candidate-set updates with parameter optimization.This bootstrapping procedure addresses the chicken-and-egg dependence between good parameters and good candidate sets, though convergence is not guaranteed.

4 Experiments

The empirical evaluation tests the DCS approach on standard semantic-parsing benchmarks and reports higher accuracy than existing systems without annotated logical forms.

  • 4 Experiments: The system obtains higher accuracies than existing systems despite requiring no annotated logical forms.The evaluation studies the approach empirically after introducing DCS trees and a probabilistic model over them.

4.1 Experimental Setup

Experiments use the Geo and Jobs benchmarks, with databases, trigger sets, features, beam search, optimization, regularization, and iteration counts controlling the evaluation setup. Prototype triggers add modest domain-specific supervision, improving accuracy and computational efficiency while lexical-trigger selection remains an important tradeoff.

  • Datasets: The evaluation uses Geo and Jobs, standard semantic-parsing datasets containing 880 US-geography questions and 640 job queries.Geo questions average 8.5 words, while Jobs queries average 9.8 words.
  • Datasets: The Jobs database is replaced with a random database containing m = 100 jobs and α = 0.8 predicate-tuple inclusion probability.Randomness is intended to make different logical forms likely to produce different answers.
  • Lexical Triggers: Lexical triggers trade expressiveness against computational complexity because more triggers enlarge the candidate space and can cause beam search to discard good trees.The trigger sets compared are base triggers Lb and augmented triggers Lb+p.
  • Settings: The model uses beam search, L-BFGS optimization, λ = 0.01 regularization, and T = 5 alternating training iterations by default.Beam size is K = 100, with each intermediate state retaining at most K DCS trees.
  • Lexical Triggers: Prototype triggers require modest domain-specific supervision and can improve both accuracy and computational efficiency.They reduce the candidate DCS trees considered for an utterance.

4.2 Comparison with Other Systems

Across Geo and Jobs comparisons, the system learns from answers rather than annotated logical forms and achieves competitive or leading accuracy. Its strongest reported results use augmented triggers or database type constraints, while evaluation metrics differ because latent logical forms are marginalized.

  • Question-Answer Supervision: The approach learns from any feasible example, unlike CGCR10, which requires the highest-scoring logical form to produce the correct answer before learning progresses.A feasible example only requires that some candidate logical form evaluates to the correct answer.
  • Question-Answer Supervision: On the 250-example Geo split, LJK11 with base triggers achieves 84% accuracy versus CGCR10’s 73.2%, and exceeds CGCR10 trained with logical forms at 80.4%.Augmented triggers widen the gap by another 3.6%.
  • Evaluation: LJK11 is evaluated on answer accuracy because it marginalizes the latent logical form, whereas other systems are evaluated on logical-form accuracy.Multiple logical forms can yield the same answer, so answer accuracy does not necessarily imply high logical-form accuracy.
  • State-of-the-Art Systems: On the main Geo comparison, augmented-trigger LJK11 leads KZGS10 with answer accuracy of 91.4% versus 88.9%.With base triggers, LJK11 reaches 87.9% versus KZGS10’s 88.9%.
  • State-of-the-Art Systems: On Jobs, LJK11 obtains the highest accuracies by combining learning with database type constraints.Precise also uses type constraints, while the other listed systems do not.

4.3 Empirical Properties

The experiments examine learned features, beam-search feasibility, error patterns, and optimization choices. Training makes more examples feasible over iterations, while lexical and search-related limitations remain important.

  • Learned Parameters: The learned model can associate words with incorrect predicates when correlated database properties confound their meanings.It correctly learns city as city but incorrectly learns sparse as elevation because Alaska is both sparse and high-elevation.
  • Learned Parameters: Lexical feature templates yield 76.4% accuracy, while adding non-lexical features raises accuracy to 84.7%.Non-lexical features alone account for 23.1% in the reported comparison.
  • Optimization: With an appropriate step size, stochastic gradient descent converges much faster than L-BFGS and reaches a slightly better solution.For this task, a very small α, below 0.2, performs best despite convergence guarantees applying only for α between 0.5 and 1.

5 Discussion

The discussion frames DCS as a dependency-based alternative designed jointly with its construction mechanism for weakly supervised semantic parsing. It connects representation, program induction, and grounded language while identifying open-domain scaling as an unresolved challenge.

  • Semantic Representation: DCS replaces heavily lexicalized constituency-based formalisms with a lightly lexicalized dependency-based formalism that exposes useful path features.The authors describe this as a shift in linguistic coordinate systems that makes certain factorizations more accessible.
  • Semantic Representation: DCS is designed to make computations expressed by natural language easier to represent, including through its mark-execute construct.The discussion treats formal-language design as distinct from expressiveness alone: ease of expressing desired computations also matters.
  • Program Induction: Program induction remains computationally difficult because the supervision signal is a complex function of the inferred program’s behavior.In this setting, logical forms must be inferred from denotations rather than directly observed structures.
  • Program Induction: DCS jointly addresses semantic representation and latent logical-form induction, enabling question-answer training without annotated logical forms.The article presents this combination as its main conceptual contribution and reports state-of-the-art question-answering performance.
  • Grounded Language: Combining language’s semantic richness with open-domain breadth remains an open challenge for database-oriented question answering.The paper contrasts compositional depth in natural-language interfaces to databases with breadth in systems retrieving answers from unstructured text.
  • Grounded Language: The authors believe DCS and its learning algorithm could extend toward noisy information-extraction databases, but acknowledge many open challenges.Their proposed direction continues to use question-answer behavior to guide induction of latent logical forms or programs.
Loading 1109.6841v1…