联邦学习论文阅读 Federated Online Learning to Rank with Evolution Strategies

这是今年刚在WSDM上发表的一篇文章，在联邦学习的框架下考虑了实时排序算法的实现，作者将这个框架称为Federated Online Learning to Rank (FOLtR)。

code开源地址

简单摘要：
问题：我们有一个排序模型，${\theta}$θ，和客户的交互数据a，如何在保证隐私的同时提高模型的评分${f(a; \theta)}$f(a;θ)
方法：ES策略，即每个客户探索一个新策略${\theta_i}$θi​，根据交互数据得到一个平均的分数${f_i}$fi​，central sever根据所有用户的${\theta_i}$θi​和${f_i}$fi​计算目标函数的梯度，用梯度下降法更新参数${\theta}$θ
用户数据隐私性：传输种子s和评分f，s可以认为是一个N(0,$\sigma$σ)的随机数，所以已经是安全的，无法从这个倒推参数。对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算法基本是一样的。
目的是选择一个权重向量使所有客户的排序质量矩阵的平均值最大。即
${\theta^* = argmax_\theta F(\theta) = E_u E_{a|u,\theta} f(a;\theta,u)}$θ∗=argmaxθ​F(θ)=Eu​Ea∣u,θ​f(a;θ,u)
u代表客户，a代表客户的交互数据，f代表ranking quality

ES策略：
通过扰动模型内部参数, 获得多个候选模型, 最后根据回报值更新得到更好的内部参数

ES策略不只是取一个固定的${\theta}$θ值，${\theta}$θ由一个分布${p_\phi (\theta)}$pϕ​(θ)生成，比如说高斯分布${p_\phi (\theta) \sim N(\phi,\sigma^2I)}$pϕ​(θ)∼N(ϕ,σ2I)。那么现在问题转化为寻求一个扰动参数${\phi}$ϕ使得排序质量矩阵的平均值最大。
${E_{\theta \sim p(\theta)} F(\theta)}$Eθ∼p(θ)​F(θ)

然后直接求导：
${g = \nabla_\phi E_\theta F(\theta) = E_\theta [F(\theta) \cdot \nabla_\phi logp_\phi (\theta)] = E_\theta[F(\theta) \cdot \frac{1}{\sigma^2}(\theta-\phi)]}$g=∇ϕ​Eθ​F(θ)=Eθ​[F(θ)⋅∇ϕ​logpϕ​(θ)]=Eθ​[F(θ)⋅σ21​(θ−ϕ)]

通常分布取为高斯分布，得到上面最后一步。

ES策略实现

本质就是一个梯度下降算法，计算出梯度g来更新参数${\theta}$θ

作者这里是用本地生成一个伪随机高斯函数种子s，随机出一个模型${\theta_s}$θs​，这样使得所有用户的模型都会有一些不同，即扰动模型。得到这个模型在一段时间内交互数据的评分f，返回种子s和评分f。central sever拿到s后可以还原出模型，然后用所有用户评分做一个平均，计算出梯度g的估计值。

保证隐私性：
考虑一个简单的情况，排序质量矩阵f的取值是离散的，e.g. 可取值为${f_0}$f0​, …, ${f_{n-1}}$fn−1​。假设要传输$f_0$f0​，以概率p传输真实值，否则从其它n-1个值中随机选取一个值。可以计算传输f的期望值为
${E(f_p|f_0) = p \cdot f_0 + \frac{1-p}{n-1} \cdot \sum \limits_{i \neq 0} f_0 = f_0 \cdot [p-\frac{1-p}{n-1}] + C}$E(fp​∣f0​)=p⋅f0​+n−11−p​⋅i̸​=0∑​f0​=f0​⋅[p−n−11−p​]+C
可以看到期望值与${f_0}$f0​是成正比的，而我们的目标是最大化n个客户${f}$f的平均值，最大化这个期望值也是一样的。

计算模型的隐私保证
根据DP的定义，
${ \frac{A(q_1) = o}{A(q_2) = o} \leq e^{\epsilon}}$A(q2​)=oA(q1​)=o​≤eϵ
当${\epsilon}$ϵ越小时，私密性越高。

直观的理解是当${q_1}$q1​的查询结果与${q_2}$q2​的查询结果相等的可能性越大时，攻击者更难区分出某个客户的数据是否存在于数据集中，或者说相等可能性越大，随机性越高。但随机性太高会使得数据很难使用。

作者假设攻击者尝试从${q_1}$q1​和${q_2}$q2​中恢复排序质量矩阵，我们关心在一个配置下${\epsilon}$ϵ的最大值是多少：
${\epsilon = \max \limits_{q_1,q_2,\widetilde{f}} log \frac{P(\widetilde{f}|q_1)}{P(\widetilde{f}|q_2)}}$ϵ=q1​,q2​,f​max​logP(f​∣q2​)P(f​∣q1​)​

${{P(\widetilde{f}|q)}}$P(f​∣q)就是${f}$f某一个取值的传输概率，以${f_0}$f0​为例，假定分布产生${f_0}$f0​的概率为${p_0}$p0​，那么其被传输的概率为

${P_T(f_0|q) = p_0 \cdot p +(1-p_0) \cdot \frac{1-p}{n-1}}$PT​(f0​∣q)=p0​⋅p+(1−p0​)⋅n−11−p​

取值范围为

${\frac{1-p}{n-1} \leq P_T(f_0|q) \leq p}$n−11−p​≤PT​(f0​∣q)≤p
可以得到一个${\epsilon}$ϵ的理论上界
${\epsilon \leq log \frac{p(n-1)}{1-p}}$ϵ≤log1−pp(n−1)​

实验
数据集是MQ2007 and MQ2008，评价标准是Mean reciprocal rank，模型分为三种，Perfect, Navigational, and Informational，具体描述见下图。

baseline模型是MSE和SVMRank，都是在离线下训练的，并且给了query和document的相关性标签。从实验结果来看FOLtR-ES和baseline的两个模型结果基本差不多。