Learning functions of \(k\) relevant variables
From MaRDI portal
Publication:1886314
DOI10.1016/j.jcss.2004.04.002zbMath1084.68057MaRDI QIDQ1886314
Elchanan Mossel, Rocco A. Servedio, Ryan O'Donnell
Publication date: 18 November 2004
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2004.04.002
68Q32: Computational learning theory
68T05: Learning and adaptive systems in artificial intelligence
Related Items
DNF are teachable in the average case, Learning juntas in the presence of noise, Quantum algorithms for learning and testing juntas, Application of a Generalization of Russo's Formula to Learning from Multiple Random Oracles, Algorithms for Inference, Analysis and Control of Boolean Networks
Cites Work
- Unnamed Item
- Unnamed Item
- Testing juntas
- Matrix multiplication via arithmetic progressions
- Occam's razor
- Selection of relevant features and examples in machine learning
- Polynomials with two values
- On learning monotone DNF formulae under uniform distributions
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- More efficient PAC-learning of DNF with membership queries under the uniform distribution
- An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
- Weakly learning DNF and characterizing statistical query learning using Fourier analysis
- Constant depth circuits, Fourier transform, and learnability
- Efficient noise-tolerant learning from statistical queries
- A theory of the learnable
- Learning Integer Lattices
- 10.1162/153244302760200669