【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.VC维
现实学习任务所面临的通常是无限假设空间，例如实数域中的所有区间、$\mathbb{R}^d$空间中的所有线性超平面。欲对此种情形的可学习性进行研究，需度量假设空间的复杂度。最常见的办法是考虑假设空间的“VC维”（Vapnik-Chervonenkis dimension）。
介绍VC维之前，我们先引入几个概念：增长函数（growth function）、对分（dichotomy）和打散（shattering）。
给定假设空间$\mathcal{H}$和示例集$D=\{ \mathbf{x}_1,\mathbf{x}_2, … , \mathbf{x}_m \}$，$\mathcal{H}$中每个假设$h$都能对$D$中示例赋予标记，标记结果可表示为：
\[h \mid _D = \{ \left( h(\mathbf{x}_1),h(\mathbf{x}_2),...,h(\mathbf{x}_m) \right) \}\]随着$m$的增大，$\mathcal{H}$中所有假设对$D$中的示例所能赋予标记的可能结果数也会增大。
例如，对二分类问题，若$D$中只有2个示例，则赋予标记的可能结果只有4种；若有3个示例，则可能结果有8种。
定义12.6 对所有$m \in \mathbb{N}$（$\mathbb{N}$为自然数域），假设空间$\mathcal{H}$的增长函数$\Pi_{\mathcal{H}}(m)$为：
\[\Pi_{\mathcal{H}}(m) = \max_{\{\mathbf{x}_1,...,\mathbf{x}_m\} \subseteq \mathcal{X} } \lvert \{ ( h(\mathbf{x}_1),...,h(\mathbf{x}_m) ) \mid h \in \mathcal{H} \} \rvert \tag{1}\]增长函数$\Pi_{\mathcal{H}}(m)$表示假设空间$\mathcal{H}$对$m$个示例所能赋予标记的最大可能结果数。显然，$\mathcal{H}$对示例所能赋予标记的可能结果数越大，$\mathcal{H}$的表示能力越强，对学习任务的适应能力也越强。因此，增长函数描述了假设空间$\mathcal{H}$的表示能力，由此反映出假设空间的复杂度。我们可利用增长函数来估计经验误差与泛化误差之间的关系。
定理12.2 对假设空间$\mathcal{H}$，$m\in \mathbb{N},0<\epsilon<1$，存在$h \in \mathcal{H}$：
\[P(\lvert E(h)-\hat{E}(h) \rvert > \epsilon ) \leqslant 4 \Pi_{\mathcal{H}} (2m) \exp (-\frac{m\epsilon^2}{8}) \tag{2}\]证明过程见论文：ON THE UNIFORM CONVERGENCE OF RELATIVE FREQUENCIES OF EVENTS TO THEIR PROBABILITIES。
假设空间$\mathcal{H}$中不同的假设对于$D$中示例赋予标记的结果可能相同，也可能不同；尽管$\mathcal{H}$可能包含无穷多个假设，但其对$D$中示例赋予标记的可能结果数是有限的：对$m$个示例，最多有$2^m$个可能结果（个人注解：针对二分类问题）。对二分类问题来说，$\mathcal{H}$中的假设对$D$中示例赋予标记的每种可能结果称为对$D$的一种“对分”（每个假设会把$D$中示例分为两类，因此称为对分）。若假设空间$\mathcal{H}$能实现示例集$D$上的所有对分，即$\Pi_{\mathcal{H}}(m)=2^m$，则称示例集$D$能被假设空间$\mathcal{H}$“打散”。
现在我们可以正式定义VC维了：
定义12.7 假设空间$\mathcal{H}$的VC维是能被$\mathcal{H}$打散的最大示例集的大小，即：
\[\text{VC}(\mathcal{H}) = \max \{ m : \Pi_{\mathcal{H}}(m) = 2^m \} \tag{3}\]个人注解：VC维的定义式上的底数2表示这个问题是二分类的问题。如果是$n$分类的问题，那么定义式中底数需要变为$n$。
$\text{VC}(\mathcal{H})=d$表明存在大小为$d$的示例集能被假设空间$\mathcal{H}$打散。注意：这并不意味着所有大小为$d$的示例集都能被假设空间$\mathcal{H}$打散。VC维的定义与数据分布$\mathcal{D}$无关！因此，在数据分布未知时仍能计算出假设空间$\mathcal{H}$的VC维。
通常这样来计算$\mathcal{H}$的VC维：若存在大小为$d$的示例集能被$\mathcal{H}$打散，但不存在任何大小为$d+1$的示例集能被$\mathcal{H}$打散，则$\mathcal{H}$的VC维是$d$。下面给出两个计算VC维的例子：
例12.1 实数域中的区间$[a,b]$：令$\mathcal{H}$表示实数域中所有闭区间构成的集合$\{ h_{[a,b]}: a,b \in \mathbb{R}, a\leqslant b \}$，$\mathcal{X} = \mathbb{R}$。对$x \in \mathcal{X}$，若$x \in [a,b]$，则$h_{[a,b]}(x)=+1$，否则$h_{[a,b]}(x)=-1$。令$x_1=0.5,x_2=1.5$，则假设空间$\mathcal{H}$中存在假设$\{ h_{[0,1]},h_{[0,2]},h_{[1,2]},h_{[2,3]} \}$将$\{ x_1,x_2 \}$打散，所以假设空间$\mathcal{H}$的VC维至少为2；对任意大小为3的示例集$\{x_3,x_4,x_5 \}$，不妨设$x_3 < x_4 < x_5$，则$\mathcal{H}$中不存在任何假设$h_{[a,b]}$能实现对分结果$\{ (x_3,+),(x_4,-),(x_5,+) \}$。于是，$\mathcal{H}$的VC维为2。
例12.2 二维实平面上的线性划分：令$\mathcal{H}$表示二维实平面上所有线性划分构成的集合，$\mathcal{H} = \mathbb{R}^2$。由图12.1可知，存在大小为3的示例集可被$\mathcal{H}$打散，但不存在大小为4的示例集可被$\mathcal{H}$打散。于是，二维实平面上所有线性划分构成的假设空间$\mathcal{H}$的VC维为3。
由定义12.7可知，VC维与增长函数有密切联系，引理12.2给出了二者之间的定量关系：
引理12.2 若假设空间$\mathcal{H}$的VC维为$d$，则对任意$m \in \mathbb{N}$有
\[\Pi_{\mathcal{H}}(m) \leqslant \sum_{i=0}^d \begin{pmatrix} m \\ i \end{pmatrix} \tag{4}\]亦称“Sauer引理”。
从引理12.2可计算出增长函数的上界：
推论12.2 若假设空间$\mathcal{H}$的VC维为$d$，则对任意整数$m \geqslant d$有
\[\Pi_{\mathcal{H}}(m)\leqslant \left( \frac{e \cdot m}{d} \right)^d \tag{5}\]$e$为自然常数。
根据推论12.2和定理12.2可得基于VC维的泛化误差界：
定理12.3 若假设空间$\mathcal{H}$的VC维为$d$，则对任意$m>d,0<\delta <1$和$h \in \mathcal{H}$有
\[P\left( E(h) - \hat{E}(h) \leqslant \sqrt{\frac{8d\ln \frac{2em}{d}+8\ln \frac{4}{\delta}}{m}} \right) \geqslant 1 - \delta \tag{6}\]由定理12.3可知，式(6)的泛化误差界只与样例数目$m$有关，收敛速率为$O\left( \frac{1}{\sqrt{m}} \right)$，与数据分布$\mathcal{D}$和样例集$D$无关。因此，基于VC维的泛化误差界是分布无关（distribution-free）、数据独立（data-independent）的。
令$h$表示学习算法$\mathfrak{L}$输出的假设，若$h$满足
\[\hat{E}(h) = \min_{h' \in \mathcal{H}} \hat{E} (h') \tag{7}\]则称$\mathfrak{L}$为满足经验风险最小化（Empirical Risk Minimization，简称ERM）原则的算法。我们有下面的定理：
定理12.4 任何VC维有限的假设空间$\mathcal{H}$都是（不可知）PAC可学习的。
2.对式(1)的解释
比如对于两个样本的二分类问题，一共有4种可能的标签组合$[[0,0],[0,1],[1,0],[1,1]]$，如果假设空间$\mathcal{H}_1$能赋予这两个样本两种标签组合$[[0,0],[1,1]]$，则$\Pi_{\mathcal{H}_1}(2)=2$。
3.式(4)的推导
依旧是只考虑2分类的情况。
由数学归纳法证明。当$m=1$，$d=0$或$d=1$时，定理成立。
现在解释下上面这句话，上面这句话是数学归纳法的起始条件。
首先考虑$m=1,d=0$的情况，由VC维的定义（即式(3)）可知，VC维（即$d$）是能让$\Pi_{\mathcal{H}}(m)=2^m$成立的最大$m$值，现在$d=0$，即最大$m$值就是0，也就是说比0大的$m$不能让$\Pi_{\mathcal{H}}(m)=2^m$成立，即有$\Pi_{\mathcal{H}}(1)<2$，又因为$\Pi_{\mathcal{H}}(m)$为整数，所以$\Pi_{\mathcal{H}}(1) \in [0,1]$，这便是式(4)的左边。现在来看式(4)的右边，$\sum_{i=0}^0 \begin{pmatrix} 1 \\ i \end{pmatrix} = 1$，因此式(4)成立。
然后考虑$m=1,d=1$的情况，因为$d=1$，所以有$\Pi_{\mathcal{H}}(1) = 2$，这便是式(4)的左边。对于式(4)的右边，$\sum_{i=0}^1 \begin{pmatrix} 1 \\ i \end{pmatrix} = 2$，因此式(4)成立。
然后利用数学归纳法，假设式(4)对$(m-1,d-1)$和$(m-1,d)$成立，推导出其对$(m,d)$也成立（个人没太理解这里的归纳法逻辑）。
令$D=\{ \mathbf{x}_1,\mathbf{x}_2,…,\mathbf{x}_m \}$，$D’ = \{ \mathbf{x}_1,\mathbf{x}_2,…,\mathbf{x}_{m-1} \}$，其中$D$比$D’$多一个样本$\mathbf{x}_m$，它们对应的假设空间可以表示为：
\[\mathcal{H}_{\mid D}=\{ ( h(\mathbf{x}_1),h(\mathbf{x}_2),...,h(\mathbf{x}_m) ) \mid h \in \mathcal{H} \}\] \[\mathcal{H}_{\mid D'}=\{ ( h(\mathbf{x}_1),h(\mathbf{x}_2),...,h(\mathbf{x}_{m-1}) ) \mid h \in \mathcal{H} \}\]任何假设$h \in \mathcal{H}$对$\mathbf{x}_m$的分类结果或为$+1$，或为$-1$，因此任何出现在$\mathcal{H}_{\mid D’}$中的串都会在$\mathcal{H}_{\mid D}$中出现一次或两次。令$\mathcal{H}_{D’ \mid D}$表示在$\mathcal{H}_{\mid D}$中出现两次的$\mathcal{H}_{\mid D’}$中串组成的集合，即：
\[\mathcal{H}_{D' \mid D} = \{ (y_1,y_2,...,y_{m-1}) \in \mathcal{H}_{\mid D'} \mid \exists h,h' \in \mathcal{H}, \\ (h(\mathbf{x}_i)=h'(\mathbf{x}_i)=y_i) \land (h(\mathbf{x}_m)\neq h'(\mathbf{x}_m)), 1 \leqslant i \leqslant m-1 \}\]举个例子，假设$m=3$：
\[\mathcal{H}_{\mid D} = \{ (+,-,-),(+,+,-),(+,+,+),(-,+,-),(-,-,+) \}\] \[\mathcal{H}_{\mid D'} = \{ (+,+),(+,-),(-,+),(-,-) \}\]其中串$(+,+)$在$\mathcal{H}_{\mid D}$中出现了两次$(+,+,+),(+,+,-)$，$\mathcal{H}_{\mid D’}$中的其他串$(+,-),(-,+),(-,-)$均只在$\mathcal{H}_{\mid D}$中出现了一次。
考虑到$\mathcal{H}_{D’ \mid D}$中的串在$\mathcal{H}_{\mid D}$中出现了两次，但在$\mathcal{H}_{\mid D’}$中仅出现了一次，有：
\[\lvert \mathcal{H}_{\mid D} \rvert = \lvert \mathcal{H}_{\mid D'} \rvert + \lvert \mathcal{H}_{D' \mid D} \rvert \tag{3.1}\]$D’$的大小为$m-1$，根据增长函数的定义，假设空间$\mathcal{H}$对包含$m-1$个样本的集合所能赋予的最大标记种类数为$\Pi_{\mathcal{H}}(m-1)$，因此$\lvert \mathcal{H}_{\mid D’} \rvert \leqslant \Pi_{\mathcal{H}}(m-1)$。又根据数学归纳法的前提假设，有：
\[\lvert \mathcal{H}_{\mid D'} \rvert \leqslant \Pi_{\mathcal{H}}(m-1) \leqslant \sum_{i=0}^d \begin{pmatrix} m-1 \\ i \end{pmatrix} \tag{3.2}\]由记号$\mathcal{H}_{\mid D’}$的定义可知，$\lvert \mathcal{H}_{\mid D’} \rvert \geqslant \lfloor \frac{\lvert \mathcal{H}_{\mid D} \rvert}{2} \rfloor$，又由于$\lvert \mathcal{H}_{\mid D’} \rvert$和$\lvert \mathcal{H}_{D’ \mid D} \rvert$均为整数，因此$\lvert \mathcal{H}_{D’ \mid D} \rvert \leqslant \lfloor \frac{\lvert \mathcal{H}_{\mid D} \rvert}{2} \rfloor$，由于样本集$D$的大小为$m$，根据增长函数的概念，有$\lvert \mathcal{H}_{D’ \mid D} \rvert \leqslant \lfloor \frac{\lvert \mathcal{H}_{\mid D} \rvert}{2} \rfloor \leqslant \Pi_{\mathcal{H}}(m-1)$。假设$Q$表示能被$\mathcal{H}_{D’ \mid D}$打散的集合，因为根据$\mathcal{H}_{D’ \mid D}$的定义，$H_D$必对元素$\mathbf{x}_m$给定了不一致的判定，因此$Q \cup \{ \mathbf{x}_m \}$必能被$\mathcal{H}_{\mid D}$打散，由前提假设$\mathcal{H}$的VC维为$d$，因此$\mathcal{H}_{D’ \mid D}$的VC维最大为$d-1$，综上有：
\[\lvert \mathcal{H}_{D' \mid D} \rvert \leqslant \Pi_{\mathcal{H}}(m-1) \leqslant \sum_{i=0}^{d-1} \begin{pmatrix} m-1 \\ i \end{pmatrix} \tag{3.3}\]由式(3.1)~(3.3)可得：
\[\begin{align} \lvert \mathcal{H}_{\mid D} \rvert &= \lvert \mathcal{H}_{\mid D'} \rvert + \lvert \mathcal{H}_{D' \mid D} \rvert \\&\leqslant \sum_{i=0}^d \begin{pmatrix} m-1 \\ i \end{pmatrix} + \sum_{i=0}^{d-1} \begin{pmatrix} m-1 \\ i \end{pmatrix} \\&= \sum_{i=0}^d \left( \begin{pmatrix} m-1 \\ i \end{pmatrix} + \begin{pmatrix} m-1 \\ i-1 \end{pmatrix} \right) \\&= \sum_{i=0}^d \begin{pmatrix} m \\ i \end{pmatrix} \end{align}\]$\begin{pmatrix} m-1 \\ -1 \end{pmatrix}=0$
由集合$D$的任意性，引理12.2得证。
最后一步依据组合公式，推导如下：
\[\begin{align} \begin{pmatrix} m-1 \\ i \end{pmatrix} + \begin{pmatrix} m-1 \\ i-1 \end{pmatrix} &= \frac{(m-1)!}{(m-1-i)!i!} + \frac{(m-1)!}{(m-1-i+1)!(i-1)!} \\&= \frac{(m-1)!(m-i)}{(m-i)(m-1-i)!i!} + \frac{(m-1)!i}{(m-i)!(i-1)!i} \\&= \frac{(m-1)!(m-i)+(m-1)!i}{(m-i)!i!} \\&= \frac{(m-1)!(m-i+i)}{(m-i)!i!} \\&= \frac{(m-1)!m}{(m-i)!i!} \\&= \frac{m!}{(m-i)!i!} \\&= \begin{pmatrix} m \\ i \end{pmatrix} \end{align}\]4.式(5)的推导
\[\begin{align} \Pi_{\mathcal{H}}(m) & \leqslant \sum_{i=0}^d \begin{pmatrix} m \\ i \end{pmatrix} \\& \leqslant \sum_{i=0}^d \begin{pmatrix} m \\ i \end{pmatrix} \left( \frac{m}{d} \right)^{d-i} \\&= \left( \frac{m}{d} \right)^d \sum_{i=0}^d \begin{pmatrix} m \\ i \end{pmatrix} \left( \frac{d}{m} \right)^i \\& \leqslant \left( \frac{m}{d} \right)^d \sum_{i=0}^m \begin{pmatrix} m \\ i \end{pmatrix} \left( \frac{d}{m} \right)^i \\&= \left( \frac{m}{d} \right)^d \left( 1+\frac{d}{m} \right)^m \\& \leqslant \left( \frac{e \cdot m}{d} \right)^d \end{align}\]前四步都是因为有$m \geqslant d$。
第五步是因为二项式定理：
\[(x+y)^n = \sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix} x^{n-k} y^k\]令$k=i,n=m,x=1,y=\frac{d}{m}$，得：
\[\left( \frac{m}{d} \right) ^d \sum_{i=0}^m \begin{pmatrix} m \\ i \end{pmatrix} \left( \frac{d}{m} \right)^i = \left( \frac{m}{d} \right) ^d \left( 1+\frac{d}{m} \right)^m\]第6步需要证明$\left( 1+\frac{d}{m} \right)^m \leqslant e^d$，因为$\left( 1+\frac{d}{m} \right)^m = \left( 1+\frac{d}{m} \right)^{\frac{m}{d}d}$，根据自然常数$e$的定义：
\[e = \lim_{n \to \infty} \left( 1+\frac{1}{n} \right)^n\]得到$\left( 1+\frac{d}{m} \right)^{\frac{m}{d}d} < e^d$，注意原书中这里用的是$\leqslant$，但因为$e$的定义是一个极限，所以应该用$<$更合理。
5.式(6)的推导
这里应该有个笔误，根据式(2)，$E(h)-\hat{E}(h)$应当被绝对值符号包裹。将式(5)代入式(2)得：
\[P \left( \lvert E(h)-\hat{E}(h) \rvert > \epsilon \right) \leqslant 4 \left( \frac{2em}{d} \right)^d \exp \left( -\frac{m\epsilon^2}{8} \right)\]令$4 \left( \frac{2em}{d} \right)^d \exp \left( -\frac{m\epsilon^2}{8} \right) = \delta$，两边取自然对数：
\[\ln \left( 4 \left( \frac{2em}{d} \right)^d \exp \left( -\frac{m\epsilon^2}{8} \right) \right) = \ln \delta\]展开左侧：
\[\ln 4 + d \ln \left( \frac{2em}{d} \right) - \frac{m\epsilon ^2}{8} = \ln \delta\]移项得：
\[\frac{m\epsilon^2}{8} = -\ln \delta + \ln 4 + d \ln \left( \frac{2em}{d} \right)\]最终可解得：
\[\epsilon = \sqrt{\frac{8d\ln \frac{2em}{d}+8\ln \frac{4}{\delta}}{m}}\]代入定理12.2，于是定理12.3得证。
6.定理12.4的证明
假设$\mathfrak{L}$为满足经验风险最小化原则的算法，$h$为学习算法$\mathfrak{L}$输出的假设。令$g$表示$\mathcal{H}$中具有最小泛化误差的假设，即：
\[E(g) = \min_{h \in \mathcal{H}} E(h) \tag{6.1}\]令：
\[\delta ' = \frac{\delta }{2} \tag{6.2}\] \[\sqrt{\frac{(\ln 2 / \delta ')}{2m}} = \frac{\epsilon}{2} \tag{6.3}\]由推论12.1可知：
\[\hat{E}(g)-\frac{\epsilon}{2} \leqslant E(g) \leqslant \hat{E}(g) + \frac{\epsilon}{2} \tag{6.4}\]至少以$1-\delta / 2$的概率成立，写成概率的形式即：
\[P \left( \lvert E(g)-\hat{E}(g) \rvert \leqslant \frac{\epsilon}{2} \right) \geqslant 1 - \delta / 2 \tag{6.5}\]即：
\[P\left( \left( E(g)-\hat{E}(g) \leqslant \frac{\epsilon}{2} \right) \land \left( E(g)-\hat{E}(g) \geqslant - \frac{\epsilon}{2} \right) \right) \geqslant 1 - \delta / 2 \tag{6.6}\]因此，有：
\[P\left( E(g)-\hat{E}(g) \leqslant \frac{\epsilon}{2} \right) \geqslant 1 - \delta / 2 \tag{6.7}\]且
\[P \left( E(g)-\hat{E}(g) \geqslant - \frac{\epsilon}{2} \right) \geqslant 1 - \delta / 2 \tag{6.8}\]成立。再令：
\[\sqrt{ \frac{8d\ln \frac{2em}{d}+8\ln \frac{4}{\delta '}}{m} } = \frac{\epsilon}{2} \tag{6.9}\]则由定理12.3可知：
\[P \left( E(h)-\hat{E}(h) \leqslant \frac{\epsilon}{2} \right) \geqslant 1 - \frac{\delta}{2} \tag{6.10}\]从而可知：
\[\begin{aligned} E(h)-E(g) &\leqslant \hat{E}(h) + \frac{\epsilon}{2} - \left( \hat{E}(g) - \frac{\epsilon}{2} \right) \\&= \hat{E}(h) - \hat{E}(g) + \epsilon \\& \leqslant \epsilon \end{aligned} \tag{6.11}\]以至少$1-\delta$的概率成立。由式(6.3)和式(6.9)可以解出$m$，再由$\mathcal{H}$的任意性可知定理12.4得证。
这部分的证明自己没太理解。
