史鼎元,王晏晟,鄭鵬飛,童詠昕

1(軟件開發(fā)環(huán)境國家重點實驗室(北京航空航天大學(xué)),北京 100191)

2(大數(shù)據(jù)科學(xué)與腦機(jī)智能高精尖創(chuàng)新中心(北京航空航天大學(xué)),北京 100191)

3(北京航空航天大學(xué) 計算機(jī)學(xué)院,北京 100191)

近年來,排序?qū)W習(xí)(learning-to-rank,簡稱LTR)在信息檢索領(lǐng)域取得了巨大的成功[1?3],這種成功在諸如谷歌(Google)與必應(yīng)(Bing)等具備大量用戶數(shù)據(jù)資源的商業(yè)搜索引擎上尤為顯著.排序?qū)W習(xí)算法的有效性離不開大量訓(xùn)練數(shù)據(jù)的支撐,搜索引擎巨頭公司的數(shù)據(jù)往往由搜索引擎與其上千萬甚至上億用戶在每日的頻繁交互中產(chǎn)生.然而,眾多普通規(guī)模的中小型企業(yè)也有搭建搜索引擎或搜索系統(tǒng)的需求,如企業(yè)搜索(enterprise search)或郵件搜索,但其并不具備單獨收集大規(guī)模用戶數(shù)據(jù)的實力.中小型企業(yè)與企業(yè)之間,乃至企業(yè)的部門之間存在的數(shù)據(jù)孤島(data silo)問題導(dǎo)致了大量數(shù)據(jù)分散存儲,出于企業(yè)機(jī)密保護(hù)以及行政手續(xù)復(fù)雜等原因難以被打通.與此同時,隨著越來越多的數(shù)據(jù)隱私保護(hù)法規(guī)如歐盟的“通用數(shù)據(jù)保護(hù)條例(general data protection regulation,簡稱GDPR)”等的出臺,即使企業(yè)在主觀上愿意,其也無法再像以往一樣自由地交換或分享含有用戶隱私的數(shù)據(jù).種種不利因素,使得中小型企業(yè)很難利用強(qiáng)大的排序?qū)W習(xí)算法與大數(shù)據(jù)的支撐搭建其自己的有效搜索系統(tǒng)[4].因此,如何為各企業(yè)克服數(shù)據(jù)孤島障礙,在滿足隱私保護(hù)的約束下訓(xùn)練有效的排序?qū)W習(xí),是一個亟待解決的問題.

為了解決上述問題,在本文中,我們首次提出了面向企業(yè)數(shù)據(jù)孤島的聯(lián)邦排序?qū)W習(xí)(cross-silo federated LTR,簡稱CS-F-LTR),其致力于協(xié)調(diào)多方企業(yè)或組織在不交換各自原始數(shù)據(jù)的前提下,聯(lián)合訓(xùn)練有效的排序?qū)W習(xí)模型.一方面,與分布式排序?qū)W習(xí)不同的是:在本文場景下,訓(xùn)練排序?qū)W習(xí)模型所需的排序?qū)ο?如文檔、電子郵件等)與查詢語句均被分散地存儲在各方,原始數(shù)據(jù)被動地被分隔且無法自由交互,只能由各方借助隱私保護(hù)的手段來生成排序?qū)W習(xí)所需的訓(xùn)練樣本;而在分布式場景下,訓(xùn)練樣本是提前由原始數(shù)據(jù)計算所得再進(jìn)行數(shù)據(jù)分割的.同時,無論是訓(xùn)練樣本的生成或是后續(xù)的訓(xùn)練過程中,各分布式節(jié)點的數(shù)據(jù)交互都不受隱私約束[5].另一方面,本文的聯(lián)邦學(xué)習(xí)場景與現(xiàn)有的其他聯(lián)邦學(xué)習(xí)也有著很大的不同.現(xiàn)有的聯(lián)邦學(xué)習(xí)中,數(shù)據(jù)一般是被橫向分割(horizontally-partitioned)或縱向分割(vertically-partitioned)[6].在橫向分割場景中,聯(lián)邦中每一方都擁有若干互不重疊的訓(xùn)練樣本,每個樣本包含了完整的訓(xùn)練特征(features)與標(biāo)簽(labels);在縱向分割場景中,聯(lián)邦每一方都擁有完整的全樣本,但是各個特征以及標(biāo)簽為不同方所擁有.然而,本文的數(shù)據(jù)分割場景不同于上述任意一個,我們將其命名為交叉分割(cross-partitioned).在交叉分割場景下,每一條訓(xùn)練樣本的特征是由聯(lián)邦任意兩方的排序?qū)ο笈c查詢語句交叉計算所得.舉例而言,甲方擁有一條樣本,其中查詢關(guān)鍵詞為“電影”,排序?qū)ο鬄橐黄霸u,標(biāo)簽為“相關(guān)”;乙方擁有一條樣本,其查詢關(guān)鍵詞為“美食”,排序?qū)ο鬄橐黄匙V,標(biāo)簽為“相關(guān)”.此時,如果遵從現(xiàn)有的橫向聯(lián)邦學(xué)習(xí)場景,聯(lián)邦中共有兩條標(biāo)簽均為“相關(guān)”的樣本.而本文場景下,則將新增兩個特征對應(yīng)了“電影-食譜”與“美食-影評”同時標(biāo)簽未知的交叉樣本.上述3 種分割場景如圖1 所示.其中,特殊的交叉分割場景給本文的面向企業(yè)數(shù)據(jù)孤島聯(lián)邦學(xué)習(xí)框架帶來了如下挑戰(zhàn).

(1)交叉特征生成:如何在隱私保護(hù)約束下安全地連接各方的查詢語句與排序?qū)ο?從而生成有效的排序?qū)W習(xí)樣本特征.在現(xiàn)有的排序?qū)W習(xí)研究工作中[7],許多具有表現(xiàn)力的特征都是通過查詢語句與排序?qū)ο舐?lián)合計算所得(如查詢語句中單詞在排序文檔中出現(xiàn)的頻率等).因此,需要一種各方的查詢語句與其他方排序?qū)ο笾g安全交互、從而計算特征的方法;

(2)缺失標(biāo)簽處理:如何應(yīng)對交叉樣本中的標(biāo)簽缺失問題.通過上文例子可以發(fā)現(xiàn),交叉樣本往往只具有訓(xùn)練特征而無法直接獲取其準(zhǔn)確的標(biāo)簽.對某一方來說,要想獲知其文檔在其他方查詢語句下的相關(guān)度而不泄露各自的文檔與查詢語句信息是一件極其困難的事,這也將我們面臨的問題轉(zhuǎn)變?yōu)橐粋€聯(lián)邦場景下的半監(jiān)督學(xué)習(xí)問題.

本文致力于解決上述兩大挑戰(zhàn),并提出高效的聯(lián)邦排序?qū)W習(xí)算法.

Fig.1 Three types of data partitions in federated learning圖1 聯(lián)邦學(xué)習(xí)中3 種類型的數(shù)據(jù)分割

本文的主要貢獻(xiàn)如下:

(1)首次定義了企業(yè)數(shù)據(jù)孤島場景下的聯(lián)邦排序?qū)W習(xí)問題,并提出相應(yīng)的解決框架,進(jìn)一步指明了其兩大研究挑戰(zhàn),即交叉特征生成與缺失標(biāo)簽處理.目前,尚未有任何面向企業(yè)數(shù)據(jù)孤島的聯(lián)邦排序?qū)W習(xí)相應(yīng)研究成果;

(2)為了應(yīng)對交叉特征生成的挑戰(zhàn),本文提出了基于略圖(sketch)數(shù)據(jù)結(jié)構(gòu)的交叉特征生成算法,并在理論上證明了算法具有的隱私性與結(jié)果精度的保證;

(3)為了應(yīng)對缺失標(biāo)簽處理的挑戰(zhàn),本文提出了一種半監(jiān)督聯(lián)合訓(xùn)練算法,通過交互的標(biāo)簽生成器,來高效與準(zhǔn)確地推斷交叉樣本對應(yīng)的缺失標(biāo)簽;

