联邦学习小结

2020 年 12 月 15 日
AI

之前面试某大厂实习的时候写的报告，可惜太忙后来水了，这里分享一下好了：

AI在实际应用中面临的问题

1、小样本问题，例如各类医疗机构稀少的病患资料，每一家机构都难以独立构建有效的医疗影像识别模型；

2、少标签甚至无标签的半监督与无监督问题，典型的情况有小型贷款机构的评分卡冷启动问题，只拥有少量甚至没有用户的标签；

3、数据往往是分散在不同机构存储的，例如电商有用户的商品交易数据，银行有用户的个人信用数据等，实际过程中的如果能够实现多方数据的联合建模往往能够起到很不错的效果，但是传统的多方数据汇集一个数据中心进行模型构建的方式却存在诸多困难与不便；

3、法律严格限制了数据的收集与共享，例如国内的网络安全法、数据管理条例等趋严的公民隐私保护法案等，缺乏有效的数据也就难以产生有效而稳定的模型，后续的应用则更加无从谈起；

4、利益分配问题，一旦数据离开企业或个人，其利用价值大大减少，合作方对失去数据的掌控权而担忧，同时模型增益的分配也是不透明的；

总结：数据的碎片化和孤岛问题始终是AI应用落地的主要阻碍；

联邦学习如何帮助解决上述问题？

1、数据隔离，联邦学习可以保证数据不直接传递到外部的情况下完成多方联合建模等任务；

2、低损：通过联邦学习分散建模的效果相对于把数据整合在一个数据中心进行建模的效果只有少量的精度损失甚至无损；

3、合作多方地位对等，某一方占领主导的现象将不再发生；

4、共同获益，多方都能得到合理的利益分配；

什么是联邦学习？

透过复杂的现象看本质，联邦学习实际上在做的事情就是多方之间的联合建模，只是通过复杂的技术手段（安全多方计算、同态加密、差分隐私等）来保障联合建模过程中的数据安全与隐私，它是一个above于常规的机器学习和深度学习的算法上的概念，可以类比于集成学习、迁移学习、半监督学习等，在这类XX学习的框架之下，我们可以选择各类传统的机器学习例如逻辑回归，gbdt，也可以选择深度学习例如DNN、CNN、RNN等来作为框架的重要组件之一

具体来说，联邦学习就是具有以下特征的用于建立模型的大型算法框架： 1、两个及以上的参与方协作构建共享的机器学习或深度学习模型，任意一方都必须拥有能够用于模型训练的数据包括了样本、特征或标签等 2、在协作建模的过程中，各方的数据不“直接”离开其拥有者； 3、模型相关的信息（例如梯度信息）在各方之间以加密的形式进行传输与交换，并且任意一方都难以推测其它方的数据； 4、在联邦学习的框架下训练出来的模型和数据集中训练出来的模型在泛化性能上是低损（用可接受的精度损失换取额外的安全性和隐私保护）甚至是无损的

联邦学习的发展历程与当前研究方向

联邦学习的概念最初由谷歌提出，谷歌基于了一种联邦平均技术，将联邦学习用于智能手机上的语言预测模型更新，在保护用户隐私数据安全的情况下，更新强化语言预测模型的表现从而为用户提供输入法自动矫正、推荐输入等更好的使用体验，可以说谷歌引爆了联邦学习研究的热点，而后arxiv上相关的研究文献层出不穷，在国内则主要是由微众银行牵头，进一步泛化和推广了联邦学习的概念，并且开源了号称工业级应用的Fate框架，在国内的学术圈和工业界引发了一波研究与应用的热潮；谷歌提出的联邦平均技术，其主要思想是建立基于分布在多个设备上的数据集的机器学习模型，同时防止数据泄漏。而后这一领域的改进集中在克服统计挑战和提高联邦学习的安全性上，还有一些研究努力使联邦学习更具个性化。以上工作都集中在设备联邦学习上，涉及分布式移动用户交互，并且大规模分发中的通信成本、不平衡的数据分布和设备可靠性是优化的主要因素之一。此外，数据是通过用户ID或设备ID等唯一性标识进行划分的，为了安全的对ID进行匹配以及后续的模型训练，一类工作是与隐私保护机器学习（privacy-preserving machine learning）相关的，因为它还考虑了去中心化协作学习条件下中的数据隐私。为了将联邦学习的概念扩展到涵盖组织间的协作学习场景，以杨强教授为首的微众银行（Webank）团队将原始的“联邦学习”扩展成所有隐私保护去中心化协作机器学习技术的一般概念，并对联邦学习和联邦迁移学习技术进行了全面概述。同时，他们进一步调查了相关的安全基础，并探讨了与其他几个相关领域的关系，如多代理理论和隐私保护数据挖掘。最关键的是，他们提供了一个更全面的联邦学习定义，它考虑了数据划分、安全性和应用程序，并对联邦学习系统的工作流和系统架构进行了描述。

