Model Complexity in Machine Learning.
本文目录：
- 霍夫丁不等式
- VC维
- 模型复杂度
- 概率近似正确
1. 霍夫丁不等式
假设给定的样本集是从总样本集中随机抽样得到的有限集合，下面从分类的角度出发推导霍夫丁不等式。
记总样本集服从分布$P$，存在一个能将总样本集中的所有样本完全正确分类的函数$f$；记观测到的样本集是\(\{x_1,x_2,...,x_N\}\)，模型的假设空间为$H$，从中选择一个假设函数$h$； 定义该假设函数对于观测到的样本的误差为样本内误差(in-sample error)，该误差可以计算得到：
- in-sample error：\(E_{in}(h)=\sum_{n=1}^{N} {[h(x_n)≠y_n]}\)
定义该假设函数对于总样本的误差为样本外误差(out-of-sample error)，该误差不可计算：
- out-of-sample error：\(E_{out}(h)=ε_{x \text{~} P}[h(x)≠f(x)]\)
⚪ 单个假设
霍夫丁不等式(Hoeffding’s inequality)描述了这两个误差的关系：
\[P[| E_{in}(h)-E_{out}(h) | > ε] ≤ 2exp(-2ε^2N)\]⚪ 有限假设空间
若模型的假设空间$H$中存在有限的$M$个假设函数$h$，则对应的霍夫丁不等式：
\[P[\exists h \in H \quad s.t. \quad | E_{in}(h)-E_{out}(h) | > ε] \\ ≤ \sum_{i=1}^{M} {P[| E_{in}(h_i)-E_{out}(h_i) | > ε]} ≤ 2Mexp(-2ε^2N)\]⚪ 无限假设空间
若模型的假设空间$H$存在无穷多个假设函数$h$，事实上许多假设函数对于有限个样本点来说是等价的，比如只对一个样本点进行二分类，尽管可能有无穷多个假设函数，但最终的结果只有两种。
引入成长函数（growth function）$m_H$，则对应的霍夫丁不等式：
\[P[\exists h \in H \quad s.t. \quad | E_{in}(h)-E_{out}(h) | > ε] ≤ 4m_H(2N)exp(-\frac{1}{8}ε^2N)\]引入break point $k$，是指对于$k$个样本，该假设空间内的所有假设都不能得到所有分类的结果（$2^k$种）。
- 比如二维空间的感知机，对于两个样本点可以得到所有的$4$种情况，但是对于三个样本点不能实现所有的$8$种情况（考虑三个样本点共线时，如下图所示），则对于二维空间的感知机，$k=3$。
- 当$k$是一个模型的break point时，所有大于$k$的正整数也是该模型的break point。
若假设空间$H$中存在break point $k$，则成长函数$m_H$存在一个上界$B(N,k)$:
\[m_H ≤ B(N,k) ≤ \sum_{i=0}^{k-1} {C_N^i} ≤ N^{k-1}\]上式右端是$N$的多项式函数，即成长函数$m_H$的增长不会超过多项式级别。
2. VC维
VC维（Vapnik-Chervonenkis Dimension）的定义是模型最小的break point减一：
\[d_{VC} = min(k)-1\]$VC$维表示当给定不超过该数量的样本点时，任何一种可能的标记情况都可以找到假设空间中的一个假设进行正确的分类。
当引入$VC$维，霍夫丁不等式可以写作：
\[P[\exists h \in H \quad s.t. \quad | E_{in}(h)-E_{out}(h) | > ε] ≤ 4(2N)^{d_{VC}}exp(-\frac{1}{8}ε^2N)\]上式右端也称为Vapnik-Chervonenkis(VC) bound。
$VC$ $Bound$是比较宽松的，而如何收紧它却不是那么容易。但$VC$ $Bound$基本上对所有模型的宽松程度是基本一致的，不同模型之间还是可以横向比较。
$VC$维表示模型的能力或自由度，通常可以用模型中可自由调节的参数个数近似。
常用模型的$VC$维:
- $d$维的感知机：$d_{VC}=d$
- 在$d$维空间，当数据点分布在半径为$R$的超球体内时，间距为$ρ$的支持向量机的$VC$维满足：$d_{VC}(A_ρ) ≤ min(\frac{R^2}{ρ^2},d)+1$
- 神经元数量为$V$、参数数量为$D$的神经网络：$d_{VC}=VD$
3. 模型复杂度
根据引入$VC$维的霍夫丁不等式：
\[P[\exists h \in H \quad s.t. \quad | E_{in}(h)-E_{out}(h) | > ε] ≤ 4(2N)^{d_{VC}}exp(-\frac{1}{8}ε^2N)\]若记上式右端的概率值为$δ$，则误差$E_{in}$和$E_{out}$超过$ε$的概率不超过$δ$，或者说以大于$1-δ$的概率认为：
\[| E_{in}-E_{out} | ≤ ε = \sqrt{\frac{8}{N}ln(\frac{4(2N)^{d_{VC}}}{δ})}\]上式右端表示模型误差的上界，称为模型复杂度（model complexity），记为$Ω(N,H,δ)$。
- 样本总数$N$越大，模型复杂度越小；
- 模型的假设空间$H$越大（$d_{VC}$越大），模型复杂度越大；
- 所允许超过误差的概率$δ$越大，模型复杂度越小。
下面给出误差$E_{in}$、$E_{out}$和模型复杂度$Ω$随$VC$维的变化：
- $VC$维越大，模型越复杂，$E_{in}$越小，模型复杂度$Ω$越大；
- $VC$维越小，模型越简单，$E_{in}$越大，模型复杂度$Ω$越小；
- 随着$VC$维增大，$E_{out}$先减小后增大，最好的$d_{VC}^*$在中间。
- 当$VC$维太小时，$E_{in}$、$E_{out}$都很大，模型对训练样本的拟合度太差，称为欠拟合（underfitting）；
- 当$VC$维太大时，$E_{in}$很小、$E_{out}$很大，对训练样本拟合过分好，称为过拟合（overfitting）；
样本复杂度（Sample Complexity）定义了选定$d_{VC}$，样本数据$N$选择多少合适。
理论上$N≈10000d_{VC}$，由于$VC$ $Bound$是比较宽松的，在实践中取$N≈10d_{VC}$。
4. 概率近似正确
由霍夫丁不等式可以观察到：
\[P[\exists h \in H \quad s.t. \quad | E_{in}(h)-E_{out}(h) | > ε] ≤ 4m_H(2N)exp(-\frac{1}{8}ε^2N)\]当样本数量$N$很大时，上式的概率上界接近$0$，误差$E_{in}$和$E_{out}$相差不会很大，可近似认为$E_{in}=E_{out}$，这个结论叫做概率近似正确（probably approximately correct，PAC）。
则可以训练一个算法，从模型的假设空间$H$中选择一个具体的模型使$E_{in}≈0$，则可以认为$E_{out}≈0$。
