Shifting, one-inclusion mistake bounds and tight multiclass expected risk bounds

Abstract

Under the prediction model of learning, a prediction strategy is presented with an i.i.d. sample of n-1 points in χ and corresponding labels from a concept f ∈ F, and aims to minimize the worst-case probability of erring on an nth point. By exploiting the structure of F, Haussler et al. achieved a VC(F)/n bound for the natural one-inclusion prediction strategy, improving on bounds implied by PAC-type results by a O(log n) factor. The key data structure in their result is the natural subgraph of the hypercube-the one-inclusion graph; the key step is a d = VC(F) bound on one-inclusion graph density. The first main result of this paper is a density bound of n(n-1/≤d-1)/(n/≤d ) < d, which positi..