LightGBM

AdaBoost

通过改变训练样本权重，学习多个分类器，并将分类器进行线性 组合，提高分类性能

• 对离群点、奇异点敏感
• 对过拟合不敏感

Boosting实现

• 改变训练数据权值或概率分布：提高分类错误样本权值、降低 分类正确样本权值

• 弱分类器组合：加权多数表决，即加大分类误差率小的弱分类器 权值，使其在表决中起更大作用；减小分类误差率大的弱分类器 权值，使其在表决中起更小作用

步骤

• 输入：训练数据集$T={(x_1, y_1), \cdots, (x_N, y_N)}$， 弱分类器算法$G(x)$

  • $x_i \in \mathcal{X \subset R^n}$
  • $y_i \in \mathcal{Y} = {-1, +1 }$

• 输出：最终分类器$G(x)$

• 初始化训练数据权值分布： $D1=(w{11}, \cdots, w{1N}), w{1i}=\frac 1 N$

• 对$m=1,2,\cdots,M$（即训练M个弱分类器）

  • 使用具有权值分布$D_m$的训练数据学习，得到基本 分类器

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

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

    $$\begin{align*} e_m & = P(G_m(x_i)) \neq y_i) \\ & = \sum_{i=1}^N w_{mi}I(G_m(x_i) \neq y_i) \\ & = \sum_{G_m(x_i) \neq y_i} w_{mi} \end{align*}$$

  • 计算$G_m(x)$组合为最终分类器时权重

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

    • $\alpha_m$表示就简单分类器$G_m(x)$在最终分类器中 的重要性，随$e_m$减小而增加 （弱分类器保证$e_m \leq 1/2$）

  • 更新训练集权值分布

    $$\begin{align*} D_{m+1} & = (w_{m+1,1}, \cdots, w_{m+1,N}) \\ w_{m+1,i} & = \frac {w_{mi}} {Z_m} exp(-\alpha y_i G_m(x_i)) = \left \{ \begin{array}{l} \frac {w_mi} {Z_m} e^{-\alpha_m}, & G_m(x_i) = y_i \\ \frac {w_mi} {Z_m} e^{\alpha_m}, & G_m(x_i) \neq y_i \\ \end{array} \right. \\ Z_m & = \sum_{i=1}^N w_{mi} exp(-\alpha_m y_i G_m(x_i)) \end{align*}$$

    • $Zm$：规范化因子，是第m轮调整后的权值之和，其 使得$D{m+1}$成为概率分布
    • 误分类样本权值相当于被放大 $e^{2\alpha_m} = \frac {e_m} {1 - e_m}$倍

• 构建基本分类器线性组合

  $$f(x) = \sum_{m=1}^M \alpha_m G_m(x)$$

  得到最终分类器

  $$G(x) = sign(f(x)) = sign(\sum_{m=1}^M \alpha_m G_m(x))$$

  • 这里$\alpha_m$没有规范化，和不为1，规范化没有必要
  • $f(x)$符号决定分类预测结果，绝对值大小表示分类确信度

• AdaBoost中分类器学习和之后的分类误差率“无关”，基分类器 学习算法中的loss不是分类误差率，可以是其他loss，只是需要 考虑训练数据的权值分布

  • 好像基学习器的loss就要是和集成部分调权的loss一致

    todo

  • 按权值分布有放回的抽样，在抽样集上进行训练
  • 各样本loss按权重加权，类似分类误差率中加权

训练误差边界

AdaBoost算法最终分类器的训练误差边界为

• $G(x_i) \neq y_i$时，$y_if(x_i)<0$，所以 $exp(-y_i f(x_i)) \geq 1$，则不等式部分可证

• $$\begin{align*} \frac 1 N \sum_i exp(-y_i f(x_i)) & = \frac 1 N \sum_i exp(-\sum_{m=1}^M \alpha_m y_i G_m(x_i)) \\ & = \sum_i (w_{1,i} \prod_{m=1}^M exp(-\alpha_m y_i G_m(x_i))) \\ & = \sum_i (Z_1 w_{2,i} \prod_{m=2}^M exp(-\alpha_m y_i G_m(x_i))) \\ & = \prod_{m=1}^M Z_i \sum_i w_{M+1,i} \\ & = \prod_{m=1}^M Z_i \end{align*}$$

• AdaBoost训练误差边界性质的关键：权重调整与基本分类器权重 调整共系数（形式不完全一样）
• 这也是AdaBoost权重调整设计的依据，方便给出误差上界

二分类训练误差边界

• $\gamma_m = \frac 1 2 - e_m$

• $$\begin{align*} Z_m & = \sum_{i=1}^N w_{m,i} exp(-\alpha y_i G_m(x_i)) \\ & = \sum_{y_i = G_m(x_i)} w_{m,i}e^{-\alpha_m} + \sum_{y_i \neq G_m(x_i)} w_{m,i}e^{\alpha_m} \\ & = (1-e_m)e^{-\alpha_m} + e_m e^{\alpha_m} \\ & = 2\sqrt{e_m(1-e_m)} \\ & = \sqrt{1-4\gamma^2} \end{align*}$$

• 由$\forall x \in [0, 0.5], e^{-x} > \sqrt{1-2x}$可得， $\sqrt{1-4\gamma_m^2} \leq exp(-2\gamma_m^2)$

• 二分类AdaBoost误差边界性质的关键：$\alpha$的取值，也是 前向分步算法（损失函数）要求
• 若存$\gamma > 0$，对所有m有$\gamma_m \geq \gamma$，则 $$\frac 1 N \sum_{i=1}^N I(G(x_i) \neq y_i) \neq exp(-2M\gamma^2)$$ 即AdaBoost的训练误差是指数下降的
• 分类器下界$\gamma$可以未知，AdaBoost能适应弱分类器各自 训练误差率，所以称为adptive

Adaboost.M1

Adaboost.M1是原版AdaBoost的多分类升级版，基本思想同Adaboost

Boosting实现

• 基分类器组合方式

  • 仍然是加权投票，且投票权重同Adaboost
  • 出于多分类考虑，没有使用sign符号函数

• 改变训练数据权值或概率分布：和Adaboost形式稍有不同，但 相对的错误分类样本提升比率完全相同

  • 被上个分类器错误分类样本，权值保持不变
  • 被上个分类器正确分类样本，权值缩小比例是Adaboost平方

步骤

• 输入

  • 训练集：$T={x_i, y_i}, i=1,\cdots,N; y_i \in C, C={c_1, \cdots, c_m}$
  • 训练轮数：T
  • 弱学习器：I

• 输出：提升分类器

  $$H(x) = \arg\max_{y \in C} \sum_{m=1}^M ln(\frac 1 {\beta_m}) [h_m(x) = y]$$

  • $h_t, h_t(x) \in C$：分类器
  • $\beta_t$：分类器权重

误分率上界

• 对弱学习算法产生的伪损失$\epsilon1,\cdots,\epsilon_t$， 记$\gamma_t = 1/2 \epsilon_t$，最终分类器$h{fin}$误分率 上界有 $$\frac 1 N |\{i: h_{fin}(x_i) \neq y_i \}| \leq \prod_{t-1}^T \sqrt {1-4\gamma^2} \leq exp(-2 \sum_{t-1}^T \gamma^2)$$

特点

Adaboost.M1和Adaboost基本上没有区别

• 类别数目为2的Adaboost.M1就是Adaboost
• 同样无法处理对误分率高于0.5的情况，甚至在多分类场合， 误分率小于0.5更加难以满足
• 理论误分率上界和Adaboost相同

Adaboost.M2

AdaboostM2是AdaboostM1的进阶版，更多的利用了基分类器信息

• 要求基学习器能够输出更多信息：输出对样本分别属于各类别 的置信度向量，而不仅仅是最终标签
• 要求基分类器更加精细衡量错误：使用伪损失代替误分率 作为损失函数

Psuedo-Loss

• $D$：权重分布（行和为1，但不满足列和为1）

  • $D_{i,y}$：个体$x_i$中错误标签$y$的权重，代表从个体 $x_i$中识别出错误标签$y$的重要性

• $B = {(i, y)|y \neq y_i, i=1,2,\cdots,N }$
• $w$：个体各错误标签权重边际分布
• $h(x, y)$：模型$h$预测样本$x$为$y$的置信度

  • $h(x_i,y_i)$：预测正确的置信度
  • $h(x_i,y), y \neq y_i$：预测$x_i$为错误分类$y$置信度

• 伪损失函数同时考虑了样本和标签的权重分布
• 通过改变此分布，能够更明确的关注难以预测的个体标签， 而不仅仅个体

Boosting实现

• 改变数据权值或者概率分布

  • 使用psuedo-loss替代误分率，以此为导向改变权值
  • 对多分类每个错误分类概率分别计算错误占比，在此基础上 分别计算

• 基分类器组合方式：同Adaboost.M1

步骤

训练误差上界

• 对弱学习算法产生的伪损失$\epsilon1,\cdots,\epsilon_t$， 记$\gamma_t = 1/2 \epsilon_t$，最终分类器$h{fin}$误分率 上界有

特点

• 基于伪损失的Adaboost.M2能够提升稍微好于随机预测的分类器

• Adaboosting.M2能够较好的解决基分类器对噪声的敏感性，但是 仍然距离理论最优Bayes Error有较大差距，额外误差主要 来自于

  • 训练数据
  • 过拟合
  • 泛化能力

• 控制权值可以有效的提升算法，减小最小训练误差、过拟合 、泛化能力

  • 如对权值使用原始样本比例作为先验加权

• 其分类结果不差于AdaBoost.M1（在某些基分类器、数据集下）

Gredient Boosting

GB：（利用）梯度提升，将提升问题视为优化问题，前向分步算法 利用最速下降思想实现

• 一阶展开拟合损失函数，沿负梯度方向迭代更新

  • 损失函数中，模型的样本预测值$f(x)$是因变量
  • 即$f(x)$应该沿着损失函数负梯度方向变化
  • 即下个基学习器应该以负梯度方向作为优化目标，即负梯度 作为伪残差

  • 类似复合函数求导

• 对基学习器预测值求解最优加权系数

  • 最速下降法中求解更新步长体现
  • 前向分布算法中求解基学习器权重

损失函数

基学习器拟合目标：损失函数的负梯度在当前模型的值

平方损失

平方损失：$L(y, f(x)) = \frac 1 2 (y - f(x))^2$（回归）

• 第m-1个基学习器伪残差为

  $$r_{m,i} = y_i - f_{m-1}(x_i), i=1,2,\cdots,N$$

  • $N$：样本数量

• 第m个基学习器为

  $$\begin{align*} h_m & = \arg\min_h \sum_{i=1}^N \frac 1 2 (y_i - (f_{m-1}(x_i) + h(x)))^2 \\ & = \arg\min_h \sum_{i=1}^N \frac 1 2 (C_{m,i} - h(x))^2 \\ C_{m,i} & = y_i - f_{m-1}(x_i) \end{align*}$$

• 第m轮学习器组合为

  $$f_m = f_{m-1} + \alpha_m h_m$$

  • $\alpha_m$：学习率，留给之后基模型学习空间

  • 这里只是形式上表示模型叠加，实际上树模型等不可加， 应该是模型预测结果叠加

指数损失

指数损失：$L(y, f(x)) = e^{-y f(x)}$（分类）

• 第m-1个基学习器伪残差

  $$r_{m,i} = -y_i e^{-y_i f_{m-1}(x_i)}, i=1,2,\cdots,N$$

• 基学习器、权重为

  $$\begin{align*} h_m & = \arg\min_h \sum_{i=1}^N exp(-y_i(f_{m-1}(x_i) + \alpha f(x_i))) \\ & = \arg\min_h \sum_{i=1}^N C_{m,i} exp(-y_i \alpha f(x_i)) \\ C_{m,i} & = exp(-y_i f_{m-1}(x_i)) \end{align*}$$

• 第m轮学习器组合为

  $$f_m = f_{m-1} + \alpha_m h_m$$

步骤

• 输入：训练数据集$T={(x_1, y_1), \cdots, (x_N, y_N)}$， 损失函数$L(y, f(x))$

  • $x_i \in \mathcal{X \subset R^n}$
  • $y_i \in \mathcal{Y} = {-1, +1 }$

• 输出：回归树$\hat f(x)$

• 初始化模型

  $$\hat y_i^{(0)} = \arg\min_{\hat y} \sum_{i=1}^N L(y_i, \hat y)$$

• 对$m=1,2,\cdots,M$（即训练M个若分类器）

  • 计算伪残差

    $$r_i^{(t)} = -\left [ \frac {\partial L(y, \hat y_i)} {\partial y_i} \right ]_{\hat y_i=\hat y_i^{(t-1)}}$$

  • 基于${(x_i, r_i^{(t)})}$生成基学习器$h_t(x)$

  • 计算最优系数

    $$\gamma = \arg\min_\gamma \sum_{i=1}^N L(y_i, \hat y_i^{(t-1)} + \gamma h_t(x_i))$$

  • 更新预测值

    $$\hat y_i^{(t)} = \hat y_i^{(t-1)} + \gamma_t h_t (x)$$

• 得到最终模型

  $$\hat f(x) = f_M(x) = \sum_{t=1}^M \gamma_t h_t(x)$$

Gradient Boosted Desicion Tree

GBDT：梯度提升树，以回归树为基学习器的梯度提升方法

• GBDT会累加所有树的结果，本质上是回归模型（毕竟梯度）

  • 所以一般使用CART回归树做基学习器
  • 当然可以实现分类效果

• 损失函数为平方损失（毕竟回归），则相应伪损失/残差

  $$r_{t,i} = y_i - f_{t-1}(x_i), i=1,2,\cdots,N$$

特点

• 准确率、效率相较于RF有一定提升
• 能够灵活的处理多类型数据
• Boosting类算法固有的基学习器之间存在依赖，难以并行训练 数据，比较可行的并行方案是在每轮选取最优特征切分时，并行 处理特征

XGBoost

Extreme Gradient Boost/Newton Boosting：前向分步算法利用 Newton法思想实现

• 二阶展开拟合损失函数

  • 损失函数中，模型的样本预测值$\hat y_i$是因变量
  • 将损失函数对$\hat y_i$二阶展开拟合
  • 求解使得损失函数最小参数

• 对基学习器预测值求解最优加权系数

  • 阻尼Newton法求解更新步长体现
  • 前向分布算法中求解基学习器权重
  • 削弱单个基学习器影响，让后续基学习器有更大学习空间

损失函数

• 第t个基分类器损失函数

  $$\begin{align*} obj^{(t)} & = \sum_{i=1}^N l(y_i, \hat y_i^{(t)}) + \Omega(f_t) \\ & = \sum_i^N l(y_i, \hat y_i^{(t-1)} + f_t(x_i)) + \Omega(f_t) \\ & \approx \sum_{i=1}^N [l(y_i, \hat y^{(t-1)}) + g_i f_t(x_i) + \frac 1 2 h_i f_t^2(x_i)] + \Omega(f_t) \\ & = \sum_{i=1}^N [l(y_i, \hat y^{(t-1)}) + g_i f_t(x_i) + \frac 1 2 h_i f_t^2(x_i)] + \gamma T_t + \frac 1 2 \lambda \sum_{j=1}^T {w_j^{(t)}}^2 \\ \Omega(f_t) & = \gamma T_t + \frac 1 2 \lambda \sum_{j=1}^T {w_j^{(t)}}^2 \end{align*}$$

  • $f_t$：第t个基学习器
  • $f_t(x_i)$：第t个基学习器对样本$x_i$的取值
  • $gi = \partial{\hat y} l(y_i, \hat y^{t-1})$
  • $hi = \partial^2{\hat y} l(y_i, \hat y^{t-1})$
  • $\Omega(f_t)$：单个基学习器的复杂度罚
  • $T_t$：第t个基学习器参数数量，即$L_0$罚

    • 线性回归基学习器：回归系数数量
    • 回归树基学习器：叶子节点数目

  • $\gamma$：基学习器$L_0$罚系数，模型复杂度惩罚系数
  • $w_j = f_t$：第t个基学习器参数值，即$L_2$罚

    • 线性回归基学习器：回归系数值
    • 回归树基学习器：叶子节点

  • $\lambda$：基学习器$L_2$罚系数，模型贡献惩罚系数
  • $\approx$：由二阶泰勒展开近似

• 对损失函数进行二阶泰勒展开（类似牛顿法）拟合原损失函数， 同时利用一阶、二阶导数求解下个迭代点

• 正则项以控制模型复杂度

  • 降低模型估计误差，避免过拟合
  • $L_2$正则项也控制基学习器的学习量，给后续学习器留下 学习空间

树基学习器

XGBoost Tree：以回归树为基学习器的XGBoost模型

• 模型结构说明

  • 基学习器类型：CART
  • 叶子节点取值作惩罚：各叶子节点取值差别不应过大，否则 说明模型不稳定，稍微改变输入值即导致输出剧烈变化
  • 树复杂度惩罚：叶子结点数量

• XGBoost最终损失（结构风险）有

  $$\begin{align*} R_{srm} & = \sum_{i=1}^N l(y_i, \hat y_i) + \sum_{t=1}^M \Omega(f_t) \end{align*}$$

  • $N, M$：样本量、基学习器数量
  • $\hat y_i$：样本$i$最终预测结果

损失函数

• 以树作基学习器时，第$t$基学习器损失函数为

  $$\begin{align*} obj^{(t)} & = \sum_{i=1}^N l(y_i, \hat y_i^{(t)}) + \Omega(f_t) \\ & \approx \sum_{i=1}^N [l(y_i, \hat y^{(t-1)}) + g_i f_t(x_i) + \frac 1 2 h_i f_t^2(x_i)] + \gamma T_t + \frac 1 2 \lambda \sum_{j=1}^T {w_j^{(t)}}^2 \\ & = \sum_{j=1}^{T_t} [(\sum_{i \in I_j} g_i) w_j^{(t)} + \frac 1 2 (\sum_{i \in I_j} h_i + \lambda) {w_j^{(t)}}^2] + \gamma T_t + \sum_{i=1}^N l(y_i, \hat y^{(t)}) \\ & = \sum_{j=1}^{T_t} [G_i w_j^{(t)} + \frac 1 2 (H_j + \lambda){w_j^{(t)}}^2] + \gamma T_t + \sum_{i=1}^N l(y_i, \hat y^{(t)}) \\ & = \sum_{j=1}^{T_t} [G_i w_j^{(t)} + \frac 1 2 (H_j + \lambda)(w_j^{(t)})^2] + \gamma T_t + \sum_{i=1}^N l(y_i, \hat y^{(t)}) \\ \end{align*}$$

  • $f_t, T_t$：第t棵回归树、树叶子节点
  • $f_t(x_i)$：第t棵回归树对样本$x_i$的预测得分
  • $w_j^{(t)} = f_t(x)$：第t棵树中第j叶子节点预测得分
  • $gi = \partial{\hat y} l(y_i, \hat y^{t-1})$
  • $hi = \partial^2{\hat y} l(y_i, \hat y^{t-1})$
  • $I_j$：第j个叶结点集合
  • $Gj = \sum{i \in I_j} g_i$
  • $Hj = \sum{i \in I_j} h_i$

  • 对回归树，正则项中含有$(w_j^{(t)})^2$作为惩罚，能够 和损失函数二阶导合并，不影响计算

  • 模型复杂度惩罚项惩罚项是针对树的，定义在叶子节点上， 而平方损失是定义在样本上，合并时将其改写

• 第t棵树的整体损失等于其各叶子结点损失加和，且 各叶子结点取值之间独立

  • 则第t棵树各叶子结点使得损失最小的最优取值如下 （$G_j, H_j$是之前所有树的预测得分和的梯度取值，在 当前整棵树的构建中是定值，所以节点包含样本确定后， 最优取值即可确定）

    $$w_j^{(*)} = -\frac {\sum_{i \in I_j} g_i} {\sum_{i \in I_j} h_i + \lambda} = -\frac {G_j} {H_j + \lambda}$$

  • 整棵树结构分数（最小损失）带入即可得

    $$obj^{(t)} = -\frac 1 2 \sum_{j=i}^M \frac {G_j^2} {H_j + \lambda} + \gamma T$$

  • 则在结点分裂为新节点时，树损失变化量为

    $$l_{split} = \frac 1 2 \left [ \frac {(\sum_{i \in I_L} g_i)^2} {\sum_{i \in I_L h_i} + \lambda} + \frac {(\sum_{i \in I_R} g_i)^2} {\sum_{i \in I_R h_i} + \lambda} - \frac {(\sum_{i \in I} g_i)^2} {\sum_{i \in I h_i} + \lambda} \right ] - \gamma$$

    • $I_L, I_R$：结点分裂出的左、右结点

• 则最后应根据树损失变化量确定分裂节点、完成树的分裂，精确 贪心分裂算法如下

  !xgb_exact_greedy_algorithm_for_split_finding

  • 对于连续型特征需遍历所有可能切分点

    • 对特征排序
    • 遍历数据，计算上式给出的梯度统计量、损失变化

  • 不适合数据量非常大、或分布式场景

模型细节

• shrinkage：对新学习的树使用系数$\eta$收缩权重

  • 类似SGD中学习率，降低单棵树的影响，给后续基模型留下 学习空间

• column subsampling：列抽样

  • 效果较传统的行抽样防止过拟合效果更好 （XGB也支持行抽样）
  • 加速计算速度

XGB树分裂算法

• 线性回归作为基学习器时，XGB相当于L0、L2正则化的 Logistic回归、线性回归

近似分割算法

XGB近似分割算法：根据特征分布选取分位数作为候选集，将连续 特征映射至候选点划分桶中，统计其中梯度值、计算最优分割点

!xgb_approximate_algorithm_for_split_finding

• 全局算法：在树构建初始阶段即计算出所有候选分割点，之后 所有构建过程均使用同样候选分割点

  • 每棵树只需计算一次分割点的，步骤少
  • 需要计算更多候选节点才能保证精度

• 局部算法：每次分裂都需要重新计算候选分割点

  • 计算步骤多
  • 总的需要计算的候选节点更少
  • 适合构建较深的树

• 分位点采样算法参见 ml_model/model_enhancement/gradient_boost

Sparsity-aware Split Finding

稀疏特点分裂算法：为每个树节点指定默认分裂方向，缺失值对应 样本归为该方向

• 仅处理非缺失值，算法复杂度和随无缺失数据集大小线性增加， 减少计算量

• 按照升许、降序分别扫描样本两轮，以便将缺失值样本分别归为 两子节点，确定最优默认分裂方向

  

XGB系统设计

Column Block for Parallel Learning

• 建树过程中最耗时的部分为寻找最优切分点，而其中最耗时部分 为数据排序

XGB对每列使用block结构存储数据

• 每列block内数据为CSC压缩格式

  • 特征排序一次，之后所有树构建可以复用（忽略缺失值）
  • 存储样本索引，以便计算样本梯度
  • 方便并行访问、处理所有列，寻找分裂点

• 精确贪心算法：将所有数据（某特征）放在同一block中

  • 可同时对所有叶子分裂点进行计算
  • 一次扫描即可得到所有叶子节点的分割特征点候选者统计 数据

• 近似算法：可以使用多个block、分布式存储数据子集

  • 对local策略提升更大，因为local策略需要多次生成分位点 候选集

Cache-aware Access

• 列block结构通过索引获取数据、计算梯度，会导致非连续内存 访问，降低CPU cache命中率

• 精确贪心算法：使用cache-aware prefetching

  • 对每个线程分配连续缓冲区，读取梯度信息存储其中，再 统计梯度信息
  • 对样本数量较大时更有效

• 近似算法：合理设置block大小为block中最多的样本数

  • 过大容易导致命中率低、过小导致并行化效率不高

Blocks for Out-of-core Computation

• 数据量过大不能全部存放在主存时，将数据划分为多个block 存放在磁盘上，使用独立线程将block读入主存 （这个是指数据划分为块存储、读取，不是列block）

• 磁盘IO提升

  • block compression：将block按列压缩，读取后使用额外 线程解压
  • block sharding：将数据分配至不同磁盘，分别使用线程 读取至内存缓冲区

分位点采样算法—XGB

Quantile Sketch

样本点权重

• 根据已经建立的$t-1$棵树可以得到数据集在已有模型上误差， 采样时根据误差对样本分配权重，对误差大样本采样粒度更大

• 将树按样本点计算损失改写如下

  $$\sum_{i=1}^N \frac 1 2 h_i(f_t(x_i) - \frac {g_i} {h_i})^2 + \Omega(f_t) + constant$$

• 则对各样本，其损失为$f_t(x_i) - \frac {g_i} {h_i}$ 平方和$h_i$乘积，考虑到$f_t(x_i)$为样本点在当前树预测 得分，则可以

  • 将样本点损失视为“二次损失”
  • 将$\frac {g_i} {h_i}$视为样本点“当前标签”
  • 相应将$h_i$视为样本点权重

• 样本权重取值示例

  • 二次损失：$h_i$总为2，相当于不带权
  • 交叉熵损失：$h_i=\hat y(1-\hat y)$为二次函数， 则$\hat y$接近0.5时权重取值大，此时该样本预测值 也确实不准确，符合预期

Rank函数

• 记集合$D={(x_1, h_1), \cdots, (x_n, h_n)}$

• 定义rank函数$r_D: R \rightarrow [0, +\infty)$如下

  $$r_D(z) = \frac 1 {\sum_{(x, h) \in D} h} \sum_{(x, h) \in D, x < z} h$$
  • 即集合$D$中权重分布中给定取值分位数
  • 即取值小于给定值样本加权占比，可视为加权秩

分位点抽样序列

• 分位点抽样即为从集合$D$特征值中抽样，找到升序点序列 $S = {s_1, \cdots, s_l}$满足

  $$|r_D(s_j - r_D(s_{j+1})| < \epsilon$$

  • $\epsilon$：采样率，序列长度$l = 1/\epsilon$
  • $s1 = \min{i} x_i$：特征最小值

  • $sl = \max{i} x_i$：特征最大值

  • 各样本等权分位点抽样已有成熟方法，加权分位点抽样方法 为XGB创新，如下

Weighted Quantile Sketch

Formalization

• 记$Dk={(x{1,k}, h1), \cdots, (x{n,k}, h_n)}$为各 训练样本第$k$维特征、对应二阶导数

  • 考虑到数据点可能具有相同$x, h$取值，$D_k$为可能包含 重复值的multi-set

• 对于多重集$D$，额外定义两个rank函数

  $$\begin{align*} r_D^{-}(y) & = \sum_{(x,h) \in D, x<y} h \\ r_D^{+}(y) & = \sum_{(x,h) \in D, x \leq y} h \end{align*}$$

  定义相应权重函数为

  $$w_D(y) = r_D^{+}(y) - r_D^{-}(y) = \sum_{(x,h) \in D, x=y} h$$

• 多重集$D$上全部权重和定义为

  $$w(D) = \sum_{(x, w) \in D} w$$

Quantile Summary of Weighted Data

• 定义加权数据上的quantile summary为 $Q(D)=(S, \tilde r_D^{+}, \tilde r_D^{-}, \tilde w_D)$

  • $S$为$D$中特征取值抽样升序序列，其最小、最大值分别 为$D$中特征最小、最大值

  • $\tilde r_D^{+}, \tilde r_D^{-}, \tilde w_D$为定义在 $S$上的函数，满足

    $$\begin{align*} \tilde r_D^{-}(x_i) & \leq r_D^{-}(x_i) \\ \tilde r_D^{+}(x_i) & \leq r_D^{+}(x_i) \\ \tilde w_D(x_i) & \leq w_D(x_i) \\ \tilde r_D^{-}(x_i) + \tilde w_D(x_i) & \leq \tilde r_D^{-}(x_{i+1}) \\ \tilde r_D^{+}(x_i) + \tilde w_D(x_i) & \leq \tilde r_D^{+}(x_{i+1}) \\ \end{align*}$$

• $Q(D)$满足如下条件时，称为 $\epsilon$-approximate quantile summary

  $$\forall y \in D_X, \tilde r_D^{+}(y) - \tilde r_D(y) - \tilde w_D(y) \leq \epsilon w(D)$$
  • 即对任意$y$的秩估计误差在$\epslion$之内

• $\phi-quantile$：秩位于$\phi * N$的元素（一般向下取整）
• $\epsilon-\phi-quantile$：秩位于区间 $[(\phi-\epsilon)N, (\phi+\epsilon)N]$的元素

构建$\epsilon$-Approximate Qunatile Summary

• 初始化：在小规模数据集 $D={(x_1,h_1), \cdots, (x_n,h_n)}$上构建初始 初始quantile summary $Q(D)=(S, \tilde r_D^{+}, \tilde r_D^{-}, \tilde w_D)$ 满足

  $$\begin{align*} \tilde r_D^{-}(x_i) & \leq r_D^{-}(x_i) \\ \tilde r_D^{+}(x_i) & \leq r_D^{+}(x_i) \\ \tilde w_D(x_i) & \leq w_D(x_i) \end{align*}$$
  • 即初始化$Q(D)$为0-approximate summary

• merge operation：记 $Q(D1)=(S_1, \tilde r{D1}^{+}, \tilde r{D1}^{-}, \tilde w{D1})$、 $Q(D_2)=(S_2, \tilde r{D2}^{+}, \tilde r{D2}^{-}, \tilde w{D_2})$、 $D = D_1 \cup D_2$，则归并后的 $Q(D)=(S, \tilde r_D^{+}, \tilde r_D^{-}, \tilde w_D)$ 定义为

  $$\begin{align*} S & S_1 \cup S_2 \\ \tilde r_D^{-}(x_i) & = \tilde r_{D_1}^{-}(x_i) + \tilde r_{D_2}^{-}(x_i) \\ \tilde r_D^{+}(x_i) & = \tilde r_{D_1}^{+}(x_i) + \tilde r_{D_2}^{+}(x_i) \\ \tilde w_D(x_i) & = \tilde w_{D_1}(x_i) + \tilde w_{D_2}(x_i) \end{align*}$$

• prune operation：从给定 $Q(D)=(S, \tilde r_D^{+}, \tilde r_D^{-}, \tilde w_D)$， （其中$S = {x_1, \cdots, x_k }$），构建新的summary $\acute Q(D)=(\acute S, \tilde r_D^{+}, \tilde r_D^{-}, \tilde w_D)$

  • 仅定义域从$S$按如下操作抽取 $\acute S={\acute x1, \cdots, \acute x{b+1}}$

    $$\acute x_i = g(Q, \frac {i-1} b w(D))$$

  • $g(Q, d)$为查询函数，对给定quantile summary $Q$、 秩$d$返回秩最接近$d$的元素