论文笔记：隐私保护的梯度提升决策树
DPBoost方案
更严格的灵敏度界限
之前的工作是通过估计函数输出的范围来设置敏感度，使得敏感度的大小与数据库大小相关，本文认为不妥，而使用定义推导出敏感度，这里的敏感度分为两种，非叶节点(lemma 1)和叶子节点(lemma 2)，可以看到两种敏感度都与g*有关，而max|gi|是梯度的最大值，他是没有先验界限的，因此需要限制梯度范围。
由于梯度是基于预测值和目标值之间的距离来计算的，所以裁剪梯度意味着间接改变目标值，这可能导致巨大的精度损失。因此提出了Gradient-based Data Filtering (GDF)，想在每次迭代尽可能过滤掉少的数据来bound梯度，减少对acc的影响。
Loss func是凸函数，梯度单调非递减，所以随着树的增多，梯度（小于零）的绝对值会越来越小。实验表明整个训练中大多数情况下都比gl*低，因此可以用它当阈值，当前迭代被过滤掉的数据不参与本次迭代，但可能在后面树的训练中使用。这样成功bound了ΔG和ΔV。
分析GDF近似误差：
根据定理5，我们有如下讨论:
(1)GDF近似误差的上界不依赖于实例数。这种良好的特性允许即使在大数据集上也有小的近似误差。
(2)通常，大多数情况下，梯度值低于阈值且其比率p较低，如附录B所示。因此，实际上近似误差较小。
(3)如果| gf|大，逼近误差可能大。然而，具有非常大梯度的实例通常是训练数据集中的异常值，因为它们不能被GBDTs很好地学习。因此，通过过滤这些异常值来学习一棵树是合理的。
GDF为所有树设置相同敏感度，但随着迭代（收敛）进行，敏感度也会随之变化，精确推导太难了，而且阈值设置不适当会引起过大的精度损失，需要新方法控制不同树之间的衰减，在内部节点加噪声会影响当前分裂的gain，而在叶子节点加噪声会直接影响预测值，这里focus叶子结点的敏感度bounding。
由于GBDT模型一次训练一棵树，以适应它之前的树的残差，因此修剪叶节点将主要影响收敛速度，但不会影响广义树模型的目标。
Geometric Leaf Clipping (GLC)发现衰减是等比数列
在第t次迭代中，在apply Laplace之前，用下式进行clip：
对每棵树进行敏感度约束可以得到：
隐私预算分配
algorithm1-单颗树时
首先，我们使用GDF预处理训练数据集。然后，从根开始构建决策树，直到达到最大深度。
对于内部节点，我们在选择分割值时采用指数机制。考虑gain of the split：G为score func，增益越高的feature value被选为分裂值的概率越大。
对于叶子节点，我们首先使用GLC裁剪叶值。然后，应用拉普拉斯机制向叶值注入随机噪声。
对于树内部的隐私预算分配，我们采用了现有研究中的机制。具体来说，我们为叶节点(即εleaf)分配一半的隐私预算，然后将剩余的预算平均分配给内部节点的每个深度(每个层获得εnleaf)。这样就有：
algorithm2-多颗树时
提出了一种 two-level boosting 结构，称为 Ensemble of Ensembles (EoE)，它可以利用 seq composition 和 parallel composition 来分配树之间的隐私预算。在每个集成(ensemble)中，我们首先用从数据集D采样的不相交子集训练一些树。因此，parallel composition 被应用在集成中。然后，使用相同的训练集D以顺序方式训练多个这样的集合。结果，在集合之间应用 seq composition。这样的设计可以利用隐私预算，同时保持 boosting 的有效性。在某些情况下，EoE可以有效地解决几何叶裁剪（GCL）的副作用，这种副作用会导致叶值随着迭代的增长而受到过于严格的限制。
给定树的总数T和每个集成中的树数Te，我们可以得到集成的总数Ne= T /Te。然后，每棵树的隐私预算为(ε/Ne)。
当构建第t个差分隐私决策树时，我们首先计算树在集合中的位置，即te= t mod Te。由于每个树的最大叶子值在GLC中是不同的，为了利用前面树的贡献，分配给树的实例数量与其叶子敏感度成比例。
具体来说，我们从数据集I中随机选择个未使用的实例作为输入，其中I在集成开始时被初始化为整个训练数据集D。每个树都是使用算法1中的 TrainSingleTree() 构建的。所有的T个树都是一个个训练出来的，这些树构成了我们最终学习的模型。
可以得到：
转载自博客园：逆光中的黑雁i。原文链接：https://www.cnblogs.com/cheerUpGZ/p/14629843.html
往期推荐
ACL Findings 2022 | THE-X: 通过同态加密实现Transformer的推断隐私安全