0和1

前言 这节课主要介绍传统的图机器学习方法。传统方法主要分为两步，第一步人工设计特征，第二步使用各种机器学习方法进行预测。因此，特征工程在传统图机器学习方法中有很重要的地位。本节课主要介绍图上的特征工程方法，分别介绍针对节点（node-level）、边（link-level）和图（graph-level）的特征工程方法。 针对节点的特征工程方法 节点水平的特征主要有四类，下面分别介绍。 节点的度（node degree） 节点的中心性（node centrality） 节点的集聚系数（clustering coefficient） 非同构子图（graphlets） 节点的度 节点的度，这个最好理解了，即该节点的所连边的数目，或者说该节点的直接邻居数目。如果是有向图，还分为出度和入度。 节点的度的不足是，没有考虑到不同邻居的重要性不同，只要有一个邻居，度就加1，即认为所有邻居的重要性是相同的。 节点的中心性 节点的中心性这个特征考虑了节点的重要性，有多个中心性指标，如下： 特征向量中心性（Engienvector centrality） 中介中心性（Betweenness centrality） 接近中心性（Closeness centrality） 特征向量中心性的定义是：节点v的重要性=v的邻居的重要性的和，除以λ进行归一化。 根据定义可知，特征向量中心性是递归定义的，写成矩阵形式就是Ac=λc，特征向量c的每个维度就是每个顶点的特征向量中心性的值。 忘记了怎么求特征值和特征向量的同学可以复习一下：https://blog.csdn.net/Junerror/article/details/80222540。 算出最大特征值λ_max对应的特征向量c_max之后，节点v的特征向量中心性就是向量c_max的第v个分量。具体看维基百科：https://zh.wikipedia.org/zh-cn/%E7%89%B9%E5%BE%81%E5%90%91%E9%87%8F%E4%B8%AD%E5%BF%83%E6%80%A7。 如果说特征向量中心性有点难以理解和计算的话，接下来介绍的中介中心性和接近中心性就很好理解了。 中介中心性，顾名思义，就是节点作为中介（枢纽）的重要性。计算方法是，所有节点对(s,t)的最短路径穿过节点v的比例。(s,t)的最短路径可以认为是(s,t)之间的交通要道，如果这条路径穿过节点v的话，说明v在交通要道上，所以v是很重要的中介枢纽。具体计算方法见下图，即v在所有(s,t)的最短路径中出现的比例。 接近中心性也很好理解，就是节点v与图中其他节点的接近程度。计算方法是：v到其他节点的最短路径之和的倒数。如果一个节点越中心，则它到其他节点的最短路径越短，则接近中心性越大。比如下图的D就比A更中心，所以D的接近中心性更大。 节点的集聚系数 集聚系数是个很有意思的指标，它描述的不是节点本身，而是节点的邻居的集聚程度。其计算公式如下图所示，分子是v的邻居形成的边的数目，分母是v的邻居理论上能形成最多的边的数目，分母用来归一化的。 集聚系数=1表示v的邻居都两两认识，=0表示v的邻居两两都不认识。集聚系数越大，表示邻居聚集程度越高，越有可能是一个紧密的团体。 非同构子图 非同构子图的英文定义是：rooted connected non-isomorphic subgraphs，很准确啊，有根的连通的非同构子图。比如下图中3个节点的graphlets有3个，G1中目标节点（根节点）在1和2形成的子图是不一样的（不同构），而在G2中3个点的位置是等价的，所以G2只有1个graphlet，加起来就是3个graphelts。从2个节点到5个节点，能形成的graphlets总数是73个。 Graphlet Degree Vector（GDV）是基于graphlets的特征，它计算以目标节点v为根，能形成的不同graphlets的数目向量，相当于描述了v周围不同子结构的子图个数。如下子图3所示，红色节点v的2-3个节点的GDV向量是[2,1,0,2]。如果统计节点v周围的2~5个节点（包含v自己）形成的graphlets的数目，则会得到一个维度为73的GDV向量，相当于节点v的一个特征向量。这个73维度的特征向量是节点v周围四跳（4-hop）的结构信息。 小结一下节点的特征大概可以分成两类，一类是基于重要性的特征，例如节点的度、节点的中心性；另一类是基于结构的特征，例如节点的度、集聚系数、非同构子图个数向量。基于重要性的特征可用于预测网络中的重要节点，例如社交网络中的名人节点；基于结构的特征可用于预测网络中不同节点的不同功能，例如蛋白质相互作用网络中不同蛋白质的功能，因为不同的局部子结构往往蕴含了不同的功能。 针对边的特征工程方法 针对边<A,B>的特征工程方法，固然可以把节点A和B的节点特征concat起来作为边<A,B>的特征，但是丢失了很多边特有的信息，效果不一定好。专门针对边设计的特征工程方法有三个，下面分别介绍： 基于距离的特征（Distance-based feature） 局部邻居重叠比例（Local neighborhood overlap） 全局邻居重叠比例（Global neighborhood overlap） 基于距离的特征 两点之间的最短路径长度，这个最好理解了，可以用Dijkstra算法和Floyd算法求解。然而最短路径无法捕捉两个节点的共同邻居数目，比如下图中BH和BE的最短路径都是2，但BH有两个共同邻居CD，而BE只有一个共同邻居D，如果只用最短路径这个特征，则无法区分BH和BE这两对节点。 局部邻居重叠比例 局部邻居重叠比例衡量两个节点的邻居重叠程度，比如简单的Common neighbors直接计算两个节点的共同邻居数目；Jaccard’s coefficient用邻居交集数目除以并集数目做了归一化。 Adamic-Adar index的计算方法是所有共同邻居的度的对数分之一加和。它的直观含义是，如果共同邻居的度越小，则说明两个节点的关系越紧密。比如下图中，A和B的共同邻居是C，C的度是4，说明C除了连接了A和B，还连了另外2个节点。如果C的度越大，则说明A和B占C的邻居的重要性越低；反之，如果C只连了A和B，则说明A和B通过C这个枢纽连接的关系很重要。举个简单的例子，比如两个人都喜欢一个很小众的电影，则他们的兴趣可能会很接近，但如果都喜欢一个大众电影，则他们的关系可能没那么强烈。 局部邻居重叠比例的问题是：只考虑了一跳直接相连的邻居，没有考虑间接相连的邻居（潜在关系），后面介绍的全局邻居重叠比例可以解决这个问题。 全局邻居重叠比例 Katz index统计的是任意两个节点之间任意长度的路径的个数。在计算Katz index的时候，需要计算两个节点uv之间长度为l的路径个数。计算方法是邻接矩阵的l次方。 ...

今天开始学习《Fluent Python 2nd》，Python进阶好书。第二版今年3月份刚刚出版，以最新Python 3.10为基础进行介绍。 第一个案例是Python风格的扑克牌类： 短短几行代码，包含了Python很多有趣的特性，咱们一一道来。 （1）第一点就是collections.namedtuple的使用。比如这里使用collections.namedtuple定义了一个Card类，这个类的名称是Card，有两个命名成员rank和suit，分别表示扑克牌的数字和花色。 通常情况下，如果我们要定义一个Card，带两个属性rank和suit，需要使用class来进行定义，比较繁琐。但是对于扑克牌这种类，它只有属性（即数字和花色），没有方法，且属性一旦赋值就不可修改。则可以用collections.namedtuple来方便快速的定义一个命名类（命名tuple）。通过Card = collections.namedtuple(‘Card’, [‘rank’, ‘suit’])一行代码就实现了上面的定义，非常简洁高效。 （2）Python类的成员变量和实例的成员变量。上述FrenchDeck可以理解为“一张扑克牌桌子”的类，桌子上放了一副扑克牌。FrenchDeck有两个类的成员变量ranks和suits，这两个变量没有self.前缀，它们属于FrenchDeck这个类，所以可以直接用类名访问，即通过FrenchDeck.ranks或FrechDeck.suits访问。 而我们看FrenchDeck的构造函数__init__中有一个变量self._cards，它带有self.，此类变量就是类的实例的成员变量，只能通过实例进行访问，无法通过类名进行访问。一般我们将实例的成员变量以下划线_开头进行命名，以示区别。 类的成员变量也能通过实例进行访问，但实例的成员变量无法通过类进行访问。 比如定义deck=FrenchDeck()，则deck既可以访问实例的成员变量_cards，也能访问类的成员变量ranks和suits。但FrenchDeck只能访问ranks和suits，无法访问_cards。 如果实例变量和类变量同名，则通过实例访问时只能访问到同名的实例变量。由于类只能访问类变量，所以是否同名对通过类访问类变量没有影响。 （3）实现了内置的__len__和__getitem__方法。这两个方法都是python内置的方法，前者返回实例长度，后者返回指定下标的元素。实现了__len__之后，如果外部调用len(deck)，则Python解释器会隐含调用deck.__len__()。实现了__getitem__自后，如果外部调用deck[i]，则Python解释器会隐含调用deck.__getitem__(i)。 实现了__len__和__getitem__之后，相当于外部函数可以知道FrenchDeck实例的总长度，同时能取到任意下标的元素。因此，FrenchDeck实例看起来很像list，也可以支持诸如切片、随机采样、遍历等操作。仔细想想，切片、随机采样、遍历这些操作，其实只需要知道实例的总长度和随机访问下标这两个操作就可以了，而通过实现__len__和__getitem__这两个方法，FrenchDeck已经实现了这两个方法，所以也就支持前面说的那些操作了。 如果需要对扑克牌进行排序，则还需要为Card自定义排序函数，或者在sorted函数传入key。下面定义了key函数是spades_high，即计算每张牌的分值大小，以这个分值作为key排序的依据。

前言 工业界的图规模都非常大，少说也是上千万的顶点+上亿的边，单机训练不现实，必须借助多机分布式训练。然而目前主流的图训练框架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和改进。