Sparsity constraint稀疏约束详解

前端之家收集整理的这篇文章主要介绍了Sparsity constraint稀疏约束详解前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

Sparsity constraint稀疏约束详解

引子: 线性模型是我们经常使用的一种模型,比如:

文本分类中,bag-of-words 有p = 20 K 个特征, 共有 N = 5K 个文本样例;
在图像去模糊化,图像分类中,有p=65K 个像素点特征,N=100个样例;
等等

这些问题我们都可以使用线性模型解决,比如线性回归,logistic回归, Cox 回归来解决。 因为 p 远大于 N,所以必须引入正则化。
为什么这里要用正则化呢?
以我们很熟悉的线性回归模型为例:线性回归问题事实上是一个最小二乘问题( A least-squares problem),目标函数为:

,其中 是所要求的参数, 注:这里表述使用Convex Optimization book的描述,与通常的稍有不同,
事实上 x 相当于我们常说的参数 w

上式可以化为:

从而我们可以得到它的解析解:


看起来好像很简单,但是存在一个问题,我们在求最优解时,即最小化f(x)时,若Ax - b 是不可逆的,则求导且令导数为0后方程有无穷解。事实上我们求导置为0后
得到的就是一个线性等式的集合,利用我们学过的线性代数的知识,即求一个齐次线性方程组的解,当方程组数小于参数数量时,或者说线性方程组对应的系数矩阵的行
数小于列数时,有无穷多解。所以我们前面所说的p对应于系数矩阵的行,样本数对应于系数矩阵的列,所以此时无法求出最优解。而且此时也出现过拟合的问题。
其实在实际中我们经常遇到这种情况:变量数(样本维度)远大于样本数目的情况,样本数目太少不足以估计出所有的所要求的系数。
我们可以基于两个思路来考虑:
首先,如此多的参数(特征)是否都与我们要求的结果有关系呢,或者说是不是有些变量(特征)对我们结果并没有影响或影响非常小可以忽略不计;
另一方面来考虑,对参数w 我们可以求出无穷多解,这个解空间太大了,我们能不能给它一个约束,使解空间大大缩小,或者说在新的解空间里能够找到最优解。
通常的解决方法是:
(1) Forward stepwise
(2) Best-subset
(3) Ridge regression
(4) Lasso regression
其中(4)即用到了我们所要探究的稀疏约束,所以我们来看看Lasso regression 回归到底是什么:
其实就是对我们的模型加了这样一个约束条件:

即Lasso 是在线性模型上加了一个L1正则化项:


为了说明稀疏性,我们也来看下方法(3) Ridge regression:
它是对模型加了这样一个约束条件:

即Ridge 是在线性模型上加了一个L2正则化项:

Ridge 仅仅对变量进行了收缩(shrinkage),但是Lasso 既对变量进行了选择,也进行了收缩,如下图所示:

看上图,相交之处即所求解;看左图,圆很容易与约束区域的角相交,此时w1为0,对于一个更高维的情况,很可能有很多会有更多地
wi为0的情况,这也意味着我们对变量进行了选择,由此造成了稀疏性。而对于右图,在坐标轴上相交的概率会远小于前者,很难形成
稀疏性。

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

回顾一下L1 正则化的历史:
首先,David L. Donoho 和 Iain M. Johnstone 在1994年发表的论文”小波软阈值去噪“中首次使用了类似于L1的公式:
论文地址:http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=412133

随后1995年,Tibshirani 将Lasso 应用于回归问题中,而且给出了详细的解释,
论文地址:https://statweb.stanford.edu/~tibs/lasso/lasso.pdf

此后,Tibshirani 又将Lasso应用于几个其他的模型,如Logistics回归。

Donoho2004,CandesandTao2005 又将lasso应用于压缩感知之中。
---------------------------------------------------------------------------------------------------

很明显Eq.1是一个凸函数,存在最优解,但是注意到L1正则化项并不是可导的,亦即不可导的凸函数求最优解问题,该如何解决呢?目前主要有6种解决方法
(1)将不平滑问题转化为平滑问题
(2)坐标下降法 (coordinate descend)
(3)ADMM算法
(4)次梯度下降法(subgradient)
(5)梯度下降
(6)加速梯度下降

我们来看次梯度方法,次梯度的定义如下:

怎么理解次梯度呢?若 f(x) 是一个凸函数,且在x0 处可导 , 则由一阶泰勒展开式,可得:

若f(x) 在x0处 不可导,我们仍然可以得到f(x)的一个下界:

以下面的函数为例:


在x1 点 函数可导,此时次梯度与导数相同,只有一个;在x2点,函数不可导,此时次梯度不止有一个,次梯度的取值范围是一个闭区间。
由此我们求解的思路是:对于可导的地方,按照常规方法直接求导求解即可;对于不可导的地方,使用次梯度。下面来求目标函数Eq.1的最优解:

不考虑正则化项,由前面说过的最小二乘法,我们有:

简单起见,我们只考虑标准正交化的情况,即有:

将Eq.3 代入 Eq.2 可得:

假设 是 J(w) 的全局最优解, 考虑第 j 个 变量,存在两种可能:
(1)梯度存在时候,,我们有:

由Eq.5 可得:

将Eq.3 和 Eq.4 代入Eq.6 得:

sign是符号函数,易得和同号(假设符号后计算下即可证明),从而有
将Eq.8 代入 Eq.7 得:

在利用 Eq.8 ,然后两边同乘 ,可得:

由 Eq.10 和 Eq.9可得:

这里
(2)当梯度不存在时,即 时,有:

这里用到了一个性质:点x0 是凸函数 f 的一个全局最小值点,当且仅当 。(注:这里上式没有给出具体的迭代求解过程)。可得:

由Eq.13 得:

由此可得,Eq.14 同样满足Eq.11,于是两种情况都可以用Eq.11 表示,所以Eq.1的最优解可以使用Eq.11表示。


参考:
http://blog.csdn.net/lansatiankongxxc/article/details/46386341
http://freemind.pluskid.org/machine-learning/sparsity-and-some-basics-of-l1-regularization/#d20da8b6b2900b1772cb16581253a77032cec97e
ttps://web.stanford.edu/~hastie/TALKS/Sparsity.pdf

猜你在找的正则表达式相关文章