这是今年刚在WSDM上发表的一篇文章,在联邦学习的框架下考虑了实时排序算法的实现,作者将这个框架称为Federated Online Learning to Rank (FOLtR)。
简单摘要:
问题:我们有一个排序模型, ,和客户的交互数据a,如何在保证隐私的同时提高模型的评分
方法:ES策略,即每个客户探索一个新策略 ,根据交互数据得到一个平均的分数 ,central sever根据所有用户的 和 计算目标函数的梯度,用梯度下降法更新参数
用户数据隐私性:传输种子s和评分f,s可以认为是一个N(0, )的随机数,所以已经是安全的,无法从这个倒推参数。对f加入随机噪声,保证了用户数据的差分隐私
解决什么问题?
如何在数据保存在本地的情况下,利用客户的交互数据实时优化手机上的排序模型。
本质是一个优化问题,用Evolution Strategy(ES)策略优化,用Federated Learning(FL)保护隐私
相比之前的工作创新之处?
1)之前算法都是centralized setting,这个框架下sever不知道用户的数据,保护了用户的隐私性(差分隐私)。
2)相比google的横向联邦学习框架以及后续的一些安全研究,他们多是假设攻击central sever的聚合模型获得隐私数据,作者考虑了传输信息的安全,并简单计算了他们模型的隐私保证(privacy guarantee)。
个人感觉第二点有些牵强,用DP,HE或者secured sharing的工作已经有很多了,都是对传输信息进行加密。创新的地方一是使用了FL框架,二是将ES算法嵌入这个框架内。我记得之前好像看过和这篇一样的ES推导,不过再找就找不到了,姑且认为是对opanAI那篇算法的简化吧。
框架如何实现?
客户先下载当前最新的推荐模型,经过一段时候后,对这段时间内客户的交互数据做一个平均,返回推荐模型的评分f和模型种子s给sever,sever用所有客户数据更新模型,客户再下载这个更新的模型。
计算传输的梯度值:(核心的优化问题)
这里的推导和ES算法基本是一样的。
目的是选择一个权重向量使所有客户的排序质量矩阵的平均值最大。即
u代表客户,a代表客户的交互数据,f代表ranking quality
ES策略:
通过扰动模型内部参数, 获得多个候选模型, 最后根据回报值更新得到更好的内部参数
ES策略不只是取一个固定的
值,
由一个分布
生成,比如说高斯分布
。那么现在问题转化为寻求一个扰动参数
使得排序质量矩阵的平均值最大。
然后直接求导:
通常分布取为高斯分布,得到上面最后一步。
ES策略实现
本质就是一个梯度下降算法,计算出梯度g来更新参数
作者这里是用本地生成一个伪随机高斯函数种子s,随机出一个模型 ,这样使得所有用户的模型都会有一些不同,即扰动模型。得到这个模型在一段时间内交互数据的评分f,返回种子s和评分f。central sever拿到s后可以还原出模型,然后用所有用户评分做一个平均,计算出梯度g的估计值。
保证隐私性:
考虑一个简单的情况,排序质量矩阵f的取值是离散的,e.g. 可取值为
, …,
。假设要传输
,以概率p传输真实值,否则从其它n-1个值中随机选取一个值。可以计算传输f的期望值为
可以看到期望值与
是成正比的,而我们的目标是最大化n个客户
的平均值,最大化这个期望值也是一样的。
计算模型的隐私保证
根据DP的定义,
当
越小时,私密性越高。
直观的理解是当 的查询结果与 的查询结果相等的可能性越大时,攻击者更难区分出某个客户的数据是否存在于数据集中,或者说相等可能性越大,随机性越高。但随机性太高会使得数据很难使用。
作者假设攻击者尝试从
和
中恢复排序质量矩阵,我们关心在一个配置下
的最大值是多少:
就是 某一个取值的传输概率,以 为例,假定分布产生 的概率为 ,那么其被传输的概率为
取值范围为
可以得到一个
的理论上界
实验
数据集是MQ2007 and MQ2008,评价标准是Mean reciprocal rank,模型分为三种,Perfect, Navigational, and Informational,具体描述见下图。
baseline模型是MSE和SVMRank,都是在离线下训练的,并且给了query和document的相关性标签。从实验结果来看FOLtR-ES和baseline的两个模型结果基本差不多。