面向企业数据孤岛的联邦排序学习∗

史鼎元,王晏晟,郑鹏飞,童咏昕

1(软件开发环境国家重点实验室(北京航空航天大学),北京 100191)

2(大数据科学与脑机智能高精尖创新中心(北京航空航天大学),北京 100191)

3(北京航空航天大学 计算机学院,北京 100191)

近年来,排序学习(learning-to-rank,简称LTR)在信息检索领域取得了巨大的成功[1−3],这种成功在诸如谷歌(Google)与必应(Bing)等具备大量用户数据资源的商业搜索引擎上尤为显著.排序学习算法的有效性离不开大量训练数据的支撑,搜索引擎巨头公司的数据往往由搜索引擎与其上千万甚至上亿用户在每日的频繁交互中产生.然而,众多普通规模的中小型企业也有搭建搜索引擎或搜索系统的需求,如企业搜索(enterprise search)或邮件搜索,但其并不具备单独收集大规模用户数据的实力.中小型企业与企业之间,乃至企业的部门之间存在的数据孤岛(data silo)问题导致了大量数据分散存储,出于企业机密保护以及行政手续复杂等原因难以被打通.与此同时,随着越来越多的数据隐私保护法规如欧盟的“通用数据保护条例(general data protection regulation,简称GDPR)”等的出台,即使企业在主观上愿意,其也无法再像以往一样自由地交换或分享含有用户隐私的数据.种种不利因素,使得中小型企业很难利用强大的排序学习算法与大数据的支撑搭建其自己的有效搜索系统[4].因此,如何为各企业克服数据孤岛障碍,在满足隐私保护的约束下训练有效的排序学习,是一个亟待解决的问题.

为了解决上述问题,在本文中,我们首次提出了面向企业数据孤岛的联邦排序学习(cross-silo federated LTR,简称CS-F-LTR),其致力于协调多方企业或组织在不交换各自原始数据的前提下,联合训练有效的排序学习模型.一方面,与分布式排序学习不同的是:在本文场景下,训练排序学习模型所需的排序对象(如文档、电子邮件等)与查询语句均被分散地存储在各方,原始数据被动地被分隔且无法自由交互,只能由各方借助隐私保护的手段来生成排序学习所需的训练样本;而在分布式场景下,训练样本是提前由原始数据计算所得再进行数据分割的.同时,无论是训练样本的生成或是后续的训练过程中,各分布式节点的数据交互都不受隐私约束[5].另一方面,本文的联邦学习场景与现有的其他联邦学习也有着很大的不同.现有的联邦学习中,数据一般是被横向分割(horizontally-partitioned)或纵向分割(vertically-partitioned)[6].在横向分割场景中,联邦中每一方都拥有若干互不重叠的训练样本,每个样本包含了完整的训练特征(features)与标签(labels);在纵向分割场景中,联邦每一方都拥有完整的全样本,但是各个特征以及标签为不同方所拥有.然而,本文的数据分割场景不同于上述任意一个,我们将其命名为交叉分割(cross-partitioned).在交叉分割场景下,每一条训练样本的特征是由联邦任意两方的排序对象与查询语句交叉计算所得.举例而言,甲方拥有一条样本,其中查询关键词为“电影”,排序对象为一篇影评,标签为“相关”;乙方拥有一条样本,其查询关键词为“美食”,排序对象为一篇食谱,标签为“相关”.此时,如果遵从现有的横向联邦学习场景,联邦中共有两条标签均为“相关”的样本.而本文场景下,则将新增两个特征对应了“电影-食谱”与“美食-影评”同时标签未知的交叉样本.上述3 种分割场景如图1 所示.其中,特殊的交叉分割场景给本文的面向企业数据孤岛联邦学习框架带来了如下挑战.

(1)交叉特征生成:如何在隐私保护约束下安全地连接各方的查询语句与排序对象,从而生成有效的排序学习样本特征.在现有的排序学习研究工作中[7],许多具有表现力的特征都是通过查询语句与排序对象联合计算所得(如查询语句中单词在排序文档中出现的频率等).因此,需要一种各方的查询语句与其他方排序对象之间安全交互、从而计算特征的方法;

(2)缺失标签处理:如何应对交叉样本中的标签缺失问题.通过上文例子可以发现,交叉样本往往只具有训练特征而无法直接获取其准确的标签.对某一方来说,要想获知其文档在其他方查询语句下的相关度而不泄露各自的文档与查询语句信息是一件极其困难的事,这也将我们面临的问题转变为一个联邦场景下的半监督学习问题.

本文致力于解决上述两大挑战,并提出高效的联邦排序学习算法.

Fig.1 Three types of data partitions in federated learning图1 联邦学习中3 种类型的数据分割

本文的主要贡献如下:

(1)首次定义了企业数据孤岛场景下的联邦排序学习问题,并提出相应的解决框架,进一步指明了其两大研究挑战,即交叉特征生成与缺失标签处理.目前,尚未有任何面向企业数据孤岛的联邦排序学习相应研究成果;

(2)为了应对交叉特征生成的挑战,本文提出了基于略图(sketch)数据结构的交叉特征生成算法,并在理论上证明了算法具有的隐私性与结果精度的保证;

(3)为了应对缺失标签处理的挑战,本文提出了一种半监督联合训练算法,通过交互的标签生成器,来高效与准确地推断交叉样本对应的缺失标签;

(4)本文通过公开数据集的大量实验,验证了所提算法的有效性.

