Partial Occam's Razor and its Applications

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 some examples that some improvement is possible by this approach. First we obtain a new (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 (Cf. The hypothesis size of Winnow is O(n k )). Next we show that 1decision lists of length d with n variable..