はじめに

自然言語処理の基本的な処理の1つとして、係り受け解析(dependency parsing)があります。係り受け解析とは、単語間の修飾関係(係り受け関係)という形で、テキストの構文構造を明らかにする処理のことです。例えば「He went to the store by bike」というテキストを係り受け解析してみると、以下のようになります。

係り受け解析を行うツールはいくつかありますが、これはspaCyを使った場合の結果です。
spaCyはPython/Cythonで実装された自然言語処理ライブラリで、係り受け解析の他にも自然言語処理における様々な処理を行うことができます。
最近業務でspaCyを使って係り受け解析を行う機会があり、内部の仕組みについて気になったので調べてみました。本記事では、その調査結果について説明します。

本記事の位置付け

spaCyの係り受け解析器(DependencyParser)に関する公式ドキュメントを見てみると、Honnibalらの論文をベースに実装していると書かれています。これは係り受け解析の基本的な手法の1つであるArc-Eagerという手法に、いくつかの改良を加えたものとなっています。そこで本記事では処理の概要をざっくりと理解することを目的として、係り受け解析に関する基本的な概念を整理しながら、Arc-Eagerとその学習方法についてメインで解説します。そして、Honnibalらの論文における改良点についても、記事の最後で簡単に説明します。

尚、記事の内容はできる限り正確であるよう努めていますが、私自身も係り受け解析については今回初めて調査を行ったので、解釈の誤っている箇所があるかもしれません。もしそのような箇所を見つけられた方がいましたら、ぜひご指摘のコメントをいただければと思います。

改めて、係り受け解析とは

まず、係り受け解析をもう少し正確に定式化してみましょう。
係り受け解析は、「1つの文を表す単語列を入力として、その構文構造を表す有向グラフを出力する処理」だと言えます。この有向グラフは、文中の各単語に対応するノードと、それらを繋ぐ係り受け関係に対応するエッジから構成されます。各エッジには、係り受け関係の種類を表すラベル(nsubj : 主語、obj : 目的語、など)が付与されることもあります。冒頭の例だと、wentからHeに向かってnsubj(主語)というラベルの付いたエッジが張られていますね。
エッジの先のノードから見て、エッジの根元のノードをheadと呼びます。Heのheadはwentで、storeのheadはtoです。係り受け構造における最も基本的な制約として、各ノードが持てるheadの数は最大で1個だけです。
また多くの場合、係り受け構造はさらに以下の3つの制約を満たすと仮定します。

循環構造を持たないこと (acyclic)
全てのノードが繋がっていること (connected)
エッジが交差しないこと (projective)

1.と2.の制約を課すことは、係り受け構造は1つのルートノードを持つ木構造だと仮定することと等価です。この時、ルートノードを除く各ノードはそれぞれただ1つのheadを持ちます。このことから、係り受け構造は「係り受け木(dependency tree)」とも呼ばれます。冒頭の例は、wentをルートノードとした木構造になっています。3.の妥当性については意見が分かれるようですが、英語ではほとんどの文が交差なしの係り受け構造を持つようです。

グラフベースの手法と遷移ベースの手法

係り受け解析に対するアプローチは、「グラフベースの手法」と「遷移ベースの手法」の2つに大別されます。両者の違いは、大域最適を目指すのか局所最適を目指すのかという点にあります。

例として長さ$n$の単語列を考えます。各単語(ノード)に対してheadの候補が$n$個存在するので、係り受け構造の候補はざっくり$n^n$乗個も存在することになります(もちろん、この中には上記の制約を満たしていないものも多く含まれますが)。

グラフベースの手法は全ての候補に対して何らかのスコアを計算し、スコアが最大となる候補を選びます。大域最適な解が得られますが、膨大な候補を全て網羅するため計算時間は長くなります。一方で遷移ベースの手法は、単語を1つずつ読み込んで状態を遷移しながら局所的な選択を繰り返します(詳細は後述)。これにより高速に解析結果を得られますが、全候補を網羅するわけではないので、得られた解が大域最適であることは保証されません。とはいえ、実用的には遷移ベースの手法でも正しい解析結果を得られる場合が多いようです。

