一种基于差分隐私的垂直联邦XGBoost算法

本发明涉及xgboost训练与问题建模，特别是涉及一种基于差分隐私的垂直联邦xgboost算法。

背景技术：

1、联邦学习是一种分布式机器学习范式，它支持在确保数据隐私的同时跨多方进行协作训练机器学习模型。根据数据的划分方式，可以将联邦学习大致分为水平联邦学习和垂直联邦学习。垂直联邦学习适用于多个数据集共享相同的样本空间，但特征空间不同的情况。垂直联邦学习是目前业界公式使用广泛的合作建模方式。极度梯度提升(extremegradient boosting，xgboost)是梯度提升决策树(gradient boosting decisiontree，gbdt)的一种改进，由于其高性能和强可解释性而得到了广泛的应用。因此，在垂直联邦学习场景中使用xgboost来建模在学术界和业界越来越受重视。

2、现有关于联邦梯度提升决策树的研究大多需要不同类型的基于加密的协议：同态加密(homomorphic encryption,he)和秘密共享。这类方法会将隐私信息加密之后计算，保证了信息的安全，然而会导致很大的通信和计算开销。另一种研究思路采用差分隐私(differential privacy，dp)或本地差分隐私(local differential privacy，ldp)的技术，对通信数据加入噪声从而达到保护隐私的目的。然而这类方法由于加入了噪声，会使模型训练受到损失。

技术实现思路

1、为解决现有技术中存在的问题，本发明提供了一种基于差分隐私的垂直联邦xgboost算法，解决了现有方法对通信数据加入噪声从而达到保护隐私的目的，由于加入了噪声，会使模型训练受到损失的问题。

2、本发明的技术方案如下：

3、一种基于差分隐私的垂直联邦xgboost算法，包括以下步骤：

4、步骤s1：初始化，得到参数σ1,σ2,c,w；

5、步骤s2：根据参数σ1,σ2,c,w，pp方生成噪声；

6、步骤s3：根据pp方生成的噪声，ap方信息加噪；

7、步骤s4：pp方根据ap方发送的加噪的信息，联合最优分裂候选点进行搜索。

8、优选地，步骤s2包括以下子步骤：

9、子步骤s21：定义激活集合a(mi)和非激活集合i(mi)；

10、

11、na,i＝|a(mi)|,ni,i＝|i(mi)|

12、式中，na,i代表第i个分裂向量对应激活集合的集合大小，ni,i代表第i个分裂向量对应非激活集合的集合大小；

13、子步骤s22：对于每个分裂向量mi,生成一个噪声矩阵bi＝[bi1,…,biw]，其中bij∈rn由激活噪声uij、非激活噪声vij和干扰噪声rij三部分组成，即bij＝uij+vij+rij；

14、其中，激活噪声uij的计算公式为：

15、

16、式中，代表uij向量中第a(mi)k个元素，a(mi)k代表着向量的不同维度，是na,i个均值为零、方差为的高斯变量；

17、其中，非激活噪声vij的计算公式为：

18、

19、式中，代表vij向量中第i(mi)k个元素，i(mi)k代表着向量的不同维度,是ni,i个均值为零、方差为的高斯变量；

20、其中，干扰噪声rij分布服从均值为零，协方差矩阵为的多维高斯分布，其中in是n维单位矩阵；

21、子步骤s23：噪声生成过程w次，pp方依次生成bi1,…,biw作为一个噪音矩阵bi，即bi＝[bi1,…,biw]∈rn×w；

22、子步骤s24：pp根据l个分裂向量生成对应的噪音矩阵；

23、子步骤s25：pp将整个噪音矩阵集合发送给ap。

24、优选地，步骤s3包括以下子步骤：

25、子步骤s31：ap方根据如下约束，生成2w个系数，ci＝[ci1,…,ciw]和di＝[di1,…,diw]；

26、

27、其中，ci1,…,ciw和di1,…,diw分别代表着对梯度和海森向量加噪声bi1,…,biw的权重，c是一个大于0的常数，代表着加噪的总能量和隐私程度；

28、子步骤s32：利用这些系数和噪音向量来对g,h进行加噪，依次得到gi＝<g>1,…,<g>l和hi＝<h>1,…,<h>l

29、

30、其中，<g>i和<h>i表示第i个加噪后的梯度向量和海森向量，ci1,…,ciw和di1,…,diw分别代表着对梯度和海森向量加噪声bi1,…,biw的权重

31、子步骤s33：pp方比较分裂候选点时，还需要梯度和海森的加和信息，所以ap在加噪梯度和海森之后，再计算：

32、

33、其中，gi和hi代表第i个训练数据的梯度和海森值，g和h代表当前树节点所有训练数据的梯度值和海森值的加和；

34、子步骤s34：ap将{{<g>i,<h>i}i∈{1,…,l},g,h}发送给pp。

35、优选地，步骤s4包括以下子步骤：

36、子步骤s41：pp根据ap发送的信息，根据如下公式计算每个分裂点对应的分裂分数l,分裂分数最高的分裂点作为最优；

37、

38、式中，si代表着当前节点的第i个分裂方式，和分别代表分裂点si对应的分到左边的训练数据的梯度和海森加和值，和分别代表分裂点si对应的分到右边的训练数据的梯度和海森加和值，g和h代表当前节点所有训练数据的梯度值和海森值的加和，l代表着分裂点si对应的信息增益，l越大信息增益越大，根据l值的大小来选择最优的分裂方式，式中，λ是xgboost算法的一个超参数，为防止对训练数据过拟合；

39、子步骤s42：pp将最优的分裂分数和具体的分裂点信息发送给ap，ap根据分裂分数找到双方整体最优的分裂点；

40、子步骤s43：ap分裂当前树节点构建新的两个节点，继续这个分裂过程直到达到树的最大深度。

41、本发明基于差分隐私的垂直联邦xgboost算法的有益效果如下：

42、1.本发明通过构造具有无损性质的噪声来实现隐私保护，在相同隐私情况下，建模效用显著优于其他基于加噪的隐私保护算法fedxgboost-ldp、xgboost-ldp。

43、2.本发明通过在明文数据上使用高斯噪声进行加噪，建模效率明显优于基于加密的隐私保护方法，同时与明文非隐私保护方法效率接近。

44、3.本发明对建模双方都有隐私保证，同时可以在此条件下取得模型效用与隐私泄露的权衡。

45、4.本发明的噪声机制采用高斯机制，在理论上对建模双方有差分隐私保护性质。

1.一种基于差分隐私的垂直联邦xgboost算法，其特征在于，包括以下步骤：

2.根据权利要求1所述的基于差分隐私的垂直联邦xgboost算法，其特征在于，所述步骤s2包括以下子步骤：

3.根据权利要求1所述的基于差分隐私的垂直联邦xgboost算法，其特征在于，所述步骤s3包括以下子步骤：

4.根据权利要求1所述的基于差分隐私的垂直联邦xgboost算法，其特征在于，所述步骤s4包括以下子步骤：