本节课主要讲述正则化。

既然我们说高复杂度的函数和低复杂度的函数是包含的关系，那我们通过'step back'的方式退回去就好了。

那么怎么样退回去呢？

其实，高次多项式和低次多项式的差别就在于w。只要我们限制了有多少个为零的w，就可以间接控制多项式的复杂度。转化成最优化的视角，就是找一些w使得E_in最小。

现在又把问题转换成找不为零的w有多少个，叫做sparse hypothesis set。这个set会比2次多项式宽松，但是又比10次多项式紧。

因为这个问题是NP hard无法解决的。所以要把问题转换成计算w²，并且给定一个上限C：

这个和上面的H2`是有一些重叠的地方的。但是也会有w很小但是不是零的情况。H(C)叫做regularized hypothesis set。怎么解这个问题呢？

将这个方程式矩阵化：

因为w^Tw≤C，所以我们要找的w是一个半径为根号C，圆心是原点的球。

解决这个方程的优化问题需要联系之前学过的梯度下降的方法，假设一个球想要滚到谷底，球滚的方向就必须是与梯度相反的方向。（图中蓝色的方向）

蓝色椭圆的中心点（w_lin）就是整个椭圆的“谷底”，但是我们的目标不是滚到“谷底”，我们是有限制条件的（图中红色的球），我们的w的最佳解必须要在红色面积内。

判断是否是最佳解得方式就是看一下还能不能继续滚，并且还不能脱离红色球的限制。球滚得方向一定不能是红色的向量，红色的normal向量是球面的法向量，是垂直于球面的，如果照着这个方向滚的话，就脱离的红色区域的限制。看起来我们只能沿着红色向量的垂直的向量，也就是绿色向量的方向滚。这个绿色的方向既可以靠近中心一点，又不会脱离红色区域。

当梯度的反方向（蓝色向量）和球面的法向量（红色向量）是平行的时候，绿色的向量就没有办法继续靠近椭圆中心了。此时就达到了最优解。

解上图的方程，找一个w_REG和λ使公式成立，也就是两个向量平行。

假设我们知道λ是多少，解方程就简化成解：

或者从augmented error的角度来看：

看来唯一的参数λ的选择变得非常的重要：

λ后面是一个惩罚项，这种正则化的方法可以把w变小。

Augmented error把VC理论中的惩罚项应用到了实践当中去，一个是单一hypothesis的复杂度，而另一个是整个hypothesis set的复杂度：

如果两边的惩罚项差不多的话，那么E_aug和E_out也就差不多，我们就可以用E_aug来替代E_out。

或者，从另一个角度来看：

并不是所有的w都真的属于备选项，只有在“谷底”附近的w，也就是比较短的w才会真正被考虑。所以d_vc也没有那么大。

那么一个好的regularizer有什么特性呢？肯定不会直接告诉我们target function是什么，但是我们希望它能至少告诉我们一个正确的方向。

1. 如果我们碰巧知道目标函数的一些已知的特性，我们就可以把这些特性当做regularizer。

2. regularizer最好能帮我们选出比较平滑比较简单的hypothesis，例如L1 regularizer。（因为有噪声的数据通常不是那么平滑）

3. 方便我们优化的regularizer，例如weight-decay(L2) regularizer.

4. 如果找不到一个好的regularizer，通过λ=0调节一下就好了。

L1会趋向于产生少量的特征，而其他的特征都是0，而L2会选择更多的特征，这些特征都会接近于0。Lasso在特征选择时候非常有用，而Ridge就只是一种规则化而已。

λ的优化问题：

如果数据中噪声比较大的时候，要选更大的λ。

如果数据中不知道噪声有多少的时候，做cross-validation。

总结：