一些关于NER任务调研的小思考

因为老师安排要去调研一些NER最近几年的论文,我才不会说又被安排一口大锅:知识图谱上的实体消歧。。。,看了一篇综述后整理了一些需要看的论文,以及搜了一些今年的相关论文,一些自己感觉比较有意思的论文还专门写写ppt啥的(但是泥萌看不到的,因为我太菜啦!),同时记录一下每篇论文的一些小收获和思考。因为比较随性就不按年代顺序了,直接按我看的顺序了囧。。。

A Local Detection Approach for Named Entity Recognition and Mention Detection

ACL 2017

貌似这个大学的人一直推那个FOFE模型,作者采用局部检测固定长度的word segments的方法:把underlying segment和它左右的上下文结合起来,来确定是否为一个实体及其标签。采用FOFE编码方法编码序列片段,来解决变长编码的问题,减少信息损失,在得到编码表示后使用简单的DNN结构降低模型复杂度,提高训练速度。但是个人感觉这种方法还是很奇怪的对于FOFE的效果表示一下存疑,主要是没看懂之前的理论证明。。。估计之后也不会很考虑吧,但是我还是做了ppt呢。

Evaluating the Utility of Hand-crafted Features in Sequence Labelling

EMNLP 2018 short paper

通过加入一个auto-encoder来衡量hand-crafted features对于NER任务到底有没有作用,作者加入一个auto-encoder模块来处理hand-crafted features,比加上之前的模块有所提升,而且显示直接使用hand-crafted features作为input或者仅作为output的效果都没有作为auto-encoder的好,似乎令人思考hand-crafted features到底应该怎么用到模型中去,是不是简单的作为representation并不能让模型理解这些特征和word embedding这类的区别。也做了个ppt。

End-to-end Sequence Labeling via Bi-directional LSTM-CNNs-CRF

ACL 2016

模型为BILSTM+CNN+CRF,CNN只是得到一个char representation,和之前训练好的word embedding喂到BILSTM,输出喂到CRF中。实验结果分析的都很好,不过感觉模型现在已经烂大街了,就没做ppt了,具体看论文吧。

DEEP ACTIVE LEARNING FOR NAMED ENTITY RECOGNITION

ICLR 2018

主动学习和NER任务相结合,因为主动学习的要求,对模型训练速度有很大需求,采用了CNN+CNN+LSTM的方法,其中LSTM作为tag而没有用CRF,但是从实验效果来看更好居然。。。感觉思路以及主动学习的结合都很新,就写了个ppt总结了。

Character-Aware Neural Language Models

AAAI 2016

传统的word embedding没有捕捉一些词素级别的信息,因此对于一些低频词、OOV很难处理,所以作者尝试只在字符级别上跑CNN(从现在来看这也是基操了)来作为解决方案。好像很多论文为了解决OOV问题都是用char-level跑CNN,当然有的任务(机器翻译)也用copy机制?感觉现在基本上都是CNN跑一下char-level在和word embedding集合作为一个word representation了。作者还提出一些有趣的观点:如利用低维向量表示char-level的信息比one-hot好。而且作者的实验发现使用结合word embedding的效果反而变差了,有点违反直觉,毕竟有的任务是变好了比如NER。解释大概是有些任务来说char-leval已经足够了。
看这篇论文了解到一个知识点:max-over-time pooling,就是对于一个filter得到的feature map全部取max,这样是因为可以固定长度(和filter个数相关了,解决了NLP中句子长短不一的情况)给上面的层操作。但好像现在一般是插入pad的操作?
作者对于CNN产生的输出过了一个Highway Network。具体公式看论文吧。其实对于这个的作用为什么好也不太理解。但是作者认为highway可以捕捉到一些次的语义特征,是为了增益CNN效果的一个方向。
作者在计算softmax的时候采用了一个叫做hierarchical softmax (Morin and Bengio 2005)的方法,直观上来看我感觉就是聚类分块???来加快速度,让模型更加有效率吧。。。

Neural Architectures for Named Entity Recognition

NAACL 2016

应该是比较经典的BiLSTM+CRF的工作了。作者提出了两点:第一点是有些实体词是由多个词组成的,这些词都是同样重要的,而且词和词之间的关系也很重要,对于这一点作者提出了两个模型:BiLSTM+CRF和栈式LSTM。第二点是怎么判断一个词看起来是否为实体以及在什么样的语境下一个词会被认为是一个实体。这其实也就对应了字向量和词向量。
作者提出了一些加入CRF的原因:对于NER这种输出标签之间依赖关系很强的任务,简单的通过LSTM输出的特征是不够的。
作者还提出有IOB和IOBES两种标注策略,有的人显示后者可以捕捉到更多有用的信息,但是作者实验并没有发现这一点(看来自己可以都试一试囧)。
作者还提出了一个stack-LSTM model。相当于一次直接把若干次组成的实体词一块处理(分块)。这个模型第一次提出是在《Transition-based dependency parsing with stack long-short-term memory》中,所以还是需要看原论文才知道细节,不过最近实在是没啥时间了。。。
作者也表示仅仅通过NER的有限数据集学习词向量不太行,也想通过char-level来学到一个词的表示,在这篇文章之前貌似大家还是用hand-engineering prefix and suffix information得多。但是和之前看的论文不太一样的是作者使用的是BiLSTM而不是CNN,坐着也给了解释就是这样可能更容易获得一个word的前缀和后缀信息(是一个挺值得思考的点就是卷积和RNN这两种结构再从char-level建模word表示有何不同?)

