本文介绍的论文题目是：《Real-time Personalization using Embeddings for Search Ranking at Airbnb》
本文论文的下载地址为：https://dl.acm.org/authorize.cfm?key=N665520
本论文获得了2018 年 KDD ADS track 的最佳论文，主要介绍了机器学习的Embedding在 Airbnb 爱彼迎房源搜索排序和实时个性化推荐中的实践，其中很多小trick具有一定的借鉴意义，咱们一起来学习学习！
文章正式开始前先提一下，论文中出现比较多的一个词是Listing，这里我们翻译为房源。
1、背景
咱们先来了解一下Airbnb搜索推荐的一些相关背景哈。
我们先来看看Airbnb的搜索结果：
点开任意一个推荐结果：
拖到底部，还有相似房源的推荐：
Airbnb中99%的房源预订就来自于搜索结果的点击和相似房源的推荐。
但是，并不是你想预订房源，就能预订到的，还要看房东是否同意。所以，整个过程如下：
所以说，这是一个双边的推荐过程，既需要考虑用户会不会预订，也需要考虑房东会不会接受预订。
为了进行更加准确的排序，Airbnb的搜索团队建立了一个Real-time实时的个性化排序模型，既考虑用户的短时兴趣，也考虑用户的长期兴趣。短时兴趣指用户在一个session中表现出的兴趣，而长期兴趣指用户在其所有历史行为中表现出的兴趣。在模型中，其精髓就在于Embedding的过程，包括Listing Embedding、User Type Embedding 和 Listing Type Embedding。
2、Listing Embedding
对房源进行Embedding，可以建模用户的短时兴趣，也可以进行相似房源的推荐。它通过用户在Session中的点击序列训练得到，这里的session定义要注意以下两点：
1）每次点击，用户需要至少在页面上停留30s，否则被视为误点击，不进行考虑。
2）用户前后两次点击时间间隔大于30min，作为切割session的依据
我们怎么来训练房源的Embedding呢？参考的是Word2Vec的做法，首先，获取一大批的Session，计做S，每一个单独的session s=(l1,l2,...,lM)包含M次房源点击。其次，借鉴Skip-Gram的做法，给定一个中心的房源，预测其前后m个点击的房源：
在Skip-Gram中，我们的目标是使如下的函数取值最大：
而概率计算如下，是一个softmax过程：
这里，V是所有的房源的集合，vl是房源的输入向量，而v'l是房源的输出向量。同一个房源，有一个输入向量和一个输出向量，我们来简单回顾一下这两个概念，通过下图便可以理解：
这里，我画了一个简单的图示，来表示输入向量和输出向量，比如，对于第2个房源来说，其输入向量就是[0.8,0.4,0.2]，对于第1个房源来说，其输出向量就是[0.3,0.7,0.1]，那么在softmax之前，第二个房源和第一个房源的相关性计算为0.8 * 0.3 + 0.4 * 0.7 + 02 * 0.1 = 0.54。也就是说，从输入层到embedding层上的权重，是我们要学习的输入向量，而embedding层到输出层上的权重，正好对应于每个房源的输出向量。
但是呢，如果每次都计算根所有房源的相关性的话，太大了，因为我们有数百万的房源，所以通常情况下，会采用负采样的方法，即随机选择一小部分作为负样本。此时，优化的目标函数变为：
上面的式子中，Dp代表的是正样本的集合，Dn代表的是负样本的集合。
这样还不算完事，我们还有许多改进效果的小trick呢！一起来看看！
trick1: Booked Listing as Global Context
在所有的训练用的Session中，有一部分发生了预订行为，我们称之为booked sessions，有一些没有发生预订行为，我们称之为exploratory sessions。对于booked sessions，无论最终预订的房源是否在Skip-Gram的窗口内，都将其放入到目标函数中。这么做出于这样的考虑：无论当前窗口是否包含预订的房源，被预订的房源都是与当前的中心房源是有关联的。
此时的目标函数变为：
而对于exploratory sessions，不做任何特殊的处理。
trick2: Adapting Training for Congregated Search.
用户在出行的时候，都是有明确的目的地的(文中的用词是market,目的地只是market的一个特例)。这样，我们在选择负样本的时候，在随机选择的基础上，可以加一批同目的地的房源负样本，记做Dmn。此时的目标函数变为：
解决冷启动问题
对于新加入的房源，训练数据中是没有它的记录的，也就是无法训练得到其Embedding。那么文中的做法是，从已有的得到embedding的房源中，选择3个同种类(种类会在下一节介绍)且距离最近(但是要在半径10miles以内)的3个房源，并用其embedding的平均值来作为新房源的embedding。 98%的新房源都可以通过这种方式来获得相应的embedding。
效果检验
最后，我们来看看获得的房源embedding的效果如何。使用8亿的session，给每个房源训练一个32维的embedding，Skip-Gram的窗口设置为5。
使用embedding对房源进行k均值聚类，加利福尼亚的房源聚类结果如下：
可以看到，基本上距离越近的房源，其embedding也相近。
通过余弦相似度计算不同种类或者不同价格的房源的相似度，可以发现如果房源的类型相同，价格相近的话，其余弦相似度也是最高的。
除了价格这些很容易定义的分类外，连建筑类型、建筑风格这种比较难以准确辨别的分类方式，我们得到的Embedding也能很好的进行区分：
3、User Type & Listing Type Embedding
用户在一个session内表现出的兴趣我们可以称为短时兴趣，但在推荐时，用户的长期兴趣有时候也很重要。比如用户正在洛杉矶找房源，那么便可以根据其之前在纽约预订过的房源信息来进行推荐。
尽管我们可以通过上面得到的房源embedding，可以捕获到不同城市之间房源的相关性信息，但是更加通用的做法是通过不同用户在不同城市的预订行为，来学习不同城市房源的相似性。
好了，思路来了，我们还是用word2vec，把用户的历史预订行为当作一个session，同样使用skip-gram来训练不就好了么？此时会存在一些问题：
1）预订序列数据相比于点击序列数据，是非常少的
2）许多用户只有过一次预订行为，这种的session是不能拿来用的
3）为了学习一个比较有效的embedding，房源至少要出现5-10次，但是有许多房源无法达到这样的标准
4）如果序列中两次预订的时间间隔过长的话，用户的偏好是会发生改变的。
好了，前三条总结来说，就是数据少，但是房源多啊。这样，我们不去学习每个具体房源的embedding，我们把房源进行归类，学习每一类房源的embedding。而为了解决第四个问题，我们把用户type考虑进来。
这样，原来的一条预订序列，此时变为了：(utype1,ltype1,utype2,ltype2,...,utypeM,ltypeM)。这样，尽管用户的偏好随时间改变了，这种改变就体现在了user type的不断变化上。
接下来的问题就是，怎么对房源和用户归类？归类规则如下：
文中举了两个例子：
细心的你可能发现了，在用户类别里，中间是画了一条线的。如果一个用户没有过预订行为，其类别只用上面五行表示，如果有预订行为，则用所有的行表示。
上文说过了，此时的序列是(utype1,ltype1,utype2,ltype2,...,utypeM,ltypeM)。我们就可以用skip-gram进行训练了：
当中心是一个user-type时，目标是如下的函数最大化：
当中心是一个listing-type时，目标是如下的函数最大化：
这样做带来了什么效果呢？user-type和listing-type得到的embedding是属于同一空间的，可以直接来计算相似度！
接下来就有意思了，在Airbnb里面，房东是可以拒绝用户的预订申请的，我们还想把这部分信息放进去，这部分就是显式的负样本：
此时的目标函数变为：
这样，我们就能通过训练得到User Type Embedding 和 Listing Type Embedding。
4、总结
本文主要介绍Airbnb实时搜索排序中的Embedding技巧。我们简单来回顾一下：
Listing Embedding
1、使用Skip-Gram方法训练embedding
2、使用负采样的方式
3、将session分为booked sessions和exploratory sessions，对于booked sessions，将最终booked的房源加入目标函数中
4、采样一批同地区的房源加入到负样本中
Listing & User Type Embedding
1、将预订序列变为(((utype1,ltype1,utype2,ltype2,...,utypeM,ltypeM))序列
2、将房东拒绝预订的房源，作为显式的负样本加入到模型训练
同时，在处理冷启动时：
1、新加入的房源，找距离最近的3个同类型的房源，用他们embedding的平均值作为新房源的embedding
2、没有过预订行为的用户，只使用表格中的前五行作为其类别
经典文章，多读多看多想！
参考文献：
1、https://zhuanlan.zhihu.com/p/55149901
2、https://zhuanlan.zhihu.com/p/57313656
3、https://www.zhihu.com/question/302288216
