SecureBoost：一种无损的联邦学习框架

摘要——用户隐私保护是机器学习中的一个重要问题，欧洲联盟于2018年5月推出的《通用数据保护条例》（GDPR）便是一个证明。GDPR旨在让用户对其个人数据有更多的控制权，这促使我们探索在不违反用户隐私的前提下进行数据共享的机器学习框架。为此，本文提出了一种在联邦学习环境下的全新无损隐私保护树提升系统SecureBoost。SecureBoost首先在隐私保护协议下进行实体对齐，然后通过精心设计的加密策略在多个参与方之间构建提升树。该联邦学习系统允许在具有共同用户样本但特征集不同的多个参与方之间共同进行学习过程，这对应于一个纵向分区的数据集。SecureBoost的一个优势是，它在提供与非隐私保护方法相同准确度的同时，不透露任何私有数据提供者的信息。我们证明了SecureBoost框架与需要集中数据的非联邦梯度树提升算法一样准确，因此它在诸如信用风险分析等工业应用中高度可扩展和实用。为此，我们讨论了协议执行过程中的信息泄露并提出了减少信息泄露的方法。

论文地址：https://arxiv.org/abs/1901.08755

关键词：联邦学习，隐私，安全，决策树

1 引言

现代社会越来越关注个人数据的非法使用和剥削。在个人层面，个人数据的不当使用可能会对用户隐私造成潜在风险。在企业层面，数据泄露可能对商业利益产生严重影响。不同社会正在采取行动，例如，欧洲联盟已经颁布了一项名为《通用数据保护条例》（GDPR）的法律。GDPR旨在赋予用户对其个人数据更多的控制权【1】【2】【3】【4】。许多依赖机器学习的企业因此开始进行大规模变革。

尽管实现用户隐私保护的目标困难重重，不同组织在构建机器学习模型时的协作需求依然强烈。实际上，许多数据拥有者没有足够的数据来构建高质量的模型。例如，零售公司拥有用户的购买和交易数据，如果提供给银行用于信用评级应用将会非常有用。同样，移动电话公司拥有用户的使用数据，但每家公司可能只有少量用户数据，无法训练高质量的用户偏好模型。这些公司有强烈的动机来共同利用数据的联合价值。

到目前为止，让不同的数据拥有者在保护用户数据隐私和机密性的同时共同构建高质量的机器学习模型仍然是一项挑战。过去，已经有一些尝试来解决机器学习中的用户隐私问题【5】【6】。例如，Apple提出使用差分隐私（DP）【7】【8】来解决隐私保护问题。DP的基本思想是在数据交换和分析过程中添加适当校准的噪声，以消除任何个体身份的歧义。然而，DP只能在一定程度上防止用户数据泄露，无法完全排除个体身份。此外，在DP下的数据交换仍然需要在组织之间交换数据，这可能不符合像GDPR这样严格的法律。此外，DP方法在机器学习中是有损的，注入噪声后构建的模型在预测准确性方面可能表现不佳。

最近，Google引入了一个联邦学习（FL）框架【9】，并将其部署在Android云上。其基本思想是允许个人客户端只上传模型更新，而不是原始数据到中央服务器，在中央服务器上聚合模型。为了确保模型参数不泄露用户信息到服务器，进一步引入了安全聚合协议【10】。该框架也被称为水平联邦学习【11】或数据分区联邦学习，其中每个分区对应于从一个或多个用户收集的数据样本子集。

本文中，我们考虑了另一个场景，即多个参与方在保护用户隐私和数据机密性的同时共同构建其机器学习模型。我们的场景如图2所示，通常被称为垂直联邦学习【11】，因为数据在不同参与方之间按特征进行分区。该场景具有广泛的现实应用。例如，金融机构可以利用第三方的替代数据来增强用户和中小企业的信用评级【12】。来自多家医院的专利记录可以一起用于诊断【13】【14】。我们可以将不同参与方的数据视为通过联合所有数据获得的虚拟大数据表的一个子集。

然后，每个参与方的数据具有以下属性：

1. 大数据表按特征维度在各参与方之间进行垂直拆分；
2. 只有一个数据提供者拥有标签信息；
3. 各参与方共享一组共同的用户。

我们的目标是允许各参与方在保护所有参与方的数据不泄露给其他参与方的情况下共同构建预测模型。与大多数现有的隐私保护数据挖掘和机器学习工作相比，我们的设置显著增加了复杂性。与样本分区/水平联邦学习不同，垂直联邦学习设置需要更复杂的机制来分解每个参与方的损失函数【5】【15】【16】。此外，由于只有一个数据提供者拥有标签信息，我们需要提出一个安全协议来指导学习过程，而不是在所有参与方之间显式共享标签信息。最后，数据保密性和隐私问题阻止了各参与方暴露其自身用户。因此，实体对齐也应在足够安全的情况下进行。

