1
$\begingroup$

In the PAC-learning setting, it is easy to learn a CNF formula when we know each clause has at most $c$ variables.

We go through each positive sample, and eliminate every clause that contradicts the sample.

Learning a DNF formula is said to be much harder, but it seems a similar procedure can be used, so it is unclear to me why DNF is more difficult.

Start with all conjuctive clauses that have at most $c$ variables. Go through each negative sample, and eliminate clauses that contradict the sample.

$\endgroup$
  • 2
    $\begingroup$ Your argument shows that there is no difference between CNFs and DNFs unless there is a difference between true and false. When people say that learning DNFs is hard, they probably have something else in mind. Since you are not explaining what learning is for you, nor providing any references, it is hard to make any progress in uncovering the mystery. $\endgroup$ – Yuval Filmus Jun 14 '17 at 21:03
5
$\begingroup$

It's important to distinguish between $k$-CNF and CNF. A $k$-CNF formula is a CNF formula where every clauses has at most $k$ literals; a CNF formula has no limit on the number of literals in each clause.

Both $k$-CNF and $k$-DNF are efficiently, properly PAC learnable, when $k$ is constant. In contrast, as far as I am aware, it is not known whether CNF or DNF are efficiently, properly PAC learnable (no PAC-learning procedure is known for either). So there is no asymmetry.

By "efficiently, properly PAC learnable", I mean that there is a polynomial-time algorithm for PAC learning, where the hypothesis space is the same as the concept space (e.g., given labelled instances from a $k$-CNF formula $\phi$, we want to find a $k$-CNF formula $\phi'$ that has low generalization error).

Since you haven't provided any references nor told us where you got the impression that $k$-DNF isn't PAC-learnable, it's hard to know what the exact source of your misconception might be.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.