出品 | 智东西公开课

讲师 | 黄启军 微众银行人工智能部高级工程师

     胡水海 星云Clustar研发副总裁

导读：

4月23日晚，微众银行人工智能部高级工程师黄启军和星云Clustar研发副总裁胡水海在智东西公开课进行了一场直播讲解，主题为《GPU在联邦机器学习中的探索》。

本次专场讲解中，黄启军老师从联邦学习中的隐私保护问题，以及其在实际应用案例两个角度进行分析，全面解析联邦学习在同态计算中的挑战与原理。胡水海老师着重分析同态运算和密文传输的问题，并就如何提高同态计算和密文传输的效率，进行相应的方案解析。

本文为此次专场主讲环节的图文整理：

大家好，我是微众银行人工智能部高级工程师黄启军，今天和胡总一起来为大家分享的主题为《GPU在联邦机器学习中的探索》，主要分四个部分：

1、联邦学习中的隐私保护问题

2、联邦学习在应用中的挑战

3、GPU加速同态运算

4、高速网络助力提高密文传输效率

联邦学习中的隐私保护问题

使用技术，尤其是像AI技术或大数据技术，来跟同业或非同业的机构建立连接时，会面临一个骨感的现实，就是数据孤岛。各方、各个组织或个人设备，都会生成一个个的数据孤岛，它们之间的数据没有很好的方法进行自由的流动。

首先面临的问题是不可避免的数据保护主义，可以看到GDPR产生的一个过程。在2012年时，欧盟开始相关的提案并通过立法来保护个人数据，2014年基本达成一致，2018年5月时，GDPR正式被推出，形成法律效力。

在国内也有相似的情况，2009年开始进行个人数据的保护，2012年全国人大做了一个关于加强网络信息保护的决定，这时已经开始对关于数据保护的政策进入快速的制定过程，后面有刑法修正案（九），明显比之前要严格，因为它已把刑法的责任明确到自然人，这就意味着不只是罚款就可以了事。随后一系列的法律法规可以看到，出台更加的严格并且国家法律、行政法规更加的完善和全面化。这个全面化的不只是个人隐私数据，还包括科学数据，医疗数据以及电子商务数据等。

面对的这些问题，可以通过一些技术手段来解决，这里提出方案就是联邦学习。联邦学习可以让不同的组织，比如说医院、银行、终端设备或公司，通过联邦学习建立成一个联邦网络，来共同挖掘数据中的价值。

相比于传统的方案有什么优势？传统方法最典型的是通过网络去共享具体的样本数据；还有一种是通过加密的移动硬盘去拷贝，相关人员在一个布满摄像头的操作室，也叫安全沙箱里进行建模。但是数据同样会出本地，还是有一定的安全风险，最重要的是你把一个数据拷进去之后，还是要把它解密出来进行建模，相关人员还会知道里面的数据。最后一种是完全服务公开数据，就是人工地分享建模的经验，这对专业人员是可以的，比如医生去分享医疗影像的经验，确实可以从里面去学习。但是对于机器来说，还很难达到一个提升模型效果的能力。

而使用联邦学习有几个好处，第一，数据是隔离的，原始的样本数据不会泄露在外部；第二，效果是无损的，也就是说联邦学习跟你把所有的数据明文堆在一起，进行机器学习的效果几乎是一样的，后面我们会去具体分析；第三，它是对等的，即各个参与方都是对等的；第四，它们可以获得最终的获益，就是说你参与联邦学习，双方都可以通过这个模型受益。

联邦学习一般分为三类，第一类是横向联邦学习，横向联邦学习的机制类似于分布式的机器学习，就是大家具有相同的特征空间，有很多的样本分布到不同的机器，这里可能是不同的组织机构之间，然后进行机器学习。它与联邦学习有很大的区别，联邦学习不是把这些数据或者梯度直接进行明文交换下的计算，它是有一些加密保护措施的，所以效果会更好。第二类是纵向联邦学习，纵向联邦学习就是具有相同的一个样本空间，通过这种方式可以得到一个更宽的表，也就是可以得到更多的特征。有机器学习相关经验的同学一定知道，一般特征越多，模型效果不一定越好，但可能性更多，如果特征是互补的，效果肯定会要好很多。第三个是联邦迁移学习，两份数据没有在样本空间或者特征空间上形成交集的数据，也能够把它应用起来，这是迁移学习的另外一种方向。

