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

1(軟件開(kāi)發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室(北京航空航天大學(xué)),北京 100191)

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

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

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

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

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

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

本文致力于解決上述兩大挑戰(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ù)孤島場(chǎng)景下的聯(lián)邦排序?qū)W習(xí)問(wèn)題,并提出相應(yīng)的解決框架,進(jìn)一步指明了其兩大研究挑戰(zhàn),即交叉特征生成與缺失標(biāo)簽處理.目前,尚未有任何面向企業(yè)數(shù)據(jù)孤島的聯(lián)邦排序?qū)W習(xí)相應(yīng)研究成果;

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

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

(4)本文通過(guò)公開(kāi)數(shù)據(jù)集的大量實(shí)驗(yàn),驗(yàn)證了所提算法的有效性.

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

2 問(wèn)題描述

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

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

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

與其他機(jī)器學(xué)習(xí)問(wèn)題類似,開(kāi)展排序?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ù)某篇文檔和某個(gè)查詢,生成交叉特征,如詞頻(term frequency,簡(jiǎn)稱TF)、BM25[49]和LMIR[50]等.

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

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

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

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

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

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

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

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

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

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

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

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

3.1 交叉特征介紹

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

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

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

其中,I是指示器函數(shù),輸入條件為真時(shí)值為1,否則為0.因?yàn)樾枰酆细髌髽I(yè)的詞頻,跨企業(yè)數(shù)據(jù)孤島逆文本頻率和傳統(tǒng)計(jì)算方法略有不同,將在下文著重說(shuō)明.

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

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

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

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

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

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

因?yàn)镾ketch 上的查詢過(guò)程需要多個(gè)哈希函數(shù),我們可以通過(guò)直接混淆這些哈希函數(shù)來(lái)實(shí)現(xiàn)查詢方的隱私保護(hù).而為了定量描述文檔一方的隱私保護(hù)程度,需要定義計(jì)數(shù)查詢的ε-差分隱私(ε-differential privacy,簡(jiǎn)稱ε-DP).因?yàn)橐蕾囉赟ketch,ε-DP 的定義和常規(guī)定義略有不同.

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

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

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

(1)構(gòu)造Sketch

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

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

(2)帶混淆哈希

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

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

(3)查詢結(jié)果擾動(dòng)

本步驟中,Pj將收到服務(wù)器發(fā)來(lái)的z維向量,然后使用在Count Sketch 上進(jìn)行查詢,得到1≤a≤z.把查詢的結(jié)果直接發(fā)布將產(chǎn)生隱私泄露風(fēng)險(xiǎn),因?yàn)閻阂獾墓粽呖赡軙?huì)查詢一些敏感單詞來(lái)推斷其他參與方的文檔詞頻分布.因此,我們?cè)O(shè)計(jì)了一個(gè)ε-DP 機(jī)制來(lái)擾動(dòng)查詢的結(jié)果,以保護(hù)文檔隱私.我們的擾動(dòng)機(jī)制采用拉普拉斯機(jī)制,擾動(dòng)方式如下:

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

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

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

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

Output:估計(jì)的單詞頻率ft.

1:Q←空向量

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

3:for 1≤a≤zdo

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

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

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

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

8:去掉混淆項(xiàng)

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

10:returnft

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

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

Output:無(wú).

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

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

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

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

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

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

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

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

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

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

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

3.5.1 隱私保護(hù)上界

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

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

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

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

對(duì)?t≠t′的情況,可得:

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

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

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

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

3.5.2 精度損失上界

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

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

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

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

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

證明:首先證明任意兩個(gè)單詞t1和t2以及任意的a∈PK,Ca(t1)和Ca(t2)是獨(dú)立的.這是因?yàn)槲覀冇?

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

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

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

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

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

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

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

一個(gè)直接的協(xié)同訓(xùn)練方法是:只使用各方的帶標(biāo)簽數(shù)據(jù),問(wèn)題就被規(guī)約為標(biāo)準(zhǔn)的橫向聯(lián)邦學(xué)習(xí).但是在這種情況下,針對(duì)查詢的數(shù)據(jù)依然十分短缺,即每條查詢所對(duì)應(yīng)的特征空間不夠大.此外,隱私保護(hù)也不應(yīng)被忽視,因?yàn)樘荻瓤赡苄孤┟舾行畔?

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

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

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

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

Output:全局模型.

1:for 企業(yè)Pido

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

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

6:fort=1,2,… do

7:for 企業(yè)Pido

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

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

10:returnM

5 實(shí)驗(yàn)評(píng)估

本節(jié)介紹實(shí)驗(yàn)結(jié)果來(lái)證明所提方法的有效性.

5.1 數(shù)據(jù)集和實(shí)驗(yàn)設(shè)置

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.2 實(shí)驗(yàn)結(jié)果

5.2.1 主要結(jié)果

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

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

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

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

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

5.2.2 Sketch 的影響

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

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

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

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

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

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

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

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

5.2.5 實(shí)驗(yàn)總結(jié)

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

6 總結(jié)與展望

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

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

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