(4)本文通過公開數(shù)據(jù)集的大量實驗,驗證了所提算法的有效性.

本文第1 節(jié)將介紹相關(guān)工作.第2 節(jié)將給出問題定義.第3 節(jié)與第4 節(jié)將分別討論交叉特征生成與缺失標(biāo)簽處理相對應(yīng)的解決方案.第5 節(jié)將展示實驗結(jié)果.最后,在第6 節(jié)進(jìn)行文章總結(jié).

1 相關(guān)工作

1.1 隱私保護(hù)的信息檢索

信息檢索系統(tǒng)通常包含同時來自于服務(wù)器端與客戶端的大量數(shù)據(jù),在當(dāng)下流行的基于排序?qū)W習(xí)的信息檢索框架下,這些大數(shù)據(jù)經(jīng)常被用來訓(xùn)練排序?qū)W習(xí)模型.隨著排序模型的使用日漸廣泛,用于訓(xùn)練排序模型的數(shù)據(jù)種類也逐漸增多,如客戶端的瀏覽器的查詢歷史信息、移動端的時空軌跡信息[8]、甚至是醫(yī)學(xué)數(shù)據(jù)[9]等.這些數(shù)據(jù)能夠反映用戶的網(wǎng)絡(luò)瀏覽習(xí)慣、出行規(guī)律和健康狀況,屬于隱私敏感的信息.這些信息難以通過簡單的脫敏手段來消除隱私泄露隱患,歷史上就曾發(fā)生過著名的AOL 數(shù)據(jù)隱私泄露事件[10].現(xiàn)如今,大多數(shù)基于隱私保護(hù)的信息檢索算法都致力于保護(hù)客戶端數(shù)據(jù)隱私免受來自惡意或半誠實的服務(wù)器的攻擊.其中,一項早期研究成果提出了名為隱私信息檢索(private information retrieval,簡稱PIR)的模型[11].然而,該模型過于理想化,需要通過數(shù)據(jù)庫的復(fù)制來實現(xiàn)隱私保護(hù),因此缺乏實際應(yīng)用價值.還有一些研究通過評估查詢語句所訪問數(shù)據(jù)的敏感程度,實現(xiàn)隱私泄漏風(fēng)險控制[12],這種方法的查詢結(jié)果嚴(yán)重受限于數(shù)據(jù)的私密程度.一些更加實用的方法通過混淆化的查詢語句來保護(hù)用戶的隱私,其混淆化的手段也是多樣的,如重構(gòu)查詢語句[13,14]、插入掩蔽語句[15]、或是滿足差分隱私(differential privacy,簡稱DP)的噪聲[16]等.另一大類模型被稱為對稱隱私信息檢索(symmetricallyprivate information retrieval,簡稱SPIR),其在防御惡意服務(wù)器攻擊的同時,也考慮了惡意用戶的攻擊,同時保護(hù)了雙方的數(shù)據(jù)隱私[17].為了實現(xiàn)對稱化的隱私保護(hù)[18,19],許多基于安全關(guān)鍵詞查詢的方法被提出,其中較為著名的有可搜索對稱加密(searchable symmetric encryption,簡稱SSE)[20]以及保序加密(order preserving encryption,簡稱OPE)[21]等.同時,也有研究工作考慮到了與本文相似的具有多數(shù)據(jù)擁有方的數(shù)據(jù)共享場景,并提出了基于保序加密的解決框架[22].然而,這些工作都只是針對簡單的關(guān)鍵詞搜索問題,而排序?qū)W習(xí)問題與之相比則復(fù)雜得多.目前,有少數(shù)研究工作考慮到了排序?qū)W習(xí)中的隱私保護(hù),但往往局限于特定的排序?qū)W習(xí)算法,如基于樹集成模型的算法[23].不同于以往的基于隱私保護(hù)的信息檢索相關(guān)工作,本文所提的聯(lián)邦排序?qū)W習(xí)考慮了在聯(lián)合學(xué)習(xí)過程中同時保護(hù)各個聯(lián)邦參與方的隱私.由于排序?qū)ο笈c查詢語句的隱私同樣都屬于隱私保護(hù)范疇,因此本文期望實現(xiàn)聯(lián)邦中任意兩兩參與方的對稱隱私要求,這是以往工作所不曾涉及的.同時,簡單地套用加密算法來實現(xiàn)任意兩方的對稱隱私,也將在計算與通信效率上變得不可行.

1.2 聯(lián)邦學(xué)習(xí)

聯(lián)邦學(xué)習(xí)(federated learning,簡稱FL)最早由谷歌提出[24],它致力于實現(xiàn)多方在數(shù)據(jù)隱私保護(hù)前提下共同完成機(jī)器學(xué)習(xí)任務(wù).個人數(shù)據(jù)隱私是當(dāng)今互聯(lián)網(wǎng)最值得關(guān)注的問題之一,隨著歐盟“通用數(shù)據(jù)保護(hù)條例(general data protection regulation,簡稱GDPR)”的頒布,大型互聯(lián)網(wǎng)公司無法再自由地收集用戶數(shù)據(jù)用于機(jī)器學(xué)習(xí).因此,谷歌于2016 年提出了針對安卓手機(jī)用戶的聯(lián)邦學(xué)習(xí)方法,它可在保證用戶數(shù)據(jù)不出本地設(shè)備的前提下訓(xùn)練一個聯(lián)合模型[24].文獻(xiàn)[4]對谷歌的聯(lián)邦學(xué)習(xí)概念進(jìn)行了擴(kuò)展,給出了更加通用的定義,并針對數(shù)據(jù)的不同切分方法,把聯(lián)邦學(xué)習(xí)分為橫向聯(lián)邦學(xué)習(xí)、縱向聯(lián)邦學(xué)習(xí)與聯(lián)邦遷移學(xué)習(xí).無論在哪種場景中,都具有幾大共同的挑戰(zhàn).首先是數(shù)據(jù)隱私保護(hù)方法的設(shè)計,現(xiàn)有的大部分工作都基于多方安全計算(secure multi-party computation,簡稱SMC)的相關(guān)方法,設(shè)計基于同態(tài)加密、秘密共享等加密技術(shù)的聯(lián)合機(jī)器學(xué)習(xí)算法[25],也有一部分工作基于隨機(jī)擾動算法,如差分隱私(differential privacy,簡稱DP),設(shè)計基于噪聲擾動的安全機(jī)器學(xué)習(xí)框架與算法[26?28].另一大挑戰(zhàn)是傳輸成本問題,由于受到原始數(shù)據(jù)不能出本地的限制,需要在多方之間交互計算機(jī)器學(xué)習(xí)的中間參數(shù),如梯度,該交互過程輪數(shù)較多,因此,如何節(jié)約傳輸成本以及減少交互輪數(shù)成為了關(guān)鍵.文獻(xiàn)[29]對此提出了提高通信效率的優(yōu)化方法.同時,如何有效地激勵用戶參與到聯(lián)邦學(xué)習(xí)的過程中來,也是目前研究的重點之一.文獻(xiàn)[30]提出了一種基于夏普利值的聯(lián)邦學(xué)習(xí)多方貢獻(xiàn)評估機(jī)制,可以高效地計算每個參與方對聯(lián)合模型的貢獻(xiàn),以此公平地分配利益.除此之外,一些現(xiàn)有工作還研究了聯(lián)邦學(xué)習(xí)的一些其他問題,如多任務(wù)學(xué)習(xí)問題[31]、數(shù)據(jù)非獨立同分布問題[32]、模型可解釋性問題[33]等.文獻(xiàn)[34]總結(jié)了大量現(xiàn)有工作并給出了更加詳細(xì)的聯(lián)邦學(xué)習(xí)綜述,根據(jù)其不同應(yīng)用場景,將之分為面向企業(yè)數(shù)據(jù)孤島(cross-silo)的聯(lián)邦學(xué)習(xí)與面向終端設(shè)備數(shù)據(jù)孤島(crossdevice)的聯(lián)邦學(xué)習(xí).在后者中,往往涉及成百上千甚至千萬級別的用戶,因此,如何縮減通信開銷成了其面臨的最大挑戰(zhàn).而前者,即本文對應(yīng)的面向企業(yè)數(shù)據(jù)孤島場景,涉及數(shù)據(jù)擁有方一般少于100,因此通信成本變得不那么重要.然而,由于每一方擁有的數(shù)據(jù)量一般要大于個人用戶的數(shù)據(jù),因此,如何縮減計算成本成為了更為重要的挑戰(zhàn).本文研究與現(xiàn)有面向企業(yè)數(shù)據(jù)孤島聯(lián)邦學(xué)習(xí)的不同之處在于考慮了一種以往工作不曾涉及的數(shù)據(jù)分割場景,即交叉分割,使得研究問題更具挑戰(zhàn)性.值得一提的是,另一項最新工作[35]也考慮到了聯(lián)邦排序?qū)W習(xí),然而其與本文的本質(zhì)區(qū)別在于:其場景為面向終端設(shè)備的聯(lián)邦學(xué)習(xí),數(shù)據(jù)也是普通的橫向分割,這使得現(xiàn)有聯(lián)邦學(xué)習(xí)方法能夠很容易地適用于其問題.相比之下,本文側(cè)重于企業(yè)搜索等面向企業(yè)數(shù)據(jù)孤島的應(yīng)用場景,問題也更加具有挑戰(zhàn)性.

