|
NeuroCOLT
Technical Report NC-TR-98-014
Efficient Read-Restricted
Monotone CNF/DNF Dualization by Learning with Membership Queries
Carlos Domingo
UPC
Barcelona
Nina Mishra
Hewlett Packard
Palo Alto
Leonard Pitt
Comp Sci
UI Urbana
Keywords:
Query learning; CNF; DNF; Membership queries
Received:10-JUN-98
Abstract
We consider exact learning monotone
CNF formulas in which each variable appears at most some constant
$k$ times (``read-$k$'' monotone CNF). Let $f: \{0,1\}^n \rightarrow
\{0,1\}$ be expressible as a read-$k$ monotone CNF formula for some
natural number $k$. We give an incremental output polynomial time
algorithm for exact learning both the read-$k$ CNF and (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 \in \{0,1\}^n$.
The algorithm yields an incremental polynomial output time solution
to the bounded degree hypergraph transversal problem, and the problem
of (read-$k$) monotone CNF/DNF dualization, which remain open problems
of importance in the unrestricted case.
Download Compressed Postscript
|