微软xgb百科，xgb是哪年提出的

XGBoost是2014年2月诞生，由中国的陈天奇提出。XGBoost实现的是一种通用的TreeBoosting算法。xgboost即能解决分类问题，也能解决回归问题。

纵向联邦 XGB 算法在蚂蚁集团的应用

导读：随着隐私计算的需求量逐渐提升，技术发展逐渐完善，方文静（蚂蚁集团-共享智能部算法专家）在隐私计算联合建模方面的算法研究，尤其在联邦学习树模型领域取得了一些进展。她今天分享的主题是“纵向联邦 XGB 算法”，主要介绍如何在保护隐私安全下实现一个多计算节点间的联合训练，以及怎样通过性能优化将其应用到工业界大规模应用中。

今天的介绍会围绕下面四点展开：

01

问题定义

首先介绍纵向XGB算法模型的现实意义。

1. 算法背景

在业务中应用联邦学习较多的模型有线性模型和XGB树模型。

相比于线性回归和神经网络等模型，XGB树模型对数据预处理的要求更低，且对数据的拟合能力更强，调参的难度也更低，是一种优秀的算法。但在联邦学习现有的应用方案中，XGB树模型的应用主要有以下两个难点：

① 在学术界中缺少垂直XGB树模型的研究。在学术界中，学者主要关注简单模型（如决策树）、预测算法和水平联邦学习，而缺少纵向联邦学习中XGB算法的研究。

② 工业界中不可证安全。工业界中只将隐私计算技术应用在模型的一小部分中，模型整体上存在隐私漏洞，因为会暴露模型的中间信息，如“各节点样本分布”、“导数累积和”等。

XGB-梯度提升树-模型是一种回归树的加性模型，树节点包括两类：

① 中间节点。存储分裂信息，如分裂特征和分裂阈值。

② 叶子节点。存储的是权重信息。

在XGBoost中，为评估各特征作为分裂节点的分裂增益，采用如下公式计算：

2. 算法设定

安全XGB算法设定主要在输入、输出有改变。

（1）输入。纵向联邦学习中使用已经对齐的垂直切分的数据样本。

（2）输出。使用分布式XGB模型：对于单个中间节点，仅会将分裂信息存储在该分裂方；对于叶子节点，将权重使用秘密分享的方式存储在各参与方。

—

02

安全训练

首先介绍传统的安全多方计算（MPC）技术，之后将MPC技术应用于纵向联邦学习XGB的训练过程提出SS-XGB算法，最后进一步介绍两个我们改进的训练算法HEP- XGB和CRP- XGB。

1. MPC技术

MPC技术，即安全多方计算，其实现方式有多种思路。

（1）秘密分享

借助随机数进行加性的秘密分享保证数据安全，将原始的计算数据变量进行随机分片发送到不同的参与方，每个参与方持有一片。这种方式拥有比较好的计算性能，且支持的算子也比较丰富，因此我们算法中主要使用MPC技术秘密分享的形式以进行计算。

（2）同态加密

在计算过程中，一个参与方作为加密方，生成公钥和私钥，并将公钥传送给各计算方，各参与方将数据加密为密文发送到计算方，在计算方本地进行计算，并将结果发送回加密方。这种方法具有通信量小和非对称计算的优点。

2. SS-XGB训练算法

根据上一节的基础知识，首先要将变量转化为秘密分享的变量形式，从而后续的计算都需要在秘密分享的算子下进行。为了使用秘密分享的算子进行计算，我们改进了“分桶累积”、“样本划分”两种方法。

（1）分桶累积

在秘密分享计算中，特征持有方A需要将所有分桶信息同步到B方，此时若直接使用秘密分享变量进行直接求和，会暴露变量的偏序信息。为解决这个问题，引入标志向量，进行“分桶累积”。分桶累积的步骤分为三步：

① 根据分桶信息生成标志向量，即根据样本特征值是否处在分割点需要累积计算的一侧，将其值设为1或0。

② 将标志变量进行秘密分享。

③ 对标志变量和梯度向量进行内积运算。

经过“秘密分享”的操作，在B方无法复原分桶信息为0或1，这保证了训练的数据安全性。

（2）样本划分

样本分布信息也属于一种中间信息，属于原始信息的一种表征形式，因此，这种信息也需要被保护。这个问题主要通过导数置零进行解决。即将不在分裂子树上的样本进行导数归零。

3. 瓶颈分析