spaCyの係り受け解析器は遷移ベースの手法に基づいて実装されているため、ここから先では遷移ベースの手法についてより詳しく説明していきます。

Arc-Eager

遷移ベースの手法において最も基本となるものの1つが、Nivreらにより提案されたArc-Eagerという手法です。spaCyの実装のベースであるHonnibalらの論文も含め、遷移ベースの手法の多くはこのArc-Eagerに対して何らかの改良を加えたものとなっています。尚、Arcというのは矢印、つまりは係り受け関係のエッジのことです。
Arc-Eagerでは、スタックとバッファを用いて与えられた単語列を前から順に処理しながら、係り受け関係のエッジを1本ずつ確定させていきます。ここで、簡単な用語の定義を行います。

状態 (configuration): 【スタックの中身, バッファの中身, これまでに確定されたエッジのリスト】の3つの組で表される、係り受け解析のある途中時点での状態。
遷移 (transition): ある状態を別の状態へと変化させる操作。Arc-Eagerでは4種類の遷移が定義されている。

これらの用語を使って言い換えると、Arc-Eagerでは「現在の状態をもとに最適な遷移を選択して実行する」ということを繰り返して係り受け解析を行います。初期状態では与えられた単語列は全てバッファに入っており、スタックの中身は空になっています。状態間の遷移を通してバッファの中身は先頭から消費されていき、バッファが空になった時点で係り受け解析は終了します。次に、Arc-Eagerで定義されている4種類の遷移について説明します。

Shift: 「バッファの先頭の単語」をスタックの一番上に移動させる。
【前提条件】なし。
Left-Arc: 「バッファの先頭の単語」から「スタックの一番上の単語」へのエッジを確定させ、「スタックの一番上の単語」を取り除く。
【前提条件】スタックに1つ以上の単語が存在し、「スタックの一番上の単語」に既にheadが存在しないこと。
Right-Arc: 「スタックの一番上の単語」から「バッファの先頭の単語」へのエッジを確定させ、「バッファの先頭の単語」をスタックの一番上に移動させる。
【前提条件】スタックに1つ以上の単語が存在すること。
Reduce: 「スタックの一番上の単語」を取り除く。
【前提条件】スタックに2つ以上の単語が存在し、「スタックの一番上の単語」に既にheadが存在すること。

言葉での説明だけではよく分からないと思うので、「He went to the store by bike」という文を実際に係り受け解析する過程を見てみましょう。

4種類の遷移を組み合わせて係り受け構造が作られていく様子が実感できたでしょうか。
4種類の遷移のうち、エッジを作る遷移はLeft-ArcとRight-Arcの2つです。その名の通り、Left-Arcでは子ノードの方が親ノード(head)よりも左に存在する左向きのエッジが作られ、Right-Arcでは右向きのエッジが作られます。

遷移ベースの手法は高速だと上で説明しましたが、Arc-Eagerでは長さ$n$の単語列に対して最大でも$2n$回の遷移を繰り返せば終了状態に到達することが証明できます。

簡単な証明(気になる人向け)

Arc-Eagerの4種類の遷移は、「単語をバッファから取り除いてスタックに追加する操作」(Shift/Right-Arc)と「スタックから単語を取り除く操作」(Left-Arc/Reduce)の2つに分けられます。バッファが空になると終了なので、「バッファから取り除く」操作であるShiftとRight-Arcが計$n$回行われると終了状態に到達します。
Left-ArcとReduceではバッファの中身は減りませんが、スタックが空の状態ではこれらの遷移は実行できません。Left-Arc/Reduceを1回実行するには、Shift/Right-Arcを1回実行してスタックの中身を補充する必要があります。ということは、$n$回のShift/Right-Arcが完了するまでに実行できるLeft-Arc/Reduceの回数はせいぜい$n$回です。
よって、最大でも$2n$回の遷移を行うと終了状態に到達します。

