|
一.GBDT簡介 GBDT(Gradient Boosting Decision Tree) 是一種迭代的決策樹算法，該算法由多棵決策樹組成，所有樹的結(jié)論累加起來做最終結(jié)果。它在被提出之初就和SVM一起被認為是泛化能力（generalization)較強的算法。近些年更因為被用于搜索排序的機器學習模型而引起大家關(guān)注。 GBDT是一個應(yīng)用很廣泛的算法，可以用來做分類、回歸。在很多的數(shù)據(jù)上都有不錯的效果。GBDT這個算法還有一些其他的名字，比如說MART(Multiple Additive Regression Tree)，GBRT(Gradient Boost Regression Tree)，Tree Net等。 二.相關(guān)基礎(chǔ)知識 2.1決策樹 決策樹分為兩大類，分類樹和回歸樹。分類樹是我們比較熟悉的決策樹，比如C4.5分類決策樹。分類樹用于分類標簽值，如晴天/陰天、用戶性別、網(wǎng)頁是否是垃圾頁面。而回 歸樹用于預(yù)測實數(shù)值，如明天的溫度、用戶的年齡、網(wǎng)頁的相關(guān)程度。也就是分類樹的輸出是定性的，而回歸樹的輸出是定量的。 GBDT的核心在于累加所有樹的結(jié)果作為最終結(jié)果，比如對年齡的累加來預(yù)測年齡，而分類樹的結(jié)果顯然是沒辦法累加的，所以GBDT中的樹都是回歸樹，不是分類樹。
2.1.1 分類樹
以C4.5分類樹為例，C4.5分類樹在每次分枝時，是窮舉每一個feature的每一個閾值，找到使得按照feature<=閾值，和feature>閾值分成的兩個分枝的熵最大的閾值(熵最大的概念可理解成盡可能每個分枝的男女比例都遠離1:1)，按照該標準分枝得到兩個新節(jié)點，用同樣方法繼續(xù)分枝直到所有人都被分入性別唯一的葉子節(jié)點，或達到預(yù)設(shè)的終止條件，若最終葉子節(jié)點中的性別不唯一，則以多數(shù)人的性別作為該葉子節(jié)點的性別。
2.1.2 回歸樹
回歸樹總體流程也是類似，區(qū)別在于，回歸樹的每個節(jié)點（不一定是葉子節(jié)點）都會得一個預(yù)測值，以年齡為例，該預(yù)測值等于屬于這個節(jié)點的所有人年齡的平均值。分枝時窮舉每一個feature的每個閾值找最好的分割點，但衡量最好的標準不再是最大熵，而是最小化均方差即(每個人的年齡-預(yù)測年齡)^2 的總和 / N。也就是被預(yù)測出錯的人數(shù)越多，錯的越離譜，均方差就越大，通過最小化均方差能夠找到最可靠的分枝依據(jù)。分枝直到每個葉子節(jié)點上人的年齡都唯一或者達到預(yù)設(shè)的終止條件(如葉子個數(shù)上限)，若最終葉子節(jié)點上人的年齡不唯一，則以該節(jié)點上所有人的平均年齡做為該葉子節(jié)點的預(yù)測年齡。 2.2 梯度迭代（Gradient Boosting） Boosting，迭代，即通過迭代多棵樹來共同決策。GBDT的核心就在于，每一棵樹學的是之前所有樹結(jié)論和的殘差，這個殘差就是一個加預(yù)測值后能得真實值的累加量。比如A的真實年齡是18歲，但第一棵樹的預(yù)測年齡是12歲，差了6歲，即殘差為6歲。那么在第二棵樹里我們把A的年齡設(shè)為6歲去學習，如果第二棵樹真的能把A分到6歲的葉子節(jié)點，那累加兩棵樹的結(jié)論就是A的真實年齡；如果第二棵樹的結(jié)論是5歲，則A仍然存在1歲的殘差，第三棵樹里A的年齡就變成1歲，繼續(xù)學習。 2.3 GBDT工作過程實例 比如年齡預(yù)測，假設(shè)訓(xùn)練集只有4個人A,B,C,D，他們的年齡分別是14,16,24,26。其中A,B分別是高一和高三學生；C,D分別是應(yīng)屆畢業(yè)生和工作兩年的員工。若用一棵傳統(tǒng)的回歸決策樹來訓(xùn)練，會得到如圖所示結(jié)果。
如果使用GBDT來來訓(xùn)練，由于數(shù)據(jù)太少，我們限定葉子節(jié)點做最多有兩個，并且限定只學兩棵樹。
A: 14歲高一學生，購物較少，經(jīng)常問學長問題；預(yù)測年齡A = 15 – 1 = 14 B: 16歲高三學生；購物較少，經(jīng)常被學弟問問題；預(yù)測年齡B = 15 + 1 = 16 C: 24歲應(yīng)屆畢業(yè)生；購物較多，經(jīng)常問師兄問題；預(yù)測年齡C = 25 – 1 = 24 D: 26歲工作兩年員工；購物較多，經(jīng)常被師弟問問題；預(yù)測年齡D = 25 + 1 = 26 注：圖1和圖2 最終效果相同，為何還需要GBDT呢？答案是過擬合。過擬合是指為了讓訓(xùn)練集精度更高，學到了很多“僅在訓(xùn)練集上成立的規(guī)律”，導(dǎo)致?lián)Q一個數(shù)據(jù)集當前規(guī)律就不適用了。只要允許一棵樹的葉子節(jié)點足夠多，訓(xùn)練集總是能訓(xùn)練到100%準確率的。在訓(xùn)練精度和實際精度（或測試精度）之間，后者才是我們想要真正得到的。 2.4 Shrinkage Shrinkage(縮減)的思想認為：每次走一小步逐漸逼近結(jié)果，要比每次邁一大步很快逼近結(jié)果的方式更容易避免過擬合。即它不完全信任每一個棵殘差樹，它認為每棵樹只學到了結(jié)果的一小部分，累加的時候只累加一小部分，通過多學幾棵樹彌補不足。 假設(shè)yi表示第i棵樹上y的預(yù)測值，y(1~i)表示前i棵樹y的綜合預(yù)測值。 y(i+1)= f(殘差(y(1~i))) 其中，殘差(y(1~i))=y真實值 - y(1~i) y_(1~i)= SUM(y_1,…, y_i) 引入Shrinkage后，y(1~i) = y(1~i-1)+step *yi step可以認為是學習速度，越小表示學習越慢，越大表示學習越快。step一般都比較小，導(dǎo)致各個樹的殘差是漸變的而不是陡變的。
三. GBDT適用范圍
機器學習可以解決很多問題，其中最為重要的兩個是 回歸與分類。GBDT可用于回歸問題，相對logistic regression僅能用于線性回歸，GBDT能用于線性回歸和非線性回歸，GBDT的適用面非常廣。GBDT也可用于二分類問題（設(shè)定閾值，大于閾值為正例，反之為負例）。 四. 搜索引擎排序應(yīng)用RankNet RankNet是基于樣本對級別(機器學習按照誤差函數(shù)的設(shè)計分為3種：點方式、對方式、列表方式)方法的一種典型的網(wǎng)頁排序算法，是利用梯度下降的原理，基于神經(jīng)網(wǎng)絡(luò)來進行模型的構(gòu)造和應(yīng)用的。 就像所有的機器學習一樣，搜索排序的學習也需要訓(xùn)練集，RankNet一般是用人工標注實現(xiàn)，即對每一個文檔給定一個分值（1,2,3,4）,分值越高表示越相關(guān)，越應(yīng)該排到前面。然而這些絕對的分值本身意義不大，例如很難說1分和2分文檔的相關(guān)程度差異是1分和3分文檔相關(guān)程度差距的一半。相關(guān)度是一個很主觀的評判，人工無法做到這種定量標注，這種標準也無法制定。但人工容易做到的是“A和B與查詢詞都很相關(guān)，但文檔A比文檔B更相關(guān)，所以A比B的分高”。 利用RankNet進行網(wǎng)頁排序，首先對訓(xùn)練樣本進行轉(zhuǎn)化。 
利用神經(jīng)網(wǎng)絡(luò)進行訓(xùn)練。假設(shè)在訓(xùn)練樣本中對于查詢q存在<xi, xj>文檔序列對，需要計算2個概率值P1和P2。 P1這個概率是由神經(jīng)網(wǎng)絡(luò)模型計算出來的，函數(shù)如下 P2=e^(o_ij )/(1+e^(o_ij ) ) 其中，對于文檔xi, xj，神經(jīng)網(wǎng)絡(luò)模型f對其打分分別為o_i=f(xi), o_j=f(xj)，并記o_ij=o_i-o_j。 模型f：R^d→R R^d是文檔的特征空間，R是實數(shù)。 對于概率P2，它表示真實存在的概率，標記了文檔x_i和x_j的真實優(yōu)先關(guān)系。根據(jù)人工對文檔的打分，若文檔xi 與查詢q的相關(guān)度大于文檔xj，則記P2=1；反之記P2=0；若文檔xi 與查詢q的相關(guān)度等于文檔xj，則記P2=0.5。神經(jīng)網(wǎng)絡(luò)模型的目的是使計算出來的P1符合P2。 定義誤差函數(shù)，使用交叉熵來計算誤差，文檔x_i 與x_j的交叉熵計算公式為： C_ij=-P2 log?〖P1 〗-(1-P2 ) log?〖P1 〗 = -P2 o_ij + log?〖(1+e^(o_ij ))〗 對于整個模型的誤差，只需要將所有文檔序?qū)Φ恼`差進行求和就可以得到。得到誤差后，利用梯度下降的原理，計算出其梯度。然后利用BP型神經(jīng)網(wǎng)絡(luò)，就可以對其樣本進行訓(xùn)練(每次對兩個樣本的輸入進行一次神經(jīng)網(wǎng)絡(luò)的權(quán)重調(diào)整)。最后，每個樣本通過Shrinkage累加都會得到一個最終分數(shù)，直接按分數(shù)從大到小對樣本進行排序。 |
|
|
