吴怀宇_中国科学院分享 http://blog.sciencenet.cn/u/wuhuaiyu 博士、副教授 「模式识别国家重点实验室」&「中国-欧洲信息,自动化与应用数学联合实验室」

博文

[CV论文读讲] LARS

已有 4151 次阅读 2012-11-30 14:31 |系统分类:科研笔记| 论文

Outline
Background: LSR, Lasso, Stagewise.
LAR Algorithm
LAR & Lasso
LAR & Stagewise
这是本次讲解的主要内容。首先阐述一些背景。LSR是Least Square Regression,LAR & Lasso, LAR & Stagewise是原文的核心内容。但是抱歉,这一块我讲不好,原文没有理解得非常清晰。
LARS:Least Angle Regression. S表示Lasso, Stagewise,因为原文证明它们可以通过修改LAR得到,是同一组方法。

原文的作者,是统计学界的数位大牛。统计学家,经常干从数据中发现统计规律的活~(当然呢,机器学习,模式识别的人也如此,甚至捡他们的现成)。既然统计,那当然需要数据了,现在大家请看~
原文的案例,使用的是如表格中的糖尿病数据。因变量,自变量。归一化、自变量中心化。

希望能够使用Covariate解释y。
我们定义这样一个指标:CurrentCorrelation。 它反映了X与当前残差之间的相关性。
如果我们使用迭代求解的方式,由于是解释y,去除残差,每一步的|c|应当减小。

统计分析中,最成熟的估计莫过于最小二乘回归了。其模型。
实践中,我们总假设,n>>m,亦即数据比解释变量多得多。
另一方面,我们假设X列满秩,也就是某个解释变量,不可由其它变量线性表出,否则的话,我们将它剔除。从统计意义上说,不存在可以被解释的解释变量。
在这两个假设的前提之下,普通最小二乘OLS,即,此时的c

现在对OLS解进行一个阐释。如图,解释变量仅仅X1,X2,它们确定了一个子空间。OLS解就是将y在该子空间的正交投影。

在此补充点数学知识。不好意思,可能大家不喜欢听纯数学啊……
我想说说看,因为发现,似乎有些人对投影矩阵,最小二乘不是很清楚
If y in L then P_Ly=y

由于统计问题必然涉及误差,所以y=Xbeta无解。数学称作矛盾方程组,并求解其最小二乘解。最小二乘解存在,不一定唯一。当且仅当,Rank(X)=m,最小二乘解唯一。
这里有另一个概念,就是MP逆。最小二乘解之中,具有最小的二范解,为X^+y

OLS的阐述到此为止。是否听得很不爽?………………
现在阐述大家都了解的Lasso。
我们都知道OLS容易过拟合,这是不希望的,也就产生了许多改进。其中Lasso极为著名。

Lasso已经家喻户晓了,但出生后的头两年却很少有人问津。
后来Tibshirani回忆时说,可能原因:
1. 速度问题:当时计算机求解Lasso的速度太慢;
2. 理解问题:大家对Lasso模型的性质理解不够(直到LARS)
3. 需求问题:当时还没有遇到太多高维数据分析的问题,对Sparsity的需求似乎不足。

(Extracted from “统计学习那些事”
http://www.cvchina.info/2011/07/08/%e7%bb%9f%e8%ae%a1%e5%ad%a6%e4%b9%a0%e9%82%a3%e4%ba%9b%e4%ba%8b/)

2理解问题。讲述Sparse,或者L1 Regularization最重要的在于其性质的阐释以及由此而来的性能上的提升。不过嘛,鄙人说不清楚……

Stagewise.它的迭代过程为.
其中,最关键的在于epsilon.某大牛,在实验中,发现乘了epsilon,效果大大提升,因此叫它Shirinkage。
据说Stagewise与Boosting相联系。具体我不甚了解了。
各位有兴趣可以参考。

Stagewise。
娱乐版的解释~

迭代过程可分为如下三步骤。个人以为,最重要的是方向的确定

接下来 要正式开始说LARS了。大牛们,自己动手做实验。发现,对于某个问题,二者的Solution Path几乎一样。然后大牛们想搞清楚WHY,也为了进一步理解Boosting(Boosting为什么不容易过拟合,似乎至今没有定论),开始了求助之旅,但是长时间无果。
但是Tibrashi,Lasso的作者找到了自己的老师,结果他单挑此问题成功~
接下来,让我们膜拜一下大神~
是否人家神采奕奕、玉树临风呢?大家不要期待过高哦~

Significance of LARS
LAR把Lasso (L1-norm regularization)和Boosting真正的联系起来,如同打通了任督二脉。
LARS结束了一个晦涩的时代:在LARS之前,有关Sparsity的模型几乎都是一个黑箱,它们的数学性质几乎都是缺失。
LARS开启了一个光明的时代:有关Sparsity的好文章如雨后春笋般地涌现,比如Candes和Tao的Dantzig Selector。
(Extracted from “统计学习那些事”
http://www.cvchina.info/2011/07/08/%e7%bb%9f%e8%ae%a1%e5%ad%a6%e4%b9%a0%e9%82%a3%e4%ba%9b%e4%ba%8b/)

Nearly the same as Lasso & Stagewise. Piecewise Linear
原文内容有关于C-p esitmate。它是关于估计误差的表达式,可用于选择最佳的回归系数。我发觉那是个很大的坑,就没有阐述了……

接下来阐述LAR与Lasso,Stagewise之间的过渡。抱歉,这一块我可能讲不太清楚,我看得并不十分明白,也就不知道如何易懂地讲才好。

LARS与Stagewise直观上理解易懂,但是为了忠实原文,我把原文的定理写出来,可能不太好懂,不懂关系也不大吧……

关于优化目标,在原文第92页述及,他们在找,而且确信了Stagewise的约束项。LAR的约束项,不很肯定,但是已经获得了初步结论。在此便不细述了。

 

相关PPT下载详见 “视觉计算研究论坛”「SIGVC BBS」:http://www.sigvc.org/bbs/thread-45-1-2.html



https://blog.sciencenet.cn/blog-4099-637826.html

上一篇:[CV论文读讲] LASSO 参数选择
下一篇:[CV论文读讲] Lasso & Homotopy
收藏 IP: 222.129.50.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-29 14:36

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部