A theory of the learnable
From MaRDI portal
Publication:3714486
DOI10.1145/1968.1972zbMATH Open0587.68077OpenAlexW4238893454WikidataQ29398622 ScholiaQ29398622MaRDI QIDQ3714486FDOQ3714486
Authors: Leslie G. Valiant 
Publication date: 1984
Published in: Communications of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1968.1972
Recommendations
Cited In (only showing first 100 items - show all)
- An average-case optimal one-variable pattern language learner
- Fourier concentration from shrinkage
- Classification by polynomial surfaces
- BET on independence
- Computational limitations on learning from examples
- Additive logistic regression: a statistical view of boosting. (With discussion and a rejoinder by the authors)
- Three fundamental concepts of the capacity of learning machines
- Bayesian-validated computer-simulation surrogates for optimization and design: Error estimates and applications
- A framework for polynomial-time query learnability
- A geometric approach to leveraging weak learners
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- Arcing classifiers. (With discussion)
- Approximate inference of functional dependencies from relations
- A Bayesian framework for learning rule sets for interpretable classification
- Noisy Monte Carlo: convergence of Markov chains with approximate transition kernels
- Differentially private data analysis of social networks via restricted sensitivity
- On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
- On the power of nonuniformity in proofs of security
- Finding the homology of submanifolds with high confidence from random samples
- Sign-representation of Boolean functions using a small number of monomials
- Learning indexed families of recursive languages from positive data: A survey
- Learning regular sets from queries and counterexamples
- Streaming computations with a loquacious prover
- Approximation by superpositions of a sigmoidal function
- Experiments with AdaBoost.RT, an Improved Boosting Scheme for Regression
- Conformal prediction: a unified review of theory and new challenges
- On universal learning algorithms
- Title not available (Why is that?)
- Infinitary self-reference in learning theory
- On learning width two branching programs
- Learning conjunctions with noise under product distributions
- Learning unions of high-dimensional boxes over the reals
- PACS, simple-PAC and query learning
- Decision lists and related Boolean functions
- Polynomial Time Algorithms for Learning k-Reversible Languages and Pattern Languages with Correction Queries
- On Learning Regular Expressions and Patterns Via Membership and Correction Queries
- On the mathematical foundations of learning
- Results on learnability and the Vapnik-Chervonenkis dimension
- Optimization approaches to supervised classification
- Learnability with respect to fixed distributions
- On the power of incremental learning.
- Variants of iterative learning
- A theory of learning with similarity functions
- Title not available (Why is that?)
- Pseudorandom generators without the XOR lemma
- Occam's razor
- Learning elementary formal systems
- Approximating hyper-rectangles: Learning and pseudorandom sets
- Learning functions of \(k\) relevant variables
- Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints (extended abstract)
- Toward efficient agnostic learning
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- Efficient learning with virtual threshold gates
- Logical analysis of data: classification with justification
- A general lower bound on the number of examples needed for learning
- The Crystallizing Substochastic Sequential Machine Extractor: CrySSMEx
- Training sequences
- Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
- Foundations of support constraint machines
- Computational aspects of monotone dualization: a brief survey
- On the Fourier spectrum of symmetric Boolean functions
- Robust optimization in the presence of uncertainty
- Learning juntas in the presence of noise
- On PAC learning algorithms for rich Boolean function classes
- A theoretical framework for deep transfer learning
- Interpreted and generated signals
- Ten More Years of Error Rate Research
- Inductive inference of unbounded unions of pattern languages from positive data
- Logical analysis of numerical data
- On classifier behavior in the presence of mislabeling noise
- On the hardness of approximate reasoning
- O-PCF algorithm for one-class classification
- Nested annealing: A provable improvement to simulated annealing
- On the complexity of computing and learning with multiplicative neural networks
- IIPS: A framework for specifying inductive-inference problems
- Logical analysis of binary data with missing bits
- On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
- Identification of pattern languages from examples and queries
- Efficient learning of context-free grammars from positive structural examples
- Extremes in the degrees of inferability
- Classification with label noise: a Markov chain sampling framework
- Deductive learning
- Learning intersections and thresholds of halfspaces
- On the hardness of learning intersections of two halfspaces
- Using relevance queries for identification of read-once functions
- Knows what it knows: a framework for self-aware learning
- Quantum speed-up for unsupervised learning
- A theory of learning from different domains
- The Vapnik-Chervonenkis dimension of decision trees with bounded rank
- Structure identification in relational data
- Learning approximately regular languages with reversible languages
- Learning read once functions using subcube parity queries
- Unconditional lower bounds for learning intersections of halfspaces
- Identification of function distinguishable languages.
- Supervised learning and co-training
- An analysis of model-based interval estimation for Markov decision processes
- Logic-based neural networks
- MAT learners for tree series: an abstract data type and two realizations
- An Asymptotic Statistical Theory of Polynomial Kernel Methods
- Learning orthogonal F-Horn formulas
This page was built for publication: A theory of the learnable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3714486)
