Abstract
Approximate Bayesian Computation (ABC) provides a powerful framework for likelihood-free inference, yet it has traditionally been optimized for continuous parameter spaces. We present ABC-Di, a framework specifically designed for discrete data. By introducing the Discrete Differential Evolution Markov Chain (dde-mc) kernel, which utilizes logical XOR operations as a discrete analog to vector subtraction, we enable efficient posterior estimation in complex discrete domains. Our evaluations across medical diagnosis networks, high-dimensional binary neural networks, and neural architecture search demonstrate that ABC-Di significantly outperforms standard discrete sampling methods.
Introduction
In many scientific and engineering domains, we rely on high-fidelity simulators to model complex processes. However, these "black-box" simulators often lack a tractable mathematical likelihood function, making traditional Bayesian inference impossible. Likelihood-free inference, particularly Approximate Bayesian Computation (ABC), has emerged to solve this by comparing simulated data to observed data.
While ABC is well-established for continuous variables, discrete state spaces (e.g., binary sequences, categorical choices) present unique challenges. Researchers often use continuous relaxations like the Gumbel-Softmax to adapt these problems, but these can be inefficient or inaccurate. ABC-Di addresses this gap by providing a native, efficient framework for discrete likelihood-free inference.
Methods: Discrete Differential Evolution
ABC-Di utilizes a Population-based MCMC ABC approach, running multiple Markov chains in parallel that interact to explore the search space more effectively. The core innovation is the Discrete Differential Evolution Markov Chain (dde-mc) kernel.
The XOR Operator
In continuous Differential Evolution, a new proposal is generated by adding a scaled difference between two existing points ($x_i + \gamma(x_j - x_k)$). In a discrete binary space, subtraction is undefined. ABC-Di replaces this with the logical XOR ($\otimes$) operator. XOR identifies the specific bits that differ between two chains, allowing the algorithm to "jump" in directions that have already proven successful for other members of the population.
Adaptive Tolerance
ABC relies on a tolerance parameter $\epsilon$, where simulated data is accepted only if its distance from the real data is less than $\epsilon$. Rather than using a fixed value, ABC-Di samples $\epsilon$ from an exponential distribution. This adaptive approach balances exploration (large $\epsilon$ early on) with exploitation (small $\epsilon$ as the chains converge), preventing the algorithm from getting stuck in local optima.
Experimental Results
Benchmark: QMR-DT Network
The framework was first validated on the QMR-DT medical diagnosis network. In likelihood-free settings, the dde-mc kernel demonstrated significantly faster convergence and lower average error compared to standard mutation-based kernels and independent sampling.
High-Dimensional Challenges: Binary Neural Networks
To test scalability, the authors trained a Binary Neural Network (BinNN) with nearly 4,000 parameters on the MNIST dataset. Training binary weights is a notoriously difficult discrete optimization problem. ABC-Di successfully navigated this high-dimensional space, achieving competitive test error rates (~1.3%) and outperforming simpler sampling baselines.
Neural Architecture Search (NAS)
Finally, the framework was applied to NAS-Bench-101 to find optimal neural network topologies. The dde-mc kernel identified high-performing architectures more efficiently than baseline methods, proving its utility for practical automated machine learning tasks.
Conclusion and Future Work
ABC-Di successfully ports the efficiency of Differential Evolution to discrete likelihood-free inference. By leveraging logical operators like XOR, the method is not only mathematically sound but also computationally efficient, with significant potential for hardware-level acceleration on FPGAs.
Future research will focus on scaling to even higher dimensions and incorporating domain-specific summary statistics. Moving toward Sequential Monte Carlo (SMC) variants of the ABC-Di framework may further enhance robustness for models with highly complex posterior distributions.
Summary updated