最近仕事の行き帰り、片道自転車が40分あるので、研究というかなんというかいろいろ頭の体操をしながら自転車を漕いでいるのだが、今日は @sassano さんに教えてもらって文節をどう区切るかを再読する。いや、N文節最長一致法というヒューリスティックがどういうものだったか(アルゴリズム的にはなにをしていることに相当するのか)考え始めてしまって、なんなんだろうなぁ、と思って……。(もしかしてこのヒューリスティックを統計的な手法で説明できたらおもしろそうだな、と考えたのが事の発端)
基本文献としては以下の3点。いずれも(かな漢字交じり文ではなく)かなだけからなる入力をいかに分かち書きするか、という問題に取り組んでいる。前読んだ気がするのだがすっかり忘れていた。かな漢字交じり文であれば漢字からひらがなやカタカナになったり、数字になったりするという、字種の切れ目の情報が使えるのだが、べた書きかな文は字種の情報が使えない、というのがポイント。とはいえ、字種情報がなくてもかなりいけるようである。
- べた書き文の分かち書きと仮名漢字変換 : 二文節最長一致法による分かち書き．牧野+．情報処理学会論文誌(1979)．
- 文節数最小法を用いたべた書き日本語文の形態素解析．吉村+．情報処理学会論文誌(1983)．
- 2重マルコフモデルを用いたべた書きかな文の仮文節境界の推定方法．荒木+．情報処理学会論文誌(1997)．
こんな昔から研究があったのか、と思うと改めてびっくりするのだが、メモリも CPU も十分にある現代ではコスト最小法(単語単位にするか文節単位にするかなど亜種はあるが)で実用上決着がついた感がある。2番目の論文はけっこう論文の書き方がしっかりしている(従来法のどこが問題で、この手法はどこが利点でどこが欠点か述べられている)ので、そういう意味でも参考になる。
まあ、目的は正しい「文節」を見つけることではなく、かな漢字変換に役立つ補助情報として「ここは確実に切れそうだ」というところだけマークすればいい(極端なことを言うと文節の情報が間違っていても変換結果が正しければ事実上関係ない)という問題なので、実用上は意味があっても研究的にはあまり盛り上がらなさそうな雰囲気である。「文節」というのも恐らくアルゴリズム(や個々人の入力スタイル)によって違うような気がするし、単語の分かち書きまではいいのだが、文節が絡んでくるととたんによく分からなくなる。(ChaIME や mana では文節の概念は全く登場しないし、文全体の変換以外サポートしていない。統計的にやる宿命だろうか？)
それで冒頭のリンクに戻るのだが、接続コスト最小法の説明で
n文節最長一致法との違いは、最長一致法が前から順番に選定していくのに対し、最小コスト法が数値化によって文全体のコストを計算するという点にある。最小コスト法は、うまくいくと複雑な文章でもきれいに変換できるという利点があるが、重み付けのさじ加減が微妙で難しいという欠点がある。最長一致法は、あくまで前から（うしろ向きの場合、後ろから）順番に分析するので、文全体をみていないという欠点がある。しかし、変換するに当たって行うべき処理が少なく、原理的に高速である利点がある。また、文全体を取り込まないと解析できない最小コスト法が、処理に係る時間が指数関数的に（2乗3乗……的に）処理に掛かる時間が増えるのに対し、最長一致法は前から順番に選定するので、入力の長さにほぼ比例した時間で解析を行うことが可能である。さらに、前から順番に解析を行うことから、辞書の先読み（入力のつど辞書を読みに行く）がより有効に働くと思われる。
とあるのだが、処理にかかる時間は前向き動的計画法(Viterbi)後ろ向き A* 探索を使えば指数関数的にはならないので、この記述は違うんじゃないかなーと思った。1994年の永田さんの論文でそれが発表されたということを考えると、10年で理論が進歩したので従来使いにくかったアルゴリズムが使えるようになった、ということかな？ 最長一致法のメリット(とされていたもの)の一つが消えるわけだが……。
- A stochastic Japanese morphological analyzer using a forward-DP backward-A* N-best search algorithm. Masaaki Nagata. COLING (1994).
- 前向きDP後向きA^*アルゴリズムを用いた確率的日本語形態素解析システム．永田．NL 研(1994)．
しかしこのあたり調べているとあらゆる文献が永田さんに行き着く。うーむすごいものである。
結局N文節最長一致法(N=1のときはいいのだが、N>1のとき)のヒューリスティックが実質的になにをやっていることに相当するのか、なぜうまく行くのか分からなかったので、これはと思うものがある人はこっそり教えてください :-)
そういえばこれも前に紹介したと思うが再度書いておくと、MS-IME チームのブログが TechNet 上にある。よくよく説明を見るとどうも変換
履歴(ログ)を記録していて、第一候補以外を選択したときにどれを選択したのか、それより上位になにがあったかといった情報はすでに使われているらしい。知らなかった……。アルゴリズムに関してはいろんなところで書かれているし、もっと分かりやすい解説(提灯記事？)もたくさんあるので他のところを見た方がいいと思うが(でも開発者の人たち自ら解説しているというのは偉い！)、個人的に面白いと思うのは
の2点。たとえば後者はいろいろな統計情報を載せていて、
最初のデータです。ユーザが文字を入力する際、平均してみると文字入力を 2 文字するごとに 1 回 Back-Spaceキーが使われるということが分かっています。これを、社内データでさらに詳しく分析してみたら、1/3は書き直し、1/3はタイプミスの修正、残りの Back-Space キーは IME が誤変換したがそのまま確定してしまい入力しなおすためでした。
とか
二つ目のデータです。IME の変換効率は、100 文字入力するうちで何文字誤変換をしたかで、その質を測ることができます。これをパーセントで表したものを、平均文字誤り率と呼んでいます。文字誤り率が低いほど、IMEの変換効率が高いということです。また、ユーザの文書作成の生産性は、1分間で何文字入力し確定したかで､測ることができます。これを分あたりの平均入力文字数と呼びます｡人によってタイピングの速さが異なりますが、何万人というユーザのデータに関して平均をとれば、ユーザ全体に関する文書作成の生産性を見ることができます｡
とか、ログを見ると分かるいろいろなことが書いてあったりする。こういうの、もっと活用していったほうがいいと思うんだけどな〜。(使い方は難しいとは思うが)
