γ-ABC: Outlier-Robust Approximate Bayesian Computation based on Robust Divergence Estimator

Masahiro Fujisawa, Takeshi Teshima, Issei Sato

Introduction

Approximate Bayesian Computation (ABC) provides a "likelihood-free" framework for statistical inference in complex models where the likelihood function is intractable. By comparing simulated data to observed data using a discrepancy measure, ABC identifies parameter sets that likely generated the observations. However, standard ABC is notoriously sensitive to outliers. Discrepancy measures like Kullback-Leibler (KL) divergence or Maximum Mean Discrepancy (MMD) often fail when observed data is contaminated, leading to biased posterior estimates.

Methodology: The γ-ABC Approach

To address this, the authors propose γ-ABC, which utilizes a $k$-nearest-neighbor ($k$-NN) estimator of γ-divergence. Unlike standard $f$-divergences, γ-divergence is inherently robust to heavy contamination due to its "redescending property"—the influence of an outlier on the estimator diminishes to zero as the outlier moves further from the true distribution.

Computational Efficiency

A significant advantage of the proposed $k$-NN estimator is its scalability. By leveraging KD trees for neighbor searches, the algorithm achieves a computational complexity of $O(N \log N)$, where $N$ is the number of samples. This makes it significantly more efficient than previous robust ABC methods, such as those based on MONK-BCD, which often exhibit cubic time complexity.

Discrepancy error comparison across different contamination rates (η). While KL divergence error grows with contamination, the γ-divergence estimator remains stable.

Experimental Evaluation

The robustness of γ-ABC was tested across several benchmark models, including Gaussian Mixture Models, M/G/1 queuing models, and Multivariate g-and-k distributions. Artificial contamination was introduced using Huber’s model, replacing 10% to 20% of the data with extreme outliers to evaluate which methods could maintain accuracy.

Results

The experimental results demonstrate that γ-ABC consistently outperforms traditional and existing robust methods. As shown in the discrepancy error analysis, the γ-divergence estimator maintains low error even under 20% contamination, whereas the KL divergence estimator's error increases significantly as it attempts to account for noise.

Simulation error (log) vs. contamination rate (η) for various ABC methods. γ-ABC (blue) demonstrates superior robustness and lower error compared to alternatives like Wasserstein distance or MMD.

In terms of parameter estimation, γ-ABC achieved the lowest Mean Squared Error (MSE) across all contaminated benchmarks. Posterior distributions generated by γ-ABC remained centered on the ground truth, while other methods were significantly skewed by the presence of outliers.

Conclusion

γ-ABC offers a robust and computationally efficient solution for likelihood-free inference in the presence of messy data. By combining the theoretical robustness of γ-divergence with the practical efficiency of $k$-NN estimation, it provides a reliable tool for researchers in fields dealing with noisy observational data. Future work will focus on addressing the curse of dimensionality inherent in $k$-NN methods to extend this approach to higher-dimensional datasets.

Summary updated

BibTeX
@inproceedings{fujisawa2021abc,
  author = {Masahiro Fujisawa and Takeshi Teshima and Issei Sato},
  title = {{γ-ABC: Outlier-Robust Approximate Bayesian Computation based on Robust Divergence Estimator}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=QjXeDWb76Jf},
}
Figure