Pinterest在《Graph Convolutional Neural Networks for Web-Scale Recommender Systems》中提出了PinSage：

介绍

深度学习方法已经在推荐系统应用中非常重要，被用于学习关于图片、文本、单个用户的有用高维embeddings。使用deep models学到的representations可以被用于补全、或者替换传统的推荐算法（比如：CF）。并且这些学到的representations具有高可用性，因为他们可以被用在许多推荐任务中。例如，使用一个deep model学到的item embeddings可以被用于item-item推荐，并且可以推荐有主题的集合（例如：playlists，或者“feed”内容）

最近，在该领域内有较大发展——特别是能够基于在图结构化数据上学习的新deep learning方法的发展，这对于推荐应用来说很基础（例如：可以利用user-to-item交互图，也可以使用社交网络图）。

在这些成就中，最著名的是Graph Convolutional Networks（GCNs）深度学习结构的成功。GCNs背后的核心思想是：学习如何从局部图邻居（local graph neighborhoods）的feature信息中进行迭代式聚合（aggregate）（图1）。这样的一个“卷积（convolution）”操作会从一个node的一跳图邻居的feature信息进行转换和聚合，并且通过将多个这样的convolutions信息进行stacking可以传播到图的远方。不同于纯content-based deep models（例如：RNNs），GCNs会同时利用内容信息和图结构。GCN-based方法已经在无数推荐系统benchmarks上设置了一个新的标准。然而，在benchmark任务上的收益还没有转换到真实生产环境中。

同时将GCN-based node embeddings的training和inference扩展到具有数十亿nodes和数百亿edges的图上是一个巨大的挑战。当在一个大数据环境中，对GCNs进行扩展很难，因为在设计底下的许多核心假设是冲突的。例如，在训练期间，所有已存在的GCN-based推荐系统需要在整个图拉普拉斯算子（full graph Laplacian）上操作，因而是不可行：当底层图（underlying graph）具有数十亿nodes，它们的结构通常是演化的。

当前工作

这里我们提出了一个高度可扩展的GCN框架，我们在Pinterest的生产环境中开发和部署过。我们的框架，是一个random-walk-based GCN 称为“PinSage”，它在30亿nodes和180亿edges的一个大型图（massive graph）上操作——该graph是GCNs的常见应用的10000倍以上大。

PinSage会利用许多关键insights来弹性提升GCNs的可扩展性：

• on-the-fly convolutions：传统的GCN算法通过将feature matrics乘以full graph Laplacian的幂来执行图卷积。相反的，PinSage算法执行很高效，通过对在一个node周围的邻居进行抽样，并且从该抽样后的邻居来动态构建一个计算图。这些动态构建的计算图（图1）指定了如何在一个特定node周围执行一个局部卷积（localized convolution），并且缓和了在训练期间对整个graph操作的需求。
• Producer-consumer minibatch construction：我们开发了一个producer-consumer架构来构建minibatches，它能确保在模型训练期间最大化GPU利用率。一个大内存、CPU-bound producer可以有效抽样node network邻居，并且获取必要。
• 有效的MapReduce inference：给定一个fully-trained GCN模型，我们会设计一个有效的MapReduce pipeline，可以将训练好的模型分散来生成数十亿节点的embeddings，可以最小化重复计算。

图1

除了在可扩展性上的这些基础优点外，我们也会引入新的训练技术和算法创新点。这些创新点会改善由PinSage学到的representations的质量，从而能导致在下游推荐系统任务上获得大的提升：

• 通过random walks来构建convolutions：通过采用节点的所有邻居来执行convolutions（图1）会导致很大的计算图，因此，我们会采用sampling。然而，random sampling是次优的，我们会开发一种新的技术，它使用short random walks来采样计算图（computation graph）。一个额外的好处是：每个node具有一个importance score，我们会在pooling/aggregation step中使用。
• Importance pooling：graph convolutions的一个核心组件是：在graph中的局部邻居的feature信息的aggregation。我们会引入一个方法来对在该aggregation中的node features的importance进行权衡，它基于random-walk相似度measures，在离线评估指标中会有一个46%的效果增益。
• 课程培训（Curriculum training）：我们设计了一个Curriculum training的scheme，其中该算法会在训练期间feed越来越hard的样本，从而产生一个12%的效果增益。

对于在Pinterest中的多个推荐任务，我们已经部署了PinSage，它是一个用户可以对交互的pins进行流行内容发现和管理的应用，其中：pins是在线内容的一个可视化书签。用户会将这些pins组织成boards，它包含了许多相似pins的collections。总之，Pinterest是世界上关于图片的最大user-curated graph（用户组织图），具有20亿唯一的pins，被收集到超过10亿的boards上。

通过大量离线metrics、A/B tests，我们展示了：对比起其它可扩展的deep content-based推荐算法，我们的方法在一个item-item推荐任务上（例如：相关pins推荐）以及一个”homefeed”推荐任务上可以达到SOTA的效果。在离线ranking指标上，我们对比baseline获得了超过40%的提升，在head-to-head人工评估上，我们的推荐要好60%。。

据我们所知，这是最大的deep graph embeddings，为新一代基于graph convolutional结构的推荐系统铺平了道路。

2.相关工作

略

3.方法

在本节中，我们会描述PinSage结构、training、以及MapReduce pipeline的技术细节，可以使用一个训练好的PinSage模型来有效生成embeddings。

我们的方法的关键计算重任是：局部图卷积（localized graph convolutions）。为了为一个node（例如：一个item）生成embedding，我们会应用多个convolutional模块，它们会聚合来自该node的局部图邻居（local graph neighborhood）（图1）的feature信息（例如：可视化features、文本features）。每个module会学习如何从一个小的图邻居（graph neighborhood）来聚合信息，通过将多个这样的模型进行stacking，我们的方法可以获得关于局部网络拓朴的信息。重要的是，这些localizied convolutional modules的参数会跨所有nodes进行共享，使得我们的方法的参数复杂度完全取决于input graph size。

3.1 问题设定

Pinterest是一个内容发现应用，其中：

• 用户会将这些pins组织成boards，
• 用户会将比较相关的pins包成集合

总之，Pinterest graph包含了20亿pins，10亿boards，并且超过180亿的edges（例如：pins的成员和它们相应的boards）。

我们的任务是，生成pins的high-quality embeddings 或者 representations（例如：通过最近邻查询相关的pin推荐，或者在下游的reranking系统中使用）。为了学习这些embeddings，我们会将Pinterest环境建模成一个二部图，它包含了两个不相互交集合I（包含了pins）和C（包含了boards）的结点。注意，我们的方法也是天然泛化的，其中I被看成是一个items集合，C被看成是user-defined contexts和collections。

除了图结构外，我们也会假设：pins/items \(u \in I\)会与real-valued属性相关联，\(x_u \in R^d\)。总之，这些属性可以指定关于一个item的metadata或content信息，另外在Pinterest的case中，我们有：具有丰富文本信息和图片features有关的pins。我们的目标是，利用这些input属性，以及二部图结构来生成高质量embeddings。这些embeddings接着会被用于通过最近邻lookup的推荐系统的候选生成（例如：给定一个pin，发现相关pins）或者在对候选排序时作为features使用。

出于便利性和泛化性，当我们描述PinSage算法时，我们会简单地将完整graph的node set使用 \(V = I \cup C\)来表示，不会显式对pin和board nodes进行显式区别（除非严格必要），会统一使用更通用的术语“node”.

3.2 模型结构

我们会使用localized convolutinal模块来生成nodes的embeddings。我们从input node features开始，接着开始学习nueral networks，它会将通过graph来对features进行transform和aggregate来计算node embeddings（图1）。

前向传播算法

我们会考虑生成一个embedding的任务， 对于一个node u的\(z_u\)，它取决于node的input features和围绕该node的图结构。

算法1

PinSage算法的核心是一个localized convolution操作，其中，我们会学习如何从u的邻居（图1）的信息聚合。该过程在算法1 CONVOLVE中有详解。基本思想是：我们将关于u的邻居通过一个dense neural network进行转换成representations \(z_v \forall v \in N(u)\)，接着在vectors的结果集（第一行）上应用一个aggregator/pooling function（例如：一个element-wise mean或weighted sum，表示为\(\gamma\)）。该aggregation step会提供一个关于u的局部邻居\(N(u)\)的vector representation \(nu\)。我们接着将aggretated neighborhood vector \(n_u\)与u的当前representation \(h_u\)进行拼接，并将contantenated vector \(n_u\)与u的当前representation \(h_u\)进行concatenate在一起，并通过另一个dense neural network layer（第2行）将concatenated vector进行转换。经验上，我们观察到：当使用concatenation operation来替代average operation时会取得极大的效果提升。另外，在第3行中的normalization会使得训练更稳定，它对于normalized embeddings来说执行近似最近邻搜索更高效（第3.5节）。该算法的output是一个关于u的representation，同时包含了它自己以及它的局部图邻居间的信息。

Importance-based neighborhoods

在我们的方案中，一个重要概念是：如何定义节点邻居\(N(u)\)，例如：如何在算法1中选择要convolve的邻居集合。然而，之前的GCN方法会简单检查k-hop的图邻居，在PinSage中，我们定义了importance-based 邻居，其中：一个node u的邻居会被定义成T nodes会对node u施加最可能的影响。具体的，我们会从node u开始模拟random walks，并且计算出由random walk访问到的L1-normalized的节点访问数。u的邻居接着被定义成：对于node u具有最高的normalized visit counts的T个nodes。

该importnace-based邻居定义的优点是两面的。

• 首先，选择一个固定数目的节点来聚合，允许我们控制着在训练期间该算法的memory footprint。
• 第二，当聚合邻居的vector representations时，它会使算法1考虑邻居的importance

