绿色健康小清新

耐得住寂寞,守得住繁华

李宏毅机器学习-59-Ensemble

Ensemble

Framework of Ensemble

Ensemble的方法就是一种团队合作,好几个模型一起上的方法。

  • 第一步:通常情况是有很多的classifier,想把他们集合在一起发挥更强大的功能,这些classifier一般是diverse的,这些classifier有不同的属性和不同的作用。举个例子,就像大家一起出团去打王的时候,每个人都有自己需要做的工作,比如有人扮演坦,有人扮演补,有人扮演DD(输出)。
  • 第二步:就是要把classifier用比较好的方法集合在一起,就好像打王的时候坦和DD都站不同的位置,通常用ensemble可以让我们的表现提升一个档次,一般在kaggle之类的比赛中,ensemble用的最多的也是效果最好的,一般前几名都需要用ensemble。

Bagging

我们先来回顾一下bias和variance,对于简单的模型,我们会有比较大的bias但是有比较小的variance,如果是复杂的模型,我们则是比较小的bias但是有比较大的variance。从上图上看,在这两者的组合下,我们最后的误差(蓝色的线)会随着模型数目的增加,先下降后逐渐上升。

在之前的宝可梦例子中,根据不同的事件我们会得到一个模型,如果一个复杂的模型就会有很大的variance。这些模型的variance虽然很大,但是bias是比较小的,所以我们可以把不同的模型都集合起来,把输出做一个平均,得到一个新的模型f^\hat{f},这个结果可能和正确的答案就是接近的。Bagging就是要体现这个思想。 Bagging就是我们自己创造出不同的dataset,再用不同的dataset去训练一个复杂的模型,每个模型独自拿出来虽然方差很大,但是把不同的方差大的模型集合起来,整个的方差就不会那么大,而且偏差也会很小。

上图表示了用自己采样的数据进行Bagging的过程。在原来的N笔训练数据中进行采样,过程就是每次从N笔训练数据中取N‘(通常N=N’)建立很多个dataset,这个过程抽取到的可能会有重复的数据,但是每次抽取的是随机形成的dataset。每个dataset都有N’笔data,但是每个dataset的数据都是不一样的,接下来就是用一个复杂的模型对四个dataset都进行学习得到四个function。

接下来在testing的时候,就把这testing data放到这四个function里面,再把得出来的结果做平均(回归)或者投票(分类),通常来说表现(variance比较小)都比之前的好,这样就不容易产生过拟合。 做Bagging的情况:模型比较复杂,容易产生过拟合。(容易产生过拟合的模型:决策树)目的:降低方差


Decision Tree

Decision Tree

随机森林(Random Forest)就是决策树(Decision tree)做Bagging的版本。

假设给定的每个Object有两个feature,我们就用这个training data建立一颗树,如果x1x_{1}小于0.5就是yes(往左边走),当x1x_{1}大于0.5就是no(往右边走),接下来看x2x_{2},当x2x_{2}小于0.3时就是class1(对应坐标轴图中左下角的蓝色)当大于0.3时候就是class2(红色);对右边的当x2x_{2}小于0.7时就是红色,当x2x_{2}大于0.7就是蓝色。这是一个比较简单的例子,其实可以同时多个dimension,可以变得更复杂。

做决策树时会有几个地方需要注意:比如每个节点分支的数量,用什么样的标准来进行分支,什么时候停止分支,基本的假设等等问题。

Experiment: Function of Miku(初音未来例子)

描述:输入的特征是二维的,红色的部分是class1,蓝色的部分是class2,其中class1分布的和初音的样子是一样的。我们用决策树对这个问题进行分类。

上图可以看到,深度是5的时候效果并不好,图中白色的就是class1,黑色的是class2.当深度是10的时候有一点初音的样子,当深度是15的时候,基本初音的轮廓就出来了,但是一些细节还是很奇怪(比如一些凸起来的边角)当深度是20的时候,就可以完美的把class1和class2的位置区别开来,就可以完美地把初音的样子勾勒出来了。对于决策树,理想的状况下可以达到错误是0的时候,最极端的就是每一笔data point就是很深的树的一个节点,这样正确率就可以达到100%(树够深,决策树可以做出任何的function)但是决策树很容易过拟合,如果只用决策树一般很难达到好的结果


