Document Type
Technical Report
Publication Date
1992-07-10
Technical Report Number
WUCS-92-25
Abstract
This paper studies the robustness of pac learning algorithms when the instances space is {0,1}n, and the examples are corrupted by purely random noise affecting only the instances (and not the labels). In the past, conflicting results on this subject have been obtained -- the "best agreement" rule can only tolerate small amounts of noise, yet in some cases large amounts of noise can be tolerated. We show that the truth lies somewhere in between these two alternatives. 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 pi, is nearly as harmful as malicious noise-- no algorithm can tolerate more than a very small amount of such noise.
Recommended Citation
Goldman, Sally A. and Sloane, Robert H., "Can PAC Learning Algorithms Tolerate Random Attribute Noise?" Report Number: WUCS-92-25 (1992). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/588
Comments
Permanent URL: http://dx.doi.org/10.7936/K78W3BPX