Joint Extraction of Entities and Relations Based on a Novel Tagging Scheme

ACL 2017

这篇文章主要关注于如何把实体抽取和实体关系同时来做,使用了一套novel的标注策略完全建模成了一个序列标注任务,模型就是一个BiLSTM的encoder和LSTM的decoder,发现自己之前认为NER就应该无脑CRFdecoder的想法也是有问题的,之前看的做主动学习的那个和这个都用的LSTM做decoder,但这里主要是为了解决relation长距离依赖的问题,这一点因为CRF的局部性可能比较难处理吧,还是要具体情况具体分析的。。。
做了个ppt作为资料(不过也没人能看到吧)

On the Strength of Character Language Models for Multilingual Named Entity Recognition

EMNLP 2018

某天师兄发了一个emnlp 2018完整版的收录结果扫了一下NER的文章,发现了一个看起来很有趣的研究char LM在多语言NER任务上的效果的paper,正好想看看char-level这样的字符表示到底有多大的效果。结果看了一下还是比较无聊的。。。。
作者在这里只针对token,通过n-gram的方法训练了一个entity CLM和一个non-entity CLM,用来做NEI这样一个二分类任务。通过算困惑度来确定一个token究竟是不是实体,因为实验效果显示越是实体词在CLM中的困惑度越低。实验结果显示这个简单的CLM模型的加入的确可以提高NEI任务的效果,但对于NER任务来说只能做的有的语言有所提升,有的甚至还有所下降。

Deep Exhaustive Model for Nested Named Entity Recognition

EMNLP 2018

这篇paper主要针对嵌套命名实体识别的情况提出了一个模型:Deep Exhaustive Model。
作者也是先把word embedding和character-based word representations结合起来作为word representation,值得一提他也是和Lample一样用的BiLSTM提出char-level的word representation。
作者提出一个解决嵌套的NER的任务可以通过region representatio来解决。其实就是相当于过了一个BiLSTM获得了各个token的隐层表示hi后,按照预先规定好的最大实体词长度来划分好region。region最后的表示是通过边界上的隐层表示以及中间token(包括边界)的隐层表示之和的平均值级联而成。看起来很简单对吧,再通过一个ReLU和softmax来得到最后的输出(但是作者在之前强调是对每个region才有一个输出,但是看论文里的图好像还是token?没看懂)。在GENIA和JNLPBA两个生物信息领域的数据集上达到了SOTA的结果。
看完这之后我有个问题就是如果还是通过BiLSTM过一个整个的句子序列的话,然后只通过简单的级联和求平均来表示region,能否被称作一个region representation呢?他其实会考虑一些区域外的信息啊?而且整篇论文也没有很系统讲为什么要这么做,可能真的只是实验科学吧囧。。。

Marginal Likelihood Training of BiLSTM-CRF for Biomedical Named Entity Recognition from Disjoint Label Sets

EMNLP 2018

这篇文章主要针对于如何利用标签集合不相交的一些数据集来让模型可以在多个数据集上提出正确的entity,主要针对的是医疗数据集,因为这些数据集可能有的只含有疾病、蛋白质名之类的,而没有一个包含所有标签集的数据集来统一一下。
首先如果直接在所有的数据集上跑训练出来一个模型,就要求必须全部正确,但这明显不符合问题的,因为不能说一个数据集上的O标签就真的是O标签。作者提出的方法有两个:Multiple CRFs就是所有的模型共享提特征用的BiLSTM,但是分别在不同的数据集上训练CRF,对于有冲突的标签选择概率最大的那个。作者还提出了一个更好的方法(从实验效果来看):EM Marginal CRF,更改了CRF层的目标函数,对于当前数据集上确定的标签我们还是正常算Loss,但是对于O标签我们认为是隐变量进行训练(这一块论文没有详细解释,只是说了一个大概思路)。
感觉这篇paper还是挺新颖的,但是作者也说还有一些问题没有解决,比如如何解决不同数据集tag的overlap的问题。

Adaptive Co-Attention Network for Named Entity Recognition in Tweets

AAAI 2018

某天早上老师给的文章,文章思路挺新颖的(之前没见过):针对推特的NER任务,作者认为之前人们只是利用了文本信息,他提出推特中大部分中是含有图片的,假如可以通过图片中的信息是可以给文本一些增益的,所以就用了个co-attention的模型来融visual feature和textual feature,细节有点多,不过写的还是比较清楚的还是具体看论文吧。实验结果来看这个att模块的确让效果变好了,并且具有一定的扩展性。

Adversarial Transfer Learning for Chinese Named Entity Recognition with Self-Attention Mechanism

EMNLP 2018

