### Noise-tolerant learning, the parity problem, and the statistical query modelNoise-tolerant learning, the parity problem, and the statistical query model

Access Restriction
Subscribed

 Author Blum, Avrim ♦ Kalai, Adam ♦ Wasserman, Hal Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2003 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Computational learning theory ♦ Machine learning ♦ Statistical queries Abstract We describe a slightly subexponential time algorithm for learning parity functions in the presence of random classification noise, a problem closely related to several cryptographic and coding problems. Our algorithm runs in polynomial time for the case of parity functions that depend on only the first $\textit{O}(log$ $\textit{n}$ log log $\textit{n})$ bits of input, which provides the first known instance of an efficient noise-tolerant algorithm for a concept class that is not learnable in the Statistical Query model of Kearns [1998]. Thus, we demonstrate that the set of problems learnable in the statistical query model is a strict subset of those problems learnable in the presence of noise in the PAC model.In coding-theory terms, what we give is a $poly(\textit{n})-time$ algorithm for decoding linear $\textit{k}$ × $\textit{n}$ codes in the presence of random noise for the case of $\textit{k}$ = $\textit{c}$ log $\textit{n}$ log log $\textit{n}$ for some $\textit{c}$ > 0. (The case of $\textit{k}$ = $\textit{O}(log$ $\textit{n})$ is trivial since one can just individually check each of the $2^{k}$ possible messages and choose the one that yields the closest codeword.)A natural extension of the statistical query model is to allow queries about statistical properties that involve $\textit{t}-tuples$ of examples, as opposed to just single examples. The second result of this article is to show that any class of functions learnable (strongly or weakly) with $\textit{t}-wise$ queries for $\textit{t}$ = $\textit{O}(log$ $\textit{n})$ is also weakly learnable with standard unary queries. Hence, this natural extension to the statistical query model does not increase the set of weakly learnable functions. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2003-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 50 Issue Number 4 Page Count 14 Starting Page 506 Ending Page 519

#### Open content in new tab

Source: ACM Digital Library