小象-机器学习互联网新技术教育领航者

本课件包括演示文稿、示例、代码、题库、和在课程范围外向任何第散播。任何其他人或机构不得盗版、、仿造其中的创意及内容，我们 课 咨

主要内样 、分类算法描前向分步算法+指数损失函

复习：线性回归的梯度

复习：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