Dependency Parsingとは？
自然言語処理におけるParsingつまり構文解析とは、単語ごとの粒度で文章に木構造のような意味解析を行うのに都合の良い構造を見出すことだ。
最も代表的かつ一般的な構文解析は、次の図のような文の構成要素（名詞句・動詞句・・とか）・品詞に基づいた構文解析だろう。これは文脈自由文法（「文→名詞句 動詞句」「名詞句→冠詞 名詞 | 代名詞 | ..」のような生成規則を逆向きに適用して木を作る）を使って構成される。
構成要素ベースの構文解析では名詞句・動詞句のような構成要素を仮定しなければいけないが、これは完全に言語依存で、言語によっては存在しない構成要素や品詞がある（日本語には冠詞や前置詞が無いとか）ので言語横断的に適用することができない。
そこで使えるのが上のようなDependeny Parsing(DP)だ。Dependency Parsingは文中の依存関係Dependencyに基いて構文解析を行う。これの何が嬉しいかというと、構文解析の下流工程である意味解析が非常に行いやすいことだ。つまり、例えば動詞の部分では関係に方向がついているので、何が動作の主体で何が客体か、などのような関係を捉えやすい。Dependency Parsingにおいては、①各ノード（単語）の流入エッジは必ずひとつでなければいけない（流出エッジは何個でも良い） ②よって非環式である（循環閉路がない） ③連結グラフである の3つの条件を満たすことが約束されなければいけない。
なお、上のように表した時に枝が交差しないように描けるとき、そのDependency TreeをProjective（投影性？）といい、英語の文は基本的にProjectiveだ（が、他の言語では成立しないことがある）。
ニューラルネットによるDependency Parsing
Dependency Parsingの手法として、最大全域木問題（Maximum Spanning Tree）を解くことでDependency Treeを求める手法がある。つまり、スコア（あらかじめ人間が作ったスコアのルールにに基いて木にスコアをつける）を最大化する木構造を探し、それをDependency Treeとする方法(2005年頃にアルゴリズムができている)がある。しかし、これは人間が作ったルールに基づくので恣意的であり、そのルールに性能が依存する上それは言語依存の部分があるので、近年（2014年頃）ニューラルネットワークで自動的にDependency Parsingを行う手法が提案された。
それはMALT パーサーと呼ばれていて、基本構造はよくコンパイラなどで使われるのと同じShift-Reduce型のパーサーだ。つまり、下図のように文頭からスタックにどんどん単語を追加していき（SHIFT）、Dependencyを発見したらスタックから単語を取り除いて（REDUCE）AにDependencyを追加する（AはDependencyの集合）という仕組みだ。
遷移（Transition: SHIFTかREDUCEかの判断）は手作りの特徴とルールに基いて行われるのが伝統的なやり方だったが、これをニューラルネットによって自動化しよう、というのがNNによるDependency Parsingの基本的なアイディアだ。
基本構造：もう少し詳しく
学習の目的は
番目の正しい遷移
を予測することであり、その際に使える情報は以下である。なお、これらをconfiguration(
と表す)。
- 対象単語とその品詞
- Dependencyの矢印の先の単語と、そのラベル
- スタックとバッファでの単語の位置
これをニューラルネットによって判断するにはどうすればよいか？単純に、それらのベクトル表現をすべてくっつけたものを入力にしてやれば良い！
つまり、入力ベクトルは![[\bm{x}^w, \bm{x}^t, \bm{x}^l ]](http://functionp.com/wp-content/ql-cache/quicklatex.com-f9771f72d7433c97cf9ea4b238c3a9f7_l3.png "Rendered by QuickLaTeX.com")
となる（それぞれ順に単語・品詞タグ・枝ラベル）。そして、隠れ層は以下の式で表される
面白いのは、活性化関数に３乗（立方）を使っていることだ。NNでは一般的ではないが、このタスクでは一番性能が良かったらしい。
出力レイヤーは通常通りソフトマックスを用いる。出力レイヤーの次元数は遷移の数(ラベルも加味した遷移なので、SHIFTとREDUCEの2種だけということではなく、結構多い)で、一番値の大きかったノードの遷移を選択する
単語・品詞タグ・枝ラベルはすべて埋め込み表現(embedding. 分散表現の一種)で表されている。品詞タグの分散表現というのは、単語の類似度と同じように例えば「”複数名詞”は”冠詞”より”単数名詞”に近い」などのような類似度が反映されたベクトル表現である。ただし、このembeddingは通常の単語表現のembeddingとは異なり、対象単語だけではなくスタック・バッファ内の数語を混ぜあわせて作られた表現である。詳しくは[1]参照。
正しい遷移とconfigurationのペア
のデータセットから得て、入力から出力
を順伝播で作成し(は遷移
が起こる確率)、誤差を次の式で計算する（普通のクロスエントロピー）。
はパラメータ、二項目はL2正則化項、学習方法は普通のNNと同じバックプロパゲーションである。
まとめ
[1]から引用したパーシングの結果は上の表の通りだ。
伝統的なMALTパーサー（人間のてづくり特徴ベース）よりも、過去のいずれのパーサーよりも良い結果（遅いが）を出しているのがわかる。
また、今回は扱わないが、上述の最大全域木MSTベースのパーサーの（特徴ベースでなく）NN版もあるようだ（これは2015年）。
ニューラルネット・Deep Learning（本例は1層なので深層ではないが）が人間のつくった特徴量ベースの手法を蹂躙するという構図は画像認識の領域のみならずいろいろなところで起こっているということが理解できる。
参考文献
[1] Chen, Danqi, and Christopher D. Manning, 2014, A fast and accurate dependency parser using neural networks, In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 740–750. Doha.
http://cs.stanford.edu/people/danqi/papers/emnlp2014.pdf
Be First to Comment