Robust Learning of Fixed-Structure Bayesian Networks
Robust Learning of Fixed-Structure Bayesian Networks
复制标题
DOI：
--
复制
发表时间：
2016-06
期刊：
影响因子：
--
通讯作者：
Yu Cheng;Ilias Diakonikolas;D. Kane;Alistair Stewart
中科院分区：
文献类型：
--
作者：
Yu Cheng;Ilias Diakonikolas;D. Kane;Alistair Stewart
我们在强大的模型中研究了学习贝叶斯网络的问题，在这种模型中，$ \ epsilon $ - 样品的差异是对抗性损坏的。在这项工作中，我们研究了给出网络结构的完全可观察到的离散情况。即使在这种基本环境中，以前的学习算法要么以指数时间运行，要么在其错误保证中失去依赖维度的因素。我们为此问题提供了第一个具有无关的错误错误保证的计算有效的鲁棒学习算法。我们的算法具有接近最佳的样本复杂性，在多项式时间内运行，并达到误差，与对抗性损坏的样本的比例几乎是线性的。最后，我们在合成和半合成数据上显示了我们的算法在实践中的表现良好。
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.