一篇搞懂隐私计算中的联邦学习（上）

　　图表 1 左：参数混合方法；右：遍历性参数混合方法

　　遍历性参数混合方法能够有效利用集群计算机得到显著加速，作为一种分布式学习方法非常高效。然而，尽管分布式学习体现了一部分“非中心化”特性，但主要着眼于效率改进，一方面并未考虑到数据集不平衡、非独立同分布（Non-IID，Non Independent Identical Distribution）的情况导致适用范围受限，另一方面则未能解决隐私或者商业机密顾虑。这些缺失导致了联邦学习的崛起。

　　关于训练算法的收敛性，我们在后面还会看到其它研究提及。这里需要先指出的是，算法能够收敛仅指训练过程中预测误差会越来越小，直到无法或者无须继续改进，这时可以停止训练。但是，不同的训练算法、不同的数据分布，都有可能导致联邦学习框架下的学习算法收敛到不同的模型或参数，能收敛并不等于一定能得到最优化的结果（以集中式训练为基准，下同）。

　　1.2 横向联邦学习

　　分布式学习的主要驱动因素为训练效率。移动互联网则对机器学习提出了隐私保护挑战。一个典型的例子是考虑如何训练一个输入法预测模型。如果继续沿用过往将数据集中到一处的训练范式，势必招致隐私顾虑（不管有无采用分布式学习框架）。即便意图训练预测模型的机构（如某个手机系统商）并不打算将所收集的用户输入法习惯数据用于其它用途，它依然面临如何安全管理这些数据的问题，并需要对可能的数据泄密承担相应的法律责任。

　　为了解决这个问题，2016年，谷歌公司和爱丁堡大学的研究人员Konečný等联合提出联邦优化（Federated Optimization）概念，并作出理论分析以及初步验证[3]。就作者所知，这是联邦学习中的“联邦”一词首次出现在相关学术文献上。Konečný等提出，联邦场景的数据分布具有如图表 2所总结的特点：

　　图表 2 联邦场景的数据特点

　　这些特点导致分布式学习方法无法直接用于联邦场景。[3]吸收了遍历性参数混合方法尽早进行加权混合的技术，提出一个新方法，使得参与训练的移动设备无须上传原始数据，只需要根据中间模型计算本地数据所产生的模型权重更新，并以节点数据量为权重加权汇总模型权重更新值，即能达到接近集中式训练的效果。

　　[3]进一步证明，此加权汇总方法可以保证在平均情况下，梯度更新的方向等同集中式训练。这似乎能够证明算法的正确性。但在偏离“平均情况”的情形下算法是否仍然正确或者是否仍然能够保证训练得到较好的模型，属于模型质量问题，我们将在第2节进一步讨论。

　　由于原始数据无须离开参与训练的设备，联邦优化方法在分布式学习的基础上大幅度提高了隐私保护的力度。但是联邦优化方法是一个过于宽泛的方法，例如其中针对数据维度分布不均衡的问题，算法也做了相应的调整。因此其基本算法过程以及理论分析结果均适用于后来命名的“纵向联邦学习”场景。具体可以参见[3]。

　　不过，机构合作场景（2B场景）的纵向联邦学习跟[3]所设定的数百万台设备可以各自具备一些不同数据维度的情形毕竟不一样，反映到纵向联邦学习，可能具体算法仍然可以优化，并需要进一步的理论探讨。

　　次年，[3]的共同作者McMahan和Ramage联合其他作者进一步提出“联邦学习”概念和“联邦平均”算法（FedAvg）[4]，对联邦优化方法作出工程技术上的优化。其中，根据数据维度出现频率加以调整的步骤被取消了，从[3]的横向、纵向统一方法简化为后来命名的“横向联邦学习”方法。具体方法可以参考图表 3。

　　图表 3 横向联邦学习方法

　　横向联邦学习适用于大规模移动设备协同训练模型，也可以用于多个具备相同数据维度的机构共同训练模型，但在2B场景中更多的是各家机构所持有的数据维度有很大差异，例如，一家医院所持有的疾患数据与一家人工智能公司所具备的建模能力，或一家银行和一个互联网出行平台都无法使用横向联邦学习技术来打通。这种情况下，分别又催生了纵向联邦学习技术和分割型神经网络技术。

　　1.3 纵向联邦学习

　　2017年，Hardy等提出两个拥有不同数据维度的数据提供方合作训练模型问题[5]，并明确提出纵向联邦学习概念，以及实体对齐和加性同态加密技术的应用。

　　所谓实体对齐，指机构间需要确定所共有数据的对应实体（用户、设备），以便能在“同一条”数据上进行训练和预测的相关计算。对齐的前提是各方能够协商出某些公共的、具备实体识别能力的数据维度，例如注册用的电子邮件地址、身份证号码、手机号码（这些能够唯一确定实体身份的标识可称为强标识），或者姓名、地址、生日等组合信息（这些不能或较难唯一确定实体身份的标识可称为弱标识）等等。如存在强标识，则实体对齐是典型的隐私求交问题[6]，一般要求参与方仅获知被对齐的集合，而未被对齐的则需要保密。