1.3 半監(jiān)督排序?qū)W習(xí)

在排序?qū)W習(xí)中,獲取足夠且高質(zhì)量的帶標(biāo)簽數(shù)據(jù)需要花費大量人力成本.因此,半監(jiān)督學(xué)習(xí)(semi-supervised learning,簡稱SSL)經(jīng)常被用于只有部分?jǐn)?shù)據(jù)帶標(biāo)簽的排序?qū)W習(xí)中.文獻(xiàn)[36]提出了一種歸納排序算法,其中,無標(biāo)簽的文檔將根據(jù)與有標(biāo)簽文檔的相似度而自動生成對應(yīng)的標(biāo)簽.文獻(xiàn)[37]則采用了一種轉(zhuǎn)導(dǎo)推理方法,利用半監(jiān)督學(xué)習(xí)來尋找更優(yōu)的特征.文獻(xiàn)[38]為直推式半監(jiān)督學(xué)習(xí)引入了聚類的方法,降低了迭代中產(chǎn)生的噪聲,提高了排序?qū)W習(xí)模型性能.事實上,如今處于研究前沿的幾種半監(jiān)督學(xué)習(xí)算法,如Temporal Ensembling[39],Mean Teacher[40]等都可以被簡單地應(yīng)用于排序?qū)W習(xí)上,因為排序?qū)W習(xí)也可以被看作是一般的分類問題.然而,在本文所涉及的聯(lián)邦學(xué)習(xí)場景下,無標(biāo)簽的數(shù)據(jù)被分散存儲在了各方,如何有效地在開銷有限的前提下為之打上標(biāo)簽成為挑戰(zhàn).

1.4 Sketch數(shù)據(jù)結(jié)構(gòu)

為了在保護(hù)隱私的同時提升計算效率,本文用到了Sketch 數(shù)據(jù)結(jié)構(gòu),它是一種用于近似推斷大規(guī)模數(shù)據(jù)流上諸如元素出現(xiàn)頻率等統(tǒng)計量的方法[41],其中比較常用的兩種頻率點估計方法分別為 Count Sketch[42]與Count-Min (CM)Sketch[43].除了大規(guī)模數(shù)據(jù)流的壓縮以外,它在許多領(lǐng)域都有廣泛的應(yīng)用,例如大規(guī)模機(jī)器學(xué)習(xí)中的梯度壓縮[44]與重要項查詢[45]等.在某些場景下,它也可以與差分隱私(differential privacy,簡稱DP)相結(jié)合,同時兼顧數(shù)據(jù)隱私與計算開銷[46,47].有文獻(xiàn)證明:在特定假設(shè)條件下,Count Sketch 可以在不加入任何噪聲的前提下直接滿足差分隱私所需的條件[48],因此也被稱為“免費的隱私(privacy for free)”.在本文中,我們將證明這種免費的隱私無法適用于我們的問題場景.因此,我們也將提出一種新的基于Sketch 的差分隱私定義.

2 問題描述

本節(jié)給出面向企業(yè)數(shù)據(jù)孤島聯(lián)邦場景下的排序?qū)W習(xí)問題的正式定義.

2.1 面向企業(yè)數(shù)據(jù)孤島的聯(lián)邦場景

設(shè)聯(lián)邦F中有n個企業(yè),F={P1,P2,…,Pn}.每個企業(yè)Pi持有排序?qū)ο?文檔)數(shù)據(jù)集合和查詢數(shù)據(jù)集合其中,文檔和查詢都可以看作是由全體單詞集合Γ中的某些單詞組成的多重集.全體數(shù)據(jù)可以表示為.每篇文檔和每個查詢之間存在一個相關(guān)度分?jǐn)?shù)(即標(biāo)簽),表示為reli(d,q),其中,d∈Di,q∈Qi.由于每個企業(yè)只能夠訪問它自身所持有的文檔數(shù)據(jù)和查詢數(shù)據(jù),所以它只能計算自己內(nèi)部文檔與查詢的相關(guān)度.然而,它的查詢可能也會和其他企業(yè)中的文檔相關(guān),或反之,其他企業(yè)中的查詢和它的文檔相關(guān),但是這些相關(guān)度分?jǐn)?shù)都因為數(shù)據(jù)不能相互訪問而無法直接計算.

與其他機(jī)器學(xué)習(xí)問題類似,開展排序?qū)W習(xí)訓(xùn)練任務(wù)需要構(gòu)造訓(xùn)練數(shù)據(jù)集(X,y),其中,X表示從文檔數(shù)據(jù)D和查詢數(shù)據(jù)Q中提取的特征,標(biāo)簽y則是相關(guān)性分?jǐn)?shù).我們假設(shè)特征提取函數(shù)Φ:D×Q→Rm是已知的.該函數(shù)依據(jù)某篇文檔和某個查詢,生成交叉特征,如詞頻(term frequency,簡稱TF)、BM25[49]和LMIR[50]等.

在沒有聯(lián)邦學(xué)習(xí)的情況下,第i個企業(yè)依據(jù)自身所持有的數(shù)據(jù)Di和Qi構(gòu)造訓(xùn)練數(shù)據(jù)集(Xi,yi),作為待訓(xùn)練排序模型Mi(θ,x)的輸入.訓(xùn)練過程為標(biāo)準(zhǔn)的經(jīng)驗風(fēng)險最小化問題,即.其中,L是損失函數(shù).在面向企業(yè)數(shù)據(jù)孤島的聯(lián)邦場景中,每個企業(yè)還可以和其他企業(yè)開展合作,來生成更多的訓(xùn)練數(shù)據(jù).如前所述,這些訓(xùn)練數(shù)據(jù)沒有標(biāo)簽,在這種情況下,各企業(yè)需要聯(lián)合訓(xùn)練一個全局模型.

為了簡化各企業(yè)之間的協(xié)作場景,假設(shè)訓(xùn)練過程中存在一個中心服務(wù)器,以協(xié)調(diào)各方信息交互.同時假設(shè)中心服務(wù)器和各個企業(yè)都是誠實但好奇的(honest-but-curious),即半誠實的(semi-honest).它們會遵守協(xié)議的要求,但是也會根據(jù)收到的數(shù)據(jù)推斷敏感信息.面向企業(yè)數(shù)據(jù)孤島聯(lián)邦學(xué)習(xí)的目標(biāo)是:在保護(hù)各企業(yè)數(shù)據(jù)隱私的情況下,訓(xùn)練一個有效的全局模型.

2.2 聯(lián)邦場景下的排序?qū)W習(xí)問題

基于第2.1 節(jié)所述的通用聯(lián)邦場景,排序?qū)W習(xí)的聯(lián)邦場景問題定義如定義1.

