Beyond Weisfeiler-Lehman: using substructures for provably expressive graph neural networks()

本文是我学习GNN时浏览国内外博客所学习到的知识汇总，并总结成一些文章分享给大家。

Expressive power of graph neural networks and the Weisfeiler-Lehman test（GNN的表达能力以及WL算法）

原文链接

帝国理工教授Michael Bronstein，是我目前看到的，GNN相关的博客数量最高的作者。所以就从这位教授出发，慢慢总结GNN。

传统的神经网络能够逼近任何光滑函数，所以可以得到一个较为理想的准确率。但是对于GNN来说，在有些数据上表现优秀的算法在其他数据集上就突然拉胯（很多GNN都是这样的）。所以我们就想问了，GNN的表达能力到底有多强？

其中一个主要的挑战就是：GNN所面向的图数据同时具有连续性和离散性两种特点。连续性表现在节点与节点之间有边相连，离散性表现在节点是离散的。所以，一个基本的问题就是，GNN是否能够分辨不同的图结构？这是一个经典图论问题，就是“同构判定”，主要是判断两个图是否等价（大家可以这样想，如果你的图神经网络能够表达一个图数据，这不就说明你的神经网络学习到了这组数据的精髓了吗？换个角度，就是神经网络与图数据的同构判定问题。如果神经网络足够优秀，那实际上应该是和你的数据是同构的）。

同构是在数学对象之间定义的一类映射，它能揭示出在这些对象的属性或者操作之间存在的关系。若这两个数学结构之间存在同构映射，那么这两个结构叫做是同构的。一般来说，如果忽略掉同构的对象的属性或操作的具体定义，单从结构上讲，同构的对象是完全等价的

而对于图结构来说，同构就是两个图的边集与点集相等，与顺序无关。

那么如何判断两个图是否同构呢？这里就需要介绍一下Weisfeiler-Lehman test¹，简称WL。简单来说，WL的中心思想就是使用中心节点和其邻居节点做哈希运算，得到的哈希值赋予中心节点，将这两个步骤迭代N次直至收敛。不过WL只是一个充分但不必要条件，有些时候会失效。如下图所示：

Two non-isomorphic graphs on which the WL graph isomorphism test fails, as evident from the identical colouring it produces. In chemistry, these graphs represent the molecular structure of two different compounds, decalin (left) and bicyclopentyl (right). Figure adapted from [14].

说了这么多，我们就要说说WL和GNN之间的联系了。
我们在文章开头时提到过，如果神经网络可以同构与一个图数据，那么这个神经网络就相当于学习到了图表示。 （当然了，上述文字中的同构并不是数学意义上那种严格的同构。我们只是希望神经网络学习到的节点分布能和被学习的图数据的节点分布近似或者相同。这里我们提到了分布，有了分布，就可以引入统计学了呀）实际上我们已经看到，WL中包含了GNN的“消息传递”，“信息聚合”这两个最基本的概念。不过WL是0参数的单层感知。更为具体的相关工作大家可以参考原博客。
参考1，kipf博客
参考2，WL和GNN

WL算法：上面两个图结构的节点分布近似，所以这两个图很可能是同构的。（事实上就是同构的，大家稍微思考一下就能够发现）

当然了，k-WL是一个更强的收敛，区别在于每个节点都会有k个哈希值。²

那么，我们就可以根据k-WL来构建一个多层GNN了。虽然从理论的角度出发，我们有了一个不错的模型，但是最近的研究成果³表明，先进的GNN模型实际上并不如以前的算法技术。这在机器学习中并不少见，因为理论和实践之间往往存在巨大差距。其中一个解释可能是基准本身的缺陷。但或许更为深刻的原因是,更好的表达能力不一定提供更好的概括(有时恰恰相反),此外,图同构可能无法准确的捕捉数据特征，我们后续再讨论这个问题。当然了，GNN的工作还是非常富有成效的，尤其是在还没有应用图方法的深度学习领域⁴。

• [1] B. Weisfeiler, A. Lehman, The reduction of a graph to canonical form and the algebra which appears therein (1968). Nauchno-Technicheskaya Informatsia 2(9):12–16. English translation and the original Russian version, which contains a pun in the form of an unusual Cyrillic notation (Операция „Ы“) referring to the eponymous Soviet blockbuster from three years earlier. See also a popular exposition in this blog post. Lehman is sometimes also spelled “Leman”, however, given the Germanic origin of the surname, I prefer the more accurate former variant.

• [2] Weisfeiler-Lehman hierarchy. One direction of extending the results of Xu and Morris was using more powerful graph isomorphism tests. Proposed by László Babai, the k-WL test is a higher-order extension of the Weisfeiler-Lehman algorithm that works on k-tuples instead of individual nodes. With the exception of 1-WL and 2-WL tests that are equivalent, (k+1)-WL is strictly stronger than k-WL, for any k≥2, i.e. there exist examples of graphs on which k-WL fails and (k+1)-WL succeeds, but not vice versa. k-WL is thus a hierarchy or increasingly more powerful graph isomorphism tests, sometimes referred to as the Weisfeiler-Lehman hierarchy.There exist several variants of WL tests that have different computational and theoretical properties, and the terminology is rather confusing: readers are advised to clearly understand what exactly different authors mean by “k-WL”. Some authors, e.g. Sato and Maron, distinguish between WL and “folklore” WL (FWL) tests, which mainly differ in the colour refinement step. The k-FWL test is equivalent to (k+1)-WL. The set k-WL algorithm used by Morris is another variant that has lower memory complexity but is strictly weaker than k-WL.
• [3] V. P. Dwivedi et al. Benchmarking graph neural networks (2020). arXiv: 2003.00982.
• [4] To be historically accurate, the WL formalism is not new to the machine learning community. The seminal paper of N. Shervashidze and K. M. Borgwardt, Fast subtree kernels on graphs (2009). Proc. NIPS was, to the best of my knowledge, the first to use this construction before the recent resurgence of deep neural networks and precedes the works discussed in this post by nearly a decade.

myblog

个人读书笔记

当了那么就的白嫖怪，也是时候为社会做出贡献了。

并对用于知乎的markdown进行了一些修改，更加适合hexo用户。

zhihu-publisher.py ： 我做了一些简单的修改，让它在文件内也能直接运行，就不需要命令行那么麻烦了。生成出来的文件会在D盘下的Data文件夹内，当然您也可以做出适合自己的修改。

github版本在这里，最好用谷歌浏览器

【图神经网络】文献阅读笔记

最近在研究图神经网络相关的内容，所以写下这篇阅读笔记。个人能力有限，所以如果您在阅读的过程中找出了错误请务必指出。另不吝赐教，相互交流学习。本文也会持续更新。😛

个人认为GNN是目前来看，唯一一个能对抗Transformer的框架了。另外，深度学习条件下的GNN的历史虽然差不多和Transformer一样，但对于GNN的研究还差得太多，因此还不够深刻和彻底，这就导致了性能和应用两方面的拉胯。不过也正是GNN的各种研究方面的缺陷才让我们有了“可乘之机”，毕竟相关领域还不是太卷，广阔天地大有可为。正所谓“熟读洋屁三百篇，不会放屁也会吟”，奥利给！兄弟们干了！

前言

众所周知，自然界的数据绝大部分都是非欧的，这些数据无头无尾，一团乱麻，处理起来非常棘手。

目前的四大主流深度学习算法(算子)：全连接，CNN,RNN,ATT（我们先暂时忽略对抗，自编码以及强化学习）。它们对于图结构的数据的处理能力有限，但问题是深度学习发展到今天，也只有这几种常见的方法。这时候研究者就面临了两种选择：

1. 要么让算法去适应非欧的数据（改算法不改数据结构）
2. 要么让非欧的数据去适应算法（改数据结构不改算法）

道理是这么个道理，但我的分类方法还是相对粗糙的。学术界的两种主流分类方法是：

1. 节点为主的建模方法，边为主的建模方法，节点和边同时建模的方法。
2. 图卷积（CNN）、时序图（RNN）、图注意力（ATT）…

无论我们采用何种分类方式，我们总是绕不开两个核心问题：

1. 图的拓扑结构应该如何表示？
2. 节点和边的信息应该如何学习？

在此，我们将图分成了两部分，即：⭐结构和信息⭐。更直白的来说，图=拓扑结构+信息。

而数学中对图的定义则是有序的节点集和边集的集合。我们所采取的这种定义方式只是比较直接的指出了图神经网络研究的主要难点，本质上和数学中的定义是相同的。我们将在后面不断的讨论这两个难点。