以上的方法存在一定的性能瓶颈：在分桶累积的过程中，在标志向量的矩阵中会包含大量零元素，这会使算法计算量大量增加。为解决这样的问题，可以通过引入不经意排列算子。具体的做法在下文详述。

—

03

训练优化

1. 不经意排列算子

通过使用不经意排列算子，将处在秘密分享下的梯度进行排序。不经意排列算子的核心为一个排列函数：

，其中，X 和 Y 均为秘密分享变量。根据排列函数的不同实现优化SS-XGB，分别得到HEP-XGB、CRP-XGB两种优化后的算法，分别在下文进行详细叙述。

2. HEP-XGB

HEP-XGB借助同态加密非对称的特性进行分桶累积的操作。在这个过程中，用到了两个转换协议：

（1）H2S

直接将同态加密的密文转变为秘密分享的变量：计算方本地生成一个随机数作为结果的随机分片，并且在原始的密文中减去随机分片，然后发送到另一方，另一方通过解密就能得到剩下的分片，即原始值的秘密分享形式。

（2）S2H

从秘密分享的状态转化为同态加密的密文：加密方将本地分片加密后发送给计算方，计算方将得到的密文与本地分片相加，得到了原始变量同态加密的密文。

基于同态加密的不经意排序分为三步：

（1）将导数值转化为同态加密的变量。

（2）对导数同态加密的密文计算分桶累积和的密文。

（3）将分桶累积的密文转回秘密分享域。

3. CRP-XGB

另一种实现不经意排序的方式为CRP-XGB。在秘密分享的状态下，为防止秘密分享变量的泄露，生成两个和排序向量相关的秘密分享向量来辅助排序过程，分别作为排序前后向量的掩码，借助随机掩码可以将原始对分片的排序问题转化为“明文”的排序，并将辅助变量的生成进行离在线拆分，使得调用TEE可信执行环境生成成对的随机掩码的过程不依赖于排序向量，从而提高算法执行效率。

在此基础上，以上HEP-XGB、CRP-XGB两种不经意排序方式都可以应用于大规模的工程应用中，相比来说，CRP-XGB更适合网络环境较好的情况，而HEP-XGB更适合网络环境较差的情况。

—

04

预测算法

1. 预测流程

在单棵树明文预测中，根据样本信息和特征信息得到一个one-hot的标志向量，并与全局的权值相乘，得到最终结果。纵向联邦XGB的预测流程：在得到分裂信息后，不同的参与方会分别产生本地的预测向量，将预测向量转换为秘密分享变量，把各方预测向量按位求积，得到合并后的预测向量，再与叶节点权值向量求内积即可得到最终预测值。

首先，从性能测试结果可以看到，联合建模相比于单独建模的结果优势比较大。而采用HEP-XGB和CRP-XGB的精度与联合建模下精度略有减少，这可能是由于秘密分享状态下采用定点数的表示方法和非线性函数近似所造成的。

接着在三种典型网络场景设定下进行了性能测试：

可以看到在网络状况较好的场景S1，CRP-XGB是一个较好选择，比HEP-XGB要快约10倍；而网络状况较弱的场景S2，HEP-XGB则表现更好，节约了26.5%的时间；场景S3由于算力和带宽的局限，两个算法耗时均较高。

最后，我们进行大规模测试，生成了1200w样本200维特征的数据集，使用2个优化模型分别训练了2棵树，并记录LAN环境下训练过程中资源消耗的情况：

两种算法均能支持到千万样本，CRP-XGB整体上CPU、内存占用较小，训练时间也较快，可见网络状况较好的时候，CRP-XGB是一个更优选择。

今天的分享就到这里，谢谢大家。

分享嘉宾：方文静 蚂蚁集团 算法专家

编辑整理：毕东海 大连理工大学

出品平台：DataFunTalk

01/分享嘉宾

方文静｜蚂蚁集团算法专家

方文静（乐彧），上海交通大学电院计算机系硕士，研究方向自然语言处理依存分析。工作方向为共享智能隐私保护机器学习算法，主要负责安全树模型方向。

02/关于我们

DataFun：专注于、人工智能技术应用的分享与交流。发起于2017年，在北京、上海、深圳、杭州等城市举办超过100 线下和100 线上沙龙、论坛及峰会，已邀请超过2000位专家和学者参与分享。其 DataFunTalk 累计生产原创文章700 ，百万 阅读，14万 精准粉丝。