A Lite BERT BERT(Devlin et al., 2019)的参数很多, 模型很大, 内存消耗很大, 在分布式计算中的通信开销很大. 但是BERT的高内存消耗边际收益并不高, 如果继续增大BERT-large这种大模型的隐含层大小, 模型效果不升反降. 针对这些问题, 启发于mobilenet, Alert使用了两种减少参数的方法来降低模型大小和提高训练速度, 分别是Factorized embedding parameterization和Cross-layer parameter sharing. 这些设计让ALBERT增加参数大小的边界收益远远大于BERT. 除此之外, 在句子关系任务上抛弃了bert的nsp任务, 改为sop任务. 整体而言, ALBERT是当前众多BERT系列模型的集大成者, 其思路值得学习, 代码也写得很清楚. 下面仔细过一遍. Factorized embedding parameterization BERT以及后续的XLNet(Yang et al., 2019), RoBERTa(Liu et al., 2019)等, WordPiece embedding的维度E是和隐层维度H绑定的. WordPiece embedding本意是学习context-independent的表达，而hidden-layer旨在学习context-dependent的表达。将WordPiece embedding大小E与隐层大小H解绑，可以更有效地利用建模所需的总模型参数. 从实用性的角度看, 这样可以减少词汇量对模型大小的影响. 在NLP中词汇量一般都很大, 所以这个解绑收益是很明显的. 具体的做法就是对embedding进行因式分解, 把非常大的单词embedding分解成两个小的矩阵, O(V × H)变成O(V × E + E × H), 可以显著减少单词映射embedding的参数量. 这个在topic models一文中的隐变量模型中类似的思路体现. Cross-layer parameter sharing 各个 transformer blocks 所有参数共享, 这样参数不再随着模型层数加深而增大....

Entity Linking Knowledge Graph (知识图谱)：一种语义网络，旨在描述客观世界的概念实体及其之间的关系，有时也称为Knowledge Base (知识库)。 图谱由三元组构成：<实体1，关系，实体2> 或者 <实体，属性，属性值>； 例如：<姚明，plays-in，NBA>、<姚明，身高，2.29m>； 常见的KB有：Wikidata、DBpedia、YAGO。 Entity 实体：实体是知识图谱的基本单元，也是文本中承载信息的重要语言单位。 Mention 提及：自然文本中表达实体的语言片段。 应用方向 Question Answering：EL是KBQA的刚需，linking到实体之后才能查询图数据库； Content Analysis：舆情分析、内容推荐、阅读增强； Information Retrieval：基于语义实体的搜索引擎，google搜索一些实体，右侧会出现wikipedia页面； Knowledge Base population：扩充知识库，更新实体和关系。 候选实体和消歧 Entity linking system consists of two components: candidate entity generation：从mention出发，找到KB中所有可能的实体，组成候选实体集 (candidate entities)； Entity Disambiguation：从candidate entities中，选择最可能的实体作为预测实体。 Entity Disambiguation (ED) 是最重要的部分 Features Context-Independent Features： LinkCount：#(m->e)，知识库中某个提及m指向实体e的次数； Entity Attributes：Popularity、Type； Context-Dependent Features： Textual Context：BOW, Concept Vector Coherence Between Entities：WLM、PMI、Jaccard Distance Context-Independent Features mention到实体的LinkCount、实体自身的一些属性（比如热度、类型等等） LinkCount作为一个先验知识，在消歧时，往往很有用 Context-Dependent Features 全局地进行entities的消歧实际上是一个NP-hard的问题，因此核心问题是如何更加快速有效地利用一致性特征 Learning to Rank Methods：Point-wise、Pair-wise、List-wise。由于ED任务ground truth只有一个实体，一般都是用point-wise来做。输入是文本的context、mention、某个entity的一些attributes，输出mention指向该entity的置信度，以此rank，选出最可信的entity； Probabilistic Methods：Incorporate heterogeneous knowledge into a probabilistic model。结合不同信息，得到条件概率 $P(e|m,c)$，其中 c 是输入文本，e 为实体， m 是mention。比如用归一化的LinkCount信息，作为先验概率 $P(e|m)$ ； Graph-Based Approaches：maximize coherene between entities。利用图特征 (entity embedding、relation)，在消歧时，考虑全局消歧后实体的一致性； Deep Type Discovering Types for Entity Disambiguation...

