陌路茶色/

Real-time Personalization using Embeddings for SearchRanking at Airbnb

    本篇论文是2018年KDD best paper,KDD(Knowledge Discovery and Data Mining) 知识发现与数据挖掘,由美国计算机协会ACM下的数据挖掘分会举办,是国际数据挖掘领域的顶级会议

ABSTRACT

    搜索排序和推荐对于主要的互联网公司来说是一个至关重要的基本问题,包括 websearch engines, content publishing websites and marketplaces。尽管分享一些公共的特征,但是在这个领域没有千篇一律的解决方案,每一个市场有自己独特的挑战。对于Airbnb,一个短租平台,在这样一个需要去优化host和guest表现的双方市场下,搜索和推荐是十分独特的,在现实生活中,用户很少会消费相同的item两次,同时一个listing在特定的时间里只能接受一个guest。这篇文章中,我们描述了listing和user的embedding技术,并且开发并部署了在搜索排序和相似推荐下的实时个性化,two channels that drive 99% of conversions(后面有提到是Search Ranking Model和Similar Listing Recommendations)。这个embedding模型是为Airbnb市场量身定制的,能够捕捉guest的短期和长期利益,做出有效的房屋listing推荐。在投入使用前,我们对embedding模型进行了严格的离线测试以及在线测试。

INTRODUCTION

    过去的搜索依赖于IR,搜索排序也依赖于你将要搜索的类型,因为现在可以被搜集到的数据增加了,这些数据打开了使用机器学习来为特定人群定制化搜索结果的可能,使用用户之前的搜索结果数据并推荐最近使用内容相似的内容给用户。

    任何一个搜索算法的目标函数因平台而变化,比如一些平台的目的是增加网站的活跃度,比如点击率,停留时间等,另外一些的目标可能是最大化转化率。在本案例中我们需要为市场双方(eg:sellers and buyers)来优化搜索结果,在很多真实的应用中,双方市场已经成为了一个可行的商业模式,此处,我们已经将社交网络范畴转变为一个分别表示supply和demand的两类型网络,行业示例包括住宿(Airbnb),乘车共享(Uber,Lyft),网上商店(Etsy)等。这些类型的市场为了繁荣发展,其content discovery 和 search ranking需要同时满足生态系统中的supply和demand。

    在Airbnb案例中,优化hosts和guests的搜索结果,意味着给定一个旅游时间以及位置的query,我们需要将这样的listing排高,即whose location, price, style, reviews, etc. are appealing to the guest and, at the same time, are a good match in terms of host preferences for trip duration and lead days。同时需要将那些因为guest的差评,宠物,停留时间,组大小等其他因素而可能拒绝guest的listing排低。实现这一目标我们使用Learning to Rank,我们将这一问题作为pairwise regression,booking(订购)作为正例,rejection作为负例,使用Lambda Rank的修改版本。

    guest在booking之前会进行多次搜索,比如会点击多个listing,并咨询多个host。Real-time Personalization的目的是向用户展示从用户开始search session时,我们认为用户喜欢的listing,相反的我们也可以获得用户不喜欢的listing。为了计算用户互动的listing和需要被排序的候选listing之间的相似性,我们提出listing embedding,从搜索会话中学习到的一个低维度的向量。我们利用相似性来为我们的Search Ranking Model创建定制化功能,并服务于Similar Listing Recommendations,这两个平台为Airbnb带来了99%的booking。

    为了在Real-time Personalization中使用即时的用户行为,我们介绍另外一种类型的embedding,在booking上训练,能够体现出用户的长期兴趣。由于旅游业务的性质,用户平均每年旅游一到两次,这样booking的信息对单个用户而言就是一个稀疏的信号,解决这一问题,我们训练embedding不针对单个用户而是一类用户,通过用户的属性将多个用户映射到一个类型上(we propose to train embeddings at a level of user type, instead of a particular user id, where type is determined using many-to-one rule-based mapping that leverages known user attributes)。同时我们在和user type embeddings相同的向量空间上学习listing type embeddings,这能够使我们在用户进行搜索的user type embeddings和需要被排序的候选listing的listing type embeddings之间进行相似性计算。(这部分有点乱)

METHODOLOGY

    接下来我们介绍在Airbnb搜索中listing推荐和listing排序任务的方法,我们会分别描述这两个不同的方法:listing embeddings for short-term real-time personalization and user-type & listing type embeddings for long term personalization。

