|
NeuroCOLT
Technical Report NC-TR-97-035
Using
Fewer Examples to Simulate Equivalence Queries
Ricard
Gavalda
Universitat Politecnica de Catalunya
Spain
Abstract
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.
Download Compressed Postscript
|