过拟合(Overfitting)和正规化(Regularization)

Overfitting就是指Ein(在训练集上的错误率)变小，Eout(在整个数据集上的错误率)变大的过程

Underfitting是指Ein和Eout都变大的过程

从上边这个图中，虚线的左侧是underfitting，右侧是overfitting，发生overfitting的主要原因是：使用过于复杂的模型，数据噪音，有限的训练集

Occam's Razor：指的是对训练数据最简单的解释就是最好的，训练的模型可能越简单越好。

Sampling Bias：抽样是有偏差的，解决方案是：训练集合测试集来自于同一个部分。

Data Snooping：在实际操作时，如果做什么决定的时候尽量要避免用数据来做决定，要先把domain knoeledge变成feature放进去，而不是看完数据再放专业知识进去

正则化公示的推到过程：

发生overfitting的一个重要原因是假设过于复杂，而我们需要的是一个稍微简单的模型来学习，避免overfitting，例如，原来假设空间是10次曲线，很容易对数据过拟合，我们希望的是他变的简单一点比如w向量只保持三个分量，如下图

根据先前的知识，可知，H₂包含于H₁₀，可得如下公式：

即H₂ 是H₁₀的一部分，并且是将w_3... w₁₀都设置为0，此时我们得到的是一个多项式，在这个多项式中，只有3个系数，此时达到了简化的目的，避免了过拟合的发生。下图是一个转化简图，这个时候只需要找到最优的H₂即可。

通过上边的转化，我们已经达到了简化的目的，但是，上边只保留的了w₀+w₁*x+w₂*x²这样的形式，接着对H₂进行扩展使得，任意三项不为零即可。即约束条件变宽，

通过上述问题，最终的问题转化为求最优的H₂'即可。但是这个问题是一个NP-hard问题，因此需要做进一步的转化，转化的条件是，使得||W_q||²小于一个常数C即可。即

此时需要找到一个正规化的假设的权重W_REG：optimal solution from regularized hypothesis set H(c)

这个时候待解决的问题就转化为了求Ein的最小值，约束条件为每一个权重值都小于C

然后继续，转化为在下式的约束条件下，的最小值。

此时采用的是梯度下降法，如下图中_，约束W^TW<=C是一个圆形，即所取的w的取值都应该在圆内部以及圆的边上，而Wlin是要求的值，因此选择梯度法向量的反方向，即当梯度的反方向和w的方向平行时的W为所求的W_REG

即到最后的约束变为：

接下来，对于所有的lamad>0，对Ein取微分，通过计算，即可得到W_REG

还有另外一种方法，即对含有梯度的等式求积分，只要求积分的最小值即可，这个时候就是前文提到的正则化的公式。

巴特西