1. 近似分割算法

XGBoost解读(1)–原理中介绍了XGBoost使用exact greedy算法来寻找分割点建树，但是当数据量非常大难以被全部加载进内存时或者分布式环境下时，exact greedy算法将不再合适。因此作者提出近似算法来寻找分割点。近似算法的大致流程见下面的算法。

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

2. Quantile

2.1 ϕ-quantile

Quantile就是ranking。如果有N个元素，那么ϕ-quantile就是指rank在⌊ϕ×N⌋的元素。例如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寻找方法，如果数据集非常大，难以排序，则需要引入ϵ-approximate ϕ-quantiles

2.2 ϵ-approximate ϕ-quantiles

也就是ϕ-quantile是在区间[⌊(ϕ−ϵ)×N⌋,⌊(ϕ+ϵ)×N⌋]。还是上面的例子，领ϵ=0.1，则有0.2-quantile={11, 12, 21}

3. Weighted Datasets

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

重新审视目标函数

n∑i=1[gift(xi)+12hif2t(xi)]+Ω(ft)

通过配方可以得到

n∑1[12hi(ft(xi)−(−gi/hi))2]+Ω(ft)+constant

因此可以将该目标还是看作是关于标签为−gi/hi和权重为hi的平方误差形式。

论文中gihi前面没有负号，可是通过推导我认为这种形式才是对的。当然这边的符号不影响论文中其他表达的正确性

3.1 二阶导数h为权重的解释

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

3.2 问题转换

Dk={(x1k,h1),(x2k,h2),⋯(xnk,hn)}

表示 每个训练样本的第k维特征值和对应二阶导数。接下来定义排序函数为rk(⋅):R→[0,+∞)

rk(z)=1∑(x,h)∈Dkh∑(x,h)∈Dk,x<zh

函数表示特征的值小于z的样本分布占比，其中二阶导数h可以视为权重，后面论述。在这个排序函数下，我们找到一组点{sk1,sk2,...,skl} ,满足：

|rk(sk,j)−rk(sk,j+1)|<ε

其中，sk1=minixik,skl=maxixik。ε为采样率，直观上理解，我们最后会得到1/ε个分界点。

对于每个样本都有相同权重的问题，有quantile sketch算法解决该问题，作者提出Weighted Quantile Sketch算法解决这种weighted datasets的情况。具体算法描述和推理在论文的补充材料。

4. Weighted Quantile Sketch

4.1 Formalization

给定一个multi-set D={(x1,w1),(x2,w2),⋯(xn,wn)}, wi∈[0,+∞],xi∈X. 如果数据集D是根据X上的升序进行排列，作者定义了两个rank function

r−D=∑(x,w)∈D,x<ywr+D=∑(x,w)∈D,x≤yw

注意到D是个multi-set，因此会有一些数据具有相同的x和w，作者还定义了weight function

wD(y)=r+D(y)−r−D(y)=∑(x,w)∈D,x=yw

样本集合D上的全部权重定义为w(D)=∑(x,w)∈Dw

4.2 Quantile Summary of Weighted Data

根据上面定义的概念和符号引出Quantile Summary of Weighted Data的定义 数据集D上的quantile summary被定义为Q(D)=(S,˜r+D,˜r−D,˜wD), 其中集合S={x1,x2,...,xk}从D中选出(xi∈x|(xw)∈D). S中的元素需要满足下面的性质:

1. xi<xi+1 对所有的i成立。并且x1和xk分别是D中的最小和最大点:

x1=min(x,w)∈Dxxk=max(x,w)∈Dx

1. 函数˜r+D,˜r−D,˜wD 是定义在集合S上的函数，并且满足

˜r−D(xi)≤r−D(xi)˜r+D(xi)≤r+D(xi)˜wD(xi)≤wD(xi)˜r−D(xi)+˜wS(xi)≤˜r−D(xi+1)˜r+D(xi)≤˜r+D(xi+1)−˜wD(xi+1)

4.3 ε-Approximate Qunatile Summary

给定的quantile summary Q(D)=(S,˜r+D,˜r−D,˜wD), Q(D)被称为ε-Approximate Qunatile summay，当且仅当 ˜r+D(y)−˜r−D(y)−˜wD(y)≤εw(S) 对于任意一个y∈X成立. 意思也就是说我们对r+y、r−y的估计的最大error至多为εw(D).

4.4 构建ε-Approximate Qunatile Summary

4.4.1 初始化

在小规模数据集D={(x1,w1),(x2,w2),⋯(xn,wn)} 上构建初始的quantile summary Q(D)=(S,˜r+D,˜r−D,˜wD)，集合S满足：S={x|(x,w)∈D}. ˜r+D,˜r−D,˜wD被定义为

˜r−D(x)=r−D(x)˜r+D(x)=r+D(x)˜wD(x)=wD(x)

可以看出，初始的Q(D)是0-approximate summary.

4.4.2 Merge Operation

Q(D1)=(S1,˜r+D1,˜r−D1,˜wD1)和Q(D2)=(S1,˜r+D2,˜r−D2,˜wD2)分别定义在数据集D1和D2上，令D={D1∪D2}，那么merged summary Q(D)=(S,˜r+D,˜r−D,˜wD)被定义为：

S={(x1,x2,...,xk)},xi∈S1orsi∈S2˜r−D(xi)=˜r−D1(xi)+˜r−D2(xi)˜r+D(xi)=˜r+D1(xi)+˜r+D2(xi)˜wD(xi)=˜wD1(xi)+˜wD2(xi)

4.4.3 Prune Operation

给定Q(D)=(S,˜r+D,˜r−D,˜wD) (其中S={x1,x2,...,xk})和memory budget b，prune operation构建一个新的summary, ˊQ(D)=(ˊS,˜r+D,˜r−D,˜wD). ˊD中的˜r+D,˜r−D,˜wD定义与原先的summary Q一致，只是定义域从S变为ˊS, ˊS={´x1,´x2,...,´xb+1}, ´xi的选择按照下面的操作获取：

´xi=g(Q,i−1bw(D))

g(Q,d)是query function，对于给定的quantile summary Q和rank d, g(Q,d)返回一个元素x，x的rank最接近d，具体定义为

1. http://www.kdd.org/kdd2016/papers/files/rfp0697-chenAemb.pdf
2. http://homes.cs.washington.edu/~tqchen/pdf/xgboost-supp.pdf
3. http://datascience.stackexchange.com/questions/10997/need-help-understanding-xgboosts-approximate-split-points-proposal

---