定義1(聯(lián)邦場景下的排序?qū)W習(xí)問題).給定有n個企業(yè)的聯(lián)邦和一個特征提取函數(shù)Φ,聯(lián)邦場景下的排序?qū)W習(xí)旨在讓各企業(yè)協(xié)同訓(xùn)練一個全局的排序模型M.其中,每個企業(yè)Pi擁有一個同其他企業(yè)合作產(chǎn)生的無標(biāo)簽數(shù)據(jù)集和自身持有的帶標(biāo)簽數(shù)據(jù)集(Xi,yi),訓(xùn)練過程需要滿足以下條件.

? 共享性:對任意的兩個企業(yè)Pi,Pj(i≠j)、任意查詢q∈Qi和任意文檔d∈Dj,存在一個,滿足

? 隱私性:在訓(xùn)練過程中,任意兩個企業(yè)之間、企業(yè)和中心服務(wù)器之間的信息交互造成數(shù)據(jù)Di和Qi的隱私泄漏需要可控;

? 有效性:協(xié)同訓(xùn)練的模型M要有比各企業(yè)獨立訓(xùn)練的模型Mi有更好的性能.

上面的3 個條件對于一般的面向企業(yè)數(shù)據(jù)孤島的聯(lián)邦學(xué)習(xí)場景同樣適用,但是本問題由于數(shù)據(jù)的分割造成了交叉特征生成難度大、標(biāo)簽丟失等諸多新挑戰(zhàn),克服這些挑戰(zhàn)所需的技術(shù)將在下面兩節(jié)介紹.

3 隱私保護(hù)的交叉特征生成

本節(jié)介紹基于Sketch 的企業(yè)間隱私保護(hù)的交叉特征生成解決方案(如圖2 所示).該方法旨在保持共享性和隱私性的條件下,解決聯(lián)邦排序?qū)W習(xí)中的企業(yè)間交叉特征生成問題.

Fig.2 Mutual feature generation for P1圖2 P1的交叉特征生成

3.1 交叉特征介紹

為簡化說明,我們使用以下兩個交叉特征實例展示基于 Sketch 的交叉特征生成解決方案:詞頻(term frequency,簡稱TF)和逆文本頻率(inverse document frequency,簡稱IDF).在面向企業(yè)數(shù)據(jù)孤島的聯(lián)邦場景下,兩個特征定義分別如定義2、定義3 所示.

定義2(跨企業(yè)數(shù)據(jù)孤島詞頻).假設(shè)Pi,Pj∈F,d∈Dj,q∈Qi,t1,t2,…,tM是查詢q中的M個單詞.tk在文檔d中的的跨企業(yè)數(shù)據(jù)孤島詞頻,其中,TC表示出現(xiàn)的次數(shù),ld是文檔的長度.假設(shè)文檔長度不屬于隱私信息可以直接傳輸,那么計算跨企業(yè)數(shù)據(jù)孤島詞頻就等價于計算跨企業(yè)數(shù)據(jù)孤島的單詞出現(xiàn)次數(shù).

定義3(跨企業(yè)數(shù)據(jù)孤島逆文本頻率).單詞tk的跨企業(yè)數(shù)據(jù)孤島逆文本頻率為

其中,I是指示器函數(shù),輸入條件為真時值為1,否則為0.因為需要聚合各企業(yè)的詞頻,跨企業(yè)數(shù)據(jù)孤島逆文本頻率和傳統(tǒng)計算方法略有不同,將在下文著重說明.

3.2 跨企業(yè)數(shù)據(jù)孤島詞頻生成

本部分的目標(biāo)是:在保護(hù)雙方(提供文檔的一方和提供查詢的一方)數(shù)據(jù)隱私的情況下,計算跨企業(yè)數(shù)據(jù)孤島詞頻.在這樣一個多方場景下,任意兩方需要相互多次查詢對方的文檔.傳統(tǒng)的基于加密的方法在效率和靈活性上都很不足,因此,我們設(shè)計了基于Sketch 的解決方案.該數(shù)據(jù)結(jié)構(gòu)有如下優(yōu)勢:首先,它在構(gòu)造后可重用,即有新企業(yè)加入不會導(dǎo)致其他已加入企業(yè)產(chǎn)生額外開銷;其次,它響應(yīng)查詢速度很快,是常數(shù)時間復(fù)雜度;最后,由于使用了哈希函數(shù),該數(shù)據(jù)結(jié)構(gòu)很自然地隱藏了部分文本信息,在此基礎(chǔ)上進(jìn)行基于差分隱私的改進(jìn)(詳見第3.2.2節(jié)),可以實現(xiàn)更強(qiáng)的隱私保護(hù).

首先給出Sketch 數(shù)據(jù)結(jié)構(gòu)和差分隱私的相關(guān)定義(分別為定義4、定義5).

定義4(Sketch).對于一篇文檔d,為其構(gòu)造SketchS=(Enc,fS),其中:Enc是一個編碼函數(shù),使得Cd=Enc(d)是d的一個編碼數(shù)據(jù)概要;而fS是一個計數(shù)查詢函數(shù),滿足fS(dt)是單詞t的計數(shù)查詢結(jié)果.

以經(jīng)典的Count Sketch 為例(也可使用Count-Min Sketch).Count sketch 的編碼過程需要兩個哈希函數(shù)集合H={h1,h2,…,hz}和G={g1,g2,…,gz},它們是從hi:?！鶾1,w](w<<|Γ|)和gi:?！鷞?1,+1}中隨機(jī)成對抽取形成的.每個單詞t的編碼方式為

在把文檔d編碼后,將得到一個z行w列的表Cd(?,?).單詞t的計數(shù)查詢方式為

因為Sketch 上的查詢過程需要多個哈希函數(shù),我們可以通過直接混淆這些哈希函數(shù)來實現(xiàn)查詢方的隱私保護(hù).而為了定量描述文檔一方的隱私保護(hù)程度,需要定義計數(shù)查詢的ε-差分隱私(ε-differential privacy,簡稱ε-DP).因為依賴于Sketch,ε-DP 的定義和常規(guī)定義略有不同.

定義5(計數(shù)查詢的ε-差分隱私).一個隨機(jī)算法A滿足ε-DP,如果對任意相鄰文檔d和d′(只相差一個單詞)、任意單詞t的計數(shù)查詢fS和所有A的可能輸出結(jié)果o,有:

如果計數(shù)查詢的結(jié)果滿足ε-DP,那么文檔方的隱私信息就無法推斷.

接下來介紹跨企業(yè)數(shù)據(jù)孤島詞頻特征生成方案的技術(shù)細(xì)節(jié).假設(shè)第i個企業(yè)Pi有單詞t,它希望找到該單詞在另一方Pj的文檔d的詞頻.

(1)構(gòu)造Sketch

首先,企業(yè)Pj構(gòu)造文檔d的Sketch.構(gòu)造Sketch 是在各方開展通訊之前就完成的.各方使用相同的哈希函數(shù)構(gòu)造 Sketch,所以在不同的企業(yè)數(shù)據(jù)中都可以查詢.哈希函數(shù)可以通過企業(yè)間加密傳輸?shù)姆绞?如 Diffie-Hellman 密鑰交換協(xié)議)來生成索引,從而避免服務(wù)器推斷哈希函數(shù)的有關(guān)信息.按照前述公式(2)可實現(xiàn)Sketch構(gòu)造,其中,單詞來自詞匯表|Γ|,構(gòu)造后將得到一個z行w列的表格.文檔d有l(wèi)d個單詞,如果哈希過程時間復(fù)雜度為O(1),則需要花費O(zld)的時間來構(gòu)造Sketch.每個文檔的Sketch 都由各方在本地保存,只能由查詢找到某個項的頻率,構(gòu)造過程如圖3 所示.

Fig.3 Construction of the Sketch from a document圖3 一篇文檔的Sketch 構(gòu)造過程

(2)帶混淆哈希

