airbnb在KDD 2018上开放了它们的方法:《Real-time Personalization using Embeddings for Search Ranking at Airbnb》, 我们来看下：

介绍

在过去十年的搜索体系中（通常基于经典的IR），已经出现了许多机器学习技术，尤其是在搜索排序领域。

任何搜索算法的目标（objective）都依赖于自身的平台。其中，一些平台的目标是增加网站参与度（engagement：比如在搜索之后的新闻文章上的点击、消费），还有的目标是最大化转化率（conversions: 比如：在搜索后的商品或服务的购买），还有的目标是需要为双边市场主体（比如：购买者和零售商）优化搜索结果。这种双边市场会合成一个可行的商业模型。特别的，我们会从社交网络范式转移到一个关于不同供需类型参与者组成的网络中。工业界的示例有：住房（airbnb），出行共享（Uber, Lyft），在线电商（Etsy）等。为这种类型的市场进行内容发现和搜索排序，需要满足供需双方，从而保持增长和繁荣。

在Airbnb中，需要对主人（hosts）和客人（guests）进行最优化搜索，这意味着，给定一个输入query，它带有位置（location）和旅行日期（trip dates），我们必须为客人带有位置、价格、风格、评论等出现给客户排序高的listings，同时，它又能很好地匹配主人关于旅行日期(trip dates)和交付期（lead days）的偏好。也就是说，我们需要发现这样的listings：它可能因为差评、宠物、逗留时间、group size或其它因素而拒绝客户，并将这些listings排的序更低。为了达到该目的，我们会使用L2R进行重排序。特别的，我们会将该问题公式化成pairwise regression问题（正向：预订bookings，负向：拒绝rejections）。

由于客户通常会在预测前浏览多个搜索结构，例如：点击多个listing，并在它们的搜索session内联系多个主人，我们可以使用这些in-session信号（例如，点击（clicks）、与主人的联系（host contacts）等）进行实时个性化，目标是给用户展示与search session相似的多个listings。同时，我们可以使用负向信号（比如，高排名listings的跳过次数），从而展示给客人尽可能少的不喜欢列表。

3.方法

下面，我们引入了listing推荐、以及listing在搜索的中ranking。我们会描述两个不同的方法，例如：对于短期实时个性化的listing embeddings、以及用于长期个性化 user-type & listing-type embeddings。

3.1 Listing embeddings

假设，给定从N个用户中获取的S个点击sessions的一个集合S，其中每个session \(s = (l_1, ..., l_M) \in S\)被定义成：一个关于该用户点击的M个listing ids连续序列。当在两个连续的用户点击之间超过30分钟的时间间隔时，启动一个新的session。给定该数据集，目标是为每个唯一的listing \(l_i\)学习一个d维的real-valued表示: \(v_{l_i} \in R^d\)，以使相似的listing在该embedding空间中更接近。

更正式的，该模型的目标函数是使用skip-gram模型，通过最大化搜索sessions的集合S的目标函数L来学习listing表示，L定义如下：

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

…(1)

从被点击的listing \(l_i\)的上下文邻居上观察一个listing \(l_{i+j}\)的概率\(P(l_{i+j} \mid l_{i})\)，使用softmax定义：

\[P(l_{i+j} | l_i) = \frac{exp(v_{l_i}^T v_{l_{i+j}}')} {\sum\limits_{l=1}^{|V|} exp(v_{l_i}^T v_l')}\]

…(2)

其中\(v_l\)和\(v_l'\)是关于listing l的输入和输出的向量表示，超参数m被定义成对于一个点击listing的forward looking和backward looking上下文长度，V被定义成在数据集中唯一listings的词汇表。从(1)和(2)中可以看到提出的方法会对listing点击序列建模时序上下文，其中具有相似上下文的listing，将具有相似的表示。

计算(1)中目标函数的梯度\(\Delta L\)的时间，与词汇表size \(\mid V \mid\)成正比，对于大词汇表来说，通常有好几百万listing ids，是不可行的任务。做为替代，我们会使用negative-sampling方法，它能极大减小计算复杂度。Negative-sampling可以如下所述。我们会生成一个positive pairs (l, c)的集合\(D_p\)，其中l表示点击的listings，c表示它的上下文，然后从整个词典V中随机抽取n个listings来组成negative pairs (l, c)的集合\(D_n\)。优化的目标函数变为：

\[argmax_{\theta} \sum\limits_{(l,c) \in D_p} log \frac{1}{1+e^{-v_c'v_l}} + \sum\limits_{(l,c) \in D_n} log \frac{1}{1+e^{v_c'v_l}}\]

…(3)

其中要学的参数\(\theta\)是：\(v_l\)和\(v_c\), \(l, c \in V\). 优化通过随机梯度上升法（SGA）完成。

将预订Listing看成全局上下文。 我们将点击session集合S划分为：

• 1) 预订型sessions（booked sessions)， 例如，点击sessions会以用户在某一listing上进行预订而结束
• 2) 探索型session（exploratory session），例如，点击sessions最后不会以预订结束，用户仅仅只是浏览.

对于捕获上下文相似度的角度来说两者都有用，然而，预订型sessions可以被用于适配以下的最优化：在每个step上，我们不仅仅只预测邻居clicked listing，也会预测booked listing。这种适配可以通过将预测的listing作为全局上下文（global context）来完成，从而能总是被预测，不管是否在上下文窗口内部。因此，对于预订型sessions来说，embedding的更新规则变为：

