http://www./2010/12/an-introduction-to-treelink.html
“機(jī)器學(xué)習(xí)”這個(gè)名詞對(duì)大家來說想必不是一個(gè)陌生的詞匯，特別對(duì)算法組的同學(xué)來說，工作中或多或少接觸使用過這種“高科技“。對(duì)于我來說，剛來淘寶工作一個(gè)月就開始接觸了機(jī)器學(xué)習(xí)，當(dāng)時(shí)做主搜索功夫熊貓項(xiàng)目，和小致飄雪一起做交易模型，正是使用了機(jī)器學(xué)習(xí)的方法，也首次接觸了treelink模型。做完那個(gè)項(xiàng)目后對(duì)機(jī)器學(xué)習(xí)解決問題的流程有了一定的了解，但對(duì)其內(nèi)部的工作原理和實(shí)現(xiàn)機(jī)制還是完全不知道，基本也就是在黑盒使用機(jī)器學(xué)習(xí)工具。后面也多多少少聽了一些機(jī)器學(xué)習(xí)的講座，但都是一些比較寬泛的基本概念，沒有深入的原理性的介紹。也自己嘗試過專研一下，但生硬晦澀的E文讓人望而生畏。一直到今年做導(dǎo)購搜索的項(xiàng)目，又再次需要使用機(jī)器學(xué)習(xí)，“懷揣著對(duì)科學(xué)真理的向往”，主動(dòng)請(qǐng)纓做模型方面的工作。經(jīng)過一個(gè)多月的學(xué)習(xí)實(shí)踐，算是對(duì)treelink模型有了一定的了解。下面做一些對(duì)treelink模型通俗版的介紹。都是自己的一些理解，如果有誤，多指教。
在介紹treelink之前首先不得不簡單介紹一下決策樹算法，決策樹相信大家都有所了解，任何一本機(jī)器學(xué)習(xí)書籍都會(huì)介紹這種算法，也是應(yīng)用最廣的歸納推理算法之一。該模型學(xué)習(xí)的結(jié)果是一棵決策樹，這棵決策樹可以被表示成多個(gè)if-else的規(guī)則。下圖是一個(gè)典型的學(xué)習(xí)得到?jīng)Q策樹。這棵決策樹根據(jù)兩個(gè)特征因素來分類“元涵今天的心情好壞”。長方形的表示特征，橢圓型的表示特征的取值，最下面的葉子節(jié)點(diǎn)就是最后的分類結(jié)果了。
學(xué)習(xí)得到如上這棵決策樹之后，當(dāng)輸入一個(gè)待預(yù)測的樣本實(shí)例的時(shí)候，我們就可以根據(jù)這個(gè)樣本的兩個(gè)特征的取值來把這個(gè)樣本劃分到某一個(gè)葉子節(jié)點(diǎn)，得到分類結(jié)果了，這就是決策樹模型的預(yù)測過程，決策樹的學(xué)習(xí)構(gòu)建過程這里就不介紹了，大家看書吧，比較經(jīng)典的有ID3算法和C4.5算法。
切入正題下面開始說treelink算法，treelink這個(gè)名字其實(shí)只是我們阿里集團(tuán)內(nèi)部的叫法，學(xué)術(shù)上的名稱叫GBDT（Gradient
boost decision
tree）。treelink模型不像決策樹模型那樣僅由一棵決策樹構(gòu)成，而是由多棵決策樹構(gòu)成，通常都是上百棵樹，而且每棵樹規(guī)模都較?。礃涞纳疃葧?huì)比較淺）。模型預(yù)測的時(shí)候，對(duì)于輸入的一個(gè)樣本實(shí)例，首先會(huì)賦予一個(gè)初值，然后會(huì)遍歷每一棵決策樹，每棵樹都會(huì)對(duì)預(yù)測值進(jìn)行調(diào)整修正，最后得到預(yù)測的結(jié)果。
F0是設(shè)置的初值，
Ti是一棵一棵的決策樹。對(duì)于不同的問題（回歸問題或者分類問題）和選擇不同的損失函數(shù)，初值的設(shè)定是不同的。比如回歸問題并且選擇高斯損失函數(shù)，那么這個(gè)初值就是訓(xùn)練樣本的目標(biāo)的均值。
下面是一個(gè)簡單的treelink模型示意圖。模型的目標(biāo)是上海一套普通商品房的價(jià)格，特征有三個(gè)：房子的面積（連續(xù)特征），是否在內(nèi)環(huán)（分類特征），是否學(xué)區(qū)房（分類特征）。模型由四棵決策樹構(gòu)成，每棵決策樹只進(jìn)行了一次分裂，即樹的深度為一（這種樹被稱為Decision
Stump）。實(shí)際應(yīng)用中通常較復(fù)雜，深度不會(huì)為一。
初值設(shè)定為上海普通商品房價(jià)格的均值150萬，每經(jīng)過一棵決策樹，都會(huì)對(duì)根據(jù)相應(yīng)特征的取值對(duì)預(yù)測價(jià)格進(jìn)行調(diào)整。比如一個(gè)面積為120平的內(nèi)環(huán)非學(xué)區(qū)房的價(jià)格預(yù)測值為：150+20-10+30-10=180萬。
那為什么要用多棵決策樹，一棵決策樹為什么不好呢？使用單棵決策樹，最大的問題就是會(huì)因?yàn)檫^度分裂，而造成過擬合，失去泛化能力。試想一下，對(duì)于給定的一批訓(xùn)練數(shù)據(jù)，完全可以只構(gòu)造一棵樹，不斷分裂下去，直到每個(gè)葉子節(jié)點(diǎn)包含的樣本的目標(biāo)值都一樣，然后把這節(jié)點(diǎn)的預(yù)測值設(shè)定成這個(gè)目標(biāo)值，這樣構(gòu)造出來的這棵樹就可以在這批訓(xùn)練數(shù)據(jù)上達(dá)到100%的準(zhǔn)確性。但這樣一棵過度分裂的決策樹，對(duì)于新的樣本基本沒有什么預(yù)測能力。而如果分裂太少，又會(huì)造成學(xué)習(xí)不夠充分。Treelink使用多棵決策樹正是希望能夠在訓(xùn)練精度和泛化能力兩個(gè)方面都能達(dá)到較好的效果。作為一種boosting算法，Treelink自然包含了boosting的思想：將一系列弱分類器組合起來，構(gòu)成一個(gè)強(qiáng)分類器。它不要求每棵樹學(xué)到太多的東西，每顆樹都學(xué)一點(diǎn)點(diǎn)知識(shí)，然后將這些學(xué)到的知識(shí)累加起來構(gòu)成一個(gè)強(qiáng)大的模型。舉個(gè)現(xiàn)實(shí)生活中的例子，電視里的那種益智類節(jié)目，如開心詞典，答題者有三次請(qǐng)求幫組的機(jī)會(huì)，其中一個(gè)就是請(qǐng)求現(xiàn)場所有觀眾，通過他們的選擇來給出答案。我們可以把每個(gè)觀眾當(dāng)做一個(gè)弱的分類器，他們各個(gè)單獨(dú)的準(zhǔn)確率都不高，但把他們的知識(shí)綜合起來這個(gè)準(zhǔn)確率會(huì)大大提升。也許上面這個(gè)例子不太能說服你，我們來把這個(gè)例子量化。假如我們有三個(gè)觀眾，他們各自的準(zhǔn)確率為60%（非常弱的分類器，只比隨機(jī)分類器好一點(diǎn)點(diǎn)），如果這三位觀眾中有大于等于兩位的答案是正確的，那么則認(rèn)為我們正確了，反之則錯(cuò)誤。那么我們正確的概率是多少呢？preciseness
= p(三個(gè)人都正確) + p(三個(gè)人中有兩個(gè)人正確) = 0.6*0.6*0.6 + 3*0.6*0.6*0.4 =
0.648，比單個(gè)人0.6的正確率有所提升，驗(yàn)了中國那句老話“三個(gè)臭皮匠頂個(gè)諸葛亮”。隨著人數(shù)的增加，這個(gè)正確率還會(huì)提升。
Treelink模型的學(xué)習(xí)過程，就是多顆樹的構(gòu)建過程。和決策樹模型一樣，在樹的構(gòu)建過程中，最重要的就是尋找分裂點(diǎn)（某個(gè)特征的某個(gè)取值）。我們希望選擇的這個(gè)分裂點(diǎn)是最能區(qū)分樣本的。那么如何衡量一個(gè)分裂點(diǎn)對(duì)樣本的區(qū)分能力？在treelink算法我們通過Loss（衡量樣本預(yù)測值與目標(biāo)值的差異）的減小程度用來衡量這個(gè)區(qū)分能力，Loss減小得越多，這個(gè)分裂點(diǎn)就越好。即以某個(gè)分裂點(diǎn)劃分，把樣本分成兩部分，使得分裂后樣本的損失函數(shù)（Loss
Function）值減小的最多。好像有點(diǎn)不太通俗了，沒辦法。
訓(xùn)練流程：
1 估計(jì)初值
2
按如下方式構(gòu)造M顆樹
2.1
隨機(jī)選取部分樣本作為本顆樹的訓(xùn)練數(shù)據(jù)
2.2
按如下方式尋找最優(yōu)分裂點(diǎn)，進(jìn)行N次葉子節(jié)點(diǎn)的分裂
2.2.1
對(duì)當(dāng)前所有葉子節(jié)點(diǎn)
2.2.1.1
計(jì)算該葉子節(jié)點(diǎn)的最優(yōu)劃分以及其增益（損失函數(shù)減少量）
2.2.1.2
選擇增益最大的葉子節(jié)點(diǎn)及其劃分點(diǎn)，進(jìn)行分裂，將樣本劃分到子節(jié)點(diǎn)中
2.2.1.3
更新樣本估計(jì)值
集團(tuán)開發(fā)的mllib機(jī)器學(xué)習(xí)工具包中treelink是最重要的一個(gè)模型。對(duì)于如何使用這個(gè)工具包， mlllib user
manual里面已經(jīng)寫的非常詳細(xì)了。下面說一下其中一些重要參數(shù)的意義及如何設(shè)置。
tree_count：前面提到的決策樹的個(gè)數(shù)，這個(gè)數(shù)設(shè)的越大學(xué)習(xí)就越充分，但太大也會(huì)造成過度擬合，而且也消耗訓(xùn)練和預(yù)測的時(shí)間?？梢韵冗x擇比較大的樹個(gè)數(shù)，然后觀察訓(xùn)練過程中的損失減少趨勢，損失減少比較平緩時(shí)，樹個(gè)數(shù)就比較合適了。tree_count和shrinkage也有關(guān)系，shrinkage越大，學(xué)習(xí)越快，需要的樹越少。
shrinkage：步長，它代表的是學(xué)習(xí)的速度，越小表示學(xué)習(xí)越保守（慢），而越大則表示學(xué)習(xí)越冒進(jìn)（快）。通常我們可以把Shrinkage設(shè)小一點(diǎn)，把樹的個(gè)數(shù)設(shè)大一點(diǎn)。
sample_rate：樣本采樣率，一次學(xué)習(xí)使用全部的樣本是浪費(fèi)，為了構(gòu)造出具有不同傾向性的模型，需要使用樣本的子集來進(jìn)行訓(xùn)練，而過多的樣本對(duì)簡單的模型無益，只會(huì)造成更多的過擬合和局部極小問題。這個(gè)采樣的比例一般選擇50%-70%比較合適。
variable_sample_rate：特征采樣率，和上面的樣本采樣率不同，這個(gè)采樣率是指從樣本的所有特征中選取部分的特征來學(xué)習(xí)，而不使用全部特征。當(dāng)你發(fā)現(xiàn)訓(xùn)練出來的模型，某一兩個(gè)特征非常強(qiáng)勢，重要性很大，而造成其他特征基本學(xué)不到的時(shí)候，可以考慮設(shè)置一下把這個(gè)參數(shù)設(shè)置成<1的數(shù)。
最后是對(duì)于使用機(jī)器學(xué)習(xí)的一些常見問題的一些理解。
1
機(jī)器學(xué)習(xí)是萬能的？
當(dāng)然不是，如果你認(rèn)為可以簡單地把一堆特征樣本扔給機(jī)器學(xué)習(xí)，就期望它給一個(gè)好的模型，那是不可能。在使用機(jī)器學(xué)習(xí)之前，一定要對(duì)所使用的模型有個(gè)基本的了解，最好能夠知道它的計(jì)算原理。如果你都不知道treelink為何物，那些參數(shù)大概是個(gè)什么意思，你最好就不要用了，用也是在拼人品。
2 使用機(jī)器學(xué)習(xí)的同時(shí)做好數(shù)據(jù)分析工作
就算使用機(jī)器學(xué)習(xí)，數(shù)據(jù)的分析工作也是省不了的，做好了分析工作，你會(huì)發(fā)現(xiàn)自己都可以像機(jī)器一樣找到那些規(guī)律。其實(shí)機(jī)器學(xué)習(xí)本身也就是統(tǒng)計(jì)，幫你找數(shù)據(jù)之間的規(guī)律，并把這些規(guī)律做成規(guī)則。好萊塢奧斯卡金像獎(jiǎng)電影《美麗心靈》中的男主人翁，諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)得主數(shù)學(xué)家約翰納什在電影中被稱為最厲害的人肉密碼破譯者，充分向我們展現(xiàn)了how
people learning beats machine
learning，當(dāng)然是有些夸張的成份。下面是一些可以做的最基本的數(shù)據(jù)分析工作：
1） 特征的分布：按特征的取值分段，每一段包含的樣本數(shù)量，特征均值，方差。
2） 目標(biāo)分布同上
3） 特征目標(biāo)關(guān)系：特征分段，每段中包含的樣本的目標(biāo)取值。
4） 目標(biāo)特征關(guān)系：目標(biāo)分段，每段中包含的樣本的特征取值
3
模型在訓(xùn)練數(shù)據(jù)上效果不錯(cuò)，但做Cross-validation效果不佳
