联邦学习笔记整理（一）

当前虽然是大数据的时代，可是咱们面临着如信息孤岛以及数据隐私保护等问题，不少数据没法直接汇总到一块儿进行建模。为了在多方数据进行联合建模的同时保护数据隐私，咱们须要联邦学习。前段时间我对联邦学习进行了一些调研，现将整理笔记附上。

什么是联邦学习

联邦学习的概念是2016年由谷歌提出的，其初衷是针对多个手机终端，各自利用其本地数据，共同训练一个模型这样的场景。而如今这一场景被延伸到了不少其它地方。

关于谷歌联邦学习2016年的文章能够参考：Andrew Hard et al., Federated learning for mobile keyboard prediction. Google, 2019。html

假设存在N个数据拥有方( $U_1$, $U_2$, …, $U_N$)，其拥有的数据为( $D_1$, $D_2$,…, $D_N$)。传统的机器学习是将多方数据进行整合 $D=D_1 \cup D_2 \cup...\cup D_N$, 建模获得模型M。而联邦学习是在多方数据彼此不可见的状况下共同建模M’。假设模型M的Loss为 $L$，模型M’的Loss为 $L'$, 若 $|L-L'|<\delta$，则称联邦学习算法损失精度为 $\delta$。web

联邦学习根据数据和数据持有者的性质能够分为：横向联邦学习，纵向联邦学习和迁移联邦学习。
算法

横向联邦学习

谷歌分布式系统

特色：安全

1. 多个用户，一个服务器
2. 全部数据特征维度相同
3. 用户本地训练
4. 用户经过服务器共享参数

大体步骤以下：服务器

1. 对于用户K，其拥有的数据个数为 $n_k$，定义 $F_k(w)=\frac{1}{n_k}\sum_i f_i(w)$，计算参数梯度 $g_k=\nabla F_k(w)$，上传到服务器。其中， $f_i(w)$为第 $i$个数据的损失函数。
2. 对于服务器，更新参数 $w_{t+1}=w_{t}-\eta\sum_k\frac{n_k}{n}g_k$。其中 $t$表示第 $t$次参数更新。
3. 用户下载最新的参数 $w_{t+1}$，并进行本地更新。

能够看到，只有服务器为信息安全负责。那么如何作到隐私保护呢？app

能够加密上传的梯度。只有收集到全部用户的梯度以后，其和才能被计算出来。这一点相似于要开启一个密室，须要6把钥匙，缺乏任何一把密室都不能被开启。具体如何加密，这一点我没有作深刻研究。机器学习

横向联邦学习有一些能够供参考的文献，如：
Reza Shokri and Vitaly Shmatikov. Privacy-Preserving Deep Learning. ACM. 2015
Jakub Konecny et al. Federated Learning: Strategies for Improving Communication Efficiency. Google, 2017分布式

横向联邦学习相对来讲比较简单。svg

纵向联邦学习

先假定只有A，B两方进行联合建模。
假设：只有一方有标签Y。
挑战：只有X的一方没法创建模型；双方不能交换共享数据。
预期：双方均得到数据保护；模型无损失。函数

在这一方面，微众银行作了不少工做。如下不少内容参考自微众银行关于联邦学习的报告。

上图摘自：Qiang Yang et al., Federated Machine Learning: Concept and Applications. 2019

下面我会介绍上述场景如何用联邦学习的方法解决。

加密的实体对齐

首先，上述场景下，A方和B方拥有的数据特征重叠较少，可是用户重叠较多。那么如何获知双方共同用户名单且不暴露其它名单呢？
能够用一种叫 CLK (cryptographic longterm key)的方法给双方用户信息进行加密，加密后的信息上传到一个可靠的第三方，第三方经过比对双方信息返回给双方两个结果：一是如何对原数据进行从新排列，二是加密的关于原数据对应用户是否为双方共有用户的信息。这里说的有点绕，之后有时间再详说。

推荐文献：
Stephen Hardy et al., Privated federated learning on vertically partitioned data via
Entity resolution and additively homomorphic encryption. arXiv:1711.1067 7

一个简单的例子

以线性回归和同态加密技术为例：


上述例子摘自：Qiang Yang et al., Federated Machine Learning: Concept and Applications. 2019

上述例子中，A和B的用户相同，可是数据特征不一样，且只有B有数据标签。双方共同训练模型，对应双方特征的参数分别为 $\Theta_A$ 和 $\Theta_B$。公式中 $[[$表示加密。为了保护双方数据隐私，对外展现的计算结果都是加密的。根据同态加密的性质，能够对加密后的损失函数进行一些分解。 $[[\mathcal{L}]]$分为了 $[[\mathcal{L}_A]]$, $[[\mathcal{L}_B]]$以及 $[[\mathcal{L}_{AB}]]$。为了更新 $\Theta_A$和 $\Theta_B$，A和B都须要知道 $[[d_i]]$，而 $[[d_i]]$的计算则同时须要A和B的数据，那么这时须要进行双方的数据交换。

首先，由第三方C将加密的公钥分别发给A和B（公钥加密，私钥解密，私钥由可靠的第三方保存）。
第一步：A计算 $u_i^A$;
第二步：A进行加密操做 $[[u_i^A]]$, 和 $[[\sum_i((u_i^A)^2+\frac{\lambda}{2}\Theta_A^2]]$
第三步：A将 $[[u_i^A]]$和 $[[\sum_i((u_i^A)^2+\frac{\lambda}{2}\Theta_A^2]]$发送给B。

图片参考自：《联邦学习的研究与应用》, 刘洋，范涛，2019.

第四步：B计算 $[[\mathcal{L}]]$，并将 $[[\mathcal{L}]]$发送
给第三方C。同时，B计算 $[[d_i]]$，并将 $[[d_i]]$发送给A。

第五步：有了 $[[d_i]]$，A和B能够分别计算 $[[\frac{\partial\mathcal{L}}{\partial\Theta_A}]]$和 $[[\frac{\partial\mathcal{L}}{\partial\Theta_B}]]$。为了不C获得A和B的梯度信息，A和B分别在梯度上加一个自定义的数字加密后再传给C。即A和B分别将 $[[\frac{\partial\mathcal{L}}{\partial\Theta_A}]]+[[mask^A]]$和 $[[\frac{\partial\mathcal{L}}{\partial\Theta_b}]]+[[mask^B]]$传递给C。
第六步：C利用私钥对 $[[\frac{\partial\mathcal{L}}{\partial\Theta_A}]]+[[mask^A]]$和 $[[\frac{\partial\mathcal{L}}{\partial\Theta_b}]]+[[mask^B]]$解密并传递给A和B。
第七步：和B更新各自的参数： $\Theta_A=\Theta_A-\eta\frac{\partial\mathcal{L}}{\partial\Theta_A}$, $\Theta_B=\Theta_B-\eta\frac{\partial\mathcal{L}}{\partial\Theta_B}$。

上述过程即是A和B如何经过可靠的第三方C进行联合训练。训练过程当中，A和B保护了各自的数据隐私，而C仅得到了整个模型的Loss，以便于判断模型的训练结果。

模型训练好了之后，A和B分别获得了 $\Theta_A$和 $\Theta_B$，那么如何进行推断呢？

第一步：C将须要预测的用户id分别传达给A和B，A和B各自计算 $u^A$和 $u^B$，并利用公钥进行加密。
第二步：A和B分别将加密好的 $[[u^A]]$和 $[[u^B]]$发送给C。
第三步：C计算 $[[y]]=[[u^A]]+[[u^B]]$，并利用私钥解密，获得 $y$，即预测值。