联邦学习论文阅读 Federated Online Learning to Rank with Evolution Strategies
这是今年刚在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的两个模型结果基本差不多。