Prediction-preserving reducibility
type: Item
instance of: scholarly article
title: Prediction-preserving reducibility
zbMATH Open document ID: 0722.68094
DOI: 10.1016/0022-0000(90)90028-J
author: Leonard Pitt
author: Manfred K. Warmuth
published in: Journal of Computer and System Sciences
publication date: 1990-01-01T00:00:00Z
review text: 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.
reviewed by: Jerzy W. Grzymala-Busse
Mathematics Subject Classification ID: 68T05
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 4191152
zbMATH Keywords: prediction-preserving reducibility
zbMATH Keywords: computational learning theory
zbMATH Keywords: probably approximately correct learning algorithm
Wikidata QID: Q56017510
MaRDI profile type: Publication
cites work: Q4013533
cites work: Learning regular sets from queries and counterexamples
cites work: On the complexity of minimum inference of regular sets
cites work: Queries and concept learning
cites work: Density and dimension
cites work: Q5685065
cites work: Learnability and the Vapnik-Chervonenkis dimension
cites work: Occam's razor
cites work: On the necessity of Occam algorithms
cites work: Alternation
cites work: A taxonomy of problems with fast parallel algorithms
cites work: Linear programming is log-space hard for P
cites work: Learning decision trees from random examples
cites work: A general lower bound on the number of examples needed for learning
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: Complexity of automaton identification from given data
cites work: Q3729902
cites work: \(\varepsilon\)-productions in context-free grammars
cites work: Q4198075
cites work: Quantifying inductive bias: AI learning algorithms and Valiant's learning framework
cites work: Predicting \(\{ 0,1\}\)-functions on randomly drawn points
cites work: \(\epsilon\)-nets and simplex range queries
cites work: Space-bounded reducibility among combinatorial problems
cites work: Complete problems for deterministic polynomial time
cites work: One way functions and pseudorandom generators
cites work: Analogical and inductive inference. International workshop AII '89, Reinhardsbrunn Castle, GDR, October 1-6, 1989. Proceedings
cites work: Computational limitations on learning from examples
cites work: The minimum consistent DFA problem cannot be approximated within any polynomial
cites work: On uniform circuit complexity
cites work: Q4138141
cites work: Q4013554
cites work: On tape-bounded complexity classes and multihead finite automata
cites work: On the Tape Complexity of Deterministic Context-Free Languages
cites work: A theory of the learnable
cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
cites work: Q3221885
cites work: Q3344029
full work available at URL: 0022-0000(90)90028-j
OpenAlex ID: W2020114845
description: scientific article; zbMATH DE number 4191152