Xgboost论文笔记原理篇(下)

网上关于陈天奇的Xgboost论文的weighted quantile sketch算法的数学推导及主要思想都说的挺笼统的，看来大家都是不愿意死磕论文啊，哈哈，开个玩笑的。您能阅读这篇文章，就说明您有很强的好奇心和进取心，加油！不贫了，上干货！

weighted quantile sketch的主要目标，至少在Xgboost这一具体情形下，就是寻找候选分裂点集合，是为节点分裂的近似算法服务的。具体如下：
图片说明

首先给出与quantile summary有关的定义：

weighted quantile sketch的核心思想，如有些博主所言，就是用子集代替全集。如下面的定义所言

下面的定义是关键，它对weighted quantile sketch的精度给予了理论上的保证

总结：个人理解，在不与GK summary框架融合的前提下，通过对quantile summary的剪枝操作，能得到候选分裂节点，且剪枝前后的误差分别为 $\epsilon$ 变到 $\epsilon+1/b$ . 要保证剪枝后的误差不至于太大，可以看出 $b$ 不能太小，也就是剪枝后保留的数据不能太少，这似乎也验证了节点分裂的近似算法的global版本，需要的数据比local版本要多。