阿里在KDD 2018上开放了它们的方法:《Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba》, 我们来看下:

介绍

互联网技术持续改变着商业版图,电商变得无处不在。Alibaba blala,10亿用户,2017 GMV是37670亿rmb,2017收入是1580亿rmb。blala。

淘宝有10亿users和2亿items,最重要的问题是,如何帮助用户快速发现需要和感兴趣的items。推荐系统对于达成这个目标来说至关重要。例如,淘宝移动APP的主页(图1),会基于用户过去的行为结合推荐技术生成,贡献了40%的总推荐流量。再者,在淘宝上,收入和流量的大头都来自推荐。简言之,推荐是taobao和alibaba的GMV和收入的核心引擎。尽管在学术界和工业界大多数推荐方法都能获得成功(例如:CF,基于内容的方法,基于deeplearning的方法),但是在淘宝,这些方法面对的问题变得更严峻,因为有海量的用户和海量的items存在。

图1: 虚线框的区域对于淘宝10亿用户来说是个性化的。为了更好的用户体验,吸引人的图片和方案描述也同样是生成的。注意,Taobao移动端主页贡献了40%的总推荐流量

这里淘宝推荐系统有三个主要的技术挑战:

  • 可扩展性(Scalability):尽量许多已经存在的推荐方法可以在小规模数据集上能很好工作(例如:数百万的users和items),但它们通常会在淘宝的海量数据集上试验失败。
  • 稀疏性(Sparsity):由于用户趋向于只与小部分的items交互,特别是当users或items只有少量交互时,很难训练一个精准的推荐模型。这通常被称为“sparsity”问题。
  • 冷启动(cold start):在淘宝,数百万的新items会在每小时持续被上传。这些items没有用户行为。处理这些items、或者预测用户对这些items的偏好是个挑战,这被称为“cold start”问题。

为了解决这些挑战,我们在淘宝技术平台上设计了two-stage推荐框架。第一阶段称为matching,第二阶段为ranking。在matching阶段,我们会生成一个候选集,它的items会与用户接触过的每个item具有相似性;接着在ranking阶段,我们会训练一个深度神经网络模型,它会为每个用户根据他的偏好对候选items进行排序。由于上述挑战的存在,在两个阶段都会面临不同的问题。另外,每个阶段的目标不同,会导致技术解决方案的不同。

在本paper中,我们主要关注如何解决在matching阶段的挑战,其中,核心任务是,基于用户行为,计算所有items的两两(pairwise)相似度。在获取items的pairwise相似度后,我们可以生成一个items候选集合,进一步在ranking阶段使用。为了达到该目的,我们提出了根据用户行为历史构建一个item graph,接着使用state-of-art的graph embedding方法[8,15,17]来学习每个item的embedding,这被称为BGE(Base Graph Embedding)。在这种方式下,我们可以基于items的embeddings向量进行点乘来计算候选items集合的相似度。注意,在之前的工作中,基于CF的方法来计算这些相似度。然而,基于CF的方法只考虑了在用户行为历史上的items的共现率。在我们的工作中,会在item graph中使用random walk,来捕获items间的高维相似性。这样,它比基于CF的方法要好。然而,为少量或者没有交互行为的items学到精准的embeddings仍是个挑战。为了减轻该问题,我们提供了使用side information来增强embedding过程,这被称为使用Side information的Graph Embedding(Graph Embedding with Side information (GES))。例如,属于相似的类目或品牌的items在embedding space空间应更接近。在这种方式下,即使items只有少数互交或没有交互,我们也可以获取精确的items embedding。然而在淘宝,有许多种类型的side information。比如类目(category)、品牌(brand)、或价格(price)等,直觉上不同的side information对于学习items的embeddings的贡献也不一样。因而,我们进一步提出了一种加权机制来使用,这被称为Enhanced Graph Embedding with Side information(EGES)

总之,matching阶段有三个重要的部分:

  • (1) 基于在淘宝这些年的实践,我们设计了一个有效的启发式方法,基于在淘宝上10亿多用户的行为历史来构建item graph。
  • (2) 我们提供了BGE,GES和EGES,来学习在淘宝上20亿items的embeddings。我们进行离线实验来演示:GES和EGES与BGE、以及其它embedding方法对比的效果。
  • (3) 为了部署十亿级users和items的方法,我们基于baobao XTensorflow(XTF)平台来构建graph embedding systems。我们展示了提出的框架可以极大提升在taobao移动端app上的推荐效果,同时能满足在双十一节上的训练效率和实时服务。

paper的其余部分组织如下:第2节介绍三种embedding方法。第3节介绍离线和在线实验结果。第4节介绍在taobao上的系统部署。第5节回顾相关工作。第6节收尾。

2.框架

这一节,首先引入graph embedding的基础,接着详述如何从用户行为历史上构建item graph。最后,我们研究了在淘宝上进行学习items embeddings的方法。

2.1 前提条件

本节,我们会给出一个关于graph embedding的总览,会采用一个很流行的方法:DeepWalk;在此基础上,我们提出了在matching阶段我们的graph embedding方法。给定一个graph:,其中V和E分别表示节点集合和边集合。Graph embedding会为空间上的每个节点学习一个低维表示,其中。换句话说,我们的目的是,学习一个映射函数:,(即:在V中的每个节点表示成一个d维向量)。

在[13,14]中,提出了word2vec来学习在语料中的每个词的embedding。受word2vec的启发,Perozzi等提出了DeepWalk来学习在graph中每个节点的embedding。首先通过运行在graph中的random walk来生成节点序列,接着应用Skip-Gram算法来学习在graph中的每个节点表示。为了维持该graph的拓朴结构,他们需要解决以下的优化问题:

…(1)

其中,是节点v的邻节点,可以被定义为从v开始在一跳或两跳内的节点。定义了给定一个节点v后,具有上下文节点c的条件概率。

在本节的其它部分,我们首先会介绍如何从用户行为中构建item graph,接着提供了基于DeepWalk的graph embedding方法来生成在taobao上20亿item上的低维表示。

2.2 根据用户行为构建item graph

图2: 淘宝graph embedding总览: a) **用户行为序列:用户u1对应一个session,u2和u3分别各对应一个session;这些序列被用于构建item graph;b) 有向加权item graph(weighted directed item graph); **c)在item graph上由random walk生成的序列; d) **使用Skip-Gram生成embedding

在本节,我们详述了从用户行为构建item graph。现实中,在淘宝上一个用户的行为趋向于如图2(a)所示的序列。之前基于CF的方法只考虑了items的共现,但忽略了顺序信息(可以更精准地影响用户的偏好)。然而,不可能使用一个用户的整个历史,因为:

  • 1.计算开销和存储开销会非常大
  • 2.一个用户的兴趣趋向于随时间漂移

