Robust Learning of Fixed-Structure Bayesian Networks

By Yu Cheng, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart. 2016

47 citations recorded by the source corpus.

We investigate the problem of learning Bayesian networks in a robust model where an $\epsilon$-fraction of the samples are adversarially corrupted. In this work, we study the fully observable discrete case where the structure of the network is given. Even in this basic setting, previous learning algorithms either run in exponential time or lose dimension-dependent factors in their error guarantees. We provide the first computationally efficient robust learning algorithm for this problem with dimension-independent error guarantees. Our algorithm has near-optimal sample complexity, runs in polynomial time, and achieves error that scales nearly-linearly with the fraction of adversarially corrupted samples. Finally, we show on both synthetic and semi-synthetic data that our algorithm performs well in practice.

Subfields: Artificial Intelligence, Control and Systems Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Control and Systems Engineering

Citations in the corpus

Robustly Learning a Gaussian: Getting Optimal Error, Efficiently (2017, unknown): “This includes studying graphical models in the presence of noise [DKS16], tolerating much more noise by”
Deep Neural Network Concepts for Background Subtraction: A Systematic Review and Comparative Evaluation (2018, background): “Theoretical aspects concern mainly the understanding and the provability of DNNs [145,194,195,219], but also their properties in presence of adversarial perturbations [34,137,138,139,140,186,231], and their robustness in presence of noisy labels [189].”
High-Dimensional Robust Mean Estimation in Nearly-Linear Time (2018, background): “Since the dissemination of [DKK + 16, LRV16], there has been a ﬂurry of research activity on robust learning algorithms in both supervised and unsupervised settings [BDLS17, CSV17, DKK + 17, DKS17, DKK + 18a, SCV18, DKS18b, DKS18a, HL18, KSS18, PSBR18, DKK + 18b, KKM18, DKS19, LSLC18, CDKS18].”
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers (2017, background): “…recently that provable algorithms for learning in the presence of a large fraction of arbitrary (and potentially adversarial) data have been formulated in high-dimensional settings (Diakonikolas et al., 2016; Lai et al., 2016; Charikar et al., 2017; Steinhardt et al., 2016; Bhatia et al., 2015).”