集成学习真不难

1. Introduction

当做重要决定时, 大家可能都会考虑吸取多个专家而不只是一个人的意见. 集成学习也是如此. 集成学习就是组合多个个体学习器, 最后可以得到一个更好的学习器.

集成学习方法:

• Bagging: 大部分情况下, 经过 bagging 得到的结果方差 (Variance) 更小, 且个体学习器之间不存在强依赖关系.
• Boosting: 大部分情况下, 经过 boosting 得到的结果偏差 (Bias) 更小, 且个体学习器之间存在强依赖关系.

集成学习的第一个问题就是如何得到若干个个体学习器, 这里我们有两种选择.

• 第一种就是所有的个体学习器都是一个种类的, 或者说是同质的. 比如都是决策树个体学习器, 或者都是神经网络个体学习器.
• 第二种是所有的个体学习器不全是一个种类的, 或者说是异质的. 比如我们有一个分类问题, 对训练集采用支持向量机个体学习器, 逻辑回归个体学习器和朴素贝叶斯个体学习器来学习, 再通过某种结合策略来确定最终的分类强学习器.

目前来说, 同质个体学习器的应用是最广泛的, 一般我们常说的集成学习的方法都是指的同质个体学习器. 而同质个体学习器使用最多的模型是CART决策树和神经网络.

2. Bagging

Bagging 是 Bootstrap Aggregating 的缩写. 我们之前在模型选择和评估已经介绍了过一次了, 我们重温一遍, 其具体步骤如下:

给定包含 $m$ 个样本的数据集 $D$, 我们对它进行采样数据集 $D’$: 每次随机从 $D$ 中挑选一个样本, 将其拷贝放入 $D’$, 然后再将该样本放回初始数据集 $D$ 中, 使得该样本在下次采样时仍有可能被采到; 这个过程重复执行 $m$ 次后, 我们就得到了包含 $m$ 个样本的数据集 $D’$, 这就是自助采样的结果. 显然, $D$ 中的一部分样本会在 $D’$ 中多次出现, 而另外一部分样本不出现. 我们可以做一个简单的估计, 样本在 $m$ 次采样中始终不被采到的概率是 $(1-\frac{1}{m})^m$, 取极限得到:

$$\lim\limits_{m\rightarrow\inf}(1-\frac{1}{m})\approx\frac{1}{e}\approx0.368$$

通过自助采样, 初始数据集 $D$ 中约有 36.8% 的样本未出现在采样数据集 $D’$ 中. 于是我们可以将 $D’$ 用作训练集, $D\backslash D’$ 用作测试集.

在 Bagging 方法中, 利用bootstrap方法从整体数据集中采取有放回抽样得到N个数据集, 在每个数据集上学习出一个模型, 最后的预测结果利用N个模型的输出得到, 具体地: 分类问题采用N个模型预测投票的方式, 回归问题采用N个模型预测平均的方式. 图示如下:

对于 Bagging 需要注意的是, 每次训练集可以取全部的特征进行训练, 也可以随机选取部分特征训练, 例如随机森林就是每次随机选取部分特征.

2.1 Random Forest

随机森林是非常具有代表性的Bagging集成算法, 它在Bagging基础上进行了强化. 它的所有基学习器都是CART决策树, 传统决策树在选择划分属性时是在当前结点的属性集合 (假定有d个属性) 中选择最优属性. 但是随机森林的决策树, 现在每个结点的属性集合随机选择部分 $k$ 个属性的子集, 然后在子集中选择一个最优的特征来做决策树的左右子树划分, 一般建议 $k=\log_2d$. 分类决策树组成的森林就叫做随机森林分类器, 回归决策树所集成的森林就叫做随机森林回归器.

随机森林的算法实现思路非常简单, 只需要记住一句口诀: 抽等量样本, 选几个特征, 构建多棵树.

