Regularization

References

• Lecture: 张颢, https://www.bilibili.com/video/BV1ga4y157L5?p=8&vd_source=8a00dab0be94d29388f2286892ba8d50

1. Ridge Regression / Tikhonov Regularization

沿用 Note 4 的记号, 我们的目标是最小化:

$$\begin{array}{rl}\underset{f_X}{\min }& \frac{1}{n}\sum _{k=1}^{n}L(f_X(x_k),y_k)\\ \text{s.t.}& f_X(x)\in \mathcal{F}.\end{array}$$

经过一定的泛函等技巧, 并确定 MSE 为 loss 的具体形式, 以线性情况为例, 可以得到:

$$\begin{array}{rl}\underset{\theta }{\min }& \frac{1}{n}\sum _{k=1}^n(y_k-{\theta }^T{x}_k{)}^2\\ \text{s.t.}& \theta \in \Omega .\end{array}$$

参考 bias-variance tradeoff, 我们需要尽可能简化模型的形式. 在经过泛函对应后, 即为限制 $\theta$ 的大小. 这里最开始是以二范数为例, 即得到 Tikhonov Regularization 的形式:

$$\begin{array}{rl}\underset{\theta }{\min }& \frac{1}{n}\sum _{k=1}^n(y_k-{\theta }^T{x}_k{)}^2\\ \text{s.t.}& \Vert \theta {\Vert }_2^2\le r.\end{array}$$

对其具体形式进行进一步求解:

$$\begin{array}{rl}\underset{\theta }{\min }& (X\theta -y{)}^T(X\theta -y)\\ \text{s.t.}& {\theta }^T\theta \le r.\end{array}$$

再次引入 Lagrange 乘子, 得到:

$$\begin{array}{rl}L(\theta ,\lambda )& =(X\theta -y{)}^T(X\theta -y)+\lambda ({\theta }^T\theta -r),\\ {\nabla }_{\theta }L(\theta ,\lambda )& =\cdots =2X^{T}X\theta -2X^{T}y+2\lambda \theta =0,\\ \Rightarrow & {\theta }_{\text{Ridge}}=(X^{T}X+\underset{\text{Diagonal Loading}}{\underbrace{\lambda I}}{)}^{-1}{X}^{T}y.\end{array}$$

说明:

• OLS 的最小二乘解是 unbiased 的, 然而这里的结果是有偏的.
• 正如 bias-variance tradeoff 所说, 这里通过牺牲一定的 bias 来降低 variance, 从而提高整体的泛化能力, 因为 variance 更无法控制.

1.1 SVD and L2 Regularization

SVD 原理.

• 对于对称矩阵 $A=A^T$:

  $$A=U\Lambda U^T=\sum _{i=1}^n{\lambda }_i{u}_i{u}_i^T,$$

  其中 $\Lambda =\text{diag}({\lambda }_1,\dots ,{\lambda }_n)$, $U{U}^T=I$.

• 对于 normal 矩阵 $A^{T}A=A{A}^T$:

  $$A=U\Lambda U^H,$$

  其中 $\Lambda =\text{diag}({\lambda }_1,\dots ,{\lambda }_n)$, $U$ 为 unitary 矩阵, $U{U}^H=I$.

• 对于一般方阵:

  $$A=U^{-1}\Lambda U,$$

  其中 $\Lambda =\text{diag}(J_1,\dots ,J_k)$, $J_k$ 为 Jordan Block. 这里称 $\Lambda$ 为 Jordan Canonical Form.

• Singular Value Decomposition. 对于一般矩阵 $A\in {\mathbb{R}}^{m\times n}$:

  $$A=U\Sigma V^T,$$

  其中 $U{U}^T=I$, $V{V}^T=I$, $\Sigma =\left[\begin{array}{cc}\Lambda & 0\\ 0& 0\end{array}\right]$; 且 $\Lambda$ 为一个 diagonal matrix, 其阶对应着 $A$ 的 rank.

SVD 解释 L2 Regularization.

已知 Ridge Regression 结果:

$${\theta }_{\text{Ridge}}=(X^{T}X+\lambda I{)}^{-1}{X}^{T}y.$$

对 $X$ 进行 SVD, 假设 column full rank:

$$\begin{array}{rl}X& =U\Sigma V^T,\\ \text{where }\Sigma & =\left[\begin{array}{c}\Lambda \\ 0\end{array}\right]\text{ thus }{\Sigma }^T\Sigma ={\Lambda }^2.\end{array}$$

因而有:

$$X^{T}X=V{\Sigma }^T{U}^{T}U\Sigma V^T=V{\Sigma }^T\Sigma V^T=V{\Lambda }^2{V}^T.$$

代入 Ridge Regression 结果:

$$\begin{array}{rl}(X^{T}X+\lambda I{)}^{-1}& =(V{\Lambda }^2{V}^T+\lambda V{V}^T{)}^{-1}=V{({\Lambda }^2+\lambda I)}^{-1}{V}^T.\end{array}$$

