An Efficient Approach for Cross-Silo Federated Learning to Rank文章翻译

An Efficient Approach for Cross-Silo Federated Learning to Rank

一种有效的cross-silo(跨孤岛)联邦排名学习方法

摘要

传统的排名学习（LTR）模型通常采用基于大量数据的集中式方法进行训练。然而，随着人们数据隐私意识的提高，像以前一样从多个所有者收集数据变得更加困难，由此产生的数据隔离问题使得学习到的 LTR 模型的性能严重受损。受联邦学习最新进展的启发，我们提出了一个名为 cross-silo 联邦排名学习（CS-F-LTR）的新框架，其中效率问题成为主要瓶颈。为了应对这一挑战，我们首先设计了一种基于草图算法和差分隐私的 cross-party词频查询方案。为了进一步提高整体效率，我们提出了一种新的结构–反向top-K 草图（RTK-sketch）的新结构，该结构在保证精度损失的同时，显著加快了特征生成过程。在公共数据集上进行的大量实验验证了该方法的有效性和效率。

1 介绍

在过去的十年里，学习排名(LTR)技术在信息检索(IR)系统[1]-[3]上取得了巨大的成功，尤其是商业搜索引擎 谷歌和 Bing。传统的 LTR 依赖于搜索引擎和数百万网络用户交互所积累的海量数据。然而，除了极少数的搜索引擎巨头之外，大多数公司都没有自己生成足够训练数据的特权。更糟糕的是，随着越来越多的数据法规和法律(比如GDPR)的生效，这些公司之间自由共享或交换数据将成为非法行为，从而导致众所周知的数据隔离(即数据碎片化)问题[4]。因此，如何打破数据孤井之间的障碍，为企业搜索训练有效的LTR模型仍然是一个有待解决的问题。

在本文中，我们提出了一个名为 Cross-Silo 联邦排名学习 (CS-F-LTR)的框架，它协调多个公司(例如，孤井或各方)来训练一个强大的LTR模型，而不需要在它们之间交换原始的训练数据。在 CS-F-LTR 中，训练模型所需的文档和查询都分布在不同的参与方之间。每一方都与其他方协作生成培训实例，而每一方的文档和查询仅在本地存储，以保护隐私。与一般的联邦学习设置中数据要么是水平分区，要么垂直分区[4]不同，在我们的设置中，训练数据是跨分区的(见图1)。由于LTR中的每个训练实例都与文档和查询同时相关，而文档和查询可能由不同的方拥有，因此特征生成可能需要在跨分区数据设置中的任何两方之间的协作。

图1:联邦LTR中跨分区数据的图示。跨分区与水平分区和垂直分区的区别在于，训练数据中的每个实例都是通过链接两个组件、查询和文档生成的，这些组件、查询和文档也分区(孤井)分布。

这种独特的数据分区特征给联邦 LTR 带来了主要的瓶颈:效率问题。首先，基于加密的隐私保护方案在效率和灵活性方面可能非常低，因为数据的跨分区导致各方之间频繁的交互。对于LTR任务，需要为文档语料库构建大规模的安全索引，同时需要非常频繁地执行加密查询，这可能会花费极高的空间和时间成本。为了提高效率，需要采取更实际的方法来降低数据的隐私性，同时也要控制隐私损失。另一方面，跨分区数据之间频繁的交互在 没有加密的情况下 仍然会带来较高的计算和通信成本，这也是通用联邦学习内在的瓶颈。没有特殊数据结构设计的Naive解决方案将在 联邦LTR 的特性生成中枚举单个方的单个查询的所有文档，这将带来不可接受的查询时间和通信开销，特别是在文档数量很大的情况下。因此，设计优化技术来提高联邦LTR中的整体效率是至关重要的。

在本文中，我们专注于解决上述的效率挑战，我们的主要贡献总结如下:
1）我们正式定义了具有唯一跨分区数据设置的联邦LTR问题。我们进一步确定其主要挑战是效率问题，并提出了一个名为CS-F-LTR的解决方案框架。
2）为了在 联邦LTR特征生成中 高效地实现对称隐私，我们提出了一种基于草图和差分隐私技术的通用词频查询方案，该方案在理论上保证了隐私性和准确性损失。
3）为了进一步优化算法的整体效率，我们提出了一种新的绘图结构——逆向top-K草图(reverse top-K sketch, RTK-sketch)，该结构既能减少查询时间，又能减少通信开销，同时又能保证算法的逼近性。
4）我们评估了我们的方法在公共数据集上的性能，大量的实验结果验证了我们的解决方案的有效性和效率。

本文的其余部分组织如下。我们回顾了第二节的相关工作，正式定义了第三节中的问题，并分别阐述了第四节和第五节中的词频查询方案和优化方法。实验结果在第六节给出，我们在第七节总结本文。

2 相关工作

我们的工作涉及以下几类研究。

Privacy-Aware隐私感知信息检索
信息检索系统通常涉及来自客户端和服务器端的大量数据，这些数据能够支持性能良好的LTR模型。客户端浏览器查询日志 包含用户的点击量，可以反映用户的日常上网行为。因此隐私问题经常发生，例如著名的美国在线数据[5]隐私泄露事件。现有的隐私感知LTR研究主要集中在 保护客户端的隐私 免受 恶意服务器 的攻击。

