正则化 Regularization

文章目录

• 正则化 Regularization
• • 1. 问题引入
  • • 1.1 拟合的准确性和过拟合
    • 1.2 Bias-Variance Trade-off
    • 1.3 正则化引入
  • 2. 吉洪诺夫正则化
  • • 2.1 模型建立
    • 2.2 对λ意义的探索
    • 2.3 奇异值分解与吉洪诺夫正则化
    • • 2.3.1 奇异值分解
      • 2.3.2 吉洪诺夫正则化分析
      • • 2.3.2.1 公式变形
        • 2.3.2.2 没有λ的情况
        • 2.3.2.3 有λ的情况
  • 3. L1正则化
  • • 3.1 L1正则化和L2正则化的比较
    • 3.2 L1正则化的求解
    • • 3.2.1 目标函数
      • 3.2.2 凸函数的性质
      • 3.2.3 基于凸优化理论求解L1正则化

1. 问题引入

1.1 拟合的准确性和过拟合

  现在我们有一些数据，我们希望对数据进行拟合。拟合的过程就是一个建模的过程。

  通常我们并不知道f(x)和x的关系，我们猜测这是个线性关系，在最小均方误差意义下，最小二乘就是最好的线性估计。

  但是线性的，并不一定是最好的，因为我很多点并不在拟合的直线(红色)上。如果我们希望把这些点全部利用起来，比如我们用分段线性的方法，构造了新的拟合曲线(黄色)。

  拟合没有好坏之分，对于现在的这些数据，黄色曲线更加贴切，但是，如果我们使用黄色曲线去继续做数据预测，预测结果很难做到准确，因为黄色的曲线的拟合做过了，过于要求把现有的数据给用上了。很大程度上，过拟合产生的根本原因就是，模型过于复杂。

M o d e l i n g ⇓ O v e r f i t ⇓ O v e r c o m p l e x Modeling \\ \Downarrow \\ Overfit\\ \Downarrow\\ Overcomplex Modeling⇓Overfit⇓Overcomplex

  模型过于复杂之后，预测就会不准确，因为模型的可用度降低，我们也没有从根本上抓住数据产生的规律

1.2 Bias-Variance Trade-off

  现在我们换一个角度来考虑拟合的事情。就是Bias-Variance Trade-Off的角度。我们的目标是通过数据x，搞清楚f(x)是什么，我们利用现有的数据做训练集，产生一个拟合。然后通过拟合结果可以产生预测。预测数据就是用来与验证集一起做检验的

B i a s − V a r i a n c e T r a d e − o f f D a t a ( T r a i n i n g ) ( F i t t i n g ) P r e d i c t i o n ( T e s t i n g ) Bias-Variance Trade-off\\ Data(Training) \\ (Fitting) \\ Prediction(Testing) Bias−VarianceTrade−offData(Training)(Fitting)Prediction(Testing)

  我们把数据标记为D，预测用的数据标记为D。我们所做的工作就是产生基于D的一个函数，然后对检验数据进行检验。

⇒ g D ( Z ) \Rightarrow g_D(Z) ⇒gD​(Z)

  我们希望新的数据表现，与我们预测的数据的表现是一致的，因此有目标函数

( g D ( Z ) − f ( Z ) ) 2 (g_D(Z) - f(Z))^2 (gD​(Z)−f(Z))2
  我们希望估计误差能够达到最小。同时，由于训练数据D和预测数据Z都是随机变量，所以，这里我们要取期望。

m i n E D , Z [ ( g D ( Z ) − f ( Z ) ) 2 ] minE_{D,Z}[(g_D(Z) - f(Z))^2] minED,Z​[(gD​(Z)−f(Z))2]

  上式可以转化为条件期望

E D , Z [ ( g D ( Z ) − f ( Z ) ) 2 ] = E Z [ E D ∣ Z ( ( g D ( Z ) − f ( Z ) ) 2 ) ] E_{D,Z}[(g_D(Z) - f(Z))^2]=E_{Z}[E_{D|Z}((g_D(Z) - f(Z))^2)] ED,Z​[(gD​(Z)−f(Z))2]=EZ​[ED∣Z​((gD​(Z)−f(Z))2)]

  我们对式子进行变形

E Z [ E D ∣ Z ( ( g D ( Z ) − f ( Z ) ) 2 ) ] = E Z [ E D ∣ Z ( ( g D ( Z ) − g ˉ ( Z ) + g ˉ ( Z ) − f ( Z ) ) 2 ) ] E_{Z}[E_{D|Z}((g_D(Z) - f(Z))^2)] = E_{Z}[E_{D|Z}((g_D(Z) -\bar g(Z)+\bar g(Z)- f(Z))^2)] \\ EZ​[ED∣Z​((gD​(Z)−f(Z))2)]=EZ​[ED∣Z​((gD​(Z)−gˉ​(Z)+gˉ​(Z)−f(Z))2)]

  其中

g ˉ ( Z ) = E D ( g D ( Z ) ) \bar g(Z) = E_D(g_D(Z)) gˉ​(Z)=ED​(gD​(Z))