1. 抽等量样本

   随机森林训练每棵树之前, 都会从训练集中随机抽出一部分样本来训练. 所以说训练每棵树用到的样本其实都是有差别的, 这样就保证了不同的树可以重点学习不同的样本. 而为了达到抽等量样本的目的, 抽样方式一般是有放回的抽样, 也就是说, 在训练某棵树的时候，这一次被抽到的样本会被放回数据集中, 下一次还可能被抽到. 因此，原训练集中有的样本会多次被抽出用来训练, 而有的样本可能不会被使用到.

   但是不用担心有的样本没有用到, 只要训练的树的棵数足够多, 大多数训练样本总会被取到的. 有极少量的样本成为漏网之鱼也不用担心, 后边我们会筛选他们出来用来测试模型.

2. 选几个特征

   在训练某棵树的时候, 也不是将样本的所有特征都用来训练, 而是会随机选择一部分特征用来训练. 这样做的目的就是让不同的树重点关注不同的特征. 在scikit-learn中, 用“max_features”这个参数来控制训练每棵树选取的样本数.

3. 构建多棵树

   通过前面两个步骤, 训练多棵树. 鲁迅曾经说过: 世界上本没有森林, 长得树多了, 就成了森林. 正是一棵棵决策树构成了整个随机森林. 具体构建树的数量, 在scikit-learn中, 用“n_estimators”这个参数来控制.

那最终的预测结果怎么得到呢? 随机森林是非常民主的算法, 最终的结果由每棵决策树综合给出: 如果是分类问题, 那么对于每个测试集, 树都会预测出一个类别进行投票, 最终统计票数多的那个类别为最终类别. 如果是回归问题, 那就更简单了, 各个树得到的结果相加求得一个平均值为最终回归结果.

从上边的流程中可以看出，随机森林的随机性主要体现在两个方面：数据集的随机选取、每棵树所使用特征的随机选取。以上两个随机性使得随机森林中的决策树都能够彼此不同，提升系统的多样性，从而提升分类性能。

2.2 Code

我们已经具备了理论基础, 现在用一个案例在实操一下.

数据集: https://www.kaggle.com/mlg-ulb/creditcardfraud

项目地址: https://github.com/alvisdeng/Credit-Card-Fraud-Detection

3. Boosting

Boosting 指的是通过算法集合将弱学习器转换为强学习器. Boosting 的主要原则是训练一系列的弱学习器, 所谓弱学习器是指仅比随机猜测好一点点的模型, 例如较小的决策树, 训练的方式是利用加权的数据. 在训练的早期对于错分数据给予较大的权重.

对于训练好的弱分类器, 如果是分类任务按照权重进行投票, 而对于回归任务进行加权, 然后再进行预测. boosting 和 bagging 的区别在于是对加权后的数据利用弱分类器依次进行训练.

boosting 是一族可将弱学习器提升为强学习器的算法, 这族算法的工作机制类似:

1. 先从初始训练集训练出一个基学习器；
2. 再根据基学习器的表现对训练样本分布进行调整, 使得先前基学习器做错的训练样本在后续受到更多关注;
3. 基于调整后的样本分布来训练下一个基学习器;
4. 重复进行上述步骤, 直至基学习器数目达到事先指定的值 T, 最终将这 T 个基学习器进行加权结合.

提到结合, 我们就不得不来看一下有哪些个体学习器的结合策略:

1. 平均法

   对于数值类的回归预测问题, 通常使用的结合策略是平均法. 也就是说, 对于若干个弱学习器的输出进行平均得到最终的预测输出.

   最简单的平均是算术平均, 也就是说最终预测是:

   $$H(x)=\frac{1}{T}\sum_{i=1}^Th_i(x)$$

   如果个体学习器有一个对应的权重 $w$, 则最终预测是:

   $$H(x)=\sum_{i=1}^Tw_ih_i(x) \\ w_i\ge0,\quad \sum_{i=1}^Tw_i=1$$

