过拟合与欠拟合（under & over）

欠拟合（underfitting）: \(E_{\text {in}}\)较高，\(E_{\text {out}}\)也较高。

过拟合（overfitting）: \(E_{\text {in}}\)较低，\(E_{\text {out}}\)却较高。（例如数据中有噪声，却使用了高次多项式非线性转换，便会出现过拟合）

常见的过拟合原因有：数据量（data size）太少，随机噪声（stochastic noise）太大，目标函数（deterministic noise）太复杂，dvc过高（excessive power）。

示例如下：

一般而言欠拟合很好处理。过拟合却很难解决，比较实用的解决方案有以下五个：

• start from simple model（从简单的模型开始）
• data cleaning/pruning（数据清理和裁剪）
• data hinting（数据提示）
• regularization（正则化）
• validation（验证）

其中数据清理实际上就是纠正数据错误，而数据裁剪便是删除无用或冗余样本。而数据提示则是数据构造（加入构造样本），以图像处理为例：可以通过移动或旋转（shifting/rotating）已知图像构造虚拟样本数据。

下面介绍两个实用的工具正则化与验证。

正则化（Regularization)

正则化的本质是减少无用项的比重，从而减小 $d_{\mathbf{vc}} $ ，进而抑制过拟合。最理想的状态是通过学习使得某些不重要的项的系数为0，但是这是一种 NP-hard 问题，所以降低要求至减小比重。

\[\begin{array} { r l } \min _ { \mathbf { w } \in \mathbb { R } ^ { Q + 1 } } & E _ { \text {in } } ( \mathbf { w } ) = \frac { 1 } { N } \underbrace { \sum _ { n = 1 } ^ { N } \left( \mathbf { w } ^ { T } \mathbf { z } _ { n } - y _ { n } \right) ^ { 2 } } _ { ( \mathbf { Z } \mathbf { w } - \mathbf { y } ) ^ { T } ( \mathbf { Z } \mathbf { w } - \mathbf { y } ) } \\ \text { s.t. } & \underbrace { \sum _ { q = 0 } ^ { Q } w _ { q } ^ { 2 } } _ { \mathbf { w } ^ { T } \mathbf { w } } \leq C \end{array} \]

这个限制实际上是将比重系数限制在半径为 \(\sqrt{C}\) 的球体内。所以优化结果转换为 regularized hypothesis \(\mathbf{w}_{REG}\)（optimal solution from regularized hypothesis set \(H(C)\)）。

可见这是一个有条件最优化问题，经典的解法是使用拉格朗日乘数。即找一个拉个朗日乘数（Lagrange multiplier）\(\lambda > 0\) 和 \(\mathbf { w } _ { \mathrm { REG } }\) 使得：

\[\nabla E _ { \text {in } } \left( \mathbf { w } _ { \mathrm { REG } } \right) + \frac { 2 \lambda } { N } \left| \mathbf { w } _ { \mathrm { REG } } \right| = \mathbf { 0 } \]

图解拉格朗日乘数（Lagrange Multiplier）法

当现在有一个球需要向负梯度方向（谷底）滚，但是呢现在有一个限制条件，不能超出半径为 \(\sqrt{C}\) 的球，所以在球的最佳位置是满足条件且不能往下滚，现在有两种状态一种是谷底在这个限制的球内，那么无所谓。如果在球外呢，便需要找出一个球边界上的点，并且该点的负梯度方向为球切面的法向量，这样的话便会满足条件且无法滚动（会导致出界）。

根据上述拉格朗日乘数方程，可以写出：

\[\nabla E _ { \mathrm { in } } \left( \mathbf { w } _ { \mathrm { REG } } \right) + \frac { 2 \lambda } { N } \mathbf { w } _ { \mathrm { REG } } = \mathbf { 0 }\\ \frac { 2 } { N } \left( \mathrm { Z } ^ { T } \mathrm { ZW } _ { \mathrm { REG } } - \mathrm { Z } ^ { T } \mathbf { y } \right) + \frac { 2 \lambda } { N } { \mathbf { W } _ { \mathrm { REG } } } = \mathbf { 0 } \]

可以看出这是根据 \(\mathbf { w } _ { \mathrm { REG }}\) 的 一个一元一次线性方程，所以可以解得：

