Learning Read-Once Formulas Using Membership Queries

Abstract

In this paper we examine the problem of exact learning (and inferring) of read-once formulas (also called μ-formulas or boolean trees) using membership queries. An simple 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. We prove that 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 3) and makes O (n 3) queries to the oracle. We introduce a new oracle, the projective equivalence oracle. We show that our membership query algorithm can be adapted to learn arbitrary read-once formulas in polynomial time using a projective equivalence oracle (or, by an observation of Angluin, using superset and subset queries). Our algorithms are based on a combinatorial characterization of read-once formulas developed by Karchmer et. al. [KLNSW88]. We use this 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 DP under randomized NC 1 -reductions. The main results of this paper can also be interpreted in terms of efficient input oracle algorithms for boolean function interpolation (cf. [KUW85], [GKS]).