记录一下近期读的一篇联邦森林的论文，题目是《Federated Forest》，是介绍联邦学习框架和随机森林结合在一起的一篇文章，文章的前三章没有翻译，如果前三章有兴趣请看原文，原文链接Federated Forest
4 Methodology本文提出了一个基于CART树和bagging的联邦森林框架，它既能处理分类问题，又能处理回归问题。如图2所示的框架和算法的细节在下面的小节中给出。
4.1 Model Building
算法1（模型建立）：按照bagging的思想，主节点首先从整个数据集中随机选择一些特征和样本。然后，主节点私下的通知每个客户选中的特征和样本的ID。对于选定的特征，主节点将私下通知每个客户端点。例如，如果主节点一共选择了十个特征，而客户端1仅拥有其中的三个特征，那么客户端1将仅仅知道他所拥有的这三个特征被选中了。它并不会知道主节点选择了多少功能，更不用说是这些特征具体是什么了。在建树的过程中，需要经常检验预剪枝的条件，如果满足预剪枝条件，则客户端点和主节点将相应的创造叶子节点。
如果不触发终止条件，则所有客户端都进入树的拆分状态，并且将通过比较基尼值来选择当前树节点的最佳拆分特征。 首先，每个客户找到各自局部最优分割特征f *i。 然后，主节点收集所有局部最佳特征和相应的基尼值，从而找到全局最佳特征。 其次，主节点通知提供了全局最佳特征的客户端点。相应的客户端点将划分样本，并将样本划分结果（属于左子树和右子树的样本ID）发送到主节点进行分发。 对于当前树节点，只有提供最佳拆分特征的客户端点才会保存此拆分的详细信息。 其他客户端仅知道所选特征不是由他们自己提供的。 分割信息（例如阈值和分割特征）也是未知的。 最后，递归创建子树，并返回当前树节点。 在建模中，如果成功创建了子树节点，则父节点无需保存子树的样本ID。另外，如果连接断开，则可以轻松地从中断点恢复建模。
算法2（模型保存）：树的预测模型由树结构和分裂信息（如特征和阈值）两部分组成。由于树是在所有客户端协同工作的情况下构建的，因此每个客户端上的每棵树的结构都是相同的。 但是，对于给定的树节点，客户端可能会或可能不会存储详细信息。只有主服务器才能存储完整的模型。 对于每个树节点，仅当客户端提供拆分功能时，客户端才会存储相应的拆分阈值。 如果不是，则客户端将不在当前节点上存储任何内容，而仅保留节点结构。 我们将完整的树节点表示为T，将其保存在主节点上，将没有由客户端存储的所有详细信息的树节点表示为Ti。 由于树结构是一致的，我们考虑Ti⊂T，T1∩T2∩···Tm = L，其中L是叶节点集。 完整树是所有部分树的并集，即T =T1∪T2∪···∪Tm。
算法3和4（模型预测）：在纵向联邦的设置下，经典的预测方法涉及到主服务器和客户端之间的多轮通信，甚至样本只有一个的时候也是这样。当树的数量，最大树的深度和样本数量很大时，用于预测的通信需求将成为严重的负担。 为了解决这个问题，我们设计了一种新颖的预测方法，该方法利用了我们的分布式模型存储策略。我们的方法只需要为每棵树甚至整个森林进行一轮集体通信。 我们首先在算法3中介绍了客户端的预测算法，在算法4中，我们描述了主服务器如何协调每个客户端以实现最终预测。
首先，每个客户使用本地存储的模型来预测样本。 对于第i个客户端上的树Ti，每个样本都从根节点进入Ti，最后通过二叉树落入一个或几个叶节点。 当样本遍历每个节点时，如果模型在该节点上存储了拆分信息，则通过检查拆分阈值确定此样本进入左或右子树。如果模型在此节点处没有拆分信息，则样本同时输入左右两个子树。
其次，递归地执行树节点的路径确定，直到每个样本落入一个或几个叶节点。 完成此过程后，客户端i上树Ti的每个叶节点将保留一批样本。我们使用Si_l表示落入树模型Ti的叶子节点l的样本，其中l∈L.L是树Ti的叶子节点的集合。
第三，对于每个叶子l∈L，主节点将在{Si_1}（i=1 to M）上求交，结果将为Sl。然后，完整树T上每个叶节点拥有的样本集Sl已经与最终预测相关联。 在这里，我们对新的预测方法提出了正式的主张，因此可以对其进行数学定义：
命题1.对于样本S落在树Ti上的一片或多片叶子上，然后对于完整树T的任何叶子l，通过取{Si_l}（i=1 to M）的交集可以得到叶子l中的样本ID Sl =Sl1∩Sl2∩···SlM。
附录7中提供了证明。获得所有树上每个样本的标签值后，我们可以轻松实现最终预测。 在这种方法中，我们只需要为每棵树进行一轮通信，甚至整个森林只需进行一轮通信。
在这里，我们将对隐私保护的工作分为五个部分：
身份。在现实世界中的任务中，我们经常会遇到样本ID与人的真实身份相关联的情况。 因此，我们必须在ID对齐之前对身份进行加密。 一个示例方法如下所示：首先，所有客户端都使用约定的哈希方法来转换样本ID并生成新的哈希ID。 然后，可以在散列ID上应用消息-摘要算法5（MD5），并生成不可逆加密的ID。
标签。对于分类问题，即使标签已编码，我们仍然可以猜测出真实的标签值，尤其是对于二叉树分类。 对于回归问题，即使可以使用同态加密对标签进行加密，建模也将非常耗时。 在实际任务中，我们将在安全保护和计算效率之间进行权衡。
特征：在每个客户端上，对本地特征进行编码，然后再将其提供给主节点进行全局特征采样。 因此，主节点将不会知道特征的真正含义。
通信：可以使用诸如RSA和AES之类的加密方法来保护在训练和预测过程中通信的所有内容（模型中间值，样本索引等）。
模型存储。整个模型分布地在储存在所有客户端上。 对于每个节点，仅当拆分特征位于本地计算机上时，客户端才会存储相应的拆分信息。 如果不是，则仅存储当前节点的结构。 客户端之间彼此一无所知，包括选择了哪些特征以及在哪个树节点上。主节点可以选择保留整个模型的副本。
在本节中，我们使用了9个基准数据集，包括一个针对目标市场的现实数据集和来自UCI [7,27,9,13]的8个公共数据集，如表1所示。考虑，并针对分类和回归问题测试了我们提出的框架的准确性，效率和健壮性。在我们的实验中，我们没有追求绝对准确性，而是测试了我们方法的性能是否与非联邦方法处于同一水平，即无损。目标营销数据集是从两个完全不同的领域收集的。其中一个来自一家电子商务公司，具有84个特征，另一个来自一家提供11个特征的银行 在建模之前，所有敏感信息都受到保护。本节进行了三个主要系列的实验，包括使用两个数据提供者进行的实验，使用多个数据提供者进行的实验以及预测效率的分析。每个实验的详细信息在以下小节中给出。
在这一部分中，按特征维度将暴露的UCI数据集垂直并随机分开，并放置在两个不同的客户端服务器（M = 2）上，每个客户端服务器包含原始数据的一半特征空间。 对于目标营销数据，它也被放置在两个不同的客户端服务器上，每个服务器都包含多个业务域。本节中的实验总结如下。
联邦逻辑/线性回归（F-LR）：我们联合训练了逻辑/线性回归模型，该模型将数据保存在本地，并将模型分布式地存储在每个客户端中。
非联邦森林（NonFF）：将所有数据整合在一起以进行随机森林建模。
随机森林1（RF1）：使用来自第一个客户端的部分数据来构建随机森林模型。
随机森林2（RF2）：使用来自第二个客户端的部分数据来构建随机森林模型
联邦森林（FF）：这是我们提出的模型，由两方共同学习随机森林。 数据保存在本地，模型部分存储在每个客户端中。
我们对分类和回归问题进行了实验，并在表1中给出了准确性和RMSE的结果。我们发现RF1和RF2的性能明显比NonFF和FF差。 RF1和RF2都可以被视为使用来自一个业务领域的数据进行建模，并且特征空间的不足导致对全局知识的研究不完善。 我们还发现，在大多数测试中，回归模型的表现都不好。 对于目标营销的测试，由于不允许在两个机构之间直接汇总数据，因此我们仅对RF1，RF2，F-LR和FF进行测试。 结果表明，FF表现出预期的效果，并且通过在不同域上构建模型可以实现更好的准确性。
对于大多数数据集，NonFF和FF优于其他方法。 在我们的方法中，我们通过在每块区域的域上进行全局处理来构建每棵树，这与通过将原始数据聚合在一起而构建的树相同。 与NonFF相比，使用Z检验来验证我们方法的无损性，其中的零假设是，在给定的显着性水平下，两个总体的均值相等。 对于每个数据集，对NonFF和FF进行了40轮检验，每个Z检验的p值列于表1。如果p值≥0.05，则不能在0.05水平上拒绝原假设。并且NonFF和FF的输出之间没有显着差异。 如果0.01≤p值<0.05，则在0.01水平上不能拒绝原假设。 并且从统计上讲，我们认为此p值范围存在微小但可以接受的差异。 如果p值<0.01且均值之间存在显着差异，则应拒绝零假设。通过检查每个数据集的p值，我们可以发现其中有六个被证明NonFF和FF的结果之间没有显着差异，其余数据集的差异很小。 没有零假设被拒绝。
总体而言，我们可以安全地确认联邦森林是分类和回归问题的无损解决方案，其性能与非联邦随机森林相同。
在这一部分中，我们对帕金森数据集进行了测试，以验证联邦森林是否能够有效地将两个以上的域合并在一起，以及是否可以实现准确性的合理提高。我们选择帕金森来运行测试，因为它已经包含八个明确分类的子域。 至于训练和预测效率的测试，我们重复了十次数据。 在测试中，每次我们将一个域添加到联合模型中，并记录准确性，训练和预测时间。 如图3所示，联合森林的准确性不断提高。训练执行时间几乎与域数量成线性关系，这是可以预期的，因为在树的构建过程中检查了所有特征。 对于预测时间，尽管添加了更多的域和特征，但执行时间的差异可以忽略不计。 结果表明，当处理多个参与方的域时，我们的新预测算法非常有效。
在这一部分中，我们将我们的新预测方法与经典预测方法的效率进行了比较。 我们以目标营销，垃圾邮件库和波形数据集为例。 我们对所有测试进行了20次测试，并报告了平均结果，如图4、5和6所示。带点标记的实线表示经典预测方法的结果，带x标记的虚线表示我们建议的预测方法。
首先，我们将最大树深度设置为4，并将参与方数量从8更改为32，结果如图4所示。可以看出，我们的方法对预测效率产生了很大的改进。 尽管这两种方法的执行时间相对于参与方的数量呈线性增加，但在我们的方法和经典预测方法之间，斜率变化很大。 对于经典方法，在预测期间每个节点中都有多轮通信。 但是在我们的方法中，每棵树只有一轮通信。
首先，我们将最大树深度设置为4，并将估计数从8更改为32，结果如图4所示。可以看出，我们的方法对预测效率产生了很大的改进。 尽管两种方法的执行时间都相对于参与方的数量呈线性增加，但是在我们的方法和经典预测方法之间，斜率变化很大（我们的方法斜率小，时间增长的慢）。 对于经典方法，在预测期间每个节点中都有多轮通信。 但是在我们的方法中，每棵树只有一轮通信。
其次，将参与方的数量设置为8，并将最大树深度从4调整为16。如图5所示，我们的方法再次优于经典预测方法。 通过增加最大树深度，两种方法的预测时间增长率逐渐减慢并稳定下来。 这是因为通过将最大深度设置为较大的值，树木构建可能会由于预修剪而提前停止，并且实际的树木深度会更小。 在我们的方法中，无论树有多深或创建了多少个叶节点，每棵树只执行一次通信。
最后，我们固定了参与方的数量和最大树深度，并将测试样本率从0.1更改为0.4，如图6所示。由于经典方法与样本量有很强的线性相关性，我们发现其结果呈线性增长趋势。同时我们的方法的执行时间变化很慢，说明我们的方法对预测样本量具有较强的鲁棒性。
总体而言，我们的新预测方法已被证明是高效的。
在本文中，我们提出了一种新颖的基于树的机器学习模型Federated Forest，该模型在模型准确性方面是无损的，并且可以保护数据隐私。 在此基础上开发了一个安全的跨区域机器学习系统，该系统允许在具有相同用户样本但特征集不同的不同客户端之间共同训练学习模型。 在建模期间，不会公开每个客户端上的原始数据并将其交换给其他客户端。 提出了一种新颖的预测算法，可以大大减少通信开销，提高预测效率。通过重新设计树算法，部署加密方法并建立第三方受信任的服务器来保护数据隐私。 原始数据永远不会直接交换，交换的只有双方之间有限的加密过的中间值。 我们对真实数据集和UCI数据集进行了实验，显示了我们的方法在分类和回归任务上的出色性能，并且事实证明，联邦森林与需要将数据收集到一个地方的非联邦随机森林一样准确。 我们所提出的系统的效率和鲁棒性也得到了验证。 总体而言，联邦森林以一种全新的方式克服了数据岛问题和隐私保护方面的挑战，并且可以将其部署到实际应用中。