LARS算法简介

最近临时抱佛脚,为了讨论班报告Group Regression方面的文章,研究了Efron等人于2004年发表在Annals of Statistics里一篇被讨论的文章LEAST ANGLE REGRESSION。这篇文章很长,有45页。加上后面一些模型方面大牛的讨论的文章,一共有93页。对于这种超长论文,我向来敬畏。后来因为要报告的文章里很多东西都看不懂,才回过头来研读这篇基石性的文章。

所谓大牛,就是他能提出一种别人从来没有提出过的想法。大牛们看待问题的角度和常人不同。比如在回归中常用的逐步回归法。我们小辈们只知道向前回归,向后回归还有二者结合的一些最基本的想法。比如向前回归,就是先选择和响应最相关的变量,进行最小二乘回归。然后在这个模型的基础上,再选择和此时残差相关度最高的(也就是相关度次高)的变量,加入模型重新最小二乘回归。之后再如法继续,直到在某些度量模型的最优性准则之下达到最优,从而选取一个最优的变量子集进行回归分析,得到的模型是相比原模型更加简便,更易于解释的。这种方法,牺牲了模型准确性(预测有偏),但是提高了模型的精确度(方差变小)。大多数本科生对逐步回归的理解也就如此了。Efron看待这个问题时,比起常人更高了一个层次。他首先指出,逐步向前回归,有可能在第二步挑选变量的时候去掉和X1相关的,但是也很重要的解释变量。这是因为它每次找到变量,前进的步伐都太大了,侵略性太强。

因此在这个基础上,Efron提出了Forward stagewise。也就是先找出和响应最相关的一个变量,找到第一个变量后不急于做最小二乘回归,而是在变量的solution path上一点一点的前进(所谓solution path是指一个方向,逐步回归是在这个方向上进行),每前进一点,都要计算一下当前的残差和原有的所有变量的相关系数,找出绝对值最大的相关系数对应的变量。我们可以想像,刚开始,前进的步伐很小,相关系数绝对值最大的对应的变量一定还是第一步选入的变量。但是随着前进的进程不断向前,这个相关系数的绝对值是在慢慢减小的,直到找到另外一个变量X2,它和当前前残差的相关系数和第一个入选变量X1的相关系数绝对值相同,并列第一。此时把X2也加入回归模型中,此时回归模型在X1上的系数已经确定了,如果在X1的solution path上继续前进,则得到的与当前残差相关系数最大的变量一定是X2,所以不再前进,而是改为在X2的solution path上前进,直到找到第三个变量X3,使得X3的与当前残差的相关系数绝对值最大。这样一步一步进行下去。每一步都是很多小步组成。直到某个模型判定准则生效,停止这个步骤。在每一个solution path上的计算都是线性的。总体的solution path是分段线性的。这种算法是一种自动进行模型构建的方法。它和传统的Forward selection在本质上是一样的,都是选择一个变量,然后选择一个继续进行的solution path,在该方向上前进。这两种方法的solution path的选择方法是一样的,唯一的区别就是前进的步伐不一样,Forward selection的前进步伐很大,一次到头,而stagewise则是一小步一小步前进。这样比Forward selection要谨慎一些,会免于漏掉一些重要的变量。

