以下文章来源于搜索与推荐Wiki ,作者Thinkgamer

其实在19年初的时候大概看了一下这篇论文,但当时其实理解的并不深,今天再读的时候发现这里边其实包含了很多东西,不仅是学术性的目标函数优化,也包括工程性的取舍和特征的构造。

本文分为两部分,第一部分主要介绍论文,第二部分谈从中的收获和启发,如果你对论文比较熟悉的话可以直接阅读第二部分。

第一部分

引言

Airbnb于2018年提出了论文《Real-time Personalization using Embeddings for Search Ranking at Airbnb》,可谓是Embedding技术在工程实践中的一次大的进步,虽然论文已经发表两年了,但每次读都会有不一样的收获,作为深度学习的「核心操作」之一,Embedding技术不仅能够将大量的稀疏特征转换成稠密特征,便于输入深度学习网络,而且能够通过Embedding将物品语义进行编码,用来计算物品的相似度,进度i2i(item to item)的推荐。

论文主要提出的是item的Embedding算法和优化方案,基于不同类型和时间窗口的房源序列构建Embedding,以致于能够捕获用户的短期(short-term)和长期(long-term)兴趣偏好。其本质是改造Word2vec的优化目标函数,使用的是其中Skip-gram模型(另一种是词袋模型,bag-of-word)

背景

Airbnb是一个在线约定房源的网站,主要是给用户提供不同地点的房源列表(需要注意的是在论文中房源使用的是「 list」进行表示,可能国内朋友阅读的时候会有点出戏),如下所示,在搜索某个地点的房源之后,展示列表为:

在点击某个具体的房源之后,也会有相似房源推荐,如下所示:

上述的两个部分,其实也是Airbnb进行论文中Embedding评估的业务场景。

基于用户短期兴趣的房源Embedding构建方法

文章中提到使用8亿的搜索点击房源session作为训练集构建房源的embedding(当然足够大的数据集构造出的Embedding也更加准确,表达信息也更加准确)。

目标函数的进化

定义S为N个用户的个click sessions,每个session为:s = (l_1, …, l_M) \in S,论文中特意提到如果一个用户的两次点击之间超过30分钟进行session的截断,最后为每个房源(list)生成一个d 维的embedding向量,v_{l_i} \in R^d,这里使用word2vec中的skip-gram,最大化目标函数为:

L = \sum_{s \in S} \sum_{l_i \in s} ( \sum_{ -m \geq j \leq m, i \neq 0} log \, P(l_{i+j} | l_i))

其中 P(l_{i+j} | l_i)可以通过softmax来进行定义和求解:

P(l_{i+j} | l_i) = \frac {exp(v_{l_i}^T v_{l_{i+j}}’)}{ \sum_{l=1}^{|V|} exp(v_{l_i}^T v_{l}’)}

其中 v_l表示的是房源 l的输入向量, v’_l表示的是房源 l的输出向量表示, m表示的上下文滑动的窗口大小,V表示的是所有房源的集合。

在实际的计算中由于 V很大,基于整体数据的负样本进行训练,在有限的计算资源下,将会消耗很多的资源和计算时间,因此会进行一定程度的负采样。

这里使用D_p 表示正样本对(l,c),即房源和其上下窗口内的房源c, D_n表示负样本对(l,c),负样本从整个房源集合中进行抽取。增加随机负采样后,优化的目标函数变为:

\underset{\theta}{ arg \, max } \sum_{(l,c) \in D_p} log \frac{1}{1+e^{-v_c’ v_l}} + \sum_{(l,c) \in D_n} log \frac{1}{1+e^{v_c’ v_l}}

求解参数 \theta可以使用随机梯度上升法(stochastic gradient ascent)。

用户的行为序列其实分为两类:

  • 经过一系列点击之后有预定房源的行为
  • 经过一系列点击之后没有预定房源的行为

