youtube的基于深度学习的推荐系统，主要分成两大部分：

介绍

Youtube是世界上最大的创建、分享、和发现视频内容的平台。Youtube推荐负责帮助超过十亿用户从不断增长的视频语料中发现个性化内容。在本paper中，我们主要关注深度学习对youtube视频推荐的巨大影响。图1展示了youtube app主页的推荐。

图1

youtube推荐视频极具挑战性，主要有：

• 规模（Scale）：许多已经存在的推荐算法证明只能在小数据集上进行。对于youtube的海量用户和语料来说必须要有高度特定的分布式学习算法和高效的serving系统
• 新鲜度（Freshness）：Youtube具有一个非常动态的语料，每秒钟都有许多视频被上传上来。推荐系统必须对这些新上传的视频内容进行建模，从而被用户快速接受。新内容与播放良好的老视频间的平衡，则通过EE（exploration/exploitation）的角度去理解。
• 噪声（Noise）：由于稀疏性、以及多种不可观察的外部因素，youtube的历史用户行为很难去预测。我们很少能获取真实的用户满意度，只能建模含噪声的隐式反馈信号。更进一步，由于没有一个较好的知识本体（ontology）定义，与内容有关的metadata很难进行组织。我们的算法必须对这些特性足够健壮。

与Google的其它产品领域进行合作，youtube已经迁移到了深度学习作为通用解法。我们的系统构建在google Brain上，它开源了tensorflow。tensorflow提供了一个灵活的框架来实验许多DNN架构。我们的模型可以学习接近10亿参数，在数百亿的样本上进行训练。

对比与MF领域的研究，使用DNN网络进行推荐的工作还相当少。神经网络被用于新闻推荐[17]，引文[8]，评论评分[20]等。协同过滤也被公式化成DNN[22]和autoencoders[18]。Elkahky等使用深度学习对用户进行跨领域建模。在一个基于内容的设定中，Burges等使用DNN进行用户推荐。

该paper组织如下：第2节讲述系统。第3节描述候选生成模型，包括如何训练以及用于对推荐进行serving。实验结果将展示模型如何从hidden units的deep layers以及额外的异构信号受益。第4节详述了排序模型，包含经典的LR如何被修改来训练一个模型预测期望的观看时长（而非点击概率）。实验结果表明，hidden layer的深度在这种情况下有用。最后，第5节为结论。

2.系统总览

推荐系统的整体结构如图2所示。系统由两个神经网络组成，一个用于候选生成，另一个用于ranking。

图2

候选生成网络会采用youtube用户历史行为作为输入，并从一个大语料中检索出一个视频子集（数百个）。这些候选（candidates）通常与用户高度相关，带有较高的precision。候选生成网络只通过CF提供了宽泛的个性化。用户的相似度被表示成粗粒度特征，比如：视频ID，搜索query tokens和人口统计学信息（demographics）。

在列表中呈现一些“best”推荐，则需要一个细粒度的表示(representation)来在具有较高recall的候选间的区分相对重要性。ranking网络会完成该任务，它会根据一个期望的目标函数，使用用户和视频的丰富特征集合，来为每个视频分配一个分数。根据排序，最高得分的视频会呈现给用户。

这种two-stage推荐方法，允许用户从一个非常大的视频语料（数百万）做出推荐，可确定的是，只有少量视频出现在移动设备中，它们对于用户是个性化、并且是吸引人的。再者，该设计可以允许对由其它源生成的候选进行混合，比如早期描述的工作[3]。

在部署期间，我们使用离线指标（precision, recall, ranking loss等）做了大量评估，来指导我们的系统进行增量改进。然而，对于一个算法或模型的效果最终决定，还是要看真实环境上的A/B testing。在真实环境中，我们会评估在CTR、观看时长、以及其它评估用户参与度的指标上上的细微变化。这很重要，因为真实A/B结果不总是与离线实现相关。

一、候选生成

在候选生成期间，从海量的Youtube语料中晒筛选出数百个与用户相关的视频。以前的推荐系统使用MF方法来根据rank loss训练。我们的神经网络模型的每个迭代会模仿该因子分解行为，它使用只嵌入用户之前观看行为的浅层网络。从该观点上看，我们的方法可以看成是因子分解技术的非线性泛化。

3.1 推荐即分类

我们将推荐当成是一个极端多分类问题（extreme multi-class），其中预测问题变为：视频库V，有上百万的视频，某用户U，在上下文C上，在时间t时的观看行为$w_t$，刚好是某个视频i.

\[P(w_t =i|U,C)=\frac{e^{v_{i} u}}{\sum_{j \in V}{e^{v_{j} u}}}\]

其中u表示一个高维的(user,context)pair的“embedding”， v表示每个候选视频的emdedding。在该假设中，一个emdedding可以简化成一个稀疏实体的映射（视频，用户等各有一个），映射到一个N维的dense vector中。深度神经网络的任务是：学到user embeddings: u，作为用户历史和上下文的函数，这在使用一个softmax分类器对视频进行判别时有用。

使用隐式反馈（观看行为）来训练模型，其中，用户完成一个视频可以认为是一个正例。

Efficient Extreme Multiclass

为了有效地训练这样一个具有上百万分类的模型，我们采用的技术是：从后台分布（“候选抽样candidate sampling”）中抽样负类(negative classes)，接着通过按重要性加权(importance weighting)[10]来纠正这些样本。对于每个样本，为true-label和negative-label，学习目标是最小化cross-entropy loss。实际中，会抽样上千个负样本，这种方法可以比传统的softmax快100倍。另一个可选的方法是：hierarchical softmax，但这里我们不去做对比。

在提供服务的阶段（serving time），我们需要计算最可能的N个分类（视频），以便选中其中的top N，来展现给用户。对上百w级的item进行打分，会在10ms左右的延迟内完成。之前的Youtube系统靠hashing技术[24]解决，和这里描述的分类器使用相类似的技术。由于在serving time时并不需要对softmax输出层校准(calibrated)likelihoods，打分问题(scoring problem)可以缩减至在点乘空间中的最近邻搜索问题，可以使用[12]中提供的库来完成。我们发现，在最近邻搜索算法上做A/B test效果并不特别明显。

1.1 模型架构

受语言模型中的CBOW(continuous bag of words)的启发，我们为固定size视频库中的每个视频学习高维emdeddings，接着将这些emdeddings前馈(feed)输入到一个前馈神经网络。一个用户的观看历史，可以被表示成一个关于稀疏视频id的可变长序列，这些id会通过embeddings被映射到一个dense vector representation上。该网络需要固定大小的dense inputs，最后选择对emdeddings的简单平均(simply averaging)，因为它在不同策略中(sum, component-wise max，等)效果最好。最重要的，该emdeddings会和其它一些模型参数一起通过常规的梯度下降BP更新即可学到。特征被拼接(concatenate)到一个很宽的第一层上（wide first layer），后面跟着许多层的完全连接的ReLU层[6]。图3展示了整体架构，它带有额外的非视频观看特征（no-video watch features）。

图3:

1.2 多种信号

将DNN作为普通的矩阵分解(MF)的一种泛化，其中一个关键优点是，任何连续的特征和类别特征都可以很方便地加进模型中。搜索历史的处理，可以与观看历史的处理方式相类似 – 每一个查询(query)可以tokenized化成1-gram和2-gram，每一个token都可被嵌入。一旦求平均，用户的tokenized化的嵌入式query，代表了一个总结型的稠密搜索历史(summarized dense search history)。人口统计学特征（Demographic features），对于新用户的推荐很重要。用户的地域和设备信息(device)，都可以被嵌入和串联。简单的二元特征和连续特征，比如用户性别，登陆态，年龄，都可以归一化到[0,1]上的实数值，直接输入到该网络。

“样本时限”特征（”Example Age” Feature）

YouTube上，每秒都有许多视频上传上来。推荐这些最新上传的新鲜(“fresh”)内容，对于YouTube产品来说相当重要。我们一致观察到：用户喜欢新鲜内容，尽管并非相关。除了简单的推荐用户想看的新视频所带来的一次传播效果外，还存在着关键的病毒式的二次传播现象。

