Prediction-preserving reducibility
This paper is a contribution to computational learning theory, where the main subject of study is finding concept classes that may be efficiently learned from examples. Each concept is described in a representation language. The authors modify the well-known definition of a probably approximately correct learning algorithm of L. G. Valiant. Namely, a variant of probably approximately correct learning has been introduced such that the learning algorithm may produce a description of the target concept chosen from a different description language. Thus, the class R of representation is probably approximately correct learnable in terms of the class \(R'\) of representations if the learning algorithm is probably approximately correct and the concept description output by the algorithm is an element of \(R'\). Prediction occurs when the algorithm is not required to output description at all, but it can predict future examples, with some error, with respect to the target concept.
- -nets and simplex range queries
- -productions in context-free grammars
- A general lower bound on the number of examples needed for learning
- A taxonomy of problems with fast parallel algorithms
- A theory of the learnable
- Alternation
- Analogical and inductive inference. International workshop AII '89, Reinhardsbrunn Castle, GDR, October 1-6, 1989. Proceedings
- Complete problems for deterministic polynomial time
- Complexity of automaton identification from given data
- Computational Complexity of Probabilistic Turing Machines
- Computational limitations on learning from examples
- Density and dimension
- scientific article; zbMATH DE number 3889430 (Why is no real title available?)
- scientific article; zbMATH DE number 3878983 (Why is no real title available?)
- scientific article; zbMATH DE number 3960854 (Why is no real title available?)
- scientific article; zbMATH DE number 67615 (Why is no real title available?)
- scientific article; zbMATH DE number 67633 (Why is no real title available?)
- scientific article; zbMATH DE number 3566175 (Why is no real title available?)
- scientific article; zbMATH DE number 3639163 (Why is no real title available?)
- scientific article; zbMATH DE number 3420728 (Why is no real title available?)
- Learnability and the Vapnik-Chervonenkis dimension
- Learning decision trees from random examples
- Learning regular sets from queries and counterexamples
- Linear programming is log-space hard for P
- Occam's razor
- On tape-bounded complexity classes and multihead finite automata
- On the complexity of minimum inference of regular sets
- On the necessity of Occam algorithms
- On the Tape Complexity of Deterministic Context-Free Languages
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- On uniform circuit complexity
- One way functions and pseudorandom generators
- Predicting \(\{ 0,1\}\)-functions on randomly drawn points
- Quantifying inductive bias: AI learning algorithms and Valiant's learning framework
- Queries and concept learning
- Space-bounded reducibility among combinatorial problems
- The minimum consistent DFA problem cannot be approximated within any polynomial
- Equivalence of models for polynomial learnability
- On the necessity of Occam algorithms
- Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
- Learning with unreliable boundary queries
- Approximating hyper-rectangles: Learning and pseudorandom sets
- Prefix grammars: An alternative characterization of the regular languages
- The query complexity of learning DFA
- The learnability of description logics with equality constraints
- Efficient learning of typical finite automata from random walks
- Logical settings for concept-learning
- Learning unions of tree patterns using queries
- Learning orthogonal F-Horn formulas
- On the intrinsic complexity of learning recursive functions
- Learnability of quantified formulas.
- On-line learning of linear functions
- On learning unions of pattern languages and tree patterns in the mistake bound model.
- Apple tasting.
- Learning elementary formal systems with queries.
- Learning fallible deterministic finite automata
- Prediction-hardness of acyclic conjunctive queries
- Minimizing nfa's and regular expressions
- Random embedding machines for pattern recognition
- Interactive clustering of linear classes and cryptographic lower bounds
- scientific article; zbMATH DE number 996387 (Why is no real title available?)
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- A framework for polynomial-time query learnability
- Structural analysis of polynomial-time query learnability
- scientific article; zbMATH DE number 1839442 (Why is no real title available?)
- On reduction of two-parameter prediction problems
- Learnability of solutions to conjunctive queries
- Pac-learning non-recursive Prolog clauses
- Pac-learning non-recursive Prolog clauses
- Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions
- Learning unions of tree patterns using queries
- Learning orthogonal F-Horn formulas
- The complexity of learning minor closed graph classes
- Classic learning
- Three \(\sum^ P_ 2\)-complete problems in computational learning theory
- Learning commutative deterministic finite state automata in polynomial time
- Partial observability and learnability
This page was built for publication: Prediction-preserving reducibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q756441)
