今天学习的是一篇 2018 年的工业论文《Real-time Personalization using Embeddings for Search Ranking at Airbnb》，介绍的是 Word2Vec 在 Airbnb 推荐场景中的应用。大概内容就是从用户日志中抽取用户行为并组成序列，然后通过 Word2Vec 完成训练，最后得到 Item 的 Embedding Vector。虽然看似简单，但这篇论文却拿到 KDD 2018 Best Paper，知易行难，在看本文文章之前，我们先来试着回答几个问题：

1. 如果你是 Airbnb 的工程师，如何构建数据集，正例是什么，负例是什么？
2. 旅游是一个低频行为，很大一部分用户一年可能只有一两次行为，这样就没法组成一个序列用于训练，这部分数据怎么处理？直接扔掉吗？
3. 如何捕捉用户的实时兴趣和长期兴趣？
4. Airbnb 这种体量的公司是如何在搜索中做到实时计算个性化，计算量不会很大吗？
5. 如何解决新用户和新房源的冷启动问题的？

读者阅读完本文后将一一得到答案：

1. Introduction

工程师在 Airbnb 的应用场景中设计了两种 Embedding 方式：

• 一种是用来反应短期实时兴趣 Item Embedding；
• 另一种反应长期兴趣的 User-type & Item-type Embedding。

2. Item Embedding

我们先来看如何构建反应短期实时兴趣的 Item Embedding。

2.1 Model

我们将用户的点击行为构建为序列 $s_i = (l_1,l_2,...,l_m) \in S$ ，其中 S 为 N 个用户的行为序列集合。为了消除噪声和增强负反馈信号，我们需要对序列进行清洗：

1. 删除用户停留时长小于 30 秒的 Item；
2. 如果用户两次点击行为间隔超过 30 分钟，将重新构建一个新的序列；

我们使用 Skip-Gram 模型来训练 Embedding，窗口大小为 2m + 1 的损失函数为：
$\sum_{-m \leq j \leq m,\ i \neq 0} log(P(l_{i+j}|l_i)) \\$
整体样本的代价函数为：
$argmax \quad L = \sum_{s\in S} \sum_{l_i \in s}\sum_{-m \leq j \leq m,\ i \neq 0} log(P(l_{i+j}|l_i)) \\$
为方便起见，我们以下讨论的损失函数均为窗口的损失函数。