\[\mathbf { w } _ { \mathrm { REG } } \leftarrow \left( \mathrm { Z } ^ { T } \mathrm { Z } + \lambda \mathrm { I } \right) ^ { - 1 } \mathrm { Z } ^ { T } \mathbf { y } \]

这个在统计上叫做岭回归（ridge regression）。其中\(\mathrm { Z } ^ { T } \mathrm { Z }\)是正半定的，\(\lambda \mathrm { I }\)是正定的，所以两者相加一定有逆。

实际上上述拉格朗日乘数方程，等同于下面这个优化问题

\[E _ { \text {in } } ( \mathbf { w } ) + \underbrace{\frac { \lambda } { N } \overbrace { \mathbf { w } ^ { T } \mathbf { w } }^{\text{regularier}}}_{\text{augmented error } E _ { \text {aug } }} \]

所以将有约束的最优化问题转换为用扩大误差的正则化（regularization with augmented error instead of constrained \(E_{\text{in}}\)）

\[\mathbf { w } _ { \mathrm { REG }} \leftarrow \mathop { \text{argmin} }_{\mathbf{w}} E _ { \text {aug } } \text{ for given }\lambda > 0 \text { or } \lambda = 0 \]

即最小化无约束 \(E _ { \text {aug } }\) 可以有效的最小化有约束的\(E_{\text{in}}\) （minimizing unconstrained \(E _ { \text {aug } }\) effectively minimizes some C-constrained \(E_{\text{in}}\).）

因为该正则化方法有效的减小了无用项权重系数的大小，所以 \(+ \frac { \lambda } { N } \mathbf { w } ^ { T } \mathbf { w }\) 又叫做权重衰减正则化（weight-decay regularization）。

知识拓展：勒让德多项式（Legendre polynomials）

\[\min _ { \mathbf { w } \in \mathbb { R } ^ { Q + 1 } } \frac { 1 } { N } \sum _ { n = 0 } ^ { N } \left( \mathbf { w } ^ { T } \mathbf { \Phi } \left( x _ { n } \right) - y _ { n } \right) ^ { 2 } + \frac { \lambda } { N } \sum _ { q = 0 } ^ { Q } w _ { q } ^ { 2 } \]

单纯的多项式转换（naïve polynomial transform）：

\[\Phi ( x ) = \left( 1 , x , x ^ { 2 } , \ldots , x ^ { Q } \right) \]

当\(x _ { n } \in [ - 1 , + 1 ] , x _ { n } ^ { q }\) 非常小，需要很大的 \(\mathbf{w}_q\)，但是正则化项却限制了这一行为。这时便提出另一种多项式转换： 归一化多项式转换（normalized polynomial transform）：

\[\Phi ( x ) = \left( 1 , L _ { 1 } ( x ) , L _ { 2 } ( x ) , \ldots , L _ { Q } ( x ) \right) \]

这叫 正交基函数 ‘orthonormal basis functions’，该多项式叫做勒让德多项式（Legendre polynomials）。

与 VC 理论的关系

minimizing \(E _ { \text {aug } }\) 的三个不同的理解

• indirectly getting VC guarantee without confining to \(H(C)\).
  即在不设置限制条件的状态下，间接的获得保证VC的安全性。
• (heuristically) operating with \(E _ { \text {aug } }\) ( a better proxy of \(E _ { \text {out} }\) than \(E _ { \text {in} }\) ); (technically) enjoying flexibility of whole \(H\).
  \(E _ { \text {aug } }\) 相比 \(E _ { \text {in} }\) 可以更好的代表 \(E _ { \text {out} }\)，实际上就是用权重惩罚项 \(\Omega(\mathbf{w})\) 代替模型复杂度惩罚项 \(\Omega(H)\)，并且可以在全部的 \(H\) 中找寻有用的 hypothesis。
• \(d_{\mathbf{vc}}(H)\) large, while \(d_{\mathbf{EFF}}(H;\underbrace{\mathcal{A}}_{\min E _ { \text {aug } }}) = d_{\mathbf{vc}}(H(C))\) small if A regularized
  显而易见的是当使用 regularization 后，会降低模型的复杂度，即降低 \(d_{\mathbf{vc}}(H)\)。

常用的正则化（General Regularizers）

正则化的目标是限制目标函数的 ‘ 学习方向 ’（constraint in the ‘direction’ of target function）。