特别的，我们会在算法1中实现\(\gamma\)作为一个weighted-mean，它使用根据L1 normalized visit counts定义的weights。我们将该方法称为importance pooling。

Stacking convolutions

每个时间，我们会使用CONVOLVE操作（算法1），我们会从一个node处获得一个新的representation，并且将多个这样的convolutions相互进行stack，以便获得围绕node u的局部图结构的更多信息。特别的，我们会使用多个关于convolutions的layers，其中：在layer k上的convolutions的inputs依赖于来自layer k-1（图1）的representations output，其中：intial（例如：“layer 0”）representations等于input node features。注意，在算法1（Q,q,W,w）中的模型参数会跨nodes共享，但在layers间的参数则不同。

算法2会详细说明：stacked convolutions 是如何为一个nodes的minibatch set M生成embeddings。我们首先计算每个node的邻居，接着使用K个convolutional迭代来生成关于target nodes的layer-K的representations。final convolutional layer的output接着通过一个fully-connected neural network进行feed来生成最终的output embeddings \(z_u, \forall u \in M\)

我们接着学习模型的full set参数：对于每个convolutional layer \((Q^{k}, q^{(k)}, W^{(k)}, w^{(k)}, \forall k \in \lbrace 1,\cdots,K \rbrace)\)的weight和bias参数，以及最终dense neural network layer \(G_1, G_2, g\)的参数。在算法1中的Line 1的输出唯度（例如：Q的column-space维度）会被设置为，在所有layers上均是m。出于简洁性，我们将所有convolutional layers的输出维度设置为相当（算法1第3行），接着我们将该size参数通过d进行表示。该模型的最终output维度（算法2）也被设置为d。

算法2

3.3 模型训练

我们会以一个监督学习的方式，使用max-margin ranking loss来训练PinSage。在该setup中，我们假设：我们已经访问了一个关于items L的labeled pairs集合，其中：在该set中的pairs \((q, i) \in L\)会被假设是相关的——例如：我们假设：如果 \((q, i) \in L\)，那么item i是对于query item q的一个好推荐侯选。training阶段的目标是，最优化PinSage参数，以便在labeled set中的pairs \((q,i) \in L\)的output embedding 是非常接近的。

我们首先详细描述了margin-based loss function。根据此，我们给出了一个关于我们开发的多个技术的总览，它会导致PinSage的计算效率以及快速收敛，允许我们可以在数十亿节点的graphs和数十亿训练样本上进行训练。最终，我们描述了我们的curriculum-training scheme，它会提升推荐的总体质量。

Loss function

为了训练模型的参数，我们会使用一个Max-margin-based loss function。基本思想是：我们希望最大化正样本的inner product，例如：query item的embedding以及相应的相关item。同时，我们希望确认，负样本的inner product（例如：在query item的embedding和一个unrelated item间的inner product）要小于正样本由一些pre-defined margin给出的正样本。对于 \((z_q, z_i) \in L\)的node embeddings的单个pair的loss function：

\[J_G(z_q z_i) = E_{n_k \sim P_n(q)} max \lbrace 0, z_q \cdot z_{n_k} - z_q \cdot z_i + \Delta \rbrace\]

…(1)

其中：

• \(P_n(q)\)表示了对于item q的负样本的分布
• \(\Delta\)表示了margin hyper-parameter

我们会在下面解释负样本的采样。

使用large minibatches的Multi-GPU训练

为了在单机训练上充分利用多个GPUs，我们会以一个multi-tower的形式来运行forward和backward propagation。有了多个GPUs后，我们首先会将每个minibatch（图1底部）划分成等size的比例。每个GPU会获取minibatch的一部分，并使用参数的相同集合进行计算。在backward propagation后，在所有GPUs上每个参数的gradients会聚合到一起，会执行单频synchronous SGD。由于需要在非常大数目的样本上（数十亿规模）训练，我们会使用large batch sizes进行运营，范围从512到4096.

我们使用由Goyal[16]提出的相似技术来确保快速收敛，当处理大的batch sizes时，并保持训练和泛化的准确率。我们使用一个渐近的热启过程（gradual warmup produre），在第一个epoch，根据线性scaling rule从小到大增加learning rate。之后，learning rate会指数递减。

Producer-consumer minibatch构建