　　除了通过公信第三方或安全计算节点实现，也可以采用密码学算法来实现。但一般而言，隐私求交问题的密码学实现计算量和通信量都较大。这里需要特别指出的是，[5]所考虑的主要是国外的情况，可能各方数据库里并不具备强身份标识，而仅具备姓名、生日等弱标识，[5]所采用的对齐算法则不可避免会产生误差。因此，[5]还深入研究了实体对齐中的各种误差对训练结果所产生的影响；这些分析研究是否适用于国内机构间的联邦学习场景，需要再结合实际情况加以具体分析。

　　而所谓的加性同态加密技术，是一种部分同态加密技术，其只能在密文空间保持对应明文的加法运算，且其密文上的运算结果解密后可以对应到相应明文的直接计算结果。[5] 使用了Paillier加法同态[7]技术。

　　在此基础上，[5]提出了纵向联邦学习训练逻辑回归模型的方法。其中设定A和B为数据提供方，C为公信第三方居中协调。由于训练中需要使用A和B的对齐数据进行一定的交叉计算，即A部分的计算需要使用B的数据，B部分的计算需要使用A的数据，Paillier加法同态技术此处被用于防止A或B看见对方的明文数据，而其私钥则由C掌握。

　　2019年，杨强等提出针对纵向线性回归模型的联邦学习方案[8]，同样使用了Paillier同态加密技术。由此也可见在纵向联邦学习场景中，目前并没有一个通用的方法框架，这跟之前所讨论的横向联邦不同，后者有通用的FedAvg算法及其Non-IID改进算法。这对纵向联邦学习的推广造成一定的障碍。

　　需要指出的是，除了同态加密技术，应用多方安全计算技术来解决A和B之间的保密计算需求，亦属可行，并且具备性能和功能的双重优势：性能方面，由于Paillier算法基于RSA，计算量相对多方安全计算协议大很多；而功能方面，则Paillier算法仅能支持加法（明文数字跟密文的相乘需要转化为多个密文相加问题），而多方安全计算协议则可以同时支持加法和乘法。本文第3节所提及的多个协议均可应用，如SPDZ[14, 15, 16]，ABY3[18]，SecureNN[19]等。

　　1.4 分割型神经网络（SplitNN）

　　2018年，Gupta等提出SplitNN，即分割型神经网络。这是一个多层的神经网络，其中靠近数据的某几层被分配给某个数据方，其它层则分配给其它参与方[9，10]。这在建模外包场景中特别有用，典型的如医疗健康行业。医院往往同时掌握医疗图像等数据，以及对应的标签，但一般缺乏机器学习建模能力。SplitNN能够同时保护原始数据机密性以及模型提供方的商业秘密。

　　SplitNN有多种部署方式，例如：1）一方拥有数据，另一方拥有标签和建模能力；2）一方拥有数据，第二方拥有标签，第三方拥有建模能力；3）多方拥有不同的数据，另一方拥有标签和建模能力。SplitNN能够支持非常多的、具备相同数据维度的数据方，也可以支持数据维度不同的多个数据方。

　　通过将多层神经网络的某些层分配给其中某些参与方，SplitNN能够同时起到混淆原始数据以保护隐私、模型分散持有以保护知识产权和商业秘密之双重作用。另外，神经网络特别是深度神经网络的训练计算量非常大。SplitNN的一个动机是尽量减少在数据端的计算量，而将主要的计算负荷交给服务端完成。

　　2 联邦学习的模型质量问题

　　这个问题是说：以集中式训练为基准，联邦学习能不能达到同样或接近的模型质量？所谓模型质量，一般使用预测准确值来度量。目前为止，这个问题的答案并不令人十分满意，学术界仍在积极研究中，以下介绍部分研究成果。

　　2.1 横向联邦学习

　　在横向联邦学习中，每个数据节点在一个中间模型的基础上使用本地数据进行训练，然后使用所得到的模型权重更新数据去参与形成新的中间模型（图表 3）。对照基准设定即集中式训练，不难看出，横向联邦往往是使用多条数据而形成一次模型权重更新数据，而集中式训练则可以根据每条数据产生模型权重更新。这在数据大体“均匀”分布于各参与设备的时候（IID，独立同分布），一般没有问题。然而，如果不均匀（Non-IID），那么训练出来的模型可能会有质量问题。

　　Zhao等指出，在极端的非独立同分布情况下即正好每个类别的数据都处于不同设备上的时候，横向联邦学习算法的精确度会大幅度降低，降幅最高可达55%；并提出了相应的折衷解决方案，即通过牺牲部分分布式特性，集中一部分数据来解决极端非独立同分布数据可能带来的问题[11]。然而，这个折衷方案跟隐私保护目标产生了直接冲突。

