Sequence classification and Part-of-Speech tagging

sequence classification

為了解決一詞多義的問題，sequence classification 試圖將劃分句子成分，判斷單詞信息。這有利于machine translate 、 grammar check等應(yīng)用。
實(shí)現(xiàn)的方式有：

• Hidden Markov Models (HMM)
• Maximum Entropy Markov Models (MEMM)
• Conditional Random Fields(CRF)
  運(yùn)用深度學(xué)習(xí)的話，有以下方法：
• Recurrent Neural Networks
• Long/Short-Term Memory Networks
• Convolutional Neural Networks

HMM

• Transition probabilities: 一種詞性跟隨另一種詞性出現(xiàn)的概率。例如：determiner 之后大概率是 noun 或 adjective。
• Emission probabilities： 給定一種詞性，不同單詞是這一詞性的概率。例如： 對于一個句子中的verb來說，大樣本下有較大概率是 ”is“。
• Beam search: 每一個詞可能有n種詞性， 在search中只考慮概率最高的前β種詞性。

結(jié)合以上三個概念，HMM 模型的工作流程為：

1. 跟據(jù)句子每一個具體的單詞，計算其所有詞性的概率（Emission probabilities）。
2. 從第一個單詞開始，選擇概率最大的β種詞性，并計算與下一個單詞β種詞性的概率（transition probabilities）
3. 遞歸實(shí)現(xiàn)步驟2，直到句子結(jié)束。
4. 返回所有符合要求的結(jié)果。

example

HMM的局限性：

HMM model

• 不同state之間僅有其觀察對象相關(guān)，state與state之間認(rèn)為是彼此獨(dú)立的，而觀察對象僅與當(dāng)前state有關(guān)。
• 學(xué)習(xí)到的是聯(lián)合概率P(Y, X) 而非條件概率P(Y|X)。

MEMM

MEMM是為了解決HMM的局限性而誕生。就我的理解來看，當(dāng)β=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， 實(shí)際上MEMM選擇了概率較小的路徑。

CRF

MEMM之所以會有l(wèi)abel bias 的問題，主要是因?yàn)樗嬎愕氖莑ocal probability，也即計算的概率只跟前一個state有關(guān)。而當(dāng)前一個state只與部分state集合有關(guān)的時候，就不可避免的出現(xiàn)bias的問題。

CRF思路和MEMM差不多，但它計算的是global probability。這樣就能解決 label bias的問題。簡單來說就是計算整個句子所有可能的單詞詞性組合的概率再進(jìn)行歸一化。

相關(guān)閱讀

概率圖模型體系：HMM、MEMM、CRF
維特比算法

POS tagging

若使用HMM進(jìn)行詞性標(biāo)注，對于某一句話很可能出現(xiàn)只由noun組合構(gòu)成的情況。
而是要MEMM或CRF，就能避免這種情況的發(fā)生。

The PENN tree bank tag set

POS Tagging Performance

• baseline : 90%準(zhǔn)確率。 僅取一個單詞概率最高的詞性
• Standard : 93% 準(zhǔn)確率。 考慮不同詞性間的組合概率（不考慮sequence）
• sequence classifier：97%。 結(jié)合CRF 等進(jìn)行判斷

參考

List of software for POS tagging

Grammar and Parsing

當(dāng)能夠精準(zhǔn)地對語句中的單詞進(jìn)行詞性標(biāo)注時（POS tagging），對sentence的語法檢查和phrase劃分就有了可靠的依據(jù)。
例如，對于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類似，只是用概率來表達(dá)。 Transition probabilities 和 Emission probabilities。

  
  

對于生成的樹（見CFG example）， 若樹是從上往下生成的，那就是一個自然語言的產(chǎn)生器，如果從下往上生成，就是parsing的過程。

Parsing 可使用CYK算法實(shí)現(xiàn)

Lexicalised parsing

PCFG的問題是僅僅關(guān)注了POS tag 的組合概率，而沒有關(guān)注實(shí)際生活中詞的用法上的頻率問題。 因此，lexicalised parsing是在PCFG的基礎(chǔ)上，基于單詞事實(shí)上的用法對概率做修正。
因此， Lexicalised PCFGs 可以更好的應(yīng)對詞意不明的情況。例如：

