【Learning Notes】线性链条件随机场（CRF）原理及实现
1. 概述
條件隨機場（Conditional Random Field, CRF）是概率圖模型（Probabilistic Graphical Model）與區分性分類( Discriminative Classification）的一種接合，能夠用來對“結構預測”（structured prediction，e.g. 序列標注）問題進行建模。
如圖1，論文 [1] 闡釋了 CRF 與其他模型之間的關系。
圖1. CRF 與 其他機器學習模型對比【src】
本文我們重點關注輸入結點獨立的“線性鏈條件隨機場”（Linear-Chain CRF）（如圖2）的原理與實現。線性鏈 CRF 通過與雙向 LSTM（Bi-LSTM）的接合，可以用來建模更一般的線性鏈 CRF（圖3），提高模型的建模能力。
圖2. 簡單的線性鏈 CRF【src】
圖3. 一般性線性鏈 CRF【src】
2. CRF 算法
2.1 模型形式化
給定長度為 mm 的序列， 以及狀態集 SS。 對于任意狀態序列 (s1,?,sm),si∈S(s1,?,sm),si∈S, 定義其“勢”（potential）如下：
ψ(s1,…,sm)=∏i=1mψ(si?1,si,i)
ψ(s1,…,sm)=∏i=1mψ(si?1,si,i)
我們定義 s0s0 為特殊的開始符號 ??。這里對 s,s′∈S,i∈1,…,ms,s′∈S,i∈1,…,m，勢函數 ψ(s,s′,i)≥0ψ(s,s′,i)≥0。也即，勢函數是非負的，它對序列第 ii 位置發生的 ss 到 s′s′ 的狀態轉移都給出一個非負值。
根據概率圖模型的因子分解理論[1]，我們有：
p(s1,…,sm|x1,…,xm)=ψ(s1,…,sm)∑s′1,…,s′mψ(s′1,…,s′m)
p(s1,…,sm|x1,…,xm)=ψ(s1,…,sm)∑s1′,…,sm′ψ(s1′,…,sm′)
Z=∑s′1,…,s′mψ(s′1,…,s′m)Z=∑s1′,…,sm′ψ(s1′,…,sm′) 為歸一化因子。
同 HMM 類似，CRF 也涉及三類基本問題：評估（計算某一序列的似然值）、解碼（給定輸入，尋找似然最大的序列）及訓練（根據數據估計 CRF 的參數），解決這三個問題也都涉及前向算法、后向算法及 Viterbi 算法。
CRF 的勢函數類似于概率，只不過沒有歸一化，因此這里介紹的 CRF 前向算法、Viterbi 算法、后向算法，同 HMM 基本一致。
2.2 前向算法
定義：
α(i,s)=∑s1,…,si?1ψ(s1,…,si?1,s)
α(i,s)=∑s1,…,si?1ψ(s1,…,si?1,s)
表示，以 ss 結尾的長度為 ii 的子序列的勢。
顯然，α(1,s)=ψ(?,s1,1)α(1,s)=ψ(?,s1,1)
根據定義，我們有如下遞歸關系：
α(i,s)=∑s′∈Sα(i?1,s′)×ψ(s′,s,i)
α(i,s)=∑s′∈Sα(i?1,s′)×ψ(s′,s,i)
歸一化因子可以計算如下：
Z=∑s1,…,smψ(s1,…sm)=∑s∈S∑s1,…,sm?1ψ(s1,…sm?1,s)=∑s∈Sα(m,s)
Z=∑s1,…,smψ(s1,…sm)=∑s∈S∑s1,…,sm?1ψ(s1,…sm?1,s)=∑s∈Sα(m,s)
對于給定的序列 (s1,?,sm)(s1,?,sm)，其中條件概率（似然）可以計算：
p(s1,…,sm|x1,…,xm)=∏mi=1ψ(si?1,si,i)∑s∈Sα(m,s)
p(s1,…,sm|x1,…,xm)=∏i=1mψ(si?1,si,i)∑s∈Sα(m,s)
* 通過前向算法，我們解決了評估問題，計算和空間復雜度為 O(m?|S|2)O(m?|S|2)。*
似然的計算過程中，只涉及乘法和加法，都是可導操作。因此，只需要實現前向操作，我們就可以借具有自動梯度功能的學習庫（e.g. pytorch、tensorflow）實現基于最大似然準則的訓練。一個基于 pytorch 的 CRF 實現見 repo。
import numpy as np
def forward(psi):
m, V, _ = psi.shape
alpha = np.zeros([m, V])
alpha[0] = psi[0, 0, :] # assume psi[0, 0, :] := psi(*,s,1)
for t in range(1, m):
for i in range(V):
'''
for k in range(V):
alpha[t, i] += alpha[t - 1, k] * psi[t, k, i]
'''
alpha[t, i] = np.sum(alpha[t - 1, :] * psi[t, :, i])
return alpha
def pro(seq, psi):
m, V, _ = psi.shape
alpha = forward(psi)
Z = np.sum(alpha[-1])
M = psi[0, 0, seq[0]]
for i in range(1, m):
M *= psi[i, seq[i-1], seq[i]]
p = M / Z
return p
np.random.seed(1111)
V, m = 5, 10
log_psi = np.random.random([m, V, V])
psi = np.exp(log_psi) # nonnegative
seq = np.random.choice(V, m)
alpha = forward(psi)
p = pro(seq, psi)
print(p)
print(alpha)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
2.69869828108e-08
[[ 1.10026295e+00 2.52187760e+00 1.40997704e+00 1.36407554e+00
1.00201186e+00]
[ 1.27679086e+01 1.03890052e+01 1.44699134e+01 1.15244329e+01
1.52767179e+01]
[ 9.30306192e+01 1.09450375e+02 1.26777728e+02 1.28529576e+02
1.16835669e+02]
[ 9.81861108e+02 8.70384204e+02 9.35531558e+02 7.98228277e+02
9.89225754e+02]
[ 6.89790063e+03 8.71016058e+03 8.84778486e+03 9.21051594e+03
6.56093883e+03]
[ 7.56109978e+04 7.00773298e+04 8.60611103e+04 5.63567069e+04
5.99238226e+04]
[ 6.69236243e+05 6.42107210e+05 7.81638452e+05 6.32533145e+05
5.71122492e+05]
[ 6.62242340e+06 5.24446290e+06 5.54750409e+06 4.68782248e+06
4.49353155e+06]
[ 4.31080734e+07 4.09579660e+07 4.62891972e+07 4.60100937e+07
4.63083098e+07]
[ 2.66620185e+08 4.91942550e+08 4.48597546e+08 3.42214705e+08
4.10510463e+08]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2.3 Viterbi 解碼
Viterbi 利用動態規劃，尋找似然最大的序列。Viterbi 與前向算法非常相似，只是將求和操作替換為最大值操作。
α(j,s)=maxs1,…,sj?1ψ(s1,…,sj?1,s)
α(j,s)=maxs1,…,sj?1ψ(s1,…,sj?1,s)
顯然，α(1,s)=ψ(?,s1,1)α(1,s)=ψ(?,s1,1)
根據定義，我們有如下遞歸關系：
α(j,s)=maxs′∈S?α(j?1,s′)?ψ(s′,s,j)
α(j,s)=maxs′∈S?α(j?1,s′)?ψ(s′,s,j)
在所有 |s|m|s|m 條可能的序列中，概率最大的路徑的未歸一化的值為：
maxα(m,s)
maxα(m,s)
沿著前向推導的反方向，可以得到最優的路徑，算法復雜度是 O(m?|S|2)O(m?|S|2)。demo 實現如下：
def viterbi_1(psi):
m, V, _ = psi.shape
alpha = np.zeros([V])
trans = np.ones([m, V]).astype('int') * -1
alpha[:] = psi[0, 0, :] # assume psi[0, 0, :] := psi(*,s,1)
for t in range(1, m):
next_alpha = np.zeros([V])
for i in range(V):
tmp = alpha * psi[t, :, i]
next_alpha[i] = np.max(tmp)
trans[t, i] = np.argmax(tmp)
alpha = next_alpha
end = np.argmax(alpha)
path = [end]
for t in range(m - 1, 0, -1):
cur = path[-1]
pre = trans[t, cur]
path.append(pre)
return path[::-1]
def viterbi_2(psi):
m, V, _ = psi.shape
alpha = np.zeros([m, V])
alpha[0] = psi[0, 0, :] # assume psi[0, 0, :] := psi(*,s,1)
for t in range(1, m):
for i in range(V):
tmp = alpha[t - 1, :] * psi[t, :, i]
alpha[t, i] = np.max(tmp)
end = np.argmax(alpha[-1])
path = [end]
for t in range(m - 1, 0, -1):
cur = path[-1]
pre = np.argmax(alpha[t - 1] * psi[t, :, cur])
path.append(pre)
return path[::-1]
np.random.seed(1111)
V, m = 5, 10
log_psi = np.random.random([m, V, V])
psi = np.exp(log_psi) # nonnegative
path_1 = viterbi_1(psi)
path_2 = viterbi_2(psi)
print(path_1)
print(path_2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
[1, 4, 2, 4, 3, 0, 3, 0, 3, 1]
[1, 4, 2, 4, 3, 0, 3, 0, 3, 1]
1
2
2.4 后向算法
為了訓練 CRF, 我們需要計算相應的梯度。為了手動計算梯度（這也為后續優化打開大門），需要用到后向算法。
定義：
β(j,s)=∑sj+1,…,smψ(sj+1,…,sm|sj=s)
β(j,s)=∑sj+1,…,smψ(sj+1,…,sm|sj=s)
其中，令 β(m,s)=1β(m,s)=1。
可以認為序列結尾存在特殊的符號。為簡單起見，不討論結尾邊界的特殊性，可以都參考前向邊界的處理及參見實現。
根據定義，我們有如下遞歸關系：
β(j,s)=∑s′∈Sβ(j+1,s′)?ψ(s,s′,j+1)
β(j,s)=∑s′∈Sβ(j+1,s′)?ψ(s,s′,j+1)
def backward(psi):
m, V, _ = psi.shape
beta = np.zeros([m, V])
beta[-1] = 1
for t in range(m - 2, -1, -1):
for i in range(V):
'''
for k in range(V):
beta[t, i] += beta[t + 1, k] * psi[t + 1, i, k]
'''
beta[t, i] = np.sum(beta[t + 1, :] * psi[t + 1, i, :])
return beta
np.random.seed(1111)
V, m = 5, 10
log_psi = np.random.random([m, V, V])
psi = np.exp(log_psi) # nonnegative
seq = np.random.choice(V, m)
beta = backward(psi)
print(beta)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
[[ 2.95024144e+08 2.61620644e+08 3.16953747e+08 2.02959597e+08
2.51250862e+08]
[ 2.73494359e+07 2.31521489e+07 3.62404054e+07 2.84752625e+07
3.38820012e+07]
[ 2.92799244e+06 3.00539203e+06 4.18174216e+06 3.30814155e+06
3.45104724e+06]
[ 4.40588351e+05 4.18060894e+05 3.95721271e+05 4.50117410e+05
4.38635065e+05]
[ 4.51172884e+04 5.40496888e+04 4.37931199e+04 4.98898498e+04
5.04357771e+04]
[ 6.50740169e+03 5.21859026e+03 5.66773856e+03 4.73895449e+03
5.79578682e+03]
[ 4.83173340e+02 5.36538120e+02 6.01820173e+02 7.07538756e+02
6.54966046e+02]
[ 7.60936291e+01 7.90609361e+01 9.08681883e+01 5.80503199e+01
5.89976569e+01]
[ 8.15414542e+00 7.95904764e+00 9.64664115e+00 8.69502743e+00
9.41073532e+00]
[ 1.00000000e+00 1.00000000e+00 1.00000000e+00 1.00000000e+00
1.00000000e+00]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2.5 梯度計算
Z=∑s1,…,smψ(s1,…,sm)=∑s′i?1∈S,s′i∈S∑si?1=s′i?1,si=s′iψ(s1,…,sm)=∑s′i?1∈S,s′i∈Sα(i?1,s′i?1)?β(i,s′i)?ψ(s′i?1,s′i,i)???1<i≤m
Z=∑s1,…,smψ(s1,…,sm)=∑si?1′∈S,si′∈S∑si?1=si?1′,si=si′ψ(s1,…,sm)=∑si?1′∈S,si′∈Sα(i?1,si?1′)?β(i,si′)?ψ(si?1′,si′,i)???1<i≤m
對于 i=1i=1 的邊界情況：
Z=∑s′1∈Sβ(1,s′i)?ψ(?,s′1,1)
Z=∑s1′∈Sβ(1,si′)?ψ(?,s1′,1)
對于路徑 (s1,?,sm)(s1,?,sm)，
p(s1,…,sm|x1,…,xm)=ψ(s1,…,sm)Z=∏mi=1ψ(si?1,si,i)Z=∏mi=1ψisi?1,siZ
p(s1,…,sm|x1,…,xm)=ψ(s1,…,sm)Z=∏i=1mψ(si?1,si,i)Z=∏i=1mψsi?1,siiZ
其中，ψis′,s=ψ(s′,s,i),?s′,s∈Sψs′,si=ψ(s′,s,i),?s′,s∈S。
記分子 ∏mi=1ψ(si?1,si,i)=M∏i=1mψ(si?1,si,i)=M 則：
?p(s1,…,sm|x1,…,xm)?ψks′,s=1Z[Mψks′,s?δs′=sk?1&s=sk?p?α(k?1,s′)?β(k,s)]
?p(s1,…,sm|x1,…,xm)?ψs′,sk=1Z[Mψs′,sk?δs′=sk?1&s=sk?p?α(k?1,s′)?β(k,s)]
其中，δtrue=1,δfalse=0δtrue=1,δfalse=0。
?lnp(s1,…,sm|x1,…,xm)?ψks′,s=1p??p(s1,…,sm|x1,…,xm)?ψks′,s=δs′=sk?1&s=skψks′,s?1Zα(k?1,s′)?β(k,s)
?ln?p(s1,…,sm|x1,…,xm)?ψs′,sk=1p??p(s1,…,sm|x1,…,xm)?ψs′,sk=δs′=sk?1&s=skψs′,sk?1Zα(k?1,s′)?β(k,s)
def gradient(seq, psi):
m, V, _ = psi.shape
grad = np.zeros_like(psi)
alpha = forward(psi)
beta = backward(psi)
Z = np.sum(alpha[-1])
for t in range(1, m):
for i in range(V):
for j in range(V):
grad[t, i, j] = -alpha[t - 1, i] * beta[t, j] / Z
if i == seq[t - 1] and j == seq[t]:
grad[t, i, j] += 1. / psi[t, i, j]
# corner cases
grad[0, 0, :] = -beta[0, :] / Z
grad[0, 0, seq[0]] += 1. / psi[0, 0, seq[0]]
return grad
np.random.seed(1111)
V, m = 5, 10
log_psi = np.random.random([m, V, V])
psi = np.exp(log_psi) # nonnegative
seq = np.random.choice(V, m)
grad = gradient(seq, psi)
print(grad[0, :, :])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
[[ 0.75834232 -0.13348772 -0.16172055 -0.10355687 -0.12819671]
[ 0. 0. 0. 0. 0. ]
[ 0. 0. 0. 0. 0. ]
[ 0. 0. 0. 0. 0. ]
[ 0. 0. 0. 0. 0. ]]
1
2
3
4
5
def check_grad(seq, psi, i, j, k, toleration=1e-5, delta=1e-10):
m, V, _ = psi.shape
grad_1 = gradient(seq, psi)[i, j, k]
original = psi[i, j, k]
# p1
psi[i, j, k] = original - delta
p1 = np.log(pro(seq, psi))
# p2
psi[i, j, k] = original + delta
p2 = np.log(pro(seq, psi))
psi[i, j, k] = original
grad_2 = (p2 - p1) / (2 * delta)
diff = np.abs(grad_1 - grad_2)
if diff > toleration:
print("%d, %d, %d, %.2e, %.2e, %.2e" % (i, j, k, grad_1, grad_2, diff))
np.random.seed(1111)
V, m = 5, 10
log_psi = np.random.random([m, V, V])
psi = np.exp(log_psi) # nonnegative
seq = np.random.choice(V, m)
print(seq)
for toleration in [1e-4, 5e-5, 1.5e-5]:
print(toleration)
for i in range(m):
for j in range(V):
for k in range(V):
check_grad(seq, psi, i, j, k, toleration)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
[0 1 4 1 3 0 0 3 3 1]
0.0001
5e-05
1.5e-05
2, 1, 2, -2.22e-02, -2.22e-02, 1.55e-05
4, 3, 3, -2.03e-02, -2.03e-02, 1.55e-05
1
2
3
4
5
6
首先定義基本的 log 域加法操作（參見）。
ninf = -np.float('inf')
def _logsumexp(a, b):
'''
np.log(np.exp(a) + np.exp(b))
'''
if a < b:
a, b = b, a
if b == ninf:
return a
else:
return a + np.log(1 + np.exp(b - a))
def logsumexp(*args):
'''
from scipy.special import logsumexp
logsumexp(args)
'''
res = args[0]
for e in args[1:]:
res = _logsumexp(res, e)
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def forward_log(log_psi):
m, V, _ = log_psi.shape
log_alpha = np.ones([m, V]) * ninf
log_alpha[0] = log_psi[0, 0, :] # assume psi[0, 0, :] := psi(*,s,1)
for t in range(1, m):
for i in range(V):
for j in range(V):
log_alpha[t, j] = logsumexp(log_alpha[t, j], log_alpha[t - 1, i] + log_psi[t, i, j])
return log_alpha
def pro_log(seq, log_psi):
m, V, _ = log_psi.shape
log_alpha = forward_log(log_psi)
log_Z = logsumexp(*[e for e in log_alpha[-1]])
log_M = log_psi[0, 0, seq[0]]
for i in range(1, m):
log_M = log_M + log_psi[i, seq[i - 1], seq[i]]
log_p = log_M - log_Z
return log_p
np.random.seed(1111)
V, m = 5, 10
log_psi = np.random.random([m, V, V])
psi = np.exp(log_psi) # nonnegative
seq = np.random.choice(V, m)
alpha = forward(psi)
log_alpha = forward_log(log_psi)
print(np.sum(np.abs(np.log(alpha) - log_alpha)))
p = pro(seq, psi)
log_p = pro_log(seq, log_psi)
print(np.sum(np.abs(np.log(p) - log_p)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
3.03719722983e-14
0.0
1
2
def backward_log(log_psi):
m, V, _ = log_psi.shape
log_beta = np.ones([m, V]) * ninf
log_beta[-1] = 0
for t in range(m - 2, -1, -1):
for i in range(V):
for j in range(V):
log_beta[t, i] = logsumexp(log_beta[t, i], log_beta[t + 1, j] + log_psi[t + 1, i, j])
return log_beta
np.random.seed(1111)
V, m = 5, 10
log_psi = np.random.random([m, V, V])
psi = np.exp(log_psi) # nonnegative
seq = np.random.choice(V, m)
beta = backward(psi)
log_beta = backward_log(log_psi)
print(np.sum(np.abs(beta - np.exp(log_beta))))
print(np.sum(np.abs(log_beta - np.log(beta))))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
1.46851337579e-06
1.86517468137e-14
1
2
def gradient_log(seq, log_psi):
m, V, _ = log_psi.shape
grad = np.zeros_like(log_psi)
log_alpha = forward_log(log_psi)
log_beta = backward_log(log_psi)
log_Z = logsumexp(*[e for e in log_alpha[-1]])
for t in range(1, m):
for i in range(V):
for j in range(V):
grad[t, i, j] -= np.exp(log_alpha[t - 1, i] + log_beta[t, j] - log_Z)
if i == seq[t - 1] and j == seq[t]:
grad[t, i, j] += np.exp(-log_psi[t, i, j])
# corner cases
grad[0, 0, :] -= np.exp(log_beta[0, :] - log_Z)
grad[0, 0, seq[0]] += np.exp(-log_psi[0, 0, seq[0]])
return grad
np.random.seed(1111)
V, m = 5, 10
log_psi = np.random.random([m, V, V])
psi = np.exp(log_psi) # nonnegative
seq = np.random.choice(V, m)
grad_1 = gradient(seq, psi)
grad_2 = gradient_log(seq, log_psi)
print(grad_1[0, :, :])
print(grad_2[0, :, :])
print(np.sum(np.abs(grad_1 - grad_2)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
[[ 0.75834232 -0.13348772 -0.16172055 -0.10355687 -0.12819671]
[ 0. 0. 0. 0. 0. ]
[ 0. 0. 0. 0. 0. ]
[ 0. 0. 0. 0. 0. ]
[ 0. 0. 0. 0. 0. ]]
[[ 0.75834232 -0.13348772 -0.16172055 -0.10355687 -0.12819671]
[ 0. 0. 0. 0. 0. ]
[ 0. 0. 0. 0. 0. ]
[ 0. 0. 0. 0. 0. ]
[ 0. 0. 0. 0. 0. ]]
1.11508025036e-14
1
2
3
4
5
6
7
8
9
10
11
在 log 域， 我們一般直接計算目標函數相對與 lnψln?ψ 的梯度計算公式如下：
?lnp(s1,…,sm|x1,…,xm)?lnψks′,s=?lnp(s1,…,sm|x1,…,xm)?ψks′,s??ψks′,s?lnψks′,s=δs′=sk?1&s=sk?exp(lnα(k?1,s′)+lnβ(k,s)?lnZ+lnψks′,s)
?ln?p(s1,…,sm|x1,…,xm)?ln?ψs′,sk=?ln?p(s1,…,sm|x1,…,xm)?ψs′,sk??ψs′,sk?ln?ψs′,sk=δs′=sk?1&s=sk?exp?(ln?α(k?1,s′)+ln?β(k,s)?ln?Z+ln?ψs′,sk)
只需將上面的 grad_log 稍做改動即可，不再贅述。
3. CRF + 人工神經網絡
3.1 勢函數選擇
目前為止，我們都假設函數已經知道，在此基礎上推導 CRF 的相關計算。理論上，除了非負性的要求 ，勢函數可以靈活的選擇。為也便于計算和訓練，CRF 中一般選擇指數的形式。假設輸入為 x1,…,xmx1,…,xm，則勢函數定義為：
ψ(s′,s,i)=exp(w??(x1,…,xm,s′,s,i))
ψ(s′,s,i)=exp?(w??(x1,…,xm,s′,s,i))
則
ψ(s1,…,sm)=∏i=1mψ(si?1,si,i)=∏i=1mexp(w??(x1,…,xm,si?1,si,i))
ψ(s1,…,sm)=∏i=1mψ(si?1,si,i)=∏i=1mexp?(w??(x1,…,xm,si?1,si,i))
其中，?(x1,…,xm,s′,s,i)∈Rd?(x1,…,xm,s′,s,i)∈Rd 是特征向量，w∈Rdw∈Rd 是參數向量。
對于線性鏈模型，簡化勢函數為：
ψ(s′,s,i)=t(s|s′)e(s|xi)
ψ(s′,s,i)=t(s|s′)e(s|xi)
轉移勢函數定義為：
t(s|s′)=exp(v?g(s′,s))
t(s|s′)=exp?(v?g(s′,s))
發射勢函數定義為：
e(s|xi)=exp(w?f(s,xi))
e(s|xi)=exp?(w?f(s,xi))
則：
ψ(s1,…,sm)=∏j=1mψ(sj?1,sj,j)=∏j=1mt(sj|sj?1)e(s|xj)=∏j=1mexp(v?g(sj?1,sj))?exp(w?f(sj,xj))
ψ(s1,…,sm)=∏j=1mψ(sj?1,sj,j)=∏j=1mt(sj|sj?1)e(s|xj)=∏j=1mexp?(v?g(sj?1,sj))?exp?(w?f(sj,xj))
ψ(s1,…,sm)=exp(∑i=1mv?g(si?1,si)+∑i=1mw?f(si,xi))
ψ(s1,…,sm)=exp?(∑i=1mv?g(si?1,si)+∑i=1mw?f(si,xi))
如果我們取對數，則我們得到一個線性模型，定義：
scoret(s|s′)=logt(s|s′)=v?g(s′,s)
scoret(s|s′)=log?t(s|s′)=v?g(s′,s)
scoree(s|xi)=loge(s|xi)=w?f(s,xi)
scoree(s|xi)=log?e(s|xi)=w?f(s,xi)
則
logψ(s1,…,sm)=∑i=1mv?g(si?1,si)+∑i=1mw?f(si,xi)=∑i=1mscoret(si?1|si)+∑i=1mscoree(si|xi)
log?ψ(s1,…,sm)=∑i=1mv?g(si?1,si)+∑i=1mw?f(si,xi)=∑i=1mscoret(si?1|si)+∑i=1mscoree(si|xi)
具體的，可以定義
scoret(sj|si)=Pij
scoret(sj|si)=Pij
其中，PP 是 |S|×|S||S|×|S| 的轉移矩陣。
如果 x=(x1,?,xm)∈Rmx=(x1,?,xm)∈Rm，則有：
scoree(sj|xi)=Wj?xi
scoree(sj|xi)=Wj?xi
其中，W∈R|s|×nW∈R|s|×n 是權重矩陣。
logψ(s1,…,sm)=∑i=1mscoret(s|s′)+∑i=1mscoree(s|xi)=∑i=1mPsi?1si+∑i=1mWsi?xi
log?ψ(s1,…,sm)=∑i=1mscoret(s|s′)+∑i=1mscoree(s|xi)=∑i=1mPsi?1si+∑i=1mWsi?xi
這里，為簡單起見，我們令 xixi 是一個標量，實際中 xixi 往往是向量。
從 xx 到 logψlog?ψ 再到 ψψ 都是可導的操作（四則運算和指數、對數運算），而 ψψ 的梯度我們上面已經推導可以求得。因此，我們可以利用誤差反傳計算 WW 等參數的梯度，從而利用 SGD 等優化方法訓練包括 CRF 在內的整個模型的參數。
def score(seq, x, W, P, S):
m = len(seq)
V = len(W)
log_psi = np.zeros([m, V, V])
# corner cases
for i in range(V):
# emit
log_psi[0, 0, i] += S[i]
# transmit
log_psi[0, 0, i] += x[0] * W[i]
for t in range(1, m):
for i in range(V):
for j in range(V):
# emit
log_psi[t, i, j] += x[t] * W[j]
# transmit
log_psi[t, i, j] += P[i, j]
return log_psi
def gradient_param(seq, x, W, P, S):
m = len(seq)
V = len(W)
log_psi = score(seq, x, W, P, S)
grad_psi = gradient_log(seq, log_psi)
grad_log_psi = np.exp(log_psi) * grad_psi
grad_x = np.zeros_like(x)
grad_W = np.zeros_like(W)
grad_P = np.zeros_like(P)
grad_S = np.zeros_like(S)
# corner cases
for i in range(V):
# emit
grad_S[i] += grad_log_psi[0, 0, i]
# transmit
grad_W[i] += grad_log_psi[0, 0, i] * x[0]
grad_x[0] += grad_log_psi[0, 0, i] * W[i]
for t in range(1, m):
for i in range(V):
for j in range(V):
# emit
grad_W[j] += grad_log_psi[t, i, j] * x[t]
grad_x[t] += grad_log_psi[t, i, j] * W[j]
# transmit
grad_P[i, j] += grad_log_psi[t, i, j]
return grad_x, grad_W, grad_P, grad_S
np.random.seed(1111)
V, m = 5, 7
seq = np.random.choice(V, m)
x = np.random.random(m)
W = np.random.random(V)
P = np.random.random([V, V])
S = np.random.random(V)
grad_x, grad_W, grad_P, grad_S = gradient_param(seq, x, W, P, S)
print(grad_x)
print(grad_W)
print(grad_P)
print(grad_S)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
[ 0.03394788 -0.11666261 0.02592661 0.07931277 0.02549323 0.11371901
0.02198856]
[-0.62291675 -0.38050215 -0.18983737 -0.65300231 1.84625859]
[[-0.34655117 -0.27314013 -0.16800195 -0.28352514 0.73359469]
[-0.22747135 -0.2967193 -0.27009443 -0.2664594 0.87349324]
[-0.27906702 -0.27747362 -0.33689934 -0.18786182 0.82788735]
[-0.2701056 -0.16940564 -0.2624276 -0.29133856 -0.25558298]
[ 0.72105085 0.86080584 0.76931185 -0.2103895 -0.11362927]]
[-0.17736447 -0.21489701 -0.20747999 -0.19735031 0.79709179]
1
2
3
4
5
6
7
8
9
梯度正確性檢驗如下：
def check_grad(seq, x, W, P, S, toleration=1e-5, delta=1e-10):
m, V, _ = psi.shape
grad_x, grad_W, grad_P, grad_S = gradient_param(seq, x, W, P, S)
def llk(seq, x, W, P, S):
log_psi = score(seq, x, W, P, S)
spi = np.exp(log_psi)
log_p = np.log(pro(seq, spi))
return log_p
# grad_x
print('Check X')
for i in range(len(x)):
original = x[i]
grad_1 = grad_x[i]
# p1
x[i] = original - delta
p1 = llk(seq, x, W, P, S)
# p2
x[i] = original + delta
p2 = llk(seq, x, W, P, S)
x[i] = original
grad_2 = (p2 - p1) / (2 * delta)
diff = np.abs(grad_1 - grad_2) / np.abs(grad_2)
if diff > toleration:
print("%d, %.2e, %.2e, %.2e" % (i, grad_1, grad_2, diff))
# grad_W
print('Check W')
for i in range(len(W)):
original = W[i]
grad_1 = grad_W[i]
# p1
W[i] = original - delta
p1 = llk(seq, x, W, P, S)
# p2
W[i] = original + delta
p2 = llk(seq, x, W, P, S)
W[i] = original
grad_2 = (p2 - p1) / (2 * delta)
diff = np.abs(grad_1 - grad_2) / np.abs(grad_2)
if diff > toleration:
print("%d, %.2e, %.2e, %.2e" % (i, grad_1, grad_2, diff))
# grad_P
print('Check P')
for i in range(V):
for j in range(V):
original = P[i][j]
grad_1 = grad_P[i][j]
# p1
P[i][j] = original - delta
p1 = llk(seq, x, W, P, S)
# p2
P[i][j] = original + delta
p2 = llk(seq, x, W, P, S)
P[i][j] = original
grad_2 = (p2 - p1) / (2 * delta)
diff = np.abs(grad_1 - grad_2) / np.abs(grad_2)
if diff > toleration:
print("%d, %.2e, %.2e, %.2e" % (i, grad_1, grad_2, diff))
# grad_S
print('Check S')
for i in range(len(S)):
original = S[i]
grad_1 = grad_S[i]
# p1
S[i] = original - delta
p1 = llk(seq, x, W, P, S)
# p2
S[i] = original + delta
p2 = llk(seq, x, W, P, S)
S[i] = original
grad_2 = (p2 - p1) / (2 * delta)
diff = np.abs(grad_1 - grad_2) / np.abs(grad_2)
if diff > toleration:
print("%d, %.2e, %.2e, %.2e" % (i, grad_1, grad_2, diff))
np.random.seed(1111)
V, m = 5, 10
seq = np.random.choice(V, m)
x = np.random.random(m)
W = np.random.random(V)
P = np.random.random([V, V])
S = np.random.random(V)
check_grad(seq, x, W, P, S)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
Check X
1, 6.75e-02, 6.75e-02, 5.74e-05
2, 5.14e-01, 5.14e-01, 1.47e-05
3, -3.17e-01, -3.17e-01, 1.51e-05
5, -6.42e-02, -6.42e-02, 7.82e-05
8, -4.38e-02, -4.38e-02, 1.08e-04
Check W
0, -6.55e-01, -6.55e-01, 1.13e-05
2, -1.33e-03, -1.33e-03, 3.77e-04
3, 5.88e-02, 5.89e-02, 1.15e-04
Check P
0, -4.50e-01, -4.51e-01, 1.03e-05
0, -2.70e-01, -2.70e-01, 2.53e-05
1, -2.11e-01, -2.11e-01, 3.13e-05
1, -2.35e-01, -2.35e-01, 1.80e-05
2, -2.93e-01, -2.93e-01, 1.76e-05
2, -1.50e-01, -1.50e-01, 2.15e-05
2, -1.72e-01, -1.72e-01, 3.40e-05
2, -3.48e-01, -3.48e-01, 1.02e-05
3, -1.90e-01, -1.90e-01, 3.10e-05
3, -3.60e-01, -3.60e-01, 1.78e-05
4, 5.47e-01, 5.47e-01, 1.50e-05
Check S
0, -2.02e-01, -2.02e-01, 2.13e-05
1, -1.97e-01, -1.97e-01, 1.82e-05
2, -1.05e-01, -1.05e-01, 6.22e-05
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
3.2 Bi-LSTM + CRF
CRF 是強大的序列學習準則。配合雙向循環神經網絡（e.g. Bi-LSTM）的特征表征和學習能力，在許多序列學習任務上都取得了領先的結果[5~7]。
基本模型如下：
圖4. Bi-LSTM CRF 模型【src】
Bi-LSTM 對整個輸入序列進行特征提取和建模，用非線性的模型建模發射得分；轉移得分用另外的 PP 表示，作為 CRF 自身的參數。相對于常規的用于神經網絡訓練的目標函數，CRF 是帶參數的損失函數。
基于 pytorch 的 CRFLoss 實現見 repo 以及[3, 4]，BiLSTM + CRF 的 實現應用見[8]。
討論
CRF 廣泛應用于序列標注任務。
由于是區分性模型，因此在分類任務上，CRF 相比 HMM 可能會更高效。
CRF 對于輸出之間的關系進行了建模，這不同于 直接的 RNN 或 CTC 模型（相應的，CRF 訓練和預測的計算量也更大）。
References
Sutton and McCuallum. An Introduction to Conditional Random Fields.
Michael Collins.The Forward-Backward Algorithm.
Pytorch CRF Forward and Viterbi Implementation.
BiLSTM-CRF on PyTorch.
Collobert. Deep Learning for Efficient Discriminative Parsing.
Collobert et al. Natural Language Processing (Almost) from Scratch.
Huang et al. Bidirectional LSTM-CRF Models for Sequence Tagging.
Bi-LSTM-CRF for NLP.
---------------------
作者：MoussaTintin
來源：CSDN
原文：https://blog.csdn.net/JackyTintin/article/details/79261981
版權聲明：本文為博主原創文章，轉載請附上博文鏈接！
總結
以上是生活随笔為你收集整理的【Learning Notes】线性链条件随机场（CRF）原理及实现的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 条件随机场(CRF) - 1 - 简介
- 下一篇： NLP进阶之（七）膨胀卷积神经网络