Neural Program Planner for Structured Predictions

Jacob Biloki, Chen Liang, Ni Lao

In the world of natural language processing, semantic parsing is the art of translating a human question (like "Which city hosted the most Olympics?") into a machine-executable program (like a SQL query). While Reinforcement Learning (RL) has made huge strides in this area, most models act like a driver looking only five feet in front of their bumper.

A paper from ICLR 2019, Neural Program Planner for Structured Predictions, argues that we should give these models a map and a chance to plan. By introducing a Neural Program Planner (NPP), the authors demonstrate how a "second-look" re-ranking stage can significantly improve the accuracy of complex program synthesis.

TL;DR

The Neural Program Planner (NPP) improves semantic parsing by treating it as a planning problem rather than just a sequence generation task. By re-ranking candidate programs using global context and "program agreement" features, NPP achieved a new state-of-the-art accuracy of 47.2% on the challenging WikiTableQuestions benchmark.

What Problem Does This Paper Address?

Most semantic parsers use "model-free" RL. They generate a program token-by-token, with each choice based on a locally normalized probability. This leads to two major issues:

  1. Exposure Bias: The model only sees its own (potentially wrong) choices during training.
  2. Spurious Programs: In "weakly supervised" settings (where the model only knows if the final answer is right, not if the code is correct), the model often learns "spurious" programs—code that accidentally hits the right answer for the wrong reasons.

The authors point out that unlike playing a video game where the future is uncertain, the environment in structured prediction (like a database) is deterministic and known. We have a "perfect model" of the world. The gap they address is the failure of current models to leverage this perfect model to plan and evaluate full programs before committing to an answer.

Methods

The authors propose a two-stage pipeline. First, a search policy (specifically MAPO, or Memory Augmented Policy Optimization) generates a "beam" of candidate programs. Then, the Neural Program Planner (NPP) steps in to re-rank them.

Architecture of the Neural Program Planner

The NPP Architecture

NPP is a scoring model that looks at the entire candidate program at once. The architecture uses a Bi-Directional LSTM to capture the full sequence context, followed by a 1D Convolutional layer (kernel size 3) to capture local functional patterns (like filter_in followed by a column name).

To evaluate the programs, the model relies on several key features:

Features used by the Neural Program Planner
  • Token Alignment ($q^{tok}$, $q^{attn}$): Does the program token match words in the question?
  • Search Probabilities ($p^{prob}$, $t^{prob}$): What did the original search policy think of this token and the overall program?
  • Program Agreement ($t^{agree}$): This is a novel feature. It counts how many other candidate programs in the beam share the same token at the same position. This helps the model identify "safe" common paths versus "risky" divergent ones.

Stacked Learning

To train NPP without bias, the authors used stacked learning. They split the training data into $K$ folds, trained $K$ different search models, and used them to generate "unseen" candidate programs for the NPP to practice ranking. This prevents the NPP from simply memorizing the quirks of a single search policy.

Datasets

The primary evaluation was performed on WikiTableQuestions (WTQ).

  • WTQ consists of 22,033 question-answer pairs over 2,108 Wikipedia tables.
  • It is notoriously difficult because the tables cover a vast range of topics, and the model must perform multi-step reasoning (comparisons, superlatives, aggregations) on tables it has never seen before.

Key Insights and Ideas

  • Planning vs. Searching: The core "aha" moment is that in deterministic environments, we shouldn't just search; we should plan. By looking at the full execution output and the global context of the beam, the model can catch errors that a token-by-token generator would miss.
  • The Power of Agreement: The "program agreement" feature is a clever way to use the "wisdom of the crowd" within the beam search. If 10 different programs all agree on a specific filter, that filter is likely correct.
  • Demoting Spuriousness: NPP is particularly good at demoting programs that ignore important parts of the question. For example, if a question asks for the "latest" match and the top program ignores the date column, NPP can recognize this lack of "utility" and pick a program that actually uses the date.

Key Results

  • State-of-the-Art: NPP achieved 47.2% accuracy on WikiTableQuestions, a 0.9% improvement over the previous state-of-the-art (MAPO ensemble).
  • Consistency: NPP consistently improved performance across different settings, whether used with a single model or an ensemble.
  • Feature Importance: Ablation studies showed that the program probability from the search policy was the most vital feature, but the program agreement and question-matching features provided the necessary edge to correct the search policy's mistakes.

Limitations and Future Work

  • Beam Dependency: NPP is a re-ranker. If the correct program isn't in the initial beam generated by the search policy, NPP has no way to find it. It can only choose the "best of the bunch."
  • Computational Overhead: Adding a second neural ranking stage increases the inference time, which might be a concern for real-time applications.
  • Future Directions: The authors suggest that future work could involve integrating the planning stage more deeply into the search process itself, rather than having it as a post-processing step, potentially allowing the planner to guide the search in real-time.

Summary updated

Abstract

We consider the problem of weakly supervised structured prediction (SP) with reinforcement learning (RL) – for example, given a database table and a question, perform a sequence of computation actions on the table, which generates a response and receives a binary success-failure reward. This line of research has been successful by leveraging RL to directly optimizes the desired metrics of the SP tasks – for example, the accuracy in question answering or BLEU score in machine translation. However, different from the common RL settings, the environment dynamics is deterministic in SP, which hasn’t been fully utilized by the model-freeRL methods that are usually applied. Since SP models usually have full access to the environment dynamics, we propose to apply model-based RL methods, which rely on planning as a primary model component. We demonstrate the effectiveness of planning-based SP with a Neural Program Planner (NPP), which, given a set of candidate programs from a pretrained search policy, decides which program is the most promising considering all the information generated from executing these programs. We evaluate NPP on weakly supervised program synthesis from natural language(semantic parsing) by stacked learning a planning module based on pretrained search policies. On the WIKITABLEQUESTIONS benchmark, NPP achieves a new state-of-the-art of 47.2% accuracy.
BibTeX
@inproceedings{biloki2019neural,
  author = {Jacob Biloki and Chen Liang and Ni Lao},
  title = {{Neural Program Planner for Structured Predictions}},
  booktitle = {DeepRLStructPred @ ICLR},
  year = {2019},
}
Figure