Listing Embeddings

    给定从N个用户的点击会话中获得的一个$S$集合,每一个会话$s=(l_1,...,l_M) \epsilon S$,表示用户点击了M个listing,按时间排序,当两个连续的点击行为超过30分钟时,这个会话就会被截断。通过这个数据集我们希望学习到对于每一个独一无二的listing $l_i$的一个d维的向量表示$v_{l_i} \epsilon \mathbb{R}^{d}$,在向量空间中相似的listing位于相近的位置。
模型的目标函数是使用skip-gram学习listing的表示,通过最大化整个训练集$S$上目标函数$L$,被定义如下:
屏幕快照 2019-10-09 下午8.27.50.png
其中$v_l$和$v_{l}^{'}$为listing $l$的输入和输出向量表示,超参数$m$被定义为点击的listing的上下文长度,$V$为数据集中listing的大小,从公式(1)和公式(2)中可以看出该方法建模listing的点击序列的时间上下文,有相似上下文(在搜索会话中有相似的相邻listing)的listing将会有相似的表示
对于一个比较大的词表而言,公式(2)的计算方法是不可行的,一个可选的方法是使用负采样(参考Stanford cs224 note1),可以大幅度的减少计算复杂度。负采样具体的如下,我们为点击listing $l$生成一个正样本对$(l,c)$集合$D_p$,其中上下文$c$表示该listing l对应的回话序列窗口大小m内的序列,生成一个负样本对$(l,c)$集合$D_n$,其中$c$是在整个listing表$V$中随机采样n个listing,对应的优化目标由公式(2)变为如下:
屏幕快照 2019-10-09 下午8.49.39.png
将被学习的参数$\theta $是$v_l$和$v_c$,通过随机梯度下降。
Booked Listing as Global Context: 将点击序列集$S$分为两部分booked sessions 和exploratory sessions,booked sessions表示通过前面的点击序列后用户booking了一个listing,exploratory sessions表示用户只发生了点击行为,从捕获上下文相似的角度来看,这两类序列都是有用的。对于booked sessions,优化函数中的每一步我们不仅要预测和其相邻的listing,而且还要预测最后的booked listing,因此我们增加booked listing作为全局上下文,即不管booked listing是否出现在中心listing的上下文,都将其作为上下文。对于booked sessions,其embedding更新规则变为:
屏幕快照 2019-10-09 下午8.59.04.png
其中$v_{l_b}$表示的是booked listing $l_b$的embedding,对于exploratory sessions,其更新规则仍旧是公式(3)的优化目标。
下图展示了listing embedding如何从booked sessions中使用大小为$2n+1$的滑动窗口学习,在每一步中中心listing $v_l$的embedding被更新通过从$D_p$中预测上下文$v_c$以及booked listing $v_{l_b}$的embedding。
屏幕快照 2019-10-09 下午9.07.27.png
Adapting Training for Congregated Search: 线上旅游的用户典型的搜索范围只会集中在一个小的区域内,例如他们呆的地方,这样的后果是$D_p$中包含的listing会是从一个相同的market中得到的(意思就是说比如用户想去北京旅游,那么他集中搜索的listing可能就是北京某个区的房屋,即$D_p$中的listing),而$D_n$中包含的大部分listing就不会和$D_p$中一样从相同的market中得到。我们发现这样会导致market内部的listing之间相似度无法学习得很好,于是增加了一个负样本集$D_{m_n}$,该样本集中的数据是从中心listing $l$的market中采样得到(当然不会包括在$D_p$中)。
【捋一下:也就是说负样本集$D_n$不是取自同一个market,但正样本却是,这样会影响market内部的相似性学习,因此引入一个中心listing对应market的内部负样本集$D_{m_n}$】
优化目标函数变为:
屏幕快照 2019-10-09 下午9.31.09.png
Cold start listing embeddings: 冷启动listing embedding问题(即host新发布的listing),论文中利用新的listing对应的元数据去发现3个地理位置最近(在10英里半径内)的3个listing,这3个listing和新的listing有相同的listing类型,属于同一价格桶内等,然后将这3个listing的embedding取平均作为新listing的embedding,使用这种方法能够覆盖超过98%的新listing。
Examining Listing Embeddings: 去评估listing的哪些特征被通过embedding来捕捉到,我们使用公式(5)在8亿点击会话上训练32维的embedding。首先,通过k-means聚类学习到的embedding来评估地理相似信息是否被编码到embedding中,下图显示对California的listing聚100个类的结果:
屏幕快照 2019-10-09 下午9.49.53.png
对不同的类别之间进行平均余弦相似度分析(相关系数),...(这个没看懂)
对于每个特征也可以通过显示指定listing最相关的k个listing来分析该特征是否被编码进embedding中。

User-type & Listing-type Embeddings

    Listing embeddings部分对于在相同market内的listing之间的相似性效果非常好,非常适合于短期会话,去定制化用户在短期的搜索会话中被点击listing的相似listing。然而,上述embedding只用到了会话的短期信号,用户的历史长期信息也是有用的,比如,给定一个正在搜索Los Angeles的listing的用户,以及该用户过去在New York和London booking的历史,去推荐那些和之间booked的listing相似的listing将是有用的。
通过学习用户长期以来booked的listing序列可以捕获cross-market的相似性,假设给定一个从N个用户中获取的booking会话集合$S_b$,其中每一个booking session $s_b=(l_{b_1},...,l_{b_M})$被定义为用户booked的按时间排序的listing序列,试图去使用该序列学习每一个listing_id的embedding $v_{l_{id}}$有如下多方面的挑战:
• First,booking session数据非常小,因为booking不经常发生
• Second,许多用户仅仅booked一次,无法从一次中进行学习
• Third,对一个实体从上下文信息中学习一个有意义的embedding,该实体与上下文共现次数至少在5到10次,但是很多listing被booked少于5到10次
• Finally,长时间的间隔可能会导致一个用户连续的booking失效,比如价格,用户偏好,用户职业等
在实际中解决这些问题,我们提出学习listing_type级别的embedding来代替listing_id的embedding,给定某些listing_id的元数据,比如位置,价格,类型,容量等,使用规则比如下表,将其映射到listing_type上。
屏幕快照 2019-10-09 下午10.27.50.png
例如:an Entire Home listing from U S that has a 2 person capacity, 1 bed, 1 bedroom & 1 bathroom, with Average Price Per Night of \$60.8, Average Price Per Night Per Guest of \$29.3, 5 re- views, all 5 stars, and 100% New Guest Accept Rate
将被映射为

                US_lt1_pn3_pg3_r3_5s4_c2_b1_bd2_bt2_nu3

对应到上表中,Country为US,Listing Type为Bucktes 1,per Night为Buckets 3...
同理,为了解决用户随时间变化的偏好我们提出学习user_type embedding和listing_type embedding一样,对应的表如下所示:
屏幕快照 2019-10-09 下午10.37.04.png

去学习user_type和listing_type的embedding,我们将user_type增加到booking sessions中,定义一个从N个用户的$N_b$个booking sessions组成的集合$S_b$,其中每个会话$s_b=(u_{type_1}l_{type_1},...,u_{type_M}l_{type_M}) ∈ S_b$作为一个booking事件的序列,按时间排序tuple (user_type,listing_type),注意每一个会话包含有相同user_id的booking,但是user_id的user_type可能会改变多次,相似的,listing_type也可能会改变多次。
对应的和公式(3)定义的优化目标一样,当中心item是user_type($u_t$)时:
屏幕快照 2019-10-09 下午10.51.08.png
当中心item是list_type($l_t$)时:
屏幕快照 2019-10-09 下午10.51.40.png
其中$D_{book}$中包含的是用户最近历史的user_type和listing_type,保证在item的时间戳内,$D_{neg}$为随机的实例。
因为会出现用户booking listing后,由于用户以前的差评等信息导致host拒绝用户booking的实例,因此在目标函数中加入rejection集的采样,rejection集合$D_{reject}$由user_type或listing_type对$(u_t,l_t)$组成,该对包含了一个拒绝事件。
相应的,当中心item是user_type($u_t$)时:
屏幕快照 2019-10-09 下午11.04.08.png
当中心item是list_type($l_t$)时:
屏幕快照 2019-10-09 下午11.04.37.png

EXPERIMENTS

...

THINKING

1.Listing embeddings部分的平均余弦相似度怎么理解,这部分我们没有做记录
2.market的理解?
一小片区域???
3.User-type & Listing-type Embeddings中的user_type和listing_type是混在一起训练,那序列是什么?
是按照tuple的方式进行排序吗,Airbnb如何解决Embedding的数据稀疏问题?中提到是这样的,在评论中说有的会话长度为1的解决,我觉得如果按照这种方式,就不会出现长度为1的会话了,因为一个listing_type一定跟一个user_type。

留下一条评论

暂无评论