机器学习系统经常展示出对过往行为存在一个隐式偏差(implicit bias)，因为它们通常是基于历史样本的训练，来预测将来的行为。视频流行度分布是高度不稳定(non-stationary)的，我们的推荐系统会生成在视频库上的多项分布(multinomial distribution)，将会影响在多周训练窗口上的平均观看似然。为了纠正这一点，我们将训练样本的age，作为一个训练特征进行feed。在serving time时，该特征被置为0(或者为一个微小的负数），反映出模型在训练窗口的最末尾正在做预测。

图4展示了该方法在选择视频上的效果。

图4: 对于一个给定的视频[26]，使用样本age作为特征训练的模型能够精准表示数据的上传时间和与时间相关的流行度间的关系。如果没有该特征，模型将会预测在训练窗口上的近似平均似然(baseline)。

1.3 Label和Context选择

需要重点强调的是，推荐(recommendation)通常涉及到求解一个替代问题（surrogate problem），并将结果转换成一个特殊上下文。一个经典的示例是，如果能准确预测rating，会产生有效的电影推荐[2]。我们已经发现，这种代理学习问题（surrogate learning problem）在A/B testing上很重要，但很难在离线试验中进行衡量。

训练样本需要从所有YouTube观看行为（即使嵌入在别的网站上）上生成，而非仅仅只使用我们生成的推荐的观看行为。否则，新内容将很难浮现出来，推荐系统在探索（exploitation）上将过度偏差。如果用户正通过别的方式探索发现视频，而非使用我们的推荐，我们希望能够快速通过协同过滤传播该发现给他人。 一个关键点是，提升live metrics的目的是为每个用户生成一个固定数目的训练样本，有效地在loss function上对我们的用户做平等的加权。这可以防止一少部分高活跃度用户主宰着loss。

这在一定程度上与我们的直觉相反，必须注意：为防止模型利用网站布局，以及代理问题造成的过拟合，需要隐瞒分类器信息(withhold information from the classifier)。可以考虑将一个样本看成是用户已经发起的一个查询(query)： 比如“taylor swift”。由于我们的问题是预测下一个要看的视频。通过给定该信息，分类器将会预测要观看的最可能的视频，是那些出现在相应搜索结果页中关于”taylor swift”的视频。一点也不惊奇的是，如果再次生成用户最新的搜索页作为主页推荐，效果会很差。通过抛弃顺序信息，使用无顺序的词袋(bag of tokens)表示搜索query，该分类器不再直接认识到label的来源。

视频的自然消费模式，通常会导致非常不对称的co-watch概率。连播电视剧（Episodic series）通常被按顺序观看，用户经常发现，对于同一个流派(genre)中的艺术家们(artists)，在关注更小众的剧之前，会从最广为流行的剧开始。因此我们发现对于预测用户的下一次观看行为上有着更好的效果，而非去预测一个随机held-out观看(a randomly held-out watch)（见图5）。许多协同过滤系统隐式地选择标签和上下文，通过hold-out一个随机item，然后通过用户历史观看中的其它item来预测它(5a)。这会泄露将来的信息(future information)，并忽略任何不对称的消费模式(asymmetric consumption patterns)。相反的，我们通过选择一个随机观看(a random watch)，然后“回滚(rollback)”一个用户的历史，只输入用户在hold-out label的watch之前(5b)的动作。

图5: 选择labels和输入上下文给模型，在离线评估时很有挑战性，但对真实的效果有巨大提升。这里，实心事件•表示网络的输入特征，而空心事件◦表示排除在外。我们发现，预测一个将来的观看(5b)，在A/B test中效果更好。在(5b)中，example age通过\(t_{max}-t_N\)来表示，其中\(t_{max}\)是训练数据中观察到的最大时间。

1.4 特征和深度的试验

如图6所示，添加特征和深度，可以极大提升在holdout data上的precision。在这些试验中，1M的视频量，和1M的搜索tokens，被嵌入到256个float值上，每个都在一个最大的bag-size：50个最近的watches和50个最近的searches。softmax层输出一个在1M个视频classes、256维的多项分布(可以看成是一个独立的output video emdedding)。这些模型被训练，直接覆盖所有的YouTube用户，对应在数据上的多个epochs上。网络结构按一个公共的”tower”模式，在网络的底部是最宽的，每个后继的隐层，将单元数二等分（与图3相同）。深度为0的网络，是一个有效的线性因式分解模型，它的效果与以往的系统很相似。增加宽度（width）和深度（depth），直到增量的效果越来越小，收敛越来越难：

• Depth 0: 一个线性层，可简单地将串联层转换成与softmax相匹配的256维.
• Depth 1: 256 ReLU
• Depth 2: 512 ReLU -> 256 ReLU
• Depth 3: 1024 ReLU -> 512 ReLU -> 256 ReLU
• Depth 4: 2048 ReLU -> 1024 ReLU -> 512 ReLU -> 256 ReLU

图6 在video embeddings之外的features可以提升holdout的Mean Average Precision(MAP)以及layers的深度添加了表现力，以便模通过对这些交互建模来有效使用这些额外特征

二、Ranking

Ranking的主要作用是，针对指定的UI，使用曝光数据来特化和校正候选预测（specialized and calibrate candidate predictions）。例如，用户通常会观看一个probability值较高的视频，但不大可能去点击指定主页上缩略图的曝光。在Ranking时，我们会访问许多描述视频的特征、以及视频与用户关系的特征，因为在候选集生成阶段，只有一小部分的视频被打过分，而非上百w的视频。Ranking对于聚合不同的候选源很重要，因为每个源的得分不能直接对比。

我们使用一个与候选生成阶段相似的架构的深度神经网络，它会使用logistic regression（图7）为每个视频的曝光分配一个独立的值。视频的列表接着会通过该分值进行排序，并返回给用户。我们最终的ranking objective会基于线上的A/B testing结果进行调整，但总体上是一个关于每次曝光的期望观看时长(expected watch time)的简单函数。根据ctr的排序通常会促进视频期诈现象：用户不会播放完整(标题党：点击诱惑”clickbait”)，而观看时长(watch time)可以捕获更好的参与度（engagement）[13,25]。

图7: 深度ranking网络架构，描绘了嵌入的类别特征（单值和多值类别都存在），与归一化的连续特征的embeddings和powers共享。所有的层都是完全连接的。惯例上，成百上千的特征都可以输入到网络中。

2.1 特征表示

我们的特征，与传统的类别特征分类，以及连续型/普通特征相互隔离开来。类别型特征，在基数上变化多样–一些是二元的（比如：用户是否登陆），而其它一些则可能有上百万种可能的值（比如：用户最新的搜索query）。特征会根据它们是否是单值（“univalent”），或者多值集合(“multivalent”)，再做进一步分割。关于单值类别特征的一个示例是：被打过分的曝光视频id；而相应的多值特征可能是一批(a bag of)关于该用户已经观看过的N个视频id。我们也会根据特征是否描述了item的属性(“impression”)或者user/context的属性（”query”），将特征进行分类。Query特征在每次请求时被计算一次，而impression特征则会为每个评过分的item计算。

特征工程(Feature Engineering)

我们通常在我们的排序模型中使用成百上千的特征，它们被分成类别型和连续型特征。尽管深度学习可以缓和手工建立特征工程的负担，但我们的原始数据天然就不能直接输入到前馈神经网络中。我们仍需要花费可观的工程资源来将用户和视频数据转换成有用的特征。最主要的挑战主要在：表示用户动作的临时顺序，以及如何将这些动作与被打分的视频曝光（impression）相关联。

我们观察到，最重要的信号是，那些描述一个用户与item本身、以及其它相似item的之前交互行为，这与广告排序(randing ads)上的经验相类似。例如，考虑用户的过往历史，以及上传被打分的频道-该用户从该频道观看了多少视频？该用户在该主题上观看一个视频的最近时间是何时？这些连续特征相当强大，它们描述了用户在相关item上的过往动作，因为它们在不同的item上泛化得很好。我们也发现，很重要，从候选生成阶段（Candidate generation）到排序阶段（Ranking）以特征的形式进行信息传递，比如：哪个源被指定给该视频候选？会分配什么分值？

描述过往视频曝光的频率的特征，对于在推荐中引入“搅动（churn）”很重要（连续的请求不会返回相同的列表）。如果一个用户最近被推荐了某个视频，但没有观看它，接着模型将自然地在下一页加载时降级该曝光（impression）。Serving即时曝光和观看历史，是一项工程壮举，超出了本paper的范围，对于产生响应式推荐至关重要。

类别特征embedding （embedding categorical features)

与候选生成阶段相类似，我们使用embeddings，将稀疏的类别型特征映射到dense表征上，更适合于神经网络。每个唯一的ID空间(视频库:”vocabulary”) 都具有一个单独学到的emdedding，它维度的递增与唯一值的数目的log成比例。这些库是简单的look-up table，在训练前由整个数据一次构建。非常大的基数ID空间（视频ID或者搜索query terms）被截断，通过只包含topN，在基于点击曝光的频率排序之后。Out-of-vocabulary的值，可以简单地映射到零嵌入上（zero embdding）。正如在候选生成阶段，多值类别特征的embeddings是被平均化的，在被输入到网络之前。

重要的是，相同ID空间的类别型特征，也共享着底层的embeddbings。例如，存着单个关于视频ID的全局embedding，供许多不同的特征使用（曝光的视频ID，该用户观看的最近视频ID，作为推荐系统”种子”的视频ID等等）。尽管共享emdedding，每个特征独自输入到网络中，因此，上面的层可以学到每个特征的特定表征(representation)。共享嵌入（sharing emdeddings）对于提升泛化、加速训练、及减小内存等相当重要。绝大多数模型参数都是在这些高基数(high-cardinality)的embedding空间中 - 例如，100w的ID，嵌入到32维的空间上，与2048个单元的宽完全连接层多7倍多的参数。

归一化连续特征(Normalizing Continuous Features)

众所周知，神经网络对于输入的归一化和分布是很敏感的[9]，其它方法（比如：决策树ensembles）对于独立特征的缩放(scaling)是稳定的。我们发现，对连续特征进行合理的归一化，对于收敛来说很重要。连续特征x，具有分布f，被转换成x^，通过对值进行归一化，比如：特征平均地分布在[0,1)上使用累积分布，$ \hat{x}=\int_{-\infty}^{x}df $。该积分与特征值的分位数的线性插值相近似，在训练开始这，在所有数据上的单个pass中计算。

