小叽导读：搜索排序的传统方法是通过各种方法对商品进行打分，最后按照每个商品的分数进行排序。
针对传统搜索排序方法的缺陷，本文首次提出了考虑商品间相互影响的全局排序方法。本篇内容已被国际人工智能联合会议（IJCAI）收录，下面，我们一起来共同探讨。
1、前言
传统的搜索排序方法无法考虑到展示出来的商品之间相互的影响。类似地，传统的针对单个商品估计ctr、cvr的方法也都基于这样一个假设：商品的ctr、cvr不会受到同时展示出来的其他商品(我们称为展示context)的影响。而实际上一个商品的展示context可以影响到用户的点击或者购买决策：假如一个商品周边的商品都和它比较类似，但是价格却比它便宜，那么用户买它的概率不会高；反之如果周边的商品都比它贵，那么用户买它的概率就会大增。
如果打破传统排序模型展示context没有影响的假设，该如何进行排序呢？为此，我们首次提出了一种考虑商品间相互影响的全局排序方法。我们将电商排序描述成一个全局优化问题，优化的目标是反应用户满意度的商品成交额：GMV（Gross Merchandise Volume）。准确地说，全局排序的优化目标是最大化GMV的数学期望。计算GMV的数学期望需要知道商品的成交概率，而商品的成交概率是彼此相互影响的，因此我们又提出了考虑商品间相互影响的成交概率估计模型。
首先，我们提出了一种全局特征扩展的思路，在估计一个商品的成交概率时，将其他商品的影响以全局特征的形式加入到概率估计模型中，从而在估计时考虑到了其他商品的影响。然后，我们进一步提出了通过RNN模型来精确考虑商品的排序顺序对商品成交概率的影响。通过使用RNN模型，我们将电商排序变成了一个序列生成的问题，并通过beam search算法来寻找一个较好的排序。我们在淘宝无线主搜索平台上进行了大量的实验，相对于当时的淘宝无线主搜算法，取得了GMV提升5%的效果。
▌2、全局排序方法
全局排序阶段的输入是要排序的N个商品，输出则是N商品的排序结果。
我们
用表示基础排序输出的top‑N商品序列；O表示S的全排列集合，
表示S的一个排列；另外，用
表示商品i在排序o中的位置，即
；
表示商品i在排序o中的展示context，具体定义后面会分情况讨论；
表示商品的价值。
我们将目标定义为本次搜索产生的GMV，于是在给定o的情况下，就有
全局排序的最终目标就是找到一个期望收益最大的排序：
寻找这个最优排序需要解决两个问题：
问题1.
这个概率如何去准确地估计；
问题2. 寻找
是个组合优化的问题，暴力搜索的时间复杂度是N!的，需要找到合理高效的近似算法。
问题1是提高效果的关键，估计得越准，后面组合优化的效果越明显，反之则会导致第二步的组合优化没有意义。
从理论上讲，
是i的完整的展示context，但是如果完整地考虑展示context，问题2的组合优化复杂度很难降低下来。为了能更高效求解问题2，需要对
进行适当地简化。根据对的简化程度，我们把全局排序模型分成了两类，分别在下面介绍。
2.1 全局特征扩展
第一类模型只利用展示context的商品集合信息，而不去深究真实的展示context的顺序，即
。直观上理解，第一类模型假设用户在判断是否购买商品i的时候，只记得他看过所有的商品集合S，而不在意S中商品的出现顺序。
这种情况相当于用户知道自己的挑选集合，从中比较和挑选出最想购买的商品。我们将商品i本身的特征成为局部特征
。这时可以把商品i的局部特征与其他候选商品的局部特征进行比较，得到这个商品的特征与候选集合其他商品比较的结果，并且把这些比较的结果作为包含全局信息的特征加入到的
预测中。
以价格特征为例，我们会按照价格纬度对S排序，将商品i的价格位次均匀地归一化成
之间的一个值（最贵的价格变成变成1，最便宜的价格变成0），这样的价格特征就扩展出了i的价格全局特征。
通过上述的方式可以对的每一维按照其位次扩展，得到相应的全局特征
，最终我们将局部和全局特征拼接起来作为考虑了展示context的商品i的特征。这时展示context通过特征扩展而加入到模型中来，帮助模型预测成交概率
。
在第一类模型的假设下，问题2的组合优化就变得很简单了。商品集合是静态的，因此各个商品的成交概率能分别独立计算出来。但是DNN计算出的
没有考虑到商品i的排序位次，应该根据position bias对做一个修正，即
。对于求解问题2来说，我们不需要具体知道
的值，只需要知道bias随着位置从前往后依次降低就可以了，因为这时只要按照
从高到低对商品进行排序，就一定能得到收益最大的排序。
2.2 排序序列生成
第二类模型不仅仅考虑展示context的商品集合信息，还精确地考虑到排在i之前的商品的顺序。与第一类模型类似，展示context的商品集合信息还是通过扩展全局特征的方式加入到了每个商品的特征中，即
。但是与第一类模型不同，计算
时，第二类模型还考虑了排在i前面的真实顺序，即
，这样问题1变成了一个序列概率估计的问题，最直观的方法就是用RNN来计算
。
与第一类模型不同的是，由于我们考虑了排在i之前的商品的顺序，前面商品的排序变化会影响商品的成交概率。这时就不能分别独立计算每个商品的收益了，因为商品i的收益要受到排在它前面的商品的影响；而在最终排序确定之前，无法知道商品i之前的排序是什么，而且我们的目标就是去确定这样一个最优的排序。同时，正是因为只考虑了排在i之前的商品顺序，使得我们可以从前往后一步一步地排序，每一步选择排在当前位置的商品。
为了便于理解，可以先看一种简单的情况：分位排序。所谓分位排序是指在排序时先将收益最大的一个商品排到第一位，然后条件在第一个商品之上，重新计算剩余商品的收益，并选出收益最大的商品排到第二位，依次类推。很明显分位排序是一种贪婪的算法。beam search算法可以理解为贪婪算法的扩展,beam search在每一步搜索的时候会保留收益最大的个序列，一直到最后一步，再返回最好的一个序列。
原始的RNN模型解决不好长距离依赖的问题：当我们计算第20个位置的商品成交概率时，排在头4位的商品几乎就没有任何影响了。而排在前面的商品由于是用户最先看到的，一般会有较深的印象，对后面商品的影响不应该被忽略。为了使模型有能力考虑到长距离和对排序位置的依赖，我们设计了一种新的attention机制加入到RNN的网络中。通过这种引入attention并且加入位置embedding的方式，模型可以根据数据自动学习不同位置attention该如何调节以得到更好的预测结果。直观来看，模型的结构图如下：
▌3、实验效果
3.1 成交概率估计
其中DNN是只使用
作为特征的baseline。reDNN是使用全局特征
的DNN全局排序模型，miRNN是RNN全局排序模型，miRNN+attention是增加了我们的attention机制的RNN模型。
3.2 淘宝无线主搜线上A/B测试
使用miRNN和miRNN + attention模型做排序，算法的时间分别是
和
，其中是被排序的商品数， 是beam search算法的beam size参数。对于淘宝搜索这样的大规模的搜索平台来说，这样的复杂度显然是太高了。不过我们可以在baseline排序的基础上，只对排在最前面的N个商品进行排序，只要N取得不大，计算量就是可以承担的。同时，因为排在前面的商品对效果的影响最大，对这些商品重新排序的收益也比较大。
我们对比了不同N和k下，本文提出的各种全局排序方法的GMV增长（反应模型效果），搜索引擎latency（反应计算负担）的增长曲线：
最终效果总结：GMV、搜索引擎Latency想对于baseline DNN的增长：
▌4、结论
我们首次提出了考虑商品间相互影响的电商全局排序方法，并在淘宝主搜索上取得了明显的效果。目前最大的问题就是RNN的方法效果虽然更好一些，但是带来的计算负担太大，如何减少计算量将是重要的研究方向。
原文发布时间为：2018-07-11
本文作者：瑞溪
本文来自云栖社区合作伙伴“ 阿里技术”，了解相关信息可以关注“ 阿里技术”。