Tree boosting 是一种高度有效且广泛使用的机器学习方法，在许多机器学习任务中表现出色，因为它具有高效性和强解释性。例如，XGBoost【17】在包括信用风险分析和用户行为研究在内的各种应用中被广泛使用。本文提出了一种新的端到端隐私保护树提升算法和框架，称为SecureBoost，以实现联邦学习环境下的机器学习。SecureBoost已在一个开源的联邦学习项目FATE中实现，用于工业应用。我们的联邦学习框架分两步运行。首先，我们在隐私保护约束下找到各参与方之间的共同用户。然后，我们在不泄露任何用户信息的情况下共同学习一个共享的分类或回归模型。我们的主要贡献总结如下：

• 我们正式定义了联邦学习环境下垂直分区数据的隐私保护机器学习这一新问题。
• 我们提出了一种方法，在多个参与方的本地数据上共同训练高质量的树提升模型。我们的协议不需要可信第三方的参与。
• 最后且最重要的是，我们证明了我们的方法是无损的，意味着它与在集中数据上构建的非隐私保护方法一样准确。
• 此外，除了提供安全性证明外，我们还讨论了使协议完全安全所需的条件。

好的，以下是“预备知识与相关工作”部分的翻译：

2 预备知识与相关工作

为了保护用于模型学习的数据的隐私，文献【18】提出利用差分隐私（DP）来学习深度学习模型。最近，Google引入了一个联邦学习框架，通过将模型训练带到每个移动终端来防止数据传输【9】【10】【19】。其基本思想是每个本地移动终端使用本地数据和相同的模型架构训练本地模型。全局模型可以通过平均所有本地模型来简单更新。遵循相同的思路，几种尝试已经在不同的机器学习模型上进行重新发明以适应联邦环境，包括决策树【20】【21】、线性/逻辑回归【22】【23】【24】和神经网络【25】【26】。

上述所有方法均适用于水平分区的数据。与样本分区/水平联邦学习不同，垂直联邦学习设置需要更复杂的机制来分解每个参与方的损失函数。垂直联邦学习的概念最早在文献【5】【11】中提出，并为线性模型【5】【13】和神经网络【27】提出了协议。一些先前的工作已经为垂直分区数据上的隐私保护决策树提出了方法【16】【28】。然而，它们的方法必须揭示给定属性上的类别分布，这会带来潜在的安全风险。此外，这些方法只能处理离散数据，这在现实生活中不太实用。相比之下，我们的方法保证了对数据的更好保护，并且可以轻松应用于连续数据。文献【29】提出的另一项工作通过对非线性逻辑损失进行泰勒展开，联合执行加密垂直分区数据上的逻辑回归，但这不可避免地会损害模型的性能。与这些工作相比，我们提出了一种本质上无损的新方法。

3 问题描述

设 $\{X_k\in {\mathbb{R}}^{n_k\times d_k}{\}}_{k=1}^m$ 为分布在 $m$ 个私有参与方上的数据矩阵，其中每行 $X_{k,i\ast }\in {\mathbb{R}}^{1\times d_k}$ 是一个数据实例。我们用 $F_k=\{f_1,...,f_{d_k}\}$ 表示对应数据矩阵 $X_k$ 的特征集。两个参与方 $p$ 和 $q$ 具有不同的特征集，表示为 $F_p\cap F_q=\mathrm{\varnothing }$，其中 $\mathrm{\forall }p\ne q\in \{1...m\}$。不同的参与方可能拥有不同的用户集，允许某种程度的重叠。只有一个参与方持有类别标签 $y$。

定义 1. 活跃方：

我们定义持有数据矩阵和类别标签的数据提供者为活跃方。由于类别标签信息对监督学习是必不可少的，活跃方自然承担了联邦学习中主导服务器的责任。

定义 2. 被动方：

我们定义仅持有数据矩阵的数据提供者为被动方。被动方在联邦学习设置中扮演客户端的角色。

隐私保护机器学习在联邦学习中垂直拆分数据的问题可以表述为：

已知：分布在 $m$ 个私有参与方上的垂直分区数据矩阵 $\{X_k{\}}_{k=1}^m$ 和分布在活跃方的类别标签 $y$。

学习：一个机器学习模型 $M$，在此过程中不向其他参与方透露任何方的数据矩阵信息。模型 $M$ 是一个函数，每个参与方 $i$ 有一个投影 $M_i$，使得 $M_i$ 以其自己的特征 $X_i$ 为输入。

