On the equivalence of Occam algorithms
Zaman Keinath-Esmail
Blumer et al. (1987, 1989) showed that any concept class that is learnable by
Occam algorithms is PAC learnable. Board and Pitt (1990) showed a partial
converse of this theorem: for concept classes that are closed under exception
lists, any class that is PAC learnable is learnable by an Occam algorithm.
However, their Occam algorithm outputs a hypothesis whose complexity is
$\delta$-dependent, which is an important limitation. In this paper, we show
that their partial converse applies to Occam algorithms with
$\delta$-independent complexities as well. Thus, we provide a posteriori
justification of various theoretical results and algorithm design methods which
use the partial converse as a basis for their work.