Source-linked AI summary
Neural Symbolic Machines: Learning Semantic Parsers on Freebase with Weak Supervision
Chen Liang, Jonathan Berant, Quoc Le, Kenneth D. Forbus, Ni Lao
TL;DR
Semantic parsing from question-answer pairs requires neural models to interact with a non-differentiable symbolic executor over a large program space. NSM combines a seq2seq programmer with key-variable memory and a symbolic Lisp computer, training them with REINFORCE augmented by iterative maximum likelihood. On WebQuestionsSP, it achieves new state-of-the-art results with weak supervision and significantly closes the gap with full supervision.
Problem
Semantic parsing remains challenging when language must be mapped to programs executed through non-differentiable operations over a large program space.
Method
NSM combines a neural seq2seq programmer with key-variable memory, a symbolic Lisp interpreter, search pruning, and REINFORCE augmented by pseudo-gold programs from iterative maximum-likelihood training.
Results
NSM achieves new state-of-the-art results on WebQuestionsSP with weak supervision and significantly closes the gap between weak and full supervision.
Takeaways & Limitations
Weakly supervised semantic parsing can combine neural language modeling with abstract, scalable, precise symbolic operations without feature engineering or domain-specific knowledge.
Takeaways & Limitations
Even after overfitting controls, NSM remains overfit, with training F1@1=83.0% and validation F1@1=67.2%.
Abstract
from arXiv · showhide
Harnessing the statistical power of neural networks to perform language understanding and symbolic reasoning is difficult, when it requires executing efficient discrete operations against a large knowledge-base. In this work, we introduce a Neural Symbolic Machine, which contains (a) a neural "programmer", i.e., a sequence-to-sequence model that maps language utterances to programs and utilizes a key-variable memory to handle compositionality (b) a symbolic "computer", i.e., a Lisp interpreter that performs program execution, and helps find good programs by pruning the search space. We apply REINFORCE to directly optimize the task reward of this structured prediction problem. To train with weak supervision and improve the stability of REINFORCE, we augment it with an iterative maximum-likelihood training process. NSM outperforms the state-of-the-art on the WebQuestionsSP dataset when trained from question-answer pairs only, without requiring any feature engineering or domain-specific knowledge.
1 Introduction
Neural Symbolic Machine combines a neural programmer with a symbolic computer to learn semantic parsers from weak supervision despite discrete execution and large program spaces. Key-variable memory supports compositionality, while search pruning and iterative maximum-likelihood augmentation stabilize REINFORCE training.
- Semantic parsing from weak supervision is difficult because language must map to executable programs over a large space through non-differentiable symbolic operations.
- NSM uses a Manager-Programmer-Computer framework integrating weak task rewards, a neural seq2seq programmer, and a symbolic Lisp interpreter over a large knowledge base.
- Key-variable memory stores and reuses intermediate execution results, enabling the programmer to represent compositional semantics.
- The symbolic computer prunes program search by executing partial programs and checking their syntax and semantics, eliminating invalid choices.
- REINFORCE directly optimizes task reward, while iterative maximum-likelihood training supplies pseudo-gold programs to improve learning from weak supervision.
- On WebQuestionsSP, NSM achieves new state-of-the-art results with weak supervision, significantly closing the gap between weak and full supervision without feature engineering or domain-specific knowledge.
2 Neural Symbolic Machines
NSM combines a neural programmer with a symbolic Lisp computer to map questions into executable programs, using memory and execution feedback for compositional semantic parsing. Training uses REINFORCE with iterative maximum likelihood to address weak supervision and sparse-reward search difficulties.
- Computer: NSM uses a non-differentiable Lisp interpreter to execute programs against a knowledge base and provide code assistance.Each expression returns an entity-list denotation and saves it to a new variable.
- Programmer: Variables let programs save and reuse intermediate execution results, yielding a left-to-right bottom-up derivation of compositional meaning.The interpreter stores each function’s denotation in a new variable for later operations.
- Computer: The interpreter restricts next tokens using syntax and runtime semantics, pruning invalid program continuations during decoding.Runtime validity is checked using denotations stored in variables.
- Programmer: The programmer is an attention-based seq2seq model augmented with key-variable memory for representing and referring to intermediate results.Memory entries pair continuous embedding keys with variable tokens that reference values in the computer.
- Programmer: The key-variable memory dynamically adds variable tokens whose embeddings are generated for each example and trained through decoder selections.Gradients flow from variable selection back to the earlier step that computed the key embedding.
- Training: REINFORCE receives a final-step F1 reward, while iterative maximum likelihood supplies pseudo-gold programs found by beam search.REINFORCE training can be slow because sparse rewards make good programs unlikely early in training.
- Training: Iterative maximum likelihood can select spurious programs that answer training questions correctly but fail to generalize to other questions.The stated example uses PLACEOFBIRTH instead of PLACEOFDEATH when both yield the same place.
3 Experiments and Analysis
NSM achieves state-of-the-art weakly supervised performance on WebQuestionsSP while avoiding feature engineering and domain-specific knowledge. Its performance reflects code-assisted search, augmented REINFORCE, curriculum learning, overfitting controls, and compositional program handling.
- Results: NSM achieves new state-of-the-art performance on WebQuestionsSP with weak supervision and significantly closes the gap between weak and full supervision.The model is trained end-to-end without feature engineering or domain-specific knowledge.
- Results: NSM beats STAGG with weak supervision by a significant margin on all metrics and closes half the gap to STAGG trained with strong supervision.STAGG obtains an F1 of 71.7 with strong supervision.
- Analysis: Semantic checks reduce the average number of choices from 23K per step to less than 100 by restricting tokens using syntax and denotation-based semantic validity.This code assistance is especially effective for open-domain knowledge bases with many properties.
- Analysis: Augmented REINFORCE achieves the best training and validation performance by bootstrapping from pseudo-gold programs found through iterative maximum-likelihood training.Plain REINFORCE gets stuck in a local optimum, while iterative maximum likelihood does not directly optimize F1.
- Analysis: Curriculum learning substantially improves the best programs found in the beam across every metric by gradually increasing function sets and program length.The staged procedure first uses Hop with at most two expressions, then adds Filter and allows three expressions.
- Analysis: 36.7% of generated programs use more than one expression, and performance does not decrease much with greater compositional depth, indicating effective compositionality.Programs with three expressions use a more limited property set, while two-expression programs use more diverse properties and perform worse.
4 Related work
NSM relates to prior neural and symbolic approaches through reinforcement learning, program semantics, and denotation-guided search. Its distinctive choices target compositional reasoning and scalability to Freebase’s large knowledge base.
- RL-NTMs and NSM both control non-differentiable machines with REINFORCE, but NSM operates in a higher-level programming language over a large knowledge base.NSM uses operations such as following properties from entities and sorting by properties, rather than low-level memory manipulation.
- Unlike Neural Programmer and Dynamic-NMN, NSM stores intermediate results in computer memory and refers to them with variable names for scalability.The alternative vector-based memory representations are described as inapplicable to Freebase’s roughly 100M entities and over 20K properties.
- NSM extends weakly supervised semantic parsing by executing partial programs and using their denotations to prune structural search.This addresses the large search space while preserving executable program semantics.
- Compared with PRA, NSM composes more complex semantics, uses a trained neural network to control search, and supports questions expressing complex relations.PRA samples actions uniformly, whereas NSM combines neural search control with key-variable memory.
5 Conclusion
The paper presents MPC and NSM as an end-to-end combination of neural program generation, symbolic execution, and reward-based training. It reports state-of-the-art weakly supervised semantic parsing without feature engineering or domain-specific knowledge.
- NSM combines a neural sequence-to-sequence programmer with key-variable memory and a symbolic Lisp interpreter with code assistance.The interpreter executes programs against a large knowledge base and supports syntax and semantic checking.
- REINFORCE optimizes task reward, while iterative maximum-likelihood training supplies pseudo-gold programs to bootstrap learning.This combination addresses the interpreter’s non-differentiability and stabilizes training under weak supervision.
- NSM achieves new state-of-the-art results on a challenging weakly supervised semantic parsing dataset and significantly closes the gap with full supervision.The reported system is trained end-to-end without feature engineering or domain-specific knowledge.
A.1 Extra Figures
The extra figures depict the MPC framework, the programmer’s attention-based sequence-to-sequence architecture, and the distributed system configuration.
- Figure 3 depicts the Manager-Programmer-Computer framework.
- Figure 4 shows a sequence-to-sequence architecture with dot-product attention and dropout at GRU input, output, and softmax layers.
- Figure 5 shows a system architecture with 100 decoders, 50 KB servers, and 1 trainer.