BT

如何利用碎片时间提升技术认知与能力? 点击获取答案

1号店11.11:机器排序学习在电商搜索中的实战

| 作者 张志浩 关注 0 他的粉丝 发布于 2016年11月11日. 估计阅读时间: 26 分钟 | CNUTCon 了解国内外一线大厂50+智能运维最新实践案例。

本次11.11策划,我们邀请了1号店来分享他们关于电商搜索的经验,另外,在本次ArchSummit全球架构师峰会北京站,设置了《电商专题:系统架构如何应对业务爆发式增长》《阿里双11技术架构突破》专题,来深入解读双11等大促背后的技术故事,大会将于2016年12月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完成实际的排序。

图 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]。

图 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> 是注释项,不影响训练结果。

<target> qid:<qid> <feature>:<value> <feature>:<value> ... <feature>:<value> # <info>

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

图 3 - LambdaMART训练样本

3.3离线训练

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

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

图 4 - LambdaMART训练过程

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

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

       参数说明

-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的模型文件,该模型文件也就是可以用于生产环境的机器排序模型。

图 5 - LambdaMART训练产生的模型

        

3.4 离线评测

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

java -jar ~/bin/RankLib.jar -load ~/models/learned_lambdamart_model.mod -test ~/test_samples.csv -metric2T NDCG@60 -score ~/rerank_scores.txt

这里-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. 默认参数设置
  2. 在1的基础上调整tvs参数
  3. 在2的基础上调整leaf参数
  4. 在3的基础上调整tree和shrinkage参数

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

不同模型的指标对比如下,模型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是我们设置的不同流量分桶,用于观测不同分桶对模型的影响)

总结

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

参考文献

[1] https://en.wikipedia.org/wiki/Learning_to_rank

[2] https://sourceforge.net/p/lemur/wiki/RankLib/

[3] http://jmlr.org/proceedings/papers/v14/burges11a/burges11a.pdf

[4] http://research.microsoft.com/en-us/um/people/cburges/tech_reports/msr-tr-2010-82.pdf

[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

[6] https://class.coursera.org/ml-003/lecture/21

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我
社区评论

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT