PyTorch:Bi-LSTM+CRF②(予測)
予測
予測時は、viterbi algorithm を用いて効率的に計算する。
最後に
_viterbi_decode
関数を確認する。
_viterbi_decode
グラフの最短経路を求めるアルゴリズム。
Viterbi アルゴリズムでは、全ての結果を計算せずに前回の要素を用いて計算量を抑える。
計算例は前に書いた。
隠れマルコフモデル(HMM)について - 機械学習・自然言語処理の勉強メモ
学習によって以下の観測素性行列・遷移素性行列が求まった状態で計算を最適経路の行う。
- 観測素性行列
B | I | O | <START> | <STOP> | |
---|---|---|---|---|---|
Mark | 3.7 | 1.4 | 1.2 | -0.1 | -1.2 |
Watney | 2.6 | 4.1 | 0.9 | -0.7 | -2.1 |
visited | 0.2 | 0.5 | 2.4 | -0.4 | -0.8 |
Mars | 3.6 | 0.4 | 1.1 | -0.2 | -0.5 |
- 遷移素性行列
B | I | O | <START> | <STOP> | |
---|---|---|---|---|---|
B | -1.2 | -1.1 | 1.8 | 2.2 | -1.4 |
I | 3.1 | 2.0 | -0.3 | -0.4 | -0.5 |
O | 1.7 | -0.2 | 1.8 | 1.1 | -1.1 |
<START> | -0.5 | -0.1 | -0.9 | -1.1 | -0.4 |
<STOP> | 1.1 | 1.3 | 2.1 | -0.4 | -0.2 |
*遷移素性行列は列方向→行方向の遷移([2,1]の場合、B→Iの遷移)
Viterbi アルゴリズムでも学習時と同様に系列の先頭から順番にスコアを計算していく。
backpointers = [] # Initialize the viterbi variables in log space init_vvars = torch.Tensor(1, self.tagset_size).fill_(-10000.) init_vvars[0][self.tag_to_ix[START_TAG]] = 0 # forward_var at step i holds the viterbi variables for step i-1 forward_var = autograd.Variable(init_vvars) for feat in feats: bptrs_t = [] # holds the backpointers for this step viterbivars_t = [] # holds the viterbi variables for this step for next_tag in range(self.tagset_size): # next_tag_var[i] holds the viterbi variable for tag i at the # previous step, plus the score of transitioning # from tag i to next_tag. # We don't include the emission scores here because the max # does not depend on them (we add them in below) next_tag_var = forward_var + self.transitions[next_tag] best_tag_id = argmax(next_tag_var) bptrs_t.append(best_tag_id) viterbivars_t.append(next_tag_var[0][best_tag_id]) # Now add in the emission scores, and assign forward_var to the set # of viterbi variables we just computed forward_var = (torch.cat(viterbivars_t) + feat).view(1, -1) backpointers.append(bptrs_t)
繰り返し処理を少しだけデバッグしてみる。
1-1. 単語='Mark' タグ='B'
まず、feat
は次のような素性ベクトル
B | I | O | <START> | <STOP> |
---|---|---|---|---|
3.7 | 1.4 | 1.2 | -0.1 | -1.2 |
現在のnext_tag
は「B」なので、
self.transitions[next_tag]
は以下の素性ベクトルとなる。
B | I | O | <START> | <STOP> |
---|---|---|---|---|
-1.2 | -1.1 | 1.8 | 2.2 | -1.4 |
forward_var
のベクトルは、
B | I | O | <START> | <STOP> |
---|---|---|---|---|
-10000 | -10000 | -10000 | 0 | -10000 |
なので、
next_tag_var = forward_var + self.transitions[next_tag]
next_tag_var
は以下となる。
B | I | O | <START> | <STOP> |
---|---|---|---|---|
-10001.2 | -10001.1 | 9998.2 | 2.2 | -10001.4 |
次の
best_tag_id = argmax(next_tag_var)
で値が最大の次元(<START>
列の3)を取得する。
listにはそれぞれ位置と値が追加される。
bptrs_t.append(best_tag_id) # 3 viterbivars_t.append(next_tag_var[0][best_tag_id]) # 2.2
内側のループが終了すると、各listは以下となる。
bptrs_t # [3, 3, 3, 3, 3] viterbivars_t # [2.2, -0.4, 1.1, -1.1, -0.4]
次に、観測素性ベクトルと足し算する。
forward_var = (torch.cat(viterbivars_t) + feat).view(1, -1)
forward_var
B | I | O | <START> | <STOP> |
---|---|---|---|---|
5.9 | 1.0 | 3.3 | -1.2 | -1.6 |
2-1. 単語='Wateny' タグ='B'
feat
は
B | I | O | <START> | <STOP> |
---|---|---|---|---|
2.6 | 4.1 | 0.9 | -0.7 | -2.1 |
self.transitions[next_tag]
は
B | I | O | <START> | <STOP> |
---|---|---|---|---|
-1.2 | -1.1 | 1.8 | 2.2 | -1.4 |
より、next_tag_var
は、
B | I | O | <START> | <STOP> |
---|---|---|---|---|
4.7 | -0.1 | 5.1 | 1.0 | -3.0 |
また、
best_tag_id = argmax(next_tag_var) # 2 bptrs_t.append(best_tag_id) viterbivars_t.append(next_tag_var[0][best_tag_id]) # 5.1
2回目の内側のループのnext_tag_var
は以下となる。
B | I | O | <START> | <STOP> | |
---|---|---|---|---|---|
B | 4.7 | -0.1 | 5.1 | 1.0 | -3.0 |
I | 9.0 | 3.0 | 1.3 | -1.6 | -2.1 |
O | 7.6 | 0.8 | 5.1 | -0.1 | -2.7 |
<START> | 3.2 | 0.9 | 2.4 | -3.3 | -2.0 |
<STOP> | 4.8 | 2.3 | 5.4 | -1.6 | -1.8 |
また、各listは以下となる。
bptrs_t # [2, 0, 0, 0, 2] viterbivars_t # [2.2, 9.0, 7.6, 3.2, 5.4]
となる。
次に、観測素性ベクトルと足し算する。
forward_var
B | I | O | <START> | <STOP> |
---|---|---|---|---|
4.8 | 13.1 | 8.5 | 2.5 | 3.3 |
これを繰り返すことで、backpointers
は以下となる。
backpointers
# [[3, 3, 3, 3, 3], [2, 0, 0, 0, 2], [1, 1, 1, 1, 1], [2, 0, 2, 2, 2]]
分かりにくいが、これは単語のタグ毎の次の最適タグを示したインデックスリストである。
つまり、こういうことである。
B | I | O | <START> | <STOP> | |
---|---|---|---|---|---|
Mark | <START> | <START> | <START> | <START> | <START> |
Watney | O | B | B | B | O |
visited | I | I | I | I | I |
Mars | O | B | O | O | O |
1行目はMarkのタグが何であれ、先頭は<START>になることを表している。
2行目はWatneyが「B」である場合、直前のタグは「O」であり、「I」である場合、直前のタグは「B」であることが最適パスであることを示している。
# Transition to STOP_TAG terminal_var = forward_var + self.transitions[self.tag_to_ix[STOP_TAG]] best_tag_id = argmax(terminal_var) path_score = terminal_var[0][best_tag_id]
では、<STOP>に続くための最適タグを求める。
ここでは、計算結果で以下が得られたとしておく。
best_tag_id = argmax(terminal_var)
# 0
(<STOP>に続くには、Marsのタグ「B」が最適経路)
以降、系列の後ろから最適経路を求める。
# Follow the back pointers to decode the best path. best_path = [best_tag_id] for bptrs_t in reversed(backpointers): best_tag_id = bptrs_t[best_tag_id] best_path.append(best_tag_id)
順番にbest_tag_id
のタグを取ると以下となる。
best_path = [0, 2, 1, 0, 3] # 0
B | I | O | <START> | <STOP> | |
---|---|---|---|---|---|
Mark | <START> | <START> | <START> | <START> | <START> |
Watney | O | B | B | B | O |
visited | I | I | I | I | I |
Mars | O | B | O | O | O |
start = best_path.pop()
# [0, 2, 1, 0]
で先頭の<START>タグを除く。
best_path.reverse()
# [0, 1, 2, 0]
で反転させる。
最終的なbest_path
は、
「0(B)→1(I)→2(O)→0(B)」となる。
これと同時に計算していた経路のスコアを呼び出し元に返す。
以上がViterbi アルゴリズムの処理となる。
これで学習と予測のコードがある程度理解できた。
次は、CoNLLのデータセットで実践する。