DocumentCode :
2262352
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
fYear :
1997
fDate :
17-19 Jun 1997
Firstpage :
45
Lastpage :
53
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;
fLanguage :
English
Publisher :
ieee
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
Type :
conf
DOI :
10.1109/ISTCS.1997.595156
Filename :
595156
Link To Document :
بازگشت