前回までで、形態素解析に必要な項目のうち、
ラティス構造を求めて、
コストを推定するところまで来た。
あとは、そのコストが最小となる経路を
どうやって見つけるかだけが残っている。
今回は、その最小コストとなる経路を求める
アルゴリズムの一つである
ビタビアルゴリズムを解説しよう。
これができれば、ようやく形態素解析が可能となる。
なお、本講座は以下の本を参考に進めている。
もしよかったら、中身を覗いてみて欲しい。
ビタビアルゴリズム
ビタビアルゴリズムとは
上でも紹介した通り、
単語コストと接続コストが付与されたラティス構造上で、
コストが最小の経路を求めるアルゴリズムの一つが、
このビタビアルゴリズムだ。
これは、動的計画法と呼ばれる
アルゴリズムの一種になる。
ラティス構造内の各頂点(=形態素)\(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となるはずだ。
以上から、この文の形態素解析の結果は、
日本 | を | 出発 | するとなるのだ。
おわりに
書いてから、前回に含めてもよかったのでは？
と思いつつあるが…まあ気にしない。
というわけで、これで形態素解析ができるようになった。
とはいえ、実際にはこのあたりの計算は
ツールで行ってくれる。
その中で、こういうことをしてるんだなぁという
認識でいてもらえればいいだろう。
さて、次回は移り変わって
係り受け解析で同じように解説…ではない。
係り受け解析は、本では
機械学習を使う場合が多いよという記述しかなかった。
そのため、詳しく解説する内容がない。
なので、そこをすっ飛ばして、
ついに意味理解に進んでいこう。
これまでは構造を云々の話だったのが、
ようやくその文章が表現する意味に入っていく。
ここからが面白くなってきそうで、
個人的にも楽しみだ。
コメント