正则化有三个特性：

• target-dependent：some properties of target（应该目标函数的属性或者范围有关）
• plausible：direction towards smoother or simpler （应该是合理的，让算法筛选出比较光滑或简单的hypothesis）
• friendly: easy to optimize （比较友好，更容易优化）

值得注意的是正则项中的的 \(\lambda\) 可以控制正则项的权重或者影响，如果感觉正则项有不好的影响的话，可以尝试调低\(\lambda\) 。

L1范数正则化（L1 Regularizer）

示意图如下：

其惩罚项表达式如下：

\[\Omega ( \mathbf { w } ) = \sum _ { q = 0 } ^ { Q } \left| w _ { q } \right| = \| \mathbf { w } \| _ { 1 } \]

可见这是一个凸函数（convex,），但不是随处可微的（not differentiable everywhere，比如顶点上）。值得注意的是其解的稀疏性（sparsity in solution），这是因为最优解常常在顶点上，也就是说某些项为零。所以说L1范数正则化常常用于稀疏解（sparse solution）。

L2范数正则化（L2 Regularizer）

示意图如下：

其惩罚项表达式如下：

\[\Omega ( \mathbf { w } ) = \sum _ { q = 0 } ^ { Q } w _ { q } ^ { 2 } = \| \mathbf { w } \| _ { 2 } ^ { 2 } \]

因为该正则化方法有效的减小了无用项权重系数的大小，所以 L2 范数正则化又叫做权重衰减正则化（weight-decay regularization）。

最佳（Optimal）\(\lambda\)

在随机噪声（stochastic noise）下的\(\lambda\) 调节曲线图：

在确定噪声（deterministic noise）下的\(\lambda\) 调节曲线图：

可见噪声越大，应当使用更多的正则化。但是噪声是不知道，如何进行选择呢，这便用到了下一节课的交叉验证进行模型选择了。

验证（Validation）

模型选择（Model Selection）

验证实际上就是为了解决模型选择的问题（Model Selection Problem），当然在可行性分析时有证明说，当 \(N\) （数据量）足够多时，机器学习可以保证\(E_{\text {in}} \approx E_{\text {out}}, E_{\text {in}} \approx 0\)，即 \(E_{\text {out}} \approx 0\) 所以说呢，只需要保证最佳的 \(E_{\text {in}}\) 即可。但是这有一个前提那就是 \(N\) （数据量）足够多，实际生活中真的能保证数据足够多吗，答案是并不能，而且很有可能会为此付出过拟合的代价。

一个简答的方法便是针对测试集进行测试，验证模型的准确率。即使用 \(\mathcal{D} _ { \text {test } }\) 去求取 \(E _ { \text {test } }\)，从而选择最优的模型。

\[m ^ { * } = \underset { 1 \leq m \leq M } { \operatorname { argmin } } \left( E _ { m } = E _ { \text {test } } \left( \mathcal { A } _ { m } ( \mathcal { D } ) \right) \right) \]

并且可以保证泛化性（generalization guarantee），可以通过有限海弗丁不等式 （finite-bin Hoeffding）求得:

\[E _ { \mathrm { out } } \left( g _ { m ^ { * } } \right) \leq E _ { \mathrm { test } } \left( g _ { m ^ { * } } \right) + O ( \sqrt { \frac { \log M } { N _ { \mathrm { test } } } } ) \]

但是真的可以使用 \(E _ { \text {test } }\) 来测试，答案仍然是否定的，因为 \(\mathcal{D} _ { \text {test } }\) 是无法获得的（infeasible & cheating）。

所以这里提出一种想法 通过验证集（validation set） \(\mathcal { D }_{\text{val}} \in \mathcal { D }，\mathcal { D } _ { \mathrm { val } } \stackrel { \text { iid } } { \sim } P ( \mathbf { x } , y ),\text{select K examples from } \mathcal{D} \text { at random}\)，计算$ E_{\text{val}}$，来筛选模型，但是 \(\mathcal { D }_{\text{val}}\) 不可被\(\mathcal { A }_{\text{m}}\)（学习算法）用于模型训练，也就是说\(\mathcal { D }_{\text{val}} \cap \mathcal { D }_{\text{train}} = \empty , \mathcal { D }_{\text{val}} \cup \mathcal { D }_{\text{train}} = \mathcal { D }\)。这样一来保证了验证数据不可知（干净，clean)，二来验证数据是可以获得的，是一种合法的欺骗（legal cheating）。