我们看一个横向联邦学习的案例，在一个视觉的机器学习系统里，标注的数据是非常宝贵的。比如在目标检测上，一般各个公司都会去标注一些数据，由于这些数据成本比较高，若能把它横向联合在一起，价值就会更大，并且可以做到本地数据不用上传，就是标注完成的数据不用再发给别人，而只是作为本地模型的一个训练数据。标注完成之后，客户端会自动的加入联邦学习，等待进行训练。当有多方设备进入训练模式时，就开始整体进行联邦学习。

相比于单点模型，联邦学习的效果提升是非常明显的。左侧有一个拍摄于6个摄像头，近2000张照片的数据集，相对于任何一个单独的摄像头，它的效果都要好很多。右图是Loss的一个分布，可以看到使用联邦学习后，波动会更小，也就是训练的过程会更加稳定，模型会更加健壮。

再看一个纵向联邦学习的例子，纵向联邦学习在信贷领域是非常有用的。国家支持小微企业的发展，但是对于银行来说很为难，因为小微企业一般它的数据很少，甚至征信报告可能是空的。如果我们通过发票或者有开票公司的数据进行一个连接，我们可就以使用纳税人识别号进行连接，那我们可以把原来20多个维度的数据扩展到几百维。这样就可以给那些本没有贷款机会的小微企业也能进行贷款，并且它的模型效果会好很多。AUC能够提升12%，贷款不良率能够降低40%。

其它方面也有很多应用，不再详细介绍。最重要的是介绍一种模式，它可以形成一种混合的联邦学习，比如说这里的在保险网络，它可以通过多个保险公司，与互联网数据进行纵向联邦，同时保险公司之间会进行横向联邦来更大的发挥数据的价值。在反洗钱或者零售都可以有类似的应用，并且很多例子都是实际的案例，可以在FedAI的官网上看到。

联邦学习在应用中的挑战

前面介绍了联邦学习的背景和应用，下面主要会介绍它里面技术的挑战和原理。

联邦学习用到的安全计算或者加密技术有很多种，同态计算是开源联邦学习框架FATE中用得比较多的一种。所谓同态计算也可以说是同态加密，但同态加密跟传统的加密有很大的区别，传统方式只做加密和解密，而同态除了加密解密外，还有一个计算就是可以直接对密文进行计算处理，并且得到结果仍然是密文。可以看上图的一个简单例子，比如“1+2=3”的明文容易进行计算，但如果把1和2进行加密，还要能够进行计算，计算结果可以得到一个密文，并且解密之后的结果还是3，这种就称它为同态加密或同态计算。

同态计算里面有几个关键的分类，一个是全同态，它支持加法和乘法，两个密文能够进行相加或相乘。但是有一种特殊的情况是可以直接乘一个明文，称为标量的同态，也就是用一个明文乘一个密文，仍然得到一个密文，当然它最终的结果与两个明文相乘解密后的效果是一样的。同态计算证明的篇幅会比较长，我们重点介绍加密的过程，这里有一个关键的因子叫r，r是一个随机数，就是同一个明文加密之后，它的密文是不一样的。若同一个明文加密后，密文是一样的，那通过多次重复的数据，可以推断出里面的一些分布的规律。再一个可以看它的公钥，它的公钥是n的平方。还有一个m，m是明文，相当于一个模幂的运算，这个比较关键，后面我们会详细介绍。对于浮点数，我们可以把它编码成整数，然后进行计算，因为同态计算的原始公式里面，一般都指的是整数。这里面有一种特殊的加密系统，就是Paillier加密系统，它支持加法和标量乘法的同态计算。相比全同态，它的性能会要高很多。所以基于工程实际的应用考虑，我们主要还是应用部分同态的一个计算。

刚刚可以看到，同态上它主要是支持加法和乘法，但总会有一些公式不是加法和乘法。比如逻辑回归算法，会用到e的x次幂的计算逻辑，那怎么办？比较好的方法是把进行泰勒展开，这样可以把它变成多项式的运算，那里面只有加法、减法和乘法以及平方，对于梯度也可以进行类似的操作。可以看到进行这样转换时，会有一些近似，不过研究表明只要到2次项就已经有足够的精度，相关更多的研究可以参考上图中的论文，上图左边可以看到拟合的效果，由于泰勒展开式是在零点处展开，也就是在零点附近它的误差特别小。如果在机器学习中有常见的归一化方式，对它进行归一化，可以认为对精度没有影响，而实际的实验也证明确实是这样。这也是为什么使用联邦学习进行多方数据的机器学习，跟把数据放在一起进行机器学习效果基本上是等同的。

