※本記事は、スタンフォード大学のCS224N: NLP with Deep Learning | Spring 2024 | Lecture 4 - Dependency Parsingの内容を基に作成されています。講義の詳細情報は https://www.youtube.com/watch?v=KVKvde-_MYc でご覧いただけます。本記事では、講義の内容を要約・構造化しております。なお、本記事の内容は原講義の内容を正確に反映するよう努めていますが、要約や解釈による誤りがある可能性もありますので、正確な情報や文脈については、オリジナルの講義をご視聴いただくことをお勧めいたします。
スタンフォード大学のオンライン人工知能プログラムについての詳細は https://stanford.io/ai をご参照ください。講義のスケジュールやシラバスは https://web.stanford.edu/class/archiv... でご確認いただけます。
登壇者：クリストファー・マニング教授 トーマス・M・シーベル機械学習教授、言語学・コンピュータサイエンス教授 スタンフォード人工知能研究所（SAIL）所長
1. 序論と構文構造の概要
1.1. コースの課題と PyTorch に関する案内
今日は火曜日の内容から180度変わって、人間言語の文の構文構造、言語構造、依存構造解析、そして依存関係とその解析器の構築方法について話します。我々は今日、言語学の領域にしっかりと足を踏み入れます。
課題2について少し説明します。火曜日に配布しましたが、課題2の後半ではPyTorchを使って依存構造解析器を構築していただきます。実際に構築するのは機械学習による決定を行う部分だけで、依存構造解析器の残りの部分はほとんど提供します。これは、主要なディープラーニングフレームワークの一つであるPyTorchを使用することを思い出させる機会でもあります。そのためPyTorchに詳しくない方は、金曜日のPyTorchチュートリアルに参加することを強くお勧めします。ただし、課題2自体もPyTorchを学びながら進められるように設計されています。
最終プロジェクトについてはもうすぐ詳しい情報をお伝えしますが、TAや私と会って相談することを既に推奨しています。TAについての情報はオフィスアワーのページに掲載されています。
1.2. 統語構造の主要な2つの表現方法の紹介
人間言語の言語構造を考える際、主に2つの方法があります。1つ目は言語学者が通常「句構造」(phrase structure)と呼び、コンピュータサイエンティストが「文脈自由文法」(context free grammars)として知っている表現方法です。このアプローチについて少し説明しますが、今日のクラスの主題ではありません。今日は主に「依存文法」(dependency grammars)と呼ばれる代替的な考え方に焦点を当てます。
この2つの考え方の間にはある程度の対応関係を作ることができますが、今日はそれらの詳細には踏み込みません。句構造文法、あるいは構成素文法のバージョンでは、人間言語の構造を考える方法として、言語には何十万もの単語がありますが、それらのほとんどが基本的な品詞クラスに分類され、文の中での振る舞いを表現しています。
依存構造では、少し異なる方法で物事を表現します。単語が何かの主要な単語や主語(head)となり、どの単語がそれらの修飾語(modifiers)や引数(arguments)となるかを考えます。これらの表現方法はどちらも、どの単語が他の単語とグループ化し、どの単語が他の単語を修飾するかという文の構造を理解するために使用できます。
2. 句構造と文脈自由文法
2.1. 単語の品詞分類の説明
人間言語の構造を考える際、言語には多くの単語があります。何十万もの単語がありますが、興味深いことに、ほぼすべての単語が基本的な数種類のクラスに分類され、それらは単語の性質や文中での振る舞いを表しています。
例えば、「cat」（猫）や「door」（ドア）などの単語は名詞です。「linguistics」（言語学）も名詞です。また、「cuddly」（もふもふした）のような単語は形容詞で、名詞を修飾できる単語です。
「the」（その）のような単語は、「the cuddly cat」（そのもふもふした猫）という場合の「the」は、命名法としては少し複雑です。現代言語学では通常、このような単語を限定詞（determiner）と呼びます。場合によっては冠詞（article）という名前も見かけます。時々、人間言語を8つの品詞カテゴリーに無理やり当てはめようとする人は、これを形容詞だと言いますが、実際には通常の形容詞とは振る舞いが異なります。
また、「by」「through」「on」「to」などの単語があり、これらは前置詞と呼ばれます。このように、各クラスに多くの単語が当てはまり、これらは従来「品詞」（parts of speech）と呼ばれています。
2.2. 句構造の構築方法
単語が整理されると、次はそれらをより大きな単位にまとめていきます。例えば「the cuddly cat」（そのもふもふした猫）はある種のまとまりを形成します。これは名詞「cat」の説明とみなすことができるので、これは「名詞句」（noun phrase）と呼ばれます。
同様に「by the door」（ドアのそば）はフレーズですが、この中には「the door」という名詞句が含まれています。しかしこの大きな単位「by the door」全体は「前置詞句」（prepositional phrase）となります。
さらに大きな単位を構築することも可能です。既に見た名詞句と前置詞句を組み合わせて、「the cuddly cat by the door」（ドアのそばにいるそのもふもふした猫）というより大きな名詞句を作ることができます。
このように、単語から始めて、それらを句に組み立て、さらにそれらの句を組み合わせてより大きな単位を構築していきます。この階層的な構造が句構造の基本的な考え方です。各句は特定のタイプを持ち（名詞句、前置詞句など）、それぞれが文全体の中で特定の役割を果たしています。
2.3. 文脈自由文法による英語の構文規則の説明と例
このような句構造を表現するために、英語の文の構造を表す句構造文法、つまり文脈自由文法を書き始めることができます。これは他の言語についても同様の句構造文法を書くことができます。これは名詞句の可能な構造を示し始めています。
例えば、次のようなルールを考えることができます：
- 名詞句は限定詞の後に名詞が続くというルール（NP → Det N） これにより「the cat」や「a dog」のような表現が可能になります。
しかし「the large cats」のような表現もあります。そこで、より良いルールとして次のように考えることができます：
- 名詞句は限定詞、オプションの形容詞、そして名詞から成る（NP → Det (Adj) N）
実際には複数の形容詞を持つこともできます。「the large cuddly green cat」（その大きなもふもふした緑の猫）のように、多くの形容詞を連続して使うことができます。そのため、アスタリスク（*）記号を使ってこれを表現します。これは「たくさんあっても良い」という意味です。
さらに、名詞の後に要素を付け加えることもできます。「in a crate」（ケージの中に）のような前置詞句を置くことができます。そこで以下のルールも追加します：
- 名詞句は名詞句の後に前置詞句が続くこともある（NP → NP PP）
- 前置詞句は前置詞の後に名詞句が続く（PP → P NP）
どこかで品詞のメンバーシップも表現する必要があります：
- 限定詞は「a」や「the」などの単語になる（Det → a | the）
- 形容詞は「large」「cuddly」などの単語になる（Adj → large | cuddly | ...）
- 前置詞は「in」「on」「under」などの単語になる（P → in | on | under | ...）
このように小さな文法を作ることで、これまで挙げた例文すべてを生成できます。名詞句を超えて考え始め、「talk to the cat」や「talk to the large cuddly dog by the door」のような文を考えると、ここには動詞「talk」と前置詞があります。そこで以下のルールを追加できます：
- 動詞句は動詞と前置詞句からなる（VP → V PP）
このようにして英語文の構造を文脈自由文法として構築していくことができます。これは言語学やその他の分野で広く行われています。
3. 依存文法の基礎
3.1. 依存構造の概念と主語と依存語の関係
依存構造は、言語学で広く使われており、NLPでも一般的に使用されています。私たちが作成する構文解析器にもこれを使います。依存構造は物事を少し異なる方法で表現します。単語が何かの主要語（head）であり、それらがどの単語を修飾語（modifiers）や引数（arguments）として取るかを考えます。
例えば「look in the large crate in the kitchen by the door」という文を考えてみましょう。これは見るという命令を表しているので、文全体の主要語は「looking」です。そして「looking」は一つ以上の引数や修飾語を取ります。この文が言っているのは、大きなクレートの中を見るということなので、何かの「中を」見ています。見ている場所は「クレート」です。
さらに「クレート」自体にも修飾語があります。それは「大きな」クレートで、「その大きな」クレートです。クレートはどこかに置かれているので、「in the kitchen」（キッチンの中に）もクレートを修飾しています。また「by the door」（ドアのそばに）もクレートを修飾しています。
このように依存構造の基本的な考え方は、主要語（head word）を特定し、どの単語が主要語を修飾しているかを示すことです。句構造表現でも依存構造表現でも、文の構造を理解する上で単語同士がどのように組み合わさり、どの単語が他の単語を修飾しているかを把握するために使用できます。
基本的な考え方は、人間がコミュニケーションを取る際、線形の流れで伝達するということです。従来の書き言葉であれば単語の線形の流れであり、話し言葉であれば線形の音の流れになります。今私が話しているのを聞いているように、話し言葉には単語間の空白はなく、時々句や文の終わりに一時停止することはありますが、一般的には連続した単語が口から出てきています。
しかし私の話を理解できているということは、その線形の流れを取り、意味に変えています。そこではある単語が他の単語を修飾し、句のような大きな単位を形成して文の意味を理解しています。人間の聞き手は「何が何を修飾しているか」を理解する必要があり、同様に私たちのモデルも言語を正しく解釈するために文の構造を理解する必要があります。
3.2. 句構造との違いと表現方法
句構造と依存構造は同じ情報を表現していますが、その方法が異なります。実際に例を通して見てみましょう。例えば「look in the large crate in the kitchen by the door」という文を句構造で表現することも、依存構造で表現することもできます。
句構造では、単語を階層的に組み立てていきます。例えば「look in the large crate」では、「the large crate」という名詞句があり、それと前置詞「in」で「in the large crate」という前置詞句になります。さらに「in the kitchen」や「by the door」も前置詞句として、より大きな構造の一部になります。
一方、依存構造では、文のヘッドとなる単語（この場合は「look」）から矢印が伸び、その単語が支配する他の単語を示します。「look」は「in」を支配し、「in」は「crate」を支配し、「crate」は「the」と「large」に修飾されます。また「crate」は「in the kitchen」や「by the door」といった前置詞句にも修飾されています。
句構造では誤りを犯してしまいましたが、実際には「the kitchen by the door」が一つの句になってしまうことはありません。正しくは「in the kitchen」が1つの前置詞句、「by the door」も1つの前置詞句として、それぞれがより大きな名詞句の一部になります。
依存構造の基本的な考え方は、どの単語が主要語であり、どの単語がその主要語を修飾しているかを特定することです。言語の構造を表現するために句構造と依存構造のどちらを使用するかは異なる選択肢ですが、いずれにしても、単語のグループ化と修飾関係を理解するという目的は共通しています。
3.3. 依存関係の矢印の描き方の慣習
依存文法に関して知っておくべきことがいくつかあります。依存文法構造の細かな詳細にこだわる必要はありませんが、大まかな考え方を理解していれば十分です。ただ、混乱の元となりうる点が一つあります。それは矢印の描き方です。
人によって矢印の描き方が異なります。一部の人は主要語（head）から依存語（dependent）へ向かって矢印を描きます。また別の人々は依存語から始まり、主要語へ向かって矢印を描きます。
現代の依存文法は主にフランスの言語学者リュシアン・テニエール（Lucien Tesnière）の研究に基づいており、彼は主要語から依存語へと矢印を描く方法を採用しました。今日の講義でもその方法を使っていますが、実際には両方の描き方を目にすることになるでしょう。
通常、依存関係は単一の根（root）を持つ木構造を形成すると仮定します。構文解析をより簡単にするために、文に仮想的なroot節点を追加するのが一般的です。これが開始点となり、文の主要語となる単語を一つだけ依存語として取り、そこから下方向に解析を進めていきます。
依存文法の矢印には通常、「主語」「目的語」「修飾語」などの文法関係の名前がタイプとして付けられます。これにより、単純な接続以上の情報が提供されます。ただし、これらの名前や手法の全てをマスターすることは期待していません。重要なのは依存文法の基本的な考え方と、フレーズレベルで何が何を修飾しているかを表現するものだということを理解することです。課題には前置詞句が何を修飾しているかといった質問がありますので、そのような質問に正しく答えられるようになることが重要です。
4. 自然言語の曖昧性
4.1. 前置詞句の曖昧性の例
何が何を修飾しているかを理解することが、文を正しく解釈する上でいかに重要であるかを示すために、いくつかの面白い例を紹介します。これらは新聞の見出しから取ったもので、一つの文に複数の解釈方法があるため面白い例となっています。
人間言語では、単語の並びが曖昧であることが一般的で、何が一緒になり、何が意味をなすかについての人間の解釈に依存しています。最初の例を見てみましょう：「Scientists count whales from space」（科学者が宇宙からクジラを数える）
この見出しはどのように二通りの解釈ができるでしょうか？
一つの可能性は、この前置詞句「from space」が「whales」を修飾しているということです。つまり「宇宙からのクジラ」で、科学者はそれを数えているという解釈です。もう一つの可能性は、「counting」（数える行為）が「from space」（宇宙から）行われているという解釈です。つまり、科学者が宇宙からクジラを数えているということです。
実際には後者の解釈が記事の内容に合っています。しかし、もう一つの解釈では宇宙クジラが存在し、科学者たちは到着している宇宙クジラを数えているということになります。
この例で見られるのは、名詞句の後に前置詞句が来るというパターンです。英語ではこのような場合、前置詞句が文のどの前の部分に依存しているかが常に曖昧です。前置詞句が増えれば増えるほど（例えば「in the morning」などを追加すると）、曖昧性は倍増します。
人間言語の重要な特徴は、統語的に全体的に曖昧だということです。プログラミング言語では局所的な曖昧性は解決されますが、人間言語はそうではありません。英語には「elseは最も近いifと対応する」といった単純なルールはなく、何も曖昧性を解決しません。文をより長くしても曖昧性は残ります。人間は文脈と知性を使って、何が起きているかを判断することが期待されているのです。
4.2. 等位接続の曖昧性
人間言語におけるもう一つの重要な曖昧性のタイプが等位接続の範囲の曖昧性です。例えば、次のような例を考えてみましょう：「shuttle veteran and longtime NASA executive Fred Gregory appointed to the board」（シャトル退役軍人と長年のNASA幹部フレッド・グレゴリーが理事会に任命された）
この文はどのように曖昧でしょうか？一人の人物を指しているのか、それとも二人の人物を指しているのかという曖昧性があります。つまり、フレッド・グレゴリーという一人の人物が「シャトル退役軍人」かつ「長年のNASA幹部」であるという解釈と、「シャトル退役軍人」と「長年のNASA幹部フレッド・グレゴリー」という二人の人物がいるという解釈の両方が可能です。
このような等位接続の曖昧性を扱うために、文法規則に追加のルールを設ける必要があります。例えば「名詞句は名詞句、接続詞、名詞句から成る」といったルールです。
英語ではまた、同格（apposition）と呼ばれる別の構造もあります。これは別の名詞句（例えば名前）の説明的な名詞句を置く構造です。例えば「the author Fred Gregory」（著者フレッド・グレゴリー）のような表現です。
英語について何度も言及していますが、ここで補足したいのは、今回は英語の例だけを紹介していますが、異なる言語では同じ曖昧性が全て現れるわけではないということです。例えば中国語を知っている人なら、前置詞句の例について「それは違う、なぜなら中国語では動詞を修飾する前置詞句は動詞の前に現れ、目的語となる名詞はその後に来るので、完全に曖昧さがない」と思ったかもしれません。その通りです。
しかし、だからといって中国語に曖昧性がないというわけではありません。中国語には非常に厄介な曖昧性がたくさんあります。ただ異なる言語には異なる統語構造があるため、曖昧性の現れ方も異なるのです。
4.3. 新聞見出しの曖昧性の例
英語では特に、より形式的な文章では、明示的な接続詞を使用する代わりに、カンマを使って単純に並置することで等位接続の考え方を表現することがあります。ここに最初のトランプ政権からの面白い例を挙げてみましょう。これは等位接続の範囲の曖昧性を示しています：
「Doctor: No heart, cognitive issues」（医師：心臓なし、認知的問題）
これもまた同じ種類の等位接続の範囲の曖昧性です。「no heart」と「cognitive issues」が接続されているのか、「no」が「heart or cognitive issues」の両方に適用されているのかという解釈の違いがあります。どちらの解釈を選ぶかはあなた次第です。
もう一つ異なる種類の曖昧性の例を紹介します。少し刺激的な内容ですが警告しておきます：「Students get firsthand job experience」（学生が直接的な仕事の経験を得る）
これもまた曖昧性を持っています。「firsthand」と「job」の両方が「experience」を修飾しているという解釈と、もし少し下品な考えを持っているなら思いつくかもしれない別の解釈があります。
もう一つ面白い例を紹介します：「Mutilated body washes up on Rio Beach to be used for Olympics beach volleyball」（オリンピックのビーチバレーで使用される予定のリオのビーチに切断された遺体が漂着）
この文の二つの解釈は何でしょうか？ここでは不定詞句「to be used for Olympic beach volleyball」が登場し、これも前置詞句と同様の効果を持ちます。つまり、異なるものを修飾することができます。オリンピックのビーチバレーで使用されるのが「リオのビーチ」なのか、「切断された遺体」なのかという曖昧性があります。
これらの例は、質の高い新聞からの実際の例です。こうした曖昧性は文の意味を理解するために文の構造をどのように使用する必要があるかを示しています。
4.4. 構文的曖昧性が自然言語処理に与える課題
自然言語処理のさまざまな実用的なシステムを構築する際にも、文の構造を活用することが多くあります。例えば、バイオインフォマティクスの分野では、タンパク質間相互作用などの事実を抽出したいことがよくあります。一般的には、パターンを探すことでそのような事実を抽出できます。「interacts」（相互作用する）という動詞を持つと、それは相互作用のパターンを示します。この動詞は引数を取ります。主語と「interacts with」という前置詞の引数を取り、これが相互作用関係を示します。
しかし、より大きなサイズの実際の例を考えてみましょう。これはウォール・ストリート・ジャーナルで毎朝読めるような少し退屈な文章です：「The board approved its acquisition by Royal Trustco limited of Toronto for $27 a share at its monthly meeting」（取締役会は、月例会議で、トロントのRoyal Trustco limitedによる1株27ドルでの買収を承認した）
この文には動詞と名詞句があり、その後に4つの前置詞句が連続しています。これらの前置詞句は何を修飾しているのでしょうか？
「by Royal Trustco limited」は「acquisition」（買収）を修飾しています。つまり、Royal Trustcoによる買収です。「of Toronto」はRoyal Trustco limitedを修飾しています。つまり、トロントのRoyal Trustco limitedです。「for $27 a share」は再び「acquisition」を修飾しています。「at its monthly meeting」は「approval」（承認）を修飾し、はるか前の部分に戻っています。
このように前置詞句がたくさんある文を扱うと、修飾関係の曖昧性がどんどん増えます。すべての選択肢を自由に選べるわけではなく、依存関係が交差しないという制約があります。一度後方に戻ったら、同じくらい後方か、さらに後方にしか戻れません。
それでも、読みの数はカタラン数列に従って増加します。これは三角形分割など、グラフ理論でもよく見られる数列です。物事が交差しないという同じ特性を持つため、カタラン数列が現れます。可能な読みの数は指数関数的に増加します。4つの前置詞句があると13の読みがあり、5つあると27になり、そこから増えていきます。
しかし重要なのは、銀行業界の人々は毎朝、コーンフレークを食べながらこのような文を読んでいても、13の異なる解釈のどれが正しいかを考えて頭が爆発することはないということです。私たちはこれを読みながら理解し、それが何を意味しているかは明らかです。
人間言語は統語的に全体的に曖昧です。プログラミング言語では局所的な曖昧性はありますが、常に解決されます。例えば「else」は最も近い「if」と結びつくというような単純なルールがあります（Pythonでは字下げの関係で少し異なりますが）。プログラミング言語には全体的な曖昧性はありません。
しかし、人間言語はそうではありません。より大きな文にしても曖昧性は残ります。読んで文脈と知性を使って何が起きているかを判断することが期待されているのです。
5. 言語学的構造の有用性
5.1. バイオインフォマティクスなどにおける事実抽出の例
文の構造は、様々な種類の自然言語処理システムを構築する際に多くの実践的な方法で使用されています。実用的なシステムでは、様々な種類の事実を抽出したいことがよくあります。バイオインフォマティクスに取り組む人々の場合、一般的にタンパク質間相互作用のような事実を抽出したいと考えています。
通常、このような事実はパターンを探すことで抽出できます。例えば、「interacts」（相互作用する）という動詞があれば、それは相互作用パターンを示します。この動詞は引数を取ります。主語と「with」という前置詞の引数を取り、これが相互作用を示します。
例えば「Kisy whatever that is interacts with Sassa」という文では、Kisyが何であれ、それがSassaと相互作用していることを示しています。ただし、この場合、SassaはKaiaとKaibと等位接続されているため、Kisyはこれらの他の2つのものとも相互作用していることになります。
このように、依存構造解析器のパターンを使用して、イベント理解システムのような、関心のある事実やイベントを抽出することができます。人々はこのような分析を生物医学テキストに対して行い、タンパク質間相互作用などの構造化されたデータベースを構築しています。
言語構造は有用であり、統語的には非常に曖昧であるため、人間は活発な解釈者として、テキストの前の部分の文脈知識、周囲の世界の知識、世界の仕組みに関する知識を使用して、正しい構造を理解していると考えるべきです。
5.2. 依存構造を利用したタンパク質間相互作用の抽出
バイオインフォマティクスの分野では、タンパク質間相互作用の事実を抽出する実際の例を見てみましょう。専門家たちは文のパターンを探し出すことでこうした情報を収集します。
例えば「Kisy whatever that is interacts with Sassa」という文を考えてみましょう。この文には「interacts」という相互作用を示す動詞があります。この動詞は主語「Kisy」と前置詞「with」に導かれる目的語「Sassa」を取っています。しかし、この例では「Sassa」は「Kaia」と「Kaib」と等位接続されています。これは「Kisy」がこれら3つすべて（Sassa、Kaia、Kaib）と相互作用していることを意味します。
依存構造解析によって、動詞がどの主語と目的語を取っているか、また等位接続によって関係が複数のエンティティに拡張されているかを正確に特定できます。「interacts with」のようなパターンを特定し、その引数（主語と目的語）を抽出することで、タンパク質A（主語）とタンパク質B（目的語）が相互作用するという事実を自動的に収集できます。
研究者たちはこのような分析を大量の生物医学文献に対して行い、既知のタンパク質間相互作用の構造化データベースを構築しています。これらのデータベースは生物学的な研究や薬剤開発において非常に価値のあるリソースとなっています。
依存構造解析によって抽出された情報は、単に「X interacts with Y」という表面的なパターンマッチングよりも正確です。なぜなら依存構造は複雑な文の中で単語間の実際の関係性を捉えるからです。これにより、偽陽性を減らし、複雑な文からも正確に情報を抽出できるようになります。
6. 依存文法の歴史と理論
6.1. 依存文法の長い歴史
依存文法について語る時、興味深い歴史的背景があります。現在、言語学の授業やスタンフォードのCS103のような計算機科学の授業で最も頻繁に目にするのは文脈自由文法や句構造文法ですが、実際には依存文法の方が本当に長い歴史を持っています。
人類の歴史を通じて、人間言語の構造を表現する主要な方法は依存文法でした。最初の依存文法学者、あるいは実際には人間言語の文法を記述しようとした最初の人物として認められているのはパーニニ（Panini）です。パーニニはサンスクリット語を研究していました。
パーニニがいつ生きていたかは、あまりにも昔のことで正確にはわかっていません。紀元前4世紀から8世紀の間のどこかと言われていますが、誰も本当のところは知りません。彼は現在のアフガニスタンの一部にあたる地域に住んでいたとされ、主に宗教的な理由からサンスクリット語の文法を開発することに着手しました。そしてサンスクリット語の構文を表現するために依存文法を使用しました。
また、最初の千年紀にはアラビア語の文法に関する多くの研究がありましたが、それらも依存文法を使用していました。対照的に、句構造文法の考え方は非常に最近のものです。句構造文法に関する最初の研究は1940年代に遡り、1950年代のチョムスキーの研究によって標準化されました。
このように、依存文法は人間言語の構造を表現するための伝統的かつ長い歴史を持つアプローチなのです。句構造文法が主流となったのは比較的最近のことで、特に西洋の言語学において顕著です。
6.2. チョムスキーの階層とその背景
計算機科学を専攻している皆さんにとって、チョムスキーについて知っていることは主に二つあると思います。一つはCS103などの入門クラスで強制的に学ばされたチョムスキー階層で、二つ目は彼が非常に左派的な政治家だということです。
ここでは最初の点だけに触れますが、実はチョムスキー階層は初級コンピュータサイエンティストを苦しめるためでも、形式言語理論の基本的な事実を説明するために発明されたものでもありません。チョムスキー階層は実は人間言語について考える中で発明されたものなのです。
当時（そして後の時代にも）、人間言語は有限状態文法（正規文法）と同等のメカニズムでモデル化されることが一般的でした。チョムスキーはそれが人間言語の複雑さを表現するには完全に不十分な形式主義だと論じたかったのです。そのため、チョムスキー階層は人間言語に関する議論の文脈で開発されました。
チョムスキーの主張は、人間言語の特定の性質（例えば、再帰的な構造や長距離依存関係）は正規言語では適切に表現できず、少なくとも文脈自由文法（あるいはさらに強力な形式）が必要であるというものでした。彼が形式的な言語のクラスの階層を構築したのは、人間言語の複雑さを捉えるために必要な計算能力を示すためだったのです。
このように、単に理論計算機科学の抽象的な構築物として教えられることが多いチョムスキー階層は、実際には人間言語の特性を理解し表現しようとする言語学的な探求から生まれたものなのです。
6.3. 口承で伝えられたパーニニの文法の興味深い事実
パーニニの文法についてもう少し説明します。ここにパーニニの文法の一部の図がありますが、実はこれは非常に誤解を招くものです。パーニニの文法に関する驚くべき事実の一つで、彼が何世紀に生きていたか誰も分からない理由の一部でもあるのは、パーニニの文法が口頭で作られたということです。
これは私の頭を完全に混乱させます。西洋の有名な作品、例えばホメロスの『オデュッセイア』や『イリアッド』は元々口承で伝えられ、何世紀もの間口頭で継承されました。高校で演劇をしたことがあれば、誰かが『オデュッセイア』を暗記することは難しいかもしれませんが、信じられないことではないでしょう。
しかし、言語の文法を暗記し、何百年もの間それを口頭で伝承するという考えは、私の想像を超えています。しかし、パーニニの文法では実際にそれが起こったのです。
この古い樺の皮の写本は、実際にはパーニニが文法を作った時期から約1000年後のものである可能性が高いのです。彼の文法は書かれたものではなく、口頭で教えられ、口頭で記憶され、口頭で継承されたのです。
この事実は言語学の歴史において本当に驚くべきことの一つです。何千もの細かい文法規則を含む複雑な言語分析システムを、何世代にもわたって正確に口頭で伝えるという能力は、当時の教育方法と記憶技術の驚異的な証拠です。これは現代のデジタル時代に住む私たちにとって、ほとんど想像できないことです。
7. アノテーションデータの重要性
7.1. 初期の自然言語処理における規則ベースアプローチの限界
現代の依存構造解析に進む前に、注釈付きデータの重要性と自然言語処理におけるその台頭について少し寄り道しておきましょう。これは興味深い逆転現象で、今日は一方向に進み、後のクラスでは別の方向に進むことになります。
初期の自然言語処理では、人々は「人間言語には構造がある」と気づき始め、人間言語の構造に関するルールを書き始めました。以前のスライドで、英語の構造のための文脈自由文法規則をいくつか書き始めたように、品詞の辞書や他の要素と共に、依存文法構造のルールも書くことができます。
人々はこうしたルール、文法規則、品詞辞書などを使って自然言語処理を試みました。それによって構文解析器が得られましたが、振り返ってみるとかなり貧弱な結果でした。それにはいくつかの理由があります。
一つの理由は、人間言語には非常に典型的で明確な構造がある一方で、奇妙な用法が出現する長いテールの混沌があり、手書きの言語の範囲をカバーすることが非常に難しくなるということです。これは人間が創造的に言語を使用するからです。
例えば、若者のスラング表現には詳しくないかもしれませんが、おそらくまだ知っているであろう例として、スターウォーズの「ヨーダ語」があります。文章の順序を入れ替えていますが、人々はそれでも理解できます。これは語順を変えていますが、通常の文法とは異なります。
また、それより前には、文の最後に「not」を置くという小さなトレンドがありました。例えば「that's a really great idea not」（それは本当に素晴らしいアイデアではない）といった表現です。人々はそれを理解することを学びましたが、通常の文法とは異なります。
完全な文法を書くことは本当に難しいですが、より大きな理由は曖昧性の問題です。単に文法を書くだけでは、前置詞句を持つ文には13の異なる解析があり、それらの間で選択する理由があまりありません。しかし、単語が他の単語をどれくらいの頻度で修飾するかという情報があれば、統計を取得し、どの順序で何が何を修飾するかを予測し始めることができます。
そのため、人々は確率的または機械学習モデルの基礎となる予測を行うことを望み始めました。これが、1960年代の最も初期の先例から、1980年代後半から1990年代にかけて本格的に始まった、自然言語処理や自然言語理解の進歩のために注釈付きデータリソースを構築することを決めた理由です。
1990年代と2000年代を通じて、自然言語処理の多くは、人々が注釈付きデータリソースを構築し、それらのリソースを使用して機械学習システムを構築することでした。これは後に大規模言語モデルによって逆転し、別の方向に進みましたが、それはまた別の週のトピックです。
7.2. アノテーションデータの登場と機械学習の進展
1990年代と2000年代の全体を通じて、自然言語処理分野の中心的なテーマは、人々が注釈付きデータリソースを構築し、それらのリソース上に機械学習システムを構築することでした。これは後に大規模言語モデルによって逆転し、別の方向に進みましたが、それは今後のクラスで扱うトピックです。
具体例として、Universal Dependencies（ユニバーサル依存関係）ツリーバンクを紹介します。私自身がこのプロジェクトに深く関わってきました。これはあらゆる目的に役立つ素晴らしいリソースです。特に、100以上の異なる言語の文が統一された依存関係形式で解析されている広範な言語横断的なデータベースとなっているため、言語横断的な研究や心理言語学的研究に非常に適しています。
このようなツリーバンクでは、「Mamar was a famous goat trainer」（ママルは有名なヤギのトレーナーだった）のような文を取り、その上に依存構造を付けていきます。これらはすべて非常に圧縮された形で記述されていますが、人間がこれらの依存構造を生成し、私たちに依存構造解析器などを学習するためのデータを提供しています。
実際、課題2で使用するのはまさにこの種類のデータです。依存構造解析器を構築するために、このデータからヤギのトレーナーや有名なトレーナーといった情報を学習し、何がどのようなものを修飾する可能性が高いかを予測するための統計や情報を構築します。
このようなツリーバンクの構築を始めることは、遅く困難な作業のように感じるかもしれませんが、非常に効果的な戦略であることが証明されました。なぜなら、一度人々がこれを行えば、構文解析器、品詞タガー、心理言語学モデルなど、あらゆる種類の用途に使用できる素晴らしい再利用可能なリソースを提供するからです。
これにより、機械学習に適した分布的頻度情報が得られ、さらに重要なことに、システムの評価方法を提供しました。これは、システムがパースを生成するのにどれだけ優れているかを評価する方法です。現代の機械学習の時代では笑えるかもしれませんが、1950年代、60年代、70年代に自然言語処理が行われていた時代には、誰も評価方法を持っていませんでした。
当時、良い構文解析器を持っていることを示す方法は、プログラムを実行して「文を入力して、見てください、うまく動作しています、本当に良い構文解析器です」と言うことでした。NLPシステムの体系的な評価は全く行われていませんでした。
そのため、「ここに手動で解析した1000文があります。あなたの構文解析器がそれらに対してどれだけうまく機能するかを評価しましょう」というのは、1980年代末から特に1990年代にかけて生じた革命的な新しい発展だったのです。
7.3. Universal Dependencies ツリーバンクの紹介と多言語対応
Universal Dependencies（ユニバーサル依存関係）ツリーバンクは、私が深く関わってきた素晴らしいリソースです。このリソースの優れている点は、100以上の異なる言語の文が統一された依存関係形式で解析されている広範な言語横断的なデータベースであることです。そのため、言語横断的な研究や心理言語学的研究に非常に適しています。
例として、「Mamar was a famous goat trainer」（ママルは有名なヤギのトレーナーだった）という文の依存構造を見ることができます。この構造では、すべての単語間の関係が明確に定義されています。人間がこれらの依存構造を手作業で生成し、そのデータが構文解析器の学習に使用されます。
このデータベースが持つ最大の利点は、すべての言語に対して同じ注釈スキーマを使用していることです。例えば、「主語」「目的語」「修飾語」などの関係が、言語に関係なく一貫した方法で注釈付けされています。これにより、ある言語で学んだことを別の言語に転移することが容易になります。
さらに、このツリーバンクは多くの低リソース言語も含んでおり、それらの言語に対する自然言語処理ツールの開発を可能にしています。一部の言語では数百の文だけですが、それでも基本的な構文解析器を訓練するのには十分です。
Universal Dependenciesプロジェクトは継続的に成長しており、新しい言語や新しい注釈が定期的に追加されています。このようなリソースが自然言語処理の発展に与えた影響は計り知れません。それ以前は、各研究グループが独自の形式で独自のデータを注釈付けしていたため、結果の比較が困難でした。
このプロジェクトによって、異なる言語間での一貫した評価が可能になり、言語処理技術の進歩を測定するための標準的なベンチマークが提供されました。課題2では、このUniversal Dependenciesデータを使用して依存構造解析器を構築することになります。
8. 依存関係解析アルゴリズム
8.1. 依存関係解析に必要な情報
これでこれらの知識をすべて持ったので、依存構造解析器の構築に取り掛かりたいと思います。まず、依存構造解析器が決定を下すために持つべき情報の種類について考えてみましょう。以下が依存構造解析に役立つ4つの基本的な要素です。
第一に、矢印の両端にある単語が妥当なものであるかどうかを考える必要があります。例えば「discussion of the outstanding issues was completed」（未解決の問題についての議論が完了した）という文では、「discussion of issues」（問題についての議論）は妥当な依存関係です。一方、「the」が「completed」の依存語になるというのは全く意味がありません。したがって、関係する単語が何であるかは重要です。
第二に、依存距離に関する要素があります。長距離の依存関係も可能ですが、ほとんどの依存関係は短距離です。多くの単語は隣接する単語に依存しています。そのため、短い距離の依存関係を優先するのは良い傾向です。
第三に、距離だけでなく、間にある要素も重要です。依存関係が動詞や句読点をまたぐことは稀です。
最後に、主要語（ヘッド）の結合価を考慮することです。これは主要語がいくつの引数を取るかということです。例えば、動詞「broke」（壊した）は、通常左側に何かを持ちます（誰が壊したか）、そして右側にも何かを持つ可能性があります（何が壊れたか）。しかし、「the cup broke」（カップが割れた）のように、左側に何かがあって右側に何もないこともあります。
一方で、任意の数のものを持つことはできません。「he broke the cup the saucer the dish」（彼はカップとソーサーと皿を壊した）とは言えません。つまり、左側には何かがあり、右側には何かあるかもしれないが、左側に無限に引数を取ることはできないという結合価の概念があります。
依存構造解析には他にも微妙な概念があります。通常、依存関係は図のように入れ子になっています。入れ子になった依存関係は文脈自由文法の木構造に対応します。例えば「I will assert that this is a sentence」（これが文であると主張します）という文では、「discussion」が「completed」という動詞の主語であり、通常文の主要なものは動詞であると言えます。そのため、ルートは「completed」へつながっています。動詞の主語である「discussion」も重要な要素ですが、動詞の引数（主語、目的語、修飾前置詞句など）はすべて動詞の依存語とみなされます。
8.2. 非交差依存と交差依存の違い
通常、依存関係はこのように入れ子になっており、これは文脈自由文法で構築できる木構造に対応しています。しかし、人間言語では入れ子にならない依存関係が生じることもあります。例えば「I'll give a talk tomorrow on new networks」（明日、新しいネットワークについて講演します）という文では、「on new networks」は「talk」を修飾していますが、「tomorrow」は「give」の引数です。
このため、依存関係が交差しており、これを「非射影的」（non-projective）依存関係と呼びます。また、質問を形成する際にも同様の現象が見られます。例えば「Who did Bill buy the coffee from yesterday?」（ビルは昨日誰からコーヒーを買ったのか？）という文では、「who」は前置詞「from」の目的語ですが、前に移動されているため、再び非射影的になります。
考えてみると、依存関係の木はまだありますが、単語の順序が異なるため、非射影性が生じます。完全な依存構造解析器を構築するためには、この非射影性に対処する必要がありますが、私たちの構文解析器では射影的な依存構造解析のみを扱います。
依存構造解析にはさまざまな方法があります。動的プログラミングを使用する人もいれば、グラフアルゴリズムを使用する人もいます（時間があれば後でこれについて触れるかもしれません）。CS220/221で見たような制約充足法を使用する人もいます。しかし、実際に最も一般的な方法として浮上してきたのは、遷移ベースの構文解析です。これは興味深く、非常に単純な機械学習メカニズムを提供するため、課題2に適しています。これから詳しく見ていきましょう。
遷移ベースの構文解析では、クラスのたった2人だけがコンパイラのクラスを受講したことは残念です。コンパイラのクラスでも使われているシフト-リデュース構文解析という単純な形式の構文解析があります。ボトムアップから始めて小さな単位を一緒に置き、より大きな構成要素を構築していきます。しかし、ほとんどの人がそれを見たことがないのであれば、あまり役に立ちませんので、具体的な例をお見せします。
9. 遷移ベース依存構造解析
9.1. スタックとバッファを使用した遷移ベース依存構造解析の仕組み
貪欲な決定ベースの構文解析、つまり遷移ベースの構文解析では、文を扱うためにいくつかのデータ構造を使用します。正確には二つのデータ構造があります（実際にはもっとありますが）。一つは入力文の単語を保持する「バッファ」、もう一つは文の構造の部分を構築していく「スタック」です。
知っておくべき小さなコツとして、バッファの先頭は左側に書かれ、スタックの先頭は右側に書かれます。そして、シフトやリデュースなどのアクションを実行し、アーク構築アクションを実行すると、文の依存構造となる依存アークのセットを構築していきます。
これは非常に抽象的なので、具体例を示したいと思います。この非常にシンプルな例「I ate fish」（私は魚を食べた）の構文解析をしてみましょう。
まず、スタックにルートシンボルを置き、バッファには文のすべての単語を入れた状態から始めます。これが開始条件です（とても小さく書いてあります）。
処理の各ステップで、3つの操作の選択肢があります。バッファの先頭の単語をスタックに移動する「シフト」、または「左アーク」か「右アーク」を実行できます。これは二つのリデュース操作で、単語の一方が他方の依存語であることを示すことで、構文構造の一部を構築します。左右の方向は依存関係の方向を示します。
ここで、実行できる操作のシーケンスを見てみましょう。最初に行えることは「シフト」操作です。これにより「I」をスタックに移動します。次に再び「シフト」を行い、「ate」もスタックに移動します。これで3つの要素がスタックに乗りました。
この時点で他の操作も可能です。特に「左アーク」はスタックの上位2つの要素を取り、一番上にあるものを主要語（ヘッド）とし、その下にあるものを依存語とします。「左アーク」操作を実行すると、「I」が「ate」の依存語であることを示し、依存語をスタックから取り除きますが、「I」を「ate」の依存語とする依存関係を追加します。
次に別の「シフト」操作を行い、「fish」をバッファからスタックに移動します。そして「右アーク」を実行し、「fish」を「ate」の依存語とします。これにより「fish」はスタックから消え、「fish」が「ate」の依存語であるという新しい依存関係が追加されます。
再び「右アーク」を実行し、今度は「ate」が「root」の依存語であることを示します。これでスタックには「root」だけが残り、「ate」が「root」の依存語であるという新しい依存関係が追加されます。
この時点で終了条件に達しました。終了条件はバッファが空で、スタックに「root」という単語だけが含まれている状態です。
これにより、遷移ベースの構文解析と呼ばれる遷移の小さなセットが得られ、これらの異なる遷移のシーケンスを実行することで文の構造を構築できます。いつシフトし、いつリデュースするか、そして左アークか右アークかを選択する必要があり、これらの選択によって文の構造が決まります。
9.2. シフト・リデュース操作の説明
遷移ベース依存構造解析の中心となるのは、文の構造を構築するために使用する3つの基本操作です。これらの操作は以下のとおりです：
- シフト（Shift）操作: これはバッファの先頭にある単語をスタックに移動する操作です。文の処理を始める際には、まずバッファにある単語をスタックに移動して分析する必要があるため、通常はシフト操作から始めます。例えば「I ate fish」という文の処理を始める際、最初のシフト操作で「I」をバッファからスタックに移動します。
- 左アーク（Left Arc）操作: この操作はスタックの上位2つの項目を取り、一番上の項目（右側）を主要語（ヘッド）として、その下の項目（左側）をその依存語として扱います。操作後は依存語をスタックから取り除き、依存関係を記録します。例えば、「I ate」がスタック上にある場合、左アーク操作を実行すると「I」が「ate」の依存語（主語）であることを示し、「I」をスタックから取り除きます。
- 右アーク（Right Arc）操作: この操作も同様にスタックの上位2つの項目を扱いますが、今度は下の項目（左側）を主要語として、上の項目（右側）をその依存語とします。操作後は依存語をスタックから取り除き、依存関係を記録します。例えば「ate fish」がスタック上にある場合、右アーク操作を実行すると「fish」が「ate」の依存語（目的語）であることを示し、「fish」をスタックから取り除きます。
これらの操作の選択により、文のさまざまな構造を構築することができます。例えば「I ate fish」という文で、もし「I」が主要語で「ate」がその依存語であるべきだと考えるなら（通常の解析とは異なりますが）、右アーク操作を選択することでそのような構造を作ることができます。
各ステップで正しい操作を選択することで、正確な依存構造を構築することができます。この方法の利点は、操作の数が文の長さに比例するため、線形時間で構文解析が可能になることです。
9.3. 具体的な例："I ate fish"の依存構造解析のステップバイステップ解説
非常に単純な例文「I ate fish」の依存構造解析を詳細にステップバイステップで見ていきましょう。
初期状態:
- スタック: [root]
- バッファ: [I, ate, fish]
- 依存関係: {}
ステップ1: シフト操作
- アクション: バッファの先頭の単語「I」をスタックに移動
- スタック: [root, I]
- バッファ: [ate, fish]
- 依存関係: {}
ステップ2: シフト操作
- アクション: バッファの先頭の単語「ate」をスタックに移動
- スタック: [root, I, ate]
- バッファ: [fish]
- 依存関係: {}
ステップ3: 左アーク操作
- アクション: スタックの上位2つの項目について、上位の「ate」を主要語とし、「I」をその依存語とする
- スタック: [root, ate] （「I」は依存語としてスタックから取り除かれる）
- バッファ: [fish]
- 依存関係: {(I, ate)} （「I」は「ate」の依存語）
ステップ4: シフト操作
- アクション: バッファの先頭の単語「fish」をスタックに移動
- スタック: [root, ate, fish]
- バッファ: []
- 依存関係: {(I, ate)}
ステップ5: 右アーク操作
- アクション: スタックの上位2つの項目について、下位の「ate」を主要語とし、「fish」をその依存語とする
- スタック: [root, ate] （「fish」は依存語としてスタックから取り除かれる）
- バッファ: []
- 依存関係: {(I, ate), (fish, ate)} （「fish」が「ate」の依存語として追加）
ステップ6: 右アーク操作
- アクション: スタックの上位2つの項目について、下位の「root」を主要語とし、「ate」をその依存語とする
- スタック: [root] （「ate」は依存語としてスタックから取り除かれる）
- バッファ: []
- 依存関係: {(I, ate), (fish, ate), (ate, root)} （「ate」が「root」の依存語として追加）
終了条件: バッファが空であり、スタックには「root」だけが残っています。これで解析が完了し、以下の依存構造が生成されました：
- 「I」は「ate」の依存語（主語）
- 「fish」は「ate」の依存語（目的語）
- 「ate」は文全体の主要語（「root」の依存語）
この例では、各ステップで正しい操作を選択したため、文法的に正しい依存構造を得ることができました。異なる操作を選択していれば、異なる構造が生成されましたが、それは文法的に不正確なものになっていたでしょう。
9.4. Joakim Nivre の線形時間アルゴリズムの紹介
遷移ベース依存構造解析の中心にあるのは、2000年代初頭にヨーム・ニーヴレ（Joakim Nivre）というスウェーデンの自然言語処理研究者が提案したアイデアです。彼の写真がどこかにあったと思いますが。
ニーヴレは、それまで一般的に使われていた動的プログラミングやチャート構文解析などの手法ではなく、機械学習を活用した高速で効率的な構文解析器を構築できるのではないかと考えました。その方法が先ほど説明した遷移のシーケンスを使うものでした。機械学習の役割は、各時点で正しい遷移を予測することです。
この方法の優れている点は、一度に一つの要素だけを扱うため、文を解析するために必要な操作の数が線形になることです。これにより線形時間の構文解析アルゴリズムが得られます。一方、CS103などで見た文脈自由文法の構造を完全に考慮する方法では、立方体時間のアルゴリズムとなり、はるかに処理が重くなります。
最も単純な形式の遷移ベース構文解析では、探索を一切行いません。各ステップで次の遷移を予測するだけであり、そのシーケンスが文の構文構造を決定します。ニーヴレが示した重要な結果は、機械学習が十分に優れているため、探索をまったく行わなくても非常に正確な構文解析器を得られるということでした。
彼が2005年に開発したときは、ニューラルネットワークが広まる前だったため、古いスタイルのシンボリックな特徴ベースの機械学習システムを使用していました。大きな分類器（ロジスティック回帰分類器やサポートベクターマシンなど）を使用し、指示的特徴（indicator features）を使っていました。
使用される特徴としては、「スタックの先頭の単語が"good"で、品詞が形容詞である」とか、「スタックの先頭の単語が"good"で、スタックの2番目の単語が動詞"had"である」といった組み合わせのマッチング関数があり、これらが機械学習システムで予測のための特徴として使用されました。
しかし、複数の条件を組み合わせた特徴を使い始めると、何百万もの特徴に対処する必要が生じました。個々の特徴は非常に希薄で、100万文中でわずか10回程度しか現れないようなものもありました。一方で、これらの特徴の組み合わせにより構文解析の精度は向上し、当時はかなり正確な構文解析器が作られていましたが、多数の特徴を扱うという望ましくない特性がありました。
このアプローチの課題は、特徴が希薄で、学習データに現れないような単語や組み合わせが存在すること、さらにこれらのシンボリック特徴の計算自体が高コストだったことです。実行時間の分析をすると、構文解析の大部分の時間は機械学習による決定ではなく、特徴の計算に費やされていたのです。
10. 依存関係解析の評価方法
10.1. ラベル無し依存精度の評価
依存構造解析器を評価する方法について説明する前に、まず依存構造解析器の評価方法の基本を理解しましょう。基本的には、提案している依存関係（矢印）が正しいかどうかを評価します。
例として、「she saw the video lecture」（彼女は動画講義を見た）という文を考えてみましょう。これが正解（ゴールド）の構文解析であるとします。この正しい構文解析をもとに、どのような依存関係があるかを書き出すことができます。例えば：
- 単語1の主要語は単語2
- 単語2の主要語は単語0（ROOT）
- 単語3の主要語は単語5
- 単語4の主要語は単語5
- 単語5の主要語は単語2
これらの数字のペアが依存関係を表しています。
誰かがこの文の構文解析を提案したとき、実際に正しい依存関係を得られたかを確認できます。例えば、5つの依存関係のうち4つが正しければ、精度は80%となります。
このように単純に依存関係（矢印）が正しいかどうかだけを見ることを「ラベル無し依存精度」（Unlabeled Dependency Accuracy）と呼びます。各依存関係が正しい位置にあるかだけを評価し、その関係がどのような種類の関係（主語、目的語など）であるかは考慮しません。
この評価方法は、構文解析器が文の基本的な構造をどれだけ正確に捉えているかを測定するのに役立ちます。特に、どの単語がどの単語に依存しているかという基本的な構造の正確さを測定できます。
10.2. ラベル付き依存精度の評価方法
依存構造解析の評価では、単に依存関係（アーク）が正しいかどうかだけでなく、それらの関係の種類（ラベル）も正確に予測できているかを評価することがあります。これを「ラベル付き依存精度」（Labeled Dependency Accuracy）と呼びます。
先ほどの例「she saw the video lecture」では、依存関係に「主語」「決定詞」「目的語」などのラベルを付けることができます。例えば：
- 単語1（she）の主要語は単語2（saw）、関係は「主語」
- 単語2（saw）の主要語は単語0（ROOT）、関係は「根」
- 単語3（the）の主要語は単語5（lecture）、関係は「決定詞」
- 単語4（video）の主要語は単語5（lecture）、関係は「修飾語」
- 単語5（lecture）の主要語は単語2（saw）、関係は「目的語」
ラベル付き依存精度では、アークの位置だけでなく、そのラベルも正しく予測する必要があります。例えば、あるシステムが5つの依存関係のうち5つすべてのアークの位置を正しく予測したとしても、そのうち3つのラベルが間違っていれば、ラベル付き精度は40%（5つのうち2つだけが完全に正しい）となります。
ラベル付き評価はより厳格で、構文解析器が文の文法的関係（主語、目的語、修飾語など）をどれだけ正確に理解しているかを測定します。これは、単に構造だけでなく、その構造の文法的な意味も捉えているかを評価する重要な指標です。
多くの現代の依存構造解析器は、ラベル無し依存精度とラベル付き依存精度の両方で評価されます。両方のスコアを比較することで、パーサーがどこで苦戦しているのかを理解できます。例えば、ラベル無し精度は高いがラベル付き精度が低い場合、パーサーは基本的な構造は捉えていますが、文法的関係の理解に課題があることを示しています。
11. ニューラル依存構造解析
11.1. 従来の特徴表現の問題点
2010年代半ばまで、依存構造解析は主にシンボリックな特徴を使った機械学習で行われていました。しかし、この手法にはいくつかの大きな問題点がありました。
第一に、特徴が希薄（スパース）だという問題です。例えば「スタックの先頭の単語が"good"で、品詞が形容詞である」という特徴は、訓練データ中にそれほど頻繁に出現しません。さらに複数の単語や条件を組み合わせた特徴は、さらに希少になります。
第二に、特徴が不完全だという点です。訓練データで見た単語や組み合わせの特徴はあっても、見ていない単語や組み合わせの特徴は欠けています。例えば「difficult」という単語の特徴を学習していても、「challenging」については情報がないといった状況が生じます。
第三に、これらのシンボリック特徴を計算すること自体が非常にコストが高いという問題があります。実行時間の分析をすると、構文解析の時間の大部分は機械学習による決定ではなく、特徴の計算に費やされていました。つまり、シンボリックな特徴計算が構文解析のボトルネックになっていたのです。
これらの問題から、ニューラルネットワークが成功を示し始めたことで、密で（dense）コンパクトな特徴表現を活用したより良い依存構造解析器をニューラルネットで構築できるのではないかという考えが浮上しました。これが次に見ていくニューラル遷移ベース依存構造解析の出発点となりました。
11.2. 分散表現を活用したニューラル依存構造解析の利点
ニューラル依存構造解析の大きな利点は、単語埋め込み（word embeddings）を活用できることです。すでに前回の授業で単語埋め込みについて見てきましたが、これを利用することで単語の分散表現を使用できます。これには大きな利点があります。特定の単語や特定の設定を見たことがなくても、類似した単語を見ていれば、単語の類似性に基づいて何が起こりそうかを推測できるのです。
さらに、単語の分散表現だけでなく、品詞（parts of speech）の分散表現も利用できます。先ほど名詞、動詞、形容詞という基本的な品詞について言及しましたが、実際のNLPシステムではもっと細かい品詞分類が使われています。例えば複数形名詞と単数形名詞などは異なる記号ですが、非常に似ています。これらに分散表現を与えることで、互いに近い関係にあることを表現できます。
同様に、依存関係のラベルの種類についても、一部は互いに密接に関連しています。これらにも分散表現を与えることができます。
依存構造解析器の状態を表現するために、同じようなスタックとバッファを使用しますが、予測のための遷移を行う際に、スタックとバッファの重要な要素（バッファの先頭の単語や、スタックの上位2つの単語など）を取り出します。これらは、シフトを行う場合に移動する単語や、左アークまたは右アークを行う場合に組み合わせる単語です。
それぞれの要素について、単語とその品詞の分散表現を取り、さらに複雑なことに、すでに構築した依存関係についても、スタック上の何かがすでに依存関係に関与している場合、それらの分散表現も取ります。そしてこれらをすべて連結して大きなベクトルを作成します。これは前回の授業で、ある単語が場所かどうかを予測するために5つの単語を連結したのと同じ方法です。
そしてこの入力をニューラルネットワークに供給します。入力層は連結された分散表現で、それを隠れ層（WX + b）に通し、ReLU非線形性を適用します。そして上にもう1層のニューラルネットワーク（W2*h + b2）を置き、その出力をソフトマックスに通して、シフト、左アーク、右アーク操作のいずれかの確率分布を得ます。
このアプローチが従来の手法より強力だったもう一つの理由は、他の依存構造解析器がまだサポートベクターマシンやロジスティック回帰などの線形分類器を使用していた一方で、私たちは深層ニューラルネットワークを使用して非線形分類器を実現したことです。これにより、以前の遷移ベース依存構造解析器よりも高い精度を達成し、他のどの依存構造解析器とも同等の性能を示すことができました。
11.3. Chen & Manning のニューラル遷移ベース依存構造解析器の構造と性能
ニューラル遷移ベース依存構造解析の革新的なアプローチは、当時私の博士課程の学生であったチェン（Chen）によって開発されました。彼は224nのヘッドTAを以前2回務めていました。彼女はニューラル遷移ベース依存構造解析器を構築し、この手法の成功を示しました。
これはニーヴレの遷移ベース依存構造解析器でしたが、他の依存構造解析の手法も探求されていました。これらはグラフベースの依存構造解析器でした。シンボリック特徴機械学習法の場合、ニーヴレの構文解析器は線形遷移ベース構文解析のアイデアを使っていたため非常に高速でした。一方、グラフベースの依存構造解析器はずっと遅く、約50倍も遅かったのです。しかしそれらは少し精度が高かったことがわかります。ここでより良い数値が見られます。
基本的にチェンが示すことができたのは、グラフベース依存構造解析器と同じくらい正確なものを構築できるが、他の遷移ベース構文解析器のように高速であるということでした。実際、実数と行列を使うことでより遅くなるはずだと思うかもしれませんが、現実には、シンボリックモデルは特徴計算に非常に多くの時間を費やしていたため、ニューラルネットワークを使用することで同時に高速化することができました。
どのように機能したのでしょうか。すでに単語埋め込みを見てきたので、単語表現を活用することができます。これには、特定の単語や特定の構成を見たことがなくても、類似した単語を見ていれば単語の類似性に基づいて予測できるという利点があります。しかしそれはさらに進んで、単語だけでなく品詞の分散表現も使用しました。先ほど説明したように、NLPの実際のシステムでは品詞はもっと細かく分類されており、複数形名詞と単数形名詞など、異なる記号ですが非常に似ているものもあります。これらに分散表現を与えることで、それらが互いに近いことを表現できます。
依存関係のタイプについても同様に、一部は密接に関連しているため、これらにも分散表現を与えました。
そして依存構造解析器の状態を表現するために、同じスタックとバッファを使いますが、遷移を予測する際には、スタックとバッファの重要な要素、つまりバッファの最初の要素（シフトする場合に移動する単語）とスタックの上位2つの要素（左アークまたは右アークを行う場合に組み合わせる単語）を取り出します。これらそれぞれについて、単語とその品詞の分散表現を取り、すでに構築した依存関係がある場合はその表現も取り、それらを連結して大きなベクトルを作成します。
この入力層は連結された分散表現で、それを隠れ層（WX + b、そしてReLU非線形性）に通し、その上にさらにもう1層（別の行列による乗算、W2x + b2）を置き、その出力をソフトマックスに通して、シフト、左アーク、右アーク操作のいずれかの確率分布を得ます。
このアプローチが従来の依存構造解析器よりも強力だった理由の一つは、非線形分類器を提供する深層ニューラルネットワークを持っていたことです。そのため、他の以前の遷移ベース依存構造解析器よりも正確で、基本的に知られている他の依存構造解析器と同じくらい優れていました。
10年前、これは大きな成功を収め、人々は非常に興奮しました。特にGoogle社の人々はこれに非常に興奮しました。なぜならこれは線形時間であり、効率的にウェブ全体を構文解析できる拡張可能な方法を提供したからです。
11.4. Google の SyntaxNet (Parsey McParseface) の紹介と精度向上
Googleはこのニューラル依存構造解析のアプローチに非常に興味を示し、Chen & Manningのモデルをさらに改良する研究を行いました。彼らはそのモデルを取り、より深いニューラルネットワークバージョンを作り、より大きなベクトルとより適切に調整されたハイパーパラメータを使用しました。
さらに彼らは、私が紹介した貪欲なバージョン（常に最良と思われる選択を即座に行う方式）にビームサーチを追加しました。実際には、ある程度の探索を行うことで、これらの構文解析器の精度を向上させることができます。
これらの改良により、彼らはUAS（Unlabeled Attachment Score、ラベル無し依存精度）を我々の約92%から94%、94.6%にまで引き上げました。恐らく若すぎて覚えていないかもしれませんが、2016年当時、Googleは依存構造解析器のために典型的な大規模PR活動を展開し、それは私の頭を完全に混乱させました。依存構造解析器について誰かがWiredやVenture Beatなどのテックブログで記事を書くとは思ってもみなかったからです。
しかし、Googleは「世界で最も正確な構文解析器」として、あらゆる場所でこれを宣伝しました。彼らはそれに「Parsey McParseface」という愉快な名前を付け、これが多くのメディアに取り上げられるのに非常に効果的でした。これは当時非常に成功した構文解析器でした。
この名前は、当時インターネット上で人気だった「Boaty McBoatface」というミーム（英国の極地研究船の名前を一般公募したところ、このふざけた名前が圧倒的に支持された出来事に由来）をもじったものでした。「Parsey McParseface」という名前は、SyntaxNetというGoogleの自然言語理解フレームワークの一部でした。
この取り組みは技術的な成果だけでなく、自然言語処理の技術を一般大衆にも知らせるという意味で重要でした。依存構造解析という、それまで主に研究者だけが知る専門的な話題が、突然テクノロジーニュースの一部となったのです。
12. グラフベース依存構造解析
12.1. グラフベース依存構造解析の基本概念
残り数分で、もう一つの依存構造解析手法についても紹介したいと思います。これもニューラルネットワークで実装できる強力な構文解析手法で、広く使用されています。これがグラフベース依存構造解析です。
グラフベース依存構造解析では、遷移ベースとは異なるアプローチを取ります。各単語について「私は何の依存語か」と問いかけます。例えば、「the big cat sat」という文があれば、「big」は文中の他の4つの単語（ROOTを含む）のうちどれかの依存語でなければなりません。
つまり、「big」は「the」の依存語か、「ROOT」の依存語か、「cat」の依存語か、「sat」の依存語かを判断します。それぞれの可能性にスコアを付け、最も可能性が高いのは「big」が「cat」の依存語であるという判断を下すことになります。
同様に他の各単語についても同じ作業を行います。例えば「sat」はこれらの単語のどれかの依存語であり、どの単語の依存語である可能性が最も高いかを判断します。おそらく「sat」は動詞として「ROOT」の依存語である可能性が最も高いと判断するでしょう。
このように、文の中のすべての可能な依存関係（N²の可能性）をスコア付けし、それぞれにスコアを与えます。しかし、依存関係は木構造を形成するという制約があります。つまり、サイクル（循環）がなく、文の部分が互いに切断されないようにする必要があります。
このため、最小コスト木を見つけるような最小スパニングツリーアルゴリズムを使用する必要があります。これがグラフベース依存構造解析の基本的な考え方です。
シンボリック特徴機械学習の時代でも、グラフベースの依存構造解析器は遷移ベースの依存構造解析器よりも精度が高かったのと同様に、私たちはニューラルグラフベース依存構造解析の研究も行いました。
12.2. 単語間の依存関係をスコアリングする方法
グラフベース依存構造解析では、文中のすべての可能な依存関係ペアに対してスコアを割り当てる必要があります。このスコアリングは、先ほど依存構造解析に役立つと説明した4つの要素を活用します。
まず、依存関係の両端にある単語のペアが妥当かどうかを考慮します。例えば「look in the large crate」という文では、「look in」（前置詞が動詞に依存する）や「the large」（形容詞が冠詞に依存する）、「large crate」（名詞が形容詞に依存する）などの単語ペアについて、それぞれの依存関係がどれだけ妥当かを評価します。
次に依存距離を見ます。一般的に近い単語同士の依存関係は遠い単語間の依存関係よりも可能性が高いため、距離が近いペアには高いスコアが与えられます。ただし、単に距離だけでなく、間に何があるかも重要です。
間にある要素としては、依存関係が動詞や句読点をまたぐことは稀なので、そのような場合は低いスコアになります。「the good cat sat」という文で、「the」と「sat」の間には「good」「cat」という単語があります。「the」が「sat」に直接依存する可能性は低く、その間の単語に依存する可能性の方が高いでしょう。
また、主要語の結合価も考慮します。例えば動詞は通常主語と目的語を取りますが、名詞は一般的に多くの引数を取りません。これらの傾向に基づいて、特定の品詞の単語が持つ典型的な依存関係の数と種類を考慮してスコアリングします。
これらの要素を組み合わせ、ニューラルネットワークなどの機械学習手法を使って、各ペアに対する最終的なスコアを計算します。このスコアリングシステムは、訓練データから学習され、実際の言語使用パターンを反映しています。
最終的に、すべての可能な依存関係ペアにスコアを割り当てた後、これらのスコアに基づいて最適な依存構造木を構築するアルゴリズムを適用します。これにより、文全体の最も可能性の高い構文解析が得られます。
12.3. 最小スパニングツリーアルゴリズムの適用
依存構造解析の重要な制約の一つは、出力が木構造でなければならないということです。つまり、すべての単語が何らかの主要語に依存し、循環依存がなく、すべての単語が接続されていなければなりません。しかし、単語ペアごとにスコアを計算した後、最も高いスコアの依存関係だけを選ぶと、この制約を満たさない構造が生じる可能性があります。
例えば、「the good cat sat」という文で、「the」→「cat」、「good」→「cat」、「cat」→「sat」、「sat」→「cat」という依存関係が高いスコアを持った場合、「sat」と「cat」の間に循環が生じてしまいます。これは有効な依存構造ではありません。
この問題を解決するために、グラフベース依存構造解析では最小スパニングツリーアルゴリズムを適用します。このアルゴリズムは、すべての節点（単語）を含み、循環を持たず、合計コスト（または負のスコア）が最小となる木を見つけます。依存構造解析では、通常Chu-Liu-Edmonds のアルゴリズムや Eisner のアルゴリズムが使用されます。
Chu-Liu-Edmonds のアルゴリズムは非射影的な依存構造（交差する依存関係を持つ構造）を扱うことができます。一方、Eisner のアルゴリズムは射影的な依存構造に特化しており、より効率的ですが制約が強いです。
これらのアルゴリズムは、各単語ペアのスコアを入力として取り、全体のスコアが最大（またはコストが最小）となり、かつ有効な依存構造木を形成する依存関係の集合を出力します。
最小スパニングツリーアプローチの優れた点は、文全体を一度に考慮できることです。遷移ベースの手法が各ステップで局所的な決定を行うのに対し、グラフベースの手法は大局的な最適化を行います。これにより、特に長距離依存関係の解析において優れた結果をもたらすことがあります。
12.4. ニューラルグラフベース依存構造解析の発展と性能
古くからのシンボリック構文解析の時代では、グラフベースの依存構造解析器は遷移ベースの依存構造解析器よりも精度が高かったことから、私たちはニューラルグラフベース依存構造解析の研究も行いました。
ここに示したのは、私たちのニューラルグラフベース依存構造解析器です。これはGoogle社の「世界最高の依存構造解析器」と称されたParsey McParsefaceよりも1%以上精度が高くなっています。
これによって2017年の時点に到達しましたが、明らかにこれは数年前の話です。より最新の構文解析技術に触れるには、大規模言語モデルの時代に入る必要がありますが、それは今日のトピックではありません。
このニューラルグラフベース依存構造解析器は、私たちのオープンソースの構文解析ソフトウェア「Stanza」に組み込まれています。このソフトウェアではより精度の高いアルゴリズムとしてこの手法が使用されています。
これで、統語構造、句構造と依存構造、依存構造解析について必要なすべての知識を得られたはずです。課題2に十分に取り組める準備ができたと思いますので、頑張ってください。ありがとうございました。
