Computational limitations on learning from examples
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Parameterized learnability of juntas
- Quantifying inductive bias: AI learning algorithms and Valiant's learning framework
- Occam's razor
- Equivalence of models for polynomial learnability
- Inductive reasoning and Kolmogorov complexity
- On the necessity of Occam algorithms
- Bounding sample size with the Vapnik-Chervonenkis dimension
- Optimal mistake bound learning is hard
- Double Horn functions
- Approximating hyper-rectangles: Learning and pseudorandom sets
- Combinatorics and connectionism
- Generating logical expressions from positive and negative examples via a branch-and-bound approach
- 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
- Toward efficient agnostic learning
- The learnability of description logics with equality constraints
- On-line learning of rectangles and unions of rectangles
- Efficient learning of typical finite automata from random walks
- Error-free and best-fit extensions of partially defined Boolean functions
- Logical settings for concept-learning
- Learning unions of tree patterns using queries
- On the difficulty of approximately maximizing agreements.
- Techniques of replica symmetry breaking and the storage problem of the McCulloch-Pitts neuron
- Logical analysis of binary data with missing bits
- The complexity of minimizing and learning OBDDs and FBDDs
- Hierarchical design of fast minimum disagreement algorithms
- The learnability of unions of two rectangles in the two-dimensional discretized space
- Learning decision trees from random examples
- A general lower bound on the number of examples needed for learning
- Hardness of indentifying the minimum ordered binary decision diagram
- Proper learning algorithm for functions of k terms under smooth distributions.
- Effects of domain characteristics on instance-based learning algorithms.
- Complexity of learning in concept lattices from positive and negative examples
- On data classification by iterative linear partitioning
- Some connections between learning and optimization
- An approach to guided learning of Boolean functions
- 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
- Independence and port oracles for matroids, with an application to computational learning theory
- Computational complexity of recognition learning procedures in the class of piecewise-linear committee decision rules
- \(P\)-sufficient statistics for PAC learning \(k\)-term-DNF formulas through enumeration
- A non-extendibility certificate for submodularity and applications
- Learning under \(p\)-tampering poisoning attacks
- PCPs and the hardness of generating synthetic data
- 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
- Revising threshold functions
- The complexity of properly learning simple concept classes
- A general comparison of language learning from examples and from queries
- Efficient learning algorithms yield circuit lower bounds
- On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.
- Circuit lower bounds from learning-theoretic approaches
- Order-revealing encryption and the hardness of private learning
- Hierarchical design of fast minimum disagreement algorithms
- PACS, simple-PAC and query learning
- Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
- On the Nonlearnability of a Single Spiking Neuron
- Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
- Bounds on the sample complexity for private learning and private data release
- Parameterized Learnability of k-Juntas and Related Problems
- GAMoN: discovering \(M\)-of-\(N^{\{\neg, \lor\}}\) hypotheses for text classification by a lattice-based genetic algorithm
- Completing networks using observed data
- A theory of the learnable
- scientific article; zbMATH DE number 67808 (Why is no real title available?)
- Learning finite binary sequences from half-space data
- A framework for polynomial-time query learnability
- Learning reliably and with one-sided error
- Training a Single Sigmoidal Neuron Is Hard
- scientific article; zbMATH DE number 6866335 (Why is no real title available?)
- Many-Layered Learning
- Improper learning by refuting
- On the hardness of approximating the minimum consistent OBDD problem
- scientific article; zbMATH DE number 7561750 (Why is no real title available?)
- scientific article; zbMATH DE number 7250145 (Why is no real title available?)
- Concept learning by example decomposition
- The computational complexity of understanding binary classifier decisions
- The Complexity of Partial Function Extension for Coverage Functions
- Maximizing agreements with one-sided error with applications to heuristic learning
- Pac-learning non-recursive Prolog clauses
- Robust logics
- Hardness of approximate two-level logic minimization and PAC learning with membership queries
- Maximizing agreements with one-sided error with applications to heuristic learning
- Pac-learning non-recursive Prolog clauses
- Learning logic programs with structured background knowledge
- Monotone term decision lists
- Agnostic learning of geometric patterns
- Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions
- Complexity of learning in artificial neural networks
- Learning unions of tree patterns using queries
- On approximately identifying concept classes in the limit
- On the non-efficient PAC learnability of conjunctive queries
- An optimal algorithm for proper learning of unions of two rectangles with queries
- scientific article; zbMATH DE number 7765404 (Why is no real title available?)
- A circuit complexity formulation of algorithmic information theory
- Learning random monotone DNF
- Statistical computational learning
- Monotonic and dual monotonic language learning
This page was built for publication: Computational limitations on learning from examples
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3813320)
