|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-97-033
Partial Occam's
Razor and its Applications
Carlos
Domingo, Tatsuie Tsukiji and Osamu Watanabe
Tokyo Institute of Technology
Japan
Abstract
We introduce the notion of ``partial Occam algorithm''. A partial
Occam algorithm produces a succinct hypothesis that is partially consistent
with given examples, where the proportion of consistent examples is
a bit more than half. By using this new notion, we propose one approach
for obtaining a PAC learning algorithm. First, as shown in this paper,
a partial Occam algorithm is equivalent to a weak PAC learning algorithm.
Then by using boosting techniques of Schapire or Freund, we can obtain
an ordinary PAC learning algorithm from this weak PAC learning algorithm.
We demonstrate with some examples that some improvement is possible
by this approach, in particular in the hypothesis size. First, we
obtain a (non-proper) PAC learning algorithm for $k$-DNF, which has
similar sample complexity as Littlestone's Winnow, but produces hypothesis
of size polynomial in $d$ and $\log k$ for a $k$-DNF target with $n$
variables and $d$ terms ({\it Cf.}~ The hypothesis size of Winnow
is $\CO(n^k)$). Next we show that 1-decision lists of length $d$ with
$n$ variables are (non-proper) PAC learnable by using $\dsp{\CO\rpr{\frac{1}{\epsilon}
\rpr{\log \frac{1}{\delta}+16^d\log n(d+\log \log n)^2}}}$ examples
within polynomial time w.r.t.\ $n$, $2^d$, $1/\epsilon$, and $\log
1/\delta$. Again, we obtain a sample complexity similar to Winnow
for the same problem but with a much smaller hypothesis size. We also
show that our algorithms are robust against random classification
noise.
Download Compressed Postscript
|