前面提到怎么样解决复杂函数计算的问题，但还有一个问题是同态的乘法。就是刚刚提到选择用效率更高的部分进行同态计算，但是它只支持标量的乘法，比如计算左边的loss时，会发现这里面有一个(wT*x)的平方。那对于两方来说，即Ua和Ub，要进行一个平方的计算。这里可以简单的把平方展开，得到上图所示的第三个公式。这时可以把A方的数据发给B方。因为A方是密文，发给B方是没有风险的。B方会对数据进行计算，因为得到结果仍然是密文，所以它仍可以安全的去发给A方。因为这两方它们都是持有了公钥，所以它们是解不开这个数据。如果有什么时候拟合或什么时候迭代结束的标注，可以通过C方来进行协调。

在这个过程中发现一轮迭代，其实是要发来发去有几次的计算，这里解决了一个部分同态加密深度的问题。一般来说传统的加密系统是有限制加密深度的。而部分同态，一旦做了乘法之后，已经变成一个密文，没法进行计算，可以通过这种方式来绕开这个问题。

除了刚刚提到的机器学习算法，在这之前，还有很重要的一步是做ID的匹配。做ID匹配的核心步骤是求一个交集，并且求关键是希望安全的求交集，也就是对于参与方不知道对方的样本的情况下，我们希望样本不会被公开。比如A持有1234，B持有1235，而对于4和5，双方都是不知道对方的数据。而传统的方案用的是哈希或者加盐，因为哈希是不可逆的，这样就可以得到一个交集。而实际上这种机制安全性太差，因为对于手机号或者身份证号这种容量不大的ID，用很简单的方案就能够破解，而这里用的是RSA+哈希的机制。

下面介绍下RSA+哈希的机制，首先是B方生成公钥和私钥的密钥对，它会把公钥发给A方，A方会做类似于RSA的加密的过程，它加密时引入了ri，ri是一个随机数，最终结果会乘一个ID的哈希值。因为加入了ri，把计算完的数据发给B方，B方实际上得不到ID的任何信息，甚至连哈希值都得不到。有了数据之后，因为B方持有私钥，它会做类似于RSA解密的操作，然后会得到一个中间结果叫Za，同时还要进行另外一个计算就是Zb，Zb的计算是把自己的一个数据进行哈希取模，然后再把私钥加进去，它把Za，Zb同时发给D方，看到Zb发送是安全的，因为Zb里面有d的因子在，所以A方是得不到任何结果的。但是A方拿到Za之后，观察这个公式可以发现，随机数ri它自己是知道的，所以可以消掉，经过这样消除的步骤之后，在A方时，它们可以通过同样的函数或操作两次哈希，得到一个相同的中间结果。但是A方不持有私钥，所以不知道具体的内容。但因为同一个ID进行相同的操作，得到结果一定相同，所以可以在这个基础上进行一个交集。交集之后把结果发给B方，这时就得到了一个最终的交集结果，并且数据不会涉及交集以外的隐私。这里的关键是A方发给B方时，数据里面有随机数，B方不知道，而B方发给A方时，这个数据里面又有私钥，所以A方也不知道，所以通过多轮的数据的交换和加密，就可以实现算法达到安全的效果。

通过前面的分析，我们可以总结下它带来的技术挑战，在传统机器学习里面一般会用32位，尤其是现有神经网络可能有时会用16位、8位来做为核心的指令。因为有芯片级的硬件层面支持，所以它的加速的效果是很不错的。而联邦机器学习带的挑战就不一样，它一般进行计算的是一个大整数，刚刚在前面提到，如果私钥是1k，那对于Paillier其实要取平方，所以它的计算量再翻一倍，同时也有RSA这样的计算，并且它们做这些计算不是简单的大数加法或减法，而是在大数的基础上做模幂等复杂运算。除了参数聚合与使用内网传输之外，它还有一个跨方的传输，而对于跨方的传输，一是迭代轮数会增加，二是因为加密，体积也会增加，所以带来很大的挑战。