这篇文章主要针对于中文的NER任务。作者认为现在的有标注的中文NER数据集是非常少的。作者提出其实中文的NER和CWS任务的分词边界(word boundary)有很多相似的,但是也有不同的特殊之处。作者就提出了一个叫做对抗迁移学习的模型来make full use of task-shared boundaries information and prevent the task- specific features of CWS。作者还认为引入self-attention是可以捕捉token之间的长距离依赖信息的。
目前中文NER主要有两个数据集:Weibo NER dataset(1.3k training examples)、Sighan2006 NER dataset(45k training examples)。而且因为数据少的原因深度模型表现都不够好。但是CWS的数据集则很多而且CWS和NER之间有很多task-shared information。所以现在就需要如何利用这些task-shared information并且过滤掉那些对于NER任务是噪声的信息。
同时上下文信息对于确定实体类型是十分重要的,例如“希尔顿离开…”,如果不关注离开的话那很难判断希尔顿是人名还是机构名。
模型如下:

作者用使用了两种BiLSTM:一种叫private BiLSTM,这种BiLSTM中的参数是任务不同而不同的,他负责提出该任务task-specific feature。还有一种是shared BiLSTM,这两个任务都通过他提feature,这部分就是要去学习task-shared word boundaries。
然后这两个private BiLSTM的输出和shared BiLSTM的输出都做一个self-attention,主要是为了解决长距离依赖的问题。然后对于这两个任务把分别把各自的private BiLSTM的输出和shared BiLSTM的输出级联起来分别用各自的CRF层进行tagging。
为了保证shared BiLSTM不把噪声提出来到shared space中去,作者加入了一个鉴别器的loss。shared BiLSTM的输出先通过一个Maxpooling层(论文中应该是每一行取一个max)得到一个2*d的向量,然后送入一个鉴别器,当训练完成后达到鉴别器无法通过shared BiLSTM提取到的特征区分来自哪个任务。(当然具体有些细节看的不太懂,比如LOSS的设计,因为没学过对抗学习的内容)。
当然整体的训练的时候loss就是NER的loss和CWS的loss以及对抗的loss之和,不同任务用不同的loss表示。(具体看论文)
实验结果显示,加入对抗的模块的确解决了之前引入噪声信息的问题。而且self-att也很有用。感觉这篇文章好有启发性。

CharNER: Character-Level Named Entity Recognition

Coling 2016

这篇文章感觉很早了,东西也没什么新的,随便记录一下。作者提出用word-level的表示在面对多语言的NER任务时需要非常复杂的特征工程,所以用Char-level的来代替。
模型是用5层的BiLSTM来把char-level的向量转换出每个token的representation,然后过一个softmax层,最后decoder用了一个维特比算法,有点类似HMM?感觉现在来看这篇文章已经没什么意思了。。。

Neural Cross-Lingual Named Entity Recognition with Minimal Resources

EMNLP 2018

面对没有标注语料的语言的NER任务,无监督的从富有标注语料的语言转换成缺少标注的语言被广泛应用。但是有两个问题:如何建立起来两种语言间的映射关系以及如何解决语言间词序的不同。作者这篇文章主要针对unsupervised cross-lingual NER问题:given labeled training data only in a separate source language, we aim to learn a model that is able to perform NER in the target language。
大致模型如下:这里把英语设置为语料丰富的语言。先分别在两种语言上训练各自训练一个单语的embedding,然后(论文里用到了SVD等操作)把两个embedding矩阵transform到shared embedding space。然后为了得到actual word translations,使用nearest-neighbor search的方法。使用的距离度量为CLCS:\(CLCS(x_i,y_i)=2cos(x_i,y_j)-r_T(x_i)-r_S(y_j)\)。其中\(r_T(x_i)\)代表着与\(x_i\)相近的K个\(y_t\)的cos距离的平均。然后我们实际上得到了一个新的dictionary,然后我们重新学一个Bilingual Embeddings,重复若干次后就认为我们得到了Word Translations。
然后就可以把英语语料转换为target语料,同时可以加入char-level的表示(target)作为输入。但是这是直接来自source的,对于target的语言来说是破碎的(order不一致),所以在原来的BiLSTM+CRF中的BiLSTM上加上了self-attention。对于BiLSTM的隐层输出h,用self-attention算一个加权的上下文向量(屏蔽掉自身的word),然后和原来的隐层拼起来送入CRF层。
实验结果显示self-att的确有了一些提升,而translation的方法更好在于引入了target的char-level的信息。但是对于维吾尔语来说,因为和英语在各个方面都有很大不同所以效果不好。作者也说这也是多语言embedding的一个挑战。

Neural Adaptation Layers for Cross-domain Named Entity Recognition

EMNLP 2018

跨领域的迁移NER任务,准备组会讲讲,做了个ppt,不详细写了。。。

Named Entity Recognition with Bidirectional LSTM-CNNs Jason

TACL 2016

