我们来看下standford的Aditya Grover的《node2vec: Scalable Feature Learning for Networks》。

1.介绍

node2vec是一种半监督算法，用于在网络中的可扩展特征学习。受之前NLP中工作[21]的启发，我们会使用SGD对一个定制的基于图的（graph-based）目标函数进行优化。直觉上，该方法会返回特征表示，对于在d维空间内的节点，会对它们的网络邻节点的似然进行最大化。我们使用2-order的随机游走来为顶点生成（抽样）网络邻节点。

我们的关键贡献是，为一个顶点的网络邻节点定义了一个灵活的概念。通过选择一个合适的概念，node2vec可以学到网络表示，它们可以基于现在的网络角色，或者属于的社群来进行组织。我们通过开发一个有偏的随机游走（biased random walks）的族谱，它可以有效探索一个给定顶点的邻居分布。结果算法很灵活，提供可调参数给我们以对搜索空间进行控制，而不是之前的方法[24,28]进行严格搜索（rigid search）。相应的，我们的方法可以建模网络等价物。参数管理着我们的搜索策略，具有一个直观解释，会让walk朝着不同的网络搜索策略进行偏移。这些参数在一个半监督学习中，只使用很小比例的带标注数据（labeled data）就可以直接学到。

我们也展示了单独节点的特征表示如何被扩展成节点对（pairs of nodes。比如：边）。为了生成边的特征表示，我们将将学到的特征表示与简单的二元操作相组合。这种组合（compositionality）将node2vec引入到关于节点（或者是边）的预测任务上。

我们的试验集中在两个关于网络的公共预测任务上：一个多标签分类任务，其中每个节点被分配一或多个标签；一个链接预测任务，其中给定一个节点对，预测该边是否存在。我们将node2vec与state-of-art的特征学习方法[24,28]进行对比。并从现实中不同领域中的网络进行实验，比如社交网络，信息网络，以及系统生物学网络。对比起state-of-art的方法，实验演示了nod2vec在多标签分类上要好26.7%，在链接预测的任务上要好12.6%。该算法展示了有竞争力的效果，即使只有10%的带标签数据，对于噪声或缺失边的情况下一样健壮。计算上，node2vec的主要过程是并行化的，它可以扩展到带有数百万节点的大网络上，只需要几个小时的计算量。

该paper主要贡献是：

• 1.提出了nod2vec，一种用于网络特征学习的高效的扩展算法，可以通过一种显著的network-aware，neighborhood preserving objectives，使用SGD方法进行高效优化。
• 2.我们展示了node2vec如何适应在网络科学中已确立的准则，提供了在发现表示上的灵活性，并有不同的等价物。
• 3.我们基于neighborhood preserving objectives，扩展了node2vec以及其它特征学习方法，将节点扩展到节点对，来基于边的预测任务。
• 4.在多个真实数据集上，在多标签分类和链接预测上评估node2vec。

2.

在NLP的表征学习的最近进展上，有新方法对离散目标（比如：词）进行特征学习。特别的，Skip-gram模型是目标就是学习连续的特征向量，通过优化一个(neighborhood preserving likelihood objective). 该算法的处理如下：扫描一个文档的词，对于每个词，它的目标是将它进行嵌入，以便该词的特征可以预测邻近词（例如：在一些上下文窗口中的词）。词的特征表示通过使用SGD、negative sampling对likelihood objective进行优化学习得到。skip-gram目标函数是基于分布式假设：有相似上下文的词，趋向于具有相近的意思。也就是说，相似的词趋向于出现在具有相似词邻居的上下文内。

受skip-gram模型的启发，最近的研究确立了一种网络的类比法，将一个网络表示成一个“文档（document）”。相同的方法是，一个有序的词序列，节点序列需要从底层网络上进行采样，将一个网络转化成一个有序的节点序列。然而，对于节点来说，存在许多可能的抽样策略，会从而学到不同的特征表示。事实上，正如我们展示的，对于所有网络和所有预测任务来说，没有明确可胜出的抽样策略可以适用所有场景。以前的方法的主要缺点是，在从一个网络上进行抽样节点时缺乏灵活性。我们的算法node2vec克服了该限制，通过设计一种灵活的目标函数，它不会绑定一个特定的抽样策略，提供参数来调节探索的搜索空间（见第3节）。

最终，对于基于节点和基于边的预测任务，存在许多监督特征学习方法[15,17,31,39]。这些架构直接最小化loss function，使用多层非线性转换来产生更高的accuracy，但扩展开销高，因为训练时间长。

…

3.特征学习框架

我们将网络特征学习看成是一个极大似然优化问题。给定一个网络\(G = (V, E)\)。我们的分析是普适性的，可以应用于任何有向（无向）、加权（不加权）的网络。假设：\(f: V -> R^d\)是映射函数，将节点映射到特征表示。这里的d是特征表示的维度。f是一个size为\(\|V\| \times d\)的参数矩阵。对于每个源节点（srouce node）\(v \in V\)，我们定义了\(N_S(u) \subset V\)作为节点u的一个网络邻节点，它通过邻节点采样策略S来生成。

我们扩展了Skip-Gram架构来处理该网络。我们对下面的目标函数进行最优化，它会基于它的特征表示，对一个节点u的一个网络邻节点\(N_S(u)\)的log概率进行最大化，f给定：

\(max_f \sum_{u \in V} log Pr(N_S(u) | f(u))\) …(1)

为了让最优化变得可处理，我出做出了两个标准假设：

• 条件独立性。我们通过假设：给定源节点的特征表示，观察到一个邻节点的似然，与观察到其它邻节点是独立的：

\[Pr(N_s(u) | f(u)) = \prod_{n_i \in N_S(u)} Pr( n_i | f(u))\]

• 特征空间的对称性。一个源节点和它的邻节点在特征空间中具有对称性的相互影响。因而，我们建模每个（源节点-邻节点）pair的条件似然建模成一个softmax unit，它由它们的特征点积进行参数化：

\[Pr(n_i | f(u)) = \frac{exp(f(n_i)\cdot f(u))} {\sum_{v \in V} exp(f(v) \cdot f(u))}\]

有了以上假设，等式一的目标可以简化为：

\(max_{f} \sum_{u \in V} [ -log Z_u + \sum_{n_i \in N_S(u)} f(n_i) \cdot f(u) ]\) …(2)

每个节点的分区函数：\(Z_u = \sum_{v \in V} exp(f(u) \cdot f(v))\)，对于大网络来说计算开销很大，我们可以使用负采样[22]来对它做近似。我们使用SGA（ascent）对等式(2)进行优化.

基于skip-gram的特征学习方法，最早源自于NLP上下文学习。文本本身是线性的，一个邻词可以很自然地使用一个在连续词汇上的滑动窗口进行定义。而对于网络，是非线性的，因而需要更丰富。为了解决这一点，我们提出了一个随机过程，它会对给定源节点u抽样许多不同的邻节点。\(N_S(u)\)不局限于它的立即邻节点（immediate neighbors），具体取决于抽样策略S，有不同的结构。

3.1 经典搜索策略

图1

我们将对一个源节点的邻节点进行抽样的问题看成是一种局部搜索（local search）。图1展示了一个图，其中，给定一个源节点u，我们的目标是生成(抽样)它的邻节点\(N_S(u)\)。重要的是，为了比较不同的抽样策略S，我们将邻节点集合\(N_S\)的size限制为k个节点，接着为单个节点u抽样多个集合。总体上，有两种极限抽样策略来生成k个节点的邻节点集合\(N_S\)：

• 广度优化抽样（BFS：Breadth-first Sampling）: 邻节点\(N_S\)被限制到关于源节点的立即领节点上（immediate neighbors）。例如：在图1中，对于一个邻节点的size为 k=3, BFS抽样的节点为：\(s_1, s_2, s_3\)。
• 深度优化抽样（DFS：Depth-first Sampling）：邻节点包含了从源节点开始在增加的距离上按顺序抽样的节点。在图1中，DFS抽样\(s_4, s_5, s_6\)

BFS和DFS表示了根据搜索空间进行探索的两种极限情况。

特别的，在网络上的节点的预测任务通常会是两种类型相似度的混合（shuffle）：同质（homophily）等价 和结构（structural）等价。在同质假设下，节点高度交错连接，并且属于同网络聚类或社群，在embedding上更紧密（例如：图1中的节点\(s_1\)和u属于相同的网络社群）。相反的，结构等价假设下，在网络上具有相似结构角色的节点，应该在embedding上更紧密（例如：节点u和\(s_6\)在图1上分演扮演着相应社群中心的角色）。更重要的是，不同于同质等价，结构等价不强调连通性；在网络中的节点可以离得很远，但它们仍具有相近的网络结构角色。在真实世界中，这些等价概念并是排斥的；网络通常具有两者的行为。

我们观察到，BFS和DFS的策略在处理表示时扮演着重要角色，它影响着上述两种等价。特别的，BFS抽样的邻节点会导致embedding与结构等价更紧密。直觉上，我们注意到，为了探明结构等价，通常会对局部邻节点进行精准的描述。例如，基于网络角色（桥接：bridges、中心：hubs）的结构等价可以通过观察每个节点的立即节点(immediate neighborhoods)观察到。通过将搜索限制到邻近节点，BFS达到了这种characterization， 并且获得了关于每个节点的邻近点的微观视角。另外，在BFS中，在抽样邻节点上的节点趋向于重复多次。这很重要，对于。

