Akaza のアルゴリズム

基本的なアルゴリズム

Akaza のビタビアルゴリズムでは、現在、単語2グラムを採用しています。

• かな漢字変換辞書を元にトライ構造を作って用意しておく。
• ローマ字で入力された文字列をもとに、平仮名に変換する。
• 共通接頭辞検索をして、平仮名ベースのグラフ構造を構築する。
• それぞれのノードごとに漢字表現とシステム辞書からword_id、システムノードスコア、ユーザーノードスコアを得て surface lattice を構築する。
• ラティス構造をビタビアルゴリズムで最適解を求める。
• 前方から後方へノードコストとエッジコストを求めながら探索する。後方から前方へ、一番コストが高いノードを辿る。途中で他の変換候補も収集する。

基本的なコスト計算の考え方

akaza ではビタビアルゴリズムで、コスト計算を行って、一番コストの低い経路を正解としている。

単語のコスト

日本語 wikipedia および青空文庫のデータをもとに形態素解析して単語ごとの統計情報を得ている。

コストの計算は -log10((その単語の出現回数 + alpha) / (文書郡に出現している単語のユニーク数 + 総単語出現数 * alpha)) である。 ここで、alpha は 0.00001 としている。

ユーザー辞書のコストも同じ形で計算されている。ではなぜユーザー辞書の学習結果のほうが優先されるかというと、wikipedia の全文書にくらべると普通のユーザーは語彙がすくないので、コスト計算の分母が小さくなって、コスト値が大きく出るということです。

デフォルトコスト

漢字など、読み仮名よりも短くなるものは -log10(1e-20)=20.0。 かなそのものなど、読み仮名と同じ長さのものは -log10(1e-19)=19.0 と設定されている。 これは、「かな漢字辞書」に登録されているが言語モデルに登録されていない単語がある場合､「かな」を出すよりも体験が良いだろうということでそうしている。

ちなみに、なぜこの数字なのかは、なんらかの根拠があった気がする。が、思い出せない。

FAQ

• なぜ品詞Nグラムを使わないのですか?
  • → 品詞を扱うのは大変そうだったので単語2グラムで実装してみたら、それでわりと精度が出るし、そこまで容量もくわないのでいいかなぁ、と。
• なぜ前向きDP後ろ向きA*をしないのですか?
  • → まだ実装してないというだけです。