VC-dimension

Tue, Apr 12, 2016

Definition 1 (Espilon net)

Let \(X\) be a set, let \(\mu\) be a probability measure on \(X\), let \(\mathcal{F}\) be a system of \(\mu\)-measurable subsets of \(X\), and let \(\varepsilon \in [0,1]\) be a real number. A subset \(N\subseteq X\) is called an \(\varepsilon\)-net for \((X,\mathcal{F})\) with respect to \(\mu\) if \(N \cap S \neq \emptyset\) for all \(S \in \mathcal{F}\) with \(\mu(S) \ge \varepsilon\).

Definition 2 (Trace of \(\mathcal{F}\) on \(Y\))

Let \(\mathcal{F}\) be a set system on \(X\) and let \(Y \subseteq X\). We define the restriction of \(\mathcal{F}\) on \(Y\) (also called the trace of \(\mathcal{F}\) on \(Y\)) as \( \mathcal{F}|_Y = \{S \cap Y \colon\, S \in \mathcal{F}\}. \)

Definition 3 (VC-dimension)

Let \(\mathcal{F}\) be a set system on a set \(X\). Let us say that a subset \(A \subseteq X\) is shttered by \(\mathcal{F}\) if each of the subsets of \(A\) can be obtained as the intersection of some \(S \in \mathcal{F}\) with \(A\), i.e., if \(\mathcal{F}|_A = 2^{A}\). We define the VC-dimension of \(\mathcal{F}\), denoted by \(dim(F)\), as the supremum of the sizes of all finite shattered subsets of \(X\). If arbitrarily large subsets can be shattered, the VC-dimension is \(\infty\).

Theorem 1 (Epsilon net theorem)

If \(X\) is a set with a probability measure \(\mu\), \(\mathcal{F}\) is a system of \(\mu\)-measurable subsets of \(X\) with \(dim(\mathcal{F}) \le d\), \(d\ge 2\), and \(r \ge 2\) is a parameter, then there exists a \(\frac{1}{r}\)-net for \((X,\mathcal{F})\) with respect to \(\mu\) of size at most \(Cdr\ln r\), where \(C\) is an absolute constant.

Definition 4 (Shatter function)

We define the shatter function of a set system \(\mathcal{F}\) by \( \pi_\mathcal{F}(m) = \max_{Y\subseteq X, \lvert Y \rvert = m} \lvert \mathcal{F}|_Y \rvert. \)

Lemma 1 (Shatter function lemma)

For any set system \(\mathcal{F}\) of VC-dimension at most \(d\), we have \(\pi_\mathcal{F}(m) \le \Phi_d(m)\) for all \(m\), where \(\Phi_d(m) = \binom{m}{0} + \binom{m}{1} + \cdots + \binom{m}{d}\).

Proposition 1

Let \(\mathbb{R}[x_1,x_2,\ldots,x_d]_{\le D}\) denote the set of all real polynomials in \(d\) variables of degree at most \(D\), and let \( \mathcal{P}_{d,D} = \{\{x\in \mathbb{R}^d \colon\, p(x) \ge 0\}\colon\, p \in \mathbb{R}[x_1,x-2,\ldots,x_d]_{\le D}\}. \) Then \(dim(\mathcal{P}_{d,D}) \le \binom{d+D}{d}\).

Proposition 2

Let \(F(X_1,X_2,\ldots,X_k)\) be a fixed set-theoretic expression (using the operations of union, intersection, and difference) with variables \(X_1,X_2,\ldots,X_k\) standing for sets. Let \(\mathcal{S}\) be a set system on a ground set \(X\) with \(dim(\mathcal{S}) = d < \infty\). Let \( \mathcal{T} = \{F(S_1,S_2,\ldots,S_k) \colon\, S_1,S_2,\ldots,S_k \in \mathcal{S}\}. \) Then \(dim(\mathcal{T}) = O(kd\ln k)\).