Evolutionary Synthesis of Probabilistic Programs

Abstract # ↰

Modeling the relationships between variables through probability distributions lies at the core of probabilistic models, enabling reasoning under uncertainty. Probabilistic programming offers an effective way to represent these models by blending the simplicity of standard programming constructs with the power of automatic inference algorithms. The languages for expressing probabilistic programs are augmented with primitives representing various probability distributions to effectively capture the stochastic behavior inherent in the data. However, writing a probabilistic program is hard, because it typically requires prior knowledge about the data generation mechanism. In this work, we propose a framework for automatically synthesizing probabilistic programs directly from data, thereby learning the underlying relationships between variables and the data-generating process. We adopt an evolutionary approach, specifically grammatical evolution, to extensively explore the space of probabilistic programs, aiming to discover the most likely program that describes the observed data. We experimentally evaluate our method across several benchmarks, incorporating varying levels of prior knowledge through a sketching strategy embedded into the grammar to demonstrate the potential of an evolutionary framework. This evaluation highlights the flexibility and effectiveness of grammatical evolution in synthesizing probabilistic programs under different informational constraints.