Airbnb搜索：重排序阶段如何优化搜索结果多样性？
本文将基于Airbnb KDD 2020年的论文，介绍Airbnb搜索排序中在重排序阶段如何解决多样性的问题，对工业界搜索推荐系统优化多样性，具有很好的指导与借鉴意义。
论文链接：
arxiv.org/abs/2004.02621v1
搜索推荐系统中的多样性问题
在互联网APP中，诸如电商（淘宝、京东、拼多多）、信息流（头条、微博、百度）、短视频（抖音、快手、微信视频号）等，搜索推荐的多样性对优化点击转化效率、用户体验、浏览深度、停留时长、回访、留存等目标至关重要。
比如，淘宝'猜你喜欢”信息流会为用户推荐多个类目的宝贝、短视频、直播、文章等，来吸引用户停留：
在Airbnb中搜索系统中，搜索结果的多样性，主要体现在房间类型、位置、价格信息等方面：
深度学习精排阶段的排序模型，泛化能力比较好，一般相似的物品精排分数也比较接近。如果直接用精排分数排序展示结果，会导致排名靠前的结果非常类似，容易造成视觉疲劳，给兴趣宽泛、单纯逛逛、需求不明确的用户带来很差的体验。
下图展示了Airbnb实际的搜索结果。可以发现，排序靠前的listing（即item，民宿房间），其价格、位置差别通常非常小。
在召回阶段，通过多路召回（item2item, 向量召回等）方式，召回和用户最近点击相似相关的物品、热门物品等，一般有几千到几万，保证效率、丰富、多样性。
粗排阶段，通过简化的精排模型，对大量召回物品打分，返回几千个物品。
在精排阶段，用更复杂的深度排序模型等对这些物品打分。
最后，在重排序阶段，对综合考虑点击率、转化率、价格、多样性等信息，对物品计算新的排序分数，最后展示给用户。
重排序阶段，多样性的优化方面，工业界搜索推荐系统实用的代表性方法，包括 MMR （Maximal Marginal Relevance）[1], Google Youtube和Hulu视频推荐中的DPP（Determinantal Point Process）[2,3]，阿里电商推荐中基于Transformer的PRM [4]，Google Youtube基于强化学习的模型SlateQ [5]等。Airbnb的搜索系统，主要包括：召回、精排（Base Ranking Model）、重排（Second Stage Ranker），这篇论文主要介绍Airbnb搜索在重排序阶段如何优化多样性问题。
多样性指标
在多样性问题中，最基础的问题是定义衡量多样性的指标。
MMR：Maximal Marginal Relevance
经典的MMR方法，定义如下：
其中 是搜索查询 , 是候选的相关物品（例如精排后的结果）， 是MMR算法已经选取的物品， 用来衡量物品 和 的相似度, 用来衡量物品间的相似度, 是平衡相关度（例如CTR）和多样性的超参数（在Aribnb中通过实验分析，值设定为0.15）。公式中 建模了当前候选的物品 和搜索 的相似度，部分表示当前候选的物品 和搜索已经选取的物品的最大相似度。MMR算法的思想是：采取贪心策略，生成top K结果列表。第一次，先选取相关度最高的物品。然后，每次选取和查询 query 匹配度高、和已经选取的物品最大相似度低的物品。相似度函数 和 可以不同，根据业务需求来定。例如，在Airbnb搜索系统中，函数可以基于listing间价格、位置、类型等信息来计算。
MLR：Mean Listing Relevance
这篇论文里，作者提出了MLR指标，用来衡量一个top N列表结果的相关性、多样性综合得分，定义如下：
可以看到MLR和MRR方法中定义的指标相比，把MRR指标中的最大值函数替换成了平均值函数，距离函数取代了相似度函数 （所以没有了负号）。这样做的动机是：MMR中的最大值函数，隐藏假设用户仅对每个类目中的一个item感兴趣；MLR中使用平均值函数，更加平滑，能更好地建模Airbnb中用户的广泛偏好。
Listing的向量表示
本文中，作者使用的是将listing人工定义为一个可解释的向量，由listing的属性来表示，例如价格，位置（经度，纬度），容纳人数，房间类型等。对于实数值属性，基于query结果集合中的数据（而非全部数据）计算均值、方差，做normlization。对于类别属性，使用one-hot encoding。对处理后的listing向量通过TSNE聚类，结果如下图所示，可以看到：这种表示聚类效果很好，对房间类型、价格、位置等信息有比较好的区分度。
基于多样性分布的距离计算
通过计算生成的top K结果的多样性分布和理想的多样性分布之间的Hellinger距离，来衡量top K结果多样性的好坏。其中Hellinger距离的定义如下图所示，反映了向量每个维度值的差别。
关键的问题是，对于每个query，理想的多样性分布如何计算呢？论文作者巧妙了利用了用户的反馈(user engagement, 例如点击、预定等)来计算。下面通过位置、价格两个例子来说明。
1. 位置多样性
在位置多样性方面，对于每个query，理想的多样性向量分布，基于这个query下用户的反馈信息来计算。论文作者用经典的KD-Tree结构来将每个地理位置，然后计算每个地理位置下用户反馈的分布，从而得到对于这个query的理想的地理位置多样性分布。下图是一个用户反馈在位置上分布的例子：
2. 价格多样性
对于价格多样性，作者选用了多个价格bucket的正态分布，如下图所示。基本的思想是：对于每个query, 返回多个价格区间的结果，让用户有更多的选择；同时，让结果以这个query的expected price (期望价格）为中心。
那么，每个query下的expected price如何计算呢？作者采用的方法是使用简单的回归模型。其特质为：基于query中的特征，例如客户人数、住几夜、地点等，标签数据：基于历史预定的实际价格来计算。
优化多样性方法
在Airbnb重排序系统中，采用过几种解决方案，从精排后的N个结果，来生成top T的重排序结果，展示给用户。
基于Greedy Ranker的重排序
最大化Mean Listing Relevance指标，是一个NP-Hard问题。所以Airbnb首先使用了贪心的方法，基于Maximal Marginal Relevance（MMR）算法，利用的是论文中定义的Mean Listing Relevance指标，每次选取能使添加这个item后整个结果列表得分最高的那个item (即Airbnb中的listing)。
基于Location Diversity Ranker的重排序
该方法是基于模拟退火的优化优化位置多样性的重排序方法，同时考虑多样性和相关性的损失函数为：
其中， 以精排阶段分数作为ground truth label, 来衡量重排序结果和精排结果的偏差，表示重排结果的相关性得分； 用重排序结果和理想地理分布的距离，表示重排结果的多样性得分。然而标准的优化方法（如SGD）并不能直接优化这个定义的损失函数，因为地理位置表示的映射是固定的。所以，作者采用了基于模拟退火的方法：多次迭代，每次迭代通过交换重排序结果列表中两个item的位置生成新的结果，如果指标增加，选取这个新的结果，否则以一定的概率来接受新结果。
基于Combined Loss Function的重排序
但是，直接使用Hellinger距离作为loss function是不可行的：因为每个listing对应的bucket是常数，和DNN的权重没有直接依赖，所以无法用SGD优化。因此，作者提出了一个巧妙的surrogate cross entropy loss function来解决这个问题。即对于每个bucket，可以用一个binary label来表示这个bucket的分布值是否低于目标值。对于每个listing —— cross entropy loss的权重和该bucket的分布值与目标值的差值成正比。如果一个listing对应到某个bucket, 这个bucket上的值超过了理想值，重排序网络权重就会调整来减少这个listing的得分，使得这个listing排名到top T以外，bucket上的值进而就会接近理想值。
Contextual features
用户实际的反馈有时会与上下文（context）相关，作者加入了一些上下文特征，例如目标位置空闲房子数量，query对应的top K结果的价格、位置、房间类型、可容纳客人数的平均值和方差等信息。
基于Query Context Embedding的重排序
为了使用深度学习更好地建模query context信息，作者借鉴 DLCM [6]中的方法，使用RNN来建模当前query对应的精排结果的top结果，表示为listwise context，用这个信息来重排所有的item。具体方法如下：
对于listing L, query Q, user U, 首先使用精排排序模型打分，生成top T结果；然后选取精排的top N结果输入到LSTM中，得到Query Context Embedding；接着用重排序DNN模型H，基于Query Context Embedding对精排的top K个listing打分，生成重排结果。重排序模型H的结构，是基于RNN+Two Tower模型 [7]。首先，作者基于下面的网络，计算Query Context Embedding: 左下方的LSTM，输入精排的top N结果；右下方的DNN，输入user和query特征；然后将LSTM的最后输出和query/user侧DNN输出拼接后，经过投影层变换，输出为Query Context Embedding，用来表示理想的listing embedding。然后，作者用下面的网络结构对listing进行重排序打分。
相关性loss function ：作者用Query Context Embedding （即理想listing embedding）和 待排序的listing embedding间的euclidean距离来衡量待排序listing的好坏，进而计算总体loss中pair-wise loss，即相关性损失。重排序模型的结构、损失函数都已经定义清楚了，接下来就可以使用梯度下降优化重排序模型了。
实验结果
Offline A/B test
不同方法在offline A/B test上的结果如下图所示。其中，baseline为只使用精排模型直接展示结果。可以看到基于RNN+Two Tower的重排序模型，取得了最好的效果。其中MLR指标为作者定义的综合考虑相关性、多样性得分，对top N结果整体打分的指标。
Online A/B test
线上实验的结果如下：
Combined Loss Function方法：多样性很好，但是存在的问题是，结果中同时包含过低、过高价格的比例大幅提升，对用户体验不好。
人工加入Contextual features方法：线上效果不好，说明人工添加的上下文特征无法实现同时优化多样性、相关性的目的。
Query Context Embedding方法：在线NDCG增加1.2%，预定量增加0.44%，新用户预定量增加0.61%，说明多样性对新用户很重要。
论文里给出了重排序模块，对搜索结果位置、价格多样性优化的效果。具体效果如下：
后记
搜索推荐重排序，生成的结果直接展现给用户，对用户体验和效率都至关重要。和精排、召回模型相比，因为需要和线上系统交互才能验证效果，相关的研究少很多，期待工业界、学术界一起在重排序方向上做出更优秀的落地应用！
参考文献
[1] The Use of MMR, Diversity-Based Reranking for Reordering Documents and Producing Summaries, SIGIR 18.
[2] Practical Diversified Recommendations on YouTube with Determinantal Point Processes, CIKM 2018.
[3] Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity, NIPS 2018.
[4] Personalized Re-ranking for Recommendation, Recsys 2019
[5] SLATEQ:A Tractable Decomposition for Reinforcement Learning with Recommendation Sets, IJCAI 2019.
[6] Learning a deep listwise context model for ranking refinement, SIGIR 2018.
[7] Improving Deep Learning For Airbnb Search，KDD 2018.