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）方法来解决这些问题。提出的方法会吸收真负样本（RN：Real Negative）到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）的变化，分布是动态变化的。例如，当新的广告被添加到系统中时，基于过去数据构建的模型可能会对其它新的广告表现不好。为了捕获数据中的变化，机器学习模型会持续进行更新来保持新鲜。最终，在训练期间，会设置一个等待窗口（waiting window）：转化被归属到在该等待窗口中发生的一个点击。接着，新的样本会被持续训练（continuous training）的训练算法所吸收。然而，由于窗口较短，持续学习方法可能会引入许多被错误标记的负样本（假负：fake negatives）。为了纠正由假负样本引入的bias，【2，26】提出了delayed feedback models。延迟反馈建模（delayes feedback modeling）首先由DFM[2]提出。在DFM中，一个负样本会被看成是一个unlabeled样本，因为转化还未发生。除了预估CVR以外，CFM也会引入第二个模型，它会捕获在点击和转化间的期望延迟（expected delay），假设延迟分布遵循指数分布。这两个模型的训练是联合训练的（jointly）。注意，延迟反馈建模也与存活时间分析（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会是正确，来减小假负样本的数目。然而，在展示广告系统中，数据分布是动态变化的，例如：新的广告会添加到系统中。为了捕获数据的最新变化，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 = \underset{w}{argmax} 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/2104.14121
• 2.https://github.com/gusuperstar/defer

Momenta公司在《Squeeze-and-Excitation Networks》提出了一种SENet的结构。我们来看下paper介绍：

1.介绍

CNNs已经被证明在解决许多视觉任务中是有用的模型。在CNN网络中的每个conv layer上，所使用的filters的集合可以用来表示：沿着input channels—的相邻空间连接模式（neighbourhood spatial connectivity patterns）——会在局部感受野（local receptive fields）内将空间信息和channel-wise信息融合（fusing）在一起。通过使用非线性激活函数和下采样操作符，与一系列conv layers进行交叉，CNNs可以生成图片表示（image representations），同时能捕获层级模式并获得global theoretical receptive fields。计算机视觉研究的一个中心主题是：关于许多强大的representations探索，只会对于一个给定任务，通过捕获一张图片的最显著属性来提升效果。对于视觉任务广泛使用的模型族来说，新的NN结构设计的发展，是一个前沿领域。最近研究表明，由CNNs生成的representations可以通过将学习机制（learning mechanisms）集合到网络中的方式来得到增强，可以捕获features间的空间相关性。这样的研究有：Inception家族，它会包含multi-scale过程到网络模块中，来达到效果提升。最近一些研究工作则会更好地建模空间依赖，并将spatial attention包含到网络结构中。

在本paper中，我们研究了【network设计-—channels间的关系】的不同方面。我们会引入一个新的结构单元，术语称为“Squeeze-andExcitation (SE) block”，它会通过显式建模convolutional features间的相互依赖，生成的representations会提升quality。为了这个结果，我们提出了一个机制，它允许该网络执行特征再校准（feature recalibration），尽管它可以学习使用全局信息来选择性地增强有信息量的features，并消除更少信息量的features。

SE building block的结构如图1所示。对于任意给定的transformation \(F_{tr}\)，会将input X映射到feature maps U上，其中：\(U \in R^{H \times W \times C}\)，例如：一个convolution，我们可以构建一个相应的SE block来执行feature recalibration。

• squeeze operation(\(F_sq(\cdot)\))：首先features U会通过一个squeeze operation进行传递，它会通过将沿着它们的空间维度（H X W）的feature maps进行聚合来生成一个channel descriptor。该descriptor的函数会生成一个关于channel-wise feature responses的全局分布，他允许来自该网络的global receptive field的信息通过所有它的layers来被使用。
• excitation operation(\(F_ex(\cdot,W)\))：接着跟一个excitation operation来进行聚合，它会采用一个简单的self-gating机制的形式，会将该embedding作为input，并生成一个关于per-channel modulation weights的集合。该weights会被应用到feature maps U来生成SE block的output，它可以被直接feed到该network的后续layers上。

图1 一个Squeeze-and-Excitation block

