本課件包括演示文稿、示例、代碼、題庫、和在課程范圍外向任何第散播。任何其他人或機構不得盜版、、仿造其中的創意及內容，我們 課 咨

主要內樣 、分類算法描前向分步算法+指數損失函

復習：線性回歸的梯度

復習：Logistic回歸的梯度方

復習：梯度下降的自適應學習xk=a，沿著負梯度方向，移動到xk+1=b，有baFafaf從x0為出發點，每次沿著當前函數梯度反方向移動x0,x1,x2,!,對應的各點函數值序列之間的關系fx0fx1fx2!fxn當n達到一定值時，函數f(x)收斂到局部最小

學習率α的計算標+αdk)的最小值。即 h'fxd

線性搜索求學習不斷將區間[α1α2]分成兩半，選擇端點異號的

dfxcfxT ,c 計算搜索方向上的最大步長，沿著搜索方向移f(xk+αdk)f())

復習：三種決策樹學習ID3：使用信息增益/互信息g(D,A)進行特征選C4.5：信息增益率gr(D,A)g(D,A)CART：基尼指(率)/gini

剪枝系數的確根據原損失函

CTNtH葉結點越多，決策樹越復雜，損失越大，修正

CTCTTleaf假定當前對以r為根 剪枝剪枝后，只保留r 以r為根 剪枝后

rCr剪枝前

令二者相等

Crα稱為結點r的剪枝系數

Rleaf

剪枝算對于給定的決策樹計算所有內部節點的剪枝系數查找最小剪枝系數的結點，剪枝得決策樹Tk重復以上步驟，直到決策樹Tk只有1個結得到決策樹序列T0T1T2…TK使用驗證樣本集選擇最 價函數：CTNtHt

隨機森隨機森林在bagging從樣本集中用Bootstrap采樣選出n從所有屬性中隨機選擇k個屬性，選擇最佳分割重復以上兩步m次，即建立了m棵CART決策這m個CART形成隨機森林，通過投票表決結果，

輸入數據x：M個樣本數據，每個數據包

隨機森

由決策樹和隨機森林的關系的思假定當前一定得到了m-1顆決策樹，是否可以通各個決策樹組成隨機森林后，最后的投票過程

提升的概提升是一個機器學習技術，可以用于回歸和分類問是依據損失函數的梯度方向，則稱之為梯度升(Gradientboosting)梯度提升弱函數集合()；提升算法近局部極小值。這種在函數域的梯度提升觀點對機器學習的很多領域有深刻影提升的理論意義：如果一個問題存在弱分類器，則

提升算給定輸入向量x和輸出變量y組成的若干訓練樣本義為2

假定最優函數為

Ly,F F*即 x,yF假定F(x)是一族基函數fi(x) M xFx!fM x

提升算法推首先，給定常函數00

nn

Lyi,

!

!n n

f

yi,Fm1

fxi

Ly, 梯度近似

f

nn

貪心法在每次選擇最優基函數f使用梯度下降的方法近似計將樣本帶入基函數f得到f(x1),f(x2),...,f(xn) 為向量

Ly,

m

xinmy, nmy,

x!Ly,

提升算

Lyi,00

F 計算偽F

"

i1,2,!,pseudo

xFm1x使用數

計算擬合殘差的基函數計算

arg

Ly,

