MeCabのコスト計算について

#はじめに
MeCabのコスト計算について勉強したのでまとめてみました。
どこか間違っていたらご指摘ください。

#MeCabの形態素解析の概要
MeCabは登録された辞書を使って形態素解析を行います。もし辞書に登録されていない単語（未知語）が出た場合、各単語のコストに基づいて分割します。そのなかで総コストが最小のものを結果として出力します。

#実際にやってみる
今回はipadic-neologd辞書を用いて、架空の単語「アメリカドイツ村」がどのように形態素解析されるか確認します。

echo アメリカドイツ村|mecab -d C:\neologd -N2

アメリカ        名詞,固有名詞,地域,国,*,*,アメリカ,アメリカ,アメリカ
ドイツ  名詞,固有名詞,地域,国,*,*,ドイツ,ドイツ,ドイツ
村      名詞,接尾,地域,*,*,*,村,ムラ,ムラ
EOS

アメリカ        名詞,固有名詞,地域,国,*,*,アメリカ,アメリカ,アメリカ
ドイツ村        名詞,固有名詞,一般,*,*,*,ドイツ村,ドイツムラ,ドイツムラ
EOS

-dで辞書を指定し、NUMオプションで指定した数だけ候補を挙げます。
このように未知語に対して2種類の分け方が候補に挙がりました。この分け方は私たちにとっても、かなり納得のいくものではないでしょうか。

#MeCabの辞書
コストの計算に入る前に、MeCab辞書の登録方法について説明します。
辞書は、

表層形,左文脈ID,右文脈ID,コスト,品詞,品詞細分類1,品詞細分類2,品詞細分類3,活用形,活用型,原形,読み,発音

という形でcsvファイルとして保存してから辞書をビルドします。これをみると、
・ 左文脈ID
・ 右文脈ID
・ コスト
という見慣れない言葉が含まれています。これらがMeCabの形態素解析に用いられる情報になります。

生起コスト

生起コストとは、ある単語自体の現れにくさです。値が高いほどその単語は現れにくくなります。生起コストは先ほど登録した辞書のコストの値です。それでは「アメリカドイツ村」はどのような生起コストになったのでしょうか？

echo アメリカドイツ村|mecab -F "%m,%c,\n" -d C:\neologd -N2

アメリカ, 4698,
ドイツ, 2543,
村, 8707,
EOS

アメリカ, 4698,
ドイツ村, 611,
EOS

%mで表層形、%cで生起コストを表示させます。
ここで一つの疑問が生まれます。総コストは明らかに2つ目の方が小さいはずなのに、出力第一候補は1つ目の結果になっています。その理由は新たなコスト、連接コストの存在にあります。

#連接コスト
連接コストとは、2つの単語の文脈IDの連続しにくさです。値が小さいほど連続する可能性が高くなります。文脈IDは辞書の左文脈IDと右文脈IDに当たります。基本的にこのIDは登録時には同じ値になっていると思われます。例えば「前後」という単語を考えます。
「前」の文脈IDは1314,「後」の文脈IDは1313です。連接コストは左文脈IDと右文脈IDの組み合わせで決められます。
組み合わせの一覧はMeCab\dic\ipadicにあるmatrix.def(またはmatrix.bin)にあります。これを見ると、

1314 1313 -316
1313 1314 716

前→後は連接コストが低い(-316)ため連続しやすく、後→前だと連接コストが高く(716)連続しにくいという結果が得られました。これも割と納得できるかと思います。
それでは「アメリカドイツ村」についても見てみましょう.

echo アメリカドイツ村|mecab  -F"%m,%phl,%phr,%c,%pc,%pn\n" -d C:\neologd -N2

アメリカ,1294,1294,4698,3746,3746
ドイツ,1294,1294,2543,-141,-3887
村,1303,1303,8707,881,1022
EOS

アメリカ,1294,1294,4698,3746,3746
ドイツ村,1288,1288,611,2614,-1132
EOS

MeCabコマンドをまとめると以下のようになります。

コマンド	説明
%m	表層形
%phl	左文脈ID
%phr	右文脈ID
%c(または%pw)	生起コスト
%pc	連接コスト+単語生起コスト(文頭から累積)
%pn	連接コスト+単語生起コスト(その形態素単独, %pw+%pC)
全てのコマンドはこちらに記載されています。
出力がわかりにくいのでこれも表にしてみます。

表層形	左文脈ID	右文脈ID	生起コスト	連接＋生起(累積)	連接+生起(単独)
アメリカ	1294	1294	4698	3746	3746
ドイツ	1294	1294	2543	-141	-3887
村	1303	1303	8707	881	1022
アメリカ	1294	1294	4698	3746	3746
ドイツ村	1288	1288	611	2614	-1132
ここで注意していただきたいのは、BOSとEOSにも文脈IDが付与されているということです。なので、1つ目の「アメリカ」の連接コストはmatrix.defより

0 1294 -952

となります。そのため、累積コストは4698-952=3746となります。
次に「ドイツ」を見てみましょう。左右の文脈IDが1294で連接コストは-6430とかなり小さくなります。(確かに国名が連続して続くのは珍しい...)
累積コストは(3746+2543)-6430=-141で、単独の場合は2543-6430=-3887で、計算と一致しました。
また、出力はされていませんが、EOSにも文脈IDがあるため最終チェックを行います。
文脈ID1303→0の連接コストは5、文脈ID1288→0は-919で累積コストを比べると、886と1695で1つ目の方が最小コストなので、先ほどの謎が解明できました。

#参考
MeCabのコスト計算を理解する。
日本テレビ東京で学ぶMeCabのコスト計算
日本語形態素解析の裏側を覗く！MeCab はどのように形態素解析しているか