publication . Preprint . 2016

Robust Learning of Fixed-Structure Bayesian Networks

Cheng, Yu; Diakonikolas, Ilias; Kane, Daniel; Stewart, Alistair;
Open Access English
  • Published: 23 Jun 2016
Abstract
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 fr...
Subjects
free text keywords: Computer Science - Data Structures and Algorithms, Computer Science - Artificial Intelligence, Computer Science - Machine Learning, Mathematics - Statistics Theory
Download from
22 references, page 1 of 2

[ADLS15] J. Acharya, I. Diakonikolas, J. Li, and L. Schmidt. Sample-optimal density estimation in nearly-linear time. CoRR, abs/1506.00671, 2015. [OpenAIRE]

[AHHK12] A. Anandkumar, D. J. Hsu, F. Huang, and S. Kakade. Learning mixtures of tree graphical models. In NIPS, pages 1061-1069, 2012.

[CDSS14b] S. Chan, I. Diakonikolas, R. Servedio, and X. Sun. Near-optimal density estimation in near-linear time using variable-width histograms. In NIPS, pages 1844-1852, 2014. [OpenAIRE]

[CGR15a] M. Chen, C. Gao, and Z. Ren. A general decision theory for huber's ǫ-contamination model. CoRR, abs/1511.04144, 2015.

[CGR15b] M. Chen, C. Gao, and Z. Ren. Robust covariance matrix estimation via matrix depth. CoRR, abs/1506.00691, 2015.

C. Chow and C. Liu. Approximating discrete probability distributions with dependence trees. IEEE Trans. Inf. Theor., 14(3):462-467, 1968. [OpenAIRE]

Machine Learning, 29(2-3):165-180, 1997.

C. Daskalakis, I. Diakonikolas, and R.A. Servedio. Learning k-modal distributions via testing. In SODA, pages 1371-1385, 2012. [OpenAIRE]

[DKK+16] I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. Robust estimators in high dimensions without the computational intractability. CoRR, abs/1604.06443, 2016. [OpenAIRE]

[DKW56] A. Dvoretzky, J. Kiefer, and J. Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. Ann. Mathematical Statistics, 27(3):642-669, 1956. [OpenAIRE]

The Knowledge Engineering Review, 26:99-157, 2011.

M. Hardt and A. Moitra. Algorithms and hardness for robust subspace recovery. In COLT 2013, pages 354-375, 2013.

[HRRS86] F. R. Hampel, E. M. Ronchetti, P. J. Rousseeuw, and W. A. Stahel. Robust statistics. The approach based on influence functions. Wiley New York, 1986.

P. J. Huber. Robust estimation of a location parameter. Ann. Math. Statist., 35(1):73- 101, 03 1964.

F. V. Jensen and T. D. Nielsen. Bayesian Networks and Decision Graphs. Springer Publishing Company, Incorporated, 2nd edition, 2007.

22 references, page 1 of 2
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue