Learning Read-Once Formulas Using Membership Queries

TitleLearning Read-Once Formulas Using Membership Queries
Publication TypeTechnical Report
Year of Publication1989
AuthorsHellerstein, L., & Karpinski M.
Other Numbers520

In this paper we examine the problem of exact learning (and inferring) of read-once formulas (also called mu-formulas or boolean trees) using membership queries. The power of membership queries in learning various classes of formulas was studied by Angluin [A]. Valiant proved that, using three powerful oracles, read-once formulas can be learned in polynomial time [V]. Pitt and Valiant proved that if RP is not equal to NP, read-once formulas cannot be learned by example in polynomial time [PV,KLPV]. We show that given explicitly a boolean formula f defining a read-once function, if RP is not equal to NP, then there does not exist a polynomial time algorithm for inferring an equivalent read-once formula. An easy argument on the cardinality of the set of all (read-once) 1-term DNF formulas implies an exponential lower bound on the number of membership queries necessary to learn read-once formulas. Angluin showed that it takes time 2(superscript Omega(n)) to learn monotone n-term DNf formulas using membership queries [A]. We prove that, surprisingly, it is possible to learn monotone read-once formulas in polynomial time using membership queries. We present an algorithm that runs in time O(n(superscript 3)) and makes O(n(superscript 3)) queries to the oracle. It is based on a combinatorial characterization of read-once formulas developed by Karchmer et. al. [KLNSW]. We also use the combinatorial characterization to prove two other results. We show that read-once formulas can be learned in polynomial time using only one of the three oracles used in Valiant's polynomial time algorithm. In addition, we show that given an arbitrary boolean formula f, the problem of deciding whether f defines a read-once function is complete in the class D(superscript P) under randomized NC(superscript 1)-reductions. The main results of this paper can also be interpreted in terms of efficient input oracle algorithms for boolean function interpolation (cf. [KUW],[GKS].

Bibliographic Notes

ICSI Technical Report TR-89-021

Abbreviated Authors

L. Hellerstein and M. Karpinski

ICSI Publication Type

Technical Report