また、Arc-Eagerによって作られる係り受け構造は、前述の「各単語のheadは1つまで」という制約、および1.(循環構造を持たない)と3.(エッジが交差しない)の制約を必ず満たすことも証明できます。ただし、2.(全てのノードが繋がっている)の制約を満たすことは必ずしも保証されません。よって一般的には、終了状態では1つ以上の木構造が存在することになります。(実用的な係り受け解析器では、終了状態においてheadを持たない全てのノードを疑似的なルートノードに接続して単一の木構造に変換するように実装されることが多いようです。)

さて、4種類の遷移を適切に繋げていけば係り受け構造を作れることが分かりましたが、そのためには「現在の状態をもとに最適な遷移を選択」する必要があります。つまり、【スタックの中身, バッファの中身, これまでに確定されたエッジのリスト】の情報をもとに、次はどの遷移を実行すべきかという4値分類を行うのです。(各エッジに係り受け関係の種類を表すラベルを付ける場合には、Left-Arc(nsubj)とかLeft-Arc(obj)のような種類ごとのクラスに分類する必要があるので、分類先のクラス数はもっと多くなります。)
このために、機械学習による何らかの分類器を利用します。最近の研究では何らかのニューラルネットを用いることが多いようで、spaCyでもニューラルネットを利用しています。ネットワーク構造の詳細については公式ドキュメントに記載されているので、興味のある方は見てみてください。

どうやって分類器を学習するのか

分類器を学習するためには、適切な学習データが必要です。係り受け解析の分野には、treebankと呼ばれる「文とその正しい係り受け木のペア」を集めた形式のデータセットがありますが、上記の分類器を学習するために必要なのは「状態と正しい遷移のペア」の形式のデータです。よって、treebankのデータをこのような形式に変換する必要があります。これを行う方法は、「static oracle」と「dynamic oracle」の2つに大別されます。spaCyではdynamic oracleを利用していますが、比較のためにstatic oracleの方から説明します。

static oracle

static oracleは、正しい係り受け木(gold treeと呼びます)を、それを作り出す遷移の系列へと変換する手法です。尚、エッジが交差しない係り受け木に対しては、そのような遷移の系列が必ず存在することが知られています。
やり方としては、gold treeを見ながら、初期状態からの状態遷移をシミュレーションするようにして遷移の系列を作ります。具体的には、実際に状態を遷移しながら、以下の判断を繰り返して新しい遷移を1つずつ繋げていきます。

「スタックの一番上の単語」を$w_s$、「バッファの先頭の単語」を$w_b$として、

gold treeにおいて「$w_b$から$w_s$へのエッジ」が存在するなら、Left-Arcを選択
gold treeにおいて「$w_s$から$w_b$へのエッジ」が存在するなら、Right-Arcを選択
「$w_s$よりも前にあり、かつ、gold treeにおいて$w_b$の親ノード(head)か子ノードになるような単語」が存在するなら、Reduceを選択
1～3のどれにも当てはまらなければ、Shiftを選択

例として、「He went there by bike」のgold treeを遷移の系列に変換する過程は以下のようになります。

static oracleの問題点

上記のstatic oracleには、2つの問題点があります。

1点目は、1つの係り受け木に対してただ1つの遷移の系列しか出力されないことです。実は、ある1つの係り受け木を作り出せる遷移の系列は、場合によっては2つ以上存在することが知られています。最終的に同じ係り受け木にたどり着くならどの系列も同等に正しいはずですが、static oracleは暗黙的にそのうちの1つを強制していることになります。

2点目は、正しい係り受け木にたどり着く系列(gold sequenceと呼びます)上の学習データしか生成できないことです。学習を終えて実際に係り受け解析を行うフェーズでは、実行すべき遷移を間違えてしまうことももちろん起こり得ます。Arc-Eagerでは過去の遷移をやり直せないので、系列の途中で一度でも間違えるとgold sequenceからは外れてしまい、その後復帰することはできません。しかし、static oracleで生成される学習データにはgold sequence上での「状態と遷移のペア」しか含まれていないため、「gold sequence上にない状態において、どの遷移を実行すべきか」は全く学習されていません。よって適切な遷移を選択することができず、一度の間違いがどんどん伝搬してしまうことになります。

dynamic oracle

これらの問題を解決するためにGoldbergらにより考案されたのが、dynamic oracleです。dynamic oracleは、ある状態$c$と正しい係り受け木$G_{gold}$のもとで、ある遷移$t$が「最適」かそうでないかをtrue/falseで判定します。

上記の1点目の問題点への解決策として、dynamic oracleでは1つの状態に対して2つ以上の遷移がtrueになり得ます。例えばある状態でShiftとReduceのどちらも最適なら、dynamic oracleは両方にtrueを返します。また2点目の問題点への解決策として、dynamic oracleはgold sequence上にない状態でも問題なく定義され、その状態において最適な遷移にtrueを返します。

さて、gold sequence上にある状態ならともかく、そうでない状態における「最適」な遷移とは何でしょうか。直感的に言うと、「なるべく損失の小さい係り受け木にたどり着ける」ような遷移が「最適」だということになります。

以下の図は、「He went there by bike」という文の係り受け解析結果を示しています。下段の2つの係り受け木はどちらも間違っていますが、それでも②の木の方がまだマシだと言えます。なぜなら正しい係り受け木に含まれる4本のエッジのうち、②の木は3本を含んでいる(1本足りない)のに対し、③の木は1本しか含んでいない(3本足りない)からです。このような考え方で、ある係り受け木$G$の正しい係り受け木$G_{gold}$に対する損失$L(G,G_{gold})$を以下のように定義できます。

L(G,G_{gold})=G_{gold}\text{には含まれるが}G\text{には含まれないエッジの本数}

gold sequence上にない状態からは、その後の遷移の系列をどう上手く選んでもgold treeにはたどり着けません。それでも、③の木よりは損失の小さい②の木にたどり着く方が望ましいです。ある状態$c$からたどり着ける木の中で損失が最小の木が、損失1の木であるとします。この時、$c$から1回遷移した状態$t(c)$からも損失1の木にたどり着けてほしいです。このように、「到達可能な木の損失の最小値を増やさない」遷移が「最適」な遷移です。逆に、$t(c)$からは損失2以上の木にしかたどり着けないなら、その遷移は「最適」ではありません。

さて、どのような遷移が「最適」かは分かりましたが、そのような遷移をどうやって見つけるのでしょうか。これを考えるのに役立つArc-Eagerの性質として、「ある状態$c$において、係り受け木$G$に含まれる個々のエッジが全て到達可能であるなら、$G$は到達可能である」というものがあります。そして、ある状態$c$において単語$w_i$から$w_j$へのエッジが到達可能なのは、以下の2つの場合です。

状態$c$にたどり着くまでの遷移によって、既に$w_i$から$w_j$へのエッジが確定されている場合。
$w_i$と$w_j$のうち、前にある方はスタックかバッファにあり、後ろにある方はバッファにあり、かつ、$w_j$のheadがまだ確定していない場合。

具体例として、「He went there by bike」の解析途中の以下の状態における最適な遷移を考えてみましょう。

これは3回目までの遷移が終わった状態ですが、2回目の遷移で正しくはLeft-ArcすべきところをRight-Arcしてしまっているため既にgold sequenceからは外れており、この状態からはもうgold treeにはたどり着けません。

