精华内容
下载资源
问答
  • Sparsity constraint稀疏约束详解
    千次阅读
    2017-11-21 20:40:22

    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 

    更多相关内容
  • 具有稀疏约束的增量非负矩阵分解用于图像表示 此repo实现了由Jing Sun等人针对“具有稀疏约束的增量非负矩阵分解进行图像表示的性能”所提出的特征提取算法的迭代更新过程。此代码对人脸(ORL-32)和对象( COIL20)...
  • 基于稀疏约束的鬼成像光谱相机, 能够通过单次曝光获得目标场景的三维空间光谱数据立方体。但是由于不同波长的散斑场在探测器的同一位置处, 使得仪器的光谱分辨率和信噪比受到限制。为了解决上述问题, 提出了利用平场...
  • 非负矩阵分解是处理高维数据的一种常用方法,对带有稀疏约束的非负矩阵分解算法进行了研究,提出了一种在曼哈顿距离最接近的向量稀疏化算法,并与欧几里得距离最接近的向量稀疏化进行对比,提出的稀疏化算法具有较快的...
  • 稀疏约束程序软件包

    2018-09-05 11:32:11
    压缩包里面有关于稀疏软件的程序包,里面包含三种软件包 已经文章
  • 一种含有反射系数稀疏约束的多组变异差分进化算法及其在波阻抗反演中的应用,高照奇,潘志斌,针对地震波阻抗反演是一类非线性反演问题以及地层反射系数往往具有稀疏特性,基于一种全局优化算法--多组变异差分进化...
  • 具有稀疏约束(SGNMF)的图正则化非负矩阵分解 该MATLAB软件包实现了具有图拉普拉斯正则化和稀疏约束的NMF算法。 GNMF的实现来自“流形上的非负矩阵分解”。 稀疏正则化已添加到原始实现中。
  • 用于图像表示的L3 / 2稀疏约束图非负矩阵分解
  • 本文提出了一种稀疏约束的改进思路,在计算重构误差的表达式后面添加L1范数的惩罚性约束,促使最优重构权值矩阵更具有稀疏性,从而增强算法的稳定性。文中首先通过正则化处理,把添加了稀疏约束的重构误差最优化目标...
  • 针对传统的宽带MVDR自适应串行形成,抑制干扰的同时会抬高高旁瓣重叠,并且过多的线性约束会导致分割输出的SINR性能下降的问题,提出了一种基于SRV约束和稀疏约束的方法该方法在窄带MVDR自适应层叠形成基础上,通过...
  • 针对Capon波束成形器旁瓣较高及零陷不深的问题,对降低旁瓣及零陷的方法进行了研究,提出了一种加权稀疏约束Capon波束成形算法。首先利用旁瓣阵列流型矩阵与协方差矩阵的相关运算,得到干扰和噪声能量在不同方向的...
  • 融合空间信息的基于稀疏约束的非负矩阵分解的高光谱图像自适应端元提取,李华丽,李登刚,本文针对高光谱图像处理中端元个数难得精确估计和端元的可变性的问题,提出了一种融合空间信息的基于稀疏约束的非负矩阵分解...
  • 文中选用深度学习中的SegNet语义分割模型进行算法改进,提出了一种基于稀疏约束SegNet的高分辨率遥感影像建筑 物提取算法。首先对SegNet模型加入正则项和Dropout,大大降低了模型过拟合现象的发生;其 次为了模型...
  • 通过增加L1范数,提出了一种稀疏约束的改进方法对重构误差函数的惩罚约束,最优重构权矩阵可以稀疏。 首先,通过正则化将添加了稀疏约束的重构误差函数转换为一般的二次规划问题,然后使用内点迭代方法快速搜索最优...
  • 为此,提出一种基于稀疏约束的改进算法,在计算重构误差的表达式后添加L1范数的惩罚性约束,促使最优重构权值矩阵更具有稀疏性。通过正则化处理,把添加稀疏约束的重构误差最优化目标函数变换成一般二次规划问题,...
  • 稀疏正则化函数的选取直接影响到稀疏非负矩阵分解高光谱解混的效果。目前,主要采用 L0.或 L1 范数作为稀疏度量。L0 稀疏性好,但求解困难;L1 求解方便,但稀疏性差。提出一种近似稀疏模.型,并将其引入到多层非负...
  • 为了选择有效的图像特征,并将这些特征融合以进行图像的显著区域检测,提出一种基于图像特征稀疏约束的显著性检测算法。该算法首先建立一个包括多种图像特征的特征池,之后假设图像的显著图由特征池中特征的线性组合...
  • 使用稀疏约束非负矩阵分解算法的跨年龄人脸识别.pdf
  • 平面约束CT变分稀疏约束的环形伪影校正方法
  • 在图像重建阶段,可以通过输入低分辨率图像稀疏系数的映射函数来计算高分辨率图像的稀疏系数。 为了消除初始高分辨率图像图像边缘的不规则性,基于人脸图像的自相似特性提出了一种优化过程。 实验结果表明,该算法...
  • 高光谱解混的稀疏约束广义双线性模型
  • 将Lorentz函数引入到RBM中,作为RBM的稀疏约束正则项,构建基于Lorentz函数的稀疏约束RBM模型,将其称之为LRBM模型。对该模型的特征提取性能进行了可视化评价,同时对稀疏度和分类率进行了实验分析;最后将多个LRBM...
  • 稀疏约束的嵌入式模糊均值聚类算法.pdf
  • 基于非凸低秩稀疏约束的鲁棒人脸识别算法.pdf
  • 大数据-算法
  • 行业分类-设备装置-基于部分稀疏约束非负矩阵分解的视频运动特征提取方法.zip
  • 基于稀疏约束非负矩阵分解的K-Means聚类算法.pdf
  • 稀疏约束和噪声群测试的快速分裂算法_Fast Splitting Algorithms for Sparsity-Constrained and Noisy Group Testing.pdf

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,066
精华内容 10,026
关键字:

稀疏约束