过拟合与欠拟合

机器学习的主要挑战是我们的算法必须能够在先前未观测的新输入上表现良好，而不只是在训练集上表现良好。在先前未观测到的输入上表现良好的能力被称为泛化。

通常情况下，当我们训练机器学习模型时，我们可以使用某个训练集，在训练集上计算一些被称为训练误差（training error）的度量误差，目标是降低训练误差。目前为止，我们讨论的是一个简单的优化问题。机器学习和优化不同的地方在于，我们也希望泛化误差（generalization error）（也被称为测试误差（test error））很低。

以下是决定机器学习算法效果是否好的因素：

1. 降低训练误差。
2. 缩小训练误差和测试误差的差距。

这两个因素对应机器学习的两个主要挑战： 欠拟合（underfitting）和过拟合（overfitting）。欠拟合是指模型不能在训练集上获得足够低的误差。而过拟合是指训练误差和和测试误差之间的差距太大。

通过调整模型的容量（capacity），我们可以控制模型是否偏向于过拟合或者欠拟合。通俗地，模型的容量是指其拟合各种函数的能力。容量低的模型可能很难拟合训练集。容量高的模型可能会过拟合，因为记住了不适用于测试集的训练集性质。容量不足的模型不能解决复杂任务。容量高的模型能够解决复杂的任务，但是当其容量高于任务所需时，有可能会过拟合。

一种控制训练算法容量的方法是选择假设空间（hypothesis space），即学习算法可以选择为解决方案的函数集。例如，线性回归算法将关于其输入的所有线性函数作为假设空间。广义线性回归的假设空间包括多项式函数，而非仅有线性函数。这样做就增加了模型的容量。

模型规定了调整参数降低训练目标时，学习算法可以从哪些函数族中选择函数。这被称为模型的表示容量（representational capacity）。在很多情况下，从这些函数中挑选出最优函数是非常困难的优化问题。实际中，学习算法不会真的找到最优函数，而仅是找到一个可以大大降低训练误差的函数。额外的限制因素，比如优化算法的不完美，意味着学习算法的有效容量（effective capacity）可能小于模型族的表示容量。

许多早期的学者提出一个简约原则，现在广泛被称为奥卡姆剃刀（Occam’srazor）（c. 1287-1387）。该原则指出，在同样能够解释已知观测现象的假设中，我们应该挑选‘‘最简单’’ 的那一个。

我们必须记住虽然更简单的函数更可能泛化（训练误差和测试误差的差距小），但我们仍然需要选择一个充分复杂的假设以达到低的训练误差。通常，当模型容量上升时，训练误差会下降，直到其渐近最小可能误差（假设误差度量有最小值）。通常，泛化误差是一个关于模型容量的U 形曲线函数。如下图所示：

正则化

正则化定义为‘‘对学习算法的修改——旨在减少泛化误
差而不是训练误差’’。正则化一个学习函数$f(x;\theta)$ 的模型，我们可以给代价函数添加被称为正则化项（regularizer）的惩罚。从而防止过拟合。
正则化方式：

1. 参数范数惩罚：
   
   1. $L^2$参数正则化：$\Omega(\theta)=\frac{1}{2}|| w||^2_2$
   2. $L^1$参数正则化： Ω(θ)=||w||@H_608_502@1=∑i|w1| $\mathrm{\Omega }(\theta )=||w|{|}_1=\underset{i}{\sum }|w_1|$$\Omega(\theta)=|| w ||_1 = \sum\limits_{i}|w_1|$.
2. 作为约束的范数惩罚：拉格朗日函数、KKT
3. 噪声鲁棒性
4. 稀疏表示
5. Bagging
6. Dropout

正则化与欠约束问题

在某些情况下，为了正确定义机器学习问题，正则化是必要的。机器学习中许多线性模型，包括线性回归和PCA，都依赖于对矩阵$X^⊤X$求逆。只要$X^⊤X$ 是奇异的，这些方法就会失效。当数据生成分布在一些方向上确实没有差异时，或因为例子较少（即相对输入特征的维数来说）而在一些方向上没有观察到方差时，这个矩阵就是奇异的。在这种情况下，正则化的许多形式对应求逆$X^⊤X+\alpha I$。这个正则化矩阵可以保证是可逆的。

例如，对于欠定线性方程，伪逆X+ 的一个定义：
X+=limα↘0@H_502_1003@(X⊤X+αI)−1X⊤. $X^{+}=li{m}_{\alpha \searrow 0}(X^{\top }X+\alpha I{)}^{-1}{X}^{\top }.$ 我们可以将伪逆解释为使用正则化来稳定欠定问题。