Premium
On learning thresholds of parities and unions of rectangles in random walk models
Author(s) -
Roch Sébastien
Publication year - 2007
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20162
Subject(s) - generalization , random walk , mathematics , sensitivity (control systems) , noise (video) , distribution (mathematics) , algorithm , combinatorics , computer science , statistics , artificial intelligence , mathematical analysis , image (mathematics) , electronic engineering , engineering
In a recent breakthrough, [Bshouty et al., J Comput Syst Sci 71 (2005), 250–265] obtained the first passive‐learning algorithm for DNFs under the uniform distribution. They showed that DNFs are learnable in the Random Walk and Noise Sensitivity models. We extend their results in several directions. We first show that thresholds of parities, a natural class encompassing DNFs, cannot be learned efficiently in the Noise Sensitivity model using only statistical queries. In contrast, we show that a cyclic version of the Random Walk model allows to learn efficiently polynomially weighted thresholds of parities. We also extend the algorithm of Bshouty et al. to the case of Unions of Rectangles, a natural generalization of DNFs to {0,…, b − 1} n . © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007