在训练期间，由于size很大，对于数十亿nodes的feature matrix和adjacency list会在CPU memory中放置。然而，在PinSage的CONVOLVE step，每个GPU过程需要访问在邻居中节点的邻居和feature信息。从CPU内容中访问来自GPU的数据并不高效。为了解决该问题，我使用一个re-indexing技术来创建一个sub-graph \(G' = (V', E')\)包含了nodes和它的邻居，它会在当前minibatch的计算中被涉及。一个小的feature matrix会只包含了与当前minibatch的计算相关的node features，会被抽取出来，以便顺序与在G’中的nodes的index相一致。G’的adjacency list和small feature matrix会在每个minibatch迭代中被feed到GPUs中，因此，在GPU和CPU间的通信在CONVOLVE step期间不需要，极大提升了GPU利用率。

训练过程会交替使用CPUs和GPUs。模型会在GPUs中计算，然而：抽取features、re-indexing、negative sampling会在CPUs中计算。除了使用multi-tower training的并行GPU计算之外，CPU计算会使用OpenMP，我们会设计一个 producer-consumer pattern来在当前迭代中运行GPU计算，在下一迭代上并行使用CPU计算。这会进一步减少一半的训练时间。

对negative items进行采样

negative sampling会在我们的loss function中会被使用，作为edge likelihood的normalization factor的一个近似。当使用大的batch sizes训练时会提升效率，我们抽样一个关于500 negative items的集合，会在每个minibatch中与所有训练样本进行共享。对比起对于每个node独立运行负样本来说，这会极大节约需要在每个training step期间被计算的embeddings的数目。经验上，我们不会观察到在两个sampling schemes间效果的一个不同之处。

在最简单的case中，我们会从items的整个集合中均匀抽样负样本。然而，确保正样本（items(q,i)的pair）的内积大于q，500 negative items的每个都太“easy”，对于要学习的系统来说，不会提供足够好的“resolution”。特别的，我们的推荐算法可以发现在20亿items的catalog间与q 最相关的1000个relevant items. 换句话说，我们的模型会在20亿items上能够区分/标识 1个item。但在500个random negaive items，模型的resolution只有1/500. 因此，如果我们从20亿items中抽样出500个随机负样本items，任何这些与query items更轻微相关的items的机会更小。因此，该学习大概率不会做出好的参数更新，不能区分非常相关items和轻微相关items。

为了解决上述问题，对于每个正的训练样本（例如：item pair (q,i)），我们会增加“hard” negative examples，例如：items一定程度上与query item q相关，但与正样本item i不相关。我们称这些为“hard negative items”。他们会根据query item q的Personlized PageRank score通过在graph中的items进行ranking来生成。在2000-5000上排序的items会被随机抽样作为hard negative items。如图2所示，hard negative examples对比起random negative examples与query更相似，对于模型排序来说挑战更大，强制模型去学习以细粒度的方式区分items。

图2

通过training produre使用hard negative items，是需要训练至收敛的epochs数目的两倍。为了帮助收敛，我们开发了一个curriculum training scheme【4】。在训练的第一个epoch，不会使用hard negative items，以便算法快速发现在参数空间中的一个区域，其中：loss是相对小的。我们接着在后续epochs中添加hard negative items，聚焦于模型去学习如何区分高度相关pins和轻微相关pins。在训练的epoch n，我们会为每个item添加n-1个hard negative items到negative items集合。

3.4 通过MapReduce的Node embeddings

在模型被训练之后，直接使用训练好的模型来为所有items（包含了在训练期间没有见过的items）来生成embeddings仍然是很具挑战的。使用算法2以naive的方式计算nodes的embeddings，会导致重复计算，这是由nodes的K-hop邻居间的重合引起的。如图1所示，当为不同的target nodes生成embeddings时，许多nodes会在多个layers上重复计算。为了确保有效的inference，我们开发一个MapReduce方法，它无需重复计算即可运行model inference。

图3

我们观察到：node embeddings的inference可以非常好地借助于MapReduce的计算模型。图3详述了在二部图上的data flow，pin-to-board Pinterest graph，其中，我们假设：input（例如：“layer-0”） nodes是pins/items（以及layer-1 nodes是boards/contexts）。MapReduce pipeline具有两个关键部分：

• (1) 一个MapReduce 工作可以用于将所有pins投影到一个低维latent space中，其中：aggregation oepration会被执行（算法1，第一行）
• (2) 另一个MapReduce job接着用于将产生的pin representations，与他们出现的boards的ids进行联合，board embedding的计算会通过它的邻居的features进行pooling。

注意：我们的方法会避免冗余计算，每个node的latent vector只会计算一次。在boards的embedding会被包含后，我们会使用两个多的MapReduce jobs来计算关于pins的第二层的embeddings，以一个相似的方式，该过程可以尽快迭代（直到K个convolutional layers）。

3.5 高效地最近邻lookups

由PinSage生成的embeddings可以被用于许多下游推荐任务中，在许多settings中，我们可以直接使用在学到的embedding空间上通过最近邻查询这些embeddings来做出推荐。也就是说，给定一个query item q，我们可以推荐那些关于query item的embedding的embedding是K个最近邻。ANN可以通过locality sensitive hashing有效获得。在hash function被计算后，items的检索可以使用一个two-level检索过程，基于Weak AND操作符来实现。假设PingSage model通过离线训练给出，所有node embeddings会通过MapReduce进行计算，并在database中保存，有效的最近邻lookup operation可以确保系统以一个在线的方式提供服务。

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

standford在《Inductive Representation Learning on Large Graphs》中提出了GraphSage：

介绍

在large graphs中的节点（nodes）的低维vector embedding，已经被证明对于许多预估和图分析任务来说作为feature inputs是很有用的。在node embedding方法的基本思想是：使用降维技术将关于一个node的图邻居的高维信息蒸馏（distill）到一个dense vector embedding中。这些node embeddings可以接着被feed到下游的机器学习系统中，并用于分类、聚类、连接预测等任务中。

然而，之前的工作主要关注于来自单个fixed graph的embedding nodes，许多真实应用，会对于未知nodes、或者全新的subgraphs也能快速生成embeddings。这些归纳能力对于高吞吐、生产环境机器学习系统来说很重要，它会在演进的图上操作、并能总是遇到未知的nodes（例如：在Reddit上的posts、在Youtube上的users和videos）。对于生成node embeddings的归纳法来说，会面临着在具有相同形式features的各种图上的泛化（generalization）：例如：来自一个模式生物的在蛋白质的相互作用图上，训练一个embedding genreator，接着可以很容易使用训练好的模型，来对于新的生物体（organisms）收集来的数据生成node embeddings。

对比起直推式setting（transductive setting），inductive node embedding问题是特别难的，因为泛化到unseen nodes需要将新观察到的subgraphs“安排（aligning）”到已经通过算法最优化好的node embeddings中。一个inductive framework必须学习去认识一个node的邻居的结构化属性，它能表明节点的在图中的局部角色（local role），以及全局位置（global position）。

对于生成node embeddings的大多数已经存在的方法，是天然直推式的（transductive）。绝大多数方法是直接使用MF-based目标来最优化每个节点的embeddings，不会天然生成unseen data，因为他们会在一个单一fixed graph上做出预估。这些方法可以在一个inductive setting环境中被修改来执行，但这些修改版本的计算开销都很大，需要在做出新预估之前额外迭代好几轮gradient descent。一些最近的方法在图结构上使用卷积操作（convolutional operators）来进行学习，能提供一个embedding方法。因此，GCNs（graph convolutional networks）已经被成功应用到在fixed graph的直推式setting（transductive setting）上。而在本工作中，我们同时将GCNs扩展到归纳式无监督学习（inductive unsupervised learning）任务上，并提出一个framework来生成GCN方法，它使用trainable aggregation function（而不是简单的convolutions）.

我们提出了一个关于inductive node embedding的general framework，称为GraphSage（抽样和聚合：SAmple and aggreGatE）。不同于基于MF的embedding方法，我们会利用node features（例如：文本属性、node profile信息、node degrees）来学习一个embedding function，它会泛化到unseen nodes上。通过在学习算法中包含node features，我们会同时学习每个node邻居的拓朴结构，以及在邻居上的node features分布。当我们关注feature-rich graphs（例如：具有文本属性的引文数据、功能/分子标记的生物学数据），我们的方法也会利用出现在所有graphs（例如：node degrees）中的结构化features，因而，我们的算法也会被应用于没有node features的graphs中。

不同于为每个node训练一个不同的embedding vector的方式，我们的方法会训练一个关于aggregator functions的集合，它们会从一个node的局部邻居（local neighborhood）（图1）中学习到聚合特征信息（aggregates feature information）。每个aggregator function会从一个远离一个给定结点的不同跳数、搜索深度的信息进行聚合。在测试（test）或推断（inference time）时，我们使用已训练系统来为整个unseen nodes通过使用学到的aggregation functions来生成embeddings。根据之前在node embeddings生成方面的工作，我们设计了一个无监督loss function，它允许GraphSage使用task-specific supervision来进行训练。我们也表明了：GraphSage可以以一个完全监督的方式进行训练。

图1 GraphSAGE抽样和聚合方法的可视化演示

我们会在三个node分类benchmarks上评估我们的算法，它们会测试GraphSAGE的能力来在unseen data上生成有用的embeddings。我们会使用两个演进的document graphs，它们基于citation data和Reddit post data（分别预估paper和post类目），以及基于一个一个蛋白质的相互作用的multi-graph生成实验。使用这些benchmarks，我们展示了我们的方法能够有效生成unseen nodes的表示，效果对比baseline有一个大的提升。。。

2.相关工作

略

3.GraphSAGE

我们方法的关键思想是，我们会学习如何从一个节点的局部节点（local neighborhood）中聚合特征信息（例如：邻近节点的degrees和文本属性）。我们首先描述了GraphSAGE的embedding生成算法（例如：forward propagation），它会假设：为GraphSAGE模型参数已经被学习的节点生成embeddings。我们接着描述：GraphSAGE模型参数可以使用标准的SGD和BP技术被学到。

3.1 Embedding生成算法（例如：forward propagation）

在本节中，我们描述了embedding生成，或者forward propagation算法（算法1），它会假设：模型已经被训练过，并且参数是固定的。特别的，我们会假设：我们已经学到了关于K个aggregator functions的参数（表示为：\(AGGREGATE_k, \forall k \in \lbrace 1,\cdots,K\rbrace\)），它会被用于在模型的不同layers间、或者“搜索深度”上传播信息。第3.2节描述了我们是如何训练这些参数的。

• $G(V, E)$：图
• $\lbrace x_v, \forall v \in V \rbrace$：输入特征
• K：深度
• $W^k, \forall k \in \lbrace 1, \cdots, K \rbrace$： 权重矩阵
• $\sigma$：非线性激活
• $AGGREGATE_k, \forall k \in \lbrace 1,\cdots, K \rbrace$：可微聚合函数
• $N: v \rightarrow 2^v$：邻居函数（neighborhood function）

算法1

算法1的背后意图是：

• 在每个迭代中，或者搜索深度上，节点会聚合来自它们的local neighbors的信息；
• 并且随着该过程迭代，nodes随着graph的更进一步触达逐渐获得越来越多的信息。

算法1描述了case中的embedding生成过程，其中：

• \(G = (V, \epsilon)\)：表示整个graph
• \(\lbrace x_v, \forall v \in V \rbrace\)：表示graph中的所有node的input features
• K：表示深度
• \(W^k, \forall \lbrace 1,\cdots,K \rbrace\)：表示weight matrics

我们在下面描述了如何生成该过程到minibatch setting中。算法1的外循环中的每个step过程如下，其中：

• k：表示在外循环（或者搜索深度）中的当前step
• \(h^k\)：表示在该step中一个node的representation

首先，每个node \(v \in V\)会将在它的立即邻居（immediate neighborhood）\(\lbrace h_u^{k-1}, \forall u \in N(v) \rbrace\)上的nodes 的representations聚合到单个vector \(h_{N(v)}^{k-1}\)中。注意，该聚合step依赖于：在outer loop的前一迭代生成的representations，并且k=0（”bad case”）representations会被定义成input node features。

接着，在聚合了邻近的feature vectors之后，GraphSAGE会将该node的当前representation \(h_v^{k-1}\)与聚合的邻近vector \(h_{N(v)}^{k-1}\)进行拼接（concatenates），该concatenated vector会通过一个具有非线性activation function \(\sigma\)的fully connected layer进行feed，它会将representations转换成在算法的下一step进行使用（例如：\(h_v^k, \forall v \in V\)）。neighbor representations的聚合可以通过多个aggregator结构来完成，并且我们会在第3.3节中讨论不同的结构选择。

为了扩展算法1到minibatch setting中，给定一个关于input nodes的集合，我们首先对所需要的neighborhood sets（到深度K）进行forward sample，接着我们在inner loop进行运行，通过替代迭代所有nodes，我们只会计算：必须满足在每个depth上的递归的representations。

与 Weisfeiler-Lehman Isomorphism Test的关系

GraphSAGE算法在概念上受testing graph isomorphism的经典算法的启发。在算法1中，我们：

• (i) 设置\(K=\| V \|\)
• (ii) 设置weight矩阵作为identity
• (iii) 使用一个合适的hash function作为一个aggregator（无非线性），

接着算法1是一个关于WL isomorphism test的实例，也被称为“naive vertex refinement”。如果由算法1输出的representations \(\lbrace z_v, \forall v \in V \rbrace\)。该test在一些情况下会失败，但是对于许多图是合法的。GraphSAGE是对WL test的连续近似，其中，我们将hash function替代成trainable neural network aggregators。当然，我们使用GraphSAGE来生成有用的节点表示（node representations）——而非test graph isomorphism。然而，在GraphSAGE和经典的WL test间的连接，为我们的算法设计提供了理论context来学习关于节点邻居的拓朴结构。

Neighborhood定义

在本工作中，我们会均匀地抽样一个关于节点邻居的fixed-size集合，而非使用算法1中完整的邻居集合，是便保持每个batch的计算开销是固定的。也就是说，使用过载的概念，在算法1中，我们将\(N(v)\)定义为一个从集合\(\lbrace u \in V:(u,v) \in \epsilon \rbrace\)中fixed-size的均匀抽取，在每个迭代k上我们会从不同的均匀样本中进行抽样。如果没有这种抽样，单个batch的内存和runtime会不可预知，最坏情况下为\(O(\| V \|)\)。作为对比，对于GraphSAGE的每个batch space和时间复杂度被固定在\(O(\prod_{i=1}^K S_i)\)，其中\(S_i, i \in \lbrace \cdots \rbrace\)，K是user-specified常数。实际来说，我们发现我们的方法可以达到具有K=2的高效果，并且\(S_1 \cdot S_2 \leq 500\)。

3.2 学习GraphSAGE的参数

为了以一个完全无监督setting方式学习有用的、可预测的表示（representations），我们会通过SGD使用一个graph-based loss function给output representations \(z_u, \forall u \in V\)，并且调节weight矩阵 \(W^k, \forall k \in \lbrace 1,\cdots, K \rbrace\)， 以及得到的aggregator functions的参数。graph-based loss function会鼓励邻近节点具有相似的表示（representations），从而强制分离的nodes的representations具有高度的不同：

\[J_G(z_u) = - log(\sigma(z_u^T z_v)) - Q \cdot E_{v_n \sim P_n(v)} log(\sigma(- z_u^T z_{v_n}))\]

…(1)

其中:

• v：是一个node，它会与u在一个fixed-length的random walk中共现
• \(\sigma\)：是sigmoid function
• \(P_n\)：是一个negative sampling分布
• Q：定义了negative samples的数目

重要的是，不同于之前的embedding方法为每个node（通过一个embedding look-up）训练一个唯一的embedding，我们feed到该loss function的representations \(z_u\)会由在一个node的局部邻居（local neighborhood）中包含的features来生成。

该无监督setting会模拟以下情况：其中node features会提供到下游的机器学习应用，或者作为一个服务 或者 在一个静态仓库中。在本case中，其中representations只会在一个指定的下游任务中，无监督loss（等式1）可以简单地被一个task-specific目标（比如：cross-entropy loss）替换。

3.3 Aggregator结构

在N-D lattices（例如：句子、图片、或3D空间），一个node的邻居没有自然序：在算法1的aggregator function必须在一个关于vectors的无序集合上操作。理由的，一个aggregator function必须是对称的（例如：它的inputs排列是不变的），同时是可训练的，并且保持一个高度表达的能力。aggregation function的对称性确保了我们的neural network model是可训练的，并且可以被用于随意顺序的节点邻居的feature sets上。我们会检查三个候选aggregator function：

Mean aggregator

我们的第一个候选 aggregator function是mean aggregator，其中：我们简单地对在\(\lbrace h_u^{k-1}, \forall u \in N(v) \rbrace\)中的vectors做elementwise平均。该mean aggregator接近等于在transductive GCN network中的convolutional propagation rule。特别的，我们可以通过在算法1中的第4和第5行使用下面进行替换，派生一个关于GCN方法的inductive variant：

\[h_v^k \leftarrow \sigma(W \cdot MEAN(\lbrace h_v^{k-1} \rbrace \cup \lbrace h_u^{k-1}, \forall u \in N(v) \rbrace)\]

…(2)

我们将该修改版称为mean-based aggregator convolutional，因为它是一个关于一个localized spectral convolution的不平滑的线性近似。在该convolutional aggregator和其它aggregators间的一个重要区别是：在算法1的第5行，不会执行concatenation操作。例如：convolutional aggregator不会将node的前一layer representation \(h_v^{k-1}\)与he aggregated neighborhood vector \(h_{N(v)}^k\)进行concatenate。该concatenate可以被看成是关于一个关于在不同“search depths”或GraphSAGE算法中“layers”间的”skip connection”的简单形式，并且它会产生在效果上的巨大收益。

LSTM aggregator

我们也会检查一个更复杂的基于一个LSTM结构的aggregator。对比起mean aggregator，LSTMs的优点是：具有更强的表达能力。然而，需要注意的是，LSTMs没有天然的对称性（例如：它们没有排列不变性），因为他们以序列方式处理它们的inputs。我们采用LSTMs用来操作一个无序集合，通过简单地将LSTMs应用到一个关于节点邻居的随机排列上。

Pooling aggregator

该aggregator具有对称性，同时可训练。在pooling方法中，每个邻居的vector会独立地通过一个fully-connected neural network进行feed；根据该转换，一个elementwise max-pooling操作会被应用来对跨邻居集合的信息进行聚合：

\[AGGREGATE_k^{pool} = max(\lbrace \sigma(W_{pool} h_{u_i}^k + b), \forall u_i \in N(v) \rbrace)\]

…(3)

其中：

• max表示element-wise max操作符
• \(\sigma\)是一个非线性activation function

原则上，该函数会在max pooling之前被使用，可以作为一个随意的deep multi-layer perceptron，但我们关注于简单的single layer结构。该方法受最近研究【29】的一些启发。直觉上，multi-layer perceptron可以被认为是：作为在邻居集合中的每个节点表示的feature计算的一个函数集合，该模型可以有效地捕获邻居集合的不同方面。注意，原则上，任务对称vector function可以被用来替代max operator（例如：一个element-wise mean）。我们发现：关于developments test在max-pooling和mean-pooling间没有大差别，因此后续主要关注max-pooling。

实验

略

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

facebook在《MEMORY NETWORKS》中提出了memory networks，在另一文《End-To-End Memory Networks》提出了end2end的实现：

摘要

我们会介绍一种使用recurrent attention model的neural network，它构建在一个可能很大的外部memory之上。该架构与Memory network的形式一样，但与其中的model不同的是：它的训练是end-to-end的，因而在训练期间几乎是无监督学习，这使得它很容易应用到实际环境中。它可以看成是关于RNNsearch[2]的一个扩展：其中在执行每次output symbol时会执行多个计算steps（hops）。该模型的灵活性允许我们将它应用到像QA等不同的任务以及语言建模上。对比起之前的Memory Networks的研究，它几乎是无监督的。我们在Penn TreeBank和Text8 datasets上验证了我们的方法要好于RNNs和LSTMs。

1.介绍

在AI 研究领域，在QA或补全任务上，构建模型会涉及多个计算步骤，模型可以描述序列数据中的long-term dependencies。

最近的一些工作，在建模时会使用显式存储和attention；维持这样的一个storeage对于解决这样的挑战提供了一种方法。在[23]中，存储会通过一个continuous representation给出；从该存储进行读取和写入，可以通过neural networks的actions进行建模。

在本工作中，我们提出了一种新的RNN结构，其中：在输出一个symbol之前，recurrence会从一个可能很大的external memory中读取多次。我们的模型可以被看成是在[23]中的Memory Network的一个continuous form。本工作中的模型通过BP训练并不容易，需要在该network的每个layer上进行监督。模型的连续性意味着：它可以从input-output pairs通过end-to-end的方式进行训练，因此很容易应用到许多任务上，例如：语言建模或者真实的QA任务。我们的模型可以看成是RNNsearch[2]的一个版本，它在每个output symbol上具有多个计算步骤。我们会通过实验展示：在long-term memory上的多跳对于我们的模型的效果来说很重要，训练memory representation可以以可扩展的方式进行集成到end-to-end neural network model上。

2.方法

我们的模型会采用：

• 一个关于inputs \(x_1, \cdots, x_n\)的离散集合，它们会被存储到memory中
• 一个query q
• 输出一个answer a

\(x_i, q, a\)的每一个都包含了来自具有V个词的字典的symbols。该模型会将所有x写到memory中，直到达到一个确定的buffer size，接着我们会为x和q寻找一个连续的representation。这会允许在训练期间，error signal的BP通过多个memory accesses回到input。

2.1 Single Layer

我们先在single layer的case中开始描述我们的模型，它会实现一个单个memory hop操作。后续我们会展示可以对它进行stack来给出在memory上的多跳。

Input memory representation

假设我们给定一个input set \(x_1, \cdots, x_i\)被存到memory中。\(\lbrace x_i \rbrace\)的整个集合会被转到d维memory vectors \(\lbrace m_i \rbrace\)中，它通过在一个连续空间上嵌入每个\(x_i\)计算得到，在最简单的case中，使用一个embedding matrix A（其中：size=\(d \times V\)）。query q也会被嵌入来获得一个internal state u。在embedding space中，我们会计算在u和每个memory \(m_i\)间的match程度，通过以下公式对内积采用softmax得到：

\[p_i = Softmax(u^T m_i)\]

…(1)

其中，\(Softmax(z_i) = \frac{ e^{z_i} } {\sum_j e^{z_j}}\)。在该方式中，p是在inputs上的一个概率向量（probability vector）。

Output memory representation

每个\(x_i\)都具有一个相应的output vector \(c_i\)。memory o的response vector是一个在transformed input \(c_i\)与来自input的probability vector进行加权求和:

\[o = \sum_i p_i c_i\]

…(2)

由于从input到output的函数是smooth的，我们可以轻易地计算gradients以及BP。其它最近提出的memory或attention形式也采用该方法【2】【8】【9】。

生成最终的prediction

在single layer case中，output vector o和input embedding u接着通过一个最终的weight matrix W（size为\(V \times d\)）和一个softmax来生成predicted label：

\[\hat{a} = Softmax(W(o+u))\]

…(3)

整体模型如图1(a)所示。在训练期间，所有三个embedding matrics A, B, C，以及W都通过最小化\(\hat{a}\)和 true label a间的一个标准的cross-entropy loss进行联合学习。训练会使用SGD进行执行。

图1

2.2 Multiple Layers

我们现在扩展我们的模型来处理K跳的操作。memory layers会以如下方式进行stack：

• 在第一个之上的layers的input，是从layer k的output \(o^k\)和input \(u^k\)的求和（后续会有不同组合）：

\[u^{k+1} = u^k + o^k\]

…(4)

• 每个layer会具有它自己的embedding matrics \(A^k, C^k\)，用于嵌入到inputs \(\lbrace x_i \rbrace\)中。然而，如下所示，他们会被限制以便减轻训练、减少参数数目.

• 在network的顶层，W的input也会将top memory layer的input和output进行组合：

\[\hat{a} = Softmax(W u^{K+1}) = Softmax(W(o^K + u^K))\]

我们探索了在模型中两种类型的weight tying机制：

• 1.Adjacent：一个layer的output embedding是下一个的input embedding，例如：\(A^{k+1} = C^k\)。我们也会限制：a) answer prediction matrix会与最终的output embedding相似，例如：\(W^T = C^K\)， b) question embedding会与第一层的input embedding相匹配，例如：\(B = A^1\)
• 2.Layer-wise（RNN-like）：input和output embeddings对于不同的layers是相同的，例如：\(A^1 = A^2 = \cdots = A^K\)以及\(C^1 = C^2 = \cdots = C^K\)。我们已经发现：添加一个线性映射H到在hops间的u的update上是有用的；也就是说：\(u^{k+1} = H u^k + o^k\)。该mapping会随着剩余参数学习，并在我们的实验上用于layer-wise weight tying。