完成Sketch 的構(gòu)造后,為得到單詞出現(xiàn)次數(shù),Pi需要使用z個H中的哈希函數(shù)將查詢中的單詞t進(jìn)行哈希.由于隱私保護(hù)的要求,不能直接在Sketch 上進(jìn)行查詢,而是隨機(jī)從H中挑選z1個哈希函數(shù)對單詞t進(jìn)行哈希.對其他的z?z1個哈希函數(shù),他們的輸入是隨機(jī)從|Γ|中選取的,使得這些單詞經(jīng)過哈希后和t經(jīng)過哈希的結(jié)果產(chǎn)生碰撞,從而實現(xiàn)混淆.經(jīng)過了這樣的哈希過程和混淆過程后,Pi將得到一個長度為z的向量,其中有z1個位置的哈希函數(shù)索引是由Pi所私有的,即:

其中,PKi是Pi的私有哈希函數(shù)索引(1 到z隨機(jī)排列后前z1個值的集合),cd(t,t′)是單詞t和t′發(fā)生碰撞的哈希函數(shù)個數(shù).Bt′包含不屬于PKi的z1?b個整數(shù),且每個Bt′彼此不重疊.因為單詞t和t′有b個哈希結(jié)果相同,我們也能找到z1個哈希函數(shù)結(jié)果和t′一致.因此,任意其他的參與方無法通過暴力枚舉z1個哈希值區(qū)分原始的單詞t和用于混淆的單詞t′.然而,我們也有,所以如果b太大,就很難找到用來混淆的單詞t′.因此,存在一個隱私保護(hù)程度和數(shù)據(jù)精度的權(quán)衡.我們設(shè)置一個較小的z1和b來實現(xiàn)相同的隱私保護(hù)程度,同時保持查詢結(jié)果的可信度.哈希處理后,Pi將把混淆的哈希向量發(fā)送給服務(wù)器,由服務(wù)器把該向量發(fā)送給Pj做進(jìn)一步查詢處理.

(3)查詢結(jié)果擾動

本步驟中,Pj將收到服務(wù)器發(fā)來的z維向量,然后使用在Count Sketch 上進(jìn)行查詢,得到1≤a≤z.把查詢的結(jié)果直接發(fā)布將產(chǎn)生隱私泄露風(fēng)險,因為惡意的攻擊者可能會查詢一些敏感單詞來推斷其他參與方的文檔詞頻分布.因此,我們設(shè)計了一個ε-DP 機(jī)制來擾動查詢的結(jié)果,以保護(hù)文檔隱私.我們的擾動機(jī)制采用拉普拉斯機(jī)制,擾動方式如下:

相關(guān)過程如圖4 所示.算法1 和算法2 分別描述了查詢方和文檔擁有者的操作過程.

Fig.4 Thecount query of term from the Sketch圖4 單詞的詞頻查詢過程

算法1.跨企業(yè)數(shù)據(jù)孤島詞頻計算:查詢方.

Input:待查詢單詞t,哈希函數(shù)H;

Output:估計的單詞頻率ft.

1:Q←空向量

2:PK←隨機(jī)生成的哈希函數(shù)編號

3:for 1≤a≤zdo

4:依據(jù)公式(4)生成哈希值

5:添加到Q結(jié)尾

6:把Q 發(fā)送給服務(wù)器

7:從服務(wù)器收到查詢結(jié)果

8:去掉混淆項

9:按照公式(6)估計ft

10:returnft

算法2.跨企業(yè)數(shù)據(jù)孤島詞頻計算:文檔持有方.

Input:文檔d,單詞的哈希值Q,哈希函數(shù)H;

Output:無.

1:按照公式(2)構(gòu)造C

2:從服務(wù)器接收向量Q

3:FQ←空向量

4:采樣N

5:for 1≤a≤zdo

6:注入噪聲

7:追加到FQ

8:把FQ發(fā)送給服務(wù)器

9:return None

3.3 跨企業(yè)數(shù)據(jù)孤島逆文本頻率生成

上文闡述了面向企業(yè)數(shù)據(jù)孤島聯(lián)邦場景下的詞頻特征生成過程,對于逆文本頻率,過程將略有不同.跨企業(yè)數(shù)據(jù)孤島逆文本頻率的定義如第3.1 節(jié)公式(1)所示.公式中分子部分表示企業(yè)所擁有的文檔總數(shù),這并非隱私信息可以直接公開.計算的主要挑戰(zhàn)來自對分母部分的計算.一個樸素的解決方案是,在每篇文檔上執(zhí)行跨企業(yè)數(shù)據(jù)孤島詞頻特征生成.然而,這樣的解決方法十分低效,僅針對一個單詞就需要進(jìn)行次查詢.造成這種低效的主要原因是:逆文本頻率的計算需要語料庫的全局信息,而不僅僅是單一的文檔信息.為了提高效率,我們設(shè)計了一種新的方法如下.

首先,從Pj的所有個文檔中生成一個新的文檔.它的單詞是所有在Dj中出現(xiàn)過的單詞,而單詞出現(xiàn)次數(shù)為所有出現(xiàn)過該單詞的文檔數(shù)量.為這個新文檔構(gòu)造一個Sketch,這樣,查詢中的每個單詞在此Sketch 上查詢的結(jié)果就是包含該單詞的文檔數(shù)量.后續(xù)步驟和跨企業(yè)數(shù)據(jù)孤島詞頻生成相同,即:使用混淆單詞隱藏查詢的真實單詞,為查詢結(jié)果添加拉普拉斯噪聲滿足差分隱私.最終的時間復(fù)雜度可以被削減為O(n).

事實上,我們還可以進(jìn)一步削減查詢的時間.可以考慮通過安全聚合的方法把各方新文檔的Sketch 聚合為一個,存儲在服務(wù)器上.這樣,未來的查找可以在O(1)時間內(nèi)完成.

3.4 其他跨企業(yè)數(shù)據(jù)孤島特征

上文我們主要介紹了詞頻和逆文本頻率的跨企業(yè)數(shù)據(jù)孤島隱私保護(hù)交叉特征生成方案,該方法可以很容易拓展到其他排序?qū)W習(xí)所使用的統(tǒng)計特征中.舉例來說,幾乎所有LETOR 4.0[51]所使用的特征(網(wǎng)頁鏈接數(shù)等文檔重要度特征除外)都可以通過這兩個基本操作來生成.例如,依據(jù)前面所介紹的跨企業(yè)數(shù)據(jù)孤島詞頻和逆文本頻率,可以定義跨企業(yè)數(shù)據(jù)孤島BM25[49]特征:

其中,avdl是文檔的平均長度,l是查詢的長度,k1是超參數(shù).不難發(fā)現(xiàn):如果詞頻和逆文本頻率是事先算好的,那么BM25 可以在O(l)的時間內(nèi)計算出來.

同理可以定義LMIR[50]的諸多特征:

其中,λ和μ是超參數(shù),p(t|Di)是單詞在文檔中的詞頻.

最后,對每個企業(yè)可以生成一個新的數(shù)據(jù)集X′.該數(shù)據(jù)包含了自身查詢語句和其他企業(yè)的文檔產(chǎn)生的交叉特征,滿足了共享性.

3.5 隱私保護(hù)與精度損失的理論分析

本部分分析我們的跨企業(yè)數(shù)據(jù)孤島隱私保護(hù)交叉特征生成方案的隱私保護(hù)情況和精度損失情況.

3.5.1 隱私保護(hù)上界

差分隱私是聯(lián)邦學(xué)習(xí)場景中定量衡量隱私保護(hù)程度的事實標(biāo)準(zhǔn).從定義5 可以看出,其核心思想是用概率之比衡量不可區(qū)分性.下面我們將證明我們的方法滿足ε-差分隱私.

定理1.對任意計數(shù)查詢,公式(5)的擾動方法滿足ε-差分隱私.

證明:設(shè)文檔d′的長度為ld′=ld+1.文檔d和d′是相鄰的文檔,即前l(fā)d個單詞相同,而d′比d多一個單詞t′.由每對哈希函數(shù)彼此獨立,可得:

對任意一個確定的企業(yè)i,我們分析相鄰文檔d和d′中單詞經(jīng)過擾動后的不可區(qū)分程度.具體來說,分為兩文檔單詞不同的情況(t≠t′)和單詞相同的情況(t=t′).

