Side Info一般指什么？

  • 主要是指商品信息，比如：
    • 商品的各种属性信息，如品类、价格、品牌等
    • 历史统计信息，如历史曝光、点击、订单数等
  • 为什么叫做Side Info：在用户行为序列中，除了主要商品列表外，每个商品还会下挂一些相关的信息，这些信息就称为 Side Info

集成学习(Ensemble)的本质是一种组合基础模型实现更高泛化能力和精度的技术框架
本文参考了博客: http://www.cnblogs.com/jasonfreak/p/5657196.html

集成学习的三族算法

Bagging

通过重采样技术生成若干不同子训练集 ，然后在每个训练集上训练一个分类器 ，最终采用投票方式产生模型最终结果

  • m个基础模型
  • 从原始训练集中抽样生成m个子训练集,用子训练集训练每个基础模型
  • 最终预测结果: 对所有基础模型预测的结果进行综合产生
代表模型
随机森林
  • RF = Bagging + DT (随机森林中特征的选择也是随机的,这一点不同于DT,也不同与Bagging)
  • 随机森林详情可参考ML——RF

Boosting

每个训练样例都有权重 ，每次训练新分类器的时候都着重训练那些在上一次分类过程中分错的样例 ，权重会随着迭代次数的变化而变化

  • 训练思想是,每一轮迭代都将重心放到分错类的样本上
  • 训练过程为阶梯状
  • 基础模型按照次序依次训练(实现时可做到并行)
  • 前一个模型的预测结果修改后一个模型的样本权重(注意:模型的训练集时不会变的,只有每个样本的权重在变化,增大分错的样本的权重,使得后面训练时重视分错的样本),以此类推
  • 最终预测结果: 对所有基础模型预测的结果进行线性综合产生
代表模型
提升树
  • Boosting Tree = AdaBoost + DT (AdaBoost是Boosting族算法的一种)
梯度提升树
  • GBDT = Gradient Boosting + DT (Gradient Boosting是Boosting族算法的一种)
  • GBDT详情可参考ML——GBDT

Stacking

每个分类器首先做一遍决策，然后将分类器们的决策送到更高一层的模型中，把他们当做特征再进行一次训练

  • 训练所有基础模型
  • 获取所有基础模型的预测结果
  • 第j个模型对某个训练样本产生的预测值作为该训练样本的第j个特征,标签不变,生成一个新的数据集(注意,样本的特征空间大小发生了变化,标签没变)
  • 基于新的训练集进行训练,得到预测模型M()
  • 测试时也要将特征转换后再用M进行预测
  • 实质上就是先用一些模型提取特征(这些模型的输出作为更高层模型的特征),然后再用模型的输出作为最终模型的特征,从而实现模型的堆叠(Stacking)
  • 理论上可以堆叠各种各样的分类器

方差与偏差

本文介绍梯度提升树(族)的推导过程,包括传统的GBDT,XGBoost等

参数空间的优化

  • 参数空间中我们使用梯度下降法(一阶导数)和牛顿迭代法(二阶导数)来优化
  • 关于无约束参数优化方法参考无约束参数优化方法

从参数空间优化到函数空间的优化

  • 函数空间中我们使用GBDT(一阶导数)和XGBoost(二阶导数)来优化
  • 函数空间的优化完全类比参数空间的优化

Boosting是一种加法模型

加法模型：additive training
$$
\begin{align}
F(x) = \sum_{t=0}^{T}f_{t}(x)
\end{align}
$$

  • 上式中 \(f_{t}(x)\) 为基分类器, 我们通常采用回归树[Friedman 1999] 和逻辑回归
    [Friedman 2000]
  • 树模型的优缺点可以参考ML——DT-决策树

GBDT算法原理

这里只原论文中的Gradient Boosting Tree算法
Friedman于论文”GreedyFunctionApproximation…”中最早 出GBDT

模型 \(F\) 的加法定义：

$$
\begin{align}
F(x) &= \sum_{t=0}^{T}\alpha_{t} h_{t}(x;w_{t}) \\
&= \sum_{t=0}^{T} f_{t}(x;w_{t})
\end{align}
$$

  • 其中, \(x\) 为输入样本, \(h_{t}\) 为分类回归树, \(w_{t}\) 是树 \(h_{t}\) 的参数, \(\alpha_{t}\) 是树 \(h_{t}\) 的权重

损失函数的定义

$$
\begin{align}
F^{\star} = \mathop{\arg\max}_{F}\sum_{i=1}^{N}L(y_{i}, F(x_{i};w))
\end{align}
$$

  • 其中， \(N\) 为样本数量，所有样本的损失总和为总的损失函数
  • 最小化损失函数即可得到最优模型

最优模型的求解

  • 直接列举所有可能的树——NP难问题
  • 所以GBDT算法使用贪心法, 迭代求局部最优解
  • 详细的Gradient Boosting Tree迭代过程如下
  • 上面的推导中
    • 2.1中： \(\tilde{y}_{i}\) 是当前的损失函数 \(L(y_{i}, F(x_{i}))\) 关于当前函数 \(F(x)\) (模型)在 \(F(x)=F_{t-1}(x)\) 处的负梯度(每个样本都有一个负梯度)，这个梯度也是GBDT名字中梯度的由来
      • 这个损失函数在使用不同回归方法时时定义各不相同
      • 原始论文中提到两个损失函数定义,根据损失函数的不同,对应的归回方法不同: 最小二乘归回或者最小绝对误差回归
    • 2.2中： \(w^{\star}\) 是指能够拟合当前负梯度的树 \(h_{t}(x;w^{\star})\) 的最佳参数，这里我们认为最佳参数就是最小二乘的最佳参数，实际上这个地方可以使用其他测拟合标准(这个标准是拟合当前负梯度的拟合标准，与后面的损失函数 \(L(y, F(x;w))\) 无关)，只是这里最小二乘是最简单也是最自然的选择
      • 原始论文中这里使用的基函数是 \(\beta h(x;w)\)，其中 \(\beta\) 是当前基函数 \(h(x;w)\) 的权重，这里我认为直接使用 \(h(x;w)\) 作为基函数即可,权重 \(\beta\) 会自动被基函数学到的(可能原始论文中 \(h(x;w)\) 指的是简单的基函数，是不含权重学习功能的)
      • 但是需要注意的是,如果我们使用的基分类器是逻辑回归,那么这里每个基分类器的结果都是在[0-1]之间的数,是需要前面的 \(\beta\) 的
      • 这里我们推导的时候假定了基分类器是回归树,所以不需要使用 \(\beta\)
    • 2.3中：由于 \(w^{\star}\) 只能保证当前树 \(h_{t}(x;w^{\star})\) 是能拟合负梯度的，不能保证把当前这棵树添加到模型中时模型的损失函数是最小的，所以我们加了一个步长参数 \(\rho\)，用来表示得到当前树的最优权重
      • 损失函数是平方损失函数时，这里的参数为 \(\rho\) 就是1，无需计算
    • 2.4中：将当前树的最优树(包括权重)一起加入到模型中

不同损失函数和基函数对应不同的算法

上述式子中推导用到的基函数为树模型，实际使用中也可以使用逻辑回归模型[Friedman 2000]等基函数
本小节将介绍不同损失函数或者基函数带来的不同算法

  • 注意:包括Adaboost和GBDT在内Boosting框架中，基函数(基分类器)都不能使用线性模型
    • 理解: Boosting框架本质上是一个加法模型，是对多个基函数的线性组合，得到更优的分类器，可以证明线性模型的线性组合还是线性模型，如果Boosting框架中使用线性模型，那么我们最终得到的分类器也是线性模型，这就局限了我们的整体模型的表达能力
