Robust Learning of Fixed-Structure Bayesian Networks.

A MATLAB implementation of Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time.

Explanation of Files

Our algorithms (robust directory)

• main.m: Evaluate the performance of different algorithms (MLE, Filtering, and ours) when the graph structure of the ground-truth Bayes net is an empty graph, a random tree, or a random graph.
• Our algorithm uses robust mean estimations in a black-box manner. We provide two examples of such algorithms.
  • robust_mean_pgd.m: run gradient descent on a natural non-convex formulation of the problem (from High-Dimensional Robust Mean Estimation via Gradient Descent).
  • robust_mean_filter.m: run one-iteration of the Filtering algorithm (from Robust Estimators in High Dimensions without the Computational Intractability).
  • Other robust mean estimation algorithms based on stability of first two moments would work as well. For example, Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection and its implementation.
• We use the following basic functions in main.m.
  • dtv_bn.m: Estimate the total variation distance (via sampling) between two Bayes nets that have the same structure.
  • empirical_cond_mean.m: Compute the empirical conditional probabilities of a known-structure Bayes net.
  • empirical_parental_prob.m: Compute the empirical parental configuration probabilities of a known-structure Bayes net.

Reference

This repository is an implementation of the paper Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time which appeared in ICLR 2021, authored by Yu Cheng and Honghao Lin.

@inproceedings{ChengL21,
  author    = {Yu Cheng and
               Honghao Lin},
  title     = {Robust Learning of Fixed-Structure {B}ayesian Networks in Nearly-Linear Time},
  booktitle = {Proceedings of the 9th International Conference on Learning Representations (ICLR)},
  publisher = {OpenReview.net},
  year      = {2021}
}