| TR#: | CS0963 |
| Class: | CS |
| Title: | PAC Learning with Nasty Noise |
| Authors: | Nader H. Bshouty, Nadav Eiron and Eyal Kushilevitz |
| CS0963.pdf | |
| Abstract: | We introduce a new model for learning in the presence of noise, which we call the {\em Nasty Noise} model. This model generalizes previously considered models of learning with noise. The learning process in this model, which is a variant of the PAC model, proceeds as follows: Suppose that the learning algorithm during its execution asks for $m$ examples. The examples that the algorithm gets are generated by a nasty adversary that works according to the following steps. First, the adversary chooses $m$ examples (independently) according to the fixed (but unknown to the learning algorithm) distribution $D$ as in the PAC-model. Then the powerful adversary, upon seeing the specific $m$ examples that were chosen (and using his knowledge of the target function, the distribution $D$ and the learning algorithm), is allowed to remove a fraction of the examples at its choice, and replace these examples by the same number of arbitrary examples of its choice; the $m$ modified examples are then given to the learning algorithm. The only restriction on the adversary is that the number of examples that the adversary is allowed to modify should be distributed according to a binomial distribution with parameters $\eta$ (the noise rate) and $m$. On the negative side, we prove that no algorithm can achieve accuracy of $\epsilon< 2\eta$ in learning any non-trivial class of functions. On the positive side, we show that a polynomial (in the usual parameters, and in $\epsilon-2\eta$) number of examples suffice for learning any class of finite VC-dimension with accuracy $\epsilon>2\eta$. This algorithm may not be efficient; however, we also show that a fairly wide family of concept classes can be {\em efficiently} learned in the presence of nasty noise. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1999/CS/CS0963), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 1999
To the main CS technical reports page