应该是一篇经典的早期用神经网络做NER的论文。作者针对之前Collobert的论文存在一些问题:使用简单的前向神经网络,使用固定大小的窗口获取每个词的上下文,会丢弃掉单词之间长距离的关系。以及只依赖word embeddings,不能开发字符一级的影响,例如前缀和后缀。
作者使用了stack-BiLSTM的架构,就是多层的BiLSTM,以及CNN来提Character Features。作者使用的embeddings是可以调整的在整个训练过程中。作者主要用的特征是word embeddings和character embeddings,辅助以大写、词典等作为的特征。然后上层加了一个类似CRF的东西来输出最后的标签。采用的标签体系是BIOES效果,之前的论文结果显示比BIO好。

Natural Language Processing (almost) from Scratch

Collobert的论文,介绍了一个统一的神经网络架构用于解决自然语言处理各种的各种任务,主要是序列标注任务,包括词性标注(POS)、词语组块分析(Chunking)、命名实体识别(NER)以及语义角色标注(SRL)等。因为提的非常早,很多工作也都把这个作为神经网络做NER的比较早的起点来说,当然和现在的网络结构相比肯定不那么合适了,文章比较长,我只挑着看了一些,简单写写。
说他的开创性在于,以往相关的工作往往需要hand feature的大量特征工程,但是他提出从大量的无标签的训练数据中学习到更加本质的特征。作者使用word embedding来做word的表示,来表示提出的这个单词的特征。因为要解决的任务是不定长的序列,作者提出两种方法进一步解决任务。第一种就是基于滑动窗口的方法,主要针对局部的特征。就是根据一个词作为中心词以及他附近的上下文窗口内的词向量为单词打tag,具体来说就是用一个前馈神经网络用窗口内的词向量得到输出作为分类根据。但是对于非常依赖上下文的某一个单词,且该单词并没有出现在窗口范围内,那么该方法就不能取得很好的效果。作者提出用CNN网络来过一遍整个句子,然后再输入到那个前馈神经网络来解决这个问题。就是sentence approach的方法。
为了让embedding能包含更多的语义和语法的信息,从而提升其的表达能力,文章使用了大量的无标签数据来提升模型的性能。这里,文章使用了一种称作 pairwise ranking approach 的方法,希望寻找到一种神经网络的结构能够在给出一个合法的序列时获得一个较高的评分,一个不合法的序列则对应着一个较低的得分。得分高则说明该中心词在当前位置是符合上下文语言的,得分低则说明该中心词在当前位置不符合上下文语义。有点类似word2vec中心词embedding得到的方式,可能这是在word2vec的方法的来源吧?
但是从现在的角度来看使用全连接层等前馈神经网络,来解决序列标注任务已经不太行了。。。

Phonologically Aware Neural Model for Named Entity Recognition in Low Resource Transfer Settings

EMNLP 2016

作者认为NER任务的难点在于,NE可以是任意拼写的格式,尤其在面对多语言的时候,可能一个词在英语是一种格式,在乌兹别克语言又是另一种格式。还有一些问题比如Turkey可以认为是土耳其也可以是火鸡,这种拼写和语义的歧义也是因为语言的形态结构带来的复杂性。
作者提出尽管NER有如上一些难点,但是足够多的单语语料也足够训练出一个优秀的单语标注模型,但是挑战是如何能把这个模型迁移到小数据的语言(语料)上去而使得需要标注或者feature engengineer的工作量尽可能的小。这个迁移过程就会引入不同语言间的种种问题。作者做了一个假设,就是命名实体很可能是跨语言的音译或保留发音模式。作者引入了音韵特征来代替之前的形态结构的特征并加入了attention的机制。
主要是通过一些工具实现language’s script到phonological feature,然后把phonological feature通过一个类似character的BiLSTM的结构,可以和orthographic feature的特征结合。作者基础模型还是BiLSTM+CRF,有个地方改动是在把BiLSTM的输出喂入CRF层之前加了个attention。是对于每个词的BiLSTM层的相应输出t和这个词构成的character BiLSTM得到的矩阵做attention,得到一个向量a和t级联再送进CRF层。
从实验结果来看phonological从att中获得了一些提升,在西班牙语中单语模型达到了比之前好的结果。当然attention的效果也在论文里详细讨论了就不写了。
感觉引入音韵特征有点不太靠谱啊,论文里也没有分析究竟效果的提升是单纯的因为参数增多了,还是这个音韵特征真的起到了效果,消融实验没法单纯的说明这一点吧?不太懂,感觉可能也只能针对特定的小语种这么搞了。

Transfer Learning for Sequence Tagging with Hierarchical Recurrent Networks

ICLR 2017

这篇文章是之前看到EMNLP 2018的一篇做迁移学习的文章的related work并且被归为了MULT的模型。做了一个ppt就简单说说,文章中做了一些假设,并做了一个类似于框架的方法来研究跨语言、跨应用、跨领域的迁移学习做序列标注。模型结构很简单,但是和EMNLP 2018那篇文章相比,没有考虑word embedding在不同领域或者应用的表示空间可能不一样。而且文章提出迁移学习效果一个重要的因素是参数被共享的多少,这一点我觉得不一定,因为共享的参数多也可以认为是在source端训练的比较好,但是我觉得其实并不一定对target真的有那么大作用,只不过是因为target数据少,所以怎么优雅的共享参数(初始化)?

Bidirectional LSTM-CRF Models for Sequence Tagging

arxiv 2015