3.2 node2vec

基于上述观察，我们设计了一种灵活的邻节点抽样策略，它允许我们在BFS和DFS间进行平衡。我们通过开发一种灵活的有偏随机游走（biased random wolk）过程，它可以以BFS和DFS的方式来探索邻节点。

3.2.1 随机游走

给定一个源节点u，我们进行模拟一个固定长度为l的随机游走。\(c_i\)表示在walk中的第i个节点，从起点\(c_0=u\)开始。节点\(c_i\)通过下面的方式生成：

\[P(c_i=x | c_{i-1}=v) = \begin{cases} \frac{\pi_{vx}}{Z} , if(v,x) \in E \\ 0 , otherwise \end{cases}\]

其中\(\pi_{vx}\)是未归一化的节点v和x间的转移概率，而Z是归一化常量。

3.2.2 搜索偏差\(\alpha\)

对我们的随机游走进行bias的最简单方法是，基于一个静态边权重\(w_{vx}\)（例如: \(\pi_{vx} = w_{vx}\)）来抽样下一个节点（无权重图则\(w_{vx}=1\)）。然而，该种情况不能解释网络结构，并指导搜索过程来探索不同类型的网络邻居。另外，不同于BFS和DFS两个极端，我们的随机游走会兼容两者。真实网络中通常也是两者混合。

图2: 在node2vec中的随机游走过程说明。该walk会从t到v进行转移，并在node v准备出去的下一步进行评估。边的labels表示搜索的bias \(\alpha\)

我们定义了一个2阶随机游走，它具有两个参数p和q来指导walk：考虑到一个随机游走，它穿过边(t,v)，现在留在节点v上（图2）。该walk需要决定，在下一步它会评估在边(v,x)上由v产生的转移概率\(\pi_{vx}\)。我们设置未归一化转移概率为\(\pi=\alpha_{pq}(t,x) \cdot w_{vx}\)，其中：

\[\alpha_{pq}(t,x) = \begin{cases} \frac{1}{p} , if d_{tx}=0 \\ 1 , if d_{tx}=1 \\ \frac{1}{q} , if d_{tx}=2 \end{cases}\]

其中，\(d_{tx}\)表示在节点t和x上的最短路径距离。注意，\(d_{tx}\)必须是{0, 1, 2}其中之一，因而，两个参数都是必须的，可以充分指导该walk。

直觉上，参数p和q控制着该walk从起始节点u进行探索和离开邻节点的快慢。特别的，该参数允许我们的搜索过程（近似）在BFS和DFS间进行插值，从而影响不同节点等价的紧密关系。

返回（Return）参数：p。参数p控制着在walk中立即访问一个节点的似然。将它设置成一个高值(> max(q,1))，可以确保我们在下两步内对一个已经访问节点进行抽样的可能性变得很小。（除非在walk内的下一个节点没有其它邻居）。这种策略鼓励适度探索，避免在抽样时存在二跳内重复（2-hop redundancy）。另一方面，如果p很小（<min(q,1)），它将导致该walk会回溯(backtrack)一个step（见图2），并且这会让该walk“局部”上保持与起始节点u的接近。

入出（In-out）参数：q。参数q允许搜索在“inward”和”outward”节点间区分。回到图2, 如果q>1, 随机游走会偏向于更接近节点t的节点。这样的walk会根据在walk中各自的起始节点获得一个关于底层graph的局部视图，近似的BFS行为感觉上我们的抽样在一个小的局部内的节点组成。

作为对比，如果 q < 1, 该walk更趋向于访问那些离节点t更远的节点。这样的行为受DFS影响，它会鼓励outward探索。然而，这里的一个基本不同是，我们在随机游走框架内完成DFS-like的探索。因而，被抽中的节点不需要对到给定节点u的距离进行增加才行，反过来，我们受益于对随机游走的回溯预处理和优秀的采样效率。注意，通过将\(\pi_{v,x}\)设置成关于一个在walk t内前继节点的函数，随机游走是2阶markovian。

随机游走的好处。比起纯BFS/DFS方法，随机游走有许多好处。随机游走在时间和空间需求上的计算很高效。在图中为每个节点存储它的立即邻节点的空间复杂度为\(O(\|E\|)\)。对于二阶随机游走，会存储在每个节点的邻节点间的交叉连接，这会引发一个空间复杂度为\(O(a^2 \|V\|)\)，其中\(a\)是该graph的平均度，它通常对于现实网络来说很小。比起经典的基于搜索的抽样策略，随机游走的其它核心优点是它的时间复杂度。特别是，通过引入在抽样生成过程中的图连通性，随机游走提供了一个很便利的机制，通过复用跨不同源节点间的样本，来增加有效抽样率。通过模拟一个长度l>k的随机游走，得益于随机游走的马尔可夫性，我们可以为l-k个节点一次生成k个样本。因而，每个样本的有效复杂度为\(O(\frac{1}{k(1-k)})\)。例如，在图1中，我们抽样一个长度为l=6的随机游走 {\(u, s_4, s_5, s_6, s_8, s_9\)}，它会产生\(N_S(u)=\left s_4, s_5, s_6 \right\)，\(N_S(s_4)=\left s_5, s_6, s_8 \right\)，以及\(N_S(s_5)=\left s_6, s_8, s_9 \right\)。注意，在整个过程中，样本复用可能引入一些bias。然而，我们观察到它可以极大提升效率。

3.2.3 node2vec算法

算法1

node2vec的伪代码，详见算法一。在任何随机游走中，由于起始节点u的选择，会有一个隐式偏差（implicit bias）。由于我们为所有节点学习表示，我们会为每个节点通过模拟r个固定长度为l的随机游走来对该bias进行补偿（offset）。在该walk的每一个step，会基于转移概率\(\pi_{vx}\)进行抽样。对于二阶马尔可夫链，转移概率\(\pi_{vx}\)可以被预计算好，因而，当模拟随机游走时，节点的抽样可以很有效地在O(1)时使用alias sampling完成。node2vec的三个阶段（phases），即：预处理计算转移概率、随机游走模拟、使用SGD进行优化，是按顺序进行的。每个phase可以并行化和异步执行，从而做到node2vec整体可扩展性。 node2vec的一个实现：http://snap.stanford.edu/node2

3.3 学习边特征

node2vec算法提供了一个半监督方法来学习网络中节点的丰富特征表示。然而，我们通常对涉及节点对（pairs of nodes）的预测任务感兴趣，而非单个节点。例如，在链接预测上，我们在网络中的两个节点间预测一个链接是否存在。由于我们的随机游走在底层网络上天然地基于节点间的连通结构，我们可以使用一个bootstrap方法来将它们扩展到节点对的特征表示，而非单个节点的特征表示。

