简谈L0,L1和L2

L1和L2是ml中常用的惩罚系数,虽然L0不是,但是既然有L1,L2了,也带上L0。我们在这里主要说一说L0,L1,L2的具体作用。

L0

形式

n范数的可以用公式 ${|x|}_p = {(\sum_i x_i^p)}^{1/p}$ 定义。当然了,对于L0来说,这个定义就有些尴尬了。当然,万能的数学家自然不可能让这种拦住,所以他们对L0定义为x中非0元素的个数。

问题

我们可以看到L0这种范数天生适用于稀疏表示。但是它到现在默默无闻的原因就是因为太难求解了,据说是NP问题。反正以我的智商连暴力求解都不知道怎么求。。。。。

L1

形式

上面已经说过n范数的定义了,放到L1这里就是绝对值。

稀疏表示

L1范式可以做到参数的稀疏表示。在这里针对一种简单的情况进行数学证明(以下证明参考博客)。
我们对线性规划进行求解。也就是说损失函数为:
$$
J(w)=\frac{1}{n}|y-w^TX|^2
$$
加上L1惩罚系数后,目标函数为
$$
J_L(w)=\frac{1}{n}|y-w^TX|^2 + \lambda |w|
$$
在这里,X是正交矩阵,即 $\frac{1}{n} X^TX=I$
我们注意到上面的函数是凸函数,但是由于L1不连续,所以无法通过求导求解。因此在这里引入subgradient的概念

对于在p维欧氏空间中的凸开子集U上定义的实值函数 $f:U \to \mathbb{R}$,一个p维向量v称为f在一点 $x_0 \in U$ 处的subgradient,如果对于任意 $x \in U$,满足 $f(x)-f(x_0)\ge v(x-x_0)$,由在点 $x_0$ 处的所有 subgradient 所组成的集合称为 $x_0$ 处的 subdifferential ,记为 $\partial f(x_0)$

举个例子说明一下。例如当 $f(x)=|x|$,它在x=0处的subdifferential为[-1,1]。这是对传统gradient的一个推广。这种推广有一个很好的性质:当 $0 \in \partial f(x_0)$ 时, $x_0$ 是f的最小值。

虽然无法对 $J_L(w)$ 求导得到解析解,但是我们仍然可以求导:
$$
\dfrac{\partial J_L(w)}{\partial w} = -\frac{2}{n}X(y-{w}^TX) + \lambda sign(w)=0
$$

上式中的sign(w)可以认为是对w各个分量进行sign后得到的矩阵
同时我们可以求出原问题(即不加L1惩罚系数的函数)的解析解
$$
\hat{w}=\frac{1}{n}{(XX^T)}^{-1}X^Ty=X^Ty
$$

令 $\bar{w}$ 为 $J_L(w)$ 最小值的解析解。则我们可以发现:
$$
\bar{w} = \hat{w}-\frac{\lambda}{2}sign(\bar{w})
$$

上式可以发现 $\bar{w}$ 和 $\hat{w}$ 的每个分量符号相同,即 $sign(\bar{w}) = sign(\hat{w})$ 。故上式可化为:
$$
\bar{w}_j = \hat{w}_j-\frac{\lambda}{2}{sign(\hat{w})}_j={sign(\hat{w})}_j({|\hat{w}|}_j-\frac{\lambda}{2})
$$

上式中j下表表示向量中第j个分量。公式两边同时乘以 ${sign(\hat{w})}_j$ ,可得:
$$\begin{aligned} {sign(\hat{w})}_j\bar{w}_j &= {sign(\bar{w})}_j\bar{w}_j = {|\bar{w}|}_j\\ &={sign(\hat{w})}_j^2({|\hat{w}|}_j-\frac{\lambda}{2}) = {|\hat{w}|}_j-\frac{\lambda}{2} \end{aligned}$$


$$
\begin{equation}
{|\bar{w}|}_j={|\hat{w}|}_j-\dfrac{\lambda}{2} \ge 0
\end{equation}
$$

故上式可以表示为:
$$\bar{w}_j = {sign(\hat{w})}_j{\big({|\hat{w}|}_j-\frac{\lambda}{2}\big)}_+\\ {(x)}_+ = max(x,0)$$

根据subgradient求最小值的性质,我们可以发现:
$$\begin{aligned} 0&=\bar{w}_j \in \left\{-\frac{2}{n}{(Xy-XX^Tw)}_j + \lambda e | e \in [-1, 1]\right\} \\ &=\left\{2\bar{w}_j-2\hat{w}_j + \lambda e | e \in [-1, 1]\right\} \end{aligned}$$

也就说存在 $e_0 \in [-1,1]$ ,使得
$$
0 = 2\bar{w}_j-2\hat{w}_j + \lambda e_0 = 2\bar{w}_j + \lambda e_0
$$

由上式可得 $|\bar{w}_j| = \dfrac{\lambda}{2} |e_0| \le \dfrac{\lambda}{2}$。

当然我们用前面的式子也可以表示( ${|\bar{w}|}_j={|\hat{w}|}_j-\dfrac{\lambda}{2} \ge 0$ 妈蛋为啥hexo-math不支持公式编号。。。。还得再打一遍)。

在这种情况下我们可以发现L1其实是对原来解的一个截断。当然我们也可以求出L2惩罚系数的解:
$$
w^*= {(XX^T-2\lambda I)}^{-1}Xy=\frac{1}{1-2\lambda}\bar{w}
$$

也就是说L2相当于对原来解的缩放

