Exact learning of subclasses of CDNF formulas with membership queries

Exact Learning of sub classes of CDNF formulas with memb ership queries ? Carlos Domingo Dept. of Computer Science, Tokyo Institute of Technology, Ookayama, Meguro-ku, Tokyo152, Japan Email: [email protected]itech.ac.jp Abstract. We consider the exact learnabili ty of sub classes of Bo olean formulas from memb ership queries alone. Weshowhowtocombine known learning algorithms that use memb ership and equivalence queries to obtain new learning results only with memb erships. In particular we show the exact learnabili tyofreadk monotone formulas, Satk O (log n )- CDNF, and O ( p log n )-size CDNF from memb ership queries only. 1 Intro duction Learning DNF formulas has b een one of the most attractive and tantalizing problems since the seminal pap er of Valiant Val84 ]. Although many results in the literature gave evidence that the problem is hard even if we are allowto use memb ership queries  AK91 , AHP92 ], it has b een recently proved byJackson  Jac94 ] that using memb ership queries, DNF are PAC learnable in p olynomial time under the uniform distribution. Here we concentrate in a more restricted framework. While Jackson's algorithm is a PAC learning algorithm, we wish to have exact identication of the target formula. In this more restricted setting known as exact learning  Ang88 ] few p ositive results have b een discovered using only memb ership queries queries. Among others, the following very restricted sub classes of monotone DNF formulas are prop erly exact learnable bymemb ership queries: monotone read-once formulas  AHK93 ], k -term monotone DNF  BGHM93 ], and 2-monotonic p ositive functions  MI94b ]. In the non monotone case, decision trees of O (log n )-depth  KM93 ]andSatk O (log n )-DNF  BF+94 ] are shown to b e exact learnable using a threshold of parit y functions as a hyp othesis. In almost all the cases, weshow that stronger results hold if wemeasure the eciency of the algorithm with resp ect to the DNF size as well as the CNF size. Our approach is the following. We use well known learning algorithms  Ang88 , Bsh95 ] that learn certain classes of formulas with memb ership and equivalence queries. Those algorithms have some nice prop erties and we ? Research supp orted by the Esprit EC program under pro ject 7141 (ALCOM-I I) and Working Group 8556 (NeuroColt), and by the Spanish DGICYT (pro ject PB92- 0709). showhow to exploit them to learn some classes of formulas with only memb ership queries. Those algorithms are monotone with resp ect to the target, i.e. they always pro duce a hyp othesis that implies the target. Moreover, they have a dual algorithm that b ehaves in a symmetric way.Thus, combining them we are able to obtain new p ositive learning results. The price wehavetopay for learning only with memb erships is that now, the query complexity dep ends on the DNF as well as the CNF size of the target, not only one of them as it would b e desired. Nevertheless, our results are optimal in the number of memb ership needed. It has b een shown in  BGHM93 ]that any exact learning algorithm that uses only memb ership queries must consider simultaneously the DNF and the CNF size when measuring the numberofmemb ership queries for monotone formulas and the dual and monotone dual dimension (which in our case are p olynomially related to the DNF and CNF size but not in general, see Section 4) for non monotone ones. The classes we show to b e exact learnable only with memb ership queries are readk monotone formulas, Satk O (log n )-DNF formulas and O ( p log n )-size CDNF. For proving our results, weshowhow to test equivalence b etween some classes of Bo olean formulas. These algorithms maybeofindependentinterest outside the learning community. The rest of the pap er is organized as follows. Section 2 gives denition and terminology used throughout the pap er. Section 3 shows how to learn readk monotone formulas. In Section 4 the learnability of sub classes of general DNF formulas is shown. Finally, Section 5 discuss the results and presents some future work and op en problems. 2 Preliminaries We are interested in the learnability of Bo olean functions. First, wegive some denitions and notation. We denote by e i the assignmentthat is 0 everywhere except in the i -th bit. A literal is either a variable x i or its negation  x i .We will use the order  over f 0  1 g n where for two assignments a and b , a  b if for every 1  i  n , a i  b i . A Bo olean function is said to b e monotone if for every pair of assignments a b 2f 0  1 g n , a  b implies f ( a )  f ( b ). A Bo olean function is called unate if there exists an assignment a suchthat f ( x + a ) is monotone, where \+" is the group addition in GF (2) n . Nowwe dene several classes of formulas that we will consider. A DNF expression is a disjunction of terms, where each term is a conjunction of literals and a CNF expression is a conjunction of clauses, where each clause is a disjunction of literals. The size of a DNF formula, denoted by d ( f ), is the number of terms and the size of a CNF formula, denoted by c ( f ) is the numb er of clauses. A k - term DNF ( k -clause CNF) is the class of functions represented as a DNF (CNF) with at most k terms (clauses). We denote by k -size CDNF the class of formulas included in k -term DNF \ k -clause CNF. On the other hand, k -DNF ( k -CNF) is the class of form ulas that haveatmost k literals in each term (clause). The class Satk DNF (CNF) is the class of formulas where each assignment satises at most k terms (clauses) simultaneously.Furthermore, a Satk CDNF is a formulas that is contained in the class Satk DNF \ Satk CNF. Finally, the class of k -depth decision trees is the class of Bo olean functions that can b e represented as a decision tree of depth at most k . The class of k -depth decision trees is strictly included in the class Sat-1 k -CDNF, also called Disjoint k -CDNF. Wenow recall the denitions of the Fourier transform needed in Section 4. Every Bo olean function can b e uniquely expressed in terms of its Fourier sp ectrum. That is, f ( x )= P S f 1 :::n g ^ f ( S )  S ( x ) where  S ( x )= Q i 2 S ( ; 1) x i and the Fourier co ecients ^ f ( S ) calculate the correlation of f and  S with resp ect to the uniform distribution. Furthermore, b ecause the vector space of real-valued functions over f 0  1 g n has dimension 2 n ,the set of2 n parity functions forms an orthonormal basis for this vector space and every function f can b e uniquely expressed as a linear combination of parity functions. We call the support of a function to f S j ^ f ( S ) 6 =0 g , i.e. the set of subsets of variables such that the corresp onding Fourier co ecient is non zero. As we mention in the intro duction, we are interested in learning algorithms that are \monotone" with resp ect to the target. The following denition formalizes this idea. Denition 1. A learning algorithm L is said to b e monotone if learning a target formula f , always pro duce hyp othesis h suchthat h ) f . Symmetrically,a learning algorithm L  is antimonotone if always pro duce hyp othesis h  such that f ) h  . 1 algorithm L 1 L  2run L until it pro duces h 3run L  until it pro duces h  4 while EQU ( h h  c ) 6 =\ YES 00 do 5/* EQU checks whether h  h  , and if not returns c such that h ( c ) 6 = h  ( c )*/ 6 if h ( c ) 6 = f ( c ) then 7 give c to L and up date h . 8 else 9 give c to L  and up date h  . 10 end 11 end Fig. 1. Combination of a monotone and an antimonotone learning algorithm. Therefore, we can combine b oth algorithms as it is shown in Figure 1 and obtain the following useful to ol for designing new learning algorithms. Lemma 2. Let L and L  berespectively a monotone and antimonotone exact learning algorithms with membership and equivalence queries for a class of concepts C .Let H and H  be the hypothesis class usedby L and L  respectively and let EQU be and algorithm for decide the equivalencebetween any pair of formulas h 2H and h  2H  such that h ) h  . Then, the concept class C is exactly learnable only with membership queries. We observethateven if algorithm EQU just decides whether h is equivalent to h  without nding the counterexample c needed in our learning algorithm, n extra calls of EQU suces to nd a counterexample. Notice also that the monotonicity restriction of the algorithms can b e relaxed as follows. Weonly need that b oth algorithms never issue a hyp othesis equal to anyhyp othesis issued by the other except when they nd the target. However, wehavenot found any pair of learning algorithms that satisfy this condition and are not \monotone" in the previous sense. This wayto combine learning algorithms was used in  BC+95 ] to obtain learning algorithms with memb ership queries and an NP-oracle. In this pap er, we concentrate in some classes that can b e eectively learned with membership queries without the need of an NP-oracle. 3 Learning monotone formulas The rst algorithm we are going to use is Angluin's algorithm (denoted by A ) for learning monotone DNF formulas with memb ership and equivalence queries  Ang88 ]. Algorithm A is a monotone learning algorithm and the hyp othesis pro duced are always monotone DNF formulas. Moreover, it is easy to see that we can invert algorithm A by greedily collecting all maximalfalse vectors from negative counterexamples instead of greedily collection all minimal true assignments from p ositive counterexamples. Thus, we obtain the dual algorithm A  that learns monotone CNF formulas with memb ership and equivalence queries and hyp othesis that are monotone CNF formulas. Moreover, this algorithm is an antimonotone algorithm. Thus, algorithms A and A  meet the requirements of Lemma 2. In the following Subsection, we showaninteresting class that is learnable by the combination of A and A  .Thiswayofcombining Angluin's algorithm was used in  BI94 ] when comparing learning with dualization. 3.1 Learning Readk monotone formulas A readk DNF formula is a formula where eachvariable app ears at most k times. The sensitive set of an assignment x is dened by S ( x )= f y j f ( x ) 6 = f ( y ) d ( x y )=1 g where d ( x y ) is the Hamming distance of x and y .If S ( x ) 6 =  and f ( x )=1then wesaythat x is a positive sensitive assignment of f . Let us rst give a couple of useful prop erties of readk formulas. Prop osition 3. If x isapositive sensitive assignment of readk monotone DNF formula f then x simultaneously satises at most k terms of f . Proof. Let x b e a p ositive sensitive assignment that satises k +1 terms of a readk DNF formula f and let y 2 S ( x )suchthat y just diers from x in the i -th bit. Since ipping the i -th bit of x from 1 to 0 the formula is not satised, x i must app ear in the k + 1 terms of f that x satised. Thus, f is not a readk formula. ut Prop osition 4. Let f bea readk monotone DNF formula and let g be a monotone CNF formula. Assume that f is not equivalent to g and there exists an assignment x such that f ( x )=0 and g ( x )=1 . Then, there exists another assignment y such that x  y , f ( y )=0 , g ( y )=1 and y belongs to the sensitive set of a positive sensitive assignment of f . Proof. Let x b e an assignmentsuchthat f ( x )=0 and g ( x )=1. Weip0bits of x while keeping f ( x )=0 until we obtain y suchthat x  y and ipping one bit more of y we satisfy f . By monotonicity, g is still satised by y and y b elongs to the sensitive set of a p ositive assignmentfor f . ut Using these two prop erties we can showhowto check equivalence for a monotone readk DNF formula. Lemma 5. Let f beareadk monotone DNF formula and g a monotone CNF formula. We can test whether f and g areequivalent in polynomial time with r espect to d ( f ) and c ( g ) . Proof. Since f is in DNF and g in CNF we can eciently check whether there exists an assignment x such that f ( x ) = 1 and g ( x ) = 0. If wendsuchan assignmentwe are done. Otherwise, if f and g are still not equivalent, there should b e an assignment x suchthat f ( x )=0and g ( x ) = 1. By Prop osition 4 there exists another assignment y that b elongs to the sensitive set of a p ositive sensitive assignment and is still a valid witness of non equivalence b etween f and g . Moreover, Prop osition 3 tell us that all the p ositive sensitive assignment satisfy at most k terms. Therefore, wecheck the sensitive sets of all the p ossible p ositive sensitive assignments of f . The numberofsensitive assignments of f is smaller than n k +1 which is p olynomial for constant k .Thus, either we nd an assignment y whichproofsthat f is not equivalentto g or, by Prop osition 4 it do es not exist and f is equivalentto g . ut Therefore, Lemma 2 together with algorithms A and A  and the ab oveLemma implies the following Theorem. Theorem 6. The class of readk monotone DNF formulas is exactly learnable using membership queries in polynomial time in max f d ( f ) c ( f ) g . By results of  BC+95 ] this upp er b ound on the numberofmemb ership queries cannot b e further improve. Moreover, since learning a readk DNF for k  3isequivalent to learn an arbitrary DNF  AK91 ], the monotonicityrestriction is also optimal. Observethatifwe can learn non-monotone read-thrice formulas with memb ership queries we will b e able to learn DNF formulas with memb ership queries and that is imp ossible since they contain the class of singletons (monomialsof n variables). This class is not exactly learnable using less than 2 n memb ership queries  Ang88 ]. 4 Learning arbitrary formulas In  Bsh95 ], Bshouty showed that CDNF formulas are exactly learnable in p olynomial time with memb ership and equivalence queries. He uses an algorithm, that we will call B which is based on Angluin's algorithm for monotone DNF formulas. Thus, it shares the same prop erty, it is a monotone learning algorithm. The hyp othesis are depth-3 formulas consisting of a CNF of p olynomiallymany DNF formulas as clauses. The algorithm runs in p olynomial time in the DNF size of the target and its monotone dimension (see  Bsh95 ] for a detailed denition). Moreover, his algorithm can b e inverted obtaining a dual monotone learning algorithm B  for the same class of formulas  BC+95 ]. In this case the hyp othesis are also depth-3 formulas but consisting of a DNF of p olynomially many CNF formulas as terms. This dual version runs in p olynomial time in the CNF size and its dual monotone dimension. In the following Subsections, weshow some classes of formulas that are learnable by the combination of B and B  . 4.1 Learning Satk O (log n ) -DNF formulas In  KM93 ], Kushilevitz and Mansour gave an algorithm for exactly nding the supp ort of the class of O (log n )-depth decision tree using memb ership queries. Moreover, in  BF+94 ]itwas proved that the same algorithm also obtains the supp ort of k -disjoint O (log n )-DNF formulas, a class that strictly contain decision trees of O (log n )-depth. These results are stated in the following theorem. Theorem 7.  KM93 , BF+94 ]There is a deterministic algorithm, that for any Boolean function f that can berepresentedasaSatk O (log n ) -DNF , outputs the support of f in polynomial time in n . We use previous algorithm to obtain the following result. Lemma 8. Let f and g beBoolean formulas that have a representation as a Satk O (log n ) -DNF. Then, we can test in polynomial time in n whether f and g areequivalent. Proof. We just have to use the algorithm of Theorem 7 to obtain the supp orts of f and g , whichhave a p olynomial numb er of sets. Wecheck whether the supp orts of f and g are equal and answer 'yes' in case they are and 'no' otherwise. Since no two dierent sets of Fourier co ecients can represent the same Bo olean function, the correctness follows. ut Notice that we do not care ab out howformulas f and g are given in the previous lemma, as far as the could b e represented as required. Thus, algorithm of Theorem 7 can b e applied, since it just tests memb ership of the input formulas. It do es not use any prop ertyofthewayin which the input formulas are actually represented. Therefore, we can obtain the following learning result. Theorem 9. The class of Satk O (log n ) -DNF formula are exactly learnable in polynomial time with respect to its DNF and CNF size, from membership queries alone. The hypothesis is a depth-3 formula. Proof. Run algorithm of Figure 1 using Bshouty's algorithms B and B  for CDNF formulas as algorithms L and L  and using the algorithm describ ed in Lemma 8 for testing equivalence. Since that algorithm do es not provide any counterexample, we need to run it n + 1 times for solving every equivalence query. Moreover, this classes have monotone and dual monotone dimension p olynomial (see  Bsh95 ]and  BGHM93 ]) and therefore the running time of B and B  is also p olynomial. ut The class of Satk O (log n )-DNF contains decision trees of logarithmic depth, so we also exactly learn the same class. Notice that we cannot extend this result to any class of decision trees that can represent singletons (for instance, p olynomial size decision trees) since that class is known to b e non exactly learnable with p olynomial numberofmemb ership queries. As wementioned b efore, our result was already proved in  BF+94 ]. However, by using the combination of Bshouty's algorithms, we are able to improved the waythe hyp othesis is represented. Our learnability result is in terms of a depth-3 formula while the result in  BF+94 ]was in terms of a threshold of parity functions (a Fourier based representation). It is op en whether this class of formulas is prop er learnable in p olynomial time from memb ership queries only. 4.2 Learning Bounded size CDNF formulas In this subsection weshowhow to use again the combination of Bshouty's algorithms to learn a class of formulas that have b ounded numb er of terms and clauses in its DNF and CNF representation resp ectively. First, let see that we can test equivalence b etween some formulas. Lemma 10. Let f = f 1 ^ ::: ^ f r and g = g 1 _ ::: _ g s be depth-3 formulas, where f i are DNF formulas and g j are CNF formulas such that j f j + j g j = O (log n ) and f ) g . Then, we can test whether f is equivalent to g in polynomial time in n . Proof. Since f implies g , there always exists at least one variable x k that either app ears p ositive or negative in b oth formulas simultaneously.To see this claim, observethatwhen f ( x )=1,wejusthave to set the variables in some terms t i 1 2 f 1 t i 2 2 f 2 :::t i r 2 f r such that all of them are satised, i.e. ( t i 1 ( y ) ^ ::: ^ t i r ( y )) = 1, where y is a partial assignmentcontained in x but dened only with the variables that app ear in those terms. The partial assignment y should already satisfy one g j 2 g , i.e. g j ( y )=1.Thus, it should b e at least one variable x k that app ears either p ositive or negative simultaneously in a one of the clauses satised by y and in g j . Then, we build a decision tree with x k in the ro ot where b oth its children have either a term less in f or a clause less in g and we solve the problem recursively. If all the leaves of this tree have equivalent pair of formulas, the input formulas are equivalent. However, if we nd a witness of non equivalence in a pair of formulas in any leaf, we can carry backthatwitness and show the non equivalence of the input formulas. After at most O (log n ) iterations either f or g b ecomes constant. Supp ose that g b ecomes constantin one of the lea ves. Then, if there is an assignment y to the variables of function f in that leaf such that f ( y ) 6 = g , it is a witness of the non equivalence b etween the original formulas. If f is a non empty unate formula, it is non constantand we can set its variables suchthat f 6 = g and prove the non equivalence. On the other hand, if f is non unate, there exists a variable x j in one term and the same variable app ears negated in another one. Then, wekeep branching with resp ect to the values of x j and again b oth children have one term less. After at most j f j iterations more f b ecomes constantandwe can solve the problem. The case when f b ecomes constantbutnot g is treated in a symmetric way.Thus, our recursion tree has depth at most O (log n ), the whole tree is p olynomial size and we are done. ut This lemma gives us a eective pro cedure to decide the equivalence b etween the formulas together with a way to nd a witness in the case that they are not equivalent. Thus, we can derive the following theorem: Theorem 11. The class of O ( p log n ) -size CDNF is exact learnable in polynomial time using membership queries and a depth-3 formula as a hypothesis. Proof. Wejusthave to observe that Bshouty's algorithms B and B  ,when learning a formula f 2O ( p log n )-term DNF \O ( p log n )-clause CNF always pro duce hyp othesis of the form h = h 1 ^ ::: ^ h r and h  = h  1 _ :::h  s where r is at most the CNF size of f and s is at most the DNF size of f .Moreover, the numb er of terms in any DNF formula h i is b ounded by the DNF size of f and the numb er of clauses in any CNF formula h  j is b ounded by the CNF size of f . Thus, j h j + j h  j = O (log n ) and we use Lemma 10 to solve an equivalence query. By Lemma 2 we can exactly learn that class only with memb ership queries. The running time of b oth algorithms B and B  is p olynomial in the formula size since so they are its resp ective monotone and dual monotone dimension. ut This result is an improvement of the learnabilityof k -term monotone DNF from mem b ership queries shown in  BGHM93 ] since we are learning a non monotone class and with non constantnumb er of terms. Although it has b een proved that k -term monotone DNF for non constantnumb er of terms is not learnable from memb ership queries only  BGHM93 ], that pro of assume that we learn with resp ect to the DNF size only.Thus, considering the CNF size together with the DNF allows us to overcome that diculty. Moreover, as we mention b efore, the numb er of memb ership queries needed is optimal  BC+95 ]. Theorem 11 also improves the results in  BGHM93 ] where p log n -term DNF are shown to b e exactly learnable with memb ership and an optimal number of equivalence queries ( p log n + 1). Again, by considering the CNF size we are able to get rid of the equivalence queries, while considering only the DNF size it is not p ossible. 5 Conclusions Wehave shown that the classes of readk monotone formulas, Satk O (log n )- DNF and O ( p log n )-size CDNF are exactly learnable with only memb ership queries. All our algorithms use a number of memb ership queries b ounded by max f d ( f ) c ( f ) g that matches the lower b ounds in  BC+95 ]. Thus, although we are using a measure for the complexity that might seem unrealistic, it is the optimal one for this framework. Moreover,we also prop ose a systematic wayto obtain new learning algorithms from memb ership queries only.Now, wejust have to concentrate in solving the equivalence problem b etween some other classes of formulas and from there we automatically will derive new learning algorithms. Furthermore, we also showhowtosolve equivalence for some classes of formulas. These results may b e of indep endentinterest outside the learning community. For instance, for the monotone case, solving equivalence has b een proved to b e equivalent to solve the duality problem (we refer the reader to  BI94 ] for details and further references). We left as op en problem the extension of our results from readk monotone formulas to read-once and read-twice arbitrary formulas. In this resp ect, we already have some encouraging results. As wemention b efore, it is not p ossible to extend this result to read-thrice formulas since it will imply exact learning of general DNF with memb ership queries. This is known to b e imp ossible with a p olynomial numb er of memb ership queries since the class of DNF contains the class of all singletons. It is also op en whether the class of Satk O (log n )-DNF or the more general one of O (log n )-CDNF is prop erly exact learnable using only memb ership queries. 6 Acknowledgments Iwould like to thank OsamuWatanab e and Ricard Gavalda for many helpful discussions. I also want to thank Jorge Castro for a simplication of the pro of of Theorem 8. References  AHP92] H. Aizenstein, L. Hellerstein, and L. Pitt. Read-thrice DNF is hard to learn with memb ership queries and equivalence queries. Proceedings of the 33rdAnnual IEEE Symposium on Foundations of Computer Science , (1992), 523-532.