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

14,267次阅读
13 条评论

共计 5589 个字符,预计需要花费 14 分钟才能阅读完成。

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

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

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

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

 

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

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

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

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

这篇文章提到的主题就是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)

相关数据下载
[fanctdl filename=’microsoft数据集’ filesize=’2G’ href=’http://research.microsoft.com/en-us/projects/mslr/’ filedown=’微软官方下载’][/fanctdl]

正文完
请博主喝杯咖啡吧!
post-qrcode
 1
admin
版权声明:本站原创文章,由 admin 2018-03-27发表,共计5589字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(13 条评论)
验证码
xiaoben_319 评论达人 LV.1
2018-04-28 15:29:53 回复

博主好,/Users/leiyang/RankNet/Data/train.txt 这个文件的数据格式是什么样的?

 Macintosh  Chrome  中国广东省广州市联通
    admin 博主
    2018-04-28 15:37:20 回复

    @xiaoben_319 文章中使用的是微软的数据,你可以点击文件下载链接会自动跳转到微软数据链接,格式类似libsvm格式

     Macintosh  Chrome  中国广东省广州市联通
cryyrc 评论达人 LV.1
2018-05-09 20:07:03 回复

你好,能请教几个问题吗?
1. 代码94行注释说明没有激活函数,但是代码中有加relu、sigmoid?另外我看原理里似乎也没提到要加激活函数?
2. 我照您代码运行的结果里,loss居高不下;我把激活函数去掉后,loss则始终是nan,您觉得可能是什么原因呢?
非常感谢!

 Macintosh  Safari  中国香港
    cryyrc 评论达人 LV.1
    2018-05-10 15:35:57 回复

    @cryyrc nan的问题弄好了,现在loss降得很慢,您有啥好的经验吗?

     Macintosh  Safari  中国浙江省杭州市联通
      admin 博主
      2018-05-11 20:39:09 回复

      @cryyrc 那么你的loss是否是正常水平?你的迭代次数设置多少?

       iPhone  Chrome  中国广东省广州市联通
        cryyrc 评论达人 LV.1
        2018-05-12 19:12:59 回复

        @admin 不知道哪里改错了又变nan了,之前loss好像是10左右。
        accuracy您是用啥的,ndcg吗?我的之前的accuracy(if pred == label_p)只有0.5左右,这是正常水平吗?
        谢谢

         Macintosh  Safari  中国浙江省杭州市电信
          admin 博主
          2018-05-14 08:46:51 回复

          @cryyrc 0.5还是比较低的,准确度是使用了相对排序准确率,比如A与B为一个组合,如果A的顺序的确排在B前面,则命中一个有效结果,除以总的组合个数,计算得到准确率;
          回答你之前的一个问题,代码94行原来是没哟relu函数的,后面是我自己添加的

           Macintosh  Chrome  中国广东省广州市联通
            cryyrc 评论达人 LV.1
            2018-05-14 11:36:43 回复

            @admin 谢谢。
            还有个问题是:inference的时候应该是以h2_o1和h2_o2作为reference score的预测值吧?但是经过sigmoid之后,h2_o1、h2_o2都在(0,1)上,o1、o2是在[0,4]上的,这个是怎么对上的一直想不通。

             Macintosh  Safari  中国浙江省杭州市联通
              admin 博主
              2018-05-14 12:12:22 回复

              @cryyrc h2_o1、h2_o2是用来计算i和j商品的得分,也就是用于后续索引i和索引j结果的相对顺序概率Pij,这里用了sigmoid使其处于[0,1]有点误导的含义,我晚上回家重新整理这篇文章

               Macintosh  Chrome  中国广东省广州市联通
                cryyrc 评论达人 LV.1
                2018-05-14 15:58:05 回复

                @admin 不好意思,我又来了,打扰打扰。
                我试了试下面这俩条路,结果差很多,您觉得原因是啥呢:

                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.9999951988976669

                2. 然后我把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 —

                按说这俩应该是一个意思,为什么结果差这么多,百思不得其解。

                 Macintosh  Safari  中国浙江省杭州市电信
                  admin 博主
                  2018-05-14 18:51:51 回复

                  @cryyrc 这个网站的评论模板不太,层数越多越不好看,你可以贴一个github的gist文件?单独在评论一下贴出gist地址或者可以通过service@deeplearn.me联系我

                   Macintosh  Chrome  中国广东省广州市联通
                    cryyrc 评论达人 LV.1
                    2018-05-15 00:12:57 回复

                    @admin ok,谢谢

                     Macintosh  Safari  中国浙江省杭州市电信
xzbwx 评论达人 LV.1
2019-11-26 19:06:00 回复

第 64行是不是应该是continue

 Windows  Chrome  中国天津天津市教育网