最小二乘回归(损失函数)

Least-Squares Regression

损失函数定义
  • 此时损失函数定义为
    $$
    \begin{align}
    L(y,F(x)) = \frac{1}{2}(y-F(x))^{2}
    \end{align}
    $$
进一步理解推导过程
  • 2.1中 \(\tilde{y}_{i}=y_{i}-F_{t-1}(x_{i})\)，这里直接对损失函数求导即可的到
    $$
    \begin{align}
    \tilde{y_{i}} &= -\left [\frac{\partial L(y,F(x_{i}))}{\partial F(x_{i})}\right ]_{F(x) = F_{t-1}(x)} \\
    &= -\left [\frac{\partial L(y,F_{t-1}(x_{i}))}{\partial F_{t-1}(x_{i})}\right ] \\
    &= -\left [\frac{\partial \frac{1}{2}(y_{i}-F_{t-1}(x_{i}))^{2}}{\partial F_{t-1}(x_{i})}\right ] \\
    &= 2 \cdot -\frac{1}{2}(y_{i}-F_{t-1}(x_{i})) \cdot -1 \\
    &= y_{i}-F_{t-1}(x_{i})
    \end{align}
    $$
  • 2.2中正常拟合(使用线性回归和CART回归树均可)
  • 2.3中基函数的权重 \(\rho^{\star}\) 是常数1，推导如下
    $$
    \begin{align}
    L(y,F_{t}(x)) &= \sum_{i=1}^{N}L(y_{i}, F_{t}(x_{i})) \\
    &= \frac{1}{2}\sum_{i=1}^{N}((y_{i}-F_{t}(x_{i}))^{2}) \\
    &= \frac{1}{2}\sum_{i=1}^{N}((y_{i}-F_{t-1}(x_{i}) - h_{t}(x_{i};w))^{2}) \\
    &= \frac{1}{2}\sum_{i=1}^{N}((\tilde{y}_{i}-h_{t}(x_{i};w))^{2}) \\
    \end{align}
    $$
  • 显然，这个式子和2.2中拟合目标完全相同(只差着2倍常数权重)，所以2.2中得到的最优基函数 \(h_{t}(x;w^{\star})\) 就是2.3中使得模型损失函数 \(L(y,F_{t}(x))\) 最小的最优基函数，无需添加任何的权重系数
最小绝对偏差回归(损失函数)

Least Absolute Deviation Regression, LAD

损失函数定义
  • 此时损失函数定义为
    $$
    \begin{align}
    L(y,F(x)) = |y-F(x)|
    \end{align}
    $$
进一步理解推导过程
  • 2.1中 \(\tilde{y}_{i}=sign(y_{i}-F_{t-1}(x_{i}))\)
    • 绝对值的导数就是1或者-1,当
      $$y_{i}-F_{t-1}(x_{i}) > 0$$
    • 对损失函数求导得到-1,负梯度为1
    • 同理得到，当
      $$y_{i}-F_{t-1}(x_{i}) > 0$$
    • 对损失函数求导得到1,负梯度为-1
    • 总结得到负梯度为
      $$\tilde{y}_{i}=sign(y_{i}-F_{t-1}(x_{i}))$$
  • 2.2中正常拟合(使用线性回归和CART回归树均可)
  • 2.3中基函数的权重 \(\rho^{\star}\) 不再是常数，推导如下
  • 待更新*
    $$
    \begin{align}
    待更新
    \end{align}
    $$
回归树(基函数)

Regression Trees

  • 传统GBDT中原始论文使用树回归 ，论文见Firedman 1999,后来作者提出可以使用逻辑回归 ，论文见Friedman 2000
  • 回归树和逻辑回归的优缺点比较
    • 树模型优点 :
      • 可解释性强
      • 可处理混合类型特征(混合类型特征指的是数值型和类别型均可处理)
      • 具有伸缩不变性(无需特征归一化: 神经网络和逻辑回归都需要,逻辑回归中是为了保证随机梯度下降的方向正确,速度快)
      • 可自然的处理缺失值, C4.5树处理缺失值默认使用的方法是先用未缺失样本计算信息增益确定分裂结点,然后将缺失值的每个样本按照权重(当前叶子节点未缺失样本数量 / 未缺失样本总数)分配到各个结点
      • 对异常点鲁棒(不用去除异常点,LR不具有这个优点)
      • 有特征选择的作用
      • 可扩展性强,容易并行(并行是最好的,用来解释为什么XGBoost等都用树模型)
    • 树模型缺点 :
      • 缺乏平滑性(回归预测时输出值只能输出若干种数值,而不是连续的数值,所以不平滑[不平滑即离散])
      • 不适合处理高维稀疏数据(当数据量太少时,非常容易过拟合,树的深度太深,从而模型变得太复杂)

传统GDBT与XGBoost的比较

决策树算法时很多优秀的集成算法的基础,包括RF,GBDT,提升树(Boosting Tree)等

论文参考: 《统计学习方法》

说明

  • 决策树(DT)是一种基本的分类和回归方法
  • 分类问题中可以理解为if-then规则的集合
  • 分类问题中也可以理解为定义在特征空间->类空间上的条件概率分布
  • 分类问题中使用的是ID3和C4.5
    • ID3 基于 最大化信息增益 来选择特征
    • C4.5基于 最大化信息增益比 来选择特征
  • 回归问题使用的是分类与回归树(Classification And Regression Tree, CART)
    • 分类树: 基于 最小化基尼(Gini Index)指数 来选择特征
    • 回归树: 基于 最小化平方误差 来选择特征
  • 关于树模型的复杂度可以用下面的方式评估, 统计学习方法中CART选择使用树的节点总数来评估树的复杂度
    • 叶子节点的数量
    • 节点总数
    • 树的深度

树模型的优缺点

优点

  • 可解释性强
  • 可处理混合类型特征(?)
  • 具体伸缩不变性(不用归一化特征,LR模型需要归一化特征)
  • 有特征组合的作用
  • 可自然地处理缺失值(神经网络不能处理缺失值)
  • 对异常点鲁棒
  • 有特征选择作用
  • 可扩展性强，容易并行

缺点

  • 缺乏平滑性(回归预测时输出值只能 输出有限的若干种数值)
  • 不适合处理高维稀疏数据
    • 数据稀疏时
      • 比如某个数据集有10000个样本
      • 某个特征只有10个样本存在值，其他样本都不存在值
    • 决策树：
    • 这样的话树容易将当前特征选中作为分类特征，这种划分可能在训练集上看起来很好，但测试集中表现可能不太好(这里不是简单的缺失值，而是数据很稀疏，这里需要进一步的理解[待更新])
    • LR等线性模型：
      • 因为现在的模型普遍都会带着正则项，而LR等线性模型的正则项是对权重的惩罚，也就是特征对应的权重一旦过大，惩罚就会很大，进一步压缩权重的值，使他不至于过大，而树模型则不一样，树模型的惩罚项通常为叶子节点数和深度等，而我们都知道，对于上面这种 case，树只需要一个节点就可以完美分割9990和10个样本，惩罚项极其之小.

决策树训练的三个步骤

