Sequence classification and Part-of-Speech tagging

sequence classification

为了解决一词多义的问题，sequence classification 试图将划分句子成分，判断单词信息。这有利于machine translate 、 grammar check等应用。
实现的方式有：

• Hidden Markov Models (HMM)
• Maximum Entropy Markov Models (MEMM)
• Conditional Random Fields(CRF)
  运用深度学习的话，有以下方法：
• Recurrent Neural Networks
• Long/Short-Term Memory Networks
• Convolutional Neural Networks

HMM

• Transition probabilities: 一种词性跟随另一种词性出现的概率。例如：determiner 之后大概率是 noun 或 adjective。
• Emission probabilities： 给定一种词性，不同单词是这一词性的概率。例如： 对于一个句子中的verb来说，大样本下有较大概率是 ”is“。
• Beam search: 每一个词可能有n种词性， 在search中只考虑概率最高的前β种词性。

结合以上三个概念，HMM 模型的工作流程为：

1. 跟据句子每一个具体的单词，计算其所有词性的概率（Emission probabilities）。
2. 从第一个单词开始，选择概率最大的β种词性，并计算与下一个单词β种词性的概率（transition probabilities）
3. 递归实现步骤2，直到句子结束。
4. 返回所有符合要求的结果。

example

HMM的局限性：

HMM model

• 不同state之间仅有其观察对象相关，state与state之间认为是彼此独立的，而观察对象仅与当前state有关。
• 学习到的是联合概率P(Y, X) 而非条件概率P(Y|X)。

MEMM

MEMM是为了解决HMM的局限性而诞生。就我的理解来看，当β=len(state set)的时候，HMM就变成了MEMM。也即MEMM会考虑所有可能的组合，但同样是基于马尔科夫链的。也即只考虑前一个state与后一个state的影响，也就是计算local probability。
而这样的后果就是会遇到 label bias的问题：

MEMM：label bias problem

state 1 会偏向于在第二个位置上取 state 2
但如果全局计算，P(1-> 1-> 1-> 1)= 0.4 x 0.45 x 0.5 = 0.09 ，
P(2->2->2->2)= 0.2 X 0.3 X 0.3 = 0.018， 实际上MEMM选择了概率较小的路径。

CRF

MEMM之所以会有label bias 的问题，主要是因为他计算的是local probability，也即计算的概率只跟前一个state有关。而当前一个state只与部分state集合有关的时候，就不可避免的出现bias的问题。

CRF思路和MEMM差不多，但它计算的是global probability。这样就能解决 label bias的问题。简单来说就是计算整个句子所有可能的单词词性组合的概率再进行归一化。

相关阅读

概率图模型体系：HMM、MEMM、CRF
维特比算法

POS tagging

若使用HMM进行词性标注，对于某一句话很可能出现只由noun组合构成的情况。
而是要MEMM或CRF，就能避免这种情况的发生。

The PENN tree bank tag set

POS Tagging Performance

• baseline : 90%准确率。 仅取一个单词概率最高的词性
• Standard : 93% 准确率。 考虑不同词性间的组合概率（不考虑sequence）
• sequence classifier：97%。 结合CRF 等进行判断

参考

List of software for POS tagging

Grammar and Parsing

当能够精准地对语句中的单词进行词性标注时（POS tagging），对sentence的语法检查和phrase划分就有了可靠的依据。
例如，对于verb phrase （VP）：
VP → Verb PP leaving on Thursday
VP → Verb NP PP leave London in the morning

Parsing 的三种方法：

• Probabilistic parsing: context-free grammars
• Lexicalised parsing
• Dependency parsing

Probabilistic parsing: context-free grammars

Context-free grammars (CFGs) 由三个要素组成：

• Terminals
• Non-terminals
• Rules

CFG example

• Probabilistic CFG: 与CFG类似，只是用概率来表达。 Transition probabilities 和 Emission probabilities。

  
  