无损约束：我们要求模型 $M$ 是无损的，这意味着在训练数据上的联邦学习中模型 $M$ 的损失与在所有数据的联合上构建模型 $M^{\prime }$ 的损失相同。

4 联邦学习与SecureBoost

作为最流行的机器学习算法之一，梯度树提升在许多机器学习任务中表现出色，如欺诈检测、特征选择和产品推荐。在本节中，我们提出了一种新的梯度树提升算法，称为SecureBoost，在联邦学习环境中运行。它包含两个主要步骤。首先，在隐私约束下对数据进行对齐。其次，在保持所有训练数据保密的情况下，协同学习共享的梯度树提升模型。我们在下文解释每一步。

我们的第一个目标是在所有参与方中找到一组共同的数据样本，以便构建联合模型 $M$。当数据在参与方之间按特征进行垂直分区时，不同参与方持有不同但部分重叠的用户，这些用户可以通过其ID识别。问题在于如何在不揭示非共享部分的情况下找到各方之间的共同数据样本。为实现此目标，我们在隐私保护协议下对数据样本进行对齐以实现跨数据库的交集【30】。

在隐私约束下对不同参与方的数据进行对齐之后，我们现在考虑在不违反隐私的情况下联合构建多个参与方的树集成模型。在进一步讨论算法细节之前，我们先介绍联邦学习的一般框架。在联邦学习中，典型的迭代包括四个步骤。首先，每个客户端从服务器下载当前的全局模型。其次，每个客户端基于本地数据和当前的全局模型计算更新的模型，该模型驻留在活跃方。第三，每个客户端在加密状态下将模型更新发送回服务器。最后，服务器聚合这些模型更新并构建更新的全局模型。

遵循联邦学习的一般框架，我们看到，为了在联邦学习环境中设计一个隐私保护的树提升框架，本质上我们必须回答以下三个问题：(1) 每个客户端（即被动方）如何在没有参考类别标签的情况下基于本地数据计算更新的模型？(2) 服务器（即活跃方）如何聚合所有更新的模型并获得新的全局模型？(3) 如何在推理时在各方之间共享更新的全局模型而不泄露任何信息？为回答这三个问题，我们首先回顾非联邦环境中的树集成模型XGBoost【31】。

给定一个数据集 $X\in {\mathbb{R}}^{n\times d}$ ，其中包含 $n$ 个样本和 $d$ 个特征，XGBoost使用 $K$ 个回归树来预测输出。

$${\hat{y}}_i=\sum _{k=1}^K{f}_k(x_i)(1)$$

为了学习在公式(1)中使用的回归树模型集，它在第 $t$ 次迭代时贪婪地添加一棵树 $f_t$ 以最小化以下损失。

$$L(t)\approx \sum _{i=1}^n[l(y_i,{\hat{y}}_i^{(t-1)})+g_i{f}_t(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i)]+\mathrm{\Omega }(f_t)(2)$$

其中 $\mathrm{\Omega }(f_t)=\gamma T+\frac{1}{2}\lambda \parallel w{\parallel }^2$， $g_i={\partial }_{{\hat{y}}^{(t-1)}}l(y_i,{\hat{y}}^{(t-1)})$ 和 $h_i={\partial }_{{\hat{y}}^{(t-1)}}^{2}l(y_i,{\hat{y}}^{(t-1)})$。这两个值仅依赖于损失函数的形式和当前模型的预测值，因此与输入特征无直接关系。然而，它们在决策树的节点分裂过程中扮演了重要角色。被动方通过这些梯度和Hessian值来评估分裂点的好坏，从而选择最优分裂点。

在第 $t$ 次迭代中构建回归树时，它从深度为0的树开始，为每个叶节点添加一个分裂，直到达到最大深度。特别地，它通过最大化以下方程来确定最佳分裂，其中 $I_L$ 和 $I_R$ 分别是分裂后左树节点和右树节点的实例空间。

$$L_{sp}=\frac{1}{2}[\frac{(\sum _{i\in I_L}{g}_i{)}^2}{\sum _{i\in I_L}{h}_i+\lambda }+\frac{(\sum _{i\in I_R}{g}_i{)}^2}{\sum _{i\in I_R}{h}_i+\lambda }-\frac{(\sum _{i\in I}{g}_i{)}^2}{\sum _{i\in I}{h}_i+\lambda }]-\gamma (3)$$

在获得最优树结构后，叶节点 $j$ 的最优权重 $w_j^{\ast }$ 可以通过以下方程计算，其中 $I_j$ 是叶节点 $j$ 的实例空间。

