lasso族(套索算法)
    学习资料:http://blog.csdn.net/godenlove007/article/details/11387977

    1.lasso族的功效
    在建立模型之初,为了尽量减小因缺少重要自变量而出现的模型偏差,通常会选择尽可能多的自变量。然而,建模过程需要寻找对因变量最具有强解释力的自变量集合,也就是通过自变量选择(指标选择、字段选择)来提高模型的解释性和预测精度。指标选择在统计建模过程中是极其重要的问题。Lasso算法则是一种能够实现指标集合精简的估计方法。

    Lasso(Least absolute shrinkage and selection operator, Tibshirani(1996))方法是一种压缩估计。它通过构造一个罚函数得到一个较为精炼的模型,使得它压缩一些系数,同时设定一些系数为零。因此保留了子集收缩的优点,是一种处理具有复共线性数据的有偏估计。

    Lasso 的基本思想是在回归系数的绝对值之和小于一个常数的约束条件下,使残差平方和最小化,从而能够产生某些严格等于0 的回归系数,得到可以解释的模型。
    R的Lars 算法的软件包提供了Lasso编程,我们根据模型改进的需要,可以给出Lasso算法,并利用AIC准则和BIC准则给统计模型的变量做一个截断,进而达到降维的目的。因此,我们通过研究Lasso可以将其更好的应用到变量选择中去。[]
    lasso estimate具有shrinkage和selection两种功能,shrinkage这个不用多讲,本科期间学过回归分析的同学应该都知道岭估计会有shrinkage的功效,lasso也同样。关于selection功能,Tibshirani提出,当t值小到一定程度的时候,lasso estimate会使得某些回归系数的估值是0,这确实是起到了变量选择的作用。当t不断增大时,选入回归模型的变量会逐渐增多,当t增大到某个值时,所有变量都入选了回归模型,这个时候得到的回归模型的系数是通常意义下的最小二乘估计。从这个角度上来看,lasso也可以看做是一种逐步回归的过程。[]
    模型选择本质上是寻求模型稀疏表达的过程,而这种过程可以通过优化一个“损失”十“惩罚”的函数问题来完成。
    2、与普通最小二乘法的区别
    使用最小二乘法拟合的普通线性回归是数据建模的基本方法。其建模要点在于误差项一般要求独立同分布(常假定为正态)零均值。t检验用来检验拟合的模型系数的显著性,F检验用来检验模型的显著性(方差分析)。如果正态性不成立,t检验和F检验就没有意义。
    对较复杂的数据建模(比如文本分类,图像去噪或者基因组研究)的时候,普通线性回归会有一些问题:
    (1)预测精度的问题 如果响应变量和预测变量之间有比较明显的线性关系,最小二乘回归会有很小的偏倚,特别是如果观测数量n远大于预测变量p时,最小二乘回归也会有较小的方差。但是如果n和p比较接近,则容易产生过拟合;如果n
    (2)模型解释能力的问题 包括在一个多元线性回归模型里的很多变量可能是和响应变量无关的;也有可能产生多重共线性的现象:即多个预测变量之间明显相关。这些情况都会增加模型的复杂程度,削弱模型的解释能力。这时候需要进行变量选择(特征选择)。
    针对OLS的问题,在变量选择方面有三种扩展的方法: (1)子集选择 这是传统的方法,包括逐步回归和最优子集法等,对可能的部分子集拟合线性模型,利用判别准则 (如AIC,BIC,Cp,调整R2 等)决定最优的模型。 (2)收缩方法(shrinkage method) 收缩方法又称为正则化(regularization)。主要是岭回归(ridge regression)和lasso回归。通过对最小二乘估计加入罚约束,使某些系数的估计为0。 (3)维数缩减 主成分回归(PCR)和偏最小二乘回归(PLS)的方法。把p个预测变量投影到m维空间(m
    3、岭回归、lasso回归和elastic net三种正则化方法[]
    (1)岭回归[]
    最小二乘估计是最小化残差平方和(RSS):
    岭回归在最小化RSS的计算里加入了一个收缩惩罚项(正则化的l2范数)
    这个惩罚项中lambda大于等于0,是个调整参数。各个待估系数越小则惩罚项越小,因此惩罚项的加入有利于缩减待估参数接近于0。重点在于lambda的确定,可以使用交叉验证或者Cp准则。
    岭回归优于最小二乘回归的原因在于方差-偏倚选择。随着lambda的增大,模型方差减小而偏倚(轻微的)增加。
    岭回归的一个缺点:在建模时,同时引入p个预测变量,罚约束项可以收缩这些预测变量的待估系数接近0,但并非恰好是0(除非lambda为无穷大)。这个缺点对于模型精度影响不大,但给模型的解释造成了困难。这个缺点可以由lasso来克服。(所以岭回归虽然减少了模型的复杂度,并没有真正解决变量选择的问题)
    (2)lasso
    lasso是在RSS最小化的计算中加入一个l1范数作为罚约束:
    l1范数的好处是当lambda充分大时可以把某些待估系数精确地收缩到0。
    关于岭回归和lasso,在[3]里有一张图可以直观的比较([3]的第三章是个关于本文主题特别好的参考):[]
    关于岭回归和lasso当然也可以把它们看做一个以RSS为目标函数,以惩罚项为约束的优化问题。
    (3)调整参数lambda的确定
    交叉验证法。对lambda的格点值,进行交叉验证,选取交叉验证误差最小的lambda值。最后,按照得到的lambda值,用全部数据重新拟合模型即可。
    (4)elastic net
    elastic net融合了l1范数和l2范数两种正则化的方法,上面的岭回归和lasso回归都可以看做它的特例:
    elastic net对于p远大于n,或者严重的多重共线性情况有明显的效果。 对于elastic net,当alpha接近1时,elastic net表现很接近lasso,但去掉了由极端相关引起的退化化或者奇怪的表现。一般来说,elastic net是岭回归和lasso的很好的折中,当alpha从0变化到1,目标函数的稀疏解(系数为0的情况)也从0单调增加到lasso的稀疏解。
    LASSO的进一步扩展是和岭回归相结合,形成Elastic Net方法。[]
    (5)岭回归与lasso算法[]
    这两种方法的共同点在于,将解释变量的系数加入到Cost Function中,并对其进行最小化,本质上是对过多的参数实施了惩罚。而两种方法的区别在于惩罚函数不同。但这种微小的区别却使LASSO有很多优良的特质(可以同时选择和缩减参数)。下面的公式就是在线性模型中两种方法所对应的目标函数:
    公式中的lambda是重要的设置参数,它控制了惩罚的严厉程度,如果设置得过大,那么最后的模型参数均将趋于0,形成拟合不足。如果设置得过小,又会形成拟合过度。所以lambda的取值一般需要通过交叉检验来确定。
    岭回归的一个缺点:在建模时,同时引入p个预测变量,罚约束项可以收缩这些预测变量的待估系数接近0,但并非恰好是0(除非lambda为无穷大)。这个缺点对于模型精度影响不大,但给模型的解释造成了困难。这个缺点可以由lasso来克服。(所以岭回归虽然减少了模型的复杂度,并没有真正解决变量选择的问题)
    4、LARS算法对lasso的贡献[]
    LAR把Lasso (L1-norm regularization)和Boosting真正的联系起来,如同打通了任督二脉。LAR结束了一个晦涩的时代:在LAR之前,有关Sparsity的模型几乎都是一个黑箱,它们的数学性质(更不要谈古典的几何性质了)几乎都是缺失。
    近年来兴起的Compressed sensing(Candes & Tao, Donoho)也与LAR一脉相承,只是更加强调L1-norm regularization其他方面的数学性质,比如Exact Recovery。我觉得这是一个问题的多个方面,Lasso关注的是构建模型的准确性,Compressed sensing关注的是变量选择的准确性。
    5、变量选择
    当我们使用数据训练分类器的时候,很重要的一点就是要在过度拟合与拟合不足之间达成一个平衡。防止过度拟合的一种方法就是对模型的复杂度进行约束。模型中用到解释变量的个数是模型复杂度的一种体现。控制解释变量个数有很多方法,例如变量选择(feature selection),即用filter或wrapper方法提取解释变量的最佳子集。或是进行变量构造(feature construction),即将原始变量进行某种映射或转换,如主成分方法和因子分析。变量选择的方法是比较“硬”的方法,变量要么进入模型,要么不进入模型,只有0-1两种选择。但也有“软”的方法,也就是Regularization类方法,例如岭回归(Ridge Regression)和套索方法(LASSO:least absolute shrinkage and selection operator)。
    6、展望
    将Lasso应用于时间序列。将Lasso思想应用于AR(p)、ARMA(p)等模型,利用Lasso方法对AR(p)、ARMA(p)等模型中的变量选择,并给出具体的算法。
    将Lasso方法应用到高维图形的判别与选择以及应用于线性模型的变量选择中,以提高模型选择的准确性。
    二、文献综述
    在做LASSO,他们都是大牛,你可以直接GOOGLE他们的主页,看他们在这块发了什么文章。yu bin, zhu ji, zhang tong, hui zou, yuan ming, Nicolai Meinshausen, Peter Bühlmann, Martin J. Wainwright, jianqing fan, Liza Levina, Peter Bickel,Tibshirani(Lasso的提出者)。
    三、R语言包——glmnet和lars
    1、glmnet包与算法
    glmnet包是关于Lasso and elastic-net regularized generalized linear models。 作者是Friedman, J., Hastie, T. and Tibshirani, R这三位。
    这个包采用的算法是循环坐标下降法(cyclical coordinate descent),处理的模型包括 linear regression,logistic and multinomial regression models, poisson regression 和 the Cox model,用到的正则化方法就是l1范数(lasso)、l2范数(岭回归)和它们的混合 (elastic net)。
    坐标下降法是关于lasso的一种快速计算方法(是目前关于lasso最快的计算方法),其基本要点为: 对每一个参数在保持其它参数固定的情况下进行优化,循环,直到系数稳定为止。这个计算是在lambda的格点值上进行的。 关于这个算法见[5][]。 关于glmnet包的细节可参考[4],这篇文献同时也是关于lasso的一个不错的文献导读。[]
    cv.glmnet函数利用交叉检验,分别用不同的lambda值来观察模型误差。
    左边线对应最佳lamda,右侧线对应一个SE内最佳模型。上图横轴是lambda值的对数,纵轴是模型误差。从上面的图可以看到,最佳的lambda取值就是在红色曲线的最低点处,对应着变量个数是11个。它右侧的另一条虚线是在其一倍SE内的更简洁的模型(变量个数为9)。由于这两个lambda对应的模型误差变化不大,而我们更偏好于简洁的模型,选择对应的lambda值为0.025。
    案例1:prostate在ESL的主页有下载,
    http://site.douban.com/182577/widget/notes/10567212/note/289294468/
    案例2:数据集是Machine Learning公开课中第七课的一个算例,http://www.zilhua.com/727.html
    2、LARS算法包
    吴喜之老师《复杂数据统计方法》p29。第一种方案采用lars包(吴老师书里的方法,细节略有修正)。这个包的方法包括:Least Angle Regression, Lasso 和 Forward Stagewise,作者是两位大牛:Trevor Hastie和 Brad Efron。[]

    在不同步数下,系数增减的情况,最左边的只有截距,最右边是保持所有变量。lasso回归系数随参数的变化(系数变量并不是连续的)
    cv的变化图,在什么时候达到最小。
    四、参考文献
    [1] Jun Liu. Large-Scale Sparse Logistic Regression[J].KDD’09.
    [2] Hui Zou and Runze Li. One-step sparse estimates in nonconxave penalized[J].The Annals of Statistics,2008,11.
    [3] Tibshirani,R.Regression Shrinkage and Selection Via the Lasso[J].Journal of the Royal Statical Society.Series B.58,267-288.
    [4] Wang Zhanfeng. A LASSO-Type Approach to Variable Selection and Estimation for Censored Regression Model[J].2010,02.
    [5] 邱南南.基于Lasso 改进的一般因果关系检验[J].统计与信息论坛,2008,02.
    [6] 赵婷婷.AR(p)模型的Lasso方法定阶[D].东北师范大学硕士论文,2008,05.
    [7] 宋国栋.线性不等式约束下的变量选择[D].东北师范大学硕士论文,2007,05.
    [8] 孙丽丽.工具变量回归模型中的变量选择[D].东北师范大学硕士论文,2008,05.
    [9] 刘小明.数据降维及分类中的流行学习研究[J].浙江大学博士学位论文,2007,4.
    [10] 杨威.函数型回归模型的成分选取[D].东北师范大学硕士论文,2009,05.