给定两个节点u和v，我们定义了一个二元操作o，在相应的特征向量f(u)和f(v)，为了生成一个表示g(u,v)，比如：\(g: V \times V -> R^d^'\)，其中\(d'\)是pair(u,v)的表示的size。我们希望我们的操作对于任意节点对可以进行定义，即使一条边在pair间不存在，因为这样做可以使表示对于连接预测有用，我们的测试集包含了true edges和false edges（不存在）。我们对于操作符o的一些选择，以便\(d'=d\)，由表1归纳的。

实验

略

node2vec: Scalable Feature Learning for Networks

hinton在google提出了《Distilling the Knowledge in a Neural Network》 knowledge distillation。

1.介绍

许多昆虫会有一个幼虫状态，可以最优地从环境中抽取能量和营养；也会有一个成虫状态，以便最优地进行飞行和繁衍。在大规模机器学习中，我们通常在训练阶段和部署阶段使用非常相似的模型来，尽管两个阶段有着非常不同的要求：对于像语音识别和目标识别，训练必须从非常大、高度过剩的数据集中抽取结构，但不能实时地方式运行，它会使用大量计算。然而，部署大量用户通常在时延（latency）和计算资源上具有非常多的严格要求。在昆虫上的类比，建议我们可以去训练非常大的模型（cumbersome models），它可以轻易地抽取来自数据中的结构。cumbersome model可以是独立训练模型的ensemble，或者使用像dropout等强正则方式训练的单个非常大的模型。一旦cumbersome model被训练后，我们可以接着使用一个不同方式的训练，我们称作“distillation”，可以将来自cumbersome model的knowledge进行transfer到一个小模型中，它会更适合部署。该策略的版本已经由Rich Caruana和它的同事一起率先尝试。在他们的重要paper中，他们表示可以由一个大模型的ensemble的knowledge进行transfer到一个小模型中。

一个阻止更多研究这种方法的概念块是：我们趋向于使用已学到的参数值来识别出（identify）在一个已训练模型中的knowledge，这使得它很难看到：在仍会记住相似的knowledge之下，该模型的形式是如何变化的。从knowledge的一个抽象视角看（这会从任何特殊实例中解释出来），是从input vectors到output vectors的一个可学习映射（learned mapping）。对于cumbersome models，可以学习判别许多类，常规的训练目标（normal training loss）是：对正确答案（correct answer）最大化平均log概率，但该学习的一个side-effect是：该训练好的模型会分配概率给所有不正确的答案，即使当这些概率非常小时，其中一些会比其它更大。不正确答案的相对概率告诉我们关于cumbersome model是如何趋向于gnerealize的许多信息。例如，一张关于BMW的照片，可能有少量的机会被误认为是一个垃圾车（garbage truck），但这种错误仍然要比被误认为一个胡萝卜的概率要大许多倍。

这通常是可接受的，对于训练使用的objective function会影响该用户的true objective，使得尽可能接近。尽管如此，模型通常会被训练成在训练数据上最优化，当实际objective是泛化给新数据。它会明显更好地训练模型以便更好泛化，但这需要关于correct way的信息来泛化，该信息通常没有提供。当我们从一个大模型中distill知识给小模型时，我们可以训练该小模型来泛化（正如大模型一样）。例如，如果cumbersome model泛化良好，它是一个不同模型的ensemble，一个小模型会以相同的方式训练用来进行泛化，通常会比正常训练的单个小模型在测试数据上要好。

transfer该cumbersome model的泛化能力的一个直接方式是，使用由cumbersome model生成的类概率(class prob)作为“soft targets”来进行训练小模型。对于transfer阶段，我们可以使用相同的训练集或者一个单独的”transfer” set。当cumbersome model是一个许多更简单模型的ensemble时，我们可以使用一个单一预测分布的算法或者几何平均作为soft targets。当soft targets具有高熵时（high entropy），他们会比hard targets在每个训练case上提供更多信息，并在traning cases间的梯度上具有更小的variance，因此小模型通常会比原始的cumbersome model使用更少数据训练，并使用一个非常更高的learning rate。

对于像MNIST这样的任务，它的cumbersome model几乎总是生成具有正确答案，它会具有高置信度、更多关于learned function的信息，在soft targerts中以非常小的概率比（ratios）存在。例如，一个关于2的version，可能会给出一个具有概率\(10^{-6}\)是3，以及\(10^{-9}\)是7，其它version有其它的形式。这是非常有价值的信息，它定义了一个在数据上的丰富的相似结构（例如：2看起来像3，也看起来看7），但它在transfer stage时在cross-entropy cost function上具有非常小的影响，因为该概率会非常接近于0。Caruana和它的同事通过使用该logits（到最终softmax的inputs）来解决该问题，而非由softmax生成的概率作为targets来学习该小模型，并且它们会最小化在logits和cumbersome model间的平方差（squared difference）。我们的更通用解决方案称为“distillation”，会提出关于final softmax的temperature，接到cumbersome model生成一个关于targets的合适soft set。当训练该小模型时，我们接着使用相同的temperature匹配这些soft targets。我们会接着展示：对该cumbersome model进行匹配logits实际是distillation的一个特例。

transfer set被用于训练小模型，可以包括无标记的数据（unlabeled data），或者我们可以使用原始的training set。我们已经发现，使用该原始的training set运行良好，特别是：如果我们添加一个小项到objective function中时，这会鼓励小模型去预测true targets，同时茶杯由cumbersome model提供的soft targets。通常，小模型不能完全匹配soft targets，并且在正常答案上的erring可以是有帮助的。

2.Distillation

许多networks通常会使用一个”softmax” output layer来生成类概率（class probabilities），它会对logits \(z_i\)进行转化，为每个class计算一个probability, \(q_i\)，并与其它logits进行相互比较\(z_i\)。

\[q_i = \frac{exp(z_i / T)}{\sum_j exp(z_j / T)}\]

…(1)

其中，T是一个temperature，通常设置为1. 将T设置得更高会生成一个在classes上的softer probability分布。

在distillation的最简形式中，通过在一个transfer set上训练模型，并使用一个对每个case在transfer set中的一个soft target分布（使用cumbersome model并在softmax中使用一个高temperature），knowledge会被转移到distilled model中。当训练该distilled model时，会使用相同高的temperature，但在它被训练后，它会使用一个temperature为1。

当correct labels被所有或部分transfer set知道时，该方法可以极大提升，也可以训练该distilled model来生成correct labels。这样做的一种方式是，使用correct labels来修正soft targets，但我们发现一种更好的方式是：简单使用一个对两个不同objective functions的weighted average。第一个objective function是使用soft targets的cross entropy，该cross entropy使用distilled model的softmax上的相同logits，但temperature=1。我们发现，获得的最好结果，会在objective function上使用一个相当低的weight。由于通过soft targets生成的梯度幅度缩放为 \(1/T^2\)，当同时使用hard和osft targets时，乘上\(T^2\)很重要。当实验使用meta-parameters时，如果用于distillation的temperature发生变化，这可以确保hard和soft targets的相对贡献仍然大致不变。

2.1 匹配logits是distillation的一个特征

在transfer set中每个case，对于distilled model的每个logit \(z_i\)，贡献了一个cross entropy gradient, \(dC/ dz_i\)。如果cumbersome model具有logits \(v_i\)，它会生成soft target probabilities \(p_i\)，并且transfer training会在temperature T上完成，我们给出了该gradient：

\[\frac{\partial C}{\partial z_i} = \frac{1}{T} (q_i - p_i) = \frac{1}{T} (\frac{e^{z_i/T}}{\sum_j e^{z_j/T}} - \frac{e^{v_i/T}}{\sum_j e^{v_j/T}})\]

…(2)

如果对于logits的幅值，temperature高，我们可以近似：

\[\frac{\partial C}{\partial z_i} \approx \frac{1}{T}(\frac{1+z_i/T}{N+\sum_j z_j/T} - \frac{1+v_i/T}{N + \sum_j v_j/T}\]

…(3)

如果我们假设：对于每个transfer case，logits已经是独立零均值的，以便\(\sum_j z_j = \sum_j v_j = 0\)，等式3简化为：

\[\frac{\partial C}{\partial z_i} \approx \frac{1}{NT^2} (z_i - v_i)\]

…(4)

因此，在高temperature限制下，distilliation等价于最小化\(1/2(z_i - v_i)^2\)，提供的logits对于每个transfer case都是独立零均值的。在更低的temperatures上时，distilliation会花费更少的attention来matching logits，以便比平均有更多的negative。这有潜在优势，因为这些logits对于用于训练cumbersome modelcost function几乎完整无限制，因此他们可能非常有noisy。另一方面，非常负的logits可能会传达关于由cumbersome model获取knowledge的有用信息。这些效果占据着哪些是一个经验性问题。我们展示了当distilled model太小，而不能获取cumbersome model中的所有知识，intermediate temperatures会运行最好，会强烈建议忽略掉大的negative logits，这样会有用。

3.在MNIST上的初步实验

…

4.在语音识别上的实验

…

5.在非常大数据集上训练ensembles

…

6.Soft targets作为Regularizers

使用soft targets来替代hard targets的主要目的之一是，在soft targets中携带的一大堆有用的信息，不能使用单个hard target进行编码。在本节中，我们展示了，通过使用相当少的数据来满足baseline语音模型中85M参数，有非常大的影响。表5展示了只有3%的数据（大概20M样本），使用hard targets的baseline model进行训练，会导致严重的overfitting（我们做了early stopping，但在accuracy达到44.5%迅速下降），其中使用soft targets的相同模型可以恢复几乎在完整训练集上的所有信息（大概2%）.这十分深刻，注意我们不必做early-stopping：使用soft targets的系统会简单“收敛”到57%。这展示了soft targets是一个非常有效的方式，一个模型在所有数据上训练发现的regularities会与另一个模型相交流（communicating）。

6.1 使用soft targets来阻止specialist避免overfitting

在JFT dataset上，我们在实验上使用的specialists会将所有其它非专家类（non-specialist classes）收缩到单个垃圾类上（dustbin class）。如果我们允许specialists具有一个在所有classes上的full softmax，比起early stopping有一种更好的方式来阻止overfitting。一个specialist会在它的special classes上高度增强的数据上进行训练。这意味着，训练集的有效大小（effective size）会更小，它具有一个很强的趋势来overfit它的special classes。该问题不能通过将specialist变得更小来解决，因为我们会丢掉非常有用来自对所有non-specialist classes建模得到的transfer effects。

我们的实验会使用3%的语音数据，它强烈建议如果一个specialist会使用genrealist的weights进行初始化，我们可以让它保持几乎所有关于non-special classes的知识，通过为non-special classes使用soft targets来训练，另外使用hard targets来训练它。soft targets可以由generalist来提供。我们现在会探索该方法。

7.与MoE（Mixtures of Experts）的关系

使用specialists可以在数据的子集上进行训练，它与MoE（mixtures of experts）具有相似性，它使用一个gating network来计算分配每个样本到每个expert的概率。同时，由于experts会学习来处理分配给它们的样本，gating network会学习选择哪个experts来分配每个样本，基于experts对该样本的相对判别表现（relative discriminative performance）。使用该关于该experts的discriminative performance来判断该学到的分配，会比简单将input vectors进行聚类并为每个cluster分配一个expert的方式要好的多，但它使得训练很难并行化：首先，每个expert的加权训练集（weighted training set）会以依赖于所有其它experts的方式保持变更；第二，gating network需要对比在相同样本上不同experts的表现来知道如何修正它的分配概率。这些难点意味着：MoE（Mixture of experts）很少被用于那些最有收益的地方：具有海量数据集并且包括着不同的子集的任务。

对多个specialists的训练并行化更容易。我们首先训练一个gneralist model，接着使用confusion matrix来定义用于训练specialists的subsets。一旦这些subsets已经被定义，specialists可以完全独立进行训练。在test time时，我们可以使用genralist model的预测来决定，哪个specialists是相关的，并且只有这些specialists需要被运行。

8.讨论

我们已经展示了，distilling可以式作良好，将一个ensemble、或者从一个大的高度复杂的模型的知识进行transfer到一个更小的distilled model上。在MNIST上，当transfer set被用于训练distilled model时，即使缺少一或多个classes，distillation的效果也很好。对于一个更深的语音模型，用于android voice search，我们展示了，几乎所有的提升都通过训练一个dnn的ensemble并将它distilled到相同size的单个neural net上（它更容易部署）来达到。

对于实际的大神经网络（big neural networks），训练一个full ensemble是可行的，但我们发现，单个大网络要训练很久，可以通过学习大量specialist nets来极大提升效果，每个specialist可以学习判断在一个高度confusable cluster中的classes。到目前为上，我们并没有展示，我们可以在specialists中的知识distill到单个大的net上。

参考

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

yahoo japan在kdd 2017的《Embedding-based News Recommendation for Millions of Users》提出了关于新闻推荐的一些方法：

#

理解文章内容和用户偏好，对于做出有效新闻推荐来说很必要。而基于ID的方法，比如：CF和低秩因子分解，也可以做出推荐，但它们不适用于新闻推荐，因为候选文章会快速超期，在短时内被更新的替代。Word-based方法，常用于信息检索，是很好的候选方法，但它们只与用户历史动作的”queries”同义相关。该paper提出了一种embedding-based方法，它使用分布式表示，以一个3-step end-to-end的方式进行：

• i) 基于一个denoising autoencoder的变种生成文章的分布式表示
• ii) 使用一个RNN，将用户浏览历史作为输入序列，生成用户表示
• iii) 基于内积（inner-product）操作为用户匹配（match）和列出(list)对应文章，并考虑上系统性能。