用户短期内预定房源的行为其实在一定程度上和之前的搜索点击行为都有强相关的关系,因此将预定房源的行为作为一个全局的动作加入到每个session中,则需要优化的目标函数转变为:

\underset{\theta}{ arg \, max } \sum_{(l,c) \in D_p} log \frac{1}{1+e^{-v_c’ v_l}} + \sum_{(l,c) \in D_n} log \frac{1}{1+e^{v_c’ v_l}} + log \frac{1}{1+e ^{- v’_{l_b} v_l}}

其中 表示预定的房源embedding表示,下图展示了预定房源的行为是如何加入到一个session中的。

用户在进行搜索房源的时候往往是集中在一个地点的,因此正样本D_p 很大概率上是同一地点附近的房源,但是负采样的样本D_n 则是基于全局进行采样的,即负样本不一定出现在同一个地方,这会造成在学习同一地点附近房源embedding时的平衡性,因此在目标函数中加入了同一市场的负采样,如下所示:

\underset{\theta}{ arg \, max } \sum_{(l,c) \in D_p} log \frac{1}{1+e^{-v_c’ v_l}} + \sum_{(l,c) \in D_n} log \frac{1}{1+e^{v_c’ v_l}} + log \frac{1}{1+e ^{- v’_{l_b} v_l}} + \sum_{(l, m_n) \in D_{mn}} log \frac{1}{ 1+ e^{v’_{m_n}v_l} }

房源Embedding中的冷启动问题

Airbnb每天都有新上的房源,但是因为其没有出现在训练集中,导致无法产出其embedding,这里采用的解决办法是最相近的三个房源的平均embedding进行表示

衡量房源的相近程度可以采用位置、价格、房源类型等,且要求距离在10英里内。

这里可以带给我们很多思考,不仅对于新物品,同样对于新用户,依旧可以采用其属性相近的n个用户的平均embedding作为其embedding表示

房源Embedding 实验

8亿的搜索点击房源session作为训练集构建房源的embedding,每个房源Embedding的维度为32(后文也提到了32维实验效果比较好,而且节省存储空间)。在进行数据构造时,移除了用户停留时间小于30秒的房源,保留了房源出现次数大于等于2的。

1、通过K-Means对房源Embedding进行聚类,对于房源的重新定价很有参考意义

2、评估了洛杉矶附近不同类型房源的Embedding相似度(Table 1)和不同价格区间房源的Embedding相似度(Table 2),从实验结果中可以看出相同类型或者相同价格范围内的房源平均相似度要明显高于不同类型或者不同价格范围的房源平均相似度,因此说明emedding是有效的

Embedding相似度评估

