Real-time Personalization using Embeddings for Search Ranking at Airbnb

1.背景

Airbnb作为全世界最大的短租网站，提供了连接房主（host）挂出的房源（listing）和租客（guest/user）的一个中介平台。这样一个中介平台的交互方式比较简单，guest输入地点，价位，关键词等等，Airbnb会给出listing的搜索推荐列表，因此guest和host之间的交互方式有：
1.guest点击listing （click）
2.guest预定lising （book）
3.host有可能拒绝guest的预定请求 （reject）

Airbnb的搜索团队建立了一个Real-time实时的个性化排序模型，既考虑用户的短时兴趣，也考虑用户的长期兴趣。短时兴趣指用户在一个session中表现出的兴趣，而长期兴趣指用户在其所有历史行为中表现出的兴趣。

文章通过两种方式生成了两种不同的embedding分别capture用户的short term和long term的兴趣。
1.一是通过click session数据生成listing的embedding，生成这个embedding的目的是为了进行listing的相似推荐，以及对用户进行session内的实时个性化推荐。
2.二是通过booking session生成user-type和listing-type的embedding，目的是捕捉不同user-type的long term喜好。由于booking signal过于稀疏，Airbnb对同属性的user和listing进行了聚合，形成了user-type和listing-type这两个embedding的对象。

2.listing embedding

训练数据集的构造：数据集由N个用户的点击Session组成，其中每个session表示的是用户点击的M个listing id序列。
1.其中时间间隔超过30分钟的，就需要被分成两个session；
2.去掉会话中的误点击和时间比较短的点击，具体操作是过滤掉查看时长在30秒之内的房源记录。
最后只保留房源数量大于等于2的会话记录，构成会话训练集S。给定数据集，目标就是通过集合S，学习出每个listing的d维的向量，让相似listing在embedding空间的距离更近。这里定义的embedding维度为32，低纬度的设置可以在模型上线后让实时召回的速度更快。

这么做一是清洗噪声点和负反馈信号，二是避免非相关序列的产生。

有了由clicked listings组成的sequence，可以把这个sequence当作一个“句子”样本，开始embedding的过程。Airbnb选择word2vec的skip-gram model作为embedding方法的框架。通过修改word2vec的objective使其靠近业务目标。

房源embedding的训练如下图所示，最上面一行橙色方块是某个用户连续点击过的房源记录，包含了11条点击房源记录。滑动窗口大小是m，通过中间的房源，预测左右两侧的m个房源。除了点击房源，最右侧还有一个预订房源，只有在预订会话中才包含预订房源。

Airbnb的类word2vec embedding方法
一步一步理解word2Vec
word2vec基于负采样的模型原理介绍
根据上面链接介绍，word2vec的skip-gram model的objective如下：
在采用negative sampling的训练方式之后，objective转换成了如下形式：
其中σ函数代表sigmoid函数，D是正样本集合，D'是负样本集合。 在Airbnb问题中，正样本取自click session sliding window里的listing，负样本则是在确定central listing后随机从语料库（这里就是listing的集合）中选取一个listing作为负样本。Airbnb初始的objective function如下：

但在上述objective上，Airbnb做了许多改进：

trick1: Booked Listing as Global Context
在原始word2vec embedding的基础上，Airbnb的工程师希望能够把booking的信息引入embedding。这样直观上可以使Airbnb的搜索列表和similar item列表中更倾向于推荐之前booking成功session中的listing。从这个motivation出发，Airbnb把click session分成两类，最终产生booking行为的叫booked session，没有的称做exploratory session。

因为每个booked session只有最后一个listing是booked listing，所以为了把这个booking行为引入objective，不管这个booked listing在不在word2vec的滑动窗口中，都假设这个booked listing与滑动窗口的中心listing相关，所以相当于引入了一个global context到objective中，因此，objective就变成了下面的样子

其中最后一项的就是代表着booked listing，因为booking是一个正样本行为，这一项前也是有负号的。

需要注意的是最后一项前是没有sigma符号的，前面的sigma符号是因为滑动窗口中的中心listing与所有滑动窗口中的其他listing都相关，最后一项没有sigma符号直观理解是因为booked listing只有一个，所以central listing只与这一个listing有关。

