Sampling for Bayesian Program Learning

Kevin Ellis, Armando Solar-Lezama, Josh TenenbaumNeurIPS 2016 · OpenReview

Introduction

Towards learning programs from data, researchers face the challenge of extreme ambiguity. When a user provides only one or two examples of a desired behavior, thousands of potential programs might fit the bill. This paper introduces PROGRAMSAMPLE, an algorithm designed to sample programs from a posterior distribution conditioned on user data, rather than simply searching for a single "best" program. By combining constraint-based program synthesis with random parity (XOR) constraints, the authors provide a robust method to handle ambiguity while maintaining theoretical guarantees on sample quality.

The Challenge of Ambiguity in Program Learning

In "Programming by Example" (PbE), a user provides a few inputs and outputs, and the system attempts to synthesize a program that performs the corresponding transformation.

Multiple programs can satisfy a single input-output example, illustrating the ambiguity in Programming by Example.

The core challenge in this domain is ambiguity. As illustrated above, if you only provide one example (e.g., transforming "1/21/2001" to "01"), numerous programs can satisfy it. Some might extract the last two digits, while others might extract the characters after the last slash, or simply return the constant "01".

Traditional systems typically resolve this by finding the "Maximum Description Length" (MDL) solution—the single shortest program. However, the shortest program is not always what the user intended. To represent this uncertainty accurately, program induction must be treated as a Bayesian inference problem: sampling from a distribution of programs $p(\text{program} | \text{data})$. The primary technical hurdle is that program spaces have "high tilt"—short programs are exponentially more likely than long ones, making standard statistical sampling algorithms prohibitively slow.

Methodology: The PROGRAMSAMPLE Algorithm

The authors propose PROGRAMSAMPLE, an algorithm that "upgrades" a standard SAT-based program synthesizer into a probabilistic sampler. The approach involves several key steps:

Converting a program sketch and specification into a Boolean satisfiability (SAT) formula.
  1. Sketching: The system uses the "Sketch" framework, where a user provides a high-level template (a grammar) of the expected program. This restricts the search space to a finite, albeit massive, set of possibilities.
  2. SAT Encoding: The program learning problem is converted into a Boolean satisfiability (SAT) formula. A solution to this formula corresponds to a program that satisfies the input/output examples.
  3. Tilt Correction: To handle the extreme probability differences between short and long programs, the authors introduce a "low-tilt approximation." They establish a cutoff length $d$. Programs shorter than $d$ are weighted normally, while all programs longer than $d$ are treated as having the same length.
  4. Random Parity Constraints: To sample nearly uniformly from this adjusted space, random XOR constraints (random projections mod 2) are added to the SAT formula. These constraints effectively "slice" the solution space until only a few valid solutions remain.
  5. Rejection Sampling: Finally, a rejection sampling step corrects the approximation made during tilt correction, ensuring the final samples are drawn from the true posterior distribution.

Key Insights and Results

Reifying the Tilt

The most significant algorithmic contribution is recognizing that "tilt" (the ratio between the most and least likely solutions) is the primary bottleneck for solver-based sampling. By making tilt a tunable parameter, the authors make sampling tractable in domains where it was previously impossible. Constraint solvers are uniquely adept at finding rare solutions in massive spaces; by using a SAT solver as the engine, the authors leverage decades of optimization in symbolic reasoning to perform statistical inference.

Evaluation and Performance

The algorithm was evaluated on 22 program learning problems across two main domains: text editing (adapted from the FlashFill domain) and list manipulation (testing recursive structures like sorting and reversing).

  • Efficiency: PROGRAMSAMPLE generated samples for text editing tasks in roughly 21 to 84 seconds per attempt. Without the novel "tilt correction" method, standard baselines failed to produce a single sample within an hour.
  • Accuracy through Diversity: In one-shot learning scenarios, the sampling approach frequently outperformed the standard "MDL learner" (which only picks the shortest program). By presenting a "Top 3" list of the most frequent samples, the system successfully solved significantly more problems than a system restricted to a single point estimate.
  • Recursive Learning: The system successfully learned complex recursive algorithms, such as Quicksort-style partitioning, from just a few examples while maintaining a proper distribution over potential, simpler (but incorrect) programs.

Limitations and Future Work

While powerful, the method requires the entire problem to be represented symbolically as a SAT/SMT formula. This limits its applicability to programs involving complex numerical routines or large-scale data that do not fit well into a solver. Furthermore, the system relies heavily on the provided "sketch"; if the grammar is too broad, the search space explodes, but if it is too narrow, the target program cannot be found.

Future work may extend this approach to semantic parsing (mapping natural language to logic) and transfer learning, where the system could learn the "prior" (the sketch itself) from previous tasks to accelerate future inference.

Summary updated

Abstract

Towards learning programs from data, we introduce the problem of sampling programs from posterior distributions conditioned on that data. Within this setting, we propose an algorithm that uses a symbolic solver to efficiently sample programs. The proposal combines constraint-based program synthesis with sampling via random parity constraints. We give theoretical guarantees on how well the samples approximate the true posterior, and have empirical results showing the algorithm is efficient in practice, evaluating our approach on 22 program learning problems in the domains of text editing and computer-aided programming.
BibTeX
@inproceedings{ellis2016sampling,
  author = {Kevin Ellis and Armando Solar-Lezama and Josh Tenenbaum},
  title = {{Sampling for Bayesian Program Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=r1Wq58ZdWr},
}
Figure