Random Forest

用决策树做Bagging就是随机森林。

传统的随机森林是通过之前的重采样的方法做,但是得到的结果是每棵树都差不多(效果并不好)。比较多的是随机的限制一些特征或者问题不能用,这样就能保证就算用同样的dataset,每次产生的决策树也会是不一样的,最后把所有的决策树的结果都集合起来,就会得到随机森林。

如果是用Bagging的方法的话,用out-of-bag可以做验证。用这个方法可以不用把label data划分成training set和validation set,一样能得到同样的效果。

具体做法:假设我们有training data是x1x^{1},x2x^{2},x3x^{3},x4x^{4},f1f_{1}我们只用第一笔和第二笔data训练(圆圈表示训练,叉表示没训练),f2f_{2}我们只用第三笔第四笔data训练,f3f_{3}用第一,第三笔data训练,f4f_{4}表示用第二,第四笔data训练,我们知道,在训练f1f_{1}f4f_{4}的时候没用用到x1x^{1},所以我们就可以用f1f_{1}f4f_{4}Bagging的结果在x1x^{1}上面测试他们的表现,同理,我们可以用f2f_{2}f3f_{3}Bagging的结果来测试x2x^{2},下面几个也是同样的道理。

最后用把每个测试的结果取平均的error,就作为最后的error。虽然我们没有明确的切出一个验证集,但是我们做测试的时候所有的模型并没有看过那些测试的数据。所有这个输出的error也是可以作为反映测试集结果的估测效果。

接下来是用随机森林做的实验结果:

强调一点是做Bagging更不会使模型能fit data,所有用深度为5的时候还是不能fit出一个function,所有就是5颗树的一个平均,相当于得到一个比较平滑的树。当深度是10的时候,大致的形状能看出来了,当15的时候效果就还不错,但是细节没那么好,当20 的时候就可以完美的把初音分出来。


Boosting

Boosting

Boosting是用在很弱的模型上的,当我们有很弱的模型的时候,不能fit我们的data的时候,我们就可以用Boosting的方法。

Boosting有一个很强的保证:如果你的机器学习算法能产生错误率小于50%的分类器,这个方法可以保证错误率达到0%

Boosting的结构:

  • 首先要找一个分类器f1(x)f_1{(x)}
  • 接下再找一个辅助f1(x)f_1{(x)}的分类器f2(x)f_2{(x)}(注意f2(x)f_2{(x)}如果和f1(x)f_1{(x)}很像,那么f2(x)f_2{(x)}的帮助效果就不好,所以要尽量找互补的f2(x)f_2{(x)},能够弥补f1(x)f_1{(x)}没办法做到的事情)
  • 得到第二个分类器f2(x)f_2{(x)}
  • 最后就结合所有的分类器得到结果

注意:Boosting的训练是有顺序的(sequentially),Bagging是没有顺序的(可以同时train)

How to obtain different classifiers?

制造不同的训练数据来得到不同的分类器

  • 用重采样的方法来训练数据得到新的数据集
  • 用重新赋权重的的方法来训练数据得到新的数据集,上图中用u来代表每一笔data的权重,可以通过改变weight来制造不同的data,举例来说就是刚开始都是1,第二次就分别改成0.4,2.1,0.7,这样就制造出新的data set。但是在实际中,就算改变权重,对训练没有太大影响。在训练时,原来的loss function是L(w)=nl(f(xn),y^n)L(w)=\sum\limits_{n}l(f(x^n),\hat{y}^n)其中ll可以是任何不同的function,只要能衡量f(xn)f(x^n)y^n\hat{y}^n之间的差距就行,然后用gradient descent 的方法来最小化这个L(total loss function)当加上权重后,变成了L(w)=nunl(f(xn),y^n)L(w)=\sum\limits_{n}u_nl(f(x^n),\hat{y}^n),相当于就是在原来的基础上乘以uu。这样从loss function来看,如果有一笔data的权重比较重,那么在训练的时候就会被多考虑一点。