另外，单独一个问题的研究都是没有意义的，因为去掉任何一个要素（结构或者信息）都不能构成一个完整的图。所以，我们还需要找到一种连结两个问题的方法。幸运的是，我们目前有两种方法同时处理结构和信息，一个是谱方法（特征值分解），另一个是采样。我个人比较支持采样方法。

好了，既然现在我们知道了图的研究对象是其结构和信息，获取样本的方法是谱分解或者采样，那么这些数据应该如何计算呢？

还记得马克思的那句话吗？人是其社会关系的总和。这句话很好的启发了我们，我们可以得到节点是其关系信息的总和，这些关系包括了节点的邻居，邻边和其自身。然后我们将这些关系信息通过某种方式聚合起来，就可以得到该节点的表示了。

我们的学习顺序和之前的综述性文章是不太一样的。
我们的论文阅读顺序如下所示：

1. 图神经网络的基本建模思路（MPNN）
2. 采样方法（GraphSAGE等）
3. 时序图
4. 图卷积
5. 图注意力

本文统一的符号

先写这么多，会慢慢扩展和补充

文献阅读笔记法

按照这个顺序记笔记

【论文题目】:

【概述】:

【需要解决的问题】:

【这个问题为什么重要】：

【解决之后有什么好处】：

【解决问题的前提条件或者是假设】：

【解决问题的具体方法】：

【实验】：

【结论】：

【源码解析】：

【个人评价】：

相关术语及概念

在进入正式的学习之前，我们需要对该领域的专业术语和概念进行一定的了解，方便同行之间的沟通和交流。不敢保证能达到智取威虎山的效果，但至少能保证不至于张嘴就被击毙。

A New Model for Learning in Graph Domains

【论文题目】：图领域的一种新的学习模型

【概述】：在一些场景中，信息是自然的以图的形式所表示的。虽然这些算法能够将图信息表示成一组向量，但通常来说，处理过程会丢失掉图的拓扑结构信息，而且其向量表示也是受算法本身约束的。这片文章提出了一种广义的RNN，能够处理许多种图结构的信息。另外，本文提出了一些重要的图神经网络的术语和概念。

【需要解决的问题】：图神经网络建模方法，以及节点和边的表示方法。

【解决问题的前提条件或者是假设】：假设数据都可以表示成图结构的。

【这个问题为什么重要】：因为自然界的数据绝大多数都是以图形式出现的，所以我们必须解决图建模的基本算法问题。

【解决之后有什么好处】：可以用高维形式进行图表示，提升相关任务的准确率。

【解决问题的具体方法及实验】：

1. 论文提出了节点级(node focused)和图级(graph focused)的两种建模方法，区别就是预测的时候，是预测了图的一部分信息还是预测整张图的信息。虽然我个人感觉这种分类方式已经有点过时了，而且以当前的算力来看，似乎又会造成一定程度上的混淆，所以我个人将不再讨论这个分类方式。

2. 广义RNN ： 首先通过随机游走的方式得到一个序列，然后用这个序列上的每一个节点及其邻居节点作为一个子图，再把这个子图中的所有信息通过一定的方式聚合到一起，形成一个新的节点。这样，我们就得到了一个序列化的子图，而且这个序列化的子图可以直接使用RNN计算，因此就成了广义RNN。在这篇论文中，广义RNN实际上就是GNN的原型。

3. 消息的传递、聚合和更新：

   $$v_{t+1}=f_{\theta}(v_t,\mathcal{N}(v_t),l_{\mathcal{N}(v_t)} )$$ $$o(v_{t+1})=g_{\theta}(v_t,v_{t+1})$$

   上式对应于原文中的等式$(7)$。

   第一行实际上就是消息的传递，$l$是节点的标签信息，也就是说，GNN可以是有监督的，也可以是自监督的。

   第二行中相当于节点信息的更新。

   那么聚合体现在哪里呢？实际上原文是没有“聚合”这个概念的，传递和聚合的过程被一同合并在了$f_{\theta}$里面。

   更为具体的概念我们将会在之后的论文中讨论。

用前向传播来计算数值解
用聚合信息的方法来计算表示解

【结论】：图神经网络=采样+消息传递+消息聚合+状态更新。这四要素构成GNN的基石，缺一不可。

【源码解析】：

【个人评价】：这篇论文提出了最原始的采样、传递、聚合、更新的概念（虽然确切的来说，是没有聚合的概念）。让我们知道了GNN中的节点的状态参数应该如何更新。

RNN可以看成是一种GNN的特例，反过来说就是：GNN是广义的RNN。再比如LSTM，其中的门控机制可以看做是聚合方程，而其马尔科夫假设也可以被看做消息传递。但GNN和RNN最大的本质区别就是节点的度。在RNN中，节点的度都是2（除了头尾），而GNN的节点度就变化万千了，因此形成了特殊的拓扑结构，也正因如此，GNN才需要各种采样技术，而RNN却不需要（RNN只需要顺序遍历即可）。虽然原文没有明确的说明，但我们读完论文就能感受到。

The Graph Neural Network Model

【论文题目】:

【概述】:

【需要解决的问题】:

【这个问题为什么重要】：

【解决之后有什么好处】：

【解决问题的前提条件或者是假设】：

【解决问题的具体方法】：

【实验】：

【结论】：

【源码解析】：

【个人评价】：

Introduction to GraphNeural Networks

在我的印象中这是比较早的几篇综述文章之一。我们仅截取其中一节：第四节，Vanilla Graph Neural Networks。这一节讲道理是我最喜欢的，介绍的

【论文题目】:图神经网络介绍之图神经网络初代机

【概述】:

【需要解决的问题】:

【这个问题为什么重要】：

【解决之后有什么好处】：

【解决问题的前提条件或者是假设】：

【解决问题的具体方法】：

【实验】：

【结论】：

【源码解析】：

【个人评价】：

Neural Message Passing for Quantum Chemistry

【论文题目】：量子化学的消息传递神经网络

【概述】：化学分子可以看做是图结构，而图结构又有许多相似之处，所以可以用一种监督学习的方法来预测分子的属性，并为新药发现和材料科学做贡献。传统的监督学习方法已经取得了很好的效果，但是作者希望能够用深度学习的方法把成果推广开来。因此他们发明了MPNN框架，并希望在此框架下，各种算法变体能取得进一步的准确度，达到数据集的极限。

【需要解决的问题】：设立一个图算法的框架，并在这个框架下寻找更多更准确更快速的，用于预测分子属性的变体模型。

【这个问题为什么重要】： 快速解决分子和材料的属性预测。

【解决问题的前提条件或者是假设】：

1. 在同一种图框架下
2. 算法不受同构（例如化学中的手性）的影响
3. 算法的计算效率足够高

【解决之后有什么好处】：

1. 预测时间会下降。用DFT(离散傅里叶变换)做预测需要$10^3$量级的时间，而使用MPNN则可以降低到$10^{-2}$量级。
2. 找到更多的变体模型，这些模型可以完全准确的预测到分子属性，或者是逼近预测的极限。
3. 可以促进新药发现和材料科学。（天坑专业自救指南）

【解决问题的具体方法及实验】：

在算法方面：

• 节点之间的消息传递：

  $$m_v^{t+1} = \sum_{w \in N(v)} M_t(h_v^t,h_w^t,F^{e})$$

  上式的含义是，节点$v$的消息传递是汇聚了它自身的信息$h_v^t$以及它邻居节点的消息$h_w^t$和邻边的消息$F^{e}$。但凡能用上的消息基本都用上了。

• 消息更新的方式：

  $$h_v^{t+1}=U(h_v^t,m_v^{t+1})$$

  这里只需要说一下$U$实际上是一个状态更新函数。通常用add,mean,max.但max是不可微的，所以使用的时候要注意。

• 图表征方法（readout）:

  $$y=R(\{h_v^T|v \in G\})$$

  $y$是一个向量，它表征了整个图。

在实验数据方面，本论文在其开发的图建模环境MPNN下，通过错误率和运行时间两方面来证明MPNN框架的可行性和实用性。但是具体的数据我并没有认真研究，因为MPNN的亮点是其图建模的思想（毕竟我太菜了，也找不到比MPNN更早的相关研究了。主要是懒）。

