筆者去年曾寫過文章《果殼中的條件隨機場（CRF In A Nutshell）》[1]，以一種比較粗糙的方式介紹了一下條件隨機場（CRF）模型。然而那篇文章顯然有很多不足的地方，比如介紹不夠清晰，也不夠完整，還沒有實現(xiàn)，在這里我們重提這個模型，將相關(guān)內(nèi)容補充完成。
本文是對 CRF 基本原理的一個簡明的介紹。當(dāng)然，“簡明”是相對而言中，要想真的弄清楚 CRF，免不了要提及一些公式，如果只關(guān)心調(diào)用的讀者，可以直接移到文末。
按照之前的思路，我們依舊來對比一下普通的逐幀 softmax 和 CRF 的異同。
逐幀softmax
CRF 主要用于序列標(biāo)注問題，可以簡單理解為是給序列中的每一幀都進行分類，既然是分類，很自然想到將這個序列用 CNN 或者 RNN 進行編碼后，接一個全連接層用 softmax 激活，如下圖所示：
▲ 逐幀softmax并沒有直接考慮輸出的上下文關(guān)聯(lián)
條件隨機場
然而，當(dāng)我們設(shè)計標(biāo)簽時，比如用 s、b、m、e 的 4 個標(biāo)簽來做字標(biāo)注法的分詞，目標(biāo)輸出序列本身會帶有一些上下文關(guān)聯(lián)，比如 s 后面就不能接 m 和 e，等等。逐標(biāo)簽 softmax 并沒有考慮這種輸出層面的上下文關(guān)聯(lián)，所以它意味著把這些關(guān)聯(lián)放到了編碼層面，希望模型能自己學(xué)到這些內(nèi)容，但有時候會“強模型所難”。
而 CRF 則更直接一點，它將輸出層面的關(guān)聯(lián)分離了出來，這使得模型在學(xué)習(xí)上更為“從容”：
▲ CRF在輸出端顯式地考慮了上下文關(guān)聯(lián)
當(dāng)然，如果僅僅是引入輸出的關(guān)聯(lián)，還不僅僅是 CRF 的全部，CRF 的真正精巧的地方，是它以路徑為單位，考慮的是路徑的概率。
模型概要
假如一個輸入有 n 幀，每一幀的標(biāo)簽有 k 中可能性，那么理論上就有k^n中不同的輸入。我們可以將它用如下的網(wǎng)絡(luò)圖進行簡單的可視化。在下圖中，每個點代表一個標(biāo)簽的可能性，點之間的連線表示標(biāo)簽之間的關(guān)聯(lián)，而每一種標(biāo)注結(jié)果，都對應(yīng)著圖上的一條完整的路徑。
▲ 4tag分詞模型中輸出網(wǎng)絡(luò)圖
而在序列標(biāo)注任務(wù)中，我們的正確答案是一般是唯一的。比如“今天天氣不錯”，如果對應(yīng)的分詞結(jié)果是“今天/天氣/不/錯”，那么目標(biāo)輸出序列就是 bebess，除此之外別的路徑都不符合要求。
換言之，在序列標(biāo)注任務(wù)中，我們的研究的基本單位應(yīng)該是路徑，我們要做的事情，是從 k^n 條路徑選出正確的一條，那就意味著，如果將它視為一個分類問題，那么將是 k^n 類中選一類的分類問題。
這就是逐幀 softmax 和 CRF 的根本不同了：前者將序列標(biāo)注看成是 n 個 k 分類問題，后者將序列標(biāo)注看成是 1 個 k^n 分類問題。
具體來講，在 CRF 的序列標(biāo)注問題中，我們要計算的是條件概率：
為了得到這個概率的估計，CRF 做了兩個假設(shè)：
假設(shè)一：該分布是指數(shù)族分布。
這個假設(shè)意味著存在函數(shù) f(y1,…,yn;x)，使得：
其中 Z(x) 是歸一化因子，因為這個是條件分布，所以歸一化因子跟 x 有關(guān)。這個 f 函數(shù)可以視為一個打分函數(shù)，打分函數(shù)取指數(shù)并歸一化后就得到概率分布。
假設(shè)二：輸出之間的關(guān)聯(lián)僅發(fā)生在相鄰位置，并且關(guān)聯(lián)是指數(shù)加性的。
這個假設(shè)意味著 f(y1,…,yn;x) 可以更進一步簡化為：
這也就是說，現(xiàn)在我們只需要對每一個標(biāo)簽和每一個相鄰標(biāo)簽對分別打分，然后將所有打分結(jié)果求和得到總分。
線性鏈CRF
盡管已經(jīng)做了大量簡化，但一般來說，(3) 式所表示的概率模型還是過于復(fù)雜，難以求解。于是考慮到當(dāng)前深度學(xué)習(xí)模型中，RNN 或者層疊 CNN 等模型已經(jīng)能夠比較充分捕捉各個 y 與輸出 x 的聯(lián)系，因此，我們不妨考慮函數(shù) g 跟 x 無關(guān)，那么：
這時候 g 實際上就是一個有限的、待訓(xùn)練的參數(shù)矩陣而已，而單標(biāo)簽的打分函數(shù) h(yi;x) 我們可以通過 RNN 或者 CNN 來建模。因此，該模型是可以建立的，其中概率分布變?yōu)椋?/span>
這就是線性鏈 CRF 的概念。
歸一化因子
為了訓(xùn)練 CRF 模型，我們用最大似然方法，也就是用：
作為損失函數(shù)，可以算出它等于：
其中第一項是原來概率式的分子的對數(shù)，它目標(biāo)的序列的打分，雖然它看上去挺迂回的，但是并不難計算。真正的難度在于分母的對數(shù) logZ(x) 這一項。
歸一化因子，在物理上也叫配分函數(shù)，在這里它需要我們對所有可能的路徑的打分進行指數(shù)求和，而我們前面已經(jīng)說到，這樣的路徑數(shù)是指數(shù)量級的（k^n），因此直接來算幾乎是不可能的。
事實上，歸一化因子難算，幾乎是所有概率圖模型的公共難題。幸運的是，在 CRF 模型中，由于我們只考慮了臨近標(biāo)簽的聯(lián)系（馬爾可夫假設(shè)），因此我們可以遞歸地算出歸一化因子，這使得原來是指數(shù)級的計算量降低為線性級別。
具體來說，我們將計算到時刻 t 的歸一化因子記為 Zt，并將它分為 k 個部分：
其中分別是截止到當(dāng)前時刻 t 中、以標(biāo)簽 1,…,k 為終點的所有路徑的得分指數(shù)和。那么，我們可以遞歸地計算：
它可以簡單寫為矩陣形式：
其中，而 G 是對 g(yi,yj) 各個元素取指數(shù)后的矩陣，即
▲ 歸一化因子的遞歸計算圖示。從t到t+1時刻的計算，包括轉(zhuǎn)移概率和j+1節(jié)點本身的概率
如果不熟悉的讀者，可能一下子比較難接受 (10) 式。讀者可以把 n=1,n=2,n=3 時的歸一化因子寫出來，試著找它們的遞歸關(guān)系，慢慢地就可以理解 (10) 式了。
動態(tài)規(guī)劃
寫出損失函數(shù) ?logP(y1,…,yn|x) 后，就可以完成模型的訓(xùn)練了，因為目前的深度學(xué)習(xí)框架都已經(jīng)帶有自動求導(dǎo)的功能，只要我們能寫出可導(dǎo)的 loss，就可以幫我們完成優(yōu)化過程了。
那么剩下的最后一步，就是模型訓(xùn)練完成后，如何根據(jù)輸入找出最優(yōu)路徑來。跟前面一樣，這也是一個從 k^n 條路徑中選最優(yōu)的問題，而同樣地，因為馬爾可夫假設(shè)的存在，它可以轉(zhuǎn)化為一個動態(tài)規(guī)劃問題，用 viterbi 算法解決，計算量正比于 n。
動態(tài)規(guī)劃在本博客已經(jīng)出現(xiàn)了多次了，它的遞歸思想就是：一條最優(yōu)路徑切成兩段，那么每一段都是一條（局部）最優(yōu)路徑。在本博客右端的搜索框鍵入“動態(tài)規(guī)劃”，就可以得到很多相關(guān)介紹了，所以不再重復(fù)了。
經(jīng)過調(diào)試，基于 Keras 框架下，筆者得到了一個線性鏈 CRF 的簡明實現(xiàn)，這也許是最簡短的 CRF 實現(xiàn)了。這里分享最終的實現(xiàn)并介紹實現(xiàn)要點。
實現(xiàn)要點
前面我們已經(jīng)說明了，實現(xiàn) CRF 的困難之處是 ?logP(y1,…,yn|x) 的計算，而本質(zhì)困難是歸一化因子部分 Z(x) 的計算，得益于馬爾科夫假設(shè)，我們得到了遞歸的 (9) 式或 (10) 式，它們應(yīng)該已經(jīng)是一般情況下計算 Z(x) 的計算了。
那么怎么在深度學(xué)習(xí)框架中實現(xiàn)這種遞歸計算呢？要注意，從計算圖的視角看，這是通過遞歸的方法定義一個圖，而且這個圖的長度還不固定。這對于 PyTorch這樣的動態(tài)圖框架應(yīng)該是不為難的，但是對于TensorFlow或者基于 TensorFlow 的 Keras 就很難操作了（它們是靜態(tài)圖框架）。
不過，并非沒有可能，我們可以用封裝好的 RNN 函數(shù)來計算。我們知道，RNN 本質(zhì)上就是在遞歸計算：
新版本的 TensorFlow 和 Keras 都已經(jīng)允許我們自定義 RNN 細胞，這就意味著函數(shù) f 可以自行定義，而后端自動幫我們完成遞歸計算。于是我們只需要設(shè)計一個 RNN，使得我們要計算的 Z 對應(yīng)于 RNN 的隱藏向量。
這就是 CRF 實現(xiàn)中最精致的部分了。
至于剩下的，是一些細節(jié)性的，包括：
1. 為了防止溢出，我們通常要取對數(shù)，但由于歸一化因子是指數(shù)求和，所以實際上是這樣的格式，它的計算技巧是：
TensorFlow 和 Keras 中都已經(jīng)封裝好了對應(yīng)的 logsumexp 函數(shù)了，直接調(diào)用即可；
2. 對于分子（也就是目標(biāo)序列的得分）的計算技巧，在代碼中已經(jīng)做了注釋，主要是通過用“目標(biāo)序列”點乘“預(yù)測序列”來實現(xiàn)取出目標(biāo)得分；
3. 關(guān)于變長輸入的 padding 部分如何進行 mask？我覺得在這方面 Keras 做得并不是很好。
為了簡單實現(xiàn)這種 mask，我的做法是引入多一個標(biāo)簽，比如原來是 s、b、m、e 四個標(biāo)簽做分詞，然后引入第五個標(biāo)簽，比如 x，將 padding 部分的標(biāo)簽都設(shè)為 x，然后可以直接在 CRF 損失計算時忽略第五個標(biāo)簽的存在，具體實現(xiàn)請看代碼。
代碼速覽
純 Keras 實現(xiàn)的 CRF 層，歡迎使用。
# -*- coding:utf-8 -*-
from keras.layers import Layer
import keras.backend as K
class CRF(Layer):
'''純Keras實現(xiàn)CRF層
CRF層本質(zhì)上是一個帶訓(xùn)練參數(shù)的loss計算層，因此CRF層只用來訓(xùn)練模型，
而預(yù)測則需要另外建立模型。
'''
def __init__(self, ignore_last_label=False, **kwargs):
'''ignore_last_label：定義要不要忽略最后一個標(biāo)簽，起到mask的效果
'''
self.ignore_last_label = 1 if ignore_last_label else 0
super(CRF, self).__init__(**kwargs)
def build(self, input_shape):
self.num_labels = input_shape[-1] - self.ignore_last_label
self.trans = self.add_weight(name='crf_trans',
shape=(self.num_labels, self.num_labels),
initializer='glorot_uniform',
trainable=True)
def log_norm_step(self, inputs, states):
'''遞歸計算歸一化因子
要點：1、遞歸計算；2、用logsumexp避免溢出。
技巧：通過expand_dims來對齊張量。
'''
states = K.expand_dims(states[0], 2) # (batch_size, output_dim, 1)
trans = K.expand_dims(self.trans, 0) # (1, output_dim, output_dim)
output = K.logsumexp(states+trans, 1) # (batch_size, output_dim)
return output+inputs, [output+inputs]
def path_score(self, inputs, labels):
'''計算目標(biāo)路徑的相對概率（還沒有歸一化）
要點：逐標(biāo)簽得分，加上轉(zhuǎn)移概率得分。
技巧：用“預(yù)測”點乘“目標(biāo)”的方法抽取出目標(biāo)路徑的得分。
'''
point_score = K.sum(K.sum(inputs*labels, 2), 1, keepdims=True) # 逐標(biāo)簽得分
labels1 = K.expand_dims(labels[:, :-1], 3)
labels2 = K.expand_dims(labels[:, 1:], 2)
labels = labels1 * labels2 # 兩個錯位labels，負責(zé)從轉(zhuǎn)移矩陣中抽取目標(biāo)轉(zhuǎn)移得分
trans = K.expand_dims(K.expand_dims(self.trans, 0), 0)
trans_score = K.sum(K.sum(trans*labels, [2,3]), 1, keepdims=True)
return point_score+trans_score # 兩部分得分之和
def call(self, inputs): # CRF本身不改變輸出，它只是一個loss
return inputs
def loss(self, y_true, y_pred): # 目標(biāo)y_pred需要是one hot形式
mask = 1-y_true[:,1:,-1] if self.ignore_last_label else None
y_true,y_pred = y_true[:,:,:self.num_labels],y_pred[:,:,:self.num_labels]
init_states = [y_pred[:,0]] # 初始狀態(tài)
log_norm,_,_ = K.rnn(self.log_norm_step, y_pred[:,1:], init_states, mask=mask) # 計算Z向量（對數(shù)）
log_norm = K.logsumexp(log_norm, 1, keepdims=True) # 計算Z（對數(shù)）
path_score = self.path_score(y_pred, y_true) # 計算分子（對數(shù)）
return log_norm - path_score # 即log(分子/分母)
def accuracy(self, y_true, y_pred): # 訓(xùn)練過程中顯示逐幀準(zhǔn)確率的函數(shù)，排除了mask的影響
mask = 1-y_true[:,:,-1] if self.ignore_last_label else None
y_true,y_pred = y_true[:,:,:self.num_labels],y_pred[:,:,:self.num_labels]
isequal = K.equal(K.argmax(y_true, 2), K.argmax(y_pred, 2))
isequal = K.cast(isequal, 'float32')
if mask == None:
return K.mean(isequal)
else:
return K.sum(isequal*mask) / K.sum(mask)除去注釋和 accuracy 的代碼，真正的 CRF 的代碼量也就 30 行左右，可以說跟哪個框架比較都稱得上是簡明的 CRF 實現(xiàn)了。
用純 Keras 實現(xiàn)一些復(fù)雜的模型，是一件頗有意思的事情。目前僅在 TensorFlow 后端測試通過，理論上兼容 Theano、CNTK 后端，但可能要自行微調(diào)。
使用案例
我的 Github 中還附帶了一個使用 CNN+CRF 實現(xiàn)的中文分詞的例子，用的是 Bakeoff 2005 語料，例子是一個完整的分詞實現(xiàn)，包括 viterbi 算法、分詞輸出等。
Github地址：https://github.com/bojone/crf/
相關(guān)的內(nèi)容還可以看我之前的文章：
中文分詞系列：基于雙向LSTM的seq2seq字標(biāo)注 [2]
中文分詞系列：基于全卷積網(wǎng)絡(luò)的中文分詞 [3]
終于介紹完了，希望大家有所收獲，也希望最后的實現(xiàn)能對大家有所幫助。
