机器学习笔记3_Adaboost

一般来说，Ensemble模型适合于过拟合的模型，包括bagging和boosting.

3.1 Bagging

其中Bagging是单独训练每个分类器，然后用平均或者投票的方法组合，boosting的方法则是分类器之前存在强依赖，前一个分类器预测的解构会影响后一个分类器。随机森林就是DT的bagging。
在相同的深度下，随机森林并不会比决策树好很多，但会让分类的结果更平滑

3.2 Boosting

boosting的目的是用迭代的方法提高弱分类器的性能(improving weak classifier)

boosting的架构如下：
首先获取到第一个分类器 $f_1(x)$ ，然后用第二个分类器 $f_2(x)$ 去help $f_1(x)$ ,如果 $f_2(x)$ 与 $f_1(x)$ 很像，则可能对帮助的有限，我们更希望 $f_2(x)$ 是 $f_1(x)$ 的补充。bagging的时候不同分类器用的dataset的原有数据集重采样得到的，而在boosting时，不同dataset用到的数据集则是原数据集然后乘一个weight $u^{(i)}$ ,这样总的损失函数就是

$L(f) = \sum_{i=1}^{m} u^{(i)} l(f(x^{(i)}),\hat{y}^{(i)})$

其中 $l(f(x^{(i)}),\hat{y}^{(i)})$ 代表任意一种衡量预测值和真实值的损失函数。
adaboost的思路就是，假设有k个弱分类器 $f_1,f_2,...,f_k$ ，先用一组带权重的数据集 $\{x^{(i)},\hat{y}^{(i)},u^{(i)}_1\}$ 训练 $f_1$ ,然后更改每组训练数据的权重得到 $u^{(i)}_2$ ，这时新的带权重的数据集 $\{x^{(i)},\hat{y}^{(i)},u^{(i)}_2\}$ 在 $f_1$ 上的performance会变差，这时候训练 $f_2$ 使得新的数据集在 $f_2$ 上的performance变好。所谓表现差，就是正确率低，错误率高，用下边的式子来计算错误率：

$\epsilon_1 = \frac{ \sum_{i=1}^{m}u^{(i)}_1\delta(f_1(x^{(i)})\not=\hat{y}^{(i)})}{Z_1}$

其中 $\delta(f_1(x^{(i)})\not=\hat{y}^{(i)})$ 为符号函数，即两者不相等时取1，否则取0, $Z_1$ 则表示归一化权重：
$Z_1 = \sum_{i=1}^{m}u^{(i)}_1$
这是因为每次训练的数据集所用的权重加起来并不为1，因此需要归一化。这个式子看起来并不太好理解，为什么能表示错误率呢？我们举个简单的例子，假设权重为1，这时候 $Z_1=m$ ，也就是 $m$ 个样本，上式的分母就是 $m$ ，假设分类器 $f_1$ 让 $t$ 个样本分类错误，这时上边 $\epsilon_1$ 表达式的分子就是 $t$ ， $\frac{t}{m}$ 当然就是错误率啦。另一个角度也可以从概率的角度理解， $\frac{u^{(i)}_1}{Z_1}$ 可以表示对于每个样本预测错误的概率，然后加权平均就是第一个分类器的错误率啦（这种解释有点粗糙，仅帮助理解）。
注意，对于二分类，错误率 $\epsilon_1<0.5$ ，多分类的话 $\epsilon_1<1/K$ ，下边的公式也只介绍二类的情况。接下来把数据集从权重从 $u^{(i)}_1$ 变到 $u^{(i)}_2$ ，使得
$\frac{ \sum_{i=1}^{m}u^{(i)}_2\delta(f_1(x^{(i)})\not=\hat{y}^{(i)})}{Z_2}=0.5$
这是因为，最烂的二分类器，随机猜也有50%的准确率，我们要使 $f_1$ 的性能变差，就让 $f_1$ 对 $u^{(i)}_2$ 权重的训练数据 $\{x^{(i)},\hat{y}^{(i)},u^{(i)}_2\}$ 的错误率升到0.5即可。

那如何让 $f_1$ 错误率提升呢，也就是让 $f_1$ 分类效果变差呢？很简单的方法就是，让分类器 $f_1$ 对于分类正确的那些数据，我们给它更少的权重，对于分类错误的数据则给更大的权重。一个形象的例子如下：

在这里插入图片描述

假设刚开始的权重都是1，其中第1，3，4组训练数据分类正确，那的错误率就是0.25，然后呢，对于分类正确的数据，我们把训练集数据要乘的权重调低到，把分类错误的第二组数据的权重调高到这时候的错误率就升高到0.5了。总结规律就是：