我们可以看下它总体的效果，相比于明文计算，使用部分同态进行计算，计算量大概增长1000倍。而使用传统方法，根据相关的研究表明要慢一千倍，也就是说最终会有慢上100万倍。对于密文传输，刚刚提到密文体积的膨胀以及传输轮数的增多，它实际上把整个传输的数据就增大了成百上千倍。

根据刚刚说的这些挑战，我们跟星云进行了很多探索，然后下面请星云的胡总为大家进行下面内容的介绍。

大家好，我是来自星云Clustar的胡水海。今天很高兴跟大家分享下我们在使用GPU加速同态运算以及高速网络助力联邦学习密文传输效力的一些探索成果。

GPU加速同态运算

首先，从使用GPU加速同态运算方面来介绍一些探索成果。我们对使用GPU加速联邦学习计算做了一些可行性分析，主要有四点观察，第一个是联邦学习里面所涉及的数据加解密及密态计算，不同数据的计算基本是互不影响的，所以它满足计算高度可并行的特点，而这个特点非常适合用GPU来加速；第二个是联邦学习里面的计算公式本身并不复杂，但重复执行的次数巨大，所以满足重复的轻量级运算的特点，而GPU适合用来加速重复的轻量级计算；第三个是联邦学习中，数据IO的时间不到计算时间的0.1%，因此就属于计算密集型的任务，那GPU正好适合用来加速计算密集型任务；最后是联邦学习里面的数据是以批量形式产生，并且数据量巨大，因此满足批量大数据的特征，而GPU也正好适用来加速海量数据的批量计算。基于这4点观察，认为使用GPU来加速联邦学习是非常可行的一件事情。

虽然联邦学习有很多性质适合于GPU加速，当然也面临着一些挑战。我们主要总结了三个挑战，第一个是联邦学习需要做大整数的运算，大整数指的是1024bit、2048 bit，甚至是更大的一些大整数，但问题是GPU的流处理器在硬件上并不直接支持大整数的直接计算。第二个问题是联邦学习里面涉及大量的模幂运算，但是GPU并不擅长做模幂运算，若让GPU直接做模幂运算，它的代价是非常大的。第三个是联邦学习的计算需要保存大量的中间计算结果，但是由于成本跟能耗的限制，GPU的显存非常有限。

针对第一个问题，我们采用的解决方案是基于分治思想来做元素级并行。我以计算大整数乘法a*b为例来讲下我们是如何以分治思想来做数据并行，首先将a与b分解成高位跟低位两部分，如上图左边的两个公式所示，那a*b可以表示为下边所示的一个表达式，观察这个表达式发现它里面除了加法以外，还有4个紫色标注的乘法子项，并且这四个乘法子项并不存在数据关联性，因此是可以进行并行计算。

基于这个思想，可以通过递归将大整数乘分解成并行计算的很多小整数乘法，这样就可以使用GPU直接进行小整数乘法的运算。对于联邦学习涉及的其它运算，也可以做类似的元素级并行。

针对联邦学习的第二个挑战，我们的主要通过平方乘算法+蒙哥马利算法来解决模幂运算代价大的问题。我们解决的具体问题是如何高效的计算模幂运算，模幂运算公式是上图中最上面的公式，这里面a,b,c均为N比特大整数，一般N都是1024或2048的常比特的一个整数。首先想到的是朴素算法，先计算出a的b次方的值，然后将这个计算结果对c取模。它的缺点是计算复杂度非常高，高达O(2N)，并且中间层级的结果非常大，在GPU里面根本就无法保存。

我们做的第一个优化就是做平方乘算法，平方乘算法的原理非常简单，若我们想求a的k次方的值，不需要让a乘上k次，可以先求a的二分之k次方，再平方。以此类推，若算a的二分之k次方的值，要先求a的4分之k次方的值，然后再平方，通过这种方法可以将计算次序降低到log(K)次。有了这个方法就可以将模幂运算里的b表示成二进制数，通过log (b)次的乘法，就能算出模幂的值。

平方乘算法的优点是将整个计算的复杂度下降到O(N)并且中间计算结果都不超过c。但它的缺点是仍然要进行2N次的取模运算，对GPU来说，取模代价是很高的。