對?t≠t′的情況,可得:

因此,fC(d′,t)=fC(d,t)+1,于是可得定理得證.□

從上面的證明過程可以看出:雖然我們的方法中帶混淆哈希和拉普拉斯噪聲都提供了單詞的不可區(qū)分性,但是拉普拉斯噪聲的方差直接反比于隱私預(yù)算ε,僅拉普拉斯噪聲提供的不可區(qū)分性就足以提供滿足ε-差分隱私的保護(hù)了.為了進(jìn)一步充分利用帶混淆哈希所產(chǎn)生的不可區(qū)分性,可以適當(dāng)降低拉普拉斯噪聲的注入量.

推論1.若注入的拉普拉斯噪聲,其中,,則公式(5)的擾動方法依然滿足ε-差分隱私.

證明:根據(jù)定理1 的證明,我們有:

3.5.2 精度損失上界

Count Sketch 的頻率估計是一個無偏估計,其方差為,其中,.為了進(jìn)一步降低精度的損失,可以考慮利用數(shù)據(jù)的偏度實現(xiàn)對方差的進(jìn)一步控制.文檔中,單詞的頻率通常滿足齊夫定律,按照文獻(xiàn)[52],F2可以進(jìn)行如下放大:

定理2.對于一個單詞t,如果z1被設(shè)定為的,那么至少有1?δ的概率,可以保證詞頻估計有如下上界:

證明:依據(jù)公式(6),我們有:

由Count Sketch 估計的期望和方差以及拉普拉斯噪聲的方差,可得:

按照齊夫定律關(guān)于詞頻分布規(guī)律的假設(shè),不論如何選取哈希函數(shù),總有7/8 的概率,使得的最頻繁項和給定的單詞k在任意給定行都不會發(fā)生碰撞.因此,

證明:首先證明任意兩個單詞t1和t2以及任意的a∈PK,Ca(t1)和Ca(t2)是獨立的.這是因為我們有:

4 半監(jiān)督協(xié)同排序?qū)W習(xí)

本節(jié)介紹半監(jiān)督協(xié)同排序?qū)W習(xí)方法,來克服標(biāo)簽缺失的挑戰(zhàn).在一個企業(yè)所持有的數(shù)據(jù)之內(nèi),可以很容易地評估查詢和文檔生成的交叉特征樣本的相關(guān)性,形成帶標(biāo)簽的樣本數(shù)據(jù).但是跨企業(yè)數(shù)據(jù)孤島所生成的交叉特征卻無法直接評估相關(guān)性,因此不存在標(biāo)簽.現(xiàn)有的半監(jiān)督學(xué)習(xí)方法并不能直接應(yīng)用到本問題中,主要有兩個原因:一是帶標(biāo)簽和不帶標(biāo)簽的數(shù)據(jù)都是分屬各方的,如圖5 所示;二是半監(jiān)督學(xué)習(xí)過程也需要考慮原始數(shù)據(jù)的隱私.為了解決上述問題,我們首先提出一個簡單的半監(jiān)督學(xué)習(xí)基準(zhǔn)算法,然后再設(shè)計一個協(xié)同學(xué)習(xí)的方法.

Fig.5 Framework of semi-supervised collaborative learning圖5 半監(jiān)督協(xié)同訓(xùn)練框架

4.1 基準(zhǔn)算法:本地訓(xùn)練

每個企業(yè)擁有自身的帶標(biāo)簽數(shù)據(jù)(Xi,yi)和無標(biāo)簽數(shù)據(jù)X′,它可以在本地利用這些數(shù)據(jù)以半監(jiān)督訓(xùn)練的方式得到一個模型.本地訓(xùn)練可以自然符合數(shù)據(jù)不離開本地的特點,所以簡單地滿足了隱私限制.本地訓(xùn)練中,可以使用一個通用的偽標(biāo)簽生成器來實現(xiàn)半監(jiān)督學(xué)習(xí).學(xué)習(xí)過程就是求解如下最優(yōu)化問題:

其中,y′是x′由偽標(biāo)簽生成器生成的的偽標(biāo)簽,β是無標(biāo)簽數(shù)據(jù)的權(quán)重.偽標(biāo)簽生成器的設(shè)計有多種方法,我們簡單地直接使用上一輪的模型給無數(shù)據(jù)打標(biāo)簽.最后,各方都會持有一個由自己訓(xùn)練的私有模型Mi作為最終結(jié)果.在這種方案中,生成的無標(biāo)簽數(shù)據(jù)并沒有被充分使用,所以我們提出了一個改進(jìn)的協(xié)同訓(xùn)練方案.

4.2 無標(biāo)簽數(shù)據(jù)的協(xié)同訓(xùn)練

一個直接的協(xié)同訓(xùn)練方法是:只使用各方的帶標(biāo)簽數(shù)據(jù),問題就被規(guī)約為標(biāo)準(zhǔn)的橫向聯(lián)邦學(xué)習(xí).但是在這種情況下,針對查詢的數(shù)據(jù)依然十分短缺,即每條查詢所對應(yīng)的特征空間不夠大.此外,隱私保護(hù)也不應(yīng)被忽視,因為梯度可能泄漏敏感信息.

為了能更好地使用這些豐富但無標(biāo)簽的、同時不包含Pi隱私信息的數(shù)據(jù),我們設(shè)計了如下方法:首先,在協(xié)同訓(xùn)練之前,各方先在本地使用自身帶標(biāo)簽數(shù)據(jù)訓(xùn)練一個分類模型Mi;之后,各方把這個本地模型發(fā)送給服務(wù)器,服務(wù)器聚合這些模型作為一個標(biāo)簽生成器,即;Agg(?)對各個模型的參數(shù)求平均,得到全局模型.由各方共享,且它也是標(biāo)簽生成器和排序模型的初始值.

可以以串行或并行的方式運行梯度下降算法.在每一輪迭代中,各方在本地使用一批帶標(biāo)簽和無標(biāo)簽數(shù)據(jù)運行梯度下降算法,并提交梯度變化Δθ給服務(wù)器.協(xié)同訓(xùn)練過程中使用的訓(xùn)練數(shù)據(jù)就是前文介紹的給類交叉特征.交叉特征的生成過程需要使用企業(yè)的原始文本數(shù)據(jù),所以我們設(shè)計了帶混淆哈希、拉普拉斯噪聲注入等方法保護(hù)隱私.而協(xié)同訓(xùn)練的過程只是在使用這些特征,并不涉及企業(yè)原始數(shù)據(jù),并且無標(biāo)簽數(shù)據(jù)的來源只有提交查詢的Pi知道,即使攻擊者有能力依據(jù)梯度更新反推出用于訓(xùn)練的交叉特征,仍然不會泄漏企業(yè)的原始文本數(shù)據(jù),所以我們不再對Δθ使用額外的隱私保護(hù)手段.最后,隨著θ的收斂,各方將獲得一個全局模型M.其他細(xì)節(jié)詳見算法3.

算法3.半監(jiān)督協(xié)同訓(xùn)練算法

Input:帶標(biāo)簽和無標(biāo)簽數(shù)據(jù),其他參數(shù);

Output:全局模型.

1:for 企業(yè)Pido

2:Pi訓(xùn)練一個本地模型Mi

5:使用M給無標(biāo)簽數(shù)據(jù)打標(biāo)簽

6:fort=1,2,… do

7:for 企業(yè)Pido

8: 收集帶標(biāo)簽和無標(biāo)簽數(shù)據(jù)批數(shù)據(jù)

9: 根據(jù)公式(9)更新權(quán)重θ

10:returnM

5 實驗評估

本節(jié)介紹實驗結(jié)果來證明所提方法的有效性.

5.1 數(shù)據(jù)集和實驗設(shè)置

