图解机器学习/第五章 稀疏学习

$l_1$约束的最小二乘学习法

$$\mathop{min}_{\theta}J_{LS}(\theta) \quad 约束条件 \quad ||\theta||_1 \le R \\ ||\theta||_1 = \sum_{j=1}^b|\theta_j|$$

 $l_1$约束的最小二乘学习法，在有些著作中也成为Lasso回归。

$l_1$约束的最小二乘学习的求解方法

 因为$l_1$范数中包含在原点处不能微分的绝对值，因此不能像$l_2$约束那样简单地进行求解。近年来产生了许多求解$l_1$约束的最小二乘学习法的算法，特别是当参数b使非常大的数值的时候，$l_1$约束的最小二乘学习法可以获得比$l_2$约束的最小二乘学习法更高的求解速度。

 使用由$l_1$约束的上限$R$决定的拉格朗日乘子$\lambda$，来考虑最优化问题：

$$\mathop{min}_{\theta}J(\theta),J(\theta)=J_{LS}(\theta)+\lambda||\theta||_1$$

另外，对于$l_1$范数中包含的不能进行微分的绝对值函数，使用可以微分的二次函数进行控制

$$|\theta_j| \le \frac{\theta_j^2}{2c_j} + \frac{c_j}{2}对于c_j >0$$

上述的二次函数就是该绝对值函数的上界，与绝对值函数在点$\theta_j = ±c_j$处相切。

 通过反复迭代来对其进行求解，可以用现在的解$|\tilde{\theta_j}| \not= 0$来替换$c_j$，以构成上界约束

$$|\theta_j| \le \frac{\theta_j^2}{2|\tilde{\theta_j}|} + \frac{|\tilde{\theta_j}|}{2}$$

据此可以得到$l_2$正则化最小二乘学习法的一般表达式

$$\hat{\theta}=\mathop{argmin}_{\theta} \tilde{J}(\theta),\tilde{J}(\theta) = J_{LS}(\theta)+ \frac{\lambda}{2}\theta^{\intercal}\tilde{\Theta}^{\dagger}\theta+C$$

上式中，$\tilde{\Theta}$是对角元素为$|\tilde{\theta_1}|,\dots,|\tilde{\theta_b}|$的对角矩阵，$C=\sum_{j=1}^b|\tilde{\theta_1}|/2$是不依赖于$\theta$的常数。

• 使用一般$l_2$约束的最小二乘学习法求解$l_1$约束的最小二乘学习法的迭代方法

1. 给初始值$\theta$以适当的值

2. 通过现在的解$\theta$来计算矩阵$\Theta$

   $$\Theta \leftarrow diag(|\theta_1|,\dots,|\theta_b|)$$

   其中，$diag(a,b,\dots,c)$是以$a,b,\dots,c$为对角元素的对角矩阵

3. 使用矩阵$\Theta$来计算解$\theta$

   $$\theta \leftarrow (\Phi^{\intercal}\Phi+\lambda\Theta^{\dagger})^{-1}\Theta^{\intercal}y$$

4. 直到解$\theta$达到收敛精度为止，重复上述2、3步的计算

通过稀疏学习进行特征选择

 使用$l_1$约束的稀疏学习进行特征选择，可以在一定程度上考虑到各个特征之间的相互联系。

$l_p$约束的最小二乘学习法

 $p \ge 0$的$l_p$范数的约束方法

$$||\theta||_p = (\sum_{j=1}^b|\theta_j|^p)^{\frac{1}{p}} \le R$$

但是，当$p=\infty$的时候

$$||\theta||_{\infty} = max \lbrace|\theta_1|,\dots,|\theta_b| \rbrace$$

因此，$l_{\infty}$范数表示的是向量元素绝对值中的最大值，$l_{\infty}$范数也成为最大值范数。$l_0$范数表示的是非零的向量元素个数。

在坐标轴上呈有峰值的尖形是存在稀疏解的秘诀，满足约束条件的空间如果不是凸形的话，可能存在局部最优解。当$p=1$时，稀疏解存在唯一的凸形，由此可知，$l_1$约束的最小二乘学习法是非常特殊的一种学习方法。

$l_1+l_2$约束的最小二乘学习法

 通过利用$l_1+l_2$范数的凸结合来进行约束

$$(1-\tau)||\theta||_1 + \tau||\theta||^2 \le R$$

 $l_1+l_2$约束的最小二乘学习法，也成为弹性网回归学习法。