往期文章請點這里

往期文章請點這里

Overview

●What is part of speech tagging?
●Markov chains
●Hidden Markov models
●Viterbi algorithm
●Example

Part of Speech Tagging

詞性標注（Part of Speech Tagging），簡稱POS Tagging，是自然語言處理（NLP）中的一個任務，它涉及到識別文本中每個單詞的詞性類別。詞性，或稱詞類，是指一個詞在句子中的語法功能，如名詞、動詞、形容詞、副詞等。
詞性標注對于理解句子結構和語義非常重要，它可以幫助計算機更好地解析語言，從而支持諸如機器翻譯、信息檢索、文本摘要、情感分析等高級語言處理任務。例如，在句子 “The cat sat on the mat” 中，詞性標注可能會標記 “The” 為定冠詞（DT），“cat” 為名詞（Noun），“sat” 為動詞（Verb），“on” 為介詞（Preposition），“the” 為定冠詞（DT），“mat” 為名詞（Noun）。通過這種方式，詞性標注為進一步的語言分析提供了基礎。
例子：

關于詞性標簽縮寫可參照：

Lexical Term	Tag	Example Words
Noun	NN	something, nothing
Verb	VB	learn, study
Determiner	DT	the, a
Wh-adverb	WRB	why, where
Adjective	JJ	big, happy
Adverb	RB	quickly, very
Pronoun	PRP	he, she, it
Preposition	IN	on, at, of
Conjunction	CC	and, but, or
Possessive	POS	's, his, her
Article	ART	the, a, an
Numeral	CD	one, two, three
Exclamation	UH	oh, wow
Auxiliary	VBZ	is, are, has
Modal	MD	can, could, will
Comparative	JJR	bigger, faster
Superlative	JJS	biggest, fastest
Gerund	VBG	running, studying
Infinitive	VBN	to run, to study
Participle	VBD	ran, studied
Interjection	INTJ	hello, goodbye

請注意，詞性標簽的命名可能因不同的詞性標注系統而有所不同，但上述表格提供了一些常見的詞性標簽和示例。
詞性標簽的應用

命名實體識別（Named Entity Recognition, NER）:命名實體識別是識別文本中的特定實體，如人名、地點、組織、日期等。詞性標注在此過程中非常有用，因為它可以幫助確定實體的邊界。例如，如果一個名詞（NN）后面跟著一個特定的詞性，如地名（例如“New York”），詞性標注可以幫助確定這個名詞是一個地點實體。

語音識別（Speech Recognition）:語音識別系統將口語轉化為文本。詞性標注在此過程中有助于提高識別的準確性。由于口語中的語法結構可能不如書面語規范，詞性標注可以幫助系統理解句子結構，從而更準確地將口語轉化為正確的文本形式。

指代消解（Coreference Resolution）:指代消解是確定文本中不同代詞或名詞短語指向相同實體的過程。詞性標注有助于識別和匹配可能的指代關系。例如，如果一個代詞（如“he”）出現在句子中，詞性標注可以幫助確定這個代詞的性別和數量，進而幫助系統找到它所指的名詞短語。上面的圖中，“埃菲爾鐵塔位于巴黎，它高324米”，這里可以用指代消解推斷“它”是指什么。

Markov Chains

上例中，learn是動詞，在英語語法中，動詞后面會接什么詞性的單詞呢？大概率是名詞。
這個現象也稱為：Part of Speech Dependencies

這里使用可視化的方式來表示單詞序列的詞性變換，這個也是馬爾科夫鏈

馬爾科夫鏈可以表示為一個有向圖，圖中的節點表示模型的狀態（state），這里 Q = { q 1 , q 2 , q 3 } Q=\{q_1,q_2,q_3\} Q={q1?,q2?,q3?}

Markov Chains and POS Tags

POS tags as States

將句子看做是帶有相關詞性標注的詞序列，就可以用馬爾科夫鏈來表示這個序列：

Transition probabilities

將邊加上狀態轉移（過渡）概率，可得到下圖：

馬爾科夫鏈有一個非常重要的假設或者說性質，就是：下一個事件的概率僅僅取決于當前事件。例如在下圖中，下一個詞的狀態只有當前詞learn來決定，而與前面的詞無關，只需要看綠色圈圈即可。

The transition matrix

可用矩陣來保存狀態轉移概率：

矩陣每一行的和為1，即：${\sum }_{j=1}^N{a}_{ij}=1$

Initial probabilities

對于句子的第一個詞，沒有前一個狀態來決定其狀態：

我們可以引入一個初始概率$\pi$來表示初始單詞詞性生成概率：