优化求解

L0的求解是NP问题,L1相对来说就好的多。我们将L1的求导抽象为如下数学问题:
$$
\min_\theta(J(\theta)+\lambda|\theta|)
$$

我们将不等式 $|ab| \le \dfrac{1}{2}(a^2 + b^2)$ 应用到 $\theta$ 的每个分量中:
$$
|\theta_j| \le \dfrac{1}{2}(\dfrac{\theta_j^2}{c_j}+c_j), c_j > 0
$$

则有:
$$
|\theta| \le \dfrac{1}{2}(\theta^TC^{-1}\theta+C)
$$

其中 $C=diag(c)$,即C是对角值为 $c_j$的对角矩阵。当 $|\theta|=c$ 时,等号成立。
故我们可以通过最小化
$$
\tilde{F}(\theta,c)=J(\theta) + \dfrac{\lambda}{2}(\theta^TC^{-1}\theta+C)
$$

来优化 $F(\theta)$ 。
不过由于只有当$|\theta|=c$时等号才严格成立,因此我们无法使用直接求导的方式求出解析解。但是这种场景很像混合高斯模型的情况,因此我们可以用EM去求解。具体求解算法如下:

  1. 选择初始参数\theta^{(0)}
  2. 对于第k次迭代,使用下式更新\theta:

    $\theta^{(k)} = arg \min_\theta \tilde{F}(\theta,|\theta^{(k-1)}|) = arg \min_\theta J(\theta) + \dfrac{\lambda}{2}(\theta^T|\theta^{(k-1)}|^\dagger\theta+C)$

    其中 $|\theta^{(k-1)}|^\dagger$ 为 $|\theta^{(k-1)}|$ 的伪逆,是为了防止 $\theta^{(k-1)}$ 出现0元素导致秩低于矩阵维度因此不可逆。 伪逆的计算公式为: $X^\dagger = {(XX^T)}^{-1}X^T$ 。对于对角矩阵,可以简化为下式:

    $$X_j^\dagger = \begin{cases} 0 & \text{x=0}\\ X_j^{-1}& \text{x!=0} \end{cases}$$

重复上述步骤直到收敛即可。

由于有 $F(\theta^{(k-1)}) = \tilde{F}(\theta^{(k-1)},|\theta^{(k-1)}|) \ge \tilde{F}(\theta^{(k)},|\theta^{(k-1)}|) \ge F(\theta^{(k)})$,所以上面的函数单调递减,这样必然可以求出最优解(感觉和NMF的求解略相似)

L1的部分就到此为止了,感觉基本应该都涵盖到了。以后如果还有,再补充吧

L2

像L2这种不傲娇,还一身宝的东西有相当广泛的应用。目前好像还没有看到关于L2的负面评价

形式

不多说了,2范式

好处

L2的好处都有啥,谁说对了就给他

机器学习

从ml的角度来看,主要是提高模型的泛化能力,降低过拟合

数值优化

从数值优化的角度来看,L2可以处理condition number较高的情况。我们先来看看什么叫condition number

在介绍condition number之前,我们先引入ill-conditioned的概念。
现在有一线性系统Ax=b,其中
$A=\begin{bmatrix}400& -201\\-800& 401\end{bmatrix},b=\begin{bmatrix}200\\-200\end{bmatrix}$
我们可以得到解[-100,-200]。但是如果我们将A中的400变成401再求解,解就是[40000,79800]。也就是说x对A和b高度敏感。

玩数学的当然不会止步于此。在ill-conditioned出现之后,就需要一种机制判断一个系统是否为ill-conditioned

在这里我们引入矩阵范数进行处理。这里的矩阵范数必须满足一致性,即 $|A||B| \ge |AB|$
在此条件下,有下式成立:
$$\begin{aligned} &A(x+\Delta x) = b + \Delta b\\ \Rightarrow &A\Delta x = \Delta b\\ \Rightarrow &\Delta x = A^{-1}\Delta b\\ \Rightarrow &\|\Delta x\| \le \|A^{-1}\|\|\Delta b\| \end{aligned}$$

同时由于 $|A||x| \ge |b|$,我们可得:
$$
\begin{aligned}
&\dfrac{|\Delta x|}{|A||x|} \le \dfrac{|A^{-1}||\Delta b|}{|x|}\
\Rightarrow & \dfrac{|\Delta x|}{|x|} \le |A||A^{-1}|\dfrac{|\Delta b|}{|b|}
\end{aligned}
$$

我们将 $|A||A^{-1}|$ 称为condition number。它表征了当A或b变化时,x变化的上界。所以如果condition number远远大于1,那么它就是ill-conditioned。

当然上面只描述了线性系统,对于非线性系统来说,condition number可以用 $\dfrac{|J(x)|}{|f(x)|/|x|}$ 来计算,其中J(x)为雅各布矩阵,即f(x)的一阶偏导

那么L2对于ill-conditioned问题的解决帮助在哪?首先我们在L1中给出了线性回归的解析解: $w=(XX^T)^{−1}X^Ty$ 。但是如果X的行数小于列数,那么 $XX^T$ 就不会满秩。这样会导致方程组有无穷多个解。如果你随便挑一个,那么八成你会过拟合。如果我们加上L2,解会变成 $w^*= {(XX^T-2\lambda I)}^{-1}Xy$ 。这样的情况下就不用担心不满秩的问题了。

同时L2还可以加快迭代速度。这一点我们可以直观的从condition number的非线性定义中直观的看到。条件数越小,收敛速度越快。