因此,实际上,我们设置了一个时间窗口,只选择用户在该窗口内的行为。这被称为是基于session的用户行为(session-based)。经验上,该时间窗口的区间是一个小时。

如果我们获取基于session的用户行为,如果两个items它们连续出现,会通过一个有向边进行连接,例如:图2(b)的item D和item A是连接的,因为在图2(a)中用户顺序访问了item D和A。通过利用在淘宝上所有用户的协同行为,我们会为每条边基于在所有用户行为的行连接items中的出现总数分配一个权重。特别的,在所有用户行为历史中,该边的权重等于item i转向item j的频次。这种方法中,构建的item graph可以基于所有用户行为表示不同items间的相似度。

实际上,在我们抽取了用户行为序列之前,我们需要过滤一些非法数据和异常行为来为我们的方法消除噪声。下述行为会被我们的系统认定为噪声:

  • 如果在一次点击后的停留时长少于1秒,该点击可能是无意识的,需要被移除。
  • 在淘宝中有许多”过度活跃(over-active)”用户,它们实际上是有害用户(spam users)。根据我们在淘宝上的时长观察,如果在三个月内,单个用户购买1000个items或者他/她的总点击数超过3500个items,该用户非常可能是一个spam user。我们需要过滤掉这些用户的行为。
  • 淘宝零售商们(Retailers)会保持更新一个商品(commodity)的详情。极端情况下,在淘宝上的一个商品可能在一连串更新后,虽然相同的id,但很可能变成了不同的item。因而,这种item也会根据id进行移除。

2.3 基于图的Embedding(BGE)

在我们获取weighted directed item graph后,表示。我们采用DeepWalk来学习在图G中的每个节点的embedding。假设M表示G的邻近矩阵(adjacency matrix),表示从节点i指向节点j的加权边。我们首先基于随机游走生成节点序列,接着在这些序列上运行Skip-Gram算法。随机游走的转移概率定义如下:

…(2)

其中,表示出链(outlink)的邻节点集合,例如,从出发指向在所有节点的边。通过运行随机游走,我们可以生成如图2(c)所示的许多序列。

接着,我们使用Skip-Gram算法来学习embeddings,它会最大化在获取序列上的两个节点间的共现概率。这会生成以下的优化问题:

…(3)

其中,w是在序列中上下文节点的window size。使用独立假设,我们具有:

…(4)

应用negative sampling,等式4可以转换成:

…(5)

其中,是对于的负采样,是sigmoid函数。经验上,越大,获得的结果越好。

2.4 使用Side Information的GE(GES)

通过应用2.3节的embedding方法,我们可以学到在淘宝上的所有items的embedding,来捕获在用户行为序列上的更高阶相似度,这种特性会被基于CF的方法忽略。然而,对于“冷启动(cold-start)”的items,学到精准的embeddings仍然是个挑战。

为了解决冷启动问题,我们提出了增强式BGE,它会使用side information来与冷启动items做绑定。在商业推荐系统的场景中,side information常指关于一个item的:类目(category),shop(商名),价格(price)等,它们常被当成是ranking阶段的关键特征而广泛使用,但很少用于matching阶段。我们可以通过将side information合并到graph embedding中来缓合cold-start问题。例如,优衣库(UNIQLO:相同店)的两款卫衣(相同类目)可能很相似,一个喜欢Nikon镜头的用户,也可能对Canon相机感兴趣(相似类目和相似品牌)。这意味着这些具有相似的side information的items也可在embedding空间中更接近。基于这个猜想,我们提出了如图3的GES方法。

图3: GES和EGES的总框架。SI表示side information,其中”SI 0”表示item自身。惯例上,1)对于items和不同的SIs,稀疏特征趋向于one-hot-encoder vectors。 2) Dense embeddings是items和相应的SI的表示 3) hidden representation是一个item和它相应的SI的聚合embedding

为了清晰些,我们对概念做了精微调整。我们使用W来表示items或者side information的embedding matrix。特别的,表示item v的embedding,表示绑定到item v上的第s个类型的side information的embedding。接着,对于item v,使用n种类型的side information,我们具有n+1个向量,其中,d是embedding的维度。注意,item embeddings和side information embeddings的维度,经验上设置为相同的值。

如图3所示,为了合并side information,我们为item v将n+1个embedding vectors进行拼接,增加一个layer,使用average-pooling操作来将所有与item v的embeddings进行聚合,它是:

…(6)

其中,是item v的聚合embeddings。这种方法中,我们将side information以这样的方式合并,从而使具有相近side information的items可以在embedding空间内更接近。这会为cold-start items的embeddings更精准些,并且提升了在线和离线的效果。(见第3节)

2.5 增强型EGS(EGES)

尽管GES可以获得收益,但在embedding过程中集成不同类型的side information时,仍存在一个问题。等式(6)中,不同类型的side information对最终的embedding的贡献是相等的,在现实中这不可能。例如,一个购买了IPhone的用户,趋向于会浏览Macbook或者Ipad,因为品牌都是”Apple”;而一个购买了多个不同品牌衣服的用户,出于便利和更低价格,还会在相同的淘宝店上继续购买。因此,不同类型的side information对于在用户行为中的共现items的贡献各不相同。

为了解决该问题,我们提出了EGES方法来聚合不同类型的side information。该框架与GES相同(见图3)。不同之处是,当embeddings聚合时,不同类型的side information具有不同贡献。 因而,我们提出了一个加权平均的average layer来聚合与items相关的side information的embeddings。给定一个item v,假设是权重矩阵(weight matrix),条目是第i个item、第j个类型side information的权重。注意,,例如,A的第一列,表示item v的权限自身。出于简洁性,我们使用来表示关于第v个item的第s个类型的side information的权重,表示item v自身的权重。加权平均层(weighted average layer)会结合不同的side information,定义如下:

…(7)

其中,我们使用来替代,以确保每个side information的贡献大于0, 被用于归一化不同类型side information的embeddings的相关权重。

在训练数据中,对于节点v和它的上下文节点u,我们使用来表示它的embedding,y来表示label。接着,EGES的目标函数变为:

…(8)

为了求解它,梯度求导如下:

…(9)

对于第s个side information:

…(10)

…(11)

EGES的伪代码如算法1如示,加权Skip-Gram updater的伪代码如算法2所示。最终每个item的隐表示通过等式(7)来计算:

算法一:

算法二:

3.实验

本节中,我们引入大量实验来演示这些方法的效果。首先通过链接预测任务评估方法,然后是在Taobao移动端APP上的在线实验。最终,我们提出一些真实case来进一步深入这些方法。

3.1 离线评估