下面总结以下后续主要的研究方向，同时也是目前联邦学习在应用上存在的一些需要克服的问题，包括了：

一、系统层面： 1、动态调度：在学习过程中，参与方的数量可能不确定。但是，在许多现有系统中，参与者的数目是固定的，并且未考虑到新参与者进入或当前参与者离开的情况。联邦学习系统应支持动态调度，并具有在参与者数量发生变化时调整策略的能力。例如，Google TensorFlow Federated可以容忍某些设备掉线。区块链的出现可能可以成为多方参与者共同协作的理想且透明的平台； 2、系统架构：像深度学习控制参数同步的parameter server一样，需要研究一些常见的系统架构来进行联邦学习。在训练联邦学习模型的性能方面，通信成本是一个重要问题，如何优化不同参与方在不同的网络、设备等客观条件影响下的通讯代价以及面对各类可能出现问题，系统面临各类潜在的不可知问题所展现出的鲁棒性等仍旧需要进一步的研究与尝试； 3、数据生命周期：学习仅仅是联邦学习系统的一个方面。数据生命周期包括多个阶段，包括数据创建、存储、使用、共享、存档和销毁。为了保证整个应用程序的数据安全性和私密性，需要在联邦学习环境下创立新的数据生命周期。尽管数据共享显然是人们主要关注的阶段之一，但联邦学习系统的设计也影响其他阶段：例如，数据创建可以帮助准备适合联邦学习的数据和特征。

二、安全和隐私层面： 1、发明新的联邦学习模型：许多现有的研究试图支持更多的机器学习模型，即在联邦学习的背景下加密训练各类机器学习与深度学习模型，并提出了新的有效方法来保护隐私，同时又不会过多牺牲学习模型的准确性； 2、对抗恶意的参与者，涉及到模型的“对抗学习问题”； 3、更灵活的隐私限制：现有系统采用技术保护同一级别所有各参与者的模型参数或梯度。但是，通常各方的隐私限制在现实中有所不同。设计一个联邦学习系统的时候，将根据各方的隐私限制来区别对待。如果可以在不违反各方隐私限制的前提下最大限度地利用其数据，则学习型模型应具有更好的性能。异差异隐私（heterogeneous differential privacy）在此类问题的解决中可能有用；

三、模型性能层面： 1、数据标签：现有的大多数研究都集中在标记的数据集。但是实际上训练数据集可能没有标签，或者标签存在噪声和错误，这可能会导致模型的错误预测。噪声和标签错误可能来自不可靠的数据收集过程，例如在移动和边缘环境的不规范性以及一些恶意团体的破坏。解决数据噪声和后门攻击的问题仍然面临许多挑战，这可能涉及到“置信学习”的问题。 2、多方数据之间不满足独立同分布的基本假设或者多方数据之间的不平衡程度差异很大的情况下如何尽量保障模型的泛化性能也是一个棘手的问题，这可能涉及到“迁移学习”的问题； 3、异构数据之间的联合学习以及多任务之间的联合学习问题，这涉及到“迁移学习”和“多任务学习”等问题；

四、贡献与激励机制层面： 1、智能收益：直观地，如果一方提供更多信息，则可以从联邦学习系统中获得更多收益。一种简单的解决方案是在各方之间达成协议，某方需要为提供更多信息的其他方付费。需要建立有代表性的激励机制，这可能涉及到“强化学习”的问题；

五、其它 1、基准：随着越来越多的联邦学习系统的开发与问世，具有代表性数据集和工作负载的基准方法对评估现有系统和指导未来开发工作非常重要；

联邦学习的三大核心技术概要

