Learning Unions of ω(1)-Dimensional RectanglesAuthors: Alp Atıcı and Rocco A. Servedio
Source: Algorithmic Learning Theory, 17th International Conference,
ALT 2006, Barcelona, October 2006, Proceedings,
(José L. Balcázar, Phil Long and Frank Stephan, Eds.),
Abstract. We consider the problem of learning unions of rectangles over the domain [b]^{n}, in the uniform distribution membership query learning setting, where both b and n are “large”. We obtain poly(n, log b)-time algorithms for the following classes:
Our main algorithmic tool is an extension of Jackson's boosting- and Fourier-based Harmonic Sieve algorithm [Jackson 1997] to the domain [b]^{n}, building on work of [Akavia, Goldwasser, Safra 2003]. Other ingredients used to obtain the results stated above are techniques from exact learning [Beimel, Kushilevitz 1998] and ideas from recent work on learning augmented AC^{0} circuits [Jackson, Klivans, Servedio 2002] and on representing Boolean functions as thresholds of parities [Klivans, Servedio 2001].
©Copyright 2006, Springer |