E Z [ E D ∣ Z ( ( g D ( Z ) − g ˉ ( Z ) + g ˉ ( Z ) − f ( Z ) ) 2 ) ] = E Z [ E D ∣ Z ( ( g D ( Z ) − g ˉ ( Z ) ) 2 + E D ∣ Z ( ( g ˉ ( Z ) − f ( Z ) ) 2 ) + 2 ∗ E D ∣ Z ( g D ( Z ) − g ˉ ( Z ) ) ∗ ( g ˉ ( Z ) − f ( Z ) ) ] ( 1 ) E_{Z}[E_{D|Z}((g_D(Z) -\bar g(Z)+\bar g(Z)- f(Z))^2)] \\ = E_{Z}[ E_{D|Z}((g_D(Z) -\bar g(Z))^2+ E_{D|Z}((\bar g(Z)- f(Z))^2) +2* E_{D|Z}(g_D(Z) -\bar g(Z))*(\bar g(Z)- f(Z))] \quad\quad(1) EZ​[ED∣Z​((gD​(Z)−gˉ​(Z)+gˉ​(Z)−f(Z))2)]=EZ​[ED∣Z​((gD​(Z)−gˉ​(Z))2+ED∣Z​((gˉ​(Z)−f(Z))2)+2∗ED∣Z​(gD​(Z)−gˉ​(Z))∗(gˉ​(Z)−f(Z))](1)

  我们来证明一下交叉项为0

E D ∣ Z ( g D ( Z ) − g ˉ ( Z ) ) ∗ ( g ˉ ( Z ) − f ( Z ) ) E_{D|Z}(g_D(Z) -\bar g(Z))*(\bar g(Z)- f(Z)) ED∣Z​(gD​(Z)−gˉ​(Z))∗(gˉ​(Z)−f(Z))

  因为条件概率中，对Z来说是没有随机性，后面可以放到外面，同时\bar g已经是期望了，也没有随机性，也可以放到期望外面

E D ∣ Z ( g D ( Z ) − g ˉ ( Z ) ) ∗ ( g ˉ ( Z ) − f ( Z ) ) = ( g ˉ ( Z ) − f ( Z ) ) ∗ E D ∣ Z ( g D ( Z ) − g ˉ ( Z ) ) ) = ( g ˉ ( Z ) − f ( Z ) ) ∗ [ E D ∣ Z ( g D ( Z ) ) − g ˉ ( Z ) ] = ( g ˉ ( Z ) − f ( Z ) ) ∗ [ E D ∣ Z ( g D ( Z ) ) − E D ( g D ( Z ) ) ] = 0 E_{D|Z}(g_D(Z) -\bar g(Z))*(\bar g(Z)- f(Z)) = (\bar g(Z)- f(Z)) * E_{D|Z}(g_D(Z) -\bar g(Z))) \\ = (\bar g(Z)- f(Z))*[E_{D|Z}(g_D(Z))-\bar g(Z)] \\ = (\bar g(Z)- f(Z))*[E_{D|Z}(g_D(Z)) - E_D(g_D(Z))] =0 ED∣Z​(gD​(Z)−gˉ​(Z))∗(gˉ​(Z)−f(Z))=(gˉ​(Z)−f(Z))∗ED∣Z​(gD​(Z)−gˉ​(Z)))=(gˉ​(Z)−f(Z))∗[ED∣Z​(gD​(Z))−gˉ​(Z)]=(gˉ​(Z)−f(Z))∗[ED∣Z​(gD​(Z))−ED​(gD​(Z))]=0

  所以(1)式可变为
