スタックポインターネットワークによる依存関係解析

依存解析の新しいアーキテクチャである \emph{スタックポインターネットワーク} (\textbf{\textsc{StackPtr}}) を紹介します。この提案モデルは、ポインターネットワーク~\citep{vinyals2015pointer} と内部スタックを組み合わせており、まず入力文全体を読み込んで符号化し、その後深さ優先探索で上位から下位へ（根から葉へ）と依存木を構築します。スタックは深さ優先探索の状態を追跡し、ポインターネットワークは各ステップでスタックの最上位にある単語の子ノードを選択します。\textsc{StackPtr} パーサーは、文全体の情報とこれまでに導出したすべての部分木構造を利用でき、古典的な遷移ベースパーサーにおける左から右への制約を取り除きます。しかし、任意の（非射影的なものを含む）解析木を構築するステップ数は他の遷移ベースパーサーと同様に文長に対して線形であり、$O(n^2)$ の時間計算量を持つ効率的なデコーディングアルゴリズムが得られます。我々は20言語および異なる依存関係注釈スキーマをカバーする29つのツリバンクでモデルを評価し、そのうち21つで最先端の性能を達成しました。