統(tǒng)計(jì)學(xué)習(xí)那些事
這里，想補(bǔ)充說(shuō)明一下Lasso的身世，它的全稱是The Least Absolute Shrinkage and Selection Operator，讀音不是[‘l?so]而是[l?’su:]，有中文翻譯為“套索”，個(gè)人覺(jué)得這個(gè)翻譯不好，太遠(yuǎn)離它本來(lái)的含義，不如就用Lasso。Tibshrani自己說(shuō)他的Lasso是受到Breiman的Non-Negative Garrote(NNG)的啟發(fā)。 Lasso把NNG的兩步合并為一步，即L1-norm regularization。Lasso的巨大優(yōu)勢(shì)在于它所構(gòu)造的模型是Sparse的，因?yàn)樗鼤?huì)自動(dòng)地選擇很少一部分變量構(gòu)造模型?，F(xiàn)在，Lasso已經(jīng)家喻戶曉了，但是Lasso出生后的頭兩年卻很少有人問(wèn)津。后來(lái)Tibshirani自己回憶時(shí)說(shuō)，可能是由下面幾個(gè)原因造成的：1. 速度問(wèn)題：當(dāng)時(shí)計(jì)算機(jī)求解Lasso的速度太慢;2. 理解問(wèn)題：大家對(duì)Lasso模型的性質(zhì)理解不夠(直到Efron的LAR出來(lái)后大家才搞明白);3. 需求問(wèn)題：當(dāng)時(shí)還沒(méi)有遇到太多高維數(shù)據(jù)分析的問(wèn)題，對(duì)Sparsity的需求似乎不足。Lasso的遭遇似乎在闡釋我們已經(jīng)熟知的一些道理： 1.千里馬常有，而伯樂(lè)不常有(沒(méi)有Efron的LAR，Lasso可能很難有這么大的影響力)。2.時(shí)勢(shì)造英雄(高維數(shù)據(jù)分析的問(wèn)題越來(lái)越多，比如Bioinformatics領(lǐng)域)。3.金子總是會(huì)閃光的。
LAR把Lasso (L1-norm regularization)和Boosting真正的聯(lián)系起來(lái)，如同打通了任督二脈(數(shù)學(xué)細(xì)節(jié)可以參考本人的一個(gè)小結(jié)，當(dāng)然最好還是親自拜讀Efron的原著)。LAR結(jié)束了一個(gè)晦澀的時(shí)代：在LAR之前，有關(guān)Sparsity的模型幾乎都是一個(gè)黑箱，它們的數(shù)學(xué)性質(zhì)(更不要談古典的幾何性質(zhì)了)幾乎都是缺失。LAR開(kāi)啟了一個(gè)光明的時(shí)代：有關(guān)Sparsity的好文章如雨后春筍般地涌現(xiàn)，比如Candes和Tao的Dantzig Selector。伯克利大學(xué)的Bin Yu教授稱“Lasso, Boosting and Dantzig are three cousins”。近年來(lái)興起的Compressed sensing(Candes & Tao, Donoho)也與LAR一脈相承，只是更加強(qiáng)調(diào)L1-norm regularization其他方面的數(shù)學(xué)性質(zhì)，比如Exact Recovery。我覺(jué)得這是一個(gè)問(wèn)題的多個(gè)方面，Lasso關(guān)注的是構(gòu)建模型的準(zhǔn)確性，Compressed sensing關(guān)注的是變量選擇的準(zhǔn)確性。由此引起的關(guān)于Sparsity的研究，猶如黃河泛濫，一發(fā)不可收拾。比如Low-rank 逼近是把L1-norm從向量到矩陣的自然推廣(現(xiàn)在流行的“用戶推薦系統(tǒng)”用到的Collaborative filtering的數(shù)學(xué)原理源于此)。有興趣的童鞋可以參考我個(gè)人的小結(jié)。
還必須提到的是算法問(wèn)題。我個(gè)人覺(jué)得，一個(gè)好的模型，如果沒(méi)有一個(gè)快速準(zhǔn)確的算法作為支撐的話，它最后可能什么也不是?？纯碙asso頭幾年的冷遇就知道了。LAR的成功除了它漂亮的幾何性質(zhì)之外，還有它的快速算法。LAR的算法復(fù)雜度相當(dāng)于最小二乘法的復(fù)雜度，這幾乎已經(jīng)把Lasso問(wèn)題的求解推向極致。這一記錄在2007年被Friedman的Coordinate Descent(CD)刷新，至今沒(méi)人打破。Hastie教授趣稱這個(gè)為“FFT(Friedman + Fortran + Tricks)”。因?yàn)镃D對(duì)Generalized Lasso問(wèn)題并不能一網(wǎng)打盡，許多凸優(yōu)化解法應(yīng)運(yùn)而生，如Gradient Projection， Proximal methods，ADMM (Alternating Direction Method of Multipliers)， (Split) Bregman methods，Nesterov’s method (一階梯度法中最優(yōu)的收斂速度，Candes 的很多軟件包都根據(jù)這個(gè)方法設(shè)計(jì)) 等等。哪個(gè)方法更好呢?這個(gè)就像問(wèn)“誰(shuí)的武功天下第一”一樣。我只能回答“王重陽(yáng)以后再也沒(méi)有天下第一了，東邪西毒南帝北丐，他們各有各的所長(zhǎng)，有的功夫是這個(gè)人擅長(zhǎng)一些，而另外幾門功夫又是另一個(gè)人更擅長(zhǎng)一些”。有關(guān)L1的算法可能還會(huì)大量涌現(xiàn)，正如優(yōu)化大師Stephen Boyd所說(shuō)(2010年9月28日)：“God knows the last thing we need is another algorithm for the Lasso.”