在港科大拿到PhD，做的是Bioinformatics方面的東西。Bioinformatics這個(gè)領(lǐng)域很亂，從業(yè)者水平參差不齊，但隨著相關(guān)技術(shù)（比如Microarray, Genotyping）的進(jìn)步，這個(gè)領(lǐng)域一直風(fēng)風(fēng)光光。因?yàn)槲冶究剖菍W(xué)計(jì)算機(jī)電子技術(shù)方面的，對(duì)這些技術(shù)本身并沒(méi)有多大的興趣，支持我一路走過(guò)來(lái)的一個(gè)重要原因是我感受到統(tǒng)計(jì)學(xué)習(xí)(Statistical learning)的魅力。正如本科時(shí)代看過(guò)的一本網(wǎng)絡(luò)小說(shuō)《悟空傳》所寫(xiě)的：“你不覺(jué)得天邊的晚霞很美嗎？只有看著她，我才能堅(jiān)持向西走。”

離校前閑來(lái)無(wú)事，覺(jué)得應(yīng)該把自己的一些感受寫(xiě)下來(lái)，和更多的愛(ài)好者分享。

先介紹一下我是如何發(fā)現(xiàn)這個(gè)領(lǐng)域的。我本科學(xué)自動(dòng)化，大四時(shí)接觸到一點(diǎn)智能控制的東西，比如模糊系統(tǒng)，神經(jīng)網(wǎng)絡(luò)。研究生階段除了做點(diǎn)小硬件和小軟件，主要的時(shí)間花在研究模糊系統(tǒng)上。一個(gè)偶然的機(jī)會(huì)，發(fā)現(xiàn)了王立新老師的《模糊系統(tǒng)與模糊控制教材》。我至今依然認(rèn)為這是有關(guān)模糊系統(tǒng)的最好的書(shū)，邏輯性非常強(qiáng)。它解答了我當(dāng)年的很多困惑，然而真正令我心潮澎湃的是這本書(shū)的序言，讀起來(lái)有一種“飛”的感覺(jué)。后來(lái)我終于有機(jī)會(huì)來(lái)到港科大，成為立新老師的PhD學(xué)生，時(shí)長(zhǎng)一年半（因?yàn)榱⑿吕蠋熾x開(kāi)港科大投身產(chǎn)業(yè)界了）。立新老師對(duì)我的指導(dǎo)很少，總結(jié)起來(lái)可能就一句話(huà)：“你應(yīng)該去看一下Breiman 和Friedman的文章?！绷⑿吕蠋熢谖倚哪恐械奈恢檬歉吒咴谏系?，于是我就忠實(shí)地執(zhí)行了他的話(huà)。那一年半的時(shí)間里，我?guī)缀醢阉麄兊奈恼驴戳撕脦妆?。開(kāi)始不怎么懂，后來(lái)才慢慢懂了，甚至有些癡迷。于是，我把與他們經(jīng)常合作的一些學(xué)者的大部分文章也拿來(lái)看了，當(dāng)時(shí)很傻很天真，就是瞎看，后來(lái)才知道他們的鼎鼎大名，Hastie, Tibshirani, Efron等。文章看得差不多了，就反復(fù)看他們的那本書(shū)“The Elements of Statistical learning”（以下簡(jiǎn)稱(chēng)ESL）。說(shuō)實(shí)話(huà)，不容易看明白，也沒(méi)有人指導(dǎo)，我只好把文章和書(shū)一起反復(fù)看，就這樣來(lái)來(lái)回回折騰。比如為看懂Efron的“Least angle regression”，我一個(gè)人前前后后折騰了一年時(shí)間（個(gè)人資質(zhì)太差）。當(dāng)時(shí)國(guó)內(nèi)還有人翻譯了這本書(shū)（2006年），把名字翻譯為“統(tǒng)計(jì)學(xué)習(xí)基礎(chǔ)”。我的神啦，這也叫“基礎(chǔ)”！還要不要人學(xué)?。‰y道絕世武功真的要練三五十年？其實(shí)正確的翻譯應(yīng)該叫“精要”。在我看來(lái)，這本書(shū)所記載的是絕世武功的要義，強(qiáng)調(diào)的是整體的理解，聯(lián)系和把握，絕世武功的細(xì)節(jié)在他們的文章里。

