BiLSTM+CRF:
如果看了之後還看不懂，我自罰三杯！！！
參考的是國外一個很好的部落格，原文連結：https://createmomo.github.io/2017/12/06/CRF-Layer-on-the-Top-of-BiLSTM-7/
現在抽空學習一下知識圖譜方面的知識
1、Introduction：
1.1 開始之前：
假設我們有兩個實體類别：person+location。在我們的資料集中，我們有五個标簽，B-person、I-person、B-location、I- location以及标簽O。在一個句子x(小明生活在北京)中，小明是一個person實體，北京是一個location實體。其他的元素如“生”“活”“在”都屬于O。
1.2 BiLSTM-CRF模型：
BilSTM-CRF模型輸入：wi是句子中每一個元素，轉換成字向量之後作為輸入。
BilSTM-CRF模型輸出：每一個元素相對應的标簽。
BiLSTM模型輸出：每一個元素對每個标簽的機率，下圖中黃色部分。這些會作為CRF的輸入。
1.3 如果沒有CRF層
如果沒有CRF層，我們貌似也可以BiLSTM層每個元素輸出的最大機率标簽當做最後結果，如下圖所示，w0的最大機率輸出标簽是B-person，那麼直接把這個元素最後結果當做B-person，相應的w1是I-person，等等。
上面說的貌似是正确的，但這種情況下元素之間的标簽不存在限制關系，即B-person之後絕對不能跟B-person，I-person之前絕對不能是I-organization，是以就會出現下面的錯誤。
1.4 CRF層能夠學習到上面所說的限制關系
CRF層能夠對最後的結果加上一些限制來確定結果是正确的，這些限制可以在訓練過程中通過訓練集自動學習得到。這些限制可能有：
- 句子中的第一個字可能是B-或者O，不能是I-
- B-label I-label2 I-label3中，label1、label2、label3應該是相同的實體label。也就是B-person後面不能跟I-location
- O後面不能跟I-label，這是明顯的。
2 、CRF層：
在CRF層，存在兩種類型的scores，這個兩種scores是crf層重要部分。
2.1 Emission score：
Emission scores主要來自于BiLSTM層，如下圖所示，第一個元素對于B-person的得分是1.5。
為了友善觀察，給每個label加 一個index。
我們使用xiyj來代表emission score，其中i表示第幾個元素，yj表示label的index。例如上上個圖中，xi=1，yj=2= xw1，B-organization=0.1,代表的是第二個元素是B-organization的得分。
2.2 Transition score
tyiyj表示transition score，例如，tB-person，I-person=0.9意味着B-person到下一個字是I-person的機率是0.9，是以，transition包含所有标簽之間的轉移機率。為了是transition矩陣更魯棒，我們新加兩個label，start和end，start表示一個句子的開始，并不是第一個字，end表示句子的結束。樣例如下圖所示：
顯然上述矩陣是存在一些限制關系的，如：transition矩陣從start到I-person和I-organization的機率是很低的，因為第一個字應該以B-或者O-開始，而不是I-；B-person到I-organization的機率很低，因為不能從一個label的開始到另一個标簽的中間；O-到I-的機率很低，因為不可能呀！！！！那麼如何獲得這個矩陣呢？
實際上，transition矩陣是整個模型的一個參數，訓練之前，你可以随機初始化這個矩陣，在訓練過程中，這個矩陣會不斷的更新，換言之，CRF層能夠學習到這個矩陣。
2.3 CRF lossfunction
這一層的損失包含真實路徑和所有路徑的得分和，真實路徑應該是最高得分。（真實路徑也就是每個元素的真是标簽，舉個例子，一個句子有5個元素，标簽數量是7個，那麼路徑個數是7^5，如下圖所示，每條路徑都有一個得分，也可以說是一個機率，真實路徑隻有一個，使其最大就好了）
那麼總得分就是Ptotal=P1+ P2+……+ Pn=eS1+ eS2+……+ eSn,e是自然對數，下一節會介紹如何計算Si。損失計算公式如下：
LossFunction=PRealPath/( P1+ P2+……+ Pn)
在訓練期間，參數的更新使這個比重越來越大。
- 如何計算每個路徑的得分
- 如何計算所有路徑的總得分
- 計算總得分的時候，有必要列出來所有路徑嗎（顯然是NO）
2.4 真實路徑
在訓練過程中，lossFunction隻需要兩個得分，真實路徑score+全部路徑的score。
真實路徑score的計算：句子有5個元素，7個label，真實路徑是START B-Person I-Person O B-Organization O END
Si=EmissionScore+TransitionScore
EmissionScore=(x0,START)+(x1,B−Person)+(x2,I−Person)+(x3,O)+(x4,B−Organization)+(x5,O)+(x6,END)
x1,B−Person是第一個字是B-person的機率，這就是BiLSTM這一層的輸出呀
x0,START和x6,END我們指派為0
TransitionScore=tSTART−>B−Person + tB−Person−>I−Person + tI−Person−>O + t0−>B−Organization + tB−Organization−>O + tO−>END
tB−Person−>I−Person是CRF層transition的參數，表示B-person到I-person的轉移機率
2.5 全路徑score
可以計算出所有路徑的score然後相加得到全路徑的得分，但這樣的話計算量是相當大的，訓練是很耗時的。
下面的例子會讓你了解如何快速計算全路徑的score，一步一步來，不着急，你會明白其中的奧妙。
Step1：LossFunction=PRealPath/( P1+ P2+……+ Pn)
LogLossFunction=log(PRealPath/( P1+ P2+……+ Pn))
最小化
Step2：為了更好的描述，我們假設我們的句子長度隻有3。 X=[w0, w1, w2];兩個label={ l1, l2}
假設emission score情況如下：xij表示wi是lj的機率，即BiLSTM層的輸出
Transition矩陣如下：tij表示label從i到j的機率
Step3: 我們的目标是計算log(eS1+ eS1+ ...+eSN)
整個計算過程和動态規劃想類似。所有可能路徑的總得分w0是已經計算好的，然後我們計算w0->w1的總得分，再計算 w0->w1->w2。在下面的步驟中，你會看到兩個變量，obs和previous。previous儲存了前一步的結果，obs表示目前字的 資訊。
w0：
obs=[x01, x02]
previous=None
如果我們句子隻有一個字，我們就不需要從previous中擷取結果了，是以previous是None。那麼很顯然，所有路徑的得分 就是log(ex01+ ex02)。
w0->w1：
obs=[ x11, x12]
previous=[x01, x02]
1.把previous和obs擴充成矩陣：
為什麼要擴充呢？因為擴充之後才能有效計算所有路徑的總得分呀。
2.計算previous、obs和transition score的和：
舉個簡單的例子你就了解了，假設隻有兩個元素，兩個label，那麼路徑是不是有4條，即上面scores裡面的東西， scores 裡面每個元素的得分就是一個路徑的得分，包括emission score和transition score，這也是為什麼要把previous 和obs擴充成矩陣了，因為這樣元素之間的相加可以羅列出所有的矩陣呀。那麼下一次疊代的previous是什麼呢，就是我 們的scores呀，隻不過樣式需要變換一下：
為什麼要這種樣式呢?我們分步計算一下就知道了：
最後這個結果和直接求e求和再求log的效果是一樣的。看着previous是兩個元素，實際上還有四條路徑。
w0->w1->w2：
接下來的疊代和上面的幾乎是一樣的了。
obs=[ x21, x22]
previous=[log(ex01+x11+t11+ ex02+x11+t21), log(ex01+x12+t12+ ex02+x12+t22)]
1.把previous和obs擴充成矩陣：
2.計算previous、obs和transition score的和：
下一次疊代的previous就是：看着複雜，實際很簡單。
分步計算可以知道，三個元素時，一共有8條路徑，
發現沒？完整的8條路徑，就是全路徑的得分了！！！
2.6 如果預測一個句子的label
Step1：emission score和transition score
假設句子還是三個字：X=[w0, w1, w2]，且已經得到相應的emission score和transition score。
Step2：如果你了解Viterbi算法（之前了解過，貌似忘了，之前的部落格有介紹HMM算法，和Viterbi差不多）。α0是曆史最好 得分 。α1是相應标簽的indexs。
w0：
obs=[x01, x02]
previous=None
現在我們隻觀察到第一個字w0，如果obs=[ x01=0.2, x02=0.8]，顯然，w0最好的結果就是l2。
w0->w1：
obs=[ x11, x12]
previous=[x01, x02]
（1）老規矩，把previous和obs擴充成矩陣：、
（2）計算previous、obs和transition矩陣的和：
到這裡你會不會覺得這和之前求總得分的步驟是一樣呀，不要着急，慢慢看。
previous=[max(scores[00], scores[10]), max(scores[01], scores[11])]
例如，如果我的得分是
那麼我們下一次疊代的previous就會變成
previous=[max(scores[00], scores[10]), max(scores[01], scores[11])] = [0.5, 0.4]
這裡previous存儲的是前一個字的每一個label的最大得分，和HMM很像啊啊啊啊啊！
Example Start：
上述例子中，我們隻有兩個label，這兩個label的index是0和1,。previous[0]表示到達前一個字是label1的最大 值，同理，previous[1]表示到達前一個字是label2的最大值。每一次疊代中，變量previous存儲到達每一個 label的最大得分值。換言之，每一次疊代中，我們都存儲了到達每一個label的最優路徑。
Example End：
我們上面提到過，我們還有兩個變量去存儲曆史資訊α0和α1。
疊代時，我們把最優得分資訊放入α0：
α0 = [(scores[10], scores[11])] = [(0.5, 0.4)]
α1中存入相應的列坐标：
α1 = [(ColumnIndex(scores[10]), ColumnIndex(scores[11]))] = [(1, 1)]
如何解釋呢，l1的下标是0，l2的下标是1，是以（1, 1）=（l2, l2）表示目前字wi和li。具體來說就是對于w1 時，到達l1（這個l1是（l2, l2）中第一個元素l2是以在位置是0）的最大值的上一個标簽是l2，即到達0.5的路 徑是l(i-1) = l2 –> l(i) = l1。
到達l2（這個l2是（l2, l2）中第二個元素l2是以在位置是1）的最大值的上一個标簽是l2，即到達0.4的路徑是
l(i-1) = l2 –> l(i) = l2。
l(i-1)指的是字w(i-1)的标簽。相當于儲存了路徑。
w0->w1->w2：
接下來的疊代和上面的幾乎是一樣的了。
obs=[ x21, x22]
previous=[0.5, 0.4]
1.把previous、obs擴充成矩陣：
- 然後還是求和：
- 然後計算找到最大值，更新previous：
previous=[max(scores[00], scores[10]), max(scores[01], scores[11])]
假設這個得分是：
那麼previous=[0.8, 0.9]，實際上previous[0]和previous[1]中最大的一個就是最優路徑的得分
同時，我們需要更新α0和α1：
α0 = [(0,5, 0.4), (scores[10], scores[01])] = [(0,5, 0.4), (0,8 0.9)]
α1 = [(1, 1), (1, 0)]
我覺得我有必要再強調一下α1，現在到達w2的l1和l2的最優路徑分别是l2 –>l1 ->l2和l2 –>l2 ->l1
Step3：找到最高得分的最優路徑：
實際上面已經說過了，α1中儲存的就是最優路徑，隻要複現出來就ok了。算了，還是再說一遍吧。
w1->w2：
α0 = [(0,5, 0.4), (0,8 0.9)]
α1 = [(1, 1), (1, 0)]
最大得分是0.9呀，相當于w2的 标簽是l2；再看α1，到達l2的上一個字w1的标簽是l1，是以最後一條連線就是 l1- l2
w0->w1：
上一個w1的标簽是l1，那麼到達l1的上一個字w0的标簽是l2，是以整個路徑就是l2 –>l1 ->l2。
3、Chainer Implementation
終于到代碼實作了，但作者使用chainer實作的，是以不寫了吧，畢竟沒用過，改天貼上自己的代碼，整個算法過程肯定了解了吧。