Celebratio Mathematica — Rubinstein

Complete Bibliography

Works connected to Thomas Hofmann

Filter the Bibliography List

year	title	people

			clear

B. I. P. Rubinstein, P. L. Bartlett, and J. H. Rubinstein: “Shifting, one-inclusion mistake bounds and tight multiclass expected risk bounds,” pp. 1193–1200 in NIPS: Proceedings of the 2006 conference (Vancouver, 4–7 December 2006). Edited by B. Schölkopf, J. C. Platt, and T. Hofmann. Advances in Neural Information Processing Systems 19. MIT Press (Cambridge, MA), 2007. incollection

Under the prediction model of learning, a prediction strategy is presented with an i.i.d. sample of \( n-1 \) points in \( \mathcal{X} \) and corresponding labels from a concept \( f\in\mathcal{F} \), and aims to minimize the worst-case probability of erring on an \( n \)th point. By exploiting the structure of \( \mathcal{F} \), Haussler et al. achieved a \( \operatorname{VC}(\mathcal{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=\operatorname{VC}(\mathcal{F}) \) bound on one-inclusion graph density. The first main result of this paper is a density bound of \[n\begin{pmatrix}n-1\\ \leq d-1\end{pmatrix}\bigm/\begin{pmatrix}n\\ \leq d\end{pmatrix} < d ,\] which positively resolves a conjecture of Kuzmin & Warmuth relating to their unlabeled Peeling compression scheme and also leads to an improved mistake bound for the randomized (deterministic) one-inclusion strategy for their unlabeled Peeling compression scheme and also leads to an improved mistake bound for the randomized (deterministic) one-inclusion strategy for all \( d \) (for \( d\approx \Theta(n) \)). The proof uses a new form of VC-invariant shifting and a group-theoretic symmetrization. Our second main result is a \( k \)-class analogue of the \( d/n \) mistake bound, replacing the VC-dimension by the Pollard pseudo-dimension and the one-inclusion strategy by its natural hypergraph generalization. This bound on expected risk improves on known PAC-based results by a factor of \( O(\log n) \) and is shown to be optimal up to a \( O(\log k) \) factor. The combinatorial technique of shifting takes a central role in understanding the one-inclusion (hyper)graph and is a running theme throughout.

John C. Platt	Related
Thomas Hofmann	Related
Benjamin I. P. Rubinstein	Related
Bernhard Schölkopf	Related
Peter L. Bartlett	Related