長文 | 詳解基於並行計算的條件隨機場
- 2019 年 10 月 11 日
- 筆記
跟著部落客的腳步，每天進步一點點
之前寫過CRF的詳解，只是為了讓大家詳細了解下原理，但是那種是沒有優化的，速度很慢。在實際應用中，還是需要用到batch，也就是需要用到GPU的，那麼此時並行計算就變得極為重要。在研究到一定的程度上，困住你的不是演算法本身，而是時間。同一件事，當然是越快越好。此時困住你的就是加速問題。
我認為的加速大概分為兩種：
- 演算法的本身的速度。
- 程式中的循環怎麼改為矩陣計算，也就是並行計算。
這裡先以條件隨機場CRF為例，詳細講解CRF原理和如何加速的並行計算。
下面的所有圖，公式都由本人zenRRan原創
1.概述
CRF（Conditional Random Field），中文被翻譯為條件隨機場。經常被用於 序列標註，其中包括詞性標註，分詞，命名實體識別等領域。但是為什麼 叫這個名字呢？下面看完了基本也就明白了！那我們繼續吧。
2.理論
我們以詞性標註為例，先介紹下詞性標註的概念：
這個表示 詞:詞性，分別為 我:PN，去:V V ，北京:NN。
Table1就是word和label數字化後變成word index，label index。最終就 變成Table2的形式：
上述是標準金標，也就是正確答案，但是實際上電腦預測的不會是正 確的。因為label有3種，每一個字被預測的label就有3種可能，為了數字化 這些可能，我們從word index 到label index 設置一種分數，叫做發射分 數emit，簡化為E。
word index 的2到label index的2，像不像發射上去的？此時的分數就記 作發射分數E[2][2]。
另外，我們想想，如果單單就這個發射分數來評價，太過於單一了， 因為這個是一個序列，比如前面的label為1代表V V 動詞，那此時的label被 預測的肯定不能是V V ,因為動詞後面不能接動詞，所以知道前一個label轉 向後一個label可能性會增加準確率，所以這個時候就需要一個分數代表前 一個label 到此時label 的分數，我們叫這個為轉移分數，即T。如圖，橫 向的label到label，就是由一個label到另一個label轉移的意思，此時的分數 為T[1][1]。
假設word index = i到label index = j的分數為s[i][j]，則
s[0][0] = E[0][0]
因為word index = 0前面沒有word index了，所以s[0][0]就為發射分數E[0][0]。word index = 1到label index = 1的分數s[1][1]為E[1][1]+T[0][1]。但是CRF 為了全局考慮，將前一個的分數也累加到當前分數上，這樣更能表達出已 經預測的序列的整體分數，則：
s[1][1] = s[0][0] + E[1][1] + T[0][1]
所以，s[2][2]也就很容易了：
s[2][2] = E[0][0] + E[1][1] + T[0][1] + E[2][2] + T[1][2]
因為s[2][2]已經為最後的詞的的分數，所以該s[2][2]為金標score({我 去 北 京},{PN VV NN})即score({0 1 2},{0 1 2})的最終得分。最後的公式總結為：
其中X為word index序列，y為預測的label index序列。
因為這個預測序列有很多種，種類為label的可重複排列組合大小。其中 只有一種組合是對的，我們只想通過神經網路訓練使得對的score的比重在總體的所有score的越大越好。而這個時候我們一般softmax化，即：
其中分子中的s為label序列為正確序列的score，分母為每種可能的score的 總和。
這個比值越大，我們的預測就越准，所以，這個公式也就可以當做我們 的loss，可是loss一般都越小越好，那我們就對這個加個負號即可，但是這個最終結果是趨近於1的，我們實驗的結果是趨近於0的，這時候log就派上 用場了，即：
當然這個log也有平滑結果的功效。
3.計算所有路徑的得分
loss的分子在上面已經求出來了，現在就差分母了，而計算所有預測序列可能的得分和也就是計算所有路徑的得分。我們第一種想法就是每一種可 能都求出來，然後累加即可。可是，比如word序列長為10，label種類為7， 那麼總共需要計算10^7次，這樣的計算太耗時間了。那麼怎麼計算的時間快呢？這裡有一種方法，就是每個節點記錄之前所有節點到當前節點的路徑 總和。如圖：
解釋下這個圖：
第一列：
首先說下，因為『我』是第一列，前面沒有別的詞，所以就不用加上前 面的值。繼續說，N[0][0]表示『我』選擇PN的得分，N[1][0]表示『我』選 擇V V 的得分,N[2][0]表示『我』選擇NN的得分而該得分只有發射得分，所以為：
N[0][0] = E[0][0]
同理，得：
N[1][0] = E[0][1] N[2][0] = E[0][2]
再來分析第二列:
N[0][1]表示前一個選擇PN的得分+『去』選擇PN的得分（『去』選 擇PN的得分為T[0][0]+E[1][0]），前一個選擇V V 的得分+加上『去』選 擇PN 的得分，加上前一個選擇NN的得分+『去』選擇PN的得分。公式為：
類推：
再類推第三列：
最後一列求完了，因為每個節點都包含了該節點之前所有節點到該節點的 可能路徑，因為現在的
的總和就是所有路徑的總和，也就是我們要求的損失函數裡面的
即為：
4.得出具體損失函數
最終的我們的損失函數求出來了：
這樣我們就能根據損失函數反向傳播梯度，更新T E參數了。
5.batch
上面的那種求總和的方法，還有一種好處就是可以加快並行計算，也就剛 好能做多個句子的batch批處理。先說什麼是並行計算，字面意思就能理 解，並行，並排行進，大家同時進行的意思，同時進行的前提條件是需要 用到的東西都已經準備好。放在電腦里的意思就是當前運行的程式需要 的數據都已經準備好了。那我們來看看我們的數據怎麼能並行計算吧，我 拿出來一列數據來看看（先說下為什麼拿出的是一列，而不是一行，因為 一列所需要的數據前一列都已經計算過了，而一行不具備這樣的條件）， 比如第二列：
但是這樣或許看不到什麼效果，我來整理下，去掉log，去掉e，只提取數 據：
我們先看N這三組數據，發現每組裡面N都是一樣都為N[0][0],N[1][0],N[2][0]， 所以我們可以設定矩陣N為：
我們看到矩陣N第0維循環變化，第1維不變，但是上面的只是一組數據， 我們需要三組，所以我們對該N進行二維擴展，也就是列複製：
再看T，第一組為T[0][0],T[1][0],T[2][0]，第二組為T[0][1],T[1][1],T[2][1]， 第三組為T[0][2],T[1][2],T[2][2]。我們能其實夠很明顯的看出第一組為T的3∗ 3矩陣第0列，剩下的分別為第1列，第2列，即矩陣T為：
最後同理我們看E，我們會觀察到它和N的情況相似，但是E第0維不變， 第1維是循環變化，所以是行複製：
我們會發現，矩陣N T E的第一列按位相加的結果剛好是N[0][1]，同理的，第二列，第三列分別按位相加分別得N[1][1]，N[2][1]，即：
同 理，求出N_02 N_12 N_22，然後：
上面的只是表示一個句子的計算，我們為了加快速度，或者使用GPU的 時候，需要用到batch，那麼batch里的上述N T E是怎麼個存在形式呢？以batch = n為例：N數據格式為：
T數據格式為：
E數據格式為：
其中，X^i_j中的i表示batch里的第i組矩陣，j表示batch里的第i組中位置為j的 數據。
6.預測過程
上面是Encoder編碼過程，訓練完了，該看看訓練的效果了，這裡預測的過 程叫做Decoder解碼過程。這時候N E T都是固定了的，不會再變化。我們 的目的是，選取可能性最高的，又因為可能性最高在這裡表示得分最高， 然後根據最高的得分，我們向前一個一個的選取每次前一個最高得分的節 點，最終這些所有的節點就是我們的最後的預測序列。這個過程是不是很 熟悉的感覺，對就是我們的動態規劃演算法，但是在這裡叫維特比演算法。我 們來走一遍過程：
每個節點選取得分最高的路徑並記錄得分和選的哪條路徑：其中n^s_ij中的s表示前一條路徑，沒有的就是−1，nij表示前節點到當前節點的最佳得 分。此時
比如此時預測n_20 + E[1][0] + T[2][0]為最高的，則記錄n_01 = n_20 + E[1][0] + T[2][0]且路徑為2,綜上記為n^2_01:
同理，我們假設有了step3的最終結果。
在最後我們假如n_22最大，而且它的前一個路徑為1，則看到n_11的前一 個路徑為0，而且n_00的前一個路徑為−1，表示結束，則整個路徑就有了， 即為n_00− > n_11− > n_22，如圖step4：
由step4得，最終(』我』，』去』，』北京』)的預測結果為：
(』我』− > PN，』去』− > V V ，』北京』− > NN)。
The End
