Akaza のアルゴリズム

基本的なアルゴリズム

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

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

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

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

単語のコスト

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

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

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

N-Best 解の出力

統計的かな漢字変換システム Mozc において、「制約なし」と呼ばれている方法で実装されている。

この方法が一番簡単そうだったのでこれで実装している。mozc で採用されている「擬似周辺化」を採用してもよいかもしれない。

FAQ

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