基本的结构如下所示：

\[\begin{array}{ c c c c c } E_{\text {in}}(h) &&&& E_{\text {val}}(h)\\ \uparrow &&&& \uparrow \\ \underbrace { \mathcal { D } } _ { \text {size } N } &\rightarrow &\underbrace { \mathcal { D } _ { \text {train } } } _ { \text {size } N - K } &\cup &\underbrace { \mathcal { D } _ { \text {val } } } _ { \text {size } K }\\ \downarrow && \downarrow && \\ g _ { m } = \mathcal { A } _ { m } ( \mathcal { D } ) &&g _ { m } ^ { - } = \mathcal { A } _ { m } \left( \mathcal { D } _ { \text {train } } \right)&& \end{array} \]

最终使用海弗丁不等式可以保证：

\[E _ { \mathrm { out } } \left( g _ { m } ^ { - } \right) \leq E _ { \mathrm { val } } \left( g _ { m } ^ { - } \right) + O ( \sqrt { \frac { \log M } { K } } ) \]

从 \(N - K\) 到 \(N\) 的启发式增益（heuristic gain）变化为：

\[E _ { \text {out } } ( \underbrace { g _ { m ^ { * } } } _ { A _ { m ^ { * } } ( \mathcal { D } ) } ) \leq E _ { \text {out } } ( \underbrace { g _ { m ^ { * } } ^ { - } } _ { A _ { m ^ { * } } \left( \mathcal { D } _ { \text {tann } } \right) } ) \]

进一步可以得出以下关系：

\[E _ { \mathrm { out } } \left( g _ { m ^ { * } } \right) \leq E _ { \mathrm { out } } \left( g _ { m ^ { * } } ^ { - } \right) \leq E _ { \mathrm { val } } \left( g _ { m ^ { * } } ^ { - } \right) + O ( \sqrt { \frac { \log M } { K } } ) \]

即训练数据越多，学习算法选择的 \(g\) （best hypothesis）便越好。所以实用的验证使用流图如下，在获得 \(g _ { m ^ { * } } ^ { - }\) 后再求取\(g _ { m ^ { * } }\)，一般来说会获得更优的效果：

那在实际中K应当如何选择呢，下面以在 \(\mathcal { H } _ { \boldsymbol { \Phi } _ { 5 } }\) 和 \(\mathcal { H } _ { \boldsymbol { \Phi } _ { 10 } }\) 选择最优模型为例，变化曲线图如下：

其中 \(g_{\hat m}\) 指的是使用 \(E_{\text{in}}\) 选择最优模型，\(g _ { m ^ { * } } ^ { - }\) 指的是使用 \(E_{\text{val}}\) 选择和使用 \(\mathcal{D}_{\text{train}}\) 训练的最优模型，\(g _ { m ^ { * } }\) 指的是使用 \(E_{\text{val}}\) 选择和使用 \(\mathcal{D}\) 训练的最优模型，而 optimal 指的是使用 \(E_{\text{test}}\) 选择的最优模型输出的 \(E_{\text{out}}\)（不可能达到的最优值）。

可见 \(E_{\text{out}}(g _ { m ^ { * } } ^ { - }) > E_{\text{out}}(g _ { m ^ { * } } )\)，证明了使用验证集进行模型选择的可行性。

同时随着验证集大小 \(K\) 的增加， \(g _ { m ^ { * } } ^ { - }\) 的 \(E_{\text{out}}\) 不断增加，这是由于验证集越大，训练集越小，训练出来的模型精度越差（\(g\) 与 \(g^-\)的差距越大）。而验证集越小，训练集越大，在全局数据下模型精度越高（\(g\) 与 \(g^-\)的差距越小）。这便是矛盾的地方，因为当验证集越大时，\(g^-\)的 \(E_{\text{out}}\) 与 \(E_{\text{val}}\) 更相近，即 \(E_{\text{val}}\) 更能代表 \(E_{\text{out}}\) 但不能代表 \(g\) 的 \(E_{\text{out}}\)。

\[E _ { \text {out } } ( g ) \quad \mathop{\approx}_{(\text{small }K)} \quad E _ { \text {out } } \left( g ^ { - } \right) \quad \mathop{\approx}_{(\text{big }K)} \quad E _ { \text {val } } \left( g ^ { - } \right) \]

