文章目录
  1. 1. GDBT and Random Forest
    1. 1.1. Introduction
    2. 1.2. Bagging and Boosting
      1. 1.2.1. Bagging
      2. 1.2.2. Boosting
    3. 1.3. Algorithm
      1. 1.3.1. GDBT
      2. 1.3.2. Random Forest
    4. 1.4. Error
    5. 1.5. Analyse
    6. 1.6. Model
    7. 1.7. References

GDBT and Random Forest

Introduction

GDBTRandom Forest 作为两种常见的集成学习方法,虽然二者都是基于决策树的集成方式,但是二者有不同的侧重点,本文从不同角度讲述不同的学习方式。

Bagging and Boosting

集成学习是机器学习领域的一个重要的分支,它不是一种具体的算法,而是一种学习的思想。主要分为两种重要的方法: BaggingBoosting。它们都是通过某种策略把多个弱学习器组合起来,形成一个具有很高预测准确率的强学习算法。

Bagging

Bagging 即套袋法,其算法过程如下:

  • 从原始样本集中抽取训练集。每轮从原始样本集中使用 Bootstrap Aggregation 的方法抽取 ${n}$ 个训练样本(在训练集中,有些样本可能被多次抽取到,而有些样本可能一次都没有被抽中)。共进行 ${k}$ 轮抽取,得到 ${K}$ 个训练集(${k}$ 个训练集之间是相互独立的)。
  • 每次使用一个训练集得到一个模型,${k}$ 个训练集共得到 ${k}$ 个模型(注:这里并没有具体的分类算法或回归方法,我们可以根据具体问题采用不同的分类或回归方法,如决策树、感知器等)。
  • 对分类问题:将上步得到的 ${k}$ 个模型采用投票的方式得到分类结果;对回归问题,计算上述模型的均值作为最后的结果(所有模型的重要性相同)。

Boosting

Boosting 是一个加法模型,从常数开始迭代,每一轮迭代增加一个函数,每次新添加的函数是基于 以往所有的学习结果的和真实值 之间的残差上学习模型。

${\hat{y_i}^{0} = 0}$

${\hat{y_i}^{1} = f_1(x_i) = \hat{y_i}^{0} + f_1(x_i)}$

${\hat{y_i}^{2} = f_1(x_i) + f_2(x_i) = \hat{y_i}^{1} + f_2(x_i)}$

${\ \ \ \ ……….}$

${\hat{y_i}^{t} = \sum_{k=1}^{t} f_k(x_i) = \hat{y_i}^{t-1} + f_t(x_i)}$

Algorithm

GDBT

GBDTBoosting 的代表,每次训练都是使用所有数据,但是最终结果是多颗树的叠加,训练完一棵树以后,将结果的残差作为下一棵树的训练目标。在这个过程中还使用了梯度近似残差的方法。

GDBT 的损失函数的数值优化可以看成是在函数空间,而不是在参数空间。损失函数 ${L(y,F)}$ 包含平方损失 ${(y−F)^2}$ 和绝对值损失 ${|y−F|}$ 用于回归问题,负二项对数似然 ${\log(1+\exp^{−2yF})}$,${y \in \{-1,1\}}$ 用于分类。但是,关注点是预测函数的加性扩展。

强分类器是由多个弱分类器线性加成的。

这里的 ${h(x;\alpha_m)}$ 指代回归树,例如 ${CART}$。${\alpha_m}$ 是模型参数,这里指代每个节点的分裂特征(变量),最佳分割点,节点的预测值。${M}$ 就是有多少个弱分类器。

然后,我们来回顾一下参数空间的数值优化。假设预测函数为 ${F(x;\theta)}$,那么损失函数就可以写成:

优化以后得到的参数最优解为:

优化方式是,常见的是基于梯度的方式,优化的每一步则为 ${\theta_m}$,从初始值 ${\theta_0}$ 开始,${m}$ 对应每一步更新迭代,负梯度 ${−g_m}$ 就是最速下降方向,${- \eta_m}$ 就是在这个最速下降方向上进行线搜索得到的最优步长(学习率)。

将预测函数 ${F(x)}$ 对应参数 ${\theta}$,最优解变成了:

相当于在函数空间上作梯度下降。每一步梯度下降:

现在把这个思想代入到 gradient boosting,我们之前已经得到预测函数为:

需要做的事情是得到预测函数的最优解,就是:

已知最速梯度下降方向为 ${g_m(x)}$,每一个 ${h_m(x;\alpha_m)}$ 都建立在最速梯度下降的方向,我们可以得到:

可以认为是用 ${h_m(x;a)}$ 去拟合伪标签 ${\hat{y} =−g_m(x)}$。这里用最小二乘原因是 GBDT 构造的树全是回归树(${CART}$)。

最后进行线搜索确定最优步长 ${\eta_m}$:

Random Forest

