Approximating hyper-rectangles: Learning and pseudorandom sets
From MaRDI portal
Publication:1278043
DOI10.1006/jcss.1998.1593zbMath0917.68185OpenAlexW2068484024MaRDI QIDQ1278043
Philip M. Long, Peter Auer, 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
Related Items (9)
Learning unions of high-dimensional boxes over the reals ⋮ A new PAC bound for intersection-closed concept classes ⋮ Multi-instance multi-label learning ⋮ On multiple-instance learning of halfspaces ⋮ Instance-level accuracy versus bag-level accuracy in multi-instance learning ⋮ PAC-learning in the presence of one-sided classification~noise ⋮ (Machine) learning parameter regions ⋮ An upper bound on the sample complexity of PAC-learning halfspaces with respect to the uniform distribution ⋮ Improved algorithms via approximations of probability distributions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Prediction-preserving reducibility
- Ramanujan graphs
- Intersection theorems with geometric consequences
- Asymptotic lower bounds for Ramsey functions
- Universal classes of hash functions
- Predicting \(\{ 0,1\}\)-functions on randomly drawn points
- 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
- Solving the multiple instance problem with axis-parallel rectangles.
- A general lower bound on the number of examples needed for learning
- Pseudorandomness for network algorithms
- Improved algorithms via approximations of probability distributions (extended abstract)
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Learnability and the Vapnik-Chervonenkis dimension
- A theory of the learnable
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Computational limitations on learning from examples
- Simple Constructions of Almost k-wise Independent Random Variables
- Bounding Ramsey numbers through large deviation inequalities
- Efficient construction of a small hitting set for combinatorial rectangles in high dimension
- Efficient noise-tolerant learning from statistical queries
- A Note on Ramsey's Theorem
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Some remarks on the theory of graphs
- Convergence of stochastic processes
This page was built for publication: Approximating hyper-rectangles: Learning and pseudorandom sets
