NLP任务的难点 不像图像的普适性, 语言本身有其多样性, 如语境的偏移, 背景的变化, 人与人间的分歧, 这导致以下问题: 有标注数据的通用性低 标注数据质量不稳定 现实世界的语言和使用场景不断更新, 导致模型的维护更新换代成本极高 … 为了应对NLP的难点, 需要充分利用各种可用的监督信号，包括但不限于传统监督学习（supervision），自监督学习（self-supervised），弱监督(weak supervision)，迁移学习（transfer learning），多任务学习（multi-task learning, MTL）。 Near-term improvements in NLP will be mostly about making clever use of “free” data. 语言模型 - 经典的自监督学习模型 Lecun有给自监督学习下定义，但我个人对自监督的理解是，基于数据本身进行学习，让模型学习到数据隐含的特征。 比如语言模型的根据前文预测下一个单词。 最近的BERT丰富了玩法，提出了Mask language model，就是通过上下文预测掩码位置的单词，作为其核心学习任务；BERT的训练过程还应用了多任务学习，把 next sentence prediction 也作为任务之一一起学习。 目前除了语言模型和句模型(next sentence)，是否还有其他任务? Baidu ERNIE: 引入了论坛对话类数据，利用 DLM（Dialogue Language Model）建模 Query-Response 对话结构，将对话 Pair 对作为输入，引入 Dialogue Embedding 标识对话的角色，利用 Dialogue Response Loss 学习对话的隐式关系。 ELMo vs GPT vs BERT 经典Word2vec表达是context free的，open a bank account和on the river bank的bank共用一个向量值[0.3, 0.2, -0.8, …]. 如指公司的苹果和指水果的苹果共用一个向量. ...

注意力机制的原理是计算query和每个key之间的相关性$\alpha_c(q,k_i)$以获得注意力分配权重。在大部分NLP任务中，key和value都是输入序列的编码。 注意力机制一般是用于提升seq2seq或者encoder-decoder架构的表现。但这篇2017 NIPS的文章Attention is all you need提出我们可以仅依赖注意力机制就可以完成很多任务. 文章的动机是LSTM这种时序模型速度实在是太慢了。 近些年来，RNN（及其变种 LSTM, GRU）已成为很多nlp任务如机器翻译的经典网络结构。RNN从左到右或从右到左的方式顺序处理语言。RNN的按顺序处理的性质也使得其更难以充分利用现代快速计算设备，例如GPU等优于并行而非顺序处理的计算单元。虽然卷积神经网络（CNN）的时序性远小于RNN，但CNN体系结构如ByteNet或ConvS2S中，糅合远距离部分的信息所需的步骤数仍随着距离的增加而增长。 因为一次处理一个单词，RNN需要处理多个时序的单词来做出依赖于长远离单词的决定。但各种研究和实验逐渐表明，决策需要的步骤越多，循环网络就越难以学习如何做出这些决定。而本身LSTM就是为了解决long term dependency问题，但是解决得并不好。很多时候还需要额外加一层注意力层来处理long term dependency。 所以这次他们直接在编码器和解码器之间直接用attention，这样句子单词的依赖长度最多只有1，减少了信息传输路径。他们称之为Transformer。Transformer只执行一小段constant的步骤（根据经验选择）。在encoder和decoder中，分别应用self-attention 自注意力机制(也称为intra Attention), 顾名思义，指的不是传统的seq2seq架构中target和source之间的Attention机制，而是source或者target自身元素之间的Attention机制。也就是说此时Query, Key和Value都一样, 都是输入或者输出的序列编码. 具体计算过程和其他attention一样的，只是计算对象发生了变化. Self-attention 直接模拟句子中所有单词之间的关系，不管它们之间的位置如何。比如子“I arrived at the bank after crossing the river”，要确定“bank”一词是指河岸而不是金融机构，Transformer可以学会立即关注“river”这个词并在一步之内做出这个决定。 Transformer总体架构 与过去流行的使用基于自回归网络的Seq2Seq模型框架不同: Transformer使用注意力来编码(不需要LSTM/CNN之类的)。 引入自注意力机制 Multi-Headed Attention Mechanism: 在编码器和解码器中使用 Multi-Headed self-attention。 Transformer也是基于encoder-decoder的架构。具体地说，为了计算给定单词的下一个表示 - 例如“bank” - Transformer将其与句子中的所有其他单词进行比较。这些比较的结果就是其他单词的注意力权重。这些注意力权重决定了其他单词应该为“bank”的下一个表达做出多少贡献。在计算“bank”的新表示时，能够消除歧义的“river”可以获得更高的关注。将注意力权重用来加权平均所有单词的表达，然后将加权平均的表达喂给一个全连接网络以生成“bank”的新表达，以反映出该句子正在谈论的是“河岸”。 Transformer的编码阶段概括起来就是： 首先为每个单词生成初始表达或embeddings。这些由空心圆表示。 然后，对于每一个词, 使用自注意力聚合来自所有其他上下文单词的信息，生成参考了整个上下文的每个单词的新表达，由实心球表示。并基于前面生成的表达, 连续地构建新的表达（下一层的实心圆）对每个单词并行地重复多次这种处理。 Encoder的self-attention中, 所有Key, Value和Query都来自同一位置, 即上一层encoder的输出。 解码器类似，所有Key, Value和Query都来自同一位置, 即上一层decoder的输出, 不过只能看到上一层对应当前query位置之前的部分。生成Query时, 不仅关注前一步的输出，还参考编码器的最后一层输出。 N = 6, 这些“层”中的每一个由两个子层组成：position-wise FNN 和一个（编码器），或两个（解码器），基于注意力的子层。其中每个还包含4个线性投影和注意逻辑。 ...

序列标注（Sequence Labeling） 序列标注任务是指根据观察得到的序列（如一个句子）, 推断出序列每个元素（单词）对应的标注。 具体的任务包括分词(Segmentation), 词性标注（Part-of-Speach tagging, POS）, 实体识别(Named Entity Recognition, NER), 等等. 所谓POS, 就是对于一个句子, 如Bob drank coffee at Starbucks, 标注可能为Bob (NOUN) drank (VERB) coffee (NOUN) at (PREPOSITION) Starbucks (NOUN). 除此之外, 还有其他涉及到需要根据观察序列推断隐含状态的问题, 这种问题的特点是每一个位置的标签都不是独立的, 而是和上下文相关依存的, 可以用序列标注的思路来处理. 单个分类器仅能预测单个类变量，但是序列标注基于概率图模型, 图模型(Graphical Models)的真正功能在于它们能够对许多有相互依赖的变量进行建模。最简单的依赖关系可以描述为一种线性链(Linear Chain), 也就是后续介绍到的隐马尔可夫模型(Hidden Markov Model, HMM)用到的假设. 概率图模型 Graphical Models, 用图的形式表示随机变量之间条件依赖关系的概率模型，是概率论与图论的结合。图中的节点表示随机变量，缺少边表示条件独立假设。 G = (V, E). 其中 V: vertex, 顶点/节点, 表示随机变量. E: edge, 边/弧. 如果两个节点不存在边, 则二者条件独立. 从图上可以看到, 贝叶斯网络(Bayesian Networks, BNs)是有向图, 每个节点的条件概率分布表示为P(当前节点 | 父节点). ...

The Line Patterns Recognition A basic but important application of pattern recognition is to recognize line patterns in a given set of points. http://coursera.cs.princeton.edu/algs4/assignments/collinear.html. This blog will give a breif introduction to this problem and provide an enfficient solution. Codes available in algs4/collinear/src/ The problem could be described as: Given a set of n distinct points in the plane, find every (maximal) line segment that connects a subset of 4 or more of the points.. ...

This blog explains an apllication of randomized queue algorithms. Permutation client memory challenge A client program Permutation.java that takes an integer k as a command-line argument; reads in a sequence of strings from standard input using StdIn.readString(); and prints exactly k of them, uniformly at random. Print each item from the sequence at most once. More detail could be found at programming assignment specification and checklist, codes available in algs4/queues/src/. Randomized queue For a randomized queue, the item removed is chosen uniformly at random from items in the data structure. ...

本文介绍注意力机制如何应用于阅读理解类任务, 并介绍了由此任务催生的一些注意力变种. 注意力机制应用于阅读理解 The Standford question and answer dataset (SQuAD) 是由 Rajpurkar 等人提出的一个较有挑战性的阅读理解数据集。该数据集包含 10 万个（问题，原文，答案）三元组，原文来自于 536 篇维基百科文章，而问题和答案的构建主要是通过众包的方式，让标注人员提出最多 5 个基于文章内容的问题并提供正确答案，且答案出现在原文中。SQuAD 和之前的完形填空类阅读理解数据集如 CNN/DM，CBT 等最大的区别在于：SQuAD 中的答案不在是单个实体或单词，而可能是一段短语，这使得其答案更难预测。SQuAD 包含公开的训练集和开发集，以及一个隐藏的测试集，其采用了与 ImageNet 类似的封闭评测的方式，研究人员需提交算法到一个开放平台，并由 SQuAD 官方人员进行测试并公布结果。 由于 SQuAD 的答案限定于来自原文，模型只需要判断原文中哪些词是答案即可，因此是一种抽取式的 QA 任务而不是生成式任务。简单的 SQuAD 的模型框架可以参考seq2seq：Embed 层，Encode 层 和 Decode 层。Embed 层负责将原文和问题中的 tokens 映射为向量表示；Encode 层主要使用 RNN 来对原文和问题进行编码，这样编码后每个 token 的向量表示就蕴含了上下文的语义信息；Decode 层则基于 query-aware 的原文表示来预测答案起始位置。 但这个文本数据集涉及问题，原文，答案三个部分, 特别是需要根据问题在原文中搜寻答案的范围, 这就涉及如果把问题的信息提取出来并作用于原文. 目前各种前沿模型的关注点几乎都是在如何捕捉问题和原文之间的交互关系，也就是在 Encode 层和 Decode 层之间, 使用一个 Interaction 层处理编码了问题语义信息的原文表示，即 query-aware 的原文表示，再输入给 Decode 层。而本来应用机器翻译Attention机制就能很好的处理这种交互。 虽然注意力机制大同小异，但是不同的注意力权重（打分函数）带来的效果是不一样的。比较常用的是就是使用全局注意力机制中提到的 $$ \begin{aligned} score_{general}(t' t) &= s^\top_{t'} W_\alpha h_t, \\\ \end{aligned} $$ 就是用一个交互矩阵$W_\alpha$来捕捉问题和原文之间的交互关系. 原文作者称之为 Bilinear. ...

时序决策 以经典的Atari游戏为例，agent在t时刻观测一段包含M个帧的视频$s_t = (x_{t-M+1}, ..., x_t) \in S$, 然后agent做决策, 决策是选择做出一个动作 $a_t \in A = \{ 1, ..., |A| \}$(A为可选的离散动作空间 ), 这个动作会让agent获得一个奖励$r_t$. 这就是时序决策过程, 是一个通用的决策框架，可以建模各种时序决策问题，例如游戏，机器人等. Agent 观察环境，基于policy $\pi\left(a_{t} \mid s_{t}\right)$ 做出响应动作，其中 $s_{t}$是当前环境的观察值(Observation 是环境State对Agent可见的部分)。Action会获得新的 Reward $r_{t+1}$, 以及新的环境反馈 $s_{t+1}$. Note: It is important to distinguish between the state of the environment and the observation, which is the part of the environment state that the agent can see, e.g. in a poker game, the environment state consists of the cards belonging to all the players and the community cards, but the agent can observe only its own cards and a few community cards. In most literature, these terms are used interchangeably and observation is also denoted as . ...