2. 投票法

   对于分类问题的预测, 我们通常使用的是投票法. 假设我们的预测类别是 $c_1,c_2,…,c_k$, 对于任意一个预测样本 $x$, 我们的 $T$ 个弱学习分类器的预测结果分别是: $h_1(x),h_2(x),…,h_T(x)$ .

   最简单的投票法是相对多数投票法, 也就是我们常说的少数服从多数, 也就是在 $T$ 个弱学习器对样本 $x$ 的预测中, 数量最多的类别 $c_i$ 为最终的分类类别. 如果不止一个类别获得最高票, 则随机选择一个做最终类别.

   稍微复杂的投票法是绝对多数投票法, 也就是我们常说的要票过半数. 在相对多数投票法的基础上, 不光要求获得最高票, 还要求票过半数, 否则会拒绝预测.

   更加复杂的是加权投票法, 和加权平均法一样, 每个弱学习器的分类票数要乘以一个权重, 最终将各个类别的加权票数求和, 最大的值对应的类别为最终类别.

3. 学习法

   投票和平均相对比较简单, 但是可能学习误差较大, 于是就有了学习法这种方法, 对于学习法, 代表方法是 stacking, 当使用 stacking 的结合策略时, 我们不是对弱学习器的结果做简单的逻辑处理, 而是再加上一层学习器. 也就是说, 我们将训练集弱学习器的学习结果作为输入, 将训练集的输出作为输出, 重新训练一个学习器来得到最终结果.

   在这种情况下, 我们将弱学习器称为初级学习器, 将用于结合的学习器称为次级学习器. 对于测试集, 我们首先用初级学习器预测一次, 得到次级学习器的输入样本, 再用次级学习器预测一次, 得到最终的预测结果.

3.1 AdaBoost

首先我们用一个幽默的例子来看一看 AdaBoost 是个什么东西: https://zhuanlan.zhihu.com/p/37671791

对于我们提到的 Boosting 算法步骤, 需要回答两个问题:

1. 如何调整每一轮的训练集的样本权重?
2. 如何将得到的 $M$ 个学习器组合成最终的学习器?

AdaBoost (Adaptive Boosting, 自适应增强) 算法采取的方法是:

1. 提高上一轮被错误分类的样本的权值, 降低被正确分类的样本的权值;
2. 线性加权求和, 误差率小的基学习器拥有较大的权值, 误差率较大的基学习器拥有较小的权值.

AdaBoost 算法结构如下图所示:

考虑如下形式的二分类 (标准AdaBoost算法只适用于二分类任务) 训练数据集:

$$(x_1,y_1),(x_2,y_2),...,(x_N,y_N)$$

其中 $x_i$ 是一个含有 $d$ 个元素的列向量, 即 $x_i\in\mathcal{X}\subseteq \mathbf{R}^d$ , $y_i$ 是标量, $y\in(+1,-1)$.

AdaBoost 算法具体步骤如下:

1. 初始化样本的权重

   $$D_1=(w_{11},w_{12},...,w_{1N}), \quad w_{1i}=\frac{1}{N},i=1,2,...,N$$