example

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

Dependency parsing

Dependency syntax 假定lexical items之間是存在雙向?qū)ΨQ的關(guān)聯(lián)關(guān)系，并由此構(gòu)成句子的句法結(jié)構(gòu)。
簡單來說，類似與一種縮寫和擴(kuò)寫的技巧。例如： 張三在吃飯→（穿著睡衣的）張三在（樹底下）吃飯

實(shí)現(xiàn)方法有兩類：

• Graph algorithms:
  • 考慮所有的 word pairs（確定短語組合有哪些）
  • 針對句子的所有pair 建立一棵最大生成樹。
• Transition-based Approaches
  -Shift-Reduce Parser: MaltParser.

其他資源

Treebank for different language

Word sense

word sense 就是試圖讓機(jī)器理解一個單詞所要表達(dá)的具體意思。

相關(guān)術(shù)語解釋

• Homonymy：指同一個單詞，可能存在完全不相關(guān)的不同意思。例如：1) I put my money in the bank₁. 2) We took the picture in the east bank₂ of the Nile river. bank₁ 指的是金融機(jī)構(gòu)， bank₂指的是坡地。
• Polysemy： 指同一個單詞，有相關(guān)聯(lián)的不同意思。例如： 1）The bank₁ was constructed in 1875 out of local red brick. 2) I withdrew the money from the bank₂. 這里bank₁指的是一個金融機(jī)構(gòu)的建筑物， bank₂指的是金融機(jī)構(gòu)
• 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是這種分類法的葉子節(jié)點(diǎn)，也是某一特定entity的名稱。例如： London is an instance of city。
• class：除去instance以外剩下的都可以當(dāng)作是class?？梢哉J(rèn)為class就是instance某一方面特點(diǎn)的抽象。例如： city is a class， city is a hyponym（subclass） of municipality or location
• Thesaurus： 將單詞安裝以上術(shù)語的定義分類整理形成的詞典。例如 Wordnet

Thesaurus method for word similarity and relatedness

通過子類、父類及class等定義，Thesaurus 的數(shù)據(jù)結(jié)構(gòu)其實(shí)是一棵樹，而通過thesaurus 判斷單詞相似性的方法有兩種：

• path-based：該方法認(rèn)為，連接樹中兩個item之間的邊的數(shù)目越少，這兩個item就越相近。使用1/(邊數(shù)+1) 表示其近似程度。但這一方面的問題在于，對于某些處于較低層次的item來說，其與兄弟節(jié)點(diǎn)的距離和它與子節(jié)點(diǎn)的距離可能是一樣的，但是兄弟節(jié)點(diǎn)與這一item的相似度可能很低。
• information content(IC)： 這一方法認(rèn)為，兩個item是否相似，與其包含的共同子結(jié)點(diǎn)有關(guān)。
  • IC = -logP(c)， P(c) = c的所有子孫節(jié)點(diǎn)數(shù)目 / 整棵樹的總結(jié)點(diǎn)數(shù)，表達(dá)的是任取一個節(jié)點(diǎn)，這個節(jié)點(diǎn)屬于某一類的概率。位于高層次的節(jié)點(diǎn)概率更小，說明其范疇越窄，IC越大
  • Lowest common subsumer(LCS): LCS(c₁, c₂)指最近一個能同時包含c₁和c₂的父節(jié)點(diǎn)。
  • Resnik’s similarity: sim_resnik = IC(LCS(c₁, c₂)) = -logP(LCS(c₁, c₂))。顯然，若兩個節(jié)點(diǎn)的LCS所在層次越高，說明兩節(jié)點(diǎn)所在的范疇越窄，就越可能是相似的。
  • Dekang lin mehod: sim_lin(c₁, c₂) = 2 logP(LCS(c₁, c₂))/(logP(c₁)+logP(c₂))
• The Lesk algorithm: 該算法認(rèn)為A和B的相似程度可以通過計算其注釋的相似程度來反映。

Distributional model for similarity

Thesaurus-based 的最大問題是：不是每一種語言都有這樣的thesaurus，thesaurus也無法攘括一個語言所有的詞匯。同時，動詞和形容詞沒有明確的父子關(guān)系，thesaurus對于這類詞的分類效果也不好。