在[6]中可以找到一个早期的理想模型——私有信息检索(PIR)，该模型旨在 保护查询 的隐私，但它需要 复制数据库 ，因此在实际场景中不现实。
一些更实用的方法选择通过锻造查询[7]、生成覆盖查询[8]或在差异隐私[9]下注入噪声来混淆查询。

对称私有信息检索(symmetric -private information retrieval, SPIR)首先在[10]中定义，其中还考虑了 服务器端 数据隐私。最广泛认可的方法是 安全关键字搜索方案 ，如可搜索对称加密(SSE)[11]和保序加密(OPE)[12]。
在[13]中，作者还考虑了多个数据所有者的数据共享场景，并提出了基于OPE的解决方案。然而，这些方法只适用于简单的关键字搜索，而不是LTR，少数作品考虑隐私敏感的LTR，但仅限于特定的分类器(如树集合[14])。与之前的工作不同，在联合LTR中，我们考虑在协作学习过程中保护不同参与方之间的隐私。在查询隐私和文档隐私都很重要的情况下，任何两方都应该实现对称隐私。在这种情况下，目前流行的基于加密的方法的效率可能非常低。

联邦学习
联邦学习（Federated learning，FL）[15]，[16]最早由谷歌提出，用于android用户之间的隐私感知协作学习，其定义在[4]中进行了概括。它可以分为 cross-silo 和 cross-device 联邦学习[17]。cross-silo设置 适合 企业对企业（B2B）场景，其中每个 silo 可以是公司或组织，而跨设备设置 对应于 企业对客户（B2C）模式。在这两种情况下，隐私保护往往成为核心问题，基于加密的方法（如秘密共享[18]）和基于噪音的方法（如差异隐私[19]–[21]）已经得到应用。不同之处在于，跨设备FL通常涉及大量用户，因此通信成本可能是一个瓶颈，而cross-silo FL只有几个参与方（通常少于10个）。我们的论文基于cross-silo设置，因为我们假设每一方都是一家企业，希望为特定的专业网络搜索建立一个全球排名模型。在这种情况下，计算成本应该得到考虑，因为作为企业的每一方都拥有比个人设备多得多的数据，基于加密的解决方案可能非常耗时。我们问题的独特之处在于原始数据的交叉分割，这在FL中从未被研究过。最近一项在 在线LTR框架 中考虑FL的工作[22]也与我们的工作相关。但它考虑了跨设备的FL，并且数据是水平分区的，这使得现有的FL解决方案框架适用。

草图算法
为了提高效率和保护隐私，我们提出了一种基于草图[23]的大规模流数据近似统计估计方法。Count sketch[24]和Count-Min（CM）sketch[25]是两种常用的点查询草图，如数据流中单个项的频率估计。通过提出新的数据草图[26]–[28]，为优化效率和准确性已经做了许多努力。该结构还被应用于许多领域，如大规模机器学习中的梯度压缩[29]和重打击发现[30]。有时，它还可以与差异隐私（DP）[31]一起使用，其目的是通过向 聚合结果 中注入噪声来保护个人隐私。在[32]中，证明了在强假设下，无附加噪声的计数草图可以满足DP的概念。

在本文中，我们首先对传统的草图绘制算法进行改进，提出了一种新的DP概念，实现了联邦LTR中的隐私保护特征生成。然后，设计了一种新的草图，以优化计算和通信效率。

3 问题陈述

在本节中，我们正式定义了 cross-silo 联邦 LTR 的问题设置。然后我们将定义 反向 top-K 文档查询 ，这是解决问题的基础。

A. Cross-Silo Federated LTR Setting 跨孤岛联邦排名学习设置
我们首先简要解释了学习排名（LTR）背景下的 Cross-Silo设置。
假设包含 N 个参与方（企业）的联邦 F = P 1 , P 2 , … P N F ={P_1,P_2,…P_N} F=P1​,P2​,…PN​。每个参与者Pi持有一个文档集合 D i = d i , 1 , d i , 2 , … , d i , ∣ D i ∣ D_i = {d_{i,1}, d_{i,2} ,…, d_{i,|Di|}} Di​=di,1​,di,2​,…,di,∣Di∣​和一个查询集合 Q i = q i , 1 , q i , 2 , … , q i , ∣ D i ∣ Qi = {q_{i,1}, q_{i,2} ,…, q_{i,|Di|}} Qi=qi,1​,qi,2​,…,qi,∣Di∣​ 。因此， D = U i = 1 n D i D=U^n_{i=1}D_i D=Ui=1n​Di​和 Q = U i = 1 n Q i Q=U^n_{i=1}Q_i Q=Ui=1n​Qi​ 。对于一个文档 d 和查询 q ，可以计算一个相关的分数 R(d,q) ,来表明他们之间的相关性。请注意，各一方只能访问自己的文档和查询之间的相关性分数，尽管来自第三方 P i P_i