Real-time Personalization using Embeddings for Search Ranking at Airbnb 解读

最近看到了Airbnb的一篇paper获得了2018年KDD best paper,于是阅读并在组内分享了下，顺便搬到博客上来

最近看到了Airbnb的一篇paper获得了2018年KDD best paper Real-time Personalization using Embeddings for Search
Ranking at Airbnb
,于是阅读并在组内分享了下，顺便搬到博客上来。
此文主要是对论文的重点部分进行翻译性地解读，同时穿插着我自己对各部分理解和想法。如有问题，欢迎指正。

目前在推荐上比较流行的方案，主要是基于google的wide&deep开启的end to end的模型，uid，itemid作为embedding输入 加上其他各种特征，并着重在wide部分进行优化，比如以deepFM为首的模型。我们自己也是在这个方向上实践的。这篇论文是先单独训练embedding，然后在把embedding当特征输入到rank model中

Introduction

搜索算法的目标就是为了提升网站的收益，在airbnb需要同时优化客人和房主两方，即给定地点和日期后，将位置、价格、风格和评价等方面对用户有吸引力的房子排前。也要考虑房主的偏好，将可能会拒绝客人的排名名降低，比如用户评价差，有宠物，人数等等原因。

在一个search session中会有多次点击和联系房主，这些都是in-session signals。实时个性化推荐的目标是在搜索会话期间为客人展现更多类似于我们认为他会喜欢的房间，同时，可以用负面信号，如跳过高排名的listings，去减少与之相似的我们认为不喜欢的。

引入listing embeddings,利用这些相似性去为Search Ranking Model创建个性化特征,驱动相似listing推荐

由于一般人一年旅行一到两次，在Airbnb的场景中，booking是很稀疏的，其中大量用户只订过一次。为此，训练listing_type级别的embeddings。同样,也学习与 listing _type embeddings 同一向量空间的user_type embeddings.这里边的一个亮点就是user_type embeddings 和 list_type embeddings是同一空间下的。

历史工作：

• Real-time Personalization
• Adapting Training for Congregated Search
• Leveraging Conversions as Global Context
• User Type Embeddings
• Rejections as Explicit Negatives

效果：

CTR相对于现有的模型提升20%

---

如上文所说，接下来介绍Listing Embeddings、Listing_type Embeddings 和 User_type Embeddings

Listing Embeddings

首先定义session，用户的点击序列就是session，两个点击间超过30min就是一个新的session，或者预订了房间也算是结束了一个session。根据此数据集去学习,使用skip-gram model最大化如下目标函数

$$\mathcal { L } = \sum _ { s \in \mathcal { S } } \sum _ { l _ { i } \in s } \left( \sum _ { - m \geq j \leq m , i \neq 0 } \log \mathbb { P } \left( l _ { i + j } | l _ { i } \right) \right)$$

$\mathbb { P } \left( l _ { i + j } | l _ { i } \right)$ 是在临近点击 $l _ { i }$ 情况下，应用soft-max后 $l _ { i + j }$ 被点击的概率:

$$\mathbb { P } \left( l _ { i + j } | l _ { i } \right) = \frac { \exp \left( \mathbf { v } _ { l _ { i } } ^ { \top } \mathbf { v } _ { l + j } ^ { \prime } \right) } { \sum _ { l = 1 } ^ { | \mathcal { V } | } \exp \left( \mathbf { v } _ { l _ { i } } ^ { \top } \mathbf { v } _ { l } ^ { \prime } \right) }$$

变量的定义很好理解，l就是listing（paper中的listing我理解就是房子），u就是user，v代指vector，像$v_ { l _ { i } }$就是指listing i的embedding，$\mathcal { V }$代指所有listings集合。

随机采样当做负例和传统的skip-gram相同，于是优化目标函数转变为：

$$\underset { \theta } { \operatorname { argmax } } \sum _ { ( l , c ) \in \mathcal { D } _ { p } } \log \frac { 1 } { 1 + e ^ { - \mathbf { v } _ { c } ^ { \prime } \mathbf { v } _ { l } } } + \sum _ { ( l , c ) \in \mathcal { D } _ { n } } \log \frac { 1 } { 1 + e ^ { \mathbf { v } _ { c } ^ { \prime } \mathbf { v } _ { l } } } （3）$$


