正则化的思想，引入的方式：想改善高阶假设空间overfitting的状况，从高阶退回低阶，即限制w的某些维度使之为零。

通过放宽限制和使用软约束（softer constraint)，问题改写成：

 

那如何求解右边的有约束最优化问题呢？

首先把Ein写成矩阵形式

 

如果没有约束，最优解就是linear regression的解，有约束后，w只能在红色的圆圈里面。

本来w应该沿着负梯度的方向移动，但是它不能移出圆圈，就是不能在 红线（normal）方向上移动。

因此将负梯度方法沿着normal做分解，w只能沿着绿色的箭头移动。什么时候w不能再移动了呢（就是不能再下降了），就是负梯度与normal平行的时候。那么这个时候的w就是问题的解。

最后问题演化成求w，使得

如果lamda已知，那么w可求得

 

另外来看，求解 可以等价于求解最小化问题

后面加上的这项就叫做正则项。

 

正则化和VC理论的联系

这里通过对最小化Ein的等价问题 Eaug 的求解，来保证VC bound.

 

Eaug的正则项可以看成是单个h的复杂度的惩罚

 

在有约束的假设空间H（C）中，w被限制了，这个空间的vc维要低于原始空间。

 

常用的正则项：L2和L1

L1正则的最优求解思路和L2是一样的，最优解会出现在角上，这样w在一些维度上为0，起到了特征选择的作用。

 

关于lamda的选择，和噪音大小有关。噪音大的话lamda也要大一些。但是通常我们并不知道噪音多大。。（下节讲到做validation）