Support Vector Machine による日本語係り受け解析

Presentation on theme: "Support Vector Machine による日本語係り受け解析"— Presentation transcript:

1 Support Vector Machine による日本語係り受け解析
奈良先端科学技術大学院大学 情報科学研究科 自然言語処理学講座 工藤 拓 松本裕治

2 係り受け解析 日本語の統語解析の基本技術の１つ 二文節間の係りやすさを数値化した行列を作成し，文全体を最適化する係り受け関係を導出
人手による手法から、解析済みコーパスから統計的に求める手法へ 係り受け解析は日本語の統語解析の基本技術の一つとして認識されています ここでは、その詳細は説明しませんが、簡単に説明いすると。。 ということになりますｌ。 初期の研究では、この係りやすさを人手で与えていましたが、一般的に係りうけに 必要とされる素性は莫大になるために網羅性、一貫性という点で問題がありました。 近年大規模コーパスが利用できるようになり、解析ずみコーパスから統計的に 係りやすさを推定する手法が主流となりつつあります。

3 文節 i, j の言語的特徴を示すｎ次元素性ベクトル
統計的係り受け解析 入力文節列 係り先パターン列 文節 i, j の言語的特徴を示すｎ次元素性ベクトル 次に統計的かかりうけ解析について簡単に説明いたします。 かかりうけ解析とは、ｍ個の入力文節列 B があり、それに対汁係さきパターン列 D を求めることにあります。 ここで Dep（I）とはI番目の文節の係り先の文節番号を示します。 統計的係うけ解析とは、入力文節列にたいし、もっともゆうどの高い係りうけパターン列 Dをもとめることです。 また、文節I、Jが持つ言語的特徴をあらわすｎ次元ベクトルFを素性ベクトルといい、 統計的なわくぐみでは、この素性をてがかりに係り先のゆうどをもとめます。 さらにすべての係り関係が独立であると仮定するならば、文全体の 係りうけ確率は、この式のように 素性ベクトルが与えられたうえでの条件つき確率の積であらわされます。 このように統計的係うけ解析は、 素性集合Fの選択 確率モデルPの推定方法 という２つの大きなわくぐみでこうせいされることになります。 係り関係がすべて独立だと仮定

4 従来手法の問題点(1) 慎重な素性選択が必要 多くの素性を使用すると過学習してしまう 最適な素性集合の選択は試行錯誤や人手に頼っている
従来手法の問題点として、以下のようなものがあります。 まず、素性集合 Fについて。。。 多くの。。。（スライド） かといって少ない素性だと学習できなかったりします。 つまり。。。（スライド）

5 従来手法の問題点(2) 各素性の組み合わせ（共起，依存関係）を効率よく 学習できない 共起選択の方法はさまざま，人手により発見的に選択
各素性の組み合わせ（共起，依存関係）を効率よく 学習できない 共起選択の方法はさまざま，人手により発見的に選択 細かな依存関係を見ると… データスパースネス，計算量増加，過学習 例

6 Support Vector Machine（1）
V.Vapnik 95 入力素性数に依存しない汎化能力を持ち過学習しにくい 計算量をほとんど変えることなく，素性どうしの組み合わせ（共起，依存関係）を含めた学習が可能 一方SVMは、この２つの問題を解決できる能力を備えています。 まず、（すらいど） 現在しられている学習あるごりずむの中でもっとも汎か能力、過学習しにくいということが いろんな分野に応用されて報告されてきています。 NL業界では、文書分類に応用され、文書分類は文書に含まれる単語を素性とするわけですが、 その素性を増やしても精度は低下するどころか向上していったと報告されています。 決定木の場合は、あるところにピークがあり、それ以上ふやすと過学習してしまい、精度が低下してしまいます。 さらに、（スライド） 実際この２つの性質も含めて次にSVMの概略を説明していきたいと思います。