本文第1 节将介绍相关工作.第2 节将给出问题定义.第3 节与第4 节将分别讨论交叉特征生成与缺失标签处理相对应的解决方案.第5 节将展示实验结果.最后,在第6 节进行文章总结.

1 相关工作

1.1 隐私保护的信息检索

信息检索系统通常包含同时来自于服务器端与客户端的大量数据,在当下流行的基于排序学习的信息检索框架下,这些大数据经常被用来训练排序学习模型.随着排序模型的使用日渐广泛,用于训练排序模型的数据种类也逐渐增多,如客户端的浏览器的查询历史信息、移动端的时空轨迹信息[8]、甚至是医学数据[9]等.这些数据能够反映用户的网络浏览习惯、出行规律和健康状况,属于隐私敏感的信息.这些信息难以通过简单的脱敏手段来消除隐私泄露隐患,历史上就曾发生过著名的AOL 数据隐私泄露事件[10].现如今,大多数基于隐私保护的信息检索算法都致力于保护客户端数据隐私免受来自恶意或半诚实的服务器的攻击.其中,一项早期研究成果提出了名为隐私信息检索(private information retrieval,简称PIR)的模型[11].然而,该模型过于理想化,需要通过数据库的复制来实现隐私保护,因此缺乏实际应用价值.还有一些研究通过评估查询语句所访问数据的敏感程度,实现隐私泄漏风险控制[12],这种方法的查询结果严重受限于数据的私密程度.一些更加实用的方法通过混淆化的查询语句来保护用户的隐私,其混淆化的手段也是多样的,如重构查询语句[13,14]、插入掩蔽语句[15]、或是满足差分隐私(differential privacy,简称DP)的噪声[16]等.另一大类模型被称为对称隐私信息检索(symmetricallyprivate information retrieval,简称SPIR),其在防御恶意服务器攻击的同时,也考虑了恶意用户的攻击,同时保护了双方的数据隐私[17].为了实现对称化的隐私保护[18,19],许多基于安全关键词查询的方法被提出,其中较为著名的有可搜索对称加密(searchable symmetric encryption,简称SSE)[20]以及保序加密(order preserving encryption,简称OPE)[21]等.同时,也有研究工作考虑到了与本文相似的具有多数据拥有方的数据共享场景,并提出了基于保序加密的解决框架[22].然而,这些工作都只是针对简单的关键词搜索问题,而排序学习问题与之相比则复杂得多.目前,有少数研究工作考虑到了排序学习中的隐私保护,但往往局限于特定的排序学习算法,如基于树集成模型的算法[23].不同于以往的基于隐私保护的信息检索相关工作,本文所提的联邦排序学习考虑了在联合学习过程中同时保护各个联邦参与方的隐私.由于排序对象与查询语句的隐私同样都属于隐私保护范畴,因此本文期望实现联邦中任意两两参与方的对称隐私要求,这是以往工作所不曾涉及的.同时,简单地套用加密算法来实现任意两方的对称隐私,也将在计算与通信效率上变得不可行.

1.2 联邦学习

联邦学习(federated learning,简称FL)最早由谷歌提出[24],它致力于实现多方在数据隐私保护前提下共同完成机器学习任务.个人数据隐私是当今互联网最值得关注的问题之一,随着欧盟“通用数据保护条例(general data protection regulation,简称GDPR)”的颁布,大型互联网公司无法再自由地收集用户数据用于机器学习.因此,谷歌于2016 年提出了针对安卓手机用户的联邦学习方法,它可在保证用户数据不出本地设备的前提下训练一个联合模型[24].文献[4]对谷歌的联邦学习概念进行了扩展,给出了更加通用的定义,并针对数据的不同切分方法,把联邦学习分为横向联邦学习、纵向联邦学习与联邦迁移学习.无论在哪种场景中,都具有几大共同的挑战.首先是数据隐私保护方法的设计,现有的大部分工作都基于多方安全计算(secure multi-party computation,简称SMC)的相关方法,设计基于同态加密、秘密共享等加密技术的联合机器学习算法[25],也有一部分工作基于随机扰动算法,如差分隐私(differential privacy,简称DP),设计基于噪声扰动的安全机器学习框架与算法[26−28].另一大挑战是传输成本问题,由于受到原始数据不能出本地的限制,需要在多方之间交互计算机器学习的中间参数,如梯度,该交互过程轮数较多,因此,如何节约传输成本以及减少交互轮数成为了关键.文献[29]对此提出了提高通信效率的优化方法.同时,如何有效地激励用户参与到联邦学习的过程中来,也是目前研究的重点之一.文献[30]提出了一种基于夏普利值的联邦学习多方贡献评估机制,可以高效地计算每个参与方对联合模型的贡献,以此公平地分配利益.除此之外,一些现有工作还研究了联邦学习的一些其他问题,如多任务学习问题[31]、数据非独立同分布问题[32]、模型可解释性问题[33]等.文献[34]总结了大量现有工作并给出了更加详细的联邦学习综述,根据其不同应用场景,将之分为面向企业数据孤岛(cross-silo)的联邦学习与面向终端设备数据孤岛(crossdevice)的联邦学习.在后者中,往往涉及成百上千甚至千万级别的用户,因此,如何缩减通信开销成了其面临的最大挑战.而前者,即本文对应的面向企业数据孤岛场景,涉及数据拥有方一般少于100,因此通信成本变得不那么重要.然而,由于每一方拥有的数据量一般要大于个人用户的数据,因此,如何缩减计算成本成为了更为重要的挑战.本文研究与现有面向企业数据孤岛联邦学习的不同之处在于考虑了一种以往工作不曾涉及的数据分割场景,即交叉分割,使得研究问题更具挑战性.值得一提的是,另一项最新工作[35]也考虑到了联邦排序学习,然而其与本文的本质区别在于:其场景为面向终端设备的联邦学习,数据也是普通的横向分割,这使得现有联邦学习方法能够很容易地适用于其问题.相比之下,本文侧重于企业搜索等面向企业数据孤岛的应用场景,问题也更加具有挑战性.