2. 对 $m=1,2,…,M$, 重复以下操作得到 $M$ 个基学习器

   (1) 按照样本权重分布 $D_m$ 训练数据得到第 $m$ 个基学习器 $G_m(x)$:

   $$G_m(x):\mathcal{X}\rightarrow-1,+1$$

   还是通过最小化分类误差来学习.

   (2) 计算 $G_m(x)$ 在加权训练数据集上的分类误差率:

   $$e_m=\sum_{i=1}^NP(G_m(x_i)\ne y_i)=\sum_{i=1}^Nw_{mi}I(G_m(x_i)\ne y_i)$$

   上式中的 $I(\cdot)$ 是指示函数, 考虑更加周全的AdaBoost算法在这一步还应该判断是否满足基本条件(例如生成的基学习器是否比随机猜测好), 如果不满足, 则当前基学习器被抛弃, 学习过程提前终止.

   (3) 计算 $G_m(x)$ 的系数 (即最终集成使用的基学习器的权重):

   $$\alpha_m=\frac{1}{2}\log\frac{1-e_m}{e_m}$$

   当基学习器 $G_m(x)$ 的误差率 $e_m\le0.5$ 时, $\alpha_m\ge0$, 并且 $\alpha_m$ 随着 $e_m$ 的减小而增大, 即分类误差率越小的基学习器在最终集成时占比也越大. 即AdaBoost能够适应各个弱分类器的训练误差率，这也是它的名称中”适应性(Adaptive)”的由来.

   我们可以看到所有的 $\alpha_m$ 的和并不为 1, 因为我们并没有做 Softmax 的操作.

   (4) 更新训练样本的权重:

   $$D_{m+1}=(w_{m+1,1},w_{m+1,2},...,w_{m+1,N}) \\ \ \\ w_{m+1,i}=\frac{w_{mi}}{Z_m}\exp(-\alpha_my_iG_m(x_i)),\quad i=1,2,...,N$$

   其中 $Z_m$ 是规范化因子, 目的是为了使 $D_{m+1}$ 的所有元素和为 1 (想一下我们之前在神经网络讲过的 Softmax), 即:

   $$Z_m=\sum_{i=1}^Nw_{mi}\exp(-\alpha_my_iG_m(x_i))$$

   通过权重更新的公式, 被基学习器 $G_m(x)$ 误分类的样本权值得以扩大, 而被正确分类的样本的权值得以缩小.

3. 构建最终的分类器线性组合

   $$f(x)=\sum_{i=1}^M\alpha_mG_m(x)$$

   得到最终的分类器为

   $$G(x)=sign(f(x))=sign(\sum_{i=1}^M\alpha_mG_m(x))$$

   $f(x)$ 的符号决定了所预测的类, 其绝对值代表了分类的确信度.

3.1.1 Why?

我们来思考思考为什么 AdaBoost 算法长上面这个样子. 但在解释 AdaBoost 算法之前我们需要先介绍前向分步算法 (Forward Stagewise Algorithm). 我们就以 AdaBoost 算法的最终模型表达式为例:

$$f(x)=\sum_{i=1}^M\alpha_mG_m(x)$$

可以看到这是一个“加性模型 (Additive Model)”, 我们希望在这个模型上的经验误差最小, 即

$$\min\sum_{i=1}^NL(y_i,f(x))\Longleftrightarrow\min\sum_{i=1}^NL(y_i,\sum_{i=1}^M\alpha_mG_m(x))$$

通常这是一个复杂的优化问题. 前向分步算法求解这一优化问题的思想就是: 因为最终模型是一个加性模型, 如果能从前往后, 每一步只学习一个基学习器 $G_m(x)$ 及其权重 $\alpha_m$, 不断迭代得到最终的模型, 那么就可以简化问题复杂度. 具体的, 当我们经过 $m-1$ 轮迭代得到了最优模型 $f_{m-1}(x)$, 因为

$$f_m(x)=f_{m-1}(x)+\alpha_mG_m(x)$$

所以, 此轮的优化目标就为

$$\min\sum_{i=1}^NL(y_i,f_{m-1}(x)+\alpha_mG_m(x))$$

求解上式即可得到第 $m$ 个基分类器 $G_m(x)$ 及其权重 $\alpha_m$.

ok, 上我们已经介绍了前向分步算法逐一学习基学习器, 这一过程也即是 AdaBoost 算法逐一学习基学习器的过程. 但是为什么 AdaBoost 中公式为什么长那样还是没有解释. 所以我们就证明前向分步算法的损失函数是指数损失函数 (Exponential Loss Function).

指数损失函数即

$$L(y,f(x))=\exp(-yf(x))$$

周志华 《机器学习》 p174 有证明, 指数损失函数是分类任务原本0/1损失函数的一致(consistent)替代损失函数, 由于指数损失函数有更好的数学性质, 例如处处可微, 所以我们用它替代0/1损失作为优化目标.

我们将指数损失函数代入 $\min\sum_{i=1}^NL(y_i,f_{m-1}(x)+\alpha_mG_m(x))$, 优化目标就为