3、对于房源的一些属性信息可以从元数据中获得,但是一些信息并不能从元数据中获得,比如风格、带给人的感觉等,因此开发了一个相似度探索工具(Figure 4)进行离线的观察和评估(更多关于相似度探索工具的功能参考:https://youtu.be/1kJSAG91TrI)

Embedding Evaluation Tool

基于用户长期兴趣的房源Embedding构建方法

上文中介绍了如何基于用户短期兴趣的房源Embedding构造方法,但是因为Airbnb平台业务的特殊性,用户旅行地不是唯一的,因此提出了基于用户长期兴趣的房源Embedding构造方法:基于用户预定房源的序列进行Embedding的构造。但是有几方面的挑战:

  • 1、预定数据相对点击数据要稀疏的多
  • 2、很多用户在过去时间段内只有一个预定
  • 3、如果要学习list(房源)的embedding,至少需要该房源出现5-10次,但是通过预定构建的数据集很多都小于5-10次
  • 4、用户的两次预定之间相差时间较长,这期间用户的兴趣会发生变化

用户类型和房源类型的定义

为了解决上边提到的问题,这里使用学习房源的类型embedding来代替房源的embedding,使用学习用户类型embedding来代替用户的embedding。

如下图所示,比如美国的一个房源,其属性为:

  • listing type:entire home
  • per night:$60.8
  • per guest:$29.3
  • number reviews:5
  • list 5 star%:全部是5 star
  • capacity:2 person
  • num beds:1
  • bedroom:1
  • bathroom:1
  • new guest accept:100%

那么其类型可以表示为:US{\_lt1\_pn3\_pg_3\_r_3\_5s_4\_c_2\_b_1\_bd_2\_bt_2\_nu_3}。

同样对于一个用户,其属性为:

  • market:San Franciso
  • Language:English
  • Device Type:MacBook laptop
  • Full Profile:full profile
  • Profile Photo:user photo
  • Number Bookings:0
  • Per night:$52.52
  • Per Guest:$31.85
  • capacity:2.33
  • num reviews:8.24
  • listing 5 star%:76.1%
  • guest 5 star%:83.4%

那么其类型可以表示为:SF{\_lg_1\_dt_1\_fp_1\_pp_1\_nb_1\_ppn_2\_ppg_3\_c_2\_nr_3\_l5s_3\_g5s_3}

注意的是,对于第一次预定的新用户,使用表中的前5行进行用户类型的定义,这在一定程度上可以缓解用户冷启动问题

房源和用户的类型映射

目标函数

S_b 包含了N_b 个预定序列,涉及了N个用户,每个session可以表示为s_b = (u_{type1}l_{type1}, …, u_{typeM}l_{typeM}):,这里需要注意的是,用户在预定房源时,其属性是变化的,因此同一用户的不同房源预定应该根据实际情况进行不同类型的划分。

定义的目标函数和上述一致,但是这里需要更新的中心不是固定的,可能是房源也可能是用户类型,因为在论文中进行处理时将其进行了展开,用户类型和房源类型是等价的。如下图5(a)所示。如果更新的中心是用户类型,目标函数为:

\underset{\theta}{ arg \, max } \sum_{(u_t,c) \in D_{book}} log \frac{1}{1+e^{-v_c’ v_{u_t}}} + \sum_{(u_t,c) \in D_n} log \frac{1}{1+e^{v_c’ v_{u_t}}}

如果更新的中心是房源类型,目标函数为:

\underset{\theta}{ arg \, max } \sum_{(l_t,c) \in D_{book}} log \frac{1}{1+e^{-v_c’ v_{l_t}}} + \sum_{(l_t,c) \in D_n} log \frac{1}{1+e^{v_c’ v_{l_t}}}

用户类型or房源类型目标函数定义的示意图但是用户进行房源预定时,房主也可以根据用户的情况进行拒绝,因此在目标函数上增加了被拒绝的优化项,其对应的图示如上图中的(b)所示,其目标函数如下所示:

如果更新的中心是用户类型:

\underset{\theta}{ arg \, max } \sum_{(u_t,c) \in D_{book}} log \frac{1}{1+e^{-v_c’ v_{u_t}}} + \sum_{(u_t,c) \in D_n} log \frac{1}{1+e^{v_c’ v_{u_t}}} + \sum_{(u_t,l_t) \in D_{reject}} log \frac{1}{1+e^{v_{u_t}’ v_{l_t}}}

如果更新的中心是房源类型:

\underset{\theta}{ arg \, max } \sum_{(l_t,c) \in D_{book}} log \frac{1}{1+e^{-v_c’ v_{l_t}}} + \sum_{(l_t,c) \in D_n} log \frac{1}{1+e^{v_c’ v_{l_t}}} + \sum_{(u_t,l_t) \in D_{reject}} log \frac{1}{1+e^{v_{u_t}’ v_{l_t}}}

因为进行session构建时,将用户类型和房源类型进行了展开,将其embedding映射到同一空间内,因此可以通过计算用户类型和房源类型的embedding余弦相似度进行候选池的召回,如下图所示。

相似度召回> 在构造预定房源的session时,因为预定房源的行为较少,因此对此进行了加强,采用了过采样(重复正样本的比例,与之对应的是欠采样)的技术,比例为5倍,关于过采样和欠采样会对模型产生怎么样的影响可以参考: https://www.zhihu.com/question/269698662

实验

  • 基于用户短期兴趣进行房源Embedding的构造:8亿的搜索点击房源session作为训练集构建房源的embedding,每个房源Embedding的维度为32(后文也提到了32维实验效果比较好,而且节省存储空间)。在进行数据构造时,移除了用户停留时间小于30秒的房源,保留了房源出现次数大于等于2的。
  • 基于用户长期兴趣进行房源Embedding的构造:使用5千万用户的预定数据进行预定sesssion的构建,同时对正样本进行了5倍的过采样。
  • 实验表明每天重新对房源进行embedding学习要比增量训练效果好
  • 试验参数:embedding维度32,滑动窗口为5,迭代次数为10
  • 训练平台:C版本的word2vec,基于MapReduce进行训练,300个mappers 1个reduce,给予AirFlow进行pipline的构建

离线评估方法

获取用户最近点击的房源列表和需要进行排序的候选池房源,其中候选池中必定包含用户最终预定的房源,分别计算候选池中房源和用户第次点击的房源相似度进行排序,观察预定房源在其中的位置信息,最终结果如下图所示:

离线评估图中不同颜色的线分别对应不同的优化目标函数,可以看出增加预定房源信息和负采样的效果最好。

在线实验中,也通过AB测试验证了效果是要比base组提升很多。

如何实时使用Embedding数据

论文中得到了房源的embedding、用户类型embedding、房源类型embedding,但Airbnb并没有直接拿embedding作为特征进行使用,而是进行了转化和构造。其排序模型为GBDT( https://github.com/yarny/gbdt),评估指标为:NDCG,训练集和测试集的比例为:8:2。

其构造的特征为:

构造的特征其中字符表示的含义为:

比如其中EmbClickSim特征的计算方式为(同类型的计算方式类似):

EmbClickSim(l_i, H_c) = \underset{ m \in M }{ max \, cos } (v_{l_i}, \sum_{l_h \in m, l_h \in H_c} v_{l_h})

EmbLastLongClickSim特征计算方式为:

EmbLastLongClickSim(l_i, H_{l_c}) = cos(v_{l_i}, v_{l_{last}})

UserTypeListingTypeSim特征计算方式为:

UserTypeListingTypeSim(u_t, l_t) = cos(v_{u_t}, v_{l_t})

针对特征的实验如下图所示:

特征的实验

  • 上图中左侧部分,可以看出EmbClickSim越大,推荐的列表得分越高
  • 上图中中间部分,可以看出EmbSkipSim越大,推荐的列表得分越高
  • 右图部分,可以看出当UserTyle和ListingType越相似时,推荐的列表得分越高

下图展示了增加Embedding构造的相关特征和不增加这些特征的AB实验数据。

启发:

  1. 通过对传统的Word2vec算法进行改造,完成对用户和房源的Embedding,并针对数据稀疏性问题,利用用户和房源的属性进行数据的聚合,这些思路值得借鉴,不仅针对老用户,在新用户冷启动的处理上也有一定的借鉴意义
  2. 在生成Embedding目标函数的过程中,引入与业务强相关的目标项,使算法改造与公司业务和商业目标强结合,值得学术导向的算法工程师的学习。

第二部分

其实如果没有太多的实际经验,在论文中收获的东西可能是有限的,如果在阅读论文的过程中能够结合实际的业务经验,你对发现其实其中有很多能够带来启发的点,或许一些点你已经在实际中进行了应用,而且取得了不错的效果,但还是有一些点值得思考和借鉴的,下面将陈列我在读论文的过程中的收获(包含曾经知道的和已经使用的),希望你也能感同身受,颇受启发。

下面的点按照阅读论文过程中看到的进行陈列,无须在乎其先后

关于业务的评估指标

其实在做模型的过程中,会涉及很多指标可以参考,不仅有离线指标,还有在线指标