$$w_j^{\ast }=-\frac{\sum _{i\in I_j}{g}_i}{\sum _{i\in I_j}{h}_i+\lambda }(4)$$

从以上回顾中，我们得到以下观察：

1. 分裂候选的评估和叶节点的最优权重计算仅依赖于 $g_i$ 和 $h_i$，这使其易于适应联邦学习环境。
2. 类别标签可以从 $g_i$ 和 $h_i$ 推断出来。例如，当我们采用平方损失作为损失函数时，$g_i={\hat{y}}_i^{(t-1)}-y_i$。

根据上述观察，我们现在介绍我们的联邦梯度树提升算法。根据观察(1)，我们可以看到，被动方可以仅通过其本地数据和 $g_i$、$h_i$ 来确定其本地最优分裂，这激励我们遵循这种方法在每个参与方分解学习任务。然而，根据观察(2)，$g_i$ 和 $h_i$ 应被视为敏感数据，因为它们能够向被动方透露类别标签信息。因此，为了保持 $g_i$ 和 $h_i$ 的机密性，活跃方需要在将 $g_i$ 和 $h_i$ 发送给被动方之前对其进行加密。剩下的挑战是如何为每个被动方确定带有加密 $g_i$ 和 $h_i$ 的本地最优分裂。

根据公式(3)，如果为每个可能的分裂计算 $g_l=\sum _{i\in I_L}{g}_i$ 和 $h_l=\sum _{i\in I_L}{h}_i$，则可以找到最优分裂。接下来，我们展示如何使用加性同态加密方案【32】获得带有加密 $g_i$ 和 $h_i$ 的 $g_l$ 和 $h_l$。我们采用Paillier加密方案作为我们的加密方案。

将数字 $u$ 在Paillier密码系统下的加密表示为 $⟨u⟩$，Paillier密码系统的主要属性确保了对于任意数字 $u$ 和 $v$，我们有 $⟨u⟩\cdot ⟨v⟩=⟨u+v⟩$。因此，$⟨h_l⟩=\prod _{i\in I_L}⟨h_i⟩$ 和 $⟨g_l⟩=\prod _{i\in I_L}⟨g_i⟩$。

因此，可以通过以下方式找到最佳分裂。首先，每个被动方为所有可能的分裂本地计算 $⟨g_l⟩$ 和 $⟨h_l⟩$，然后将其发送回活跃方。活跃方解密所有 $⟨g_l⟩$ 和 $⟨h_l⟩$ 并根据公式(3)计算全局最优分裂。我们采用文献【31】中使用的近似方案，以减少枚举所有可能的分裂候选项并通信其 $⟨g_i⟩$ 和 $⟨h_i⟩$ 的需求。我们安全梯度聚合算法的详细信息如算法1所示。

根据观察(1)，分裂查找算法在联邦学习框架中与XGBoost基本相同，仅做了少量调整。==由于特征的分离==，SecureBoost需要不同参与方为每个分裂存储某些信息，以便对新样本进行预测。被动方应保留一个查找表，如图3所示。它包含分裂阈值[特征ID $k$，阈值 $v$]和用于索引表的唯一记录ID $r$，以在推理期间查找分裂条件。同时，由于活跃方没有位于被动方的特征，为了让活跃方知道将实例传递给哪个被动方，并在推理时指示被动方使用哪个分裂条件，它将每个树节点与一对（参与方ID $i$，记录ID $r$）关联。SecureBoost的分裂查找算法的具体细节总结在算法2中。剩下的问题是最优叶权重的计算。根据公式4，叶节点 $j$ 的最优权重仅依赖于 $\sum _{i\in I_j}{g}_i$ 和 $\sum _{i\in I_j}{h}_i$。因此，它遵循与分裂查找相似的步骤。当到达叶节点时，被动方将 $⟨\sum _{i\in I_j}{g}_i⟩$ 和 $⟨\sum _{i\in I_j}{h}_i⟩$ 发送给活跃方，活跃方再解密以通过公式4计算相应的权重。

5 联邦推理

