Abstract

本文提出了 RankNet, 引出pairwise排序方法梯度下降法来学习排序. 我们使用神经网络来实现这个 idea本文使用 toy data来测试结果.这是第一篇关于 AUC 优化 pairwise 方法的论文, 虽然已经过去了几年,但是对于初学者的我来说仍然具有很大的意义.

Introduction

我们使用神经网络来学习排序函数, 一个常见的例子是搜索引擎排名.对于此问题，数据由一组查询关键字组成，对于每个查询关键字，都包含一组返回的文档.在训练阶段，一些查询关键词/文档对对被标记为相关性（“优秀匹配”，“良好匹配”等）.因此所有的数据集中的数据都会参与排名,只有满足召回条件的文档才会参加排名.本文的贡献在于1.不需要向 point wise 那样需要回归预测相关性,而是直接进行排序. 2. 提出 pair wise 的概率代价函数,这种方法不是特定于基础学习算法; 我们选择使用神经网络探索这些想法，因为它们很灵活.然而本文提出的成本函数同样可以应用于各种机器学习算法.在实验部分:本文通过使用 toy dataset 和从商业搜索引擎搜索到的数据来提供试验.对于商业搜索引擎方面,数据采用17004个查询词,对于每一个查询词,最多返回1000个文档,因此每个查询词最多生成1000个特征向量.
符号说明:我们用 N 表示相关登记,训练集样本数目为 m, 数据的维度为 d.

A probabilistic Ranking Cost Function

我们考虑一个这样的模型:从\mathcal{R}^d中抽样一些成对的样本[A,B]和标签的概率\hat{P}_ {AB},标签概率\hat{P}_ {AB}的意思是样本 A 排名比样本 B 高的概率,他们不需要训练集数据的完整排名。我们考虑一个模型f:R^d \mapsto R能够使得测试样本的顺序能够由 f 给出的实数值决定. 如果f(x_1) > f(x_2), 那么该模型认为x_1 \triangleright x_2(x_1的排名比x_2要高)
我们用P_{ij}表示模型的后验概率P(x_i \triangleright x_j), 其中i,j = 1,2,...,m, 我们令\bar{P}_ {ij}为理想标签的后验概率. 定义o_i \equiv f(x_i) 和o_{ij} \equiv f(x_i)-f(x_j).我们使用交叉熵代价函数
C_{ij} \equiv C(o_{ij}) = -\bar{P}_ {ij} \log P_{ij} - (1-\bar{P}_ {ij})\log(1-P_{ij}) \quad\quad(1)
其中我们使用logistic函数完成从输出到概率的映射.
P_{ij} \equiv \frac{e^{o_{ij}}}{1 + e^{o_{ij}}} \quad\quad (2)
然后我们有C_{ij}
C({o_{ij}}) = - \bar{P}_{ij} o_{ij} + \log(1 + e^{o_{ij}}) \quad\quad (3)
值得一提的是C_{ij}是线性渐进函数,对于标签的噪声问题,该损失函数会比二次函数的鲁棒性更强.当i和j没有相对排名信息时,\bar{P}_ {ij}=\frac12(1+S_{ij}).
其中S_{ij}的意思就是,给定两个商品i,j. 如果i比j更好(更符合用户的口味)那么定义<i,j>,S_{ij}=1如果两者的相关性相同也就是都是50%的概率,<i,j>,S_{ij}=0,除此之外就是<i,j>,S_{ij}=-1

Combining Probabilities

上述模型对\bar{P}_ {ij} 提出了一致性要求,因此必须存在一个理想的输出\bar{o}_ i使得
\bar{P}_{ij} \equiv \frac{e^{\bar{o}_{ij}}}{1+e^{\bar{o}_{ij}}} \quad\quad (4)
其中$\bar{o}{ij} \equiv \bar{o}_i - \bar{o}_j出现这种一致性是因为如果不满足,那么在给定期望的pair-wise概率,将不会存在任何模型的输出.一致性约束给出了\bar{P}的一些可能的选择,例如给定\bar{P}{ij}和\bar{P}{jk}$, 根据公式(4), 我们有:
\bar{P}_ {ik} = \frac{\bar{P}_ {ij}\bar{P}_ {jk}}{1 + 2 \bar{P}_{ij}\bar{P}_{jk} - \bar{P}_{ij} - \bar{P}_{jk}} \quad\quad(5)
这个结论是说:对于任何一个长度为n的排列，只需要知道n-1个相邻 item 的概率 P_{i,i+1}，就可以推断出来任何两个item的排序概率。
其中最后一步的推导使用了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(n) 问题的理论基础。

Experiment

对于实验部分,需要强调的是:我们只需要构造正序的pair就足够了,因为对于模型来说正序Pair和逆序Pair是完全等价的,加入逆序Pair对于模型来说不能增加任何新的信息.这里我们用一个小demo来作为介绍,我们假设有一个计算文档score的函数f,为了简化问题的标书,我们假定其为线性函数,即:
f(x) = w[1] \times w[1] + w[2] \times w[2] + w[3] \times w[3]...

import sys
import math
x = [(2,0,0),(2,1,‐1),(2,2,‐2),(0,1,‐1),(0,2,‐2),(0,1,‐1)]
alpha = 0.001 # 步长
m = len(x) # 训练数据条数
w = [0.1,0.1,0.1] #初始随机设置权值
loop_max = 10 # 最大迭代次数
count = 1
while count<=loop_max:
    print ('第%d轮：'%count)
    count += 1
    # 遍历训练数据集，不断更新w值
    for i in range(m):
        sum = w[0]*x[i][0]+w[1]*x[i][1]+w[2]*x[i][2]
        w[0] = w[0]+alpha*x[i][0]*(1+2*math.exp(sum))/(1+math.exp(sum))
        w[1] = w[1]+alpha*x[i][1]*(1+2*math.exp(sum))/(1+math.exp(sum))
        w[2] = w[2]+alpha*x[i][2]*(1+2*math.exp(sum))/(1+math.exp(sum))
    print w