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

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

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

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

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

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

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

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

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

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

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

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

CTCTTleaf假定當(dāng)前對(duì)以r為根 剪枝剪枝后，只保留r 以r為根 剪枝后

rCr剪枝前

令二者相等

Crα稱(chēng)為結(jié)點(diǎn)r的剪枝系數(shù)

Rleaf

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

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

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

隨機(jī)森

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

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

提升算給定輸入向量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使用梯度下降的方法近似計(jì)將樣本帶入基函數(shù)f得到f(x1),f(x2),...,f(xn) 為向量

Ly,

m

xinmy, nmy,

x!Ly,

提升算

Lyi,00

F 計(jì)算偽F

"

i1,2,!,pseudo

xFm1x使用數(shù)

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

arg

Ly,

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

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

!!

tmx

bjmIxRjmj margminLyi,Fm1xitmxi Fm Fm1 argminLy, !!

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

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

GBDT

FMM

x,yf

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

boosting的思

設(shè)訓(xùn)練數(shù)據(jù)集T={(x1,y1Dw,w! !, , 1,i1,2,!,

Adaboost：對(duì)于 NNemPGmxiyiwmiIGmxiyi

1log1m m

Adaboost：對(duì)于 , ! !,

wmiexpyGx,i1,2,!,ZZm

NZmwmiexpmyiGmxiN它的目的僅僅是使Dm+1成為一個(gè)概率分 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)計(jì)算G1的系數(shù)1

log1

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

更新訓(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,分類(lèi)器sign(f1(x))在訓(xùn)練數(shù)據(jù)集上有3個(gè)誤分類(lèi)

Gx

x x

e2=P(G2(xi)≠yi)0.2143(0.0715*3)計(jì)算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)+分類(lèi)器sign(f2(x))在訓(xùn)練數(shù)據(jù)集上有3個(gè)誤分類(lèi)

Gx

x

x

e3=P(G3(xi)≠yi)0.1820(0.0455*4)計(jì)算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)+分類(lèi)器sign(f3(x))在訓(xùn)練數(shù)據(jù)集上有0個(gè)誤分類(lèi)

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對(duì)于N極小化損失函

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

更新當(dāng)前模mfx xbx;m M得到加法模型fxfMxmbx;mM

前向分步算法與

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

fm

證 ,Gx

NN

expyiGxi

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

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

NN

I

Gxi其中， expy x

權(quán)值的計(jì)

w w

wmiyiGmxi yiGmxiwmiwmi

N

NNe

將G*(x)

*xG

I

Gxi

1log1m m

分類(lèi)錯(cuò)誤em

wmiIyiGxiN NNN

wmiIyiGxiNN

權(quán)值的更

fmxfm1xmGm

exp

wm1,iwm,iexpyimGm

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

Gm

i i

wmi

Gx

1mm

1log1

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