$$\mathop{\arg\min}_{\alpha_m,G_m}\sum_{i=1}^N\exp[-y_i(f_{m-1}(x)+\alpha_mG_m(x))]$$

因为 $y_if_{m-1}(x)$ 与优化变量 $\alpha_m$ 和 $G_m(x)$ 无关, 如果令

$$w_{mi}=\exp[-y_if_{m-1}(x)]$$

那么优化目标就变成了

$$\mathop{\arg\min}_{\alpha_m,G_m}\sum_{i=1}^Nw_{mi}\exp(-y_i\alpha_mG_m(x))$$

我们分两步来求上式的最优解 $\hat{\alpha}_m$ 和 $\hat{G}_m(x)$:

1. 对任意的 $\alpha_m>0$, 求 $\hat{G}_m(x)$:

   $$\hat{G}_m(x)=\mathop{\arg\min}_{G_m}\sum_{i=1}^Nw_{mi}I(y_i\ne G_m(x_i))$$

   上式将指数损失函数转换成指示函数是因为前面说的指数损失函数和0/1损失函数是一致等价的.

   我们不难发现, 上面这个式子就是 AdaBoost 算法的基学习器的学习过程, 得到的 $\hat{G}_m(x)$ 是使第 $m$ 轮加权训练数据分类误差最小的基分类器.

2. 求解 $\hat{\alpha}_m$:

   我们将目标函数展开

   $$\begin{equation} \begin{aligned} \sum_{i=1}^Nw_{mi}\exp(-y_i\alpha_mG_m(x)) =&\sum_{y_i=G_m(x_i)}w_{mi}\exp(-\alpha_m)+\sum_{y_i\ne G_m(x_i)}w_{mi}\exp(\alpha_m) \\ =&(e^{\alpha_m}-e^{-\alpha_m})\sum_{i=1}^Nw_{mi}I(y_i\ne G_m(x_i))+e^{-\alpha_m}\sum_{i=1}^Nw_{mi} \end{aligned} \end{equation}$$

   将上式对 $\alpha_m$ 求导并令导数为 0, 即

   $$(e^{\alpha_m}+e^{-\alpha_m})\sum_{i=1}^Nw_{mi}I(y_i\ne G_m(x_i))-e^{-\alpha_m}\sum_{i=1}^Nw_{mi}=0$$

   解得

   $$\alpha_m=\frac{1}{2}\log\frac{1-e_m}{e_m}$$

   其中, $e_m$ 是分类误差率

   $$e_m=\frac{\sum_{i=1}^Nw_{mi}I(y_i\ne G_m(x_i))}{\sum_{i=1}^Nw_{mi}}$$

   如果将上式进行归一化那么也和我们在 Adaboost 中的误差率计算一模一样了.

   最后我们来看看每一轮样本权值的更新, 由下面两式:

   $$f_m(x)=f_{m-1}(x)+\alpha_mG_m(x) \\ w_{mi}=\exp[-y_if_{m-1}(x)]$$

   我们可以得到

   $$w_{m+1,i}=w_{mi}\exp(-y_i\alpha_mG_m(x))$$

   将上式进行归一化那么也和我们在 Adaboost 中的误差率计算一模一样了.

由此可见, AdaBoost 的算法步骤是可以经过严密推导得到的. 总结一下, 推导有如下关键点:

• AdaBoost 算法是一个加性模型, 将其简化成前向分步算法求解;
• 将0/1损失函数用数学性质更好的指数损失函数替代.

3.1.2 Example

请查看李航 《统计学习方法》 P158

3.1.2 Code

AdaBoost 算法实现如下:

def my_adaboost_clf(Y_train, X_train, Y_test, X_test, M=20, weak_clf=DecisionTreeClassifier(max_depth = 1)):
    n_train, n_test = len(X_train), len(X_test)
    # Initialize weights
    w = np.ones(n_train) / n_train
    pred_train, pred_test = [np.zeros(n_train), np.zeros(n_test)]
    
    for i in range(M):
        # Fit a classifier with the specific weights
        weak_clf.fit(X_train, Y_train, sample_weight = w)
        pred_train_i = weak_clf.predict(X_train)
        pred_test_i = weak_clf.predict(X_test)
        
        # Indicator function
        miss = [int(x) for x in (pred_train_i != Y_train)]
        print("weak_clf_%02d train acc: %.4f"
         % (i + 1, 1 - sum(miss) / n_train))
        
        # Error
        err_m = np.dot(w, miss)
        # Alpha
        alpha_m = 0.5 * np.log((1 - err_m) / float(err_m))
        # New weights
        miss2 = [x if x==1 else -1 for x in miss] # -1 * y_i * G(x_i): 1 / -1
        w = np.multiply(w, np.exp([float(x) * alpha_m for x in miss2]))
        w = w / sum(w)

        # Add to prediction
        pred_train_i = [1 if x == 1 else -1 for x in pred_train_i]
        pred_test_i = [1 if x == 1 else -1 for x in pred_test_i]
        pred_train = pred_train + np.multiply(alpha_m, pred_train_i)
        pred_test = pred_test + np.multiply(alpha_m, pred_test_i)
    
    pred_train = (pred_train > 0) * 1
    pred_test = (pred_test > 0) * 1

    print("My AdaBoost clf train accuracy: %.4f" % (sum(pred_train == Y_train) / n_train))
    print("My AdaBoost clf test accuracy: %.4f" % (sum(pred_test == Y_test) / n_test))

3.2 GBDT

3.2.1 Intuition

GBDT是 Gradient Boosting Decision Tree 的缩写, 即梯度提升决策树. 我们可以看出 GBDT 的基础还是决策树, 而且是我们之前已经提到过的 CART 算法.

现在我们从直觉的角度来看一看 GBDT 是如何拟合的. 假设现在有样本集

