長文詳解基於平行計算的條件隨機場

作者：由 zenRRan 發表于攝影時間：2018-06-08

來自本人微信公眾號

深度學習自然語言處理

之前寫過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表示前節點到當前節點的最佳得分。此時