由于篇幅有限，我就以Lasso和Boosting為主線(xiàn)講講自己的體會(huì)。故事還得從90年代說(shuō)起。我覺(jué)得90年代是這個(gè)領(lǐng)域發(fā)展的一個(gè)黃金年代，因?yàn)閮煞N絕世武功都在這個(gè)時(shí)候橫空出世，他們是SVM和Boosted Trees。

 先說(shuō)SVM。大家對(duì)SVM的基本原理普遍表述為，SVM通過(guò)非線(xiàn)性變換把原空間映射到高維空間，然后在這個(gè)高維空間構(gòu)造線(xiàn)性分類(lèi)器，因?yàn)樵诟呔S空間數(shù)據(jù)點(diǎn)更容易分開(kāi)。甚至有部分學(xué)者認(rèn)為SVM可以克服維數(shù)災(zāi)難(curse of dimensionality)。如果這樣理解SVM的基本原理，我覺(jué)得還沒(méi)有看到問(wèn)題的本質(zhì)。因?yàn)檫@個(gè)看法不能解釋下面的事實(shí)：SVM在高維空間里構(gòu)建分類(lèi)器后，為什么這個(gè)分類(lèi)器不會(huì)對(duì)原空間的數(shù)據(jù)集Overfitting呢？要理解SVM的成功，我覺(jué)得可以考慮以下幾個(gè)方面：第一，SVM求解最優(yōu)分類(lèi)器的時(shí)候，使用了L2-norm regularization，這個(gè)是控制Overfitting的關(guān)鍵。第二，SVM不需要顯式地構(gòu)建非線(xiàn)性映射，而是通過(guò)Kernel trick完成，這樣大大提高運(yùn)算效率。第三，SVM的優(yōu)化問(wèn)題屬于一個(gè)二次規(guī)劃（Quadratic programming），優(yōu)化專(zhuān)家們?yōu)镾VM這個(gè)特殊的優(yōu)化問(wèn)題設(shè)計(jì)了很多巧妙的解法，比如SMO（Sequential minimal optimization）解法。第四，Vapnika的統(tǒng)計(jì)學(xué)習(xí)理論為SVM提供了很好的理論背景（這點(diǎn)不能用來(lái)解釋為什么SVM這么popular，因?yàn)橛衫碚搶?dǎo)出的bound太loose）。于是SVM成功了，火得一塌糊涂！

再說(shuō)Boosted Trees。它基本的想法是通過(guò)對(duì)弱分類(lèi)器的組合來(lái)構(gòu)造一個(gè)強(qiáng)分類(lèi)器。所謂“弱”就是比隨機(jī)猜要好一點(diǎn)點(diǎn)；“強(qiáng)”就是強(qiáng)啦。這個(gè)想法可以追溯到由Leslie Valiant教授（2010年圖靈獎(jiǎng)得主）在80年代提出的probably approximately correct learning (PAC learning) 理論。不過(guò)很長(zhǎng)一段時(shí)間都沒(méi)有一個(gè)切實(shí)可行的辦法來(lái)實(shí)現(xiàn)這個(gè)理想。細(xì)節(jié)決定成敗，再好的理論也需要有效的算法來(lái)執(zhí)行。終于功夫不負(fù)有心人， Schapire在1996年提出一個(gè)有效的算法真正實(shí)現(xiàn)了這個(gè)夙愿，它的名字叫AdaBoost。AdaBoost把多個(gè)不同的決策樹(shù)用一種非隨機(jī)的方式組合起來(lái)，表現(xiàn)出驚人的性能！第一，把決策樹(shù)的準(zhǔn)確率大大提高，可以與SVM媲美。第二，速度快，且基本不用調(diào)參數(shù)。第三，幾乎不Overfitting。我估計(jì)當(dāng)時(shí)Breiman和Friedman肯定高興壞了，因?yàn)檠劭粗麄兲岢龅腃ART正在被SVM比下去的時(shí)候，AdaBoost讓決策樹(shù)起死回生！Breiman情不自禁地在他的論文里贊揚(yáng)AdaBoost是最好的現(xiàn)貨方法（off-the-shelf，即“拿下了就可以用”的意思）。其實(shí)在90年代末的時(shí)候，大家對(duì)AdaBoost為什么有如此神奇的性能迷惑不解。1999年，F(xiàn)riedman的一篇技術(shù)報(bào)告“Additive logistic regression: a statistical view of boosting”解釋了大部分的疑惑（沒(méi)有解釋AdaBoost為什么不容易Overfitting，這個(gè)問(wèn)題好像至今還沒(méi)有定論），即搞清楚了AdaBoost在優(yōu)化什么指標(biāo)以及如何優(yōu)化的?；诖耍現(xiàn)riedman提出了他的GBM（Gradient Boosting Machine，也叫MART或者TreeNet）。幾乎在同時(shí)，Breiman另辟蹊徑，結(jié)合他的Bagging (Bootstrap aggregating) 提出了Random Forest （今天微軟的Kinect里面就采用了Random Forest，相關(guān)論文Real-time Human Pose Recognition in Parts from Single Depth Images是CVPR2011的best paper）。