trick2: Adapting Training for Congregated Search
当用户确定旅行目的地之后，搜索或浏览的房源都在目的地附近，因此正样本中的房源大部分都在同一个地点或城市，而负样本是从所有房源中随机采样得到的，大概率会来自其他不同的地方。这样的正负样本，无法很好地对同一个地方的房源进行区分，因此又增加了一个负样本集合，是从当前房源l所在的地方随机抽样得到。

其中：

• 是正在更新的中心房源的向量;
• 是一对正对，表示（中心房源，相关房源）元组，其向量在优化中会被相互推近；
• 是一对负对，表示（中心房源，随机房源）元组，其向量在优化中会被相互推离；
• 是最终被预定的房源，被视为全局上下文并被推向中心房源向量；
• 是一对目的地维度的负例对，代表（中心房源，来自同一目的地的随机列表）元组，其向量被推理彼此。

解决冷启动问题
对于新加入的房源，训练数据中是没有它的记录的，也就是无法训练得到其Embedding。文中的做法是从已有的得到embedding的房源中，选择3个地理位置最近(但是要在半径10miles以内)、房源类别和价格区间相同的房源，并用其embedding的平均值来作为新房源的embedding。 98%的新房源都可以通过这种方式来获得相应的embedding。

评估 Listing Embedding

• 1.K-means聚类：对embeddings做k-means聚类，查看聚类效果和地理位置是否一致。
  上图展示了美国California的房源聚类效果，可以看到地理位置接近的房源都被聚类到了一起。
• 2. embeddng之间的余弦距离度量：在不同类型的listing之间计算余弦距离，不同价格范围的listing之间计算余弦距离，结果如下：
  同一房源类型（包括整个房源，独立房间，合住房间3类）的平均相似度要高于不同房源类型的相似度，同一价格区间的平均相似度高于不同价格区间。
• 3.Embeddings evaluation tool：对无法量化的特征进行评估。
  比如建筑风格，作者通过可视化的方式进行查看，如图所示，左侧是一个树屋，右侧是搜索到最相似的k个房源，同样都是树屋。

3.User Type & Listing Type Embedding

上节中的listing embedding并没有包含用户的长期兴趣信息。比如用户6个月前订了一个listing，其中包含了该用户对于房屋价格、房屋类型等属性的长期偏好，但由于之前的embedding只使用了session级别的点击数据，从而明显丢失了用户的长期兴趣信息。为了捕捉用户的长期偏好，airbnb在这里使用了booking session序列。
构造数据集：由前面的点击序列变成预定序列，数据集为N个用户预定的Listing 组成的session集合。每个sesison可以表示为是用户的预定listing序列。但会面对数据稀疏性问题：

1.book行为的总体数量本身就远远小于click的行为，所以booking session集合的大小是远远小于click session的；
2.很多用户在过去只预定过一次，这导致很多booking session sequence的长度为1，这些数据是没法用来训练模型的。；
3.大部分listing被book的次数也较少，而w2v要训练出较稳定有意义的embedding，item最少需要出现5-10次，但大量listing的book次数少于5次，根本无法得到有效的embedding。
4.长时间的跨度，可能用户的喜欢已经一些习惯已经发生变化。
因此Airbnb提出根据特征对房源进行归类，对每个房源类型学习embedding。类似地，对用户做归类，学习**用户类型的embedding。

listing的属性 可以用属性名和bucket id组成一个属性标识，比如说某个listing的国家是US，类型（listing type）是Ent（bucket 1），每晚的价格（per night）是56-59美金（bucket3），那么就可以用US_lt1_pn3来表示该listing的listing_type。 user type的属性及bucket

user_type的定义同理。为了让user type embedding和listing type embedding在同一个vector space中生成，airbnb采用了如下的方式。

针对某一user id按时间排序的booking session，，用（user_type, listing_type）组成的元组替换掉原来的listing item，因此sequence变成了，这里指的就是listing l1对应的listing type，指的是该user在book listing l1时的user type，由于同一user的user_type可能随时间变化，所以，不一定相同。