另外，原始的归一化特征$ \hat{x} $，我们也输入$ \hat{x}^2 $和$ \sqrt{\hat{x}} $，给网络更多有表现力的阶，通过允许它，很容易形成特征的super-linear和sub-linear function。我们发现：输入连续特征的阶，可以提升离线的accuracy。

2.2 对期望的观看时长建模

我们的目标是，给定训练样本：包含正例（曝光的视频被点击）和负例（曝光的视频没被点击），来预测期望的观看时间。正例可以解释成：该用户花费观看该视频的时间量。为了预测期望的观看时间，我们出于该目的，开发并使用加权logistic regression技术。

该模型的训练通过logistic regression和cross-entropy loss进行（图7）。然而，正例（被点的）的曝光，会由视频所观察到的观看时间进行加权。所有负例（未点击）的曝光，都使用单位加权。这种方式下，通过logistic regression学到的差异（odds）是：$ \frac{\sum{T_i}}{N-k} $，其中：

• N是训练样本的数目
• k是正例曝光的数目
• Ti是第i个曝光的观看时间

假设，正例曝光很小（真实情况就这样），学到的差异(odds)近似为：\(E[T](1+P)\)

• 其中P是点击概率
• E[T]是该曝光所期望的观看时间

由于P很小，该乘积近似为E[T]。为便于推理，我们使用指数函数\(e^x\)作为最终的激活函数，来产生这些odds，来近似估计期望的观看时长。

2.3 隐层的试验

表1展示了，我们在下一天的holdout数据上，使用不同的隐层配置所获得的结果。Value展示了每个配置（”加权，每用户的loss”），包括正例和负例，曝光展示给单个页内的某个用户。我们首先使用我们的模型对两种曝光进行打分。如果负例的曝光接受到更高的分值，那么我们会认为，正例的观看时长为：误预测的观看时长（mispredicted watch time）。加权的每用户loss，就是误预测的观看时间的总量，作为一个分数，在heldout曝光pair上的一个总观看时长。

这些结果展示了隐层的width的增加会提升效果，同样depth的增加也会。然而，服务器的CPU时间需要进行权衡下。该配置是一个1024-wide的ReLU，后面跟着一个512-wide的ReLU，再接一个256-wide的ReLU，会给我们最佳的结果，而允许我们在CPU预算范围内。

对于1024->512->256的模型，我们尝试只输入归一化连续特征，而不输入它们的powers，会增加0.2%的loss。相同的隐层配置，我们也训练了一个模型，其中正例和负例的加权相同。不令人惊讶，观看时间加权loss会增加4.1%之多。

表1:在基于观看时长加权的pairwise loss上，更深和更宽的隐ReLU层的效果

参考

－ 0.Deep Neural Networks for YouTube Recommendations

我们来看下prod2vec作者Mihajlo Grbovic†等人提出的HDV《Hierarchical Neural Language Models for Joint Representation of Streaming Documents and their Content》中提出的新方法：

介绍

考虑为数据流中的文档学习分布式表示的问题。文档(documents)被表示成低维向量，与word tokens的分布式向量，使用两个embedded神经语言模型的层次结构框架，通过联合学习得到。特别的，我们会利用在streams中的文档内容，并使用一个语言模型来建模文档序列，另一个模型则建模在它们中的词序列。该模型（the models复数）会为word tokens和documents学习两者的连续向量表示，以便语义相近的documents和words在同一向量空间中更接近。我们讨论了该模型的扩展，通过进一步添加user layers到该结构中，就可以被应用于个性化推荐、以及社交关系挖掘中，这样可以学到用户的向量来表示私人偏好。我们在公共电影评分数据集MovieLens和Yahoo News三个月数据集上进行了验证。结果表明，提出的模型可以学到文档和word tokens的有效表示，效果要好于当前state-of-art的方法一大截。

3.层次化语言模型

本节中，提出的算法会对streaming documents和在它内的words进行联合建模，其中学到的documents和words向量表示会在一个共享的、低维的embedding空间内。该方法受[14]的启发。然而，与[13]的不同之处是，我们会利用steaming documents中的时序邻居（temporal neighborhood）。特别的，我们会建模一个特定文档的概率，会考虑上时序上更接近（temporally-close）的文档，另外还会考虑文档内容。

3.1 模型结构

我们假设，训练文档会以序列形式给定。例如，如果该文档是新闻文章，那么document序列可以是：用户根据阅读时间按前后顺序排列的新闻文章序列。更特别的，我们会假设，设置S个document序列的集合\(S\)，每个序列\(s \in S\)包含了\(N_s\)个文档，\(s = (d_1, d_2, ..., d_{N_s})\)。接着，在一个stream \(d_m\)中的每个文档是一个由\(T_m\)个词组成的序列，\(d_m = (w_{m_1}, w_{m_2}, ..., w_{m, T_m})\)。我们的目标是，在同一个向量空间中同时学习streaming documents和language words的低维表示，并将每个document和word表示成D维的连续特征向量。如果我们假设，在训练语料中存在M个唯一的文档(doc)，以及在词汇表中存在W个唯一的词(words)，那么在训练期间，我们的目标是学习\((M+W) \cdot D\)个模型参数。

图1: hierarchical模型结构，有两个embedded神经语言模型（橙色：左：文档向量；绿色／右：词向量）

一个文档序列的上下文和自然语言上下文，会使用提出的HDV方法进行建模，其中documents向量不光只看成是预测周围documents的单元，同时也看成是在它之间包含的word序列的全局上下文。该结构包含了两个embedded layers，如图1所示。upper layer可以学到一个文档序列的时序上下文，基于假设：在文档流（document stream）中时序更接近的文档在统计学上相互依赖性更强。我们注意到，时序不需要指文档的创建时间，而是用户阅读文档的时间，在我们的实验中使用该定义。bottom layer会建模word序列的上下文信息。最后，我们采用paragraph vectors的思想，将这两个layer进行连接，并将每个文档token看成是在该文档内所有词的一个全局上下文。

更正式的，给定文档序列集合S，hierarchical模型的目标函数是：最大化streaming data的log似然：

\(L = \sum_{s \in S} (\alpha \sum_{d_m \in s} \sum_{w_{mt} \in d_m} log P(w_{mt} | w_{m,t-c}: w_{m,t+c}, d) + \\ \sum _{d_m \in s} (\alpha log P(d_m | w_{m1}: w_{mT}) + \sum_{-b \le i \le b, i \neq 0} log P(d_{m+i} | d_m)))\) …(8)

其中，\(\alpha\)是权重，它会在文档序列的log似然、以及词序列的log似然的最小化之间做一个权衡（在实验中会设置\(\alpha=1\)），b是文档序列的训练上下文长度，c是词序列的训练上下文长度。在该特定架构中，我们对于下面的setence layer使用cbow模型，对于上层的document layer使用skip-gram模型。然而，我们注意到，两个模型的任一个可以被用于该hierarchy的任意层上，具体选择取决于目前手头的问题形态。

给定如图1的架构，基于当前文档\(P(d_{m+i} \mid d_m)\)，观察到某一周围文档的概率，可以使用下面的softmax函数定义：

\(P(d_{m+i} | d_{m}) = \frac{exp(v_{d_m}^T v_{d_{m+i}}')} {\sum_{d=1}^{M} exp(v_{d_m}^T v_d')}\) …(9)

