Title :
Learning with queries corrupted by classification noise
Author :
Jackson, Jeffrey ; Shamir, Eli ; Shwartzman, Clara
Author_Institution :
Dept. of Math. & Comput. Sci., Duquesne Univ., Pittsburgh, PA, USA
Abstract :
Kearns introduced the “statistical query” (SQ) model as a general method for producing learning algorithms which are robust against classification noise. We extend this approach in several ways, in order to tackle algorithms that use “membership queries”: focusing on the more stringent model of “persistent noise”. The main ingredients in the general analysis are: (1) Smallness of dimension of both the targets´ class and the queries´ class. (2) Independence of the noise variables. Persistence restricts independence forcing repeated invocation of the same point x to give the same label. We apply the general analysis and ad-hoc considerations to get noise-robust version of Jackson´s Harmonic Sieve (1995), which learns DNF under the uniform distribution. This corrects an error in his earlier analysis of noise tolerant DNF learning
Keywords :
learning by example; statistical analysis; Harmonic Sieve; classification noise; learning algorithms; membership queries; noise-robust version; persistent noise; statistical query; uniform distribution; Computer science; Harmonic analysis; Learning systems; Mathematical model; Mathematics; Noise robustness; Probability distribution; Random variables; Sampling methods; Statistical distributions;
Conference_Titel :
Theory of Computing and Systems, 1997., Proceedings of the Fifth Israeli Symposium on
Conference_Location :
Ramat-Gan
Print_ISBN :
0-8186-8037-7
DOI :
10.1109/ISTCS.1997.595156