下面的问题就是如何训练embedding使得user type和listing type在一个空间内了。按照时间顺序排列生成booking session，用户类型和房源类型交替排列，然后按照skip-gram的方式进行训练，但由于文章用一个（user type，listing type）的元组替换掉了原来的listing，如何确定central item就成为了一个核心问题。针对该问题，文章的原话是这么说的。

instead of listing l , the center item that needs to be updated is either user_type (ut) or listing_type (lt) depending on which one is caught in the sliding window.

central item为user type central item为listing type 目标函数第1项表示正样本集合的目标函数，表示正样本集合，即用户预订的房源，或者该用户的其他用户类型。第2项表示负样本的目标函数，是随机抽取的用户类型或者房源类型。点击行为仅仅反应了用户的偏好，但是预订不仅反应用户的偏好，还反应了房东的偏好。因为在Airbnb的场景下，房东可以接受用户对房源的预订，也可以拒绝预订。可以利用房东的拒绝行为，在向量空间中编码房东的偏好，在推荐中增加预订几率的同时，减少拒绝的发生。在第3项中，表示用户被拒绝的元组(user_type, listing_type)的集合。

Airbnb上99%的预订都来自于搜索排序和相似房源推荐这两个渠道，而房源类型和用户类型的embedding主要用于搜索排序算法，而上一部分介绍的单个房源的embedding，既用于相似房源的推荐，也用在了搜索排序算法中。

4.房源搜索排序

作者将房源搜索排序问题当做一个回归问题来解决，去拟合标签。标签包括{0, 0.01, 0.25, 1, -0.4},0表示房源曝光给用户但并没有被点击，0.01表示用户点击了房源，0.25表示用户联系了房东但是并没有预订，1表示房源预订成功，-0.4表示房东拒绝了用户的预订。采用的搜索排序模型是一个pairwise的支持Lambda Rank(learning to Rank算法介绍：RankNet，LambdaRank，LambdaMart)、(RankNet与LambdaRank)的GBDT模型。

输入特征包括房源特征，用户特征，搜索特征，和交叉特征几个类别，大约100个特征。房源特征包括价格，房源类型，房间数目，拒绝率等。用户特征包括用户的平均预订价格等。查询特征包括入住人数，租住天数等。交叉特征是多个特征的组合，包括搜索位置和房源位置的距离，入住人数和房源容纳人数的差异，房源价格和用户历史预订的平均价格的差异等。模型训练完成后以在线的方式运行，用户搜索之后，对候选房源打分，并按照分数降序排列展示给用户。

将用户最近两周有行为的房源做个分类，一共包括6个类别：
1）：用户最近两周点击过的房源id；
2）：用户点击并且停留时长超过60秒的房源；
3）：过去两周用户跳过的排在前面的房源id；
4）：用户加入收藏的房源；
5）：用户联系过房东但是却未预订的房源；
6）：用户在过去两周内预定过的房源。
将候选房源与上述6个类别的房源计算相似度，作为特征加入到搜索排序模型中，如下图的前6个特征，EmbClickSim, EmbSkipSim, EmbLongClickSim等。

以为例其他5个类别的计算方法相同。对于每个类别，根据城市再一次进行划分，比如中的房源来自于New York和Los Angeles两个城市，将划分为和。将中所有房源的embedding求平均，作为centroid embedding，然后计算当前候选房源与centroid embedding的余弦相似度。类似的，计算候选房源与的centroid embedding的余弦相似度。最后，取两个相似度的最大值作为EmbClickSim。如果Hc中的房源来自于多个城市，也是相同的计算方法。

可以看到，最后一个feature UserTypeListingTypeSim指的是 user type和listing type的similarity，该feature使用了文章介绍的包含用户长期兴趣的embedding，除此之外的其他feature都是前面介绍的listing embedding。比如EmbClickSim指的是candidate listing与用户最近点击过的listing的相似度。

针对real time personalization，由于在这些embedding相关的feature中，加入了“最近点击listing的相似度”，“最后点击listing的相似度”这类特征，由于这类特征的存在，用户在点击浏览的过程中就可以得到实时的反馈，搜索结果也是实时地根据用户的点击行为而改变，所以形成一个real time个性化系统。
参考文章：
看Airbnb实时搜索排序中的Embedding技巧
Airbnb实时搜索排序中的Embedding技巧
深入解读Airbnb推荐算法