为了解决取模运算代价高的问题，我们进一步引入蒙哥马利模乘算法。它最大的特点是能够在不进行取模运算的这个前提下，就算出模乘的值，这样就完全避免了代价高昂的取模运算。

接下来，我讲下如何解决联邦学习需要缓存大量中间计算结果的问题，我们的主要解决方案就是使用中国剩余定理。

首先，先讲下联邦学习的解密计算公式，上面是联邦学习解密运算的完整的公式。通过观察整个公式会发现，联邦学习解密计算出来的明文m其实是一个长度为N比特的值，但是它中间一部分的计算结果其实是2N比特，意味着在计算中需要两倍的显存进行存储，这对计算效率的影响还是挺大的。

接下来我会讲解如何用中国剩余定理来减少解密计算里的中间计算结果，首先，简单介绍下中国剩余定理。中国剩余定理指给定一组两两互质的整数n1、n2…… nk以及任一组整数a1、a2……ak，类似于上面的统一方程组，它一定有解，并且解一定同余于N，N指的是n1、n2……nk相乘的值。

利用中国剩余定理就可以避免直接去计算解密公式来求解明文m，首先会构造两个子项mp以及mq，通过mp跟mq两个子项，构造一个同余方程组，因为这个p与q都是大质数，它们一定是互质的，一定满足中国剩余定理的条件，所以这是一个满足中国剩余定理的统一方程组。我们用CRT(mp，mq)表示方程组的解。在数学上可以证明，同余方程组的解mod pq的值等价于上面联邦学习解密计算公式得出的值。也就是说如果求解联邦学习解密计算，我们不一定要根据上面表达式来计算，也可以用下面的表达式来替代。下面的表达式计算主要涉及图中紫色框框出的三个部分的计算，这三个部分的计算有两个特点，第一个是三部分的中间计算结果都不超过N比特，因此避免使用更大的显存来缓存中间结果；另外是从2N比特数的模幂运算简化成N比特数的模幂运算，计算量是大幅度减少。

最后来看下使用上面三种方法以后，GPU加速联邦学习计算的一个评测结果。对比的bassline是14核2.2Ghz的CPU，用的GPU是Tesla V100，我们主要对比了四种联邦学习涉及的密态计算，包括同态加密、同态解密、密态乘法及密态加法。对于计算比较复杂的同态加密和同态解密，差不多有6倍左右的加速，对于计算相对简单的密态乘法及密态加法，实现了几十倍和几百倍的加速。这其实只是一个初步的结果，我们相信使用GPU加速联邦学习计算其实还有更大的空间，值得大家一起来探索。

高速网络助力提高密文传输效率

接下来讲下如何用高速网络来助力提高密文传输效率。

我们主要考虑联邦学习通信的两种场景，第一个场景是数据中心内部不同机构间的通信，第二个场景是不同机构的数据中心跨区域通信，这在联邦学习里都是很常见的通信场景。

不同的场景，它们的挑战不太一样。对于数据中心内的场景，它的主要挑战是如何在高速网络时代去加速联邦学习通信。而对于这种跨区域的场景，它的主要挑战是在高延迟、高丢包率网络环境下如何加速联邦学习通信。

对于第一个场景的挑战，我们主要解决方案是使用RDMA技术来优化两点间的通信，然后使用动态参数聚合模型来优化多点间通信。

我们来看下数据中心网络近年来的带宽增长，很明显就能看出数据中心其实已经进入了百G网络。在现在的商业数据中心里，100G、200G的交换机基本上已经成为标配了。

这样的高速网络时代，事实上对通信带来了非常大的挑战。因为带宽10到100倍的增长，其实主要带来了三大问题，第一是收发两端在相同时间里要处理10到100倍的网络数据包；第二是网络突发流量现象变得更加严重；第三是网络流完全所需要的RTT大大减少，留给拥塞控制其响应的时间也变少了，因此拥塞控制算法需要更快的去响应网络拥塞。

传统的TCP协议在数据中心网络用了很多年，但由于在高速网络下的存在三大缺点，包括这个CPU负载高带来的端处理延迟及吞吐量瓶颈等问题。现在使用RDMA网络代替TCP网络已经成为工业界的共识，而RDMA网络主要有两大特点，一个是内核旁路，一个是它的传输层是卸载到网卡硬件上。因为两大特点，RDMA就能够在高速网络上实现高吞吐、低时延、低CPU负载的两点间通信，因此我们认为RDMA网络非常适合用来加速联邦学习在数据中心内的通信。

