|
Abstract : |
This paper studies the robustness of PAC learning algorithms when the instance space is f0; 1g 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., |
