An Algorithm to Learn Read-Once Threshold Formulas, and some Generic Transformations between Learning Models
Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein, Marek Karpiński · 1993
We present a membership query (i.e. black box interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of boolean threshold functions. We also present a catalogue of generic transformations that can be used to convert an algorithm in one learning model into an algorithm in a different model. 1 Introduction In one of the simplest models of learning, the learner must exactly identify an unknown target function by asking membership queries. A membership query asks for the output of the function on an element of its domain. The query is answered by an infallible, honest oracle. This learning model is equivalent to standard black box interpolation where one substitutes inputs into a black box oracle computing a function from some class, and uses the observed outputs to deduce what the hidden function must be. This research was supported in part by the NSERC of Canada. y Supported by ONR grant N00014-85-K-0445 and NSF grant NSF-CCR-89-02500. The r...