但将RDMA网络用来加速联邦学习，还需要解决RDMA与GPU怎么样很好配合的问题。目前在GPU与RDMA网卡之间的数据拷贝，存在这样一个拷贝路径，就是它的数据会先从GPU拷贝到主机内存，然后再从主机内存拷贝到RDMA网卡，这种拷贝不仅会增大传输延迟，降低吞吐量的同时也会浪费很多CPU资源。那我们利用NVIDIA的GPU-Direct-RDMA技术实现GPU跟RDMA网卡的直接数据拷贝，这样就能够让RDMA网卡跟GPU很高效的配合。通过这个技术，我们就将通信吞吐量从20G提升到100G，并且将传输延迟最多降低了1000倍。

那我们也做了一些测试，主要针对AlexNet和VGG16两种模型。发现这两种模型性能提升分别是超过60%和50%，所以这个RDMA带来的性能加速呢还是挺可观的。

下面介绍下如何使用动态参数聚合模型来优化联邦学习多点间通信。上图展现了现在常用的两种模型训练框架，左边是这个Parameter Server，右边是Ring Allreduce，它们都各自存在一些缺点，那对于左边的Parameter Server，在通信上的缺点是它会存在多对一的通讯模式，那在超售网络下，PS的性能会因为链路拥塞而大幅下降。对右边的Ring Allreduce来说，它的主要问题就是当Worker数目多时，会有一个非常长的传输依赖链，一旦的链上的某一跳阻塞，它会让整个聚合任务都停止下来。

在联邦学习的场景下，多方之间的网络状况是非常复杂的，所以前面两种静态模型都无法很好优化多方间通信。我们提到的动态参数聚合模型的一个核心想法是根据网络的实时状态，包括物理拓扑、参与训练的节点数以及网络里实施的负载情况，去动态生成一个最合适的参数聚合模型。模型的具体情况如上图右边所示，我们的模型里面会将所有训练节点划分成多个组，每个组就是构成一个小树，然后不同树之间连成一个环。相比PS来说，多对一通信的程度就小了很多，那对比环结构Ring Allreduce来说，它的环跳数又被大大减少了。因此，它很好的解决了前面两种静态模型各自的缺点，同时又把两种模型的优点很好的结合。

最后介绍下如何解决联邦学习跨区域场景的通信挑战，我们的解决方案是设计一种机器学习专用网络传输协议。

对于联邦学习跨区域通讯，主要有三点观察，第一个是这个随着物理距离增加，跨区域通讯时间在联邦学习中时间占比越来越大；第二个是跨区域主干网具有高延迟、高丢包率等特征，并且丢包侦测及丢包恢复的代价都是很大的；第三个通过观察发现机器学习模型训练，是可以容纳一定的丢包。为了验证第三点，我们也做了两个实验，第一个实验发现当这个模型训练的丢包率小于15%时，它的模型收敛需要的轮次是不变的。第二个实验发现，当你丢包率低于15%时，如果不做丢包重传，能够有效减少模型训练所需要的时间。

那大家就会有个疑问，为什么机器学习模型训练可以容忍部分丢包呢？其实是因为目前的模型训练，大多数是采用随机梯度下降的方式通过多轮迭代进行，丢失一部分数据并不会影响训练算法来找到模型收敛点，通过上图能更直观的解释。中间五角星的是模型训练的收敛点，最大的圆圈外面的点是模型训练的起始点。如果整个训练过程当中没有任何包丢失，那它可能就会走这条蓝色的弧线，一轮一轮走到收敛点。如果丢失一部分包，但是丢包括多，模型训练的这个路径如红色的弧线，可以收敛，训练轮次也差不多，只是它的路径与原路径相比，稍微有一点点偏离，并不会影响模型训练收敛的性能以及最终的精确度。

基于前面的观察，我们设计了一种机器学习专用的网络层数协议，叫做MIT。它的核心想法是在不影响模型收敛的前提下，我们允许一定的丢包，不去做重传，从而降低联邦学习跨区域通信所需要的时间。