梯度提升決策樹梯度提升的典型基函數即決策樹(尤其是在第m步的梯度提升是根據偽殘差數據計算決策樹性預測。使用指示記號I(x)，對于輸入x，tm(x)!tmx!

bjmIxRjmj。其中，bjm是樣本x在區域Rjm的預測。

!!

tmx

bjmIxRjmj margminLyi,Fm1xitmxi Fm Fm1 argminLy, !!

參數設置和正則對訓練集擬合過高會降低模型的泛化能力，需要使對復雜模型增加懲罰項，如：模型復雜度正比于葉葉結點數目控制了樹的層數，一般選擇4≤J≤8葉結點包含的最少樣本數梯度提升迭代次數

衰減因子、降采 0 稱ν每次迭代都對偽殘差樣本采用無放回的降采樣，用部分降采樣的額外好處是能夠使用剩余樣本

GBDT

FMM

x,yf

函數估計本來被認為是在函數空間而非參數空間的歸問題；而誤差函數換成多類別Logistic似然函數，對目標函數分解成若干基函數的 思考：如果對基函數的學習中，不止考慮函數的參數和權值，而是對樣本本身也，會得到什么結

boosting的思

設訓練數據集T={(x1,y1Dw,w! !, , 1,i1,2,!,

Adaboost：對于 NNemPGmxiyiwmiIGmxiyi

1log1m m

Adaboost：對于 , ! !,

wmiexpyGx,i1,2,!,ZZm

NZmwmiexpmyiGmxiN它的目的僅僅是使Dm+1成為一個概率分 wmiexpyGxZ expyGxZ wexpyGxZZm

1

MMfxmGmGxsignfx

m

舉

解Dw,w! !, , 1,i1,2,!, =

Gx

x

x

G1(x)在訓練數據集上的誤差率e1=P(G1(xi)≠yi)計算G1的系數1

log1

分類器sign(f1(x))在訓練數據集上有3個誤分類

更新訓練數據的權值分 , ! !, m1, wmiexpyGx,i1,2,!,ZZm

D2=(0.0715,0.0715,0.0715,0.0715,0.0715,0.1666,0.1666,0.1666,分類器sign(f1(x))在訓練數據集上有3個誤分類

Gx

x x

e2=P(G2(xi)≠yi)0.2143(0.0715*3)計算G2的系2 1log12

更新訓練數據的權值分 , ! !, m1, wmiexpyGx,i1,2,!,ZZm

D3=(0.0455,0.0455,0.0455,0.1667, 0.1060,0.1060,0.1060,f2(x)=0.4236G1(x)+分類器sign(f2(x))在訓練數據集上有3個誤分類

Gx

x

x

e3=P(G3(xi)≠yi)0.1820(0.0455*4)計算G3的系1log1 3 3

更新訓練數據的權值分 , ! !, m1, wmiexpyGx,i1,2,!,ZZm

D4=(0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,f3(x)=0.4236G1(x)+分類器sign(f3(x))在訓練數據集上有0個誤分類

IGxy

1expyfx NAdaboost誤差上N

i

mNN

后半部分

expyifxi

i w

yG

mim

myiGmMM m1 MMw1iexp1yiG1xiexpmyiGmxi Z1expmyiGmxiZ1expmyiGmxi iMMZ1w2iexpmyiGmxi MZ1Z2w3iexpmyiGmxiM Z1Z2!ZM1wMiexpMyiGMxii ZyGxm Zmwm1,iwmiexpmyiGmxiZ1w2,iw1iexp1yiG1xim

MM

后半部1

myGxNexpyifxiN

i

w1iexpmyiGmxiw1iexpmyiGmxi

Mw1iexp1yiG1xiexpmyiGmxi Z1expmyiGmxiZ1expmyiGmxi iM w miexpZZ1w2iexpmyiGM w miexpZ

yxyxM12 mimiZM12 mimi

yGx

Zmwm1,iwmiexpmyiGmxi

Z1Z2!ZM1wMiexpMyiGMxi

Z

yGxiMM

1

訓練誤差

142

2 Zm

其中， 222

NZmwmiexpmyiGmxiN

ww mww yiGmxi m1eemem

1

m2 14

1

訓練誤差NZmwmiexpmyiGmxiN ww m wwyiGmxi yiGmxi

e

m

1m mm 14m

1

取γ1,γ2…的最小 N1NN

Adaboost算法AdaBoost算法是模型為加法模型、損失函數

前向分步算M

基函數：bx;m基函數的參 基函數的系數：

前向分步算法的含在給定訓練數據及損失函數L(y,f(x))的條件

minLyi,mbxi; m,m N

minLyi,bxi;

前向分步算法的算法框訓練數據集T={(x1,y1),損失函數基函數集加法模型

前向分步算法的算法框初始化f0(x對于N極小化損失函

m,margminLyi,fm1xibxi;得到參數m

更新當前模mfx xbx;m M得到加法模型fxfMxmbx;mM

前向分步算法與

證到fm-1(x)：fm1xfm2xm1Gm1x1G1x!m1Gm1在第mm,Gmx和fmNN

fm

證 ,Gx

NN

expyiGxi

fm1xiwmi既不依賴α也不依賴G，所以與最小化無關。但wmi依賴于fm-1(x)，所以，每輪迭代會

基本分類器對于任意α>0，是上式最小的G(x)由下式mG*xmG

NN

I

Gxi其中， expy x

權值的計

w w

wmiyiGmxi yiGmxiwmiwmi

N

NNe

將G*(x)

*xG

I

Gxi

1log1m m

分類錯誤em

wmiIyiGxiN NNN

wmiIyiGxiNN

權值的更

fmxfm1xmGm

exp

wm1,iwm,iexpyimGm

權值和錯誤率的關鍵解事實上，根據Adaboost的構造過程，權值

Gm

i i

wmi

Gx

1mm

1log1

AdaBoostAdaBoost算法可以看做是采用指數損失函數Ada