特征选择

信息增益
  • 对数据集D的经验熵: \(H(D)=-\sum_{k=1}^{K}\frac{|C_{k}|}{|D|}log_{2}\frac{|C_{k}|}{|D|}\)
  • 对特征A对数据集D的经验条件熵: \(H(D|A)=\sum_{n=1}^{n}\frac{|D_{i}|}{|D|}H(D_{i})=-\sum_{n=1}^{n}\frac{|D_{i}|}{|D|}\sum_{k=1}^{K}\frac{|D_{ik}|}{|D_{i}|}log_{2}\frac{|D_{ik}|}{|D_{i}|}\)，n为特征A的取值个数
信息增益比
  • 特征A对训练数据D的信息增益比: \(g_{R}(D,A)=\frac{g(D,A)}{H_{A}(D)}\)
    • 其中 \(H_{A}=-\sum_{i=1}^{n}\frac{|D_{i}|}{|D|}log_{2}\frac{|D_{i}|}{|D|}\)，n为特征A的取值个数
基尼指数
  • 对于分布 \(p=(p_{1},…,p_{k})\) 的基尼指数: \(Gini(p)=\sum_{k=1}^{K}p_{k}(1-p_{k})=1-\sum_{k=1}^{K}p_{k}^{2}\)
  • 对样本集合D,基尼指数为: \(Gini(p)=1-\sum_{k=1}^{K}\left(\frac{|C_{k}|}{|D|}\right)^{2}\)
  • 在特征A的条件下,集合D的基尼指数: \(Gini(D,A)=\frac{|C_{1}|}{|D|}Gini(D_{1})+\frac{|C_{2}|}{|D|}Gini(D_{2})\)
    • 我们将集合D根据特征A分为两类:
    • 是否取特征A的某个值,其中 \(A=a\) 的是 \(D_{1}\)， \(A\neq a\) 的是 \(D_{2}\)

决策树的生成

ID3
  • 基于最大化信息增益来选择特征
  • 选取所有信息增益最大的特征作为当前结点的特征
  • 对取值数目较多的属性有所偏好
  • 只有分类树,没有回归树
  • ID3相当于用极大似然法对模型进行选择(问题:如何理解?)
C4.5
  • 基于最大化信息增益比来选择特征
  • 选取信息增益比最大的特征作为当前结点的特征
    • 由于使用最大的信息增益比特征可能对取值数目少的特征属性有所偏好,所以C4.5算法一般不会直接选信息增益比最大的,而是
      • 先从候选区属性中找出信息增益高于平均水平的
      • 再从筛选结果中寻找信息增益比最大的
  • 处理连续型特征时使用二分法(bi-partition)
  • 只有分类树,没有回归树
CART
  • CART的决策树是二叉树
  • 分类树: 基于最小化基尼指数来选择特征
    • 输出变量为离散变量
    • 基于基尼指数选取所有可能的特征A和所有可能的切分点a中,选择基尼指数最小的特征和切分点为最优特征和最优且分点
  • 回归树: 基于最小化平方误差来选择特征
    • CART回归树一般称为最小二乘回归树(因为目标函数的优化是最小化误差的平方和实现的)
    • 输出变量为连续变量
    • 选取时选择最优划分变量(特征)j和最优切分点s,然后按照变量j的划分点s将结点分为两个结点,大于s的为第一个结点,小于s的为第二个结点
  • 一点说明:
      • 《统计学习方法》 *中:
        • 回归树的特征默认是连续变量,选取划分点s时使用的是连续变量的各种中间值作为候选值,大于s的分为一个结点,小于s的分为一个结点
        • 分类树的特征默认是离散变量,选取划分点a时使用的是离散变量的值作为候选值,等于a的分为一个结点,不等于a的分为另一个结点
        • 但是实际上无论时分类树还是回归树,CART都可以用相同手段处理连续值

剪枝

  • 剪枝的核心思想:
    • 就是加入考虑树的复杂度考量(决策树的生成时仅仅是考虑到信息增益和信息增益比,没有考量树的复杂度)
      • 树的深度越深,树越复杂
    • 整体上再考虑树变得更简单的同时保证分类误差较小
预剪枝
  • 预剪枝发生在决策树生成过程中
  • 在每个节点划分前先进行估计
  • 若当前节点划分不能带来决策树准确率提升,则停止划分
  • 在 《统计学习方法》 中未提到这个方法,只讲了一种简单的后剪枝算法
  • 时间复杂度小,欠拟合风险大
后剪枝
  • 后剪枝发生在决策树生成后
  • 自底向上的对非叶子节点进行考察(注意千万不可从根节点开始自顶向下的剪枝,可能失去整体最优的决策树)
  • 若将该节点换成叶子节点能带来决策树准确率提升,则将该节点替换为叶子节点
  • 时间复杂度大,欠拟合风险小
常见的后剪枝方法

各种方法各有优劣,关注不同的优化角度

  • REP 错误率降低剪枝(Reduced Error Pruning)
  • PEP 悲观剪枝(Pessimistic Error Pruning)
  • CCP 代价复杂度剪枝(Cost Complexity Pruning), 详细过程参考CPP剪枝算法描述
  • MEP 最小误差剪枝(Minimum Error Pruning)
  • CVP (Critical Value Pruning)
  • OPP (Optimal Pruning)
ID3和C4.5的剪枝
CART的剪枝

CART使用的是CCP剪枝

  • 对任意的子树,我们可以定义子树的损失
    • \(C_{a}(T)=C(T)+\alpha|T|\)
    • 子树的损失 = 子树的预测误差 + \(\alpha\) * 子树的节点数
    • 对于回归树和分类树,子树的预测误差定义不一样,前者是误差的平方和,后者是基尼指数
  • 可以证明对于给定的Alpha,一定存在某个损失最小的子树,也就是我们要的最优子树
  • 现实中实现时可以使用递归的方法实现
CCP剪枝算法描述

CPP剪枝也是一种后剪枝算法
修正：统计学习方法CART算法第六步中应该跳到第二步，而不是第三步

  • 1：计算所有节点对应的 \(\alpha\) 值: \(\alpha=\frac{C(t)-C(T_{t})}{|T_{t}|-1}\)
    • \(C(t)\) 是以t节点单一节点为树时单一节点树的损失函数
    • \(C(T_{t})\) 是以t节点为根节点的子树时整棵子树的损失函数
    • \(|T_{t}|\) 是以t节点为根节点的子树时整棵子树的节点数量
  • 2：对当前 \(\alpha\) 值最小的节点t剪枝，并存储中间结果的 \(\alpha\) 值和剪枝后的树结构
    • 当 \(\alpha\) 确定时，存在唯一的最小子树 \(T_{\alpha}\) 使损失函数 \(C_{\alpha}(T)\) 最小
  • 3：选取当前树为剪枝后的树，跳转到第1步，直到剪枝到只有三个节点的树时截止
  • 4：截止后得到节点数量从大到小的多个子树 \(T_{\alpha_{0}}, T_{\alpha_{1}},…,T_{\alpha_{n}}\) . (其中 \(T_{\alpha_{i}}\) 也就对应着第i个 \(\alpha\) 值 \(\alpha_{i}\))
  • 5：用交叉验证法对 \(\alpha\) 的值进行选择(CART算法执行时 \(\alpha\) 类似超参数，整个算法学习的过程类似于用交叉验证法确定超参数的过程， \(\alpha\) 的值确定了，对应的决策树也就确定了！)