1.3 半监督排序学习

在排序学习中,获取足够且高质量的带标签数据需要花费大量人力成本.因此,半监督学习(semi-supervised learning,简称SSL)经常被用于只有部分数据带标签的排序学习中.文献[36]提出了一种归纳排序算法,其中,无标签的文档将根据与有标签文档的相似度而自动生成对应的标签.文献[37]则采用了一种转导推理方法,利用半监督学习来寻找更优的特征.文献[38]为直推式半监督学习引入了聚类的方法,降低了迭代中产生的噪声,提高了排序学习模型性能.事实上,如今处于研究前沿的几种半监督学习算法,如Temporal Ensembling[39],Mean Teacher[40]等都可以被简单地应用于排序学习上,因为排序学习也可以被看作是一般的分类问题.然而,在本文所涉及的联邦学习场景下,无标签的数据被分散存储在了各方,如何有效地在开销有限的前提下为之打上标签成为挑战.

1.4 Sketch数据结构

为了在保护隐私的同时提升计算效率,本文用到了Sketch 数据结构,它是一种用于近似推断大规模数据流上诸如元素出现频率等统计量的方法[41],其中比较常用的两种频率点估计方法分别为 Count Sketch[42]与Count-Min (CM)Sketch[43].除了大规模数据流的压缩以外,它在许多领域都有广泛的应用,例如大规模机器学习中的梯度压缩[44]与重要项查询[45]等.在某些场景下,它也可以与差分隐私(differential privacy,简称DP)相结合,同时兼顾数据隐私与计算开销[46,47].有文献证明:在特定假设条件下,Count Sketch 可以在不加入任何噪声的前提下直接满足差分隐私所需的条件[48],因此也被称为“免费的隐私(privacy for free)”.在本文中,我们将证明这种免费的隐私无法适用于我们的问题场景.因此,我们也将提出一种新的基于Sketch 的差分隐私定义.

2 问题描述

本节给出面向企业数据孤岛联邦场景下的排序学习问题的正式定义.

2.1 面向企业数据孤岛的联邦场景

设联邦F中有n个企业,F={P1,P2,…,Pn}.每个企业Pi持有排序对象(文档)数据集合和查询数据集合其中,文档和查询都可以看作是由全体单词集合Γ中的某些单词组成的多重集.全体数据可以表示为.每篇文档和每个查询之间存在一个相关度分数(即标签),表示为reli(d,q),其中,d∈Di,q∈Qi.由于每个企业只能够访问它自身所持有的文档数据和查询数据,所以它只能计算自己内部文档与查询的相关度.然而,它的查询可能也会和其他企业中的文档相关,或反之,其他企业中的查询和它的文档相关,但是这些相关度分数都因为数据不能相互访问而无法直接计算.

与其他机器学习问题类似,开展排序学习训练任务需要构造训练数据集(X,y),其中,X表示从文档数据D和查询数据Q中提取的特征,标签y则是相关性分数.我们假设特征提取函数Φ:D×Q→Rm是已知的.该函数依据某篇文档和某个查询,生成交叉特征,如词频(term frequency,简称TF)、BM25[49]和LMIR[50]等.

在没有联邦学习的情况下,第i个企业依据自身所持有的数据Di和Qi构造训练数据集(Xi,yi),作为待训练排序模型Mi(θ,x)的输入.训练过程为标准的经验风险最小化问题,即.其中,L是损失函数.在面向企业数据孤岛的联邦场景中,每个企业还可以和其他企业开展合作,来生成更多的训练数据.如前所述,这些训练数据没有标签,在这种情况下,各企业需要联合训练一个全局模型.

为了简化各企业之间的协作场景,假设训练过程中存在一个中心服务器,以协调各方信息交互.同时假设中心服务器和各个企业都是诚实但好奇的(honest-but-curious),即半诚实的(semi-honest).它们会遵守协议的要求,但是也会根据收到的数据推断敏感信息.面向企业数据孤岛联邦学习的目标是:在保护各企业数据隐私的情况下,训练一个有效的全局模型.

2.2 联邦场景下的排序学习问题

基于第2.1 节所述的通用联邦场景,排序学习的联邦场景问题定义如定义1.

定义1(联邦场景下的排序学习问题).给定有n个企业的联邦和一个特征提取函数Φ,联邦场景下的排序学习旨在让各企业协同训练一个全局的排序模型M.其中,每个企业Pi拥有一个同其他企业合作产生的无标签数据集和自身持有的带标签数据集(Xi,yi),训练过程需要满足以下条件.

• 共享性:对任意的两个企业Pi,Pj(i≠j)、任意查询q∈Qi和任意文档d∈Dj,存在一个,满足

• 隐私性:在训练过程中,任意两个企业之间、企业和中心服务器之间的信息交互造成数据Di和Qi的隐私泄漏需要可控;

• 有效性:协同训练的模型M要有比各企业独立训练的模型Mi有更好的性能.

