Celebratio Mathematica

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

B. I. P. Rubinstein, P. Bartlett, and J. H. Rubinstein: Shifting: One inclusion mistake bounds and sample compression. Technical report UCB/EECS-2007-86, EECS Department, UC-Berkeley, 25 June 2007. Preprint of an article published in J. Comput. Syst. Sci. 75:1 (2009). techreport

We present new expected risk bounds for binary and multiclass prediction, and resolve several recent conjectures on sample compressibility due to Kuzmin and Warmuth. By exploiting the combinatorial structure of concept class \( \mathcal{F} \), Haussler et al. achieved a \( \operatorname{VC}(\mathcal{F})/n \) bound for the natural one-inclusion prediction strategy. The key step in their proof is a \( d = \operatorname{VC}(\mathcal{F}) \) bound on the graph density of a subgraph of the hypercube–one-inclusion graph. The first main result of this report 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 and Warmuth relating to their unlabeled Peeling compression scheme and also leads to an improved one-inclusion mistake bound. The proof uses a new form of VC-invariant shifting and a group-theoretic symmetrization. Our second main result is an algebraic topological property of maximum classes of VC-dimension \( d \) as being \( d \)-contractible simplicial complexes, extending the well-known characterization that \( d=1 \) maximum classes are trees. We negatively resolve a minimum degree conjecture of Kuzmin and Warmuth — the second part to a conjectured proof of correctness for Peeling — that every class has one-inclusion minimum degree at most its VC-dimension. Our final 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 result improves on known PAC-based expected risk bounds 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.

Peter L. Bartlett	Related
Benjamin I. P. Rubinstein	Related

B. I. P. Rubinstein, P. L. Bartlett, and J. H. Rubinstein: “Shifting: one-inclusion mistake bounds and sample compression,” J. Comput. Syst. Sci. 75 : 1 (2009), pp. 37–59. A corrigendum was published in J. Comput. Syst. Sci. 76:3–4 (2010). MR 2472316 Zbl 1158.68452 article

We present new expected risk bounds for binary and multiclass prediction, and resolve several recent conjectures on sample compressibility due to Kuzmin and Warmuth. By exploiting the combinatorial structure of concept class \( \mathcal{F} \), Haussler et al. achieved a \( \operatorname{VC}(\mathcal{F})/n \) bound for the natural one-inclusion prediction strategy. The key step in their proof is a \( d=\operatorname{VC}(\mathcal{F}) \) bound on the graph density of a subgraph of the hypercube–one-inclusion graph. 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 and Warmuth relating to their unlabeled Peeling compression scheme and also leads to an improved one-inclusion mistake bound. The proof uses a new form of VC-invariant shifting and a group-theoretic symmetrization. Our second main result is an algebraic topological property of maximum classes of VC-dimension \( d \) as being \( d \)-contractible simplicial complexes, extending the well-known characterization that \( d=1 \) maximum classes are trees. We negatively resolve a minimum degree conjecture of Kuzmin and Warmuth — the second part to a conjectured proof of correctness for Peeling — that every class has one-inclusion minimum degree at most its VC-dimension. Our final 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 result improves on known PAC-based expected risk bounds by a factor of \( O(\log n) \) and is shown to be optimal up to an \( 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

Peter L. Bartlett	Related
Benjamin I. P. Rubinstein	Related

B. I. P. Rubinstein, P. L. Bartlett, and J. H. Rubinstein: “Shifting: One inclusion mistake bounds and sample compression,” J. Comput. Syst. Sci. 75 : 1 (2009), pp. 39–75. A preprint of this article was published in 2007. article

We present new expected risk bounds for binary and multiclass prediction, and resolve several recent conjectures on sample compressibility due to Kuzmin and Warmuth. By exploiting the combinatorial structure of concept class \( \mathcal{F} \), Haussler et al. achieved a \( \operatorname{VC}(\mathcal{F})/n \) bound for the natural one-inclusion prediction strategy. The key step in their proof is a \( d = \operatorname{VC}(\mathcal{F}) \) bound on the graph density of a subgraph of the hypercube–one-inclusion graph. The first main result of this report 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 and Warmuth relating to their unlabeled Peeling compression scheme and also leads to an improved one-inclusion mistake bound. The proof uses a new form of VC-invariant shifting and a group-theoretic symmetrization. Our second main result is an algebraic topological property of maximum classes of VC-dimension \( d \) as being \( d \)-contractible simplicial complexes, extending the well-known characterization that \( d=1 \) maximum classes are trees. We negatively resolve a minimum degree conjecture of Kuzmin and Warmuth — the second part to a conjectured proof of correctness for Peeling — that every class has one-inclusion minimum degree at most its VC-dimension. Our final 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 result improves on known PAC-based expected risk bounds 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.

Peter L. Bartlett	Related
Benjamin I. P. Rubinstein	Related

B. I. P. Rubinstein, P. L. Bartlett, and J. H. Rubinstein: “Corrigendum to ‘Shifting: One-inclusion mistake bounds and sample compression’,” J. Comput. Syst. Sci. 76 : 3–4 (May–June 2010), pp. 278–280. Corrigendum to an article published in J. Comput. Syst. Sci. 75:1 (2009). MR 2656493 Zbl 1201.68103 article

Peter L. Bartlett	Related
Benjamin I. P. Rubinstein	Related

B. I. P. Rubinstein and J. H. Rubinstein: “A geometric approach to sample compression,” J. Mach. Learn. Res. 13 (April 2012), pp. 1221–1261. MR 2930638 ArXiv 0911.3633 article

The Sample Compression Conjecture of Littlestone & Warmuth has remained unsolved for a quarter century. While maximum classes (concept classes meeting Sauer’s Lemma with equality) can be compressed, the compression of general concept classes reduces to compressing maximal classes (classes that cannot be expanded without increasing VC dimension). Two promising ways forward are: embedding maximal classes into maximum classes with at most a polynomial increase to VC dimension, and compression via operating on geometric representations. This paper presents positive results on the latter approach and a first negative result on the former, through a systematic investigation of finite maximum classes. Simple arrangements of hyperplanes in hyperbolic space are shown to represent maximum classes, generalizing the corresponding Euclidean result. We show that sweeping a generic hyperplane across such arrangements forms an unlabeled compression scheme of size VC dimension and corresponds to a special case of peeling the one-inclusion graph, resolving a recent conjecture of Kuzmin & Warmuth. A bijection between finite maximum classes and certain arrangements of piecewise-linear (PL) hyperplanes in either a ball or Euclidean space is established. Finally we show that \( d \)-maximum classes corresponding to PL-hyperplane arrangements in \( \mathbb{R}^d \) have cubical complexes homeomorphic to a \( d \)-ball, or equivalently complexes that are manifolds with boundary. A main result is that PL arrangements can be swept by a moving hyperplane to unlabeled \( d \)-compress any finite maximum class, forming a peeling scheme as conjectured by Kuzmin & Warmuth. A corollary is that some \( d \)-maximal classes cannot be embedded into any maximum class of VC-dimension \( d+k \), for any constant \( k \). The construction of the PL sweeping involves Pachner moves on the one-inclusion graph, corresponding to moves of a hyperplane across the intersection of \( d \) other hyperplanes. This extends the well known Pachner moves for triangulations to cubical complexes.

year	title	people

			clear

J. Hyam Rubinstein

Complete Bibliography

Works connected to Benjamin I. P. Rubinstein

Filter the Bibliography List