chainerで自然言語処理できるかマン

chainerで自然言語処理を勉強していくブログ

Andor et al., Globally Normalized Transition-Based Neural Networks, 2016メモ

paper_read

googleのstate-of-the-artな係り受け解析器として公開された「SyntaxNet」の論文を眺めてみたメモ。
SyntaxNetの紹介記事は結構あるのに論文の内容に関する記事があまり見当たらないので有識者の解説待っています。
また、以下について、なにか間違いなどありましたらコメントいただけるとうれしいです。

models/syntaxnet at master · tensorflow/models · GitHub
[1603.06042] Globally Normalized Transition-Based Neural Networks

概要

  • transition-baseなニューラルネットワークモデルで、品詞タグ付け、係り受け解析、文圧縮(要約の一種で単語を削除することで短くする)でstate-of-the-artな結果が得られた
  • 誤りに「Label Bias問題」が含まれているようで、「大域的な正規化をするモデル」を作ることで解決している
  • 最近はrecurrentな構造が流行っているが、このモデルでは「Feed-forwardなニューラルネット」使っていて、これでも匹敵する結果が実現できている

モデル

  • Nivre(2006)の「incremental transition based parser」をベースにしている

Transition System

  • 入力xに対して、以下を定義
    • 状態sの集合S
    • 状態の初期状態s*
    • 各状態で行える決定行為の集合A(s)
    • 状態sで決定行為dをした時の次の状態s'を返す(推移)関数t(s,d)
  • 各状態sで、いくつか選べる決定行為dからどれを選ぶか？をスコア関数ρ(s,d;θ)を使って決める
    • ベクトルθは、適当なパラメータ
  • 各状態へは、初期状態s*から決定行為を繰り返すことでたどり着ける

「入力xと同じ数の決定を持つ完全構造transition system」を各タスク(品詞タグ付けや係り受け解析など)に適用する。
係り受けの場合、transition-basedな手法での「arc-standard」や「arc-eager」は適用できる。(が、「swap transition system」はダメっぽい)

スコア関数ρ

  • 先行研究に従って、FFNNを利用
  • ただし、「ρ(s,d;θ) := 状態sに対するベクトル関数 * 最後の層に関するパラメータベクトル」の形で、線形にスコアが計算される
  • これを次のようなsoftmax的な正規化をかけた学習を行う

大域的な正規化と局所的な正規化

局所的な正規化

  • Chen&Manning(2014)の方法では、j回目の決定行為の時の各決定行為d_jを選ぶ確率は、「決定行為d_jを選ぶスコア関数ρ()のexp()を取った値」を「すべてのjについてその値を計算した和」で割ったもの、を使っている
    • その状態における決定行為について正規化(足して1になるように)しているので「局所的」
    • 遷移確率的な感じ
  • この方法だと、最初から最後までの決定行為列の確率は、各状態における「決定行為の確率値の積」で表せる

大域的な正規化

  • 上記とは対照的に、最初から最後までの決定行為列の確率を、CRFのように「nまでのあらゆる決定行為列でのスコア合計のexp()を取った値の和」で割ったもの、を使う
    • 要するに、「考えられるすべての決定行為列」の確率値を足し合わせると1になるような正規化
    • パス全体を見て正規化しているので「大域的」
    • これだと、ある状態での決定行為の確率の合計は1にはならないので、「遷移確率」とはならない
  • 大域的な正規化を目的関数とする場合を「CRF objective」とよんでいるようです

学習

上記の局所的・大域的な正規化を行っている確率値pがあるので、損失関数は「L(最適な決定行為列d;θ)=-ln p(d;θ)」のように書ける。
損失関数が定義できれば、誤差を使って逆誤差伝播でNNを学習できる。
(微分はどうやって計算するのかコードをのぞいてみると、Tensorflowはgradients関数が使えて自動で計算できるっぽい)

ただ、まともに計算すると(おそらく各決定行為列ごとに係り受けの状態を保持しながら素性を取り出す必要があって膨大な決定行為列候補を持ち続ける必要があって)結構処理が重いっぽいので、「ビームサーチ」と「early updates」という手法を使っている。

ビームサーチ

1回目の決定行為、2回目の決定行為、、、、のように何回目の決定行為か？で階層をわけたとする場合、各階層ごとに、スコアの合計値が高いd個の決定列のみ保持する方法。dのことを「ビーム幅」と呼び、これを大きくするほど処理は増えるが正確な値になっていく。
d=1の時は、各決定行為で一番良いスコアを選び続けることに相当。

transition-baseな係り受け解析でも取られる方法のようですが、ビームサーチ自体はより一般的な手法で、競プロのマラソンマッチとかだとよく見かける気がします。 Chokudai search

early updates

詳しく引用論文を見ていないけど、ビーム幅から最適な決定行為列のパスが外れてしまうような場合、本来ビーム幅内にいて、かつ、最後の決定行為後は一番スコア合計値が高くなるようになっていなければならないことから、外れてしまった時点までの部分的な決定行為列を使って更新してしまう方法、のことのようです。

ビームサーチとearly updatesを使った場合は、「考えられるすべての決定行為列」を求めることはできないので、「ビーム幅に残っている決定行為列」で代用しているようです。

ラベルバイアス問題

局所的な正規化の場合は、遷移確率的に、必ずある状態における決定行為の確率は全部合わせて1になるようにしていましたが、これだと表現力が弱く、同じ入力で後に続く入力によってラベルが決まるような(先読みが必要な)問題に対してうまく対応できないようです。
実用上は局所的な正規化でも、入力のある程度の先読みを行えれば解消できる(できない例もすぐ作れる)とありますが、大域的な正規化を用いるとちゃんと扱える点で有用のようです。

実装

SyntaxNetのgithubのReadmeを読んでみると、英文が入力された後、上記のシステムを使った「品詞付与」→「係り受け解析」の順で処理をしているようです。
また、学習は、「局所的な正規化で事前学習」した後にその学習済みモデルを初期値に「大域的な正規化で学習」しているようです。
取り出す素性については、引用文献で素性について検討している論文があるようで、それを参考にしているようです。

メモ

  • windowsでdocker動かしていじってみようと準備してみたら、デフォルトのメモリが1GB程度の割り当てのようでビルドに失敗してしまったので、確保メモリは多めにしてあげたほうが良いようです
  • 引用論文は一通り目を通した方がよい
  • 学習の実装の細かいところで不明確な部分が多いので、一通り実装を読みたい
  • 論文の5.1の1行目、been beenは誤字？