其中 $({\Lambda }^2+\lambda I)$ 是一个对角矩阵, 其逆是方便求解的.

故:

$$\begin{array}{rl}{\theta }_{\text{Ridge}}& =(X^{T}X+\lambda I{)}^{-1}{X}^{T}y\\ & =V{({\Lambda }^2+\lambda I)}^{-1}{V}^{T}V{\Sigma }^T{U}^{T}y\\ & =V\left({({\Lambda }^2+\lambda I)}^{-1}\Sigma \right)\left(U^{T}y\right)\\ & =V\left[\begin{array}{cccc}\frac{{\lambda }_1}{{\lambda }_1^2+\lambda }& 0& \cdots & 0\\ 0& \frac{{\lambda }_2}{{\lambda }_2^2+\lambda }& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & \frac{{\lambda }_n}{{\lambda }_n^2+\lambda }\end{array}\right]U^{T}y\\ & =\sum _{i=1}^n\boxed{\frac{{\lambda }_i}{{\lambda }_i^2+\lambda }}{u}_i{u}_i^{T}y\\ & :=\sum _{i=1}^n\boxed{\frac{{\lambda }_i}{{\lambda }_i^2+\lambda }}{\tilde{y}}_i.\end{array}$$

从这里可见:

• $\lambda =0$ 就相当于原始 OLS, 也就是对 $y$ 进行一个坐标变换.
• $\lambda$ 很大时, 参照 Lagrange 函数, 发现相当于惩罚使得前项并不重要.
• $\lambda$ 在正常范围内时, ${\lambda }_i$ 需要纳入考量.
  • 这里的 ${\lambda }_i$ 是数据特征矩阵 $X$ SVD 的结果, 相当于是数据的特征.
  • ${\lambda }_i$ 作为 SVD 的结果表示对应数据的权重. 当 ${\lambda }_i$ 较大时, $\lambda$ 对于数值的影响较小.
  • 反之 ${\lambda }_i$ 较小时, 说明这些数据本身对于原训练集的重要性不那么大, 有可能这些 feature 本身就是噪声. 这时 $\lambda$ 相对起到关键作用.
  • 当 ${\lambda }_i$ 较小时, 分母上为 ${\lambda }_i^2$, 更小, 因此原先可能出现数值不稳定的情况, 即几乎不可逆等. $\lambda$ 的引入控制了这个问题.

Note: Link to Laplace smoothing

This stabilization role is reminiscent of Laplace smoothing.

2. LASSO Regularization

• Ridge. 回顾 L2 regularization 的优化目标:

  $$\begin{array}{rl}\underset{\theta }{\min }& (X\theta -y{)}^T(X\theta -y)\\ \text{s.t.}& {\theta }^T\theta \le r.\end{array}$$

  可以发现, 其可行域 ${\theta }^T\theta \le r$ 为一个圆形区域; 其解集 $(X\theta -y{)}^T(X\theta -y)$ 为一系列关于 $\theta$ 的二次曲线.

  事实上, 椭圆等高线与圆形可行域相切的点即为最优解.

• LASSO (Least Absolute Shrinkage and Selection Operator). Tibshirani, 1996.

  与 Ridge Regression 相比, LASSO 的惩罚项为 L1 范数:

  $$\begin{array}{rl}\underset{\theta }{\min }& \frac{1}{n}\sum _{k=1}^n(y_k-{\theta }^T{x}_k{)}^2\\ \text{s.t.}& \Vert \theta {\Vert }_1\le r.\end{array}$$

  因此其可行域为菱形, 而等高线不变.

  与 Ridge Regression 相比, LASSO 的解更容易出现在坐标轴附近, 因此更加稀疏, 即更多的 ${\theta }_i$ 为 $0$.

  LASSO 对模型起到了 selection 的作用, 而且这种变量选择是自动的.

3. $L_q$ Regularization and Elastic Net

3.1 $L_q$ Regularization

其约束形式为

$$\Vert \theta {\Vert }_q\le r.$$

3.2 Elastic Net

其约束形式为

$$\alpha \Vert \theta {\Vert }_1+(1-\alpha )\Vert \theta {\Vert }_2^2\le r.$$

4. Regularization Theory

4.1 Weight Decay

• 上面提到的 L1, L2 等都是通过限制参数的大小实现其目的, 即 weight decay.
• Weight decay 只是 regularization 的一种.

4.2 Dropout

• 为了保证模型的泛化能力及其弹性, 有时在一定的训练后会随机去掉一定数据, 这就是 dropout.
• Dropout 相当于一个随机 selection.

4.3 Noise Injection

• 在 CV 等训练过程中, 可以注入一定的噪声信息, 从而提高模型的鲁棒性.
• 事实上, Ridge Regression 也是广义的 noise injection 的一种.

Related Notes

• Linear Regression
• Kernel Methods
• Naive Bayes Classifier