Learning unions of omega(1)-dimensional rectangles
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 It are "large". We obtain poly(n. log 5)-time algorithms for the following classes: poly(n log b)-way MAJORITY of O(log(n log b)/log log (n log b))-dimensional rectangles. Union of poly(log(n log b)) many O(log(2) (n log b)/ (log log(n log b) log log log (n log b))(2))-dimensional rectangles. poly (n log b)-way MAJORITY of poly (n log b)-OR of disjoint O(log(n log b)/log log (n log b)) dimensional rectangles. Our main algorithmic tool is an extension of Jackson's boosting- and Fourier-based Harmonic Sieve algorithm [J.C. Jackson, An efficient membership-query algorithm for learning DNF with respect to the uniform distribution, journal of Computer and System Sciences 55 (3) (1997) 414-440] to the domain [b](n), building on work of Akavia et al. [A. Akavia, S. Goldwasser, S. Safra, Proving hard core predicates using list decoding, in: Proc. of the 44th Annual IEEE Symposium oil Foundations of Computer Science, FOCS '03, 2003, pp. 146-156]. Other ingredients used to obtain the results stated above are techniques from exact learning [A. Beimel, E. Kushilevitz, Learning boxes in high dimension, Algorithmica 22 (1/2) (1998) 76-90] and ideas from recent work on learning augmented AC(0) circuits [J.C. Jackson, A.R. Klivans, R.A. Servedio, Learnability beyond AC(0), in: Proc. of the 34th Annual ACM Symposium on Theory Of Computing, STOC'02, 2002,pp. 776-784) and on representing Boolean functions as thresholds of parities [A.R. Klivans, R.A. Servedio, Learning DNF in time 2(0(n1/3)), Journal Of computer and System Sciences 68 (2) (2004) 303-318]. (C) 2008 Elsevier B.V. All rights reserved.
learning unions of rectangles learning with membership queries boosting