On Learning Conjunctions with Malicious Noise.
Yishay Mansour, Michal Parnas · 1996
We show how to learn monomials in the presence of malicious noise, when the underlined distribution is a product distribution. We show that our results apply not only to product distributions but to a wide class of distributions. 1 Introduction The Probably Approximately Correct (PAC) Learning model [Val84] has been the most widely studied model in Computational Learning Theory. From the beginning of the field, it has been considered of the utmost importance to develop algorithms that are tolerant to noise. A variety of noise models were studied. The most notable ones are the random classification noise, where the classification of the examples may be flipped randomly, and the malicious noise model, where there is no assumptions about the way in which the corrupted examples are generated. A general framework to handle noise is the Statistical Query model [K93], which was originally aimed at the random classification noise model, and later extended to the malicious noise model [D93]. (...