关于连续特征

统计学习方法
  • 在 《统计学习方法》 中回归树的特征默认是连续变量,分类树的特征默认是离散变量
机器学习 周志华
  • 在<<机器学习>>中提到连续特征的一种解决方案:
    • 把该连续特征所有出现的取值排序
    • 取临近两两之间的平均值作为划分点
    • 像处理离散的点一样,使用信息增益最大化,信息增益率最大化,或者是基尼指数最小化实现对应的划分选择
个人总结
  • 处理连续型变量(特征的能力)
    • ID3 不能处理连续型特征
      • 因为连续型特征往往使得每一个样本该特征取值都不一样,造成该特征对数据集D的经验条件熵为0?
      • 使得ID3算法趋向于选择这个特征?
    • C4.5 能处理连续型特征
      • 将数据排序后找到类别不同的分割线作为切分点
      • 根据切分点把连续属性二分类装换为布尔类型
      • 可多次使用连续属性分类
    • CART 能处理连续型特征
      • 实际对连续型特征的处理与C4.5一样
      • 由于CART树构建时每次都会对特征进行二值化分,所以可以很好的适用与连续型变量

一些总结

  • 算法ID3生成可能是多叉树,而CART一定是二叉树，《统计学习方法》中二者生成相同的数是巧合，除了不同评价方式的特征选择结果一样以外，还需要被选中的特征都是二值的！
  • ID3相当于用极大似然法对模型进行选择

一种很好的理解思路

ID3
  • ID3算法就是用信息增益大小来判断当前节点应该用什么特征来构建决策树，用计算出的信息增益最大的特征来建立决策树的当前节点
ID3的缺点:
  • ID3不能处理连续特征
  • ID3对取值较多的特征有着偏好在相同条件下，取值比较多的特征比取值少的特征信息增益大
  • ID3不能处理缺失值
  • 没有考虑过拟合的问题(问题: ID3没有剪枝吗?)
C4.5
  • C4.5可以看成是对ID3进行改进
C4.5对ID3的改进

  • 对于ID3不能处理连续特征，C4.5的思路是将连续的特征离散化.

    • 样本(m个样本)按照特征的取值排列后取相邻样本的平均值作为划分点(m-1个划分点),分别计算以每个划分点作为二元分类时的信息增益. 最终选择信息增益高的(问题:这里是C4.5,为什么不是使用信息增益比而是信息增益来作为区分?)
    • C4.5选择连续特征作为分类特征时,只分两类,但是后面(其他层结点)可以使用该特征分类,也就是说连续特征在C4.5中可以多次使用,但每次只分为两部分

  • 对于ID3信息增益最大指标会造成偏向于取值较多的特征的问题. C4.5使用信息增益比来解决问题

  • 对于ID3不能处理缺失值的问题,C4.5主要解决两个问题

    • 1）如何在属性值缺失条件下进行属性选择
      • 没有缺失值的属性,正常处理
      • 每个属性A有缺失值:
        • 对该特征进行划分时仅仅考虑在属性A上没有缺失的部分数据,有缺失的数据不考虑.
        • 无缺失的数据计算收益时需要乘以一个权重(无缺失的样本总数/样本总数)
        • 相当于信息增益适当缩小
    • 2）给定划分属性,若样本在该属性上的值缺失,如何对样本进行划分
      • 在A属性没有缺失值的样本,正常划分
      • 在A属性有缺失值的样本:
        • 给每个样本引入权重,初始值都为1
        • 同一个样本按照不同概率划入到不同的结点(当前叶节点)中去(概率是当前结点中样本数量/无缺失样本总数)

  • 对于没有考虑过拟合的问题:

    • C4.5引入了正则化系数剪枝(问题: ID3没有剪枝吗?)
C4.5的缺点
  • [这个问题存疑,没有任何书籍显示C4.5的剪枝策略是PEP, 《统计学习方法》 中只是简单的介绍了后剪枝]C4.5的剪枝方法时PEP,PEP准确度高,但是存在下面两个子问题:
    • 1）PEP使用由上而下的剪枝策略,会导致与预先剪枝相同的问题,造成过度剪枝
    • 2）会造成剪枝失败的情况
  • C4.5生成多叉树,计算机中很多时候多叉树运算效率不如二叉树来的高
  • C4.5只能用于分类
  • C4.5需要进行大量的对数运算(计算熵)
CART
  • 可以理解为对C4.5进一步的改进
CART对C4.5的改进
  • CART使用CPP代价复杂度剪枝算法
  • CART使用二叉树只生成二叉树,即使是离散特征
    • CART对连续特征的处理与C4.5完全相同
    • CART对离散特征也是二分类且也是可以多次使用同一特征(ID3与C4.5中离散特征只能使用一次,且是多分叉)
    • 所以CART是一颗二叉树
  • CART可有分类树和回归树两种
    • 回归树的目标函数的优化是: 最小化误差的平方和
    • 分类树以概率最大的类别作为叶节点的类别
    • 回归树以中位数或者均值作为预测结果
  • CART使用基尼指数作为结点混乱度的度量指标
    • 避免了对数计算(与熵比较)
ID3,C4.5,CART的缺点
  • 每次之全责一个最优特征作为分类决策,而实际中其实可能需要多个特征一起决策
    • 解决方案: 多变量决策树(每次选择多个特征一起决策)
      • 单个特征决策可以看成是直线
      • 多个特征决策可以看成是斜线
  • 样本改变一点点都会造成树的结构改变很大
    • 解决方案: 随机森林等集成学习方法

GBDT(GradientBoostingDecisionTree), 梯度提升树
GBDT泛指所有梯度提升树，包括XGBoost(XGBoost是GBDT的变种),平时为了进行区分,GBDT特指“Greedy Function Approximation:A Gradient Boosting Machine”(GBDT论文原文)提出的算法,只利用了一阶导数信息(XGBoost利用了二阶导数信息)
*梯度的数学定义:函数上升最快的方向

参考论文:Greedy Function Approximation: A Gradient Boosting Machine
一篇很详细的论文阅读笔记:GBM Paper Reading

引用一个常见的通俗例子:GBDT的思想可以用一个通俗的例子解释，假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了（残差作为下一轮拟合的数据的理解）。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小,最终预测时使用他们的结果

五种简称

  • 各种简称,都是同一种算法:
    • GBDT(Gradient Boosting Decision Tree)
    • MART(Multiple Additive Regression Tree)
    • GBT(Gradient Boosting Tree)
    • GTB(Gradient Tree Boosting)
    • GBRT(Gradient Boosting Regression Tree)

模型原理

核心

  • 使用CART作为基础模型(GDBT只能使用CART,不能使用其他树C4.5和ID3等), 后来作者提出也可以使用逻辑回归模型
  • 每棵树学习的是前一棵树的残差(预测值与真实值的差)[这里是当损失函数是均方误差(平方损失, square loss)时可直接使用残差,其他类似的学习算法中若]
  • 残差 = 真实值 - 预测值

如何理解GBDT中的梯度G？

  • G表示Gradient，表示梯度，在GBDT中梯度是指损失函数关于每一个迭代中模型的梯度