上面的3 个条件对于一般的面向企业数据孤岛的联邦学习场景同样适用,但是本问题由于数据的分割造成了交叉特征生成难度大、标签丢失等诸多新挑战,克服这些挑战所需的技术将在下面两节介绍.

3 隐私保护的交叉特征生成

本节介绍基于Sketch 的企业间隐私保护的交叉特征生成解决方案(如图2 所示).该方法旨在保持共享性和隐私性的条件下,解决联邦排序学习中的企业间交叉特征生成问题.

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

3.1 交叉特征介绍

为简化说明,我们使用以下两个交叉特征实例展示基于 Sketch 的交叉特征生成解决方案:词频(term frequency,简称TF)和逆文本频率(inverse document frequency,简称IDF).在面向企业数据孤岛的联邦场景下,两个特征定义分别如定义2、定义3 所示.

定义2(跨企业数据孤岛词频).假设Pi,Pj∈F,d∈Dj,q∈Qi,t1,t2,…,tM是查询q中的M个单词.tk在文档d中的的跨企业数据孤岛词频,其中,TC表示出现的次数,ld是文档的长度.假设文档长度不属于隐私信息可以直接传输,那么计算跨企业数据孤岛词频就等价于计算跨企业数据孤岛的单词出现次数.

定义3(跨企业数据孤岛逆文本频率).单词tk的跨企业数据孤岛逆文本频率为

其中,I是指示器函数,输入条件为真时值为1,否则为0.因为需要聚合各企业的词频,跨企业数据孤岛逆文本频率和传统计算方法略有不同,将在下文着重说明.

3.2 跨企业数据孤岛词频生成

本部分的目标是:在保护双方(提供文档的一方和提供查询的一方)数据隐私的情况下,计算跨企业数据孤岛词频.在这样一个多方场景下,任意两方需要相互多次查询对方的文档.传统的基于加密的方法在效率和灵活性上都很不足,因此,我们设计了基于Sketch 的解决方案.该数据结构有如下优势:首先,它在构造后可重用,即有新企业加入不会导致其他已加入企业产生额外开销;其次,它响应查询速度很快,是常数时间复杂度;最后,由于使用了哈希函数,该数据结构很自然地隐藏了部分文本信息,在此基础上进行基于差分隐私的改进(详见第3.2.2节),可以实现更强的隐私保护.

首先给出Sketch 数据结构和差分隐私的相关定义(分别为定义4、定义5).

定义4(Sketch).对于一篇文档d,为其构造SketchS=(Enc,fS),其中:Enc是一个编码函数,使得Cd=Enc(d)是d的一个编码数据概要;而fS是一个计数查询函数,满足fS(dt)是单词t的计数查询结果.

以经典的Count Sketch 为例(也可使用Count-Min Sketch).Count sketch 的编码过程需要两个哈希函数集合H={h1,h2,…,hz}和G={g1,g2,…,gz},它们是从hi:Γ→[1,w](w<<|Γ|)和gi:Γ→{−1,+1}中随机成对抽取形成的.每个单词t的编码方式为

在把文档d编码后,将得到一个z行w列的表Cd(⋅,⋅).单词t的计数查询方式为

因为Sketch 上的查询过程需要多个哈希函数,我们可以通过直接混淆这些哈希函数来实现查询方的隐私保护.而为了定量描述文档一方的隐私保护程度,需要定义计数查询的ε-差分隐私(ε-differential privacy,简称ε-DP).因为依赖于Sketch,ε-DP 的定义和常规定义略有不同.

定义5(计数查询的ε-差分隐私).一个随机算法A满足ε-DP,如果对任意相邻文档d和d′(只相差一个单词)、任意单词t的计数查询fS和所有A的可能输出结果o,有:

如果计数查询的结果满足ε-DP,那么文档方的隐私信息就无法推断.

接下来介绍跨企业数据孤岛词频特征生成方案的技术细节.假设第i个企业Pi有单词t,它希望找到该单词在另一方Pj的文档d的词频.

(1)构造Sketch

首先,企业Pj构造文档d的Sketch.构造Sketch 是在各方开展通讯之前就完成的.各方使用相同的哈希函数构造 Sketch,所以在不同的企业数据中都可以查询.哈希函数可以通过企业间加密传输的方式(如 Diffie-Hellman 密钥交换协议)来生成索引,从而避免服务器推断哈希函数的有关信息.按照前述公式(2)可实现Sketch构造,其中,单词来自词汇表|Γ|,构造后将得到一个z行w列的表格.文档d有ld个单词,如果哈希过程时间复杂度为O(1),则需要花费O(zld)的时间来构造Sketch.每个文档的Sketch 都由各方在本地保存,只能由查询找到某个项的频率,构造过程如图3 所示.

Fig.3 Construction of the Sketch from a document图3 一篇文档的Sketch 构造过程

(2)带混淆哈希

完成Sketch 的构造后,为得到单词出现次数,Pi需要使用z个H中的哈希函数将查询中的单词t进行哈希.由于隐私保护的要求,不能直接在Sketch 上进行查询,而是随机从H中挑选z1个哈希函数对单词t进行哈希.对其他的z−z1个哈希函数,他们的输入是随机从|Γ|中选取的,使得这些单词经过哈希后和t经过哈希的结果产生碰撞,从而实现混淆.经过了这样的哈希过程和混淆过程后,Pi将得到一个长度为z的向量,其中有z1个位置的哈希函数索引是由Pi所私有的,即:

其中,PKi是Pi的私有哈希函数索引(1 到z随机排列后前z1个值的集合),cd(t,t′)是单词t和t′发生碰撞的哈希函数个数.Bt′包含不属于PKi的z1−b个整数,且每个Bt′彼此不重叠.因为单词t和t′有b个哈希结果相同,我们也能找到z1个哈希函数结果和t′一致.因此,任意其他的参与方无法通过暴力枚举z1个哈希值区分原始的单词t和用于混淆的单词t′.然而,我们也有,所以如果b太大,就很难找到用来混淆的单词t′.因此,存在一个隐私保护程度和数据精度的权衡.我们设置一个较小的z1和b来实现相同的隐私保护程度,同时保持查询结果的可信度.哈希处理后,Pi将把混淆的哈希向量发送给服务器,由服务器把该向量发送给Pj做进一步查询处理.

(3)查询结果扰动

本步骤中,Pj将收到服务器发来的z维向量,然后使用在Count Sketch 上进行查询,得到1≤a≤z.把查询的结果直接发布将产生隐私泄露风险,因为恶意的攻击者可能会查询一些敏感单词来推断其他参与方的文档词频分布.因此,我们设计了一个ε-DP 机制来扰动查询的结果,以保护文档隐私.我们的扰动机制采用拉普拉斯机制,扰动方式如下:

相关过程如图4 所示.算法1 和算法2 分别描述了查询方和文档拥有者的操作过程.

Fig.4 Thecount query of term from the Sketch图4 单词的词频查询过程

算法1.跨企业数据孤岛词频计算:查询方.

Input:待查询单词t,哈希函数H;

Output:估计的单词频率ft.

1:Q←空向量

2:PK←随机生成的哈希函数编号

3:for 1≤a≤zdo

4:依据公式(4)生成哈希值

5:添加到Q结尾

6:把Q 发送给服务器

7:从服务器收到查询结果

8:去掉混淆项

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

10:returnft

算法2.跨企业数据孤岛词频计算:文档持有方.

Input:文档d,单词的哈希值Q,哈希函数H;

Output:无.

1:按照公式(2)构造C

2:从服务器接收向量Q

3:FQ←空向量

4:采样N

5:for 1≤a≤zdo

6:注入噪声

7:追加到FQ

8:把FQ发送给服务器

9:return None

3.3 跨企业数据孤岛逆文本频率生成

上文阐述了面向企业数据孤岛联邦场景下的词频特征生成过程,对于逆文本频率,过程将略有不同.跨企业数据孤岛逆文本频率的定义如第3.1 节公式(1)所示.公式中分子部分表示企业所拥有的文档总数,这并非隐私信息可以直接公开.计算的主要挑战来自对分母部分的计算.一个朴素的解决方案是,在每篇文档上执行跨企业数据孤岛词频特征生成.然而,这样的解决方法十分低效,仅针对一个单词就需要进行次查询.造成这种低效的主要原因是:逆文本频率的计算需要语料库的全局信息,而不仅仅是单一的文档信息.为了提高效率,我们设计了一种新的方法如下.

首先,从Pj的所有个文档中生成一个新的文档.它的单词是所有在Dj中出现过的单词,而单词出现次数为所有出现过该单词的文档数量.为这个新文档构造一个Sketch,这样,查询中的每个单词在此Sketch 上查询的结果就是包含该单词的文档数量.后续步骤和跨企业数据孤岛词频生成相同,即:使用混淆单词隐藏查询的真实单词,为查询结果添加拉普拉斯噪声满足差分隐私.最终的时间复杂度可以被削减为O(n).

事实上,我们还可以进一步削减查询的时间.可以考虑通过安全聚合的方法把各方新文档的Sketch 聚合为一个,存储在服务器上.这样,未来的查找可以在O(1)时间内完成.

3.4 其他跨企业数据孤岛特征

上文我们主要介绍了词频和逆文本频率的跨企业数据孤岛隐私保护交叉特征生成方案,该方法可以很容易拓展到其他排序学习所使用的统计特征中.举例来说,几乎所有LETOR 4.0[51]所使用的特征(网页链接数等文档重要度特征除外)都可以通过这两个基本操作来生成.例如,依据前面所介绍的跨企业数据孤岛词频和逆文本频率,可以定义跨企业数据孤岛BM25[49]特征:

其中,avdl是文档的平均长度,l是查询的长度,k1是超参数.不难发现:如果词频和逆文本频率是事先算好的,那么BM25 可以在O(l)的时间内计算出来.

同理可以定义LMIR[50]的诸多特征:

其中,λ和μ是超参数,p(t|Di)是单词在文档中的词频.

最后,对每个企业可以生成一个新的数据集X′.该数据包含了自身查询语句和其他企业的文档产生的交叉特征,满足了共享性.

3.5 隐私保护与精度损失的理论分析

本部分分析我们的跨企业数据孤岛隐私保护交叉特征生成方案的隐私保护情况和精度损失情况.

3.5.1 隐私保护上界

差分隐私是联邦学习场景中定量衡量隐私保护程度的事实标准.从定义5 可以看出,其核心思想是用概率之比衡量不可区分性.下面我们将证明我们的方法满足ε-差分隐私.

定理1.对任意计数查询,公式(5)的扰动方法满足ε-差分隐私.

证明:设文档d′的长度为ld′=ld+1.文档d和d′是相邻的文档,即前ld个单词相同,而d′比d多一个单词t′.由每对哈希函数彼此独立,可得:

对任意一个确定的企业i,我们分析相邻文档d和d′中单词经过扰动后的不可区分程度.具体来说,分为两文档单词不同的情况(t≠t′)和单词相同的情况(t=t′).

对∀t≠t′的情况,可得:

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

从上面的证明过程可以看出:虽然我们的方法中带混淆哈希和拉普拉斯噪声都提供了单词的不可区分性,但是拉普拉斯噪声的方差直接反比于隐私预算ε,仅拉普拉斯噪声提供的不可区分性就足以提供满足ε-差分隐私的保护了.为了进一步充分利用带混淆哈希所产生的不可区分性,可以适当降低拉普拉斯噪声的注入量.

推论1.若注入的拉普拉斯噪声,其中,,则公式(5)的扰动方法依然满足ε-差分隐私.

证明:根据定理1 的证明,我们有:

3.5.2 精度损失上界

Count Sketch 的频率估计是一个无偏估计,其方差为,其中,.为了进一步降低精度的损失,可以考虑利用数据的偏度实现对方差的进一步控制.文档中,单词的频率通常满足齐夫定律,按照文献[52],F2可以进行如下放大:

定理2.对于一个单词t,如果z1被设定为的,那么至少有1−δ的概率,可以保证词频估计有如下上界:

证明:依据公式(6),我们有:

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

按照齐夫定律关于词频分布规律的假设,不论如何选取哈希函数,总有7/8 的概率,使得的最频繁项和给定的单词k在任意给定行都不会发生碰撞.因此,

证明:首先证明任意两个单词t1和t2以及任意的a∈PK,Ca(t1)和Ca(t2)是独立的.这是因为我们有:

4 半监督协同排序学习

本节介绍半监督协同排序学习方法,来克服标签缺失的挑战.在一个企业所持有的数据之内,可以很容易地评估查询和文档生成的交叉特征样本的相关性,形成带标签的样本数据.但是跨企业数据孤岛所生成的交叉特征却无法直接评估相关性,因此不存在标签.现有的半监督学习方法并不能直接应用到本问题中,主要有两个原因:一是带标签和不带标签的数据都是分属各方的,如图5 所示;二是半监督学习过程也需要考虑原始数据的隐私.为了解决上述问题,我们首先提出一个简单的半监督学习基准算法,然后再设计一个协同学习的方法.

Fig.5 Framework of semi-supervised collaborative learning图5 半监督协同训练框架

4.1 基准算法:本地训练

每个企业拥有自身的带标签数据(Xi,yi)和无标签数据X′,它可以在本地利用这些数据以半监督训练的方式得到一个模型.本地训练可以自然符合数据不离开本地的特点,所以简单地满足了隐私限制.本地训练中,可以使用一个通用的伪标签生成器来实现半监督学习.学习过程就是求解如下最优化问题:

其中,y′是x′由伪标签生成器生成的的伪标签,β是无标签数据的权重.伪标签生成器的设计有多种方法,我们简单地直接使用上一轮的模型给无数据打标签.最后,各方都会持有一个由自己训练的私有模型Mi作为最终结果.在这种方案中,生成的无标签数据并没有被充分使用,所以我们提出了一个改进的协同训练方案.

4.2 无标签数据的协同训练

一个直接的协同训练方法是:只使用各方的带标签数据,问题就被规约为标准的横向联邦学习.但是在这种情况下,针对查询的数据依然十分短缺,即每条查询所对应的特征空间不够大.此外,隐私保护也不应被忽视,因为梯度可能泄漏敏感信息.

为了能更好地使用这些丰富但无标签的、同时不包含Pi隐私信息的数据,我们设计了如下方法:首先,在协同训练之前,各方先在本地使用自身带标签数据训练一个分类模型Mi;之后,各方把这个本地模型发送给服务器,服务器聚合这些模型作为一个标签生成器,即;Agg(⋅)对各个模型的参数求平均,得到全局模型.由各方共享,且它也是标签生成器和排序模型的初始值.

可以以串行或并行的方式运行梯度下降算法.在每一轮迭代中,各方在本地使用一批带标签和无标签数据运行梯度下降算法,并提交梯度变化Δθ给服务器.协同训练过程中使用的训练数据就是前文介绍的给类交叉特征.交叉特征的生成过程需要使用企业的原始文本数据,所以我们设计了带混淆哈希、拉普拉斯噪声注入等方法保护隐私.而协同训练的过程只是在使用这些特征,并不涉及企业原始数据,并且无标签数据的来源只有提交查询的Pi知道,即使攻击者有能力依据梯度更新反推出用于训练的交叉特征,仍然不会泄漏企业的原始文本数据,所以我们不再对Δθ使用额外的隐私保护手段.最后,随着θ的收敛,各方将获得一个全局模型M.其他细节详见算法3.

算法3.半监督协同训练算法

Input:带标签和无标签数据,其他参数;

Output:全局模型.

1:for 企业Pido

2:Pi训练一个本地模型Mi

5:使用M给无标签数据打标签

6:fort=1,2,… do

7:for 企业Pido

8: 收集带标签和无标签数据批数据

9: 根据公式(9)更新权重θ

10:returnM

5 实验评估

本节介绍实验结果来证明所提方法的有效性.

5.1 数据集和实验设置