没有找到这篇文章被投到哪里,但是貌似是第一篇把BiLSTM+CRf的结构用到NLP序列标注上的文章。文章系统比较了LSTM、BiLSTM和CRF等模型结构,在POS任务上得到了当时的最好结果,在NER和chunking上也都比较接近。实验结果显示BiLSTM+CRF的结构对于word embedding的依赖程度更小,但是这篇论文引入了大量的人工特征,所以在之后的工作中大家貌似都用CNN等结构在char-level上做。

Character-Based LSTM-CRF with Radical-Level Features for Chinese Named Entity Recognition

NLPCC-ICCPOL 2016

作者非常新颖的把部首这个概念引入了进来,认为部首相近的一些字的表示应该在向量空间距离较近,因此训练了一个部首embedding,和每个字的embedding结合再送入BiLSTM+CRF模型。个人理解:对于中文来说,字其实类似于英文中的word的概念,而作者认为部首类似于英文中的char的概念。因此这么结合相当于类似于英文中的在char-level的操作。实验效果来看,在没有引入外部的字典的情况下达到了SOTA的效果。

Hybrid semi-Markov CRF for Neural Sequence Labeling

ACL 2018

之前听xy说过semi-crf用在序列标注任务上,之前也看过一些关于semi-hmm的介绍和用的论文,这次正好也看到了semi-crf做NER的。
这是一篇在ACL 2018上的短文,采用的神经网络模型还是之前基础的Bi-LSTM这一套,但是联合使用了CRF和改进的semi-CRF。改进后的semi-crf是指,之前的semi-crf对于段内的word-level的信息没有很好的考虑到,往往是词级别的转移特征经常被忽略。作者在这里把每一段的段内的分数是把这一段内的BiLSTM得到的每个word的输出进行一个加权得到的。同时每个word的表示既考虑到了它本身的输出也级联了位置的embedding和段尾和段头的embedding之差。剩余的semi-crf的和之前的工作一样。同时它还联合训练了一个CRF decoder和HSCRF decoder,目标函数考虑这两个loss,并且在解码阶段选择loss较低的输出。
和之前工作对比发现,只考虑segment的信息会让模型在长实体上识别效果较好,短实体上不如CRF。这也比较直觉:因为短实体可能更加注重于word-level的表示而不是segment-level的表示。但是HSCRF在这两种上都可以表现很好,而且达到了不引入外部知识的情况下的state of the art。
有一篇较早的用semi-crf的论文可能需要我抽空看看,才能更好理解这篇文章。

Learning Named Entity Tagger using Domain-Specific Dictionary

EMNLP 2018

这篇文章感觉还是挺有意思的,值得详细写一下。
随着神经网络在NER任务中的广泛应用,并且效果很好,但是这些深度模型都是需要很多人工标注的数据,但是对于一些特定领域的NER任务来说,很难得到这么多数据。所以就提出了distant supervision的方法。现在的一些利用distant supervision的做法往往都是基于人工设置的一些启发式规则,比如根据字典进行字符串匹配等等。但是这些方法往往会把一些没有在字典中出现的词标记为non-entity,但是这其实并不太对,因为每个字典覆盖的实体都是有限的。所以作者这里把这些词中high-quantity的短语认为是unknown的。同时在用distant supervision方法的时候,可能出现一个token被打上多个标签的情况,因为字典内可能有两个不同的实体词但是有相同的字面值。传统的方法CRF没有办法处理这种multi-label token,所以作者提出了一个fuzzy CRF的方法。同时作者也提出一种新的tagging scheme:Tie or Break,并基于这种方法给出另一个模型AutoNER。
详细说一下:对于一个语料和一个字典,那么每个token可以分成三类:是实体词的一部分(这个词可能有多个标签),或者是unknown标签的一部分,或者是non-entity。先说一下Fuzzy-LSTM-CRF这个模型:
作者引入Modified IOBES机制,对于一个token被打上多个实体标签的他都考虑这些标签并且根据位置给出BIES的位置标签。对于unknown的token,那么这个词将会被打上全部的标签(实体标签数*位置标签数(4)+1(O))。对于non-entity直接给O。基本结构和之前的工作一样都是用BiLSTM得到发射矩阵。而fuzzy CRF也只不过是把原来我们需要最优化true label sequence的比例,这里相当于优化一个所有可能的label sequence的和占的比例(其实这里我也没有细想会不会增加dp的复杂度。。。)。这就是作者说的Fuzzy-LSTM-CRF模型。
再来说AutoNER模型,整体架构如下:

AutoNER模型引入另外一个tag机制:Tie or Break。对于相邻的两个token,对于这两个token指的是同一实体词的话,就打上tie的标签,当这二者之间至少有一个token属于unknown-typed high-quality phrase,那么就打上unknown的标签。否则就打Break标签。两个连续的Break标签之间的token组成的span,打上他匹配的标签类似于modified IOBES机制。当然对于没有相匹配的就给O标签。作者说这么做的理由主要是:当一个entity被部分匹配的时候,其中部分正确的Tie信息得以被利用。并且当一个unigram entity被错误匹配的时候(false positive),Tie or Break部分并不会出错,因为这种词旁边往往是break(这点其实没看懂,感觉上是不会因为这个词影响到别的词的匹配??)。而unigram entity正是字符串匹配中最容易匹配错误的部分。
对于这种机制产生的序列,作者把AutoNER分成两部分来做:第一步做entity span的识别。这时候忽略掉unknown的标签,只为了识别break和tie。作者用BiLSTM的输出u来过一个sigmod,分别得到这个标签是break还是tie的概率,然后算loss进行训练。然后得到entity span后需要给他们分类,还是用BiLSTM得到一个输出向量v,然后过一个softmax层,然后算loss训练。注意到这个过程decode不需要CRF层等,直接用分类层来做,所以效率比Fuzzy-LSTM-CRF效率高。
作者对于distant supervision的字典也做了处理:首先因为字典中可能出现这个词本身不在,但是他的别名(简写)在的情况,这回导致false-positive。所以作者规定匹配的词必需保证它本身在语料中出现过,才可以用别名匹配。但是还有false-negative的问题,作者引入了之前做的工作AutoPhrase来得到领域相关的high-quality phrases,从而扩充字典的功能。从实验效果来看这两个方法都很有效。
实验分别在BC5CDR,NCBI-Disease,LaptopReview这三个特定领域的数据集上跑,结果上来看虽说不如之前的Supervised benchmarks,但是在distant supervision的方法来看达到了STOA的效果。而且AutoNER效果要好于fuzzy-crf,同时distant supervision也有较好的泛化效果。而且AutoNER只需要的外部资源是字典而已,就可以高效distant supervision。
作者在知乎上的一些解释:
1.提出了”Tie or Break” labeling scheme。区别于传统的BIOES labeling scheme,该方法只关心相邻两个tokens之间的关系,是连在一起还是分开。
2.相邻的两个Break之间,就是一个可能的entity span。对于一个给定的span,再做一个(k+1)分类,其中k为NER需要识别的entity types的个数,额外的一类为None。
这样的好处是可以更多的利用字符串匹配得到的信息。Unknown的引入主要是为了最大程度的减少不确定的label对model training的负面影响。

Efficient Contextualized Representation: Language Model Pruning for Sequence Labeling

EMNLP 2018

ELMO等语言模型因为层数参数过多,可能在做具体任务(比如,序列标注任务)在inference阶段会非常耗时。所以作者在ELMO的基础上提出了用dense connection构建了一个新的stack-LSTM的架构LD-Net来训练语言模型并且加入了layer-wise dropout。在特定任务的训练在加上layer selection的一个剪枝过程,最后可以利用少量的参数且不需要重新训练便可以达到和整个预训练的语言模型所达到的效果近似。

Model-Free Prediction

题外话:书上没有按照把所有的方法融合在一起讲prediction的方法来讲,而是分方法分别讲prediction,control这样的,为了看上去的方便,而且自己看视频也有很多地方没看懂,所以就按照视频上的顺序摘抄一下做个记录。

Incremental Implementation

这部分在书中的第二章,当时直接跳过了,在这里做一个记录。
Let \(Q_n\) denote the estimate of its action value after it has been selected n − 1 times,易得:
\(Q_{n+1}=\frac{1}{n}(R_n+\sum_{i=1}^{n-1}R_i)=Q_n+\frac{1}{n}[R_n-Q_n]\)。就是相当于把最后新来的一项平均分成n份和原来的相补。This implementation requires memory only for \(Q_n\) and \(n\), and only the small computation for each new reward.
The general form is

The expression [Target − OldEstimate] is an error in the estimate.The target is presumed to indicate a desirable direction in which to move, though it may be noisy. In the case above, for example, the target is the nth reward.

Monte Carlo Methods

因为只看了一部分所以可能有些偏差。。。
Monte Carlo methods require only experience——sample sequences of states, actions, and rewards from actual or simulated interaction with an environment.
Monte Carlo methods only for episodic tasks. we assume experience is divided into episodes, and that all episodes eventually terminate no matter what actions are selected. Only on the completion of an episode are value estimates and policies changed.
我们可以认为MC是一种基于对于完整的回报(Gt)的平均。

Monte Carlo Prediction

目的: learning the state-value function for a given policy
An obvious way to estimate it from experience, then, is simply to average the returns observed after visits to that state. As more returns are observed, the average should converge to the expected value.
Each occurrence of state s in an episode is called a visit to s.
根据对于一个episode中对同一个状态s的访问计算不同,得到first-visit MC和every-visit MC。
first-visit MC伪代码:

需要注意:我们是按照时光倒流来计算G的(这里貌似也可以考虑折扣因子)。
Both first-visit MC and every-visit MC converge to \(v_\pi(s)\) as the number of visits (or first visits) to s goes to infinity. By the law of large numbers the sequence of averages of these estimates converges to their expected value.
从Blackjack这个例子可能得到的思考:即便我们对于我们完全了解Blackjack的环境,但是我们还是不能准确得到一个关于下一个事件的分布,DP的方法需要我们知道全部的概率分布,但是这往往很不现实。In contrast, generating the sample games required by Monte Carlo methods is easy.The ability of Monte Carlo methods to work with sample episodes alone can be a significant advantage even when one has complete knowledge of the environment’s dynamics.
Whereas the DP diagram includes only one-step transitions, the Monte Carlo diagram goes all the way to the end of the episode.
An important fact about Monte Carlo methods is that the estimates for each state are independent. The estimate for one state does not build upon the estimate of any other state, as is the case in DP. In other words, Monte Carlo methods do not bootstrap.
The computational expense of estimating the value of a single state is independent of the number of states. One can generate many sample episodes starting from the states of interest, averaging returns from only these states, ignoring all others.