实践经验（practical rule of thumb）选择：\(K = \frac{N}{5}\)。

Leave-One-Out ( LOO ) Cross Validation

那怎么才能使得\(E _ { \text {val } }(g^{-}) \approx E _ { \mathrm { out } } ( g )\)呢，这便是LOO交叉验证的由来：

\[E _ { \text {loocv } } ( \mathcal { H } , \mathcal { A } ) = \frac { 1 } { N } \sum _ { n = 1 } ^ { N } e _ { n } = \frac { 1 } { N } \sum _ { n = 1 } ^ { N } \operatorname { err } \left( g _ { n } ^ { - } \left( \mathbf { x } _ { n } \right) , y _ { n } \right) \mathop{\approx}^{\text{hope}} E_{\text{out}}(g) \]

实际上就是每次取出一个样本作为验证集，使用剩下的 \(N-1\) 个作为训练集，计算 \(E _ { \text {val }}\)，最后针对全部的样本计算平均值。下面进行证明（\(\mathop{\mathcal { E }} _ { \mathcal { D } }\) 指的是在数据集\(\mathcal{D}\)上取结果的平均）：

\[\begin{aligned} \mathop{\mathcal { E }} _ { \mathcal { D } } E _ { \operatorname { loocv } } ( \mathcal { H } , \mathcal { A } ) &= \mathop{\mathcal { E }} _ { \mathcal { D } } \frac { 1 } { \mathcal { N } } \sum _ { n = 1 } ^ { N } e _ { n } = \frac { 1 } { N } \sum _ { n = 1 } ^ { N } \mathop{\mathcal { E }} _ { \mathcal { D } } e _ { n } \rightarrow 由于独立同分布（iid）所以 \mathop{\mathcal { E }} _ { \mathcal { D } }可拆为\mathop{\mathcal { E }} _ { \mathcal { D_n } }\mathop{\mathcal { E }} _ { \mathcal { (\mathbf{x}_n, y_n) } } \\ &= \frac { 1 } { N } \sum _ { n = 1 } ^ { N } \mathop{\mathcal { E }} _ { \mathcal { D_n } } \underbrace{\mathop{\mathcal { E }} _ { \mathcal { (\mathbf{x}_n, y_n) } } \operatorname { err } \left( g _ { n } ^ { - } \left( \mathbf { x } _ { n } \right) , y _ { n } \right) } \\ & = \frac { 1 } { N } \sum _ { n = 1 } ^ { N } \mathop{\mathcal { E }} _ { \mathcal { D_n} } \quad \quad \quad E _ { \text {out } } \left( g _ { n } ^ { - } \right) \rightarrow 一个固定的g在各式各样的样本下的误差均值 \\ & = \frac { 1 } { N } \sum _ { n = 1 } ^ { N } \overline { E _ { \text {out } } } ( N - 1 ) = \overline { E _ { \text {out } } } ( N - 1 ) \end{aligned} \]

同时当 \(N\) 相当大时，\(\overline { E _ { \text {out} } } ( N - 1 ) \approx \overline { E _ { \text {out} } } ( N )\)，所以 \(E _ { \text {loocv } } ( \mathcal { H } , \mathcal { A } ) \approx E_{\text{out}}(g^{-})\) 又叫 \(E_{\text{out}}(g)\) 的无偏估计。

V折交叉验证 （V-Fold Cross Validation）

V折交叉验证（V-fold cross-validation）：将 \(\mathcal{D}\) 随机分为 V 块， 依次拿 V - 1 份进行训练 和 1 份进行测试。

\[E _ { \mathrm { cv } } ( \mathcal { H } , \mathcal { A } ) = \frac { 1 } { V } \sum _ { v = 1 } ^ { V } E _ { \mathrm { val } } ^ { ( v ) } \left( g _ { v } ^ { - } \right) \]

并依此找最优模型：

\[m ^ { * } = \underset { 1 \leq m \leq M } { \operatorname { argmin } } \left( E _ { m } = E _ { \mathrm { cv } } \left( \mathcal { H } _ { m } , \mathcal { A } _ { m } \right) \right) \]

实践经验（practical rule of thumb）选择：\(V = 5 \text{ or } 10\)。