　　除了标签分布问题，Non-IID可能还有其它形式，例如数据主体之间可能具备不同的、足以影响模型参数的特性。例如，语音识别样本数据可能具有鲜明的年龄特色，而消费习惯模型则可能具备地域特色。

　　为此，Mohri等提出“不可知”联邦学习方法（AFL，Agnostic Federated Learning）[12]。所谓不可知，是指在组合每个参与方所训练出来的本地模型（以更新全局模型）时，并不采用FedAvg算法以数据量占比为权重加权汇总的做法，而是说“不知道”应该用什么权重来汇总。

　　由于不知道具体的权重分布，AFL算法着眼于训练出一个权重分布，以最小化在所有可能的数据-标签联合分布中造成的最大期望损失。Mohri等作者测试了三个数据集，结果显示AFL能在一定程度上改善预测精度，特别是在传统方法预测精度比较差的类别上能有较大改善。Mohri等认为，这显示AFL算法能够产生更为“公平”的训练结果。

　　2.2 纵向联邦学习

　　纵向联邦学习面临类似横向联邦学习的Non-IID数据问题：如果针对每条对齐数据都计算更新、交换数据，则计算量、通信量都很大；如果将一批数据汇总计算一次更新，则需要设法保证总体数据在各批次数据之间是独立同分布的，以此避免Non-IID数据问题。幸运的是，跟横向联邦学习场景不同，纵向场景中，参与方一般拥有全部交集用户，因此具备保证数据独立同分布的基础。目前还没有看到相关的研究文献，但这是落地应用需要关注的问题：如果实体对齐后的数据乱序重排未能解决Non-IID问题，则需要专门再去研究。这也是为什么需要设立性能基准的原因之一。（参见后续“一篇搞懂隐私计算中的联邦学习（下）”中5.2内容）

　　2.3 分割型神经网络

　　除了需要在参与实体之间传递某层的输出或权重更新，分割型神经网络跟集中式训练的过程并无太多差异。因此，它能达到的模型质量可以匹敌集中式训练。SplitNN设定中没有将客户端全部数据本地集中训练以后再归集服务器的做法，而是每条数据都需要经过本地层计算后传给服务器。这避免了Non-IID数据引起的模型质量问题，也是SplitNN方法的一个显著优势。

　　参考资料：

　　[1]Mann G,Mc DonaldR,Mohri M,et al.Efficient Large-Scale Distributed Training of Conditional Maximum Entropy Models[J].Neural Information Processing Systems (NIPS), 2009.

　　[2] McDonald R , Hall K , Mann G . Distributed Training Strategies for the Structured Perceptron[C]//HumanLanguageTechnologies:Conference of the North American Chapter of the Association of Computational Linguistics, Proceedings, June 2-4, 2010, Los Angeles, California, USA. Association for Computational Linguistics, 2010.

　　[3] Konečný J , McMahan H B , Ramage D , et al. Federated Optimization: Distributed Machine Learning for On-Device Intelligence. arXiv preprint arXiv:1610.02527. 2016.

　　[4] McMahan H B , Moore E , Ramage D , et al. Communication-Efficient Learning of Deep Networks from Decentralized Data[J]. Artificial Intelligence and Statistics, 2017: 1273-1282

　　[5] Hardy S , Henecka W , Ivey-Law H , et al. Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption. arXiv preprint arXiv:1711.10677. 2017.

　　[6] Freedman M J , Nissim K , Pinkas B . Efficient Private Matching and Set Intersection[C]// International conference on the theory and applications of cryptographic techniques. Springer Berlin Heidelberg, 2004: 1-19.

　　[7] Paillier P . Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[C]. International conference on the theory and applications of cryptographic techniques. Springer, Berlin, Heidelberg, 1999: 223-238.

　　[8] Yang Q , Liu Y , Chen T , et al. Federated Machine Learning: Concept and Applications[J]. ACM Transactions on Intelligent Systems and Technology, 2019, 10(2):1-19.

　　[9] Gupta O , Raskar R . Distributed learning of deep neural network over multiple agents[J]. Journal of network and computer applications, 2018, 116(AUG.):1-8.

　　[10] Vepakomma P , Gupta O , Swedish T , et al. Split learning for health: Distributed deep learning without sharing raw patient data. arXiv preprint arXiv:1812.00564. 2018.

　　[11] Zhao Y , Li M , Lai L , et al. Federated Learning with Non-IID Data. arXiv preprint arXiv:1806.00582. 2018.

　　[12] Mohri M , Sivek G , Suresh A T . Agnostic FederatedLearning[C]. International conference on machine learning, 2019: 4615-4625.

　　作者简介

　　郭伟基：原美国运通在中国境内合资银行卡清算机构——连通（杭州）技术服务有限公司创新技术部负责人，总监，主要从事前沿创新技术如隐私计算、联邦学习、同态加密、智能合约等在金融支付、风险管理、精准营销等方面的应用。

　　待续......敬请期待～

　　内容旨在信息传递，不构成任何投资建议。

　　]