Source-linked AI summary
From Language to Programs: Bridging Reinforcement Learning and Maximum Marginal Likelihood
Kelvin Guu, Panupong Pasupat, Evan Zheran Liu, Percy Liang
TL;DR
The paper studies semantic parsing from execution results without target programs, where many spurious programs can fit the supervision. It connects RL and MML, then introduces RANDOMER, which combines randomized and systematic exploration with meritocratic updates. On SCONE, RANDOMER outperforms standard RL and MML and achieves state-of-the-art results, including over 30% higher accuracy on the most challenging domain.
Problem
Indirect supervision gives only correct execution results, while many incorrect spurious programs can produce those results and obscure the intended program.
Method
RANDOMER combines randomized beam search with meritocratic parameter updates that spread probability more evenly across programs producing the correct output.
Results
RANDOMER achieves new state-of-the-art results on all three SCONE domains, improving accuracy by over 30% on the most challenging domain.
Takeaways & Limitations
The approach outperforms standard RL and MML methods in direct comparison while combining their exploration and learning perspectives.
Takeaways & Limitations
Training uses weak supervision consisting of target world states rather than target programs, and the experiments use SCONE's three domains.
Abstract
from arXiv · showhide
Our goal is to learn a semantic parser that maps natural language utterances into executable programs when only indirect supervision is available: examples are labeled with the correct execution result, but not the program itself. Consequently, we must search the space of programs for those that output the correct result, while not being misled by spurious programs: incorrect programs that coincidentally output the correct result. We connect two common learning paradigms, reinforcement learning (RL) and maximum marginal likelihood (MML), and then present a new learning algorithm that combines the strengths of both. The new algorithm guards against spurious programs by combining the systematic search traditionally employed in MML with the randomized exploration of RL, and by updating parameters such that probability is spread more evenly across consistent programs. We apply our learning algorithm to a new neural semantic parser and show significant gains over existing state-of-the-art results on a recent context-dependent semantic parsing task.
1 Introduction
The paper addresses semantic parsing with indirect supervision, where correct outputs do not identify the intended programs and spurious programs can mislead learning. RANDOMER combines systematic and randomized exploration with meritocratic updates, achieving state-of-the-art results on SCONE.
- Indirect supervision provides correct execution outputs but not the programs that produced them.
- Spurious programs produce correct outputs for incorrect reasons and can draw the parser away from the true program.
- MML and RL optimize closely related objectives but their exploration can concentrate around short spurious programs.
- Randomized beam search combines MML-style systematic beam search with RL-style randomized off-policy exploration.
- The meritocratic update more equally increases probability for programs producing the correct output, reducing overfitting to spurious programs.
- Over 30% accuracy improvement on the most challenging SCONE domain accompanied new state-of-the-art results across all three domains.
2 Task
SCONE requires programs that transform a sequence of world states according to natural-language actions, but training supplies only target states. Many programs reach those states, although few express the utterances' intended reference strategies.
- Each example supplies an initial world state, multiple utterances, and target world states after the utterances, but not the target program.
- SCONE contains ALCHEMY, TANGRAMS, and SCENE, which emphasize ellipsis, action anaphora, and entity anaphora respectively.
- At least 1600 programs per example on average transform the initial state into the correct final state, but almost all are spurious.
- Different reference strategies allow many programs to implement the same action, while only a few match the utterance-defined strategy.
3 Model
The parser generates executable programs as postfix token sequences with a neural encoder-decoder and attention. It represents execution history either through recent tokens or the evolving stack state.
- Programs are represented in postfix notation so they can be incrementally executed from left to right with a stack.
- An attention-based neural encoder-decoder generates program tokens from left to right while tracking the current utterance.
- Encoder: The encoder uses a bidirectional LSTM over utterance words and concatenates its final forward and backward states into the utterance embedding.
- Decoder: A feed-forward decoder combines the utterance representation, execution-history embedding, and attention vector to compute token probabilities.
- Execution history embedding: The TOKENS history representation concatenates the embeddings of the four most recent tokens.
- Execution history embedding: STACK summarizes execution history by concatenating embeddings of stack values, with maximum stack size limited to 3.
4 Reinforcement learning versus maximum marginal likelihood
RL and MML both seek programs that execute to the observed output, but differ in how they aggregate program probabilities and approximate gradients. Their practical procedures explore program space using sampling or beam search.
- Reinforcement learning: RL treats program generation as sequential decisions receiving a terminal reward of 1 for executing to the target and 0 otherwise.
- Reinforcement learning: The RL objective is expected reward across examples, with the expectation summing over possible programs.
- Maximum marginal likelihood: MML treats the program as latent, marginalizes its probability given the observed output, and maximizes the resulting log marginal likelihood.
- Comparing objective functions: With the chosen reward, RL expected reward equals MML marginal probability; RL sums across examples, whereas MML optimizes a product.
- Comparing gradients: Both methods use closely related gradient forms that upweight reward-earning programs, but their expectations are generally intractable and must be approximated.
- Comparing gradient approximation strategies: REINFORCE uses Monte Carlo samples, while MML commonly uses numerical integration over programs found by beam search.
- Beam search: Beam search retains at most B highest-scoring partial programs at each step and returns complete programs discovered during search.
5 Tackling spurious programs
The paper identifies exploration and optimization biases that cause RL and MML to favor short, high-probability spurious programs over correct ones. RANDOMER combines randomized beam search with β-meritocratic updates to find correct programs more reliably and distribute learning weight more evenly.
- 5.1 Spurious programs bias exploration: RL and MML exploration is guided by the current policy, so low-probability correct programs can be overlooked while spurious programs reinforce their advantage.This feedback loop makes learning sensitive to initialization, especially because thousands of spurious programs are often found before the few correct ones.
- 5.1 Spurious programs bias exploration: A near-uniform decision policy still favors shorter programs, giving a shorter spurious path two orders of magnitude higher probability than a longer correct path.Thus, even an apparently neutral initialization can produce a strongly nonuniform distribution over complete programs.
- Solution: randomized beam search: ϵ-greedy randomized beam search selects continuations by mixing uniform random sampling with highest-probability selection, preserving beam search coverage while injecting exploration noise.It chooses B continuations without replacement, using random selection with probability ϵ and greedy selection with probability 1 − ϵ.
- Solution: randomized beam search: Randomized beam search performs much better than both classic beam search and ϵ-greedy sampling, while MML also performs significantly better than RL in the experiments.The comparisons are reported in Tables 3 and 4.
- 5.2 Spurious programs bias optimization: Even perfect exploration leaves spurious programs problematic because gradient weights remain proportional to current policy probability, potentially directing roughly 99% of updates toward a spurious program.Simply increasing the learning rate is inadequate because larger steps toward the spurious program can cause optimization to diverge.
- Solution: the meritocratic update rule: The β-meritocratic update extends MML weighting to distribute updates more evenly across reward-earning programs, with β = 0 fully uniform and β = 1 recovering original MML weighting.RANDOMER combines this update rule with ϵ-greedy randomized beam search to reduce exploration bias and balance optimization.
6 Experiments
Experiments evaluate RANDOMER and its components on SCONE, comparing exploration, gradient weighting, and execution-history representations against established methods. RANDOMER achieves state-of-the-art performance, while randomized beam search and β-meritocratic updates reduce spurious-program effects under domain-dependent conditions.
- Evaluation: Experiments evaluate models on all three SCONE domains using five random seeds and report median accuracy after three and five utterances.Accuracy is the percentage of test examples producing the correct final world state.
- Main results: RANDOMER achieves new state-of-the-art results, significantly outperforming Long et al. (2016), REINFORCE, and BS-MML, especially on SCENE.The comparison uses hyperparameters selected by validation performance.
- Main results: REINFORCE performs very well on TANGRAMS but worse on ALCHEMY and very poorly on SCENE, where program syntax is more complex.The authors suggest TANGRAMS is simpler because objects can only be referenced by index.
- Randomized beam search: ϵ-greedy randomized beam search consistently outperforms classic beam search, with beam 32 surpassing classic beam search even at beam 128.Further increases to classic beam size yield no additional improvement.
- β-meritocratic updates: More uniform β-meritocratic upweighting improves accuracy and reduces spurious programs, especially in SCENE, but no β value is best across all domains.On ALCHEMY, β = 0 reaches good performance in half the time while ultimately achieving similar accuracy to β = 1.
- Execution history and overfitting: STACK execution-history embeddings outperform TOKENS in SCENE and ALCHEMY, while RANDOMER spreads probability across multiple reward-earning programs instead of overfitting a spurious one.STACK is invariant to how objects were pushed onto the stack, and this may improve robustness to spurious histories.
7 Related work and discussion
The paper situates RANDOMER between MML and RL, combining randomized exploration with meritocratic updates to address spurious programs. It also connects these ideas to related exploration, smoothing, and neural semantic parsing work.
- Discussion: RANDOMER reaches 60% validation accuracy on ALCHEMY faster with β = 0, while REINFORCE plateaus before climbing after 40k iterations.The figure compares RANDOMER, BS-MML, and REINFORCE over training iterations; runs are averaged over 5 seeds.
- RANDOMER: RANDOMER combines randomized beam search with meritocratic updates, distributing probability across reward-earning programs instead of concentrating on one spurious program.The update is targeted at reward-earning programs, while randomized search explores low-probability states under peaky policies.
- MML and RL: Without correct program sequences, indirect supervision requires marginal likelihood rather than direct likelihood maximization.The paper presents MML as a substitute for standard RL training and the β-meritocratic update as an improvement over that objective.
- Related methods: The work differs from simulated annealing by smoothing an expectation in the gradient rather than smoothing the objective function.The authors note that β = 0 is effective in their method, unlike total smoothing in the compared simulated-annealing methods.
- Neural semantic parsing: The paper develops a neural semantic parser for context-dependent parsing using a new stack-based programming language.The parser is evaluated in the SCONE setting, whose domains involve different forms of ellipsis and anaphora.
B SCONE domains and program tokens
The stack-based language defines shared tokens for constants, object lists, indexing, and references to prior actions across all three SCONE domains.
- Shared tokens: Shared tokens include constants for numbers and colors, allObjects for the object list, index for selecting an object, and prior-action reference operations.The index function uses one-based indexing and permits negative indices.