lambdaFM

前言

　　前阵子github上有人问我能不能实现一下基于FM的排序模型，于是周末就在alphaFM基础上修改一番，类似lambdaMART的思路，把lambdaRank和FM结合，实现了lambdaFM。

　　代码地址以及使用方法在：
　　https://github.com/CastellanZhang/lambdaFM

　　同样是FTRL的online learning优化方法，支持高维稀疏特征，单机多线程版本。

　　lambdaFM同时也实现了pairwise的算法，即不考虑deltaNDCG，可以通过参数-rank来选择使用lambdaRank还是pairwise。

pairwise

　　让我们从pairwise说起，以搜索为例，对于一对样本 $\langle x^i,x^j\rangle$ ，如果 $x^i$ 的相关性好于 $x^j$，我们记为 $x^i\triangleright x^j$ ,反之为 $x^i\triangleleft x^j$ ，相应目标值 $y_{ij}$ 为1或0。建立概率模型如下：
$$
P_{ij}=P(x^i\triangleright x^j|\Theta)=P(y_{ij}=1|\langle x^i,x^j\rangle,\Theta)\\
=\sigma(\hat{y}(x^i|\Theta)-\hat{y}(x^j|\Theta))=\frac{1}{1+e^{-(\hat{y}(x^i|\Theta)-\hat{y}(x^j|\Theta))}}
$$
　　其中 $\hat{y}(x|\Theta)$ 就是FM的输出：
$$
\hat{y}(x|\Theta):=w_0+\sum_{i=1}^nw_ix_i+\sum_{i=1}^n\sum_{j=i+1}^n\langle v_i,v_j\rangle x_ix_j\\
=w_0+\sum_{i=1}^nw_ix_i+\sum_{i=1}^n\sum_{j=i+1}^nx_ix_j\sum_{f=1}^kv_{i,f}v_{j,f}\\
=w_0+\sum_{i=1}^nw_ix_i+\frac{1}{2}\sum_{f=1}^k\left(\left(\sum_{i=1}^nv_{i,f}x_i\right)^2-\sum_{i=1}^nv_{i,f}^2x_i^2\right)
$$
　　模型参数估计仍然用最大似然，对于所有训练样本对集合 $S$ ，最优化问题为：
$$
\mathop{\arg\max}_{\Theta}\prod_{(\langle x^i,x^j\rangle,y_{ij})\in S}P_{ij}^{y_{ij}}(1-P_{ij})^{1-y_{ij}}
$$
　　对于训练样本集合 $S$ ，我们总可以调整每一对样本的顺序使得总是有 $x^i\triangleright x^j$ ，即所有的 $y_{ij}$ 都等于1，上面公式简化为：
$$
\mathop{\arg\max}_{\Theta}\prod_{(\langle x^i,x^j\rangle,1)\in S}P_{ij}=\mathop{\arg\min}_{\Theta}\sum_{(\langle x^i,x^j\rangle,1)\in S}-\ln P_{ij}
$$
　　这样每一对样本 $\langle x^i,x^j\rangle$ 的损失函数为：
$$
l(\Theta|\langle x^i,x^j\rangle)=-\ln P_{ij}=\ln (1+e^{-(\hat{y}(x^i|\Theta)-\hat{y}(x^j|\Theta))})
$$
　　损失函数对参数求偏导数：
$$
\frac{\partial l}{\partial\theta}=
\frac{\partial l}{\partial(\hat{y}(x^i|\Theta)-\hat{y}(x^j|\Theta))}(\frac{\partial\hat{y}(x^i|\Theta)}{\partial\theta}-\frac{\partial\hat{y}(x^j|\Theta)}{\partial\theta})
$$
　　我们令：
$$
\lambda_{ij}=\frac{\partial l}{\partial(\hat{y}(x^i|\Theta)-\hat{y}(x^j|\Theta))}=-\frac{1}{1+e^{\hat{y}(x^i|\Theta)-\hat{y}(x^j|\Theta)}}
$$
　　则上面公式可以简化为：
$$
\frac{\partial l}{\partial\theta}=
\lambda_{ij}(\frac{\partial\hat{y}(x^i|\Theta)}{\partial\theta}-\frac{\partial\hat{y}(x^j|\Theta)}{\partial\theta})
$$
　　而FM的输出对参数的偏导数在alphaFM的介绍中已经给出过，下面直接列出。注意，由于是pair的方法，偏置项 $w_0$ 相减总会抵消掉，我们可以固定 $w_0$ 为0，不需要再求解，也就不需要对 $w_0$ 再算偏导数：
$$
\frac{\partial\hat{y}}{\partial\theta}=
\begin{cases}
x_i, & if\,\,\theta\,\,is\,\,w_i \\
x_i\sum_{j=1}^nv_{j,f}x_j-v_{i,f}x_i^2 & if\,\,\theta\,\,is\,\,v_{i,f} \\
\end{cases}
$$
　　有了损失函数对参数的偏导，后面优化就是水到渠成。

lambdaRank

　　在上面的pairwise方法中，可以看到对于每一对样本都是同等对待的，算法尽量使得每一对样本的label大小关系都能预测对，而对于它们具体的label是多少以及在展现中的位置并不敏感。但在实际问题中，当评价指标是NDCG等时，这些信息就很重要了。举个例子：比如同一query下召回了4个doc，实际相关性分数分别为0 1 3 4，我们有两个排序模型A和B，通过模型的打分，排列结果分别为4 3 0 1和3 4 1 0。从pairwise的角度来看，两个排列跟最优排列4 3 1 0都只相差一次交换，似乎模型效果没差别，但是从NDCG的角度来看，NDCG(A) = 0.997，NDCG(B) = 0.852，明显模型A的效果更好。

　　为了迎合NDCG指标，需要在训练的时候对样本pair区别对待，设置不同的权重，lambdaRank提出了一种权重deltaNDCG，即在原来的顺序上如果交换样本 $i$ 和样本 $j$ ，带来的NDCG值变化的绝对值。形式上是将上面公式的 $\lambda_{ij}$ 乘以权重系数，变成 $\lambda_{ij}’$ ：
$$
\lambda_{ij}’=\lambda_{ij}|\Delta NDCG_{ij}|
$$
　　这应该就是lambda名字的来源。在我看来，lambdaRank其实仍然是一种pairwise的方法，因为并没有直接对list做优化，跟ListNet等listwise方法有本质不同。