<commit_before>---
layout: post
title: XGBoost解读(2)--近似分割算法
categories:
- datamining
tags:
- GBDT
- XGBoost
image:
    teaser: /datamining/xgboost_fig/xgboost_logo.png
---

# 近似分割算法
[文章](https://yxzf.github.io/2017/03/xgboost-v1/)介绍了XGBoost使用exact greedy算法来寻找分割点建树，但是当数据量非常大难以被全部加载进内存时或者分布式环境下时，exact greedy算法将不再合适。因此作者提出近似算法来寻找分割点。近似算法的大致流程见下面的算法。

![](/images/datamining/xgboost_fig/tree_split1.png)

对于某个特征$k$，算法首先根据特征分布的分位数找到切割点的候选集合$S_k =  \{s_{k1}, s_{k2}, ... ,s_{kl}\}$；然后将特征$k$的值根据集合$S_k$划分到桶(bucket)中，接着对每个桶内的样本统计值$G$、$H$进行累加统计，最后在这些累计的统计量上寻找最佳分裂点。从算法伪代码可以看出近似算法的核心是如何**根据分位数采样得到分割点的候选集合$S$**.  本文接下来的内容也是围绕这个进行阐述。 

# Quantile
## $\phi$-quantile
[Quantile](http://www.mathcs.emory.edu/~cheung/Courses/584-StreamDB/Syllabus/08-Quantile/Greenwald.html)就是ranking。如果有N个元素，那么$\phi$-quantile就是指rank在$\lfloor \phi \times N \rfloor$的元素。例如$S=[11, 21, 24, 61, 81, 39, 89, 56, 12, 51]$，首先排序为$[11, 12,  21,  24,  39,  51,  56,  61,  81,  89]$，则0.1-quantile=11, 0.5-quantile=39. 上面的是exact quantile寻找方法，如果数据集非常大，难以排序，则需要引入$\epsilon$-approximate $\phi$-quantiles

## $\epsilon$-approximate $\phi$-quantiles
也就是$\phi$-quantile是在区间$[ \lfloor (\phi - \epsilon) \times N \rfloor, \lfloor (\phi + \epsilon) \times N \rfloor]$。还是上面的例子，领$\epsilon=0.1$，则有0.2-quantile={11, 12, 21}

# Weighted  Datasets
回到XGBoost的建树过程，在建立第$i$棵树的时候已经知道数据集在前面$i-1$棵树的误差，因此采样的时候是需要考虑误差，对于误差大的特征值采样粒度要加大，误差小的特征值采样粒度可以减小，也就是说采样的样本是需要权重的。

重新审视目标函数$\sum_{i=1}^n [g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t)$，通过配方可以得到
$$
\sum_{1}^n \left[ {1 over 2} h_i \left( f_t(x_i) - (-g_i/h_i)\right)^2 \right] + \Omega (f_t) + constant
$$
因此可以将该目标还是看作是关于标签为${-{g_i}/{h_i}}$和权重为$h_i$的平方误差形式。
> 论文中$\frac{g_i}{h_i}$前面没有负号，可是通过推导我认为这种形式才是对的。当然这边的符号不影响论文中其他表达的正确性

## 二阶导数h为权重的解释
如果损失函数是Square loss，即$Loss(y, \widehat y) = (y - \widehat y)^2$，则$h=2$，那么实际上是不带权。
如果损失函数是Log loss，则$h=pred* (1 - pred)$. 这是个开口朝下的一元二次函数，所以最大值在0.5。当pred在0.5附近，这个值是非常不稳定的，很容易误判，h作为权重则因此变大，那么直方图划分，这部分就会被切分的更细

![](/images/datamining/xgboost_fig/weighted.png)

## 问题转换
记${D_k} = \left\{ {\left( {{x_{1k}},{h_1}} \right),\left( {{x_{2k}},{h_2}} \right) \cdots \left( {{x_{nk}},{h_n}} \right)} \right\}$表示 每个训练样本的第$k$维特征值和对应二阶导数。接下来定义排序函数为$r_k(\cdot):R \rightarrow[0, +\infty)$
$$r_k(z) = \frac {1} {\sum\limits_{\left( {x,h} \right) \in {D_k}} h } \sum\limits_{\left( {x,h} \right) \in {D_k},x < z} h $$
函数表示特征的值小于$z$的样本分布占比，其中二阶导数$h$可以视为权重，后面论述。在这个排序函数下，我们找到一组点$\{s_{k1}, s_{k2}, ... ,s_{kl}\}$ ,满足：
$$\left| r_k \left( s_{k,j} \right) - {r_k}\left( {{s_{k,j + 1}}} \right) \right| < \varepsilon$$
其中，${s_{k1}} = \mathop {\min }\limits_i {x_{ik}},{s_{kl}} = \mathop {\max }\limits_i {x_{ik}}$。$\varepsilon$为采样率，直观上理解，我们最后会得到$1/\varepsilon$个分界点。<commit_msg>xgboost v2<commit_after>---
layout: post
title: XGBoost解读(2)--近似分割算法
categories:
- datamining
tags:
- GBDT
- XGBoost
image:
    teaser: /datamining/xgboost_fig/xgboost_logo.png
---

# 近似分割算法
[文章](https://yxzf.github.io/2017/03/xgboost-v1/)介绍了XGBoost使用exact greedy算法来寻找分割点建树，但是当数据量非常大难以被全部加载进内存时或者分布式环境下时，exact greedy算法将不再合适。因此作者提出近似算法来寻找分割点。近似算法的大致流程见下面的算法。

![](/images/datamining/xgboost_fig/tree_split1.png)

对于某个特征$k$，算法首先根据特征分布的分位数找到切割点的候选集合$S_k =  \{s_{k1}, s_{k2}, ... ,s_{kl}\}$；然后将特征$k$的值根据集合$S_k$划分到桶(bucket)中，接着对每个桶内的样本统计值$G$、$H$进行累加统计，最后在这些累计的统计量上寻找最佳分裂点。从算法伪代码可以看出近似算法的核心是如何**根据分位数采样得到分割点的候选集合$S$**.  本文接下来的内容也是围绕这个进行阐述。 

# Quantile
## $\phi$-quantile
[Quantile](http://www.mathcs.emory.edu/~cheung/Courses/584-StreamDB/Syllabus/08-Quantile/Greenwald.html)就是ranking。如果有N个元素，那么$\phi$-quantile就是指rank在$\lfloor \phi \times N \rfloor$的元素。例如$S=[11, 21, 24, 61, 81, 39, 89, 56, 12, 51]$，首先排序为$[11, 12,  21,  24,  39,  51,  56,  61,  81,  89]$，则0.1-quantile=11, 0.5-quantile=39. 上面的是exact quantile寻找方法，如果数据集非常大，难以排序，则需要引入$\epsilon$-approximate $\phi$-quantiles

## $\epsilon$-approximate $\phi$-quantiles
也就是$\phi$-quantile是在区间$[ \lfloor (\phi - \epsilon) \times N \rfloor, \lfloor (\phi + \epsilon) \times N \rfloor]$。还是上面的例子，领$\epsilon=0.1$，则有0.2-quantile={11, 12, 21}

# Weighted  Datasets
回到XGBoost的建树过程，在建立第$i$棵树的时候已经知道数据集在前面$i-1$棵树的误差，因此采样的时候是需要考虑误差，对于误差大的特征值采样粒度要加大，误差小的特征值采样粒度可以减小，也就是说采样的样本是需要权重的。

重新审视目标函数
$$
\begin{equation}
\sum_{i=1}^n [g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t)
\end{equation}
$$, 通过配方可以得到
$$
\begin{equation}
\sum_{1}^n \left[ \frac {1}{2}  h_i \left( f_t(x_i) - (-g_i/h_i)\right)^2 \right] + \Omega (f_t) + constant
\end{equation}
$$
因此可以将该目标还是看作是关于标签为${-{g_i}/{h_i}}$和权重为$h_i$的平方误差形式。
> 论文中$\frac{g_i}{h_i}$前面没有负号，可是通过推导我认为这种形式才是对的。当然这边的符号不影响论文中其他表达的正确性

## 二阶导数h为权重的解释
如果损失函数是Square loss，即$Loss(y, \widehat y) = (y - \widehat y)^2$，则$h=2$，那么实际上是不带权。
如果损失函数是Log loss，则$h=pred* (1 - pred)$. 这是个开口朝下的一元二次函数，所以最大值在0.5。当pred在0.5附近，这个值是非常不稳定的，很容易误判，h作为权重则因此变大，那么直方图划分，这部分就会被切分的更细

![](/images/datamining/xgboost_fig/weighted.png)

## 问题转换
记$${D_k} = \left\{ {\left( {{x_{1k}},{h_1}} \right),\left( {{x_{2k}},{h_2}} \right) \cdots \left( {{x_{nk}},{h_n}} \right)} \right\}$$表示 每个训练样本的第$k$维特征值和对应二阶导数。接下来定义排序函数为$r_k(\cdot):R \rightarrow[0, +\infty)$
$$r_k(z) = \frac {1} {\sum\limits_{\left( {x,h} \right) \in {D_k}} h } \sum\limits_{\left( {x,h} \right) \in {D_k},x < z} h $$
函数表示特征的值小于$z$的样本分布占比，其中二阶导数$h$可以视为权重，后面论述。在这个排序函数下，我们找到一组点$\{s_{k1}, s_{k2}, ... ,s_{kl}\}$ ,满足：
$$\left| r_k \left( s_{k,j} \right) - {r_k}\left( {{s_{k,j + 1}}} \right) \right| < \varepsilon$$
其中，${s_{k1}} = \mathop {\min }\limits_i {x_{ik}},{s_{kl}} = \mathop {\max }\limits_i {x_{ik}}$。$\varepsilon$为采样率，直观上理解，我们最后会得到$1/\varepsilon$个分界点。
{'fraction_non_alphanumeric': 0.22142857142857142, 'fraction_numerical': 0.03717948717948718, 'mean_word_length': 5.903919089759798, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 5, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '120884', 'n_tokens_mistral': 3567, 'n_tokens_neox': 3745, 'n_words': 333}