$\mathcal { D }$ 指数据集， p为positive，n就是negative了。

Booked Listing as Global context:

session被分为两种:

1. booked sessions ( i.e. click sessions that end with user booking a listing to stay at
2. exploratory sessions (i.e. click sessions that do not end with booking, i.e. users were just browsing

引入最终预订的listing作为全局上下文，无论其是否在窗口内，帮助优化临近点击listing到预订listing的先关关系。于是booked sessions的embedding更新规则变成：

$$\underset { \theta } { \operatorname { argmax } } \sum _ { ( l , c ) \in \mathcal { D } _ { p } } \log \frac { 1 } { 1 + e ^ { - v _ { c } ^ { \prime } v _ { l } } } + \sum _ { ( l , c ) \in \mathcal { D } _ { n } } \log \frac { 1 } { 1 + e ^ { v _ { c } ^ { \prime } v _ { l } } } + \log \frac { 1 } { 1 + e ^ { - v _ { l _ { b } } ^ { \prime } v _ { l } } } （4）$$

Adapting Training for Congregated Search:

在线预定一般都是在一个market里去选择，比如你想去London，那么你会在London这个market里去选择。而负样本是全局随机采样的，很可能与正例不在同一个market里，导致同market内学习到的相似性不够好，为此引入同market的随机样本作为额外的负样本。

$$\underset { \theta } { \operatorname { argmax } } \sum _ { ( l , c ) \in \mathcal { D } _ { p } } \log \frac { 1 } { 1 + e ^ { - v _ { c } ^ { \prime } v _ { l } } } + \sum _ { ( l , c ) \in \mathcal { D } _ { n } } \log \frac { 1 } { 1 + e ^ { v _ { c } ^ { \prime } v _ { l } } } + \log \frac { 1 } { 1 + e ^ { - v _ { l _ { b } } ^ { \prime } v _ { l } } } + \sum _ { ( l , m_{n} ) \in \mathcal { D } _ { m_{n} } } \log \frac { 1 } { 1 + e ^ { - v _ { m_{n} } ^ { \prime } v _ { l } } } （5）$$

cold start listing embedding

新房子的embedding，用10英里内最相似的三个房子（类型、价格范围）的embedding均值来代替

Examining Listing Embeddings

在8亿的click sessions上训练32维embeddings,进行K-means聚类，可以发现位置相近的聚集在一起，可知学习到了地理位置的相似性。也可以看到相同类型和价格的listing比不同的更相似,如下图：

User-type & Listing-type Embeddings

用用户预订序列来训练Embedding，可以捕获cross-market的相似度

不过这样学习有以下挑战：

• 预订是个低频事件，booking sessions数据相较于click sessions少很多。
• 许多用户只预订一次，session长度为1是无法被学习的
• 对于任何一个实体，要学到有意义的embedding需要实体出现在数据中至少5-10次
• 用户两次预订间隔时间很长的话，用户自身偏好可能会改变比如因为职业的改变而对价格敏感度改变

解决方案，引入Listing_type embeddings

listing Embeddings 比较适合short-term, in session场景, peronalization还需要基于长期历史的个性化，用户曾经在纽约和伦敦预订过，现在在搜索洛杉矶。这就需要去找到不同market之间的相似性，通过用户的booked list可以捕获此信息。

给定一个listing_id，根据它的位置，价格，类型，容量，床数等进行规则映射用数据驱动的方式最大化每个listing_type 桶的覆盖范围

使用Listing_type embeddings来解决这个问题。给定一个listing_id，根据它的位置，价格，类型，容量，床数等进行规则映射，用数据驱动的方式最大化每个listing_type 桶的覆盖范围。Airbnb的映射table如下：

Training Procedure

此处我觉得是一个比较有想法的点，就是学习在同一向量空间下的user_type和listing_type embedding

$s _ { b } = \left( u _ { t y p e _ { 1 } } l _ { t y p e _ { 1 } } , \ldots , u _ { t y p e _ { M } } l _ { t y p e _ { M } } \right) \in \mathcal { S } _ { b }$ 是用户预订序列数据集，将user_type, list_type组合在一起，再拼成一个序列即相当于把他们确定到了一个空间中。
于是在skip-gram中， $user_type ( u _ { t } )$为中心项时，目标函数为：

$$\underset { \theta } { \operatorname { argmax } } \sum _ { \left( u _ { t } , c \right) \in \mathcal { D } _ { b o o k } } \log \frac { 1 } { 1 + e ^ { - v _ { c } ^ { \prime } \mathbf { v }_{ u _ { t }} } } + \sum _ { \left( u _ { t } , c \right) \in \mathcal { D } _ { n e g } } \log \frac { 1 } { 1 + e ^ { \mathbf { v } _ { c } ^ { \prime } \mathbf { v } _ { u_{t}} } }$$

$listing_type ( l _ { t } )$为中心项时，目标函数为：

$$\underset { \theta } { \operatorname { argmax } } \sum _ { \left( l_ { t } , c \right) \in \mathcal { D } _ { b o o k } } \log \frac { 1 } { 1 + e ^ { - v _ { c } ^ { \prime } \mathbf { v }_{ l _ { t }} } } + \sum _ { \left( u _ { t } , c \right) \in \mathcal { D } _ { n e g } } \log \frac { 1 } { 1 + e ^ { \mathbf { v } _ { c } ^ { \prime } \mathbf { v } _ { l_{t}} } }$$

Explicit Negatives for Rejections

不像一般的场景里只考虑用户偏好，Airbnb的这个场景既要考虑用户偏好也要考虑主人的偏好。引入房主拒绝行为，作为房主方的显示反馈。某种层面上会使对用户不敏感的房主和评分一般的客人聚拢，减少客人被拒绝几率，提高预定概率。
对于被拒绝的序列，我们优化的目标函数分别变为：

$$\underset { \theta } { \operatorname { argmax } } \sum _ { \left( u _ { t } , c \right) \in \mathcal { D } _ { b o o k } } \log \frac { 1 } { 1 + e ^ { - v _ { c } ^ { \prime } \mathbf { v }_{ u _ { t }} } } + \sum _ { \left( u _ { t } , c \right) \in \mathcal { D } _ { n e g } } \log \frac { 1 } { 1 + e ^ { \mathbf { v } _ { c } ^ { \prime } \mathbf { v } _ { u_{t}} } } + \sum _ { \left( u _ { t } , l_{t} \right) \in \mathcal { D } _ { reject } } \log \frac { 1 } { 1 + e ^ { \mathbf { v } _ { l_{t} } ^ { \prime } \mathbf { v } _ { u_{t}} } }$$

and

$$\underset { \theta } { \operatorname { argmax } } \sum _ { \left( l_ { t } , c \right) \in \mathcal { D } _ { b o o k } } \log \frac { 1 } { 1 + e ^ { - v _ { c } ^ { \prime } \mathbf { v }_{ l _ { t }} } } + \sum _ { \left( u _ { t } , c \right) \in \mathcal { D } _ { n e g } } \log \frac { 1 } { 1 + e ^ { \mathbf { v } _ { c } ^ { \prime } \mathbf { v } _ { l_{t}} } } + \sum _ { \left( l _ { t } , u_{t} \right) \in \mathcal { D } _ { reject } } \log \frac { 1 } { 1 + e ^ { \mathbf { v } _ { u_{t} } ^ { \prime } \mathbf { v } _ { u_{t}} } }$$

EXPERIMENTS

这段主要介绍了下训练和离线评估的细节，和listing Embeddings在房间相似推荐中的应用，以及如何将embedding处理为特征提供给Search Ranking Model。

Training Listing Embeddings

1. 30分钟不活跃原则
2. 移除偶发和短点击（如停留少于30s）
3. 只保留>=2 的sessions
4. 匿名session，移除userid

点击会话分为 exploratory sessions & booked sessions。训练数据中booked sessions过采样5倍达到最好效果.

Setting up Daily Training

• over multiple months
• 每天引入新一天，去掉最早一天的数据
• 重新训练是要比增量训练现有的vector效果好。

模型中，day-to-day vector的变化不会导致矛盾，因为最终使用的是embeddings间的相似度而非具体的vector

超参

• dimensionality 32
• window size 5
• iterations 10.

Offline Evaluation of Listing Embeddings

从预订房间开始回溯17个点击，统计预订房间在对应点击时刻的平均位置，比较了如下三个版本：

1. d32: trained using (3),
2. d32 book: trained with bookings
   as global context (4)
3. d32 book + neg: trained with bookings
   as global context and explicit negatives from same market (5)

最终可以发现d32 book + neg效果最好，具体如下图：

Similar Listings using Embeddings

Airbnb home listing page有相似房源，会展示相同可用日期下类似的房源,用余弦相似度，最近邻，取top K。

A\B Test显示，CTR整体提升21%（有入住日期的提升23%，无日期提升20%），在相似房源处进行最终预定的提升4.9%

Real time personalization in Search Ranking using Embeddings

训练数据 $D_{s} = (x_{i} ,y_{i}), i = 1…K$， K是搜索后返回listing的序号，$x$特征vector，$y$是label

• y = 1 booked
• y = 0.25 contacted but no booked
• y = -0.4 host rejected
• y = 0.01 clicked
• y = 0 just viewed

每次使用最近30天的数据训练新的ranking model

特征具体如下：

Feature vector xi for the i-th listing result consists of listing features,
user features, query features and cross-features. Listing
features are features associated with the listing itself, such as price
per night, listing type, number of rooms, rejection rate, etc. Query
features are features associated with the issued query, such as number
of guests, length of stay, lead days, etc. User features are features
associated with the user who is conducting the search, such as
average booked price, guest rating, etc. Cross-features are features
derived from two or more of these feature sources: listing, user,
query. Examples of such features are query listing distance: distance
between query location and listing location, capacity fit: difference
between query number of guests and listing capacity, price difference:
difference between listing price and average price of user’s
historical bookings, rejection probability: probability that host will
reject these query parameters, click percentage: real-time memorization
feature that tracks what percentage of user’s clicks were
on that particular listing, etc. The model uses approximately 100
features. For conciseness we will not list all of them.

他们使用了pairwise regression的思路去训练了一个GBDTmodel,使用的支持Lambda Rank的gbdt,用NDCG评估。

Embedding Features for Search Ranking
| Feature Name | Feature Name |
|—————|:——————-:|
|EmbClickSim| similarity to clicked listings in Hc
|EmbSkipSim| similarity to skipped listings Hs
|EmbLongClickSim| similarity to long clicked listings Hlc
|EmbWishlistSim| similarity to wishlisted listings Hw
|EmbInqSim| similarity to contacted listings Hi
|EmbBookSim| similarity to booked listing Hb
|EmbLastLongClickSim| similarity to last long clicked listing
|UserTypeListingTypeSim| user type and listing type similarity

User-type & Listing-type Embedding Features

• 500K user types
• 500K listing type
• 50 million user booking sessions

Embedding Features Coverage and Importances

Feature Name	Coverage	Feature Importance
EmbClickSim	76.16%	5/104
EmbSkipSim	78.64%	8/104
EmbLongClickSim	51.05%	20/104
EmbWishlistSim	36.50%	47/104
EmbInqSim	20.61%	12/104
EmbBookSim	8.06%	46/104
EmbLastLongClickSim	48.28%	11/104
UserTypeListingTypeSim	86.11%	22/104

Online Experiment Results Summary

引入 embedding features后，NDCU提升2.27%，booking DCU增长2.58%

收获&反思

• 我们自己的end to end模型所产生的embedding是否训练的足够充分有效
• 尝试引入以其他逻辑训练的embeddings
  不一定直接引入embedding，论文中引入的实际是相似度
• 训练同一向量空间下的embedding是很好的想法，将本来不同的embedding进行了统一
• 和平台自身场景、需求进行合理的结合