论文原文：

论文原文：《Real-time Personalization using Embeddings for Search Ranking at Airbnb》

论文地址：https://dl.acm.org/authorize.cfm?key=N665520

本论文获得了2018 年 KDD ADS track 的最佳论文，利用了embedding技术在airbnb租赁市场中进行搜索和个性化推荐，并且给airbnb带来了99%的转化收益，embedding技术在推荐系统中可谓是发挥了重大的作用，在上一篇dssm文章中，正是利用了embedding来计算user和item的相似度进行推荐的，还有以后我们要讲到的youtube的召回任务是如何利用embedding的。现在我们先来读读这篇2018 KDD最佳论文吧。

一 、背景

搜索排名和推荐是主要互联网公司（包括Web搜索引擎，内容发布网站和市场）至关重要的基本问题。尽管这些任务会有些相似性，但是不存在一个万能的算法能hold住所有的生产任务，而在搜索和推荐场景下，这个问题就变得更复杂，每个市场的环境千差万别，对房源主人和用户来说，这是一个双向市场，要构建一个令双方都满足的实时搜索推荐模型关乎着airbnb收益转化的问题。

我们先看一下airbnb民宿的搜索过程：

airbnb主页

搜索过程需要输入目的地，城市或者经典，以及日期，在输入目的地后：

在输入目的地后，可以看到airbnb已经为我们提供了几个优质的房源了，而且在第一次搜索的时候排序靠前的都是评分高的好房源。我们点击第一个房源进去看：

在鼠标滑到网页最下方可以看到airbnb为我们推荐了三个相似的房源，这几个房源的地址，价格，关键字都是相近的，airbnb是如何做到的呢？

由于访客通常会在预订之前进行多次搜索，即单击多个列表并在搜索过程中与多个主持人联系，因此我们可以使用这些会话中信号（例如，点击，与主人联系等）进行实时个性化设置，目的是向客人展示更多自从搜索会话以来我们认为他们喜欢的房源。

airbnb把房源进行了embedding操作，把每一个房源映射到了低维向量，在用户开始一个session后，计算这个session里面的房源跟候选房源之间的相似性进行排序展示。按照论文原文中的论述，airbnb99%的房源预定都是来自搜索和推荐这两个系统中，其实也符合这种双向市场的市场性质。

上面说的用session內的房源进行相似性推荐是短期兴趣推荐，只计算了用户的短期兴趣，事实上用户还有自己的长期兴趣，这个长期兴趣的计算是根据用户在过去旅游预定历史来决定的，因为用户一年旅游的次数只有一两次，比较稀疏，所以不能像计算user id的embedding一样为每个用户单独计算embedding，为了解决这个这题，airbnb进行了类型映射，根据user的各个属性进行多对一映射成一个类型，对类型进行embedding。跟用户类型一样，房源也进行类型映射。可以用类型相似度计算作为长期兴趣推荐的依据。

在进行embedding操作后，产生包括Listing Embedding、User Type Embedding 和 Listing Type Embedding三个embedding，这也是这个模型最关键的部分，下面就来详细说说怎么构建这三个embedding。

二 、Listing Embedding

在论文中Listing就是房源的意思，跟电商推荐里面的item可以当作同一个概念的东西。在用户开始进行一个session后，用户进行的click操作，产生M个点击的房源（，，...）,相信大家都知道skip-gram训练word embedding的方法，airbnb就是用skip-gram训练listing embedding的。

这里原文中对session做了定义：

1）每次点击，用户需要至少在页面上停留30s，否则被视为误点击，不进行考虑。

2）用户前后两次点击时间间隔大于30min，作为切割session的依据

极大化目标函数：

其中：

这里是房源l的要学习的embedding向量，V是所有的房源，这个P就是在给定上下文的点击条件下，出现的概率。可以看到，其中具有相似上下文（即在搜索会话中具有相似相邻房源）的房源将具有相似的表示形式。

回忆下word2vec中直接对这个目标函数进行优化会有什么问题，从公式中看，首先V这个listing vocabulary太大了，会让softmax的计算复杂性变得非常大，在一个语料库很大的训练集合中，每计算一次P就要计算所有的词向量跟当前向量的内积，这是非常耗费计算资源的。在airbnb实时推荐系统中，房源的数量级是在几百上千万的，想象一下计算一次P计算进行几千万次内积运算，这谁顶得住啊。。