有一個(gè)關(guān)于Gradient Boosting細(xì)節(jié)不得不提。Friedman在做實(shí)驗(yàn)的時(shí)候發(fā)現(xiàn)，把一棵新生成的決策樹(shù)，記為f_m，加到當(dāng)前模型之前，在這棵決策樹(shù)前乘以一個(gè)小的數(shù)，即v×f_m（比如v=0.01），再加入到當(dāng)前模型中，往往大大提高模型的準(zhǔn)確度。他把這個(gè)叫做“Shrinkage”。接下來(lái)，Hastie，Tibshirani和Friedman進(jìn)一步發(fā)現(xiàn)（我發(fā)現(xiàn)大師們都是親自動(dòng)手寫(xiě)程序做實(shí)驗(yàn)的），如果把具有Shrinkage的Gradient Boosting應(yīng)用到線(xiàn)性回歸中時(shí)，得到的Solution Path與Lasso的Solution Path驚人地相似(如圖所示)！他們把這一結(jié)果寫(xiě)在了ESL的第一版里，并推測(cè)這二者存在著某種緊密的聯(lián)系，但精確的數(shù)學(xué)關(guān)系他們當(dāng)時(shí)也不清楚。Tibshirani說(shuō)他們還請(qǐng)教了斯坦福的優(yōu)化大師（我估計(jì)是Stephen Boyd），但還是沒(méi)有找到答案。

后來(lái)Tibshirani找到自己的恩師Efron。Tibshirani在“The Science of Bradley Efron”這本書(shū)的序言里寫(xiě)道，“He sat down and pretty much single-handedly solved the problem. Along the way, he developed a new algorithm, ‘least angle regression,’ which is interesting in its own right, and sheds great statistical insight on the Lasso.”我就不逐字逐句翻譯了，大意是：Efron獨(dú)自擺平了這個(gè)問(wèn)題，與此同時(shí)發(fā)明了“Least angle regression (LAR)”。Efron結(jié)論是Lasso和Boosting的確有很緊密的數(shù)學(xué)聯(lián)系，它們都可以通過(guò)修改LAR得到。更令人驚嘆的是LAR具有非常明確的幾何意義。于是，Tibshirani在序言中還有一句，“In this work, Brad shows his great mathematical power–not the twentieth century, abstract kind of math, but the old-fashioned kind: geometric insight and analysis.”讀Prof Efron的文章，可以感受到古典幾何學(xué)與現(xiàn)代統(tǒng)計(jì)學(xué)的結(jié)合之美（推薦大家讀讀Efron教授2010年的一本新書(shū)Large-Scale Inference，希望以后有機(jī)會(huì)再寫(xiě)寫(xiě)這方面的體會(huì)）！總之，Efron的這篇文章是現(xiàn)代統(tǒng)計(jì)學(xué)的里程碑，它結(jié)束了一個(gè)時(shí)代，開(kāi)啟了另一個(gè)時(shí)代。

這里，想補(bǔ)充說(shuō)明一下Lasso的身世，它的全稱(chēng)是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)家喻戶(hù)曉了，但是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é)[1]，當(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教授稱(chēng)“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)在流行的“用戶(hù)推薦系統(tǒng)”用到的Collaborative filtering的數(shù)學(xué)原理源于此）。有興趣的童鞋可以參考我個(gè)人的小結(jié)[2]。