提出的方法在Yahoo! Japan的主页上的历史访问数据进行评估和实验，并表现良好。我们基于实验结果，在我们实际的新闻分发系统上实现了它，并比较它的在线效果。CTR的提升有23%，总时长（total duration）提升了10%，对比起常用的方法。我们提出的方法已经开放给所有用户，并每天提供推荐给超过1000w个人用户，每月访问次数超10亿。

1.介绍

对于用户来说，读取所有存在的文章的新闻分布是不可能的，这受限于时间。因而，用户喜欢新闻服务可以选择性地提供文章。这种选择通常由编辑人工完成，所选故事的公共集合会在传统媒体上（比如：电视新闻节目、报纸）被提供给用户。然而，在互联网上，我们可以使用以下信息：user ID cookies、单个用户的个性化阅读文章等等，从而对用户进行标识来更好地选择文章。

ID-based方法，比如CF或低秩因子分解，可以很好地做出推荐。然而，[22]建议，这样的方法不适合于新闻推荐，因为候选文章很快会过时。因而，新闻推荐需要有三个关键点：

• 理解文章内容
• 理解用户偏好
• 基于内容和偏好为用户列出挑选的文章

另外，在现实中能快速响应扩展性和噪声并做出推荐很重要[14]。应用也需要在数百ms内返回响应给每个用户。

覆盖上面三个关键点的一个baseline实现如下。一篇文章被看成是关于它的文本的一个词集合（words collection）。一个用户可以看成是他/她浏览的多篇文章的一个词集合（words collection）。该实现会使用文章集和它的浏览历史之间的词共现作为特征来学习点击概率。

该方法有一些实际优点。它可以快速响应最新趋势，因为模型很简单，可以很快进行学习和更新。优先级的估计可以使用已经存在的搜索引擎和词的倒排索引进行快速计算。

出于这些原因，我们的之前版本实现基于该方法。然而，有一些要点可能会对推荐质量有负面影响。

第一个是词的表征（representation of words）。当一个词只当成一个feature使用时，两个具有相同意思的词会被看成是完全不同的feature。该问题会趋向于出现在在新闻文章中当两个提供者对于相同的事件提交文章时。

第二个问题是，浏览历史的处理。浏览历史在该方法中被处理看一个集合（set）。然而，他们实际上是一个序列，浏览的顺序应能表示用户兴趣的转移。我们也必须注意，用户在历史长度上分别很大的，从私人浏览，到那些每小时多次访问。

基于深度学习的方法已经在多个领域取得效果。词的分布式表示可以捕获语义信息。RNN已经为处理不同长度的输入序列提供了有效结果【9,15,17】。

如果我们使用一个RNN来构建一个深度模型来估计用户和文章间的兴趣度，另一方面，很难满足在实时系统中的响应限制。该paper提出了一个embedding-based方法，它使用一个在3-step end-to-end中使用分布式表示的方法，基于相关性和重复性，来为每个用户表示文章列表中的每篇文章。

• 基于一个denoising autoencoder的变种来生成文章的分布式表示
• 通过使用一个RNN，使用浏览历史作为输入序列，来生成用户表示
• 为每个用户基于用户-文章的内积，根据相关性和文章间的去重性，来匹配和列出文章

我们的方法的关键点是估计文章-用户间（article-user）的相关性。我们可以在用户访问足够时间之前，计算文章表示和用户表示。当一个用户访问我们的服务时，我们只选择他／她的表示，它计算候选文章和该表示间的内积。我们的方法可以表达包含在用户浏览历史中的复杂关系，并能满足实时性限制。

提出的方法被用到新闻分发服务中。我们比较了我们的方法和其它方法，结果表明，提出的方法要好于常用方法，不管是在实时服务上还是静态实验数据上，缺点是，增加了学习时间，模型更新延迟，但都在允许范围内。

2.服务和处理流

在该paper中讨论的方法被用在Yahoo！Japan上。第6节描述的在线实验也在该页上进行。

图1: Yahoo!Japan在移动端的主页示例。该paper讨论了关于个性化模块中的文章的方法

图1展示了一个我们的服务的实物，可以在May 2015复现。在顶部header有一个搜索窗口和其它服务的链接。中间部分，称为“Topics module”，提供了在主要新闻上通过人工专家为读者群精心挑选的的6篇文章。底部，称为“个性化模块(Personalized module)”，提供了许多文章和广告，它们对于用户是个性化的。在个性化模块中的用户，可以随着他们的滚动看尽可能多的文章。典型的读者基本上会浏览20篇文章。该paper描述了个性化文章提供的最优化。

会执行5个过程来为数百万用户进行个性化选择文章。

• Identify：通过用户之前的历史行为计算获取user features
• Matching：使用user features抽取匹配上的文章
• Ranking: 以特定优先级对文章列表重排序
• De-duplication：去重，移除包含相似信息的文章
• Advertising: 如果有必要，插入广告

从用户发起请求到展示文章，这些过程必须在数百ms内完成，因为文章是经常变化的。事实上，在我们服务中的所有文章，超过24小时就失去了新鲜度，每天会发表上万的新文章，同样的，相同数目的老文章会因为超期被移除。因而，每个过程都会采用较轻计算开销的方法，它会使用预计算好的文章的分布式表示（第3节描述）和用户表示（第4节）。

我们使用一个用户的分布式向量和候选文章向量间的内积，来匹配相关性和选择满意的候选。我们通过考虑额外因子(比如：PV的期望数目，每篇文章的新鲜度，以及匹配的相关度)来决定排序的优先顺序。我们会以贪婪的方式基于分布式表示的cosine相似度去复相似文章。当带有更高优先级的文章的cosine相似度的最大值，超出一定阀值时，我们会跳过该文章。在真实新闻分发服务中这是一个重要的过程，因为相似文章在排序时具有相似的分数。如果相似文章的展示相互挨着，用户满意度会下降，因为在展示时缺少多样性。广告也很重要，但许多研究表明广告与用户满意度间的关系，这里我们省略这一块的讨论。

3.文章表示

第1节介绍了一种使用words作为一篇文章的features的方法，它在特定的关于抽取和去重的cases中不一定能工作良好。这一节会描述一种方法来将文章表示成分布式表示。我们提出了之前的一种方法[12]。

3.1 生成方法

我们的方法会基于一个denoising autoencoder，并使用弱监督的方法来生成分布式表示向量。常见的denosing autoencoder可以公式化：

\[\hat{x} \sim q(\hat{x} | x) \\ h = f(W \hat{x} + b) \\ y = f(w'h+b') \\ \theta = argmin_{W,W',b,b'} \sum_{x \in X} L_R(y,x)\]

其中\(x \in X\)是原始input vector，\(q(\cdot \mid \cdot)\)是加噪声混淆分布（corrupting distribution）。stochastically corrupted vector, \(\hat{x}\)，从\(q(\cdot \mid x)\)中获取。隐表示，h，从\(\hat{x}\)映射穿过该网络，它包含了一个激活函数，\(f(\cdot)\)，参数矩阵W，参数向量b。在相同的方式下，reconstructed vector，y, 也从h映射，带有参数\(W'\)和\(b'\)。使用一个loss函数，\(L_R(\cdot, \cdot)\)，我们学习这些参数来最小化y和x的reconstruction errors。

h通常被用于一个对应于x的向量表示。然而，h只持有x的信息。我们希望解释，如果\(x_0\)与\(x_1\)更相似时，两个表示向量的内积 \(h_0^T h_1\)更大。为了达到该目的，我们使用了一个三元组，\((x_0, x_1, x_2) \in X^3\)，作为训练的输入，并修改了目标函数，来维持他们的类目相似性：