boosting 是一种将弱分类器转化为强分类器的方法统称,而adaboost是其中的一种,采用了exponential loss function(其实就是用指数的权重),根据不同的loss function还可以有其他算法,比如L2Boosting, logitboost…

我们接下来会介绍Adaboost !

Adaboost

Adaboost

想法:先训练好一个分类器f1(x)f_1(x),要找一组新的training data,让f1(x)f_1(x)在这组data上的表现很差,然后让f2(x)f_2(x)在这组training data上训练。

怎么找一个新的训练数据集让f1(x)f_1(x)表现差?

ϵ1\epsilon_1就是训练数据的error rate:

ϵ1=nu1nδ(f1(xn)y^n)Z1\epsilon_1 = \frac{\sum_nu_1^n\delta(f_1(x^n)≠\hat{y}^n)}{Z_1}

这个就是对所有训练的样本求和,δ(f1(xn)y^n)\delta(f_1(x^n)\neq\hat{y}^n)是计算每笔的training sample分类正确与否,用0来表示正确,用1来表示错误,然后乘以一个weightuu,然后做normalization,这个Z1Z_1标准化就是所有的weight的和。这里的ϵ1<0.5\epsilon_1<0.5

然后我们用u2u_2的权重来进行计算得到error rate恰好等于0.5。这个过程相当于重新给训练数据赋权重,原来用u1u^1 作为训练数据的权重,现在用u2u^2作为训练数据的权重,在新的权重上,f1(x)f_1(x)的表现就是随机的,接下来我们拿这组新的训练数据集再去训练f2(x)f_2(x),这样的f2(x)f_2(x)f1(x)f_1(x)就是互补的。

例子

假设我们上面的四组训练数据,权重就是u1u_1u4u_4,并且每个初始值都是1,我们现在用这四组训练数据去训练一个模型f1(x)f_1(x),假设f1(x)f_1(x)只分类正确其中的三笔训练数据,所以ϵ1=0.25\epsilon_1=0.25然后我们改

变每个权重,把对的权重改小一点,把第二笔错误的权重改大一点(就比如当你做完考卷,老师说把你错误题目的分数增大,你就会很生气,这里对应的就是让f1(x)f_1(x)在新的训练集上表现差)这样一来,f1(x)f_1(x)在新的训练数据集上表现就会变差ϵ1=0.5\epsilon_1=0.5

然后在得到的新的训练数据集上训练得到f2(x)f_2(x),这个f2(x)f_2(x)训练完之后得到的ϵ2\epsilon_2会比0.5小。


Reweight的具体流程

假设训练数据xnx^n会被f1(x)f_1(x)分类错,那么就把第n笔data的u1nu^n_1乘上d1d_1变成d2d_2,这个d1d_1是大于1的值(也就是把错误分类的data权重提高)

如果xnx^n正确的被f1(x)f_1(x)分类的话,那么就用u1nu^n_1除以d1d_1变成d2d_2(也就是把正确分类的data的权重减少)
f2(x)f_2(x)就会在新的权重u2nu^n_2上进行训练。

对于d1d_1

对于图中分子部分分类错误的f1(xn)y^nf_1(x^n)\neq\hat{y}^n对应的u1nu^n_1就乘上d1d_1

nu2nδ(f1(xn)y^n)=f1(xn)y^nu1nd1\sum_nu_2^n\delta(f_1(x^n)≠\hat{y}^n) = \sum_{f_1(x^n)≠\hat{y}^n}u_1^nd_1

再看分母的部分,Z2Z_2就等于nu2n\sum\limits_n{u^n_2},同时也等于后面分类错误和分类正确的两个u1nu^n_1的权重和:

Z2=nu2n=f1(xn)y^nu2n+f1(xn)=y^nu2n=f1(xn)y^nu1d1+f1(xn)=y^nu1nd1Z_2 = \sum_nu^n_2 = \sum_{f_1(x^n)≠\hat{y}^n}u_2^n + \sum_{f_1(x^n)=\hat{y}^n}u_2^n = \sum_{f_1(x^n)≠\hat{y}^n}u_1d_1+\sum_{f_1(x^n)=\hat{y}^n}\frac{u_1^n}{d_1}

然后将上述两个式子带进:

nu2nδ(f1(xn)y^n)Z2=0.5\frac{\sum_nu_2^n\delta(f_1(x^n)≠\hat{y}^n)}{Z_2} = 0.5

得到:

f1(xn)y^nu1nd1f1(xn)y^nu1d1+f1(xn)=y^nu1nd1=0.5\frac{\sum_{f_1(x^n)≠\hat{y}^n}u_1^nd_1}{\sum_{f_1(x^n)≠\hat{y}^n}u_1d_1+\sum_{f_1(x^n)=\hat{y}^n}\frac{u_1^n}{d_1}} = 0.5

然后再取个倒数就可以得到图中最后一个式子:

f1(xn)y^nu1d1+f1(xn)=y^nu1nd1f1(xn)y^nu1nd1=2\frac{\sum_{f_1(x^n)≠\hat{y}^n}u_1d_1+\sum_{f_1(x^n)=\hat{y}^n}\frac{u_1^n}{d_1}}{\sum_{f_1(x^n)≠\hat{y}^n}u_1^nd_1} = 2

f1(xn)y^nu1d1+f1(xn)=y^nu1nd1f1(xn)y^nu1nd1=2\frac{\sum_{f_1(x^n)≠\hat{y}^n}u_1d_1+\sum_{f_1(x^n)=\hat{y}^n}\frac{u_1^n}{d_1}}{\sum_{f_1(x^n)≠\hat{y}^n}u_1^nd_1} = 2

上面这个式子可以进行化简:

1+f1(xn)=y^nu1nd1f1(xn)y^nu1nd1=2f1(xn)=y^nu1nd1f1(xn)y^nu1nd1=11 +\frac{\sum_{f_1(x^n)=\hat{y}^n}\frac{u_1^n}{d_1}}{\sum_{f_1(x^n)≠\hat{y}^n}u_1^nd_1} = 2 \leftarrow\rightarrow \frac{\sum_{f_1(x^n)=\hat{y}^n}\frac{u_1^n}{d_1}}{\sum_{f_1(x^n)≠\hat{y}^n}u_1^nd_1} = 1

两边同乘分母,可以得到:

f1(xn)=y^nu1nd1=f1(xn)y^nu1nd1\sum_{f_1(x^n)=\hat{y}^n}\frac{u_1^n}{d_1} = {\sum_{f_1(x^n)≠\hat{y}^n}u_1^nd_1}

1d1\frac{1}{d_1}d1d_1提取出来:

1d1f1(xn)=y^nu1n=d1f1(xn)y^nu1n\frac{1}{d_1}\sum_{f_1(x^n)=\hat{y}^n}u_1^n= d_1{\sum_{f_1(x^n)≠\hat{y}^n}u_1^n}

其中由ϵ1=f1(xn)y^nu1nZ1\epsilon_1 = \frac{\sum_{f_1(x^n)≠\hat{y}^n}u_1^n}{Z_1}又可以推得:

f1(xn)=y^nu1n=Z1(1ϵ1)f1(xn)y^nu1n=Z1ϵ1\sum_{f_1(x^n)=\hat{y}^n}u_1^n = Z_1(1-\epsilon_1) \\ \sum_{f_1(x^n)≠\hat{y}^n}u_1^n = Z_1\epsilon_1

带进上一个式子中,可以得到:

1d1Z1(1ϵ1)=d1Z1ϵ1\frac{1}{d_1}Z_1(1-\epsilon_1) = d_1Z_1\epsilon_1

最后能得到结果是:

d1=(1ϵ1)/ϵ1d_1=\sqrt{(1-\epsilon_1)/\epsilon_1}

然后用这个d1d_1去乘或者除权重,就能得到让f2(x)f_2(x)表现不好的新的训练数据集。

注意:d1d_1是大于1的,因为ϵ1\epsilon_1是小于0.5,所以该式子会大于1


Algorithm for AdaBoost(算法)

给定一笔训练数据以及其权重,设置初始的权重为1,接下来用不同的权重来进行很多次迭代训练弱分类器,然后再把这些弱的分类器集合起来就变成一个强的分类器。其中在每次迭代中,每一笔训练数据都有其对应的权重。

用每个弱分类器对应的权重训练出每个弱分类器ft(x)f_t(x),计算ft(x)f_t(x)在各自对应权重中的错误率ϵt\epsilon_t

然后就可以重新给训练数据赋权值,如果分类错误的数据,就用原来的utnu^n_t乘上dtd_t来更新其权重,反之就把原来的utnu^n_t除以dtd_t得到一组新的权重,然后就继续在下一次迭代中继续重复操作。(其中d1=(1ϵ1)/ϵ1d_1=\sqrt{(1-\epsilon_1)/\epsilon_1}

或者对dtd_t我们还可以用αt=ln(1ϵ)/ϵ\alpha_t=ln\sqrt{(1-\epsilon)/\epsilon}来代替,这样我们就可以直接统一用乘的形式来更新utnu^n_t,变成了乘以exp(αt)exp(\alpha_t)或者乘以exp(αt)exp(-\alpha_t),这里的正负1用y^nft(xn)-\hat{y}^nf_t(x^n)来取正负号(当分类错误该式子就是正的,分类正确该式子就是负的)这样表达式子就会更加简便。

经过刚才的训练之后我们就得到了f1(x)f_1(x)fT(x)f_T(x)

一般有两种方法进行集合:

  • Uniform weight:我们把T个分类器加起来看其结果是正的还是负的(正的就代表class1,负的就代表class2),这样可以但不是最好的,因为分类器中有好有坏,如果每个分类器的权重都一样的,显然是不合理的。

  • Non-uniform weight:在每个分类器前都乘上一个权重αt\alpha_t,然后全部加起来后取结果的正负号,这种方法就能得到比较好的结果

这里的αt=ln(1ϵ)/ϵ\alpha_t=ln\sqrt{(1-\epsilon)/\epsilon}从后面的例子可以看到,错误率比较低的ϵt\epsilon_t=0.1得到最后的αt\alpha_t=1.10就比较大,反之,如果错误率比较高的ϵt\epsilon_t=0.4得到最后的αt\alpha_t=0.20就比较小。

总结:错误率比较小的分类器,最后在最终结果的投票上会有比较大的权重。


Toy example(例子)

Decision stump:假设所有的特征都分布在二维平面上,在二维平面上选一个维度切一刀,其中一边当做class1,另外一边当做class2。

上图中t=1时,我们先用decision stump找一个f1(x)f_1(x),左边就是正类,右边就是负类,其中会发现有三笔data是错误的,所以能得到错误率是0.3,d1d_1=1.53(训练数据更新的权重),α1\alpha_1=0.42(在最终结果投票的权重)

然后改变每笔训练数据的权重,分类错误的权重就要变大(乘以1.53),分类对的权重就变小(0.65)

t=2和t=3按照同样的步骤,就可以得到第二和第三个分类器。由于设置了三次迭代,这样训练就结束了,用之前每个分类器乘以对应的权重,就可以得到最终分类器。

结果整合:这个三个分类器把平面分割成六个部分,左上角三个分类器都是蓝色的,那就肯定就蓝色的。上面中间部分第一个分类器是红色的,第二个第三个是蓝色的,但是后面两个加起来的权重比第一个大,所以最终中间那块是蓝色的,对于右边部分,第一个第二个分类器合起来的权重比第三个蓝色的权重大,所以就是红色的。下面部分也是按照同样道理,分别得到蓝色,红色和红色。所以这三个弱分类器其实本事都会犯错,但是我们把这三个整合起来就能达到100%的正确率了。


AdaBoost证明推导

上式中的H(x)H(x)是最终分类结果的表达式,αt\alpha_t是权重(与ϵt\epsilon_t有关),ϵt\epsilon_t是错误率。

先计算总的训练数据集的错误率,也就是1Nnδ(H(xn)yn^)\frac{1}{N}\sum\limits_{n}\delta\left({H(x^n)\neq\hat{y^n}}\right)其中H(xn)yn^H(x^n)\neq\hat{y^n}得到的就是1,反之如果H(xn)=yn^H(x^n)=\hat{y^n}就是0

进一步,可以把H(xn)yn^H(x^n)\neq\hat{y^n}写成yn^g(xn)<0\hat{y^n}g(x^n)<0,如果yn^g(xn)\hat{y^n}g(x^n)是同号的代表是正确的,如果是异号就代表分类错误的。整个错误率有一个上界就是1Nnexp(y^ng(xn))\frac{1}{N}\sum\limits_{n}exp(-\hat{y}^ng(x^n))
上图中横轴是yn^g(xn)\hat{y^n}g(x^n),绿色的线代表的是δ\delta的函数,蓝色的是exp(y^ng(xn))exp(-\hat{y}^ng(x^n))也就是绿色函数的上限。

证明上界函数会越来越小

上面我们求出来的错误率的上界是:

1Nnexp(y^ng(xn))=1NnuT+1n=1NZT+1\frac{1}{N}\sum\limits_{n}exp(-\hat{y}^ng(x^n)) = \frac{1}{N}\sum_nu_{T+1}^n = \frac{1}{N}Z_{T+1}

上式证明中,思路是先求出ZT+1Z_T+1(也就是第T+1次训练数据集权重的和),就等于nuT+1n\sum\limits_{n}u_{T+1}^n

ut+1nu_{t+1}^nutnu_{t}^n有关系,通过联立u1nu_{1}^nut+1nu_{t+1}^n的式子:

u1n=1ut+1n=utn×exp(y^nft(xn)αt)u_1^n = 1 \\ u_{t+1}^n = u_t^n × exp(-\hat{y}^nf_t(x^n)\alpha_t)

能得到T次连乘的exp(y^nft(xn)αt)exp(-\hat{y}^nf_t(x^n)\alpha_t),也就是uT+1nu_{T+1}^n

t=1Texp(y^nft(xn)αt)\prod_{t=1}^T exp(-\hat{y}^nf_t(x^n)\alpha_t)

然后在累加起来得到ZT+1Z_T+1

ZT+1=nt=1Texp(y^nft(xn)αt)Z_{T+1} = \sum_n\prod_{t=1}^T exp(-\hat{y}^nf_t(x^n)\alpha_t)

同时把累乘符号放到exp里面去变成了累加:

ZT+1=nexp(y^nt=1Tft(xn)αt)Z_{T+1} = \sum_n exp(-\hat{y}^n\sum_{t=1}^Tf_t(x^n)\alpha_t)

由于y^n\hat{y}^n是迭代中第n笔的正确答案,所以和累乘符号没有关系,就会发现后面的t=1ft(xn)αt\sum\limits_{t=1}f_t(x^n)\alpha_t恰好等于图片最上面的g(x)g(x)

这样就说明了,训练数据的权重的和会和训练数据的错误率有关系。接下来就是证明权重的和会越来越小就可以了。

Z1Z_1的权重就是每一笔初试权重的和N,然后这里的ZtZ_{t}就是要根据Zt1Z_{t-1}来求出;

  • 对于分类错误的,用Zt1Z_{t-1}乘以ϵt\epsilon_t乘以exp(αt)exp(\alpha_t)
  • 对于分类正确的,用Zt1Z_{t-1} 乘以1ϵt1-\epsilon_t再乘以exp(αt)exp(-\alpha_t)

然后再把αt\alpha_t代入到这个式子中化简得到得到:

=Zt1ϵt(1ϵt)ϵt+Zt1(1ϵt)ϵt(1ϵt)=Zt1×2ϵt(1ϵt)\begin{aligned} & = Z_{t-1}\epsilon_t\sqrt{\frac{(1-\epsilon_t)}{\epsilon_t}}+Z_{t-1}(1-\epsilon_t)\sqrt{\frac{\epsilon_t}{(1-\epsilon_t)}} \\ & =Z_{t-1}\times{2\sqrt{\epsilon_t(1-\epsilon_t)}} \end{aligned}

进一步推导可以得到:

ZT+1=Nt=1T2ϵt(1ϵt)Z_{T+1} = N\prod_{t=1}^{T}2\sqrt{\epsilon_t(1-\epsilon_t)}

其中,ϵt\epsilon_t是错误率,肯定小于0.5,所以2ϵt(1ϵt)2\sqrt{\epsilon_t(1-\epsilon_t)}最大值是当ϵt=0.5\epsilon_t=0.5时,最大值为1,所以ZtZ_t小于等于Zt1Z_{t-1}
ZT+1Z_{T+1}就是N乘以T个2ϵt(1ϵt)2\sqrt{\epsilon_t(1-\epsilon_t)}

最后我们知道,这样的一来训练数据的错误率就会越来越小!


AdaBoost的神秘现象

其中图中x轴是训练的次数,y轴是错误大小,从这张图我们发现训练数据集上的错误率其实很快就变成了0(大概在第五次左右就是0),但是测试数据集上错误一直在不断下降。

我们把y^g(x)\hat{y}g(x)定义为margin

原因:图中是5,100,1000个权重的分类器结合在一起时的分布图,当5个分类器结合的时候,其实margin已经大于0了,但是当增加弱分类器的数量的时候,margin还会一直变大,增加margin的好处就是增加这个方法鲁棒性,也就是在测试集上能得到比较好的结果。

为什么margin会增加?

该图是y^ng(xn)\hat{y}^ng(x^n)的函数图像,红色的线就是AdaBoost的目标函数,从图中可以看出AdaBoost的在y^\hat{y}为0时,依然能不断的下降,也就是让y^ng(xn)\hat{y}^ng(x^n)(margin)能不断增大,得到更小的错误。


AdaBoost+决策树做初音的例子

本来深度是5的决策树是不能做好初音的分类(只能通过增加深度来进行改进),但是现在有了AdaBoost的决策树是互补的,所以用AdaBoost就可以很好的进行分类。T代表AdaBoost运行次数,图中可知用AdaBoost,100棵树就可以很好的对初音进行分类。


Gradient Boosting

Gradient Boosting是Boosting的更泛化的一个版本。

具体步骤:

  • 初始化一个g0(x)=0g_{0}(x)=0,
  • 现在进行T次的迭代:
    • 找到一组ft(x)f_t(x)αt\alpha_t来共同改进gt1(x)g_{t-1}(x)gt1(x)g_{t-1}(x)就是之前得到所有的f(x)f(x)α\alpha乘积的和
    • 把找到的一组ft(x)f_t(x)αt\alpha_t(与gt1(x)g_{t-1}(x)互补)加上原来的gt1(x)g_{t-1}(x)得到新的gt(x)g_{t}(x),这样gt(x)g_{t}(x)就比原来的gt1(x)g_{t-1}(x)更好
  • 最后再得到T个迭代的H(x)H(x)

这里的cost function是L(g)=nl(y^n,g(xn))L(g)=\sum\limits_{n}l(\hat{y}^n,g(x^n)),其中lly^n\hat{y}^ng(xn)g(x^n)的差异(loss function,这个函数可以直接选择,可以是交叉熵,也可以是均方误差)这里定义成了exp(y^ng(xn))exp(-\hat{y}^ng(x^n))

接下来我们要最小化损失函数,我们就需要用梯度下降来更新每个g(x)g(x)

从梯度下降角度考虑:上图式子中,我们需要用函数g(x)g(x)L(g)L(g)求梯度,然后用这个得到的梯度去更新gt1g_{t-1},得到新的gtg_{t}
这里对L(g)L(g)求梯度的函数g(x)g(x)就是可以想成包含很多参数的,通过调整参数就能改变函数的形状,这样就可以对L(g)L(g)做偏微分。

从Boosting角度考虑,红色框的两部分是同方向的,如果ft(x)f_t(x)和微分的方向是一致的话,那么就可以把ft(x)f_t(x)加上gt1(x)g_{t-1}(x),就可以让新的损失减少。

我们希望ft(x)f_t(x)nexp(y^ngt(xn))(y^n)\sum\limits_{n}exp(-\hat{y}^ng_t(x^n))(\hat{y}^n)方向越一致越好。

所以我们构造一个函数让两个式子相乘求其最大值,这样就能保证这两个式子方向很一致。对于得到的新式子,exp(y^ngt(xn))exp(-\hat{y}^ng_t(x^n))就是权重,经过计算之后发现这个权重恰好就是AdaBoost上的权重

这里找出来的ft(x)f_t(x),其实也就是AdaBoost找出来的ft(x)f_t(x),所以在AdaBoost的时候,找一个弱的分类器ft(x)f_t(x)的时候,就相当于用梯度下降更新损失,值得损失会变小。

由于求ft(x)f_t(x)是很不容易才找到的,所以我们这里就会给ft(x)f_t(x)配一个最好的αt\alpha_t,把ft(x)f_t(x)的价值发挥到最大。

对于αt\alpha_t,αt\alpha_t就很像学习率,但是这里有点不一样,我们是固定ft(x)f_t(x),穷举所有的αt\alpha_t,找到一个αt\alpha_t使得gt(x)g_{t}(x)的损失更小
实际中就是求解一个最优化问题,找出一个αt\alpha_t,让L(g)L(g)最小。

巧合的是找出来的αt\alpha_t就是αt=ln(1ϵt)/ϵt\alpha_t=ln\sqrt{(1-\epsilon_t)/\epsilon_t}

AdaBoost其实可以想成在做梯度下降,只是这个梯度是一个函数,然后有一个很好的方法来决定学习率的这样一个问题。
Gradient Boosting有一个好的就是我们可以任意更改目标函数。这样就可以创造出很多新的方法。


Stacking

上图中,把一笔数据x输入到四个不同的模型中,然后每个模型输出一个y,然后用投票法决定出最好的(对于分类问题)

但是有个问题就是并不是所有系统都是好的,有些系统会比较差,但是如果采用之前的设置低权重的方法又会伤害小毛的自尊心,这样我们就提出一种新的方法:

把得到的y当做新的特征输入到一个最终的分类器中,然后再决定最终的结果。

对于这个最终的分类器,应当采用比较简单的函数(比如说逻辑回归),不需要再采用很复杂的函数,因为输入的y已经训练过了。

在做stacking的时候我们需要把训练数据集再分成两部分,一部分拿来学习最开始的那些模型,另外一部分的训练数据集拿来学习最终的分类器。原因是有些前面的分类器只是单纯去拟合training data,比如小明的代码可能是乱写的,他的分类器就是很差的,他做的只是单纯输出原来训练数据集的标签,但是根本没有训练。如果还用一模一样的训练数据去训练最终分类器,这个分类器就会考虑小明系统的功能。所以我们必须要用另外一部分的数据来训练最终的分类器,然后最终的分类器就会给之前的模型不同的权重。

-------------本文结束感谢您的阅读-------------
六经蕴籍胸中久,一剑十年磨在手

欢迎关注我的其它发布渠道