在本节中，我们描述了如何使用分布在各参与方中的学习模型来对新实例进行分类，即使实例的特征是私有的并且分布在各参与方之间。由于每个参与方只知道自己的特征而不知道其他参与方的特征，我们需要一个安全的分布式推理协议来控制从一个参与方到另一个参与方的传递，基于所做的决策。为了说明推理过程，我们考虑一个如图3所示的三方系统。具体来说，参与方1是活跃方，收集的信息包括用户的月账单支付、教育水平以及标签（用户X是否按时支付）。参与方2和参与方3是被动方，分别持有年龄、性别、婚姻状况和授信金额的特征。假设我们希望预测用户$X_6$是否会按时支付，那么所有站点都必须协作进行预测。整个过程由活跃方协调。从根节点开始，通过参考记录[参与方ID:1，记录ID:1]，活跃方知道参与方1持有根节点，因此要求参与方1根据记录ID 1从其查找表中检索相应属性（账单支付）。由于分类属性是账单支付，而参与方1知道用户$X_6$的账单支付为4367，小于阈值5000，因此决定向其左子节点（节点1）移动。然后，活跃方参考与节点1关联的记录[参与方ID:3，记录ID:1]，要求参与方3进行相同操作。此过程持续到达叶节点为止。

6 无损属性的理论分析

定理1. SecureBoost是无损的，即SecureBoost模型 $M$ 和XGBoost模型 $M^{\prime }$ 在相同初始化和超参数化的情况下将表现一致。

证明。根据公式(3)，$g_l$ 和 $h_l$ 是计算最佳分裂所需的唯一信息，这可以通过使用Paillier密码系统对加密的 $g_i$ 和 $h_i$ 进行处理获得。在Paillier密码系统中，消息 $m$ 的加密为 $⟨m⟩=g^m{r}^n\mathrm{mod}{n}^2$，其中 $r$ 为某个随机数 $\{0,...,n-1\}$。给定加密消息的定义，我们有 $⟨m_1⟩\cdot ⟨m_2⟩=⟨m_1+m_2⟩$ 对于任意消息 $m_1$ 和 $m_2$ 在Paillier密码系统下成立，证明如下：

$$\begin{array}{rl}⟨m_1⟩.⟨m_2⟩& =(g^{m_1}{r}_1^c)(g^{m_2}{r}_2^c)\mathrm{mod}n\\ & =g^{m_1+m_2}(r_1{r}_2{)}^c\mathrm{mod}n& \text{(5)}\\ & =⟨m_1+m_2⟩\end{array}$$

因此，我们有 $⟨h_l⟩=\prod _{i\in I_L}⟨h_i⟩$ 和 $⟨g_l⟩=\prod _{i\in I_L}⟨g_i⟩$。假设使用相同的初始化，实例 $i$ 在任何环境下将具有相同的 $g_i$ 和 $h_i$ 值。因此，模型 $M$ 和 $M^{\prime }$ 可以始终在树结构构建过程中实现相同的最佳分裂，并最终生成相同的 $M$ 和 $M^{\prime }$，确保无损属性。

7 安全讨论

SecureBoost在训练和推理过程中避免了各参与方暴露其持有的数据记录，从而保护了各参与方数据的隐私。然而，我们强调，在协议执行过程中存在一些可以推断的信息泄露，这在被动方与活跃方之间有很大的不同。

活跃方在SecureBoost中处于有利地位，因为它了解每个分裂的实例空间以及哪个参与方负责每个节点的决策。此外，它在学习过程中还了解所有可能的 $g_l,g_r$ 和 $h_l,h_r$ 的值。前者在这种设置中似乎是不可避免的，除非愿意在推理阶段显著增加开销。然而，后者可以使用安全多方计算技术来比较加密值（例如【33】【34】）来避免。这样，活跃方只能了解每个参与方的最优 $g_l,g_r,h_l,h_r$，另一方面，这在学习过程中显著影响了效率。

注意，与同一叶节点相关联的实例强烈表明它们属于同一类。我们将属于多数类的样本比例称为叶纯度。相对于被动方的信息泄露与SecureBoost第一棵树的叶纯度直接相关。此外，第一棵树的叶纯度可以从叶子的权重中推断出来。

定理2：给定一个学习到的SecureBoost模型，可以从其第一棵树的叶子权重中推断出叶纯度。

证明：对于二元分类问题，损失函数如下：

$$L=y_i\log (1+e^{-{\hat{y}}_i})+(1-y_i)\log (1+e^{{\hat{y}}_i})$$

根据损失函数，在第一次迭代构建决策树时，我们有 $g_i={\hat{y}}_i^{(0)}-y_i$ 和 $h_i={\hat{y}}_i^{(0)}\cdot (1-{\hat{y}}_i^{(0)})$。具体来说，${\hat{y}}_i^{(0)}$ 被初始化为一个值。假设我们将所有 ${\hat{y}}_i^{(0)}$ 初始化为 $a$，其中 $0<a<1$。根据公式(4)，对于与特定叶节点 $j$ 相关联的实例，${\hat{y}}_i^{(1)}=S(w_j^{\ast })=S(-\frac{\sum _{i\in I_j}{g}_i}{\sum _{i\in I_j}{h}_i+\lambda })$，其中 $S(x)$ 是sigmoid函数。假设与叶节点 $j$ 相关联的实例数为 $n_j$，正样本的百分比为 ${\theta }_j$。当 $n_j$ 相对较大时，我们可以忽略 $\lambda$ 在 $-\frac{\sum _{i\in I_j}{g}_i}{\sum _{i\in I_j}{h}_i+\lambda }$ 中的影响，将叶节点 $j$ 的权重 $w_j^{\ast }$ 重写为：