將表格寫成矩陣的形式為：
$$A=\left[\begin{array}{ccc}0.4& 0.1& 0.5\\ 0.2& 0.2& 0.6\\ 0.4& 0.3& 0.3\\ 0.2& 0.3& 0.5\end{array}\right]$$

Hidden Markov Models

Hidden表示狀態是隱藏的，可將詞性標簽的狀態看做是隱藏狀態，因為它們從文本數據中不直接可觀察到。機器能觀察到的只有句子中的單詞。我們用虛線節點表示隱藏狀態，則其過渡概率可以用N+1乘N維的矩陣A表示，N是隱藏狀態的數量。

Emission probabilities

發射概率指的是在給定一個特定的狀態時，觀察到某個具體輸出（或觀察值）的概率。簡單來說，它描述了在某個隱藏狀態下，某個可見事件（如單詞、聲音等）發生的可能性。例如這里在隱藏狀態VB的狀態下，生成一些詞（觀測值）的概率如下圖所示：

右邊是發射概率的表格形式，發射矩陣表示詞性標簽代表的每個最終隱藏狀態到語料庫中的M個單詞的轉換概率。
同樣的，每一行的概率和為1，即：${\sum }_{j=1}^V{b}_{ij}=1$
注意，圖示中三個詞在不同隱藏狀態下的生成概率都大于0，是因為詞在不同上下文中可能會有不同的詞性。
He lay on his back.
I’ll be back.
第一句back是名詞，第二句是副詞。

Summary

States:
Q = { q 1 , ? , q N } Q = \{q_1, \cdots, q_N\} Q={q1?,?,qN?}
Transition matrix:
$$A=\left[\begin{array}{ccc}{a}_{1,1}& ?& a_{1,N}\\ 0& ?& ?\\ a_{N+1,1}& ?& a_{N+1,N}\end{array}\right]$$
Emission matrix:
$$B=\left[\begin{array}{ccc}{b}_{1,1}& ?& b_{1V}\\ ?& ?& ?\\ b_{N1}& ?& a_{NV}\end{array}\right]$$

Calculating Probabilities

Transition probabilities

根據實例計算轉移概率，假設語料庫如下：

我們用顏色來表示不同的詞性標簽，從詞庫中可以統計得到，例如藍色到紫色出現了兩次，語料庫中以藍色開頭的標簽數量是3：

transition probability:

要計算馬爾科夫模型的所有轉移概率，必須統計語料庫中所有標簽對出現次數。
1.Count occurrences of tag pairs
$$C(t_{i?1},t_i)$$
2.Calculate probabilities using the counts
$$P(t_i|t_{i?1})=\frac{C(t_{i?1},t_i)}{{\sum }_{j=1}^{N}C(t_{i?1},t_j)}$$

The corpus

假設有以下語料庫：
In a Station of the Metro
The apparition of these faces in the crowd :
Petals on a wet , black bough .
語料庫中每一行是一個單獨的句子。先在句首添加起始標記，以便計算初始概率：

然后將所有字母轉成小寫字母，這里沒有去掉標點，因為是一個toy model

Populating the Transition Matrix

先準備好空表：

先用與相關標記的計數來填充矩陣的第一列（矩陣的行代表當前狀態，列代表下一個狀態，值代表從當前狀態轉移到下一個狀態的轉移概率），先用不同顏色來標記狀態：

對于第一列，需要計算下面標記組合出現的次數

得到以下結果：

按這個方式可以填充其他部分，這里有一個trick，注意到語料庫中沒有動詞VB，所以，矩陣中VB所在的行列均為0：

最后結果如下（這里O-O，在語料中出現了八次，注意最后一句加上標點，有4次）：

接下來計算轉移概率：

但是VB這行會出現分母為0的情況。

Smoothing

為解決這個問題，需要加上一個很小的值$?$，最后公式變成：
$$P(t_i|t_{i?1})=\frac{C(t_{i?1},t_i)+?}{{\sum }_{j=1}^{N}C(t_{i?1},t_j)+N\times ?}$$
分母加上一項，以保證概率總和為1

這里如果用$?=0.001$，這轉移矩陣就得到：

平滑之后沒有為0的概率，VB的轉移概率是相等的。
實際操作中，第一行不需要加$?$，加上會使得標點符號也會有概率出現在句首，這個是不科學的。

Populating the Emission Matrix

上面的轉移矩陣只考慮了詞性的轉化，這里需要將具體的詞也考慮進來，例如：

我們希望計算一個詞性標簽與特定詞語的共現次數，例如：

進一步用復雜一點例子：

以第一列為例，這里不是計算標簽對的數量，而是計算一個詞與特定標簽相關聯的次數：

