聯邦計算：不暴露真實資料如何完成合作建模？
一、引言
銀行等金融機構擁有使用者歷史行為資料，例如是否違約詐騙等，但缺乏資料去對新使用者進行判斷。而運營商、卡組織（如銀聯、VISA）等擁有大量資料的機構，有意願跟金融機構合作建模。
但是，因為金融機構與資料擁有方都有商業保密和政策合規的需要，因此無法把資料給對方來執行傳統建模程式。
針對這一現象，騰訊神盾-聯邦計算，把兩個最常用的演算法，梯度提升樹（GBDT）和邏輯迴歸（LR）的計算過程進行重新組織。
將其中部分環節使用同態加密進行改造，從而做到在雙方資料都不需要給對方的情況下也能合作建模。解決了金融行業既需要資料合作來改善業務，但同時又必須對資料保密這一矛盾。
二、同態加密與機器學習的結合
1。 互不信任，但需要相互合作
筆者近來觀看了一部經典香港警匪片——《線人》，該電影講述了張家輝扮演的刑事情報科督察李滄東與線人收取情報，最終破獲案件的驚險過程。
拋開電影場景下險象環生、步步驚心的劇情，其本質跟引言處提到的困境有異曲同工之處，那就是在互不信任，但又需要互相合作的情況下，如何兼顧雙方的權益。
下文將以電影中的情景出發，解析在資訊不對稱的場景下，聯邦演算法的資訊加密與解密原理。（注：本文所有關於警匪博弈內容，僅限對電影劇情本身的討論）。
如果你也喜歡看警匪片，可能對以下經典的情節印象深刻：帥氣的探長對案件束手無策，要找兇手如大海撈針，於是偷偷聯絡上了線人。這線人混跡江湖多年，三教九流認識一大票，掌握了不少小混混的資訊，以此換取情報費。
例如，轄區發生了劫殺案，線人能提供轄區內小混混們最近買毒品的數量，探長就能優先去調查那些買毒品多，手頭緊，更容易起歪念去打劫生財的人。
可探長並不知道線人手上的情報是否真實，所以需要先打探個虛實。同時，線人也擔心資訊提供出去就收不到錢了，畢竟也不是合法生意，因此雙方往往構成僵局。
2。 用技術打破僵局：同態加密
電影中，警探和線人都有自己的立場，在情報收取過程中，也因為立場的對立和資訊傳達的矛盾導致了一些無法挽回的嚴重後果。但如果從技術角度來看，資訊交換本不必如此麻煩。
假如探長不但查案了得，還精通密碼學和統計學，他就可以把問題解決得更加優雅一些：先讓線人把小混混們按照過往購毒量分成高低兩組，他自己也根據過往的檔案把小混混們歸類為犯案者和守法者。
如果線人手上資訊可靠，那高低兩組的犯案者比例應當明顯地不同，高購毒量一組犯案佔比更大。
回顧一下我們的場景限制，線人並不願意把資訊直接給探長，探長更不能把資訊直接給線人（不能把答案供出去了），於是探長使用了同態加密技術。
所謂同態加密是什麼呢？我們把原來人能看懂的有意義的資訊叫做明文（例如犯案者和守法者標記），密文就是把明文經過加密後得到的，人看上去沒有意義的資訊。這個同態加密妙就妙在，把密文相加後再解密的結果，和直接對明文相加的結果是一樣的。
同態加密的基本性質
首先我們來想一下，不用密碼的情況下，我們是怎樣去計算兩組人的犯罪者比例差異的呢？
我們會去數一個組裡有總共有多少人，然後數里面有多少個犯罪者。如果是犯罪者，那就是犯罪者總數+1，如果不是犯罪者，那就是犯案者總數+0。所以，我們把犯罪者標記為1，不是犯罪者標記為0，把這些1和0全部加總在一起，就知道了犯罪者總數，然後除以某組的總人數就知道了犯罪者比例。
我們用同態加密把上面這些1和0掩藏成線人看上去沒有意義的資訊，既能算出每一個分組犯罪者比例，同時線人也不知道探長手上拿著的具體是什麼資訊。
總結起來就是，探長先把犯案者記為1，守法者記為0，然後把所有的1和0做同態加密，發給線人。後者則按探長指示把高低兩組小混混的密文分別求和，然後把加總好的兩組“密文的和”發還給探長。
探長經過解密，得到值就是各組犯案者的數量，除以每組的人數，就可以知道兩組當中犯案者的比例。如果有明顯差異，就可以放心給錢，得到最有可能犯罪的小混混清單了。
這個過程中，探長的資訊（誰是犯案者，誰是守法者）沒有洩漏給線人，線人只得到了密文。線人手上的資訊（哪些小混混買毒買得多）也沒有洩漏給探長，探長只知道兩組小混混的犯案者比例而並不知道每一組有哪些小混混。
透過同態加密進行線索區分度驗證
3。 現實生活中：風控和騙徒
上述場景看似有點和現實生活脫節，但真實世界當中這樣的故事每天都在發生。
現實中會統計學的“探長們”不在警察局，而是在銀行和貸款的公司風控部門當中，一般被稱為金融風控分析師。而現實中的線人，則是擁有銀行所沒有資料的其它組織，例如電信運營商（如移動、聯通），卡組織（如銀聯、VISA）或者政府部門等。
風控部門需要去識別，哪些貸款申請人實際上是騙徒或者老賴，把他們剔除掉，以免銀行的錢被騙走。
在這個過程中，由於銀行和資料提供方都需要保護自己的客戶隱私和商業機密，所以也跟探長與線人一樣，需要在不洩漏真實資料的情況下共同完成這個識別工作。
而同態加密正是用到的其中一種方法，騰訊神盾-聯邦計算把同態加密和機器學習演算法結合起來，就成了當前最常見的聯邦學習演算法。
銀行和資料擁有方，既要合作，又要保密
神盾-聯邦計算透過提供一站式聯邦學習平臺，在金融機構和資料提供方合作當中作為聯通資料的橋樑，分析師們無需關注演算法底層密碼學和機器學習改造的底層細節，滑鼠簡單點選即可完成聯邦機器學習建模流程，同時又能確保雙方資料都不洩漏，保障資料安全
三、聯邦梯度提升樹和聯邦邏輯迴歸
基於前文所述，透過同態加密來驗證資料區分能力的基本原理，神盾-聯邦計算對最常用的決策樹類演算法梯度提升樹（XGBoost/GBDT）和線性模型類演算法邏輯迴歸（Logistic Regression）分別進行了改造。下面我們來看看改造是怎麼進行的。
1。 聯邦決策樹演算法：多個線索組合起來
讓我們再次回到探長與線人的故事中來。線人現在只提供了一個線索，也就是小混混們的購毒量，並且高低兩組的犯案者比例確實是有明顯差異的。
但是探長還不是很滿意，因為高低低組的犯案者比例分別是：30%/5%，也就是說即使拿到購毒量大的小混混清單，裡面也有70%不會犯罪。
探長想再精確一點，一抓一個準，讓線人再提供一個線索。線人撓撓頭說：行，我還知道他們最近打零工的收入。探長大喜，但還是要留個心眼，先驗證一下吧。
按照之前使用同態加密的辦法，探長讓線人根據購毒量和零工收入兩個線索組合起來，分成了4個組，然後按照之前用同態加密的方法進行驗證分別得到了四組小混混的犯案者比例：10%/5%/80%/30%。
購毒量大且零工收入低的這組混混，有80%可能犯罪，近乎能一抓一準。探長滿意了。
多條線索組合計算更精確的犯罪率
這裡其實還遺留了幾個問題：
第一，購毒量和零工收入有效，這是探長根據經驗所得知的。線上人所瞭解的諸多線索當中，如果沒有探長的經驗，就只能用機器，透過上述同態加密的方法逐個去試，從而找到兩組犯案者比例差異最大的線索，這裡稱為聯邦決策樹當中的
變數搜尋
。
第二，這裡把小混混劃分成高低兩組，但到底多少是高，多少是低，劃分點在哪其實也需要機器一個個可能性去試，這裡稱為聯邦決策樹中的
分裂點搜尋
。
第三，現在只是兩個線索的兩兩組合，共有四個組合。如果有1000條線索選三個來組合呢，那就有1000X1000X1000，即一百萬種組合需要計算的，這計算量太多了，需要算很久很久。
有個取巧的方法是，先做變數搜尋找到最有區分度的第一層變數，然後固定住第一層（如購毒量）再去搜索第二層變數。如此類推，這樣就只需要1000+1000X2+1000X4（第一層1節點，第二層2節點，第三層四節點），即7000種組合需要計算，比100萬少多了。
這種辦法叫做
貪心搜尋
，就是每一層最佳的變數和分裂點選定後就不變了。
總結來看，透過同態加密的方法進行變數和分裂點的貪心搜尋，在找到最能區分犯案者和守法者的條件組合的同時，保護探長和線人的資訊都不透露給對方。這就是聯邦決策樹演算法。
在現實中，如果每一個變數和每一個分裂點都完整進行同態加密，傳送，求和，返回，解密，計算比例六步這整個流程，就需要在探長和線人中往返很多次，速度難以接受。
由於我們使用貪心演算法，所以在探長髮送完同態密文給線人後，讓線人把所有線索按照所有可能分割點都先統一進行求和後再返回給探長一次性解密，探長再從中選出比例差異最大的變數和分割點。這個所有線索按照所有可能分割點都先統一進行求和，得到的結果叫做同態密文梯度直方圖。
聯邦決策樹演算法
上述就是聯邦決策樹的建模過程，如果我們再往前一步，把多棵樹聯合起來，就能得到不同的整合模型（Ensemble）用以提升效果。
例如使用相同一份梯度同態密文多次反覆對特徵和樣本取樣來建立多棵決策樹，然後把多棵決策樹的結果取平均，就有了聯邦隨機森林模型（Random Forest）。
另外一個整合方向是每建立一棵樹就用這個樹的結果來更新梯度密文，後一棵樹以上一棵樹的結果為基礎來訓練，這就有了梯度提升樹（GBDT），其中著名的實現就有XGBoost等。
2。 聯邦邏輯迴歸：另一種可能性
神盾-聯邦計算改造了的另一個常用演算法則是邏輯迴歸。
上文提到過，同態加密的特性是明文加密之後求和再解密，等價於明文直接求和。把這條性質衍生一下，那明文乘以密文再加密，等價於明文乘以明文。
例如 3*密文，其實就是等於 密文+密文+密文。我們利用這個性質可以幫助探長和線人構建另一種模型：邏輯迴歸。
同態加密基本性質的衍生
前文所述的透過條件組合，如購毒量高且零工收入高，這種方式來組合多個線索，就得到了樹模型。
那能否換一種線索組合的方式，例如：犯案可能性 = 購毒量線索的權重x購毒量+零工收入的權重x零工收入。我們把這樣的組合方式稱為線性模型，其中最常用的就是邏輯迴歸。由於這種模型是把多個線索的得分加起來預測犯案可能性，所以又叫做評分卡。
這裡聯邦演算法唯一需要做的事便是確定每一項線索的權重，這裡我們可以用瞎猜的辦法。線人隨便指定權重，計算得出每個人的犯案可能性，然後發給探長，探長再答覆線人猜得有多準。
當然，這樣子不知道要到何年何月才能猜出足夠好的一組權重了，所以科學家想出了很多讓這個猜測過程更快的辦法，其中一種就叫做梯度下降法。
邏輯迴歸
線人先瞎猜一組權重，然後告訴探長結果。探長想了想，如果我直接回復他哪些小混混猜準了，哪些沒猜準，他多猜幾次不就把我的檔案資料摸清楚了，所以不能直接給他。我能不能直接告訴他每一個權重是多了還是少了，應該加多少或者減多少，這樣就不會洩漏到底猜對了還是猜錯了。
探長這裡所想到的每一個權重值應該加多少或者減多少，其實就是所謂的梯度。透過減梯度值來儘快猜出一個最佳的權重值，這種方法就叫做梯度下降法。
其中最簡單的梯度就是“線索的值”X“猜測的犯罪可能性與真實是否犯罪的差值”。這公式的推導需要微積分，但理解卻不難。
前者是因為線索的值越大，對最終結果的影響越大，所以變化幅度要越大；後者則是變化的方向，猜多了要減一點，猜少了要加一點，差得遠加減的幅度也要越大。
但是探長不能直接給出“猜測的犯罪可能性與真實是否犯罪的差值”，因為這樣會讓線人很快摸清檔案真實情況。
探長心生一計，他把這個差值做了同態加密，發給線人，讓線人使用所掌握的“線索的值”計算出梯度的密文，也就是 “線索的值”X“猜測的犯罪可能性與真實是否犯罪的差值的密文”，然後發還給探長進行解密。最後探長就可以只把梯度告訴線人，而不需要把猜測正確與否洩漏出去了。
聯邦邏輯迴歸梯度計算流程
把上面這個過程反覆進行，直到猜來猜去準確性都沒什麼提升了，就停止不猜了，被稱為“收斂”了。
結語
在本文中，我們從電影中探長與線人的博弈場景延伸展開，探討如何在雙方都不透露具體資料給對方的情況下進行資料合作。
藉此介紹了同態加密的技術，而同態加密的特點是對密文求和再解密等價於對明文直接求和。同時介紹了神盾-聯邦計算在此基礎之上，對經典的梯度提升樹演算法（GBDT）和邏輯迴歸演算法（LR）進行了改造，從而讓雙方資料都不洩漏的情況下訓練模型。
目前這兩個演算法已融入騰訊神盾體系，成為其中重要的能力，幫助促進金融行業的資訊共享合作。同時，神盾也在安全性、效率和演算法的豐富性完整性方面投入研發，取得了成效，例如：
同態加密演算法：神盾透過自研的RIAC同態加密系統替代傳統的Paillier系統，讓演算法整體計算速度提升70%。
邏輯迴歸演算法：神盾透過重新設計算法協議，剔除了可信第三方這個不安全設定，同時徹底免除了近似計算誤差，使聯邦邏輯迴歸效果跟傳統邏輯迴歸完全一致。
決策樹演算法：神盾透過矩陣計算最佳化，將同態密文的梯度直方圖計算速度提升70%以上，使整體計算時間減少50%。
非對稱聯邦技術：透過摻入假樣本保護金融機構的客戶ID列表，同時不影響模型訓練效果。
未來，神盾-聯邦計算將繼續致力於聯通資料孤島，讓資料發揮更大價值的同時，助力業務發展。