链接预测(Link Prediction)。链接预测任务被用于离线实验,因为它是在网络中的一个基础问题。给定移除某些边的一个网络,预测任务是预测这些链接的出现概率。根据在[30]中相似的实验设置,1/3的边被随机选中及移除,在测试集中作为ground truth,图中剩余的边作为训练集。在测试集中,相同数目的没有边连接的节点对(node pairs)会被随机选中作为负样本。为了评估链接预测的效果,使用AUC得分作为metric。

数据集:我们使用两个数据集来进行链接预测任务。第一个是Amazon Electronics数据集。第二个从Taobao移动端APP抽取。两个数据集都包含了不同类型的side information。对于Amazon数据集,item graph可以从“共同购买(co-purchasing)”的关系中被构建(在提供的数据中由also_bought表示),使用了三种类型的side information,例如:类目(category),子类目(sub-category)以及品牌。对于Taobao数据集,item graph通过第2.2节的方法购建。注意,为了效率和效果,在Taobao真实生产环境中,使用了12种类型的side information,包括:零售商(retailer), 品牌(brand), 购买级别(purchase level), 年代(age), 适用性别(gender), 风格(style), 等等。这些类型的side information根据这些年在taobao的实际经验很有用。两个数据集的统计如表1所示。我们可以看到两个数据集的稀疏性大于99%。

表1

比较方法。引入了4种方法进行实验:BGE, LINE, GES和EGES。LINE在[17]中被提出,它可以捕获在graph embedding中的第一阶和第二阶的邻近关系。我们使用由作者提供的实现,使用第一阶和第二阶邻近(LINE(1st)和LINE(2nd))来运行它。我们实现了其它三种方法。所有这些方法的embedding维度都设置为160.对于我们的BGE、GES和EGES,随机游走的长度为10, 每个节点的walks数目为20, 上下文窗口为5.

表2

结果分析。结果如表2所示。我们可以看到GES和EGES的AUC效果在两个数据集上都要好于BGE、LINE(1st)和LINE(2st)。另换,稀疏性问题也通过合并side information而缓合。当比较Amazon和Taobao的效果时,我们可以看到,在taobao数据集上的效果增益更大。我们将它归功于在Taobao数据集上使用了更多类型的有效的、有信息量的side information。当比较GES和EGES时,我们可以看到,在Amazon上的效果收益比在Taobao上的要大。这可能归功于Taobao的效果已经非常好了,比如:0.97.因而,EGES的提升不显著。在Amazon dataset上,EGES在AUC上的效果要好于GES。基于这些结果,我们可以观察到合并side information对于graph embedding非常有效,准确率可以通过对多个side information的mebeddings进行加权聚合而提升。

图4 2017年11月连续7天内不同方法的在线CTR

3.2 在线A/B test

我们在一个A/B testing框架下进行在线实验。实验的目标是在Taobao APP主页上的CTR。我们实现了上述的graph embedding方法,接着为每个item生成多个相似的items作为推荐候选。最终在Taobao主页(见图1)上的推荐结果,由基于一个DNN模型的ranking引擎生成。在实验中,我们在ranking上使用相同的方法对候选排序。如上所述,相似items的质量直接影响着推荐结果。因而,推荐效果(例如:CTR)可以受matching阶段不同的方法而影响。我们在A/B test框架上部署了4个方法。并对2017年11月中的7天的结果进行展示(如图4)。注意,“Base”表示一个item-based CF的方法,在graph embedding方法部署之前,它被广泛用于淘宝上。它会根据item的共现以及用户投票权重,计算两个items间的相似度。该相似度可以很好地进行调参、并很适合淘宝电商。

从图4我们可以看到,EGES和GES在CTR上的效果要好于BGE、以及Base方法,这展示了在graph embedding上合并side information的效果。另外,Base的CTR要大于BGE。这意味着,经过良好调参的CF-based方法可以战胜简单的embedding方法,因为在实际中会大量使用人工经验的策略。另一方面,EGES会一直胜过GES,它在3.1节的离线实验中一致。这进一步演示了,side information的加权聚合要胜过平均聚合。

3.2 案例研究

在本节中,我们提出了一些在taobao的真实案例,来展示这些方法的效果。这些case会检查三个方面:

  • 1.通过EGES的embedding可视化
  • 2.冷启动items
  • 3.在EGES中的权重

3.3.1 可视化

在本部分,我们会将由EGES学到的items的embeddings进行可视化。我们使用由tensorflow提供的可视化工具。结果如图7所示。从图7(a),我们可以看到不同类目(categories)的鞋子会在不同的聚类中。这里一种颜色表示一个类目,比如:羽毛球,乒乓球,足球。它演示了学到的合并side information的embeddings的效果。例如,具有相似side information的items在embedding空间中应更接近。从图7(b)看到,我们进一步分析三种鞋子的embeddings:羽毛球,乒乓球,足球。在embedding空间中,羽毛球和乒乓球相互很接近,而足球更更远些。这可以被解释成:在中国,喜欢羽毛球的人很多也喜欢打乒乓球。然而,喜欢足球的人与喜欢户内运动(羽毛球和乒乓球)的人则相当不同。推荐羽毛球鞋给这些观看过乒乓球鞋的人效果要好于推足球鞋的。

3.3.2 冷启动items

图5: 冷启动item的相似items。展示了top4相似的items。注意:这里的”cat”表示category.

在本部分,我们展示了冷启动的embeddings质量。对于在淘宝上刚更新的一个新item,在item graph中没法学到embedding,之前基于CF的方法也不能处理冷启动问题。然而,我们可以将一个冷启动item使用它的side information进行表示。结果如图5所示。我们可以看到,尽管对于两个冷启动items来说缺失用户行为,但可以利用不同的side information来有效学习它们的embeddings,在top相似的items上。在图中,我们为每个相似的item做了注释,连接到冷启动item上的side information的类型。我们可以看到,items的所属商店(shops)是用于衡量两个items相似度上非常重要的信息,它也会在下面部分使和每个side information的权重进行对齐。

图6: 不同items的不同side information的weights. 这里的”Item”表示一个item本身的embedding

3.3.3 在EGES中的权重

我们会为不同的items作不同类型side information权重可视化。每个在不同类目上的8个items会被选中,与这些items相关的所有side information的权重会从学到的weight matrix A中抽取。结果如图6所示,其中,每一行记录了一个item的结果。可以观察到许多注意点:

  • 1.不同items的weight分布很不同,它们会与我们的猜假一致,不同的side information对于最终的表示来说贡献是不同的。
  • 2.在所有items中,”Item”的权重,表示了item自身的embeddings,会一直大于其它的side information的权重。必须承认的是,一个item自身的embedding仍然是用户行为的主要源,其中side information提供了额外的提示来推断用户行为。
  • 3.除了”Item”外,”Shop”的权重会一直大于其它side information的权重。这与淘宝的用户行为相一致,也就是说,用户可能出于便利或更低价格因素,趋向于购买在相同店内的items。

