• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

LTR排序之pair-wise-ranknet算法TensorFlow实现

ml admin 6个月前 (03-27) 1512次浏览 12个评论 扫描二维码

在之前的有一篇文章给出了pointwise 之 prank 算法说明以及实现,这一篇文章会讲解 pairwise。

写这篇文章之前也看了很多篇博客包括原版论文,在这里自己尽量用白话 的方式让读者理解这个看似很厉害的方法。

乍一看 pair,英文直接翻译就是一对的意思,哈哈,这个排序方法与组队有很大的关系,究竟组队会在哪里体现呢?等会就知道了

先看两幅图,为什么要出现组队情况

 

在上图中红色的框是用户点击的框,黄色的框虽然排在前面但是用户没有点击,因此按照我们正常的理解红色的商品应该放在前面更符合用户的习惯,但是现在的

结果是商品排在黄色的商品后面,所以这个排序还是存在一定改善的空间。此时出现了两个商品的对比,也就是说红色的商品相对黄色的商品较好,此处也仅仅是相对而言,

把这两个商品单独拎出来看的话,那肯定是红色框框里面的商品更好。

这篇文章提到的主题就是 pariwise,这时候 pair 的意思就体现出来了。这个方法的核心就是先将商品组合起来,组合还是有先后之分的,我们定义一下几个规则

给出两个商品\( i,j \),如果 i 比 j 更好(更符合用户的口味)那么定义 \( <i,j>,1\) 如果二者的相关性相同也就是都是 50%概率, \( <i,j>,0\) 除此之外就是\( <i,j>,-1\)

机器学习排序还是需要找到一个函数\( F(x)\) 来给我们的样本打分排序,如果我们的样本 i 比样本 j 更好,那么的对应的分数\( F(i)>F(j)\)

假设上面的打分函数是个线性模型,那么函数中有很多的参数需要我们去求解,这些参数该如何求解?
这个跟逻辑回归就有点像了,在逻辑回归中我们给定了样本,然后我们想要在样本集上最大化 p(y|x),这个可以通过最大似然估计的方法来求解。

首先我们要给出概率定义公式:

样本 \(x_i\) 的排名得分用 \(o_i\) 表示,定义 \(o_{i,j}=o_i−o_j\) ,如果 \(o_{i,j}>0\) 就说明 xi 名次高于 xj 。将这个排名概率化,定义:

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

表示 xi 排名高于 xj 的概率。可以发现, \(o_{i,j}=0\) 的时候有 \(P_{i,j}=0.5\) 。

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

例如已知 Pi,k 和 Pk,j ,那么 Pi,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} \]

其中最后一步的推倒使用了 Pi,j 和 oi,j 的定义的推导,即:
\[ o_{i,j} = \ln \frac{P_{i,j}}{1-P{i,j}}\]

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

下面给出损失函数的定义
\[ \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} \]
跟逻辑回归的一模一样,感叹一下

