小町守（NAIST） 森信介（京大）・徳永拓之（PFI） 第一回入力メソッドワークショップ 2008年12月28日（日）@京都大学 統計的かな漢字変換 ChaIME 小町守（NAIST） 森信介（京大）・徳永拓之（PFI） 第一回入力メソッドワークショップ 2008年12月28日（日）@京都大学

自己紹介:小町守 奈良先端科学技術大学院大学 インターン（共同研究）先: 自然言語処理学講座（松本研）D2 ChaSen, MeCab, Namazu の研究室 インターン（共同研究）先: NTT（3年前-今年）, Microsoft Research（去年）, Yahoo! Japan 研究所（今年-来年） （少し前まで）Gentoo Linux 開発者、東大 Fink チーム開発者 Id:mamoruk 「生駒日記」

かな漢字変換開発の動機 Webの拡大→ユーザ入力文書増大 新しくなって本当に使いづらい・・・前に戻してもらいたいです。慣れれなのかな〜 新語や新表現の変換はストレスフル 新しくなって本当に使いづらい・・・前に戻してもらいたいです。慣れれなのかな〜 どぅゃら､風邪をひぃてしまぃました｡ 頭重ぃし､鼻水がｽﾞｰﾙｽﾞﾙ… でも仕事休めなぃしｰ ｶﾗﾀﾞだるぃしｰ もぅ嫌ｬｰｯ!!! ねぇよ こどもやばす ｗｗｗｗｗｗｗｗｗｗ 天丼ｗｗ おいおい かあいいｗｗ ちょｗｗ...

かな漢字変換開発の背景 Web データを処理したいがタグつきデータ・辞書がな い（特にフリーで使えるもの） NAIST-jdic （旧 IPADic） Google日本語Nグラム 辞書やコーパスに正しく情報（品詞・単語境界）振るの は（一般の人には）難しい （できるだけ）品詞情報を用いないで処理したい 自然言語処理における文節とIMEにおける文節の違い（eg. 東京特許許可局）

統計的かな漢字変換開発の目的 大規模コーパスの利用 統計的な理屈づけ 品詞情報を用いない頑健なかな漢字変換 できるだけ人手をかけないでメンテナンス Google 日本語 N グラム Webコーパス5億文 Wikipedia・etc… 統計的な理屈づけ 品詞情報を用いない頑健なかな漢字変換 Web に出現する全単語を用いる→凝った未知語処理はしな い

ヒューリスティックなかな漢字変換 ルールによる変換 N文節最長一致法 接続コスト最小法 Canna 要言語学（国語学）的知識 必ずしも精度よく変換できるとはかぎらない N文節最長一致法 （昔の）ATOK, VJE, Wnn など 要人手によるパラメータチューニング 接続コスト最小法 WXG, （少し前までの）MS-IME など 要人手による辞書チューニング

接続コスト最小法 コストが一番低いパスを選ぶ →コストは辞書に書いてある（人手） に ワニ は に わ 鶏 二 わ に 歯 二 羽 庭 煮 入力: にわにはにわにわとりがいる。 に ワニ は に わ 鶏 100 10 10 15 10 10 30 40 30 40 二 わ に 歯 二 羽 庭 100 10 10 30 10 25 10 20 20 煮 羽 二 葉 120 煮 輪 に 10 10 20 20 10 15 20 20 85 10 50 10 似 輪 煮 刃 庭 二 30 20 20 35 20 10 20 庭 90 似 埴輪 似 40 70 20 30 80 30 コストが一番低いパスを選ぶ →コストは辞書に書いてある（人手）

× 統計的かな漢字変換 かな漢字モデル 言語モデル 森ら（1998）の提案 P(x|y) の降順に変換可能文字列 (x1, x2, …) を提 示する x: 文, y: 入力 MS-IME 2007, ATOK 2008が統計的手法を採用 かな漢字モデル × 言語モデル によるランキング

統計的接続コスト最小法 かな漢字モデル 言語モデル 接続コスト最小法の自然な拡張になっている に ワニ は に わ 鶏 二 わ に 歯 二 100 10 10 15 10 10 30 40 30 40 二 わ に 歯 二 羽 庭 100 10 10 30 10 25 10 20 20 煮 羽 二 葉 120 煮 輪 に 10 10 20 20 10 15 20 20 85 10 50 10 似 輪 煮 刃 庭 二 30 20 20 35 20 10 20 庭 90 似 埴輪 似 40 70 20 30 80 30 接続コスト最小法の自然な拡張になっている

確率的言語モデル 我が輩 は 猫 である 文頭 文末 文を単語列 と見なすngram言語モデ ル（i<1は文頭、i=h+1は文末） 日本語っぽい単語列の確率は高く、 日本語っぽくない単語列の確率は低く 文を単語列　　　　　　　　　　と見なすngram言語モデ ル（i<1は文頭、i=h+1は文末） Google 日本語Nグラムデータ（200億文）から表記 の1-2グラムを計算して使用 異なり1グラム数:250万 異なり2グラム数:8,000万 我が輩 は 猫 である 文頭 文末