从这个视角来看,我们可以选择另外一种solution path。Efron等人在这篇文章中,就提出了一种新的solution path。在已经入选的变量中,寻找一个新的路径,使得在这个路径上前进时,当前残差与已入选变量的相关系数都是相同的。直到找出新的与当前残差相关系数最大的变量。从几何上来看,当前残差在那些已选入回归集的变量们所构成的空间中的投影,是这些变量的角平分线。下面我简单的描述一下这个算法:

  • 第一步,我们初始的估计模型为0,那么当前的残差就是Y,我们找出X’Y中绝对值最大的那个对应的变量,记为X1,把它加入回归模型。这一步中X’Y是当前残差和所有变量的相关系数向量。(注意这里Y都已经中心化,X中心标准化过了)。
  • 第二步,在已选的变量的solution path上前进,solution path就是s1*X1,s1是X1与当前残差的相关系数的符号。在这个path上前进,直到另外一个变量出现,使得X1与当前残差的相关系数与它和当前残差的相关系数相同。记这个变量为X2,把它加入回归模型中。
  • 第三步,找到新的solution path。Efron在文章中提出了一种找出满足LARS条件的solution path的解法。solution path需要使得已选入模型变量和当前残差的相关系数均相等。因此这样的路径选择它的方向很显然就是$X_k(X_k’X_k)^{-1}1$的指向(因为$X_k'(X_k(X_k’X_k)^{-1})1$的元素都相同,保证了LARS的要求,当然这里或许会有一些其他的解,也能满足LARS的要求,有没有达人能想到或许证明这个解是唯一的)。只要再标准化这个向量,我们便就找到了solution path的方向。在这个方向上前进,直到下一个满足与当前残差相关系数绝对值最大的变量出现。如此继续下去。

LARS算法,保证了所有入选回归模型的变量在solution path上前进的时候,与当前残差的相关系数都是一样的。这一点,比起Forward stagewise要捷径一些,走得更快一些。

LARS算法已经在SAS和R中实现了。作为回归模型选择的一种重要的算法,LARS相比起传统的Forward selection和Forward stagewise,既不那么富于侵略性,又比较走捷径。LARS算法在lasso 估计的求解中也有非常好的应用。在Efron等人的同篇论文中有详细的讨论。关于lasso和它的LARS算法,笔者将在今后的文章中介绍。

 

LARS算法简介》有32个想法

  1. 在没征求同意的情况下直接帮你修改了几个错别字。:)
    几点建议,可能会让没有接触过LARS的人更快理解它:
    1、可以对文中反复出现的solution path进行一些解释。普通的回归求解系数时都是“一步到位”的,而LARS中是一种“搜索”的思想,因此才会有路径的概念;
    2、可以对LARS的第三步再多一些解释,比如[latex]X_k[/latex]的含义,还有为什么“显然”等。可能是我一直比较迟钝,读论文的时候作者说显然成立的我一般都看不懂。:D

      1. 你好,我现在临时要用LARS分析一组数据,有个问题不明白,特来请教:
        Efron的论文中说变量之间要线性独立,这个条件是必须的吗。我的数据现在是
        各个变量之间存在较高的Pearson相关性,如果直接套用LARS,这种相关性对回归结果有什么影响?
        谢谢,期待得到回答

      2. 如果变量之间的想关心较高的话,Lars倾向于只选择这些相关变量中的一条变量,但是有些经济模型明知道,几个变量是相关的还是要加到模型中时,可以用Zou的elastic net来解决这个问题

  2. 我一直believe不必要的中文与English mixed up是writing的一大恶习,but太多太多people坚持to write like this,似乎already成为一种popular style。在你的article中大多数English words都可以replace为相应的Chinese词。你的opinion如何?

    BTW,文章是好文,赞之。

    1. 哈哈,你的建议我太赞同了。本人其实一直也有此看法,没想到自己写出来居然也成了这样。我已经把一些英文单词转为了中文。但是一些专有的名词我还是保留了比如solution path,一方面是感觉自己翻译的不太恰当,另外一方面我想可能对于读过原文的人来说,会有更加熟悉的感觉吧。
      ps:哈哈,谢大侠您真是太幽默了哈。

      1. 我松了一口气……我原来还有点担心我这样说是与广大人民群众为敌,因为我个人实在是受不了半中不英的写法,而这年头你放眼望去遍地都是这样的混血文字,我一直好奇难道这些打字的人不嫌输入法切换麻烦吗?要用哪种语言就好好用,没必要写得仿佛在异国他乡呆了很多年中文都讲不流利似的(口语也一样)。我感觉现在我们的写作能力在下降,这是不行滴,期待你在这里好好锻炼。

        solution path如果国内没有翻译的话,我觉得不妨译为“求解路径”;stepwise已经翻译为逐步,那么stagewise可译为逐段;当你引入一个别人不熟悉的新名词时,通常可以用括号标注一下相应的英文用词,这也是写作的常用习惯。

        跑题至此结束。

  3. 谢谢介绍!请问这是回归方法中比较新的进展么?看到有些文章中,先是回归一堆变量,然后去掉不相关的再回归,再继续。这里介绍的方法是不是常规方法的一种更好的改进呢?
    比较外行,请教各位!

    1. 你好,小本认为你所说的常规方法就是逐步回归,也就是stepwise,这里的LAR确实是比较好的一种“改进”方法,至少我听起来用类似向量夹角的方法,来选择最相关的变量或者因子来回归,确实比较有理。
      另外,stepwise似乎是每步都要做一次假设检验的。

  4. 我读起来很多中文词都费劲啊,还是比较prefer将一些基本概念的词保留英文的。BTW,这篇文章激起了让我想要去读一下这个93页论文的兴趣,估计也能醍醐灌顶的对model selection和regression有个更深层的认识。好文!虽然我还是没弄明白你的那个solution path的path是怎么回事

    1. 参见三楼的回复。若有不熟悉的词汇,可以翻译并用括号标注相应的英文。

      比如prefer写成“倾向于”又会怎样?BTW写成“另外”又如何?等等。真的不嫌中英文输入法切换麻烦吗?还是真的已经在异国他乡呆了半个世纪……

      本文若能激起读者对原文的兴趣,也是一种成功了。

      1. 看到了,我自己觉得语言的目的就是方便沟通,只要大家方便就好,我第一次留言,试一下水深而已,真没有别的意思。话说听说上次你来爱荷华城了

  5. 我看过原文,看得很晕,看了您的解说有了近一步的理解,请问lasso的解如何编程得到呢,解路径要怎样画出呢?请帮帮忙哦

  6. 你好,我是计算机专业的,数学基础不是很好,我现在临时要用LARS分析一组数据,有个问题不明白,特来请教:
    Efron的论文中说变量之间要线性独立,这个条件是必须的吗。我的数据现在是
    各个变量之间存在较高的Pearson相关性,如果直接套用LARS,这种相关性对回归结果有什么影响?
    谢谢,期待得到这里高手回答

  7. LZ,非常有幸这个版块看到你对LARS这一系列的理解,我有个疑问,在做lasso,在什么条件下的解是唯一的呢??因为我最近注意到当X1=X2时,lasso会产生不是唯一的解,请帮我解释一下可以吗?或者提供一下唯一解的条件的论文,可以吗??谢谢

  8. 我刚才的评论怎么没有了,楼主,你好,我想问下,lasso在什么条件的解是唯一的呢?最近看到当变量X1=X2时,会出现解不唯一的现象!

  9. 楼主的文章写的非常好,LARS的基本思想将的很清楚。Efron这篇文章我也拜读过几遍,但其间关于如何求solution path的方向以及步长,似乎并不透彻。楼主如果能结合几何特征讲解下这两个关键点就更好了:)

  10. “Efron提出了Forward stagewise”,这个是概念性错误。Forward Stagewise Regression 应该归功于Friedman,源于Gradient Boosting。LARS的几何意义可以结合凸优化来理解。

  11. 还想问几个问题,
    1、这些变量找出来以后再做一次最小二乘么?还只可以直接通过每一步得到的步长r算出来对应各个变量的系数改变量?已知在角分线ua上边的长度是r了,怎么确定其他边的步长呢?
    2、是不是应该每一步求得的步长r是越来越小的呢?我的结果乱七八糟的
    谢谢~

  12. 我个人实在是受不了翻译成中文的写法,比如当我看到最小二乘,愣了一下,看到响应,又愣了一下。。。

    1. 看到“最小二乘”能愣一下的话,要么你出国才学统计,要么你出国很多年了,因为在国内的统计教育里最小二乘是非常基础的词汇。

  13. 关于提到的“然而这里或许会有一些其他的解,也能满足LARS的要求,有没有达人能想到或许证明这个解是唯一的”,我是这样想的,因为这个solution path要在当前活跃集合所生成的空间中,所以这个解是唯一的,另一方面,因为投影向量和这个解的乘积还是这个解,所以也证明了这个解在当前活跃集合所生成的列空间中,所以证明了这个解是正确的。具体可以看我写的http://blog.csdn.net/u014664226/article/details/52240272

发表评论

邮箱地址不会被公开。 必填项已用*标注