E Z [ E D ∣ Z ( ( g D ( Z ) − f ( Z ) ) 2 ) ] = E Z [ E D ∣ Z ( ( g D ( Z ) − g ˉ ( Z ) ) 2 + E D ∣ Z ( ( g ˉ ( Z ) − f ( Z ) ) 2 ) ] = V a r i a n c e + B i a s E_{Z}[E_{D|Z}((g_D(Z) - f(Z))^2)] = E_{Z}[ E_{D|Z}((g_D(Z) -\bar g(Z))^2+ E_{D|Z}((\bar g(Z)- f(Z))^2)] \\ = Variance + Bias EZ​[ED∣Z​((gD​(Z)−f(Z))2)]=EZ​[ED∣Z​((gD​(Z)−gˉ​(Z))2+ED∣Z​((gˉ​(Z)−f(Z))2)]=Variance+Bias

  得到的两项分别是方差和偏差。因此，我们做的拟合，实际上就是包括方差和偏差两部分。

  我们从机器学习的角度来思考这件事情。什么是训练结束呢?其实训练结束就是个理想概念，当我们拟合的模型方差足够小的时候，就认为训练好了，然后再看跟实际数据的偏差有多少，然后继续训练。因为往往我们训练的数据都是少的可怜，我们训练的时间也是有限的，因此一般差不多就行了，很难达到训练结束的标准。

  所以，我们知道了，我们数据拟合的两部分误差的意义是，方差部分表示离完全训练好还有多远，偏差部分代表训练好了以后距离目标还有多远。

1.3 正则化引入

  我们在训练中真正能够控制好的只有前面那部分。如果我们想让训练过程变得可控，我们必须采用简单的模型。这里我们举个例子，有时候训练可能会产生这样的问题，就是我们训练的数据很好，得到的拟合的误差很小，但是使用测试集就很差了。很大的原因就是，我们训练的时候模型过于复杂，以致于得到的模型是个过拟合的，因此得到的模型效果很差。

  这里有个原则叫做Occam’s Razor，其含义是，如果我们能用简单的模型去处理问题，就不要使用复杂的模型。但是简单的模型就会有其他代价。因为偏差可能会很大。不过我们往往并不关心偏差，因为我们很多时候对目标并不清晰，数据量也是有限的，我们应该更加着眼于我们能够控制的事情上。

  那么我们应该如何使用简单的模型呢?首先，能用线性的模型，就不要使用非线性的模型。

  其次，假设我们的目标就定在线性模型上了，其复杂性体现在线性模型拟合的因子数量上。

  假设有这样的模型

∑ k = 1 N ω k Z k N > > 1 ⇒ m i n E ( Y − ∑ k = 1 N ω k Z k ) 2 \sum_{k=1}^N \omega_kZ_k \quad\quad N>>1 \Rightarrow minE(Y- \sum_{k=1}^N \omega_kZ_k)^2 k=1∑N​ωk​Zk​N>>1⇒minE(Y−k=1∑N​ωk​Zk​)2

  我们有这样的问题，这里面使用的拟合因子是否都是重要的。如果我们评价因素一旦多了起来，我们又可能陷入过拟合的风险去了，因为我们对系数没有任何的约束，系数是任意变化的。

  往往为了达到更好的拟合结果，有一些因素的系数会增长，而有一些因素的系数会很小，使得这些因素的影响变得微乎其微。这就好比足球比赛选球员，一旦主力球员全部都受伤了，没法上场，选了一些替补，比赛结果相比也不会很好。因此一旦在拟合的过程中，出现了系数极端分布的情况，最终很可能没有办法得到一个好的结果。

  因此，我们希望对每个因素的权力加以限制。避免少数人得到大多数的权力这种情况。也就是一方面要让主力得到更多的权力，但是同时，主力也不会单打独斗，要让更多人得到平衡的发挥。

  因此，我们希望引入一种方法来解决两个问题

• 第一，对系数进行约束，避免产生系数极端分布的情况
• 第二，识别拟合的因素中，哪些是重要的影响因素。然后简化模型

  这种方法就是正则化。

2. 吉洪诺夫正则化

2.1 模型建立

  正则化有很多种形式，而吉洪诺夫正则化主要是用来解决对系数的约束问题的。为了避免系数产生极端分布的情况，我们就要对系数进行约束，使得各个因素的权力得到分散，我们可以使用这样的方法来进行约束

∑ k = 1 N ω k 2 ≤ P \sum_{k=1}^N \omega_k^2 \leq P k=1∑N​ωk2​≤P

  我们就要对系数进行约束，通过约束完成我们的目的。使得我们的模型，不至于进入到极端的情况中。增加能够起到分散权力的目的的约束。因此，我们要求系数的平方和不能太大。如果我们使用上这个约束条件，目标函数就变成了

E ( Y − ∑ k = 1 N ω k Z k ) 2 + λ ( ∑ k = 1 N ω k 2 − P ) E(Y- \sum_{k=1}^N \omega_kZ_k)^2 + \lambda(\sum_{k=1}^N \omega_k^2 - P) E(Y−k=1∑N​ωk​Zk​)2+λ(k=1∑N​ωk2​−P)

  由于P是常数，我们把目标方程修改为。这个式子就是吉洪诺夫正则化Tikhonov Regularization。吉洪诺夫正则化是一种L2正则化，要取模型参数二范数

∣ ∣ ω ∣ ∣ 2 2 ||\omega||^2_2 ∣∣ω∣∣22​

T i k h o n o v R e g u l a r i z a t i o n E ( Y − ∑ k = 1 N ω k Z k ) 2 + λ ( ∑ k = 1 N ω k 2 ) Tikhonov \quad Regularization\\ E(Y- \sum_{k=1}^N \omega_kZ_k)^2 + \lambda(\sum_{k=1}^N \omega_k^2 ) TikhonovRegularizationE(Y−k=1∑N​ωk​Zk​)2+λ(k=1∑N​ωk2​)

  目标函数表示为

m i n [ E ( Y − ω T Z ) 2 + λ ∣ ∣ ω ∣ ∣ 2 ] min[E(Y- \omega^TZ)^2 + \lambda||\omega||^2] min[E(Y−ωTZ)2+λ∣∣ω∣∣2]

Z = ( Z 1 , . . . , Z N ) T , ω = ( ω 1 , . . , ω N ) T Z = (Z_1,...,Z_N)^T, \omega = (\omega_1,..,\omega_N)^T \\ Z=(Z1​,...,ZN​)T,ω=(ω1​,..,ωN​)T

  我们使用吉洪诺夫正则化，一方面是为了求得准确的拟合结果，另一方面是为了约束模型，获得更加简单的结果。因此λ实际上就是在控制两个目标的比例。如果λ是0，那么就变成了最小二乘问题。如果λ是∞，那么就意味着前面一部分可以忽略了，并且为了获得一个最简单的模型，ω只能是0。这两种情况都不是我们希望看到的。

λ = 0 ⇒ L S λ = ∞ ⇒ ω = 0 \lambda =0 \Rightarrow LS \\ \lambda = \infty \Rightarrow \omega = 0 λ=0⇒LSλ=∞⇒ω=0

2.2 对λ意义的探索

  这里我们希望继续深入挖掘一下λ对这个系统起到了怎么样的影响。

  假设我们有若干用于拟合的数据。其中Z是个N维的数据，为Y是个一维的数据。

( Z 1 , Y 1 ) , ( Z 2 , Y 2 ) , . . . , ( Z n , Y n ) Z k ∈ R N , Y k ∈ R , k = 1 , . . . , n (Z_1,Y_1),(Z_2,Y_2),...,(Z_n,Y_n) \quad\quad Z_k \in R^N,Y_k \in R,k=1,...,n (Z1​,Y1​),(Z2​,Y2​),...,(Zn​,Yn​)Zk​∈RN,Yk​∈R,k=1,...,n

  目标函数为
∑ i = 1 n E ( Y i − ω T Z i ) 2 + λ ∣ ∣ ω ∣ ∣ 2 ⇒ ( Y − Z ω ) T ( Y − Z ω ) + λ ∣ ∣ ω ∣ ∣ 2 \sum_{i=1}^{n}E(Y_i- \omega^TZ_i)^2 + \lambda||\omega||^2 \Rightarrow (Y-Z\omega)^T(Y-Z \omega) + \lambda||\omega||^2 i=1∑n​E(Yi​−ωTZi​)2+λ∣∣ω∣∣2⇒(Y−Zω)T(Y−Zω)+λ∣∣ω∣∣2

Z = ( Z 1 . . . Z n ) ∈ R n ∗ N , ω ∈ R N Z = \begin{pmatrix} Z_1 \\ ... \\ Z_n \end{pmatrix} \in R^{n*N},\omega \in R^N Z=⎝⎛​Z1​...Zn​​⎠⎞​∈Rn∗N,ω∈RN

  展开
L ( ω ) = Y T ∗ Y − Y T Z ω − ω T Z T ∗ Y + ω T ∗ Z T ∗ Z ∗ ω + λ ∗ ω T ∗ ω L(\omega) = Y^T*Y -Y^TZ \omega - \omega^TZ^T*Y + \omega^T*Z^T*Z*\omega + \lambda*\omega^T*\omega L(ω)=YT∗Y−YTZω−ωTZT∗Y+ωT∗ZT∗Z∗ω+λ∗ωT∗ω

  求梯度
∇ ω L ( ω ) = − Z T Y − Z T Y + 2 ( Z T Z ) ω + 2 λ ω = 0 \nabla_\omega L(\omega) = - Z^TY - Z^TY + 2(Z^TZ)\omega + 2\lambda \omega = 0 ∇ω​L(ω)=−ZTY−ZTY+2(ZTZ)ω+2λω=0

  计算可得

ω = ( Z T Z + λ I ) − 1 Z T Y \omega = (Z^TZ +\lambda I)^{-1}Z^T Y ω=(ZTZ+λI)−1ZTY

  我们可以用这个结果与最小二乘解进行比较。我们发现，λ是0的时候，这个结果就是最小二乘解

  我们根据这个结果可以对λ的作用进行更加深入的分析。

• 首先，我们知道Z^T*Z一定是非负矩阵，但是不一定是正定的。因此，最小二乘解不一定存在，因为这个矩阵不一定可逆。而且Z必须要是个长矩阵，也就是方程数量必须大于未知数数量，因为最小二乘解的是一个超定矩阵。并且要求这个矩阵是列满秩的。现在，在后面加入了一部分新东西，这部分一定是正的。因此，(Z^TZ+λI)这个矩阵一定是个可逆的，因此，λ使得这个方程变成良态的了。这种处理方法在信号处理中叫做对角加载。在统计上叫做岭回归，因为相当于顶起来一堵墙。所以，吉洪诺夫正则化、对角加载、岭回归是一个意思。他们的目的都是使得方程变成良态的。

R i d g e R e g r e s s i o n 岭 回 归 D i a g o n a l L o a d i n g 对 角 加 载 T i k h o n o v R e g u l a r i z a t i o n 吉 洪 诺 夫 正 则 化 Ridge \quad Regression \quad 岭回归 \\ Diagonal \quad Loading 对角加载 \\ Tikhonov \quad Regularization 吉洪诺夫正则化 RidgeRegression岭回归DiagonalLoading对角加载TikhonovRegularization吉洪诺夫正则化

• 第二个值得探讨的是，得到的这个解并不是一个无偏估计的解

  我们可以来证明一下,首先要凑一个最小二乘解

ω R i d g e = ( Z T Z + λ I ) − 1 Z T Y = ( Z T Z + λ I ) − 1 ( Z T Z ) ( Z T Z ) − 1 Z T Y = ( I + λ ( Z T Z ) − 1 ) − 1 ∗ ( Z T Z ) − 1 ∗ ( Z T Z ) ( Z T Z ) − 1 Z T Y = ( I + λ ( Z T Z ) − 1 ) − 1 ∗ ω L S \omega_{Ridge} = (Z^TZ +\lambda I)^{-1}Z^T Y \\ =(Z^TZ +\lambda I)^{-1} (Z^TZ)(Z^TZ)^{-1}Z^T Y \\ = (I+\lambda(Z^TZ)^{-1})^{-1}*(Z^TZ)^{-1} * (Z^TZ)(Z^TZ)^{-1}Z^T Y \\ = (I+\lambda(Z^TZ)^{-1})^{-1} * \omega_{LS} ωRidge​=(ZTZ+λI)−1ZTY=(ZTZ+λI)−1(ZTZ)(ZTZ)−1ZTY=(I+λ(ZTZ)−1)−1∗(ZTZ)−1∗(ZTZ)(ZTZ)−1ZTY=(I+λ(ZTZ)−1)−1∗ωLS​

  矩阵具有这样的性质，当||A|| 小于1时

( I + A ) − 1 = ∑ k = 0 ∞ ( − 1 ) k A k ∣ ∣ A ∣ ∣ < 1 (I+A)^{-1} = \sum_{k=0}^{\infty}(-1)^k A^k \quad\quad ||A|| <1 (I+A)−1=k=0∑∞​(−1)kAk∣∣A∣∣<1

  因此，当λ很小的时候，有这样的式子成立

λ < < 1 ω R i d g e = ( I + λ ( Z T Z ) − 1 ) − 1 ∗ ω L S = ∑ k = 0 ∞ ( − 1 ) k ( λ ( Z T Z ) − 1 ) k = ( I − λ ( Z T Z ) − 1 + λ 2 ( Z T Z ) − 2 + . . . ) ω L S = ( I − λ ( Z T Z ) − 1 ) ω L S + O ( λ ) \lambda << 1 \\ \omega_{Ridge} = (I+\lambda(Z^TZ)^{-1})^{-1} * \omega_{LS} \\ = \sum_{k=0}^{\infty}(-1)^k (\lambda(Z^TZ)^{-1})^k \\ = (I - \lambda(Z^T Z)^{-1} + \lambda^2(Z^T Z)^{-2}+...) \omega_{LS} \\ = (I - \lambda(Z^T Z)^{-1} )\omega_{LS} + O(\lambda) λ<<1ωRidge​=(I+λ(ZTZ)−1)−1∗ωLS​=k=0∑∞​(−1)k(λ(ZTZ)−1)k=(I−λ(ZTZ)−1+λ2(ZTZ)−2+...)ωLS​=(I−λ(ZTZ)−1)ωLS​+O(λ)

  因为最小二乘是无偏的，加上一个高阶无穷小以后，就是偏差的了。

  一般来说λ和系数ω具有这样的关系

  当λ很大的时候，ω的活力没有体现出来，受到严重的约束。当λ是0的时候，ω完全不受约束，会产生过拟合问题。因此应该选择一个适合的λ，来在两个问题之间做取舍。

2.3 奇异值分解与吉洪诺夫正则化

2.3.1 奇异值分解

  从另外一个角度看待吉洪诺夫正则化，也就是奇异值分解的角度。

  奇异值分解的定义如下。

A ∈ R n ∗ N , A = U Σ V T , U ∈ R n ∗ n , V ∈ R N ∗ N , Σ ∈ R n ∗ N U ∗ U T = U T ∗ U = I ， V ∗ V T = V T ∗ V = I , Σ = ( D 0 0 0 ) A \in R^{n*N}, A = U \Sigma V^T, U \in R^{n*n},V\in R^{N*N},\Sigma \in R^{n*N} \\ U*U^T = U^T*U = I， V*V^T = V^T * V = I , \Sigma = \begin{pmatrix} D & 0 \\ 0 & 0 \end{pmatrix} A∈Rn∗N,A=UΣVT,U∈Rn∗n,V∈RN∗N,Σ∈Rn∗NU∗UT=UT∗U=I，V∗VT=VT∗V=I,Σ=(D0​00​)
  其中U和V都是正交矩阵。∑是对角阵的扩充矩阵。

  我们类比下矩阵的特征值分解,特征分解需要满足两个条件

• 只能对方阵做
• 方阵必须是对称的

A ∈ R n ∗ n , A T = A ⇒ A = U ∗ Σ ∗ U T U T ∗ U = I , Σ i s d i a g A \in R^{n*n}, A^T = A \Rightarrow A = U * \Sigma*U^T \\ U^T*U = I ,\Sigma \quad is \quad diag A∈Rn∗n,AT=A⇒A=U∗Σ∗UTUT∗U=I,Σisdiag

  奇异值分解是对称具体特征分解的推广。

• 不要求是方阵
• 不要求对称
• 中间是个对角阵补0

  如果A能做奇异值分解，则

A T ∗ A = V Σ T Σ V T A ∗ A T = U Σ Σ T U T A^T*A = V \Sigma ^T \Sigma V^T \\ A* A^T = U \Sigma \Sigma^T U^T AT∗A=VΣTΣVTA∗AT=UΣΣTUT
  奇异值矩阵的对角线叫做奇异值

2.3.2 吉洪诺夫正则化分析

2.3.2.1 公式变形

  我们来深入分析一下吉洪诺夫正则化

ω R i d g e = ( Z T Z + λ I ) − 1 Z T Y \omega_{Ridge} = (Z^TZ +\lambda I)^{-1} Z^T Y ωRidge​=(ZTZ+λI)−1ZTY

  对Z做奇异值分解

Z = U ∗ Σ ∗ V T Z T ∗ Z = V ∗ Σ T ∗ Σ ∗ V T Z = U*\Sigma *V^T \\ Z^T*Z = V* \Sigma^T * \Sigma* V^T Z=U∗Σ∗VTZT∗Z=V∗ΣT∗Σ∗VT

  代入得

ω R i d g e = ( V ∗ Σ T ∗ Σ ∗ V T + λ I ) − 1 ∗ ( U ∗ Σ ∗ V T ) T ∗ Y = ( V ∗ ( Σ T ∗ Σ + λ ∗ I ) ∗ V T ) − 1 ∗ ( V ∗ Σ T ∗ U T ) ∗ Y = [ V T ] − 1 ∗ ( Σ T ∗ Σ + λ ∗ I ) − 1 ∗ V − 1 ∗ ( V ∗ Σ T ∗ U T ) ∗ Y = V ∗ ( Σ T ∗ Σ + λ ∗ I ) − 1 ∗ Σ T ∗ U T ∗ Y \omega_{Ridge} = (V* \Sigma^T * \Sigma* V^T +\lambda I )^{-1}*(U*\Sigma *V^T )^T*Y \\ = (V*(\Sigma^T * \Sigma + \lambda*I)*V^T)^{-1} * (V*\Sigma^T*U^T)*Y \\ = [V^T]^{-1}*(\Sigma^T * \Sigma + \lambda*I)^{-1}*V^{-1}*(V*\Sigma^T*U^T)*Y \\ = V*(\Sigma^T * \Sigma + \lambda*I)^{-1}*\Sigma^T*U^T*Y ωRidge​=(V∗ΣT∗Σ∗VT+λI)−1∗(U∗Σ∗VT)T∗Y=(V∗(ΣT∗Σ+λ∗I)∗VT)−1∗(V∗ΣT∗UT)∗Y=[VT]−1∗(ΣT∗Σ+λ∗I)−1∗V−1∗(V∗ΣT∗UT)∗Y=V∗(ΣT∗Σ+λ∗I)−1∗ΣT∗UT∗Y

  因为Z是一个方程数量超过变量数量的矩阵，因此是个细长的矩阵，因此奇异值分解的∑具有这样的形式

Σ = ( D 0 ) Σ T = ( D 0 ) \Sigma = \begin{pmatrix} D \\ 0 \end{pmatrix} \\ \Sigma^T = \begin{pmatrix} D &0 \end{pmatrix} Σ=(D0​)ΣT=(D​0​)

  把上面的式子写一下

( Σ T ∗ Σ + λ ∗ I ) − 1 ∗ Σ T = ( ( D T ∗ D + λ I ) − 1 D 0 ) (\Sigma^T * \Sigma + \lambda*I)^{-1}*\Sigma^T =\begin{pmatrix} (D^T*D +\lambda I)^{-1}D &0 \end{pmatrix} (ΣT∗Σ+λ∗I)−1∗ΣT=((DT∗D+λI)−1D​0​)

  从结构中，我们可以分析出来，这个矩阵是个对角阵补0矩阵，对角线元是

[ ( D T ∗ D + λ I ) − 1 D ] i i = d i d i 2 + λ [(D^T*D +\lambda I)^{-1}D]_{ii} = \frac{d_i}{d_i^2+\lambda} [(DT∗D+λI)−1D]ii​=di2​+λdi​​

D = d i a g ( d 1 , . . . , d N ) D = diag(d_1,...,d_N) D=diag(d1​,...,dN​)
  因此

ω R i d g e = V ∗ ( ( D T ∗ D + λ I ) − 1 D 0 ) ∗ U T ∗ Y \omega_{Ridge} = V*\begin{pmatrix} (D^T*D +\lambda I)^{-1}D &0 \end{pmatrix}*U^T*Y ωRidge​=V∗((DT∗D+λI)−1D​0​)∗UT∗Y

  估计结果为
Z ∗ ω R i d g e = U ∗ Σ ∗ V T ∗ V ∗ ( ( D T ∗ D + λ I ) − 1 D 0 ) ∗ U T ∗ Y = U ∗ ( D 0 ) ∗ ( ( D T ∗ D + λ I ) − 1 D 0 ) ∗ U T ∗ Y = ( U ( 1 ) U ( 2 ) ) ∗ ( D ( D T ∗ D + λ I ) − 1 D 0 0 0 ) ∗ ( U ( 1 ) T U ( 2 ) T ) ∗ Y = U ( 1 ) ∗ ( D ( D T ∗ D + λ I ) − 1 D ) ∗ U ( 1 ) T ∗ Y ( i ) Z*\omega_{Ridge} = U*\Sigma*V^T*V*\begin{pmatrix} (D^T*D +\lambda I)^{-1}D &0 \end{pmatrix}*U^T*Y \\ = U* \begin{pmatrix} D \\ 0 \end{pmatrix}*\begin{pmatrix} (D^T*D +\lambda I)^{-1}D &0 \end{pmatrix}*U^T*Y \\ = \begin{pmatrix} U_{(1)} &U_{(2)} \end{pmatrix} * \begin{pmatrix} D(D^T*D +\lambda I)^{-1}D & 0 \\ 0& 0 \end{pmatrix}* \begin{pmatrix} U_{(1)}^T \\ U_{(2)}^T \end{pmatrix}*Y \\ = U_{(1)}*(D(D^T*D +\lambda I)^{-1}D)*U_{(1)}^T*Y \quad\quad(i) Z∗ωRidge​=U∗Σ∗VT∗V∗((DT∗D+λI)−1D​0​)∗UT∗Y=U∗(D0​)∗((DT∗D+λI)−1D​0​)∗UT∗Y=(U(1)​​U(2)​​)∗(D(DT∗D+λI)−1D0​00​)∗(U(1)T​U(2)T​​)∗Y=U(1)​∗(D(DT∗D+λI)−1D)∗U(1)T​∗Y(i)
  U₍₁₎和U₍₂₎有如下定义

U ( 1 ) ∼ r o w = N U ( 2 ) ∼ r o w = n − N U_{(1)} \sim row = N \\ U_{(2)} \sim row = n-N U(1)​∼row=NU(2)​∼row=n−N

  令U₍₁₎

U ( 1 ) = ( U 1 , . . . , U N ) U_{(1)} = (U_1,...,U_N) U(1)​=(U1​,...,UN​)

  (i)式可化为

U ( 1 ) ∗ ( D ( D T ∗ D + λ I ) − 1 D ) ∗ U ( 1 ) T ∗ Y = ∑ k = 1 N ( d k 2 d k 2 + λ ) U k ( U k T ∗ Y ) = ∑ k = 1 N ( d k 2 d k 2 + λ ) ( U k T ∗ Y ) ∗ U k U_{(1)}*(D(D^T*D +\lambda I)^{-1}D)*U_{(1)}^T*Y \\ = \sum_{k=1}^{N}(\frac{d_k^2}{d_k^2+\lambda})U_k (U_k^T*Y) \\ = \sum_{k=1}^{N}(\frac{d_k^2}{d_k^2+\lambda}) (U_k^T*Y)*U_k U(1)​∗(D(DT∗D+λI)−1D)∗U(1)T​∗Y=k=1∑N​(dk2​+λdk2​​)Uk​(UkT​∗Y)=k=1∑N​(dk2​+λdk2​​)(UkT​∗Y)∗Uk​

  后面那部分，U^T是横着的，Y是横着的，相乘是个数，所以可以交换次序

2.3.2.2 没有λ的情况

  当λ是0的时候，得到的就是最小二乘解

λ = 0 ⇒ ∑ k = 1 N ( U k T ∗ Y ) ∗ U k \lambda = 0 \Rightarrow \sum_{k=1}^{N} (U_k^T*Y)*U_k λ=0⇒k=1∑N​(UkT​∗Y)∗Uk​

  与最小二乘进行比较
m i n ( Y − Z ω ) T ( Y − Z ω ) ⇓ ω L S = ( Z T Z ) − 1 Z T Y ⇓ Y ^ = Z ∗ ω L S = Z ( Z T Z ) − 1 Z T Y min(Y-Z \omega)^T(Y-Z \omega) \\ \Downarrow \\ \omega_{LS} = (Z^TZ)^{-1}Z^T Y \\ \Downarrow \\ \hat Y = Z*\omega_{LS} \\ =Z(Z^TZ)^{-1}Z^TY min(Y−Zω)T(Y−Zω)⇓ωLS​=(ZTZ)−1ZTY⇓Y^=Z∗ωLS​=Z(ZTZ)−1ZTY

  最小二乘相当于Y在一组规范正交基上做了投影。而奇异值分解的本质就是做正交化。

Z = ( Z 1 , . . . , Z N ) U ( 1 ) = ( U 1 , . . . , U N ) Z = (Z_1,...,Z_N) \\ U_{(1)} = (U_1,...,U_N) Z=(Z1​,...,ZN​)U(1)​=(U1​,...,UN​)

  U张成的向量空间与Z张成的向量空间是一样的。只不过U是一组规范正交基。因此Y在U上的投影与Y在Z上的投影速度等价的。

S p a n ( Z ) = S p a n ( U ) P r o j Z Y = P r o j U Y Span(Z) = Span(U) \\ Proj_ZY = Proj_U Y Span(Z)=Span(U)ProjZ​Y=ProjU​Y

2.3.2.3 有λ的情况

  没有λ的时候，U里面所有的向量都是等同看待的，有了λ之后，对U矢量看法变了，开始有权重了。d越大，也就是奇异值越大，这个d对应的正交基的权重就变大了。

  我们可以与PCA进行类比

  实际上，主成分分析得到的是能量的体现，也就是能量最高的方向

  而对于吉洪诺夫正则化来说，奇异值分解得到的正交基U就是新的坐标系，奇异值d表示在坐标轴上的能量体现，d越大，能量就越高。我们通过这个d，能够让我们知道哪些参数是比较重要的，能够让我们筛选有价值的参数。就体现出了各个方向的重要性。然后就能够简化模型了。这也叫做模型选择。选择重要的参数。

  因此，正则化也可以起到一个自然选择的作用。

3. L1正则化

3.1 L1正则化和L2正则化的比较

  这里我们回顾一下，正则化的目的是为了实现两个目的

• 通过正则化的约束，使得模型不会出现极端分布的情况
• 通过正则化对影响因素进行辨别，判断哪些是重要因素，从而能够简化模型

  L2正则化，也就是吉洪诺夫正则化，是用来解决第一个问题的，在吉洪诺夫正则化的约束下，使得系数不会极端分布，同时也让方程变得良态。

  而这里我们使用的L1正则化，是为了解决第二个问题的，也就是判断哪些因素是重要的因素，从而选择合适的特征，进行简化模型

L 2 R e g u l a r i z a t i o n ∣ ∣ ω ∣ ∣ 2 2 ( T i k h o n o v ) L 1 R e g u l a r i z a t i o n ∣ ∣ ω ∣ ∣ 1 = ∑ k = 1 N ∣ ω k ∣ L^2 \quad Regularization \quad ||\omega||^2_2 \quad (Tikhonov) \\ L^1 \quad Regularization \quad ||\omega||_1 = \sum_{k=1}^N|\omega_k| L2Regularization∣∣ω∣∣22​(Tikhonov)L1Regularization∣∣ω∣∣1​=k=1∑N​∣ωk​∣

  那么L1正则化和L2正则化有什么区别呢?

  我们先从L2正则化开始。

  L2正则化的约束条件的模的平方和小于某个数值
∣ ∣ ω ∣ ∣ 2 2 ≤ P ||\omega||_2^2 \leq P ∣∣ω∣∣22​≤P

  我们取二维的来看，也就是
ω 1 2 + ω 2 2 ≤ P \omega_1^2 + \omega_2^2 \leq P ω12​+ω22​≤P

  这是一个圆的方程。根据拉格朗日数乘法求条件极值问题，我们知道，最优解就是两个函数的交点处

  也就是我们的线性拟合模型，与圆不断靠近，得到切线。因为约束条件是个圆，切线在不断改变位置的过程中，ω₁和ω₂都是可以连续变化的，变化的时候就是切点改了而已。而且，因为最优解是在圆周上，所以，总体上ω的取值不会有很多极端的情况。

  而如果是L1正则化，就是模的和小于某个值
∣ ω 1 ∣ + ∣ ω 2 ∣ ≤ P |\omega_1| + |\omega_2| \leq P ∣ω1​∣+∣ω2​∣≤P

  这个约束条件是个菱形。因此，大部分情况，最优解是在菱形顶点上。线性模型与菱形边缘重合的概率不是很高

  而最优解在菱形的顶点上就意味着，得到的解是个稀疏解–Sparse Solution。也就是只有部分ω是非零0值，而很多的ω是零值，这样就是简化模型了。

3.2 L1正则化的求解

3.2.1 目标函数

  使用L1正则化的目标函数是下式

m i n ( ∑ i = 1 n ( Y i − ∑ k = 1 N Z i k ω k ) 2 + λ ∑ k = 1 N ∣ ω k ∣ ) min(\sum_{i=1}^n(Y_i - \sum_{k=1}^NZ_{ik}\omega_k)^2 + \lambda \sum_{k=1}^N |\omega_k|) min(i=1∑n​(Yi​−k=1∑N​Zik​ωk​)2+λk=1∑N​∣ωk​∣)

  但是我们发现，L1正则化虽然能够得到稀疏矩阵，但是L1正则化求解有些棘手。因为绝对值是不好求导的。如果我们不关注零点的问题，那么绝对值求导得到的就是符号函数。但是我们要关心零点。这个时候怎么进行求解呢

d d x ∣ x ∣ = s g n ( x ) \frac{d}{dx}|x| = sgn(x) dxd​∣x∣=sgn(x)

  下面我们需要引入一些凸分析的理念 Convex Analysis(Optimization)。

  因为我们发现这个目标函数是个凸函数。

3.2.2 凸函数的性质

  凸函数具有两重要性质

  性质一，凸函数弦上的值大于等于函数值

f ( x ) i s C o n v e x ⇔ ∀ x 1 , x 2 , ∀ λ ∈ [ 0 , 1 ] f ( λ x 1 + ( 1 − λ ) x 2 ) ≤ λ f ( x 1 ) + ( 1 − λ ) f ( x 2 ) f(x)\quad is \quad Convex \Leftrightarrow \forall x_1,x_2, \forall \lambda \in[0,1] \\ f(\lambda x_1 + (1-\lambda)x_2) \leq \lambda f(x_1) +(1-\lambda) f(x_2) f(x)isConvex⇔∀x1​,x2​,∀λ∈[0,1]f(λx1​+(1−λ)x2​)≤λf(x1​)+(1−λ)f(x2​)

  性质二，凸函数的切线一定小于等于函数值

f ( x ) i s C o n v e x ⇔ ∀ x 1 , x 2 , ∃ g f ( x 2 ) ≥ f ( x 1 ) + g T ( x 2 − x 1 ) f(x)\quad is \quad Convex \Leftrightarrow \forall x_1,x_2, \exists g \\ f(x_2) \geq f(x_1) + g^T (x_2-x_1) f(x)isConvex⇔∀x1​,x2​,∃gf(x2​)≥f(x1​)+gT(x2​−x1​)

  凸函数的性质不但对光滑的函数成立，对不光滑的函数也是成立的。对于光滑函数来说，g是导数/梯度，对于不光滑函数来说g是次梯度。次梯度是个集合

∂ x f ( x ) = ∇ x f ( x )  x is smooth point \partial_xf(x) = \nabla_xf(x) \quad \text{ x is smooth point} ∂x​f(x)=∇x​f(x) x is smooth point

∂ x ∣ x ∣ = x = { 1 x > 0 [ − 1 , 1 ] x = 0 − 1 x < 0 \partial_x|x| = x = \begin{cases} 1 & x>0 \\ [-1,1] &x = 0\\ -1& x<0 \end{cases} ∂x​∣x∣=x=⎩⎪⎨⎪⎧​1[−1,1]−1​x>0x=0x<0​

3.2.3 基于凸优化理论求解L1正则化

  因为绝对值函数是个凸函数，因此我们可以利用凸优化理论去求解L1正则化。我们假设x₀是凸函数的最小值，那么0必定存在于这个点的次梯度中

f(x) is convex x 0 = a r g m i n f ( x ) ⇒ 0 ∈ ∂ x f ( x 0 ) \text{f(x) is convex} \quad x_0 = argminf(x) \Rightarrow 0 \in \partial_x f(x_0) f(x) is convexx0​=argminf(x)⇒0∈∂x​f(x0​)

  因此，我们只需要求一下目标函数的次梯度，让0落在次梯度区间里面就行。这里我们用一种简化方式进行求解，仅仅表示一下意思

∂ w k ( ∑ i = 1 n ( Y i − ∑ j = 1 N Z i j ω j ) 2 + λ ∑ i = 1 N ∣ ω i ∣ ) = ∂ w k ( ( A k + B k ω k + C k ω k 2 ) + λ ∑ i = 1 N ∣ ω i ∣ ) = B k + 2 C k ω k 2 + λ ∂ w k ∣ ω k ∣ = { B k + 2 C k ω k 2 + λ ω k > 0 [ B k + 2 C k ω k 2 − λ , B k + 2 C k ω k 2 + λ ] ω k = 0 B k + 2 C k ω k 2 − λ ω k < 0 \partial_{w_k}(\sum_{i=1}^n(Y_i - \sum_{j=1}^NZ_{ij}\omega_j)^2 + \lambda \sum_{i=1}^N |\omega_i|) \\ = \partial_{w_k}((A_k+B_k\omega_k+C_k\omega_k^2)+\lambda \sum_{i=1}^{N}|\omega_i|) \\ = B_k + 2C_k \omega_k^2 + \lambda \partial_{w_k}|\omega_k| \\ = \begin{cases} B_k + 2C_k \omega_k^2 + \lambda & \omega_k>0 \\ [B_k + 2C_k \omega_k^2 - \lambda, B_k + 2C_k \omega_k^2 + \lambda] &\omega_k = 0\\ B_k + 2C_k \omega_k^2 - \lambda& \omega_k<0 \end{cases} ∂wk​​(i=1∑n​(Yi​−j=1∑N​Zij​ωj​)2+λi=1∑N​∣ωi​∣)=∂wk​​((Ak​+Bk​ωk​+Ck​ωk2​)+λi=1∑N​∣ωi​∣)=Bk​+2Ck​ωk2​+λ∂wk​​∣ωk​∣=⎩⎪⎨⎪⎧​Bk​+2Ck​ωk2​+λ[Bk​+2Ck​ωk2​−λ,Bk​+2Ck​ωk2​+λ]Bk​+2Ck​ωk2​−λ​ωk​>0ωk​=0ωk​<0​

  因为中间的条件是ω_k=0,所以可以继续消项

{ B k + 2 C k ω k 2 + λ ω k > 0 [ B k − λ , B k + λ ] ω k = 0 B k + 2 C k ω k 2 − λ ω k < 0 \begin{cases} B_k + 2C_k \omega_k^2 + \lambda & \omega_k>0 \\ [B_k - \lambda, B_k + \lambda] &\omega_k = 0\\ B_k + 2C_k \omega_k^2 - \lambda& \omega_k<0 \end{cases} ⎩⎪⎨⎪⎧​Bk​+2Ck​ωk2​+λ[Bk​−λ,Bk​+λ]Bk​+2Ck​ωk2​−λ​ωk​>0ωk​=0ωk​<0​

  我们只需要让0处于在解集中即可,分别让三个梯度区间等于0

B k + 2 C k ω k 2 + λ = 0 ⇒ ω k = − B k + λ 2 ∗ C k B k + 2 C k ω k 2 − λ = 0 ⇒ ω k = B k + λ 2 ∗ C k 0 ∈ [ B k − λ , B k + λ ] B_k + 2C_k \omega_k^2 + \lambda =0 \Rightarrow \omega_k = -\frac{B_k +\lambda}{2*C_k} \\ B_k + 2C_k \omega_k^2 - \lambda =0 \Rightarrow \omega_k = \frac{B_k +\lambda}{2*C_k}\\ 0 \in [B_k - \lambda, B_k + \lambda] Bk​+2Ck​ωk2​+λ=0⇒ωk​=−2∗Ck​Bk​+λ​Bk​+2Ck​ωk2​−λ=0⇒ωk​=2∗Ck​Bk​+λ​0∈[Bk​−λ,Bk​+λ]