分享

机器排序学习在电商搜索中的应用——1号店的搜索Ranking Model

fc013 发表于 2017-3-12 16:37:42 [显示全部楼层] 只看大图 回帖奖励 阅读模式 关闭右栏 2 8557


问题导读:

1.机器排序学习有哪些特点?
2.机器排序学习的整个过程是怎样的?
3.机器排序学习适用哪些系统?








背景

1号店的搜索Ranking Model一直在朝着精细化方向深化,我们希望在提升用户满意度的同时,也能提升网站的流量转化率。在实践机器排序学习之前,1号店网站的搜索Ranking Model已经经历了4个阶段:通用排序模型(Universal Ranking Model)、基于区域的排序模型(Region-based Ranking Model)、基于品类的排序模型(Category-based Ranking Model)和基于用户的排序模型(User-based Ranking Model)。

在这个过程中,需要对搜索、浏览、点击、购买,评论等几十个行为特征进行细粒度的分解和重组,这就需要人工去分析用户的搜索行为和流量效率之间的关系,并通过人工调整排序模型来优化效果。在细分了区域和品类之后,为了更有效地提升排序模型的优化效率,我们开始考虑使用机器排序学习算法。

机器排序学习的一般分为两个流程,其中“training data -> learning algorithm -> ranking model”是一个离线训练过程,包含数据清洗、特征抽取、模型训练和模型优化等环节。而“user query -> top-k retrieval -> ranking model -> results page”则是在线应用过程,表示利用离线训练得到的模型进行预估。

机器排序学习有如下优点:

  • 人工规则排序是通过构造排序函数,并通过不断的实验确定最佳的参数组合,以此形成排序规则对搜索结果进行排序。但是在数据量较大、排序特征较多的情况下,依靠人工很难充分发现数据中隐藏的信息,而机器排序则可以较好地解决这个问题;
  • 机器学习可以基于持续的数据反馈进行自我学习和迭代,不断地挖掘业务价值,对目标问题进行持续优化;

设计原则

从一开始,我们就没有考虑将机器排序学习作为人工规则排序的替代者,而是致力于将两者作为互为补充的排序模型,不同品类采用不同的排序策略,这也体现在了我们的搜索排序架构上。

图1表示目前1号店现在生产环境上机器排序学习的框架,包含两个部分:离线训练和在线应用。离线部分主要是根据历史数据以及训练目标,产生一个可用于在线预测的排序模型;而在线部分则是利用离线产生的排序模型,根据在线用户的Context完成实际的排序。

QQ20161111163757.jpg

图 1 - 机器排序学习框架

在整个机器排序框架中,整个在线排序模块分为3层。

第一层称为一排(也称为粗排),主要是根据用户Query从索引库中召回所有相关商品,然后依据文本相关性和类目相关性得分,完成第1轮商品筛选,形成上层排序模型的候选商品集;

第二层称为二排(也称为精排),主要是以一排的候选商品集为基础,应用LTR模型或者人工排序模型,完成基于排序特征的重新排序;

第三层称为三排,主要是根据各种商业需求对二排的排序结果进行调整,如类目打散、商品推广等;

在整个机器排序框架中,离线部分需要模型评测环境,而在线部分更需要数据收集模块和A/B Test模块。这两点并没有在图1的框架中列出,但是在后续的介绍中会给出相应的说明。

机器排序学习离线训练过程

我们选择开源的RankLib[2]作为机器排序学习的工具包。在离线训练过程中,我们测试了RankNet, LambdaMART和Random Forests,根据评测结果,我们选择了LambdaMART(具体采用哪种模型,需要根据实际业务场景和训练结果而定)。该算法是一种有监督学习(Supervised Learning)的迭代决策回归树排序算法,目前已经被广泛应用到数据挖掘的诸多领域。

LambdaMART模型可以分成Lambda和MART两部分,底层模型训练用的是MART(Multiple Additive Regression Tree),也叫GBDT(Gradient Boosting Decision Tree),它的核心是每一棵树学习的是之前所有树结论和的残差,这个残差+当前的预测值就能得到真实值。而Lambda是MART求解过程使用的梯度,其物理含义是一个待排序的文档下一次迭代应该排序的方向和强度。具体LambdaMART的算法和工作原理可以参考[4]。

下面我们以LambdaMART为基础算法来介绍机器排序学习的整个过程。

3.1 训练目标数据