如果 $f_1$ 能正确分类某个数据，也就是 $f_1(x^{i})\not =\hat{y}^{(i)}$ ，则把新训练数据的权重 $u^{(i)}_2$ 减小为原来的权重除以 $d_1$ : $u^{(i)}_2=u^{(i)}_1/d_1$
如果 $f_1$ 错误分类某个数据，也就是 $f_1(x^{i})=\hat{y}^{(i)}$ ，则把新训练数据的权重 $u^{(i)}_2$ 增大为原来的权重乘 $d_1$ : $u^{(i)}_2=u^{(i)}_1 d_1$
那 $d_1$ 怎么求呢？
$\frac{ \sum_{i=1}^{m}u^{(i)}_2\delta(f_1(x^{(i)})\not=\hat{y}^{(i)})}{Z_2}=0.5$
其实就是把上式中 $u^{(i)}_2$ 分类错误的展开成 $u^{(i)}_1d_1$ ，分类正确的展开乘 $u^{(i)}_1/d_1$ 然后解方程即可，经过一系列化简可以得到：
$\sum_{f_1(x^{(i)})=\hat{y}^{(i)}} u^{(i)}_1/d_1=\sum_{f_1(x^{(i)})\not=\hat{y}^{(i)}} u^{(i)}_1d_1$

也就是那些分类错误的数据的权重的和要等于分类正确的数据的权重的和，在经过推导得到 $d_1$ 为：
$d_1 = \sqrt{\frac{1-\epsilon_1}{\epsilon_1}}>1$
从上边可以看出，要更新数据的权重时，对于上一轮迭代分类错误的数据，我们要增加权重也就是乘一个数，对于上一轮迭代分类正确的数据，我们要减小权重也就是除一个数，有没有办法都用乘法表示呢？只需要把权重取对数即可，因为取对数后原来的函数仍然保持之前的单调性，除此之外，取完对数，之前的乘除运算就可以变成加减运算。上述 $d_1$ 取对数后就变成：
$a_1 = \log d_1 = \log (\sqrt{\frac{1-\epsilon_1}{\epsilon_1}})= \frac{1}{2}\log \frac{1-\epsilon_1}{\epsilon_1}$
这样更新的权重就都可以用乘法来表示

如果 $f_1$ 能正确分类某个数据，权重 $u^{(i)}_2$ 减小为 $u^{(i)}_2=u^{(i)}_1 e^{-a_1}$
如果 $f_1$ 错误分类某个数据，权重 $u^{(i)}_2$ 增加为 $u^{(i)}_2=u^{(i)}_1 e^{a_1}$
用一个式子表示 $u^{(i)}_2$ 的更新就是
$u^{(i)}_2 = u^{(i)}_1 \times \exp(-\hat{y}^{(i)}f_1(x^{(i)})a_1)$

当预测值和真实值相同时， $-\hat{y}^{(i)}f_1(x^{(i)})=-1$ 否则取1

综上，二分类的Adaboost算法就可以概况为：
输入： $\{(x^{(1)},\hat{y}^{(1)},u^{(1)}_1),（x^{(2)},\hat{y}^{(2)},u^{(2)}_1),...,（x^{(m)},\hat{y}^{(m)},u^{(m)}_1)\}$
其中 $y^{(i)}=\pm 1$ , 初始权重为 $u^{(i)}_1=1$

对于弱分类器 $t=1,2,...,T$
a. 用带权重 $\{u^{(1)}_1,u^{(2)}_1,...,u^{(m)}_1\}$ 的数据训练弱分类器t
b. 计算第t个弱分类器的分类错误率 $\epsilon_t$ (公式见上)
c. 用分类错误率计算权重要乘的数 $a_t$
d. 用 $u^{(i)}_2 = u^{(i)}_1 \times \exp(-\hat{y}^{(i)}f_1(x^{(i)})a_1)$ 更新数据集的权重
训练得到一系列的弱分类器 $f_1,f_2,...,f_T$
最后的强分类器就为：
$H(x) = sign(\sum_{t=1}^T a_t f_t(x))$
这里的 $a_t$ 就是前边用错误率计算出的 $a_t$

组合的策略从直观上解释就是错误率低的分类器权重更高，反之权重更低。

至此adaboost讲完

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,362评论 5赞 477
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,330评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,247评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,560评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,580评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,569评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,929评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,587评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,840评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,596评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,678评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,366评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,945评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,929评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,165评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 43,271评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,403评论 2赞 342

机器学习笔记3_Adaboost

3.1 Bagging

3.2 Boosting

推荐阅读更多精彩内容