基于梯度提升决策表的隐私保护垂直联邦学习方法及系统

1.本发明涉及信息安全
技术领域：
：，尤其涉及基于梯度提升决策表的隐私保护垂直联邦学习方法及系统。
背景技术：
：：2.联邦学习(federatedlearning)作为分布式机器学习的一种，极大地增强了多方合作。联邦学习允许参与方的训练数据被保存在本地，并且仅共享训练算法的中间输出以进行聚合。根据数据在参与者之间的分布方式，联邦学习可以分为两种：水平联邦学习(hfl)和垂直联邦学习(vfl)。其中，垂直联邦学习针对的场景是每个参与者都拥有相同的样本但拥有不同特征的数据，垂直联邦学习的参与者持有具有相同行索引(对应于同一组实例)但不同的非重叠列索引(对应于不同特征)的数据集。近年来，垂直联邦学习在不同企业的合作中受到越来越多的关注。3.在现有的垂直联邦学习研究中，梯度提升算法(gradientboosting)是一个研究热点，因为梯度提升算法在网络搜索排名、在线广告和欺诈检测等众多领域都得到了广泛应用。梯度提升算法通过梯度提升技术训练若干个弱学习器，以获得一个预测性能更好的模型。许多工作表明，梯度提升决策表(gradientboosteddecisiontables)能够胜任许多机器学习任务，并取得比常用的决策树更好的预测效率。4.所有现有的决策表学习和预测算法考虑的都是中心化数据，不能直接支持垂直联邦学习下决策表的安全梯度提升算法，也就是说，在现有技术中，在进行垂直联邦学习的过程中，各方有可能会获取到其他方持有的数据、还可能会获取到学习过程中的中间数据进而获取到整个模型的参数。但是在实际应用中，出于隐私保护的考虑，企业可能不愿意将自身持有的数据共享给其他企业，同时，也不愿意将自身持有的模型参数分享给其他企业。因此，现有技术无法实现对基于梯度提升决策表的垂直联邦学习的中间数据的隐私保护。技术实现要素：5.本发明提供一种基于梯度提升决策表的隐私保护垂直联邦学习方法及系统，用以解决现有技术中无法实现对基于梯度提升决策表的垂直联邦学习的中间数据的隐私保护的缺陷，实现基于梯度提升决策表的垂直联邦学习数据的隐私保护。6.本发明提供一种基于梯度提升决策表的隐私保护垂直联邦学习方法，所述方法应用于包括多个参与终端的系统中，每个所述参与终端持有每个学习样本的部分特征数据，且各个所述参与终端持有的特征数据的类别不同；所述方法包括：7.各个所述参与终端中的第一目标参与终端基于本地持有的各个所述学习样本的第一目标特征数据以及目标决策表中第一目标层对应的最优测试，确定所述第一目标层对应的指示向量，其中，所述目标决策表为当前学习轮次中需要学习的决策表，所述目标特征数据与所述第一目标层对应，所述第一目标参与终端持有所述第一目标层对应的所述第一目标特征数据，所述指示向量用于反映所述第一目标层中每个结点对应的样本被划分至结点的第一子结点或第二子结点，所述目标决策表中每一层对应的最优测试用于确定层中每个样本的划分结果；8.所述第一目标参与终端生成所述指示向量对应的n个第一加性秘密共享份额，将n-1个所述第一加性秘密共享份额分别发送至所述系统中其余的所述参与终端，其中，n为所述参与终端的个数；9.每个所述参与终端基于本地持有的各个所述第一加性秘密共享份额更新本地持有的第二目标层中的各个结点分别对应的第二加性秘密共享份额和第三加性秘密共享份额，其中，所述第二目标层为所述目标决策表中所述第一目标层的子结点所在的层，所述第二加性秘密共享份额为一阶梯度向量的加性秘密共享份额，所述第三加性秘密共享份额为二阶梯度向量的加性秘密共享份额，当第i个所述学习样本被划分至目标结点时，所述目标结点对应的所述一阶梯度向量中的第i个值为第i个所述学习样本当前的一阶梯度，其余值为0，所述目标结点对应的所述二阶梯度向量中的第i个值为第i个所述学习样本当前的二阶梯度，其余值为0；10.各个所述参与终端中的第二目标参与终端基于本地持有的所述第二加性秘密共享份额和所述第三加性秘密共享份额，在秘密共享域计算各个候选测试对应的评价分数，所述第二目标参与终端基于所述评价分数的秘密共享份额确定所述第二目标层对应的最优测试，其中，所述第二目标参与终端持有所述第二目标层对应的第二目标特征数据；11.在所述目标决策表的每个层的最优测试均被确定后，完成所述当前学习轮次，基于已被学习的决策表，各个所述参与终端获取各个所述学习样本的预测结果的第四加性秘密共享份额，并基于所述第四加性秘密共享份额得到下一学习轮次中被学习的决策表中第一个结点对应的所述第二加性秘密共享份额和所述第三加性秘密共享份额，直到已被学习的决策表的数量达到预设数量，以完成学习过程。12.本发明还提供一种基于梯度提升决策表的隐私保护垂直联邦学习系统，包括多个参与终端，所述多个参与终端协同完成上述的基于梯度提升决策表的隐私保护垂直联邦学习方法。13.本发明提供的基于梯度提升决策表的隐私保护垂直联邦学习方法中，为决策表中的每个结点维护一个对应的梯度向量，每个参与终端持有梯度向量的加性秘密共享份额，而持有一种完整特征数据的参与终端，通过生成指示向量，将指示向量的加性秘密共享份额发送给各个参与终端，各个参与终端通过指示向量来更新下一层结点的梯度向量的秘密共享份额，使得结点的子结点对应的梯度向量中没有被划分至该子结点的样本对应的值为0，划分至该子结点的样本对应的值为1，实现了每个结点处理的样本数保持不变，除了持有该完整特征数据的终端，所有的参与终端都无法从结点分裂中推断出任何信息，包括该完整特征数据的最优测试阈值，以及哪些样本的特征数据小于或大于这个阈值，进一步地，本发明提供的方法中各个参与终端还基于加性秘密共享确定决策表中的每一层的最佳测试的阈值的加性秘密共享份额，以及确定学习样本的预测结果的加性秘密共享份额，用于下一轮决策表的学习，在学习的全部过程中，所有的中间数据都是被加密的，每个参与终端只能获取到数据的加性秘密共享份额，而无法获取到完整的明文数据，因此，本发明可以实现对基于梯度提升决策表的隐私保护垂直联邦学习数据的隐私保护。附图说明14.为了更清楚地说明本发明或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作一简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。15.图1为明文域的基于决策表的学习算法示意图；16.图2为常规决策树和决策表等价的决策树的比较示意图；17.图3为本发明提供的基于梯度提升决策表的隐私保护垂直联邦学习方法的流程图；18.图4为本发明提供的基于梯度提升决策表的隐私保护垂直联邦学习方法的总体框架示意图；19.图5为本发明提供的基于梯度提升决策表的隐私保护垂直联邦学习方法中安全结点分裂的过程示意图；20.图6为本发明提供的基于梯度提升决策表的隐私保护垂直联邦学习方法中安全置换的过程示意图；21.图7为本发明提供的基于梯度提升决策表的隐私保护垂直联邦学习方法中安全离散化的过程示意图；22.图8为本发明提供的基于梯度提升决策表的隐私保护垂直联邦学习方法中分布式决策表训练过程示意图；23.图9为本发明提供的基于梯度提升决策表的隐私保护垂直联邦学习方法中安全决策表预测过程示意图。具体实施方式24.为使本发明的目的、技术方案和优点更加清楚，下面将结合本发明中的附图，对本发明中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。25.针对现有的基于梯度提升决策表的垂直联邦学习技术中都不能实现隐私保护的问题，本发明提供一种基于梯度提升决策表的垂直联邦学习方法，支持任意数量的参与方来联合地训练梯度提升决策表，同时允许这些参与方将数据保存在本地，并在训练过程中为敏感的中间输出数据提供了强有力的隐私保护。为了便于本领域技术人员理解本发明提供的基于梯度提升决策表的隐私保护垂直联邦学习方法的技术方案，首先对本发明提供的方法的技术背景进行说明。26.1、决策表27.考虑一个包含n个样本的数据集其中xi＝(xi1,…,xij)是一个j元组，yi是第i个样本的标签。xi的第j个元素是特征xj的值。一个d维决策表由d个布尔测试和2d个输出值组成。布尔测试的形式为xj《t，如果给定输入元组中的第j个元素小于阈值t，则输出1，否则输出0。28.如图2所示，一个d维决策表相当于一个d+1层的满二叉树，其中每个内部结点从第0层(对于根结点)到第d-1层有一个布尔测试；每条边都分配了其父结点测试的结果，并且第d层的每个叶结点都与一个输出值相关联。这种等价树称为oblivioustree，因为同一级别的所有内部结点共享相同的测试，这与在同一级别具有不同测试的常规决策树完全不同。更具体地说，oblivioustree第d层的测试可以表示为fd《td，其中d∈[0,d-1]，分裂特征fd∈(x1,…,xj)，td是分裂阈值。oblivioustree的特殊结构导致其与cart等常规决策树不同的训练和预测方法。[0029]在被发明提供的方法中，自顶向下地训练oblivioustree。如图1所示，图1中给出了oblivioustree的训练算法，该算法输出d个测试和2d个输出值。学习算法从第0层开始，逐层迭代地构建遗忘树。给定一个测试xj《t，定义《t，定义还将此符号应用于子集令表示在第l层的子集集合，其中l∈[0,d]。在第0层，训练数据集与根结点相关联，并满足(第1行)。一旦通过方法find_split(图1中算法的第4行)找到该层的最优测试f0《t0，会根据这一测试被划分为两个子集之后，将添加到并创建新的一层(图1中算法的第6-7行)。[0030]在第1层，训练算法找到一个最佳测试分别根据f1《t1被划分为两个子集。重复上述步骤，直到所有的d个测试都被学习。这种方式使得树状结构保持完全对称。在第l层，决策表满足其中中的每个集合都与该层的一个结点相关联。当达到第d层时，训练算法将为叶结点计算输出值。最后，可以学习到一棵由d个测试和2d个输出值组成的oblivioustree。[0031]每层的最佳测试是通过评估候选测试的find_split方法来找到的。对候选测试的评估可以通过不同的指标进行。在本发明中，遵循常用的二阶近似法来评估测试，因为本发明中的决策表是为梯度提升系统训练的。此外，决策表的输出值也可以按照梯度提升理论来计算。[0032]决策表在预测速度方面明显优于常规决策树。如图2所示，oblivioustree的每个叶结点(图2中右侧的结点)对应于一个布尔序列，并且d个测试所需的比较可以并行化。相比之下，常规决策树中的预测是通过从根结点遍历树到叶结点进行的，这意味着当前结点之后的预测路径的方向取决于该结点的测试结果。决策表中的预测没有这种依赖性，可以同时执行d个布尔比较，并得到一个布尔序列作为结果，然后使用布尔序列查表快速得到预测结果，为了方便描述后，后文中直接将输出的布尔序列称为预测结果。[0033]2、梯度提升决策表[0034]梯度提升系统是在提升算法的基础上训练一组弱学习器(一个决策表可以看做一个弱学习器)而建立的。对于给定的数据集梯度提升系统将t个弱学习器的预测结果相加，得到第i个样本的最终预测结果：其中ft对应第t个弱学习器。一个给定的样本将根据决策表中的测试结果被划分到决策表的叶子结点中，而它的最终预测结果是通过将与对应叶子结点相关的输出值相加来计算的。[0035]梯度提升算法的精髓在于它如何依次训练弱学习器。在训练t-1个弱学习器后，需要对第t个模型ft进行训练和添加，以最小化以下目标函数：[0036][0037]其中是一个二次可微的凸损失函数，它以作为输入，并输出损失。正则化项ω(ft)参考xgboost的常规设置。接下来使用二阶逼近快速逼近目标函数：[0038][0039]其中分别是第i个样本的一阶和二阶梯度。通常，对于回归问题，使用mse作为损失函数，梯度的计算方法如下：当问题是分类时，常见的选择是logistic损失，梯度计算如下：gi＝pi-yi,hi＝pi×(1-pi)，其中对于x∈r，sigmoid函数为：sigmoid(x)＝1/(1+e-x)。对于与一个子集相关的叶子结点k，定义ik＝{i∣(xi,yi)∈vk}为其样本集。这个符号也用来表示与内部结点相关的样本集，例如，把结点q写成iq。然后，在去除常数项后，公式1可以改写为[0040][0041]其中wk是与叶子结点k相关的输出值，l是树中叶子结点的数量，λ，γ是控制正则化的超参数。当树停止生长时，wk和当前树的最小损失如下计算：[0042][0043][0044]公式4可以作为评估测试的不纯度函数。遵循上述理论来寻找决策表中的最优测试，假设从d维决策表的0层到(b-1)层学习了b个测试，那么这时需要在b层找到一个最佳测试。一个候选测试xj《t将把这一级的2b结点分成2b+1结点。在所有的候选测试中，最优测试是具有最小得分的测试。得分的定义为：[0045][0046]其中，[0047][0048]是结点的不纯度，分别是分裂后第q个结点的左右子结点关联的样本集。[0049]3、加性秘密共享[0050]在本发明中，使用环上的加性秘密共享，其中q代表用于表示数值的位数。在这样的秘密共享中，一个秘密值被加性地拆分为n个秘密共享份额以满足[[x]]＝《x》1+《x》2+…+《x》nmod2q，而这n个份额由n方分别持有。为简单起见，用[[x]]表示加法秘密共享的x。下面介绍在n方场景下与加法秘密共享有关的基本操作。[0051]共享(sharing):为了加性地分享pl一方的私有值x，pl需要生成n-1个随机数{xm}，m∈[1，n]，m≠l，并将xm发送给对应的pm。然后pl持有其他每个参与者pm∈[1,n],m≠l分别持有《x》m＝xm，作为x的一个秘密共享份额。为简洁起见，我们将在下面的协议中省略模运算记号。[0052]重建(reconstruction)：为了在pl上重建(rec(·))共享值[[x]]，除pl外每个其他参与者pm∈[1,n],m≠l将其秘密共享份额《x》m发送给pl，随后pl计算[0053]加法(addition)：对于两个秘密共享的值[[x]]和[[y]]，为了安全地计算加法([[z]]＝[[x]]+[[y]])，每个参与者pm∈[1,n]本地计算《z》m＝《x》m+《y》m。同样，为了计算减法([[z]]＝[[x]]-[[y]])，每个参与者从x的份额中减去y的份额。[0054]乘法(multiplication)：要将一个秘密共享值[[x]]与一个常数c相乘([[z]]＝c×[[x]])，每个参与者可以直接将其本地的x的份额乘以c。要将两个秘密共享值[[x]]和[[y]]相乘，则可以使用乘法三元组。在离线阶段，所有各方都得到一个秘密共享的乘法三元组([[a]]，[[b]]，[[c]])，其中a,b是中的均匀随机数，满足c＝ab。秘密共享三元组是独立于数据的，可以由第三方离线准备和分发，所以此后假设三元组可用于各方之间的在线安全计算。秘密共享的乘法过程如下：首先，每一方pm∈[1,n]本地计算《e》m＝《x》m-《a》m和《f》m＝《y》m-《b》m。之后，双方运行rec([[x]])、rec([[y]])。接下来，pm计算《z》m＝j×e×f+f×《a》m+e×《b》m+《c》m，其中j＝1，如果m＝1，那么j＝0。最后，pm将《z》m作为乘法结果的秘密分享份额。[0055]本发明提供的方法，可以应用于云计算领域，用于解决多个参与方(例如商业组织)在垂直划分的数据上协作训练梯度提升决策表时无法实现隐私保护的问题。在这样的场景下，一个包含n个样本(每个样本都与一个特征向量和一个标签相关联)的数据集在n个参与方的终端p1,p2,...,pn之间垂直划分。每个参与终端pm持有其各自的数据集其中jm代表pm拥有的特征数目并且满足拥有的特征数目并且满足代表中的第i个样本。也就是说，本发明提供的方法，应用于包括多个参与终端的系统中，每个参与终端持有每个学习样本的部分特征数据，且各个参与终端持有的特征数据的类别不同。用代表样本的标签集，根据之前关于垂直联邦学习的工作，考虑参与者的两种角色：主动参与者(ap)和被动参与者(pp)。具体来说，有一个持有本地数据集和标签集y的ap；其余的参与者是pp，每个pp只持有一个本地数据集。[0056]在本发明的整个安全训练过程中，每个参与终端都将其特征数据保存在本地。本发明中的隐私保护技术可以以避免数据泄露的方式学习决策表中的布尔测试和输出值，在整个训练过程中以及训练完毕后，没有任何一个参与者可以获得完整的模型，实现了数据隐私保护的效果。在本发明中，所有参与终端都知道训练所得是梯度提升决策表中每个测试的分裂特征以及谁拥有该特征，但只有拥有该特征的参与终端知道测试的分裂阈值。从形式上而言，对于集成中第t个决策表(t∈[1,t])的第d层(d∈[0,d-1])的布尔测试fd《td，分裂特征fd的特征类型向所有参与终端公开，具体特征数据只有一个参与终端持有，对应的阈值td也只有拥有fd的参与终端持有。此外，叶结点的所有输出值在所有参与终端之间以秘密共享的形式保存。[0057]基于本发明提供的方法，可以在半诚实敌手模型中实现隐私保护，具体而言，假定每个参与终端都遵循协议规范，但可能会尝试推断其他参与终端的隐私信息，同时，尽管为参与终端考虑了两个角色ap和pp，但是并不假定会给予ap额外的信任，因为联邦学习旨在打破组织之间的数据孤岛，其中每个组织的行为都严格遵守隐私法规，所以半诚实的对手模型是一个合理的设置，此外，本发明还可以支持在存在一个可以侵占高达n-1个参与终端的静态敌手的情况下，确保每个参与终端的本地数据和学习到的部分模型(集成模型中每个决策表的布尔测试和输出值)不会被泄露给其他参与终端。本发明中并不隐藏与数据无关的通用参数，例如决策表的维度d和数量t。[0058]下面结合图3-图9描述本发明提供的基于梯度提升决策表的隐私保护垂直联邦学习方法。[0059]首先简单介绍本发明提供的方法的总体框架，本发明提供的方法，应用于包括点多个参与终端的系统中，每个参与终端持有每个学习样本的部分特征数据，且各个参与终端持有的特征数据的类别不同，如图4所示，每个参与终端输入垂直分类的数据集和标签集y，从而输出分布式决策表集合ε。开始时，加密的预测结果被初始化为秘密共享[[on]]，ap将其标签集的秘密共享分配给其他参与终端。之后，t个决策表在t轮中被安全地建立。本发明提供的方法支持在每一轮中对单一(分布式)决策表进行安全训练，可以看做主要由三个组件组成，主要包括(i)安全结点分裂secsplit，(ii)安全sigmoid函数计算secsigmoid，和(iii)安全离散化secdisc。安全结点分裂是为了安全地拆分某一级别的结点，并对与这些结点相关的样本集进行分裂，同时不泄露分裂后的样本集。安全sigmoid函数计算过程是输入一个秘密共享的值并计算秘密共享域中的sigmoid函数。安全离散化是根据每个参与者拥有的本地置换安全地重新排列秘密共享的梯度，然后将它们分组到桶中。通过这些方式，本发明提供的方法允许参与终端在每一轮中安全地训练一个分布式决策表。在某一轮安全地训练分布式决策表后，需要进行安全预测，其结果将被聚合到之前的预测结果中，以便在下一轮中用于决策表训练。为此，本发明提供的方法还提供一种安全地基于决策表的预测结果获取方式，可以实现输入每个参与者的本地数据和部分模型，以产生秘密共享的预测结果，而不泄露它们的数据和部分模型。值得注意的是，除了在训练过程中，本发明提供的方法中的预测结果获取方式也可用于支持整个训练过程完成后的新数据的安全预测。[0060]如图3所示，本发明提供的方法，包括步骤：[0061]s100、各个参与终端中的第一目标参与终端基于本地持有的各个学习样本的第一目标特征数据以及目标决策表中第一目标层对应的最优测试，确定第一目标层对应的指示向量，其中，目标决策表为当前学习轮次中需要学习的决策表，目标特征数据与第一目标层对应，第一目标参与终端持有第一目标层对应的第一目标特征数据，指示向量用于反映第一目标层中每个结点对应的样本被划分至结点的第一子结点或第二子结点，目标决策表中每一层对应的最优测试用于确定层中每个样本的划分结果；[0062]s200、第一目标参与终端生成指示向量对应的n个第一加性秘密共享份额，将n-1个第一加性秘密共享份额分别发送至系统中其余的参与终端，其中，n为参与终端的个数；[0063]s300、每个参与终端基于本地持有的各个第一加性秘密共享份额更新本地持有的第二目标层中的各个结点分别对应的第二加性秘密共享份额和第三加性秘密共享份额，其中，第二目标层为目标决策表中第一目标层的子结点所在的层，第二加性秘密共享份额为一阶梯度向量的加性秘密共享份额，第三加性秘密共享份额为二阶梯度向量的加性秘密共享份额，当第i个学习样本被划分至目标结点时，目标结点对应的一阶梯度向量中的第i个值为第i个学习样本当前的一阶梯度值，其余值为0，目标结点对应的二阶梯度向量中的第i个值为第i个学习样本当前的二阶梯度值，其余值为0。[0064]正如前文中对决策表的明文学习过程所说明的，oblivioustree通过将当前层的每个结点拆分为两个子结点来增长到新的一层，在明文决策表学习中，结点分裂是通过划分与待分裂结点相关的样本来进行的，然而，在垂直联邦学习中，由于所有参与者持有的样本空间相同，样本的划分方式必须想所有参与者公开，例如，给定一个测试“身高《180”，拥有“身高”特征数据的参与者需要告诉其他参与者哪些样本小于180，哪些样本大于180，否则持有下一层的特征数据的参与者无法进行进一步划分，这将泄露每个样本的“身高”范围，造成隐私隐患。为了避免这种泄露，本发明提供的方法中，通过安全的节点分裂分裂方式(称为secsplit)来实现特征数据的隐私保护。具体地，在本发明提供的方法中，每一个结点都关联一个一阶梯度向量和一个二阶梯度向量，即将oblivioustree第d层(d∈[0，d-1])的第k个结点(k∈[0，2d-1])与一个一阶梯度向量[[g(k,d)]]和一个二阶梯度向量[[h(k,d)]]相关联，每个向量包含n个元素，在所有参与终端pm∈[1,n]之间秘密共享。如果第i个样本被划分到这个结点，[[g(k,d)]]和[[h(k,d)]]中的第i个元素将被分别设置为第i个样本的一阶和二阶梯度，否则第i个元素将被设置为[[0]]。由于不被划分到结点的梯度向量中的元素被设置为0，因此即使这些元素参与了运算，也不会对最终结果的准确性造成性影响。[0065]如图5所示，基于每个结点关联一个一阶梯度向量和一个二阶梯度向量的设置，安全结点分裂的过程如下：[0066]在第d层(第一目标层)拥有最优测试fd《td的参与终端(即第一目标参与终端)pl在本地生成第一指示向量vl和第二指示向量vr，然后将其秘密共享给其他参与终端(表示为[[vl]]和[[vr]])。也就是说，指示向量包括第一指示向量和第二指示向量，当第i个学习样本被划分至所属结点的第一子结点时，第一指示向量中第i个值为1，否则为0，当第i个学习样本被划分至所属结点的第二子结点时，第二指示向量中第i个值为1，否则为0。具体地，如图2所示，在决策表对应的决策树中，每个结点会分裂为两个结点，这两个结点是分裂的结点的子结点，所以根据第一目标层的最优测试，所有的学习样本会有两种划分情况：划分到第一子结点(可以为左子结点)或者第二子结点(可以为右子结点)。[0067]在收到[[vl]]和[[vr]]后，对于第二目标层的第k个结点，pm∈[1,n]更新第k个结点左右子结点的一阶和二阶梯度向量。更新是通过加密指示向量和梯度向量之间的安全元素乘法实现的。即每个参与终端基于本地持有的各个第一加性秘密共享份额更新本地持有的第二目标层中的各个结点分别对应的第二加性秘密共享份额和第三加性秘密共享份额，包括：[0068]当第二目标层中的目标结点为第一子结点时，各个参与终端基于加性秘密共享协议计算第一指示向量与目标结点对应的一阶梯度向量的乘积的秘密共享份额作为更新后的目标结点对应的第二加性秘密共享份额，计算第一指示向量与目标结点对应的二阶梯度向量的乘积的秘密共享份额作为更新后的目标结点对应的第三加性秘密共享份额；[0069]当第二目标层中的目标结点为第二子结点时，各个参与终端基于加性秘密共享协议计算第二指示向量与目标结点对应的一阶梯度向量的乘积的秘密共享份额作为更新后的目标结点对应的第二加性秘密共享份额，计算第二指示向量与目标结点对应的二阶梯度向量的乘积的秘密共享份额作为更新后的目标结点对应的第三加性秘密共享份额。[0070]这样，由于被划分到右子结点的学习样本在第一指示向量中对应的元素为0，也就是说，左子结点对应的一阶梯度向量中被划分到右子结点的学习样本对应的值会变为0，相当于将其排除出左子结点对应的样本集合。这种设计隐藏了每个结点处理的样本集，每个结点处理的样本数保持不变为n，这意味着除了持有本层最优测试的参与终端之外，其余的参与终端无法从结点分裂中推断出任何信息。[0071]可以理解的是，在训练第一个决策表时，由于其没有前序预测过程，所以不能通过前次的预测结果得到每个学习样本的一阶梯度和二阶梯度，此时可以对一阶梯度向量和二阶梯度向量进行随机初始化，或者直接置为0。[0072]再次参阅图3，本发明提供过的方法，还包括步骤：[0073]s400、各个参与终端中的第二目标参与终端基于本地持有的第二加性秘密共享份额和第三加性秘密共享份额，在秘密共享域计算各个候选测试对应的评价分数，第二目标参与终端基于评价分数的秘密共享份额确定第二目标层对应的最优测试，其中，第二目标参与终端持有第二目标层对应的第二目标特征数据。[0074]一种简单的查找最优测试的方法，是采用贪心算法来枚举每个训练样本以找到最佳测试，但是，枚举所有训练样本会产生大量的计算开销，还会产生分布式环境中昂贵的通信开销，降低系统的效率。本发明提供的方法，采用安全的离散化学习(简称为secdisc)来使得本发明能够适应更大的数据集。[0075]具体地，各个参与终端中的第二目标参与终端基于本地持有的第二加性秘密共享份额和第三加性秘密共享份额，在秘密共享域计算各个候选测试对应的评价分数，包括：[0076]第二目标参与终端对本地持有各个学习样本的第二目标特征数据进行排序，得到第一排序结果，其中，第二目标参与终端持有第二目标层对应的第二目标特征数据；[0077]第二目标参与终端基于第一排序结果和其余各个参与终端协同更新本地持有的第二目标层中每个结点对应的第二加性秘密共享份额和第三加性秘密共享份额，以实现对第二目标层中每个结点对应的一阶梯度向量和二阶梯度向量中的梯度值的重排序，使得一阶梯度向量和二阶梯度向量中的梯度值的排序结果与第一排序结果一致；[0078]每个参与终端基于预设的桶数量对本地持有的一阶梯度向量和二阶梯度向量中的各个梯度值进行分桶，得到各个桶的秘密共享份额，每个桶中包括多个按顺序排列的一阶梯度值和二阶梯度值；[0079]每个参与终端基于本次持有的各个桶的秘密共享份额，确定每个候选测试对应的评价分数的秘密共享份额，其中，每个候选测试的阈值为第一梯度值和第二梯度值分别对应的第二目标特征数据中的一个，或第一梯度值和第二梯度值分别对应的第二目标特征数据之间的一个值，第一梯度值为第一桶中的最后一个一阶梯度值或二阶梯度值，第二梯度值为第二桶中的第一个一阶梯度值或二阶梯度值，第一桶为相邻的两个桶中的前一个桶，第二桶为相邻的两个桶中的后一个桶。[0080]离散化，也称为分桶，是大规模机器学习中常用的方法。具体来说，离散化将样本分组到少量的桶中，以便允许模型训练支持更大的数据集。令b表示离散化中的桶数，其中b＜＜n，n是样本数。在梯度提升中，梯度被分组到桶中，在训练阶段需要计算每个桶中的梯度总和。通常，对于每个特征，梯度首先由排列π排列，该排列通过对该特征的值进行排序获得的。然后将置换后的梯度划分到b个桶中。显然，装桶操作可以大大降低训练的成本。然而，离散化在隐私保护机器学习中并不容易。在本发明中，训练数据是垂直分区的，因此排序过程可以在本地实现，以减少开销。具体地，在本发明中，秘密共享的梯度被安全地离散成b个桶，并分别存储在秘密共享的向量[[αk,d]]和[[βk,d]]中。b个桶中有b-1个间隔，每个间隔对应一个候选测试。这样，本发明只需要从每个特征的b-1个候选测试中选择最佳测试，而不是枚举n个样本，从而节省了大量的计算和通信成本。在本发明中，为每个特征初始化一个秘密共享的向量[[θ]]＝[[0b-1]]，以存储b-1个候选测试的分数。[0081]可以理解，当需要学习第二目标层对应的最优测试时，如果采用离散化学习，那么第二目标参与终端需要对持有的第二目标特征数据进行排序之后，将对应的梯度向量也排序，但是，梯度向量是以秘密共享的方式被所有的参与终端持有，所以需要其他的参与终端也对本次持有的梯度向量的秘密共享份额进行重排序，但是，在不向其他参与终端透露π的情况下，很难通过参与终端pl持有的置换π来置换秘密共享梯度向量。为了解决这个问题，本发明提供的方法中，采用一种安全置换方式，简称为secperm，如图6所示，在secperm开始时，各参与终端pm∈[1,n]持有一个秘密向量[[x]]，pl持有一个排列π。在secperm结束时，参与终端pm∈[1,n]持有一个秘密向量[[u]]，其中u＝π(x)。secperm保证除了pl之外，其他参与终端无法知道排列π。secperm中的初始化由第三方(称为协调者终端)离线完成。具体来说，协调者终端首先将πp(r)和r的秘密份额分发给所有参与者，然后将πp发给pl。初始化后，所有参与者在2轮中协作排列[[x]]。在第一轮中，pl生成排列πs，其满足π(·)＝πs[πp(·)]。然后pl将πs发送给所有其他参与终端。之后，每个参与终端pm∈[1,n]在本地计算《x》m-《y》m。在第二轮中，x-r被透露给pl。最后，参与者输出[[u]]＝[[π(x)]]。secperm的正确性分析如下：[0082]u＝《u》1+《u》2+…+《u}l+…+《u＞n[0083]＝πs(《πp(r)》1)+πs(《πp(r)》2)+…+π(x-r)+πs(《πp(r)》1)+…+πs(《πp(r)》n)[0084]＝π(x-r)+πs(πp(r))[0085]＝π(x-r)+π(r)[0086]＝π(x)[0087]如图7所示，在本发明提供的安全离散化过程中，首先使用secperm，基于第二目标参与终端持有的置换π进行安全置换，然后将梯度划分到b个桶中。在开始时，加密的一阶梯度向量和二阶梯度向量[[g]]和[[h]]被secperm安全地置换。基于secperm，第二目标参与终端基于第一排序结果和其余各个参与终端协同更新本地持有的第二目标层中每个结点对应的第二加性秘密共享份额和第三加性秘密共享份额，包括：[0088]将第二加性秘密共享份额和第三加性秘密共享份额分别作为目标共享份额，目标共享份额基于如下的步骤实现更新：[0089]辅助终端生成随机向量和随机排序规则，基于随机排序规则对随机向量中的值进行排序，得到辅助排序向量，将n个第五秘密共享份额和n个第六秘密共享份额分别发送至各个参与终端，将辅助排序向量发送至第二目标参与终端，第五秘密共享份额为随机向量的加性秘密共享份额，第六秘密共享份额为辅助排序向量的加性秘密共享份额；[0090]参与终端在本地计算本地持有的目标共享份额和第五秘密共享份额的第一差值向量，第二目标参与终端接收其余参与终端发送的第一差值向量，在本地获取第二差值向量，第二差值向量为目标共享份额对应的明文向量与随机向量的差值向量；[0091]第二目标参与终端生成辅助排序规则，将辅助排序规则发送至其余的参与终端，辅助排序规则满足条件：按照辅助排序规则对辅助排序向量进行重排序后得到随机向量；[0092]第二目标参与终端之外的参与终端根据辅助排序规则对本地持有的第六秘密共享份额进行重排序，将重排序后的第六秘密共享份额作为更新后的目标共享份额；[0093]第二目标参与终端对第二差值向量按照第一排序结果对应的排序规则进行排序，将排序后的第二差值向量作为更新后的目标共享份额。[0094]之后，对于b∈[0,b-1]，第b个桶的加密分组一阶和二阶梯度按如下方式计算：[0095][0096]其中m＝n/b是桶中梯度的数量。为了简洁起见，假设n可以被b整除。由于无效梯度设置为[[0]]，桶中的加密梯度之和等于明文中的梯度之和。[0097]第二目标参与终端基于评价分数的秘密共享份额确定第二目标层对应的最优测试，包括：[0098]所有的参与终端基于评价分数的秘密共享份额确定各个评价分数之间的比较结果的秘密共享份额；[0099]第二目标参与终端基于评价分数之间的比较结果的秘密共享份额确定最优测试的序号，第二目标参与终端基于最优测试的序号，在第一排序结果中查找第一梯度值和第二梯度值，基于第一梯度值和第二梯度值确定最优测试对应的阈值，以确定最优测试。[0100]在安全地将梯度离散为b个桶之后，对b-1个候选测试进行评估，以选择第j个特征的最佳测试。第c个候选测试对应的评价分数通过基于前c个桶中的梯度值计算得到的不纯度和基于后b-c个桶中的梯度值计算得到的不纯度确定，c为正整数，b为桶数量。具体地，对于第c个候选测试(c∈[1,b-1])，前c个桶被聚合，得到[[gl]]和[[hl]]，这是与左子结点相关的梯度总和，其余的b-c个桶被聚合，得到[[gr]]和[[hr]]，这是与右子结点相关的梯度总和。每个结点的两个子结点的不纯度按照公式6进行安全计算，然后将这些不纯度聚合到一起，按照公式5产生第c个候选测试的加密得分。然后，对于第j个特征，将有b-1个加密的分数存储在[[θ]]中。[0101]公式6中存在除法，除法在加性秘密共享域中不被天然的支持，本发明提供的方法中，提出了一个安全除法组件sdiv，将除法计算转化为一个数值优化问题，具体来说，在给定[[x]]和[[y]]的情况下，计算的核心障碍是计算加密的倒数因此，首先通过newton-raphson算法对进行近似，沿用以前的工作：进行近似，沿用以前的工作：结果最终将收敛为在本发明中，固定初始值其中y是一个足够大的值。需要注意的是，近似计算仅包括基本的减法和乘法运算，这些运算在秘密共享域中是自然支持的，因此，给定[[y]]，加密的倒数可以被安全地计算。在安全地计算出倒数后，用[[x]]乘以得到[0102]第二目标参与终端基于评价分数的秘密共享份额确定第二目标层对应的最优测试，包括：[0103]所有的参与终端基于评价分数的秘密共享份额确定各个评价分数之间的比较结果的秘密共享份额；[0104]第二目标参与终端基于评价分数之间的比较结果的秘密共享份额确定最优测试的序号，第二目标参与终端基于最优测试的序号，在第一排序结果中查找第一梯度值和第二梯度值，基于第一梯度值和第二梯度值确定最优测试对应的阈值，以确定最优测试。[0105]在得到b-1个得分后，需要选择得分最小的最佳测试，这就需要一种方法来安全地计算秘密共享向量中最小值的索引。为了应对这一挑战，本发明引入了一个组件secargmin。注意到，从秘密共享向量中选择最小值需要安全比较操作，但它在秘密共享领域中没有得到自然支持。因此，给定两个秘密共享的值[[a]]和[[b]]，首先将[[a-b]]分解为比特，然后将这些比特输入并行前缀加法器(ppa)，以安全地计算[[a-b]]的加密最高位(msb)。之后，将加密的msb转换成算术秘密共享值，从而得到安全比较的加密结果。也就是说，所有的参与终端基于评价分数的秘密共享份额确定各个评价分数之间的比较结果的秘密共享份额，包括：[0106]所有的参与终端基于如下步骤确定第一评价分数和第二评价分数的比较结果：[0107]所有的参与终端基于本地持有的第一评价分数和第二评价分数的加性秘密共享份额，获取分数差值的加性秘密共享份额，分数差值为第一评价分数和第二评价分数的差值；[0108]所有的参与终端将本地持有的分数差值的加性秘密共享份额转换为比特值，通过前缀加法器得到分数差值的最高位的加性秘密共享份额作为第一评价分数和第二评价分数的比较结果的秘密共享份额。[0109]基于上面介绍的安全比较方法，secargmin输入加密的向量[[θ]]，然后输出明文中第j个特征的最佳测试所对应的桶id，也可称为桶序号，桶序号q∈[0,b-2]。在本发明中，所有参与终端都可以在训练阶段学习所产生的桶id，但只有拥有第j个特征的参与终端可以得到第j个特征的最佳测试的阈值。由于第j个特征的值(表示为)是按升序排序的，拥有第j个特征的参与终端可以通过查找索引为(q+1)×(n/b)的排序值(即πj[d(j)])来获得分裂阈值。其他参与终端无法推导出分裂阈值，因为第j个特征被其所有终端保存在本地，其他参与终端无法得到。[0110]如图8所示，结合前文所说明的，本发明提供的方法中决策表的训练过程可以概括为：pm∈[1,n]计算秘密共享的一阶和二阶梯度向量(针对根结点)(即图8中第1-6行的[[g]]和[[h]])。在计算完秘密共享的梯度后，我们初始化一个秘密向量以存储2d个秘密共享的输出值。之后，按层建立一个决策表。与图1中find_split的功能类似，本发明在第d层(d∈[0,d-1])安全地选择最优测试fd《td。具体来说，首先为每个特征选择最佳测试(即图8中第10-25行)，然后在选择的j个候选测试中选择最佳测试(即图8中第26-28行)。值得注意的是，这里的选择是按照明文域的选择进行的，不过选择中的计算被替换为安全计算和设计的组件。对于j个候选测试，初始化一个秘密共享的向量[[σ]]＝[[0j]]来存储每个特征的最佳测试的得分。此外，本发明还使用一个公开的向量γ＝0j来记录每个特征的最佳测试的桶id。为了选择所有特征的最佳测试，本发明让参与终端在γ和[[σ]]的第j个位置分别记录第j个特征的最佳桶序号q和加密的最小分裂分数[[θq]](即图8的第23-24行)。回顾一下，对于j个特征，用γ和[[σ]]来存储每个特征的最佳测试的桶id和分裂分数。γ和[[σ]]的j个索引分别对应于j个特征。在枚举完j个特征后，j个分数被存储在[[σ]]中，需要对[[σ]]再次调用secargmin。输出结果是最优测试的分裂特征fd，所有参与终端都知道。然后，可以用fd从γ中检索到分裂特征的最优桶id(qd)(图8第27行)。之后，拥有分裂特征fd的参与终端查找其排序值索引为(qd+1)×(n/b)，得到分裂阈值td。在学习了第d个测试fd《td之后，拥有fd《td的参与终端与其他参与终端合作，用secsplit安全地分裂第d层的所有结点，以创建一个新的层次(图8中第29行)。本发明中的决策表是以这种方式逐层学习的。在第d层，本发明按照公式3安全地计算叶子结点的输出值(即图8中的第31-34行)，其中分裂是用sdiv安全地计算的。最后，sectable输出一个由d个测试和2d个秘密共享的输出值组成的分布式决策表。具体来说，所有参与终端都知道第d级的分裂特征fd，其中d∈[0,d-1]，但每个分裂阈值td只对拥有特征fd的参与终端可见。[0111]如图3所示，本发明提供的方法，还包括步骤：[0112]s500、在目标决策表的每个层的最优测试均被确定后，完成当前学习轮次，基于已被学习的决策表，各个参与终端获取各个学习样本的预测结果的第四加性秘密共享份额，并基于第四加性秘密共享份额得到下一学习轮次中被学习的决策表中第一个结点对应的第二加性秘密共享份额和第三加性秘密共享份额，直到已被学习的决策表的数量达到预设数量，以完成学习过程[0113]在本发明中，在安全训练阶段学到的集合中的每个决策表都由参与终端以分布式方式持有，每个参与终端持有其中的一部分。载这种设置下，需要考虑如何让参与终端安全地使用模型进行预测。同时，预测用的数据在垂直联邦学习的参与终端之间也是垂直分裂的，因此也需要被保护。为了防止每个参与终端的模型信息和用于预测的数据泄露，本发明提出一个安全预测算法secinfer，如图9所示。secinfer允许参与终端利用分布式的梯度提升决策表集合对其本地数据进行安全预测，并产生秘密共享的预测结果，同时在整个预测过程中保持本地数据对其他参与终端不可用。[0114]各个参与终端获取各个学习样本的预测结果的第四加性秘密共享份额，包括：[0115]持有目标决策表的分裂层对应的特征数据的参与终端生成目标学习样本在分裂层对应的叶指标向量，其中，分裂层为目标决策表中具有子结点的层，叶指标向量用于表示目标学习样本被划分至分裂层中的结点的第一子结点或第二子结点，叶指标向量中的元素个数等于已被学习的决策表中结点最多的一层中结点的个数；[0116]持有分裂层对应的特征数据的参与终端对叶指标向量进行加密，将叶指标向量的加性秘密共享份额发送至其余的参与终端；[0117]所有的参与终端基于本地持有的加性秘密共享份额，获取目标学习样本在各个分裂层对应的叶指标向量的乘积结果的加性秘密共享份额作为目标决策表对应的预测结果分值的秘密共享份额；[0118]所有的参与终端基于加性秘密共享将所有的已被学习的决策表对应的预测结果分值进行聚和，得到目标学习样本对应的第四加性秘密共享份额。[0119]持有分裂层对应的特征数据的参与终端生成目标学习样本在分裂层对应的叶指标向量，包括：[0120]持有分裂层对应的特征数据的参与终端基于本地持有的分裂层的最优测试和目标学习样本对应的特征数据，确定目标学习样本被划分至分裂层中的结点的第一子结点或第二子结点；[0121]当目标学习样本被划分至分裂层中的结点的第一子结点时，分裂层对应的叶指标向量中的各个元素组中的第一个元素为1，第二个元素为0；[0122]当目标学习样本被划分至分裂层中的结点的第二子结点时，分裂层对应的叶指标向量中的各个元素组中的第一个元素为0，第二个元素为1；[0123]其中，分裂层对应的叶指标向量中包括2d个元素组，每个元素组中包括两个元素，d为分裂层在所述目标决策表中的层序号，d∈[0,d-1]，d为所述目标决策表的层数。[0124]具体来说，为了安全地对垂直划分的样本进行预测，在第d层(d∈[0,d-1])拥有测试fd《td的参与终端pl通过比较样本的fd的特征值(表示为)与分裂阈值td，在本地生成一个叶指示向量(表示为ud)。之后，叶指示向量ud被秘密分享给其他参与终端。然后，预测结果可以通过d个加密的叶指示向量和决策表的输出值的加密向量[[w]]之间的安全元素乘法而被安全地计算。以样本(“身高＝175”，“体重＝55”，“工资＝11000”)的预测为例。这三个特征被垂直分裂，分别由三个参与方持有。对于第一个测试“身高《170”，p1在本地将“身高＝175”与阈值170进行比较，因为175》170，p1生成叶指标向量u0＝(0,0,0,0,1,1,1,1)以指示预测路径。类似地，可以得到u1＝(1,1,0,0,1,1,0,0)和u2＝(0,1,0,1,0,1,0,1)。然后，每个叶指标向量被所有参与终端秘密共享。虽然本发明中决策表是分布式并且加密的，但是它们的逻辑结构保持不变，因此不同层的操作仍然可以被并行化。在秘密共享叶指标向量之后，这个样本的预测结果可以通过矩阵元素乘进行计算。这样一来，每个参与终端都不会知道在安全预测过程中使用了分布式决策表中的哪条路径，因此预测过程和预测结果都受到保护。[0125]需要指出的是，secinfer也可以在安全训练阶段使用。也就是说，在某一轮安全训练分布式决策表后，可以使用secinfer对每个训练样本产生加密的预测结果。这一轮的预测结果将被聚合到以前的预测结果中，来为下一轮建立新的决策表计算梯度。在整个安全训练过程中，集合中决策表的聚合预测结果被保存在秘密共享域中。而在安全预测过程中，所有t个决策表的最终聚合预测结果会公开给所有参与终端。[0126]在学习过程中，获得预测结果之后，基于预测结果计算下一轮决策表学习中需要使用的一阶梯度和二阶梯度。而一阶梯度和二阶梯度的计算过程中，可能需要用到sigmoid函数，sigmoid函数中包括除法和指数运算，安全的除法运算在前文中已经说明过，对于计算给定秘密共享值[[x]]的指数[[ex]]，本发明通过极限来近似需要注意的是，由于近似计算包括基本的加法和乘法运算，这些运算在秘密共享域中自然支持，给定[[x]]，加密的指数[[ex]]可以被安全地计算。然而，近似方法需要2n次链式乘法，因此需要2n轮在线通信。近似方法在实践中是低效的，因为通信复杂度会呈指数级增长。因此，本发明将指数级的通信复杂度进一步降低为线性通信。更具体地说，注意到近似中的计算可以视为其中因此，给定[[a]]，本发明首先安全地计算出[[a2]]，这只需要一轮通信。之后，本发明将输出视为[[y]]＝[[an]]，然后安全地计算[[y2]]，这也只需要一轮通信。因此，通过这种方式，可以安全地在log2n＝n轮而不是2n轮中计算[0127]综上所述，本发明提供的基于梯度提升决策表的隐私保护垂直联邦学习方法，为决策表中的每个结点维护一个对应的梯度向量，每个参与终端持有梯度向量的加性秘密共享份额，而持有一种完整特征数据的参与终端，通过生成指示向量，将指示向量的加性秘密共享份额发送给各个参与终端，各个参与终端通过指示向量来更新下一层结点的梯度向量的秘密共享份额，使得结点的子结点对应的梯度向量中没有被划分至该子结点的样本对应的值为0，划分至该子结点的样本对应的值为1，实现了每个结点处理的样本数保持不变，除了持有该完整特征数据的终端，所有的参与终端都无法从结点分裂中推断出任何信息，包括该完整特征数据的最优测试阈值，以及哪些样本的特征数据小于或大于这个阈值，进一步地，本发明提供的方法中各个参与终端还基于加性秘密共享确定决策表中的每一层的最佳测试的阈值的加性秘密共享份额，以及确定学习样本的预测结果的加性秘密共享份额，用于下一轮决策表的学习，在学习的全部过程中，所有的中间数据都是被加密的，每个参与终端只能获取到数据的加性秘密共享份额，而无法获取到完整的明文数据，因此，本发明可以实现对基于梯度提升决策表的隐私保护垂直联邦学习数据的隐私保护。[0128]下面对本发明提供的基于梯度提升决策表的隐私保护垂直联邦学习系统进行描述，下文描述的基于梯度提升决策表的隐私保护垂直联邦学习系统与上文描述的基于梯度提升决策表的隐私保护垂直联邦学习方法可相互对应参照。[0129]本发明提供的基于梯度提升决策表的隐私保护垂直联邦学习系统包括多个参与终端，多个参与终端协同完成如上所述的基于梯度提升决策表的隐私保护垂直联邦学习方法。[0130]通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到各实施方式可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件。基于这样的理解，上述技术方案本质上或者说对现有技术做出共享的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在计算机可读存储介质中，如rom/ram、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行各个实施例或者实施例的某些部分所述的方法。[0131]最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。当前第1页12当前第1页12
技术特征：
1.一种基于梯度提升决策表的隐私保护垂直联邦学习方法，其特征在于，所述方法应用于包括多个参与终端的系统中，每个所述参与终端持有每个学习样本的部分特征数据，且各个所述参与终端持有的特征数据的类别不同；所述方法包括：各个所述参与终端中的第一目标参与终端基于本地持有的各个所述学习样本的第一目标特征数据以及目标决策表中第一目标层对应的最优测试，确定所述第一目标层对应的指示向量，其中，所述目标决策表为当前学习轮次中需要学习的决策表，所述目标特征数据与所述第一目标层对应，所述第一目标参与终端持有所述第一目标层对应的所述第一目标特征数据，所述指示向量用于反映所述第一目标层中每个结点对应的样本被划分至结点的第一子结点或第二子结点，所述目标决策表中每一层对应的最优测试用于确定层中每个样本的划分结果；所述第一目标参与终端生成所述指示向量对应的n个第一加性秘密共享份额，将n-1个所述第一加性秘密共享份额分别发送至所述系统中其余的所述参与终端，其中，n为所述参与终端的个数；每个所述参与终端基于本地持有的各个所述第一加性秘密共享份额更新本地持有的第二目标层中的各个结点分别对应的第二加性秘密共享份额和第三加性秘密共享份额，其中，所述第二目标层为所述目标决策表中所述第一目标层的子结点所在的层，所述第二加性秘密共享份额为一阶梯度向量的加性秘密共享份额，所述第三加性秘密共享份额为二阶梯度向量的加性秘密共享份额，当第i个所述学习样本被划分至目标结点时，所述目标结点对应的所述一阶梯度向量中的第i个值为第i个所述学习样本当前的一阶梯度值，其余值为0，所述目标结点对应的所述二阶梯度向量中的第i个值为第i个所述学习样本当前的二阶梯度值，其余值为0；各个所述参与终端中的第二目标参与终端基于本地持有的所述第二加性秘密共享份额和所述第三加性秘密共享份额，在秘密共享域计算各个候选测试对应的评价分数，所述第二目标参与终端基于所述评价分数的秘密共享份额确定所述第二目标层对应的最优测试，其中，所述第二目标参与终端持有所述第二目标层对应的第二目标特征数据；在所述目标决策表的每个层的最优测试均被确定后，完成所述当前学习轮次，基于已被学习的决策表，各个所述参与终端获取各个所述学习样本的预测结果的第四加性秘密共享份额，并基于所述第四加性秘密共享份额得到下一学习轮次中被学习的决策表中第一个结点对应的所述第二加性秘密共享份额和所述第三加性秘密共享份额，直到已被学习的决策表的数量达到预设数量，以完成学习过程。2.根据权利要求1所述的基于梯度提升决策表的隐私保护垂直联邦学习方法，其特征在于，所述指示向量包括第一指示向量和第二指示向量，当第i个所述学习样本被划分至所属结点的所述第一子结点时，所述第一指示向量中第i个值为1，否则为0，当第i个所述学习样本被划分至所属结点的所述第二子结点时，所述第二指示向量中第i个值为1，否则为0；所述每个所述参与终端基于本地持有的各个所述第一加性秘密共享份额更新本地持有的第二目标层中的各个结点分别对应的第二加性秘密共享份额和第三加性秘密共享份额，包括：当所述第二目标层中的目标结点为所述第一子结点时，各个所述参与终端基于加性秘密共享协议计算所述第一指示向量与所述目标结点对应的所述一阶梯度向量的乘积的秘
密共享份额作为更新后的所述目标结点对应的所述第二加性秘密共享份额，计算所述第一指示向量与所述目标结点对应的所述二阶梯度向量的乘积的秘密共享份额作为更新后的所述目标结点对应的所述第三加性秘密共享份额；当所述第二目标层中的目标结点为所述第二子结点时，各个所述参与终端基于加性秘密共享协议计算所述第二指示向量与所述目标结点对应的所述一阶梯度向量的乘积的秘密共享份额作为更新后的所述目标结点对应的所述第二加性秘密共享份额，计算所述第二指示向量与所述目标结点对应的所述二阶梯度向量的乘积的秘密共享份额作为更新后的所述目标结点对应的所述第三加性秘密共享份额。3.根据权利要求1所述的基于梯度提升决策表的隐私保护垂直联邦学习方法，其特征在于，各个所述参与终端中的第二目标参与终端基于本地持有的所述第二加性秘密共享份额和所述第三加性秘密共享份额，在秘密共享域计算各个候选测试对应的评价分数，包括：所述第二目标参与终端对本地持有各个所述学习样本的第二目标特征数据进行排序，得到第一排序结果，其中，所述第二目标参与终端持有所述第二目标层对应的所述第二目标特征数据；所述第二目标参与终端基于所述第一排序结果和其余各个所述参与终端协同更新本地持有的所述第二目标层中每个结点对应的所述第二加性秘密共享份额和所述第三加性秘密共享份额，以实现对所述第二目标层中每个结点对应的所述一阶梯度向量和所述二阶梯度向量中的梯度值的重排序，使得所述一阶梯度向量和所述二阶梯度向量中的梯度值的排序结果与所述第一排序结果一致；每个所述参与终端基于预设的桶数量对本地持有的所述一阶梯度向量和所述二阶梯度向量中的各个梯度值进行分桶，得到各个桶的秘密共享份额，每个桶中包括多个按顺序排列的所述一阶梯度值和所述二阶梯度值；每个所述参与终端基于本次持有的所述各个桶的秘密共享份额，确定每个所述候选测试对应的所述评价分数的秘密共享份额，其中，每个所述候选测试的阈值为第一梯度值和第二梯度值分别对应的所述第二目标特征数据中的一个，或所述第一梯度值和所述第二梯度值分别对应的所述第二目标特征数据之间的一个值，所述第一梯度值为第一桶中的最后一个所述一阶梯度值或所述二阶梯度值，所述第二梯度值为第二桶中的第一个所述一阶梯度值或所述二阶梯度值，所述第一桶为相邻的两个桶中的前一个桶，所述第二桶为相邻的两个桶中的后一个桶。4.根据权利要求3所述的基于梯度提升决策表的隐私保护垂直联邦学习方法，其特征在于，所述第二目标参与终端基于所述第一排序结果和其余各个所述参与终端协同更新本地持有的所述第二目标层中每个结点对应的所述第二加性秘密共享份额和所述第三加性秘密共享份额，包括：将所述第二加性秘密共享份额和所述第三加性秘密共享份额分别作为目标共享份额，所述目标共享份额基于如下的步骤实现更新：辅助终端生成随机向量和随机排序规则，基于所述随机排序规则对所述随机向量中的值进行排序，得到辅助排序向量，将n个第五秘密共享份额和n个第六秘密共享份额分别发送至各个所述参与终端，将所述辅助排序向量发送至所述第二目标参与终端，所述第五秘密共享份额为所述随机向量的加性秘密共享份额，所述第六秘密共享份额为所述辅助排序
向量的加性秘密共享份额；所述参与终端在本地计算本地持有的所述目标共享份额和所述第五秘密共享份额的第一差值向量，所述第二目标参与终端接收其余所述参与终端发送的所述第一差值向量，在本地获取第二差值向量，所述第二差值向量为所述目标共享份额对应的明文向量与所述随机向量的差值向量；所述第二目标参与终端生成辅助排序规则，将所述辅助排序规则发送至其余的所述参与终端，所述辅助排序规则满足条件：按照所述辅助排序规则对所述辅助排序向量进行重排序后得到所述随机向量；所述第二目标参与终端之外的所述参与终端根据所述辅助排序规则对本地持有的所述第六秘密共享份额进行重排序，将重排序后的所述第六秘密共享份额作为更新后的所述目标共享份额；所述第二目标参与终端对所述第二差值向量按照所述第一排序结果对应的排序规则进行排序，将排序后的所述第二差值向量作为更新后的所述目标共享份额。5.根据权利要求3所述的基于梯度提升决策表的隐私保护垂直联邦学习方法，其特征在于，第c个所述候选测试对应的所述评价分数通过基于前c个桶中的总梯度值计算得到的不纯度和基于后b-c个桶中的总梯度值计算得到的不纯度确定，c为正整数，b为所述桶数量。6.根据权利要求3所述的基于梯度提升决策表的隐私保护垂直联邦学习方法，其特征在于，所述第二目标参与终端基于所述评价分数的秘密共享份额确定所述第二目标层对应的最优测试，包括：所有的所述参与终端基于所述评价分数的秘密共享份额确定各个所述评价分数之间的比较结果的秘密共享份额；所述第二目标参与终端基于所述评价分数之间的比较结果的秘密共享份额确定所述最优测试的序号，所述第二目标参与终端基于所述最优测试的序号，在所述第一排序结果中查找所述第一梯度值和所述第二梯度值，基于所述第一梯度值和所述第二梯度值确定所述最优测试对应的阈值，以确定所述最优测试。7.根据权利要求6所述的基于梯度提升决策表的隐私保护垂直联邦学习方法，其特征在于，所有的所述参与终端基于所述评价分数的秘密共享份额确定各个所述评价分数之间的比较结果的秘密共享份额，包括：所有的所述参与终端基于如下步骤确定第一评价分数和第二评价分数的比较结果：所有的所述参与终端基于本地持有的所述第一评价分数和所述第二评价分数的加性秘密共享份额，获取分数差值的加性秘密共享份额，所述分数差值为所述第一评价分数和所述第二评价分数的差值；所有的所述参与终端将本地持有的所述分数差值的加性秘密共享份额转换为比特值，通过前缀加法器得到所述分数差值的最高位的加性秘密共享份额作为所述第一评价分数和所述第二评价分数的比较结果的秘密共享份额。8.根据权利要求1所述的基于梯度提升决策表的隐私保护垂直联邦学习方法，其特征在于，所述各个所述参与终端获取各个所述学习样本的预测结果的第四加性秘密共享份额，包括：
持有所述目标决策表的分裂层对应的特征数据的所述参与终端生成目标学习样本在所述分裂层对应的叶指标向量，其中，所述分裂层为所述目标决策表中具有子结点的层，所述叶指标向量用于表示所述目标学习样本被划分至所述分裂层中的结点的第一子结点或第二子结点，所述叶指标向量中的元素个数等于所述已被学习的决策表中结点最多的一层中结点的个数；持有所述分裂层对应的特征数据的所述参与终端对所述叶指标向量进行加密，将所述叶指标向量的加性秘密共享份额发送至其余的所述参与终端；所有的所述参与终端基于本地持有的加性秘密共享份额，获取所述目标学习样本在各个所述分裂层对应的所述叶指标向量的乘积结果的加性秘密共享份额作为所述目标决策表对应的预测结果分值的秘密共享份额；所有的所述参与终端基于加性秘密共享将所有的所述已被学习的决策表对应的预测结果分值进行聚和，得到所述目标学习样本对应的所述第四加性秘密共享份额。9.根据权利要求1所述的基于梯度提升决策表的隐私保护垂直联邦学习方法，其特征在于，持有所述目标决策表的分裂层对应的特征数据的所述参与终端生成目标学习样本在所述分裂层对应的叶指标向量，包括：持有所述分裂层对应的特征数据的所述参与终端基于本地持有的所述分裂层的最优测试和所述目标学习样本对应的特征数据，确定所述目标学习样本被划分至所述分裂层中的结点的第一子结点或第二子结点；当所述目标学习样本被划分至所述分裂层中的结点的第一子结点时，所述分裂层对应的所述叶指标向量中的各个元素组中的第一个元素为1，第二个元素为0；当所述目标学习样本被划分至所述分裂层中的结点的第二子结点时，所述分裂层对应的所述叶指标向量中的各个元素组中的第一个元素为0，第二个元素为1；其中，所述分裂层对应的所述叶指标向量中包括2
d
个元素组，每个元素组中包括两个元素，d为所述分裂层在所述目标决策表中的层序号，d∈[0,d-1]，d为所述目标决策表的层数。10.一种基于梯度提升决策表的隐私保护垂直联邦学习系统，其特征在于，所述系统包括多个参与终端，所述多个参与终端协同完成如权利要求1-9任一项所述的基于梯度提升决策表的隐私保护垂直联邦学习方法。

技术总结
本发明提供一种基于梯度提升决策表的隐私保护垂直联邦学习方法及系统，方法应用于包括多个参与终端的系统中，每个参与终端持有每个学习样本的部分特征数据，且各个参与终端持有的特征数据的类别不同；本发明提供的学习方法中，在学习的全部过程中，所有的中间数据都是被加密的，每个参与终端只能获取到数据的加性秘密共享份额，而无法获取到完整的明文数据。本发明可以实现对基于梯度提升决策表的隐私保护垂直联邦学习数据的隐私保护。私保护垂直联邦学习数据的隐私保护。私保护垂直联邦学习数据的隐私保护。


技术研发人员：郑宜峰 徐双庆 花忠云
受保护的技术使用者：哈尔滨工业大学（深圳）
技术研发日：2023.03.31
技术公布日：2023/8/1