离线训练目标数据的获取有2种方法,人工标注和点击日志。两者都是为了构建出<q, p, r-score>的数值pair对,作为机器学习的训练数据集。这里q表示用户的查询query,p表示通过q召回的商品product,r-score表示商品p在查询q条件下的相关性得分。

其中人工标注一般步骤为,根据给定的query商品对, 判断商品和query是否相关,以及相关强度。该强度值可以用数值序列来表示,常见的是用5档评分,如1-差,2-一般,3-好,4-优秀,5-完美。人工标注一方面是标注者的主观判断,会受标注者背景、爱好等因素的影响,另一方面,实际查询的query和相关商品数量比较多,所以全部靠人工标注工作量大,一般很少采用。

因此,在我们的实践探索中,寻找获取方便且具有代表性的相关性的度量指标则成为重中之重。经过初期的探索,我们确定以CTR为基础,实现了低成本的query-product相关性标注(虽然不完美,但在实际工程中切实可行)。具体步骤如下:从用户真实的搜索和点击日志中,挖掘出同一个query下,商品的排序位置以及在这个位置上的点击数,如query_1有3个排好序的商品a, b和c,但是b得到了更多的点击,那么b的相关性可能好于a。点击数据隐式地反映了相同query下搜索结果相关性的好坏。

在搭建相关性数据的过程中,需要避免“展示位置偏见”position bias现象,即在搜索结果中,排序靠前的结果被点击的概率会大于排序靠后的结果;在我们的训练模型中,如图2所示,第6位开始的商品点击数相比前5位有明显的下降,所以我们会直接去除搜索结果前5个商品的点击数[5]。


image002.png
图 2 – 位置偏见的示意图

同时在实际场景中,搜索日志也通常含有噪音,只有足够多的点击次数才能体现商品相关性的大小。因此为了提升训练效率和训练效果,我们也针对Click数少于某个阈值的情况(即少于某个阈值的点击,我们就直接忽略)进行了测试,分别为2,3,4,5,6,7,8。经过离线分析,在阈值为4的情况下,NDCG分别有20%-30%的提升(这是NDCG@60 on validation data和当前线上的NDCG相比),效果提升比较明显。

表格 1 - Click数对训练目标的影响
2
3
4
5
6
7
8
AverageOverlapScore
0.2779563
0.2622574
0.2927366
0.2605555
0.3292106
0.2570833
0.2815816
RBOScore
0.3660776
0.3278322
0.3587360
0.3362893
0.3906409
0.3456386
0.3614653
LikeNDCG1
3918.920
4529.955
4345.691
4550.222
3970.641
3555.782
3418.661
LikeNDCG2
203.5713
250.1454
235.3356
244.135
209.4407
217.9441
207.5903
NDCG@60 on training data
0.4734
0.4479
0.502
0.4846
0.4983
0.621
0.643
NDCG@60 on validation data
0.4896
0.4727
0.536
0.4743
0.4928
0.5015
0.4864

3.2 特征抽取
LTR使用的排序特征(也称为Feature),和人工规则排序使用的特征基本相同。按照数据特性的差异,我们将其分为2大类,如表1所示,当然不同类型的数据价值和反映用户意图的强弱也不尽相同。   

表格 2 - 特征抽取部分样例
Feature类别
Feature项
查询相关性特征
查询相关性
text relevance, category relevance
商品特征
商品静态特征
title, sub-title, attribute (brand, category, size, color, flavor)等
商品动态特征
price, promotion等
订单特征
sales volume by day/week/month, GMV by day/week/month等
行为特征
CTR (list->detail, detail->shopping)
售后特征
number of review, positive rate of review, complain rate, return rate等
商家服务特征
DSR, online duration, online instant response等

特征数据分几类或者怎么分类都不是重要问题,这里主要是说明要尽可能抽取多的特征数据,供后续训练使用。同时对于机器排序学习而言,这里的行为特征都需要跟踪到Query维度,所以在数据采集的时候,需要预先处理好,这样才能体现Query对应的排序影响。如果能将订单特征也区分到Query维度会更好,但是我们现在还没有做到这一点,以后还会继续实验。

除了商品静态特征以外,商品动态特征、订单特征、行为特征、售后特征、商家服务特征都需要细分到品类和区域,幸运的是,在人工规则的排序模型阶段,就已经为我们准备好了profile-based的特征数据。为了能在人工规则排序和机器排序学习之间共享这些特征数据,我们将这些特征数据存储在基于HBase的Item Feature Repository数据库中。目前这些特征数据还是以天为单位进行批处理,而非实时完成。   