\[\hat{x}_n \sim q(\hat{x}_n | x_n) \\ h_n = f(W \hat{x}_n + b) - f(b) \\ y_n = f(W' h_n + b') \\ L_T(h_0, h_1, h_2) = log(1 + exp(h_0^T h_2 - h_0 ^T h_1)) \\ \theta = argmin_{W, W', b, b'} \sum_{(x_0,x_1,x_2) \in T} \sum_{n=0}^2 L_R(y_n, x_n) + \alpha L_T(h_0, h_1, h_2)\]

其中，\(T \subset X^3\)， 以至于\(x_0\)和\(x_1\)具有相同或相似的类目，\(x_0\)和\(x_2\)具有不同的类目。在等式(1)中的h满足该属性，\(x=0 \rightarrow h = 0\)。这意味着，这是一篇与其它文章都不相似的文章。该概念，\(L_T(\cdot, \cdot, \cdot)\)是一个关于文章相似度的罚项函数，它对应于类别相似度（categorical similarity），其中\(\alpha\)是一个用于权衡的超参数。图2提供了该方法的一个总览。

图2: 文章三元组有encoder

我们使用elementwise sigmoid 函数，\(\sigma(x)_i = \frac{1}{1+exp(-x_i)}\)作为\(f(\cdot)\)，elementwsie cross entropy为\(L_R(\cdot, \cdot)\)，masking noise为\(q(\cdot \mid \cdot)\)。我们训练该模型，\(\theta = \lbrace W, W', b, b' \rbrace\)，通过使用mini-batch SGD进行最优化。

我们在应用阶段（application phase）通过使用常数衰减来构建\(\hat{x}\)，在训练阶段（training phase）则使用stochastic corruption作为替代：

\[\hat{x} = (1-p) x \\ h = f(W \hat(x) + b) - f(b)\]

其中，p是训练阶段的corruption rate。因而，h是应用时唯一确定的。乘以(1-p)对于将输入分布均衡到在middle layer中的每个神经元有影响，在masking noise和没有该noise间进行学习(待)。

我们使用在上述三个应用中生成的h作为文章的表示：

• (i) 可作为user-state函数的输入
• (ii) 可以衡量user和article间匹配的相关度
• (iii) 衡量在去重时文章间的相似度

4.用户表示

本节描述了通过用户浏览历史进行计算用户偏好的多种方法。首先，我们对问题进行公式化，并生成一个简单的基于word的baseline方法。接着描述使用文章的分布式表示的一些方法。

4.1 概念

假设：A是关于文章的所有集合。元素\(a \in A\)的表示依赖于该京城。在4.2节中，a是一个描述的word-based方法的稀疏向量，向量中的每个元素对应于词汇表中的每个词。然而，在4.3节和4.4节中，a是一个关于文章的分布式向量表示。

浏览（Browse）意味着用户访问一篇文章的URL。假设\(\lbrace a_t^u \in A \rbrace_{t=1,...,T_u}\)是用户\(u \in U\)的浏览历史。

会话（Session）意味着用户访问推荐服务并在推荐列表中点击某篇文章。

当用户u点击在我们的推荐服务中的一篇文章时（发生一次会话），他/她会立即访问被点文章的URL（发生一次浏览）。这样，对于浏览\(a_t^u\)和\(a_{t+1}^u\)之间，从不会超过一个session；因此，该session被称为\(s_t^u\)。然而，用户u也可以不经过我们的服务而访问一篇文章的URL，例如：通过一次Web search。因此，\(s_t^u\)并不总是存在。

由于一个session会对应提供给u的列表，我们通过一个文章列表\(\lbrace s_{t,p}^u \in A\rbrace_{p \in P}\)来表示一个session： \(s_t^u\)。\(p \subset N\)是推荐列表位置的集合，它实际上对应于在该session中屏幕上的展示位置。假设：\(P_{+} \subseteq P\)是点击位置，而\(P_{-} = P \backslash P_{+}\)是非点击位置。尽管P, \(P_{+}\), \(P_{-}\)取决于u和t, 我们会忽略这些下标以简化概念。图3展示了这些概念间的关系。

图3: 浏览历史和session

假设\(u_t\)是user state，它取决于\(a_1^u, ..., a_t^u\)等等，\(u_t\)表示在浏览\(a_t^u\)之后u的即时偏好。假设：\(R(u_t, a)\)是user state \(u_t\)与文章 a间的相关度，它表示了用户u在时间t上对于文章a的兴趣强度。我们的目标是，构建user-state function：\(F(\cdot, ..., \cdot)\)以及相关度函数：\(R(\cdot, \cdot)\)，它们需满足下面属性：

\(u_t = F(a_1^u, ..., a_t^u) \\ \forall_{s_t^u} \forall_{p_{+} \in P_{+}} \forall_{p_{-} \in P_{-}} R(u_t, s_{t,p_{+}}Yu) > R(u_t, s_{t,p_{-}^u})\) …(2)

我们考虑下：请求量很大的真实新闻分发系统的受限响应时间，\(R(\cdot, \cdot)\)必须是一个简单函数，并能快速计算。对于所有用户\(\lbrace u_t \mid u \in U\rbrace\)，以及所有文章\(\brace a \in A \rbrace\)，由于候选文章会很频繁更新，对相关得分进行预计算是不可能的。因此，有必要在很短的时间内计算它（从访问我们的服务页面到推荐列表到被展示）。然而，我们具有足够多的时间来计算user state function：\(F(\cdot, ..., \cdot)\)(从浏览一些文章页面到下一次session发生)。

我们的受限相关函数(restrict relevance function)：\(R(\cdot, \cdot)\)，表示一个简单的内积关系，\(R(u_t, a) = u_t^T a\)，出于这些原因，只有对user state function: \(F(\cdot,...,\cdot)\)来最小化目标函数：

\[\sum_{s_t^u} \sum_{p_{+} \in P_{+}, p_{-} \in P_{-}} - \frac{log( \sigma( R(u_t, s_{t,p_{+}}^u) - R(u_t, s_{t,p_{-}^u}))} { |P_{+}| |P_{-}|}\]

…(3)

其中\(\sigma(\cdot)\)是logistic sigmoid function。等式4.1是等式(2)的一个宽松版本。实际上，在点击率上存在一个bias，具体取决于文章的展示位置，我们使用以下包含bias项\(B(\cdot,\cdot)\)的目标函数，来纠正这种影响。尽管\(B(\cdot, \cdot)\)是一个通过学习决定的参数，它的描述在下面会被忽略，因为它是该模型的一个公共项。

\[\sum_{s_t^u} \sum_{p_{+} \in P_{+}, p_{-} \in P_{-}} - \frac{log( \sigma( R(u_t, s_{t,p_{+}}^u) - R(u_t, s_{t,p_{-}}^u) + B(p_{+}, p_{-})))} { |P_{+}| |P_{-}| }\]

4.2 Word-based模型

我们引入第1节所述的word-based模型作为baseline。

回顾下baseline实现的三个steps。

• 一篇文章通过它的文本中的词集合进行表示
• 一个用户通过他/她浏览过的文章所包含的词集合表示
• 用户与文章间的相关度通过关于在两者间的词共现数的一个线性函数表示

如果文件表示为a，用户函数为F，V是词汇表，定义如下：

\[a, u_t \in \lbrace 0, 1 \rbrace ^ V \\ (a)_v = \\ (u_t)_v = (F(a_1^u, ..., a_t^u))_v = a_v max_{1 \leq t' \leq t} (a_{t'}^u)_v\]

…(4)

其中\((x)_v\)是x中的第v个元素。接着，相关函数变为一个关于参数\(\lbrace a_v \rbrace\)简单线性模型：

\[R(u_t, a) = u_t^T a \\ = \sum_{v \in V} (u_t)_v (a)_v \\ = \sum_{v \in V} a_v 1_{v \in u_t \cap a}\]

该模型有两个缺点，略。

4.3 Decaying Model

我们引入了一个简单模型来解决上述缺点。模型的两点改变是：

• 它会使用由第3节构建的分布式表示作为表示向量，而非纯BOW表示。
• 它会使用根据浏览历史的加权平均，而非最大值。更特别的，我们会增加最近浏览在权重，减小前些天浏览的权重。

总之，\(u_t\)可以表示为：

