Learning to rank算法

简介

互联网搜索诞生初期,检索模型使用的特征相对简单,这些特征主要基于query与doc之间的相关度来对文档进行排序。另一种传统排序模型是重要性排序模型,此时模型不考虑query ,而仅仅根据文档(网页)之间的图结构来判断doc的重要程度,例如PageRank排序模型。而随着互联网不断发展,海量数据的产生,更多复杂有效的特征被用于搜索排序,人工调参已不能满足需求,此时机器学习开始在搜索排序领域得到应用,learning to rank逐渐成为热门研究方向。

搜索

搜索的目标是选择与用户输入query最相关的一组文档,目前主要步骤如下:

  1. 粗排:query-doc匹配,得到一组与query相关的文档,目前一般采用倒排索引实现;
  2. 精排:选取更多特征,按照用户点击该doc的可能性大小排序,Learning to rank即是实现该部分的机器学习模型。

机器学习排序系统

典型的机器学习排序系统如下图所示:

Learning to rank

包含pointwise方法、pairwise方法和listwise方法三种类型。

(1) pointwise方法:对于某一个query, 判断每个doc这个query的相关度,由此将docs排序问题转化为了分类(比如相关、不相关)或回归问题(相关程度越大,回归函数的值越大)。其L2R框架具有以下特征:

  • 输入空间中样本是单个 doc(和对应 query)构成的特征向量;
  • 输出空间中样本是单个 doc(和对应 query)的相关度;
  • 假设样本满足打分函数;
  • 损失函数评估单个 doc 的预测得分和真实得分之间差异。

(2) pairwise方法:该方法并不关心某一个doc与query相关程度的具体数值,而是将排序问题转化为任意两个不同的docs di和dj谁与当前的query更相关的相对顺序的排序问题。一般分为di比dj更相关、更不相关和相关程度相等三个类别,分别记为{+1, -1, 0},由此便又转化为了分类问题。其 L2R 框架具有以下特征:

  • 输入空间中样本是(同一 query 对应的)两个 doc(和对应 query)构成的两个特征向量;
  • 输出空间中样本是 pairwise preference;
  • 假设空间中样本满足二变量函数;
  • 损失函数评估 doc pair 的预测 preference 和真实 preference 之间差异。

(3) listwise方法:将一个query对应的所有相关文档看做一个整体,作为单个训练样本。其 L2R 框架具有以下特征:

  • 输入空间中样本是(同一 query 对应的)所有 doc构成的多个特征向量(列表);
  • 输出空间中样本是这些 doc与对应 query的相关度排序列表;
  • 假设空间中样本满足多变量函数,对于 docs 得到其排列,实践中,通常是一个打分函数,根据打分函数对所有 docs 的打分进行排序得到 docs 相关度的排列;
  • 损失函数分成两类,一类是直接和评价指标相关的,还有一类不是直接相关的。

由于评价指标通常是离散不可微的,直接优化ranking评价指标并不简单,通常有以下处理方式:

  • 优化基于评价指标的 ranking error 的连续可微的近似,这种方法就可以直接应用已有的优化方法,如SoftRank,ApproximateRank,SmoothRank。
  • 优化基于评价指标的 ranking error 的连续可微的上界,如 SVM-MAP,SVM-NDCG,PermuRank。
  • 使用可以优化非平滑目标函数的优化技术,如 AdaRank,RankGP。非直接相关的损失函数则不再使用与评价相关的loss来优化模型,而是设计能衡量模型输出与真实排列之间差异的 loss,如此获得的模型在评价指标上也能获得不错的性能。例如 :ListNet,ListMLE,StructRank和BoltzRank。

主要模型分类

按照这三种类型,可以将主要模型做如下梳理:

图中Rank Creation指给定查询Query和文档Docs,得到Docs排序结果;Rank Aggregation指综合多个不同的Ranking System的排序结果,得出最终排序结果。

XGBoost

下面以xgboost模型为例,说明如何完成排序。大致过程如下:
训练

  1. 获取训练数据;
  2. 构造特征候选集,完成训练样本准备;
  3. 基于xgboost寻找划分点,重复该步至不能再分裂划分点;
  4. 通过最小化pairwise loss生成下一棵树;
  5. 生成设定数量的树后,训练完成;

测试

  1. 输入测试样本;
  2. 根据训练所得模型和打分函数进行打分;
  3. 获得每个对打分,并完成排序。

值得注意的是,目前使用比较多的XGBoost ranking模型是LambdaRank,但尚未完成,参考dmlc/xgboost .

代码示例

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
import os,sys,json
import math
import random
import numpy as np
import pandas as pd
import sklearn.utils
import xgboost as xgb
enableFeatures = [
"fea1",
"fea2"
]
train_data = pd.read_csv("train.csv", sep="\t")
test_data = pd.read_csv("test.csv", sep="\t")
print("all data {0}".format(train_data.shape))
print("all data {0}".format(test_data.shape))
# 分组处理数据
traingroups = {}
validgroups = {}
for qid, df in list(train_data.groupby("group_id")):
group = traingroups.setdefault(qid, {})
group["length"] = len(df)
group["weight"] = 1
group["df"] = df
for qid, df in list(test_data.groupby("group_id")):
group = validgroups.setdefault(qid, {})
group["length"] = len(df)
group["weight"] = 1
group["df"] = df
print("groups")
traingroups = [group for qid, group in traingroups.items() ]
validgroups = [group for qid, group in validgroups.items() ]
print("concat")
train_X = pd.concat(map(lambda x: sklearn.utils.shuffle(x["df"]), traingroups), ignore_index=True)
valid_X = pd.concat(map(lambda x: sklearn.utils.shuffle(x["df"]), validgroups), ignore_index=True)
train_y = train_X["label"]
valid_y = valid_X["label"]
train_X = train_X[enableFeatures]
valid_X = valid_X[enableFeatures]
train_X, valid_X = train_X.align(valid_X, join="left", axis=1)
print("data length weight")
train_q = np.array(list(map(lambda x: x["length"], traingroups)))
valid_q = np.array(list(map(lambda x: x["length"], validgroups)))
train_w = np.array(list(map(lambda x: x["weight"], traingroups)))
valid_w = np.array(list(map(lambda x: x["weight"], validgroups)))
print("model train")
#"rank:ndcg"
ranker = xgb.XGBRanker(objective="rank:pairwise")
ranker.fit(train_X, train_y, train_q, sample_weight=train_w,
eval_set=[(valid_X, valid_y)], eval_group=[valid_q], sample_weight_eval_set=[valid_w],
eval_metric=["ndcg@5-", "ndcg@10-"], early_stopping_rounds=5, verbose=True,
callbacks=[xgb.callback.reset_learning_rate(lambda x,y: 0.95 ** x * 0.1)])
ranker.feature_names = map(str, train_X.columns)
with open("xgb_pair.model.features", "w") as fw:
fw.write( ",".join(ranker.feature_names))
ranker.save_model('xgb_pair.model')
model = xgb.Booster(model_file='xgb_pair.model')
print(ranker.get_booster().get_score(importance_type='gain') )

参考资料

用xgboost做排序任务——xgboost下的learning2rank
Learning to Rank系列之概述
Learning to Rank 概述