Asking Questions to Minimize Errors
A number of efficient learning algorithms achieve exact identification of an unknown function from some clas using membership and equivalence queries. Using a standard transformation such algorithms can easily be converted to on-line learning algorithms that use membership queries. Under such a transformation the number of equivalence queries made by the query algorithm directly corresponds to the number of mistakes made by the on-line algorithm. In this paper we consider several of the natural classes known to be learnable in this setting, and investigate the minimum number of equivalence queries with accompanying counterexamples (or equivalently the minimum number of mistakes in the on-line model) that can be made by a learning algorithm that makes a polynomial nubmer of membership queries and uses polynomial computation time. We are able both to reduce the nubmer of equivalence queries used by the previous algorithms and often to prove matching lower bounds. As an example, consider the class of DNF formulas over n variables with at most k = O(logn) terms. Previously, the algorithm of Blum and Rudich... Read complete abstract on page 2.