HMM與CRF應用在NER任務
這邊寫下之前讀到的筆記，基本上資料來源是李弘毅老師的投影片 Structured Learning: Sequence Labeling
(http://speech.ee.ntu.edu.tw/~tlkagk/courses/ML_2016/Lecture/Sequence.pdf)
先簡單講一下 named entity recognition(ner) 這個任務最後希望能做到的事，假設有一個句子
I come from New York .我們會希望對應的標註是
O O O B-loc I-loc O也就是把 New York 標示成 B-loc I-loc，這裡的B表示開頭，I表示之後的字，loc代表自己定義entity的類別，如果像是
I come from Taiwan .O O O B-loc O
單個字就成詞，那就只有B-loc
你可以自訂所需要的entity，基本上在不同場景所需要的entity是不一樣的，如果要製作一個任務導向的bot，這些entity就是bot執行任務時所需要的參數
基本上如果任務簡單或訓練資料量很少，用正則表達式或直接比對資料庫的方式去抓就好，這兩個方式基本上就是有建資料就不會錯，但使用者如果輸入一些奇怪、否定或文法不通的句子故意測試時，我們還是會希望抓到 entity 嗎?或是當使用者剛好講到沒在資料庫的東西時又該怎麼辦？基本上資料庫越大維護的成本也越高
如果我們訓練資料量夠多的話就可以用以下的方法HMM或CRF，這類問題基本上都可以寫成3個步驟
1.Evaluation:定義F(x,y)，x代表輸入序列，y代表輸出序列，F(x,y)代表好壞程度，值越大代表y越符合我們的需要
2.Inference:在所有可能的y集合裡找到一組y能最大化F(x,y)的值
3.如何Training，這裡我們不討論，有興趣請看老師的課程網頁
HMM的的算法基本上就是聯合機率，在這裡F(x,y)=P(y|x)，而P(x,y)=P(y)P(x|y)=P(x)P(y|x)，移項後就得到了
P(y|x)=P(y)P(x|y)/P(x)基本上P(x)在給定句子後是值固定的，所以在第2步驟Inference時我們就直接當它是1，這不影響最後的結果
P(y)裡的每一項可以由訓練數據統計得到，這裡我們會得到一個N維向量代表Start Probability，N*N的矩陣代表Transition Probability，P(x|y)是有了這個標註後，產生這個詞的機率，也可以由統計後得到，寫成N*M的矩陣代表Emission Probability，N代表有多少種tag，M代表詞彙量，這裡會有個實際應用的問題
上述有些機率值如果在訓練資料裡沒有出現過，那就會是0，這時就要想一下是真的不可能還是剛好沒有出現在訓練資料裡，如果只是剛好沒出現那就要將其變為一個很小的值
第二個問題Inference時要窮舉所有的y，用 Viterbi 演算法
要注意的是HMM可能會得出一組完全沒看過的P(y|x)是高分，這個現象有好有壞，當訓練資料本身是少量時可能會有益，如果想要解決這問題可以用更複雜的模型
一樣我們要先定義F(x,y)，這裡一樣寫成P(x,y)
Φ(x,y)代表特徵向量，是要自己定義的，不用訓練，w 是機器學習得出的權重向量，因為能自訂任何特徵向量，這也是比HMM強的地方，老師的課程裡有推導如何把HMM寫成CRF的形式，有興趣的人能去看看
第二個問題Inference時要窮舉所有的y，一樣用 Viterbi 演算法
但是如果一般人想用CRF時就會遇到一個困擾，Φ(x,y)到底要如何定義才好？這裡我們可以用Bidirectiona LSTM或Self Attention等讓機器自己學出來就好
最後來說下Viterbi 演算法，如果直接求所有可能的y的話，會有N^seq_len個組合，當seq_len比N大很多時，這計算量大大了，Viterbi 演算法複雜度為seq_len*(N²)，Viterbi 演算法基礎可以概括為下面3點
- 如果概率最大的路徑經過 Directed Acyclic Graph 中的某點，則從起始點到該點的子路徑也一定是從起始點到該點路徑中概率最大的
- 假定第i時刻有N個狀態，從開始到第i時刻的各狀態n各自有最短路徑，而最終的最短路徑必然經過其中之一
- 根據上述，在計算第i+1某個狀態n’的最短路徑時，只需要考慮當前N個狀態各自最短的路徑和第n個狀態值到i+1 的n’狀態值最短路徑即可
s(tag=n',t) 表示的是第t步時以tag為n'的最大的序列概率s(tag=j,t)= max{s(tag=i,t-1) * TP(i,j,t)|i=1...N}TP(i,j,t)為第t－1步從狀態i跳到第t步的狀態j的概率，假設狀態轉移跟time step無關簡化為
s(tag=j,n)= max{s(tag=i,t-1) * TP(i,j)|i=1...N}
TP表示Transition Probability取log後*變加
s(tag=j,t)= max{log[s(tag=i,t-1)] + log[TP(i,j)]|i=1...N}
我們要的只是個排序，實際值不重要，把log去掉
s(tag=j,t)= max{s(tag=i,t-1) + TP(i,j)|i=1...N}
NN 出來的是 seq_len*N的矩陣(score)，另外還有一個額外的 N*N Transition Probability矩陣TP(transition_params)
以下為用例子示範一下此算法
先把TP加上score[0]得到v，v的直行取max代表到各tag的最大分數，寫為np.max(v,0)，同時記錄下此時是從哪裡出發backpointers[1]，再把np.max(v,0)+score[1]當作下次各tag的起始分數
同樣的操作
依最高分去回朔路徑
tensorflow中 viterbi_decode 其中一段可以對照一下
trellis = np.zeros_like(score)
backpointers = np.zeros_like(score, dtype=np.int32)
trellis[0] = score[0]
for t in range(1, score.shape[0]):
v = np.expand_dims(trellis[t - 1], 1) + transition_params
trellis[t] = score[t] + np.max(v, 0)
# trellis[t] 為上面的[s(tag=i,t),...s(tag=N,t)]
backpointers[t] = np.argmax(v, 0)
# backpointers 紀錄了之後要回朔時的N