自然言語処理勉強結果「ビタビアルゴリズム」

自然言語処理学習結果

前回までで、形態素解析に必要な項目のうち、
ラティス構造を求めて、
コストを推定するところまで来た。

あとは、そのコストが最小となる経路を
どうやって見つけるかだけが残っている。

今回は、その最小コストとなる経路を求める
アルゴリズム
の一つである
ビタビアルゴリズムを解説しよう。

これができれば、ようやく形態素解析が可能となる。

なお、本講座は以下の本を参考に進めている。

もしよかったら、中身を覗いてみて欲しい。

Javaで学ぶ自然言語処理と機械学習 | 徹, 杉本, 志乃, 岩下 |本 | 通販 | Amazon
Amazonで徹, 杉本, 志乃, 岩下のJavaで学ぶ自然言語処理と機械学習。アマゾンならポイント還元本が多数。徹, 杉本, 志乃, 岩下作品ほか、お急ぎ便対象商品は当日お届けも可能。またJavaで学ぶ自然言語処理と機械学習もアマゾン配送商品なら通常配送無料。
スポンサーリンク

ビタビアルゴリズム

ビタビアルゴリズムとは

上でも紹介した通り、
単語コストと接続コストが付与されたラティス構造上で、
コストが最小の経路を求めるアルゴリズムの一つが、
このビタビアルゴリズムだ。

これは、動的計画法と呼ばれる
アルゴリズムの一種になる。

ラティス構造内の各頂点(=形態素)\(w\)に対して、
文頭からその頂点までの経路の合計コスト最小値
実際の経路を求めながら、次に進んでいくというもの。

わりと直感的でわかりやすいと思う。

ある形態素\(w\)までのコスト最小値を\(C(w)\)とし、
その一個前の形態素を\(w’\)とする。

このとき、その単語までの最小コスト\(C(w)\)は、
以下の式で求めることができる。

$$C(w) = \min_{w’}\{C(w’) + cost(w’, w)\} + cost(w)$$

要するに、その手前までのコストと接続コストの和
最小となるものに、自身の単語コストを足せばいい。

これで最後まで求めていき、
最後にコストが最小となった経路を辿れば、
それが形態素解析の結果となる。

ビタビアルゴリズム具体例

では、具体例を見ていこう。

前回と同じく、
「日本を出発する」という文で見ていこう。

先に、ラティス構造を再掲しておく。

こんな感じだった。

ここで、コストが以下のように付与されたとしよう。

では、先頭から順番に見ていこう。

まず、「日本」について。

直前は経路しかないので、
単純に足して1+7、\(C(\)日本\() = 8\)だ。

また、「日」も同じで\(C(\)日\() = 9\)となる。

次に、「本(名詞)」、「本(接尾)」も
同じように考えられる。

一つ前の単語が「日」のみで、
そのコストが9だった。

それと頂点間のコスト、自身のコストを足すので、
\(C(\)本(名詞)\() = 9 + 3 + 10 = 22\)、
\(C(\)本(接尾)\() = 9 + 3 + 8 = 20\)だ。

では、次の「を」を見ていこう。

まず、ここまでには三つの経路がある。

直前が「日本」、「本(名詞)」、「本(接尾)」
となっているルートだ。

このとき、それぞれの頂点までのコストと、
「を」との接続コストを足してみる。

  • 日本:8 + 1 = 9
  • 本(名詞):22 + 1 = 23
  • 本(接尾):20 + 1 = 22

この中で最小のもの
「を」の単語コストを足したものが、
ここまでの最小経路となる。

明らかに「日本」が一番小さい。

というわけで、9に「を」の単語コスト3を足して、
\(C(\)を\() = 9 + 3 = 12\)となるのだ。

当然、経路も
「文頭」→「日本」→「を」となっている。

これをあとはひたすら繰り返すだけ。

残りの計算は皆さんの手にゆだねて、
ここでは結果だけ紹介する。

最短となる経路は、
「文頭」→「日本」→「を」→「出発」→「する」→「文末」
という流れで、最終的なコストは36となるはずだ。

以上から、この文の形態素解析の結果は、

日本 | を | 出発 | する

となるのだ。

おわりに

書いてから、前回に含めてもよかったのでは?
と思いつつあるが…まあ気にしない。

というわけで、これで形態素解析ができるようになった。

とはいえ、実際にはこのあたりの計算は
ツールで行ってくれる。

その中で、こういうことをしてるんだなぁという
認識でいてもらえればいいだろう。

さて、次回は移り変わって
係り受け解析で同じように解説…ではない

係り受け解析は、本では
機械学習を使う場合が多いよという記述しかなかった。

そのため、詳しく解説する内容がない。

なので、そこをすっ飛ばして、
ついに意味理解に進んでいこう。

これまでは構造を云々の話だったのが、
ようやくその文章が表現する意味に入っていく。

ここからが面白くなってきそうで、
個人的にも楽しみだ。

コメント

タイトルとURLをコピーしました