为防止每次迭代计算更新输出向量的所有参数值，我们采用 Negative Samping 进行负采样，损失函数为：
$argmax \quad \sum_{(l,c) \in D_p} log[\sigma(v_c^{'}v_l)]+\sum_{(l,c) \in D_n} log[\sigma(-v_c^{'}v_l)] \\$
其中，$v_c^{'}$ 为上下文 $c$ 的输出向量；$v_l$ 为房源 $l$ 的输入向量；$D_p$ 为正例集合（长度为 m 的窗口内，点击的房源为 l ，窗口内的其他点击房源为 c，用房源 l 来预测其他房源 c），$D_n$ 为 Negative Sampling 的负采样集合（l 为点击的样本，c 为样本库中其他样本）。

2.2 Booking Item

我们以点击序列进行模型训练可以计算出 Item 的 Embedding 向量，但显然的 Item 丢失了有效信息，被预订的 Item 更能反映出用户的兴趣。

目前来看我们现在的点击序列共有两种类型：

• 预订序列：以用户预订为结尾的点击序列；
• 探索序列：不以用户预订为结尾的点击序列；

于是我们们将预订序列单独拿出来，探索序列的损失函数不变，修改预订序列的损失函数：
$argmax \quad \sum_{(l,c) \in D_p} log[\sigma(v_c^{'}v_l)]+\sum_{(l,c) \in D_n} log[\sigma(-v_c^{'}v_l)] + log[\sigma(v_c^{'}v_{l_b})] \\$

从预订序列的损失函数中我们可以看到，每一个窗口都会预测一次预订的 Item。

下图显示预订序列的工作方式，虚箭头表示预订的 Item 始终会进行预测。

2.3 Negative Sampling

$D_n$ 为 Negative Sampling 的负采样集合，Word2Vec 的负采样是以一定从语料库中抽取单词，这显然不符合 Airbnb 的商业场景——用户本身就不会预订目的地外的房源。

为了增强负反馈，我们将从 Central Item （Skip-Gram 的输入）所在地区中随机添加一组负样本。损失函数为：
$argmax \quad \sum_{(l,c) \in D_p} log[\sigma(v_c^{'}v_l)]+\sum_{(l,c) \in D_n} log[\sigma(-v_c^{'}v_l)] + log[\sigma(v_c^{'}v_{l_b})] + \sum_{(l,m_n) \in D_{m_n}} log[\sigma(-v_{m_n}^{'}v_l)]\\$

2.4 Cold Start

冷启动问题一直是推荐、CTR 等领域的一大难题。新的房源每天都会发布，但是这些房源没有 Embedding 可以使用，就没办法给用户进行推荐。为了给新 Item 完成冷启动，我们可以利用其他 Item 的 Embedding：

我们将 Item 分解为更细的元数据，如：位置、价格、类型等。然后我们找出新 Item 周围具有相同元数据的三个 Item。将这三个 Item 的 Embedding 向量取质心作为新 Item 的 Embedding 向量，这种方法可以 cover 掉 98% 的需求。

2.5 Evaluation

我们用八亿点击序列来训练数据，最终为每个 Item 得到 32 维的 Embedding 向量。为了评估 Embedding 的质量呢，我们可以从以下几个方面进行评估：

• 地理位置：利用 k-means 聚类来评估地理位置是否被编码进 Item 中；
• 价格/类型：利用余弦相似度来评估同价格/类型的 Item 相似度是否最高；
• 风格：利用 k 近邻来找到相近 Item，然后观察他们之间的相似性；

3. User-type & Item-type Embeddings

上一节介绍的 Item Embedding 可以很好的用来发现 Item 之间的相似性，非常适用于用户短期的个性化点击场景，但是这种 Embedding 没法捕捉到用户的长期兴趣，比如说用户几个月在洛杉矶和纽约预订了房子，现在要在旧金山预订房子，已有的 Embedding 方式没法捕捉到用户的长期偏好。如果我们将用户预订的 Item 组成预订序列 $s_b = (l_{b_1},l_{b_2},...,l_{b_m})$ 采用对待点击序列相同的方式会遇到很多问题（区别与上文提到的预订序列）：

• 首先，大量用户只预订过一个 Item，没法用长度为 1 的 Item 进行学习；
• 其次，有效的学习 Item 至少需要其出现 5～10 次，但很多 Item 出现次数不满足；
• 最后，用户的两个连续预订的 Item 之间可能会有很长的时间间隔（旅游低频）。

3.1 Meta Data

为了解决这种问题，我们提出了学习 Item-type 的 Embedding 来代替原本的学习 Item-Id 的 Embedding。利用元数据的思想，将一个 Item 分解为位置、价格、类型、房间数、床位数等等，这样每个 Item 都可以由多个元数据拼接而成。下图是我们定义的元数据及映射规则。

同样的方法，我们也适用于用户：

有了元数据后我们可以利用聚类的方式将相似用户聚在一起形成一个随时间变化的预订序列，这便很好的解决了数据的稀疏性。

为了给用户推荐相似 Item，该如何让 User-type 和 Item-type 处于同一向量空间？

一个简单的方法就是将 User-type 和 Item-type 混合并利用交替训练使其参数相互影响，从而同处一个空间内。

这种随时间变换的预订序列：
$s_b = ([u_{type_1},l_{type_1}],[u_{type_2}, l_{type_2}],...,[u_{type_m}, l_{type_m}) \\$
其中，$[u_{type_i},l_{type_i}]$ 表示由用户订购的房源时的 User-type 和 Item-type 组成，对同一个用户来说，$u_{type_i}$ 可能随时间发生变化，所以相邻的两个 $u_{type_i} $ 不一定相同，在实际应用时使用最新的 $u_{type_i} $。

至此我们便解决了训练数据的问题，对于第二个问题，我们直接将所有的 $[u_{type_i},l_{type_i}]$ 拼接成一整条数据，滑动窗口可以在整条数据上滑行，这样便保证了其处于同一向量空间内。

3.2 Rejection

目前我们已经利用了用户的点击行为和预订行为，还有一种行为没有被利用——房东拒绝。与点击预订反应用户偏好类似，拒绝行为也反映出了房东的偏好。

房东拒绝用户的原因可能有：用户的评分低、资料不完整、养宠物等等，这是一种强烈的负反馈信号，我们也可以在训练过程中加以利用。

我们将房东的 Reject 行为编码到 User-type 的元数据中（User-type 相对于 Item-type 来说更敏感，如用户低评分、资料不完整等等），这样用户碰到的 Rejection 会越来越少，可以提高预订转换率。我们将 Reject 行为加入到损失函数中：
$argmax \quad \sum_{(l,c) \in D_{book}} log[\sigma(v_c^{'}v_l)]+\sum_{(l,c) \in D_{neg}} log[\sigma(-v_c^{'}v_l)] + \sum_{(l,l_r) \in D_{reject}} log[\sigma(-v_{l_r}^{'}v_l)]\\$
其中，$D_{reject}$ 为 Reject 集合。

下图为加入 Reject 后的模型，在预订序列中预订失败会有负号标记。

3.3 Cold Start

User 和 Item 都具有某些属性，比如说地理位置、价格等，对于新用户或者新 Item 可以通过现有的元数据完成冷启动。

4. Evaluation

通过余弦相似度计算 User-type 和 Item-type 之间的相似度，下图是某个例子，我们可以看到与 User-type 相似度高的 Item-type 和相似度低的 Item-type 类型正好相反。

Expenriments

我们来评估一下这两种 Embedding 的质量。

4.1 Search Model

首先我们将 Item Embedding 应用于搜索模型中，d32 表示维度大小为 32。横坐标为用户预订前最新的 17 次点击，纵坐标为预订 Item 平均排名，我们我可以看到对于系统本身的 Search Model，用户点击次数越多越精准，而我们的 Embedding 向量加入也是非常有效的。

4.2 Similar Item

Airbnb 的首先都会推荐给用户相似的 Item，我们将现有的相似检测算法和基于 Embedding 的相似计算方法进行 A/B 测试，结果表明基于 Embedding 的方法提高了 21% 的点击率，通过提高了 4.9% 的预订概率（通过推荐页进行预订）。

4.3 Embedding FE

Airbnb 使用基于 Pariwise 并支持 Lambda Rank 的 GDBT 模型进行搜索排序，使用的特征包括房源特征、用户特征、搜索特征和交叉特征等共 104 个特征，标签数据包括 (0, 0.01, 0.25, 1, -0.4) 分别对应，浏览没点击、点击、联系但是没预订、预订成功、拒绝预订。采用 NDCG 来作为排序的评价指标。

我们先来看下如何利用 Embedding 来构建特征，这个对工业界来说非常实用。首先从用户行为日志中收集用户过去两周的房源信息：

1. EmbClickSim：用户点击过的房源；
2. EmbSkipSim：曝光却没有点击的房源；
3. EmbLongClickSim：用户点击并且停留时长超过60秒的房源，表示长点击房源；
4. EmbWishlistSim：用户加入收藏的房源；
5. EmbInqSim：用户联系过房东但是却未预订的房源；
6. EmbBookSim：用户在过去两周内预定过的房源；
7. EmbLastLongClickSim：用户最后一次长点击房源；
8. UserTypeListingTypeSim：User-type 和 Item-type 的相似性。

然后计算候选房源与上述房源（1-7）的相似性，并作为新的特征输入到模型中。第 8 个特征中，一个用户可能有多个 User-type，取最近的一次。

下图为构建特征的重要性程度：

4.4 Results

下图为线上的实验指标：

4.5 Real-time personalization

Airbnb 在标题中 Real-time Personalization using Embeddings for Search Ranking，应该是指：在搜索后段加载全部的 Embedding 向量到内存中，然后利用 Kafka 实时计算候选房源与历史房源的相似性作为实时特征。

这里的候选房源，也就是召回策略其实是由用户确定的，通常用户会输入日期和地点，这种情况下的候选集通过只有几百个，这就对性能的要求很低了，而实时计算的相似性也只是与历史房源的质心做计算，所以计算速度是非常快的。

5. Conclusion

看完这篇文章后的思考：

1. Airbnb 的 Negative Sampling 由语料库中的其他 Item 和同一地区的 Item 随机抽样组成，这样学出的 Item Embedding 具有位置信息，但在实际的业务场景下，用户输入目的地后就已经把 Item 的位置信息确定了，还在 Item 的 Embedding 中加入位置信息算不算一种数据冗余？如果从曝光而没点击的 Item 中进行 Negative Sapmling，是不是能在有限的空间中更加充分的学习出用户的兴趣偏好？

6. Reference

1. 《Real-time Personalization using Embeddings for Search Ranking at Airbnb》
2. 《Listing Embeddings in Search Ranking》
3. 《从KDD 2018 Best Paper看Airbnb实时搜索排序中的Embedding技巧》
4. 《Airbnb如何解决Embedding的数据稀疏问题？》

关注公众号跟踪最新内容：阿泽的学习笔记。