在理解多方安全计算之前，先了解一下密码学的学科背景的概要

密码学知识体系的简单描述

多方安全计算不仅仅需要对每一方的隐私输入进行加密，同样重要的是，协同的从每一方的加密隐私输入中计算出函数的结果，并且在这个过程中不需要将这些输入展示给其它方，在计算的过程中也不需要明文地显示计算过程，这一点和传统地现代密码学不一样，我们日常中常见的方法是对数据进行加密传输之后，数据获取方对数据进行解密得到原文之后进行各类运算得到结果，这个过程中数据获取方显然直接获取了数据提供方的原始数据信息，而这个严重的问题在多方安全计算中则不会发生。我们在联邦学习中使用到的加密算法主要属于后量子密码的范畴；

多方安全计算

安全多方计算的定义

安全多方计算允许计算私有输入值的函数结果，从而使得每一方只能得到其对应的函数输出值，而不能得到其他方的输入值和输出值，举个例子，假设一个私有的数值x是由于n位共享方共同提供的，每一方只能获知自己提供的xi的内容，则多方协同计算为：
y1,y2,…..yn=f(x1,x2……xn)
因此，Pi方只能根据自己的输入xi来获知输出值yi，而不能获得其它任何额外的信息

目前，安全多方计算能够通过三种不同的框架实现：
1、不经意传输； 2、秘密共享； 3、同态加密
从某种程度上来说，不经意传输和同态加密都使用到了秘密共享的思想，因此，秘密共享被广泛认为是安全多方计算的核心；
由此可见，同态加密的属于安全多方计算的一种技术手段；

同态加密

同态加密技术是一种很有意思的技术，它允许在加密的条件下进行一些允许的代数运算，并且运算结果经过解密之后的结果与原文进行相同代数运算的结果一致；

一个简单的示意图

1982年，GOLDWASSER S和MICALI S在其论文《Probabilistic encryption and how to play mental poker keeping secret all partial information》中提出的加密系统允许对单一位的密文进行加法运算；1999年 Paillier在1999年提出了一种可证的安全加密系统允许对密文直接进行加法计算，2005年，Boneh等人发明了一种允许无限次数的加法运算和一次乘法运算的可证安全加密系统，而Gentry在2009年实现了突破，发布了第一个能够支持无限次数的加法运算和乘法运算的同态加密方法；

值得一提的是，2009年IBM的Gentry提出的完全同态加密(FHE)方案是密码学上的一项重大突破，后续的各类同态加密方法也是base与Gentry最初提出的FHE上的各种改进，可以类比于CNN的诞生与后代各类复杂CNN结构的发展/

同态加密的定义

同态加密方法H由一个四元组构成： H={keygen,enc,dec,eval} 其中，keygen表示密钥生成函数，enc表示加密函数，dec表示解密函数，eval表示评估函数，按照对称和非对称两种加密分别有对应的对称和非对称同态加密： 1、非对称同态加密，一个密钥生成元g被输入keygen，并输出一个密钥对{pk,sk}=keygen(g)，其中pk表示用于明文加密的公钥，sk表示用于解密的密钥，而后enc加密函数，以公钥pk和明文m为输入，产生一个密文c=enc(pk)(m)，而后可以在密文c上进行一些特定的运算，例如d=c+c,此时d是在密文c的条件下进行计算的，因此d实际上也是密文形式，最后通过评估函数eval，将密文d和公共密钥pk作为输入，输出密文对应的明文计算结果e，e=m+m； 2、对称同态加密，只生成一个密钥sk=keygen(g)，而后enc加密函数，以公共密钥sk和m作为输入，产生密文c=enc(sk)(m)，后续的过程与非对称加密是类似的，这里就不赘述了。

设enc(pk)(.)表示使用pk作为加密密钥的加密函数，设M表示明文空间，且C为密文空间，一个安全密码系统如果满足以下条件，则称之为同态的：

对于M中的运算符：

和C中的运算符：

<– 表示左边项等于或者可以直接从右边项计算出来，而不需要任何中间解密之后进行计算的过程，我们将同态加密运算定义为：[[.]]，并且分别给出加法同态加密和标量乘法（注意这里是标量乘不是向量乘）同态加密的定义：

注意标量乘法中n是一个常数而不是一个加密后的结果。

同态加密的分类

