联邦学习&&集成学习

1.Federated Forest
IEEE Transactions on Big Data 2020

  该文章在纵向联邦学习（客户端有相同的样本但特征空间不相同）方向上提出了一个基于CART树和bagging的联邦森林框架，它既能处理分类问题，又能处理回归问题。这个框架具有一定的隐私保护，预测是通信负担不高。

  首先，先本文假设有数据标签y为主服务器（只有一个），没数据标签的为客户机，主服务器和客户端加起来总数为M，主服务器有标签y，并将加密后的标签y分发给其它客户端。主服务器和客户端的数据特征都不相同。数据例子的编号都已经对齐，每个例子有唯一的ID。

模型构建
  主服务器首先从整个数据中随机选择特征和样本的子集。然后主服务器将私下通知每个客户机所选的特性和样本id。对于选定的特征，主服务器将私下通知每个客户端。例如，如果主服务器选择了十个特征，而客户机1只拥有其中的三个特征，则客户机1将仅显示这三个特征已被选中。它永远不会知道在全局范围内选择了多少特征，更不用说这些特征是什么了。在建树过程中，经常检查预剪枝条件。如果条件成立，客户机和主机将相应地创建叶节点。如果不触发终止条件，则所有客户端进入分枝状态，通过比较基尼值，选择当前树节点的最佳拆分特征。
  首先，每个客户机确定局部最优分割特征。然后主服务器收集所有局部最优特征和基尼值，从而找到全局最优特征。第二，服务器通知提供全局最佳特征的客户机，相应的客户机将拆分样本并将数据分区结果（分为左子树和右子树的样本ID）发送到主服务器。对于当前树节点，只有提供最佳拆分功能的客户端才会保存此分枝的详细信息。其他客户机只知道所选特征不是由他们自己贡献的。分枝信息如阈值和分割特征对其它客户机来说也是未知的。最后，递归地创建子树并返回当前树节点。在建模中，如果子树节点创建成功，则父节点不需要保存子树的样本id。否则，如果连接断开，可以很容易地从断点恢复建模（最后两句我也没理解）

模型保存
  树预测模型由两部分组成：树结构和用于每个分枝的特征和阈值等分割信息。由于森林是由所有客户机协同工作构建的，因此每个客户机上的每棵树的结构都是相同的。但是，对于给定的树节点，客户机可能存储详细信息。只有主服务器能够存储完整的模型。对于每个树节点，只有当客户端提供了分枝特征时，才会存储相应的分枝阈值。否则，客户端将不在当前节点存储任何内容，而只保留节点结构。我们将完整的树节点表示为 T T T，并将客户端i存储的没有完整细节的树节点表示为 T i T_{i} Ti​。因为树形结构是一致的，所以 T i ⊂ T T_{i} \subset T Ti​⊂T ，并且 T 1 ⋂ T 2 ⋂ T 3 . . . ⋂ T M = L T_{1} \bigcap T_{2} \bigcap T_{3}... \bigcap T_{M}=L T1​⋂T2​⋂T3​...⋂TM​=L，其中是叶子节点集合(上面说了主服务器会将加密后标签y分发给其它客户端，所以每一个叶子节点对应一个加密后的y）。完整的树是由全部客户端的树的并集，即 T i ⊂ T T_{i} \subset T Ti​⊂T ，并且 T 1 ⋃ T 2 ⋃ T 3 . . . ⋃ T M = T T_{1} \bigcup T_{2} \bigcup T_{3}... \bigcup T_{M}=T T1​⋃T2​⋃T3​...⋃TM​=T。

模型预测
  作者设计了一种预测算法，每次预测只需对整个森林的每棵树进行一轮集体通信。首先，每个客户机使用本地存储的模型来预测样本。对于第i个客户端上的树 T i T_{i} Ti​，每个预测样本从根节点进入 T i T_{i} Ti​，最终会落入一个或多个叶子节点中。当样本经过每个节点时，如果模型将分枝信息存储在该节点上，则通过检查分枝阈值确定该样本进入左子树或右子树。如果模型在此节点没有分枝信息，则示例同时输入左子树和右子树。递归地执行树节点的路径确定，直到每个样本落入一个或多个叶节点。当这个过程完成后，客户端i上的树 T i T_{i} Ti​的每个叶子节点将保存一批预测样本，我们用 S i l S^{l}_{i} Sil​来表示属于树模型 T i T_{i} Ti​的叶节点 l l l的预测样本，其中 l ⊂ L l \subset L l⊂L。
  最后，对于每个客户端的 S i l S^{l}_{i} Sil​，我们取 { S i l } i = 1 M \{S^{l}_{i}\}^{M}_{i=1} {Sil​}i=1M​的交集，结果为 S l S^{l} Sl，将 S l S^{l} Sl与主服务器的标签y对应即可得到预测结果。其中为什么取 { S i l } i = 1 M \{S^{l}_{i}\}^{M}_{i=1} {Sil​}i=1M​的交集，论文中有详细证明，感兴趣的可以去看论文，我这里就不说了。

2.Practical Federated GradientBoosting Decision Trees
AAAI 2020

有时间再写