例如$C(NN,in)=0$表示在語料庫中in與Noun標簽并無關聯，同理in與動詞也無關系，在其他標簽類別中出現了兩次：

最后的概率由以下公式計算：
$$\begin{gathered} P(w_i|t_i)=\frac{C(t_i,w_i)+?}{{\sum }_{j=1}^{N}C(t_i,w_j)+N??} \\ =\frac{C(t_i,w_i)+?}{C(t_i)+N??} \end{gathered}$$
其中，大與字母N代表標簽數，大寫字母V代表我們的詞匯表大小。

The Viterbi Algorithm

Viterbi algorithm - a graph algorithm

維特比算法是一個圖算法，下面以句子：I love to learn為例，來演示其原理。

這里綠色顯示的轉移概率是0.3，橙色顯示的發射概率為0.5

那么第一個單詞為I的概率實際是聯合概率：0.5×0.3=0.15

接下來觀察到love有兩種可能，分別是O→NN和O→VB
由于VB對應生成love的發射概率要大，因此選擇O→VB：

這I后面接love的概率為：0.5×0.5=0.25

由于love后面的to只會在O狀態下出現：

love后面接to的概率為：0.2×0.4=0.08
最后是learn，只會在VB狀態出現：

其出現概率是0.5×0.2=0.1

最后可得到所有單詞序列對應的隱藏狀態概率為：
$$0.15?0.25?0.08?0.1=0.0003$$

Viterbi algorithm Steps

一共三步：
1.Initialization step
2.Forward pass
3.Backward pass

這里要用到兩個輔助矩陣：

矩陣C保存中間的最優概率，矩陣D保存訪問過的狀態的索引。
下面詳細講解三個步驟。

Viterbi: Initialization

初始化步驟是填充輔助矩陣C和D第一列的：

填充結果為：

填充公式為：
$$\begin{gathered} c_{i,1}={\pi }_i?b_{i,cindex(w_1)} \\ =a_{1,i}?b_{i,cindex(w_1)} \end{gathered}$$
C矩陣中的第一列表示從圖中的起始狀態$\pi$到第一個標簽$t_i$和單詞$w_1$的轉換概率，示例圖中有三個隱藏狀態。
從公式中可以看到，第一列單詞$w_1$出現的概率是初始化概率乘以狀態發射概率，初始化概率從矩陣A中可以得到，發射概率從矩陣B中可以得到。
對于矩陣D：

第一列直接設置為0即可：
$$d_{i,1}=0$$
因為沒有遍歷任何之前的詞性標簽。

Viterbi: Forward Pass

前向傳遞是填充矩陣C和D的第二步。

對于矩陣C，使用的公式為：
$$c_{i,j}=\underset{k}{\max }{c}_{k,j?1}?a_{k,i}?b_{i,cindex(w_j)}$$
例如要計算$c_{1,2}$

$$c_{1,2}=\underset{k}{\max }{c}_{k,1}?a_{k,1}?b_{i,cindex(w_2)}$$
$b_{i,cindex(w_2)}$是狀態$t_1$到$w_2$的發射概率
$a_{k,1}$是狀態$t_k$到當前狀態$t_1$的轉移概率
$t_{k1}$表示已經遍歷的前一個路徑的概率
這里選擇k使得整個公式最大化

對于矩陣D：

使用以下公式：
$$d_{i,j}=\underset{k}{\mathrm{argmax}}{c}_{k,1}?a_{k,1}?b_{i,cindex(w_2)}$$

Viterbi: Backward Pass

到這一步，C和D已經填充完畢
現在需要從D中提取路徑，它代表了最可能生成我們給定的詞序列的隱藏狀態的序列（從第一個到第K個）
首先，在矩陣C的最后一列中計算具有最高概率的條目$c_{i,K}$的系引。這個索引處的概率是最可能的隱藏狀態序列生成給定詞序列的概率。
$$s=\underset{i}{\mathrm{argmax}}{c}_{i,K}$$

例如：這里最高概率的條目是第一個，概率為0.01，也就是對應的$c_{1,5}$
這個索引表示你觀察到單詞$w_5$時遍歷的最后一個隱藏狀態。也就是生成$w_5$最有可能狀態是$t_1$詞性標簽，將$t_1$加到序列的最后：

然后根據D中的值查找矩陣D中的下一個索引：

Implementation notes

1.In Python index starts with 0!
2.Use log probabilities，防止概率值太小相乘導致下溢
$$c_{i,j}=\underset{k}{\max }{c}_{k,j?1}?a_{k,i}?b_{i,cindex(w_j)}$$
取log后：
$$\log c_{i,j}=\underset{k}{\max }\log (c_{k,j?1})+\log (a_{k,i})+\log (b_{i,cindex(w_j)})$$