4.3.3　所提算法详述

京东科技对SecureBoost算法架构进行了改造，提出一种新的纵向联邦梯度提升树模型（FederatedGBoost）。其训练和推理结构包含两种角色：一种是拥有特征或标签数据的客户端（Client），另一种是负责协调和数据转发的服务器端（Server）。各个客户端之间不进行直接通信，通过服务器端的通信和调度完成训练和推理过程。所有客户端都可以作为联邦学习建模的发起方。具体的服务器端（协调端）与客户端架构设计可参见第14章。

1. 加密梯度共享

与XGBoost算法一致，联邦梯度提升树的特征预排序和特征分箱计算都在客户端本地进行。但是，只有一个客户端拥有标签数据，而所有客户端都需要梯度值才能计算候选的分裂增益，因此需要一套安全的梯度共享机制来为没有标签数据的客户端完成这一目的。

我们将拥有标签的客户端称为主动方。为了保证数据安全，纵向联邦梯度提升树使用了同态加密，具体步骤如下。

1）主动方客户端j生成一对同态加密密钥（pk，sk），将公钥pk发送给服务器端，而客户端j掌握公钥/私钥对。在每轮梯度更新时，客户端j用公钥加密本地梯度值并发给服务器端。

2）服务器端将加密后的梯度值和公钥pk转发给其他客户端。

3）没有标签数据的客户端，根据特征分箱结果，对加密的梯度值进行分箱累计加和，这一过程使用同态加法计算。而且联邦梯度提升树中不涉及密文乘法计算，因此只需要半同态算法。客户端将分箱梯度值密文之和发送回服务器端。

4）主动方客户端j收到服务器端转发的分箱梯度密文和后，使用sk解密，并按照XGBoost算法的分裂增益公式（4.4）计算分裂增益。至此，主动方客户端j获得了全局所有特征及阈值候选的分裂增益，选出最佳分裂后，通知服务器端告知该分裂特征所属的客户端。

2. 模型存储和推理

与分布式XGBoost类似，纵向联邦梯度提升树的树结构和树节点分裂信息分开存储在不同平台上。各个树节点的分裂特征和阈值仅存储在该特征所属的客户端上，而拥有标签数据的客户端记录整个树结构，并维护一个记录节点分裂信息所在客户端的查询表queryTable。在上文最后一个步骤中，客户端j将当前的树节点标记为序号recordID，并在查询表queryTable中记录该序号所对应的客户端。叶节点存储在客户端j上，从而避免其他客户端通过叶节点的权重逆向推理出原始数据的标签值。

因此，最终每个客户端都拥有了模型的一部分子结构，这些子结构的合集构成完整的联邦梯度提升树模型。推理须由任意一个客户端发起，通过服务器端问询客户端j，从而知道下一步向哪个客户端查询样本在树中的走向。当推理完成时，客户端j为每个推理样本计算到达的叶子权重和，并将得到的推理结果返回给发起推理的一方。