所以airbnb就采用了negative sampling的方法训练listing embedding：

是正样例，是随机采样的n个负样例，这个公式的推导过程很多地方都有，这里我也简单的推一下吧。首先skip-gram方法是用中心词去预测上下文，也就是P(,,...,... | )，这里我们假设每个词的出现是相互独立的，当然事实上词与词之间存在着很强的关联，但为了计算方便，我们暂时假定词与词之间没有关联，于是前面的联合条件概率可以分解成P()*P()*···*P(),要最大化这个联合概率，我们把这个函数机上log后就变成了加法了,同时我们不用softmax了，该用sigmoid函数计算表示概率P(Wj | Wi),即将P(Wj | Wi) = sigmoid(Wj Wi)。

根据上面的简单推导就可以知道airbnb优化目标为什么变成了上面那个式子了。不过跟sgns还是有点不太一样的，sgns里面是直接减负样例的值，不过看上面的优化函数，负样例把负号去掉后其实优化的目标是一样的，都是让正样例·变大，让负样例的变小，这个在结果上是一样的。

2.1 Booked Listing as Global Context.

在所有的训练用的Session中，有一部分发生了预订行为，我们称之为booked sessions，有一些没有发生预订行为，我们称之为exploratory sessions。对于booked sessions，无论最终预订的房源是否在Skip-Gram的窗口内，都将其放入到目标函数中。这么做出于这样的考虑：无论当前窗口是否包含预订的房源，被预订的房源都是与当前的中心房源是有关联的。 因此，对于预订的会话，更新规则变为:

就是booked sessions的最终预定的房源，看前面的图也知道就算最终预定的房源在窗口之外，也加到了优化函数中。

对于exploratory sessions优化函数还是跟之前一样。

2.2 Adapting Training for Congregated Search

在线旅行预订网站的用户通常仅在单个地区（即他们想要停留的位置）内进行搜索。 结果，很有可能Dp包含来自同一市场的商品。 另一方面，由于对负样例进行了随机抽样，因此Dn中包含的房源所属的地区可能有很大部分跟Dp房源地区不一致。在每个步骤中，对于给定的中央房源l，正向上下文主要由与l相同的地区中的列表组成，而负向上下文主要由与l不在同一地区中的列表组成，这种不平衡会导致学习次优的地区内相似性。 为了解决这个问题，airbnb建议添加一组从中央房源l的所属地区中抽样的随机负样本Dmn，优化目标变成：

可以先看看这样的相似度计算效果：

、

这几个确实长的差不多。。。

2.3 Cold start listing embeddings.

这部分主要讲怎么解决冷启动问题，冷启动问题是推荐系统中需要解决的关键问题，一个新用户，从来没有进行点击，搜索，浏览等操作，怎么给他做实时推荐呢？如果是新加入房源，那么这些新房源的embedding怎么得到呢？难道要从新计算一遍所有房源的embedding吗，当然是不可能了。

为了构建这些新加入的房源的embedding，房东需要提供房源的属性数据，比如价格，地区，房源类型等属性，我们找到离这个房源地理位置最近的三个现有房源，而且这三个房源在价格，房源类型等属性跟新房源相近，求得三个房源的embedding平均作为新房源的embedding。

2.4  Examining Listing Embeddings.

检验embedding的好坏，airbnb用了8亿个session进行训练，房源的向量维度为d = 32，为了检验地理位置特征是否被编码，我们先进行k-mean聚类，下图显示了在加利福尼亚州产生的100个集群，该图证实了相似位置的房源被聚集在一起。我们发现这些集群对于重新评估我们的旅游市场定义非常有用。

为了更进一步检验我们训练的embedding的好坏，我们对洛杉矶不同房源类型的房源进行余弦相似度计算，对不同价格的房源进行余弦相似度计算：

从这些表中可以看出，与不同类型和价格范围的清单之间的相似度相比，相同类型和价格范围的清单之间的余弦相似度要高得多，这也说明了学习到到embedding效果不错。

为了更好的检验，airbnb开发了检验工具：

这个工具直接求除了相近的房源，从图可以看出来这些房源确实好像。。都是树屋。。

三 、User-type & Listing-type Embeddings