以LETOR4.0[51]為代表的大部分標(biāo)準(zhǔn)數(shù)據(jù)集都只包含了已經(jīng)提取好的特征,而沒有原始的文檔和查詢數(shù)據(jù),因此無法應(yīng)用在我們的實驗中.本文中,我們選擇MS MARCO 排序數(shù)據(jù)集(http://www.msmarco.org/dataset.aspx),從中采樣部分?jǐn)?shù)據(jù)用于實驗.假設(shè)企業(yè)的數(shù)量為4,每一方只有有限的帶標(biāo)簽的查詢結(jié)果.從MS MARCO中采樣4 個子集,每個包含約200 條查詢和40 000 篇文檔,每篇文檔有大約1 000 個單詞.我們所提出的技術(shù)是為數(shù)據(jù)規(guī)模較小的企業(yè)提供幫助,因此設(shè)置單個企業(yè)數(shù)據(jù)孤島的數(shù)據(jù)規(guī)?？刂圃?04數(shù)量級.使用每條查詢最相關(guān)的100 篇文檔的相關(guān)度分?jǐn)?shù)作為標(biāo)簽.最相關(guān)的10 篇文檔被標(biāo)記為非常相關(guān)(相關(guān)性分?jǐn)?shù)為2),排在11 名～100 名的文檔是相關(guān)(相關(guān)性分?jǐn)?shù)為1),100 名以外是不相關(guān)(相關(guān)性分?jǐn)?shù)為0).對每一方,生成約2.4 萬條帶標(biāo)簽數(shù)據(jù),并取其中7 000 條樣本數(shù)據(jù)構(gòu)造全局測試集(共2.8 萬條).

在半監(jiān)督學(xué)習(xí)模型的設(shè)置方面,我們采用點排序模型.模型結(jié)構(gòu)為線性分類模型.損失函數(shù)設(shè)置為交叉熵,并且引入了L2 正則項.本地訓(xùn)練和全局訓(xùn)練因為數(shù)據(jù)規(guī)模不同,分別設(shè)置迭代1 000,2 000 輪次.更新過程采用批處理隨機(jī)梯度下降,全局模型的更新在每一批數(shù)據(jù)處理完成后進(jìn)行.而所提算法則取本地模型平均用來打標(biāo)簽,以開展線性回歸訓(xùn)練.

交叉特征選取的主要依據(jù)是LETOR4.0 所使用的公認(rèn)排序?qū)W習(xí)特征.查詢分別和文檔的標(biāo)題與正文交叉計算詞頻、逆文本頻率、TF-IDF、BM25、LMIR.ABS、LMIR.DIR、LMIR.JM 屬性,結(jié)合文檔標(biāo)題長度與正文長度,形成一條擁有16 個特征的樣本數(shù)據(jù).與LETOR4.0 相比,我們的排序?qū)ο笫羌兾谋疚臋n,不包含鏈接數(shù)量、網(wǎng)址深度等網(wǎng)頁文檔的特有特征.此外,除了我們所采用的查詢語句和正文與標(biāo)題分別計算的交叉特征外,LETOR4.0 還進(jìn)一步把正文與標(biāo)題看作整體,再與查詢語句進(jìn)行交叉特征計算.但是我們的排序?qū)ο笳拈L度大,把標(biāo)題和正文結(jié)合和僅考慮正文相比差異不大,加之過多特征還會顯著拖慢訓(xùn)練速度,所以我們并未引入這些特征.我們?yōu)槊恳环缴闪?.97 萬條跨企業(yè)數(shù)據(jù)孤島數(shù)據(jù),用于半監(jiān)督協(xié)同學(xué)習(xí).可以看到:同單個企業(yè)數(shù)據(jù)孤島所能產(chǎn)生的2.4 萬條數(shù)據(jù)相比,交叉特征生成的過程顯著增加了訓(xùn)練樣本數(shù)量.增加的數(shù)據(jù)對于模型訓(xùn)練的幫助將在后面的實驗中具體說明.文檔的預(yù)測順序?qū)凑漳Ｐ徒o出的預(yù)測分?jǐn)?shù)從高到低排序.評估排序好壞的指標(biāo)有:

? 期望倒數(shù)排名(expected reciprocal rank,簡稱ERR).評估相關(guān)度高的文檔其排序位置是否靠前,計算方式為

其中,reli表示排序在第i個位置文檔的相關(guān)性分?jǐn)?shù)(即0,1,2),relmax為最大的相關(guān)性分?jǐn)?shù)(即為2);

? 平均準(zhǔn)確率(mean average precision,簡稱MAP).評估排序?qū)W習(xí)模型給出的順序與按照實際相關(guān)度排序的差別,計算方式為

其中,rank(d)表示文檔d按照相關(guān)度分?jǐn)?shù)排序時的位置,position(d)為排序?qū)W習(xí)模型給出的位置;

? 歸一化折損累計增益(normalized discounted cumulative gain,簡稱nDCG).綜合考慮相關(guān)性和排序位置的評估指標(biāo),計算方式為

其中,IDCG 為歸一化系數(shù),其值為文檔按照相關(guān)度分?jǐn)?shù)降序排列時得到的

? 前10 名歸一化折損累計增益(normalized discounted cumulative gain at 10,簡稱nDCG@10).即排在前10 文檔的nDCG.計算方式為

我們的方法是為全新的交叉分割聯(lián)邦學(xué)習(xí)場景設(shè)計的,目前尚未有其他方法能夠適用于這樣的場景.這讓我們很難找到其他的橫向?qū)Ρ确椒?因此,我們實驗的重點在于檢驗使用交叉特征生成進(jìn)行增廣的數(shù)據(jù)集是否有助于排序模型的性能提升,于是選取以下3 種方法同所提算法CS-F-LTR 進(jìn)行比較.

? Local:各方僅使用自己的帶標(biāo)簽數(shù)據(jù)訓(xùn)練一個模型;

? Local+:各方使用自己的帶標(biāo)簽和無標(biāo)簽數(shù)據(jù)訓(xùn)練一個半監(jiān)督模型;

? Global:各方使用帶標(biāo)簽數(shù)據(jù)協(xié)同訓(xùn)練一個模型,和橫向聯(lián)邦學(xué)習(xí)場景類似.

5.2 實驗結(jié)果

5.2.1 主要結(jié)果

在表4 中,我們記錄了Local,Local+,Global 和CS-F-LTR 的4 項評估指標(biāo).

Table 4 Comparison results表4 比較結(jié)果

可以發(fā)現(xiàn):各方的nDCG@10 指標(biāo)在Local 方法下結(jié)果為0.7 左右,該方法只采用了本地數(shù)據(jù)來訓(xùn)練.而Local+的方法使用了無標(biāo)簽數(shù)據(jù),因此在一定程度上可以提高本地模型的表現(xiàn).企業(yè)B,C的nDCG@10 分別增長了5.8%,3.1%,企業(yè)D略微變好,企業(yè)A略微更差.這是因為各方的數(shù)據(jù)并不一定是獨立同分布的.所以各方依據(jù)自身數(shù)據(jù)所訓(xùn)練的偽標(biāo)簽生成器在給交叉產(chǎn)生的互特征生成標(biāo)簽時,如果雙方數(shù)據(jù)分布差異過大,打標(biāo)簽就可能出錯.在CS-F-LTR 中,通過模型平均和使用無標(biāo)簽數(shù)據(jù),nDCG@10 有一個明顯的提高,從0.65～0.75 的范圍升高到0.83.同時,把CS-F-LTR 和Global 所訓(xùn)練的模型比較,后者雖然也聚合了數(shù)據(jù)但是沒有使用半監(jiān)督學(xué)習(xí)的方法,通過比較發(fā)現(xiàn),nDCG@10 分?jǐn)?shù)提高了.而對于其他的評價指標(biāo),分?jǐn)?shù)也有一定的提高.

各企業(yè)在使用不同方法訓(xùn)練過程中,nDCG@10 指標(biāo)隨迭代過程變化如圖6 所示.可以看出:本地訓(xùn)練的兩個方法(Local 和Local+)因為使用的數(shù)據(jù)有限,性能顯著低于全局方法訓(xùn)練的模型;而在兩個全局方法(CS-FLTR 和Global)中,我們所提出的CS-F-LTR 方法因為能夠進(jìn)一步使用無標(biāo)簽數(shù)據(jù)采用半監(jiān)督學(xué)習(xí)的策略,因此性能更勝一籌.此外,對任一企業(yè),采用全局方法進(jìn)行訓(xùn)練得到的模型和僅在本地開展訓(xùn)練得到模型相比,在性能上有顯著提升,這也從客觀上推動了各企業(yè)破除“數(shù)據(jù)孤島”開展合作.

