Seminar on Computational Learning and Adaptation

 
Efficient Read-Restricted Monotone CNF/DNF Dualization
by Learning with Membership Queries

Nina Mishra
Hewlet-Packard Laboratories
Palo Alto, CA
nmishra@hpl.hp.com

The monotone CNF/DNF dualization problem is the problem of computing a CNF expression given a monotone DNF expression.  The dualization problem naturally arises in many disciplines.  For example, in the context of finding association rules in data mining, it is equivalent to the common subproblem of computing antecedents with sufficiently high support. In the context of graph theory, it is equivalent to generating all maximal independent sets of a hypergraph. In the context of machine learning, it is equivalent to learning a monotone CNF and DNF formula with membership queries.

We give an efficient monotone CNF/DNF learning algorithm when the formula is read-k, i.e., when each variable appears at most some constant k times.  More specifically, let f be a boolean function expressible as a read-k monotone CNF formula.  We give an incremental output polynomial time algorithm for exact learning both the read-k CNF and the (not necessarily read restricted) DNF descriptions of f.  The algorithm's only method of obtaining information about f is through membership queries, i.e., by inquiring about the value f(x) for points x.  The algorithm yields an incremental output polynomial time solution to the (read-k) monotone CNF/DNF dualization problem.

Joint work with Carlos Domingo and Leonard Pitt.

Return to the seminar schedule