Combinatorial shell bounds for generalization ability
D. A. Kochedykov · Pattern Recognition and Image Analysis · 2010
We consider a problem of supervised statistical learning for a finite population and obtain PAC generalization bounds within the combinatorial PAC framework. Combinatorial counterparts of Langford shell bounds are obtained and are shown to be either the particular case of the Occam razor bound or a variant of Vapnik-Chervonenkis bound and similarly loose in both cases. The reasons for looseness of shell bounds are analyzed, the bounds are compared experimentally.