\[u_t = \alpha \bigodot \frac{1}{\sum_{1 \leq t' \leq t}} \beta^{t-t'} \sum_{1 \leq t' \leq t} \beta^{t-t'} a_{t'}^u\]

其中，\(\alpha\)是一个参数向量，它与\(a_t^u\)具有相同维度，\(\bigodot\)是两个向量的elementwise乘法，其中\(0 \leq \beta \leq 1\)是一个标量，它是一个用于表示时间衰减的超参数。如果\(\beta\)是1, 就是简单的平均，无需考虑浏览次序。训练参数只有\(\alpha\)，它与baseline模型相似。

4.4 Recurrent Models

4.4.1 simple Recurrent Unit.

尽管decaying model要比word-based model要好，它有局限性，与频次、以及受指数衰减限制的遗忘影响成线性关系。

更常见的，\(u_t\)由前一state\(u_{t-1}\)，和前一浏览\(a_t^u\)决定：

\[u_t = f(a_t^u, u_{t-1})\]

因而，我们会尝试使用一个RNN来学习该函数。一个简单的RNN可以公式化为：

\[u_t = \phi ( W^{in} a_t^u + W^{out} u_{t-1} + b)\]

其中\(\phi(\cdot)\)是激活函数；因而，我们后续使用双曲正切函数：\(tanh(\cdot)\)。训练参数是个方阵\(W^{in}, W^{out}\)，bias vector为b，初始state vector \(u_0\)，其中\(u_0\)是公共初始值，并不依赖于u。

我们通过end-to-end minibatch SGD的方式对等式 4.1的目标函数进行学习。然而，当输入序列过长时，简单的RNN很难学习，因为会存在梯度消失和爆炸问题。额外的结构被绑定到hidden layer上，以便减轻该问题。

下一部分会介绍使用这些结构的两个模型。

4.4.2 LSTM Unit

LSTM是一种解决梯度消失和爆炸问题的结构。我们可以将LSTM模型公式化为：

\[gi_t = \sigma(W_{gi}^{in} a_t^u + W_{gi}^{out} u_{t-1} + W_{gi}^{mem} h_{t-1}^u + b_{gi}) \\ gf_t = \sigma(W_{gf}^{in} a_t^u + W_{gf}^{out} u_{t-1} + W_{gf}^{mem} h_{t-1}^u + b_{gf}) \\ enc_t = \phi(W_{enc}^{in} a_t^u + W_{enc}^{out} u_{t-1} + b_{enc} \\ h_t^u = gi_t \bigodot enc_t + gf_t \bigodot h_{t-1} ^u \\ go_t = \sigma(W_{go}^{in} a_t^u + W_{go}^{out} u_{t-1} + W_{go}^{mem} h_t^u + b_{go}) \\ dec_t = \phi(W_{dec}^{mem} h_t^u + b_{dec}) \\ u_t = go_t \bigodot dec_t\]

其中，\(\sigma(\cdot)\)是elementwise logistic sigmoid函数，\(h_t^u\)是一个hidden memory state。图4是LSTM模型的一个网络结构。

图4

center flows是从输入（浏览过的文章）到输出(user state)的最重要的flows。输入，\(a_t^u\)，被编码中从文章向量空间到hidden空间（等式5），会合并之前的hidden state(等式6)，并编码成文章向量空间（等式7,等式8）作为user state。

另外，该unit具有三个gates，称为input gate(\(gi_t\))，forget gate（\(gf_t\)），output gate（go_t）。我们假设每个gate都会各尽其职。input gate会过滤掉不必要的输入来构建一个user state，比如：由突然兴趣造成的。forget gate表示用户在兴趣上的下降。它可以表示比指数衰减（exponential decay）更复杂的forget影响。output gate会过滤掉在下一个session中不关注的成分。

训练参数是权重矩阵\(W\)，bias向量b，初始化state vectors \(u_0\)和\(h_0^u\)，其中\(u_0\)和\(h_0^u\)是不依赖于u的公共初始化值。

4.4.3 Gated Recurrent Unit(GRU)

是另一种避免梯度消失和爆炸的方法。公式如下：

\[gz_t = \sigma(W_{gz}^{in} a_t^u + W_{gz}^{mem} h^{t-1} + b_{gz}) \\ gr_t = \sigma(W_{gr}^{in} a_t^u + W_{gr}^{mem} h^{t-1} + b_{gr}) \\ enc_t = \phi(W_{enc}^{in} a_t^u + W_{enc}^{out}(gr_t \bigodot h^{t-1}) + b_{enc}) \\ h_t^u = gz_t \bigodot enc_t + (1-gz_t) \bigodot h_{t-1}^u \\ dec_t = \phi(W_{dec}^{mem} h_t^u + b_{dec}) \\ u_t = dec_t\]

更准确的，该模型使用一个GRU layer和一个fully connected layer来构建，因为等式(1) 在原始GRU配置中不包含。图5展示了GRU-based模型的结构。

图5

除了省略了一些键头，该结构与LSTM-based模型相似。然而，等式(6)和等式(9)有一个重要的不同点。\(gz_t\)gate会扮演在LSTM-based模型的两个gates的角色：\(gi_t\)和\(gf_t\)。

\(sup_{u} \| h_t^u \|_{infty} =\) …(12)

等式11对于非常长的输入序列具有一个较大值；等式(12)从不会超过该常数。因此，我们认为GRU-based模型比LSTM-based模型能更好地解决梯度爆炸问题。

LSTm-based模型在训练时偶尔会失败，归因于我没在实验中没有使用梯度裁减（gradient clipping）从而造成梯度爆炸。然而，GRU-based模型不需要任何前置处理，不会造成梯度爆炸。

5.实验

5.1 训练数据集

首先，抽样了接近1200w的用户，它们在2016年1月到9月间，在Yahoo!Japan主页上有点击文章的动作。我们会为每个用户抽取一个超过两周时间的日志，随机包含至少一次点击。该抽取方法被用于减轻在特定时间内流行文章的影响。

最后产生的结果，在训练数据中，会有16600w个session，10亿次浏览，200w唯一的文章。我们也创建了相同时期内另一个数据集，并使用它作为验证集来最优化参数。

5.2 测试集

抽样了50w sessions，在2016年10月，用户点击文章超过位置20. 我们为每个session抽取前两周的浏览日志。我们使用位置1到20的文章数据来进行评估，忽略是否实际在屏幕中显示过。这基于我们timeline-based UI的观察。用户会从顶划到底，当点击一篇文章时趋向于离开我们的服务。这就是说，如果我们只使用实际展示的数据进行evaluation，安排实际展示按逆序的方式，进行不成比例地评估也佳。

5.3 离线Metrics

AUC、MRR、nDCG

5.5 结果

表

参考

http://sci-hub.tw/10.1145/3097983.3098108

在google提出的deep-wide模型之后，华为实验室的人提出了一个DeepFM模型：

1.介绍

现有的模型基本都是偏向于这么几类：低阶特征交叉、高阶特征交叉、或者依赖特征工程。DeepFM可以以一种端到端（end-to-end）的方式来学习特征交叉，无需在原始特征之上做特征工程。deepfm可以归结为：

• 提出了一种新的NN模型：DeepFM（图1），它集成了FM和DNN的架构。它即可以像FM那样建模低阶特征交叉，也可以像DNN那样建模高阶特征交叉。不同于Wide&Deep模型，DeepFM可以进行端到端训练，无需任何特征工程。
• DeepFM的wide part和deep part，与Wide&Deep模型不同的是，它可以很有效地进行训练，共享相同的输入以及embedding vector。在Wide&Deep方法中，输入向量（input vector）的size可能很大，因为需要为wide部分人工设计pairwise型特征交叉，复杂度增长很快。
• DeepFM在benchmark数据上和商业数据上都进行了评测，对现有模型可以有效进行提升。

2.方法

假设训练数据包含了n个样本(x, y)，其中x是一个m-fields的数据记录，通常涉及到一个(user,item)的pair，其中\(y \in \{ 0, 1\}\)表示用户点击行为的label。x也包含了类别型字段（比如：性别，位置）和连续型字段（比如：年龄）。每个类别型字段被表示成一个one-hot编码的向量，每个连续型字段用它原有的值进行表示，或者进行离散化one-hot编码表示。这样，每个实例可以被转换成(x,y)，其中 \(x = [x_{field_1}, x_{field_2}, .., x_{field_j}, ..., x_{field_m}]\)是一个多维向量，其中\(x_{field_j}\)是向量中的第j个字段。通常，x是高维且十分稀疏的。CTR预测的任务就是构建一个预测模型\(\hat{y} = CTR_{model}(x)\)来估计用户点击的概率。

2.1 DeepFM

图1

我们的目标是同时学到低阶和高阶特征交叉。为此，我们提出了基于NN的FM（DeepFM）。如图1所示，DeepFM包含了两个组件：FM组件和Deep组件，它们共享相同的输入。对于feature i，使用\(w_i\)作为权重来衡量1阶的重要性，隐向量\(V_i\)用于衡量feature i与其它特征交叉的影响。所有的参数，包括\(w_i, V_i\)，以及网络参数\(（W^{(l)}, b^{(l)}）\)会进行joint training：

\[\hat{y} = sigmoid(y_{FM} + y_{DNN})\]

…(1)

其中\(\hat{y} \in (0, 1)\)是预测的CTR，\(y_{FM}\)是FM组件的输出，\(y_{DNN}\)是deep组件的输出。

2.1.1 FM组件

图2：FM组件架构

FM组件是一个因子分解机，它可以学到推荐系统的交叉特征。除了特征间的线性交叉（1阶）外，FM还可以将pairwise（2阶）特征交叉建模成各自特征隐向量的内积。

当数据集是稀疏时，对比起过去的方法，它可以更有效地捕获2阶特征交叉。在之前的方法中，特征i和特征j的交叉的参数只有当两者都出现在同一数据记录时才能被训练。而在FM中，它可以通过隐向量\(V_i\)和\(V_j\)的内积来衡量。由于这种灵活的设计，当只有i（或j）出来在数据记录中，FM也可以训练隐向量Vi(Vj)。因而，对于从未出来或很少出现在训练数据中的特征交叉，可以通过FM很好地学到。

如图2所示，FM的输出是一个求和单元（Addition unit），以及多个内积单元：

\[y_{FM} = \langle w,x \rangle + \sum_{j_1=1}^{d} \sum_{j_2=j_1+1}^{d} \langle V_i,V_j \rangle x_{j_1} \cdot x_{j_2}\]

…(2)

其中 \(w \in R^d\), \(V_i \in R^k\)(k给定)。求和单元反映了1阶特征的重要性，而内积单元则表示二阶特征交叉的影响。

2.1.2 Deep组件

图3：deep组件的架构

Deep组件是一个前馈神经网络，它用于学习高阶特征交叉。如图3所示，一个数据记录（即一个向量）被feed给NN。对比起图像和音频的神经网络输入数据（它们几乎都是continuous和dense的），CTR预测所需的输入相当不同（需要一个新的网络结构设计）。尤其是，ctr预测的原始特征输入向量通常是高度稀疏的，相当高维，类别型和连续型混杂，以fields进行分组（例如：性别、地域、年龄）。这暗示了：在进一步feed给第一个隐层(the first hidden layer)之前，需要一个embedding layer来将输入向量压缩成一个低维的、dense的实数值向量，否则该网络将很难训练。

图4:embedding layer的结构

图4高亮出从input-layer到embedding layer的子网络结构。我们指出了该网络结果的两个有趣的特征：

• 1) 当不同的field输入向量（input field vectors）的长度可以不同，他们的embeddings则具有相同的size(k)
• 2) 在FM中的隐特征向量(V)现在作为网络的权重(weight)使用，它可以将input field vectors压缩到embedding vectors中。在[Zhang et al.2016]中，V由FM预训练得到，用于初始化。在DeepFM中，并不会这样做，FM模型是整个学习架构的一部分。这样，我们不需要由FM进行预训练，而是直接以end-to-end的方式进行joint train。

embedding layer的output定义如下：

\[a^{(0)} = [e_1, e_2, ..., e_m]\]

…(3)

其中\(e_i\)是第i个field的embedding，m是field总数。接着，\(a^{(0)}\)被feed给DNN，forward处理如下：

\[a^{(l+1)} = \sigma(W^{(l)} a^{(l)} + b^{(l)})\]

…(4)

其中l是layer的depth，\(\sigma\)是一个activation function。\(a^{(l)}, W^{(l)}, b^{(l)}\)分别是第l层的output，模型weight，bias。之后，会生成一个dense型实数值特征向量（dense real-value feature vector），最后它会被feed给CTR预测用的sigmoid function：

\[y_{DNN} = \sigma (w^{|H|+1} \cdot a^H + b^{|H|+1})\]

其中$|H|$是hidden layer的数目。

需要指出的是，FM组件和Deep组件会共享相同的feature embedding，这会带来两个好处：

• 1) 可以学到从原始特征的低阶交叉和高阶交叉
• 2) 没必要像Wide&Deep模型那样对输入进行专门的特征工程

