To interact naturally with databases, knowledge bases, and physical environments, computers must translate human language into machine-executable code. This task is known as semantic parsing. Traditionally, training a semantic parser required a dataset of natural language sentences paired with expert-annotated logical forms (such as SQL queries or lambda-calculus expressions).
However, collecting these formal logical annotations creates a severe "supervision bottleneck," as noted by Clarke et al.. Human experts who understand both the domain logic and the database schema are expensive and difficult to scale.
To bypass this bottleneck, a powerful paradigm emerged: weakly supervised semantic parsing. Instead of teaching a model how to write code step-by-step, we allow the model to treat the underlying program as a hidden, latent variable. The model learns simply by executing its predicted programs against an environment and checking if the final output—the denotation—matches the correct answer.
The Intuition: Learning from Denotations
Imagine trying to learn a new programming language without a textbook, but with access to a compiler and a set of input-output examples. If you guess a command, run it, and get the correct output, you receive a positive reinforcement signal that your guess was likely correct.
This is the core mechanism behind learning from denotations. As pioneered by Liang et al., a semantic parser can bootstrap its own lexicon and grammar by identifying which latent logical structures consistently yield correct answers from a database.
Natural Language Query: "What is the capital of France?"
│
▼
┌──────────────┐
│ Parser │ ──► Generates Latent Program: SELECT capital FROM countries WHERE name='France'
└──────────────┘
│
▼
┌──────────────┐
│ Executor │ ──► Runs program against Database
└──────────────┘
│
▼
Denotation: "Paris" ◄─── Compare ───► Target Answer: "Paris" (Match! Reward Parser)
In this framework, the training data consists only of simple question-answer pairs, which are significantly easier to crowdsource than expert code. As Liang outlined, treating the program as a latent variable allows the system to optimize its parameters based entirely on the success of the final execution.
The Optimization Mechanism
How does a model optimize its parameters when it cannot compute a direct gradient through a discrete database execution?
Different strategies exist depending on the model architecture:
- Reinforcement Learning and Binary Feedback: Clarke et al. demonstrated that binary feedback (whether the database response is correct or incorrect) can serve as a reward signal to update the model's mapping between natural language and formal representations.
- Discriminative Reranking: The model can generate a large pool of candidate logical derivations. As shown by Berant et al., a discriminative model can then reward the specific derivations that execute to the correct result while penalizing those that do not.
- Continuous Expectations: In neural architectures, models like the one proposed by Neelakantan et al. induce latent programs by optimizing the expected value of the execution result directly against the target answer using gradient descent.
The Challenge of Spurious Programs
The primary hurdle in training a parser without intermediate logical ground truth is the problem of spurious programs. A spurious program is a piece of code that arrives at the correct answer for the entirely wrong reason.
For example, if a user asks, "Which country has the largest population?" and the correct answer is "China", the parser might accidentally generate a program that simply selects the first row of the table. If China happens to be in the first row, the program returns the correct denotation ("China"), and the model receives a positive reward. This causes the model to incorrectly learn that "largest population" means "first row."
Because the search space of possible programs is combinatorially massive, spurious programs can severely degrade model accuracy. To mitigate this, researchers introduce structural and semantic constraints:
- Type Constraints: Krishnamurthy et al. integrated a grammar-based decoder that enforces strict type constraints during offline search. By preventing the model from even considering logically impossible or malformed programs, the search space is dramatically pruned.
- Structural Alignment: As Ou et al. noted, aligning a statement's grammatical structure with its logical execution order helps ensure the model learns the true semantic mapping rather than exploiting accidental data regularities.
Broad Applications of Weak Supervision
The principle of learning from execution feedback extends far beyond traditional database queries:
- Temporal Resolution: Interpreting messy time expressions like "the week before last" can be framed as a latent parsing problem. Models designed by Manning et al. and Angeli et al. optimize internal parse trees using only the final standardized date range as supervision.
- Conversational Feedback: In dialogue systems, explicit question-answer pairs are rarely provided. Instead, Artzi et al. demonstrated that a parser can treat subsequent user reactions (such as confirmations or corrections) as indirect execution signals to back-calculate what the user originally meant.
- Grounded Robotics: When a human commands a robot, the execution environment is physical rather than digital. Wang et al. showed that an agent can learn to map natural language to Linear Temporal Logic (LTL) formulas by observing physical trajectories and using a planner-based critic to evaluate whether the executed behavior satisfied the command.
Key Foundational Work
Driving Semantic Parsing from the World's Response (2010) — contributed 3 concept elements to this direction.
Bootstrapping Semantic Parsers from Conversations (2011) — contributed 2 concept elements to this direction.
Learning Dependency-Based Compositional Semantics (2011) — contributed 1 concept elements to this direction.