3.2　极端梯度提升树的联邦学习实现方式

上述传统机器学习算法为单个弱学习器的训练，本节所涉及的极端梯度提升树属于集成学习。集成学习方法把多个效果较弱的学习器按一定的方式结合，从而形成一个效果强的学习器。相较于单个学习器，集成学习的表征能力和泛化能力可以获得明显的提升。一般而言，将不相同的弱学习器结合在一起，集成学习的效果会有更好的提升。

较为著名的获得广泛认同的集成学习模型［包括以决策树为基学习器的随机森林（Random Forest，RF） ^[47] 、梯度提升决策树（Gradient Boost Decision Tree，GBDT） ^[48] 和极端梯度提升树（eXtreme Gradient Boosting，XGBoost） ^[49] 等］，在网络入侵检测、客户关系管理、教育数据挖掘和音乐推荐等多个学习任务中均表现出强大的能力，其中XGBoost更凭借其计算高效、预测准确等特点获得了高度的关注和广泛的应用。

谷歌于2016年发表了首次提出联邦学习概念的相关论文，文章论述了重叠样本特征多、重叠用户少的横向联邦场景。在跨机构数据联合应用的实践中，纵向联邦，即重叠用户多、重叠样本特征少的情况，也是非常典型的场景，有着广泛的应用需求。以提供金融信贷服务的银行为例，如果银行能与电信运营商合作并使用其数据，那么银行风控模型的预测能力将会显著提升。将集成树类的算法推广到联邦学习场景，在保护数据隐私的前提下，Cheng等提出了将XGBoost纵向联邦化时无损的计算框架，即SecureBoost ^[50] 。

本节首先回顾XGBoost的算法特点，而后从数据对齐、模型构建、结果预测和效果评估等几个方面全面介绍SecureBoost。

3.2.1　XGBoost算法介绍

XGBoost是一种以梯度提升决策树为基础的算法，已经被广泛地应用到多种场景中，被用于处理分类、回归、排序等多种类型的任务，并能在分布式环境中部署使用。XGBoost的显著优点包括以下几个。

（1）对叶子节点的设置加入惩罚，相当于添加了正则化项，防止过拟合。

（2）支持列采样，在构建每棵树时对属性进行采样，训练速度快，效果好。

（3）支持稀疏数据，对于特征有缺失的样本特殊处理，仍可以通过学习得出分裂的方向。

（4）使用可并行的近似频数统计分布算法，在节点分裂时，经过预排序的数据按列存放，在特征维度进行并行计算，即可以同时遍历各个属性，寻找最优分裂点。

（5）每经过一轮迭代，叶子节点上的权重都会乘以某系数，该系数被称为缩减系数，用于削弱每棵树的作用，使之后的训练有更大的提升空间。

XGBoost算法求解的优化问题的目标函数如式（3-2-1）所示。

式中， 为样本数量； 为决策树数量； 为真实值 与预测值 分布差异对应的损失函数； 为正则化项； 为第 棵树。

模型的复杂度由正则化项控制，见式（3-2-2）。正则化项包括叶子节点数 和叶子节点得分 ， 与 为正则化系数。

我们对目标函数中的损失函数做二阶泰勒展开，并使用叶子节点分裂前后的增益作为分裂准则，从而推导出增益的数学形式，如式（3-2-3）所示。

式中， 和 分别为叶子节点切分后左、右节点的得分； 为切分前的得分； 、 、 、 分别为左节点损失函数的一阶导数、右节点损失函数的一阶导数、左节点损失函数的二阶导数和右节点损失函数的二阶导数，具体的数学形式如式（3-2-4）所示。

通过贪心算法来最大化目标函数，即最大化节点分裂前后的增益，其对应的特征和切分点则为最优特征和最优分裂点。与基于信息熵和基尼系数计算增益的ID3算法和CART算法相比，XGBoost算法使用了损失函数的一阶和二阶导数信息来计算分裂增益，可以改进基学习器的能力，同时对树型结构做预剪枝来避免过拟合，即当节点分裂带来的增益超过自定义的阈值 时，叶子节点才进行分裂。此外，式（3-2-3）中的 是正则化项中叶子节点得分的系数，在对叶子节点得分做平滑处理的同时，也起到防止过拟合的作用。

3.2.2　SecureBoost算法介绍

SecureBoost算法要解决的问题，是将多个数据提供方和具备标签的需求发起方联合起来，在保证数据不出域的前提下共同训练模型。同时，与将数据合并在一起训练时相比，还须保证联合训练的模型具备性能无损的特点。在此过程中，SecureBoost算法将涉及数据对齐、构造Boost树、模型预测和模型性能评估四个方面。

1.数据对齐

联邦学习的第一步是数据对齐，其难点在于如何让隐私信息在数据对齐的过程中不被暴露。在纵向联邦学习场景中，SecureBoost算法使用了文献[51]中的方法，实现数据参与方在不知道其他方与己方的差集数据的情况下得到交集，从而实现了隐私保护下的数据对齐，相关的计算请参考2.2节。

2.构造Boost树