確率的かな漢字モデル 確率は読みが振られたコーパスから最尤推定 毎日新聞95年分1年に MeCab で分かち書き・読 みを付与して使用 出現する単語の読みは なんだったか推定するモデル 確率は読みが振られたコーパスから最尤推定 毎日新聞95年分1年に MeCab で分かち書き・読 みを付与して使用 コーパス 中の頻度 かつあき こくめい 克明 小野克明さん（43） 克明なやりとりが判明

規則ベースと統計的手法の比較 規則ベース 統計的手法 なにをやっているのかはっきり分かる 柔軟な前処理・後処理 問題が簡単なときは規則ベースで書き尽くすこともできる アドホックなヒューリスティック（要言語学的直観） 「必殺パラメータ」 統計的手法 数学的モデルに基づいた理論的根拠 変換規則や辞書に当たる知識を自動で学習（人手不要） なにやっているのかよく分からない コーパスに激しく依存 変化の微調整が難しい

デモ http://cl.naist.jp/~mamoru-k/chaime/

サンプル変換 ChaIME ＡＴＯＫ 2007 Anthy 9100c AjaxIME 請求書の支払日時 請求書の市は来日時 請求書の支払い日時 請求書の支払いに知事 近く市場調査を行う。 知覚し冗長さを行う。 その後サイト内で その五歳都内で その後再都内で 去年に比べ高い水準だ。 去年に比べた海水順だ。 去年に比べたかい水準だ。 昼イチまでに書類作っといて。 昼一までに書類津くっといて。 昼一までに書類作っといて。 肥留市までに書類作っといて。 そんな話信じっこないよね。 そんな話心十個内よね。 そんなはな視診時っこないよね。 そんな話神事っ子ないよね。 初めっからもってけばいいのに。 恥メッカら持って毛羽いいのに。 恥メッカ羅持ってケバ飯野に。 始っから持ってけば良いのに。 熱々の肉まんにぱくついた。 熱々の肉まん二泊着いた。 あつあつの肉まん２泊付いた。 熱熱の肉まんにぱくついた。

関連ソフトウェア（１） Anthy http://anthy.sourceforge.jp/ HMM → MEMM による識別モデル（の亜種） 文節分割された読みつきコーパスから学習 表記の素性を用いていない 文法体系が難しい（文節・品詞の判断） Social IME http://social-ime.com/ 複数人による辞書共有機能 アルゴリズムは Anthy と同じ

関連ソフトウェア（２） AjaxIME http://ajaxime.chasen.org/ MeCab-skkserv による連文節かな漢字変換 読みが振られたコーパスから変換コストを推定 コーパスが小さい・素性がスパース Sumibi http://www.sumibi.org/ 単語分かち書きによるかな漢字変換 生コーパスから連接コストを推定（言語モデル） 辞書にない単語の変換ができない 連文節変換ではない

まとめ 統計に基づくかな漢字変換エンジンを開発している 統計的かな漢字変換は、規則ベースに比べ、 Google 日本語 N グラム・新聞記事を用いた実装・デモを公 開中 ソースコードは Google Code にある（動かすには Google 日本語 N グラムかそれに相当するデータが必要） 統計的かな漢字変換は、規則ベースに比べ、 数学的根拠がある 大規模なデータから辞書・パラメータを自動推定できる なにをやっているのかよく分からない コーパスに依存する（「コーパスの品格」） 細かい調整ができない

問題点 単語2グラムでは出現しない単語の組み合わせも大 量にある →Exchange アルゴリズムを用いて単語クラスタリ ング クラスタリングによる精度向上 →モデルサイズの圧縮にもつながる →Exchange アルゴリズムを用いて単語クラスタリ ング

Exchange アルゴリズム 単語を尤度最大になるクラスタに移動 アメリカ 600 300 太郎 ひよこ ロシア オオカミ うさぎ 単語 辞書 日本語 300 仏蘭西 次郎 キーボード まどか マウス 愛子 太郎 200 1000

Exchange アルゴリズム（2） それ以上クラスタの変動がなくなれば終了 アメリカ 仏蘭西 オオカミ ひよこ ロシア うさぎ 単語 辞書 日本語 キーボード 次郎 まどか マウス 愛子 太郎

Exchange アルゴリズムを Hadoop 単語辞書を分割して実行 アメリカ 仏蘭西 キーボード オオカミ ひよこ うさぎ 日本語 黒板 芋 単語 辞書 ロシア マウス まどか 次郎 愛子 太郎

今後の予定 クラスタ2グラムを動かす 変換ログを用いた変換候補のリランキング 1万語で1時間程度 O(反復回数*単語数*(2グラム数 + クラスタ数)) 変換ログを用いた変換候補のリランキング