Efficient distribution-free learning of probabilistic concepts
From MaRDI portal
Publication:1329154
DOI10.1016/S0022-0000(05)80062-5zbMath0822.68093MaRDI QIDQ1329154
Michael Kearns, Robert E. Schapire
Publication date: 9 October 1995
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Related Items (49)
PAC learning of probability distributions over a discrete domain. ⋮ Efficient algorithms for learning functions with bounded variation ⋮ An algorithmic theory of learning: robust concepts and random projection ⋮ On-line maximum likelihood prediction with respect to general loss functions ⋮ Approximation and learning of convex superpositions ⋮ \(L_{p}\)-norm Sauer-Shelah lemma for margin multi-category classifiers ⋮ Nonlinear approximation via compositions ⋮ Uniform approximation of Vapnik-Chervonenkis classes ⋮ Learning cost-sensitive active classifiers ⋮ Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu ⋮ Knows what it knows: a framework for self-aware learning ⋮ Learning from examples with unspecified attribute values. ⋮ Robustness and generalization ⋮ Robust regression using biased objectives ⋮ On biased random walks, corrupted intervals, and learning under adversarial design ⋮ Approximate location of relevant variables under the crossover distribution. ⋮ Margin Error Bounds for Support Vector Machines on Reproducing Kernel Banach Spaces ⋮ Visual stability analysis for model selection in graded possibilistic clustering ⋮ Deep Network Approximation for Smooth Functions ⋮ Sample Complexity of Classifiers Taking Values in ℝQ, Application to Multi-Class SVMs ⋮ Deep Network Approximation Characterized by Number of Neurons ⋮ Aspects of discrete mathematics and probability in the theory of machine learning ⋮ Sequential complexities and uniform martingale laws of large numbers ⋮ Links between probabilistic automata and hidden Markov models: probability distributions, learning models and induction algorithms ⋮ A note on a scale-sensitive dimension of linear bounded functionals in Banach spaces ⋮ An algorithmic theory of learning: Robust concepts and random projection ⋮ Partial observability and learnability ⋮ Regularization and statistical learning theory for data analysis. ⋮ Computational sample complexity and attribute-efficient learning ⋮ Comments on: Support vector machines maximizing geometric margins for multi-class classification ⋮ Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions ⋮ On Martingale Extensions of Vapnik–Chervonenkis Theory with Applications to Online Learning ⋮ A graph-theoretic generalization of the Sauer-Shelah lemma ⋮ Scale-sensitive dimensions and skeleton estimates for classification ⋮ Prediction, learning, uniform convergence, and scale-sensitive dimensions ⋮ Learning with restricted focus of attention ⋮ Optimal approximation rate of ReLU networks in terms of width and depth ⋮ Structural results about exact learning with unspecified attribute values ⋮ Efficient learning with robust gradient descent ⋮ Maximal width learning of binary functions ⋮ Exact lower bounds for the agnostic probably-approximately-correct (PAC) machine learning model ⋮ Integer cells in convex sets ⋮ On the boosting ability of top-down decision tree learning algorithms ⋮ Learning fixed-dimension linear thresholds from fragmented data ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Learnability in Hilbert spaces with reproducing kernels ⋮ Primal and dual combinatorial dimensions
Cites Work
- Occam's razor
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
- Equivalence of models for polynomial learnability
- Decision theoretic generalizations of the PAC model for neural net and other learning applications
- A learning criterion for stochastic rules
- Central limit theorems for empirical measures
- Toward efficient agnostic learning
- Learnability and the Vapnik-Chervonenkis dimension
- A theory of the learnable
- Computational limitations on learning from examples
- Probability Inequalities for Sums of Bounded Random Variables
- Fuzzy sets
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Convergence of stochastic processes
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Efficient distribution-free learning of probabilistic concepts
