DNF are Teachable in the Average Case.
H. Lee and
R. Servedio and
A. Wan.
Machine Learning, 69: 79--96, 2007.
Preliminary version in
Nineteenth Annual Conference on Computational Learning Theory
(COLT), 2006, pp. 214--228.
Abstract:
We study the average number of well-chosen labeled examples that are
required for a helpful teacher to uniquely specify a target function
within a concept class. This ``average teaching dimension'' has been
studied in learning theory and combinatorics
and is an attractive
alternative to the ``worst-case'' teaching dimension of Goldman and
Kearns \cite{golkea92} which is exponential for many interesting
concept classes. Recently Balbach \cite{bal05} showed that the
classes of 1-decision lists and 2-term DNF each have linear
average teaching dimension.
As our main result, we extend Balbach's teaching result for 2-term
DNF by showing that for any $1 \leq s \leq 2^{\Theta(n)}$, the
well-studied concept classes of at-most-$s$-term DNF and
at-most-$s$-term monotone DNF each have average teaching dimension
$O(ns)$. The proofs use detailed analyses of the combinatorial
structure of ``most'' DNF formulas and monotone DNF formulas. We
also establish asymptotic separations between the worst-case and
average teaching dimension for various other interesting Boolean
concept classes such as juntas and sparse $GF_2$ polynomials.
Postscript or
pdf of full version
of conference paper
pdf of journal version
Back to
main papers page