其中\(v_d\)和\(v_d'\)是文档d的输入和输出向量表示。更进一步，观察到一个词的概率不仅依赖于周围的词，也依赖于该词所属的文档。更准确的，概率\(P(w_{mt} \mid w_{m,t-c} : w_{m,t+c},d_m)\)被定义成：

\(P(w_{mt} | w_{m,t-c}: w_{m,t+c}, d_m) = \frac{exp(\bar{v}^T v_{w_{mt}}')} {\sum_{w=1}^{W} exp(\bar{v}^T v_w')}\) …(10)

其中，\(v_{w_{mt}}'\)是\(w_{mt}\)的输出向量表示，其中\(\bar{v}\)是该上下文（包含指定的文档\(d_m\)）的平均向量表示，定义如下：

\(\bar{v} = \frac{1}{2c+1} (v_{d_m} + \sum_{-c \leq j \leq c, j \neq 0} v_{w_{m,t+j}})\) …(11)

最后，我们通过复用等式(10)和(11)来替换合适的变量，定义了以一个相同方式在\(P(d_m \mid w_{m1}: w_{m,{T_m}})\)。

3.2 模型变种

前面提到了一个典型结构，其中我们指定了在hirerachy上每一层的语言模型。然而，在真实应用中，我们会以一种更简单的方式来为不同目的区分语言模型。例如，一个新闻网站可能会对预测即时性感兴趣，即：对于个性化新闻信息流，一个用户在点击了一些其它新闻故事后接下去会阅读什么。接着，它可以使用直接的前馈模型来估计\(P(d_m \mid d_{m-b}: d_{m-1})\)，即：给定了它的b个之前文档，在序列中第\(m^{th}\)个文档的概率。或者，相同的，如果我们想建模哪个文档会在读取前面序列后被读取，我们可以使用前馈模型：它可以估计\(P(d_m \mid d_{m+1}: d_{m+b})\)，它是给定前b个文档的第m个文档的概率。

另外，很方便扩展该描述，但也很容易具有超过两个layers。假设我们具有一个streaming documents的数据集，它面向一个不同的用户集合（例如：对每个文档我们希望知道哪个用户生成或阅读了该文档）。接着，我们可以构建更复杂的模型, 通过在document layer的顶部添加user layer来同时学习用户的分布式表示。在该setup中，一个用户向量可以看成是指定用户的steaming documents的一个全局上下文, 一个文档向量则看成是指定文档的words的一个全局上下文。更特殊的，我们可以预测一个文档，它基于周围文档和它的内容来预测一个文档，同时也只对某一指定用户。该变种模型\(P(d_m \mid d_{m-b}:d_{m-1},u)\)，其中u是对于某一用户的一个指示变量。对于提升个性化服务来说，学习用户的向量表示是一个开放问题，其中个性化会降维到：在联合embedding空间中的最简单的最近邻搜索。

3.3 模型最优化

该模型使用SGA（随机梯度上升法），很适合大规模问题。然而，在(8)中的梯度的计算 \(\delta log P(w_{mt} \mid w_{m,t-c} : w_{m,t+c},d_m)\)与词汇size W成比例，梯度\(\Delta log P(d_{m+i} \mid d_m)\)和\(\Delta log P(d_m \mid w_{m1}: w_{m,T_m})\)与训练的文档数M成比例。这在实例上很昂贵，因为W和M两者都可以很容易达到上百万的规模。

我们使用的一种有效替换方法是，hirarchical softmax，它可以将时间复杂度减小到\(O(R log(W) + bM log(M))\)，其中R是在文档序列中的总词汇数。为了计算等式(9)和等式(10)中的求和，我们并不用在每次梯度step期间评估每个不同词或文档，hirarchical softmax会使用两个二叉树，一棵树将不同文档作为叶子，另一棵树将不同的词作为叶子。对于每个叶子节点，从该根节点出发的路径(path)会有一个唯一分配，它使用二进制数字进行编码。为了构建一个树结构，通常用使用Huffman编码，其中，在数据集中更常见的文档（或词）会具有更短的编码。更准确的，hierarchical softmax表示在该序列中当前文档（或词）被观察到的概率，它作不二叉树的概率积，通过文档的Huffman编码如下：

\(P(d_{m+i} \mid d_m) = \prod_l P(h_l \mid q_l, d_m)\) …(12)

其中\(h_l\)是编码中第l位的码，对应于\(q_l\)，它是指定树路径\(d_{m+i}\)中的第l个节点。每个二叉树的概率定义如下：

\(P(h_l = 1 \mid q_l, d_m) = \sigma(v_{d_m}^T V_{q_l})\) …(13)

其中\(\sigma(x)\)是sigmoid函数，\(v_{q_l}\)是节点\(q_l\)的向量表示。它可以通过\(\sum_{d=1}^M P(d_{m+i}=d \mid d_m) = 1\)进行验证，因而概率分布的属性会被保留。我们可以以同样的方式计算\(P(d_m \mid w_{m1} : w_{m, T_m})\)。更进一步，我们相似地表示\(P(w_{mt} \mid w_{m,t-c}: w_{m,t+c}, d_m)\)，但独立的Huffman树的构建会与词有关。

参考

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

我们来看下Bryan Perozzi的<DeepWalk: Online Learning of Social Representations>。

1.介绍

网络表示的稀疏性，即是它的强项，也是它的弱项。稀疏性允许设计一些很有效的分立算法，但使它很难泛化到统计学习（statistical learning）中。在网络机器学习应用中（比如：网络分类、内容推荐、异常检测、缺失环节预测missing link prediction等），必须能处理这种稀疏性。

本文引入了deep learning（非监督特征学习）技术来进行网络分析，DL已经在NLP上取得了成功。我们开发了一个算法（DeepWalk），它会通过建模一个关于短随机游走（short random walk）的流（stream），会学到一个关于图顶点(graph vertices)的社群表示（social representations）。社群表示是顶点的隐特征，它可以捕获相邻顶点间的相似度和社群关系。这些隐表示（latent representation）可以把社交关系使用相对少量的维度编码在连续特征空间中。DeepWalk可以看成是会将自然语言模型泛化来处理一个特殊的语言：它由一个随机生成的walk集合组成。这些自然语言模型被用于捕获人类语言中的语法和语义结构、以及逻辑类比。

图1

DeepWalk会将一个图作为输入，并生成一个隐表示作为它的输出。将我们的方法应用于Karate network上，结果如图1所示。图1a通过力导向（force-directed）的布局进行表示，图1b展示了我们使用2个隐维度的方法。除了显著的相似性外，我们注意到1b中线性可分的部分，对应于通过输入图1a的模块最大化（modularity maximization）的聚类（clusters）: 通过顶点颜色区分。

为了演示DeepWalk在真实世界场景中的潜力，我们在多标签网络分类问题上评估了它的效果。在关系分类（relational classification）问题上，特征向量间的连结（links）与传统的独立同分布（i.i.d）假设冲突。解决该问题的技术通常使用近似推断技术（approximate inference ）通过增加依赖信息来提升分类结果。我们通过增加图表示(representations of the graph)的标签独立性（label-independent）来解决。我们的表示（representation）质量不会因带label顶点（labeled vertices）的选择而受影响，因而它们可以在任务间共享。

DeepWalk比其它用于创建社交维度（social dimension）隐表示方法要好，尤其是当带label的节点（labeled nodes）很稀少时。我们的表示法的性能可能与最简单的分类器（LR）相当。我们的表示是可泛化的，可以结合任何分类方法（包含迭代型推断法）。DeepWalk可以完成上述所有，它是一个在线算法，可并行化。

本paper贡献：

• 引入深度学习作为一个工具来分析图，来构建健壮的表示，很适合于统计建模。DeepWalk会学到在短随机游走(short random walks)内表示的结构化规律。
• 我们对多个社交网络上使用我们的表示法，并在多标签分类上进行评估。我们发现可以极大提升存在标签稀疏性情况的分类效果，在Micro F1上可以提升5%-10%。在一些case中，即使只给了更少的60%的数据，DeepWalk的表示也可以胜出其它对手。
• 我们展示了我们的算法的可扩展性，使用一个并行实现去构建web-scale图（比如：Youtube）的表示。另外，我们描述了小的变种，来构建一个流版本（streaming version）。

本paper的其余部分如下安排。在第2-3节，描述了在数据网络中的分类问题，以及如何与我们的工作相结合。在第4节，我们描述了DeepWalk算法。第5､6节描述实验以及实验结果。等

2.问题定义

问题：对一个社交网络的成员进行分类，分成一或多个类(categories)。

更正式地表示：G=(V, E)，其中V是网络的成员，E是它们的边，\(E \subseteq (V \times V)\)。给定一个部分标记的社交网络\(G_L = (V,E,X,Y)\)，属性\(X \in R^{\mid V\mid \times S}\)， 其中S是每个属性向量的特征空间size，\(Y \in R^{\mid V \mid \times \mid \mathcal{Y} \mid}\)，其中\(\mathcal{Y}\)是labels的集合。

在传统的机器学习分类设定中，我们的目标是学习一个假设函数H，它会将元素X映射到标签集合\(\mathcal{Y}\)上。在我们的case中，我们可以利用关于样本依赖的显著信息，嵌入到G的结构中来完成更好的效果。

在学术上，这被称为是关系分类（relational classification)或者称为协作分类(collective classification）。关系分类的传统方法将该问题看成是在一个无向马尔可夫网络上做推断，接着使用迭代近似推断算法（比如：迭代型分类算法，Gibbs Sampling，或者 标记松弛法label relaxation）来计算给定网络结构下的标签后验分布。

我们提出了一个不同的方法来捕获网络拓朴信息。这种方法不再使用将标签空间进行混合作为特征空间的一部分，而是提出了一种无监督的方法，可以学到这样的特征：它能捕获与标签分布相独立的图结构。

结构化表示与标记任务间的分隔，可以避免重复错误，这常在迭代型方法中出现。另外，相同的表示可以被用于网络的多分类问题。

我们的目标是，学习\(X_E \in R^{\mid V \mid \times d}\)，其中，d是隐维度（latent dimensions）是最小数目。这些低维度表示是distributed式表示的; 这意味着每个社交现象（social phenomena）可以通过维度的某个子集进行表示，每个维度只会对通该空间表示的社交概率的某个子集做出贡献。

使用这些结构化特征，我们可以增大属性空间来帮助分类决策。这些特征是通用的，可以被用于任何分类算法（包括迭代型方法）。然而，我们相信，这些特征的最大作用是，它们很容易与简单的机器学习算法集成。它们可以很适合地在现实网络中扩展，在第6节会介绍。

3.学习社交表示

我们使用以下的特征来探索社交表示学习（learning social representations）：

• 适应性（Adaptability）：真实社交网络是不断演进的；新的社交关系不需要再次重复所有学习过程。
• 社群意识（Community aware）：隐维度间的距离可以作为评估网络成员的社交相似性的一个metric。这允许泛化到同质的网络中。
• 低维（Low dimensional）：当标记数据很少时，低维模型泛化更好，加速收敛和推断。
• 连续（Continuous）：我们需要隐表示来建模在连续空间中的部分社群成员关系（community membership）。除了提供一个关于社群关系的细微视图外，连续表示法具有在社群间的平滑决策边界，这可以允许更健壮的分类。

我们的方法满足这些需求，从一个短随机游走流中，使用语言建模上的优化技术来为顶点学到表示。这里，我们会复习下随机游走和语言建模，并描述两者如何结合来满足我们的需要。

3.1 随机游走

一个根顶点\(v_i\)的随机游走的定义为：\(W_{v_i}\)。它是一个随机过程，具有随机变量：\(W_{v_i}^1, W_{v_i}^2, ..., W_{v_i}^k\)，\(W_{v_i}^{k+1}\)是从顶点\(v_k\)的邻节点上随机选中的顶点。随机游走已经被用于在内容推荐和社群发现领域的多个问题上作为一个相似度衡量方法。他们也是输出敏感算法（output sensitive algorithms）大类的基础，使用它们来及时计算局部社群结构信息，与输入图的size成次线性关系（sublinear）。

这种局部结构的连接特性，启发我们来使用一个短随机游走作为我们的基础工具来从一个网络中抽取信息。除了捕获社群信息外，在我们的算法中使用随机游走作为基础，能给我们带来其它两个特性。

• 1.局部探索（local exploration）很容易并行化。多个随机游走者（random walkers）以不同线程、进程、机器可以并行探索同一个graph下的不同部分。
• 2.依靠从短随机游走上获取信息，可以使它更能适应在图结构上的小变动，无需进行全局重新计算。我们可以迭代式地更新学到的模型，从变动区域上使用新的随机游走，它对整个graph是在时间上是次线性的。

3.2 连接：二八法则（power law）

已经选择在线随机游走作为我们的基础来捕获图结构，我们现在需要一个更适合的方法来捕获这种信息。如果一个连接图的度分布（degree distribution）遵循一个power law（scale-free），我们会观察到，出现在短随机游走上的哪个顶点的频次也是遵循power-law分布的。

图2

在自然语言中，词频会遵循一个相似的分布，其中，语言建模领域的技术可以对该分布行为作出解释。为了强调该相似性，如图2所示，我们展示了两个不同的power-law分布。第1个图来自在一个scale-free的graph上进行一系列短随机游走，第2个图来自关于英文wikipedia的10w篇文章的文本。

我们的工作的一个核心贡献是，用于建模自然语言的技术（其中，符号频次遵循power-low分布）可以被用于建模在网络中的社群结构。该节剩余部分将讨论语言建模，并将它迁移到我们的case中来学习顶点表示。

3.3 语言建模

语言建模的目标是，在语料中出现的一个指定词序列的似然。更正式地，给定一个词序列：

\[W_1^n = (w_0, w_1, ..., w_n)\]

其中，\(w_i \in V\)（V是词汇表），我们想最大化在所有训练语料上的\(Pr(w_n \mid w_0, w_1, ..., w_{n-1})\)。

在表征学习上的最近工作，主要使用概率神经网络来构建词的通用表示，可以扩展到语言建模范围之外。

在本paper中，我们使用一个语言建模的泛化版本、结合短随机游走的一个流(stream)来探索图。这些游走可以被认为是在一个特殊语言中的短句、短段落。直接类比是，给定在随机游走中所有访问过的前节点，估计观察顶点\(v_i\)的似然。

\[Pr(v_i | (v_1, v_2, ..., v_{i-1}))\]

我们的目标是学习一个隐表示，它不仅仅是节点共现的一个概率分布，而且我们引入了一个映射函数 \(\Pi: v \in V \rightarrow R^{\mid V \mid} \times d}\)。该映射函数\(\Phi\)表示与在图中每个顶点v相关的隐社交表示。（实际上，我们通过一个\(\mid V \mid \times d\)的自由参数矩阵来表示\(\Phi\)，它可以在之后作为我们的\(X_E\)服务）。接着该问题是，估计以下似然：

\(Pr(v_i | (\Phi(v_1), \Phi(v_2), ..., \Phi(v_{i-1})))\) …(1)

然而，随机游走长度的增长，计算该目标函数会变得不可行。

在自然语言中的最近实验是，开始转变预测问题。首先，它不同使用上下文来预测一个缺失的词（word），而是使用一个词来预测它的上下文。第二，上下文由给定词的右侧和左侧组成。最后，它在该问题上会移除顺序限制。作为替代，该模型需要最大化出现在该上下文中的任何词的概率，无需知道与给定词间的偏移。

用顶点表示建模的优化问题，如下：

\(minimize_{\Phi} - log Pr({v_{i-w}, ..., v_{i-1}, v_{i+1}, ..., v_{i+w}} | \Phi(v_i))\) …(2)

我们发现这些条件放宽，特别适合于社交表征学习。首先，顺序无关性假设可以更好捕获由随机游走提供的“邻近度(nearness)”。另外，该relaxation通过一次只为一个顶点构建小模型对于加速训练时间相当有用。

对等式(2)的优化问题进行求解来构建表示，可以捕获在顶点间的局部图结构的共享相似度。具有相同邻节点的顶点可以获取相似的表征（encoding cocitation similarity），允许在机器学习任务上进行泛化。

通过组合截短的随机游走和自然语言建模，我们会对该方法公式化，它可以满足所有我们期待的特性。该方法可以生成社交网络的表征，具有低维、连续空间的特性。它的表示会对社群的隐形式进行编码，因为该方法会输出有用的中间表征，可以用来更改网络拓朴。

4.方法

在本节中，我们讨论算法的主要构成。

4.1 总览

在任何语言建模算法中，只需要一个语料和词汇表V。DeepWalk会考虑短截断的随机游走的一个集合作为它的语料，图顶点作为它的词汇表（\(v=V\)）。其中，它有利于知道在训练之前的随机游走上顶点的词频表V和频次分布。

4.2 算法：DeepWalk

该算法包含了两个主要部分：

• 1.随机游走生成器
• 2.一个更新过程

随机游走生成器会使用一个图G，并且均匀地抽样出一个随机顶点\(v_i\)作为随机游走\(W_{v_i}\)的根节点（root）。一个游走会均匀从最后访问的顶点的邻节点进行抽样，直到到达最大长度(t)。在我们的实验中，随机游走的长度设置是固定的，但是对于随机游走来说没有限制一定要用相同长度。这些游走会重启(restart)（例如：一个传送点（teleport）的概率会返回到它的root），但我们的初步结构不会展示使用重启(restarts)的任何优点。实际上，我们的实现指定了在每个顶点上进行随机游走的数目(\(\gamma\))和长度(t)。

算法一

在算法1中的3-9展示了我们算法的核心。外层的循环指定了次数，\(\gamma\)，即我们在每个顶点上启动随机游走的数目。我们认为每个迭代会生成一个对数据的”通路（pass）”，并在该pass期间为每个节点抽样一个walk。在每个pass的开头，我们生成了一个随机顺序来遍历这些顶点。这不是必需的，但可以加速随机梯度下降（SGD）的收敛。

在内层循环中，我们会迭代图的所有顶点。对于每个顶点\(v_i\)，我们会生成一个随机游走 \(\mid W_{v_i} \mid = t\)，接着使用它来更新我们的表征represntations（第7行）。我们使用SkipGram算法来更新这些表征，以适应在等式2中的目标函数。

4.2.1 SkipGram

SkipGram是一个语言模型，在一个句子中，它会最大化在同一窗口w中词之间的共现率。

图3: 补充

算法2会迭代在窗口w内出现的随机游走中的所有可能排列（collocations）（第1-2行）。for-each操作中，我们会将每个顶点\(v_j\)映射到它的当前表征向量\(\Phi(v_j) \in R^d\)中（见图3b）。给定\(v_j\)的表示，我们可以最大化在该walk中的邻节点的概率（第3行）。我们可以有多种分类器选择来学到在walk中这样的后验分布。例如，使用LR建模前面的问题，可以生成一个海量的标签（上百万或数十亿），它等于词汇表数\(\mid V \mid\)。这样的模型需要大量计算资源，可能会占用整个计算集群。为了加速训练时间，可以使用Hierarchical Softmax来近似概率分布。

算法2

4.2.2 Hierarchical Softmax

给定\(u_k \in V\)，计算第3行中\(Pr(v_k \mid \Phi(v_j))\)是不可行的。计算分区函数（正归化因子）很昂贵。如果我们将顶点设计成一棵二叉树的叶子节点，预测问题就转化成了最大化在树中一条指定路径上的概率（见图3c）。如果到顶点\(u_k\)的路径通过一个树节点序列\((b_0, b_1, ..., b_{[log \mid V \mid]})\)表示，其中：\(b_0 =root, b_{[log\mid V \mid]}=u_k\)，那么：

\[Pr(u_k | \Phi(v_j)) = \prod_{i=1}^{log|V|} Pr(b_l | \Phi(v_j))\]

现在，\(Pr(b_l \mid \Phi(v_j))\)可以通过一个二分类器进行建模，该值被分配给节点\(b_l\)的父节点。这可以减少计算\(Pr(u_k \mid \Phi(v_j))\)的计算复杂度：从\(O(\mid V \mid)\)到\(O(log\mid V \mid)\)。

我们可以进一步加速训练过程，通过分配更短的路径给在随机游走中的频繁顶点。Huffman编码常用于减小在树中频繁顶点的访问次数。

4.2.3 最优化

模型参数集是\(\{ \Phi, T\}\)，其中每个的size都是\(O(d\mid V \mid)\)。随机梯度下降(SGD)被用于最优化这些参数（算法2第4行）。导数的估计使用BP算法。SGD的learning rate \(\alpha\)在训练开始处初始化设置为2.5%，接着随着见过的顶点数进行线性递减。

4.3 并行化(Parallelizability)

如图2所示，在社交网络上的随机游走中，顶点的频率分布与语言中的字分布遵循power law。这会产生一个关于不频繁顶点的长尾，因此，对\(\Phi\)有影响的更新在本质上很稀疏。这允许我们使用并行版本的ASGD(asynchronous version of stochastic gradient descent)，在多个worker上。假定：我们的更新是稀疏的，我们不需要一个锁来访问模型的共享参数，那么ASGD将会达到一个收敛的最优rate。其中我们在单机上使用多线程进行实验，它可以演示这种技术是高度可扩展的，可以用于大规模机器学习上。图4展示了并行的DeepWalk。它展示了处理BLOGCATELOG和Flickr网络的加速与我们增加workers数是一致的（图4a）。也展示了相对于顺序版本的DeepWalk，预测效果并没有损失（图4b）。

图4

4.4 算法变种

我们提出的方法还有一些变种。可能是你感兴趣的。

4.4.1 Streaming

其中一个有意思的变种是streaming方法，它没需知道整个graph就可以实现。在该变种中，从一个图出发的小游走，直接传到表示学习编码上，模型是直接更新的。该学习过程的一些修改是必须的。首先，使用一个衰减的learning rate不再可能。相反地，我们会初始化learning rate \(\alpha\)，我们不必构建一个参数树。如果V的基数是已经的（可以限定），我们可以构建Hierachical Softmax tree来最大化值。当顶点被首先看到时，它们会被被分配给余下叶子之一。如果我们能估计顶点频率的一个先验，我们也可以仍使用Huffman编码来减小频繁节点的访问次数。

4.4.2 非随机游走

一些图是作为一系列元素行为的一个副产品被创建的。（例如：用户在一个网站上的导航）。当一个图通过这样的非随机游走方式创起家时，我们可以使用该过程来直接feed该建模阶段。以这种方式抽样的图不仅能捕获与网络结构相关的信息，也能捕获在该路径进行反向的频率。

我们认为，该变种也包括语言建模问题。句子可以看成是通过一个合理设计的语言网络上的一些特定游走，像SkipGram的语言模型可以被设计用来捕获这种行为。

该方法可以结合streaming变种来在连续演化网络上训练特征，无需显式构建整个网络。使用该技术维护表示，可以允许web-scale分类，无需处理一个web-scale规模的graph。

5.实验设计

略.

YouTube是一个社交网络，用户共享流行的视频。这里的labels表示viewers的群组，它们喜欢相同的视频类目（比如：动作 和 摔跤）

6.实验

6.1.3 YouTube

详见paper.

参考

DeepWalk: Online Learning of Social Representations

1.介绍

对于词（words）的分布式组成语义的算法开发是一个长期存在的开放性难题。最近几年的算法有：将word vectors映射到sentence vectors（包括recursive networks, recurrent networks, convolutional networks，以及recursive-convolutional方法）。所有的这些方法会生成句子表示，传给一个监督式任务，依赖一个class label来对组成权重（composition weights）做BP算法。因而，这些方法能学到高质量句子表示，但只能对自己的特定任务进行调整。paragraph vector是另一种方法，它通过引入一个分布式句子索引作为模型的一部分，以非监督式学习进行句子表示。

本文中，我们考虑了另一种loss function，可以用于任何组成操作（composition operator）上。考虑以下的问题：是否存在一个任务，它对应的loss允许我们学习高度泛化的句子表示？受使用word vector学习的启发，我们提出了一个目标函数，它从句子级别上抽象了skip-gram模型。也就是说，它不再使用单个word来预测它的上下文，我们会encode一个句子。因而，任何组成操作（composition operator）都适用于一个句子编码器(sentence encoder)，只是目标函数被修改了而已。图1展示了该模型，我们会调用我们的skip-thoughts模型和向量。

图1: skip-thoughts模型。给定一个tuple（\(s_{i-1}, s_i, s_{i+1}\)），\(s_i\)表示book中的第i个句子，\(s_i\)被编码并尝试重构前一个句子\(s_{i+1}\)和下一个句子\(s_{i+1}\)。在本例中，输入的句子三元组：I got back home. I could see the cat on the steps. This was strange. 未绑定箭头被连接到encoder output上。颜色表示哪个component共享参数。(与skip-gram有点像)

表1: BookCorpus dataset的统计信息

我们的模型依赖于一个关于连续文本的训练语料。我们选择使用一个小说集合BookCorpus dataset来训练我们的模型。这些书由未出版的作者编写。该dataset具有6种不同的种类：Romance, Fantasy, Science fiction , Teen等。表1高亮了该语料的统计。伴随着故事，书包含着对话，感情（emotion）和广泛的字符交叉。另外，训练集的量很大，不会偏向于任何特定领域或应用。表2展示了该语料中句子的最近邻。该结果展示了skip-thought vectors精确地捕获了编码后的句子的语义和结构。

表2: 在每个样本中，第一个句子是一个query，而第二个句子是它的最近邻。通过从语料中随机抽取5w个句子中，通过计算cosine相似度进行最近邻分数排序。

我们以新的setting评估了我们的向量：在学到skip-thoughts后，冻结模型，使用encoder作为一个泛化的特征抽取器（generic feature extractor）以用于特定任务。在我们的实验中，我们考虑了8个任务：句义相关性，段落检测，图像句子排序以及其它5个标准的分类benchmarks。在这些实验中，我们抽取了skip-thought向量，并训练了线性模型来评估它的表示（representations），没有任何额外的参数fine-tuning。结果说明，skip-thoughts提出的泛化表示对所有任务都很robust。

一个难点是，这样的实验会构建一个足够大的词汇表来编码句子。例如，一个从wikipedia文章中的句子可能包含了与我们的词汇表高度不一样的名词。为了解决这个问题，我们学到了一个mapping：从一个模型传递给另一个模型。通过使用cbow模型预训练好的word2vec表示，我们学到了这样的一个线性映射：将在word2vec空间中的一个词映射到encoder词汇表空间中的一个词上。学到的该mapping会使用所有单词，它们共享相同的词汇表。在训练后，出现在word2vec中的任何word，可以在encoder word embedding空间中获得一个vector。

2.方法

2.1 引入skip-ghought vectors

我们使用encoder-decoder模型框架来对待skip-thoughts。也就是说，一个encoder会将words映射到一个句子向量（sentence vector）上，一个decoder会用于生成周围的句子。在该setting中，一个encoder被用于将一个英文句子映射到一个向量。decoder接着根据该向量来生成一个关于源英文句子（source sentence）的翻译（translation）。已经探索了许多encoder-decoder pair选择，包括：ConvNet-RNN，RNN-RNN，LSTM-LSTM。源句子表示（source sentence representation）也可以通过使用一个attention机制来动态变化，用于说明任何时候只有相关的才用于翻译（translation）。在我们的模型中，我们使用一个带GRU activations的RNN encoder，以及一个conditional GRU的RNN decoder。该模型组合近似等同于神经机器翻译中的RNN encoder-decoder【11】。GRU展示了在序列建模任务中效果比LSTM要好，并且更简单。GRU units只有两个gates，不需要使用一个cell。而我们的模型则使用RNN，只要能在它之上进行BP算法，任何encoder和decoder可以被使用。

假设我们给定了一个句子的tuple：\((s_{i-1}, s_i, s_{i+1})\)。假设\(w_i^t\)表示了句子中的第t个word，\(x_i^t\)表示它的word embedding。我们将模型描述成三部分：encoder，decoder，目标函数。

Encoder：假设\(w_i^1, ..., w_i^N\)是句子\(s_i\)中的words，其中N表示在句子中的words数目。在每个step中，encoder会产生一个hidden state：\(h_i^t\)，它可以解释成序列\(w_i^1,...,w_i^t\)的表示（representation）。hidden state：\(h_i^N\)可以表示整个句子。

为了encode一个句子，我们对下面的等式进行迭代（这里去掉了下标i）：

\(r^t = \sigma(W_r x^t + U_r h^{t-1})\) … (1)

\(z^t = \sigma(W_z x^t + U_z h^{t-1})\) … (2)

\(\bar{h}^t = tanh(W x^t + U (r^t \odot h^{t-1})\) … (3)

\(h^t = (1-z^t) \odot h^{t-1} + z^t \odot \bar{h}^t\) …(4)

其中 \(\bar{h}^t\)是在时间t提出的状态更新，\(z^t\)是update gate，\(r^t\)是reset gate（\(\odot\)）表示一个component-wise product。两个update gates会采用0到1间的值。

Decoder: decoder是一个神经语言模型，它的条件是encoder output \(h_i\)。该计算与encoder相似，除了我们引入了矩阵\(C_z，C_r\)，以及C，它们被用于偏置由句子向量计算得到的update gate，reset gate和hidden state。一个decoder会被用于下一个句子\(s_{i+1}\)，而第二个decoder被用于前一句子\(s_{i-1}\)。Separate参数被用于每个decoder，除了词汇矩阵V，它的权重矩阵会连接decoder的hidden state，以便计算在词上的一个分布。我们在下一个句子\(s_{i+1}\)上描述decoder，通过一个在前一句子\(s_{i-1}\)上的类似计算得到。假设\(h_{i+1}^t\)表示decoder在时间t的hidden state。对下面的等式进行迭代（丢掉下标i+1）：

\(r^t = \sigma(W_r^d x^{t-1} + U_r^d h^{t-1} + C_r h_i)\) …(5)

\(z^t = \sigma(W_z^d x^{t-1} + U_z^d h^{t-1} + C_z h_i)\) …(6)

\(\bar{h}^t = tanh(W^d x^{t-1} + U^d (r^t \odot h^{t-1} + C h_i\) …(7)

\(h_{i+1}^t = (1-z^t) \odot h^{t-1} + z^t \odot \bar{h}^t\) …(8)

给定\(h_{i+1}^t\)，单词\(w_{i+1}^t\)的概率给出了前(t-1) words，encoder vector为：

\(P(w_{i+1}^t | w_{i+1}^{<t}, h_i) \propto exp(v_{w_{i+1}^t} h_{i+1}^t )\) …(9)

其中，\(v_{w_{i+1}^{t}}\)表示V的行，对应于word \(w_{i+1}^t\)。对于前面句子\(s_{i-1}\)可以做一个类似的计算。

目标函数。给定一个tuple \((s_{i-1}, s_i, s_{i+1})\)，目标优化为：

\(\sum_{t} log P(w_{i+1}^t | w_{i+1}^{<t}, h_i) + \sum_{t} log P(w_{i-1}^t | w_{i-1}^{<t}, h_i)\) …(10)

总的目标函数是对所有这样的training tuples进行求和。

2.2 词汇表膨胀

现在，我们会描述如何将我们的encoder的词汇表扩展到那些在训练期间未见过的词上。假设我们有个被训练的模型引入了词表示（word representations），假设\(V_{rnn}\)表示了RNN的词向量空间。我们假设词汇表\(V_{w2v}\)比\(V_{rnn}\)更大。我们的目标是构建一个mapping f: \(V_{w2v} \rightarrow V_{rnn}\)，它由一个矩阵W进行参数化，比如：\(v'=Wv\)，其中\(v \in V_{w2v}\)， \(v' \in V_{rnn}\)。受[15]的启发，它会学到在词空间转移之间的线性映射，我们为矩阵W求解一个非正则的L2线性回归loss。这样，对于编码中的句子，任何来自\(V_{w2v}\)的词可以被映射到\(V_{rnn}\)。

3 实验

在我们的实验中，我们在BookCorpus dataset上评估了我们的encoder作为一个通用的feature extractor的性能。实验setup如下：

• 使用学到的encoder作为一个feature extractor，抽取所有句子的skip-thought vectors
• 如果该任务涉及到计算句子对（pairs of sentences）之间的分数，会计算pairs间的component-wise features。
• 在抽取的features上训练一个线性分类器，在skip-thoughts模型中没有任何额外的fine-tuning或者backpropagation。

我们限定在线性分类器主要出于两个原因。第一个是为了直接评估计算向量的representation quality。如果使用非线性模型可能会获得额外的性能增益，但这超出了我们的目标。再者，它可以允许更好地分析学到的representations的优点和缺点。第二个原因是，重现（reproducibility）很简单。

3.1 训练细节

为了引入skip-thought vectors，我们在我们的book corpus上训练了两个独立的模型。一个是带有2400维的unidirectional encoder，它常被称为uni-skip。另一个是一个bidirectional model，forward和backward每个各1200维。该模型包含了两个encoder，它们具有不同的参数：一个encoder会给出正确顺序的句子，另一个会给出逆序的句子。输出接着被拼接形成一个2400维的向量。我们将该模型称为bi-skip。对于训练，我们会初始化所有的recurrent矩阵：进行正交初始化。non-recurrent weights则从一个[-0.1, 0.1]的均匀分布上进行初始化。使用mini-batches的size=128, 如果参数向量的norm超过10, 梯度会被裁减（clip）。我们使用Adam算法进行optimization。模型会被训练两周。另外作为一个额外的试验，我们使用一个组合模型导出了试验结果，包含了uni-skip和bi-skip，会生成4800维的向量。我们称该模型为combine-skip。

在被模型被训练后，我们接着使用词汇扩展，将word embedding映射到RNN encoder空间上。会使用公开提供的CBOW word vectors[2]。被训练的skip-thought会有一个词汇size=20000个词。在从CBOW模型中移除多个word样本后，会产生一个词汇size=930911个词。这样，即使被训练的skip-thoughts模型具有20000个词，在词汇表扩展后，我们可以对930991个可能的词进行成功编码。

由于我们的目标是将skip-thoughts作为一个通用的feature extractor进行评估，我们将文本预处理保持最低水平。当编码新句子时，除了基本的tokenization，不会有额外的预处理。这样做可以测试我们的vectors的健壮性。作为一个额外的baseline，我们也会考虑来自uni-skip模型学到的word vectors的平均（mean）。我们将该baseline称为bow。这会决定着在BookCorpus上训练的标准baseline的效果。

3.2 语义相关性

3.3 段落检测

3.4 Image-sentence ranking

3.5 Classification benchmarks

略

3.6 skip-thoughts可视化

t-sne.

参考

Convolutional Neural Networks for Sentence Classification

《Web Metasearch: Rank vs. Score Based Rank Aggregation Methods》提出了rank fusion的问题。

1.介绍

rank fusion的问题是，给定多个judges的独立ranking偏好（一个ranking是一个items集合的线性顺序），计算一个“一致的（consensus）”ranking。该ranking fusion问题出现在许多情况下，一个著名的场景是metasearch：metasearch会处理由多个search engines对于一个给定query所返回的多个result lists组合，其中，在result list中的每个item对于各自的search engine是有序的，并且有一个相关分值。

搜索引擎们会帮助人们定位与用户信息相关的信息，但仍有一些不足：

• i) 检索web数据是一个耗时的任务。由于web内容变化很快，每个search engine必须在覆盖率(coverage)间做个trade-off，例如，web文档的数据会与整个web以及更新频率（例如，在完整数据库的后续re-indexing间发生的时间）有关。
• ii) 有许多信息源
• iii) 对于一些搜索引擎，广告商付费越多，在search results上的rank会越高，这被称为：“pay-for-placement”，这在precesion上会有平均损失
• iv) search engines会有作弊（spamming）

