機械学習・自然言語処理の勉強メモ

学んだことのメモやまとめ

TheanoでNER(CRF)

前回まででメインとなるLSTM層を説明した。
kento1109.hatenablog.com

今回はCRFによる出力部を見ていく。

元となるコードを再掲
github.com

CRF



簡単に言うと、「識別モデルを用いて系列ラベリングの問題を学習するもの。」

詳しくは前回まとめた。
kento1109.hatenablog.com

では、なぜsoftmax関数ではなくCRFを使うと良いか。
論文にはこうある

NER imposes several hard constraints (e.g., I-PER cannot follow B-LOC) that would be impossible to model with independence assumptions.
...
We use a CRF to take into account neighboring tags.

例えば、ラベルB-LOCの後にI-PERが続くことはあり得ないので、各ラベルの独立性を仮定することは出来ない。
ラベル同士が独立性を仮定しないのであれば、識別時に近くの単語のラベルもを考慮するべきである。
しかし、softmax関数の場合、ラベル同士は独立を仮定しており、その単語の最も所属確率の高いラベルに識別されてしまう。(単語の素性のみしか考慮していない。)
一方、CRFは遷移素性を用いて前後のタグの連結スコアを考慮した識別モデルであり、固有表現抽出ではより高い識別精度が期待できる。
CRFを接続する目的が分かったので、実際にそのコードを読んでいく。

出力層の前の隠れ層での線形和(tags_scores)は、下記のような行列となる。
(簡単のためラベルは5種類のみとしている)
※HMMやCRFの観測素性の重みに相当するスコア
f:id:kento1109:20171219100156p:plain:w290
CRFを接続しない場合、上の行列をsoftmax関数の入力とし、各ラベルの確率を求めた。
しかし、ここで問題が生じる可能性がある。
上記の識別結果は下記になる。

Mark Watney visited Mars
B-PER B-PER O B-LOC

しかし、固有表現抽出では「B-PER - B-PER」ラベルが続くことはあり得ない。
以降でCRFを接続して「遷移素性」を含めた識別をみていく。
まず、ラベル間の依存性を考慮するための遷移行列(transitions)を作る。(論文中でAとして出てくる行列。)

transitions = shared((n_tags + 2, n_tags + 2), 'transitions')

small = -1000
b_s = np.array([[small] * n_tags + [0, small]]).astype(np.float32)
e_s = np.array([[small] * n_tags + [small, 0]]).astype(np.float32)
observations = T.concatenate(
    [tags_scores, small * T.ones((s_len, 2))],
    axis=1
)
observations = T.concatenate(
    [b_s, observations, e_s],
    axis=0
)