图1(b)展示了一个3-layer版本。总体上，它与[23]中的Memory Network相似，除了每一layer中的hard max操作已经使用了一个来自softmax的continuous weighting替换外。

注意，如果我们使用layer-wise weight tying scheme，我们的模型可以被转成一个传统的RNN，其中我们会将RNN的outputs分割成internal和external outputs。触发一个internal output可以与考虑一个memory相对应，触发一个external output对应于预测一个label。从RNN的角度，图1(b)和等式(4)的u是一个hidden state，该模型会使用A生成一个internal output p（图1(a)中的attention weights）。该模型接着会使用C来吸收p，并更新hidden state等。这里，与一个标准RNN不同的是，我们会在K hops期间，显式的基于在memory中储存的outputs作为条件，我们会采用soft的方式来保存这些outputs，而非对它们采样。这样，我们的模型会在生成一个output之前做出一些计算step，这意味着被“外部世界”见过。

其它

略

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

facebook在《MEMORY NETWORKS》中提出了memory networks：

摘要

我们描述了一种称为”memory networks”的新学习模型。memory networks会让inference components与一个long-term meory component进行组合；他们会学习如何使用这些联合机制。其中：long-term memory可以读取和写入，我们的目标是使用它进行预估。我们会在QA场景对该模型进行研究，其中，long-term memory会有效扮演着一个动态的knowledge base，输出是一个textual response。我们会在一个大规模QA任务上对它们进行评估，并从一个仿真世界生成一个很少并且复杂的toy task。在后者，我们展示了这些模型的强大之处，它们会将多个支持的句子串联来回答需要理解动词强度的问题.