由于上述这些限制，必须引入metasearch engines来提升检索效果。

ranking fusion的理想场景是，每个judge（search engine）给出对所有alternative items一个完整顺序。不幸的是，在metasearch中这不太现实，有两个原因：

• i) search engines的coverage是不同的
• ii) search engines会限制访问top 100 or 1000个ranked items

因此，rank aggregation必须可以处理具有有限数目个entires的每个ranking。当然，如果rankings间没有重叠项，。。。设计ranking fusion的一个挑战是，当在每个ranking中的top 几百个／上午个items间存在有限个重合项（但non-trivial）。

。。。

2.ranking fusion方法

对于rank-ordered lists进行合并，存在许多方法。最基础的，他们会使用来自ranked lists中已经提供的信息。在大多数情史中，策略依赖于以下信息：

• i) 顺序排序(irdinal rank)：rank list中的一个item分配一个顺序
• ii) 得分(score)：在rank list中分配给每个item的得分

在score-based方法中，items会根据rank lists中的scores进地rank，或者对这些scores做一些转换（transformation）[1,4,8,9,12,13,17,18]；而在rank-based方法中，items会根据rank lists中的rank重新排序，或者对这些ranks做一些转换[1,7,12,19]。另一种正交去重的rank fusion方法则依赖于训练数据（比如：Bayes-fuse方法[1]，或者线性组合方法[17]，或者偏好rank组合方法[8]）。基它一些方法基于ranked items的内容。