$$w_j^{\ast }=-\frac{{\theta }_j\cdot n\cdot (a-1)+(1-{\theta }_j)\cdot n\cdot a}{n\cdot a\cdot (1-a)}=\frac{a-{\theta }_j}{a(1-a)}$$

通过重新整理方程，我们得到 ${\theta }_j=a-a(1-a)w_j^{\ast }$。${\theta }_j$ 取决于 $a$ 和 $w_j^{\ast }$，而 $a$ 作为初始化值已给定。因此，$w_j^{\ast }$ 是确定 ${\theta }_j$ 的关键。注意，${\theta }_j$ 可以用来表示叶节点 $j$ 的纯度（即，叶节点 $j$ 的纯度可以正式写为 $max({\theta }_j,1-{\theta }_j)$），给定学习到的SecureBoost模型，可以从其第一棵树的叶子权重 ($w_j^{\ast }$) 中推断出叶纯度。

根据定理2，给定SecureBoost模型，可以从其第一棵树的叶子权重中推断出敏感信息。为了减少相对于被动方的信息泄露，我们选择将决策树的叶子存储在活跃方，并提出我们框架的修改版本，称为Reduced-Leakage SecureBoost (RL-SecureBoost)。使用RL-SecureBoost，活跃方仅基于自己的特征独立学习第一棵树，从而完全保护其叶节点的实例空间。因此，被动方所学到的所有信息都是基于残差。尽管残差也可能泄露信息，但我们证明，随着第一棵树叶纯度的增加，这种残差信息减少。

定理3：随着第一棵树叶纯度的增加，残差信息减少。

证明：如前所述，对于二元分类问题，我们有 $g_i={\hat{y}}_i^{(t-1)}-y_i$ 和 $h_i={\hat{y}}_i^{(t-1)}\cdot (1-{\hat{y}}_i^{(t-1)})$，其中 $g_i\in [-1,1]$。因此：