构造Boost树是在联邦学习的模式下按XGBoost算法的思路进行树模型的构建。SecureBoost算法的关键是在保护数据隐私的前提下，利用全部信息构建Boost树，这就需要在数据对齐之后，加密传递训练涉及的中间值，即损失函数的一阶导数 和二阶导数 。而在寻找最优分裂特征和分裂点时，算法需要对叶子节点上样本的 和 进行求和操作，这仅需要加密之后的导数信息依然保持可加性即可。所以，SecureBoost算法采用Paillier半同态加密算法，加密需要跨数据方传递的导数信息，并进行相应计算进而实现特征分裂 ^[17] ，从而保证了联邦的SecureBoost与XGBoost算法无异。SecureBoost算法的叶子节点分裂过程如图3-2-1所示，对应的步骤如下。

（1）Guest方基于当前节点分别计算一阶和二阶导数的和，并将所得的结果加密与当前ID集合一同传递到各个Host方。

（2）Host方遍历所有变量，基于变量的分箱结果计算统计直方图，并将不同分裂点加密后的一阶梯度 和二阶梯度 的求和值随后回传给Guest方。

（3）Guest方解密求和值，并基于当前节点的一阶导数和二阶导数的和，计算每个Host方各个特征的不同分裂点的信息增益。

（4）Guest方继续计算自身各个特征在不同分裂点的信息增益，并与Host方的相应值进行比较，选出最优分裂点，且将最优信息增益结果传给所有Host方。

需要强调的是，根节点的分裂只有Guest方可以参与，原因在于防止Host方反向推断标签信息。即便Host方有足够的能力，也只能拿到第一个子树的结果。此外，Guest方知晓各个节点归属于哪一方进行切割，但也仅限于此，Guest方并不知道切割所使用的特征及其分裂点。

3.模型预测

SecureBoost算法的预测需要Guest方与Host方交互才能完成，各方只拥有和维护属于自己的树节点，而对其他方掌握的节点信息不可见。与其他常见的树模型一样，SecureBoost算法左边的叶子节点值永远小于右边的叶子节点值。

以证券机构信用风险高低的二分类预测为例，介绍SecureBoost算法构建树的过程中叶子节点如何进行分裂。其中，Guest方、Host 1方和Host 2方存在交集用户 ，Guest方具有因变量信用风险、自变量机构类型和公司规模；Host 1方提供自变量注册资本；Host 2方提供自变量注册地和经营年限，变量解释见表3-2-1。

下面基于 训练数据，利用SecureBoost算法构建的模型进行预测。假设树结构是图3-2-2中左下方形式。根节点使用的特征是Guest方的公司规模变量，节点分裂的阈值等于45 000，其含义为当测试数据的公司规模小于45 000人时，样本数据会进入左边的叶子节点，反之进入右半支，其他节点以此类推，直至待预测样本数据进入某个叶子节点，然后利用训练集在该叶子节点样本标签取值的分布，选取数量占比最高的标签，作为待预测样本数据的预测标签。对于这个例子中的树结构，真正影响信用风险的自变量只有公司规模、注册资本和经营年限。以待预测样本数据为例（公司规模为23 632 人，注册资本为3128万元，经营年限为7年），该数据被预测的过程如下。

（1）在根节点依据Guest方的“公司规模”进行分流。

（2）样本数据进入左半支后，Host 1方会根据该节点的“注册资本”继续分流该数据。

（3）Host 2方参照“经营年限”的阈值将数据分流至右半支。

（4）直至到达叶子节点停止，此时该节点对应的标签值为0，所以数据的预测结果也为0。

4.模型性能评估

SecureBoost算法的性能主要通过误差收敛速度、单棵树的深度、数据样本量和特征量四项指标来反映。对于误差收敛速度而言，SecureBoost ^[50] 算法与非联邦的XGBoost算法和GBDT算法，在同一训练数据样本下，随着迭代步数的增加，三者的损失函数的收敛程度几乎一样，如图3-2-3所示。这说明了SecureBoost算法的加密/解密过程并没有损害模型的性能。

进一步增加单棵树的深度，观察SecureBoost算法的计算时间。如图3-2-4（a）所示，SecureBoost算法的计算时间与单棵树的最大深度呈线性关系。这种线性关系对SecureBoost算法的大规模运用具有重要价值，既能针对自身业务需求设置树的最大深度阈值，也能根据该线性关系预测增加树深对应的计算时间。SecureBoost算法的计算时间随特征数量和数据量的变化如图3-2-4（b）和（c）所示。根据变化曲线可以看出，当数据量为30 000个时，随着特征数量增加并超过1000个，计算时间大幅增加；而当特征数量为5000个时，且随着数据量增加并超过10 000个，计算时间也大幅增加。这能帮助我们平衡特征数量和数据量，进而对特征数量做取舍，以保证能高效地训练模型。

SecureBoost算法是联邦学习场景下，XGBoost算法的一种实现方式。该算法填补了联邦学习在集成学习领域的空缺。SecureBoost算法的本质仍是树模型，它不仅可以处理分类场景，还可以解决回归问题。树模型在应用中的优异模型效果表现和训练部署的便利性也让SecureBoost算法成为众多联邦学习算法中备受关注的对象之一。 WQvChjWd37C3T5uSEzofRZd+UdETkVW2fN5giWXOr2BQ4IUW1DoOVxPk6TZrhj+I