Posts

注意力机制的原理是计算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个线性投影和注意逻辑。 编码器: Stage 1 - 输入编码: 序列的顺序信息是非常重要的。由于没有循环，也没有卷积，因此使用“位置编码”表示序列中每个标记的绝对（或相对）位置的信息。 positional encodings $\oplus$ embedded input Stage 2 – Multi-head self-attention 和 Stage 3 – position-wise FFN....

序列标注（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(当前节点 | 父节点). 而马尔可夫网络则是无向图. 无向图形模型是指一整个家族的概率分布，每个概率分布都根据给定的因子集合进行因式分解。一般用random field来指代无向图中定义的特定分布....

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/....

本文介绍注意力机制如何应用于阅读理解类任务, 并介绍了由此任务催生的一些注意力变种. 注意力机制应用于阅读理解 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$来捕捉问题和原文之间的交互关系....

时序决策 以经典的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....

注意力机制如何起源的 神经网络中的注意力机制启发自人类的视觉注意力机制，能够（高分辨率地）聚焦于图像中需要重点关注的目标区域（节省大脑资源），同时（低分辨率地）感知周围的图像，然后随着时间的推移调整焦点（状态调整）。 在神经网路中，注意力机制是为了解决什么问题？ 在深度学习还没流行的时候, 传统的算法早已应用了注意力机制的思想. 比如一个非线性回归问题，对于代表位置的输入变量${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$自身是存储信息能力是有限的. 再者, 解码器是否有足够的解码能力从一个隐含状态中解码出所有的信息? 虽然大部分句子是相对紧凑的, 但语言有个特点, 就是一个词有可能和前面好几步之外的词有联系, 比如一些指代词用于指代文本最开头出现的名词; 语义上, 某个句子的理解, 可能依赖于前面多个句子; 当然往大了说, 要理解一篇文章或一本书, 我们通常需要理解并联系多个段落, 多个章节....

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?...

Word2vec Mikolov et al. How to represent meanings? 如何在数学上表达词义？ Vector space models (VSMs) 表示把单词映射到(嵌入)连续的矢量空间, 而且理论上语义相似的单词会映射到空间中临近的位置。VSMs是一个历史悠久的NLP理论，但所有实现方法都不同程度依赖于Distributional Hypothesis, 即出现在相同（相似）的上下文中的单词具有相同（相似）的语义意义。利用此原则的方法大致可以分为两类: Count-based methods (例如, Latent Semantic Analysis))和Predictive models(例如 neural net language models (NNLM))。 具体的区别详见Baroni et al.. 但总的来说，Count-based methods 统计词汇间的共现频率，然后把co-occurs matrix 映射到向量空间中；而Predictive models直接通过上下文预测单词的方式来学习向量空间（也就是模型参数空间）。 Word2vec 是一种计算特别高效的predictive model, 用于从文本中学习word embeddings。它有两种方案, Continuous Bag-of-Words model (CBOW) 和 Skip-Gram model (Section 3.1 and 3.2 in Mikolov et al.). 从算法上讲, 两种方案是相似的, 只不过 CBOW 会从source context-words ('the cat sits on the')预测目标单词(例如"mat"); 而skip-gram则相反, 预测目标单词的source context-words。Skip-gram这种做法可能看起来有点随意....

循环神经网络 当人类阅读时，会根据对之前单词的理解和记忆来辅助理解当前看到的每个单词。也就是人能够很好地处理语言的长距离依赖特性（long-term dependency）。在自然语言处理任务中，很多传统的模型无法做到这一点，比如前馈神经网络；而传统的n-gram模型固然可以通过把把n系数增大来捕捉长距离依赖，但带来的非常巨大的内存消耗。 循环神经网络（Recurrent Neural Networks, RNNs)可以看做是多个共享参数的前馈神经网络不断叠加的结果  这里的核心是想办法解码历史信息, 即通过递归方程$s_i = R(x_i, s_{i−1})$让$s_i$解码序列$x_{1:n}$. 比如把所有历史信息累加就是一种非常简单粗暴的方式, 这样得到的是连续词袋模型(continuous-bag-of-words model)$s_i = R_{CBOW}(x_i, s_{i-1}) = x_i + s_{i−1}$, 虽然简单，但这种RNN其实忽略了数据的时序性质。 一般意义上的RNN是指Elman Network or Simple-RNN (S-RNN)(Elman [1990]), $s_i = R_{SRNN}(x_i, s_{i-1}) = g(x_iW^x + s_{i−1}W^s + b)$, 也就是把历史信息先进行线性变换(乘以矩阵), 再和bias加起来, 再通过一个非线性激活函数(tanh或ReLU). 添加了线性变换再进行非线性激活, 使网络对输入的顺序变得敏感。 在使用时, 给定输入序列（单词序列或语音）得出输出序列的过程如下： 把每个词$x_{t}$(以向量表示)逐个输入RNN 每一时间步$t$都有对应的隐含状态$s_t$，用于解码历史信息: $s_t = g(Ux_t + Ws_{t-1} + b)$....