写点什么

阿里提出电商搜索全局排序方法,淘宝无线主搜 GMV 提升 5%

2018 年 6 月 15 日

1. 前言

搜索排序的传统方法是通过各种方法对商品进行打分,最后按照每个商品的分数进行排序。这样传统的搜索排序方法就无 法考虑到展示出来的商品之间相互的影响。类似地,传统的针对单个商品估计 ctr、cvr 的方法也都基于这样一个假设:商品 的 ctr、cvr不会受到同时展示出来的其他商品 (我们称为展示 context) 的影响。而实际上一个商品的展示 context 可以影响到 用户的点击或者购买决策:假如一个商品周边的商品都和它比较类似,但是价格却比它便宜,那么用户买它的概率不会 高;反之如果周边的商品都比它贵,那么用户买它的概率就会大增。

如果打破传统排序模型展示 context 没有影响的假设,该如何进行排序呢?为此,我们首次提出了一种考虑商品间相互影响的全局排序方法。我们将电商排序描述成一个全局优化问题,优化的目标是反应用户满意度的商品成交额:GMV(Gross Merchandise Volume)。准确地说,全局排序的优化目标是最大化 GMV 的数学期望。计算 GMV 的数学期望需要知道商品 的成交概率,而商品的成交概率是彼此相互影响的,因此我们又提出了考虑商品间相互影响的成交概率估计模型。

首先, 我们提出了一种全局特征扩展的思路,在估计一个商品的成交概率时,将其他商品的影响以全局特征的形式加入到概率估 计模型中,从而在估计时考虑到了其他商品的影响。然后,我们进一步提出了通过 RNN 模型来精确考虑商品的排序顺序对 商品成交概率的影响。通过使用 RNN 模型,我们将电商排序变成了一个序列生成的问题,并通过 beam search 算法来寻找 一个较好的排序。我们在淘宝无线主搜索平台上进行了大量的实验,相对于当时的淘宝无线主搜算法,取得了GMV 提升 5% 的效果。

2. 全局排序方法

全局排序阶段的输入是要排序的 N 个商品,输出则是 N 商品的排序结果。

我们用 S = (1, … , N) 表示基础排序输出的 top‑N 商品序列;O 表示 S 的全排列集合,o = (o1, … , oN ) ∈ O 表示 S 的一个排列;另外,用 di 表示商品 i 在排序 o 中的位置,即 odi = i;c(o, i) 表示商品 i 在排序 o 中的展示 contex 全局排序 t,具体定义后面会分情况讨论;

v(i) 表示商品 i 的价值。

我们将目标定义为本次搜索产生的 GMV,于是在给定 c(o, i) 的情况下,就有:

全局排序的最终目标就是找到一个期望收益最大的排序:

寻找这个最优排序需要解决两个问题:

  • 问题 1. p(i|c(o, i)) 这个概率如何去准确地估计;
  • 问题 2. 寻找 o∗是个组合优化的问题,暴力搜索的时间复杂度是 N! 的,需要找到合理高效的近似算法。

问题 1 是提高效果的关键,估计得越准,后面组合优化的效果越明显,反之则会导致第二步的组合优化没有意义。从理论上讲,c(o, i) = (o1, … , oN ) 是 i 的完整的展示 context,但是如果完整地考虑展示 context,问题 2 的组合优化复杂度很难降低下来。为了能更高效求解问题 2,需要对 c(o, i) 进行适当地简化。根据对 c(o, i) 的简化程度,我们把全局排序模型分成了两类,分别在下面介绍。

2.1 全局特征扩展

电商搜索全局排序方法

第一类模型只利用展示 context 的商品集合信息,而不去深究真实的展示 context 的顺序,即 c(o, i) = S ∖ {i}。直观上理解,第一类模型假设用户在判断是否购买商品 i 的时候,只记得他看过所有的商品集合 S,而不在意 S 中商品的出现顺序。

