language: en

Asking Questions to Minimize Errors

Nader H. Bshouty
Department of Computer Science The University of Calgary
2500 University Drive N.W. Calgary, Alberta, Canada T2N 1N4
bshouty@cpsc.ucalgary.ca
Sally A. Goldman
Department of Computer Science Washington University
St. Louis, MO 63130
sg@cs.wustl.edu
Thomas R. Hancock
Siemens Corporate Research, Inc.
755 College Road East Princeton, NJ 08540
hancock@learning.siemens.com
Sleiman Matar
Department of Computer Science The University of Calgary
2500 University Drive N.W. Calgary, Alberta, Canada T2N 1N4
sleiman@cpsc.ucalgary.ca September 1993 WUCS-93-23

Abstract A number of efficient learning algorithms achieve exact identification of an unknown function from some class 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 number of membership queries and uses polynomial computation time. We are able both to reduce the number 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(log n) terms. Previously, the algorithm of Blum and Rudich [BR92] provided the best known upper bound of 2 O(k) log n for the minimum number of equivalence queries needed for exact identification. We greatly improve on this upper bound showing that exactly k counterexamples are needed if the learner knows k a priori and exactly k +1 counterexamples are needed if the learner does not know k a priori. This exactly matches known lower bounds [BC92]. For many of our results we obtain a complete characterization of the tradeoff between the number of membership and equivalence queries needed for exact identification. The classes we consider here are monotone DNF formulas, Horn sentences, O(log n)-term DNF formulas, read-k sat-j DNF formulas, read-once formulas over various bases, and deterministic finite automata.