图7: 随机选中的鞋子的一个集合的embedding可视化。item embeddings通过PCA被投影到一个2D平面上。不同颜色表示不同的categories。相同category中的Item被一起分组。

4.系统部署和操作

本节中介绍graph embedding方法在淘宝的实现和部署。首先给出对淘宝整个推荐平台的一个大体介绍,接着详述与embedding方法相关的模块。

图8: 淘宝推荐平台的架构

在图8中,我们展示了推荐平台的架构。该平台包含了两个子系统:online和offline。对于online子系统,主要组件是TPP(Taobao Personality Platform:淘宝个性化平台)和RSP(Ranking Service Platform: 排序服务平台)。一个典型的workflow如下所示:

  • 当用户加载淘宝移动APP时,TPP会抽取用户最新的信息,并从离线子系统中检索一个items候选集,它们会接着被fed进RSP。RSP会使用一个fine-tuned DNN模型对items候选集进行排序,接着返回相应的排序结果给TPP。
  • 当用户在淘宝内浏览时,它们的行为会被收集和存储成离线子系统中的日志。

offline子系统的workflow,包含了graph embedding的实现和部署,如下描述:

  • 包含用户行为的日志会被检索。item graph会基于用户行为进行构建。实际上,我们会选择最近三个月的日志。在生成基于session的用户行为序列之前,会对数据进行anti-spam。留下的日志包含了6000亿条目。item graph会根据2.2节的方法进行构建。
  • 为了运行我们的graph embedding方法,会采用两种实际方法:1) 整个graph划分成许多个sub-graphs,它们可以通过Taobao的ODPs(Open Data Processing Service)分布式平台进行处理。每个subgraph有将近5000w个节点。2)为了生成random walk序列,我们在ODPs中使用基于迭代的分布式图框架。通过random walk生成的序列总是将近1500亿。
  • 为了实现该embedding算法,在我们的XTF平台上使用了100个GPU。在部署平台上,使用1500亿样本,在离线子系统中的所有模块,包含日志检索、anti-spam、item图构建、通过random walk生成序列、embedding、item-to-item相似度计算以及map生成,执行过程小于6个小时。这样,我们的推荐服务可以在非常短时间内响应用户最近行为。

参考

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 被定义成一个关于该用户点击的M个listing ids连续序列。当在两个连续的用户点击之间超过30分钟的时间间隔时,启动一个新的session。给定该数据集,目标是为每个唯一的listing 学习一个d维的real-valued表示: ,以使相似的listing在该embedding空间中更接近。

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

…(1)

从被点击的listing 的上下文邻居上观察一个listing 的概率,使用softmax定义:

…(2)

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

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

…(3)

其中要学的参数是:, . 优化通过随机梯度上升法(SGA)完成。

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

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

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

…(4)

其中,是预订listing 的embedding。对于 exploratory session来说,更新仍会由(3)的最优化进行管理。

图1

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

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

…(5)

其中要学习的参数有:,

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

在listing创建时,需要提供listing的信息,比如:位置,价格,listing type等。我们利用这些关于listing的meta-data来发现3个地理位置上接近的listings(在10公里内),它们具有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。它使用点击sessions进行训练,能很好地发现相同market间的listings相似度。这样,他们更适合短期(short-term)、session内(insession)、个性化的需求,目标是展示给user listings,他们与在搜索session期间点击的listing相似。

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

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

  • 1.booking sessions数据比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,它是一个二人间,1床,一个卧室 & 1个浴室,每晚平均价格为60.8美刀,每晚每个客人的平均价格为29.3美刀,5个评价,所有均5星好评,100%的新客接受率(New Guest Accept Rate),可以映射为: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、带有MacBook laptop,英文设置、具有用户照片的全轮廓,83.4%平均5星率,它在过去有3个预订,其中关于booked listings的平均统计是:52.52美刀 Price Per Night, 31.85美刀 Price Per Night Per Guest, 2.33 Capacity, 8.24 Reviews and 76.1% 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中。特别的,我们形成了一个集合,它由N个用户的个booking sessions组成, 其中每个session 被定义成一个关于booking事件的序列,例如:按时间顺序排列的(user_type, listing_type)元组。注意,每个session由相同user_id的bookings组成,然而,对于单个user_id来说,他们的user_types可以随时间变化,这一点与下述情况相似:相同listing的listing_types会随着他们接受越来越多的bookings按时间变化。

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

…(6)

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

…(7)

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

图5

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

拒绝的显式负样本。不同于点击只影响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看成是显式负样本,以如下方式公式化。除了集合,我们会生成一个集合,它由涉及到rejection事件的user_type和listing_type的pairs()组成。如图5b所示,我们特别关注,对于同一用户,当在对于另一个listing的成功预定(通过一个正号标记)之后主人拒绝(通过一个负号-标记)。新的目标函数可以为:

更新一个的中心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)