2.1 前提

首先看一些基本定义。假设：

• U是一个items集合，称为“universe”。
• \(\tau\)是一个rank list，它与U有关，是关于子集\(S \subseteq U\)的一个排序，例如：\(\tau = [x_1 \geq x_2 \geq \cdots \geq x_k\)，对于每个\(x_i \in S\)，\(\geq\)是在S上的顺序关系.

如果 \(i \in U\)出现在\(\tau\)中，写成\(i \in \tau\)，\(\tau(i)\)表示i的position或rank。我们假设\(U = \lbrace 1,2,\cdots, \mid U \mid \rbrace\)，通过对每个\(i \in U\)分配一个唯一的id，没有对普适性有损失。

。。。

2.2 Fusion方法

本节中，我们将讲述分析的ranking fusion方法。考虑一个包含了n个rankings的集合\(R=\lbrace \tau_1, \cdots, \tau_n \rbrace\)。假设：

• U表示在\(\tau_1, \cdots, \tau_n\)中的items的union，例如：\(U = \cup_{\tau \in R, i \in \tau} \lbrace i \rbrace\)。
• \(\hat{\tau}\)表示ranking（被称为fused ranking或fused rank list），它是一个rank fusion方法应用到在R中的rank lists之后得到的结果。

为了彻底说明\(\hat{\tau}\)，它足够决定分值\(s^{\tau}(i)\)（称为：fused score）(对于每个item \(i \in U\))，因为\(\hat{\tau}\)会根据\(s^{\hat{\tau}}\)的值递减进行排序。我们认为：

• 如果两个fused ranking \(\hat{\tau}_1, \hat{\tau}_2\)是相等的（equal），则：\(\hat{\tau}_1 = \hat{\tau}_2\)
• 如果\(\hat{\tau}_1\)和\(\hat{\tau}_2\)是等价的(equivalent)，那么对于\(i \in U\)，有\(\hat{\tau}_1(i) = \hat{\tau}_2(i)\)（他们具有相同的顺序）

当然，equality意味着equivalence，但反过来不成立。

2.2.1 线性组合

Fox[9]提出的ranking fusion方法基于对每个item的归一化得分(normalised score)采用不加权（unweighted）的min, max或sum。另外，Lee[12]解决了rank取代score的case。两种方法如下：

\[CombSUM: s^{\hat{\tau}}(i) = \sum\limits_{\tau \in R} w^{\tau}(i) \\ CombMNZ: s^{\hat{\tau}}(i) = h(i, R) \cdot \sum\limits_{\tau \in R} w^{\tau}(i)\]

从[9,12]的测试结果看，CombMNZ被认为是最好的ranking fusion方法，它的效果要稍好于CombSUM。根据Lee的实验，CombMNZ基于该事实：“不同搜索引擎返回(return)相似的相关文档集合，但检索(retrieve)不同的不相关文档集合”。确实，CombMNZ组合函数会对常见文档进行大的加权。

。。。

2.2.1.1 Borda Count

Borda的方法[2,14]是一个基于ranks的voting方法，例如，一个candidate出现在每个voter的ranked list中，则会为相应的ranks分配一个weight。计算上非常简单，因为实现是线性的。Borda Count (BC)方法在rank fusion问题中被引入，并以如下方式运转。每个voter会对一个关于c个candidates的固定集合以偏好顺序进行rank。对于每个voter，会给top ranked candidate为c分，第二个ranked candidate会得到c-1分，以此类推。在unranked candidates间则均匀分配剩余得分。candidates会以总分(total points)的递减顺序进行rank。正式的，该方法与以下过程等价：对于每个item \(i \in U\)以及rank list \(\tau \in R\)，Borda归一化权重为\(w^{\tau}(i)\)（定义1）。fused rank list \(\hat{\tau}\)根据Borda score \(s^{\hat{\tau}}\)的顺序排序，其中在\(\hat{\tau}\)中的一个item \(i \in U\)被定义为：

\[s^{\hat{\tau}}(i) = \sum\limits_{\tau \in R} w^{\tau}(i)\]

…(6)

相应的，BC等价于CombSUM方法组合上Borda rank normalisation，（例如：\(\sum.b.0\)）。Aslam[1]也考虑过一种Weighted Borda Count，其中，在对归一化Borda weights求和的部分，会使用这些weights的一个线性组合。

2.2.2 Markovchain-based方法

[7]中提出一种关于rank fusion的有意思的方法，它基于Markov chains实现。一个系统的一个(齐次：homogeneous)Markov chain可以通过一个状态集\(S=\lbrace 1,2, \cdots, \mid S \mid \rbrace\)以及一个\(\mid S \mid \times \mid S \mid\)的非负随机矩阵M（例如：每行的求和为1）来指定。该系统从S中的某个状态开始，并在每个step时会从一个state转移到另一个state。转移(transition)通过矩阵M来指导：在每个step上，如果系统从状态i移到状态j的概率为\(M_{ij}\)。如果给定当前状态作为概率分布，下一状态的概率分布通过表示当前状态的该vector与M相乘得到。总之，系统的起始状态（start state）根据在S上的一些分布x被选中。在m个steps后，该系统的状态会根据\(xM^m\)进行分布。在一些条件下，不需要考虑起始分布x，该系统最终会达到一个唯一确定点（状态分布不再变化）。该分布称为“稳态分布(stationary distribution)”。该分布可以通过M的左主特征向量（principal left eigenvector）y给出，例如：\(yM = \lambda y\)。实际上，一个简单的power-iteration算法可以快速获得关于y的一个合理近似。y中的entries定义了在S上的一个天然顺序。我们称这样的顺序为M的马尔可夫排序（Markov chain ordering）。

对rank fusion问题使用Markov chains如下所示。状态集合(State Set) S对应于包含待排序(rank)的所有candidates的list（例如：在\(R=\lbrace \tau_1, \cdots, \tau_2 \rbrace\)中的所有items的集合）。在M中的转移概率在某种程度上依赖于\(\tau_1, \cdots, \tau_n\)，待估计的\(\hat{\tau}\)是在M上的Markov chain ordering。下面，[7]提出了一些Markov chains(MC):

• \(MC_1\): 如果当前state为item i，那么，下一state从对应rank >= item i的所有items j的multiset中均匀选中，例如，从multiset \(Q_i^{C_1} = \cup_{k=1}^n \lbrace j: \tau_k(j) \leq \tau_k(i) \rbrace\)中均匀选中下一state。

• \(MC_2\)：如果当前state为item i，下一state的挑选过程如下：首先从所有包含i的\(\tau_1, \cdots, \tau_n\)中均匀选中一个ranking \(\tau\)，接着从集合\(Q_{\tau,i}^{C_2} = \lbrace \tau(j) \leq \tau(i) \rbrace\)中均匀选中一个item j

• \(MC_3\)：如果当前state为item i，下一state的挑选过程如下：首先从包含i的所有\(\tau_1, \cdots, \tau_n\)中均匀选择一个ranking \(\tau\)，接着均匀选择通过\(\tau\)排序的一个item j。如果\(\tau(j) < \tau(i)\)那么跳到j，否则留在i；

• \(MC_4\)：如果当前state为item i，下一state挑选过程如下：首先从S中均匀选中一个item j。如果\(\tau(j) < \tau(i)\)对于会同时对i和j进行排序的lists \(\tau \in R\)中的大多数都成立，那么跳到j，否则留在i。

注意，Markov chain方法确实只依赖于ranks间的比较，即不考虑scores也不考虑hits。下面是一个示例。

示例1.考虑以下在S={1,2,3}中的三个items的rankings \(R = \lbrace \tau_1, \tau_2, \tau_3 \rbrace\).

图1

它可以展示成关于\(MC_1, MC_2, MC_3, MC_4\)的转移矩阵，分别为：\(M^1, M^2, M^3, M^4\)。

图2

下面，我们会为matrix entries展示一些示例计算。记住\(M_{ij}^k\)是给定当前state（item i）到下一state（item j）的概率。

• \(M_{13}^1\)是2/6. 确实，\(Q_1^{C_1}\)是\(\lbrace 1,1,3,1,2,3 \rbrace\)(rank<=item 1的case：1; 1,3; 1,2,3)。因此，在\(Q_1^{C_1}\)中均匀选中某一元素的概率为1/6, 选中item 3的概率为2/6.

• \(M_{21}^2\)是5/18. 均匀选择一个包含item 2的rank list的概率为1/3. 如果\(\tau_1\)被选中，那么\(Q_{\tau_1,2}^{C_2}=\lbrace 2,1 \rbrace\)。因此，选中item 1的概率为1/2. 相似的，有\(Q_{\tau_2,2}^{C_2}=\lbrace 2,1,3 \rbrace\)，以及\(Q_{\tau_3,2}^{C_2}=\lbrace 2, 3 \rbrace\)。因此，\(M_{21}^2 = \frac{1}{3} \cdot \frac{1}{2} + \frac{1}{3} \cdot \frac{1}{3} + \frac{1}{3} \cdot 0 = \frac{5}{18}\)

• \(M_{23}^3\)是2/9. 均匀选中一个包含item 2的概率为1/3. 在一个rank list范围内均匀选择一个item的概率也为1/3. 由于\(\tau_1(3) \nless \tau_1(2), \tau_2(3) < \tau_2(2), \tau_3(3) < \tau_3(2)\), 因此\(M_{23}^3 = \frac{1}{3} \cdot 0 + \frac{1}{3} \cdot \frac{1}{3} + \frac{1}{3} \cdot \frac{1}{3} = \frac{2}{9}\)。

图3

• \(M_{22}^4\)是1/3. 均匀选中在S中一个item的概率为1/3. 另外，考虑图3中的表：在上表中的每个entry \(a_{ij}\)是满足\(\tau \in R, \tau(j) < \tau(i)\)的lists的count数（例如，有多少rankings满足：item j的rank比item i要好）。由于存在三个lists，因此majority的阀值是2. \(M_{22}^4\)指的是：给定item 2, 在下一step之后我们仍停留在item 2上的概率。由于\(a_{21}, a_{22}, a_{23}\)分别是2､ 0､ 2, 三种情况中有两种会从item 2进行转移，另一种仍会停留在item 2上。相应的\(M_{22}^4\)是1/3.

最终，rank set R的fused rank list \(\hat{\tau}_k\)是在\(M^k, k=1, \cdots, 4\)上的Markov chain ordering。可以看到所有4种情况都是：\(\hat{\tau}=[3 \geq 2 \geq 1]\)。

3.实验

3.1 数据集

使用Text Retrieval Conference(TREC)数据集。它提供了具有许多rank lists的大的、标准的数据集，准备进行fused。通常，每年会提供一个大的文档数据base S和一个包含 50个querie的list。在ad-hoc和web信息检索大会上，每个系统x会

参考

• 1.http://www.umbertostraccia.it/cs/download/papers/SAC03/SAC03.pdf