4 - Vapnik–Červonenkis Combinatorics

Summary

This chapter will treat some classes of sets satisfying a combinatorial condition. In Chapter 6 it will be shown that under a mild measurability condition to be treated in Chapter 5, these classes have the Donsker property, for all probability measures P on the sample space, and satisfy a law of large numbers (Glivenko–Cantelli property) uniformly in P. Moreover, for either of these limit-theorem properties of a class of sets (without assuming any measurability), the Vapnik–Červonenkis property is necessary (Section 6.4).

The name Červonenkis is sometimes transliterated into English as Chervonenkis. The present chapter will be self-contained, not depending on anything earlier in this book, except in some examples.

Vapnik–Červonenkis Classes of Sets

Let X be any set and C a collection of subsets of X. For A ⊂ X let C_A:= C ⊓ A:= A ⊓ C:= {C ⋂ A: C ∈ C}. Let card(A):= |A| denote the cardinality (number of elements) of A and 2^A:={B: B ⊂ A}. Let Δ^C(A):=|C_A|. If A ⊓ C = 2^A, then C is said to shatter A. If A is finite, then C shatters A if and only if Δ^C(A) = 2^|A|.