更新一个的中心item: …(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.实验

参考

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

介绍

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

在处理海量corpus时,为了减少计算量,基于内存的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中的每个节点,除了根节点外,具有一个父节点、以及特定数目的子节点。特别的,在语料C中的每个item ,仅仅只对应于树中的一个叶子节点,这些非叶子节点是粗粒度概率。不失一般性,我们假设节点是根节点。一个关于树的示例如图2右下角所示,在其中,每个圆表示一个节点,节点的数字是在树中的索引。该树总共具有8个叶子节点,每个都对应于语料中的一个item。值得一提的是,给定的示例是一个完全二叉树,我们不会在我们的模型中强制完全二叉。

3.2 相关工作

有了树结构,我们首先引入hierachical softmax来帮助区分TDM。在hierachical softmax中,树中的每个叶子节点n,从根节点出发到该节点具有唯一编码。例如,如果我们假定:左分枝为1,右分枝为0, 那么图2中树的编码为110, 的编码为000. 注意,是在第j层的节点n的编码。在hierachical softmax的公式中,下个词的概率通过上下文给定:

…(1)

其中w是叶子节点n的编码,是在第j层的n的父节点。

这种方式下,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来说,满足以下公式:

…(2)

其中是真实概率(ground truth probability),用户u对n感兴趣。是第j层指定layer的归一化项,用来确保在level上的概率和等于1。等式(2)表明,一个父节点的真实偏好等于它的子节点的最大偏好,除以归一化项。注意,我们轻微修改该概率,让u表示一个特定的用户状态(user state)。换句话说,一旦该用户有新行为,会从一个特定用户状态u转移到另一个状态u’。

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

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

假设是关于u的正负样本集合。似然函数为:

…(3)

其中是给定u的节点n的预测label。是采用用户状态u以及抽样节点n作为输入时二分类模型的输出。相应的loss函数为:

…(4)

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

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

算法1

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

我们提出的TDM方法不仅减少了预测时的计算量,也潜在地提升了推荐质量(对比起在所有叶子节点上的brute-force search)。如果没有这棵树,训练一个模型来直接发现最优items是一个很难的问题,归因于corpus size。使用树的层次化(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 DNN:
  • TDM attention-DNN-HS:

实验结果如表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

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的回报率)。详细如下:

…(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时需要更多的计算,但整个预测过程的复杂度不会大于,其中,k是所需结果的size,是corpus size,t是网络中单个feed-forward pass的复杂度。该复杂度的上界在当前CPU/GPU硬件环境下是可接受的,在单个检索中,用户侧特征可以跨不同的节点共享,一些计算可以根据模型设计被共享。在Taobao展示广告系统中,它实际上会采用TDM DNN模型,平均一次推荐需要6ms。这样的运行时间比接下来的ctr预测模型要短,不会是系统瓶颈。

6.结论

参考

前几天微软提出了一个xDeepFM算法:

介绍

传统交叉特征工程主要有三个缺点,以下部分来自paper:

  • 1.获取高质量特征代价高昂
  • 2.大规模预测系统(比如:推荐系统),存在大量原始特征(raw features),很难人工抽取所有交叉特征
  • 3.人工交叉特征不能泛化到在训练数据中未见过的交叉上

FM会将每个特征i嵌入到一个隐因子向量 上,pairwise型特征交叉可以被建模成隐向量的内积:。在本paper中,我们使用术语bit来表示在隐向量中的一个元素(比如:)。经典的FM可以被扩展到专门的高阶特征交叉上,但一个主要缺点是:会建模所有的特征交叉,包括有用组合和无用组合。无用组合会引入噪声、以及效果的下降。最近几年,DNNs越来越流行。利用DNNs可以学习复杂和可选择的特征交叉。[46]提出来FNN用于学习高阶特征交叉。它会使用对于field embedding的预训练FM,然后应用于DNN。[31]提出了PNN,它不依赖预训练的FM,而是在embedding layer和DNN layer之间引入了一个product layer。FNN和PNN的主要缺点是,它们主要更多关注高阶特征交叉,而非低阶交叉。Wide&Deep模型和DeepFM模型通过引入混合结构克服了上面的缺点,它包含了一个shallow组件以及一个deep组件,可以学到memorization和generalization。因而可以联合学习低阶和高阶特征交叉。

上面的所有模型都使用DNN来学习高阶特征交叉。然而,DNN可以以一个隐式的方式建模高阶特征交叉。由DNN学到的最终函数可以是任意形式,关于特征交叉的最大阶数(maximum degree)没有理论上的结论。另外,DNNs在bit-wise级别建模征交叉,这与FM框架不同(它会在vector-wise级别建模)。这样,在推荐系统的领域,其中DNN是否是用于表示高阶特征交叉的最有效模型,仍然是一个开放问题。在本paper中,我们提供了一个基于NN的模型,以显式、vector-wise的方式来学习特征交叉。我们的方法基于DCN(Deep&Cross Network)之上,该方法能有效捕获有限阶数(bounded degree)的特征交叉。然而,我们会在第2.3节讨论,DCN将带来一种特殊形式的交叉。我们设计了一种新的压缩交叉网络CIN(compressed interaction network)来替换在DCN中的cross network。CIN可以显式地学到特征交叉,交叉的阶数会随着网络depth增长。根据Wide&Deep模型和DeepFM模型的精神,我们会结合显式高阶交叉模块和隐式交叉模型,以及传统的FM模块,并将该联合模型命名为“eXtreme Deep Factorization Machine (xDeepFM)”。这种新模型无需人工特征工程,可以让数据科学家们从无聊的特征搜索中解放出来。总结一下,主要有三个贡献:

  • 提出了一种新模型xDeepFM,可以联合训练显式和隐式高阶特征交叉,无需人工特征工程
  • 设计了CIN来显式学习高阶特征交叉。我们展示了特征交叉的阶(degree)会在每一层增加,特征会在vector-wise级别进行交叉。
  • 我们在三个数据集中进行了实验,结果展示xDeepFM效果好于其它state-of-art模型

2.PRELIMINARIES

2.1 Embedding Layer

在CV或NLP领域,输入数据通常是图片或文本信号,它们空间相关(spatially correlated)或时序相关(temporally correlated),因而DNN可以被直接应用到dense结构的原始特征上。然而,在推荐系统中,输入特征是sparse、高维、没有明显地空间相关或时序相关。因此,multi-field类别形式被广泛使用。例如,一个输入实例为: [user_id=s02,gender=male,organization=msra,interests=comedy&rock]

通过field-aware one-hot进行编码成高维稀疏特征:

在原始特征输入上使用一个embedding layer,可以将它压缩到一个低维、dense、real-value vector上。如果field是一阶的(univalent),feature embedding被当成field embedding使用。以上述实例为例,特征(male)的embedding被当成field gender的embedding。如果field是多阶的(multivalent),feature embedding的求和被用于field embedding。embedding layer如图1所示。embedding layer的结果是一个wide concatenated vector:

其中,m表示fields的数目,表示一个field的embedding。尽管实例的feature长度可以是多变的,它们的embedding具有相同的长度 m x D, 其中D是field embedding的维数。

图1: field embedding layer。本例中embedding的维度是4

2.2 隐式高阶交叉

FNN, Deep&Cross,以及Wide&Deep的deep part会使用一个在field embedding vector e上的feed-forward神经网络来学习高阶特征交叉。forward process是:

…(1)

…(2)

其中,k是layer depth,是激活函数,是第k层的output。可视化结构与图2展示的非常像,但不包括FM layer或Product layer。该结构会以bit-wise的方式建模交叉。也就是说,相同field embedding vector中的元素也会相互影响。

PNN和DeepFM在上述结构上做了小修改。除了在embedding vector e上应用了DNNs外,它们在网络中添加了一个2-way interaction layer。因而,bit-wise和vector-wise的交叉都能在模型中包含。PNN和DeepFM中主要不同是,PNN会将product layer的输出连接到DNNs中,而DeepFM会直接将FM layer连接给output unit。

图2: DeepFM和PNN的架构。我们复用了符号,其中红色边表示weight-1 connections(没有参数),灰色边表示normal connections(网络参数)

2.3 显式高阶交叉

[40]提出的Cross Network(CrossNet)它的结构如图3所示:

图3:

它可以显式建模高阶特征交叉。不同于经典的fully-connected feed-forward network,它的hidden layers通过以下的cross操作进行计算:

…(3)

其中,是第k层的weights,bias以及output。对于CrossNet能学到一个特殊类型的高阶交叉这一点我们有争论,其中,CrossNet中的每个hidden layer是一个关于的标量乘积。

theorem 2.1: 考虑到一个k层cross network,第i+1层的定义为:。接着,cross network的output 是一个关于的标量乘积。

证明如下:

k=1时,根据矩阵乘法的结合律和分配律,我们具有:

…(4)

其中,标量实际上是关于的线性回归。其中,是关于的一个标量乘。假设标量乘适用于k=i。对于k=i+1, 我们可以有:

…(5)

其中,是一个标量。其中,仍是一个关于的标量乘。通过引入hypothesis,cross network的output 是一个关于的标量乘。

注意,并不意味着是与是线性关系的。系数是与敏感的。CrossNet可以非常有效地学到特征交叉(复杂度与一个DNN模型对比是微不足道的),然而,缺点是:

  • (1) CrossNet的输出受限于一个特定的形式,每个hidden layer是关于的一个标量乘
  • (2) 交叉是以bit-wise的方式进行

3.新模型

3.1 CIN

我们设计了一个新的cross network,命名为CIN(Compressed Interaction Network),具有如下注意事项:

  • (1) 交叉是在vector-wise级别上进行,而非bit-wise级别
  • (2) 高阶特征的交叉显式衡量
  • (3) 网络的复杂度不会随着交叉阶数进行指数增长

由于一个embedding vector被看成是一个关于vector-wise 交叉的unit,后续我们会将field embedding公式化为一个矩阵:,其中,假设表示在第k层的(embedding)feature vectors的数量。对于每一层,通过以下方式计算:

…(6)

其中是第h个feature vector的参数矩阵,表示Hadamard product,例如:。注意,通过在间的交叉产生,其中,特征交叉会被显式衡量,交叉的阶数会随着layer depth增长。CIN的结构与RNN非常相似,其中下一个hidden layer的outputs取决于最近一个(the last)的hidden layer和一个额外的input。我们在所有layers上都持有embedding vectors的结构,这样,即可在vector-wise级别上使用交叉。

有意思的是,等式(6)与CNN具有很强的关联。如图4a所示,我们引入了一个内部张量(intermediate tensor) ,其中,它是hidden layer和原始特征矩阵的外积(outer products:沿着每个embedding维度)。被看成是一个特殊类型的图片,看成是一个filter。我们如图4b所示跨沿着该embedding dimension(D)滑动该filter,获得一个hidden vector ,这在CV中通常被称为一个feature map。在CIN命名中所使用的术语”compressed”表示了第k个hidden layer会将 向量的隐空间压缩到向量中。

图4c提供了CIN的一个总览。假设T表示网络的深度。每个hidden layer 具有一个与output units的连接。我们首先在hidden layer的每个feature map上使用sum pooling:

…(7)

其中,。这样,我们就得到一个pooling vector:,对于第k个hidden layer相应的长度为。hidden layers的所有polling vectors在连接到output units之前会被concatenated:。如果我们直接使用CIN进行分类,output unit是在上的一个sigmoid节点:

…(8)

其中,是回归参数。

3.2 CIN详解

我们对CIN进行分析,研究了模型复杂度以及潜在的效果。

3.2.1 空间复杂度

在第k层的第h个feature map,包含了个参数,它与具有相同的size。因而,在第k层上具有个参数。考虑到对于output unit的当前最近(the last)的regression layer,它具有个参数,CIN的参数总数是 。注意,CIN与embedding dimension D相互独立。相反的,一个普通的T-layers DNN包含了个参数,参数的数目会随着embedding dimension D而增长。

通常,m和不会非常大,因而,的规模是可接受的。当有必要时,我们可以利用一个L阶的分解,使用两个小的矩阵以及来替换

…(9)

其中以及。出于简洁性,我们假设每个hidden layer都具有相同数目(为H)的feature maps。尽管L阶分解,CIN的空间复杂度从下降到。相反的,普通DNN的空间复杂度是,它对于field embedding的维度D是敏感的。

3.2.2 时间复杂度

计算tensor 的开销是O(mHD)。由于我们在第一个hidden layer上具有H个feature maps,计算一个T-layers CIN会花费时间。相反的,一个T-layer plain DNN,会花费时间。因此,CIN的主要缺点是在时间复杂度上。

3.2.3 多项式近似(Polynomial Approximation)

接下来,我们检查了CIN的高阶交叉属性。出于简洁性,我们假设,在hidden layers上的feature maps数目,等于fields m的数目。假设[m]表示小于或等于m的正整数集。在第1层上的第h个feature map,表示为,通过下式计算:

…(10)

因此,在第1层的每个feature map会使用个系数来建模pair-wise特征交叉。相似的,在第2层的第h个feature map为:

…(11)

注意,l和k相关的所有计算在前一个hidden layer已经完成。我们在等式(11)扩展的因子是为了清晰。我们可以观察到,在第二层的每个feature map会使用新参数来建模3-way交叉。

一个经典的k阶多项式具有系数。我们展示了CIN会逼近这类型多项式,根据一个feature maps链,只需要个参数。通过引入hypothesis,我们可以证明,在第k层的第h个feature map为:

…(12)

为了更好地演示,我们参考了[40]的注解。假设表示一个multi-index,其中。我们会从中忽略原始的上标,使用来表示它,因为对于最终展开的表达式,我们只关心来自第0层(等同于field embedding)的feature maps。现在,使用一个上标来表示向量操作,比如。假设表示一个multi-vector 多项式的阶数k:

…(13)

在该类中的每个向量多项式都具有个系数。接着,我们的CIN接似系数

…(14)

其中, 是一个multi-index,是索引()的所有排列。

3.3 与隐式网络的组合

在第2.2节,plain DNNs可以学到隐式高阶特征交叉。由于CIN和plain DNNs可以互补,一个直观的做法是,将这两种结构进行组合使模型更强。产生的模型与Wide&Deep和DeepFM非常像。结构如图5所示,我们将新模型命名为eXtreme Deep Factorization Machine(xDeepFM),一方面,它同时包含了低阶和高阶特征交叉;另一方面,它包含了隐式特征交叉和显式特征交叉。它产生的output unit如下:

…(15)

其中,\sigma为sigmoid函数,a是原始特征。分别是是plain DNN和CIN的outputs。和b是可学习的参数。对于二分类,loss函数为log loss:

…(16)

其中,N是训练实例的总数。Optimization过程是最小化下面的目标函数:

…(17)

其中表示正则项,表示参数集,包含linear part,CIN part,DNN part。

图5: xDeepFM的结构

3.3.1 与FM和DeepFM的关系

假设所有field是一阶的(univalent)。如图5所示,当depth和CIN part的feature maps同时设为1时,xDeepFM就是DeepFM的一个泛化,通过为FM layer学习线性回归权重实现(注意,在DeepFM中,FM layer的units直接与output unit相连,没有任何系数)。当我们进一步移去DNN part,并同时为该feature map使用一个constant sum filter(它简单采用输入求和,无需任何参数学习),接着xDeepFM就变成了传统的FM模型。

4.实验

实验主要回答下述问题:

  • (Q1) CIN在高阶特征交叉学习上是如何进行的?
  • (Q2) 对于推荐系统来说,将显式和隐式高阶特征交叉相组合是否是必要的?
  • (Q3) xDeepFM的网络设置如何影响效果?

4.1 实验设置

4.1.1 数据集

1. Criteo Dataset:ctr预测的benchmarking dataset,对外开放。给定一个用户和他访问的页面,目标是预测它点击一个给定广告的概率。

2. Dianping Dataset:收集了6个月的关于大众点评的用户check-in活动用于餐厅推荐实验。给定一个用户的profile,一个餐厅的相应属性,该用户最近三次访问POIs(point of interest),我们希望预测它访问该餐厅的概率。对于在一个用户的check-in样本中的每个餐厅,我们会通过POI流行度抽样出在3公里内的4个餐厅作为负样本。

3.Bing News Dataset.:Bing News是微软Bing搜索引擎的一部分。我们收集了在新闻阅读服务上连续5天的曝光日志。使用前3天数据用于训练和验证,后两天数据用于测试。

对于Criteo dataset和Dianping dataset,随机将样本划分为8:1:1进行训练、验证、测试。三个数据集的特性如表1所示。

表1:评估数据计的统计。

4.1.2 评估metrics

我们使用两种metrics:AUC和LogLoss。有时更依赖logloss,因为我们需要使用预测概率来估计一个排序系统带来的收益(比如常见的CTR x bid)

4.1.3 Baselines

我们比较了xDeepFM, LR, FM, DNN, PNN, Wide&Deep, DCN, DeepFM.

4.1.4 Reproducibility

使用tensorflow来实现模型。每个模型的超参数通过在validation set上进行grid-searching调参,然后选择最好的settings。

  • learning rate设置为0.001.
  • optimization方法使用Adam。
  • mini-batch size=4096.
  • 对于DNN, DCN, Wide&Deep, DeepFM和xDeepFM,使用L2正则,对应的
  • 对于PNN,使用dropout=0.5
  • 每层neurons数目的缺省setting为:
    • (1) DNN layers为400
    • (2) 对于Criteo dataset,CIN layers为200; 对于DIanping和Bing News datasets,CIN layers=100
  • 由于本文主要关注网络结构,所有field embedding的维度统一设为固定值=10.
  • 本试验在并行化在5块tesla K80 GPUs上跑.
  • 源码为: https://github.com/ Leavingseason/ xDeepFM

效果展示部分:

表3: depth列表示单模型中的最佳深度,分别表示(cross layers, DNN layers)

4.2 Q1: 单一Neural组件间的效果比较

我们想知道CIN单独是如何执行的。注意FM会显式衡量2阶特征交叉,DNN模型可以隐式衡量高阶特征交叉,CrossNet尝试使用较少参数来建模高阶特征交叉,CIN则会显式建模高阶特征交叉。由于它实际依赖于数据集,单一模型(individual model)间的比较优势没有理论保证。例如,如果实际数据集不需要高阶特征交叉,FM可能是最好的单一模型。对于该实验,我们并不期望哪个模型表现最好。

表2展示了单一模型在三个实际数据集上的效果。令人惊讶的是,CIN的表现都要好些。另一方面,结果表明,对于实际数据集,稀疏特征上的高阶交叉是必要的,可以证实:DNN,CrossNet, CIN的效果要远好于FM。另一方面,CIN是最好的单一模型,图中展示了CIN在建模高阶特征交叉上的效果。注意,一个k-layer的CIN可以建模k阶的特征交叉。有趣的是,在Bing News dataset上,它会采用5 layers的CIN来达到最佳结果。

表2: 不同数据集下的模型表现。Depth列表示每个模型最好的网络深度

4.3 Q2: 集成模型的效果

xDeepFM会将CIN和DNN集成一个end-to-end模型。而CIN和DNN能cover在特征交叉学习上两种不同的属性,我们感兴趣的是,是否确实有必要将两者组合在一起进行explicit和implicit的joint learning。这里,我们比较了一些比较强的baselines,如表3所示。另一个有意思的观察是,所有基于neural的模型并不需要非常深的网络结构来达到最佳效果。常见的depth超参数设置为2或3, xDeepFM的最佳深度是3,可以表示最多学习4阶的交叉。

4.4 Q3: 超参数学习

  • 1.hidden layers的数目
  • 2.每层的neurons数目
  • 3.激活函数

参考

Facebook在2017年提出了《StarSpace: Embed All The Things!》,我们可以看下:

介绍

StarSpace是一种神经嵌入模型(neural embedding model ),可以广泛解决多种问题:

  • 文本分类,或者其它标注任务,比如:语义分类
  • 实体排序,比如:给定一个query,对web文档进行排序
  • 基于CF的推荐,例如:文档、音乐、或视频推荐
  • 基于内容的推荐,其中,内容通过离散特征(例如:词)定义
  • 图谱嵌入(mebedding graphs),例如,Freebase这样的多关系图谱
  • 学习词、句、文档的embeddings

相关工作

隐文本表示(或称为embeddings),是在一个大语料上使用非监督学习得到的关于词、文档的向量表示。相应的方法有:Bengio 2003 embedding, Mikolov word2vec 2013, Bojanowski fastText 2017。

在监督式embeddings领域,方法有:SSI,WSABIE, (Tang, Qin, and Liu 2015), (Zhang and LeCun 2015), (Conneau et al. 2016), TagSpace(Weston, Chopra, and Adams 2014) and fastText(Joulin et al. 2016) 。

在推荐领域,embedding模型很成功,有:SVD (Goldberg et al. 2001), SVD++ (Koren and Bell 2015),(Rendle 2010; Lawrence and Urtasun 2009; Shi et al. 2012)。这些方法中的一些方法主要关注于:CF的setup,其中user IDs和movie IDs具有单独的embeddings,比如:在Netflix挑战赛的setup(例如: (Koren and Bell 2015),新的users和items不能天然合并进去)。我们展示了StarSpace是如何天然地迎合该settings和基于content的settings,其中users和items可以被表示成features,具有天然的out-of-sample扩展,而非只是一个固定集合。

在知识图谱中的链接预测上。有s(Bordes et al. 2013) and (GarciaDuran, Bordes, and Usunier 2015)。StarSpace也可以应用于此,匹配TransE方法。

模型

StarSpace模型由学习实体(learning entities)组成,每个通过一个离散特征(bag-of-features)的集合描述。一个像(文档、句子)这样的实体可以通过bag-of-words或n-grams进行描述,一个像user这样的实体可以通过bag-of-documents、movies、items的方式进行描述。重要的是,StarSpace模型可以自由比较不同类型的实体(entities)。例如,一个用户实体可以与一个item实体、或者一个文档实体(推荐)、一个文带标签实体的文档实体等进行比较。这可以通过学习来完成,并将它们嵌入到相同的空间中,这样的比较才有意义————通过根据各自的metric进行最优化。

字典D,特征为F,那么有一个D X F的矩阵,其中表示第i维特征(行),它有d维的embedding,我们可以使用来嵌入一个实体a。

这就是说,像其它embedding模型,我们的模型通过为在该集合(称为字典,它包含了像words这样的特征)中的每个离散特征分配一个d维向量。实体由特征组成(比如:文档),被表示成一个bag-of-features,它们的embeddings可以隐式被学到。注意,一个实体可以由像单个特征(唯一)组成,比如:单个词(word)、名字(name)、user ID、Item ID。

为了训练我们的模型,我们必须学到比较实体。特别的,我们希望最小化以下的loss function:

注意:

  • 正实体对 positive entity pairs (a,b)的生成器来自于集合。这是任务非独立的,将会在下面描述。
  • 负实体的生成器来自于集合。我们使用一个k-negative sampling策略(Mikolov 2013)来为每个batch update选择k个这样的负样本对。我们会从在该实体集内随机选择,它们可能出现在相似函数的第二个参数上(例如:对于文本标注任务, a是文档,b是标签,因此我们可以从labels集合上抽样)。k的因素分析将在第4部分讨论。
  • 相似函数。在我们的txxik,我们的实现有:cosine相似度和内积,可以通过一个参数进行选定。总之,对于较少数目的label features(比如:分类),它们的工作机制很像;对于更大数目(比如:句子或文档相似度)时,cosine更好。
  • loss function为 ,它比较了positive pair (a,b),negative pairs(a, b_i^-),其中i=1,…, k. 我们也实现了两个概率:margin ranking loss(例如:,其中是margin参数),negative loss loss of softmax。所有的实验都使用前者,因为表现更好。

我们使用SGD进行最优化,例如,每个SGD step是从在outer sum中上的一个抽样,在多CPU上使用Adagrad,hogwild。我们也应用一个max norm的embeddings来将学到的向量限制在球半径为r的空间上。

在测试时,可以使用学到的函数来测量实体间的相似度。例如,对于分类,在测试时为给定输入a预测一个label,使用来表示可能的label。或者,对于ranking,通过similarity对实体进行排序。另外,embedding向量可以直接被下游任务使用,例如:word embbeding models。然而,如果直接满足你的应用需要,我们推荐使用StarSpace,它很擅长这一块。

接着,我们会描述该模型如何被应用到其它任务上:每个case会描述是如何生成的。

:positive pair generator直接来自于一个标注数据训练集,(a,b) pairs,其中,a是文档(bags-of-words),b是labels(单个features)。负实体()从可能的labels集合中被抽样。

: 在该case中,每个文档a可以具有多个正标签,其中之一在每个SGD step中从b中抽样,来实现multilabel分类。

:训练数据包含了:一个用户集合,其中每个用户通过bag-of-items进行描述(字典里的唯一特征)。positive pair生成器会选择一个user,选择a作为该user ID的唯一单个特征,以及单个item b。负实体从该可能的items中进行抽样。

基于CF的推荐,使用out-of-sample用户扩展:经典CF的一个问题是,不能泛化到新用户上,每个user ID可以学到一个独立的mebedding。与之前方法使用相同的训练数据,可以使用StarSpace学到一个新模型。该方法中,positive pair genterator会选择一个user,选择a作为除它之外的所有item,b作为left out item。也就是说,该模型会学到估计:如果一个用户喜欢一个item,可以将该用户建模成,。

基于内容的推荐:该任务包含了一个用户集合,其中,每个用户通过一个bag-of-items进行描述,其中每个item通过一个bag-of-features(来自字典)进行描述。例如,对于文档推荐,每个用户通过bag-of-documents进行描述,其中,每个文档通过bag-of-words进行描述。现在,a可以被选成除它外的所有items,b表示left out item。该系统可以扩展到新items和新users上,只要两都被特征化。

多关系知识图谱(例如:逻接预测):给定一个graph三元组(h,r,t),包含了一个head conecpt:h,一个relation:r,一个tail concept t,例如:(Beyonce,´born-in, Houston),一个可以从该graph中学习embeddings。对h, r, t的实例可以被定义成字典里中唯一features。我们可以随机均匀选择:

  • (i) a由bag-of-features:h和r 组成,其中b只包含t;
  • (ii) a由h组成,b包含了r和t.

负实体从可能的concepts中抽样得到。学到的embeddings可以通过学到的sim(a,b)被用于回答link prediction问题,比如:(Beyonce, born-in, ?) ´ or (?, born-in, Houston).

信息检索IR(例如:文档搜索)和文档嵌入:给定监督式训练数据,包含了(搜索关键词,相关文档)pairs,可以直接训练一个信息检索模型:a包含了搜索关键词,b是一个相关文档,是另一个不相关的文档。如果只提供了非监督式训练数据,它包含了未标注文档的集合,从文档中选择a的一个方法是,作为随机关键词,b作为保留词。注意,两种方法可以隐式地学习文档嵌入,可以被用于该目的。

学习word embedding:我们可以使用StarSpace来学习非监督式word embeddings,它使用训练raw text组成的数据。我们会选择a作为一个窗口的词(例如:4个words,两边各两个),b作为中间词。

学习sentence embeddings:当你可以直接学习句子的embeddings,使用上述方法来学习word embeddings、并使用它们来嵌入看起来不是最优的。给定一个未标注文档的训练集,它们由句子组成,我们选择a和b作为来自相同文档的一个句子对(pair of sentences);是来自其它文档的句子。直觉上,句子间的语义相似度在同一个文档内共享(如果文档很长的话,也可以只选择在特定距离内的句子)。再者,embeddings将会自动为关于句子长度的words sets进行最优化,因此,训练时间会与测试时间相匹配,而使用短窗口进行训练来使用word embeddings进行特殊学习——window-based embbedings可以变差,当一个句子中的words总和变得更大时。

多任务学习:任何这些任务可以组合,如果它们共享在基础字典F中的一些特征时可以同时训练。例如,可以使用非监督式word/sentence embedding,并结合监督式分类,来给出半监督式学习。

实验

略。

参考