Prediction-preserving reducibility (Q756441)

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.