统计学习那些事
这里，想补充说明一下Lasso的身世，它的全称是The Least Absolute Shrinkage and Selection Operator，读音不是[‘læso]而是[læ’su:]，有中文翻译为“套索”，个人觉得这个翻译不好，太远离它本来的含义，不如就用Lasso。Tibshrani自己说他的Lasso是受到Breiman的Non-Negative Garrote(NNG)的启发。 Lasso把NNG的两步合并为一步，即L1-norm regularization。Lasso的巨大优势在于它所构造的模型是Sparse的，因为它会自动地选择很少一部分变量构造模型。现在，Lasso已经家喻户晓了，但是Lasso出生后的头两年却很少有人问津。后来Tibshirani自己回忆时说，可能是由下面几个原因造成的：1. 速度问题：当时计算机求解Lasso的速度太慢;2. 理解问题：大家对Lasso模型的性质理解不够(直到Efron的LAR出来后大家才搞明白);3. 需求问题：当时还没有遇到太多高维数据分析的问题，对Sparsity的需求似乎不足。Lasso的遭遇似乎在阐释我们已经熟知的一些道理： 1.千里马常有，而伯乐不常有(没有Efron的LAR，Lasso可能很难有这么大的影响力)。2.时势造英雄(高维数据分析的问题越来越多，比如Bioinformatics领域)。3.金子总是会闪光的。
LAR把Lasso (L1-norm regularization)和Boosting真正的联系起来，如同打通了任督二脉(数学细节可以参考本人的一个小结，当然最好还是亲自拜读Efron的原著)。LAR结束了一个晦涩的时代：在LAR之前，有关Sparsity的模型几乎都是一个黑箱，它们的数学性质(更不要谈古典的几何性质了)几乎都是缺失。LAR开启了一个光明的时代：有关Sparsity的好文章如雨后春笋般地涌现，比如Candes和Tao的Dantzig Selector。伯克利大学的Bin Yu教授称“Lasso, Boosting and Dantzig are three cousins”。近年来兴起的Compressed sensing(Candes & Tao, Donoho)也与LAR一脉相承，只是更加强调L1-norm regularization其他方面的数学性质，比如Exact Recovery。我觉得这是一个问题的多个方面，Lasso关注的是构建模型的准确性，Compressed sensing关注的是变量选择的准确性。由此引起的关于Sparsity的研究，犹如黄河泛滥，一发不可收拾。比如Low-rank 逼近是把L1-norm从向量到矩阵的自然推广(现在流行的“用户推荐系统”用到的Collaborative filtering的数学原理源于此)。有兴趣的童鞋可以参考我个人的小结。
还必须提到的是算法问题。我个人觉得，一个好的模型，如果没有一个快速准确的算法作为支撑的话，它最后可能什么也不是。看看Lasso头几年的冷遇就知道了。LAR的成功除了它漂亮的几何性质之外，还有它的快速算法。LAR的算法复杂度相当于最小二乘法的复杂度，这几乎已经把Lasso问题的求解推向极致。这一记录在2007年被Friedman的Coordinate Descent(CD)刷新，至今没人打破。Hastie教授趣称这个为“FFT(Friedman + Fortran + Tricks)”。因为CD对Generalized Lasso问题并不能一网打尽，许多凸优化解法应运而生，如Gradient Projection， Proximal methods，ADMM (Alternating Direction Method of Multipliers)， (Split) Bregman methods，Nesterov’s method (一阶梯度法中最优的收敛速度，Candes 的很多软件包都根据这个方法设计) 等等。哪个方法更好呢?这个就像问“谁的武功天下第一”一样。我只能回答“王重阳以后再也没有天下第一了，东邪西毒南帝北丐，他们各有各的所长，有的功夫是这个人擅长一些，而另外几门功夫又是另一个人更擅长一些”。有关L1的算法可能还会大量涌现，正如优化大师Stephen Boyd所说(2010年9月28日)：“God knows the last thing we need is another algorithm for the Lasso.”