聯邦學習小結

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、在聯邦學習的框架下訓練出來的模型和數據集中訓練出來的模型在泛化性能上是低損（用可接受的精度損失換取額外的安全性和隱私保護）甚至是無損的

聯邦學習的發展歷程與當前研究方向

聯邦學習的概念最初由Google提出，Google基於了一種聯邦平均技術，將聯邦學慣用於智慧手機上的語言預測模型更新，在保護用戶隱私數據安全的情況下，更新強化語言預測模型的表現從而為用戶提供輸入法自動矯正、推薦輸入等更好的使用體驗，可以說Google引爆了聯邦學習研究的熱點，而後arxiv上相關的研究文獻層出不窮，在中國則主要是由微眾銀行牽頭，進一步泛化和推廣了聯邦學習的概念，並且開源了號稱工業級應用的Fate框架，在中國的學術圈和工業界引發了一波研究與應用的熱潮； Google提出的聯邦平均技術，其主要思想是建立基於分布在多個設備上的數據集的機器學習模型，同時防止數據泄漏。而後這一領域的改進集中在克服統計挑戰和提高聯邦學習的安全性上，還有一些研究努力使聯邦學習更具個性化。以上工作都集中在設備聯邦學習上，涉及分散式移動用戶交互，並且大規模分發中的通訊成本、不平衡的數據分布和設備可靠性是優化的主要因素之一。此外，數據是通過用戶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、輸出參數：雜訊被加入訓練後的輸出參數。

其它部分感覺不是很重要，網上的資料挺多的，就不費勁粘出來了。