CAN PAC LEARNING ALGORITHMS TOLERATE RANDOM ATTRIBUTE NOISE
CAN PAC LEARNING ALGORITHMS TOLERATE RANDOM ATTRIBUTE NOISE
复制标题
DOI：
10.1007/bf01300374
复制
发表时间：
1995-07-01
期刊：
影响因子：
1.1
通讯作者：
SLOAN, RH
中科院分区：
文献类型：
--
作者：
GOLDMAN, SA;SLOAN, RH
本文研究了实例空间为{0,1}(n)时PAC学习算法的鲁棒性，并且示例受到仅影响属性（而不影响标签）的纯随机噪声的破坏。对于均匀属性噪声，即每个属性以相同的概率独立随机翻转，我们提出了一种PAC学习任何（未知）噪声率小于1/2的单项式的算法。对比这个积极的结果，我们证明了产品随机属性噪声，其中每个属性i以其自己的概率p(i)随机独立翻转，几乎和恶意噪声一样有害-没有算法可以容忍超过非常少量的此类噪声。
This paper studies the robustness of PAC learning algorithms when the instance space is {0, 1}(n), and the examples are corrupted by purely random noise affecting only the attributes (and not the labels). For uniform attribute noise, in which each attribute is flipped independently at random with the same probability, we present an algorithm that PAC learns monomials for any (unknown) noise rate less than 1/2. Contrasting this positive result, we show that product random attribute noise, where each attribute i is flipped randomly and independently with its own probability p(i), is nearly as harmful as malicious noise-no algorithm can tolerate more than a very small amount of such noise.