\[argmax_{\theta} \sum\limits_{(l,c) \in D_p} log \frac{1}{1+e^{-v_c'v_l}} + \sum\limits_{(l,c) \in D_n} log \frac{1}{1+e^{v_c'v_l}} + log \frac{1}{1+ e^{-v_{l_b}' v_l}}\]

…(4)

其中，\(v_{l_b}\)是booked listing \(l_b\)的embedding。对于 探索型session来说，更新仍会由（3）的最优化进行管理。

图1

图1展示了listing embeddings是如何从预定型sessions中进行学习的，它会使用一个滑动窗口size=2n+1, 从第一个clicked listing到最后的booked listing滑动。在每一步，central listing \(v_l\)的embedding会被更新，以便它能预测context listing \(v_c\)的embedding、以及booked listing \(v_{l_b}\)的embedding。随着窗口滑入和滑出上下文集合，booked listing总是会作为全局上下文存在。

自适应训练. 在线旅行预定网站的用户通常会在单个market(例如，他们想逗留的地理位置)内进行搜索。因此，\(D_p\)会有较高的概率包含了相同market中的listings。在另一方面，归因于negative sampling，\(D_n\)包含的大多数listings与\(D_p\)包含的listings很大可能不会是相同的markets。在每一步，对于一个给定的central listing l，positive上下文几乎由与l相同market的listings所组成，而negative上下文几乎由与l不同market的listings组成。为了解决该问题，我们提议添加一个随机负样本集合\(D_{m_n}\)，它从中心listing l的market上抽样得到：

\[argmax_{\theta} \sum\limits_{(l,c) \in D_p} log \frac{1}{1+e^{-v_c'v_l}} + \sum\limits_{(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\limits_{(l,m_n) \in D_{m_n}} log \frac{1}{1+e^{v_{m_n}'}v_l}\]

…(5)

其中要学习的参数\(\theta\)有：\(v_l\)和\(v_c\), \(l,c \in V\)。

冷启动listing的embeddings. 每天都有新的listings被主人创建，并在Airbnb上提供出租。这时候，这些listings不会有一个embedding，因为他们在训练数据中没有对应的点击sessions。为了为这些新的listings创建embeddings，我们打算利用其它listings的embeddings。

在listing创建时，需要提供listing的信息，比如：位置，价格，listing type等。我们利用这些关于listing的meta-data来发现3个地理位置上接近的listings（在10公里内），这些listings具有embeddings，并且具有与新listing相同的listing-type，并与新listing属于相同的价格区间（比如：每晚20-25美刀）。接着，我们使用3个embeddings计算平均向量，来构成新的listing embedding。使用该技术，我们可以覆盖98%的新listings。

图2

表1:

表2

检查listing embeddings.。为了评估由embeddings所捕获的listings的特性，我们检查了d=32维的embeddings，它使用公式(5)在800w点击sessions上进行训练。首先，通过在学到的embeddings上执行k-means聚类，我们对地理相似度进行评估。图2展示了生成的在加州的100个聚类，证实相似位置的listing会聚在一起。我们发现这些聚类对于重新评估我们的travel markets的定义非常有用。接着，我们评估了来自洛杉矶的不同listing-type间（表1）、以及不同价格区间（表2）间的listings的平均cosine相似度。从这些表中可以观察到，相同type和相同价格区间间的cosine相似度，要比不同type和不同价格区间间的相似度要高很多。因此，我们可以下结论，两个listing特性在被学到的embeddings中可以很好地编码。

图3

有一些listing特性（比如价格）不需要学习，因为他们会直接从listing的meta-data中被抽取；而其它类型的listing特性（比如：房屋结构:architecture、装修风格:style、感受:feel），很难以listing features的形式进行抽取。为了评估这些特性是否由embeddings捕获，我们检查了在listing embedding空间中单一房屋结构的listings的k近邻。图3展示了这个case，对于左侧的一个单一architecture的listing来说，最相似的listings具有相同的style和architecture。为了能在listing embedding空间上进行快速和方便的探索，我们开发了一个内部的相似度探索工具，如图4所示。

图4

该工具的演示在https://youtu.be/1kJSAG91TrI, 展示了可以发现相同architecture（包括：houseboats, treehouses, castles, chalets, beachfront apartments）的相似listings。

3.2 User-type & Listing-type embeddings

在3.1节描述的是Listing embeddings。它使用clicked sessions进行训练，能很好地发现相同market间的listings相似度。同样的，他们更适合短期(short-term)、session内（insession）、个性化的需求，它们的目标是给用户展示与在搜索session期间点击的listing相似的listings。

然而，除了in-session personalization，（它基于在相同session内发生的信号构建），基于用户长期历史的信号对于个性化搜索来说很有用。例如，给定一个用户，他当前在搜索洛杉矶内的一个listing，过去他在纽约、伦敦预定过，给他推荐之前预定过的listings相似的listings是很有用的。

当在由点击训练得到的listing embeddings中捕获一些cross-market相似度时，学习这种cross-market相似度一个原则性方法是，从由listings构成的sessions中学习。特别的，假设，我们给定一个从N个用户中获取的booking sessions的集合\(S_b\)，其中每个booking session \(s_b = (l_{b1}, ..., l_{b_M})\)被定义成：由用户j按预定(booking)的时间顺序排列的一个listings序列。为了使用该类型数据来为每个listing_id，学习embeddings \(v_{l_{id}}\)，会有以下多方面挑战：

• 1.booking sessions数据\(S_b\)比click sessions数据S要小很多，因为预定是低频事件。
• 2.许多用户在过去只预定单个listing，我们不能从session length=1中进行学习
• 3.为了上下文信息中的任意实体学习一个有意义的embeddings，至少需要该实体出现5-10次，然而在平台中的许多listing_ids会低于5-10次。
• 4.最后，由同用户的两个连续预定可能会有很长时间的间隔，这时候，用户偏好（ 比如：价格点）可能会随职业发展而变化。

为了解决这些非常常见的问题，我们提出了在listing_type级别学习embeddings，而非listing_id级别。给定一个特定listing_id的meta-data，比如：位置，价格，listing-type，空间，床数等，我们使用一个在表3中定义的基于规则的映射，来决定listing_type。

表3

**例如，一个来自US的Entire Home listing（lt1），它是一个二人间(c2)，1床（b1），一个卧室(bd2) & 1个浴室(bt2)，每晚平均价格为60.8美刀(pn3)，每晚每个客人的平均价格为29.3美刀(pg3)，5个评价(r3)，所有均5星好评(5s4)，100%的新客接受率（nu3），可以映射为：listing_type = U S_lt1_pn3_pg3_r3_5s4_c2_b1_bd2_bt2_nu3. **分桶以一个数据驱动的方式决定，在每个listing_type分桶中最大化覆盖。从listing_id到一个 listing_type的映射是一个多对一的映射，这意味着许多listings会被映射到相同的listing_type。

表4:

为了解释用户随时间变化的偏好，我们提出在与listing_type embedding相同的向量空间中学习user_type embeddings。user_type使用一个与listings相似的过程来决定，例如，利用关于user和它之前预订记录的metadata，如表4定义。例如，对于一个用户，他来自San Francisco(SF)、带有MacBook笔记本（dt1）、说英文(lg1)、具有用户照片资料(pp1)、83.4%平均5星率(l5s3)、他在过去有3个预订(nb1)、其中关于订单（booked listings）的平均消费统计为：52.52美刀 (每晚平均价格: Price Per Night), 31.85美刀 (每晚单客户平均价格：Price Per Night Per Guest), 2.33(Capacity), 8.24(平均浏览数：Reviews）、76.1%（5星好评单：Listing 5 star rating)。对于该用户所生成的user_type是：SF_lg1_dt1_fp1_pp1_nb1_ppn2_ppg3_c2_nr3_l5s3_g5s3. 当为训练embeddings生成booking sessions时，我们会一直计算user_type直到最近的预定。对于那些首次做出预定的user_type的用户，可以基于表4的第5行进行计算，因为预测时我们没有关于过去预定的先验信息。这很便利，因为对于为user_types的embeddings，它基于前5行，可以用于对登出用户或者没有过往预定记录的新用户进行冷启动个性化。

训练过程. 为了学习在相同向量空间中的user_type和listing_type的embeddings，我们将user_type插入到booking sessions中。特别的，我们形成了一个\(S_b\)集合，它由N个用户的\(N_b\)个booking sessions组成， 其中每个session \(s_b = (u_{type_1} l_{type_1}, ..., u_{type_M} l_{type_M}) \in S_b\)被定义成一个关于booking事件的序列，例如：按时间顺序排列的(user_type, listing_type)元组。注意，每个session由相同user_id的bookings组成，然而，对于单个user_id来说，他们的user_types可以随时间变化，这一点与下述情况相似：相同listing的listing_types会随着他们接受越来越多的bookings按时间变化。

目标函数与(3)相似，会替换listing l，中心项需要使用\(user\_type(u_t)\)或者\(listing\_type(l_t)\)进行更新，取决于在滑动窗口中捕获的项。例如，为了更新中心项\(user\_type(u_t)\)，我们使用：

\[argmax_{\theta} \sum\limits_{(u_t,c) \in D_{book}} log \frac{1} {1+e^{-v_c'v_{u_t}}} + \sum\limits_{(u_t,c) \in D_{neg}} log \frac{1} {1 + e^{v_c'v_{u_t}}}\]

…(6)

其中\(D_{book}\)包含了来自最近用户历史的user_type和listing_type，特别是与中心项接近的用户预定记录，其中\(D_{neg}\)包含了使用随机的user_type或listing_type实例作为负例。相似的，如果中心项是一个\(listing\_type(l_t)\)，我们可以对下式最优化：

\[argmax_{\theta} \sum\limits_{(l_t,c) \in D_{book}} log \frac{1} {1+e^{-v_c'v_{l_t}}} + \sum\limits_{(l_t,c) \in D_{neg}} log \frac{1} {1 + e^{v_c'v_{l_t}}}\]

…(7)

图5a展示了一个该模型的图形表示，其中，中心项表示\(user\_type(u_t)\)用于执行(6)中的更新。

图5

由于定义中的booking sessions几乎包含了来自不同markets的listings，没有必要从相同market中抽样额外的负样本作为booked listing。

拒绝订单(rejection)的显式负样本。不同于点击只影响guest端的偏好，bookings也会影响host端的偏好，也存在着来自host的一个显式反馈，形式表现为：接受guest的请求进行预定，或者拒绝guest的预订请求。对于host来说，拒绝的一些原因可能是：客户较差的guest star ratings、用户资料不完整或空白、没有资料图等等。这些特性有一部分存在表4中的user_type定义中。

来自主人的拒绝（Host rejections），可以在训练期间被用来编码主人（host）在向量空间中的偏好。合并这些拒绝信号的目的是：一些listing_types比没有预定记录的、不完整的资料、以及较低的评星率的user_types敏感度更小。我们希望，这些listing_types和user_types在向量空间的embedding更接近，这样基于embedding相似度的推荐可以减小拒绝率，最大化预订机会。

我们对rejections看成是显式负样本，以如下方式公式化。除了集合\(D_{booking}\)和\(D_{neg}\)，我们会生成一个集合\(D_{rej}\)，它由涉及到rejection事件的user_type和listing_type的pairs(\(u_t, l_t\))组成。如图5b所示，我们特别关注，对于同一用户，当在对于另一个listing的成功预定(通过一个正号标记)之后主人拒绝（通过一个负号-标记）。新的目标函数可以为：

更新一个\(user\_type(u_t)\)的中心item：

\[argmax_{\theta} \sum_{(u_t,c) \in D_{book}} log \frac{1} {1+e^{-v_c'v_{u_t}}} + \sum_{(u_t,c) \in D_{neg}} log \frac{1} {1 + e^{v_c'v_{u_t}}} + \sum_{(u_t,l_t) \in D_{reject}} log \frac{1} {1+exp^{v_{l_t}' v_{u_t}}}\]

…(8)

更新一个\(listing\_type(l_t)\)的中心item： \(argmax_{\theta} \sum\limits_{(l_t,c) \in D_{book}} log \frac{1} {1+e^{-v_c'v_{l_t}}} + \sum\limits_{(l_t,c) \in D_{neg}} log \frac{1} {1 + e^{v_c'v_{l_t}}} + \sum\limits_{(l_t,u_t) \in D_{reject}} log \frac{1}{1+exp(v_{u_t}' v_{l_t})}\)

…(9)

表5

对于所有user_types和listing_types所学到的embeddings，我们可以根据用户当前的user_type embedding和listing_type embedding，基于cosine相似度给用户推荐最相关的listings。例如，表5中，我们展示了cosine相似度：

user_type = SF_lg1_dt1_fp1_pp1_nb3_ppn5_ppg5_c4_nr3_l5s3_g5s3, 该用户通常会预定高质量、宽敞、好评率高、并且在美国有多个不同listing_types的listings。可以观察到，listing_types最匹配这些用户的偏好，例如，整租，好评多，大于平均价，具有较高cosine相似度；而其它不匹配用户偏好的，例如：空间少，低价，好评少，具有较低cosine相似度。

4.实验

4.1 Listing embeddings训练

对于listing embeddings的训练，我们从搜索中创建了8亿个点击sessions，通过使用从logged-in users所有searches，将它们通过user id进行分组，并在listing ids上按时间进行排序。

4.2 Listing Embeddings的离线评估

为了能快速根据不同最优化函数、训练数据构造、超参数、等做出快速决策，我们需要一种方式来快速对比不同的embeddings。

对训练出的embedding进行评估的一种方法是，基于用户最近点击行为，测试在用户推荐列表中将要预定的效果好坏。更特别的，假设我们给定了最常见的clicked listing和需要被排序的candidate listings（它包含了用户最终预定的listing）。通过计算在clicked listing和candidate listings间的cosine相似度，我们可以对候选进行排序，并观察booked listing的排序位置。

图6

为了评估，我们使用一个较大数目的这种search、click和booking事件，其中rankings通过我们的Search Ranking模型进行分派。在图6中，我们展示了离线评估的结果，我们比较了d=32的多个版本embeddings，并认为他们基于点击来对booked listing进行排序。booked listing的rankings对于每个产生预定的点击进行平均，在预定之前的17次点击，转到在预定之前的最后一次点击（Last click）。越低值意味着越高的ranking。我们要对比的embedding versions有：

• d32: 它使用(3)进行训练
• d32 book: 它使用bookings做为全局上下文 (4)
• d32 book + neg: 它使用bookings做为全局上下文，并对于相同的market采用展式负样本（5）

可以观察到，Search Ranking模型会随着它使用记忆型特征（memorization features）而获得更好更多的点击。可以观查到基于embedding相似度的re-ranking listings是有用的，特别是在search漏斗的早期阶段。最后，我们可以断定：d32 book + neg的效果要好于其它两者。相同类型的图可以被用于对其它因素：（超参数、数据构建）做出决策。

4.3 使用Embeddings的相似listing

每个Airbnb的home listing page页包含了Similar Listings(类似房源)这个 carousel控件，它会为home listing推荐与它相似的listings，并在相近的时间集合是可入住的。在我们的测试中，对于“Similar Listing” carousel控件的已存在算法，会调用主要的Search Ranking模型，给出通过给定listing过滤出与它相近位置、是否可入住、价格区间、listing type的listing。

我们进行了A/B test，其中会对比已存在算法与embedding-based的算法，其中，相似listings通过在listing embedding空间中寻找k个最近邻得到。给定学到的listing embeddings，对于一个给定的listing l，相似listings可以在时间上吻合（check-in和check-out的dates设置相同）的相同market上所有listings，通过计算\(v_l\)和\(v_j\)间的cosine相似度找到。具有最高相似度的K listings会被检索为相似listings。计算可以在线执行，使用我们共享架构来并行得到，其中，embeddings的部分存储在每个search机器上。

A/B test展示了，embedding-based解决方案在Similar Listing carousel上会产生一个21%的ctr提升（当listing page有entered dates时为23%，无date时为20%）。在Similar Listing carousel上发现listing并进行预定的客户，4.9%提升。从而部署到生产环境中。

4.4 使用Embeddings在Search Ranking上实时个性化

背景。为了正式描述我们的搜索排序模型（Search Ranking Model），我们假设，给定关于每个搜索\(D_s = (x_i, y_i), i=1, ..., K\)的训练数据，其中K是通过search返回的listings数目，\(x_i\)是一个向量，它包含了第i个listing结果的features，\(y_i \in \lbrace 0, 0.01, 0.25, 1, -0.4 \rbrace\)是分配给第i个listing结果的label。为了给一个特定的listing分配label。…

参考

• 1.https://astro.temple.edu/~tua95067/kdd2018.pdf

Taobao在2017年《Optimized Cost per Click in Taobao Display Advertising》提出了GAUC的概念：

1.介绍

广告促进了新品牌的提升，并保持已存在的高质量品牌长青。在线广告自1990s年后获得了指数式增长，它的市场策略涉及到使用互联网做为中介来获取网站流量和受众（target），并分发市场信息给合适的顾客。在在线广告中的实时竞价（RTB: real-time bidding）技术，允许广告主（advertiser）为每个独立的曝光（impression）进行竞价（bid）。大量研究【23-26】发现，有效的竞价策略可以最大化一个party（比如：广告主、消费者、媒介平台）的单边经济顺差（unilateral economic surplus）。

除了RTB系统外，淘宝建立了世界上最高级的在线广告系统之一。在移动app和pc网站上，被选中的ads会在指定spots（插播广告）中被呈现给用户。本文中关注在taobao移动app端上CPC展示广告（display advertising）中的竞价优化问题。主要涉及到两块：

• Banner CPC Ads：图1中taobao主页的top banner上出现的ads。广告主会为单个item、一个store或一个brand设置广告系列。
• Item CPC Ads：在猜你喜欢栏目中，单个items会被展示给用户，它包含了200多个spots，只有三个是广告，其它为推荐项，如图1所示。

图1

考虑到用户和广告主，taobao广告平台形成了自己独特的经济体，特性如下：

• 1.不同于大多数RTB系统（很难获取完整用户数据），taobao自身同时扮演着需求端和供给端。这种经济闭环系统使得taobao可以收集完整的用户数据和广告活动（ad campaign）信息。
• 2.系统中的大多数广告主是小型、中型广告主，它们只关注收益（revenue）的增加，而非品牌提升。因此，在GMV（交易总额：Gross Merchandise Volume）上的增加可以使这些广告主受益。
• 3.不同的广告主会购买不同的KPI（比如：impressions，clicks，ROI），它们对于taobao平台上的点击进行竞价，例如：采用CPC。我们会讨论其它方法，比如：CPM（每千人成本：cost per mille）和CPS（每次销售成本：cost per sale）。
• 4.最后但最重要的是：广告位（advertising spots）必须满足媒介需求，它可以通过一些指标进行衡量，比如：CTR、转化率(CVR)、GMV等。这里有一个GMV的分析。首先，我们希望商业流量的介绍不会过度影响用户体验。因而，设置GMV需要达到一个在商业回报和用户体验上的双赢（win-win）。第二，一个taobao广告主通常是taobao的卖方（sellers），它们会使用一个固定比例的回顾用于市场推广，提升GMV会导致广告主增加它们的广告预算，这会带来平台的长期收益。

考虑上述优缺点，我们在两种广告形式上采用CPC。尽管广告主认为CPS对比于CPC的风险更低，但CPS会忽略点击的价值，提供更差的流量清算效率。由于广告形式主要针对中小广告主，CPM造成更高的风险，而CPC允许广告主控制点击成本(cost of clicks)，平台则承担着调整page views给clicks的风险。有了taobao完整的数据生态（data ecology）、以及标准电商广告和交互过程，CPC足够有效。

许多SOTA的系统，比如facebook[7]使用不同的设计。对于一些大型社交网络服务（SNSs），通过oCPM（optimized cost per mille），广告主可以为click竞价，实际每次impression都有花费。SNS广告交互通常是有差异的，比如：like、click、share等。而taobao交易通常通过简单的系列点击(serial clicks)来完成。从数据生态的视角，在ad click之后，taobao用户的所有行为仍在taobao平台上，这可以为可跟踪的基于交互的演绎提供条件。然而，SNS通常会让广告主为clicks或其它actions竞价，从而转化成等价的CPM方式，这在机制上鼓励广告主上传实际的follow-up intereaction数据，以便进一步优化bid。

前面提到的两种ad形式，根据生态、效率等，我们选择CPC。

taobao的广告系统包括：数百万ads的过滤，并对这些候选ads进行ranking。首先，根据历史行为以及ad item细节挖掘用户偏好。taobao targeting系统[17,18]会训练模型为每次page view请求来过滤大量ads，这被称为matching stage。不同于推荐（不涉及广告主），matching service会召回相关的users，它们必须反映广告主竞价意愿，并确保市场深度。第二，实时预测（RTP：real-time prediction）引擎会为每个符合条件的广告（eligible ad）预测pCTR。第三，传统上，这些候选广告通过bid * pctr进行排序，并基于该order来最大化eCPM（effective cost per mille：每千次展示可以获得的有效广告收入）。

广告主总是希望bid匹配流量质量（traffic quanlity）。由于技术限制，对于粗粒度流量差异，传统方法只能为指定user groups和ad slots设置固定竞价(fixed bid)，然而，广告主正进一步寻找细粒度bids和traffic quanlity的匹配(matching)。一方面，一个fiexed bid set很。。。

2.系统架构

这部分描述了taobao中的展示广告系统(display ads system)中数据和信息是如何流动的，如图2所示。每个系统组件和events序列会从foremost page view request中：

图2

3.OCPC

OCPC(Optimized Cost Per Click)

在这部分，我们首先数学描述advertisers和conditions以便optimization。第二，我们提出一个算法来优化平台生态指标（index）和平台回报（revenue）。最后，介绍相关细节。实际上，我们的算法框架使用大量广告主需求和平台生态指标，比如：（PV数、点击数、转化率（conversion）等）。作为一个常见case，该paper会将ROI和gaining qulity traffic按广告主的要求进行设置，GMV作为平台生态指标，它与平台收益（playform revenue）通过调节广告主的竞价来进行优化。假设A是对于一个PV请求来说合格的广告活动（ad campaigns）的集合。有了该特定PV请求，对于每个campaign \(a \in A\)，存在一个由advertiser预先设定的相应的bid \(b_a\)。对于每个\(b_a\)，OCPC算法的角色是，调整并发现一个最优的\(b_a^*\)来达到预先设计的多种最优化需求。

3.1 Optimization Scope

ROI constraint。考虑

3.2 ranking

3.3 算法细节

4.模式估计

4.1 模型和features

4.2 模型performance

serving precise结果对于预测模型来说非常重要。在像CTR预估的任务中，AUC是一个被广泛用来评估模型有效性的指标。然而，一些研究表明[4]，在testing上更好的AUC结果可能会在生产环境中带来差的performance。当在实际中对预测模型进行调参时，这会带来困扰。我们分析了该问题，并发现，AUC指标并不会对用户（users）和广告位（spots）进行区别对待。例如，从未点击任何ad的用户或模糊的广告位，可能会对AUC结果偏向一个更低值。根据这些事实和分析，我们提出了一个AUC-like metric，称为Group AUC（GAUC），如等式(9)所示。

• 首先，我们将所有测试数据根据the user (u)和广告位的特定位置(p)进行聚合
• 接着，在每个单一group上会计算AUC结果（注意：如果在一个group中存在的样本全为正、或全为负时，我们需要从数据中对该group进行移除）
• 最后，我们对这些在不同的groups上的AUC进行加权平均（weight \(w_{(u,p)}\)与group中的impression times或click times成比例），并将结果作为GAUC value

\[GAUC = \frac{\sum\limits_{(u,p)} w_{(u,p)} * AUC_{(u,p)}}{\sum\limits_{(u,p)} w_{(u,p)}}\]

…(9)

CTR和CVR模型performance。在图6中，我们给出了在一个7天周期中，CTR和CVR预测模型在AUC和GAUC的performance。结果表明，由MLR算法的天模型（daily model）的performance很稳定。CVR模型比CTR模型具有更高的GAUC，因为在CVR模型的样本中具有更小的noises。在图7和4中，我们展示了CTR、CVR在不同预测值levels下的预测和实际ratio。结果表明，CTR的预测值(predicted)通常要比实际值(real)更大。然而，在提出的OCPC策略中，不同的predicted CTR值间的顺序关系影响会更多。

图6 在一个7天的周期中，CTR和CVR模型在AUC和GAUC上的performance (从2017.1.10-2017.1.16)

图7 predicted和real CTR间的gap w.r.t. 不同pCTR level（从2017.1.10-2017.1.16）

参考

• 1.https://arxiv.org/pdf/1703.02091.pdf

阿里在KDD 2018上开放了它们的方法:《Learning Tree-based Deep Model for Recommender Systems》, 我们来看下：

注：tdm的paper最好结合代码去理解。

介绍

在推荐系统设计中，为每个用户从整个语料(corpus)集中预测最好的候选集合，存在许多挑战。在海量corpus的系统中，一些推荐算法会失败。与corpus size成线性预测复杂度关系是不可接受的。部署这样的大规模推荐系统，预测每个用户所需要的计算量是受限的。除了精准度外，在用户体验上也应考虑推荐items的新颖度（novelty）。推荐结果中如果包含许多与用户的历史行为的同质items是不可接受的。

在处理海量corpus时，为了减少计算量，memory-based的CF方法在工业界常被广泛使用。作为CF家族的代表方法，item-based CF可以从非常大的corpus进行推荐，只需要很少的计算量，具体决取于预计算的item pairs间的相似度，以及使用用户历史行为作为触发器（triggers）来召回多个相似items。然而，这限制了候选集的范围，例如，只有与triggers相似的items可以被推荐。这阻止了推荐系统跳出它们的历史行为来探索潜在的其它用户兴趣，限制了召回结果的accuracy。实际上，推荐的新颖性（novelty）也是很重要的。另一个减小计算量的方法是，进行粗粒度推荐（coarsegrained recommendation）。例如，系统为用户推荐少量的item类目，并根据它选择所有相应的items，接着进行一个ranking stage。然而，对于大语料，计算问题仍然没解决。如果类目数很大，类目推荐本身也会遇到计算瓶颈。如果不这样做，一些类目将不可避免地包含过多items，使得后续的ranking计算行不通。另外，使用的类目通常不是为推荐问题专门设计的，它也会对推荐的accuracy有害。

在推荐系统的相关文献中，model-based的方法是一个很活跃的话题。像矩阵分解（MF）这样的模型，尝试将pairwise user-item偏好分解成user factors和item factors，接着为每个用户推荐它最喜欢的items。因子分解机（FM）进一步提出了一个统一模型，对于任意类型的输入数据，可以模仿不同的因子分解模型。在一些真实场景中，没有显式偏好，只有隐式用户反馈（例如：像点击 or 购买 这样的用户行为），Bayesian personalized ranking【29】给出了一个求解思路，它会将三元组中的偏好按局部顺序进行公式化，并将它应用到MF模型中。工业界，YouTube使用DNN来学习user embedding和item embeddings，其中，两种类型的embeddings会分别由其相对应的特征进行生成。在上述所有类型的方法中，user-item pair的偏好可以被公式化成，user vector表示与item vector表示间的内积（inner product）。预测阶段等同于检索用户向量在内积空间中的最近邻。对于向量搜索问题，像hashing或quantization[18]用于近似kNN搜索来确保检索的高效性。

然而，在user vector representations和item vector representations间的内积交互形式，严重限制了模型的能力。存在许多类型的其它更具表现力的交互形式，例如，用户历史行为和候选items间的cross-product特征在CTR预估上广泛被使用。最近的工作【13】提出了一种neural CF方法，它使用一个神经网络来替代内积，被用于建模user和item向量表示间的交互。该工作的试验结果表明，一个多层前馈神经网络，比固定内积方法的效果要好。DIN[34]指出，用户兴趣是分散的，一种基于attention机制的网络结构可以根据不同候选items生成不同的user vectors。除了上述工作外，其它像product NN[27]的方法也表明高级NN的效果。然而，这些类型的模型与user vector和item vector间的内积方法（利用高效的kNN搜索）不相一致，在大规模推荐系统中，它们不能被用于召回候选集。为了克服计算屏障，在大规模推荐中使用高级NN是个问题。

为了解决上述挑战，我们提出了一个新的TDM（tree-based deep recommendation model）. 树和基于树的方法在多分类问题中被广泛研究，其中，tree通常被用于划分样本(sample)/标签(label)空间，来减小计算代价。然而，研究者们涉足于推荐系统环境中使用树结构做为索引进行检索。实际上，层次化结构（hierarchical structure）的信息存在于许多领域。例如，在电商中，iPhone是细粒度item，而smartphone是粗粒度概念，iPhone属于smartphone。TDM方法会使用信息的层级，将推荐问题转化成一系列的层次化分类问题（hierarchical classification problems）。从简到难解决该问题，TDM可以同时提升accuracy和efficiency。该paper的主要贡献如下：

• TDM是第一个这样的方法，使得在大规模语料中生成推荐的任意高级模型成为可能。受益于层次化树搜索，TDM的计算量只与corpus size成log关系。
• TDM可以从大型数料中发现更精准的显著并有效的推荐结果，由于整个语料是探索式的，更有效的深度模型也可以帮助发现潜在兴趣。
• 除了更高级的模型外，TDM也通过层次化搜索来提升推荐accuracy，它可以将一个大问题划分成更小的问题分而治之。
• 作为索引的一种，为了更高效地检索，树结构可以朝着items和concepts的最优层次结构被学到，它可以帮助模型训练。我们使用一个tree learning方法，它可以对神经网络和树结构进行joint training。
• 我们在两个大规模数据集上做了大量实验，结果展示TDM的效果要比现有方法好很多。

值得一提的是，tree-based方法也在语言模型中使用（hirearchical softmax），但它与TDM在思想和公式上都不同。在对下一个词的预测问题上，常用的softmax必须计算归一化项（normalization term）来获取任意单个词的概率，它非常耗时。Hierarchical softmax使用tree结构，下一个词的概率就被转换成沿着该tree path的节点概率乘积。这样的公式将下一个词概率的计算复杂度减小到关于语料size的log级别。然而，在推荐问题上，为这些最喜爱items搜索整个语料的目标，是一个检索问题。在hierarchical softmax tree中，父节点的最优化不能保证：最优的低级别节点在它们的子节点上（descendants），并且所有items仍需要被转换成发现最优解。为了解决该检索问题，我们提出了一个类似最大堆的树公式（max-heap like tree），并引入了DNN来建模该树，它为大规模推荐提供了一个有效的方法。以下部分展示了公式的不同之处，它在性能上的优越性。另外，hierarchical softmax采用了单层hidden layer网络来解决一个特定的NLP问题，而我们提出的TDM则实际上可使用任意网络结构。

提出的tree-based模型是一个通用解法，适用于所有类型的在线内容提供商。

2.系统架构

图1 Taobao展示广告(display advertising)推荐系统的系统架构

在本节，图1介绍了Taobao 展示广告推荐系统。在接受到一个用户的PV请求时，系统使用用户特征、上下文特征、以及item特征作为输入，会在matching server中从整个语料中（上百万）来生成一个相对较小的候选集合（通常百级别）。tree-based推荐模型在该stage发挥作用，并将候选集的size缩减了好多阶。

有了数百个候选items，实时预测server会使用更昂贵但也更耗时的模型[11,34]来预测像CTR或转化率之类的指标。在通过策略排完序后，一些items会最终曝光给用户。

如上所述，提出的推荐模型的目标是，构建一个含数百个items的候选集。该stage是必须的，也很难。用户在生成的候选上是否感兴趣，给出了曝光质量的一个上界。然而，从整个语料中有效抽取候选是个难题。

3.tree-based Deep模型

在本部分，我们首先介绍在我们的tree-based模型中所使用的树结构。然后，介绍hierarchical softmax来展示为什么该公式不适合推荐。最后，我们给出了一个新的类max-heap tree公式，并展示了如何训练该tree-based模型。接着，引入DNN结构。最后，我们展示了如何构建和学习在tree-based模型中构建和学习该tree。

图2 tree-based deep模型架构。用户行为根据timestamp被划分成不同的时间窗口。在每个时间窗口中，item embeddings被平均加权，权重来自activation units。每个时间窗口的output沿着候选节点的embedding，被拼接成神经网络的输入。在经过三个带PReLU activation和batch normalization的fully-connected layers之后，使用一个二分类softmax来输入probability：用户是否对候选节点感兴趣。每个item和它对应的叶子节点共享相同的embedding。所有embeddings都是随机初始化的。

3.1 推荐所用树

一棵推荐树（recommendation tree）由一个包含N个节点的集合构成，其中\(N=\lbrace n_1, n_2, ..., n_{\mid N \mid}\rbrace\)，表示\(\mid N \mid\)个孤立的非叶子节点或叶子节点。在N中的每个节点，除了根节点外，具有一个父节点、以及特定数目的子节点。特别的，在语料C中的每个item \(c_i\)，仅仅只对应于树中的一个叶子节点，这些非叶子节点是粗粒度概率。不失一般性，我们假设节点\(n_1\)是根节点。一个关于树的示例如图2右下角所示，在其中，每个圆表示一个节点，节点的数字是在树中的索引。该树总共具有8个叶子节点，每个都对应于语料中的一个item。值得一提的是，给定的示例是一个完全二叉树，我们不会在我们的模型中强制完全二叉。

图2右下角

3.2 相关工作

有了树结构，我们首先引入hierachical softmax来帮助区分TDM。在hierachical softmax中，树中的每个叶子节点n，从根节点出发到该节点具有唯一编码。例如，如果我们假定：左分枝为1,右分枝为0, 那么图2中树\(n_9\)的编码为110, \(n_{15}\)的编码为000。在hierachical softmax的公式中，下个词的概率通过上下文给定：

\[p(n | context) = \prod\limits_{j=1}^{w} P(b=b_j(n) | l_j(n), context)\]

…(1)

其中：

• \(b_j(n)\)指的是节点n在第j层上的编码
• w：指的是叶子节点n的编码
• \(l_j(n)\)：是在节点n在第j层的父节点

通过上述的概率计算方式，hierarchical softmax可以避免softmax中的归一化项(语料中每个词都要遍历一次)，从而解决概率计算问题。然而，为了发现最可能的叶子，该模型仍会遍历整个语料。从上到下沿着树路径（tree path）遍历每个层中最可能的节点，不能保证成功检索到最优的叶子。因此，hierarchical softmax的公式不适合大规模检索问题。另外，根据公式1, 树中的每个叶子节点以二分类的方式训练，来在两个子节点间做区分。但是如果两个节点是树中的邻居，它们很可能很相似。在推荐场景中，很可能该用户对两个子节点都感兴趣。hierarchical softmax主要会在最优解和次优解上建模，从全局上看会丢掉识别能力。如果使用贪婪定向搜索（greedy beam search）来检索这些最可能的叶子节点，一旦在树的上层做出坏的决策，模型在发现更好结果上会失败。YouTube的工作[7]也报告了他们已经尝试用hierachical softmax来学习user embeddings和item embeddings，而它比sampled-softmax[16]的方式效果要差。

hierachical softmax的公式不适合于大规模推荐，我们提出了一种新的树模型。

3.3 Tree-based模型公式

为了解决top-k 最喜欢items检索的效率问题，我们提出了一个最大堆树（max-heap like tree）的概率公式。最大堆树是一个树结构。其中在第j层中的非叶子节点n，对于每个用户u来说，满足以下公式：

\[P^{(j)} (n | u) = \frac{\underset{n_c \in \lbrace 第j+1层的n个子节点 \rbrace}{max} P^{(j+1)}(n_c | u)} {\alpha^{(j)}}\]

…(2)

其中：

• \(P^{(j)}(n \mid u)\)：是第j层上，用户u对节点n感兴趣的真实概率(ground truth probability)。
• \(\alpha^{(j)}\)：是第j层指定layer的归一化项，用来确保在level上的概率和等于1。

等式(2)表明，一个父节点的真实偏好等于它的子节点的最大偏好，除以归一化项。注意，我们对该概率做细微修改，让u表示一个特定的用户状态（user state）。换句话说，一旦该用户有新行为，会从一个特定用户状态u转移到另一个状态u’。

我们的目标是，寻找具有最大偏好概率(largest preference probabilitiy)的k个叶子节点。假设，我们具有在树中每个节点n的真实概率\(P^{(j)}(n \mid u)\)，我们可以使用layer-wise的方式来检索k个节点的最大偏好概率，只有每一层的top k的子节点需要被探索。在这种方式下，top k个叶子节点可以被最终检索到。实际上，我们不需要知道在上述过程中每棵树节点的实际真实概率。我们需要知道的是每一层的概率顺序，来帮助发现在该层级上的top k个节点。基于这个观察，我们使用用户的隐式反馈数据和神经网络来训练每个层级（level）的识别器（discriminater），它可以告诉偏好概率的顺序。

假设用户u具有一个与叶子节点\(n_d\)的交互(interaction)，即，。这意味着：

\[P^{(m)}(n_d \mid u) > p^{(m)}(n_t \mid u)\]

其中：

• \(n_d\)是一个u的正样本节点
• m是叶子层级
• \(n_t\)是同层级任意其它叶子节点

在任意层级j上，根据等式(2)的公式，我们假设：

\[P^{(j)}(l_j(n_d) \mid u) > P^{(j)}(n_q \mid u)\]

其中：

• \(l_j(n_d)\)表示在级别j上的\(n_d\)的父节点
• \(n_q\): 在层级j上，除了\(l_j(n_d)\)外的任意节点

在上述分析的基础中，我们可以使用negative sampling来训练每个层级的顺序判别器（order discriminator）。细节上，与u有交互的叶子节点，它的父节点为u构成了在每个层级中的正样本集合。在每个层级上，随机选择若干负样本（除去正样本），构建了负样本集合。在图2中，绿色和红色节点给出了抽样示例。假设，给定一个用户和它的状态，目标节点是\(n_{13}\)。接着，\(n_{13}\)的父节点是正样本，这些在每个层级上随机抽取的红色节点，是负样本。这些样本接着被feed给二分类概率模型来获取层级(levels)上的顺序判别器（order discriminators）。我们使用一个全局DNN二分类模型，为所有层级使用不同输入来训练顺序判别器。可以使用高级的神经网络来提升模型能力。

假设\(y_u^+\)和\(y_u^-\)是关于u的正负样本集合。似然函数为：

\[\prod\limits_u (\prod\limits_{u \in y_u^+} P(\hat{y}_u(n) = 1 |n, u) \prod_{n \in y_u^-} P(\hat{y}_u(n)=0 | n, u))\]

…(3)

其中：

• \(\hat{y}_u(n)\)是给定u的节点n的预测label。
• \(P(\hat{y}_u(n) \mid n, u)\)是二分类概率模型的输出（它采用用户状态u以及抽样节点n作为输入）。

相应的loss函数为：

\[-\sum\limits_u \sum\limits_{n \in y_u^+ \cup y_u^-} y_u(n) log P(\hat{y}_u(n) = 1 | n,u) + (1 - y_u(n)) log P(\hat{y}_u(n) = 0 | n,u)\]

…(4)

其中：\(y_u(n)\)是给定u的节点n的ground truth label。3.4节将讲述如何根据loss函数来训练模型。

注意，提出的抽样方法与hierarchical softmax相当不同。对比在hierarchical softmax中使用的方法（它会让模型混淆最优和次优结果），我们的方法会为每个正节点的同层级随机选择负样本。这种方法让每一层的判别器是一个内部层级全局判别器(intra-level global)。每个层级的全局判别器(global discriminator)可以更独立的做出精准决策，不需要依赖于上层决策的好坏。全局判别能力对于hierarchical推荐方法非常重要。它可以确保：即使模型做出坏的决策，让低质量节点会漏进到上层中的候选集，通过该模型在下层也能选中那些相对更好的节点，而非非常差的节点。

算法1

给定一棵推荐树、以及一个最优模型，详细的hierarchical预测算法在算法1中描述。检索过程是layer-wise和top-down的。假设，期望的候选item数是k。对于语料C，它具有size=\(\mid C \mid\)，在最多\(2 * k * log \mid C \mid\)个节点上遍历，可以获取在一个完全二叉树上最终的推荐集合。节点数需要在一个关于log(corpus size)级别上遍历，这样可以做出高级的二分概率模型。

我们提出的TDM方法不仅减少了预测时的计算量，也潜在地提升了推荐质量（对比起在所有叶子节点上的brute-force search）。由于corpus size可能很大，如果没有这棵树，训练一个模型来直接发现最优items是一个很难的问题。使用树的层次化（tree hierarchy），大规模推荐问题可以被划分成许多更小的问题。在树的高层中只存在很少节点，判别问题更容易些。由高层上做出的决策可以重新定义候选集，它可以帮助更低层级做出更好的决策。第5.4节中的实验结果，将展示提出的hierarchical retrieval方法的效果要好于brute-force search。

3.4 Deep模型

下面，我们引入deep模型。整个模型如图2所示。受ctr工作的启发[34]，我们为树中的每个节点学习低维embeddings，并使用attention模块来为相关行为进行软搜索（softly searching）以求更用的user representation。为了利用包含timestamp信息的用户行为，我们设计了block-wise input layer来区别在不同时间窗口的行为。历史行为可以被划分成沿timeline的不同时间窗，在每个时间窗口中的item embeddings是平均加权的。Attention模块和下面介绍的网络可以极大增强模型能力，同时可以在不能够以内积形式表示的候选集上做出用户偏好。

树节点的embeddings和树结构本身是模型的一部分。为了最小化公式(4)的Loss，抽样节点和相应的特征可以被用于训练该网络。注意，我们只在图2中出于简洁性，展示了用户行为特征的使用，而其它像user profile的features或contextual feature，可以被使用，并无大碍。

3.5 树的构建和学习

推荐树是tree-based deep推荐模型的一个基础部件。不同于multiclass和multi-label分类任务，其中tree被用于划分样本或labels，我们的推荐树会对items进行索引以方便检索。在hierarchical softmax中，词的层次结构可以根据WordNet的专家知识构建。在推荐场景，并不是每个语料可以提供特有的专家知识。一个直觉上的选择是：使用hierarchical聚类方法，基于数据集中item共现或相似度来构建树。但聚类树可能相当不均衡，不利于训练和检索。给定pairwise item similarity，paper[2]的算法给出了一种方法来通过谱聚类将items递归分割成子集。然而，对于大规模语料来说谱聚类的扩展性不够（复杂度随corpus size成三次方增长）。在本节中，我们主要关注合理和可行的树构建和学习方法。

树的初始化。由于我们假设该树表示了用户兴趣的层次结构化（hierarchical）信息，很自然地以在相近位置组织相似items的方式来构建树。假设，在许多领域中类目信息是广泛提供的，我们直觉上提出一个方法来利用item的类目信息来构建初始的树。不失一般性，我们在本节中使用二叉树。

• 首先，我们会对所有类目随机排序，以一个intra-category的随机顺序将属于相同类目的items放置在一起。如果一个item属于多个类目，出于唯一性，item被随机分配给其中之一。这种方式下，我们给出了一个ranked items的列表。
• 第二，这些ranked items被递归均分为两个相同的部分，直到当前集合有且仅包含一个item，它可以自顶向底构建一个近似完全二叉树。上述类型的category-based初始化，可以比完全随机树获取更好的hierarchy。

树的学习。作为模型的一部分，每棵叶子节点的embedding可以在模型训练之后被学习得到。接着，我们使用学到的叶子节点的embedding向量来聚类一棵新的树。考虑到corpus size，我们使用k-means聚类算法。在每个step，items会根据它们的embedding vectors被聚类成两个子集。注意，两个子集会被调整成相等以得到一个更平衡的树。当只剩下一个item时，递归过程停止，结果产生一棵二叉树。在我们的实验中，使用单台机器，当语料size为400w时，它会花费一个小时来构建这样的一个聚类树。第5节的实验结果表明所给树学习算法有效率。

4.online serving

图3展示了提出方法的online serving系统。Input feature assembling和item retrieval被划分成两个异步的stages。每个用户行为(包含点击、购买以及加入购物车），会触发realtime feature server组装新的input features。一旦接收到PV请求时，user targeting server会使用预组装的features来从该树中检索候选。如算法1所述，检索是layer-wise的，训练的神经网络被用于计算：对于给定input features，一个节点是否被喜欢的概率。

图3

5.实验研究

本部分会研究tree-based模型的效果。实验结果在MovieLens-20M和Taobao advertising dataset（称为UserBehavior数据集）。

• MovieLens-20M: 包含了user-movie评分数据，带有timestamps。我们会处理隐式反馈问题，评分被二值化：4分以上为1. 另外，只有观看了至少10部电影的用户才会被保留。为了创建训练集、测试集、验证集，我们随机抽样了1000个用户做测试集，另1000用户做验证集，其余用户用于训练集。对于测试集和验证集，沿timeline的前一半user-movie观看记录被看成是已知行为，用于预测后一半。
• UserBehavior: 该数据集是taobao用户行为数据集的子集。我们随机选取了100w具有点击、购买、加入购物车、喜欢收藏的行为，在2017年11.25-12.03间。数据的组织与MovieLens非常相似，例如，一个user-item行为，包含了user ID, item ID, item category ID, 行为类型和timestamp。和MovieLens-20类似，只有至少有10个行为的用户会保留。10000用户会被机选中做为测试集，另一随机选中的10000用户是验证集。Item categories从taobao当前的商品类目的最底层类目得到。表1是两个数据集的主要统计：

表1

5.2 Metrics和比较

为了评估不同方法效果，我们使用Precision@M, Recall@M和F-Measure@M。

• FM：由xLean项目提供的FM
• BPR-MF: 由[10]提供的BPR-MF
• Item-CF: Item-based CF，由Alibaba自己实现
• Youtube product-DNN: Youtube的方法。训练时使用Sampled-softmax，在Alibaba深度学习平台上实现。预测时在内积空间中采用Exact kNN search。
• TDM attention-DNN(tree-based模型，使用attention网络)，如图2所示。树的初始化由3.5节所示，在实验期间保持不变。实现在github上。

对于FM, BPR-MF和item-CF，我们会基于验证集调参，例如：在FM和BPR-MF的因子数和迭代数，在item-CF中的邻居数。FM和BPR-MF需要用户在测试集和验证集上也具有在训练集中的反馈。因些，我们会根据timeline添加在测试集和验证集中前一半的user-item交互，到训练集中。对于Youtube product-DNN和TDM attention-DNN，节点的embeddings的维度设置为25, 因为在我们的实验中一个更高维度并不会带来很大的效果提升。hidden unit数目分别设置为128, 64, 64. 根据timestamp，用户行为被划分成10个time windows。在Youtube product-DNN和TDM attention-DNN中，对于每个隐式反馈，我们为MovieLens-20M随机选择100个负样本， 为UserBehavior随机选择600个负样本。注意，TDM的负样本数据是所有层的求和。我们会为接近叶子的层级抽样更多的负样本。

5.3 结果比较

结果如表2所示：

表2

为了验证新颖性（novelty），一种常用的方法是：过滤掉在推荐集中的交互项【8，20】，例如，只有这些新的items可以被最后推荐。因而，在一个完全新的结果集上比较accuracy更重要。在该实验中，结果集的size可以被补足到M，如果在过滤后size小于M。在过滤完交互items后，表2的底部展示了TDM的attention-DNN效果要好于所有baseline一大截。

为了进一步评估不同方法的能力，我们通过将这些交互类目从结果中排除做实验。每个方法可以补足以满足size需求。确实，category-level novelty在Taobao推荐系统中是最重要的新颖性（novelty）指标。我们希望减小与用户交互项的推荐数目。由于MovieLens-20M只有20个类目，该实验只包含了UserBehavior数据集，结果如表3所示。以recall指标为例，我们观察到item-CF的recall只有1.06%，由于它的推荐结果可以有一半跳出用户的历史行为。Youtube product-DNN对比item-CF会获取更好的结果，由于它从整个语料探索用户的潜在兴趣。而TDM attention-DNN在recall上的效果比Youtube的inner product方式要好34.3%。这种巨大的提升对于推荐系统来说非常有意义，它证明了更高级的模型对于推荐问题来说有巨大的不同。

表3

5.4 经验分析

TDM的变种。为了自身比较，也评估了一些变种：

• TDM product-DNN: 为了找出高级神经网络是否可以受益于TDM，我们测试了TDM product-DNN。TDM product-DNN使用与Youtube product-DNN相似的inner product方式。特别的，在图2中的attention模块会被移除，node embedding term也被从网络输入中被移除。node embedding和第三个fc layers的output（without PReLU和BN）的inner product会使用一个sigmoid activation来构成新的二分类器.
• TDM DNN: 为了进一步验证由TDM attention-DNN的attention module带来的提升，我们会测试TDM DNN变种，它只会移除activation unit，例如：在图2中所有items的weights。
• TDM attention-DNN-HS: 正如第3节提到的，hirearchical softmax方法并不适合推荐。我们会测试TDM attention-DNN-HS变种，例如，使用positive nodes的邻居作为negative samples，来替代随机选择的样本。相应的，在算法1的检索中，ranking indicator会发生变化：从单个node的\(P(\hat{y}_u(n)=1 \mid n,u)\)变为 \(\prod_{n' \in n's \ ancestors P(\hat{y}_u(n') = 1 \mid n', u)}\)。Attention-DNN被当成网络结构进行使用.

实验结果如表2中虚线以下所示。TDM attention-DNN到TDM DNN的比较，在UserBehavior数据集上有10% recall提升，attention模块会有明显的提升。TDM product-DNN效果比TDM DNN、TDM attention-DNN要差，因为inner product的方法比神经网络的交互形式要差些。这些结果表明：在TDM中引入的高级模型可以极大提升推荐的效果。注意，对比起TDM attention-DNN，TDM attention-DNN-HS会获取更差的结果。因为hierarchical softmax的公式不能很好适应推荐问题。

树的角色。Tree是TDM的关键组件。它不仅扮演着检索时的索引角色，也会以从粗到细的层级结构形式来建模语料。第3.3节中提到的，直接做出细粒度推荐要比以层级结构方式更难。我们通过实验证明了这个观点。图4展示了layer-wise Recall@200的hierarchical tree search（算法1）和brute-force search。该实验在UserBehavior数据集上使用TDM product-DNN模型，因为它是唯一可以采用brute-force search的变种。在高层级上（8-9），burte-force search的效果只比tree search要稍微好一点点，因为节点数很小。一旦在一个层级上的节点数增长了，对比起burte-force search，tree search会获取更好的recall结果，因为tree search可以排除那些在高层级上的低质量结果，它可以减少在低层级上的问题的难度。该结果表明，在树结果中包含的hierarchy信息，可以帮助提升推荐的准确性。

图4

表4

tree learning。在3.5节中，我们提出了树的初始化和学习算法。表4给出了在initial tree和learnt tree间的比较结果。从结果看，我们可以发现，使用learnt tree结构的训练模型的效果要远好于只使用intial tree的训练模型。例如，learnt tree的recall指标从4.15%到4.82%，对比起在过滤交互类目的实验中的initial tree，它使用Youtube product-DNN: 3.09%, item-CF: 1.06%。为了进一步比较这两个tree，我们展示了TDM attention-DNN的test loss和recall曲线，训练迭代如图5所示。从图5(a)中，我们可以看到learnt tree结构的test loss变小。图5(a)和5(b)表明，模型会收敛到较好的结果。上述结果表明，tree-learning算法可以提升items的hierarchy，从而进一步提升训练和预测。

图5

5.5 Online效果

我们在taobao效果广告平台的真实流量上评估了提出的TDM的方法。实验在taobao app主页上的猜你喜欢（Guess What You Like）中进行实验。用于评估效果的两个指标是：CTR和RPM（每1000的回报率）。详细如下：

\[CTR=\frac{\# of clicks}{\# of impressions}, \\ RPM = \frac{广告收入}{曝光数} * 1000\]

…(8)

在我们的广告系统中，广告主会对一些给定的ad clusters竞价。有将近1400w的clusters，每个ad cluster包含了上百或上千条相似的ads。该验验以ad cluster的粒度开展，以保持与现有系统的一致。比较方法有：LR作为baseline。由于系统中有许多stages，部署TDM online方法是一个巨大的项目，涉及到整个系统。我们完成了第一个TDM DNN版本，并评估了online流量。每个分桶具有5%的在线流量。值得一提的是，有许多在线同时运行推荐的方法。他们从不同的视角，产生的结果进行合并进入到下一stages。TDM只会替换它们中最有效的，保持其它模块不变。带有TDM的测试分桶的平均metric提升率，如表5所示。

如表5所示，TDM方法的CTR提升了2.1%。这项提升表明提出的方法可以为用户召回更多精准的结果。另一方法，RPM的metric增加了6.4%，这意味着TDM的方法也可以为taobao广告平台带来更多回报。

预测效果。TDM使得，在大规模推荐中与user和items交叉高级神经网络变得可行，它打开了一个全新视角。值得一提的是，尽管高级神经网络在inferring时需要更多的计算，但整个预测过程的复杂度不会大于\(O(k * log \mid C \mid * t)\)，其中，k是所需结果的size，\(\mid C \mid\)是corpus size，t是网络中单个feed-forward pass的复杂度。该复杂度的上界在当前CPU/GPU硬件环境下是可接受的，在单个检索中，用户侧特征可以跨不同的节点共享，一些计算可以根据模型设计被共享。在Taobao展示广告系统中，它实际上会采用TDM DNN模型，平均一次推荐需要6ms。这样的运行时间比接下来的ctr预测模型要短，不会是系统瓶颈。

6.结论

参考

• 1.https://arxiv.org/pdf/1801.02294.pdf

阿里盒马团队在KDD 2018上开放了它们的方法:《Learning and Transferring IDs Representation in E-commerce》, 这个方法也很简单，我们来看下paper的主要内容部分：

3.4 联合嵌入Attribute IDs

通过探索在item ID和它的attribute IDs间的结构连接，我们提出了一个hirerarchical embedding模型来联合学习item ID和attribute IDs的低维表示。模型结构如图4所示，其中item ID是核心的交互单元，它与attibute IDs间通过虚线连接。

图4

首先，item IDs的共现也隐含了对应attribute IDs间的共现，它通过图4的实心键头表示。假设存在K个类型的IDs，并使 \(ID_s(item_i) = [id_1(item_i), \cdots, id_k(item_i), \cdots, id_K(item_i)]\)，其中\(id_1(item_i)\)等于\(item_i\)的item ID，\(id_2(item_i)\)是product ID，\(id_3(item_i)\)是store ID等。我们学习目标替换成：

\[P(ID_s(item_j) | ID_s(item_i)) \\ = \sigma(\sum\limits_{k=1}^K (w_{jk} e_{jk}')^T (w_{ik} e_{ik})) \\ = \prod\limits_{s=1}^S \sigma(-\sum_{k=1}^K (w_{sk} e_{sk}')^T (w_{ik} e_{ik}))\]

…(7)

其中，\(e_{\cdot k}' \in E_k'(\subset R^{m_k \times D_k})\)以及\(e_{\cdot k} \in E_k(\subset R^{m_k \times D_k})\)。\(E_k'\)和\(E_k\)是分别对应于类型(type)为k的context和target representations。对于类型k，\(m_k\)是它的embedding vectors的维度，\(D_k\)是它的字典size。注意，不同类型的IDs可以被嵌入到不同的维度上。标量\(w_{ik}\)是\(id_k(item_i)\)的权重。假设每个item的贡献与\(id_k(item_i)\)相等，\(id_k(item_i)\)包含了\(V_{ik}\)个不同的items，\(w_{ik}\)与\(V_{ik}\)成反比是合理的。更正式的，我们有:

\[I(x)= \begin{cases} 0, & \text{x is False} \\ 1, & \text{x is True} \end{cases}\]

…(8)

\[V_{ik} = \sum\limits_{j=1}^D I(id_k(item_i) = id_k(item_j))\]

…(9)

\[w_{ik} = \frac{1}{V_{ik}} (k=1, \cdots, K)\]

…(10)

例如，\(w_{i1}=1\)表示每个\(id_1(item_i)\)刚好包含了一个item；而\(w_{i2} = \frac{1}{10}\)表示：product ID\((item_i)\)包含了10个不同的items。

第二，item ID和attribute IDs间的结构连接意味着限制(constraints)，例如：两个item IDs的向量应更接近，不仅是对于它们的共现，而且对于它们共享相同的product ID, store ID, brand ID或cate-level1 ID等。相反的，attribute IDs等价于包含在对应item IDs内的信息。以store ID为例，对于一个指定store ID的embedding vector，它可以看成是应该商店所售卖的所有item IDs的合适的总结(summary)。 相应的，我们定义了：

\[p(item_i | ID_s(item_i)) = \sigma(\sum\limits_{k=2}^K w_{ik} e_{i1}^T M_k e_{ik})\]

…(11)

其中，\(M_k \subset R^{m_1 \times m_k} (k=2, \cdots, K)\)是一个转移矩阵，它会将embedding vector \(e_{i1}\)转称到相同维度的embedding vector \(e_{ik}\)上。接着，我们最大化下面的平均log概率：

\[J = \frac{1}{N} \sum\limits_{n=1}^N ( \sum\limits_{-C \leq j \leq C}^{1 \leq n+j \leq N, j \neq 0} log p(ID_s(item_{n+j}) | ID_s(item_n)) \\ + \alpha log p(item_n | ID_s(item_n)) - \beta \sum_{k=1}^K \| M_k \|_2)\]

…(12)

其中，\(\alpha\)是介于IDs间的约束强度，\(\beta\)是在转移矩阵上的L2正则的强度。

我们的方法可以将item ID和它的attrbute IDs嵌入到一个语义空间中，它很有用。item ID的属性和它的attrbute IDs对于一个相对长的时间来说是稳定的，该jointly embedding model和学到的表示会每周更新一次。

3.5 Embedding User IDs

用户偏好受item IDs交互序列的影响，通过对交互的item IDs的embedding vectors做聚合来表示user IDs是合理的。有许多方法来聚合item embedding vectors，比如：Average, RNN等[26]，本paper中使用的是平均方式（Average）。

由于Hema中的用户偏好变化很快，user IDs的embedding vectors也应进行频繁更新（比如：按天更新），来快速响应最新的偏好。不同于RNN模型，它需要训练过程并且计算开销很大，Average可以在很短的时间内学习和更新表示。

对于用户\(u \in U\)，假设\(S_u = [item_1, \cdots, item_t, \cdots, item_T]\)表示交互序列，其中最近的T个item IDs以逆时序的方式排列。我们为用户u构建了embedding vector：

\[Embedding(u) = \frac{1}{T} \sum\limits_{t=1}^{T} e_t\]

其中，\(e_t\)是\(item_t\)的embedding vector。

3.6 模型学习

对该jointly embedding model进行优化等同于最大化(12)的log似然，它与log-uniform negative-sampling相近。为了解决该最优化问题，我们首先使用“Xavier” initialzation来初始化所有可训练参数。接着使用SGD算法和shuffled mini-batches到J上。参数的更新通过BP+Adam rule来完成。为了加速并行操作，在NVIDIA-GPU+tensorflow上训练。

模型的超参数设置如下：context window C=4; negative samples数 S=2; embedding dimensions为 \([m_1, m_2, m_3, m_4, m_5, m_6, m_7] = [100, 100, 10, 20, 10, 10, 20]\)；constraints强度\(\alpha=1.0\)；L2 reg强度 \(\beta=0.01\)；batch size=128, 训练5个epochs。

#

参考

• 1.Kui Zhao etc. 《Learning and Transferring IDs Representation in E-commerce》

netflix在《The Netflix Recommender System: Algorithms, Business Value, and Innovation》中，提到了一个指标：ECS（EFFECTIVE CATALOG SIZE）。我们来看下它的实现：

EFFECTIVE CATALOG SIZE

假设我们在视频库（catalog）中具有N个items，它们根据在线观看时长（hours streamed）从最流行到最不流行进行排序，表示成\(v_1, \cdots, v_N\)。假设 vector \(p=[p_1, \cdots, p_N]\)表示概率质量函数( probability mass function (p.m.f.))，对应于来自在catalog中按流行度排序的视频的时间流的share，也就是说，\(p_i\)是所有（hours streamed）的share，它来自于第i个最流行的流视频 \(v_i\)。注意，对于\(i=1, \cdots, N-1\)以及\(\sum_{i=1}^N p_i=1\)来说，\(p_i \geq p_{i+1}\)。我们寻找这样一个metric：它是关于p作为参数、输出在范围[1, N]内的一个函数，在某种程度上告诉我们，需要有多少视频来解释一个典型的hour streamed。如果最流行视频\(v_1\)占据着大多数hours streamed，该metric应返回一个略高于1的值；如果catalog中的所有视频具有相同的流量，则返回一个N值。这样的一个metric称为effective catalog size（ECS），它的定义如下：

\[ECS(p) = 2(\sum\limits_{i=1}^N p_i i) - 1\]

…(1)

等式(1)会简单计算在p.m.f. p下视频索引（video index）的平均，并将它重新缩放（rescale）到合理区间上。很容易确认，对于所有的i，当\(p_1=1\)时，ECS具有一个最小值1；当\(p_i = 1/N\)时具有一个最大值N。

ECS可以被应用到任意p.m.f.上。我们可以计算一个索引（refenerce）开始，对于该p.m.f的ECS只会考虑最流行的k个视频的hours，随着我们从1到N递增k。特别的，我们定义了\(p(k) = \alpha [p_1, \cdots, p_k]\)，其中，\(\alpha = 1/(\sum\limits_{i=1}^k p_i)\)是一个归一化常数，并绘制了ECS(p(k))来区分不同的k，得到如图4所示的黑线。该线位于identity line(没显示)之下，因为并不是所有视频都具有相同的流行度。在同一图中的红线是使用ECS等式到一个不同的p.m.f q(k)上的结果，k从1到N。p.m.f. q(k)是来自每个关于k的PVR rank的share of hours，或者来自top k PVR ranks的所有streamed hours之外的。为了形成q(k)，对于我们的每个会员（members），我们采用k个最高ranked PVR videos，来寻找由这些member-video pairs生成的所有streaming hours，并定义了它的第i个entry作为这些来自PVR rank i的streaming hours的share。注意，尽管对于每个member q(k)和p(k)一样只包含了k个videos，跨members的一个抽样，更多videos（可能为N）会出现，因为PVR是个性化的。PVR rank对应于跨所有播放（plays）的中位数rank（median rank），effective catalog size是4倍于unpresonalized effective catalog size。

#

effective catalog size(ECS)是一个这样的metric，它描述在我们的catalog中，跨items的扩展观看（spread viewing）的程度。如果大多数viewing来自于单个视频，它会接近于1。如果所有视频会生成相同量的viewing，ECS会接近于在catalog中的视频数。否则，它介于两者之间。ECS的描述见上一节。

如果没有个性化，所有用户（members）会接收到相同的视频推荐。图4左侧的黑线表明，没有个性化的ECS是如何随着数据中视频数的增长而增长的，从最流行的视频开始，随着x轴向右移动添加下一个流行(next popular)的视频。另一方面，相同图中的红色，展示了ECS是如何增长的，它是一个关于用来进个性化的PVR ranks数目的函数（而非一个关于包含视频数的函数）。尽管是否进行个性化的catalog exploration的量不同之处很显著，但它还不够令人信服。毕竟，我们可以通过对每个session提供完全随机的推荐来进行扩展观看（spread viewing）。

更重要的，个性化允许我们极大增加推荐的成功率。达到该目标的一个metric是take-rate：产生一个播放所提供的推荐比例。图4右侧展示了take-rate，一个是关于视频流行度的函数，另一个是video PVR rank的函数。我们从推荐中获得的在take-rate上的提升是大幅度的。但是，更重要的是，当推荐被正确生产和使用时，会产生在产品（比如：streaming hours）上整体engagement上的大幅提升，以及更低的订阅取消率。

图4

参考

• 1.https://dl.acm.org/doi/pdf/10.1145/2843948