通过简单地将一个关于SE blocks的collection进行stacking，可以构造一个SE network（SENet）。另外，在网络结构的深度范围内，这些SE blocks可以被用来作为一个对于original block的简易替换(drop-in replacement)。而该building block的模板是通用的，它会在不同的depths上进行执行，而非贯穿该network。在更早的layers中，它会以一个分类不可知（class-agnostic）的方式来激发有信息量的features，增强共享的low-level representations。在更后的layers中，SE blocks会变得更专业，来以一个高度class-secific的方式响应不同的inputs。因此，通过SE blocks进行feature recalibration的好处是：效果可以通过network进行累积。

新的CNN结构的设计和开发是一个非常难的工程任务，通常需要许多新超参数以及layer配置的选择。相反的，SE block的结构非常简单，可以直接用在state-of-the-art的结构中，通过将组件替换成SE部分即可，其中：效果可以被有效增强。SE blocks的计算非常轻量，只会在模型复杂性和计算开销上引入一个轻微的增加。

为了提供证据，我们开发了许多SENets，并在ImageNet dataset上进行评估。我们的方法在ILSVRC 2017分类比赛中得到第一。在top-5 error上达到了2.251%的提升。

2.相关工作

3. SQUEEZE-AND-EXCITATION BLOCKS

一个Squeeze-and-Excitation block是一个计算单元，它可以在一个transformation \(F_{tr}\)上构建，该转换会将一个input \(X \in R^{H' \times W' \times C'}\)映射成feature maps \(U \in R^{H \times W \times C}\)。接着，我们将\(F_{tr}\)看成是一个convolutional operator，并使用\(V = [v_1, v_2, \cdots, v_C]\)来表示关于filter kernals的learned set，其中：\(v_c\)指的是：第c层filter的参数。我们接着将outputs写为 \(U = [u_1, u_2, \cdots, u_C]\)，其中：

\[u_c = v_c * X = \sum\limits_{s=1}^{C'} v_c^s * x^s\]

…(1)

其中：

• \(*\)表示convolution
• \(v_c = [v_c^1, v_c^2, \cdots, v_c^{C'}], X = [x^1, x^2, \cdots, x^{C'}], u_c \in R^{H \times W}\)。
• \(v_c^s\)是一个2D spatial kernel，表示\(v_c\)的一个单通道（single channel），扮演着X的相应channel。

为了简化该概念，bias项会被忽略。由于该output会通过一个关于所有channels的总结来生成，channel dependencies会隐式地嵌入在\(v_c\)中，但会与由filters捕获的local spatial correlation牵连在一起。通过convolution建模的channel relationships，天然就是隐式（implicit）和局部的（local），除了在top-most layers上。我们期望，convolutional features的学习可以通过显式建模channel间的相互依赖性来进行增强，因此，该network可以增加对informative features的感知，它们可以通后续的转换所利用。因此，我们希望在两个steps中提供访问全局信息和对filter responses进行recalibrate：squeeze和excitation，在它们被feed到下一transformation前。SE block的结构如图1所示。

3.1 Squeeze: Global Information Embedding

为了解决利用channel dependencies的问题，我们首先考虑在output features中每个channel的信号。每个learned filters会与一个local receptive field进行操作，相应的，该transformation output U的每个unit不能利用在该区域外的contextual information。

为了消除该问题，我们提出将全局空间信息（global spatial information）进行压缩（squeeze）到一个channel descriptor中。通过使用global average pooling来生成channel-wise statistics的方式来达到。正式的，一个statistic \(z \in R^C\)通过对U在它的空间维度\(H \times W\)上进行收缩（shrinking）来生成，以使z的第c个element可以被计算：

\[z_c = F_{sq}(u_c) = \frac{1}{H \times W} \sum\limits_{i=1}^H \sum\limits_{j=1}^W u_c(i, j)\]

…(2)

讨论：transformation U的output可以被解释成一个关于local descriptors的集合，它的statistics对于整个image来说表达力强。利用这样的信息在之前的feature engineering工作中很盛行。我们选择最简单的聚合技术，global average pooling，注意：最复杂的策略在这也可以使用。

3.2 Excitation：自适应再校准（Adaptive Recalibration）

为了利用在squeeze操作中聚合的信息，我们会接着使用一个二级操作符（second operation），它的目标是完全捕获channel-wise dependencies。为了满足该目标，该函数必须满足两个准则：首先，它必须是灵活的（特别的，它必须能学习一个在channels间的非线性交叉）；第二，它必须学习一个非相互排斥（non-mutually-exclusive）关系，由于我们会确保：多个channels会被允许强调（非而强制一个one-hot activation）。为了满足这些准则，我们选择采用一个使用sigmoid activation的简单gating机制：

\[s = F_{ex}(z, W) = \sigma(g(z, W)) = \sigma(W_2 \sigma(W_1 z))\]

…(3)

其中，\(\sigma\)指的是ReLU function，\(W_1 \in R^{\frac{C}{r} \times C}\)和\(W_2 \in R^{C \times \frac{C}{r}}\)。为了限制模型复杂度，以及aid generalisation，我们会对gating机制进行参数化，通过在非线性周围构建一个具有两层FC layers的瓶颈来达到：例如，一个具有reduction ratio为r的降维层（dimensionality-reduction layer）（该参数选择可以在第6.1节中讨论）、一个ReLU、接着一个增维层（dimensionality-increasing layer），它会返回transformation output U的channel维度。该block的最终output可以通过使用activations s，并对U进行rescaling来获得：

\[\bar{x}_c = F_{scale}(u_c, s_c) = s_c u_c\]

…(4)

其中，\(\bar{X} = [\bar{x}_1, \bar{x}_2, \cdots, \bar{x}_C]\)以及\(F_{scale}(u_c, s_c)\)指的是在标量\(s_c\)和feature map \(u_c \in R^{H \times W}\)间的channel-wise乘法。

讨论：excitation operator会将input-specific descriptor z映射到一个关于channel weights的set上。就这一点而言，SE blocks内在会基于input上引入动态性（dynamics），它会被看成是在channels上的一个self-attention function，它的关系会受限于convolutional filters所响应的local receptive field。

3.3 实例化

SE block可以被集成到如VGGNet的标准结构中，在每个convolution的非线性之后通过插方式实现。再者，SE block的灵活性意味着，它可以被直接应用到在标准卷积之外的转换上。为了说明这一点，我们开发了SENets，通过将SE blocks包含到许多更复杂结构的实例中，来描述。

我们首先考虑，对于Inception networks上SE blocks的构建。这里，我们简单地将transformation \(F_{tr}\)看成是一整个Inception module（如图2所示），并且通过对于在结构上的每个module做出这种变更，我们可以获得一个SE-Inception network。SE blocks可以被直接与residual networks一起使用（图3描述了SE-ResNet module的schema）。这里，SE block transformation \(F_{tr}\)被看成是一个residual module的非正定分支（non-identity branch）。Squeeze和Excitation会在使用identity branch进行归纳前同时起作用。更进一步，使用ResNeXt、Inception-ResNet、MobileNet和ShuffleNet集成SE blocks的变种，可以通过遵循相应的schemes来构建。对于SENet结构的具体示例，如表1有给出：SE-ResNet-50、SE-ResNeXt-50的详细描述。

图2

图3

SE block的灵活性的一个结果是，有许多变种方式，可以很容易集成到其它结构中。因此，为了对所使用的集成SE blocks到网络结构中的策略评估敏感性，我们可以提供消融实验（ablation experiments）来探索关于block的不同设计。

4.模型和计算复杂度

对于提出的SE block设计，它必须提供一个在效果和模型复杂度间的较好tradeoff。为了说明与module相关的计算开销，我们会考虑在ResNet-50和SE-ResNet-50间的一个对比作为示例。ResNet-50在单个forward pass上对于一个224 x 224 pixel input image上需要~3.86 GFLOPs。每个SE block会在squeeze阶段利用一个global average pooling操作符，而在excitation阶段会使用两个小的FC layers，接着跟一个昂贵的channel-wise scaling操作。在聚合时，当设置reduction ratio r到16时，SE-ResNet-50需要~3.87 GFLOPs，对比起原始ResNet50，对应有一个0.26%的相对提升。除了增加轻微的额外开销外，SE-ResNet-50的accuracy要超过ResNet50，可以达到一个更深的ResNet-101网络的效果，而它需要~7.58 GFLOPs（表2）。

在实际项中，通过ResNet-50的单个pass forwards和backwards会花费190ms…

略

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