$$(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$$

然后我们用一个模型, 现在我们用 $F(x)$ 去拟合这些数据, 使得这批样本的均方误差最小. 最后我们发现, 虽然模型的拟合效果很好, 但仍然有一些差距. 比如, 预测值 $F(x_1)=0.8$, 而真实值 $y_1=0.9$, $F(x_2)=1.4$, $y_2=1.3$ 等等. 但是现在我们却没有办法去更改模型 $F(x)$ 的参数, 那么有什么办法进一步来提高模型的拟合能力呢?

既然不能更改原来模型的参数, 那么意味着必须在原来模型的基础上做改善, 那么直观的做法就是建立一个新的模型 $f(x)$ 来拟合 $F(x)$ 未完全拟合真实样本的残差, 即 $y-F(x)$. 所以对于每个样本来说, 拟合的样本集就变成了:

$$(x_1,y_1-F(x_1)),(x_2,y_2-F(x_2)),...,(x_n,y_n-F(x_n))$$

而在这个新的待拟合样本集中, $y_i-F(x_i)$ 被称为残差, 将交给新的模型来完成. 我们知道 GBDT 的全称是 Gradient Boosting Decision Tree, 其中 Gradient 被称为梯度, 那么这里的残差与梯度是什么关系呢? 我们之前提到了均方误差, 也就是下面这个式子:

$$L=\frac{1}{2}\sum_{i=1}^n(y_i-F(x_i))^2$$

熟悉其他算法的原理应该知道, 这个损失函数主要针对回归类型的问题, 分类则是用熵值类的损失函数. 具体到平方损失函数的式子, 你可能已经发现它的一阶导其实就是残差的形式, 所以基于残差的 GBDT 是一种特殊的 GBDT 模型, 它的损失函数是均方误差, 常用来处理回归类问题, 且残差就是负梯度.

$$\frac{\partial L}{\partial F(x_i)}=F(x_i)-y_i \\ y_i-F(x_i)=-\frac{\partial L}{\partial F(x_i)}$$

我们可以用 $r_{mi}$ 来表示第 $m$ 棵回归树对于样本 $i$ 的训练目标, 它的公式为:

$$r_{mi}=y_i-F(x_i)$$

但注意, 不能把残差简单理解成目标值和 $F(x_i)$ 的差值, 它本质是由损失函数计算负梯度得到的. 至于为什么拟合负梯度可以得到一个好的模型呢? 因为沿着负梯度的方向学习, 效率是最高的, 当负梯度为0时, 全局损失函数就是最好的, 得到的强学习器 $F(x)$ 自然也是比较好的.

但是!!! 基于残差的 GDBT 并不是一个很好的选择. 一个比较明显的缺点就是对异常值过于敏感, 我们来看一个例子.

$y_i$	$F(x_i)$	$L=(y-F)^2/2$
0.5	0.6	0.005
1.2	1.4	0.02
2	1.5	0.125
5	1.7	5.445

很明显后续的模型会对第4个值关注过多, 这不是一种好的现象, 所以一般回归类的损失函数会用绝对损失或者huber损失函数来代替平方损失函数:

• Absolute Loss (More robust to outliers)

  $$L(y,F)=|y-F|$$

• Huber Loss (More robust to outliers)

  $$L(y,F)= \begin{cases} \begin{aligned} \frac{1}{2}(y-F)^2\quad |y-F|\le\delta \\ \delta(|y-F|-\frac{\delta}{2})\quad |y-F|\gt\delta \end{aligned} \end{cases}$$

$y_i$	$F(x_i)$	Square Loss	Absolute Loss	Huber Loss ($\delta=0.5$)
0.5	0.6	0.005	0.1	0.005
1.2	1.4	0.02	0.2	0.02
2	1.5	0.125	0.5	0.125
5	1.7	5.445	3.3	1.525

3.2.2 Regression Algorithm

我们现在把模型训练的整个过程摆出来, 把所有细节串联起来.

首先我们明确几个参数, $M$ 表示基学习器 CART 的数量, $f_m(x_i)$ 表示第 $m$ 轮训练之后的整体模型. $f_m(x_i)$ 即为最终输出的 GBDT 模型.

1. 初始化

   首先, 我们创建第一棵回归树即 $f_1(x)$, 在回归问题当中, 它是直接用回归树拟合目标值的结果, 所以:

   $$f_1(x)=\mathop{\arg\min}_c\sum_{i=1}^NL(y_i,c)$$

2. 迭代

   (1) 对于第 2 到第 m 棵回归树, 我们要计算出每一颗树的训练目标, 也就是前面结果的残差(当损失函数是均方误差时):

   $$r_{mi}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}$$

   (2) 对于当前第 $m$ 棵子树而言, 我们需要将上面得到的残差作为样本新的真实值, 并将数据 $(x_i,r_{mi}),i=1,2,…,N$ 作为下棵树的训练数据, 得到一颗新的回归树. 我们需要遍历可行特征以及切分点 (阈值), 找到最优的预测值 $c$ 对应的参数, 使第 $m$ 棵树尽可能逼近残差, 公式表达如下:

   $$c_{mj} = \mathop{\arg\min}_c\sum_{x_i\in R_{mj}}L(y_i,f_{m-1}(x_i)+c)$$

   $R_{mj}$ 指的是第 $m$ 棵子树按照划分方法 $j$ 所得到的特征空间, $j=1,2,3…,J$. 如果你对这个感到模糊, 可以看我的决策树笔记.

   接着我们更新我们的模型:

   $$f_m(x)=f_{m-1}(x)+\sum_{j=1}^Jc_{mj}I(x\in R_{mj})$$

3. 最后我们得到回归树

   $$F(x)=f_M(x)=\sum_{m=1}^Mf_m(x)=\sum_{i=1}^M\sum_{j=1}^Jc_{mj}I(x\in R_{mj})$$

3.2.3 Classification Algorithm

我们现在来看看 GBDT 分类算法, GBDT的分类算法从思想上和GBDT的回归算法没有区别, 但是由于样本输出不是连续的值, 而是离散的类别, 导致我们无法直接从输出类别去拟合类别输出的误差.

