Computational limitations on learning from examples

DOI10.1145/48014.63140zbMath0662.68086OpenAlexW2117049614MaRDI QIDQ3813320

Leonard Pitt, Leslie G. Valiant

Publication date: 1988

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/48014.63140

zbMATH Keywords

computational complexityNP-completenessinductive inferencelearning from exampleslearnabilitydistribution-free learning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)

Related Items (only showing first 100 items - show all)

A circuit complexity formulation of algorithmic information theory ⋮ Unnamed Item ⋮ The complexity of minimizing and learning OBDDs and FBDDs ⋮ Many-Layered Learning ⋮ Effects of domain characteristics on instance-based learning algorithms. ⋮ Efficient distribution-free learning of probabilistic concepts ⋮ Inference of a minimum size Boolean function from examples by using a new efficient branch-and-bound approach ⋮ On the learnability of monotone \(k\mu\)-DNF formulae under product distributions ⋮ On data classification by iterative linear partitioning ⋮ Some connections between learning and optimization ⋮ PACS, simple-PAC and query learning ⋮ Toward efficient agnostic learning ⋮ The learnability of description logics with equality constraints ⋮ On-line learning of rectangles and unions of rectangles ⋮ On the hardness of approximating the minimum consistent OBDD problem ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ Revising threshold functions ⋮ Quantifying inductive bias: AI learning algorithms and Valiant's learning framework ⋮ Occam's razor ⋮ An approach to guided learning of Boolean functions ⋮ GAMoN: discovering \(M\)-of-\(N^{\{\neg, \lor\}}\) hypotheses for text classification by a lattice-based genetic algorithm ⋮ Efficient learning of typical finite automata from random walks ⋮ A framework for polynomial-time query learnability ⋮ On the geometric separability of Boolean functions ⋮ The bounded injury priority method and the learnability of unions of rectangles ⋮ On the minimum number of logical clauses inferred from examples ⋮ Error-free and best-fit extensions of partially defined Boolean functions ⋮ Independence and port oracles for matroids, with an application to computational learning theory ⋮ Logical settings for concept-learning ⋮ Learning unions of tree patterns using queries ⋮ On approximately identifying concept classes in the limit ⋮ Unnamed Item ⋮ On the non-efficient PAC learnability of conjunctive queries ⋮ An optimal algorithm for proper learning of unions of two rectangles with queries ⋮ On the difficulty of approximately maximizing agreements. ⋮ Learning random monotone DNF ⋮ Learning reliably and with one-sided error ⋮ Learning under \(p\)-tampering poisoning attacks ⋮ Hierarchical design of fast minimum disagreement algorithms ⋮ Parameterized Learnability of k-Juntas and Related Problems ⋮ PCPs and the hardness of generating synthetic data ⋮ Measuring teachability using variants of the teaching dimension ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ Equivalence of models for polynomial learnability ⋮ The Complexity of Partial Function Extension for Coverage Functions ⋮ \(P\)-sufficient statistics for PAC learning \(k\)-term-DNF formulas through enumeration ⋮ The complexity of properly learning simple concept classes ⋮ Monotonic and dual monotonic language learning ⋮ A general comparison of language learning from examples and from queries ⋮ On the limits of proper learnability of subclasses of DNF formulas ⋮ Inductive reasoning and Kolmogorov complexity ⋮ On the necessity of Occam algorithms ⋮ Learning unions of tree patterns using queries ⋮ Three \(\sum^ P_ 2\)-complete problems in computational learning theory ⋮ On the complexity of learning strings and sequences ⋮ Bounds on the sample complexity for private learning and private data release ⋮ Bounding sample size with the Vapnik-Chervonenkis dimension ⋮ Learning logic programs with structured background knowledge ⋮ Monotone term decision lists ⋮ Agnostic learning of geometric patterns ⋮ Training a Single Sigmoidal Neuron Is Hard ⋮ A non-extendibility certificate for submodularity and applications ⋮ Unnamed Item ⋮ Partial observability and learnability ⋮ Maximizing agreements with one-sided error with applications to heuristic learning ⋮ Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions ⋮ Complexity of learning in artificial neural networks ⋮ Order-Revealing Encryption and the Hardness of Private Learning ⋮ Pac-learning non-recursive Prolog clauses ⋮ Maximizing agreements with one-sided error with applications to heuristic learning ⋮ Robust logics ⋮ Pac-learning non-recursive Prolog clauses ⋮ On the Nonlearnability of a Single Spiking Neuron ⋮ Efficient learning algorithms yield circuit lower bounds ⋮ Learning finite binary sequences from half-space data ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ The learnability of unions of two rectangles in the two-dimensional discretized space ⋮ Teachability in computational learning ⋮ Unnamed Item ⋮ Hardness of approximate two-level logic minimization and PAC learning with membership queries ⋮ Prediction-preserving reducibility ⋮ Double Horn functions ⋮ Approximating hyper-rectangles: Learning and pseudorandom sets ⋮ Learning decision trees from random examples ⋮ A general lower bound on the number of examples needed for learning ⋮ Completing Networks Using Observed Data ⋮ Hierarchical Design of Fast Minimum Disagreement Algorithms ⋮ Parameterized learnability of juntas ⋮ Bounds on the Sample Complexity for Private Learning and Private Data Release ⋮ Proper learning of \(k\)-term DNF formulas from satisfying assignments ⋮ Explaining AI decisions using efficient methods for learning sparse Boolean formulae ⋮ Hardness of indentifying the minimum ordered binary decision diagram ⋮ Proper learning algorithm for functions of \(k\) terms under smooth distributions. ⋮ Techniques of replica symmetry breaking and the storage problem of the McCulloch-Pitts neuron ⋮ Unnamed Item ⋮ On the hardness of approximating the minimum consistent acyclic DFA and decision diagram. ⋮ Combinatorics and connectionism ⋮ Learnability with respect to fixed distributions ⋮ Generating logical expressions from positive and negative examples via a branch-and-bound approach ⋮ Logical analysis of binary data with missing bits

This page was built for publication: Computational limitations on learning from examples