与AdaBoost不同

  • AdaBoost是通过利用前一轮弱学习器的误差率来更新训练集的权重

    • 增大分类错误的样本权重,从而使得样本更加关注上一步中分类错误的样本

  • GBDT是通过学习上一轮学习器的残差来实现对真实结果的不断逼近

    • 上一步中预测越接近真实结果的样本,残差越接近0,下一轮中对该样本的关注度越低
    • 上一步中预测越不接近真实结果的样本,残差越大,下一轮中对该样本的关注度越高

  • GBDT的弱学习器只能使用CART回归树,只能用回归树这一点与AdaBoost和RF均不同

    • 因为我们的目标是拟合上一若学习器的残差
    • 而残差往往是数值,不是类别,所以只能使用回归树CART

GBDT分类

二分类
  • GBDT实现二分类时可以每轮迭代直接用一个模型去学残差
  • 此时类别可编码为一个一维向量,取值0或1
多分类
  • GBDT实现多分类时每轮使用一个模型不够了,因为三个模型时使用1,2,3编码显然是不科学的,类别之间不应该有这种数值大小关系
  • 此时三分类模型的类别可编码为一个三维向量,每一维的取值为0或1
  • 在每一轮迭代时,为每个类训练一个CART树,每棵CART树是相互独立的
  • 然后每个模型每轮分别学习当前特征的残差
  • 每个模型都会用到所有的样本
    • 比如一个标记为标记为类别2的样本(x, y=2)
    • 编码为(x, [0,1,0])
    • 对于CART1和CART3(类别1和类别3的CART树)来说,该样本对应输入为(x, y=0)
    • 对于CART2(类别2CART树)来说,该样本对应输入为(x, y=1)
  • 可以理解为把一个三分类问题转化成了3个二分类问题解决了
  • 最后预测时
    • 给定一个未标记样本
    • 每个类对应的模型(每个类的模型个数是该类上模型的迭代次数)都对应给出该类的打分
    • 最后选择分数最高的一个类为最终分类即可

GDBT + LR

  • 为什么在广告CTR预估中, GDBT+LR能够提升效果?
    • 和LR对比: 线性模型
    • 和GBDT对比:

GBDT和神经网络的优劣

深度神经网络

  • 通过不同层级和类型的网络可以对时空信息建模
  • 适合图像, 声音, 文字等带有时序特质的数据

GBDT

  • 基于树模型的GBDT则能很好地处理表格数据
  • 模型的可解释性
  • 输入数据的不变性(几乎不用格式化数据)
  • 更易于调参等特质更适合数值型数据

随机森林是一种集成学习(Ensemble)方法,属于集成学习中的Bagging族,是一种典型的Bagging方法

随机森林

训练

  • 假设训练集总大小为N,特征总数为K
  • 有放回抽样N个训练样本
    • 说明:这种有放回的抽样技术又称为自助法(Bootstrap)重采样技术
  • 随机从所有特征中选取k个特征(k一般远小于总特征数K)
  • 用bootstrap采样的结果(N个样本)和k个特征训练一棵决策树(训练时不剪枝,每棵树都尽可能生长)
  • 重复上述三个步骤:bootstrap采样和训练新的决策树,直到生成m棵决策树
  • 将m棵决策树组合成随机森林

预测

  • 对于一个确定的未标记样本
  • 经过每一棵决策树预测
  • 投票产生结果,确定最终分类

优点

  • 避免过拟合(bootstrap采样[随机]和随机选择部分特征)
  • 便于处理高维度的数据
  • 对高维度的数据无需做特征选择,全部保留也无所谓
  • 可并行计算
  • 模型实现简单

缺点

  • 模型训练多棵树,所以训练时间长
  • 预测时经过多棵树,预测时间长

参数

  • 决策树类型: 三种(ID3,C4.5,CART)均可选,默认均分的三种算法混合到一起
  • 树的数量m:
    • n_estimators
    • int i: n_estimators = i
    • 默认为10
  • 特征个数k(以Sklearn库为例):
    • max_features = k
    • int i: k = i
    • float f: k = f * K
    • sqrt: k = sqrt(K)
    • log2: k = log2(K)
    • None: k = K
    • Sklearn.ensemble.RandomRorestClassifier默认是”auto”,也就是sqrt(K)
  • 树的深度:
    • max_depth
    • 单棵树的深度
    • 默认是None,不做限制
    • int i: 指定树的深度为i
  • 叶子节点最小样本数:
    • int i: min_samples_leaf = i
    • float f: min_samples_leaf = f * N
    • 默认为1

问题: 随机森林的随机体现在哪里?

  • 个人理解
    • 体现在每棵树的训练样本随机 ，有放回采样(自助法(Bootstrap)重采样技术)
    • 体现在每棵树的训练样本的特征随机 ， 对每棵树而言,随机从K个特征中选取k个特征,当前树的每个叶节点分裂时只能从这k个特征中选择

本文主要广告计算领域用于CTR,CVR预估的模型

计算广告领域的术语

一些术语

  • CPA(Cost Per Action):
    • 一种广告计费模式
    • 按照行为(Action)来计费
    • 这里的行为可以是注册,咨询,放入购入车等
  • CPC(Cost Per Click)
    • 一种广告计费模式
    • 按照点击(Click)次数

衡量指标

  • 点击率CTR(click-through rate), 又名点击通过率:
    $$CTR = \frac{Count_{click}}{Count_{show}} $$
    • 分母是广告的实际展示次数
    • 分子是广告的实际点击次数
  • 转化率CVR(conversion rate), 一种CPA衡量指标
    $$CVR= \frac{Count_{conversion}}{Count_{click}}$$
    • 分母是广告的实际点击次数
    • 分子是广告的转化次数,不同场景对转化成功的定义不同,比如手机号码注册用户为一次有效转化,那么这里CVR统计的就是所有点击了广告的人中有多少进行了实际的手机号注册

预估CTR,CVR的模型

人工特征工程+LR

  • 人工提取当前广告的特征
  • LR模型预估用户是否会点击该广告或者注册该网站(二分类)

GBDT+LR

  • 参考博客: https://www.jianshu.com/p/96173f2c2fb4
  • Facebook paper中的一个例子
    • 图中的GBDT只包含两棵树,实际上使用时可包含更多
    • LR的特征数量(样本维度)就是所有树的叶节点树,样本落到当前叶节点则,当前叶节点对应的特征值为1,否则为0
    • 用于LR训练的特征维度共num_trees * num_leaves(也就是所有树叶节点的总数)
    • 由于有多棵树,每个原始样本在每棵树都会落到一个叶节点上,所以得到的新样本中可能有很多个特征值为1
    • 实践中原始输出时可能维度是树的棵数,每个数表示当前树中样本落到第几个叶节点上,对每棵树分别使用OneHot编码即可的到上面的 (num_trees * num_leaves) 维数据

FM

FFM

XGBoost,全称: Extreme Gradient Boosting

概述

  • CART回归树是XGBoost的基分类器

XGBoost模型推导(假设回归树的结构确定)

模型 \(F\) 的加法定义：

$$
\begin{align}
F(x;w) = \sum_{k=0}^{K} f_{k}(x;w_{k})
\end{align}
$$

  • 其中, \(x\) 为输入样本, \(f_{k}\) 为分类回归树,可以是分类回归树空间中的任意一棵树, \(w_{k}\) 是树 \(f_{k}\) 的参数

定义损失函数

