Technical Report CS-2000-07

 TR#: CS-2000-07 Class: CS Title: Efficient Agnostic Learning of Linear Perceptrons Authors: Shai Ben-David and Hans Ulrich Simon PDF CS-2000-07.pdf Abstract: We introduce an efficient agnostic learning algorithm for the class of half-spaces in $\Re^n$. We make no assumptions whatsoever on the example-generating distribution. Our performance guarantee is that, given any $\eta >0$, our algorithm runs in time polynomial in the sample size and dimension, and outputs a hypothesis half-space that classifies correctly at least the number of points classified correctly with margin $\eta$ by any other half-space. While our algorithm's running time is {\em not} polynomial in $1/\eta$, we prove that unless P$=$NP no such `fully polynomial' approximation scheme exists. 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/2000/CS/CS-2000-07), rather than to the URL of the PDF files directly. The latter URLs may change without notice.