Learning unions of (1)-dimensional rectangles

DOI10.1016/J.TCS.2008.06.036MaRDI QIDQ950197zbMATH OpenOpenAlexFDO

Authors Alp Atıcı, Rocco A. Servedio

Publication date 22 October 2008

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2008.06.036

zbMATH Keywords

boostinglearning unions of rectangleslearning with membership queries

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Recommendations

• Learning Unions of ω(1)-Dimensional Rectangles
• Learning unions of high-dimensional boxes over the reals
• On-line learning of rectangles and unions of rectangles
• The bounded injury priority method and the learnability of unions of rectangles
• The learnability of unions of two rectangles in the two-dimensional discretized space

Cites work

• scientific article; zbMATH DE number 3772326 (Why is no real title available?)
• 10.1162/153244304773936072
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• Boosting a weak learning algorithm by majority
• Computing Boolean functions by polynomials and threshold circuits
• Efficient learning with virtual threshold gates
• Harmonic Analysis of Polynomial Threshold Functions
• Learnability beyond AC ⁰
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• Learning Decision Trees Using the Fourier Spectrum
• Learning boxes in high dimension
• On Learning Read-k-Satisfy-j DNF
• On using the Fourier transform to learn disjoint DNF
• On-line learning of rectangles and unions of rectangles
• The bounded injury priority method and the learnability of unions of rectangles
• Threshold circuits of bounded depth

Cited in

(8)

• Learning union of integer hypercubes with queries (with applications to monadic decomposition)
• An optimal algorithm for proper learning of unions of two rectangles with queries
• Learning Unions of ω(1)-Dimensional Rectangles
• On-line learning of rectangles and unions of rectangles
• The learnability of unions of two rectangles in the two-dimensional discretized space
• On learning thresholds of parities and unions of rectangles in random walk models
• Learning unions of high-dimensional boxes over the reals
• scientific article; zbMATH DE number 1559547 (Why is no real title available?)

This page was built for publication: Learning unions of \(\omega(1)\)-dimensional rectangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q950197)