$$
\begin{align}
L^{t} &= \sum_{i=1}^{n}l(y_{i},\hat{y}_{i}^{t}) + \Omega(f_{t}) \\
&= \sum_{i=1}^{n}l(y_{i},\hat{y}_{i}^{t-1} + f_{t}(x_{i})) + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2
\end{align}
$$

  • \(L^{t}\)： 第 \(t\) 轮迭代的损失函数
  • \(l(y_{i},\hat{y}_{i}^{t})\) 表示单个样本的损失函数定义
  • \(\hat{y}_{i}^{t} = \hat{y}_{i}^{t-1} + f_{t}(x_{i})\) 表示第 \(t\) 轮 \(x_{i}\) 样本的预测值
    • 加法模型: 第 \(t\) 轮预测值 = 第 \(t-1\) 轮预测值 + 第 \(t\) 棵(轮)决策树的预测值
  • \(\Omega(f_{t})\) 表示正则项
    • \(n\) 表示样本的个数
    • \(T\) 表示叶子结点的个数
    • \(w_{j}\) 表示叶节点分数 ， 即任意样本落到第 \(t\) 棵(轮)决策树的第 \(j\) 叶子结点时的预测值(可称为第 \(t\) 棵(轮)决策树的第 \(j\) 叶子结点的预测值)
    • \(\gamma\) 和 \(\lambda\) 都是正则项参数

第 \(t\) 轮训练的目标

  • 找到一个最优的分类器 \(f_t^{\star}(x)\)，满足
    $$
    \begin{align}
    f_t^{\star}(x) &= \mathop{\arg\max}_{f_t(x)}L^{t} \\
    &= \mathop{\arg\max}_{f_t(x)}\left(\sum_{i=1}^{n}l(y_{i},\hat{y}_{i}^{t}) + \Omega(f_{t})\right) \\
    &= \mathop{\arg\max}_{f_t(x)}\left(\sum_{i=1}^{n}l(y_{i},\hat{y}_{i}^{t-1} + f_{t}(x_{i})) + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2 \right)
    \end{align}
    $$

最小化损失函数推导

损失函数二阶泰勒展开

  • 回忆传统泰勒展开:
    $$
    \begin{aligned}
    f(x) &= f(x_0) + f’(x_0)(x-x_0) + \frac{f’’(x_0)}{2!}(x-x_0)^2 + \cdots + \frac{f^{(n)}(x_0)}{n!}(x-x_0)^n \\
    & = \sum\limits_{n=0}^{\infty}\frac{f^{(n)}x_0}{n!}(x - x_0)^n
    \end{aligned}
    $$

  • 二阶泰勒展开公式
    $$
    \begin{align}
    f(x+\Delta x) \approx f(x) + f’(x)\Delta x + \frac{1}{2}f’’(x)\Delta x^2
    \end{align}
    $$

  • 在我们的场景中,令

    • \(x = \hat{y}_{i}^{t-1}\)
    • \(\Delta x = f_{t}(x_{i})\)

  • 则有对单个样本能得到
    $$
    \begin{align}
    l(y_{i},\hat{y}_{i}^{t-1} + f_{t}(x_{i})) \approx l(y_i,\hat{y}_i^{t-1}) + l’(y_i,\hat{y}_i^{t-1})f_t(x_i) + \frac{1}{2}l’’(y_i,\hat{y}_i^{t-1})f_t^2(x_i)
    \end{align}
    $$

    • \(l’(y_i,\hat{y}_i^{t-1})\) 是 \(l(y_i,\hat{y}_i)\) 对 \(\hat{y}_i\) 的一阶导数在 \(\hat{y}_i = \hat{y}_i^{t-1}\) 处的值
    • \(l’’(y_i,\hat{y}_i^{t-1})\) 是 \(l(y_i,\hat{y}_i)\) 对 \(\hat{y}_i\) 的二阶导数在 \(\hat{y}_i = \hat{y}_i^{t-1}\) 处的值

  • 我们第 \(t\) 轮的目标是找到一个最优的分类器 \(f_t^{\star}(x)\) 最小化损失函数 \(L^{t}\)
    $$
    \begin{align}
    L^{t} \approx \sum_{i=1}^{n}\left(l(y_i,\hat{y}_i^{t-1}) + l’(y_i,\hat{y}_i^{t-1})f_t(x_i) + \frac{1}{2}l’’(y_i,\hat{y}_i^{t-1})f_t^2(x_i)\right) + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2
    \end{align}
    $$

  • 显然上面式子中的 \(l(y_i,\hat{y}_i^{t-1})\) 与 \(f_t(x_i)\) 无关,可以移除,于是有
    $$
    \begin{align}
    L^{t} \approx \sum_{i=1}^{n}\left(l’(y_i,\hat{y}_i^{t-1})f_t(x_i) + \frac{1}{2}l’’(y_i,\hat{y}_i^{t-1})f_t^2(x_i)\right) + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2
    \end{align}
    $$

  • 令:

    • \(g_i = l’(y_i,\hat{y}_i^{t-1})\) 为 \(l(y_i,\hat{y}_i)\) 对 \(\hat{y}_i\) 的一阶导数在 \(\hat{y}_i = \hat{y}_i^{t-1}\) 处的值
    • \(h_i = l’’(y_i,\hat{y}_i^{t-1})\) 是 \(l(y_i,\hat{y}_i)\) 对 \(\hat{y}_i\) 的二阶导数在 \(\hat{y}_i = \hat{y}_i^{t-1}\) 处的值

  • 则有:
    $$
    \begin{align}
    L^{t} \approx \sum_{i=1}^{n}\left(g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)\right) + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2
    \end{align}
    $$

  • 做一个重要的转换 :
    $$f_t(x_i) = w_j, \quad s.t. \ x_i \in I_j$$

    • 上面的式子前半部分成立的条件是 \(x_i\) 落在叶子结点 \(j\) 上
    • 我们将条件 \(x_i\) 落在叶子结点 \(j\) 上表示为 \(\ x_i \in I_j\)

  • 于是: 我们可以将前面对样本的累加变成对叶子结点的累加
    $$
    \begin{align}
    L^{t} &\approx \sum_{j=1}^{T}\left((\sum_{i \in I_j}g_i)w_j + \frac{1}{2}(\sum_{i \in I_j}h_i)w_j^2\right) + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2 \\
    &\approx \sum_{j=1}^{T}\left((\sum_{i \in I_j}g_i)w_j + \frac{1}{2}(\sum_{i \in I_j}h_i + \lambda)w_j^2\right) + \gamma T
    \end{align}
    $$

  • 令:

    • \(G_j = \sum_{i \in I_j}g_i\)
    • \(H_j = \sum_{i \in I_j}h_i\)

  • 则有
    $$
    \begin{align}
    L^{t} \approx \sum_{j=1}^{T}\left(G_jw_j + \frac{1}{2}(H_j + \lambda)w_j^2\right) + \gamma T
    \end{align}
    $$

  • \(L^t\) 对 \(w_j\) 求偏导有
    $$
    \begin{align}
    \frac{\partial L^{t}}{\partial w_j} = G_j + (H_j + \lambda)w_j
    \end{align}
    $$

  • 令导数 \(\frac{\partial L^{t}}{\partial w_j} = 0\) 可得
    $$
    \begin{align}
    w_j^{\star} = -\frac{G_j}{H_j+\lambda}
    \end{align}
    $$

  • 同时
    $$
    \begin{align}
    L^{\star^t} &\approx min(L^t) \\
    &\approx \sum_{j=1}^{T}\left(G_j\cdot (-\frac{G_j}{H_j+\lambda}) + \frac{1}{2}(H_j + \lambda)\cdot(-\frac{G_j}{H_j+\lambda})^2\right) + \gamma T \\
    &\approx -\frac{1}{2}\sum_{j=1}^{T}\left(\frac{G_j^2}{H_j+\lambda}\right) + \gamma T
    \end{align}
    $$

  • 目标函数的计算示例: 目标分数越小越好