以LETOR4.0[51]为代表的大部分标准数据集都只包含了已经提取好的特征,而没有原始的文档和查询数据,因此无法应用在我们的实验中.本文中,我们选择MS MARCO 排序数据集(http://www.msmarco.org/dataset.aspx),从中采样部分数据用于实验.假设企业的数量为4,每一方只有有限的带标签的查询结果.从MS MARCO中采样4 个子集,每个包含约200 条查询和40 000 篇文档,每篇文档有大约1 000 个单词.我们所提出的技术是为数据规模较小的企业提供帮助,因此设置单个企业数据孤岛的数据规模控制在104数量级.使用每条查询最相关的100 篇文档的相关度分数作为标签.最相关的10 篇文档被标记为非常相关(相关性分数为2),排在11 名～100 名的文档是相关(相关性分数为1),100 名以外是不相关(相关性分数为0).对每一方,生成约2.4 万条带标签数据,并取其中7 000 条样本数据构造全局测试集(共2.8 万条).

在半监督学习模型的设置方面,我们采用点排序模型.模型结构为线性分类模型.损失函数设置为交叉熵,并且引入了L2 正则项.本地训练和全局训练因为数据规模不同,分别设置迭代1 000,2 000 轮次.更新过程采用批处理随机梯度下降,全局模型的更新在每一批数据处理完成后进行.而所提算法则取本地模型平均用来打标签,以开展线性回归训练.

交叉特征选取的主要依据是LETOR4.0 所使用的公认排序学习特征.查询分别和文档的标题与正文交叉计算词频、逆文本频率、TF-IDF、BM25、LMIR.ABS、LMIR.DIR、LMIR.JM 属性,结合文档标题长度与正文长度,形成一条拥有16 个特征的样本数据.与LETOR4.0 相比,我们的排序对象是纯文本文档,不包含链接数量、网址深度等网页文档的特有特征.此外,除了我们所采用的查询语句和正文与标题分别计算的交叉特征外,LETOR4.0 还进一步把正文与标题看作整体,再与查询语句进行交叉特征计算.但是我们的排序对象正文长度大,把标题和正文结合和仅考虑正文相比差异不大,加之过多特征还会显著拖慢训练速度,所以我们并未引入这些特征.我们为每一方生成了5.97 万条跨企业数据孤岛数据,用于半监督协同学习.可以看到:同单个企业数据孤岛所能产生的2.4 万条数据相比,交叉特征生成的过程显著增加了训练样本数量.增加的数据对于模型训练的帮助将在后面的实验中具体说明.文档的预测顺序将按照模型给出的预测分数从高到低排序.评估排序好坏的指标有:

• 期望倒数排名(expected reciprocal rank,简称ERR).评估相关度高的文档其排序位置是否靠前,计算方式为

其中,reli表示排序在第i个位置文档的相关性分数(即0,1,2),relmax为最大的相关性分数(即为2);

• 平均准确率(mean average precision,简称MAP).评估排序学习模型给出的顺序与按照实际相关度排序的差别,计算方式为

其中,rank(d)表示文档d按照相关度分数排序时的位置,position(d)为排序学习模型给出的位置;

• 归一化折损累计增益(normalized discounted cumulative gain,简称nDCG).综合考虑相关性和排序位置的评估指标,计算方式为

其中,IDCG 为归一化系数,其值为文档按照相关度分数降序排列时得到的

• 前10 名归一化折损累计增益(normalized discounted cumulative gain at 10,简称nDCG@10).即排在前10 文档的nDCG.计算方式为

我们的方法是为全新的交叉分割联邦学习场景设计的,目前尚未有其他方法能够适用于这样的场景.这让我们很难找到其他的横向对比方法.因此,我们实验的重点在于检验使用交叉特征生成进行增广的数据集是否有助于排序模型的性能提升,于是选取以下3 种方法同所提算法CS-F-LTR 进行比较.

• Local:各方仅使用自己的带标签数据训练一个模型;

• Local+:各方使用自己的带标签和无标签数据训练一个半监督模型;

• Global:各方使用带标签数据协同训练一个模型,和横向联邦学习场景类似.

5.2 实验结果

5.2.1 主要结果

在表4 中,我们记录了Local,Local+,Global 和CS-F-LTR 的4 项评估指标.

Table 4 Comparison results表4 比较结果

可以发现:各方的nDCG@10 指标在Local 方法下结果为0.7 左右,该方法只采用了本地数据来训练.而Local+的方法使用了无标签数据,因此在一定程度上可以提高本地模型的表现.企业B,C的nDCG@10 分别增长了5.8%,3.1%,企业D略微变好,企业A略微更差.这是因为各方的数据并不一定是独立同分布的.所以各方依据自身数据所训练的伪标签生成器在给交叉产生的互特征生成标签时,如果双方数据分布差异过大,打标签就可能出错.在CS-F-LTR 中,通过模型平均和使用无标签数据,nDCG@10 有一个明显的提高,从0.65～0.75 的范围升高到0.83.同时,把CS-F-LTR 和Global 所训练的模型比较,后者虽然也聚合了数据但是没有使用半监督学习的方法,通过比较发现,nDCG@10 分数提高了.而对于其他的评价指标,分数也有一定的提高.

各企业在使用不同方法训练过程中,nDCG@10 指标随迭代过程变化如图6 所示.可以看出:本地训练的两个方法(Local 和Local+)因为使用的数据有限,性能显著低于全局方法训练的模型;而在两个全局方法(CS-FLTR 和Global)中,我们所提出的CS-F-LTR 方法因为能够进一步使用无标签数据采用半监督学习的策略,因此性能更胜一筹.此外,对任一企业,采用全局方法进行训练得到的模型和仅在本地开展训练得到模型相比,在性能上有显著提升,这也从客观上推动了各企业破除“数据孤岛”开展合作.

Fig.6 Comparison among different solutions on each data silo图6 各企业数据孤岛中不同方法的性能比较

5.2.2 Sketch 的影响

我们评估了不同的Sketch 策略:使用CountSketch(CS)和Count-MinSketch(CMS)两种Sketch 类型,使用不同的哈希空间w和使用不同数量的哈希函数z1,实验结果如图7 所示.

Fig.7 Evaluation of different sketch strategies图7 不同Sketch 构造策略评估

从全局随机抽取400 个正负样本(相关度分数大于0 为正样本,否则为负样本),构造不同的Sketch 来评估影响.为了能更清楚地展示实验结果,通过TSNE 把样本点嵌入到二维平面中.图7(a)展现了没有Sketch 的情况,图7(b)对应CS-F-LTR 中的Sketch 构造方法.可以看到:在使用Sketch 以后,不同类别之间的分界线依然是可以辨认的.我们也尝试使用相同的参数构造了CM Sketch,结果如图7(e).随着哈希空间w的减小,噪声在增加(图7(c)和图7(d)),这说明准确度关于哈希空间w十分敏感.哈希空间越小,越多的单词会彼此碰撞,词频和其他特征的计算结果就会越不准确.然而,当哈希函数的数量z1减少时,结果会更加鲁棒.即使当z1为5(如图7(f)所示)或者3(如图7(g)所示)时,依然有一个明显的分界.当z减小到1 时,分界才开始模糊(如图7(h)所示).这说明:当z确定时,一个较小的z1依然可以保证较为准确的特征,同时保持较好的隐私保护.

5.2.3 隐私预算的影响

隐私预算的影响如图8(a)所示,我们惊讶地发现:将少量噪声(ε为0.5)注入到样本数据中,会带来更好的效果.可能的原因是噪声值增加到了无标签数据上,并且他们的伪标签可能不正确,这种情况下,增加噪声可以避免模型过拟合,从而提高泛化性能.随着噪声进一步增加,模型表现开始变差,但依然是可控的.半监督训练过程就像是一个微调过程,而带标签数据则为微调方向提供了一个很好的指引.

Fig.8 Impact of privacy budgetand number of datasiloson CS-F-LTR图8 隐私预算和企业数据孤岛数量对CS-F-LTR 算法的影响

5.2.4 企业数据孤岛数量的影响

企业数据孤岛数量的影响如图8(b)所示.可以看到:几乎所有的指标都在随着企业数量的增加而增长.nDCG@10 和MAP 随着企业数量从1 增长到5 有着8%的增长,这说明了CS-F-LTR 的有效性.而nDCG 的增长并不显著,这是因为每一条查询在测试集中有太多不相关的文档.ERR的数值先降低后增加,最终增加了5%.可能的原因是:当企业数量小的时候,各企业中数据分布差异大,非独立同分布特点明显,从而影响了某些指标.

5.2.5 实验总结

从以上结果可以看出,CS-F-LTR 方法和本地训练相比是更加有效的.更多的参与方可以提高模型的性能.同时,该方法关于隐私相关的参数也是鲁棒的,这说明它能够更好地平衡隐私保护的程度和模型的性能.然而,CS-F-LTR 的有效性也取决于各企业的数据分布情况.如果数据分布差异过大,增加更多的企业可能并不总是对提高性能有效,这也是符合常理的.

6 总结与展望

本文研究了在面向企业数据孤岛联邦场景下的排序学习问题.首先.针对这一特定问题,总结出了一种不同于现有横向或纵向联邦场景的新型面向企业数据孤岛的联邦场景——交叉分割联邦场景,并提出了联邦框架CS-F-LTR,该框架可以帮助那些本地数据不足的企业间合作构建专有的文档检索系统.我们主要解决了该问题中的两大挑战:一是跨企业数据孤岛的交叉特征生成问题,即隐私保护限制造成了大量交叉特征数据无法被生成和利用.为此,我们提出了基于Sketch 与差分隐私的解决方法.可以在实现隐私保护满足差分隐私要求的前提下,实现误差可控的词频、逆文档频率等交叉特征的计算.二是生成数据标签缺失的问题,即用于交叉特征生成的查询和文档因分属不同企业无法直接评估相关性.我们使用半监督协同学习的方法解决了该问题.最终,在公开数据集上的实验结果验证了我们提出方法的有效性.

与此同时,联邦排序学习的未来研究仍存在诸多挑战.首先是数据非独立同分布的问题.各企业数据分布可能存在不均衡性,对模型性能会产生影响.不同企业所持有的数据不一定满足独立同分布的假设,这可能导致不同企业本地所训练的模型泛化性能降低,从而影响全局模型性能.其次是排序模型的拓展性问题.本文中,排序模型使用了经典的点排序模型;而对于基于文档对和文档列表的排序方法,因其标签和特征更加复杂,该框架中的特征生成和半监督学习方法需要进一步设计.最后是传输可靠性问题.虽然本文所提框架主要是针对企业间的联邦场景,但依然可能存在网络时延、掉线等因素破坏模型的训练进程,提高鲁棒性也是值得研究的问题.

目前,数据非独立同分布问题和传输可靠性问题是联邦学习领域的热点问题,已经有诸多研究可以参考.而针对排序模型的拓展性问题,则应该结合训练所需的样本结构设计新的协作方式和传输规划.未来,克服上述挑战将有助于彻底打通企业数据孤岛,并促成联邦排序学习的真实应用落地.