Boost-GBDT

GBDT也是集成学习Boosting家族的成员，但是却和传统的Adaboost有很大的不同。回顾下Adaboost，我们是利用前一轮迭代弱学习器的误差率来更新训练集的权重，这样一轮轮的迭代下去。GBDT也是迭代，使用了前向分布算法，但是弱学习器限定了只能使用CART回归树模型，同时迭代思路和Adaboost也不同
GBDT在迭代过程中, 假设我们前一轮得到的强学习器是 $f_{t-1}(x)$ ,损失函数是 $L(y,f_{t-1}(x))$ , 那么本轮得到的新的一个学习器 $h_t(x)$ , 让本轮的损失函数 $L(y,f_t(x))=L(y, f_{t-1}(x)+h_t(x))$ , 本轮迭代的决策树, 要使得全局上的损失尽量变小.

GBDT 回归

GBDT的思想可以用一个通俗的例子解释，假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。
本质上, GBDT对于回归类问题, 拟合的是一个残差
GBDT也是一个加法模型, 用的也是前向分步算法:
$f_k(x)=\sum_{k=1}^{K}T(x;\theta_k)$
其中, $\theta_k$ 为决策树的参数, $K$ 为决策树的个数
假设一个训练集
$T=\{(x_1,y_1),(x_2,y_2),...,(x_i,y_i)\}$
我们知道GBDT使用CART作为其弱分类器, 对于回归问题, 输出数据将被划分为 $J$ 个互不相交的区域 $R_1,R_2,...,R_J,$ ,并且在每个区域上都有一个固定的输出常量 $c_j$ , 这个常量前面提到过,可能是一个均值, 那么树可以表示为:
$T(x;\theta)=\sum_{j=1}^{J}c_jI(x\in R)$
在前向分布算法的第 $k$ 步, 给定当前模型 $f_{k-1}(x)$ ,我们需要求解:
$\theta_k=argmin\sum_{i=1}^{m}L(y_i,f_{k-1}(x_i)+T(x_i,\theta_k))$
公式和文章开始部分是一致的, 那么我们得到了第 $k$ 步的树的参数, 那么对于这个损失函数 $L$ , 我们使用平方误差损失函数:
$L(y,f(x))=(y-f(x))^2$
其损失变为:
$L(y,f_{k-1}(x)+T(x;\theta_k))\\ =[y-f_{k-1}(x)-T(x;\theta_k)] \\ =[r-T(x;\theta_k)]$
此处 $r=y-f_{k-1}(x)$ , 就是当前模型拟合到的数据的残差
算法步骤如下

输入数据T
初始化树 $f_0=0$
对 $k=1,2,3..,K$ :

计算残差
$r_{ki}=y_i-f_k(x_i)$
拟合残差得到一个回归树 $T_k$
更新
$f_k=f_{k-1}(x)+T(x;\theta_k)$

得到完整的回归树

GBDT 负梯度拟合

前面的步骤, 损失函数是平方误差损失, 这类sunshi优化是简单的, 但也容易过拟合, 针对这一个问题, 有学者提出了梯度提升(gradient boosting)算法, 利用快速梯度下降的方法, 利用损失函数的负梯度作为回归算法中, 残差的近似值
$-[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]$
那么, 最终,GBDT的算法变为了:
算法步骤如下

输入数据T
初始化树 $f_0=0$
对 $k=1,2,3..,K$ :

对于 $i=1,2,...,m$ :
计算残差近似
$r_{ki}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]$
对 $r_{ki}$ 拟合一棵回归树, 最终我们得到 $K$ 棵树的结点区域 $R_{kj}$
对于 $j=1,2,...,J$ , 计算最优的拟合值:
$c_{kj}=argmin \sum L(y_i, f_{k-1}(x_i)+c)$
更新
$f_k=f_{k-1}(x)+T(x;\theta_k)$

得到回归树
$f(x)=\sum_{k=1}^{K}\sum_{j=1}^{J}c_{kj}I(x\in R_{kj})$
在上述步骤中, 如果损失函数是平方损失, 那么就按以前的步骤计算就可以了, 如果不是, 那就替换为残差近似. 对于区域 $J$ 来说, 这部分属于CART的内容

GBDT 分类问题

这里我们再看看GBDT分类算法，GBDT的分类算法从思想上和GBDT的回归算法没有区别，但是由于样本输出不是连续的值，而是离散的类别，导致我们无法直接从输出类别去拟合类别输出的误差。
为了解决这个问题，主要有两个方法，一个是用指数损失函数，此时GBDT退化为Adaboost算法。另一种方法是用类似于逻辑回归的对数似然损失函数的方法。也就是说，我们用的是类别的预测概率值和真实概率值的差来拟合损失。本文仅讨论用对数似然损失函数的GBDT分类。而对于对数似然损失函数，我们又有二元分类和多元分类的区别。

二元分类

如果使用指数损失, 那么GBDT其实相当于Adaboost, 如果使用逻辑回归里的对数似然,那么损失函数为:
$L(y,f(x))=\log(1+e^{-yf(x)})$

多元分类GBDT

多元比二元复杂一些, 多元对数似然,损失函数为:
$L(y,f(x))=-\sum_{k=1}^{K}y_k\log p_k(x)$
这里的 $k$ 为类别数
集合上两式，我们可以计算出第t轮的第i个样本对应类别l的负梯度误差为 $r_{til} = -\bigg[\frac{\partial L(y, f(x_i)))}{\partial f(x_i)}\bigg]$

GBDT总结

GBDT主要的优点有：

可以灵活处理各种类型的数据，包括连续值和离散值。
在相对少的调参时间情况下，预测的准备率也可以比较高。这个是相对SVM来说的。
使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。
GBDT的主要缺点有：
由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。

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