0和1

前言 工业界的图规模都非常大，少说也是上千万的顶点+上亿的边，单机训练不现实，必须借助多机分布式训练。然而目前主流的图训练框架PyG、DGL对图的多机分布式训练支持都不太好。工业界好像阿里的Euler、百度的PGL可以支持分布式训练。今天介绍一下亚马逊DGL针对分布式训练所做的优化。 摘要 GNN广泛应用在推荐、搜索、风控等领域，在这些领域，图的规模往往非常大，有数以亿计的顶点和万亿的边。为支持大规模图的分布式训练，本文提出了DistDGL，它能以mini-batch的方式在多机上进行分布式训练。DistDGL基于DGL框架，它将图数据分布在多台机器上，并基于数据分布，将计算也分布在多台机器上（owner-compute rule）。DistDGL以同步更新的方式进行训练。为了减小分布式训练的通信开销，DistDGL使用一个高效、轻量的图分割算法对图进行分割，在分割时设计了多个负载均衡约束，使得每个分割的子图达到较好的负载均衡。此外，为了减小跨机器的通信，DistDGL在每个子图中保留了halo nodes（正文会介绍到），并且使用了稀疏embedding更新策略。这些优化策略使得DistDGL在分布式训练时能达到较好的高并行效率和内存可扩展性。实验结果表明，在分布式训练时，随着计算资源的增大，DistDGL的训练速度可以线性增长。在16台机器组成的分布式环境中，DistDGL仅用13秒就可以完成1亿节点+30亿边的一个epoch的训练。DistDGL是DGL的一部分，已开源在：https://github.com/dmlc/dgl/tree/master/python/dgl/distributed。 简介 GNN很有用，但是现实世界中的网络都很大，比如Facebook的社交网络、Amazon的用户商品关系网络等。 GNN分布式训练的难点： GNN中每个训练样本（顶点）不是独立的，是相互依赖的，比如为了训练顶点A，必须采样A的邻居，随着GNN层数的增大，采样的邻居数目呈指数上升。而CV、NLP中每条样本是相互独立的。 GNN的多机分布式训练的通信数据主要是图数据（顶点和边，及其属性），而CV、NLP的分布式训练的通信数据主要是网络参数、梯度等，需要通信的数据类型不同，导致CV、NLP的分布式训练优化技术无法直接迁移到GNN的分布式训练中。 此外，神经网络大多采用同步更新的分布式训练策略（难道不是异步？），因此需要尽量做到不同机器或者worker的负载均衡。由于图的特殊结构，不同顶点的度差异很大，即不同子图的负载差异很大，所以如何实现GNN训练时的负载均衡，也是一个难点。 背景介绍 GNN 以消息传递的方式来解读GNN，每一层GNN可以用下面的公式来概括。\(\mathbf{h}_v^{(l+1)}\)和\(\mathbf{h}_v^{l}\)分别表示节点\(v\)在第\(l+1\)层和第\(l\)层的向量表示。\(f\)表示节点\(v\)和每个邻居\(u\)计算消息；\(\oplus\)表示邻居聚合函数；\(g\)用来更新节点表示。 作者将GNN的参数分为两部分，一部分是网络参数，即上面的\(f\)、\(\oplus\)和\(g\)。另一部分是节点本身的embedding参数，对于transductive模型来说，节点本身有embedding，故有这部分参数；但对于inductive模型，节点本身没有embedding参数，节点的embedding表示是通过网络参数生成的。 为了区分这两部分参数，作者将网络参数称为稠密参数dense parameters，所有dense参数在每个mini-batch都需要被全部更新。作者将顶点本身的embedding参数称为稀疏参数sparse parameters，每个mini-batch只需要更新该batch涉及到的顶点的稀疏参数即可。 Mini-batch training GNN进行mini-batch训练时的基本流程如下： 从训练集中随机采样N个顶点，这部分顶点称为target vertices 对每个target vertex随机采样最多K个邻居顶点 对每个target vertex，通过聚合其邻居的信息得到target vertex的表示 上述流程是一层GNN的训练过程，如果GNN有多层，则邻居采样的过程会递归进行下去。 方法 DistDGL分布式训练框架 DistDGL的核心可以用上面的图来表示。DistDGL包含三个组件： Trainer，即图中的GNN Training Component，其中放大的GNN Training Component只是右边3个之一的放大图而已。Trainer主要是用来训练的，即进行前向传播和反向传播的。 Sampler，即图中的Sampling Component，用来采样邻居的。 KVStore，即图中的KVStore Component，用来存储顶点和边的特征，以及相应的embedding。 对照背景介绍中的mini-batch training过程，DistDGL的训练过程如下： Trainer随机采样N个顶点作为target vertices Trainer向Sampler请求采样target vertices的邻居 Trainer向KVStore请求target vertices及其邻居的属性信息 Trainer开始分布式训练，并使用AllReduce方式同步更新dense参数（网络参数）；并将sparse参数（embedding）存储到KVStore中 主要优化点 图分割及负载均衡 这是DistDGL最核心的优化点。为了实现高效的分布式训练，DistDGL首先使用METIS图分割算法把图分割成多个子图，不同子图分布式存储在不同机器上；然后把不同子图的计算也分配到存储数据的机器上。做到数据在哪里，计算就在哪里（owner-compute rule），最大程度利用数据和计算的局部性，减小网络通信。 如下图所示，METIS算法以最小割的方式分割图网络，即如果每条边都有不同的权重的话，METIS希望分割的时候切割的边的权重之和最小，由此可以尽量把有密切连接的节点分割到同一个子图中。 我没仔细研究METIS算法，我理解METIS还需要一个约束，即需要分割成多少个子图，或者每个子图最多有多少个顶点之类的。要不然什么都不分割，直接输出全图，则割最小是0。 如果某一条边被分割了，其所连的两个顶点被分割到两个不同的子图中了，称这样的顶点为HALO vertices（通俗理解就是边缘点）。如果需要采样HALO顶点的邻居，则需要跨子图进行采样，涉及到网络通信。为了避免网络通信成为瓶颈，DistDGL会在两个子图中都保留HALO顶点的另一端顶点。在这种情况下，如果只涉及到HALO顶点的一跳采样的话，不需要跨子图通信。DistDGL通过冗余存储HALO顶点，以减小网络通信。由于GNN网络的邻居采样一般只会有2-3跳，所以这种策略应该能避免大部分跨子图通信。 由于同一批数据只需要在开始训练时做一次分割，相对于漫长的N个epoch训练时间来说，分割图的时间开销被分摊了，可以忽略不计。 分割完图之后，DistDGL把不同子图分配到不同机器上。在训练的时候，由于trainer、sampler和KVStore需要互相交换数据，为了提高数据交换效率，DistDGL把属于同一个子图的trainer、sampler和KVStore分配到了同一台机器上，则三者之间的通信可以直接通过共享内存的方式进行内存拷贝，大幅减小了网络通信带来的延时。 如下图所示，同一台机器上的Trainer、Sampler和KVStore是共享内存的。 文中还提到在METIS分割图的时候，增加了很多约束条件，以达到负载均衡的目的。我理解默认METIS在进行分割的时候，可能只保证不同子图的顶点数大致相同，在这个约束下去最小化割。然而子图的顶点数相同，并不代表子图的负载也相同，还涉及到子图中边的数目，不同类型顶点的数目分布等等。因此DistDGL在METIS子图分割时还增加了很多约束条件，使得分割的子图在训练的时候尽量达到负载均衡。 分布式KVStore DistDGL把顶点和边的属性特征及embedding存储在分布式KVStore中，DistDGL开发了自己的分布式KVStore，而不是使用现成的比如Reddis，原因是更方便自定义功能，比如把属于同一个子图的顶点、边、特征存储到同一个机器上，优化了网络传输，实现稀疏embedding的异步更新等。 分布式Sampler Trainer训练和Sampler采样是并行进行的，简单理解就是，Trainer在训练当前Epoch数据的时候，Sampler就已经在异步采样下一个Epoch的数据了，充分利用计算资源，实现流水线作业。类似的，局部采样和远程网络RPC通信也可以overlap“同步”进行，使得局部采样感受不到远程通信的等待时间。 ...

前言 最近的工作涉及到图神经网络，打算系统学习下这方面的内容。首先搜集了相关的教材，发现市面上的教材大多数是罗列论文的形式，不太适合初学者入门。后来找到了斯坦福CS224W这门公开课，打算入坑，一是之前学习过斯坦福CS224N，感觉不错；二是CS224W这门课的老师是GraphSAGE的作者Jure Leskovec，有大佬背书错不了。 CS224W主页：http://web.stanford.edu/class/cs224w/ Winter 2021版主页：http://snap.stanford.edu/class/cs224w-2020/ Winter 2021版视频：https://www.youtube.com/playlist?list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn，Jure Leskovec是斯洛文尼亚人，英语不是很标准，建议打开YouTube的字幕。 背景介绍 图（Graph）是描述实体（entity）和关系（relation）的一种通用语言形式，它由节点（vertex或node）和连接节点的边组成，很多数据类型都可以用图的形式来描述。 图1 图及其应用实例 目前常见的图有两类： 第一类是网络（network），也称为自然图，例如： 社交网络，全球70亿人形成一个大网络 通信网络，例如通过电话、邮件、交易等形成的网络 生物医药网络，例如基因、蛋白质之间形成的网络 大脑中的成千上万的神经元形成的网络 第二类是通过抽象表示形成的图，例如 人工组织形成的信息网络、知识网络 软件中的代码调用形成的网络 分子网络、场景图、基于粒子的物理模拟等 现有的机器学习工具箱主要针对图像、文本和语音，对图的机器学习处理工具相对较少，因为图是不规则的数据，难以处理。对图的处理主要有以下难点： 图不是欧几里得数据结构，没有固定的大小和拓扑结构 图上的节点没有固定的顺序，也没有参考点，是去中心化的 图会随着时间动态变化，并且图中常常会融合多模态信息 本课程的两个重点： Deep learning in graphs，即图上的深度学习算法 Representation learning，即图表示学习，将图中的节点嵌入到一个低维稠密向量中，使得网络中相似节点的embedding距离接近 本课程的主要内容包括： 传统方法：Graphlets，Graph Kernels 节点嵌入方法：DeepWalk，Node2Vec 图神经网络：GCN，GraphSAGE，GAT，Theory of GNNs 知识图谱：TransE，BetaE 图上的深度生成网络 图在生物医药，科学和工业上的应用 图机器学习应用 图可以有很多应用场景，这些应用可以分为节点水平的（nodel level）、边水平的（edge level）、子图水平的（subgraph level）和图水平的（graph level）。下面逐一举例： Node-level：节点分类（node classification），例如预测节点的属性。节点回归？例如AlphaFolde使用GNN预测每个氨基酸在三维空间中的位置坐标，从而预测蛋白质的结构。感觉和GNN关系不太大吧？具体得看论文了。 Edge-level：链接预测（link prediction），预测两个节点之间是否存在边。例如在推荐系统中，预测user是否会购买item等。另外还可以用于预测药物的副作用，例如任意两种药组合吃，是否会产生副作用，产生哪种副作用，都是针对边的任务。 Sub-graph level：地图导航，预测预期到达时间（ETA）。DeepMind和Google Maps合作的一个工作，很有意思：https://www.deepmind.com/blog/traffic-prediction-with-advanced-graph-neural-networks。简单来说，把每条路分段（supersegment），每段表示成一个点，一条路的相邻段（点）连边，交叉路口的段（点）连边。通过GNN的消息传递，一条路的拥堵信息，可以传递到相邻的路。很自然的想法，也符合实际情况，比如在这条路拥堵了，司机可能就会走相邻的路，进而会影响相邻的路的ETA。问题是，GNN对图很敏感，不同地区、地段的路网图差异很大，有的路网小，有的路网大，因此不同training run之间的方差很大。一开始想到用lr decay来缓解。后来使用MetaGradients让模型自动调整学习率。使用多个loss，多目标学习防止过拟合。 Graph-level：例如新药发现：节点是原子、边是各种键，生成一个graph，就是一种新的复合物。物理模拟：动态图，节点表示粒子，有属性比如速度、动量，然后下一个时刻有新的位置，不断进化变化，类似RNN，可以模拟出粒子的动态变化过程。 图2 图机器学习应用场景 图的表示方法 构成图的基本要素包括顶点集合N和边集合E，可以用\(G(N,E)\)来表示一张图。 根据边是否有方向，可以将图分为无向图和有向图，无向图即图中的边没有方向，有向图即图中的边有方向。 对于无向图G，每个顶点的度就是该顶点所连边的数目，由于一条边连接了两个顶点，贡献了2个度，所以所有顶点的平均度数=2E/N。 对于有向图，顶点的度可分为入度和出度，如图3所示，顶点C的入度为2，出度为1。所有顶点的平均入度=平均出度=E/N。如果某个顶点的入度为0，则称该顶点为源点，例如顶点G；如果某个顶点的出度为0，则称该顶点为槽点（sink），就像水槽一样，只进不出；如果某个顶点的入度和出度都为0，则称该顶点为孤立点。 图3 图的表示方法和顶点的度 ...

这篇论文严格来说是一个实验报告（report），作者分析了使用word2vec训练得到的词向量的特点，提出使用词频和词向量的模长来衡量词的重要性。 整篇论文的核心就是上面这张图。作者将arXiv上理论高能物理范围内的论文都下载下来，提取所有论文摘要，并使用word2vec默认参数进行训练，得到所有词的词向量。使用词向量的模长和词频绘制了上图。 由图可知，当词频小于30时，随着词频的增大，词向量的模长也增加；但当词频大于30后，词频继续增大时，词向量的模长呈减小趋势。作者分析发现，对于词频比较小的词，这些词所在的上下文相对固定，而word2vec正是通过词的上下文来学习词向量的，因此在word2vec训练的时候，这些词的词向量的更新方向相对固定，所以随着词频的增大，这些词的词向量在某个固定方向走得越远，故向量模长越大。但是对于词频很大的词，这些词很可能是多义词（比如may即可以做名词也可以做助动词），则在word2vec训练的时候，词向量会频繁往不同方向上更新，虽然词频很大更新了很多步，但由于分散在了多个不同方向上，故离初始点的距离并不远，即模长并不长。常见的停用词就是后者的典型代表。 因此，作者提出同时使用向量模长和词频来衡量词的重要性，如果这两个值都很大，则说明这个词很重要，而且很可能是某个子领域的专用词，只出现在特定的上下文中，类似于IDF很大。

时隔多年，我发现我写的和我一起构建搜索引擎系列是我的博客中访问量最高的内容，截至目前该搜索引擎的GitHub项目已经收获了上百个Star和Fork。这几天我又回顾了一下这个项目，并进行了部分的更新和修改，以及将该搜索引擎部署到了我的个人网站上，以便展示和外网访问。以下是我将搜索引擎部署到个人网站上的截图，大家可以访问 http://news.bitjoy.net/ 进行测试。 下面分别介绍新增的爬虫，对打分的修改和部署到服务器上的过程。 新增爬虫。我们之前是抓取搜狐新闻的数据，但是这个页面自从2018年之后就没再更新过，难道是被很多爬虫爬了之后停更了吗。经过多方查找，我发现中国新闻网的滚动新闻上的新闻数据特别全，从2008年至今，每天的新闻都有，而且新闻类型丰富、格式规整。于是，我重现写了一个爬虫程序：spider.chinanews.com.py，运行该爬虫会自动从网站上爬取最近5天的新闻数据，并整理成xml格式。 在编写爬虫的过程中，有两点建议。一是一定要捕获异常，因为爬虫在运行的过程中会遇到各种异常情况，比如突然断网了、某个URL无效、连接超时等等，如果不捕获异常，爬虫很容易崩溃停止，有可能爬了一整天都前功尽弃了。二是要控制抓取频率，宁愿让爬虫抓取频率慢一点，也不要让网站封了你的爬虫，一旦被封，要解禁估计要等好几个小时，还不如爬的时候慢一点，可以一直爬；我的策略是，遇到异常时，无条件睡眠10分钟，因为异常很可能是服务器察觉到爬虫然后拒绝响应了；还有就是每抓取到500条新闻后睡眠3分钟。在这两条策略下，我的爬虫运行一天一夜都没问题，可以连续抓取几万条新闻。 修改打分。之前在介绍检索模型时，我设计了一个基于新闻热度的打分公式，该公式的热度是综合了BM25相关性打分和新闻发布时间的一个函数。后来我在测试时发现由于BM25打分可能是负数（在df很大时），会导致计算热度打分时对数异常。于是，我把热度公式中的对数函数更换为了sigmoid函数，新的热度公式如下： $$hot_{score}=k_1*sigmoid(BM25_{score})+\frac{k_2}{t_{now}-t_{news}}$$ 线上部署。Flask是一个基于python的很轻量的web服务，之前我们通过本地http://127.0.0.1:5000/访问该搜索引擎服务，现在我把它部署到线上，和我的这个博客在一个VPS中。线上部署的步骤如下。 首先是准备新闻数据。由于我的VPS性能很弱，所以我只爬了约2500条新闻，并构建好了数据库等文件。 然后是准备服务器环境，如果是性能比较弱的VPS，建议安装Minicoda，否则直接安装正常版本的Anaconda。有了conda环境之后，就按之前的步骤安装lxml、jieba、Flask。此时，在web文件夹运行main.py后，可以通过服务器的内网访问，但外网还不能访问。 为了让外网也能访问，需要在运行Flask应用时指定host=”0.0.0.0″，此外还需要指定端口，如port=5000。此时，可通过服务器的ip:port的方式访问到Flask服务。 你也可以申请一个域名，将域名指向你的服务器，并设置port=80，此时就可以通过域名直接访问Flask服务了。 由于我的VPS上已经运行了Nginx服务，搭建了两个wordpress博客，所以我希望能够通过子域名的方式访问我的搜索引擎服务。比如直接访问 http://news.bitjoy.net/ 就可访问搜索引擎。此时，我们需要在DNS设置上将news.bitjoy.net这个二级域名指向服务器IP（我用的是DNSPOD），然后我们可以用通过news.bitjoy.net:5000的方式访问搜索引擎。但我希望只输入域名访问，省掉输入端口的操作。如果只输入域名news.bitjoy.net，默认访问的是服务器的80端口，但80端口已经给了Nginx的wordpress。为了实现输入news.bitjoy.net，访问的是5000端口，需要对Nginx进行设置，告诉它从 news.bitjoy.net:80进来的流量都转给 news.bitjoy.net:5000。为此，需要在Nginx的配置文件中增加一个虚拟主机，我的VPS上的文件路径是/usr/local/nginx/conf/vhost，这个文件夹下存放了所有网站的Nginx配置文件。新增一个配置文件news.bitjoy.net.conf，表示需要对访问 news.bitjoy.net 的网站的设置。内容如下，就是告诉Nginx，从news.bitjoy.net:80进来的流量，都交给localhost:5000处理。这里的localhost:5000就是ip:5000，前面我们已经对Flask进行了设置，所以访问ip:5000就可以访问我们的搜索引擎服务了。 server { listen 80; server_name news.bitjoy.net; location / { proxy_pass http://localhost:5000; } } 综上所述，流量走过的路径是这样的： 访问news.bitjoy.net 等价于访问news.bitjoy.net:80 Nginx将流量转发给localhost:5000 localhost:5000等价于ip:5000 Flask收到流量，开始处理 新增了Nginx的配置文件后，使用命令service nginx restart重启Nginx，此时就可直接通过二级域名访问Flask了。最后，可以使用nohup命令运行Flask并将其置于后台，这样关于服务器的远程连接后，Flask依然会运行。

今天是该课程的最后一节课，介绍了使用未标注数据集进行NLP学习的方法，以及谈了谈NLP未来的发展方向。下面主要介绍使用未标注数据集进行NLP学习的方法。 我们知道，在机器翻译领域，特别缺少标注好的语料集。目前世界上有上千种语言，但用得最多的只有十几种。对于那些使用人数很少的语言，它们和其他语言之间标注好的翻译句子就更少了。如何使用少量标注集，甚至不用标注集，就能实现机器翻译功能，是NLP领域一个很有前景的发展方向。 之前的很多工作使用pre-training来提高机器翻译模型的性能。具体方法是，先在源语言和目标语言的语料集上分别训练一个语言模型，这是无监督的，这个语言模型可以学到不同词的含义。然后在翻译模型中，用源语言的语言模型初始化Encoder权重，用目标语言的语言模型初始化Decoder权重。使用pre-training的模型相比于不使用pre-training的模型的BLEU大概有2分的提高。 Pre-training的问题是，由于预训练是在两种语言上独立进行的，两种语言在预训练期间没有交互过程。 下面的Back-Translation比较有意思。比如我们要训练一个英语到法语的翻译器，初始化的时候让模型随便从英语翻译成法语。同时，训练一个法语到英语的翻译器，把上一个翻译器输出的法语翻译成英语。有点像练功的时候左右互搏，也有点像AlphaGo自己教自己下棋，随着训练的进行，两个模型的翻译能力都得到了提升。 当然这有一些问题，如果两个模型一开始都一无所知，则可能前一个模型的输出是随机的，后一个模型的输入是随机的，模型根本学不到任何知识，无法收敛。所以更好的做法是，有少量的标注数据，两个模型先在标注数据上学到一个比较差的模型；然后用这个比较差的模型左右互搏，相当于可以粗略的标注一部分新数据；然后又在标注数据上训练；如此循环往复。实验结果表明，使用Back-Translation和大量无标注数据集之后，翻译模型的性能有大幅提升。 Back-Translation要求我们还是需要少量的标注数据，用来启动左右互搏的过程。那么如果有两种语言X和Y，我们没有X和Y的任何翻译好的句子pair，但依然想翻译它们，怎么办。这时候，可以先从简单的单词翻译做起。在训练X和Y各自的词向量时，可以把它们的词向量映射到同一个空间，则空间中相近的词的含义也相近。对于X中的一个词x，只需要在词向量空间中选与x最接近的Y中的词y，则y可以作为x的翻译。这种把多种语言的词向量统一对齐到一个空间之后的词向量称为跨语言的词向量，也就是说从这个空间中取一个词向量，虽然它的含义是固定的，但可以转换成任意一种语言的具体的词。 那么，关键问题就是怎样把X和Y的词向量对齐。我们知道word2vec有一个很好的特点就是，它训练出来的词向量能够保持比较好的空间结构。举例来说，对于X中的词x和Y中的词y，即使它们的含义很接近，但如果直接把x和y放到同一个空间中，它们的距离可能还是比较大，因为X和Y的词向量坐标系可能就不一样。但是，对于X中的两个词x1和x2，如果它们分别对应Y中的两个词y1和y2，则在X空间中，x1和x2的距离应该与Y空间中y1和y2的距离相近，也就是说两个空间的整体结构是一样的。如下图所示，X和Y对齐的过程就是找出它们的变换矩阵W。由于我们只希望将它们的坐标系进行变换对齐，并不想改变里面的数据分布，所以变换矩阵W最好是正交的。 学习矩阵W的过程也很有意思，这里介绍了一种对抗学习的方式。有一个生成器，用来生成矩阵W。有一个判别器，它想要区分一个词向量是Y中的词向量，还是X中的词向量经过W变换得到的。起初，由于X和Y的空间分布不同，W也是随机的，判别器可以很容易地区分Y和WX。但是随着对抗的进行，W越来越准，最后WX和Y重合了，此时判别器傻傻分不清楚，它只能随机猜，有50%的几率猜对。所以学习矩阵W的过程就是让判别器懵圈的过程。 上述是非监督的词与词的翻译，怎样由此得到非监督的句子与句子的翻译呢？ 我们首先使用上述的跨语言的词向量，然后使用相同的encoder-decoder来编码和解码两种语言。解码的时候，设置一个标志位，告诉decoder要把目标含义用哪种语言表达出来，就是下图的<Fr>标签。 然后有两个训练目标，第一个目标是对源句子进行微小的打乱，然后让encoder恢复原来的句子。第二个目标是使用上文提到的back translation进行左右互搏（所以好像还是需要少量标注集？）。 这种方法有效是因为输入的词向量是跨语言词向量，输入一个英文句子就相当于输入了一个法文句子。又因为使用的encoder是相同的，所以英文句子在进行第一个目标训练时，隐含学到了将法语翻译为英语的能力。 上述的非监督词与词、句子与句子的翻译，只有在源语言和目标语言比较像的情况下才能取得比较好的效果，比如英语、法语、德语比较像，可以用。但英语和土耳其语差别比较大，这种非监督方法的效果就比较差。语言像不像涉及到很多方面，比如语法结构、句子结构、用词顺序等等。

今天介绍AI的偏见，本质上，AI的偏见由人类的偏见导致。 看到成熟的黄颜色的香蕉，我们不会说这是黄颜色的香蕉，我们只会说这是香蕉，而如果看到未成熟的青色的香蕉，我们会特别说明这是未成熟的香蕉，或者说这是青色的香蕉。所以我们通常说香蕉时，其实暗含了它是黄颜色这个属性。 原型理论（Prototype Theory）说的就是这个意思，原型理论认为，我们在定义事物，并且给事物分类时，把这类事物中最常见的状态或实体定义为这一类的原型（Prototype）。同属于这一类，但具有不同特性的实物，只需要对原型增加修饰词来说明即可。比如香蕉这个例子，成熟的黄色的香蕉就是香蕉这一类别中的原型，它具有常见香蕉最典型的特征，而未成熟的香蕉最大的区别是颜色，所以我们可以用青色的香蕉来表示这是未成熟的香蕉的意思。 那么原型理论会对AI造成什么影响呢？由于原型是一类事物中的典型代表，人们在描述这类事物时，往往会省略原型的基本特征，而会重点描述某个具体事物的有差别的特征。这就导致不同事物出现在人类报道中的频率并不能反应事物真实发生的频率。 比如下面的例子，对于凶杀案，只要出现了，人们很可能就会报道，但对于眨眼睛，人们却很少报道。主要是因为眨眼睛是人类这个原型的基本特征，是众所周知的，而谋杀往往是少数人的特征，这个特征和人类原型是有显著差别的，所以人们在报道时反而更倾向于报道谋杀案，而不是眨眼睛。但事实上，每个人几乎每分钟都会眨眼睛，眨眼睛的真实频率远远大于凶杀案出现的频率，但相比于眨眼睛，人们更关注凶杀案，所以报道的凶杀案的数量远多于眨眼睛的数量。这就是人类在报道中出现的偏差，这种偏差反应了人类处理信息的方式以及人类对不同事物的关注程度。而AI模型是从数据中学习特征，由于人类报道的偏差，AI很可能会学到凶杀案比眨眼睛更常见这种荒唐的知识。 下图是常见的机器学习流程，在最开始的收集数据并建立标注集的过程中，会引入很多Human biases，包括上面提到的Reporting bias，这里就不具体介绍其他bias了。由于在整个pipeline的输入端就引入了bias，导致bias也跟着网络前向和反向传播，导致整个网络也是bias的，这个效应被称为Bias Network Effect。 一些可能的解决方法。比如去掉带有偏见的数据；评价模型在不同子类上的性能，有点类似于分开过滤的思想；对一批数据集，使用多任务学习等。

在开始今天的内容之前，给所有AI炼丹师的建议： 简化模型，使用最简单的词袋模型 使用很少的数据集进行训练和调试，比如就用10个样本，确保模型能够在10个样本上过拟合 确认模型没问题之后，增加模型的复杂度 画出训练集和测试集上的错误率变化曲线 如果一切都符合预期的话，增加L2正则和Dropout 搜索更优的超参数组合 今天要介绍的内容是成分句法分析（Constituency Parsing）。如下图是CS理解语言的两个极端，左边是bag of words，即词袋模型，把句子中的词完全独立出来，不管词与词之间的关系。右边就是对句子进行严格的成分句法分析，明确每个词在句子中充当的成分和依赖关系。本节课要讲的内容就是成分句法分析。 我们知道，我们的语言可以通过递归的方式表达含义，比如多个单词可以组成一个短语，多个短语又可以组成更长的短语，如此递归进行下去。类似的，单词在组成句子成分时也可以是递归的，比如短的名词短语NP可以组成长的NP，一级一级往上抽象，形成一个树形的句子成分结构。把一个句子转换为这样一个树形结构的过程就是成分句法分析的过程。 一个很简单的方法就是贪心的方法。对于一个句子，如下图所示的“The cat sat on the mat.”，对于任意相邻的两个词，它们可能组合成一个新的短语表达一个更完整的含义。那么，组合哪两个相邻的词呢？我们可以对所有相邻的两个词的词向量，输入到一个神经网络中，算出它们能组合成一个新的含义（新词）的概率（打分），以及这个新词的词向量。在所有组合中取打分最高的组合，把这个组合确定下来。比如下图中，The和cat组合后新的词的打分是最高分3.1，所以第一步把The cat组合起来，形成的新词的词向量是[5,2]。于是，就用[5,2]代替原来的The和cat，成为一个新词，和剩余的sat、on、the、mat.组成一个新的句子，再重复刚才的操作，直到建成一棵树，得到根节点。通过这种方法构建了一棵TreeRNN，训练的过程也是误差反向传播，各种求导。 贪心方法是最简单的成分句法分析的方法，后续针对这个方法有诸多改进，由于本人对这方面不感兴趣，本博客就不展开介绍了，感兴趣的可以去看这门课的视频。

今天介绍NLP中的多任务学习。 我们知道预训练和参数共享在CV中很重要，很多模型都会在ImageNet上预训练，然后迁移到具体的任务中进行微调。这种方式能够成功的原因是很多CV任务几乎都是以分类为基础任务，分类相当于CV的积木（building block），所以在ImageNet上训练的CNN分类模型迁移到其他CV任务中能起到很好的提升效果。 NLP中虽然也有一些预训练模块，比如预训练词向量，然后用到具体的NLP任务中，但也仅仅是将词向量作为下游模型的输入。在NLP中，并没有一个基础模型（包括模型的结构、权重等），能把整个基础模型迁移到下游任务进行微调，现在都是针对不同的问题设计专门的网络结构，比如POS、NER、NMT等，处于不同任务各自为政的局面。 在NLP中，一个统一的多任务基础模型可以很方便地进行模型迁移、模型部署，并且对这个基础模型的不断改进，可以不断提高下游模型的性能，有可能达到持续学习、持续提升的目的，而如果每个新的子模型都重新学习的话，相当于利用不到基础模型长期学习到的知识。 但是，NLP领域有很多任务，比如序列标注、命名实体识别是一类；对整个句子的分类是一类；还有就是seq2seq的机器翻译、自动摘要等，要怎样将这些不同的任务统一到一个模型中呢？ 可以把所有NLP任务统一成QA任务。如下左图所示，机器翻译转换为QA任务就是问这个句子翻译成另一种语言是什么句子，句子情感分类就是问这个句子表达的是积极还是消极的含义等等，所以所有NLP任务都可以转换为QA任务。PPT中列出了10个NLP任务都可以转换为QA任务，所以这个统一的基础任务相当于十项全能选手（decaNLP）。 设计这样一个十项全能的NLP模型，需要满足如下三个条件。1. 必须对十项任务一视同仁，也就是喂给模型的数据不能包含这条数据具体是哪个任务，不能告诉模型这条数据是要做NMT，另一条数据要做QA等。2. 模型也不能包含针对不同任务的特殊模块，模型必须学会自己辨别不同的任务类型，并且进行内部切换，执行不同的操作。3. 此外，模型还应具备执行这10个任务之外的任务的能力，即zero shot learning。 如下图是这个多任务QA模型的一个全貌。首先给一个上下文Context，然后给一个问题Question，最后模型输出答案。输出答案的时候，每次产生一个词，这个词可能来自Question、Context、或者Vocabulary，所以有一个指针开关，指向这个词可能的来源分布。 模型细节如下图所示，基本上是以前学过的模块，这里只是把它们组合起来了。 输入：固定词向量GloVe和charCNN，然后用bi-LSTM进行编码（Initial Encoding），注意这个bi-LSTM是Question和Context共享的，共享一套参数。输出就是Question和Context的每个词的隐藏层特征向量，图中Question有3个词，所以Initial Encoding后面有一个3*4的矩阵，3行就表示Question中的3个词，Context有4个词，也是类似的。 Coattention：以Question为例，Question自己的bi-LSTM输出经过一个attention，然后拼上Context的bi-LSTM输出再过一个attention，所以相当于Question和Context进行了co-attention。Context的也类似。 Transformer：Coattention出来后经过一层bi-LSTM、两层Transformer、再经过一层bi-LSTM，得到Question和Context最终的编码。这里的bi-LSTM就是Question和Context独立的了。 输出：Question和Context的Final Encoding输出又经过Attention，综合Question、Context和Vocabulary得到输出词的分布。 在训练阶段，PPT底部还提供了Answer，供误差反传。 收集的10个数据集，虽然不同任务的评价指标不同，但他们的值理论上都在0~100之间，所以模型总的得分是10个子任务各自得分的累加和。 性能表如下，看起来在大多数任务上，针对该任务单独训练的模型比Multitask模型的性能要好，但是在QA Zero shot relation extraction（QA-ZRE）任务上，Multitask具有比较大的优势。 训练技巧。不同的训练方式可能对模型的性能产生影响，这里介绍两种方式，一种是Fully joint，另一种是Anti-Curriculum。Fully joint，有10个不同的数据集需要训练，训练的时候，从每个数据集中抽一部分数据出来，组成一个batch进行训练，而不是依次训练第一个、第二个数据集这样子。Anti-Curriculum，训练的时候先训练难的任务，比如先在机器翻译上训练，再在句子情感分类上训练，因为情感分类任务相对简单，如果先在这上面训练的话，很容易达到局部最优，到时候就很难爬出来再针对机器翻译训练了；而如果先在更难的机器翻译上训练的话，得到泛化能力更强的模型后再在情感分类上训练就容易得多了。仅仅是训练方式的不同，Anti-Curriculum比Fully joint的测试得分会有所提高。 但是多任务模型的性能依然弱于单任务模型，发现主要在机器翻译数据集上，多任务模型的性能较大地差于单任务模型，可能是因为机器翻译的输出词大多数不在Question和Context中，而是在Vocabulary中。作者近期又有很多改进，使得多任务一个模型的总性能已经很接近多个单任务模型的性能总和了。 最后，愿景，希望把decaNLP变成NLP的ImageNet-CNN模型，以后大家的模型都可以基于decaNLP进行fine-tune和改进。

今天介绍的内容是指代消解（Coreference Resolution）。指代（mention）是指句子中出现的名词、名词短语、代词等，指代消解就是把指向同一实体（entity）的指代聚类到一起的过程。比如下面的两句话，蓝色的词就是很多的指代，需要找出来哪些指代是指向同一个实体。比如Barack Obama、his、He都是指奥巴马。 下面的例子是比较简单的情况，事实上，在真实的语言中，情况更加复杂，比如有些指代可能表示多个实体。比如“他们”，可能同时指代了“小明”和“小王”，这种指代对于现在的NLP模型来说比较难，暂时不考虑。 指代消解有很多应用场景，比如知道代词的含义之后，能更好地理解全文，进而能更准确的进行机器翻译，另外，在对话系统中进行指代消解能产生更正确的回答句子。 指代消解主要有两个步骤。第一步是指代识别（mention detection），即找出句子中所有的指代，这一步相对简单。第二步才是进行真正的指代消解（coreference resolution），这一步比较难，也是本节课的主要内容。 指代（Mention）是指句子中的一个短语（span），它可以是代词、也可以是命名实体、还可以是名词短语。指代识别的方法有多种，比如词性标注（POS）、命名实体识别（NER）、语法分析器（parser）等。 指代识别虽然相比于指代消解更简单，但也不是那么简单，它也有它自己的一些难题。比如下面列出的几个例子其实就不是指代，但用POS、NER等方法有可能把它们找出来，导致找出过多的指代（over-generates）。 一个简单的方法是，指代识别阶段尽量保召回率，保留所有找到的可能是指代的词，都参与后期的指代消解。如果一个指代没有找到它的共同指代（coreference），则说明这个指代是孤立的（singleton mention），有可能是指代识别阶段找到的不是指代的词，直接把它扔掉即可。 指代消解发展至今，经历了四种不同的方法，分别是Rule-based、Mention pair、Mention Ranking和Clustering。下面分别介绍每一种方法。 1976年Hobbs提出了基于规则的朴素算法，被后人称为Hobbs算法。该方法有9个步骤，包含了很多规则，非常繁琐，这里就不具体介绍了。Hobbs算法虽然是基于规则的，但在当时取得了不错的效果，现在也常常作为该领域的baseline模型。但是因为该方法是基于规则的，有很多指代消解没法解决。比如下图的两组例子，它们的句子结构完全相同，但指代不同，基于规则的Hobbs算法如果正确消解了第一个句子的指代，则肯定无法正确消解第二个句子的指代。 很明显，要想同时正确消解两个句子的指代，必须像人一样理解句子的含义。所以，指代消解也可以作为图灵测试之外的实验，用来测试AI的智力。如果AI能100%准确完成指代消解，AI的智力也就达到了人类的水平。 比较简单的Mention pair的方法。该方法把指代消解问题转化为一个二分类问题。从左到右遍历句子，每找到一个指代，就把它和前面找到的每个指代作为一个pair，问分类器这个pair是否指代同一个实体，如果是的话，就把它们连起来。二分类的损失就是交叉熵。很简单的一个模型。 该模型在测试的时候，设定一个概率阈值，比如把所有概率超过0.5的指代pair都连起来，然后所有连在一起的指代作为一个聚类。如果一个指代不与任何其他指代连接，则它可能不是一个指代。这种方法有over-cluster的风险，即万一有一根线连错了，则会导致原本属于两个cluster的所有指代归为一个类。 Mention pair模型的不足：对于很长的句子，可能会找到很多指代，而一个指代的先行词（antecedent）往往只有一个，但mention pair方法却把它和它前面的所有指代都pair进行指代消解。比如下面的例子，最后的he明确的指代是紧邻它的前一个Nader，但却需要把he和前面的4个指代都pair进行消解，无形中增加了计算量。可能的解决方法是只让模型预测一个先行词，也就是mention ranking方法。 Mention ranking的方法。每个指代同时和前面所有指代打分，用softmax归一化，找出概率最大的先行词，添加一条连边。注意需要添加一个NA节点，因为有的指代可能第一次出现，前面没有先行词，或者这个指代根本就不是一个真正的指代。 Mention ranking在训练时的损失函数如下：i：对于每一个指代；j：看看其前面的所有指代，最大化i所指代的j的概率\(1(y_{ij}=1)p(m_j,m_i)\)。 测试的时候与mention pair类似，把有边连的指代聚类到一起。 前面的内容都是假设我们计算好了任意两个指代是coreference的概率，那么，如何来计算这个概率呢？主要有三种方法，分别是Non-neural statistical classifier、Simple neural network和More advanced model using LSTMs, attention。下面分别介绍这三种方法。 A. Non-neural statistical classifier。统计机器学习方法，抽取每个指代的各种特征，然后用机器学习分类器来计算两个指代是coreference的概率。这里面的特征包括人称、性别一致性，语义相容性等等，如下图所示。 B. Neural Coref Model。输入是候选先行词和当前指代词的词向量，还需要加入一些额外的特征（Additional Feature），也就是上面统计机器学习方法里用到的一些特征。中间是FFNN，即全连接网络，最后输出两个指代是coreference的概率。 C. End-to-end Model。end2end模型是目前指代消解的SOTA模型，它把指代识别和指代消解两个任务融合到一起，用一个模型来解决。 它的网络结构如下左图所示。由于该模型同时完成了指代识别和指代消解两个任务，所以它需要枚举句子中任意两个词之间的span是否是一个指代，以及这个指代与其他指代是否是coreference的关系。 具体来说，对于每个词i，输入网络中的是这个词的词向量以及charCNN词向量拼接起来的向量。然后送入bi-LSTM中，提取bi-LSTM两个LSTM的隐藏层向量，拼接起来作为词i的特征向量\(x^*\)。枚举包含词i的起始位置START(i)和终止位置END(i)，由起始位置到终止位置构成一个span，假设这个span可能是一个指代。一个span由向量\(g_i\)表示，它包含4个部分，分别是：span的起始和终止位置的特征向量\(x^*_{START(i)}\)和\(x^*_{END(i)}\)，包含这个span的起始和终止位置的特征；这个span的attention表示向量\(\hat{x_i}\)，提取这个span表示的核心信息，比如the black cat中cat是核心信息；以及一些额外的特征\(\phi(i)\)。 一个span的attention表示向量\(\hat{x_i}\)计算公式如下右图。span中每个词的特征向量经过全连接网络FFNN，得到一个attention打分，softmax归一化得到归一化的attention打分分布，最后加权平均起来。 ...

今天要介绍的内容比较多，但都是概述性的内容，主要了解自然语言生成领域的进展。 Section 1: Recap LMs and decoding algorithms 之前已经讲过什么是语言模型，语言模型就是给定句子中的一部分词，要求预测下一个词是什么。形式化表述就是预测\(P(y_t|y_1,…,y_{t-1})\)，其中的\(y_1,…,y_{t-1}\)就是目前已知的词，\(y_t\)就是要预测的下一个词。 条件语言模型是指除了已知\(y_1,…,y_{t-1}\)，还给定了\(x\)，这个\(x\)就是提供给语言模型的额外的信息。比如机器翻译的\(x\)就是源语言的句子信息；自动摘要的\(x\)就是输入的长文；对话系统的\(x\)就是历史对话内容等。 需要提醒的是，语言模型在训练阶段，输入Decoder的是正确的词，这种方法被称为Teacher Forcing，即不论上一步的输出是什么，都强制给这一步输入正确的词。而如果在测试阶段，Decoder的输入是上一步的输出。 在机器翻译那期的博客中（CS224N（1.31）Translation, Seq2Seq, Attention），我们曾提到过在测试阶段，语言模型的Decoder有两种策略，一种是Greedy search，另一种是Beam search。Greedy search是指当前步的输入是上一步输出中概率最大的词。而Beam searh是指不但保留概率最大的词，还要保留概率在Top-k的词，那么在每一个时间步，都会有k条路径，最后选一条概率最大的路径。 那么，Beam search中保留的Top-k到底取多少合适呢？当k=1时，Beam search退化为Greedy search，产生的句子可能会不够自然，甚至难以理解。增大k会使得产生的句子的全局概率更大，读起来会更通顺一些。但是k的增大也会带来一些问题，比如：计算量增大；对于NMT任务，k的增大会导致翻译出来的句子更短，BLEU得分更低；对于对话系统，k的增大会导致产生的句子过于“安全”和“通用”，也就是和当前对话没有太大关系但又比较通顺的句子。 比如下面右图的例子，k=1时，回答和对话有点关系，但句子语法有问题；k=6时，句子很同时，但感觉答非所问。 事实上，除了Greedy search和Beam search，还有其他的decoding方法。下面是两种基于采样的decoding方法。 Pure sampling：每个时间步t，根据softmax输出的概率分布进行采样，来决定t时刻最终输出的词。Top-n sampling：只在概率top-n的词中采样，相当于对Pure sampling的概率分布进行truncate。两种方法都是单路径的，不像Beam search那样保留多条路径。由于两种方法都是通过采样决定输出，属于随机算法，所以每次运行算法输出都不一样，可增加句子的多样性，比较适合于对话系统。 还有一种可以改变语言模型输出概率的方法，就是Softmax temperature，带温度的Softmax，如下图所示。当t越大，分布变得越扁平，削弱了大和小的差别；t越小，则分布变得越尖，大的越大，小的越小。配合不同的decoding算法，可以控制产生句子的流畅度、平庸度、或者新奇度等。 以下是语言模型的decoding算法小结。 Section 2: NLG tasks and neural approaches to them 自然语言生成是一类生成新文本的任务，包括机器翻译、自动摘要、对话系统（聊天机器人）、写作机器人、看图写作等。下面对其中几个任务进行简单的介绍。 自动摘要的定义是，给定长文本x，要求生成短文本y，y能概括x的主要内容。自动摘要又分为x是单文档或多文档两类。 （左图）自动摘要的一些数据集。Summarization：根据长文本写一个短句子作为长文本的摘要，就是常规意义的自动摘要。Sentence simplification：把复杂的句子转换为简单的句子，通常转换后的句子比源句子短，主要是换成更简单易懂的词，用简单的句子结构替代复杂的句子结构等，比如把新闻转换为儿童容易读懂的新闻。 （右图）两种自动摘要的策略对比。Extractive summarization是指摘要的句子从原文中提取；Abstractive summarization是指使用语言模型生成新的句子作为摘要。前者类似于从原文中高亮某些关键句子，后者相当于用笔创作出新的句子作为摘要。 前神经网络时代的自动摘要大多数是Extractive summarization，是一个pipeline，很复杂，可能会用到各种不同的算法。 自动摘要的评价指标ROUGE。ROUGE和BLEU类似，都是基于模型输出和标准答案之间的n-gram的overlap，但是ROUGE不会对太短的摘要进行惩罚，而且ROUGE对不同的n-gram打分是分开的，而BLEU综合了n=1,2,3,4的n-gram结果。BLEU更关注precision，所以对太短（可能没有包含源句子的意思）的翻译有惩罚。ROUGE更关注recall，从其名称就可以看出来，在某个长度限制下，尽量包含长文的信息。） 2015年开始，基于神经网络的自动摘要方法蓬勃发展。基本思路是把自动摘要看成从长句子到短句子的翻译任务，使用seq2seq+attention的方法解决，效果还不错。下图是一些技巧，感兴趣的可以搜索原文阅读。 对话系统的分类：assistive：个人助手型；co-operative：协作型；adversarial：对抗型，辩论？chit-chat：聊天机器人；therapy：心理咨询师？ 神经网络之前的做法是，事先设计一些问答模板，根据场景，给模板填充不同的内容。或者使用信息检索的方式，从问答库中检索问答。 2015年后，很多人开始用seq2seq+attention的方法做问答系统，但存在一些问题，如下。 ...