1、部分（半）同态加密（PHE）指的是该同态加密方案只能做无限次同态加法（additive-only）或者只能做无限次同态乘法（multiplicative-only）操作；

2、些许同态（SHE）可以对密文进行有限次数的任意同态操作，换句话说，它既能做乘法又能做加法，但是不能同态计算任意的函数；

3、全同态（FHE）可以对密文进行无限次数的任意同态操作，也就是说它可以同态计算任意的函数（当然也得是 efficiently computable functions）;

很显然，部分同态加密能做的事情，全同态加密也能做；但是全同态加密一般计算开销比较大，所以部分同态加密方案够用的时候没必要选用全同态加密；

目前，全同态加密因为计算代价高昂与安全性问题，发展十分缓慢且实践效果不佳，研究的方向主要集中开发满足特定需求，更有效的SHE加密方法上。

部分加法同态加密原理(已实现，但是原理部分未研究明白，论文很多地方缺少背景知识看不太懂)

考虑到需要完成同态加密之下ks的计算，所以这里先研究一下加法同态加密的原理，首先，如果要实现加法同态我们可以使PHE、SHE或者FHE，下面介绍的是部分同态PHE下的加法同态加密算法，也就是大佬 Paillier 发明的加密系统，一共有两代：

The Paillier Cryptosystem

由Paillier发表于1999年，整个加密解密的流程如下：

初始：
1、随机选择两个大质数p和q满足需要保证两个质数长度相等（例如111和311，它们的长度均为3）。 2、计算n=pq和λ=lcm(p-1,q-1) 3、选择随机整数g，需要满足：

