Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain
Author:
- Avrim L. BlumABAvrim L. Blum
- 1 October 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 23 (5) , 990-1000
Abstract
Two of the most commonly used models in computational learning theory are the distribution-free model in which examples are chosen from a fixed but arbitrary distribution, and the absolute mistake-bound model in which examples are presented in an arbitrary order. Over the Boolean domain $\{ 0,1\} ^n $, it is known that if the learner is allowed unlimited computational resources then any concept class learnable in one model is also learnable in the other. In addition, any polynomial-time learning algorithm for a concept class in the mistake-bound model can be transformed into one that learns the class in the distribution-free model. This paper shows that if one-way functions exist, then the mistake-bound model is strictly harder than the distribution-free model for polynomial-time learning. Specifically, given a one-way function, it is shown how to create a concept class over $\{ 0,1\} ^n $ that is learnable in polynomial time in the distribution-free model, but not in the absolute mistake-bound model. In addition, the concept class remains hard to learn in the mistake-bound model even if the learner is allowed a polynomial number of membership queries. The concepts considered are based upon the Goldreich, Goldwasser, and Micali random function construction [Goldreich, Goldwasser, and Micali, Journal ACM, 33 (1986), pp. 792–807] and involve creating the following new cryptographic object: an exponentially long sequence of strings $\sigma _1 ,\sigma _2 , \ldots ,\sigma _r $ over $\{ 0,1\} ^n $ that is hard to compute in one direction (given $\sigma _i $ one cannot compute $\sigma _j $ for $j < i$) but is easy to compute and even make random-access jumps in the other direction (given $\sigma _i $ and $j > i$ one can compute $\sigma _j $, even if j is exponentially larger than i ). Similar sequences considered previously [Blum, Blum, and Shub, SIAM J. Comput., 15 (1986), pp. 364–383], [Blum and Micali, SIAM J. Comput., 13 (1984), pp. 850–863] did not allow random-access jumps forward without knowledge of a seed allowing one to compute backwards as well.
Keywords
This publication has 22 references indexed in Scilit:
- Pseudo-random sequence generators using structured noise1990
- Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold AlgorithmMachine Learning, 1988
- Queries and Concept LearningMachine Learning, 1988
- Learning regular sets from queries and counterexamplesInformation and Computation, 1987
- Learning Decision ListsMachine Learning, 1987
- Occam's RazorInformation Processing Letters, 1987
- How to construct random functionsJournal of the ACM, 1986
- A Simple Unpredictable Pseudo-Random Number GeneratorSIAM Journal on Computing, 1986
- A theory of the learnableCommunications of the ACM, 1984
- How to Generate Cryptographically Strong Sequences of Pseudorandom BitsSIAM Journal on Computing, 1984