这种情况相当于用户知道自己的挑选集合,从中比较和挑选出最想购买的商品。我们将商品 i 本身的特征成为局部特征 fi,l。这时可以把商品 i 的局部特征 fi,l 与其他候选商品的局部特征进行比较,得到这个商品的特征与候选集合其他商品比较的结果,并且把这些比较的结果作为包含全局信息的特征加入到 p(i|c(o, i)) 的预测中。

以价格特征为例,我们会按照价格纬度对 S 排序,将商品 i 的价格位次均匀地归一化成 [0, 1] 之间的一个值(最贵的价格变成变成 1,最便宜的价格变成 0),这样 i 的价格特征就扩展出了i 的价格全局特征。

通过上述的方式可以对 fi,l 的每一维按照其位次扩展,得到相应的全局特征 fi,g,最终我们将局部和全局特征拼接起来作为考虑了展示 context 的商品 i 的特征 fi = (fi,l, fi,g)。这时展示 context 通过特征扩展而加入到模型中来,帮助模型预测成交概率 p(i|c(o, i))。

在第一类模型的假设下,问题 2 的组合优化就变得很简单了。商品集合是静态的,因此各个商品的成交概率能分别独立计算出来。

但是 DNN 计算出的 p(i|c(o, i)) 没有考虑到商品 i 的排序位次,应该根据根据 position bias 对 p(i|c(o, i)) 做一个修正,即 p(i|c(o, i))bias(di)。对于求解问题 2 来说,我们不需要具体知道 bias(di) 的值,只需要知道 bias 随着位置从前往后依次降低就可以了,因为这时只要按照 v(i)p(i|c(o, i)) 从高到低对商品进行排序,就一定能得到收益最大的排序。

2.2 排序序列生成

第二类模型不仅仅考虑展示 context 的商品集合信息,还精确地考虑到排在 i 之前的商品的顺序。与第一类模型类似,展示 context 的商品集合信息还是通过扩展全局特征的方式加入到了每个商品的特征中,即 fi = (fi,l, fi,g)。但是与第一类模型不同,计算 p(i|c(o, i)) 时,第二类模型还考虑了排在 i 前面的真实顺序,即 p(i|c(o, i)) = p(i|o1, o2, . . . , odi−1),这样问题 1 变成了一个序列概率估计的问题,最直观的方法就是用 RNN 来计算 p(i|c(o, i))。

与第一类模型不同的是,由于我们考虑了排在 i 之前的商品的顺序,前面商品的排序变化会影响商品 i 的成交概率。这时就不能分别独立计算每个商品的收益了,因为商品 i 的收益要受到排在它前面的商品的影响;而在最终排序确定之前,无法知道商品 i 之前的排序是什么,而且我们的目标就是去确定这样一个最优的排序。同时,正是因为只考虑了排在 i 之前的商品顺序,使得我们可以从前往后一步一步地排序,每一步选择排在当前位置的商品。

为了便于理解,可以先看一种简单的情况:分位排序。

所谓分位排序是指在排序时先将收益最大的一个商品排到第一位,然后条件在第一个商品之上,重新计算剩余商品的收益,并选出收益最大的商品排到第二位,依次类推。很明显分位排序是一种贪婪的算法。beam search 算法可以理解为贪婪算法的扩展,beam search 在每一步搜索的时候会保留收益最大的 k 个序列,一直到最后一步,再返回最好的一个序列。

原始的 RNN 模型解决不好长距离依赖的问题:当我们计算第 20 个位置的商品成交概率时,排在头 4 位的商品几乎就没有任何影响了。而排在前面的商品由于是用户最先看到的,一般会有较深的印象,对后面商品的影响不应该被忽略。为了使模型有能力考虑到长距离和对排序位置的依赖,我们设计了一种新的 attention 机制加入到 RNN 的网络中。

通过这种引入 attention 并且加入位置 embedding 的方式,模型可以根据数据自动学习不同位置 attention 该如何调节以得到更好的预测结果。直观来看,模型的结构图如下:

3. 实验效果

3.1 成交概率估计

其中 DNN 是只使用 fi,l 作为特征的 baseline。reDNN 是使用全局特征 fi = (fi,l, fi,g) 的 DNN 全局排序模型,miRNN 是 RNN 全局排序模型,miRNN+attention 是增加了我们的 attention 机制的 RNN 模型。

