The Vapnik-Chervonenkis Dimension

2 Notes on Classes with Vapnik-Chervonenkis Dimension 1

The simplest non-trivial structures, in terms of the vapnik-chervonenkis dimension, are the classes (i.e., sets of subsets) for which that dimension is 1. in this note we show a couple of curious results concerning such classes.The first result shows that such classes share a very simple structure, and, as a corollary, the labeling information contained in any sample labeled by such a class can be compressed into a single instance.The second result shows that due to some subtle measurability issues, in spite of the above mentioned fundamental theorem, there are classes of dimension 1 for which an empirical risk minimization learning rule fails miserably.