注意力机制如何起源的 神经网络中的注意力机制启发自人类的视觉注意力机制，能够（高分辨率地）聚焦于图像中需要重点关注的目标区域（节省大脑资源），同时（低分辨率地）感知周围的图像，然后随着时间的推移调整焦点（状态调整）。 在神经网路中，注意力机制是为了解决什么问题？ 在深度学习还没流行的时候, 传统的算法早已应用了注意力机制的思想. 比如一个非线性回归问题，对于代表位置的输入变量${x_1, ..., x_m}$ 和 代表位置对应的输出值${y_1, ..., y_m}$, 如何预测新的$x_n$对应的输出? Baseline 就是求均值, $$\frac{1}{m} \sum_{i=1}^{m} y_i$$ 当然更好的方案(Watson, Nadaraya, 1964)是根据不同的输入$x_i$给与$y_i$不同的权重, $$y = \sum_{i=1}^{m} \alpha(x, x_i) y_i $$这里$x$代表一个新的输入(作为query), 根据$x$和已有的位置$x_i$(作为key)进行某种运算, 得到$x_i$对应的输出$y_i$(作为value)的权重. 如果每一个权重都是一个Guassians分布, 并正则化, 则一个加权的回归预测模型就是: $$f(x) = \sum_i y_i \frac{k(x_i, x)}{\sum_j k(x_j, x)}$$这个算法的"深度学习"版本, 就是其权重是通过优化器(如sgd)学习得来, 并且把平均运算改为加权池化(weighted pooling). 如何简单直观地理解注意力机制 虽然注意力机制一开始被应用于图像识别领域，但是后来推广到神经机器翻译(NMT)中(Seq2Seq for Machine Translation, Sutskever, Vinyals, Le ‘14). NMT也是注意力机制在NLP领域最早最成功的应用之一. 在上图中，Echt，Dicke和Kiste词被送到编码器中，并且在特殊信号（未显示）之后，解码器开始生成翻译后的句子。解码器不断生成单词，直到产生特殊的句子结尾标记(如<eos>)。也就是说解码器仅根据最后一个隐含状态$h_3$来生成序列. 假如这个句子很短, 那么效果其实是很好的. 不过对于比较长的句子, 那么这个架构的弱点就暴露无疑了. 首先, 编码器能否把句子的所有信息(语言学上的和常识等知识)都理解/捕捉到? 其次, 受限于目前的实现技术(主要是硬件), 单个隐含状态(如$h_3$这个向量)的维度大小是有限的, 而句子长度以及语言的组合情况是无限的, 单靠$h_3$自身是存储信息能力是有限的. 再者, 解码器是否有足够的解码能力从一个隐含状态中解码出所有的信息? 虽然大部分句子是相对紧凑的, 但语言有个特点, 就是一个词有可能和前面好几步之外的词有联系, 比如一些指代词用于指代文本最开头出现的名词; 语义上, 某个句子的理解, 可能依赖于前面多个句子; 当然往大了说, 要理解一篇文章或一本书, 我们通常需要理解并联系多个段落, 多个章节. 这种现象称之为语言的长距离依赖(long-term dependency), 在一般性的序列数据中, 这个现象称之为的Long-range dependence(LRD). 即使是使用了LSTM这种理论上可以克服长距离依赖问题地网络, 也无法很好的克服语言的长距离依赖问题, 究其原因, 除了LSTM自身的局限性之外, 更主要是深度学习的梯度学习方法的局限性(在梯度反向传播中, 会出现梯度消失). ...

Union-find applications: Percolation Problem discriptions Percolation data type. To model a percolation system, create a data type Percolation with the following API: public class Percolation { public Percolation(int n); // create n-by-n grid, with all sites blocked public void open(int row, int col); // open site (row, col) if it is not open already public boolean isOpen(int row, int col); // is site (row, col) open? public boolean isFull(int row, int col); // is site (row, col) full? public int numberOfOpenSites(); // number of open sites public boolean percolates(); // does the system percolate? } Monte Carlo simulation. To estimate the percolation threshold, consider the following computational experiment: ...

爱丁堡大学信息学院课程笔记 Accelerated Natural Language Processing, Informatics, University of Edinburgh References: Accelerated natural language processing ANLP revision guide Lecture Slides from the Stanford Coursera course Natural Language Processing, by Dan Jurafsky and Christopher Manning 概率模型 Probability Model 概率模型是随机现象的数学表示，由样本空间，样本空间内的事件以及与每个事件相关的概率定义。目标是模拟给一个事件发生的概率 估算概率（Probability Estimation）一般使用最大似然估计（MLE，相关频率）： $$p(x_i) = \frac{Count(x_i)}{\sum_{i=0}^nCount(x_i)}$$平滑Smoothing 一般用于处理0概率的问题，比如在训练集中看不到, 但出现在测试集中的词。 Language modeling To compute the probability of sentence /sequence of words $P(w_1, w_2, w_3...)$, or to predict upcomming words $P(w|w_1, w_2, w_3...)$… a language model is also a probability model. ...