3.2 淘宝无线主搜线上 A/B 测试

使用 miRNN 和 miRNN + attention 模型做排序,算法的时间分别是Θ(kN 2) 和Θ(kN 3),其中 N 是被排序的商品数,k 是 beam search 算法的 beam size 参数。对于淘宝搜索这样的大规模的搜索平台来说,这样的复杂度显然是太高了。

不过我们可以在 baseline 排序的基础上,只对排在最前面的 N 个商品进行排序,只要 N 取得不大,计算量就是可以承担的。同时,因为排在前面的商品对效果的影响最大,对这些商品重新排序的收益也比较大。

我们对比了不同 N 和 k 下,本文提出的各种全局排序方法的 GMV 增长(反应模型效果),搜索引擎 latency(反应计算负担)的增长曲线:

最终效果总结:GMV、搜索引擎 Latency 想对于 baseline DNN 的增长:

结论

我们首次提出了考虑商品间相互影响的电商全局排序方法,并在淘宝主搜索上取得了明显的效果。目前最大的问题就是 RNN 的方法效果虽然更好一些,但是带来的计算负担太大,如何减少计算量将是重要的研究方向。

2018 年 6 月 15 日 16:189687

评论

发布
暂无评论
发现更多内容

《重学 Java 设计模式》PDF 出炉了 - 小傅哥,肝了50天写出18万字271页的实战编程资料

小傅哥

Java 设计模式 小傅哥 重构 代码质量

设计模式(1)—什么是设计模式?设计模式的六大原则是什么?

爱嘤嘤嘤斯坦

Java 程序员 编程语言 设计模式 23种设计模式

看动画学算法之:排序-插入排序

程序那些事

Java 数据结构 算法 插入排序

第6周-作业2-总结

seng man

负载均衡方式

羽球

负载均衡

智慧4S店解决方案发布,看英特尔如何引领汽车销售行业变革

最新动态

CAP原理简述

刘志刚

SpringBoot 入门:03 - 统一请求返回

封不羁

Java spring springboot

Spring5-Reactor函数式编程

小技术君

spring reactor Spring5 springboot

进程、线程基础知识全家桶,30 张图一套带走

小林coding

Linux 操作系统 计算机基础 进程 进程线程区别

简述CAP理论

lei Shi

ARTS打卡 第7周

引花眠

ARTS 打卡计划

抽象工厂模式

Leetao

Python 面试 设计模式

设计模式六大原则

刘志刚

设计原则

分布式系统设计理念这么难学?

架构师修行之路

架构 分布式

程序的机器级表示-程序的编码

引花眠

计算机基础

Cache解决算法 Charles断点调试breakpoint John 易筋 ARTS 打卡 Week 08

John(易筋)

ARTS 打卡计划

MySQL实战45讲总结

`

MySQL

第6周-作业1

seng man

ARTS打卡-06

Geek_yansheng25

低代码与无代码

lidaobing

低代码 无代码开发

ARTS打卡 - Week 07

teoking

redis系列之——高可用(主从、哨兵、集群)

诸葛小猿

redis redis集群 redis哨兵 redis主从

Go:Stringer命令,通过代码生成提高效率

陈思敏捷

go golang stringer

时间去哪了?

escray

自动化测试首先是一种工作文化

wangwei1237

自动化测试 测试文化

人人都需要一份自己的「使用说明书」

非著名程序员

程序员 程序人生 提升认知 独立思考 自我思考

编程核心能力之抽象

顿晓

抽象 编程日课

ARTS WEEK5

紫枫

ARTS 打卡计划

数据驱动 vs 关键字驱动:对UI自动化测试框架搭建的探索

Winfield

DevOps 敏捷 自动化测试

Mysql插入百万条数据

Java小咖秀

MySQL 运维 数据

2021年全国大学生计算机系统能力大赛操作系统设计赛 技术报告会

2021年全国大学生计算机系统能力大赛操作系统设计赛 技术报告会

阿里提出电商搜索全局排序方法,淘宝无线主搜GMV提升5%-InfoQ