1.介绍

大多数机器学习模型缺少一种简单方式来读取和写入long-term memory component的部分，并将它与inference进行无缝组合。因而，他们不能利用现代计算机的最大优势。例如，考虑这样一个任务：告诉一个关于事实（facts）或故事（story）的集合，接着回答与该主题相关的问题。通常这会通过一个语言建模器（language modeler，比如：RNN）来达到。这些模型会被训练成：当读取一个words流后，预测并输出下一个word(s)或者集合。然而，它们的memory（通过hidden states和weights进行encode）通常很小，没有被分得足够开来准确记住来自过往知识的事实（知识会被压缩到dense vectors中）。RNNs很难执行记忆，例如：简单的copying任务：读入一个句子输出相同的句子（Zaremba 2014）。其它任务也类似，例如：在视觉和音频领域，需要long-term memory来watch一个电影并回答关于它的问题。

在本工作中，我们介绍了一种新的模型，称为memory networks，它会尝试解决该问题。中心思想是：通过将成功的学习策略（其它机器学习文献中）进行组合，使用可读可写的memory component进行inference。该模型接着会被训练来学习如何有效操作memory component。我们引入了第二节中的通用框架，并提出一个在文本领域关于QA的指定实现。

2.Memory Networks

一个memory network包含了：

• 1个memory： m（一个通过使用\(m_i\)索引的objects的数组）
• 4个components：I、G、O、R

其中：

• I（input feature map）: 将incoming input转换成内部的feature representation
• G（generalization）： 给定new input更新旧的memories。我们称该genrealization为：在该stage，对于该network存在一个机会来压缩和泛化该memories，以便后续进一步使用
• O（output feature map）：给定new input和当前memory state，生成一个新的output（在feature representation space中）
• R（response）：将output转化成期望的response format。例如，一个文本reponse或一个action response。

给定一个input x（例如：一个input character，word或sentence，一个image或一个音频信号），该模型的flow如下：

• 1.将x转换成一个interal feature representation：\(I(x)\)
• 2.给定new input，更新memories \(m_i\)：\(m_i = G(m_i, I(x), m), \forall i\)
• 3.给定new input和该memories，计算output features o：\(o = O(I(x), m)\)
• 4.最终，将output features o解码给出最终的response: \(r = R(o)\)

该过程会同时被应用到train和test时，但在这样的过程间存在差别，也就是说，memories会在test time时已经被存储下来，但I、G、O、R模型参数不会被更新。Memory networks会覆盖许多种可能实现。I、G、O、R的components可以潜在使用任何机器学习文献的思想：例如：使用你最喜欢的模型（SVMs，或者decision trees等）

I component

component I可以使用标准的预处理：例如：关于文本输入的解析、共指、实体解析。它可以将input编码成一个internal feature representation，例如：将text转换成一个sparse或dense feature vector。

G component

G的最简单形式是，将I(x)存储到在memory中的一个”slot”上：

\[m_{H(x)} = I(x)\]

…(1)

其中：\(H(.)\)是一个slot选择函数。也就是说，G会更新关于index \(H(x)\)对应的m，但memory的其它部分不会动。G的许多复杂变种可以回溯并基于当前input x的新证据来更新更早存储的memories。如果input在character和word级别，你可以将inputs（例如：将它们分割成 chunks）进行group，并将每个chunk存储到memory slot中。

如果memory很大（例如：考虑Freebase或Wikipedia），你需要将memories进行合理组织。这可以通过使用前面描述的slot choosing function H来达到：例如，它可以被设计、或被训练、或者通过entity或topoic来存储记忆。因此，出于规模上的效率考虑，G（和O）不需要在所有memories上进行操作：他们可以只在一个关于候选的恢复子集上进行操作（只在合适主题上操作相应的memories）。在我们的实验中，我们会探索一个简单变种。

如果memory满了（full），会有一个“遗忘过程（forgetting）”，它通过H来实现，它会选择哪个memory需要被替换，例如：H可以对每个memory的功率（utility）进行打分，并对用处最少的一个进行覆盖写。我们不会在该实验中进行探索。

O和R components

O组件通常负责读取memory和执行inferenece，例如：计算相关的memories并执行一个好的response。R component则通过给定O来生成最终的response。例如，在一个QA过程中，O能找到相关的memories，接着R能生成关于该回答的实际wording，例如：R可以是一个RNN，它会基于output O生成。我们的假设是：如果在这样的memories上没有conditioning，那么这样的RNN会执行很差。

3.文本的MEMNN实现

一个memory network的特殊实例是：其中的components是neural networks。我们称之为memory neural networks（MemNNs）。在本节中，我们描述了关于一个MemNN的相对简单实现，它具有文本输入和输出。

3.1 基础模型

在我们的基础结构中，I模块会采用一个input text。我们首先假设这是一个句子：也可以是一个关于事实的statement，或者待回答的一个问题（后续我们会考虑word-based input sequences）。该text会以原始形式被存储到下一个提供的memory slot中，例如：S(x)会返回下一个空的memory slot N：\(m_N = x, N = N+1\)。G模块只会被用来存储该新的memory，因此，旧的memories不会被更新。更复杂的模型会在后续描述。

inference的核心依赖于O和R模块。O模块会通过由给定的x寻找k个supporting memories来生成output features。我们使用k直到2，但该过程可以被泛化到更大的k上。对于k=1，最高的scoring supporing memory会被检索：

\[o_1 = O_1(x, m) = \underset{i=1,\cdots,N}{argmax} \ s_O(x, m_i)\]

…(2)

其中：\(s_O\)是一个打分函数，它会对在sentenses x和\(m_i\)的pair间的match程度进行打分。如果k=2，我们会接着找到一个second supporting memory，它基于前一迭代给出：

\[o_2 = O_2(x, m) = \underset{i=1,\cdots,N}{argmax} \ s_O([x, m_{o_1}], m_i)\]

…(3)

其中，候选的supporing memory \(m_i\)现在分别由原始的input和第一个supporting memory进行打分，其中：方括号内表示一个list。最终的output o是\([x, m_{o_1}, m_{o_2}]\)，它是module R的输入。

最终，R需要生成一个文本response r。最简单的response是返回\(m_{o_k}\)，例如：输出我们检索的之前公开的句子。为了执行真实的句子生成，我们可以采用一个RNN来替代。在我们的实验中，我们也会考虑一个简单的评估折中方法，其中，我们会通过将它们排序，将文本响应限制到单个word（输出的所有words会在模型中被见过）：

\[r = \underset{w \in W}{argmax} \ s_R([x, m_{o_1}, m_{o_2}], w)\]

…(4)

其中：W是字典中所有words的集合，并且\(S_R\)是一个关于match程度的得分函数。

图1

一个示例任务如图1所示。为了回答该问题：x = “where is the milk now?”，O module会首先对所有memories进行打分，例如：所有之前见过的句子，与x相反来检索最可能相关的事实：该case中的\(m_{o_1}\)=”Joe left the milk”。接着，它会由给定的\([x, m_{o_1}]\)再次搜索该memory来找出第二可能的fact，也就是 \(m_{o_2}\)=”joe travelled to the office”（Joe在倒掉牛奶之前到过的最后的地方）。最终，R module使用等式(4)对给定的\([x, m_{o_1}, m_{o_2}]\)的words进行打分，并输出 r = “office”。

在我们的实验中，scoring functions \(S_O\)和\(S_R\)具有相同的形式，一个embedding model：

\[s(x, y) = \phi_x(x)^T U^T \phi_y(y)\]

…(5)

