小象-機器學(xué)習(xí)互聯(lián)網(wǎng)新技術(shù)教育領(lǐng)航者

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

主要內(nèi)樣 、分類算法描前向分步算法+指數(shù)損失函

復(fù)習(xí)：線性回歸的梯度

復(fù)習(xí)：Logistic回歸的梯度方

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

學(xué)習(xí)率α的計算標+αdk)的最小值。即 h'fxd

線性搜索求學(xué)習(xí)不斷將區(qū)間[α1α2]分成兩半，選擇端點異號的

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

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

剪枝系數(shù)的確根據(jù)原損失函

CTNtH葉結(jié)點越多，決策樹越復(fù)雜，損失越大，修正

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

rCr剪枝前

令二者相等

Crα稱為結(jié)點r的剪枝系數(shù)

Rleaf

剪枝算對于給定的決策樹計算所有內(nèi)部節(jié)點的剪枝系數(shù)查找最小剪枝系數(shù)的結(jié)點，剪枝得決策樹Tk重復(fù)以上步驟，直到?jīng)Q策樹Tk只有1個結(jié)得到?jīng)Q策樹序列T0T1T2…TK使用驗證樣本集選擇最 價函數(shù)：CTNtHt

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

輸入數(shù)據(jù)x：M個樣本數(shù)據(jù)，每個數(shù)據(jù)包

隨機森

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

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

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

假定最優(yōu)函數(shù)為

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

提升算法推首先，給定常函數(shù)00

nn

Lyi,

!

!n n

f

yi,Fm1

fxi

Ly, 梯度近似

f

nn

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

Ly,

m

xinmy, nmy,

x!Ly,

提升算

Lyi,00

F 計算偽F

"

i1,2,!,pseudo

xFm1x使用數(shù)

計算擬合殘差的基函數(shù)計算

arg

Ly,

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

bjmIxRjmj。其中，bjm是樣本x在區(qū)域Rjm的預(yù)測。

!!

tmx

bjmIxRjmj margminLyi,Fm1xitmxi Fm Fm1 argminLy, !!

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

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

GBDT

FMM

x,yf

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

boosting的思

設(shè)訓(xùn)練數(shù)據(jù)集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)在訓(xùn)練數(shù)據(jù)集上的誤差率e1=P(G1(xi)≠yi)計算G1的系數(shù)1

log1

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

更新訓(xùn)練數(shù)據(jù)的權(quán)值分 , ! !, 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))在訓(xùn)練數(shù)據(jù)集上有3個誤分類

Gx

x x

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

更新訓(xùn)練數(shù)據(jù)的權(quán)值分 , ! !, 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))在訓(xùn)練數(shù)據(jù)集上有3個誤分類

Gx

x

x

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

更新訓(xùn)練數(shù)據(jù)的權(quán)值分 , ! !, 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))在訓(xùn)練數(shù)據(jù)集上有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

訓(xùn)練誤差

142

2 Zm

其中， 222

NZmwmiexpmyiGmxiN

ww mww yiGmxi m1eemem

1

m2 14

1

訓(xùn)練誤差NZmwmiexpmyiGmxiN ww m wwyiGmxi yiGmxi

e

m

1m mm 14m

1

取γ1,γ2…的最小 N1NN

Adaboost算法AdaBoost算法是模型為加法模型、損失函數(shù)

前向分步算M

基函數(shù)：bx;m基函數(shù)的參 基函數(shù)的系數(shù)：

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

minLyi,mbxi; m,m N

minLyi,bxi;

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

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

m,margminLyi,fm1xibxi;得到參數(shù)m

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

前向分步算法與

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

fm

證 ,Gx

NN

expyiGxi

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

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

NN

I

Gxi其中， expy x

權(quán)值的計

w w

wmiyiGmxi yiGmxiwmiwmi

N

NNe

將G*(x)

*xG

I

Gxi

1log1m m

分類錯誤em

wmiIyiGxiN NNN

wmiIyiGxiNN

權(quán)值的更

fmxfm1xmGm

exp

wm1,iwm,iexpyimGm

權(quán)值和錯誤率的關(guān)鍵解事實上，根據(jù)Adaboost的構(gòu)造過程，權(quán)值

Gm

i i

wmi

Gx

1mm

1log1

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