【结论】：MPNN确实从准确率和运行时间两方面达到了理想的结果。并且实现了一些图建模的最基本要素，如：消息传递，节点和边的参数更新，图表征（readout，我翻译成图表征，因为readout指的是把一张图表示为一个向量。）

【源码解析】：MPNN确实是有一套自己的代码框架，但是我水平有限，没有看懂😂。不过MPNN的基本思想被研究者们广泛认同，被PYG（pytorch_geometric）继承，然后PYG有被OGB（open graph benchmark）所继承，所以我们来看一下OGB的源码即可😄。（torch\geometric\nn\conv\message_passing.py）

关于OGB，可以参考这篇文章

MPNN的英文文档

首先，在OGB中，我们定义MPNN的算法框架：

$$v^{t+1} = \gamma_t(v^t,\square_{u\in \mathcal{N(v)}} \phi(v^t,u^t,F^e))$$

其中，$\square$是一个可微的且组合不变的方程，比如sum,mean,max。而$\gamma$和$\phi$则是任意可微方程，如MLP（全连接）。在本文中，$\gamma$就相当于$U$或者$AGG$，$U$和$AGG$的区别仅限于运算的对象，是负责聚合和更新信息的。而$\phi$则相当于$M$，负责收集信息。

MessagePassing类内有三个主要方法：

• MessagePassing.propagate(edge_index, size=None, **kwargs):该方法的输入参数是edge_index，知道了边的编号之后，自然就知道了输入节点$v$和输出节点$u$了。该方法会在内部调用MessagePassing.aggregate和MessagePassing.update。实际上，每次采样的结果就相当于一个子图，而且这个子图还是一个二部图。
• MessagePassing.message：相当于$\phi_{\mathbf{\Theta}}$。这个方法的输入就是MessagePassing.propagate的输入，
• MessagePassing.aggregate:相当于$\square_{u\in \mathcal{N(v)}}$，
• MessagePassing.update:相当于$\gamma_{\mathbf{\Theta}}$这一部分，对每一个节点$v$进行聚合。其输入是MessagePassing.aggregate的输出。

【个人评价】：
MPNN的思想非常简单且可行：节点就是其关系的总和。简单好用易于理解，所以成为了OGB的基础层。

图上的采样方法

DeepWalk: Online Learning of Social Representations

【论文题目】：深度随机游走：社团表示的在线学习

【个人评价】： 真·随机游走。第一个使用深度优先采样的图深度学习方法。

LINE: Large-scale Information Network Embedding

【论文题目】：【LINE】大规模信息网络嵌入

【概述】：LINE使用了广度优先采样+深度优先采样

【需要解决的问题】：大规模网络节点的向量空间嵌入问题

【解决问题的前提条件或者是假设】：

从直觉的角度来说，两个有着相同朋友圈的人，其兴趣也应该接近，因此这两个人很有可能成为好朋友。从上图中的5，6节点可以看出，这两个节点有着相同的“朋友圈”，所以他们之间的向量应该较为接近。

另外，6，7的嵌入向量也应该接近，因为这两个节点是直接相连（而且关系也比较强，因为边比较粗）

根据以上两个直觉，LINE定义了两种相似度。

1. 一阶相似：类似于6，7。如果两个节点之间没有边直接相连，这两个节点的一阶相似就是0.
2. 二阶相似：类似于5，6。如果两个节点之间没有相邻的其它节点，那么这两个节点的二阶相似度就是0.

【这个问题为什么重要】：图数据是离散的。如果能把节点信息向量化，那么我们可以获得更丰富的表示信息。这些表示信息对后续任务的帮助巨大。

【解决之后有什么好处】：这种采样方法相当于NLP的pre-train。对下游任务是有很大帮助的。

【解决问题的具体方法】：

LINE的目标函数是一个由一阶相似和二阶相似共同拼凑的。

首先是一阶近似的目标函数：

1. 定义两个节点之间的概率 $$p_{ij} = \frac{1}{1+exp(-v_i,v_j)} \tag{1}$$

2. 定义两个节点之间的经验概率。这里需要说明的是，$z{ij}$ 是一个非0即1的数。因为边权的数值是不确定的，有时候很大有时候很小，这会导致梯度的大幅波动，因为方差实在是太大了。所以作者很巧妙的使用了01数值来局部归一化。所以，$Z$ 就代表了边权的数值（只能是整数），$z{ij}$ 要看两个节点间是否有边相连，有就是1，没有就是0.

   $$\hat{p}_{ij} = \frac{z_{ij}}{Z} \tag{2}$$ $$Z = \sum_{(i,j)\in E}z_{ij}$$

3. $(1)$和$(2)$代表了两个节点之间的相关性，那么我们直接联立两个方程，就可以得到一个误差值，这个误差值就代表了两个节点的一阶相似度（也可以看成是距离）。在原文中，作者使用了KL散度来计算这个距离。

   $$d(p,\hat{p}) = KL(p,\hat{p}) = \sum_{(i,j)\in E}z_{ij}\log{p(v_i,v_j)}$$

然后是二阶近似的目标函数：

根据之前对二阶近似的定义，如果想计算两个节点之间的二阶近似的目标函数，就是看看第二个节点在第一个节点的朋友圈（目标节点的全部邻居）当中的份量。

这个份量，就可以用条件概率来描述。

1. 定义条件概率

$$p(v_j|v_i) = \frac{exp(v_i \cdot v_j)}{\sum_{\mathcal{v_k \in N(v_i)}}exp(v_k \cdot v_i)} \tag{4}$$

1. 计算二阶相似度。其中，$\lambda$代表节点的权值，毕竟节点和节点的重要程度也是不一样的。同样的，$d$也是用KL散度代替。然后把$(5)$式化简一下，就能得到$(6)$

$$O_2 = \sum_{v_k\in \mathcal{N}(v_i)} \lambda_i d(\hat{p}(\cdot|v_i),p(\cdot|v_i)) \tag{5}$$ $$O_2 = \sum_{v_k\in \mathcal{N}(v_i)} z_{ij} \log{p(v_j|v_i)} \tag{6}$$

但比较拉胯的是，原文里的训练方法是分别训练，然后把两种近似情况得到的向量拼接在一起。

【实验】：

【结论】：仅从采样方法来看，LINE = deepwalk + BFS。采样的方法变多了，因此能够得到更好的效果。

【源码解析】：

这个算法的问题我个人感觉非常大（先写着，以后慢慢补充）。因为论文为了省时省力（可能是受限于当时的硬件设备），context变量本来是$v_i$的全部邻居节点，但结果却只是$v_j$的嵌入。

【个人评价】：

低情商：这个算法有问题

高情商：这个算法仍旧有很大的改进空间。

开个玩笑。实际上LINE可以看做是DEEPWALK的改进，毕竟deepwalk只是用了DFS做采样，而LINE用了BFS。但LINE的问题我个人认为有两处。

1. 在一阶相似的定义方面：我们观察公式可以发现，$p$是节点向量的内积，而$\hat{p}$是与节点之间的边权相关的量。一阶相似的目标函数是希望内积和边权尽量相同。我们现在用极端条件来验证一下：

   • 当$v_i=v_j$时，带入公式$(1)$可得：$p = \frac{1}{1+exp(-1)} =0.73$。这个误差大概是0.27

   • 当$v_i \perp v_j$时，带入公式$(1)$可得：$p =\frac{1}{1+exp(0)}= 0.5$,这个误差是0.5

   所以，我个人认为用内积来定义相似度是没有问题的，但问题出在相似度的解析方程，至少文中给出的解析方程是有问题的。另外，LINE将相似度与边权划等号，在直觉上是说得通的，但更具体的形式还要继续探索。

2. 在二阶相似的定义方面：因为在源码中，$v_j$的向量和context(也就是$v_k$，是$v_i$的全部邻域)的向量实际上都是依靠$v_j$做嵌入的，所以当前节点$v_i$的邻域信息，也就是BFS采样，并没有充分利用。如果简化来看，这种方法甚至比deepwalk还简单（LINE在极端条件下实际上就采样了一个点…也就是$v_j$）。

node2vec: Scalable Feature Learning for Networks

【论文题目】:网络的可扩展特征学习

【概述】:如何捕捉邻居节点的多样性特征一直以来都是一个难题。node2vec首次提出了一种启发式的灵活采样方法，该方法结合了DFS和BFS的精髓，并且作者认为这种采样方法能够有效的反映出节点的特性。其中的核心观点就是：

1. 邻近的节点应该相似
2. “朋友圈”相同的节点也应该相似。

【需要解决的问题】:蕴含更多更丰富信息的采样方法。

【这个问题为什么重要】：节点的向量表示在不同的采样策略下，有着不同的表示方法，而且原文中也指出，目前（2016）还没有一种通用的良好表示方法。所以，采样方法在很大程度上决定了节点向量表示学习的能力。而深度学习框架下的采样方法也几乎都是DFS和BFS，一种很自然的想法就是将二者结合。但之前的LINE算法在本质上属于拼接了DFS和BFS，而DeepWalk只有BFS，所以node2vec就搞出了启发式算法来融合DFS和BFS，作者们也认为，灵活的采样方法能够获取更加丰富的表示信息。

【解决之后有什么好处】：让节点的嵌入向量包含更多更丰富的信息，用以处理下游任务。并且可以更快更好的学习节点的嵌入表示。

【解决问题的前提条件或者是假设】：

【解决问题的具体方法】：

1. skip-gram: $$\max_v \sum_{u\in \mathcal{N}(v)} \log{p}(\mathcal{N}(v)|v) \tag{1}$$ 其中，$v$代表节点的向量。这个公式的含义就是，依靠节点$v$来最大可能的预测其周围邻居。相当于NLP中的skip-gram
2. 条件独立: $$\log{p}(\mathcal{N}(v)|v)=\prod_{u\in \mathcal{v}}p(u|v) \tag{2}$$ 有了这个假设，子图就可以按节点进行分割了。
3. 特征空间的对称性（我个人觉得，写成排列无关性更好）： $$p(n|v)=\frac{exp(n\cdot v)}{\sum_{u\in \mathcal{v}} exp(u\cdot v)} \tag{3}$$ 这个公式是说，起始点$v$和终点$n$之间的概率关系与两者之间节点的排列顺序无关。
   根据上述三个等式，最终的优化目标可以写为： $$\max_{v} \sum_{u\in \mathcal{N}(v)}[-\log{Z_u} + \sum_{n\in \mathcal{N}(u)}n\cdot u]$$ 其中： $$Z_u = \sum_{u\in \mathcal{N}(v)} u\cdot v$$

4. search bias:这是一种启发式的搜索策略。就是在搜索的过程中设置不同的转移概率$\alpha$（可以理解为一种阻力）。
   

   1. 如果节点$t$和$v$共享同一个邻居$x_1$，那么$\alpha$就是1
   2. $t$和$v$构成的边的$\alpha$是$\frac{1}{p}$

   3. 其他情况为$\frac{1}{q}$

      当然了，真正的$\alpha$还需要和边权$w{vu}$相乘，所以真正的转移概率应该是$\alpha \cdot w{vu}$。
      另外，每次采样过后，中心节点都会变更，这样才能保证采样的多样性。

【实验】：所有的实验结果以OGB为准。

【结论】：转移概率在本文中充当了胶水的角色，很好的将BFS和DFS结合在了一起。这种启发式的算法比DeepWalk和LINE这两种最优化算法要好一些。

【源码解析】：以后再补。

【个人评价】：从论文的实验结果来看，启发式确实是比最优化的采样方法要好。但更重要的信息是，不同的采样方法对结果的影响非常巨大，而且node2vec的超参$p$和$q$仍旧有讨论的空间，但更大的舞台还是设计新的采样方法。

Inductive Representation Learning on Large Graphs

【论文题目】： 大图的归纳表示学习

【概述】：之前的节点嵌入方法都是直接计算一整个较小的图，因此泛化能力差，而且对于新的节点的嵌入显得束手无策。本文采用近邻采样的方法对大图中的节点的嵌入向量进行学习。这种学习方法并非传统的直接学习节点的向量表示，而是去训练聚合器来间接学习节点的向量表示。而且学习目标不仅仅是节点的向量表示，还包括了节点的分布。这种方法速度快，效果好，对未知的节点嵌入也有较高的鲁棒性。

【需要解决的问题】：大图中的节点表示学习

【解决问题的前提条件或者是假设】：大图

【这个问题为什么重要】：节点的向量表示是下游任务的基础。不解决这个问题很难搞下去。

【解决之后有什么好处】：解决了节点向量的表示，才能为之后的任务服务。比如推荐系统，只有解决了当前用户节点的表示，才能为新用户的行为进行预测。

【解决问题的具体方法及实验】：

如图所示：

(1)表示一个节点的1阶邻居和2阶邻居，这些就是我们所要聚合的信息。

(2)表示对当前节点的信息以及它邻居的信息进行聚合。我们可以很清楚的看到，1阶聚合器和2阶聚合器是不同的，这也很好理解，毕竟你亲戚的亲戚不一定是你的亲戚。所以要区别对待。

(3)则是一个目标函数，要求当前节点去预测他的邻居以及其自身的标签。（有点类似于word2vec的CBOW步骤）

算法的伪代码如下所示：

步骤4聚合了全部的邻居信息，而步骤5则是对当前节点的状态更新。步骤7则是一个常见操作，因为不断的聚合会使节点的模长爆炸，所以需要把隐藏层的模长限定在$[0,1]$之间。这个操作就是求一个向量的单位向量。

最后是目标方程。

$$J = -log(\sigma(z_u^Tz_v)) - Q\mathbb{E}_{v_n \sim P_{n}(v) }log(\sigma(z_u^Tz_{v_n}))$$

其中，$\sigma$代表了softmax函数，$z_u$是邻居节点的向量，$z_v$是中心节点的向量。$z_u^Tz_v$代表了两者之间的内积，并用内积来代表相似度。而$P$则代表了负采样，$v_n$就是那个被负采样出来的虚假中心节点，它和$z_u$之间的内积自然会小。所以就用这样一真一假的操作让聚合器去学习。至于Q，那就是负采样的样本个数了。

【结论】：

【源码解析】：该方法的实现是较为简单的，主要就是将聚合器替换为一种带参的方程，之前提到过的四种常见算子大家有兴趣都可以挨个试一遍。（我太懒了，实际上也根本没有实践过。。。而论文的实际效果又不一定那么好，所以有空还是需要去写一遍代码的。）

【个人评价】：从直接学习转变为间接学习，可以说这个idea是可以的，反正我是想不出来。当然了，光有idea还是不够的，还必须work。我觉得GraphSAGE不仅能work还work的很好的主要原因是它的可学习参数加对了地方。因为在之前的聚合器一般都是选用mean,add等一些不带参的方程，但GraphSAGE突破了传统（虽然我也不清楚在此之前是否有人提出过这个问题）。转念一想，什么直接学习间接学习的，在深度学习里，参数的多寡是决定算法上限的最重要标准（毕竟都是拟合）。如果后来人能发现其他增加参数量的地方也一样可以发一篇好文章。

Adaptive Sampling Towards Fast Graph Representation Learning

【论文题目】：面向图表示学习的自适应采样方法

【需要解决的问题】：

1. 大规模图数据在训练时的采样问题
2. 我个人另外一个理解是：能优化期望的估计值。

【这个问题为什么重要】：因为大规模的图数据会导致内存爆炸或者运算量过大的问题
【解决之后有什么好处】：
【解决问题的具体方法及实验】：
【结论】：

以后再分类

Learning with Local and Global Consistency

【论文题目】:局部和全局一致性的学习

【概述】:这个是标签传播（LPA : label propagation algorithm） 的开山之作。文章从全局一致和局部一致两个方面分析了标签传播的算法。其优点是速度快，缺点是不准确。

【需要解决的问题】:从已标注数据到未标注数据的（半监督）学习问题。

【这个问题为什么重要】：减少标注劳动量，从而获得大量带标签数据。

【解决之后有什么好处】：未标注数据往往是容易获得的，这些未标注数据如果有了标签，就可以用于后续模型的学习，提升模型的效果。

【解决问题的前提条件或者是假设】：
The key to semi-supervised learning problems is the prior assumption of consistency, which
means: (1) nearby points are likely to have the same label; and (2) points on the same structure (typically referred to as a cluster or a manifold) are likely to have the same label.

给定一组点集$\mathcal{X}={x1,x_2,\cdots,x+_l,x{l+1},\cdots,x_n}$

以及标签集合$\mathcal{l}={1,\cdots,c}$

那么现在的目标就是从已标注数据到未标注数据的推断问题。

The keynote of our method is to let every point iteratively spread its label
information to its neighbors until a global stable state is achieved.

$\mathcal{F}$代表了一个具有非负元素的$n\times c$矩阵，矩阵$F=[F1^T,\cdots,F_n^T] \in \mathcal{F}$代表了数据集$\mathcal{x}$的一个分类，其中的每一个元素$x_i$都有一个$y_i = \argmax{j\le c}F_{ij}$的标签。我们可以认为$F$就是一个向量函数，将数据集$\mathcal{X}$映射到标签集上。$F:\mathcal{X} \rightarrow \mathbb{R}^c$

我们再定义一个$n\times c$的矩阵$Y$，$Y\in \mathcal{F}$,若$xi$具有标签$y_i = j$,则$Y{ij}=1$,其余则为0。显然，$Y$与初始标签是一致的。

算法如下：

1. 定义关联矩阵$W$,$W{ij}=exp(-\Vert x_i - x_j \Vert^2 /2\sigma^2)$ 若$i\ne j$否则$W{ii}=0$
2. 构建矩阵$S = D^{-\frac{1}{2}} W D^{-\frac{1}{2}}$,其中，$D$是一个对角矩阵，其$(i,i)$（对角）元素是$W$矩阵第$i$行的和。
3. 迭代$F(t+1)=\alpha SF(t)+(1-\alpha)Y$至收敛，$\alpha$是一个介于0，1之间的超参。
4. 记$F^{}$为${F(t)}$的极限，每一个点$xi$都被标记为$y_i = \argmax{j\le c}F^_{ij}$

我们首先在数据集$\mathcal{X}$上定义成对关系$W$，其对角线元素为零。那么我们就可以认为图$G=(V,E)$中的顶点集$V$是定义在数据集$\mathcal{X}$上的，边集$E$的权重是定义在关联矩阵$W$上。在第二步骤中，$W$的标准对角化是为了后续迭代的收敛。前两步骤和谱聚类方法完全相同。在第三个步骤中，每一次的迭代都会让顶点接收其邻居的信息，同时也保持了其自身的特征（第二项）。超参$\alpha$则代表了邻居信息与中心节点信息之间的相关程度。除此之外，信息是均匀传播的因为$S$是一个对称矩阵。最后，每一个未被标注的节点的标签会被标注为迭代过程中接收信息最多的那一类的标签。

关于收敛性的证明：

不妨设$F(0)=Y$.

迭代过程的等式可以记为：$F(t+1)=\alpha SF(t)+(1-\alpha)Y$

那么从0到$n$累加可得：

$$F(t)=(\alpha S)^{t-1}Y+(1-\alpha)\sum_{i=0}^{t-1}(\alpha S)^{i}Y \tag{1}$$

由于$0<\alpha <1$,且$S$的特征值在$[-1,1]$之间（级数收敛）（另外，$S$与随机矩阵$P=D^{-1}W=D^{-\frac{1}{2}} W D^{-\frac{1}{2}}$相似）

$$\lim_{t\rightarrow \infty} (\alpha S)^{t-1}=0 \quad and \quad \lim_{t\rightarrow \infty} \sum_{i=0}^{t-1}(\alpha S)^{i}=(I-\alpha S)^{-1} \tag{2}$$

前者是极限，后者是无穷级数求和。

所以：

$$F^* = \lim_{t\rightarrow \infty} F(t) = (1-\alpha)(I-\alpha S)^{-1}Y$$

而对于分类问题，则可以得到：

$$F^* = \lim_{t\rightarrow \infty} F(t) = (I-\alpha S)^{-1}Y \tag{3}$$

(（3）没弄明白)

【解决问题的具体方法】：

【实验】：

【结论】：

【源码解析】：

【个人评价】：

动机

为了研究NLG和NLU，我们必须要了解主流的预处理方法，以便更好的服务下游任务。

预处理语言模型：理论&架构&技巧

2013年，word2vec横空出世。在那个深度学习还未出现，caffe尚未被开发的年代，这个最早的自然语言预处理模型给人工智能带来了一些惊喜，比如【国王-男人=女王-女人】的词类比。当时的人们还不知道这项技术有何用处，受制于当时的硬件条件，在那个岁月静好，网络层很少的年代，word2vec如同种子一般深埋大地。直到14年后，预处理语言模型终于成长为参天大树，并在那个名为BERT的树干之上开花结果，令人眼花缭乱。

独热码

缺点：矩阵太大，而且极为稀疏

共现矩阵

缺点：矩阵太大，而且极为稀疏

【2003年】 NNLM:基于前馈神经网络的 N 元神经语言模型

【2013年】 word2vec

作为被大家公认的第一个预处理语言模型（）

八卦时间

word2vec的主要贡献并不是其结构，因为skip gram（预测+聚类） 和 CBOW（采样+完形填空）在传统方法中也有被用到（比如n元语法），也不是层次化的softmax（Hierarchical Softmax）和 负采样（negative sampling），毕竟这些写不成公式的方法都属于trick。
主要贡献是【词类比】。

首先来解释word2vec中的各项技术：

1. CBOW：continuous bag of words 连续词袋模型。可以理解为：用一个固定大小的窗口对语料库进行采样，并对采样后的样本做一个“完形填空”，用窗口中的周围词去预测中心词。
2. skip gram：得到了预测到的中心词之后，再反过来用中心词去预测周围的词。从直觉上来说，同一个窗口中的词汇应该在某种程度上更加近似，所以skip gram就有点聚类的味道了。
3. Hsoftmax: 可以先看一下softmax的函数图像 如果直接预测，会分母太大，直接爆炸，因为少说也是大几千的token量。但如果分开来看，每一句都给一个softmax，那就不会产生爆炸，有点像激活函数和BN。
4. 负采样：就是预测标签中的一个子集。因为整个标签集太大了，即使是现在的硬件水平做起来也很慢。

那为什么词类比成了word2vec的主要贡献了呢？个人认为是它达到了一个【情理之中，意料之外】的效果。

到目前为止，预训练模型都充满了令人怀念的古早味。那时的NLP三四层是比较正常的，超过十层都属于“巨型结构”。

【2015】Semi-supervised Sequence Learning

可以说是预训练语言模型的开山之作，明确了“pretrain”的概念，提出了预训练模型的“fine-tuning”概念。虽然这篇文章放在今天看来，它的思想已经让我们感到理所当然，它的效果也没有那么地让人感觉惊艳，但是放在那个历史时刻里，它就像一盏明灯，为人们照明了一个方向。

论文的主要内容如下：

1. 利用自回归（AR）对一个句子进行逐词预测。
2. 利用自编码方法（AE）对句子进行映射再重构。

他们明确提出了，这两种算法可以为接下来的监督学习算法提供 “pretraining step”，换句话说这两种无监督训练得到的参数可以作为接下来有监督学习的模型的起始点，他们发现这样做了以后，可以使后续模型更稳定，泛化得更好，并且经过更少的训练，就能在很多分类任务上得到很不错的结果。

众所周知，RNN模型虽然对时序数据建模很强大，但是因为训练时需要 “back-propagation through time”， 所以训练过程是比较困难的。Dai 和 Le 提出的预训练的方法，可以帮助RNN更好的收敛和泛化，而且在特定业务上不需要额外的标注数据，只需要收集成本很低的无标注的文本。而且这些文本与你的特定业务越相关，效果就会越好，他们认为如此一来，这种做法就支持使用大量的无监督数据来帮助监督任务提高效果，在大量无监督数据上预训练以后只要在少量监督数据上fine-tuning就能获得良好的效果，所以他们给这篇论文取名为 “半监督序列学习”。

【2016年】context2vec: Learning Generic Context Embedding with Bidirectional LSTM

双向LSTM + mask

这篇文章提出的idea是学习文本中包含上下文信息的embeddings。由于词在不同上下文可以有歧义，相同的指代词也经常在不同上下文中指代不同的实体。所以NLP任务中很重要的就是考虑每个词在其上下文中所应该呈现的向量表达方式。从摘要看，这篇文章的主要贡献，是它使用了双向的LSTM可以从一个比较大的文本语料中，有效地学到了包含上下文信息的embeddings，在很多词义消岐，完形填空的任务上都取得了不低于state-of-the-art的效果。同时他们提到，之前的研究有把上下文的独立embedding收集起来，或是进行简单的平均，而没有一个比较好的机制来优化基于上下文的向量表达。所以，他们提出了context2vec ，一个能够通过双向LSTM学习广泛上下文embedding的非监督的模型。

从这一年之后，NLP进入了大力出奇迹的时代

【2017年】ELMO

更大的双向LSTM。

具体而言，ELMO的底层输入推荐使用已经学好的静态词向量比如Glove等，向上接两层的双向LSTM作为特征提取器，最终以语言模型作为训练任务进行学习。学好之后，每一个词会得到三个向量（底层，第一层拼接LSTM，第二层拼接LSTM），ELMO告诉你只要下游任务用到WordEmbedding的时候，就用产生的三个向量进行加权平均，其中的权重需要在新任务中进行学习。而这种方式也称为Feature-based Pre Training。

相应的评价指标也都做到了在当时的SOTA，并比其他的高出5-25个百分点。这么好的效果和清晰地思路也使得该论文获得了NAACL2018最佳论文。不过，现在看来ELMO也有缺点，具体而言：

1. LSTM抽取特征的能力远弱于Transformer
2. 拼接方式双向融合特征融合能力偏弱。

【2018】GPT & BERT

GPT最主要的贡献就是证明了tranformer结构比RNN更好。

除了以ELMO为代表的这种基于特征融合的预训练方法外，NLP里还有一种典型做法，这种做法和图像领域的方式更为契合，我们一般将这种方式成为基于“Fine-tuning”的二阶段训练。
GPT：ImprovingLanguage Understanding by Generative Pre-Training 其实就是Transformer的decoder，一种采用了masked self-attention的训练方式。GPT总结而言有以下几点：

1. semi-supervised learning：无监督pre-train+下游有监督fine-tune
2. multi-task learning：损失函数为预训练阶段languagemodel目标函数+ λ * 有监督softmax损失
3. 12个decoder：masked-attention（12个multi-head+768维）+ point-wise FFN（3072维）+ Adam + warm-up + GELU

BERT刷榜

RoBERTa，屠榜神器

1. 更大的训练集:16GB-> 160GB
2. 更长的训练时间，6W美金训练一次。
3. 静态Mask -> 动态Mask
4. 去除了NSP

ALBERT

1. 词嵌入向量参数的因式分解
2. 跨层参数共享 （feed-forward network、attention、all）
3. NSP 预训练任务-> Sentence-order prediction (SOP)
4. 去掉dropout、LAMB优化器、更大的batch-size
5. N-gram mask

ERINE，更加疯狂的mask训练

1. Basic-Level Masking：和BERT的方式一致，简单的随机mask单独的单词
2. Phrase-Level Masking：对命名实体进行全词Mask，包括人名、地名、机构名等
3. Phrase-Level Masking：对短语进行全词的Mask，如 a series of等
4. 引入多源数据语料：百科类，新闻资讯类、论坛对话类数据并引入DLM（Dialogue Language Model）来训练模型。

XLNET

本文最后介绍的就是xlnet了。
因为BERT的训练中有mask占位符存在。如果一个原本有4000词的文本，在训练的时候就会变成4001词（至少）。这就会造成三个问题：

1. 训练与使用不一致，因为在使用阶段是没有mask占位符的。
2. 多出来的mask占位符会影响整体性能。
3. mask的训练假设是，被mask掉的词是统计独立，但显然不是。
4. 因为BERT的mask占位符在训练阶段有15%，这也就是说，BERT的训练效率只有15%。

xlnet希望解决上述问题。
根据组合数学，一个由n个词汇组成的句子会产生n！个语言模型。xlnet利用了一个巧妙的方式在训练阶段学习到了这n！个语言模型。

Single Image Haze Removal Using Dark Channel Prior

In this paper , we proposed a simple but effecient image prior - dark channel
prior to remove haze from a single input image.The dark channel is a kind of
statistics of haze free out door images.It is based on a key observation -
most local patches in haze-free outdoor images contains some pixels which
have very low intensities in at least one color channel.Using this prior
with the haze imaging model,we can directly estimate the thickness of the haze and recover a high quality haze-free image.Results on a variety of
outdoor haze images demonstrate the power of proposed prior.More over , a
deepth map can also be obtained as a by-product of haze-removal.

In this paper,we proposed a simple but effecient image prior - dark channel
prior to remove haze from a single input image.The dark channel is a kind of
statistacs of haze free outdoor images.It is based on a key observation -
most local patches in haze-free outdoor images contains some pixels which
have very low intensities in at least one color channel.Using this prior
with the haze imaging model,we can directly estimate the thickness of the
haze and recover a high quality haze-free image.Results on a variety of
outdoor haze images demostrate the power of proposed prior.

吐槽

本篇笔记实际上是GSN的草稿。

图论的基本概念

边与两端点称为关联的(incident)

与同一条边关联的两端点或者与同一个顶点关联的两条边称为相邻的(adjacent)

两端点相同的边称为环(loop)

有公共起点并没有公共终点的边称为平行边(paralled edges)

无环并且无平行边的图称为简单图。

设G为无向图，$x \in V(G)$的顶点度(vertex degree)定义为G中与x关联边的数目，记为$d_G(x)$

1.4 导出子图和支撑子图

1.5 路和连通
图$D$(或$G$)中连接顶点$x$和y且长度为k的链W，记为

p32最后一段：割边和割点

4.3 LIMITATIONS
Though experimental results showed that GNN is a powerful architecture for modeling struc-
tural data, there are still several limitations of the vanilla GNN.
• First, it is computationally inefficient to update the hidden states of nodes iteratively to get
the fixed point. The model needs T steps of computation to approximate the fixed point.
If relaxing the assumption of the fixed point, we can design a multi-layer GNN to get a
stable representation of the node and its neighborhood.
• Second, vanilla GNN uses the same parameters in the iteration while most popular neural
networks use different parameters in different layers, which serves as a hierarchical feature
extraction method. Moreover, the update of node hidden states is a sequential process
which can benefit from the RNN kernels like GRU and LSTM.
• Third, there are also some informative features on the edges which cannot be effectively
modeled in the vanilla GNN. For example, the edges in the knowledge graph have the
type of relations and the message propagation through different edges should be differ-
ent according to their types. Besides, how to learn the hidden states of edges is also an
important problem.
22 4. VANILLAGRAPH NEURALNETWORKS
• Last, if T is pretty large, it is unsuitable to use the fixed points if we focus on the repre-
sentation of nodes instead of graphs because the distribution of representation in the fixed
point will be much more smooth in value and less informative for distinguishing each
node.

写在最前面的逻辑导图

如果看晕了就可以回过头看一下这个，整理思路。

主线剧情

1. 句子可以用一个联合概率分布来描述
2. 但是联合的不好算，我们用贝叶斯全概率公式改写成条件概率分布
3. 条件概率分布是链式的，可以用递归的方法计算
4. 自然而然的得到seq2seq结构
5. 针对seq2seq的固有问题，提出attention解决方案
6. 绕了一圈又突然发现attention就可以直接求解联合分布
7. 深度学习的哲学1：不好算的东西都交给神经网络去拟合，我们用attention算法来拟合联合概率分布。
8. 深度学习的哲学2：大力出奇迹，如果一层attention不能拟合联合分布，那就叠100层。
9. 深度学习的哲学3：能用显卡解决的问题，就不要用算法。几十层attention堆叠的BERT就这么被搞出来了。而且BERT的原理十分简单（相对于传统的机器学习），但是效果又出奇的好，是NLP的里程碑。
10. 既然有了求解联合分布的BERT，那么文本生成任务实际上就可以看成是全概率公式的逆向运用，用条件概率（也就是不完整的输入）去求联合分布（完整的文本）
11. 整 上 花 活：当我们不再满足于单个句子的联合分布的计算的时候，比如对话或者长文本生成，这时候，针对更长的文本的联合分布的计算，我们就需要用mask方法了。虽然这个方法的名字叫做【掩码】，但实际上它的作用相当于胶水。

什么是文本生成？

文本生成在计算机领域指的是用算法生成可读的文本(让代码说人话)，所谓的人话就是自然语言，这东西极其复杂，因此与自然语言相关的任务大都是非常棘手的。

文本生成的局限性

1. 模型的自然语言理解和语义分析。
2. 长程依赖和全局一致
3. 融入知识图谱

以上这三条摘抄自一片综述性文章，都是NLP中的困难问题，当然也是研究的重点方向。

经典的Seq2Seq

原理

Seq2Seq模型是一种基于RNN的序列学习模型，其主要的工作原理是求解条件概率。(不要太在意下标，问题不大)

$$p(x_0) = p(x_0|x_1,x_2,x_3,...,x_n)$$

例如给定一个句子：

今天晚上去吃麻辣【】

我们已经给定了“今天晚上去吃麻辣”这几个字符，也就是对应的$x_1$至$x_n$。那么现在，我们的任务就是求解【】内的内容。所以，今天晚上究竟是吃麻辣小龙虾还是麻辣香锅，这个问题就是神经网络所需要解决的重点了。

对应实际的问题，我们可以将公式写成如下形式：

$$sentence = \{x_0,x_1,x_2,x_3,...,x_n\}$$

其中，sentence是由$n$个单词组成的有序集合。只有当这些单词有序的时候，整个句子才会产生意义。虽然我们不知道自然语言的结构形式，但至少我们可以从概率的角度先进行考虑：

$$P(sentence) = P(x_0,x_1,x_2,x_3,...,x_n)$$

但问题是上式右边是一个联合分布，求解困难。当然，如果加入一点马尔科夫的思想，这个联合分布讲道理还是可以计算出来的，也确实有这种算法，那就是n元语法：

n元语法((n-gram grammar)建立在马尔可夫模型上的一种概率语法.它通过对自然语言的符号串中n个符号同时出现概率的统计数据来推断句子的结构关系.当n=2时，称为二元语法，当n = 3时，称为三元语法.

我们可以退而求其次，继续将公式改写成如下形式：

$$P(sentence) = p(x_0)p(x_1|x_0)p(x_2|x_0,x_1)\cdots p(x_n|x_0,x_1,\cdots,x_{n-1})$$

这样，我们就得到了一个贝叶斯视角下的句子建模了。上式是计算可行的，其中$n$并非趋近于无穷，因为一个句子总是有结束的时候。甚至当我们不开心的时候可以指定$n=1$，这就对应了一个字的回复。

那么应该如何计算呢？
我们可以递归的计算：先求第一个字的概率，然后将答案作为输入，输入神经网络中再计算第二个字的概率。。。这就是递归神经网络（RNN）了。

随着硬件计算能力的进步，现在的RNN一般都是结合n元语法的思想，每次的输入都是n个字符，然后去求第n+1个字符。

这时候，我们就可以自然而然的得出seq2seq结构了。

seq2seq的结构

encoder-decoder框架如上图所示，中间的那个“语义编码c”实际上相当于链接encoder-decoder的桥梁。我们很自然而然的觉得问题不大，但实际上这其中却蕴藏着一定的不合理：在训练阶段，模型有着明确的目标。但在测试阶段，模型就没了目标。就好比读书的时候老师会告诉你要学什么，但是工作之后就基本再也没有人管你了，唯一关心你（工作进度）的人就是产品经理了。 这个现象（笔者也是最近才听说）被称为Teacher-Foring，确实很形象。当模型没有了训练阶段的压力之后就会放飞自我。例如tensorflow官网的一个教程，用LSTM生成文本，以下是第4000轮的结果。尽管有些短文本已经能读的足够通顺，但是整体上还是拉胯。

究其原因，最主要问题是RNN的长程依赖问题，形象的说就是“记不住”和“记得太死”。当然后来的LSTM和GRU都在一定程度上缓解了这个问题，但还是治标不治本。这里就需要提到一个概念：Exposure Bias

Exposure Bias 是在RNN（递归神经网络）中的一种偏差,即 RNN 在 训练(training) 时接受的标签是真实的值(ground truth input)，但测试 (testing) 时却接受自己前一个单元的输出(output)作为本单元的输入(input)，这两个setting不一致会导致误差累积error accumulate,误差累积是因为，你在测试的时候，如果前面单元的输出已经是错的，那么你把这个错的输出作为下一单元的输入，那么理所当然就是“一错再错”，造成错误的累积。

Exposure Bias给我的感觉实际上是这样的：

工程师：马冬【梅】

RNN:马什么梅？

工程师：马【冬】梅

RNN：什么冬梅？

工程师：最后一遍，马冬梅，记住了吗？！

RNN：记住了记住了。

工程师：马什么梅？

RNN：马化腾

那有的小朋友就会问了，为啥呢？

为了回答小朋友的这个问题，我们可以设想，如果现在机器预测出了一个【小】字，那你以为最终结果一定会是【小龙虾】吗？当然不一定，一旦变成【小汉堡】，整个模型的level就拉胯了。

其根本原因是递归问题都存在长程依赖和局部最优问题。

1. 长程依赖：RNN是递归求解的序列模型，因此当序列（本文我们就单指文本序列）足够长的时候，最开始的几个字就可能会被遗忘，因此不构成训练的依赖。就比如你还记得这篇文章的最开始是那几个字吗？所以，再回头看安娜·卡列尼娜的那个文本生成模型，长句基本都是很拉胯。
2. 局部最优问题：我们以【麻辣小龙虾】为例，对于【麻辣小】这三个字来说，【龙虾】是他的最优解，因为【麻辣小】+【龙虾】构成了我们爱吃的麻辣小龙虾。但是对于【小】这个字来说，有可能【汉堡】是他的最优解，毕竟曾经的小汉堡几乎全网尽人皆知。。。但是【麻辣小汉堡】就有点意义不明。这个例子就是说，如果模型每一次都选择它所认为的“最优解”，最终有可能每一步的选择都是“正确”的，但得到的结果却是错误的。

虽然我们可以用Beam-Search来解决搜索问题，但beam-search只能说是缓解了局部最优的问题（因为自然语言并不是一个最优化的问题，但目前来看我们很难找到其他的解决方案，所以我们就需要先解决局部最优化的问题）。顺着这个思路，我们也可以加长RNN的长度和深度，毕竟大力出奇迹。

其实，写到这里的时候我就突然想起来我国科学家当年试东风1号导弹，（忘记了什么原因）导致航程不够，无法在靶点爆炸。当时的大部分方案都是加入更多的燃料，但这又会增加弹体重量，那不就飞不动了吗。唯独一个年轻人的方案是抽出燃料，理论上也确实可行（大佬就是大佬）。最后还真的成功了。

所以，考虑到beam-search和大力出奇迹的方案都是增加计算量，我们可以反向思考，比如用mask的方法盖住几个词。这个方法苏神已经帮我们做了，可以去看他的博客。

我们到底在干什么？

说了这么多，我们到底在解决什么问题？

继续观察这个公式：

$$P(sentence) = p(x_0)p(x_1|x_0)p(x_2|x_0,x_1)\cdots p(x_n|x_0,x_1,\cdots,x_{n-1})$$

只看右边：

$$p(x_0)p(x_1|x_0)p(x_2|x_0,x_1)\cdots p(x_n|x_0,x_1,\cdots,x_{n-1})$$

每一个$p(\cdot)$都代表着一个字，如果将这些字看做节点，实际上我们就是在寻找一个“最优”的路径把他们都链接起来。当然了，如果你回过头去看这张图：

就会发现，“桥梁”只有一条。

众所周知，一条路只能链接两个城市。如果写成公式，那就是：

$$p(x_0)p(z)p(x_1|x_0)p(z)p(x_2|x_0,x_1)\cdots p(z)p(x_n|x_0,x_1,\cdots,x_{n-1})$$

$p(z)$就是神经网络所要拟合的参数之一(对应于上图的“语义编码c”)，它告诉了句子应该以什么样的概率转移为另一个概率。

单一的$p(z)$显然是不充分的，【马】这个字显然是不能以相同的概率转移为马冬梅或者马化腾或者马云。

所以，为了造更多的“桥”：

参考博客

注意力机制就应运而生了。

注意力机制

$$self\, attention = Softmax(\frac{QK^T}{\sqrt{d}})V$$

其中的QKV同一个东西的三种投影。所以，如果不看softmax一项，整个公式实际上是在求非归一化的联合概率分布。

假设上图就是self attention的计算结果，每一行每一列的和都不是1，所以没有归一化。但从感觉上来看，这东西长的可真的像联合分布的计算结果啊！我们随便上网找一张联合分布的图片:

简直神似啊！

仔细一想…好像又绕回了最初的原点。
我们来分析一下：

1. 早期的NLP探索者们用n元语法模型去求解联合分布，但是受制于当时的硬件条件，所以n元语法模型的探索也都止步在个位数。
2. 后来出现了word2vec，滑动窗口实际上相当于n元语法中的n，但窗口大小依旧没有突破个位数。
3. 神经网络大行其道，RNN递归求解条件概率，直逼联合分布。

但是随着seq2seq问题的研究（主要是当年研究自动翻译的那些学者，著名的attention公式就是从Transformer的研究中诞生的），大家突然发现，直接用attention去求联合分布不就OJBK了吗？？？

然后就出现了不讲武德的BERT，虽然算法层面没有太多的进步，但是从深度学习的哲学水平上来看，这波BERT在大气层。（一部分算法工程师的梦想是用数学的方法去解决复杂的问题，但是另外一批算法工程师直接对复杂问题重拳出击）

mask方法：建造跨海大桥

我们知道，自然语言是有其结构信息的，而问题在于我们对自然语言的结构知之甚少。从小学开始我们就要一直学习语法，定语从句，倒装句之类；将语法结构应用于自然语言处理也确实是NLP的最初之路。但这种路子很快就被证明是走不通的，因为我们不知道如何描述结构。反观BERT的成功，再怎么成功，其数学基础也是建立在统计学之上的，至少我们知道联合概率分布是如何计算的。现在的问题是，我们既不知道结构如何描述，也不知道结构如何计算。

所以，mask是一种通过表象去计算自然语言结构的主要方式。mask虽然被称为掩码，但其主要的功能是【补全】，就好像英语考试中的完形填空，在补全句子信息的过程之中也学习到了句子的整体结构，做的多了，自然而然的也就形成了“语感”。这个语感，实际上就是脑子里对自然语言结构的建模。

在之前的叙述中，我们所关注的都是单个句子的联合分布。秉承深度学习的哲学，我们可以用mask的方式对多个句子重拳出击，甚至说如果你开心(有显卡)，你也可以同时对多篇文章一起重拳出击。

具体做法就是把多个句子当成一个句子，每一个句子的句尾加入一个特殊的标记，比如$[cut]$，然后多个句子顺序拼接，直接输入神经网络进行计算。

GAN

gan的主要问题是：

1. 训练困难，有可能因为梯度爆炸而导致模式崩塌。（这个训练困难的问题我不确定还是否存在，因为看到的论文是在18年发表的，而18年的时候又提出了f-gan，其中的共轭算法已经基本避免了这个问题）
2. 多样性不足：具体表现为GAN文本生成模型总是会生成一些短小的句子，从而可以获得更高的分数。（但这个问题我感觉也已经基本解决了，那就是依靠mask方法做长文本输入。）

强化学习

强化学习目前给我的感觉仍旧是牛刀杀鸡。我们来简单的讨论一下强化学习中的两个概念：收益和动作空间。（这两个问题也许是强化学习在自然语言处理方面效果不显著的主要原因）

首先，收益相当于深度学习中的损失函数，因为在数学上，前者是求最大值，后者是求最小值，没有本质上的区别。对我来说，也许不同的概念会帮助人们产生不同的理解，但这种名称上的改变并没有给算法带来本质上的不同：因此我就可以在损失函数前面加上一个符号，然后将这个负损失定义为收益。

其次，动作空间。这个东西就有点像几十年前人们精心设计的特征一样。如果是对于一些简单问题，那当然是非常有效；但对于自然语言这种极其复杂的问题来说，动作空间就显得有点“狭小且破碎”，因为人工定义的动作空间目前还不能完全描述自然语言。反向思考，如果动作空间能够几乎完整的描述自然语言的特性，那我为什么不去手工写正则表达式呢？

文本生成的关键在于MASK

用mask来取代动作空间

着手建模

依旧是基于公式：

$$p(x_0) = p(x_0|x_1,x_2,x_3,...,x_n)$$

个人认为，这个是最好的文本建模方法了，公式中既包含了结构信息（贝叶斯全概率公式）又能够体现语义信息（条件概率），是非常好的生成模型。

但是好东西也是不容易获得的，条件概率的计算量可以达到无穷，力大砖飞的BERT系列甚至就可以看做一个非常强悍的条件概率计算模型。如何降低条件概率的计算复杂度问题仍旧是一个非常值得研究的问题。

好了，言归正传。首先给定一个$sentence$作为输入

$$P(sentence) = p(x_0)p(x_1|x_0)p(x_2|x_0,x_1)\cdots p(x_n|x_0,x_1,\cdots,x_{n-1})$$

文献时间

第一篇

An Auto-Encoder Matching Model for Learning Utterance-Level
Semantic Dependency in Dialogue Generation

编码器和解码器都是LSTM，作者希望在隐变量空间中将上文信息与下文信息对齐，如大图中的中间那一层所示。

对齐的方式是L2范数。其实改成别的散度也是可以的。

生成效果如图所示。

第二篇

CommonGen: A Constrained Text Generation Challenge for Generative Commonsense Reasoning

这篇文章在文本生成的任务中引入了人类的常识。

其作用相当于引入了知识图谱，这就相当于在求联合分布的时候给定了一些标签，标签相当于条件，在某种程度上相当于求解条件分布。虽然文章的任务是做图片描述，但有一些地方还是值得我们参考的。 给定的输入为若干个单词，目标是生成一句通顺的人话。 作者认为完成这个任务的条件主要有两个： 1. 词与词之间的关系 2. 合理的语法 作者首先构造了一个“概念的集合”，这个集合中的概念都是一些基本的名词和动词： $$\{c_1,c_2,...\} \in \mathcal{X}$$ 以及一个句子集合$\mathcal{Y}$，里面装的都是人话。模型的目的就是去学习$\mathcal{X} \rightarrow \mathcal{Y}$的映射。 那么这个映射应该怎么去学习呢？ ***对比学习 *** 首先我们构造训练集$\mathcal{T}$，$\mathcal{T}$是$\mathcal{Y}$的一个子集，但是我们需要给$\mathcal{T}$加上一个限制条件:所有的$\mathcal{T}$ 都必须包含$\mathcal{X}$中的若干个元素

举例来说（本节第一张图片所示），训练集可以长成这个样子：
x1 : {苹果，袋子，放}
t1 ：{一个女孩儿把苹果放在她的袋子里}
x2 ：{苹果，树，摘}
t2 ：{一个男人从树上摘了一些苹果}
x3 : {苹果，篮子，洗}
t3 ：{一个男孩从篮子里拿了几个苹果去洗}

好了，现在我们有了三个训练样本。里面包含了实体，以及隐藏在句子中的实体关系。在训练阶段，假设输入的概念集合为:{梨，袋子，放}，【梨】这个词在训练集中从来没有出现过，那么就可以认为【鸭梨】=【苹果】，在{袋子，放}的条件下

第三篇

Adversarial Ranking for Language Generation

图中,G是生成器生成的文本，H是人话。RANKER是一个打分器，给所有的输入样本打分，本质上是一个discriminator.打分方法本质上还是对比学习的方法，请参考第二篇。

具体的做法是，针对相同的$x \in \mathcal{X}$,挑选出一些包含x的人话H，然后用这些x生成样本G，将${H,G}$输入到打分器中排序，并根据排序来设计loss.

第四篇

Generating Text through Adversarial Training using Skip-Thought Vectors
文本是离散的，所以不适合用GAN来训练。虽然我们可以用嵌入的方式得到词向量，但在输出端还是需要把词向量转化成离散的字，这样才能得到一句文本。就比如我们假设”你好”=1.0,但是”1.01”是什么，谁也不知道。

所以本文作者打算用稠密的句向量来做。所谓的稠密就是连续，与离散相对的概念。
在介绍这篇文章之前，我们要先看看什么是Skip-Thought。
一种传统的句表示学习方法——Skip-Thought Vectors

然后，原文作者将文本转化为稠密的句向量输入到GAN中做训练，输出的稠密向量用Skip-Thought 的解码器解码一下就是句子了。

第五篇

Learning Neural Templates for Text Generation

这篇文章虽然是说用神经网络学习模板，但实际上已经是在践行强化学习了。如果将模板想象成动作空间，那就容易理解一些了。

第六篇

Long Text Generation via Adversarial Training with Leaked Information

文章作者认为，训练GAN的时候，目标文本序列作为控制信号是处于最后一个阶段的，而生成器所生成的隐变量序列中是包含结构信息和语义信息的，而控制信号作为离散的序列只是在最后阶段与隐变量交互信息。什么意思，就是说稠密的隐变量只有在argmax运算之后才能与文本计算距离，而argmax却大量的损耗了隐变量所蕴含的信息。
那么作者做了一件什么什么事情呢？那就是把控制序列的最后一个信号，也就是文本的最后一个字作为额外的输入信息，以及判别器的编码，输入生成器中，。
一般的GAN，生成器和判别器之间只有在BP阶段才有信息交互。

模型整体结构如下图所示。