2.2 与其它NN关系

图5

这部分比较了CTR预测中，DeepFM与其它存在的deep模型。

FNN

如图5（左）所示，FNN是一个由FM初始化的前馈神经网络。FM预训练策略会产生两个限制：1) embedding参数完全受FM的影响 2) 由于预训练阶段引入的开销，效率会降低。另外，FNN只能捕获高阶特征交叉。

PNN

目标是捕获高阶特征交叉，PNN在embedding layer和第一个hidden layer间引入了一个product layer。根据不同类型的product操作，有三种变种：IPNN，OPNN，PNN，其中IPNN是基于向量内积，OPNN基于外积，PNN同时基于内积和外积。

为了让计算更有效率，作者提出了内积和外积的近似计算：1) 内积通过消除一些神经元来近似计算 2) 外积通过将m个k维feature vector压缩到一个k维vector来近似。然而，我们发现外积比内积的可靠性更差，因为外积的近似计算会丢失很多信息，让结果不稳定。尽管内积更可靠，它仍具有高的计算复杂度，因为product layer的输出连接到第一个hidden layer上的所有神经元（neuron）上。不同于PNN，DeepFM的product layer的output只连接到最后的output layer上（一个neuron）。与FNN类似，所有的PNN都会忽视低阶特征交叉。

Wide & Deep

Wide & Deep由Google提出，用于同时建模低阶和高阶特征交叉。它需要专家对wide部分的输入端进行特征工程（例如：用户安装的app和app推荐曝光的app间的交叉），相反地，DeepFM不需要专家知识，直接从输入的原始特征进行学习。

该模型的一个简单扩展是，通过FM替代LR。该扩展与DeepFM相似，但DeepFM会在FM组件和Deep组件间共享feature embedding。这种共享策略会影响低阶和高阶特征交叉的特征表示，可以更准备地进行建模。

总结

3.试验

数据集：

1) Criteo Dataset: 4500w用户点击记录。13个连续特征，26个类别型特征。 2) ) Company∗（华为） Dataset：收集了该公司App Store的游戏中心连续7天的用户点击记录数据进行训练，下一天数据进行预测。整体数据集有10亿记录。在该数据集中，有app特征（id，类别等），user特征（下载过的app等），context特征（操作时间）

Evaluation Metrics

AUC （(Area Under ROC)）和 LogLoss（cross entropy）

具体见paper，不详述。

参考

https://arxiv.org/pdf/1703.04247.pdf

yahoo在2010年提出的《Learning to Blend Rankings: a Monotonic Transformation to Blend Rankings from Heterogeneous Domains》。

介绍

给定一个关于items的集合 \(X=\lbrace x_1, \cdots, x_n \rbrace\)，X的一个ranking是一个关于\([n]=\lbrace 1, \cdots, n \rbrace\)的排列。在l2r的领域中有大量研究[1,2,5,8,12]。然而，在许多应用中，我们需要将多个异构领域(heterogeneous domains)的关于items的rankings集成到一个关于在所有sets中所有items的单个ranking中，比如多种垂直搜索引擎(vertical search engine)：视频搜索、图片搜索、博客搜索等。例如，一个items集合可以是来自Web的文档集合，而另一个可以是来自一个垂直搜索引擎（比如：Blog或News搜索）的文档集合。将来自多个异构领域的rank lists进行合并是一个非平凡问题（non-trivial topic），因为：

• 1) 这些异构集合可以共享一些文档，但很可能也有许多非公共文档
• 2) 异构领域通常具有不同的features和feature-to-relevance相关性(correlations)

以问答网站（Yahoo! Answer）为例，尽管对于普通网站的text matching和click features可以被用于该domain的ranking中，使用这些独一无二的页面结构和用户反馈开发的features，比如：在Yahoo! Ansers中的点赞率(thumbs up ratings)和反馈总数(feedbacks)，在自有domain中的ranking上有大的用处。但Yahoo! Answers和普通网页文档共享的features在两个domains中的相关度上可能有非常不同的相关性。因此，需要使用一种跨domain的统一ranking function，以便在每个私有domain内更好地对文档进行排序，因此需要新的技术：将来自异构domains的文档融合(blend)到单个ranking list中。

我们想强调的是，该问题通常与rank aggregation问题[4,9]是相当不同的，RA问题需要在items的异构集合(homogeneous set)上将不同的rankings进行merge。

我们将来自多个异构域的rank lists进行集成(integration)定义为一个blending问题，将以如下方式将learning to blend rankings的问题进行公式化：

• a) 我们具有异构类型的items。每种类型的items在相应domain内都有一个rank order
• b) blending的训练数据的形式为：items sets和它相关的rankings的pairs，pair中的第一个属于items的某一类型(type)，第二者属于items的另一类型(type)。

最优组合排序(optimal combined rankings)是learning to blend的ground truth，可以以如下两个steps生成：

• 1) 为这些rankings中的每个item分配相关度标签，比如：Perfect, Excellent, Good, Fair, Bad (简写为：P/E/G/F/B)
• 2) 根据这些标签将ranking lists进行merge sort

以这种方式进行Blending可以最大化Discounted Cumulative Gain(DCG)，并且可以为这些rankings保留原排序（ordering）。

给定训练数据——组合排序（combined ranking）和在私有domain中的rankings，我们希望学到一种单调递增的转换（在私有domain上的ranking score），使得当使用关于(item sets, 相关rankings)的一个新pair时，我们可以使用转换后的ranking scores来生成一个combined ranking。

在本paper中，我们将该问题公式化成一个二次规划问题(quadratic programming problem)，并学习一个线性单调转换，使得在每个domain中的排序（rank order）保留，以及转换后的分值是可比的。

2.问题公式化

为了设计一个blending转换，我们假设：训练数据是一个包含了pairs\(\lbrace q_i \rbrace_{i=1}^Q\)的集合。在该工作中，我们主要关注以下场景：每个私有的ranking的order会在blending后保留。具有该constraint的Blending非常像归并排序（merge sorting）。

出于简洁性，假设我们只有两个rankings。考虑\(q_i\)，我们有：

\[R_1^i = \lbrace \langle d_{11}^i, r_{11}^i \rangle, \langle d_{12}^i, r_{12}^i \rangle, \cdots, \langle d_{1M}^i, r_{1M}^i \rangle \rbrace \\ R_2^i = \lbrace \langle d_{21}^i, r_{21}^i \rangle, \langle d_{22}^i, r_{22}^i \rangle, \cdots, \langle d_{2N}^i, r_{2N}^i \rangle \rbrace\]

其中，M和N分别是第一个set和第二个set的items数目，\(d_{1m}^i\)和\(d_{2n}^i\)是items。

在每个domain中的rank order为\(R_1^i\)和\(R_2^i\)，关于rankings的格式我们考虑两种situations：

• 1) 对于一个items集合，只有items的ranking
• 2) 对于一个items集合，每个item都有一个score，items的ranking通过items的scores引出，例如：ranking是通过对items的scores进行sorting获得的

给定一个关于item sets和它相关rankings的pair，我们可以区分三种cases：

