
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Polynomially Sparse Variations and Reducibility among Prediction Problems
Naoki ABE Osamu WATANABE
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E75D
No.4
pp.449458 Publication Date: 1992/07/25
Online ISSN: Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Issue on Algorithmic Learning Theory) Category: Keyword: prediction preserving reducibility, turing reducibility, manyone reducibility, polynomially sparse variants, PAC learning model, computational learning theory,
Full Text: PDF(861.7KB) >>Buy this Article
Summary:
We investigate the relationship between two different notions of reducibility among prediction (learning) problems within the distributionfree learning model of Valiant (PAC learning model). The notions of reducibility we consider are the analogues for prediction problems of the manyone reducibility and of the Turing reducibility. The former is the notion of prediction preserving reducibility developed by Pitt and Warmuth, and its generalization. Concerning these two notions of reducibility, we show that there exist a pair of prediction problems A and B, whose membership problems are polynomial time solvable, such that A is reducible to B with respect to the Turing reducibility, but not with respect to the prediction preserving reducibility. We show this result by making use of the notion of a class of polynomially sparse variants of a concept representation class. We first show that any class A of polynomially sparse variants of another class B is reducible to B with respect to the Turing reducibility'. We then prove the existence of a prediction problem R and a class R of polynomially sparse variants of R, such that R does not reduce to R with respect to the prediction preserving reducibility.