为了解决这个问题, 主要有两个方法, 一个是用指数损失函数, 此时GBDT退化为Adaboost算法. 另一种方法是用类似于逻辑回归的对数似然损失函数的方法. 也就是说, 我们用的是类别的预测概率值和真实概率值的差来拟合损失.

逻辑回归的单个样本 $(x_i,y_i)$ 的损失函数可以表达为:

$$L(\theta)=-y_i\log\hat{y}_i-(1-y)\log(1-\hat{y}_i)$$

现在我们假设 GBDT 第 $M$ 步迭代之后学习器为:

$$F(x)=\sum_{i=1}^Mf_m(x)$$

我们将 $y_i$ 替换为 $f(x)$ 代入上式之后, 可以将损失函数写为:

$$\begin{equation} \begin{aligned} L(y_i,f(x_i))=&-y_i\log(\frac{1}{1+\exp(-f(x_i))})-(1-y_i)\log(1-\frac{1}{1+\exp(-f(x_i))}) \\ =&y_i\log(1+\exp(-f(x_i)))+(1-y_i)[f(x_i)+\log(1+\exp(-f(x_i)))] \end{aligned} \end{equation}$$

此时, 第 $m$ 棵树所要拟合的负梯度为:

$$r_{mi}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}=y_i-\frac{1}{1+\exp(-f(x_i))}=y_i-\hat{y}_i$$

对于生成的决策树, 计算各个叶子节点的最佳残差拟合值为:

$$c_{mj}=\mathop{\arg\min}_c\sum_{x_i\in R_{mj}}L(y_i,f_{m-1}(x_i)+c)$$

由于上式没有闭式解 (closed form solution), 我们一般使用近似值代替:

$$c_{mj}=\frac{\sum_{x_i\in R_{mj}}r_{mi}}{\sum_{x_i\in R_{mj}}(y_i-r_{mi})(1-y_i+r_{mi})}$$

因此我们现在可以给出 GBDT 二分类算法的完整过程:

1. 初始化

   我们首先建立第一个弱学习器 $f_0(x)$

   $$f_0(x)=\log\frac{P(Y=1)}{1-P(Y=1)}$$

   其中, $P(Y=1)$ 是训练样本中 $y=1$ 的比例, 我们利用先验信息来初始化学习器.

2. 迭代

   (1) 对于第 1 到第 m 棵回归树, 我们要计算出每一颗树的训练目标, 也就是损失函数的负梯度, 即伪残差:

   $$r_{mi}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}=y_i-\frac{1}{1+\exp(-f(x_i))}$$

   (2) 利用 CART 回归树拟合新的数据集 $(x_i,r_{mi})$, 得到第 $m$ 棵回归树

   $$c_{mj}=\frac{\sum_{x_i\in R_{mj}}r_{mi}}{\sum_{x_i\in R_{mj}}(y_i-r_{mi})(1-y_i+r_{mi})}$$

   (3) 更新强学习器 $f_m(x)$

   $$f_m(x)=f_{m-1}(x)+\sum_{j=1}^Jc_{mj}I(x\in R_{mj})$$

3. 得到最用强学习器 $F(x)$ 的表达式

   $$F(x)=f_M(x)=\sum_{i=0}^Mf_m(x)=f_0(x)+\sum_{m=1}^M\sum_{j=1}^Jc_{mj}I(x\in R_{mj})$$

从以上过程中可知, 除了由损失函数引起的负梯度计算和叶子节点的最佳残差拟合值的计算不同, 二元GBDT分类和GBDT回归算法过程基本相似. 那二元GBDT是如何做分类呢?

将逻辑回归的公式进行整理, 我们可以得到 $\log\frac{p}{1-p}=\theta^Tx$, 其中 $p=P(Y=1|x)$, 也就是将给定输入 $x$ 预测为正样本的概率. 逻辑回归用一个线性模型去拟合这个事件的对数几率. 二元GBDT分类算法和逻辑回归思想一样, 用一系列的梯度提升树去拟合这个对数几率, 其分类模型可以表达为:

$$P(Y=1|x)=\frac{1}{1+\exp(-F(x))}$$