この状態から右下にある②の木(損失は1)にたどり着けるか、上記の性質から考えてみましょう。まず②の木に含まれる4本のエッジのうち、(He→went)と(went→there)の2本は既に確定しています。次に(went→by)についてですが、前にあるwentはスタックに、後ろにあるbyはバッファにあり、子になるべきbyにはまだheadが付けられていないため、このエッジは到達可能です。同様にして(by→bike)も到達可能と分かるので、この状態から②の木は到達可能です。

しかしこの状態からRight-Arcを実行すると、②の木は到達不可能になります(スライドを右に送ってください)。なぜなら、(went→by)のエッジが到達不可能になってしまうからです。Right-Arcによってbyのheadはthereに確定し、byはスタックに移動します。これにより、byがwentの子になる可能性が失われるのです。「到達可能な木の損失の最小値」が増えてしまうので、この状態においてRight-Arcは最適な遷移ではありません。

このように、ある遷移により新たに到達不可能となるgold treeのエッジが存在するかを調べることで、その遷移が最適かどうかを判定できます。この状態ではReduceしても新たに到達不可能となるエッジは存在しないので、Reduceは最適な遷移だということになります。

dynamic oracleを用いたオンライン学習

gold sequenceから外れた状態においてもなるべく損失を増やさない遷移を選択できるように分類器を学習するためには、gold sequenceから外れた「状態と正しい遷移のペア」も学習データとして与える必要があります。これを実現するため、以下の方法で実際に状態を遷移しながら分類器を学習します。

分類器により、現在の状態において実行すべき遷移を予測する。
gold treeとdynamic oracleにより、現在の状態において真に最適な遷移のセットを求める。
1.と2.の結果から損失を計算し、分類器の重みを更新する。
1.で予測された遷移を、たとえ間違っていた(=最適でなかった)としても実行する。

4.が特に重要で、分類器による予測結果は(特に学習の初期段階では)必ずしも正しいとは限りませんが、あえてそれを信じて(時には)gold sequenceから外れることで、gold sequence上にない「状態と正しい遷移のペア」も学習させることができます。

non-monotonic(非単調)な遷移の導入

最後に、Honnibalらの論文における改良点について簡単に説明します。
Arc-Eagerでは過去の遷移の結果を後から修正できないため、途中で一度でも間違った遷移を選んでしまうと、その後どう頑張っても正しい係り受け木にはたどり着けません。Honnibalらの論文では、Arc-Eagerのこのような単調性(過去に行った遷移のやり直しができない性質)を和らげるような改良が行われています。

Arc-Eagerで「現在の状態をもとに最適な遷移を選択」する際、実際にはスタック/バッファ内の全ての単語の情報を利用するわけではなく、それぞれの上の方にある数単語をもとに分類器のための特徴量を作ることが多いです。よって、次の遷移を選択するために重要な手がかりとなる単語が文の後ろの離れた場所にあると、それが特徴量に含まれない(=考慮されない)ために間違えてしまう場合があります。このような場合、さらに何回か遷移を行って後ろの単語が「見える」ようになった後の方が適切な判断を行える可能性があります。

このような背景からHonnibalらの論文では、より後に実行される遷移が過去の不適切な遷移の結果を修正できるように、non-monotonic(非単調)な遷移を新しく導入したり、既存の遷移の動作を変更するという改良を行っています。

終わりに

何気なく使っているツールでしたが、内部の仕組みを調べてみると面白いものですね。
今後はもっと感謝して使っていこうと思います！

参考文献

Matthew Honnibal, Mark Johnson (2015), An Improved Non-monotonic Transition System for Dependency Parsing
Joakim Nivre (2004), Incrementality in Deterministic Dependency Parsing
Joakim Nivre (2003), An Efficient Algorithm for Projective Dependency Parsing
Yoav Goldberg, Joakim Nivre (2012), A Dynamic Oracle for Arc-Eager Dependency Parsing
統計的係り受け解析入門
最近のTransition based parsing

spaCyはどうやって係り受け解析しているのか調べてみた