Efficient distribution-free learning of probabilistic concepts

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)

zbMATH Keywords

machine learning; probabilistic concepts

Mathematics Subject Classification ID

68T05: Learning and adaptive systems in artificial intelligence

Related Items

Unnamed Item, Unnamed Item, Deep Network Approximation for Smooth Functions, Deep Network Approximation Characterized by Number of Neurons, Margin Error Bounds for Support Vector Machines on Reproducing Kernel Banach Spaces, Unnamed Item, A note on a scale-sensitive dimension of linear bounded functionals in Banach spaces, 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, Knows what it knows: a framework for self-aware learning, Robustness and generalization, Visual stability analysis for model selection in graded possibilistic clustering, An algorithmic theory of learning: robust concepts and random projection, Partial observability and learnability, Maximal width learning of binary functions, 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, On the boosting ability of top-down decision tree learning algorithms, On-line maximum likelihood prediction with respect to general loss functions, Approximation and learning of convex superpositions, Learning from examples with unspecified attribute values., Approximate location of relevant variables under the crossover distribution., Structural results about exact learning with unspecified attribute values, Learnability in Hilbert spaces with reproducing kernels, Robust regression using biased objectives, Learning fixed-dimension linear thresholds from fragmented data, PAC learning of probability distributions over a discrete domain., Efficient algorithms for learning functions with bounded variation, Uniform approximation of Vapnik-Chervonenkis classes, Optimal approximation rate of ReLU networks in terms of width and depth, Nonlinear approximation via compositions, On biased random walks, corrupted intervals, and learning under adversarial design, Sequential complexities and uniform martingale laws of large numbers, Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions, Efficient learning with robust gradient descent, Exact lower bounds for the agnostic probably-approximately-correct (PAC) machine learning model, \(L_{p}\)-norm Sauer-Shelah lemma for margin multi-category classifiers, Aspects of discrete mathematics and probability in the theory of machine learning, Links between probabilistic automata and hidden Markov models: probability distributions, learning models and induction algorithms, An algorithmic theory of learning: Robust concepts and random projection, Integer cells in convex sets, On Martingale Extensions of Vapnik–Chervonenkis Theory with Applications to Online Learning, Sample Complexity of Classifiers Taking Values in ℝ^Q, Application to Multi-Class SVMs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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