Using fewer examples to simulate equivalence queries
Ricard Gavaldà · 1996
It is well known that an algorithm that learns exactly using Equivalence queries can be transformed into a PAC algorithm that asks for random labelled examples. The first transformation due to Angluin (1988) uses a number of examples quadratic in the number of queries. Later, Littlestone (1989) and Schuurmans and Greiner (1995) gave transformations using linearly many examples. We present here another analysis of Littlestone's transformation which is both simpler and gives better leading constants. Our constants are still worse than Schuurmans and Greiner's, but while ours is a worst-case bound on the number of examples to achieve PAC learning, theirs is only an expected one. 1 Introduction Angluin's model of exact learning from queries [2] is one of the most frequently studied models of computational learning. The goal of a query learning algorithm is to infer an exact description of some unknown target concept by asking queries about it to some teacher. Department of Software (LS...