欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

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}\) 的影响:

QQ20160731-0

模型和损失函数

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/ 查看。

 

参考资料

《Learning to Rank using Gradient Descent》

 

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

评论 2

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    Pij公式推导的第三行,分子的参数应该是Oi-Ok+Ok-Oj。

    曹鹏3个月前 (07-26)回复
    • 已改

      leihao3个月前 (07-27)回复

关注大数据算法在工业界应用

本站的GitHub关于本站