Random Forest 是基于 BaggingDecision Tree 模型融合,最后用简单的投票方式作为最终结果,同时,每颗决策树会对数据的特征进行随机采样,这样的目的也是让每个模型只看到原来数据的一部分。

由于引入了随机性,使得随机森林不太容易过拟合,也具有一定的高噪声能力,能够处理高维度的数据,所以不用做特征选择,模型的训练的过程中,可以很容易地实现并行化。

Error

同样的算法在不同的数据集上得到的模型结果很可能不同,尽管数据集来自于同一个分部。对于观测数据 ${X}$ 以及待预测的变量 ${Y}$,假设两者服从 ${Y = f(X) + \epsilon}$ ,${\epsilon}$ 为噪声,其服从的 ${N(0,\sigma_{\epsilon}^2)}$ ,预测任务中需要得到 ${Y}$ 值,首先在数据集 ${D}$ 上通过算法学习一个近似 ${f(X)}$ 的模型 ${\hat{f}(X)}$ 来预测得到 ${X}$ 的输出。给定 ${X}$ 一个观测值 ${x}$,待预测变量 ${y=f(x)+\epsilon}$。

  • 对于样本数量相同的不同训练集模型 ${\hat{f}(X)}$ 的期望输出为: ${E[\hat{f}(X)]}$。
  • 对于样本数量相同的不同训练集模型产生的方差为:${E[\hat{f}(X) −E[\hat{f}(X)]]^2}$。

将模型的误差分解,采用均方损失,模型 ${\hat{f}(X)}$ 在点 ${x}$ 的整体预测误差为真实值与模型预测值之间的误差:

${E[\hat{f}(X)]–f(x)}$ 即为 Bias ,${E[\hat{f}(X)−E[\hat{f}(X)]^2}$ 为 Variance ,${\sigma_{\epsilon}^2}$ 即为模型无法避免的 Noise。那么现在对于一个预测模型的误差可以分为如下几部分:

Bias and variance in dart-throwing.

  • Bias:度量了学习算法的期望输出与真实结果的偏离程度,刻画了算法的拟合能力,Bias 偏高表示预测函数与真实结果差异很大。
  • Variance:则代表 “同样大小的不同的训练数据集训练出的模型” 与 “这些模型的期望输出值” 之间的差异。训练集变化导致性能变化,Variance 偏高表示模型很不稳定。
  • Noise:刻画了当前任务任何算法所能达到的期望泛化误差的下界,即刻画了问题本身的难度。

Analyse

Bias 表示离中心越远,高 Variance 表示对不同数据集学习得到的结果很分散,对于好的模型,我们希望既有较低的 Bias,又有较低的 VarianceGDBTRF 在这两种 ${Error}$ 上,有着不同的侧重点。

对于 Bagging 算法来说,由于我们会并行地训练很多不同的分类器的目的就是降低这个方差,因为采用了相互独立的基分类器多了以后,预测的值自然就会靠近。所以对于每个基分类器来说,目标就是如何降低这个偏差,所以我们会采用深度很深甚至不剪枝的决策树。随机森林 RF 采用完全成长的子决策树(低偏差,高方差)。随机森林要求这些子树之间尽可能无关,从而综合之后能降低方差,但是保持低偏差。

对于 Boosting 来说,每一步我们都会在上一轮的基础上更加拟合原数据,所以可以保证偏差,所以对于每个基分类器来说,问题就在于如何选择 方差更小的分类器,即更简单的分类器,所以我们选择了深度很浅的决策树。梯度提升树 GDBT 采用弱分类器(高偏差,低方差)。梯度提升树综合了这些弱分类器,在每一步的过程中降低了偏差,但是保持低方差。

Model

模型

  • 当模型越复杂时,拟合的程度就越高,模型的训练偏差就越小。但此时如果换一组数据可能模型的变化就会很大,即模型的方差很大。所以模型过于复杂的时候会导致过拟合。
  • 当模型越简单时,即使我们再换一组数据,最后得出的学习器和之前的学习器的差别就不那么大,模型的方差很小。还是因为模型简单,所以偏差会很大。

References

  1. GBDT、XGBoost、LightGBM 的使用及参数调优
  2. 【机器学习(李宏毅)】 三、Bias and Variance
  3. A Few Useful Things to Know about Machine Learning
  4. 理解 Bias 与 Variance 之间的权衡
  5. GDBT 原理详解
  6. GBDT详解
  7. 集成学习 by 华校专
文章目录
  1. 1. GDBT and Random Forest
    1. 1.1. Introduction
    2. 1.2. Bagging and Boosting
      1. 1.2.1. Bagging
      2. 1.2.2. Boosting
    3. 1.3. Algorithm
      1. 1.3.1. GDBT
      2. 1.3.2. Random Forest
    4. 1.4. Error
    5. 1.5. Analyse
    6. 1.6. Model
    7. 1.7. References