RankNet算法原理和实现

首先抄一下论文中的理论，介绍一下RankNet，由于损失函数的特殊性，所以通过Tensorflow实现这个网络。

排序问题

在互联网的世界中有很多场景涉及到排序，搜索引擎根据用户输入的Query检索得到最相关的topk个网页；推荐引擎根据用户的兴趣偏好推荐用户最感兴趣的topk个文章。涉及到topk的问题，都会涉及到排序的问题。

排序有下面几个思路：

1. 每一个文章计算一个绝对得分，然后按照得分排序。
2. 每两个文章计算一下谁的得分高，用这个相对得分进行排序。
3. 枚举topk的所有排列情况，计算综合得分最高的一种作为结果。

上面三中方法分别被称为point-wise、pair-wise、list-wise，对应的复杂度分别为 $O(n),O(n^2), O(A_n^k)$ ，我接下来介绍的RankNet算法是一种复杂度为 $O(n)$ 但是属于pair-wise方法的算法。

排名的传递性

样本 $x_i$ 的排名得分用 $o_i$ 表示，定义 $o_{i,j}=o_i-o_j$ ，如果 $o_{i,j}>0$ 就说明 $x_i$ 名次高于 $x_j$ 。将这个排名概率化，定义：

$P_{i,j}=\frac{e^{o_{i,j}}}{1+e^{o_{i,j}}}$

表示 $x_i$ 排名高于 $x_j$ 的概率。可以发现， $o_{i,j}=0$ 的时候有 $P_{i,j}=\frac{1}{2}$ 。

接下来就有一个有意思的结论：对于任何一个长度为n的排列，只需要知道n-1个相邻item的概率 $P_{i,i+1}$ ，就可以推断出来任何两个item的排序概率。

例如已知 $P_{i,k}$ 和 $P_{k,j}$ ，那么 $P_{i,j}$ 可以使用下面公式推断出来：

$\begin{matrix} P_{i,j}&=&\frac{e^{o_{i,j}}}{1+e^{o_{i,j}}}\\ &=&\frac{e^{o_i-o_j}}{1+e^{o_i-o_j}} \\ &=& \frac{e^{o_i- o_k + o_k + o_j}}{1+e^{o_i-o_k + o_k -o_j}}\\&=& \frac{e^{o_{i,k} + o_{k,j}}}{1+e^{o_{i,k} + o_{k,j}}} \\&=& \frac{P_{i,k}\ P_{k,j}}{1+2P_{i,k}\ P_{k,j}\ -P_{i,k}\ -P_{k,j}}\end{matrix}$

其中最后一步的推倒使用了 $P_{i,j}$ 和 $o_{i,j}$ 的定义的推导，即：

$o_{i,j} = \ln \frac{P_{i,j}}{1-P{i,j}}$

所以，我们如果想要知道任何两个item的排列关系，不需计算 $C_n^2$ 种组合，n-1个 $P_{i,i+1}$ 已经含有了所有组合的排序信息，这个就是RankNet将 $O(C_n^2)$ 复杂度的问题，变为 $O(n)$ 问题的理论基础。

下图为 $P_{i,j}=P_{j,k}$ 时候，不同的取值对计算 $P_{i,k}$ 的影响：

模型和损失函数

RankNet是一个三层的神经网络，输入为两个样本 $x_i$ 的特征，输出是 $o_{i}$ 的回归值。特别之处在于，每计算两个样本的分值 $o_{i},o_j$ 进行一次损失的计算，然后进行反向传播。

损失函数函数使用交叉熵的形式，具体为：

$\begin{matrix}C(o_{ij})&=&-\hat{P}_{i,j} \ln P_{ij} - (1-\hat{P}_{ij})\ln (1-P_{ij})\\&=&-\hat{P}_{ij} o_{ij}+\ln (1+e^{o_{ij}})\end{matrix}$

Tensorflow实现RankNet

网络结构前面已经说的比较清楚了，具体代码如下（点击展开）：

上面代码会在当前目录写入tensorboard信息，通过命令tensorboard --logdir=./logs/ 查看。

参考资料

未经允许不得转载：大数据算法 » RankNet算法原理和实现