Temporal-Difference Learning

这一部分主要是TD(0)。
TD learning is a combination of Monte Carlo ideas and dynamic programming (DP) ideas.
TD methods update estimates based in part on other learned estimates, without waiting for a final outcome (they bootstrap)
constant-α MC:\(V(S_t)=V(S_t)+\alpha[G_t-V(S_t)]\),\(G_t\) is the actual return following time \(t\), and \(alpha\) is a constant step-size parameter.
TD methods need to wait only until the next time step. At time \(t + 1\) they immediately form a target and make a useful update using the observed reward \(R_{t+1}\) and the estimate \(V(S_t+1)\). The simplest TD method makes the update:\(V(S_t)=V(S_t)+\alpha[R_{t+1}+\gamma V(S_{t+1})-V(S_t)]\).
伪代码:

书上有一段关于MC、DP、TD为什么都是估计的一个说法:MC是因为期望下的Gt用了采样得到的return来替代,DP则是因为我们在计算下一步的\(V_\pi\)时候采用的是当前的估计。而TD则综合了他们俩既是sample又是采用了当前状态的估计下一步状态。
Sample updates differ from the expected updates of DP methods in that they are based on a single sample successor rather than on a complete distribution of all possible successors.
TD error:\(\delta_t=R_{t+1}+\gamma V(S_{t+s})-V(S_t)\).
if the array V does not change during the episode (as it does not in Monte Carlo methods), then the Monte Carlo error can be written as a sum of TD errors:

Advantages of TD Prediction Methods

TD methods have an advantage over DP methods in that they do not require a model of the environment, of its reward and next-state probability distributions.
The next most obvious advantage of TD methods over Monte Carlo methods is that they are naturally implemented in an on-line, fully incremental fashion.TD methods one need wait only one time step.
TD methods are much less susceptible to these problems because they learn from each transition regardless of what subsequent actions are taken.(这一部分的的对比没有看太懂,可能是和control之类的比)
For any fixed policy \(\pi\), TD(0) has been proved to converge to vπ, in the mean for a constant step-size parameter if it is sufficiently small.
MC和TD这两种方法很难说谁先收敛到真正的解最快,但是一般:TD methods have usually been found to converge faster than constant-α MC methods on stochastic tasks.

n-step Bootstrapping

The backup diagrams of n-step methods:

The methods that use n-step updates are still TD methods because they still change an earlier estimate based on how it differs from a later estimate.
The natural state-value learning algorithm for using n-step returns is thus,\(V_{t+n}(S_t)=V_{t+n-1}(S_t)+\alpha[G_{t:t+n}-V_{t+n-1}(S_t)]\).Note that no changes at all are made during the first n−1 steps of each episode.
伪代码:

error reduction property:

Because of the error reduction property, one can show formally that all n-step TD methods converge to
the correct predictions under appropriate technical conditions.

Eligibility Traces

The mechanism is a short-term memory vector, the eligibility trace \(Z_t \in R^d\), that parallels the long-term weight vector \(W_t \in R^d\). The rough idea is that when a component of \(W_t\) participates in producing an estimated value, then the corresponding component of \(Z_t\) is bumped up and then begins to fade away.
Forward views are always somewhat complex to implement because the update depends on later things that are not available at the time.MC以及n-step 的方法都属于这种。


待补充。。。。

Dynamic Programming

题外话:以前做题的时候老是碰到dp,不过队内有两位dp大师,我也不怎么输出dp题,没想到最近看书又碰到了dp。。。DP真是个需要智商的东西,很绝望啊。。。
UPD:自己之前以为值迭代和策略迭代相比会更加不稳定,但是后来问了一下why,被告诉其实两者都会产生震荡(不稳定)。

Policy Evaluation (Prediction)

police evalution(prediction problem):We consider how to compute the state-value function \(v_\pi\) for an arbitrary policy \(\pi\).

For our purposes, iterative solution methods are most suitable. The initial approximation, \(v_0\), is chosen arbitrarily (except that the terminal state, if any, must be given value 0), and each successive
approximation is obtained by using the Bellman equation for \(v_\pi\) (4.4) as an update rule:

iterative policy evaluation:在\(v_\pi\)的存在下,找到一个序列的\({v_k}\),使得k趋近于无穷的时候,\(v_k=v_\pi\)。
expected update: To each state s: it replaces the old value of \(s\) with a new value,obtained from the old values of the successor states of s, and the expected immediate rewards, along all the one-step transitions possible under the policy being evaluated.
All the updates done in DP algorithms are called expected updates because they are based on an expectation over all possible next states rather than on a sample next state.
过程伪代码:

注意更新价值函数的时候有两种思路:第一种就是开两个数组old/new,按照之前的式子那样迭代。第二种是in-place,新算出来的值立马代替old,这样每轮迭代,如果一些依赖的状态已经更新了,就用更新后的来计算。in-place的收敛速度更快,但是其中每一轮计算各s的顺序也有很大影响。其实我在这里想到的居然是01背包的空间优化(囧了)。。。

Policy Improvement

Our reason for computing the value function for a policy is to help find better policies.Suppose we have determined the value function vπ for an arbitrary deterministic policy \(\pi\). For some state s we would like to know whether or not we should change the policy to deterministically choose an action \(a \neq \pi(s)\).
根据状态行为对的价值函数,
如果我们没有按照当前的policy选择一个action a,而是自己选择了一个a,并且得到了一个\(q_\pi(s,a)\)是大于原来的\(v_\pi(s)\)的话,也就意味着当前这一步贪心的选择一个比原来好的a哪怕之后还是按照之前的policy进行操作选择action也会比原来的策略好,所以就可以生成一个新的策略了。
policy improvement theorem:对于两个确定性策略\(\pi\)和\(\pi’\),假设对于所有的状态s来说都满足,\(q_\pi(s,\pi'(s))\geq v_\pi(s)\),那也就意味着都满足\(v_\pi'(s)\geq v_\pi(s)\)。
证明过程:

policy improvement:
根据上面在一个状态下选择一个较优的方式,我们可以拓展到在每个状态下在所有action中选择最优策略,规则如下:\(\pi'(s) = argmax_a q_\pi(s, a) = argmax_a \sum_{s’,r} p(s’, r | s, a) (r + \gamma v_\pi(s’))\).The greedy policy takes the action that looks best in the short term–after one step of lookahead–according to \(v_\pi\).
对于随机性的policy,上面的理论也是适用的,当有若干action的都可以达到最优的时候, each maximizing action can be given a portion of the probability of being selected in the new greedy policy. Any apportioning scheme is allowed as long as all submaximal actions are given zero probability.Any apportionment of probability among these actions is permitted.

Policy Iteration

We can thus obtain a sequence of monotonically improving policies and value functions:

E代表a policy evaluation,I代表了a policy improvement。Each policy is guaranteed to be a strict improvement over the previous one (unless it is already optimal). Because a finite MDP has only a finite number of policies, this process must converge to an optimal policy and optimal value function in a finite number of iterations.
伪代码:

Value Iteration

evolution可能很慢,In fact, the policy evaluation step of policy iteration can be truncated in several ways
without losing the convergence guarantees of policy iteration.
One important special case is when policy evaluation is stopped after just one sweep (one update of each state).This algorithm is called value iteration.

伪代码:

Because the max operation in (4.10) is the only difference between these updates, this just means that the max operation is added to some sweeps of policy evaluation. All of these algorithms converge to an optimal policy for discounted finite MDPs.

Asynchronous Dynamic Programming

If the state set is very large, then even a single sweep can be prohibitively expensive.
Asynchronous DP algorithms are in-place iterative DP algorithms that are not organized in terms of systematic sweeps of the state set. These algorithms update the values of states in any order whatsoever, using whatever values of other states happen to be available.
The values of some states may be updated several times before the values of others are updated once. To converge correctly, however, an asynchronous algorithm must continue to update the values of all the states: it can’t ignore any state after some point in the computation. Asynchronous DP algorithms allow great flexibility in selecting states to update.
Of course, avoiding sweeps does not necessarily mean that we can get away with less computation. It just means that an algorithm does not need to get locked into any hopelessly long sweep before it can make progress improving a policy.
We can try to take advantage of this flexibility by selecting the states to which we apply updates so
as to improve the algorithm’s rate of progress. We can try to order the updates to let value information propagate from state to state in an efficient way.

Generalized Policy Iteration

generalized policy iteration (GPI):the general idea of letting policy evaluation and policy improvement processes interact, independent of the granularity and other details of the two processes.所以也就是说之前的三种迭代dp的方法都可以认为是GPI的。
所有的RL方法都可以被建模为GPI。It is easy to see that if both the evaluation process and the improvement
process stabilize, that is, no longer produce changes, then the value function and policy must be optimal.

两个过程都达到稳定,也说明找到了最优策略。
The evaluation and improvement processes in GPI can be viewed as both competing and cooperating.Making the policy greedy with respect to the value function typically makes the value function incorrect for the changed policy, and making the value function consistent with the policy typically causes that policy no longer to be greedy.

Efficiency of Dynamic Programming

DP is sometimes thought to be of limited applicability because of the curse of dimensionality, the fact that the number of states often grows exponentially with the number of state variables. Large state sets do create difficulties, but these are inherent difficulties of the problem, not of DP as a solution method. In fact, DP is comparatively better suited to handling large state spaces than competing methods such as direct search and linear programming.
In practice, DP methods can be used with today’s computers to solve MDPs with millions of states.In practice, these methods usually converge much faster than their theoretical worst-case run times, particularly if they are started with good initial value functions or policies.