• 两个sets都是situation 1)。我们需要学习一个transformation：它可以将一个set中的ranks与另一set的ranks相关联
• 一个set是situation 1)，另一个set是situation 2)。我们需要学习一个transformation：它可以将一个set中的ranks与另一个set中的scores相关联
• 两个sets都是situation 2)。我们需要学习一个transformation：它可以将两个sets中的scores进行校正(calibrate)

对于在situation 1)中的一个ranking \(r_{1m}^i\)或\(r_{2n}^i\)是它的rank的负数，而在situation 2)中是相应的score。因此，三种cases可以使用一个公式进行表述。

对于\(R_1^i\)和 \(R_2^i\)，我们有：

\[r_{11}^i \geq r_{12}^i \geq \cdots \geq r_{1M}^i \\ r_{21}^i \geq r_{22}^i \geq \cdots \geq r_{2N}^i\]

对应于\(R_1^i\)和\(R_2^i\)，我们也具有共M+N items的combined ranking（出于简洁，这里假设两个list间没有重叠items）：

\[R^i = \lbrace \cdots, d_{1m}^i, \cdots, d_{2n}^i, \cdots \rbrace\]

根据需要，来自两个list的items的原list顺序会被保留。

相应的，我们定义了\(\lbrace (m,n) 1 \leq m \leq M, m \leq n \leq N \rbrace\)两个子集：\(S_i^+\)对应于\(d_{1m}^i\)的rank高于\(d_{2n}^i\)的cases，\(S_i^-\)对应于\(d_{1m}^i\)的rank低于\(d_{2n}^i\)的cases，并定义了：

\[S^+= \bigcup\limits_{q_i \in Q} S_i^+, S^- = \bigcup_{q_i \in Q} S_i^-\]

核心问题是，如何从训练数据中自动化学习一个blending transformation。我们提出在\(R_2^i\)中对\(r_{2n}^i \ (n=1, \cdots, N)\)使用一个单调递增函数\(f(\cdot)\)，使得该blending可以基于\(r_{1m}^i\)和\(f(r_{2n}^i)\)。通过这样做，来自每个单独的ranking list的顺序(order)可以被自动保留。\(f(\cdot)\)的学习会最大程度地遵循editorial blending ranking。（假设我们具有X个rankings，\(X \geq 2\)。可以选择其中之一做为参照点，其余\(X-1\)个transformations会被学到）

3.算法

3.1 我们的算法

我们将transformation learning问题公式化成一个二次规划问题。

\[min \sum\limits_{k=1}^K \zeta_k^2\]

服从：

\[r_{1m}^i \geq f(r_{2n}^i) - \zeta_k \ \ \ (m,n) \in S_i^+, \\ f(r_{2n}^i) \geq r_{1m}^i - \zeta_k \ \ \ (m,n) \in S_i^-, \\ \zeta_k \geq 0\]

其中：

• K是来自\(S_i^+\)和\(S_i^-, i=1, \cdots, Q\) 两者的items的总数目。

如果假设\(f(\cdot)\)是线性的，并且形式为：\(f(x)=\alpha x + \beta\)，上述问题将变为：

\[\underset {\alpha, \beta, \zeta_k}{min} \sum\limits_{k=1}^K \zeta_k^2 + \lambda_1 \alpha^2 + \lambda_2 \beta^2\]

…(1)

满足：

\[r_{1m}^i \geq \alpha r_{2n}^i + \beta - \zeta_k \ \ \ (m,n) \in S_i^+, \\ \alpha r_{2n}^i + \beta \geq r_{1m}^i - \zeta_k \ \ \ (m,n) \in S_i^-, \\ \zeta_k \geq 0, \alpha \geq 0\]

通过求解以上QP问题，我们可以获取该线性变换（linear transformation）的一个\((\alpha, \beta)\) （相同的\((\alpha, \beta)\)可以被应用到所有queries上）

如果query的分类信息足够，我们也可以为每个query length、或者每种类型的queries学习一个\((\alpha, \beta)\)。在等式(1)中的constraints会给定相同的权重，它可以进行调整来为更重要的constraints提供更高的weights。其它非线性单调变换在将来的工作中会进行探索。

等式(1)演示了两个domains的思想。该算法可以轻易地扩展到blend超过两个的rankings上。给定来自X domains的ranking lists，选择其中一个作为参照点，其余X-1的转换\((\alpha_1, \beta_1), \cdots, (\alpha_{X-1}, \beta_{X-1})\)。该QP问题的constraints会涉及到来自任意两个domains的item sets的所有pairs，例如：该问题将变为：

\[\underset{\alpha_v, \beta_v, \zeta_k}{min} \sum_{k=1}^{K} \zeta_k^2 + \lambda_{1,1} \alpha_1^2 + \lambda_{1,2} \beta_1^2 + \cdots + \lambda_{X-1,1} \alpha_{X-1}^2 + \lambda_{X-1,2} \beta_{X-1}^2\]

符合：

\[\alpha_u r_{um}^i + \beta_u \geq \alpha_v r_{vn}^i + \beta_v - \zeta_k \ \ \ (m,n) \in \underset{u, v_i}{S^+}, \\ \alpha_v r_{vn}^i + \beta_v \geq \alpha_u r_{um}^i + \beta_u - \zeta_k \ \ \ (m,n) \in \underset{u, v_i}{S^-}, \\ r_{1m}^i \geq \alpha_u r_{um}^i + \beta_u - \zeta_k \ \ \ (m,n) \in \underset{1,u_i}{S^+}, \\ \alpha_u r_{um}^i + \beta_u \geq r_{1m}^i - \zeta_k \ \ \ (m,n) \in \underset{1, u_i}{S^-}, \\ \zeta_k \geq 0, \alpha_v \geq 0, u, v = 1, \cdots, X-1\]

4.实验

4.1 数据

我们对提出的算法进行了评估，所使用数据为：使用web搜索结果与Yahoo！Answers domain产生的垂直搜索结果进行blending。1300个queries从一个商业搜索引擎的query logs中抽样得到，800个queries被用于训练，500个用于validation。对于每个query，我们具有两个集合的文档：普通web文档、Yahoo! Answers文档。每个文档会被5种label之一进行标记(label)：Perfect、Excellent、Good、Fair和Bad，以相关度的递减序排列。我们在每个domain上具有预生成的ranking functions，并于rank score \(r_{1m}^i\)或\(r_{2n}^i\)可以通过在每个domain上对相应domain的文档使用ranking function生成。给定\(R_1^i\)和\(R_2^i\)，QP问题的constrains可以通过应用merge-sort到两个rank lists上进行构建，并在web文档和Answers文档间保留paired score perference。

4.2 实验

为了评估提出的算法，我们只关注\(f(\cdot)\)是线性变换的简单case，例如：\(f(x)=\alpha x + \beta\)。使用800个queries来学习transformation和500个queries用于validation。

Baseline方法

我们对比的该baseline是Naive blending方法，其中\(r_{1m}^i\)和\(r_{2n}^i\)的scores直接拿来比较进行排序。

评估metrics

我们上报了广泛使用的相度度指标：Discounted Cumulaive Gain(DCG)。对于一个N个文档的ranked list（N被设置成10, 或者实验中的1），我们使用以下的DCG变种：

\[DCG_N = \sum\limits_{i=1}^N \frac{G_i}{log_2(i+1)}\]

其中\(G_i\)表示在position i上分配的label的weights（比如：10表示Perfect match，7表示Excellent match, 3表示Good match等），相关度越高，DCG的值越高。我们使用DCG来表示：在testing queries的集合上的DCG值的平均。

在我们的应用中，目标是将Yahoo! Ansers的文档blend到web rank list中。我们上报了DCG1和DCG10, 如表1中的web rank list和blended list。我们的方法可以观察到有1.18% DCG10和0.9% DCG1增益。两者在统计上都是很大的提升。在我们的应用中，\(\lambda_1, \lambda_2\)的选择不会极大影响我们的实验，我们在实验中使用\(\lambda_1=1, \lambda_2=10\)。该Naive blending方法不会达到任何DCG的提升。这表明，从异构域的rank scores不能直接比较，需要一个blending算法。

也需要计算pair-wise error rate，（例如：item sets的pairs百分比，不能被正确rank）。换句话说，该error rate会衡量在QP问题中有多少constraints不能被满瞳。表2上报了error rate。学到的线性变换给出了一个35%的error rate。因此，我们会研究optimal DCG，螃蟹烧开吃测评发票merge-sort策略获取。

Blending的上界

merge-sort的思想是，两个ranking lists可以被认为是最好的DCG10(它可以通过blending获取)，例如：一个blending算法可以达到的上界。我们的测试数据中，最好的DCG 10是7.06. 因此，还有提升的空间。第5节会讨论将来的研究方法。

5.相关工作

最近几年，ranking问题被多次表示成一个监督机器学习问题。这些l2r方法可以组合不同类型的features来训练ranking functions。ranking的问题可以被看成是从pair-wise的偏好数据中学习一个ranking function。该思想是，最小化在训练数据中的矛盾对的数目。例如，RankSVM会使用SVM来学习ranking function。RankNet则使用神经网络来梯度下降来获取一个ranking function。RankBoost则使用boosting从一个弱ranking functions集合中来构建一个高效的ranking function。。。

受[10]的启发，我们的算法将一个pairwise ranking问题看成是一个二次规划问题。

6.略

参考

• 1.http://yichang-cs.com/yahoo/cikm10_blending.pdf