首先抄一下论文中的理论,介绍一下RankNet,由于损失函数的特殊性,所以通过Tensorflow实现这个网络。
排序问题
在互联网的世界中有很多场景涉及到排序,搜索引擎根据用户输入的Query检索得到最相关的topk个网页;推荐引擎根据用户的兴趣偏好推荐用户最感兴趣的topk个文章。涉及到topk的问题,都会涉及到排序的问题。
排序有下面几个思路:
- 每一个文章计算一个绝对得分,然后按照得分排序。
- 每两个文章计算一下谁的得分高,用这个相对得分进行排序。
- 枚举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
网络结构前面已经说的比较清楚了,具体代码如下(点击展开):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
#coding=utf-8 import tensorflow as tf import numpy as np import random import matplotlib.pyplot as plt def get_train_data(batch_size = 32): #生成的数据特征维数为10,lable为前5个维度的特征 * 2 + 后五个维度的特征 * 3得到 X1,X2 = [],[] Y1,Y2 = [],[] for i in range(0, batch_size): x1 = [] x2 = [] o1 =0.0 o2 = 0.0 for j in range(0,10): r1 = random.random() r2 = random.random() x1.append(r1) x2.append(r2) mu = 2.0 if j >=5 : mu = 3.0 o1 += r1 * mu o2 += r2 * mu X1.append(x1) Y1.append([o1]) X2.append(x2) Y2.append([o2]) return ((np.array(X1), np.array(X2)), (np.array(Y1), np.array(Y2) ) ) feature_num = 10 h1_num = 10 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") o1 = tf.placeholder(tf.float32, [None,1], name="o1") o2 = tf.placeholder(tf.float32, [None, 1], name="o2") #添加隐层节点 with tf.name_scope("layer1"): with tf.name_scope("w1"): w1 = tf.Variable(tf.random_normal([feature_num, h1_num]), name="w1") tf.histogram_summary("layer1/w1", w1) with tf.name_scope("b1"): b1 = tf.Variable(tf.random_normal([h1_num]), name="b1") tf.histogram_summary("layer1/b1", b1) #此处没有添加激活函数 with tf.name_scope("h1_o1"): h1_o1 = tf.matmul(x1,w1) + b1 tf.histogram_summary("h1_o1", h1_o1) with tf.name_scope("h2_o1"): h1_o2 = tf.matmul(x2, w1) + b1 tf.histogram_summary("h2_o1", h1_o2) #添加输出节点 with tf.name_scope("output"): with tf.name_scope("w2"): w2 = tf.Variable(tf.random_normal([h1_num, 1]), name="w2") tf.histogram_summary("output/w2", w2) with tf.name_scope("b2"): b2 = tf.Variable(tf.random_normal([1])) tf.histogram_summary("output/b2", b2) h2_o1 = tf.matmul(h1_o1, w2) + b2 h2_o2 = tf.matmul(h1_o2, w2) + b2 #根据输出节点计算概率值 with tf.name_scope("loss"): o12 = o1 - o2 h_o12 = h2_o1 - h2_o2 pred = 1/(1 + tf.exp(-h_o12)) lable_p = 1/(1 + tf.exp(-o12)) cross_entropy = -lable_p * tf.log(pred) -(1-lable_p) * tf.log(1-pred) reduce_sum = tf.reduce_sum(cross_entropy, 1) loss = tf.reduce_mean(reduce_sum) tf.scalar_summary("loss", loss) with tf.name_scope("train_op"): train_op = tf.train.GradientDescentOptimizer(0.1).minimize(loss) with tf.Session() as sess : summary_op = tf.merge_all_summaries() writer = tf.train.SummaryWriter("./logs/", sess.graph) init = tf.initialize_all_variables() sess.run(init) for epoch in range(0,10000): X, Y = get_train_data() sess.run(train_op, feed_dict={x1:X[0], x2:X[1], o1:Y[0], o2:Y[1]}) if epoch % 10 == 0 : summary_result = sess.run(summary_op, feed_dict={x1:X[0], x2:X[1], o1:Y[0], o2:Y[1]}) writer.add_summary(summary_result, epoch) l_v = sess.run(loss, feed_dict={x1:X[0], x2:X[1], o1:Y[0], o2:Y[1]}) h_o12_v = sess.run(h_o12, feed_dict={x1:X[0], x2:X[1], o1:Y[0], o2:Y[1]}) o12_v = sess.run(o12, feed_dict={x1:X[0], x2:X[1], o1:Y[0], o2:Y[1]}) print "------ epoch[%d] loss_v[%f] ------ "%(epoch, l_v) for k in range(0, len(o12_v)): print "k[%d] o12_v[%f] h_o12_v[%f]"%(k, o12_v[k], h_o12_v[k]) |
上面代码会在当前目录写入tensorboard信息,通过命令tensorboard --logdir=./logs/ 查看。
参考资料
《Learning to Rank using Gradient Descent》
未经允许不得转载:大数据算法 » RankNet算法原理和实现