approach和基于神经网络的listnet算法及java实现.包括：
1.基于列的学习排序(listwise)介绍
2.listnet算法介绍
3.listnet算法java实现
ltr中单文档方法是将训练集里每一个文档当做一个训练实例,文档对方法是将同一个查询的搜索结果里任意两个文档对作为一个训练实例,文档列方法是将一个查询里的所有搜索结果列表作为一个训练实例.
listwise方法将一个查询对应的所有搜索结果评分作为一个实例,训练得到一个最优的评分函数.在给出如下数据集中：(数据集介绍详见上一篇文章)
===============================================================================
0 qid:10 1:0.000000 2:0.000000 3:0.000000 ... 45:0.000000 46:0.000000 #docid =
1 qid:10 1:0.031310 2:0.666667 3:0.500000 ... 45:0.448276 46:0.000000 #docid =
1 qid:10 1:0.078682 2:0.166667 3:0.500000 ... 45:1.000000 46:0.000000 #docid =
0 qid:50 1:0.044248 2:0.400000 3:0.333333 ... 45:0.622951 46:0.000000 #docid =
2 qid:50 1:0.764381 2:0.200000 3:0.000000 ... 45:0.252874 46:0.000000 #docid =
1 qid:50 1:0.693584 2:0.000000 3:0.000000 ... 45:0.275862 46:0.000000 #docid =
基于列的学习排序(listwise approach)是将qid=10对应的所有查询文档作为一个实例进行训练,即一个查询及其对应的所有搜索结果评分作为一个实例进行训练;训练得到一个最后评分函数f后,test测试集中一个新的查询,函数f对每一个文档进行打分,之后按照得分顺序由高到低排序即是对应搜索的结果.
下面介绍一种基于搜索结果排序组合的概率分布情况来训练.如下图：
参考《这就是搜索引擎：核心技术详解 by:张俊林》第5章
用户输入查询q1,假设返回的搜索结果集合里包含a、b和c三个文档,搜索引擎要对搜索结果排序,而3个文档顺序共有6种排列组合方式:abc、acb、bac、bca、cab和cba,每种排列组合都是一种可能的搜索结果排序方法.
我们可以把函数g设想成最优评分函数(人工打分),对查询q1来说：文档a得6分,文档b得4分,文档c得3分;我们的任务是找到一个函数,使得其对q1的搜索结果打分顺序尽可能的接近标准函数g.其中函数f和h就是实际的评分函数,通过比较两个概率之间的kl距离,发现f比h更接近假想的最优函数g.故选择函数f为搜索的评分函数.
listwise主要的算法包括：adarank、svm-map、listnet、lambdamart等.
pointwise学习排序是将训练集中的每个文档看作一个样本获取rank函数,主要解决办法是把分类问题转换为单个文档的分类和回归问题,如prank.
pairwise学习排序(下篇介绍)是将同一个查询中不同的相关标注的两个文档看作一个样本,主要解决思想是把rank问题转换为二值分类问题,如ranknet.
listwise学习排序是将整个文档序列看作一个样本,主要是通过直接优化信息检索的评价方法和定义损失函数两种方法实现.listnet算法将luce模型引入到了排序学习方法中来表示文档序列,同时大多数基于神经网络的排序学习算法都是基于luce模型(luce模型就是将序列的任意一种排序方式表示成一个概率值)来表示序列的排序方式的.
listnet算法参考：
通过该算法步骤解释如下:
1.首先输入训练集train.txt数据.{x,y}表示查询号对应的样本文档,包括标注等级label=y(46维微软数据集共3个等级:0-不相关,1-部分相关,2-全部相关),x表示对应的特征和特征值,需要注意的是x(m)表示m个qid数,每个x(m)中有多个样本文档.
2.初始化操作.迭代次数t(设置为30次)和learning rate(ita可以为0.003、0.001、0.03、0.01等),同时初始化权重w.
3.两层循环操作.第一层是循环迭代次数：for t = 1 to t do;第二层循环是迭代查询总数(qid总数)：for i = 1 to m do.
4.计算该行分数用当前权重w.注意权重w[46]是一维数组,分别对应46个特征值,同时f(w) = w * x.
5.计算梯度向量delta_w(46个维度).其中计算公式如下：
其中n(i)表示查询号qid=i对应的总文档数,j表示qid=i的当前文档.x的右上方下标表示对应的qid数,右下方下标表示对应的文档标号.而p是计算概率的函数,如下：
它表示s1排第一、s2排第二且s3排第三的概率值.这就是使用luce模型使一个序列的排序方式表示成一个单一的概率值.实际过程中,我们通过使用exp()函数来表示fai.主要保证其值为正、递增.
但n!的时间复杂度很显然效率很低,所以提出了top-k概率来解决,即用前k项的排列概率来近似原有的整个序列的概率,通过降低精准度来换取运行时间.
top-k概率公式如下：
在下面的java代码实现中我采用的是top-1,即获取当前行文档排第一的概率值.
6.循环更新权重w.
7.最后输出w[46]权重,训练过程结束.通过该模型可以进行测试预测排序,test.txt通过该权重进行w*x打分,再进行从高到低排序即可.
ps:这仅仅是我结合两篇论文后的个人理解,如果有错误或不足之处,欢迎探讨!同时感谢我的同学xp和mt,我们一起探讨和分享才理解了一些listnet算法及代码.
(ps:该部分代码非常感谢我的组长xp和mt,他们在整个编程路上对我帮助是一生的.同时自己也希望以后工作中能找到更多的老师和挚友指导我前行~)
代码中有详细的注释,按照每个步骤完成.左图是主函数,它主要包括：读取文件并解析数据、写数据、学习排序模型和打分预测,右图是学习排序的核心算法.
代码如下：
上面的代码我更希望你关注的是listnet在训练模型过程中的代码,也就是通过train.txt获取得到46维的权重的模型.通过该模型你可以对test.txt进行打分(权重*特征值)排序,而上面的代码仅是对train.txt进行了简单的打分操作,那时因为我们的作业是基于hadoop或spark分布式处理基础上的.所以该部分由其他同学完成.
同时你也可以通过开源的ranklib或罗磊同学的listnet算法进行学习,地址如下:
最后我们使用开源的map和ndcg@r简单对该算法进行了性能评估,同时附上hadoop上的运行截图(mapreduce只找到了prank的一张截图).
希望文章对大家有所帮助,同时我是根据论文写出的java代码,如果有错误或不足之处,还请海涵~同时欢迎提出问题,我对机器学习和算法的了解还是初学,但是会尽力答复.同时发现该部分的代码真的很少,所以才写了这样一些文章,后面还准备写写pairwise和map\ndcg评价.