7 SVM(2) 線形２値（正例，負例）分類器，Euclid空間上の平面で分離 正例，負例，その他(マージン領域），の３つの領域に分割
SVMはこの空間を、線形ーーーで、Wx＋ｂ＝０というEucilid空間上の平面で事例を分離します。 分離する前に、事例を、せいれいふれい、そのたの３つの領域に分割します。 すべてのせいれいが、－－－の領域にはいるように、また すべてのふれいが、－－－－の領域にはいるように分割します。 この２つをまとめると、このようになります。 このどれにもぞくさない領域がその他（マージン領域）となります

8 SVM(3) マージン d を最大にするためには ||w|| を最小にすればよい マージンdが最大となる識別平面
式ではつかみにくいので、２次元平面じょうで考えてみましょう。 このようにせいれい と不例があり、ーーー の領域にすべてのせいれいが、 ーーーの領域にすべての不例が配置されるように分割します。 この太線が分離平面となります。 このような、領域の分割方法ってのは、たくさんあって、たとえばこういうのとか こういうのとか、無数に存在します。このなかでどれが精度よく分離できるのでしょうか？ 直感的には、このようにあるデータにひっぱられることなく、できるだけ真ん中をとおるような 直線できれば精度よく分離できるのではないかと考えられます。このようにあるデータのみにひっぱられている 状態は、まさしくかがくしゅうの状態にあります。 できるだけ真ん中を定量的にはどういことかというと、マージンｄが最大になるような識別平面をつくること になります。 実際に、ｄを計算すると。。。のようになり、。。となります つまり、スライド このマージン最大化の戦略は、入力時減数に依存しない汎か能力をもつことが 実際に証明されており、汎か能力という点では現在しられているアルゴリズムのなかでは 最適だと考えられています。 マージン d を最大にするためには ||w|| を最小にすればよい

9 SVM(4) 以下の制約付き多項式の最適化問題に帰着 最小化： 制約条件： Lagrange乗数 αを導入して双対問題に変換 最大化：
つまり、このような、、に帰着されます。 これを実際の詳細な証明ははぶきますが、 。。。 に変換すると。。。 のようになります。 最終的な識別関数は、。。。 のようになります。 Ｓｇｎとは、正の値のとき、１を、負の値のときにー１をかえす関数のことをいいます。 最終的な識別関数

10 Kernel関数(1) 線形分離できない場合 各素性をの組み合わせを展開し，より高次元の素性ベクトル 空間に射影すれば線形分離しやすくなる
2 3 4 5 6 7 1 2 4 5 6 7 1,2 1,3 1,4 1,5 1,6 1,7 2,3 2,4 2,5 さて、ないーぶなSVM は線形分離しかあつかえませんでした。 しかし、実際の分離問題は、線形分離できない場合がほとんどで、線形分離できない問題を 対処できないと使いものになりません。 SVMの理論じたいは、１９６０年代からあったのですが、線形分離できない問題を 解決する手法が提案され、SVMぐーんとその能力とか、知名度をあげることとなりました。 一般に線形分離できない場合は、。。。 です。 たとえば、ｎ個の学習サンプルがあるばあいは、２＾ｎ次元の素性ベクトルをあたえれば かならず線形分離できます。 たとえば、７次元のベクトルがあります。これの2個、3個の組み合わせを考慮して このように、射影関数Φをつかって、高次元な空間に射影することを考えます。 こうすると、線形分離しやすくなります。 しかし、・。・（スライド）

11 Kernel関数(2) K: Kernel関数 学習： 識別関数: 学習、識別は素性ベクトルの内積のみに依存した形
Φを経由せずに簡単な演算で直接内積を計算できれば 計算量を大幅に減らすことが可能 K: Kernel関数 さてここで、学習と識別関数の式に戻って考えてみましょう。 Φによって射影されたわけですから、この部分がΦにおきかわります。 ここで、よーくこの式をながめていると、これらは素性ベクトルのない積 しか使っていません。 となると、スライド。。。 このような簡単な演算をあらわす関数のことをかーねる関数といいます。 つまり、かーねる関数をつかうとない積はこのようになります。

12 Kernel関数(3) 例 d次のPolynomial関数 2次元を6次元の空間へ写像，組み合わせの項も追加される
例として、かーねる関数のなかでもっともよくつかわれるｄじの。。関数をみてみましょう ここでは、さらに簡略かして、ｄ＝２、素性ベクトルは２次元だと仮定します。 これを、カーネル関数に代入すると。。。のように展開ｓあれ、 つまり射影関数は、。。。 のような 2次元を６次元の空間に射影するような関数になります。 ここで注目すべきは、ここの組み合わせの項が追加されたことです。 一般に、ｄ時の。。関数は、ｄ個までのすべての組み合わせを考慮した学習もでるとなります。 2次元を6次元の空間へ写像，組み合わせの項も追加される d次のPolynomial関数はd個までの組み合わせを含めた学習

13 SVM（まとめ） 入力素性数に依存しない汎化能力を持ち過学習しにくい 計算量をほとんど変えることなく素性どうしの組み合わせを含めた学習が可能
マージン最大化 計算量をほとんど変えることなく素性どうしの組み合わせを含めた学習が可能 Kernel関数 d個までの素性の組み合わせを考慮しながらその中で汎化能力を最大にする戦略 Smoothingの効果が期待できる SVMをまとめてみます、 最初に従来手法にくらべて２つの優位な点があると述べました。 まず。。。 この背景にあるのは。 これらをまとめると、ｄ個の素性の。。。。戦略であるといえます。 これは、すむーじんぐの効果があるのではないかと期待できます。

14 SVMによる係り受け解析（1） 正例，負例の与え方 係った事例 → 正例 学習データ中の 全係り受け候補 係らなかった事例 → 負例
係った事例 → 正例 学習データ中の 全係り受け候補 係らなかった事例 → 負例 さて、SVMの説明はここでおわりにして、実際に係りうけ解析にどう応用するのかのべたいとおもいます。 まず、２値分類きなんで、せいれいふれいをきめるひつようがあります。 われわれは、非常に簡単、であたりまえの手法を使いました つまり。。 式でかくと、となります。

15 SVMによる係り受け解析（2） 係り受け確率 （Sigmoid関数）
厳密には確率値ではない，距離を確率値に正規化，Sigmoid関数は確率へのよい近似を与えることが実験的に示されている （J.Platt 99） 従来からある確率モデルの枠組で解析 関根99の文末からビームサーチを行う解析手法を採用 次に、係りうけ確率ですが、これは、SVMの識別関数の 距離部分を しぐもいど関数に入力したような形にしました。 一般に０を境に大きな値をとればとるほどかかりやすくなり ちいさな値になればなるほどかかりにくくなります。 その値の幅はまいなすむげんだいからぷらすむげんだいとなります。 つまり、これは距離を確率のあたいに正規かしてるだけにすぎず、厳密には確率値ではありません。 われわれは、。。。 のためにこの手法を採用しました。 また、確率が決定されると、実際のぱーじんぐとなるわけですが、一般にはCYKのような ぼとむあっぷぱーざを用いて解析します。われわれは、日本語のかかりうけかいせきに とっかした、関根９９の手法を実際に採用しました。これは文末から上位ｋ個のビームはばおを もたせながらビームサーチを行う手法です。

16 静的素性と動的素性 静的素性 動的素性 2文節の主辞の語彙，品詞，2文節間距離など 文節まとめあげの段階で決定される ?
私は |この本を | 持っている| 女性を | 探している。 ? 「探している」の素性として「女性を」を追加 二重 を格 の可能性が取り除かれる 素性にかんしてはいままで一切ふれてきませんでしたが、 従来手法で有効なものをしようする枠組みで、素性選択の最適化は あまり年頭にいれていません。それは、純粋にSVMの能力を 調べたかったと理由があります。 しかし、従来とはまったく違う視点の素性を導入してみました。 従来からある手法は、すべて静的素性とよばれるものです。 これは（スライド）のような素性です。日本語のかかりうけかいせきは末尾の 活用形などでそのおおくのかかりうけさきを決定できるんですが、 複数候補があったときどちらが優先されるか決定したがいときがあります。 たとえばこの例文のとき、この本は （スライド） わかりません。 それはどうしてかというと、静的素性はあくまで２文節の情報しかみてないからです。 そこで、探しているという文節は、女性をという文節に修飾されてるわけだから、 これを探しているの素性とし動的に追加します。 これで、探しているはすでに「を」かくで修飾されることになり、日本語のばあい２じゅうの 表層各をとることはまれなんで、このほんは、もっているにしかかからないことがわかります。 また、２じゅうの表層各をとることはまれといいましたが、これは、逆にかんがえると、 ２じゅうのひょうそうかくを取る可能性のある並列構造の解析にも有効ではないかと考えられます。 つまり、係り関係そのもを素性としてかんがえ、解析しながら動的に追加していきます。 このような素性のことを動的素性とよぶことにします。 で、実際解析する文には、係りうけかんけいが付与されてないために、動的素性を観察することはできないんですが、 解析しながら追加していけばよく、動的素性をふくめてビームサーチを行えば解析できます。 動的素性 係り関係そのもの，解析しながら動的に追加 動的素性も含めてビームサーチ

17 実験環境，設定（1） 京都大学テキストコーパスVersion2.0の一部 評価方法 学習データ 1月1日－8日 7958文
テストデータ 1月9日 1246文 内元98と同じ学習データ，テストデータ Kernel関数は，Polynomial関数，次元数 d=3 Beam幅 k=5 評価方法 係り受け正解率 文末から2番目の評価含める (A) デフォルト， 含めない（B） 文正解率 さて、実際のタグ付きコーパスを用いて実験を行ってみました。 ここにその環境設定を示します。 まず・。。。。

18 実験環境，設定（2） 静的 素性 係り元/ 係り先 文節 主辞（見出し，品詞，品詞細分類， 活用，活用形）
主辞（見出し，品詞，品詞細分類， 活用，活用形） 語形（見出し，品詞，品詞細分類，活用，活用形） 括弧，句読点，文節位置 文節間 距離（1，2-5，6），助詞，括弧， 句読点 動的 2文節間にある文節で，後ろの文節に 係る文節の語形見出し 次にしようした素性を示します。 静的素性にかんしては、内本９９の素性そのままで、唯一追加したといえば、この文節位置ぐらいでしょうか、 注意していただきたいのは、ここで使われている主事と語形ということばなんですが、 主事というのは、、、でごけいとは、、、のことを示します これはもちろん一般的な定義ではなく、便宜的な名前にすぎません。 さらに、動的素性としては、（スライド）を使いました、 先ほどの 例だと この本を 探している の間にふくまれる女性を の語形 「を」が動的素性にあたります。

19 実験結果（1）（d=3，k=5）

20 実験結果（2）（d=3，k=5）

21 動的素性の効果（d=3，k=5）

22 Kernel関数と解析精度

23 ビーム幅と解析精度

24 関連研究との比較 内元98との比較 最大エントロピー法に基づくモデル 87.2%の精度 （本手法は89.1%）
87.2%の精度 （本手法は89.1%） 素性の組み合わせ（共起，依存関係）の重要性を指摘しているが，組み合わせは，人手により発見的に 選択，有効な組み合わせを網羅できない 本手法はKernel関数の変更のみ， 網羅性， 一貫性という意味で優位

25 全係り受け関係を用いるため，多くの計算量が必要
今後の課題 全係り受け関係を用いるため，多くの計算量が必要 すべての候補から分類に必要な事例を選択 学習の効率化，解析の高速化 明らかに係らない制約を（人手により）導入 他の計算コストの少ないモデルとの融合 誤り駆動型による素性選択

26 まとめ 7958文という非常に少量のデータにもかかわらず，89.1％の高い精度を示す
SVMの持つ，高次元の入力に対して過学習しにくいという性質を裏付ける結果 係り受け解析は各素性の組み合わせ（共起，依存関係）が重要，SVMはKern el関数を使うことで効率性，網羅性，一貫性で優位