還必須提到的是算法問(wèn)題。我個(gè)人覺(jué)得，一個(gè)好的模型，如果沒(méi)有一個(gè)快速準(zhǔn)確的算法作為支撐的話(huà)，它最后可能什么也不是?？纯碙asso頭幾年的冷遇就知道了。LAR的成功除了它漂亮的幾何性質(zhì)之外，還有它的快速算法。LAR的算法復(fù)雜度相當(dāng)于最小二乘法的復(fù)雜度，這幾乎已經(jīng)把Lasso問(wèn)題的求解推向極致。這一記錄在2007年被Friedman的Coordinate Descent（CD）刷新，至今沒(méi)人打破。Hastie教授趣稱(chēng)這個(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)一些，而另外幾門(mén)功夫又是另一個(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.”

最后我想以討論“模糊系統(tǒng)”和“統(tǒng)計(jì)學(xué)習(xí)”來(lái)結(jié)尾。這個(gè)話(huà)題非常具有爭(zhēng)議，我就冒天下之大不諱吧，談一談我這幾年的學(xué)習(xí)體會(huì)。記得十年前，立新老師曾經(jīng)寫(xiě)過(guò)一篇文章《模糊系統(tǒng)：挑戰(zhàn)與機(jī)遇并存——十年研究之感悟》，發(fā)表在2001年《自動(dòng)化學(xué)報(bào)》上。我2005年看到的時(shí)候，敬仰之情，猶如滔滔江水。立新老師曾經(jīng)有這么一句話(huà)：“If a method works well in practice, there must be some theoretical reasons for its success.”2005年的時(shí)候，我開(kāi)始問(wèn)自己什么使模糊系統(tǒng)的成功？立新老師認(rèn)為有如下幾個(gè)原因：1.模糊系統(tǒng)的通用逼近性能（Universal Approximator）；2.模糊系統(tǒng)快速的構(gòu)造算法，比如他自己的WM方法，Roger Jang的ANFIS等等；3.結(jié)果的可解釋性；4.利用各種不同形式的信息。

下面我談?wù)勛约旱目捶?，第一，通用逼近性能?dāng)然是一個(gè)好的性質(zhì)，它表明模糊系統(tǒng)是很flexible的，但flexible的結(jié)構(gòu)太多了，比如神經(jīng)網(wǎng)絡(luò)。問(wèn)題往往不在flexible，而在太flexible導(dǎo)致overfitting。就如同SVM一樣，沒(méi)有L2-norm regularization，實(shí)踐中的性能就會(huì)變得很差。第二，快速算法，這是好的方法必備的，SVM，Boosting，Random Forest的算法都很快，而且可以直接用到高維，這一點(diǎn)上，我沒(méi)有看到模糊系統(tǒng)的優(yōu)勢(shì)。第三，可解釋性：模糊系統(tǒng)對(duì)低維數(shù)據(jù)（比如2-4維）的確具有好的解釋性（因?yàn)镮F-THEN規(guī)則的前提和結(jié)論都很簡(jiǎn)潔），但這個(gè)時(shí)候其它工具也可以做得到，比如Gradient Boosting和Random Forests（很多例子可以在ESL這本書(shū)里看到）。第四，充分的利用各種信息。立新老師指的是IF-THEN規(guī)則可以比較自由靈活的加入先驗(yàn)知識(shí)，并在他的書(shū)里面詳細(xì)給出實(shí)例。遺憾的是，這些例子都在處理低維空間的問(wèn)題。如何用IF-THEN規(guī)則解構(gòu)高維空間呢？我個(gè)人看不到它們特殊的優(yōu)勢(shì)。然而，在統(tǒng)計(jì)學(xué)習(xí)里，利用不同的先驗(yàn)知識(shí)處理高維空間的例子比比皆是，比如Sparsity，group-structure，smoothness等等?，F(xiàn)在舉一個(gè)Gradient Boosting  machine（GBM，也叫MART）的例子來(lái)說(shuō)明我的觀點(diǎn)。根據(jù)Lasso和Boosting的關(guān)系，可以知道GBM已經(jīng)用到了Sparsity的性質(zhì)（L1-norm regularization）。GBM有兩個(gè)參數(shù)可以反映我們的先驗(yàn)知識(shí)。第一個(gè)參數(shù)是深度（depth），控制每棵決策樹(shù)的深度 。如果深度為1，即樹(shù)樁結(jié)構(gòu)（Stump），表明GBM將采用加法模型（Generalized Additive model），即不考慮變量之間的交互式作用（Interaction）；如果深度大于1，則考慮交互式作用。因?yàn)榻换ナ阶饔迷诜蔷€(xiàn)性建模中比較重要，如異或（XOR）問(wèn)題，沒(méi)有考慮交互式作用將失敗得很慘，所以這個(gè)參數(shù)設(shè)置反映了對(duì)非線(xiàn)性建模的先驗(yàn)。第二個(gè)參數(shù)是Shrinkage的大小。假設(shè)深度選取是合理的，在噪聲比較小的時(shí)候，沒(méi)有Shrinkage會(huì)比較好；噪聲比較大的時(shí)候，有Shrinkage會(huì)好一些。實(shí)踐中，使用GBM對(duì)高維數(shù)據(jù)分析，試錯(cuò)法（Trial and error）很容易使用，因?yàn)榫瓦@兩個(gè)參數(shù)（通常depth=3～4；實(shí)際數(shù)據(jù)的噪聲往往比較大，推薦設(shè)置Shrinkage=0.01）。模型構(gòu)建好之后，GBM會(huì)告訴你哪些變量是重要的，變量之間的交互式作用如何等等，這樣模型的結(jié)果也是比較容易理解。Random Forests也有相似的功能。好了，最后借Hastie教授的一幅圖來(lái)總結(jié)一下，無(wú)疑，GBM（MART）是他們的最?lèi)?ài)，也是我的最?lèi)?ài)。