其中：U是一个\(n \times D\)的矩阵（D是features的数目，n是embedding的维度）。\(\phi_x\)和\(\phi_y\)的角色是，将原始文本映射到D维feature space中。最简单的feature space是选择一个BOW的representation，我们为\(s_O\)选择 \(D = 3 \mid W \mid\)，例如，在字典中的每个word会具有三个不同的representations：一个是为\(\phi_y(.)\)，另一个是为\(\phi_x(.)\)，依赖于关于input arguments的words是否来自于实际的input x或者来自于supporting memories，以便他们可以不同方式建模。相似的，我们会为\(S_R\)使用\(D=3\mid W \mid\)。\(S_O\)和\(S_R\)会使用不同的weight矩阵\(U_O\)和\(U_R\)。

training 我们以一个fully supervised setting方式训练，其中给定想要的inputs和responses，supporting sentences会在训练数据中被标记（在test data中，我们只输了inputs）。也就是说，在训练期间，我们知道在等式 （2）和(3)中的max functions的最佳选择。训练会接着使用一个margin ranking loss和SGD来执行。特别的，对于一个给定的question x，它具有true response r，supporting sentences \(m_{o_1}\)和\(m_{o_2}\)（当k=2），我们会通过模型参数\(U_O\)和\(U_R\)进行最小化：

\[\sum\limits{\bar{f} \neq m_{o_1}} max(0, \gamma - s_O(x, m_{o_1}) + s_O(x, \bar{f})) + \\ \sum\limits{\bar{f}' \neq m_{o_2}} max(0, \gamma - s_O([x, m_{o_1}], m_{o_2}) + s_O([x, m_{o_1}, \bar{f}'])) + \\ \sum\limits{\bar{r} \neq r} max(0, \gamma - s_R([x, m_{o_1}, m_{o_2}], r) + s_R([x, m_{o_1}, m_{o_2}], \bar{r}))\]

…(6)(7)(8)

其中，\(\bar{f}, \bar{f}', \bar{r}\)是对比正确labels所有其它选择，\(\gamma\)是margin。在SGD的每个step，我们会抽样\(\bar{f}, \bar{f}', \bar{r}\)，而非计算每个训练样本的总和。

在我们的MemNN中，采用一个RNN作为R component，我们会使用在一个语言建模任务中的标准log likelihood来替换最后一项，其中RNN会被feed序列\([x, o_1, o_2, r]\)。在test time时，我们会根据给定的\([x, o_1, o_2]\)输出prediction r。对比起最简单的模型，使用k=1并输出localted memory \(m_{o_1}\)作为response r，只会使用第一项进行训练。

下面章节我们会考虑扩展基础模型。

3.2 WORD序列作为input

如果input是word级别，而非sentence级别，那就在流中到达的words（例如，使用RNNs），并且还未被分割成statements和questions，我们需要将该方法进行修改。接着我们添加一个“segmentation” function，它会输入关于words的至今未被分割的最近序列。当该segmenter触发时（表示当前序列是一个segment）我们会将该序列写到memory中，接着如之前方式进行处理。segmenter会与其它组件相似建模，以一个embedding model的形式：

\[seg(c) = W_{seg}^T U_S \phi_{seg} (c)\]

…(9)

其中，\(W_{seg}\)是一个vector（实际上在embedding space中一个线性分类器的参数），并且c是input words序列，表示成使用一个独立字典的BOW。如果 \(seg(c) > \gamma\)，其中\(\gamma\)是margin，接着，该序列会被识别成一个segment。这种方式下，我们的MemNN在它的写操作中具有一个学习组件。我们将该segmenter考虑成概念的第一个证明：当然，你也可以设计得更复杂。附录B中给出了训练机制的详情。

3.3 通过Hashing方式的高效memory

如果存储的memories集合非常大，将等式（2）和等式（3）中所有内容进行打分会非常昂贵。作为替代，我们会探索hashing tricks来加速lookup：将input I(x)进行hash到一或多个buckets中，接着只有在相同buckets中的memories \(m_i\)会进行打分score。我们会研究hashing的两种方式：

• i) 采用hashing words
• ii) 将word embeddings进行聚类

对于(i)我们会考虑许多buckets，它们是字典里的words，接着对于一个给定的句子，我们将所有对应words hash到相应的buckets中。(i)的问题是：一个memory \(m_i\)只会考虑，它与input I(x)是否只共享至少一个word。方法(ii)尝试通过聚类方式解决该问题。在训练完embedding matrix \(U_O\)后，我们会运行K-means来将word vectors \(U(O)_i\)进行聚类，并给出K个buckets。我们接着将一个给定的句子中每个单独的word都落到各自的buckets中。由于word vectors趋向于与它们的同义词更近，他们会聚在一起，我们接着对这些相应的memories进行打分。input和memory间完全精准匹配则会通过定义进行打分。K的选择用于控制speed-accuracy间的trade-off。

3.4 建模write time