结论

  • 在第 \(t\) 轮回归树的结构确定后 ，我们得到的最优叶节点分数与结构无关 \(w_j^{\star} = -\frac{G_j}{H_j+\lambda}\)
  • 最小损失与第 \(t\) 轮回归树的结构的复杂度(叶节点数量)相关
  • 我们还需要确定第 \(t\) 轮回归树的结构

回归树的结构确定

普通决策树树结构的确定

ID3
  • 最大化信息增益来选择分裂特征
C4.5
  • 最大化信息增益比来选择分裂特征
CART
分类树
  • 最小化基尼指数来选择分裂特征
回归树
  • 最小化平方误差来选择分裂特征

XGBoost结点分裂前后的信息增益

  • 信息增益应该与前面的损失函数相关, 损失越小越好
  • 原始损失函数为
    $$
    \begin{align}
    L^{\star^t} \approx -\frac{1}{2}\sum_{j=1}^{T}\left(\frac{G_j^2}{H_j+\lambda}\right) + \gamma T
    \end{align}
    $$
  • 显然,要使得损失函数最小,我们需要使得下面的式子最大:
    $$
    \begin{align}
    \frac{G_j^2}{H_j+\lambda}
    \end{align}
    $$
  • 一个结点分裂后的信息为
    $$
    \begin{align}
    \frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda}
    \end{align}
    $$
    • 左子树的信息 + 右子树的信息
  • 一个结点分裂前信息为
    $$
    \begin{align}
    \frac{(G_L + G_R)^2}{H_L+ H_R + \lambda}
    \end{align}
    $$
  • 从而我们定义一个结点分列前后的信息增益为:
    $$
    \begin{align}
    Gain = \frac{G_L^2}{H_L+ \lambda} + \frac{G_R^2}{H_R+ \lambda} - \frac{(G_L + G_R)^2}{H_L+ H_R + \lambda} - \gamma
    \end{align}
    $$
    • Gain 越大说明当前结点的当前分裂方式越好
    • 其中 \(\gamma\) 是一个超参数用于防止过拟合 ，可以理解为有两层含义:
      • 用于对叶节点数目进行控制
      • 用于增大分裂前后Gain的阈值
      • 事实上 \(\gamma\) 不是凭空来的,开始的定义中 \(\gamma\) 就是L1正则化(叶节点数量)的系数, 这里分裂后叶节点数量多了1个, 我们希望树的叶节点越少越好(模型越简单越好),而这个的信息增益越大越好, 所以减去 \(\gamma\) 值,防止结点分裂得太多
      • 对于每个特征的每个分裂点, \(\gamma\) 值都相同,所以 \(\gamma\) 值对特征和分裂点的选择没有影响,只是影响了某个结点是否能够被分裂(信息增益太小或者为负时我们可以选择不分裂)

XGBoost树节点分裂

精确分裂算法
  • 单个叶节点精确计算信息增益分裂流程(特征和特征分裂取值的选择, 假设一共m个特征)
近似分裂算法
  • 将每个特征的取值划分为多个分位点
  • 每次考察特征时值考察分位点,减少计算复杂度
  • 其他的步骤与前面的精确分裂算法相同,包括分数计算和选择最大分数等
分桶策略与GBDT的不同
  • 传统的GBDT分桶时每个样本的权重都是相同的
  • XGBoost中每个样本的权重为损失函数在该样本点的二阶导数(对不同的样本,计算得到的损失函数的二阶导数是不同的), 这里优点AdaBoost的思想,重点关注某些样本的感觉
  • 这里影响的是划分点的位置(我们划分划分点[桶]时都是均匀划分样本到桶里面,当不同样本的权重不同时,每个桶里面的样本数量可能会不同)
  • 下图是一个示例
  • 详细推导解释,为什么选择损失函数在当前样本的二阶导数作为权重?
    $$
    \begin{align}
    L^{t} &\approx \sum_{i=1}^{n}\left(g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)\right) + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2 \\
    &\approx \sum_{i=1}^{n}\frac{1}{2}h_i\left(2\frac{g_i}{h_i}f_t(x_i) + f_t^2(x_i)\right) + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2 \\
    &\approx \sum_{i=1}^{n}\frac{1}{2}h_i\left(f_t(x_i) - \frac{g_i}{h_i}\right)^2 + \sum_{i=1}^{n}\left ( \frac{g_i^2}{2h_i} - 2g_if_t(x_i) \right) + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T}w_{j}^2 \\
    \end{align}
    $$
    • 上面的式子中第二项在原文中用constant来表示,可以被看成某种正则项
    • 第一项是一个平方误差表达式,样本 \(x_i\) 对应的输出值为 \(\frac{g_i}{h_i}\)，而样本权重就是 \(h_i\)
    • 权重代表概率,概率越大说明该点出现的次数或者该点附近的值出现的次数就越多.
  • XGBoost分桶流程
    • [待更新]

XGBoost整棵树分裂流程

  • 初始化 \(f^0(x)\)
  • for t=1 to M:
    • 计算损失函数对每个训练样本点的一阶导数 \(g_i\)，二阶导数 \(h_i\)
    • 递归对叶子节点运用树分裂算法生成一颗决策树 \(f^t(x)\)，
      • (这一步包括叶子节点的分数 \(w_j\) 也都确定下来)
      • (这一步可以使用近似分裂算法加快训练速度)
    • 把新生成的决策树加入到模型中, \(\hat{y}^t = \hat{y}^{t-1} + f_m(x)\)

传统GDBT与XGBoost的比较

本文主要介绍Attention的原理和变种

RNN的局限: Encoder-Decoder模型

  • RNN 结构
  • Encoder-Decoder结构