实现上直接令g=n+1，此时g必然与n**2互质，避免了在n**2内搜索所有互质数再随机选择其中一个巨大的计算复杂度 4、计算l=(p-1) * (q-1),m= “l”关于”1 mod n”的乘法逆元 5、公钥为(n,g)，私钥为(m)
补充：
1、Z* n 表示的是小于n且与n互质的数字构成的群，例如当n=8的时候，z* n=[1,3,5,7] 2、Z* n2 表示的是小于n平方且与n平方互质的数字构成的群，例如当n=3的时候，n**2=9，则 z*n2=[1,2,4,5,7,8]
加密阶段:
1、选择随机数r∈Zn 2、计算密文：c=g**m * r**n mod n**2 可以根据数学公式转化为c= (g**m mod n**2)*(r**n mod n**2) mod n**2
加密状态下的加法运算：
假设我们有明文x1和x2，其对应的密文分别为c1与c2，则 x1+x2=decrypt(c1 * c2 mod n**2) decrypt表示解密
解密阶段：
我们令解密结果为res，密文为cipher 则 temp=(cipher**l mod n**2-1 其中temp为临时中间变量 res= (temp//n*m)%n

我们需要：
1、一个随机数生成器用于生成一个随机的n位数字； 2、一个用于判断数字是否为质数的函数； 3、公钥和密钥的两个class用于存放相应的公钥和密钥的值便于后续调用； 4、一个加密函数； 5、一个解密函数； 6、密文加法定义函数； 7、乘法逆元计算函数

import math
import random
from functools import reduce
def get_random_number_str(length):
    """
    生成随机length位数字
    :param length: 数字的长度
    :return:
    """
    num_str = ''.join(str(random.choice(range(1,10))) for _ in range(length))
    return int(num_str)

def is_prime(a):
    
  """
  判断一个数字是否是质数的函数
  a:待判断数字
  """

  if isinstance(a,int)==False:
    return False
  if a<=1:
    return False
  if a==2:
    return True
  flag=1
  x=int(pow(a,0.5))+1
  for n in range(2,x):
    if a%n == 0:
      flag=0
      break
  if flag==1:
    return True
  else:
    return False
class PublicKey(object):
    '''公钥类，用于存放n，n**2和g'''

    @classmethod
    def from_n(cls, n):
        return cls(n)

    def __init__(self, n):
        self.n = n
        self.nsquare=n**2
        self.g = n + 1
        
class PrivateKey(object):
    '''私钥类，用于存放l和m'''
    def __init__(self, p, q, n):
        self.l = (p-1) * (q-1)
        self.m = invmod(self.l, n)
        

def default_k(bits):
    return max(40, 2 * bits)


def encrypt(pub, plain):
    '''加密函数，pub表示公钥对象，plain表示要加密的明文，返回密文'''
    r=4
    while not is_prime(r):
        r = get_random_number_str(round(math.log(pub.n, 2)))
        if r > 0 and r < pub.n:
            break
    x = pow(r, pub.n, pub.nsquare)
    cipher = (pow(pub.g, plain, pub.nsquare) * x) % pub.nsquare
    return cipher

def decrypt(priv, pub, cipher):
    '''解密函数，priv表示私钥对象，pub表示公钥对象，cipher表示密文，返回解密后的明文'''
    x = pow(cipher, priv.l, pub.nsquare) - 1
    plain = ((x // pub.n) * priv.m) % pub.n
    return plain


def e_add(a, b):
    '''定义加密状态下的密文a和b的加法运算，返回计算结果，对于多个密文的求和可以使用reduce的方法来做累积计算'''
    return a * b % pub.nsquare


def add(cyphers,e_add=e_add):
    '''e_add为加密状态下的密文加法计算定义，cyphers为密文组成的list'''
    return reduce(e_add,cyphers)


def generate_keypair(p,q):
    n = p * q
    return PrivateKey(p, q, n), PublicKey(n)

def invmod(a, p, maxiter=1000000):
    """乘法逆元计算
         a * b == 1 mod p
       需要计算出b
       上述式子转化为中文描述即：
       a关于1模p的乘法逆元为多少，而这个乘法逆元就是d，我们最终是计算出a关于1模p的乘法逆元返回
       
       """
    if a == 0:
        raise ValueError('0 has no inverse mod %d' % p)
    r = a
    d = 1
    for i in range(min(p, maxiter)):
        d = ((p // r + 1) * d) % p
        r = (d * a) % p
        if r == 1:
            break
    else:
        raise ValueError('%d has no inverse mod %d' % (a, p))
    return d

下面是一个简单的demo

p=q=100

while p==q:
    while not is_prime(p):
        p=get_random_number_str(2)

    while not is_prime(q):
        q=get_random_number_str(2)
print('p:'+str(p))
print('q:'+str(q))
n=p*q
print('n:'+str(n))

后面代码用截图替代好了，复制起来略麻烦

差分隐私

差分隐私（英语：differential privacy）是密码学中的一种手段，旨在提供一种当从统计数据库查询时，最大化数据查询的准确性，同时最大限度减少识别其记录的机会。假设 epsilon 是一个正实数，A是一个随机算法，它将数据集作为输入（表示信任方拥有的数据）。imA表示A的映射。对于在非单个元素（即，一个人的数据）的所有数据集D1和D2以及imA的所有子集S，算法A是 epsilon -差分隐私，其中概率取决于算法的随机性。。

例如, 假设我们有一个医疗记录数据库 D1 在那里每条记录是一对 (名字, x), 其中 X 是一个布尔值表示一个人是否痪有糖尿病。例如:

假设一个恶意用户 (通常被称为攻击者) 想知道Chandler是否有糖尿病。假设他知道Chandler在数据库的哪一行。攻击者只能使用特定形式的查询Qi返回数据库中前i行中第一列 X 的部分总和。攻击者为了获取Chandler是否有糖尿病的信息。只需要执行两个查询 Q5（D1）和Q4（D1），分别计算前五行和前四行的总和，然后计算两个查询的差别。在本例中Q5（D1）=3，Q4（D1）=2，差是1。攻击者在知道Chandler在第5行的情况下，就会知道他的糖尿病状况是1（有糖尿病）。这个例子显示了即使在没有明确查询特定个人信息的情况下, 个人信息如何被泄露。

上述的攻击方式称之为差分攻击，差分隐私主要解决的就是这类恶意攻击的问题

差分隐私的分类

根据差分隐私使用的方式有：

1、根据函数的敏感性增加噪声；
2、根据离散值的指数分布选择噪声。

根据使用的位置来分类有：

1、输入扰动：噪声被加入训练数据；
2、目标扰动：噪声被加入学习算法的目标函数；
3、算法扰动：目标被加入中间值，例如迭代过程中的梯度；
4、输出参数：噪声被加入训练后的输出参数。

其它部分感觉不是很重要，网上的资料挺多的，就不费劲粘出来了。