上述公式有两个概率,其中一个在之前的描述中已经给出来了,还有一个\( \hat{P}_{i,j} \)计算方法未给出,这个概率是真实的 i 和 j 的相对顺序的概率,下面给出计算公式:
\[ \hat{P}_{i,j}=\frac{1}{2}(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\)

呀呀呀,上面描述的都是 ranknet 算法,pairwise 的算法还有其他的,有兴趣可以继续了解,博主也会去学习


TensorFlow 的代码保存在 mac 上面,明天抽个时间贴到这里来。。。。,先去洗澡睡觉觉了

# -*- coding: utf-8 -*-
# @Time    : 2018/3/27 上午 10:55
# @Author  : Tomcj
# @File    : tensor_ranknet.py
# @Software: PyCharm
import  tensorflow as tf
import numpy as np

BATCH_SIZE=100
y_train=[]
X_train=[]
Query=[]
array_train_x1=[]
array_train_x0=[]

feature_num = 46
h1_num = 10
def extractFeatures(split):
    '''
    获取特征
    '''
    features = []
    for i in range(2, 48):
        features.append(float(split[i].split(':')[1]))
    return features


def extractQueryData(split):
    '''
    获取以下数据 quryid documentid 等
    Format:
    
    '''
    queryFeatures = [split[1].split(':')[1]]
    queryFeatures.append(split[50])
    queryFeatures.append(split[53])
    queryFeatures.append(split[56])

    return queryFeatures
def get_microsoft_data():
    '''
    获取基础样本特征数据
    :return:
    '''
    with open('/Users/leiyang/RankNet/Data/train.txt','r') as fp:
        for data in fp:
            split = data.split()
            y_train.append(int(split[0]))
            X_train.append(extractFeatures(split))
            Query.append(extractQueryData(split))

def get_pair_feature(y_train,Query):
    '''
    获取组合样本特征
    :return:
    '''
    pairs = []
    tmp_x0=[]
    tmp_x1=[]
    for i in range(0, len(Query)):
        for j in range(i + 1, len(Query)):
            # Only look at queries with the same id
            if (Query[i][0] != Query[j][0]):
                break
            # Document pairs found with different rating
            if (Query[i][0] == Query[j][0] and y_train[i] != y_train[j]):
                # Sort by saving the largest index in position 0
                if (y_train[i] > y_train[j]):
                    pairs.append([i, j])
                    tmp_x0.append(X_train[i])
                    tmp_x1.append(X_train[j])
                else:
                    pairs.append([j, i])
                    tmp_x0.append(X_train[j])
                    tmp_x1.append(X_train[i])

    array_train_x0 = np.array(tmp_x0)
    array_train_x1=np.array(tmp_x1)
    print('Found %d document pairs' % (len(pairs)))
    return pairs,len(pairs),array_train_x0,array_train_x1


with tf.name_scope("input"):
    x1 = tf.placeholder(tf.float32,[None, feature_num],name="x1")
    x2 = tf.placeholder(tf.float32,[None, feature_num],name="x2")

#添加隐层节点
with tf.name_scope("layer1"):
    with tf.name_scope("w1"):
        w1 = tf.Variable(tf.random_normal([feature_num, h1_num]), name="w1")
    with  tf.name_scope("b1"):
        b1 = tf.Variable(tf.random_normal([h1_num]), name="b1")

    #此处没有添加激活函数
    with tf.name_scope("h1_o1"):
        h1_o1 = tf.matmul(x1,w1) + b1
        h1_o1=tf.nn.relu(h1_o1)


    with tf.name_scope("h2_o1"):
        h1_o2 = tf.matmul(x2, w1) + b1
        h1_o2 = tf.nn.relu(h1_o2)

#添加输出节点
with tf.name_scope("output"):
    with tf.name_scope("w2"):
        w2 = tf.Variable(tf.random_normal([h1_num, 1]), name="w2")

    with tf.name_scope("b2"):
        b2 = tf.Variable(tf.random_normal([1]))

    h2_o1 = tf.matmul(h1_o1, w2) + b2
    h2_o2 = tf.matmul(h1_o2, w2) + b2
    h2_o1=tf.sigmoid(h2_o1)
    h2_o2=tf.sigmoid(h2_o2)

#根据输出节点计算概率值
with tf.name_scope("loss"):
    # o12 = o1 - o2
    h_o12 = h2_o1 - h2_o2
    pred = 1/(1 + tf.exp(-h_o12))
    #此处的 label_P 就是真实的概率,因为前面组 pair 数据已经人为将相关的样本放在
    #前面,所以 Sij 均为 1,所以计算的结果就是 1
    lable_p = 1

    cross_entropy = -lable_p * tf.log(pred) -(1-lable_p) * tf.log(1-pred)

    reduce_sum = tf.reduce_sum(cross_entropy)
    loss = tf.reduce_mean(reduce_sum)

with tf.name_scope("train_op"):
    train_op = tf.train.GradientDescentOptimizer(0.1).minimize(loss)


with tf.Session() as sess :
    # step 1 解析 microsoft 数据集
    get_microsoft_data()
    #step 2 获取 pair 组合
    pairs,datasize,array_train_x0,array_train_x1=get_pair_feature(y_train,Query)
    init = tf.global_variables_initializer()
    sess.run(init)
    for epoch in range(0,10000):
        start=(epoch*BATCH_SIZE)%datasize
        end=min(start+BATCH_SIZE,datasize)
        sess.run(train_op, feed_dict={x1: array_train_x0[start:end,:], x2: array_train_x1[start:end,:]})
        if epoch % 1000== 0 :
            l_v = sess.run(loss, feed_dict={x1:array_train_x0, x2:array_train_x1})

            result_0=sess.run(h2_o1,feed_dict={x1:array_train_x0, x2:array_train_x1})
            result_1=sess.run(h2_o2,feed_dict={x1:array_train_x0, x2:array_train_x1})
            #使用所有的样本计算模型预测的准确率
            print  np.sum(result_0>result_1)*1.0/datasize
            # print  sess.run(cross_entropy,feed_dict={x1:array_train_x0, x2:array_train_x1})
            # print "------ epoch[%d] loss_v[%f] ------ "%(epoch, l_v)

相关数据下载
文件下载


Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明LTR 排序之 pair-wise-ranknet 算法 TensorFlow 实现
喜欢 (5)
admin
关于作者:

您必须 登录 才能发表评论!

(12)个小伙伴在吐槽
  1. 博主好,/Users/leiyang/RankNet/Data/train.txt 这个文件的数据格式是什么样的?
    • 文章中使用的是微软的数据,你可以点击文件下载链接会自动跳转到微软数据链接,格式类似libsvm格式
      admin2018-04-28 15:37
  2. 你好,能请教几个问题吗?1. 代码94行注释说明没有激活函数,但是代码中有加relu、sigmoid?另外我看原理里似乎也没提到要加激活函数?2. 我照您代码运行的结果里,loss居高不下;我把激活函数去掉后,loss则始终是nan,您觉得可能是什么原因呢?非常感谢!
    cryyrc2018-05-09 20:07
    • nan的问题弄好了,现在loss降得很慢,您有啥好的经验吗?
      cryyrc2018-05-10 15:35
      • 那么你的loss是否是正常水平?你的迭代次数设置多少?
        admin2018-05-11 20:39
        • 不知道哪里改错了又变nan了,之前loss好像是10左右。accuracy您是用啥的,ndcg吗?我的之前的accuracy(if pred == label_p)只有0.5左右,这是正常水平吗?谢谢
          cryyrc2018-05-12 19:12
          • 0.5还是比较低的,准确度是使用了相对排序准确率,比如A与B为一个组合,如果A的顺序的确排在B前面,则命中一个有效结果,除以总的组合个数,计算得到准确率;回答你之前的一个问题,代码94行原来是没哟relu函数的,后面是我自己添加的
            admin2018-05-14 08:46
            • 谢谢。还有个问题是:inference的时候应该是以h2_o1和h2_o2作为reference score的预测值吧?但是经过sigmoid之后,h2_o1、h2_o2都在(0,1)上,o1、o2是在[0,4]上的,这个是怎么对上的一直想不通。
              cryyrc2018-05-14 11:36
              • h2_o1、h2_o2是用来计算i和j商品的得分,也就是用于后续索引i和索引j结果的相对顺序概率Pij,这里用了sigmoid使其处于[0,1]有点误导的含义,我晚上回家重新整理这篇文章
                admin2018-05-14 12:12
                • 不好意思,我又来了,打扰打扰。我试了试下面这俩条路,结果差很多,您觉得原因是啥呢:1. 按您的code(使label_p始终为1)来,有3点区别是: output层去掉了sigmoid; 另外layer1那层relu之前加了个batch_normalization(不加的时候我的loss会nan,遂加之); cross_entropy改用了tf.nn.sigmoid_cross_entropy_with_logits(也是为了解决nan)。这样的结果是一个epoch之后loss就降到0左右了(accuracy=0.99)。------ epoch[0] loss_v[313.779449] ------ 0.6056278521548547------ epoch[1000] loss_v[0.000299] ------ 0.99999519889766692. 然后我把label_p改成了0或1的形式,其他参数和第一种相同,这次acc始终0.5+,试着把batch_size加到10000,跑了100000个epoch后acc也才到0.6。--- epcoh: 0 loss_v: 3025.997314453125 acc: 0.5300270590833341 ------ epcoh: 1000 loss_v: 0.9345578551292419 acc: 0.5659493897177698 ------ epcoh: 2000 loss_v: 0.7046830654144287 acc: 0.5705210409417381 ---...--- epcoh: 98000 loss_v: 0.6801395416259766 acc: 0.5912141276199131 ------ epcoh: 99000 loss_v: 0.674396276473999 acc: 0.5931556957184217 ---按说这俩应该是一个意思,为什么结果差这么多,百思不得其解。
                  cryyrc2018-05-14 15:58
                  • 这个网站的评论模板不太,层数越多越不好看,你可以贴一个github的gist文件?单独在评论一下贴出gist地址或者可以通过service@deeplearn.me联系我
                    admin2018-05-14 18:51
                    • ok,谢谢
                      cryyrc2018-05-15 00:12