Introduction
Traditional machine learning typically involves fitting parameters to a fixed model or finding deterministic functions. However, many real-world processes are better described as stochastic programs—executable procedures that generate samples from a distribution. This paper addresses the challenge of "learning" these generative models by representing the model itself as program text. By treating program induction as a Bayesian inference problem, the authors demonstrate that machines can automatically generate efficient sampling algorithms directly from data.
Methodology
The authors utilize Anglican, a Turing-complete, higher-order probabilistic programming language (PPL). Anglican's eval function allows the system to treat program code as data, enabling its execution during the inference process.
The learning framework consists of three primary components:
- Generative Prior over Programs: A grammar-based prior, informed by a corpus of human-written code for common statistical distributions, guides the search toward readable and efficient algorithms.
- MCMC-ABC (Approximate Bayesian Computation): To navigate the vast, discrete space of possible programs, the system uses ABC to compare summary statistics (mean, variance, skewness, and kurtosis) of samples from candidate programs against the observed data.
- Hierarchical Modeling: The system learns programs that can take parameters as input (e.g., a Bernoulli sampler with parameter $\theta$), ensuring that the generated code generalizes across different settings rather than overfitting a single dataset.
Experimental Evaluation
The approach was evaluated using synthetic distributions (including Bernoulli, Poisson, Gamma, Beta, and Normal), real-world features from a credit approval dataset, and a collection of existing statistical sampling procedures. These experiments tested the system's ability to discover exact algorithms and to generate samplers for complex, unknown empirical distributions.
Results and Discussion
The results demonstrate a powerful proof-of-concept for automated algorithm discovery. The system successfully inferred exact human-standard code for simple cases like the Bernoulli distribution. For more complex distributions, the generated programs produced samples that closely matched the target statistical profiles.
As illustrated in the grid above, the framework is capable of capturing a wide variety of distribution shapes. This highlights the expressiveness of the "programs as models" paradigm, which allows for representations involving loops, recursion, and complex conditional logic.
A key innovation presented is "probabilistic program compilation," where the system automatically generates a new, efficient standalone program that samples directly from the posterior of a more complex model. This effectively automates the creation of high-performance inference algorithms.
Conclusion
While the computational cost of searching program space remains a significant hurdle, this work shows that Bayesian program induction is a viable path toward automated programming in the probabilistic domain. Future work will focus on incremental learning, allowing the system to build and reuse a library of learned subroutines to solve increasingly complex problems, much like a human programmer.
Summary updated