大纲

Regularized Hypothesis Set

1 Regularization

• 我们做regularization的目的就是从高维的假设空间倒退回低维的假设空间

2 Stepping Back as Constraint

我们从高维到低维倒退，可以将高阶部分的权重置为0，这样相当于在原假设的基础上加上了约束

3 Regression with Looser Constraint

刚刚我们讨论的限制是H10高阶部分的权重w限制为0，这是比较苛刻的一种限制。下面，我们把这个限制条件变得更宽松一点，即令任意8个权重w为0，并不非要限定w3=w4=⋯=w10=0，这个Looser Constraint可以写成：

也就只是限定了w不为0的个数，并不限定必须是高阶的w。这种hypothesis记为H′2，称为sparse hypothesis set，它与H2和H10的关系为：

• more flexible than H2

• less risky than H10

对于这种sparse hypothesis set的约束问题求解，是一种NP难问题

4 Regression with Softer Constraint

我们进一步放松约束条件，也就是说，所有的权重w的平方和的大小不超过C，我们把这种hypothesis sets记为H(C)

• H(C)和H′2有交集，但不精确相等
• 当C≥0时，限定的范围越大，越宽松
  
  H(0)∈H(1.126)∈......∈H(1126)∈...∈H(∞)=H10

当C无限大的时候，即限定条件非常宽松，相当于没有加上任何限制，就与H10没有什么两样。H(C)称为regularized hypothesis set，这种形式的限定条件是可以进行求解的，我们把求解的满足限定条件的权重w记为wREG。接下来就要探讨如何求解wREG。

Weight Decay Regularization

1 Matrix Form of Regularized Regression Problem

2 The Lagrange Multiplier

下图描述了如何引入拉格朗日乘子

如上图所示，假设在空间中的一点w，根据梯度下降算法，w会朝着−∇Ein的方向移动（图中蓝色箭头指示的方向），在没有限定条件的情况下，w最终会取得最小值wlin，即“谷底”的位置。现在，加上限定条件，即w被限定在半径为C‾‾√的圆内，w距离原点的距离不能超过圆的半径，球如图中红色圆圈所示wTw=C。那么，这种情况下，w不能到达wlin的位置，最大只能位于圆上，沿着圆的切线方向移动（图中绿色箭头指示的方向）。与绿色向量垂直的向量（图中红色箭头指示的方向）是圆切线的法向量，即w的方向，w不能靠近红色箭头方向移动。那么随着迭代优化过程，只要−∇Ein与w点切线方向不垂直，那么根据向量知识，−∇Ein一定在w点切线方向上有不为零的分量，即w点会继续移动。只有当−∇Ein与绿色切线垂直，即与红色法向量平行的时候，−∇Ein在切线方向上没有不为零的分量了，也就表示这时w达到了最优解的位置。

随意我们可以导出最优解满足的性质

其中λ是拉格朗日乘子，乘以一个2N是为了方便公式推导

3 Augment Error

现在假设是线性回归的情况，我们可以把线性回归的∇Ein代入，则有

当λ≥0时，

进一步，导出最优解为

我们注意到ZTZ是半正定矩阵，加上一个正定矩阵，所以juzhen(ZTZ+λI)一定正定，而且可逆，所以解wREG一定存在。统计学上称Ridge Regression

对于一般的假设，∇Ein不是线性的，代入方程之后是一个非线性方程，wREG不易求解,我们可以从另一个角度看待这个方程

已知∇Ein是Ein对wREG的导数，而2λNwREG也可以看成是λNw2REG的导数。那么平行等式左边可以看成一个函数的导数，导数为零，即求该函数的最小值。也就是说，问题转换为最小化该函数：

我们把这个函数称之为Augment Error

4 Result

• λ过大过小都不合适，λ需要根据具体的数据进行交叉验证得到

• λ大的时候，对应限制条件C比较小，倾向于选择简单的模型

事实上，这种regularization不仅可以用在多项式的hypothesis中，还可以应用在logistic regression等其他hypothesis中，都可以达到防止过拟合的效果。

Regularization and VC Theory

1 Another View of Augmented Error

Augmented Error

其中λNw2表示的是单个Hypothesis的复杂度

VC Bound

其中Ω(H)表示的是整个假设空间的复杂度

Ω(w)∈Ω(H),所以Eaug(w)比Ein(w)更接近Eout(w)。所以Eaug(w)更能代表Eout(w)

2 Effective VC Dimension

根据VC Dimension理论，整个hypothesis set的dVC=d̃ +1，这是因为所有的w都考虑了，没有任何限制条件。而引入限定条件的dVC(H(C))=dEFF(H,A)，即有效的VC dimension。也就是说，dVC(H)比较大，因为它代表了整个hypothesis set，但是dEFF(H,A)比较小，因为由于regularized的影响，限定了w只取一小部分。其中A表示regularized算法。

General Regularizers

1 General Regularizers

• L2 Regularizers
• L1 Regularizers

2 The Optimal λ

从上图我们可以看出，噪声越大，所需要的λ也越大，但我们往往不知道噪声的大小，所以我们需要通过交叉验证选取最优的λ