直接上兩個單詞如果意思相近，那么他們的上下文應(yīng)該也是相近的。 這有點(diǎn)類似與 word embedding。但對于單詞 w₁和 w₂來說， 這兩個詞不能是同時出現(xiàn)的。例如 look forward 經(jīng)常一起出現(xiàn)，但是look和forward是兩個詞。

上下文相似的單詞意思更可能相近

Word Sense Disambiguation (WSD)

參見York大學(xué)的Multilingual Word Sense Disambiguation System

Information Extraction

建立見wordsense和POS tagging的基礎(chǔ)上， information extraction(IE)要做的是將非結(jié)構(gòu)化的文本轉(zhuǎn)化為結(jié)構(gòu)化的表單信息的方式。例如常見的行程信息，預(yù)訂酒店收到預(yù)定信息的確定短信時，很多智能手機(jī)上可以將這些從短信中提取最重要的信息，如時間、位置、酒店名稱等，轉(zhuǎn)化為卡片的形式，提升可讀性。這就是所謂的智慧短信。 IE是一個很寬泛的概念，包括以下子任務(wù)：

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

Named Entity Recognition

• Named Entity (NE): 其實(shí)就是任意一個instance的父類（class）。最常見的class或category包括 person, location and organisation等。

NER的任務(wù)包括： 1）識別文本中那些部分可以作為一個NE（類似parsing中找到word phrase），2） 將找到的部分分類到一個具體的NE中去。
Standard NER算法是一種 word-by-word sequence labelling task。通過label去判斷某個phrase的邊界和類別

• 可以采用類似POS tagging的方法，運(yùn)用CRF或MEMM實(shí)現(xiàn) part of a named entity
• 也可以使用gazetteers 來分配label。 gazetteers和thesaurus 類似。

Relation extraction

Relation extraction指的是識別NE之間關(guān)系的過程

Relation extraction example

這個問題同樣是一個有監(jiān)督學(xué)習(xí)的問題：

1. 先固定一個relation跟entity的集合
2. 找一個手動標(biāo)記好entities和relation的語料庫用于訓(xùn)練
3. 測試模型的效果。
   常用的模型有：SVM, Logistic Regression, Naive Bayes, Perceptron.

對于無監(jiān)督學(xué)習(xí)來說，relation只能是文本之間的連接符。即模型之間分類出來的各個NE之間有關(guān)系，但具體是什么關(guān)系不管。
目前最先進(jìn)的是Stanford 的OpenIE 系統(tǒng)。

Temporal expression extraction

這一任務(wù)的目的是想要找出句子中的指代關(guān)系。例如：

• Absolute：20th March 2020（信息是明確的）
• Relative: yesterday（對于什么時間來說的yesterday？）

• Duration: 3 hours（在什么時間點(diǎn)基礎(chǔ)上的三個小時？）
  這一問題的實(shí)現(xiàn)，需要參考一個標(biāo)志性單詞，用來判斷是否出現(xiàn)的指代關(guān)系。

  
  
  Temporal lexical triggers

通常來說可以運(yùn)用 sequence classifier（見POS tagging）實(shí)現(xiàn)，整合以下features（有監(jiān)督學(xué)習(xí)）:

• Token: 指需要被標(biāo)記的target token，例如具體的時間、人名等（NER實(shí)現(xiàn)）
• Tokens in window: 指target token的上下文，類似co-occurrence 中的偏移量β，因?yàn)橐话阏J(rèn)為指代關(guān)系不會離其具體實(shí)體太遠(yuǎn)。
• POS tags: target token 及其Windows token，用于判斷關(guān)系
• Lexical triggers：在temporal terms中出現(xiàn)過的所有單詞集合。

Temporal normalization

在提取出temporal terms 之后，有時會希望能夠 normalize temporal expression。效果如下：

example

這樣的話就有一個starting point 來確定指代的時間了，也稱為 temporal anchor
但事實(shí)是當(dāng)前的方法基本都是人工寫規(guī)則來判斷的，因?yàn)閷?shí)際生活中沒人這么說話（我在XX年XX月XX日的前一天 ...）

相關(guān)資源

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