遷移行列は、ラベル数+2×ラベル数+2の要素を持つ行列。
(+2は文頭・文末のダミーラベルを加えるため)
shared関数でスコアを各要素を初期化する。
行列自体はこんな感じ。
f:id:kento1109:20171206150503p:plain
次に、tags_scoresを用いて、observationsを作る。
(論文の\sum _{ i=1 }^{ n }{ { P }_{ i,y_i } }
observationsはこんなイメージ
f:id:kento1109:20171206141351p:plain

Score from tags

次に、

real_path_score = tags_scores[T.arange(s_len), tag_ids].sum()

tags_scoresから正解ラベルの列の要素の総和を計算する。
tag_idsは、文章内の単語の正解ラベル
例えば、正解ラベルが

Mark Watney visited Mars
B-PER I-PER O B-LOC

の場合、
real_path_scoreは、「14.7(3.7 + 4.1 + 3.8 + 3.1)」となる。

その値に遷移行列の要素を加算する。

# Score from transitions
b_id = theano.shared(value=np.array([n_tags], dtype=np.int32))
e_id = theano.shared(value=np.array([n_tags + 1], dtype=np.int32))
padded_tags_ids = T.concatenate([b_id, tag_ids, e_id], axis=0)
real_path_score += transitions[
    padded_tags_ids[T.arange(s_len + 1)],
    padded_tags_ids[T.arange(s_len + 1) + 1]
].sum()

この操作の意図が分かりにくかったので疑似コードを書いてみた。

import numpy as np

np.set_printoptions(precision=3)
np.random.seed(8)
s_len = 4
n_tags = 5
b_id = np.array([n_tags])
e_id = np.array([n_tags + 1])
tag_ids = [0, 1, 4, 2]
transitions = np.random.uniform(low=-1.0, high=1.0, size=[n_tags + 2, n_tags + 2])
[[ 0.747  0.937  0.738  0.062 -0.535 -0.977 -0.139]
 [-0.195  0.045 -0.043  0.111  0.087  0.522  0.425]
 [ 0.239 -0.148 -0.422  0.948 -0.332 -0.562 -0.868]
 [ 0.966 -0.744 -0.356 -0.858 -0.55  -0.213  0.792]
 [-0.309  0.969 -0.943 -0.297 -0.238  0.528  0.878]
 [-0.361 -0.135 -0.46   0.602  0.276 -0.863  0.207]
 [ 0.591 -0.936 -0.089  0.58   0.977  0.168 -0.922]]

padded_tags_score = np.concatenate([b_id, tag_ids, e_id], axis=0)

transitions[padded_tags_score[np.arange(s_len + 1)],
            padded_tags_score[np.arange(s_len + 1) + 1]]
[-0.361  0.937  0.087 -0.943 -0.868]

これはtransitions行列のオレンジの要素の総和
f:id:kento1109:20171206150834p:plain
表にすると

no i j
1 <BOS> B-PER
2 B-PER I-PER
3 I-PER O
4 O B-LOC
5 B-LOC <EOS>

となる。
(論文の\sum _{ i=0 }^{ n }{ { A }_{ y_i,y_{i+1} } }
つまりこの総和(real_path_score)が、論文のs({\rm X,y})に相当する。
\sum _{ i=1 }^{ n }{ { P }_{ i,y_i } } :観測素性
\sum _{ i=0 }^{ n }{ { A }_{ y_i,y_{i+1} } } :遷移素性
なので、観測素性と遷移素性の総和であることが分かる。

論文ではsoftmax関数を使って
\begin{eqnarray}P({\rm { y|X }})=\frac { { e }^{ s({\rm { X,y }}) } }{ \sum _{\tilde y  }^{  }{  { e }^{ {\rm s(X,\tilde{y} }) } }  } { }\end{eqnarray}
の条件付き確率の最大化を目的関数にするとある。
\begin{eqnarray}s({\rm { X,y }})=\sum_{i}( W\cdot \phi(x,y_t,y_{i-1}))\end{eqnarray} なので、
これは対数線形モデルの条件付き確率
\begin{eqnarray}
P(y|X)=\frac{\exp \sum_{i}(W\cdot {\phi(x,y_t,y_{i-1})})}{\sum_{y}{ \exp \sum_{i}(W\cdot {\phi(x,y_t,y_{i-1})})}}
\end{eqnarray}
の最大化問題と同じであることが分かる。

対数尤度の最大化を考えると、
\begin{eqnarray}
\log P(y|X)=\log \exp \sum_{i}(W\cdot {\phi(x,y_t,y_{i-1})})-\log \sum_{y}{ \exp \sum_{i}(W\cdot {\phi(x,y_t,y_{i-1})})}
\end{eqnarray}
\begin{eqnarray}
\hspace{2.2cm}=s({\rm { X,y }})-\log \sum _{\tilde y }e ^{\rm s(X,\tilde{y}) }
\end{eqnarray}
この対数尤度最大化は

all_paths_scores = forward(observations, transitions)
cost = - (real_path_score - all_paths_scores)

に相当する。
つまり、

  • real_path_score:s({\rm { X,y }})
  • all_paths_scores:\log \sum _{\tilde y }e ^{\rm s(X,\tilde{y})}

であることを押さえておく。

\log \sum _{\tilde y }e ^{\rm s(X,\tilde{y})}のスコアをforword関数で求める。

forword

{ e }^{ {\rm s(X,\tilde{y} }) }の対数を取った値の総和を計算する。

def recurrence(obs, previous, transitions):
    previous = previous.dimshuffle(0, 'x')
    obs = obs.dimshuffle('x', 0)
    return log_sum_exp(previous + obs + transitions, axis=0)

initial = observations[0]
alpha, _ = theano.scan(
    fn=recurrence,
    outputs_info=initial
    sequences=[observations[1:]],
    non_sequences=transitions
)
return log_sum_exp(alpha[-1], axis=0)

※コードは簡単のため一部省略

最初にrecurrenceに渡す引数は、

  • observations[0]
  • observations[1:]
  • transitions

f:id:kento1109:20171219145941p:plain

previous + obs + transitionsに対して行うので、
f:id:kento1109:20171219150120p:plain
\exp (各行ベクトル)の値の総和の対数を取った値を返す。

2回目のループの場合、
f:id:kento1109:20171219151503p:plain
の行列に対して同様の計算を行う。
最後の系列までの計算を行った後、最後のベクトルにも同様の総和計算を行い、スカラー値を返す。
このスカラー値が
all_paths_scores:\log \sum _{\tilde y }e ^{\rm s(X,\tilde{y})}
である。

log_sum_exp

対数の総和の計算。
やっていることは\log(\exp(x1)+\exp(x2))と同じ。
※アンダーフローを防ぐための計算上の工夫。
実際に計算すると

import numpy as np

x1 = [1.2, 2.7, 3.2]
x2 = [3.2, 1.2, 1.9]
print np.log(np.exp(x1) + np.exp(x2))
[ 3.32692801  2.90141328  3.44100845]

x = np.array([x1, x2])

xmax = x.max(axis=0, keepdims=True)
xmax_ = x.max(axis=0)
print xmax_ + np.log(np.exp(x - xmax).sum(axis=0))
[ 3.32692801  2.90141328  3.44100845]

同じであることが分かる。

Network parameters

必要なパラメータを追加していく。

Prepare train and eval inputs
if word_dim:
    eval_inputs.append(word_ids)
if char_dim:
    eval_inputs.append(char_for_ids)
    if char_bidirect:
        eval_inputs.append(char_rev_ids)
    eval_inputs.append(char_pos_ids)
if cap_dim:
    eval_inputs.append(cap_ids)
train_inputs = eval_inputs + [tag_ids]

最後のtrain_inputsが訓練時のデータセットを受け取るlistになる。

Parse optimization method parameters

勾配更新アルゴリズムと学習率を取得する。

if "-" in lr_method:  # default="sgd-lr_.005"
    lr_method_name = lr_method[:lr_method.find('-')]
    lr_method_parameters = {}
    for x in lr_method[lr_method.find('-') + 1:].split('-'):
        split = x.split('_')
        assert len(split) == 2
        lr_method_parameters[split[0]] = float(split[1])
else:
    lr_method_name = lr_method
    lr_method_parameters = {}
Compile training function
if training:
    updates = Optimization(clip=5.0).get_updates(lr_method_name, cost, params, **lr_method_parameters)
    f_train = theano.function(
        inputs=train_inputs,
        outputs=cost,
        updates=updates,
        givens=({is_train: np.cast['int32'](1)} if dropout else {})
    )
else:
    f_train = None

dropoutが0でない場合、is_trainには1がセットされる。(訓練用)

Compile evaluation function
if not crf:
    f_eval = theano.function(
        inputs=eval_inputs,
        outputs=tags_scores,
        givens=({is_train: np.cast['int32'](0)} if dropout else {})
    )
else:
    f_eval = theano.function(
        inputs=eval_inputs,
        outputs=forward(observations, transitions, viterbi=True,
                        return_alpha=False, return_best_sequence=True),
        givens=({is_train: np.cast['int32'](0)} if dropout else {})
    )

評価時のスコアもforward関数で求めている。
学習時はコストを計算するためであったが、評価時は評価データでのモデルのスコア計算を行う。
評価時は、viterbiアルゴリズムでスコアを計算する。

ここでは、scanの二重ループでviterbiアルゴリズムを実現している。

後は、train.pyでエポック数だけ学習を繰り返す。