我们扩展我们的模型，来说明当一个memory slot是何时被写入。当回答关于确定事实的问题时（比如：“what is the capital of France?”），这并不重要。但当回答关于一个story的问题时（如图1），这就很重要。一种明显的方式是，添加额外的features到representations \(\phi_x\)和\(\phi_y\)中，它们会编码一个给定memory \(m_j\)的index j，假设：j会遵循write time（例如：没有memory slot rewriting）。然而，这需要处理绝对时间，而非相对时间。对于后续过程我们具有更成功经验：通过替代scoring input，与s的候选pairs，我们会在三元组 \(s_{O_t}(x, y, y')\)上学习一个funciton：

\[s_{O_t} (x, y, y') = \phi_x(x)^T U_{O_t}^T U_{O_t} (\phi_y(y) - \phi_y(y') + \phi_t(x, y, y'))\]

…(10)

\(\phi_t(x, y, y')\)使用三个新features，它会采用值0或1: 不管x是否大于y，x是否大于y’, y大于y’。（也就是说，我们会将所有\(\phi\) embeddings的维度扩展到3，并在当没有使用时将这三个维度设置成0）。现在，如果\(s_{O_t}(x, y, y') > 0\)，该模型会偏爱y胜过y’，如果\(s_{O_t}(x, y, y')<0\)则它偏好y’。等式(2)和(3)的argmax会通过在memories i=\(1, \cdots, N\)上的一个loop进行替换，在每个step时将胜出的memory(y或y’)保持住，并且总是将当前的胜者与下一memory \(m_i\)进行对比。在当time features被移除之前，该过程等价于argmax。更多细节由附录C给出。

3.5 建模之前未见过的words

对于那些读了很多text的人来说，新的words仍会持续引入。例如：word “Boromir”第一次出现在《指环王》中。那么机器学习模型如何处理这些呢？理想的，只要见过一次就能work。一个可能的方法是使用一个language model：给定邻近词语，预测可能的word，并且假设新的word与它们相似。我们提出的方法会采用该思想，但将它组装到我们的网络\(s_O\)和\(s_R\)中，而非一个独立的step。

具体的，对于每个见过的word，我们会存储共现过的BOW，一个bag用于左侧context，另一个用于右侧context。任意未知的word可以被这样的features进行表示。因而，我们会将我们的feature representation D从\(3 \mid W \mid\)增加到\(t \mid W \mid\)来建模这样的contexts（对于每个bag有\(\mid W \mid\) features）。我们的模型会在训练期间使用一种“dropout”技术来学习处理新words: d%的可能性我们会假装没有见过一个词，因而对于那个word来说不会有一个n维embedding，我们会使用context来替代表示它。

3.6 精准匹配和unseen words

embedding models不能有效使用exact word matches，因为维度n过低。一种解决方法是，对一个pair x,y使用下式进行打分：

\[\Phi_x(x)^T U^T \Phi_y(y) + \lambda \Phi_x(x)^T \Phi_y(y)\]

也就是说，“bags of words”会将得分与学到的embedding score进行茶杯。另外，我们的建议是，保留在n维embedding space中，但使用matching features扩展feature representation D，例如：每个word一个。一个matching feature表示着：一个词是否在x和y中同时出现。也就是说，我们会使用\(\Phi_x(x)^T U^T \Phi_y(y, x)\)进行打分，其中：\(\Phi_y\)实际基于x的条件构建：如果在y中的一些words与在x中的words相匹配，我们会将这些matching features设置为1。unseen words可以被相似建模，基于它们的context words使用matching features。接着给出一个feature space \(D = 8 \mid W \mid\)。

#

略

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

阿里在《Real Negatives Matter: Continuous Training with Real Negatives for Delayed Feedback Modeling》中提出了一种延迟建模方式：

抽要

CVR预估的一个难点是：转化会有延迟，并且在点击完较长时间后才发生。这种延迟反馈会提出一个新挑战：新数据会对连续训练（continuous training）有益，但在训练时并不会具有完整的label信息。为了平衡模型的新鲜度（freshness）和label确定性（label certainty），之前的方法会设置一个较短的等待窗口(waiting window)，或者甚至不用等转化信号。如果转化发生在等待窗口外，该样本将被复制，带上一个postive label，并被吸收到training pipeline中。然而，这种方法具有一些问题：

• 首先，他们假设：观察到的feature分布仍与实际分布是相同的。但该假设不会成立，因为有重复样本
• 第二，转化动作的确定度(certainty)在商业系统中是稀疏的。

这些问题会在延迟反馈建模期间引入bias。在本paper中，我们提出了DElayed FEedback modeling with Real negatives（DEFER）方法来解决这些问题。提出的方法会吸收真负样本到training pipeline中。真负样本能确保观察到的feature分布与实际分布等价，从而减少bias。真负样本的加入，也会带来更多关于转化的确定信息。为了纠正分布偏移（distribution shift），DEFFR会采用importance sampling来对loss function进行加权。工作数据集上的实验结果，验证了DEFFR的优越性。DEFFR会在阿里的展示广告系统上部署，并在多个场景下在CVR上获得了6%的提升。本paper中的代码和数据是开源的。

1.介绍

2.相关工作

一些之前的工作主要关注于delayed feedback问题【13】，这些方法并不是连续训练的，会忽略掉被错误标记的负样本。例如，如果模型在30天数据上进行训练，归属窗口（attribution window）是7天（在一个点击和一个转化间的延迟可能从不会超过7天），接着最近7天中的负样本的labels可能会不正常，因为转化可能发生在未来。注意，如果点击刚发生，negative label很有可能是不正确的。

2.1 Delayed Feedback Models

在展示广告中，因为活跃的advertisers、ad campaigns和users的变化，分布是动态变化的。例如，当新的ad campaigns被添加到系统中时，基于过去数据构建的模型可能会对其它新的ad campaigns表现不好。为了捕获数据中的变化，机器学习模型会持续进行更新来保持新鲜。最终，在训练期间，会设置一个等待窗口（waiting window）：转化被归属到在该等待窗口中发生的一个点击。接着，新的样本会被持续训练（continuous training）的训练算法所吸收。然而，由于窗口较短，持续学习方法可能会引入许多被错误标记的负样本（假负：fake negatives）。为了纠正由fake negatives引入的bias，【2，26】提出了delayed feedback models。延迟反馈建模（delayes feedback modeling）首先由DFM[2]提出。在DFM中，一个负样本会被看成是一个unlabeled样本，因为转化还未发生。除了预估CVR以外，CFM也会引入第二个模型，它会捕获在点击和转化间的期望延迟（expected delay），假设延迟分布遵循指数分布。这两个模型的训练是联合训练的（jointly）。注意，delayed feedback modeling也与存活时间分析（survival time analysis）紧密关联，它会研究存活时间的分布。在实际上，可能违反指数假设。为了解决该问题，Yoshikawa等【26】提出了一个无参数的delayed feedback model来进行CVR预估，它可以在没有假设一个参数分布的情况下，表示time delay的分布。

Ktena【12】采用一个持续训练的模式，通过初始使用一个负样本来包含所有样本。如果一个正向的engagement发生，该样本会复制上正标记（postive label），并在第二次时被包含在训练算法中。这里，这种有偏观察数据分布包含了来自实际数据分布会被标记为负样本的所有样本，以及原始正样本。为了学习来自bias分布的模型，ktena[12]提出了两个loss function FNW和FNC，它会利用importance sampling来处理分布偏移（distribution shift）。除了在初始将所有样本标记成负样本外，Yasui[25]提出了一种feedback shift importance weighting算法，在该算法中，模型会在一个特定时间间隔中的真实转化。然而，它不会允许数据纠正（data correction），例如，重复的正样本（当未来发生一个转化时）。为了发现在模型训练中的延迟与假负样本率（fake negative rate）间的一个tradeoff，ESDFM【24】会建模在观察到的转化分布和真实化分布间的关系。

图2 真负样本、假负样本、正样本的图示。这里，waiting window指的是在点击时间和在样本被取到训练pipeline间的时间间隔。

• 一个真负样本指的是：样本没有发生转化。
• 一个假负样本指的是：样本的转化发生在waiting window外，但仍在attribution window内。
• 一个正样本指的是：样本的转化发生在waiting window内

2.2 Delayed Bandits

存在一些bandit算法[10,18,22]，它们会研究延迟反馈建模。这些bandit算法的目标是，做出顺序决策，以便最小化累积遗忘（cumulative regret）。Joulani[10]分析了在在线学习算法的regret的延迟影响，并表明：延迟会以乘法方式增加在对抗问题（adversarial problems）中的regret，以加法方式增加在随机问题（stochastic problems）的regret。Pike【18】研究了带延迟的bandits问题，会聚合anonymous feedback。Vernade【22】则研究了随机延迟bandit设置，并提供了一个在假设延迟分布是已知下的完全分析。

3.前提

我们首先给出一个关于在线CVR建模的简单介绍。接着我们会引入之前的方法是如何解决CVR预估的延迟反馈的。

3.1 背景

在CVR预估中，模型会将输入看成是：\((x,y) \sim (X, Y)\)，

其中：

• x是feature，
• $y \in \lbrace 0, 1\rbrace $是转化标签（conversion label）

CVR预估的目标是：学习一个具有参数$\theta$的函数f，它会最小化从数据分布中抽样的样本的泛化错误（genrealization error）：

\[E_{(x,y) \sim (X,Y)} [l(x,y; f_{\theta}(x))]\]

…(1)

其中：

• l是loss function。

由于转化可能延迟，一些样本会通过传统的监督学习方法被不正确标记成负样本。

• z：在转化和点击期间的duration我们将它标记为z。如果该样本没有实际转化，$z = +\infty$。
• $w_1, w_2$分别分别是等待窗口和归属窗口的长度，并且$w_2 > w_1$。

如图2所示，在延迟反馈建模中存在三种类型的样本：

• 真负样本（Real negatives）：$z > w_2$。真负样本是没有发生转化的样本
• 假负样本（Fake negatives）：$w_1 < z < w_2$。假负样本是在训练时没有发生转化并且被误标记为负样本的样本，因为它的等待时间（waiting window）太短了。
• 正样本（Positives）：$z < w_1$。正样本指的是在等待窗口中具有转化动作的样本

注意，假负样本也是正样本，但转化并没有发生在等待窗口中。一种naive strategy是，等待一个足够长的窗口来确保大多数labels会是正确，来减小假负样本的数目。然而，在展示广告系统中，数据分布是动态变化的，例如：新的ad campaigns会添加到系统中。为了捕获数据的最新变化，CVR模型会持续更新。这样，它需要对模型新鲜度（model freshness）和标签确定度（label certainty）间进行权衡。之前的方法会通过设置一个短的等待窗口等待立即转化（immediate conversions）来解决该问题。为了纠正label噪声，假负样本会在当engagement发生时会复制一个正标记（postive label）【12】。这个重复的样本会被包含到训练管线中（training pipeline）。这里如图1(a)所示，观察到的分布包含了4部分：真负样本、正样本、假负样本、重复样本（带正标签的假复样本拷贝）。由于直接使用假负样本训练，会误导最优化的方向，之前的方法开发了多种方式来纠正分布偏移问题。

图1 (a) 之前的在线延迟反馈方法的data pipeline，它会复制具有positive labels的假负样本 (b) 提出的方法的data pipeline。提出的方法会复制正样本和真负样本。在复制后，特征分布与实际分布仍保持一致

3.2 假负样本加权（Fake Negative Weighted）

由于在观察分布与实际分布间的不一致（disparity），会采用importance sampling来纠正分布偏移（distribution shift）。Ktena【12】提出了假负样本加权（FNW：fake negative weighted）方法。

CVR预估的loss function可以被写成：

\[\begin{align} L = E_{(x,y) \sim p} l(x,y; f_{\theta}(x)) \\ = \int \int p(x) q(y | x) \frac{p(y|x)}{q(y|x)} l(x,y; f_{\theta}(x)) dxdy \\ \approx \int \int q(x) q(y | x) \frac{p(y|x)}{q(y|x)} l(x,y; f_{\theta}(x)) dxdy \\ = E_{(x,y) \sim q} \frac{p(y|x)}{q(y|x)} l(x,y; f_{\theta}(x)) \end{align}\]

…（2）

其中：

• q是有偏观察分布（biased observed distribution）

由于包含重复正样本，观察到的特征分布q(x)不等于实际特征分布p(x)。FNW假设：\(p(x) \approx q(x)\)，它会引入额外的bias到延迟反馈建模中。

在FNW中，没有设置waiting window，样本会立即看成是带负标签的负样本。一旦用户与ad有交互，相同的数据点使用一个正标签传给模型。这里，我们可以获得：

\[q(x \mid y = 0) = p(x), q(x \mid y = 1) = p(x \mid y = 1)\]

其中：

• $q(y=0) = \frac{1}{1+p(y=1)}$

在有偏分布中观察到的一个转化的概率为：

\[q(y = 1 | x) = \frac{q(y = 1)q(x | y = 1)}{q(y = 1)q(x | y = 1) + q(y = 0)q(x | y = 0)} \\ = \frac{p(y=1)}{1+p(y=1)} \cdot \frac{p(x | y = 1)}{p(x | y = 1) + \frac{1}{1+p(y=1)}p(x)} \\ = \frac{p(y = 1|x)}{1 + p(y = 1|x)}\]

同样，观察到负样本在有偏分布中的概率可以计算为：

\[q(y=0 | x) = \frac{1}{1+p(y=1|x)}\]

…(4)

通过替换在等式(2)中的等式3和等式4，loss function可以重写为：

\[L = -\sum\limits_{x,y} y(1+p(y=1|x))log f_{\theta}(x) + (1-y)p(y=0|x) ((1+p(y=1|x)) log(1-f_{\theta}(x))\]

…(5)

由于\(p(y=1 \mid x)\)不能被访问，FNW会将它替代为模型估计\(f_{\theta}\)，并在训练期间通过它对梯度传播进行stop。

3.3 假负样本校准（Fake Negative Calibraiton）

Fake negative calibration（FNC）会学习一个函数，它直接估计有偏分布q。接着FNC会通过以下calibration来获得函数\(p(y=1 \mid x)\)：

\[p(y=1 | x) = \frac{q(y=1 | x)}{1 - q(y=1 | x)}\]

…(6)

4.使用真负样本进行延迟反馈建模

在本节中，我们会详细介绍DEFER：DElayed FEedback modeling with Real negatives。我们：首先引入在DEFER中的数据流，它会复制真负样本（real negatives）来纠正分布漂移。基于设计好的数据流，DEFER会使用importance sampling来纠正分布漂移。其它方法也会使用真负样本进行训练，我们会派生出相应的loss function。最终，我们会共享我们的商业平台的部署经验，以及不同的转化归属机制、生产环境预算等。

4.1 数据流

如上所述，之前的持续训练方法会包含假负样本，以便在有噪声信号开销下捕获新鲜度（freshness）。为了引入更多确定的转化信息，会包含重复样本，我们使用importance sampling来纠正分布漂移。然而，这些方法都具有一些问题：

• 首先，重复样本会改变特征分布。该近似\(q(x) \approx p(x)\)会引入额外偏差。
• 再者，所有关于转化动作的特定信息会来自于正样本，这在CVR预估中是不足的。这使得模型很难学习并且仍表现良好。

为了减少bias，并且不伤害新鲜度，我们会包含重复正样本以及重复真负样本到训练pipeline中。

具体的，在重新设计过的数据pipeline中，我们让每个样本都具有一个waiting window $w_1$来等待转化信号。waiting window对于所有样本或者指定样本(sample-specific)来说是相同的。使用一个指定样本的窗口(sample-specific window)的原因是，不同的商品具有不同的延迟分布。例如，对比起便宜商品，昂贵的商品会具有较长的期望转化次数（expected conversion times），因而需要一个更长的窗口来等待转化信号。设置sample-specific window的一个策略是：定义多个window长度，来训练一个multi-class分类模型 $P_{length}(w_1 \mid x)$并预测waiting window长度：

\[w_1 = \underset{w}{argmax} P_{waiting} (w | x)\]

…(7)

在该窗口中具有转化的样本，会被标记成正样本；没有转化的样本会是假负样本或者真负样本。对于那些假负样本，如果之后在归属窗口中发生转化，我们会将这些样本带上正标签包含到pipeline中。对于那些最终不会发生转化的真负样本，我们也会进行复制，并将它们包含到训练pipeline中。这种重复会带来关于转化信号的更多确定信息。因而，在提出的方法中存在4种样本，如图1(b)所示，真负样本、正样本、假负样本、带真实label的重复样本（可以是正label，也可以是负label）。

4.2 Loss function

由于在观测到的分布与实际分布间的不一致，提出的方法会使用importance sampling来纠正分布偏移。有了重复样本的包含，我们可以获得：\(q(x) = p(x)\)，以及联合概率 \(q(x,y=0)\)可以被计算为：

\[q(x,y = 0) = p(x, y=0) + \frac{1}{2} p (x, y=1, z > w_1)\]

…(8)

条件概率$q(y=0 \mid x)$可以被写成：

\[q(y=0 | x) = \frac{q(x,y=0)}{q(x)} \\ = \frac{p(x,y=0)+\frac{1}{2} p(x,y=1, z > w_1)}{p(x)} \\ = p(y=0 | x) + \frac{1}{2} p_{dp}(x)\]

其中：

• $p_{dp}(x) = p(x, y=1, z>w_1 \mid x)$是x是一个假样本的概率。

相似的，$q(y=1 \mid x)$可以被写成：

\[q(y=1 | x) = p(y=1 | x) - \frac{1}{2} p_{dp}(x)\]

…(10)

接着，根据等式(2)，我们可以为x计算importance sampling：

\[\frac{p(y=0 | x)}{q(y=0 | x)} = \frac{p(y=0 | x)}{p(y=0|x) + \frac{1}{2} p_{dp}(x)} \\ \frac{p(y=1 | x)}{q(y=1 | x)} = \frac{p(y=1 | x)}{p(y=1|x) + \frac{1}{2} p_{dp}(x)}\]

…(11)

因而，importance weighed CVR loss funciton可以被公式化为：

\[L = - \sum\limits_{x,y} y \frac{p(y=1 | x)}{p(y=1|x) - \frac{1}{2}p_{dp}(x)} log f_{\theta}(x) \\ + (1-y) \frac{p(y=0 | x)}{p(y=0 | x) + \frac{1}{2} p_{dp}(x)} log(1-f_{\theta}(x))\]

…(12)

由于\(p(y=1 \mid x), p(y=0 \mid x)\)不能被访问，我们可以使用模型估计\(f_{\theta}(x)\)和\(1 - f_{\theta}(x)\)来分别替代\(p(y=1 \mid x), p(y=0 \mid x)\)。对于\(p_{dp}(x)\)，我们会训练一个分类器\(f_{dp}\)来预测x是一个假负样本的概率。如【12】所示，我们会通过importance weight来停止梯度传播。因此，等式(13)可以被重写成：

\[L = -\sum_{x,y} y [\frac{f_{\theta}(x)}{f_{\theta}(x) - \frac{1}{2} f_{dp}(x)}] log f_{\theta}(x) \\ + (1-y) [\frac{1 - f_{\theta}(x)}{1 - f_{\theta}(x) + \frac{1}{2} f_{dp}(x)}] log(1 - f_{\theta}(x))\]

其中\([\cdot]\)意味着停止梯度操作。

4.3 变种

对于其它方法（像FNW和FNC），重复的真负样本可以被包含来提升学习。我们为FNW和FNC来派生相应的loss function。

4.3.1 FNW

对于FNW，我们有：

\[q(y=1 | x) = \frac{p(y=1 | x)}{1 + p(y=1 | x) + p(y=0 | x)} = \frac{p(y=1 | x)}{2} \\ q(y=0 | x) = \frac{1 + p(y=0 | x)}{1 + p(y=1 | x) + p(y=0 | x)} = \frac{1 + p(y=0 | x)}{2}\]

…(14)(15)

接着我们有：

\[\frac{p(y=1 | x)}{q(y=1 | x)} = 2 \\ \frac{p(y=0 | x)}{q(y=0 | x)} = \frac{2 p(y=0 | x)}{1 + p(y=0 | x)}\]

…(16)

最终，loss function可以重新公式化为：

\[L = - \sum\limits_{x,y} 2y log f_{\theta}(x) + (1-y) p(y=0 | x) (\frac{2p(y=0|x)}{1+p(y=0|x)}) log(1 - f_{\theta}(x))\]

…(17)

4.3.2 FNC

相似的，对于FNC，我们有：

\[p(y = 1 | x) = 2q(y=1 | x)\]

…(18)

4.4 真负样本的生产环境设定

在展示公告中，不同的商业场景根据不同的用户行为，经常会设置不同的归属窗口。例如，在阿里巴巴，一些业务场景会将归属窗口设置为1天，而一些业务场景则会将归属窗口设置为7天。需要注意的是，真负样本的延迟时间等于正样本的最大延迟时间，并且模型新鲜度不可能受真负样本所大大影响，但会带来更多的确定label来训练算法。对于一个长转化窗口的业务场景，重复样本的引入，会增加维持数据缓存的额外的基础设施开销。因而，对于长转化窗口场景，我们会通过设置一个较短的窗口\(w_3 (w_1 < w_3 < w_2)\)。在\(w_3\)之前没有转化的样本，可以被近似为真负样本并直接放到训练算法中。对于具有短归属窗口的业务场景，我们不会采用近似，会包含真负样本。换句话说，我们将在线延迟反馈建模划分成2个settings：短的归属窗口和长归属窗口。对于首者，我们直接使用模型。对于第二个，我们假设：真负样本会在一个时间窗口\(w_3(w_1 < w_3 < w_2)\)之后被获取。相似的，\(w_3\)对于所有样本来说都是固定的，或者通过一个多分类模型进行预测：

\[w_3 = argmax_w P_{attribution} (w | x)\]

…(19)

4.5 离线训练方法

对于商业平台来说会使用离线训练，我们也提出了一个方法，它在许多场景被证明是有用的。

图3

如图3所示，我们提出的离线方法，会使用多任务学习（multi-task learning）通过利用在转化时间内包含的信息来提升泛化性。具体的，模型在shared bottom layers的top上具有N+1个heads。其中的一个head会预测：点击是否会被实际转化的概率，表示为\(p(y=1 \mid x)\)。其它heads会预测转化是否会在预定义的time window \(w_1, w_2, \cdots, w_N\)内发生：

\[p(z < w_n, y=1 | x) = p(z < w_n | y=1, x) * p(y=1 | x)\]

…(20)

\(y_n\)表示样本在\(w_n\)是否具有转化的概率，loss function可以被写成：

\[L = - \sum_n \sum_x y_n log p(z < w_n, y=1 | x) \\ - \sum_n \sum_x (1-y_n) log(1 - p(z < w_n, y=1 | x)) \\ - \sum_x y log p(y=1|x) - \sum_x (1-y) log(1-p(y=1 | x))\]

由于接近训练天数末尾的样本，可能具有所有的N+1个labels，我们只会根据观察到的labels更新相应的参数。对于一个样本来说，如果预定义的\(w_n, \cdots, w_N\)窗口还未到达，我们只会通过\(p(y=1, z<w_1 \mid x), \cdots, p(y=1, z<w_{n-1} \mid x)\)，当其它heads的参数在阻断时使用观察到的labels来来更新参数。注意，\(p(y=1 \mid x)\)也会通过\(p(y=1, z<w_1 \mid x), \cdots, p(y=1, z< w_{n-1} \mid x)\)的梯度进行更新。例如，5天作为第三个时间窗口。如果在从过去的第4天有样本点击，我们只会从\(p(z < w_1, y=1 \mid x), p(z<w_2, y=1\mid x)\)来更新参数。对于从过去的第7天前有过样本点击，那所有参数会同时更新。

5.实验

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