使用点击会话进行训练的用户非常适合在同一地区的房源之间寻找相似之处。因此，它们适用于短期会话中的个性化，其目的是向用户显示与他们在即时搜索会话中单击的列表相似的房源。但在推荐时，用户的长期兴趣有时候也很重要，比如用户正在洛杉矶找房源，那么便可以根据其之前在纽约预订过的房源信息来进行推荐。

尽管我们可以通过上面得到的房源embedding，可以捕获到不同城市之间房源的相关性信息，但是更加通用的做法是通过不同用户在不同城市的随时间预订的房源构成预订行为Sb，来学习不同城市房源的相似性。

有了预定行为的序列，是不是也可以用skip-gram方法进行训练？答案是不行的，理由如下：

1.首先，预订会话数据Sb比点击会话数据S小得多，因为预订是不太频繁的事件。

2. 其次，过去许多用户只预订了一个房源，我们无法从长度1的会话中学习。

3. 第三，要从上下文信息中为任何实体学习有意义的embedding，数据中至少需要5-10次该实体的出现，并且平台上有很多listing_id预订的次数少于5-10次。

4. 最后，用户两次连续预订之间可能会间隔很长时间，在此期间，用户偏好（例如价格）可能会发生变化，例如由于职业变化。

归纳下来就是：数据少无法进行训练

为了解决这个问题，airbnb对房源类型进行训练，而不是对listing_id 进行训练，为了解决用户兴趣的变化，引入了user_type 这个属性，跟listing_type一起训练。

在进行训练之前，我们需要对user 和 listing进行分类，分类方法如下：

user_type映射表跟listing_type有点不同，分成了两部分，这是因为有些用户是第一次预定，所以只用前五行就行，其他情况用所有行。

好了，现在有了房源类型和用户类型的映射，现在可以根据世界顺序构建booked listing序列了：

预定的序列加入了user_type，所以就变成了上面那个，这是为了让训练到的种向量在同一空间下

同样也是用skip-gram训练：

原先是用listing-id训练，现在相当于把(user_type, listing_type)当作整体，作为序列中的一项，这个序列是同一个用户按照预定的时间顺序构建的。

请注意，每个session都由相同的user_id进行预订，但是对于单个user_id，其user_type可以随时间变化，这与相同房源的listing_types随着接收更多预订而可以随时间变化的方式类似。

当中心是user_type时，优化函数：

当中心是listing_type时，优化函数：

3.1 Explicit Negatives for Rejections

在airbnb中，房东是可以拒绝用户的，所以在上面的优化函数中，还可以加入拒绝的部分作为负样本，优化函数变为：

四  、实验部分

实时个性化主要分两边，一块是从候选集中实时对比每个候选集和用户相关listing的相似度，再将相似度分值作为特征，进一步作为排序模型的特征，对候选集进一步重排序。

如何实时收集用户短期行为，aitbnb团队采用kafka消息队列来收集用户的两个历史记录：

1. Hc: 用户过去两周内点击过的Listing id

2. Hlc:用户点击并且停留在listing详情页超过60s

3. Hs:用户过去两周内跳过的Listing id（跳过的定义是那些排在前面但是用户没有点，反而点了后面的Listing)

4. 用户添加到期望列表

5. 用户联系了但是没有预定

6. 两周内用户预定的

有了这两个规则后，就可以获得一批Listing id，然后根据这批Listing id，利用整个Hc的embedding均值和候选集Listing 的相似度表。这样就可以获得每个H*和候选listing embedding的相似度，然后把这些相似度分别作为特征，进一步的放到后一层的排序模型中对候选集进行排序。当然最后的排序模型还用到了其他的特征，比如用户类型和lsiting 类型级别的embedding相似度，以及其他的一些基础特征等等。

airbnb并没有直接把embedding similarity直接得到搜索结果，而是基于embedding得到不同的user-listing pair feature，然后输入搜索排序模型，得到最终的排序结果。

现在看下来这篇文章前面还是比较简单的embedding技巧，在实验部分就开始具备工业界的难度了，作为一个还没工作的学生，很难去理解。论文后面还介绍了排序模型，用的gbdt，这里就不做解释了。

总的来说，这又是一篇极佳的工程实践和理论创新结合的文章，想必三五年后重新阅读都会有所收获·～