Fig.6 Comparison among different solutions on each data silo圖6 各企業(yè)數(shù)據(jù)孤島中不同方法的性能比較

5.2.2 Sketch 的影響

我們評估了不同的Sketch 策略:使用CountSketch(CS)和Count-MinSketch(CMS)兩種Sketch 類型,使用不同的哈?？臻gw和使用不同數(shù)量的哈希函數(shù)z1,實驗結(jié)果如圖7 所示.

Fig.7 Evaluation of different sketch strategies圖7 不同Sketch 構(gòu)造策略評估

從全局隨機(jī)抽取400 個正負(fù)樣本(相關(guān)度分?jǐn)?shù)大于0 為正樣本,否則為負(fù)樣本),構(gòu)造不同的Sketch 來評估影響.為了能更清楚地展示實驗結(jié)果,通過TSNE 把樣本點嵌入到二維平面中.圖7(a)展現(xiàn)了沒有Sketch 的情況,圖7(b)對應(yīng)CS-F-LTR 中的Sketch 構(gòu)造方法.可以看到:在使用Sketch 以后,不同類別之間的分界線依然是可以辨認(rèn)的.我們也嘗試使用相同的參數(shù)構(gòu)造了CM Sketch,結(jié)果如圖7(e).隨著哈?？臻gw的減小,噪聲在增加(圖7(c)和圖7(d)),這說明準(zhǔn)確度關(guān)于哈希空間w十分敏感.哈?？臻g越小,越多的單詞會彼此碰撞,詞頻和其他特征的計算結(jié)果就會越不準(zhǔn)確.然而,當(dāng)哈希函數(shù)的數(shù)量z1減少時,結(jié)果會更加魯棒.即使當(dāng)z1為5(如圖7(f)所示)或者3(如圖7(g)所示)時,依然有一個明顯的分界.當(dāng)z減小到1 時,分界才開始模糊(如圖7(h)所示).這說明:當(dāng)z確定時,一個較小的z1依然可以保證較為準(zhǔn)確的特征,同時保持較好的隱私保護(hù).

5.2.3 隱私預(yù)算的影響

隱私預(yù)算的影響如圖8(a)所示,我們驚訝地發(fā)現(xiàn):將少量噪聲(ε為0.5)注入到樣本數(shù)據(jù)中,會帶來更好的效果.可能的原因是噪聲值增加到了無標(biāo)簽數(shù)據(jù)上,并且他們的偽標(biāo)簽可能不正確,這種情況下,增加噪聲可以避免模型過擬合,從而提高泛化性能.隨著噪聲進(jìn)一步增加,模型表現(xiàn)開始變差,但依然是可控的.半監(jiān)督訓(xùn)練過程就像是一個微調(diào)過程,而帶標(biāo)簽數(shù)據(jù)則為微調(diào)方向提供了一個很好的指引.

Fig.8 Impact of privacy budgetand number of datasiloson CS-F-LTR圖8 隱私預(yù)算和企業(yè)數(shù)據(jù)孤島數(shù)量對CS-F-LTR 算法的影響

5.2.4 企業(yè)數(shù)據(jù)孤島數(shù)量的影響

企業(yè)數(shù)據(jù)孤島數(shù)量的影響如圖8(b)所示.可以看到:幾乎所有的指標(biāo)都在隨著企業(yè)數(shù)量的增加而增長.nDCG@10 和MAP 隨著企業(yè)數(shù)量從1 增長到5 有著8%的增長,這說明了CS-F-LTR 的有效性.而nDCG 的增長并不顯著,這是因為每一條查詢在測試集中有太多不相關(guān)的文檔.ERR的數(shù)值先降低后增加,最終增加了5%.可能的原因是:當(dāng)企業(yè)數(shù)量小的時候,各企業(yè)中數(shù)據(jù)分布差異大,非獨立同分布特點明顯,從而影響了某些指標(biāo).

5.2.5 實驗總結(jié)

從以上結(jié)果可以看出,CS-F-LTR 方法和本地訓(xùn)練相比是更加有效的.更多的參與方可以提高模型的性能.同時,該方法關(guān)于隱私相關(guān)的參數(shù)也是魯棒的,這說明它能夠更好地平衡隱私保護(hù)的程度和模型的性能.然而,CS-F-LTR 的有效性也取決于各企業(yè)的數(shù)據(jù)分布情況.如果數(shù)據(jù)分布差異過大,增加更多的企業(yè)可能并不總是對提高性能有效,這也是符合常理的.

6 總結(jié)與展望

本文研究了在面向企業(yè)數(shù)據(jù)孤島聯(lián)邦場景下的排序?qū)W習(xí)問題.首先.針對這一特定問題,總結(jié)出了一種不同于現(xiàn)有橫向或縱向聯(lián)邦場景的新型面向企業(yè)數(shù)據(jù)孤島的聯(lián)邦場景——交叉分割聯(lián)邦場景,并提出了聯(lián)邦框架CS-F-LTR,該框架可以幫助那些本地數(shù)據(jù)不足的企業(yè)間合作構(gòu)建專有的文檔檢索系統(tǒng).我們主要解決了該問題中的兩大挑戰(zhàn):一是跨企業(yè)數(shù)據(jù)孤島的交叉特征生成問題,即隱私保護(hù)限制造成了大量交叉特征數(shù)據(jù)無法被生成和利用.為此,我們提出了基于Sketch 與差分隱私的解決方法.可以在實現(xiàn)隱私保護(hù)滿足差分隱私要求的前提下,實現(xiàn)誤差可控的詞頻、逆文檔頻率等交叉特征的計算.二是生成數(shù)據(jù)標(biāo)簽缺失的問題,即用于交叉特征生成的查詢和文檔因分屬不同企業(yè)無法直接評估相關(guān)性.我們使用半監(jiān)督協(xié)同學(xué)習(xí)的方法解決了該問題.最終,在公開數(shù)據(jù)集上的實驗結(jié)果驗證了我們提出方法的有效性.

與此同時,聯(lián)邦排序?qū)W習(xí)的未來研究仍存在諸多挑戰(zhàn).首先是數(shù)據(jù)非獨立同分布的問題.各企業(yè)數(shù)據(jù)分布可能存在不均衡性,對模型性能會產(chǎn)生影響.不同企業(yè)所持有的數(shù)據(jù)不一定滿足獨立同分布的假設(shè),這可能導(dǎo)致不同企業(yè)本地所訓(xùn)練的模型泛化性能降低,從而影響全局模型性能.其次是排序模型的拓展性問題.本文中,排序模型使用了經(jīng)典的點排序模型;而對于基于文檔對和文檔列表的排序方法,因其標(biāo)簽和特征更加復(fù)雜,該框架中的特征生成和半監(jiān)督學(xué)習(xí)方法需要進(jìn)一步設(shè)計.最后是傳輸可靠性問題.雖然本文所提框架主要是針對企業(yè)間的聯(lián)邦場景,但依然可能存在網(wǎng)絡(luò)時延、掉線等因素破壞模型的訓(xùn)練進(jìn)程,提高魯棒性也是值得研究的問題.

目前,數(shù)據(jù)非獨立同分布問題和傳輸可靠性問題是聯(lián)邦學(xué)習(xí)領(lǐng)域的熱點問題,已經(jīng)有諸多研究可以參考.而針對排序模型的拓展性問題,則應(yīng)該結(jié)合訓(xùn)練所需的樣本結(jié)構(gòu)設(shè)計新的協(xié)作方式和傳輸規(guī)劃.未來,克服上述挑戰(zhàn)將有助于徹底打通企業(yè)數(shù)據(jù)孤島,并促成聯(lián)邦排序?qū)W習(xí)的真實應(yīng)用落地.