作者 :清华大学计算机系博士 谷育龙Eric
本文将基于Airbnb KDD2020年的论文 , 介绍Airbnb搜索排序中在重排序阶段如何解决多样性的问题 , 对工业界搜索推荐系统优化多样性 , 具有很好的指导与借鉴意义 。
文章图片
arxiv.org/abs/2004.02621v1
搜索推荐系统中的多样性问题
在互联网APP中 , 诸如电商(淘宝、京东、拼多多)、信息流(头条、微博、百度)、短视频(抖音、快手、微信视频号)等 , 搜索推荐的多样性对优化点击转化效率、用户体验、浏览深度、停留时长、回访、留存等目标至关重要 。
比如 , 淘宝"猜你喜欢”信息流会为用户推荐多个类目的宝贝、短视频、直播、文章等 , 来吸引用户停留:
文章图片
在Airbnb中搜索系统中 , 搜索结果的多样性 , 主要体现在房间类型、位置、价格信息等方面:
文章图片
深度学习精排阶段的排序模型 , 泛化能力比较好 , 一般相似的物品精排分数也比较接近 。 如果直接用精排分数排序展示结果 , 会导致排名靠前的结果非常类似 , 容易造成视觉疲劳 , 给兴趣宽泛、单纯逛逛、需求不明确的用户带来很差的体验 。
下图展示了Airbnb实际的搜索结果 。 可以发现 , 排序靠前的listing(即item , 民宿房间) , 其价格、位置差别通常非常小 。
文章图片
所以 , 工业界的搜索推荐系统 , 一般包括召回、粗排、精排、重排模块 。
- 在 召回 阶段 , 通过多路召回(item2item, 向量召回等)方式 , 召回和用户最近点击相似相关的物品、热门物品等 , 一般有几千到几万 , 保证效率、丰富、多样性 。
- 粗排 阶段 , 通过简化的精排模型 , 对大量召回物品打分 , 返回几千个物品 。
- 在 精排 阶段 , 用更复杂的深度排序模型等对这些物品打分 。
- 最后 , 在 重排序 阶段 , 对综合考虑点击率、转化率、价格、多样性等信息 , 对物品计算新的排序分数 , 最后展示给用户 。
文章图片
多样性指标
在多样性问题中 , 最基础的问题是定义衡量多样性的指标 。
- MMR:Maximal Marginal Relevance
文章图片
其中 是搜索查询 , 是候选的相关物品(例如精排后的结果) , 是MMR算法已经选取的物品 , 用来衡量物品和 的相似度, 用来衡量物品间的相似度, 是平衡相关度(例如CTR)和多样性的超参数(在Aribnb中通过实验分析 , 值设定为0.15) 。 公式中 建模了当前候选的物品 和搜索 的相似度 , 部分表示当前候选的物品 和搜索已经选取的物品的最大相似度 。 MMR算法的思想是:采取贪心策略 , 生成top K结果列表 。 第一次 , 先选取相关度最高的物品 。 然后 , 每次选取和查询 query 匹配度高、和已经选取的物品最大相似度低的物品 。 相似度函数 和 可以不同 , 根据业务需求来定 。 例如 , 在Airbnb搜索系统中 , 函数可以基于listing间价格、位置、类型等信息来计算 。
- MLR:Mean Listing Relevance
文章图片
可以看到MLR和MRR方法中定义的指标相比 , 把MRR指标中的最大值函数替换成了平均值函数 , 距离函数取代了相似度函数 (所以没有了负号) 。 这样做的动机是:MMR中的最大值函数 , 隐藏假设用户仅对每个类目中的一个item感兴趣;MLR中使用平均值函数 , 更加平滑 , 能更好地建模Airbnb中用户的广泛偏好 。
- Listing的向量表示
文章图片
- 基于多样性分布的距离计算
文章图片
关键的问题是 , 对于每个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的重排序
- 基于Location Diversity Ranker的重排序
文章图片
其中 , 以精排阶段分数作为ground truth label, 来衡量重排序结果和精排结果的偏差 , 表示重排结果的相关性得分;用重排序结果和理想地理分布的距离 , 表示重排结果的多样性得分 。 然而标准的优化方法(如SGD)并不能直接优化这个定义的损失函数 , 因为地理位置表示的映射是固定的 。 所以 , 作者采用了基于模拟退火的方法:多次迭代 , 每次迭代通过交换重排序结果列表中两个item的位置生成新的结果 , 如果指标增加 , 选取这个新的结果 , 否则以一定的概率来接受新结果 。
- 基于Combined Loss Function的重排序
基于重排序模型训练时得到listing的重排序得分 , 分别计算多样性损失、pair-wise多样性损失 , 如果每部分loss都能用梯度下降来优化 , 那么就可以直接学习重排序网络的参数了 。 其中Loss 和精排模型类似 , 基于正负样本 , 计算pair-wise loss , 可以用梯度下降来优化 。 多样性loss, 是根据重排序生成结果的分布和理想的分布来计算的 。 关键问题是可以如何设计能用SGD优化的多样性loss function呢?作者首先基于一下假设 , 将重排序优化问题 , 转化为优化生成结果和目标结果多样性分布的Hellinger距离, 代码如下:
文章图片
但是 , 直接使用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
- 基于Query Context Embedding的重排序
文章图片
对于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
文章图片
- Online A/B test
文章图片
- Combined Loss Function方法:多样性很好 , 但是存在的问题是 , 结果中同时包含过低、过高价格的比例大幅提升 , 对用户体验不好 。
- 人工加入Contextual features方法:线上效果不好 , 说明人工添加的上下文特征无法实现同时优化多样性、相关性的目的 。
- Query Context Embedding方法:在线NDCG增加1.2% , 预定量增加0.44% , 新用户预定量增加0.61% , 说明多样性对新用户很重要 。
1. 使得搜索结果的位置分布更加多样了 。
文章图片
2. 使得搜索结果的价格分布更加接近期望价格、减少极端的价格 。
文章图片
后记
搜索推荐重排序 , 生成的结果直接展现给用户 , 对用户体验和效率都至关重要 。 和精排、召回模型相比 , 因为需要和线上系统交互才能验证效果 , 相关的研究少很多 , 期待工业界、学术界一起在重排序方向上做出更优秀的落地应用!
参考文献
[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.
【用户|Airbnb搜索:重排序阶段如何优化搜索结果多样性?】[7] Improving Deep Learning For Airbnb Search , KDD 2018.
推荐阅读
- 安全|Redline Stealer恶意软件:窃取浏览器中存储的用户凭证
- 吴祖榕|上线 2 周年,用户数破 2 亿,腾讯会议和我们聊了聊背后的产品法则
- 硬件|上线两年用户破两亿,腾讯会议还能做什么?
- 全体|喜报:三星 Galaxy S21 系列全体用户现已获推 One UI 4.0 正式版
- 隐私|用户隐私保护新境界,2021 vivo开发者大会将发布安全新动作
- 挖矿|深信服2021年度安全技术盘点,解决了用户哪些需求呢?
- 词条|百度百科上线2500万词条,超750万用户参与共创科普知识内容
- 接口|微信小程序用户信息相关接口调整
- 用户|扫地机器人行业未来怎么走?石头科技给出了答案
- 视点·观察|HDMI 2.1a规范或让用户购买HDMI线缆更复杂