Learning Discrete Energy-based Models via Auxiliary-variable Local Exploration

Discrete structures play an important role in applications like program language modeling, and software engineering. Current approaches to predicting complex structures typically consider autoregressive models for their tractability, with some sacrifice of the flexibility. Energy-based models (EBMs) on the other hand offer a more flexible and thus more powerful approach to modeling such distributions. Learning and inference with EBMs requires the partition function estimation which is intractable in general. For discrete structured data this is even more challenging due to the absence of gradients. In this paper we propose ALOE, a new algorithm for learning conditional and unconditional EBMs for discrete, structured data, where parameter gradients are estimated using a learned sampler mimicking random local search, and thus, achieving a better trade-off between flexibility and tractability. We show that the sampler can still be trained efficiently using a bias reduction principle that alternates between importance reweighted maximum likelihood estimation and Gibbs sampling. Experimentally, we show that learning local search leads to significant improvements on two different domains in program synthesis and software engineering. Most notably, our energy model guided fuzzer for software testing can achieve comparable performance to well engineered fuzzing engines like libfuzzer on some targets.

• Machine Intelligence

• Software Systems