$$\{\begin{array}{ll}{h}_i=g_i(1-g_i),& \text{if}{y}_i=0\\ h_i=-g_i(g_i+1),& \text{if}{y}_i=1\end{array}(7)$$

当我们在第 $t$ 次迭代中构建具有 $k$ 个叶节点的决策树以拟合前一棵树的残差时，本质上，我们将数据分成 $k$ 个簇，以最小化以下损失：

$$\begin{array}{rl}\text{L}& =-\sum _{j=1}^k\frac{(\sum _{i\in I_j}{g}_i{)}^2}{\sum _{i\in I_j}{h}_i}\\ & & \text{(8)}\\ & =-\sum _{j=1}^k\frac{(\sum _{i\in I_j}{g}_i{)}^2}{\sum _{i\in I_j^N}{g}_i(1-g_i)+\sum _{i\in I_j^P}-g_i(1+g_i)}\end{array}$$

我们知道 ${\hat{y}}_i^{(t-1)}\in [0,1]$ 且 $g_i={\hat{y}}_i^{(t-1)}-y_i$。因此，对于正样本，$g_i\in [-1,0]$，对于负样本，$g_i\in [0,1]$。考虑到 $g_i$ 的范围，我们可以将上述方程重写如下：

$$\sum _{j=1}^k\frac{(\sum _{i\in I_j^N}|g_i|-\sum _{i\in I_j^P}|g_i|{)}^2}{\sum _{i\in I_j^N}|g_i|(|g_i|-1)+\sum _{i\in I_j^P}|g_i|(|g_i|-1)}(9)$$

其中 $I_j^n$ 和 $I_j^p$ 分别表示与叶节点 $j$ 相关联的负样本和正样本的数量。我们将正样本的 $|g_i|$ 的期望表示为 ${\mu }_p$，将负样本的 $|g_i|$ 的期望表示为 ${\mu }_n$。当我们有大量样本但叶节点数量较少时，我们可以使用以下公式近似等于公式9：

$$\sum _{j=1}^k\frac{(n_j^n{\mu }_n-n_j^p{\mu }_p{)}^2}{n_j^n{\mu }_n({\mu }_n-1)+n_j^p{\mu }_p({\mu }_p-1)}(10)$$

其中 $n_j^n$ 和 $n_j^p$ 分别表示与叶节点 $j$ 相关联的负样本和正样本的数量。由于 ${\mu }_n\in [0,1]$ 和 ${\mu }_p\in [0,1]$，我们知道分子必须为正，分母必须为负。因此，整个方程必须为负。最小化此方程(10)等同于最大化分子，同时最小化分母。注意，分母为 $\sum x^2$ 而分子为 $(\sum x{)}^2$，其中 $x\in [0,1]$。该方程受分子支配。因此，最小化方程可以视为最大化分子 $(n_j^n{\mu }_n-n_j^p{\mu }_p{)}^2$。理想情况下，我们需要 $n_j^n=n_j^p$ 以防止标签信息泄露。当 $|{\mu }_n-{\mu }_p|$ 较大时，更有可能实现目标。我们知道，对于负样本 $|g_i|=|{\hat{y}}_i^{(t-1)}-y_i|={\hat{y}}_i^{(t-1)}$，对于正样本 $|g_i|=|{\hat{y}}_i^{(t-1)}-y_i|=1-{\hat{y}}_i^{(t-1)}$。因此：${\mu }_n=\frac{1}{N_n}\sum _{j=1}^k(1-{\theta }_j)n_j{\hat{y}}_i^{(t-1)}$ 并且 ${\mu }_p=\frac{1}{N_p}\sum _{j=1}^k{\theta }_j{n}_j(1-{\hat{y}}_i^{(t-1)})$

$|{\mu }_n-{\mu }_p|$ 可以计算如下：

$$\begin{array}{rl}& |{\mu }_n-{\mu }_p|\\ & =|\frac{1}{N_n}\sum _{j=1}^k(1-{\theta }_j)n_j{\widehat{y_i}}^{(t-1)}-\frac{1}{N_p}\sum _{j=1}^k{\theta }_j{n}_j(1-{\widehat{y_i}}^{(t-1)})|\\ & & (11)\end{array}$$

其中，$N_n$ 和 $N_p$ 分别表示负样本和正样本的总数。${\theta }_j$ 是与第 $j$ 个叶节点关联的正样本在第 $(t-1)$ 次迭代（上一个决策树）中的比例。$n_j$ 表示与第 $j$ 个叶节点关联的实例数量。$y{̂}_i(t-1)=S(w_j)$，其中 $w_j$ 表示上一个决策树的第 $j$ 个叶节点的权重。当正样本和负样本平衡时，即 $N_n=N_p$，我们有：

$$\begin{array}{rl}& |{\mu }_n-{\mu }_p|\\ & =\frac{1}{N_n}|\sum _{j=1}^k((1-{\theta }_j)n_{j}S(w_j)-{\theta }_j{n}_j(1-S(w_j))|\\ & =\frac{1}{N_n}\sum _{j=1}^k{n}_j|(S(w_j)-{\theta }_j)|& \text{(12)}\\ & =\frac{1}{N_n}\sum _{j=1}^k{n}_j|(S(\frac{a-{\theta }_j}{a(a-1)})-{\theta }_j)|\end{array}$$

如公式12所示，当 $S\left(\frac{a-{\theta }_j}{a(1-a)}\right)=a$ 时，取最小值。通过求解该方程，我们得到 ${\theta }_j$ 的最优解为：${\theta }_j^{\ast }=a(1+(1-a)\ln \left(\frac{a}{1-a}\right))$
为了实现较大的 $|{\mu }_n-{\mu }_p|$，我们希望 ${\theta }_j$ 与 ${\theta }_j^{\ast }$ 之间的偏差尽可能大。对于适当的初始化 $a$，例如 $a=0.5$，我们有 ${\theta }_j^{\ast }=0.5$。在这种情况下，最大化 $|{\theta }_j-{\theta }_j^{\ast }|$ 就是最大化 $max({\theta }_j,1-{\theta }_j)$，即叶纯度。因此，我们证明了高叶纯度将保证 ${\mu }_n$ 和 ${\mu }_p$ 之间的较大差异，从而最终导致较少的信息泄露。我们完成了证明。

根据定理3，我们证明了只要RL-SecureBoost的第一棵树学到足够的信息来用残差掩盖实际标签，它就是安全的。此外，正如我们在第8节中通过实验证明的那样，从预测准确性的角度来看，RL-SecureBoost与SecureBoost的表现完全相同。

8 实验

我们在两个公共数据集上进行了实验。

Credit 1：涉及用户是否会遭遇严重财务问题的分类问题。总共包含150,000个实例和10个属性。

Credit 2：也是一个信用评分数据集，涉及预测用户是否会按时付款的任务。总共包含30,000个实例和25个属性。

在实验中，我们使用每个数据集的2/3进行训练，剩余的用于测试。我们将数据垂直分成两半，并分配给两个参与方。为了公平比较不同的方法，我们将每棵树的最大深度设置为3，拟合单个回归树的样本比例为0.8，所有方法的学习率为0.3。我们采用Paillier加密方案作为加密方案，密钥大小为512位。所有实验均在具有8GB内存和Intel Core i5-7200u CPU的机器上进行。

8.1 可扩展性

SecureBoost的效率可能反映在收敛率和运行时间上，这可能会受到以下因素的影响：(1)单个回归树的最大深度；(2)数据集的大小。在本小节中，我们进行收敛性分析，并研究所有变量对学习运行时间的影响。所有实验均在Credit 2数据集上进行。

首先，我们对系统的收敛率感兴趣。我们将SecureBoost的收敛行为与非联邦树提升方法，包括GBDT和XGBoost进行比较。从图4中可以看出，SecureBoost在训练数据集上的学习曲线与其他非联邦方法类似，甚至在测试数据集上的表现略优于其他方法。此外，SecureBoost的训练和测试损失的收敛行为与GBDT和XGBoost非常相似。

接下来，为了研究单棵树的最大深度如何影响学习的运行时间，我们将单棵树的最大深度在{3, 4, 5, 6, 7, 8}之间变化，并报告一次提升阶段的运行时间。如图5(a)所示，运行时间几乎随单棵树的最大深度线性增加，这表明我们可以在相对较少的额外时间内训练深度较大的树，这在实际应用中特别具有吸引力，尤其是在大数据场景中。

最后，我们研究数据大小对提议系统运行时间的影响。我们通过特征乘积来增加特征集。我们将单棵回归树的最大深度固定为3，并将特征数量在{50, 500, 1000, 5000}之间变化，将样本数量在{5000, 10000, 30000}之间变化。我们比较了一次提升阶段的运行时间，以研究每个变量对算法效率的影响。我们在图5(b)和图5(c)上做了类似的观察，表明样本和特征数量对运行时间的贡献是相等的。此外，我们可以看到，即使在相对较大的数据下，我们的提议框架仍然具有良好的可扩展性。

8.2 RL-SecureBoost的性能

为了研究RL-SecureBoost在安全性和预测准确性方面的性能，我们旨在回答以下问题：(1) RL-SecureBoost的第一棵树（仅基于活跃方的特征构建）是否学到了足够的信息以减少信息泄露？(2) RL-SecureBoost与SecureBoost相比，准确性是否会下降？

首先，我们研究RL-SecureBoost在安全性方面的表现。根据第7节中的分析，我们用叶纯度来评估信息泄露的程度。此外，我们知道随着第一棵树叶纯度的增加，泄露的信息会减少。因此，为了验证RL-SecureBoost的安全性，我们必须证明RL-SecureBoost的第一棵树在减少第二棵树泄露的信息方面表现良好。如表1所示，我们比较了第一棵树和第二棵树的平均叶纯度。特别地，平均叶纯度是加权平均值，计算公式为$\sum _{i=0}^k\frac{n_i}{n}{p}_i$。这里，$k$ 和 $n$ 分别表示叶节点数和总实例数，$p_i$ 和 $n_i$ 分别表示叶节点 $i$ 的纯度和与其相关联的实例数。根据表1，平均叶纯度从第一棵树到第二棵树显著下降，反映了信息泄露的大幅减少。此外，第二棵树的平均叶纯度在两个数据集上都刚好超过0.6，这足以确保协议的安全性。

接下来，为了研究RL-SecureBoost的预测性能，我们比较了RL-SecureBoost和SecureBoost在第一棵树和整体性能方面的表现。我们考虑了常用的指标，包括准确率（Accuracy）、ROC曲线下面积（AUC）和F1分数。结果如表2所示。可以观察到，RL-SecureBoost在几乎所有情况下的表现与SecureBoost一样好。我们还对RL-SecureBoost和SecureBoost进行了配对的Wilcoxon符号秩检验。比较结果表明，RL-SecureBoost的准确性与SecureBoost相同，显著性水平为0.05。RL-SecureBoost仍然保证了无损属性。

9 结论

在本文中，我们提出了一种无损的隐私保护树提升算法SecureBoost，用于在跨多个参与方的私有数据上训练高质量的树提升模型。我们从理论上证明了我们提出的框架与非联邦梯度树提升方法一样准确。此外，我们分析了协议执行过程中的信息泄露，并提出了可验证的方法来减少这种信息泄露。