Attention机制的引入

  • Attention机制的根本优势在于对不同的
  • 引入Attention前后的Encoder和Decoder对比图
    • 使用 Attention 前: \(\vec{h_{t}^{out}} = f(\vec{h_{t-1}^{out}},\vec{y_{t-1}})\)
    • 使用 Attention 后: \(\vec{h_{t}^{out}} = f(\vec{h_{t-1}^{out}},\vec{y_{t-1}}, \vec{c_{t}})\)
      • \(\vec{c_{t}} = q(\vec{h_{1}^{in}}, \dots, \vec{h_{T}^{in}})\)
      • \(q\) 是个多层的运算,有多重不同实现,详情参考后面的讲解
  • 动态图理解 Attention 机制
    • 图中线条越清晰说明对当前结点的影响越大,不清晰说明影响较小
  • 进一步看结构图
  • 上图中Encoder使用的是双层双向的RNN
    • 第一层倒序从后 \(X_T\) 到前 \(X_1\) 生成, 反方向编码器
    • 第二层正序从前 \(X_1\) 到后 \(X_T\) 生成, 正方向编码器
    • 二者combine为一个更高维度的向量, 这个更高维度的向量整个作为Encoder的隐藏层
  • 流程说明:
    • 利用 RNN 结构得到 Encoder中的 Hidden State (\(\vec{h_1}, \vec{h_2},\dots, \vec{h_T}\))
    • 假设当前 Decoder 的Hidden State 是 \(\vec{s_{t-1}}\)，计算每一个 \(\vec{h_j}\) 与当前输入位置的关联性 \(e_{ij} = a(\vec{s_{t-1}}, \vec{h_j})\)，得到向量 \(\vec{e_t} = (a(\vec{s_{t-1}}, \vec{h_1}), \dots, a(\vec{s_{t-1}}, \vec{h_T})) \)
      • 这里的 \(a\) 是相关性的(函数)运算符, 常用的可以用向量内积(点成),加权点乘等
        • 内积点乘: \(e_{tj} = \vec{s_{t-1}}^T\cdot\vec{h_j}\)
        • 加权点乘: \(e_{tj} = \vec{s_{t-1}}^TW\vec{h_j}\) (一般使用这个)
        • 更复杂的: \(e_{tj} = \vec{v}^Ttanh(W_1\vec{s_{t-1}}^T + W_2\vec{h_j})\)
    • 对 \(\vec{e_t}\) 进行 softmax 操作,将其归一化得到 Attention 的分布, \(\vec{\alpha_t} = softmax(\vec{e_t})\)
    • 利用 \(\vec{\alpha_t}\)，我们可以进行加权求和得到相应的上下文向量(context verctor) \(\vec{c_t} = \sum_{j=1}^T\alpha_{tj}\vec{h_j}\)
    • 计算 Decoder 的下一个 Hidden State \(\vec{s_t} = f_h(\vec{s_{t-1}}, \vec{y_{j-1}}, \vec{c_t})\)

Attention的变种

这里的总结参考博客Attention

  • 基于强化学习的注意力机制：选择性的Attend输入的某个部分
  • 全局&局部注意力机制：其中，局部注意力机制可以选择性的Attend输入的某些部分
  • 多维度注意力机制：捕获不同特征空间中的Attention特征
  • 多源注意力机制：Attend到多种源语言语句
  • 层次化注意力机制：word->sentence->document
  • 注意力之上嵌一个注意力：和层次化Attention有点像
  • 多跳注意力机制：和前面两种有点像，但是做法不太一样。且借助残差连接等机制，可以使用更深的网络构造多跳Attention。使得模型在得到下一个注意力时，能够考虑到之前的已经注意过的词
  • 使用拷贝机制的注意力机制：在生成式Attention基础上，添加具备拷贝输入源语句某部分子序列的能力
  • 基于记忆的注意力机制：把Attention抽象成Query，Key，Value三者之间的交互；引入先验构造记忆库
  • 自注意力机制：自己和自己做attention(这里的自己只每个文档自身)，使得每个位置的词都有全局的语义信息，有利于建立长依赖关系

广义的Attention机制

参考博客: https://www.sohu.com/a/226596189_500659

  • Attention的本质:
    • 一个Attention函数可以被描述为一个把查询(Query)和键-值(Key-Value)对集合变换成输出(Attention Value)的映射
    • 简单的讲就是一个把 (Query,[Key-Value]s) 映射成一个 Attention Value (输出)
    • An attention function can be described as Mapping aquery and a set of key-value pairs to an output
  • 表示成数学公式如下
  • 如上图所示,在计算 Attention 时主要分为三步
    • 第一步是将 Query 和每个 Key 进行相似度计算得到权重，常用的相似度函数有点积，拼接，感知机等
    • 第二步一般是使用一个 Softmax 函数对这些权重进行归一化
    • 第三步将权重和相应的键值 Value 进行加权求和得到最后的 Attention
  • Attention过程还可以大致分为两步理解:
      1. 将Query和Key经过相似度计算(某种数学运算)的结果通过 Softmax 激活函数激活得到上文所说的权重得分布 \(\vec{\alpha} = (\alpha_1\dots \alpha_n)\)
        • 变换一般包括
          • 点乘(Dot): \(f(Q,K_i) = Q^TK_i\)
          • 加权点乘(General): \(f(Q,K_i) = Q^TW_{\alpha}K_i\)， \(W_{\alpha}\) 对不同的 \(\alpha_i\)
          • 拼接(Concat): \(f(Q,K_i) = W[Q^T;K_i]\)
          • 感知机(Perceptorn): \(f(Q,K) = \boldsymbol{v}^T tanh(W_Q, UK_i)\)
        • Query和Key在不同任务中是不同的东西
          • 在阅读理解中: Query指的是问题,Key指的是文档
          • 在简单的文本分类中: Query和Key可以是同一个句子(这也就是Self Attention), 也就是句子自己和自己做两个词之间的相似度计算的到权重分布
      1. 将权重分布 \(\vec{\alpha} = (\alpha_1\dots \alpha_n)\) 对Value做加权求和得到最终的特征表示
        • 在当前NLP任务中, 基本上 Key == Value
        • 阅读理解任务中, Value指的就是前面的Key, 是文档
        • 简单文本分类中, Value指句子
        • 在 Self Attention 机制中, 由于之前提到过, Query == Key ， 所以有Key == Value == Query
          • 输入一个句子，那么里面的每个词都要和该句子中的所有词进行 Attention 计算, 然后Softmax得到当前句子中每个词的权重,进而对句子中的词求和, 输出当前句子在当前模型中的Attention表示(Attention Value), 即$$\boldsymbol{Y_{AttentionOutput}} = Self Attention(\boldsymbol{Q},\boldsymbol{K},\boldsymbol{V}) = Attention(\boldsymbol{X},\boldsymbol{X},\boldsymbol{X})$$

对Attention的直观解释是

请求为向量时

  • 现有查询向量 q
  • 想从 Value 矩阵(每列对应一个样本) 中按照比例选择样本进行加权求和得到与 q 相关的查询结果
    • 要求是样本与 q 越相关，权重越大
  • Value 中的每个样本都有 Key 矩阵 中的一个样本与之对应(NLP中 Key 往往是 Value 自己)
  • 将 q 与 Key 的每个样本做相关性计算，得到其与 Key 中每个样本的相关性
  • 对 q 与 Key 的所有相关性做归一化，得到权重比例
  • 按照这个比例将 Value 中的样本加权输出结果
  • 该结果就是 Value 经过 \(F(q, Key)\) 加权求和后的结果
  • 也就是 q 对应的结果

请求为矩阵时

  • 现有查询矩阵 Query， 包含 m 个查询向量
  • 相当于重复 m 次做单个请求为向量的运算
  • 每个 q 都能得到一个结果
  • 在实际计算时，可以将整个矩阵一起计算，主要注意归一化是对单个 q 向量与 Key 矩阵生成的结果即可

更多分析

  • 当 Key 与 Value 相同时
    • 其实是说计算 Value 每个样本的权重就用自己去与 q 计算即可
    • NLP中一般都是这样的
  • 当 Key 与 Query 相同时，
    • 其实是找自身不同样本间的相关性
    • 然后根据不同样本的对应其他样本的相关性对其他样本进行加权求和得到自己对应的结果
    • NLP中Self-Attention是这样的
  • Self-Attention是 Key == Value == Query 的情况

Attention研究发展趋势

ps

  • 应用场景：当使用命令sh run.sh启动一个进程后，想要删除，却不知道进程号
  • 查找步骤：
    • 首先使用ps aux | grep run.sh列出进程
    • 杀死进程kill -9 [PID]