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, logb)-time algorithms for the following classes:
– poly (n logb)-Majority of \(O(\frac{\log(n \log b)} {\log \log(n \log b)})\)-dimensional rectangles.
–Unions of poly(log(n logb)) many rectangles with dimension
\(O(\frac{\log^2 (n \log b)} {(\log \log(n \log b) \log \log \log (n \log b))^2})\).
– poly (n logb)-Majority of poly (n logb)-Or of disjoint rectangles
with dimension \(O(\frac{\log(n \log b)} {\log \log(n \log b)})\)
Our main algorithmic tool is an extension of Jackson’s boosting- and Fourier-based Harmonic Sieve algorithm [13] to the domain [b]n, building on work of Akavia et al. [1]. Other ingredients used to obtain the results stated above are techniques from exact learning [4] and ideas from recent work on learning augmented AC 0 circuits [14] and on representing Boolean functions as thresholds of parities [16].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Akavia, A., Goldwasser, S., Safra, S.: Proving Hard Core Predicates Using List Decoding. In: Proc. 44th IEEE Found. Comp. Sci., pp. 146–156 (2003)
Aizenstein, H., Blum, A., Khardon, R., Kushilevitz, E., Pitt, L., Roth, D.: On Learning Read-k Satisfy-j DNF. SIAM Journal on Computing 27(6), 1515–1530 (1998)
Atıcı, A., Servedio, R.: Learning Unions of ω(1)-Dimensional Rectangles, available at: http://arxiv.org/abs/cs.LG/0510038
Beimel, A., Kushilevitz, E.: Learning Boxes in High Dimension. Algorithmica 22(1/2), 76–90 (1998)
Bruck, J.: Harmonic Analysis of Polynomial Threshold Functions. SIAM Journal on Discrete Mathematics 3(2), 168–177 (1990)
Chen, Z., Homer, S.: The Bounded Injury Priority Method and The Learnability of Unions of Rectangles. Annals of Pure and Applied Logic 77(2), 143–168 (1996)
Chen, Z., Maass, W.: On-line Learning of Rectangles and Unions of Rectangles. Machine Learning 17(2/3), 23–50 (1994)
Freund, Y.: Boosting a Weak Learning Algorithm by Majority. Information and Computation 121(2), 256–285 (1995)
Freund, Y., Schapire, R.: A Short Introduction to Boosting. Journal of the Japanese Society for Artificial Intelligence 14(5), 771–780 (1999)
Goldberg, P.W., Goldman, S.A., Mathias, H.D.: Learning Unions of Boxes with Membership and Equivalence Queries. In: COLT 1994: Proc. of the 7th annual conference on computational learning theory, pp. 198–207 (1994)
Hajnal, A., Maass, W., Pudlák, P., Szegedy, M., Turan, G.: Threshold Circuits of Bounded Depth. J. Comp. & Syst. Sci. 46, 129–154 (1993)
Håstad, J.: Computational Limitations for Small Depth Circuits. MIT Press, Cambridge, MA (1986)
Jackson, J.C.: An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution. J. Comp. & Syst. Sci. 55(3), 414–440 (1997)
Jackson, J.C., Klivans, A.R., Servedio, R.A.: Learnability Beyond AC 0. In: Proc. of the 34th annual ACM symposium on theory of computing (STOC), pp. 776–784 (2002)
Khardon, R.: On Using the Fourier Transform to Learn Disjoint DNF. Information Processing Letters 49(5), 219–222 (1994)
Klivans, A.R., Servedio, R.A.: Learning DNF in Time \(2^{\tilde{O}(n^{1/3})}\). J. Comp. & Syst. Sci. 68(2), 303–318 (2004)
Krause, M., Pudlák, P.: Computing Boolean Functions by Polynomials and Threshold Circuits. Computational Complexity 7(4), 346–370 (1998)
Kushilevitz, E., Mansour, Y.: Learning Decision Trees using the Fourier Spectrum. SIAM Journal on Computing 22(6), 1331–1348 (1993)
Maass, W., Warmuth, M.K.: Efficient Learning with Virtual Threshold Gates. Information and Computation 141(1), 66–83 (1998)
Schapire, R.E.: The Strength of Weak Learnability. Machine Learning 5, 197–227 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Atıcı, A., Servedio, R.A. (2006). Learning Unions of ω(1)-Dimensional Rectangles. In: Balcázar, J.L., Long, P.M., Stephan, F. (eds) Algorithmic Learning Theory. ALT 2006. Lecture Notes in Computer Science(), vol 4264. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11894841_7
Download citation
DOI: https://doi.org/10.1007/11894841_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-46649-9
Online ISBN: 978-3-540-46650-5
eBook Packages: Computer ScienceComputer Science (R0)