知识图谱补全 基于知识表示的方法 知识表示学习：对知识图谱中的实体和关系学习其低维度的嵌入式表示。 常见的知识表示学习方法：主要是以 TransE 法及其变种为核心，针对空间映射等场景做的改进 基于实体和关系的表示对缺失三元组进行预测； 利用实体描述信息，可以解决开放域实体补全的问题； 基于路径查找的方法 可使用基于路径查找的方法来处理这类多步推理问题。 传统的路径查找方法主要是 PRA 方法（Path Ranking Algorithm）；但是这种方法对于包含较大规模的知识图谱来说，会由于路径数量爆炸式增长，导致特征空间急剧膨胀 可以尝试用 embedding 的方式表示关系，对关系进行泛化，并基于此对知识的补全进行建模，以缓解路径数量过多导致的特征空间膨胀问题。 给定实体对集合，利用 PRA 查找一定数量的路径； 路径计算过程中加入实体类型信息（减少长尾实体影响）； 使用 RNN 沿着路径进行向量化建模；RNN 模型参数在不同关系之间共享； 通过比较路径向量与待预测关系向量间的关联度来进行关系补全。 基于强化学习的方法 前面提到的两种方法，仍然存在若干的问题： 需要基于 random walk 来查找路径； 而 random walk 算法在离散空间中运行，难以评价知识图谱中相似的实体和关系； 超级结点可能影响 random walk 算法运行速度。 强化学习方法： 在连续空间中进行路径搜索； 通过引入多种奖励函数，使得路径查找更加灵活、可控。 DeepPath DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning xwhan/DeepPath 任务：查找 Band of Brothers 和 English 之间的关系。 路径起点：Band of Brothers 状态：实体中的 embedding 动作：图谱中的关系； 奖励 Binary，是否到达终点 路径长度 路径多样性 策略网络：使用全连接网络。 DeepPath 方法仍然存在一些缺陷：知识图谱本身的不完善很可能对路径查找造成影响。...

Combining reinforcement learning and deep neural networks at scale. The algorithm was developed by enhancing a classic RL algorithm called Q-Learning with deep neural networks and a technique called experience replay. Q-Learning Q-Learning is based on the notion of a Q-function. The Q-function (a.k.a the state-action value function) of a policy $\pi$，$Q^{\pi}(s, a)$ ，measures the expected return or discounted sum of rewards obtained from state $s$ by taking action $a$ first and following policy $\pi$ thereafter....

Adam Weight Decay in BERT 在看BERT(Devlin et al., 2019)的源码中优化器部分的实现时，发现有这么一段话 # Just adding the square of the weights to the loss function is *not* # the correct way of using L2 regularization/weight decay with Adam, # since that will interact with the m and v parameters in strange ways. # # Instead we want ot decay the weights in a manner that doesn't interact # with the m/v parameters. This is equivalent to adding the square # of the weights to the loss with plain (non-momentum) SGD....

What is Word Lattices? A word lattice is a directed acyclic graph with a single start point and edges labeled with a word and weight. Unlike confusion networks which additionally impose the requirement that every path must pass through every node, word lattices can represent any finite set of strings (although this generality makes word lattices slightly less space-efficient than confusion networks) 语音识别结果的最优路径不一定与实际字序列匹配，所以人们一般希望能够得到得分最靠前的k-best条候选路径。为了紧凑地保存候选路径，防止占用过多内存空间，可以采用词格（Word Lattice）来保存识别的候选序列。 在序列标注任务中，一般的编码器+CRF的分词模型，因为实体标签的定义不同，词汇不同，语料不同等等原因，普遍无法适应垂直领域的问题。如果要适配，需要走一遍数据准备和模型训练验证的流程。 所以实践中一般都需要词典来匹配。词典匹配方法直接针对文本进行匹配从而获得成分识别候选集合，再基于词频（基于各种工程经验统计获得）筛选输出最终结果。这种策略比较简陋，对词库准确度和覆盖度要求极高，所以存在以下几个问题： 未登录词，易引起切分错误 粒度不可控 节点权重如何设定, 比如每夜总会加班涉及每夜和夜总会 因此我们需要把词典匹配方法和神经网络NER模型结合使用....

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

注意力机制的原理是计算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....