对于生成的树（见CFG example）， 若树是从上往下生成的，那就是一个自然语言的产生器，如果从下往上生成，就是parsing的过程。

Parsing 可使用CYK算法实现

Lexicalised parsing

PCFG的问题是仅仅关注了POS tag 的组合概率，而没有关注实际生活中词的用法上的频率问题。 因此，lexicalised parsing是在PCFG的基础上，基于单词事实上的用法对概率做修正。
因此， Lexicalised PCFGs 可以更好的应对词意不明的情况。例如：

example

PCFG achieves ~73% on Penn TreeBank.
State-of-the art ~92%: Lexicalised PCFG.

Dependency parsing

Dependency syntax 假定lexical items之间是存在双向对称的关联关系，并由此构成句子的句法结构。
简单来说，类似与一种缩写和扩写的技巧。例如： 张三在吃饭→（穿着睡衣的）张三在（树底下）吃饭

实现方法有两类：

• Graph algorithms:
  • 考虑所有的 word pairs（确定短语组合有哪些）
  • 针对句子的所有pair 建立一棵最大生成树。
• Transition-based Approaches
  -Shift-Reduce Parser: MaltParser.

其他资源

Treebank for different language

Word sense

word sense 就是试图让机器理解一个单词所要表达的具体意思。

相关术语解释

• Homonymy：指同一个单词，可能存在完全不相关的不同意思。例如：1) I put my money in the bank₁. 2) We took the picture in the east bank₂ of the Nile river. bank₁ 指的是金融机构， bank₂指的是坡地。
• Polysemy： 指同一个单词，有相关联的不同意思。例如： 1）The bank₁ was constructed in 1875 out of local red brick. 2) I withdrew the money from the bank₂. 这里bank₁指的是一个金融机构的建筑物， bank₂指的是金融机构
• Synonyms：指不同的单词在上下文中有相近的意思。例如：coach/sofa, big/large。但基本上没有完全一致的情况。
• Antonyms： 在某方面意思相反的一对词。例如：hot/cold, light/dark
• hyponym: 指一个词是另一个词的子类。例如： car is a hyponym of vehicle
• hypernym： 指一个词是另一个词的父类。例如：vehicle is a hypernym of car
• instance：instance是这种分类法的叶子节点，也是某一特定entity的名称。例如： London is an instance of city。
• class：除去instance以外剩下的都可以当作是class。可以认为class就是instance某一方面特点的抽象。例如： city is a class， city is a hyponym（subclass） of municipality or location
• Thesaurus： 将单词安装以上术语的定义分类整理形成的词典。例如 Wordnet

Thesaurus method for word similarity and relatedness

通过子类、父类及class等定义，Thesaurus 的数据结构其实是一棵树，而通过thesaurus 判断单词相似性的方法有两种：

• path-based：该方法认为，连接树中两个item之间的边的数目越少，这两个item就越相近。使用1/(边数+1) 表示其近似程度。但这一方面的问题在于，对于某些处于较低层次的item来说，其与兄弟节点的距离和它与子节点的距离可能是一样的，但是兄弟节点与这一item的相似度可能很低。
• information content(IC)： 这一方法认为，两个item是否相似，与其包含的共同子结点有关。
  • IC = -logP(c)， P(c) = c的所有子孙节点数目 / 整棵树的总结点数，表达的是任取一个节点，这个节点属于某一类的概率。位于高层次的节点概率更小，说明其范畴越窄，IC越大
  • Lowest common subsumer(LCS): LCS(c₁, c₂)指最近一个能同时包含c₁和c₂的父节点。
  • Resnik’s similarity: sim_resnik = IC(LCS(c₁, c₂)) = -logP(LCS(c₁, c₂))。显然，若两个节点的LCS所在层次越高，说明两节点所在的范畴越窄，就越可能是相似的。
  • Dekang lin mehod: sim_lin(c₁, c₂) = 2 logP(LCS(c₁, c₂))/(logP(c₁)+logP(c₂))
