Hatena::ブログ(Diary)

Wisteria::Diary RSSフィード Twitter

2009/04/20

[] AHOKA システムの理論と実装

欧文キーボードの文字配列を蟻コロニー法で最適化しちゃったプロ研究者がいるんですね*1。blechmusik2 さんがその論文日本語で解説してくださっている のを読んで初めて知りました。

実は私も一昨年の研究室合宿で似たよう話を発表したんですが、そのスライドは墓まで持って行くつもりでした。なぜって、いわゆる「夜の部」で聴衆が酔ってることを前提に発表した「自由研究」ですから……。お察しください。

ところで blechmusik2 さんも日本語入力を対象に 似たよう話に取り組んでいらっしゃる ようで、最近はてな村キーボード集落の井戸端会議が盛り上がっています。ならば、いっそこの機会に燃料として投下してしまおう、というわけで、ここにそのスライドを晒しておきます。

http://picasaweb.google.co.jp/mobitan/Ahoka1#slideshow

夜の部だけあってノリがアレなのは勘弁してください。要約すると

  • キーボード上の文字のレイアウトを数理計画法で最適化する。
  • 目的関数は打鍵速度の最大化。
  • パラメータは 2-gram の打鍵時間と出現頻度。
    • 打鍵時間は自分を被験者として Excel マクロで実測した。
    • 出現頻度は自分のブログkakasi で逆変換して集計した。
  • 整数計画問題としてモデル化し、線形計画ソルバーで解こうとした。
    • 2-gram を素直に定式化したら 2 次計画になり、挫折。
    • 2-gram を展開してむりやり線形化したら組合せ爆発を起こし、挫折。
  • 厳密なモデル化をあきらめ、いいかげんな (意味的に間違った) モデルでとにかく解いてみた。
    • 結果、なんとなく良さげなレイアウトが得られた。

ということです。上述した Eggers らの論文に比べて、この方式のキモは

  • パラメータ空間として 2-gram を採用したこと
  • 指の敏捷さや同指打鍵の負荷係数といった非自明なパラメータを排除し、それらのファクターを 2-gram の打鍵時間という自明なパラメータに統合したこと
  • 言語別の特徴を直接モデル化しようとせず、2-gram の出現頻度という汎用的なパラメータに帰着させたこと

かなぁと思います。まあ所詮は自由研究にすぎませんけどね。

*1:J. Eggers, "Optimization of the keyboard arrangement problem using an ant colony algorithm," European Journal of Operational Research, vol. 148, no. 3, pp. 672-686, August 2003.

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト

コメントを書くには、なぞなぞ認証に回答する必要があります。

トラックバック - http://d.hatena.ne.jp/mobitan/20090420/1240256898
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2013 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2015 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2016 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |