Approximating hyper-rectangles: Learning and pseudorandom sets

DOI10.1006/JCSS.1998.1593zbMATH Open0917.68185OpenAlexW2068484024MaRDI QIDQ1278043FDOQ1278043

Authors: Peter Auer, Philip M. Long, Aravind Srinivasan 

Publication date: 21 February 1999

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1998.1593

Recommendations

• scientific article; zbMATH DE number 1559547
• Learning unions of \(\omega(1)\)-dimensional rectangles
• Learning Unions of ω(1)-Dimensional Rectangles
• Improved pseudorandom generators for combinatorial rectangles
• Pseudo-derandomizing learning and approximation

zbMATH Keywords

PAC learning

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Cites Work

• Title not available (Why is that?)
• Convergence of stochastic processes
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Learnability and the Vapnik-Chervonenkis dimension
• Intersection theorems with geometric consequences
• Universal classes of hash functions
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Title not available (Why is that?)
• Simple Constructions of Almost k-wise Independent Random Variables
• Some remarks on the theory of graphs
• Ramanujan graphs
• Solving the multiple instance problem with axis-parallel rectangles.
• A theory of the learnable
• A general lower bound on the number of examples needed for learning
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Efficient noise-tolerant learning from statistical queries
• Asymptotic lower bounds for Ramsey functions
• Pseudorandomness for network algorithms
• Computational limitations on learning from examples
• Bounding Ramsey numbers through large deviation inequalities
• Explicit Ramsey graphs and orthonormal labelings
• PAC learning axis-aligned rectangles with respect to product distributions from multiple-instance examples
• A note on learning from multiple-instance examples
• Predicting \(\{ 0,1\}\)-functions on randomly drawn points
• Improved algorithms via approximations of probability distributions (extended abstract)
• Prediction-preserving reducibility
• Title not available (Why is that?)
• A Note on Ramsey's Theorem
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension

Cited In (12)

• Improved algorithms via approximations of probability distributions
• Instance-level accuracy versus bag-level accuracy in multi-instance learning
• Multi-instance multi-label learning
• On learning thresholds of parities and unions of rectangles in random walk models
• Learning unions of high-dimensional boxes over the reals
• (Machine) learning parameter regions
• Improved pseudorandom generators for combinatorial rectangles
• Title not available (Why is that?)
• On multiple-instance learning of halfspaces
• A new PAC bound for intersection-closed concept classes
• An upper bound on the sample complexity of PAC-learning halfspaces with respect to the uniform distribution
• PAC-learning in the presence of one-sided classification~noise

This page was built for publication: Approximating hyper-rectangles: Learning and pseudorandom sets

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