在得到相关度数据和特征数据后,就可以根据LambdaMART训练数据的格式(如下所示),构建完整的训练数据集。每一行代表一个训练数据,项与项之间用空格分隔,其中<target>是相关性得分,<qid>是每个query的序号,<feature>是特征项的编号,<value>是对应特征项归一化后的数值,<info> 是注释项,不影响训练结果。

[mw_shl_code=text,true]<target> qid:<qid> <feature>:<value> <feature>:<value> ... <feature>:<value> # <info>
[/mw_shl_code]

图3表示项目中使用的实际训练数据(这里选取了其中10个特征作为示例,#后面可以增加Query和商品名称,方便分析时的查看):


image003.png
图 3 - LambdaMART训练样本

3.3离线训练
LambdaMART学习过程的主要步骤可以参考[4],数学推导不是本文的重点:

  • 先遍历所有的训练数据,计算每个pair互换位置导致的指标变化deltaNDCG以及lambda;
  • 创建回归树拟合第一步生成的lambda,生成一颗叶子节点数为L的回归树;
  • 对这棵树的每个叶子节点通过预测的regression lambda计算每个叶子节点的输出值;
  • 更新模型,将当前学习到的回归树加到已有的模型中,用学习率shrinkage系数做regularization;

1image004.png

图 4 - LambdaMART训练过程

RankLib提供了简单的命令行,只需根据实际的需要配置好参数,就可以实现训练模型、保存模型的功能。下面是我们在工程中使用的参数配置示例:

[mw_shl_code=shell,true]java -jar ~/bin/RankLib.jar -train ~/train_all.csv -gmax 4 -tvs 0.8 -norm zscore -ranker 6 -metric2t NDCG@60 -tree 1000 -leaf 10 -shrinkage 0.1 -save ~/models/learned_lambdamart_model.mod
[/mw_shl_code]

       参数说明

-train是必须的,表示训练样本所在的文件名;
-ranker是必须的,表示指定的机器学习算法,而6就是LambdaMART;
-gmax是可选的,指定训练目标相关性的最大等级,默认是4,代表5档评分,即{0,1,2,3,4};
-tvs是可选的,设置样本中用于训练的数据比例,即train数据:validation的比是0.8:0.2;
-norm是可选的,指定特征归一化的方法,默认没有归一化,zscore代表采用均方误差来归一化;
-metric2t是可选的,训练数据的评测方法,默认是ERR@10;
-tree是可选的,指定lambdamart使用的树的数目,默认是1000;
-leaf是可选的,指定lambdamart每棵树的叶节点数,默认是10;
-shrinkage是可选的,指定lambdamart的学习率,默认是0.1;
-save是可选的,用于保存模型;

上述命令执行结束后会在-save指定的目录下产生一个如图6的模型文件,该模型文件也就是可以用于生产环境的机器排序模型。

image005.png
图 5 - LambdaMART训练产生的模型


3.4 离线评测

在排序模型训练完成之后,我们需要准备与训练样本相同数据格式的离线测试样本,这个测试样本尽量选取和训练样本不同的数据集。

[mw_shl_code=shell,true]java -jar ~/bin/RankLib.jar -load ~/models/learned_lambdamart_model.mod -test ~/test_samples.csv -metric2T NDCG@60 -score ~/rerank_scores.txt
[/mw_shl_code]

这里-load对应的参数就是在离线训练中得到的排序模型,-test对应的参数就是测试样本集,-metric2T使用和训练过程相同的评价方式,-score对应的参数就是保存测试样本集中每个query下商品的得分。

【实验样本】为了离线测试LTR的模型效果,选择了两个流量差异较大的类目,暂且称为类目A和类目B,其中类目A的流量大约是类目B的40倍。同时选择不同平台、不同时间段内的数据作为训练样本。

【评测指标】除了使用评价排序效果的NDCG以外,出于商业因素的考虑,我们还选择了4个评价排序位置变动情况的指标,其中AverageOverlapScore和RBOScore指标越大表示正常排序和LTR排序越接近,LikeNDCG1和LikeNDCG2指标越小表示正常排序和LTR排序越接近。

表格 3 - 类目A的离线评测效果
类目
A
训练数据平台
PC
PC + IOS + ANDROID
PC
PC
PC
训练数据时间段
一周
一周
两周
一周
一周
NDCG@60
on training data
0.5617
0.5365
0.5313
0.5253
0.5778
NDCG@60
on validation data
0.5391
0.5411
0.5605
0.5138
0.5372
AverageOverlapScore
0.3535
0.3751
0.3710
0.4254
0.3442
RBOScore
0.4236
0.42823
0.4306
0.4591
0.4005
LikeNDCG1
3001.8343
2997.8116
2957.3804
3591.0862
3108.4491
LikeNDCG2
148.5160
147.1333
141.9098
176.5259
156.8397

表格 4 - 类目B的离线评测效果
类目
B
训练数据平台
PC
PC + IOS + ANDROID
PC
PC
PC + IOS + ANDROID
训练数据时间段
一周
一周
两周
一周
一周
NDCG@60
on training data
0.6834
0.4882
0.6148
0.7887
0.4955
NDCG@60
on validation data
0.5193
0.5356
0.5549
0.5522
0.5042
AverageOverlapScore
0.2273
0.3438
0.3100
0.2207
0.1965
RBOScore
0.2597
0.3636
0.3495
0.2573
0.2344
LikeNDCG1
3166.5950
2765.4566
2022.0802
3202.8392
3142.5835
LikeNDCG2
208.9072
156.8297
110.9762
201.1636
188.5675

可以看出,同样用一周的数据,PC+IOS+Android的评测效果在多个指标上要好于只用PC的效果;而同样在PC端,两周数据的评测效果也好于一周;但是这个结论并不是普遍性,对于不同类目,需要具体问题具体分析,进而确定表现较好的模型。   

另外,为了验证LambdaMART的不同训练参数对预测效率和预测效果的差异,我们也进行了其它4组实验,分别是如下:

  • 默认参数设置
  • 在1的基础上调整tvs参数
  • 在2的基础上调整leaf参数
  • 在3的基础上调整tree和shrinkage参数

4个模型的排序结果如下图所示,其中横坐标PO1表示线上排序1-8,PO2表示线上排序9-16,纵坐标表示这8个位置与LTR排序下商品位置变动数量。

image006.png

image007.png

image008.png


1image009.png


不同模型的指标对比如下,模型2的4个指标均为最佳。

表格 5 - 不同训练参数对训练结果的影响
模型
AverageOverlapScore
RBOScore
LikeNDCG1
LikeNDCG2
1
0.54369
0.580978
4739.148
189.846
2
0.67377
0.669086
4089.201
162.9705
3
0.574048
0.59842
4874.85
194.454
4
0.629045
0.64889
4186.75
166.738

综合LambdaMART在Training Data和Validation Data的迭代次数和训练时间来看,随着参数的增加,训练时间和迭代次数都有增加;但是当去除噪音Click的数据后,训练时间和迭代次数有明显的降低。

在线应用
【模型加载】离线测评时,可以用命令行的方式加载模型,读取数据文件,进而测试模型性能。显然这种方式并不适合在线应用,因此我们需要提取RankLib加载模型和在线打分的代码。为了有效进行系统地管理,我们将模型文件统一存放在MySQL表中,并利用字段区分类目和平台等信息。

【在线测试】为了排除用户固有行为特性的影响,从而更加准确地比较LTR排序和人工排序的各项指标,在进行A/B Test之前,我们首先进行了一段时间的AA测试,从而选出各项指标较为接近的桶,再比较这些桶在LTR排序和人工排序之间差异。

将训练后的LTR模型按照图2的框架应用到生产环境中,在整个测试期间,我们观察了不同时间周期、不同平台数据产生的多个模型。总体来讲,LTR模型对“搜索导航页到商详页的CTR”在2016年11.11活动期间有约8.7%的提升,并且“订单转化率”在11.11活动期间有约4.5%的提升。(其中LTR_1和LTR_2是我们设置的不同流量分桶,用于观测不同分桶对模型的影响)

image010.gif

总结
总的来说,人工规则与机器排序是紧密结合的。如果排序的量化目标不太明确,则人工规则就更适合。电商搜索不仅要考虑查询相关性,还要考虑销售额和订单转化率,因此电商搜索往往有较多的业务规则。如eBay和Google在搜索排序方面就结合了人工业务规则,而广告排序一般更依赖于机器排序,因为其优化目标比较明确。所以我们也会在当前成果的的基础上,将机器排序学习进一步应用到推荐和广告系统上。

参考文献

[5] An experimental comparison of click position-bias models. In Proceedings of the 2008 International Conference on Web Search and Data Mining (pp. 87-94). ACM





来源:zybuluo
作者:hanbingtao

本帖被以下淘专辑推荐:

已有(2)人评论

跳转到指定楼层
yangelar 发表于 2017-3-13 10:14:04
赞啊  很不错
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

推荐上一条 /2 下一条