• The Lesk algorithm: 该算法认为A和B的相似程度可以通过计算其注释的相似程度来反映。

Distributional model for similarity

Thesaurus-based 的最大问题是：不是每一种语言都有这样的thesaurus，thesaurus也无法攘括一个语言所有的词汇。同时，动词和形容词没有明确的父子关系，thesaurus对于这类词的分类效果也不好。

直接上两个单词如果意思相近，那么他们的上下文应该也是相近的。 这有点类似与 word embedding。但对于单词 w₁和 w₂来说， 这两个词不能是同时出现的。例如 look forward 经常一起出现，但是look和forward是两个词。

上下文相似的单词意思更可能相近

Word Sense Disambiguation (WSD)

参见York大学的Multilingual Word Sense Disambiguation System

Information Extraction

建立见wordsense和POS tagging的基础上， information extraction(IE)要做的是将非结构化的文本转化为结构化的表单信息的方式。例如常见的行程信息，预订酒店收到预定信息的确定短信时，很多智能手机上可以将这些从短信中提取最重要的信息，如时间、位置、酒店名称等，转化为卡片的形式，提升可读性。这就是所谓的智慧短信。 IE是一个很宽泛的概念，包括以下子任务：

• Named Entity Recognition(NER)
• Relation Extraction
• Temporal expression extraction
• Coreference resolution
• Event extraction
• Slot filling
• Entity linking

Named Entity Recognition

• Named Entity (NE): 其实就是任意一个instance的父类（class）。最常见的class或category包括 person, location and organisation等。

NER的任务包括： 1）识别文本中那些部分可以作为一个NE（类似parsing中找到word phrase），2） 将找到的部分分类到一个具体的NE中去。
Standard NER算法是一种 word-by-word sequence labelling task。通过label去判断某个phrase的边界和类别

• 可以采用类似POS tagging的方法，运用CRF或MEMM实现 part of a named entity
• 也可以使用gazetteers 来分配label。 gazetteers和thesaurus 类似。

Relation extraction

Relation extraction指的是识别NE之间关系的过程

Relation extraction example

这个问题同样是一个有监督学习的问题：

1. 先固定一个relation跟entity的集合
2. 找一个手动标记好entities和relation的语料库用于训练
3. 测试模型的效果。
   常用的模型有：SVM, Logistic Regression, Naive Bayes, Perceptron.

对于无监督学习来说，relation只能是文本之间的连接符。即模型之间分类出来的各个NE之间有关系，但具体是什么关系不管。
目前最先进的是Stanford 的OpenIE 系统。

Temporal expression extraction

这一任务的目的是想要找出句子中的指代关系。例如：

• Absolute：20th March 2020（信息是明确的）
• Relative: yesterday（对于什么时间来说的yesterday？）

• Duration: 3 hours（在什么时间点基础上的三个小时？）
  这一问题的实现，需要参考一个标志性单词，用来判断是否出现的指代关系。

  
  Temporal lexical triggers

通常来说可以运用 sequence classifier（见POS tagging）实现，整合以下features（有监督学习）:

• Token: 指需要被标记的target token，例如具体的时间、人名等（NER实现）
• Tokens in window: 指target token的上下文，类似co-occurrence 中的偏移量β，因为一般认为指代关系不会离其具体实体太远。
• POS tags: target token 及其Windows token，用于判断关系
• Lexical triggers：在temporal terms中出现过的所有单词集合。

Temporal normalization

在提取出temporal terms 之后，有时会希望能够 normalize temporal expression。效果如下：

example

这样的话就有一个starting point 来确定指代的时间了，也称为 temporal anchor
但事实是当前的方法基本都是人工写规则来判断的，因为实际生活中没人这么说话（我在XX年XX月XX日的前一天 ...）

相关资源

Stanford Temporal Tagger
Temporal expression normalisation in natural language texts
Stanford CoreNLP
IEPY-tool for information extraction