AHOKA システムの理論と実装
欧文キーボードの文字配列を蟻コロニー法で最適化しちゃったプロ研究者がいるんですね*1。blechmusik2 さんがその論文を 日本語で解説してくださっている のを読んで初めて知りました。
実は私も一昨年の研究室合宿で似たよう話を発表したんですが、そのスライドは墓まで持って行くつもりでした。なぜって、いわゆる「夜の部」で聴衆が酔ってることを前提に発表した「自由研究」ですから……。お察しください。
ところで blechmusik2 さんも日本語入力を対象に 似たよう話に取り組んでいらっしゃる ようで、最近はてな村キーボード集落の井戸端会議が盛り上がっています。ならば、いっそこの機会に燃料として投下してしまおう、というわけで、ここにそのスライドを晒しておきます。
夜の部だけあってノリがアレなのは勘弁してください。要約すると
- キーボード上の文字のレイアウトを数理計画法で最適化する。
- 目的関数は打鍵速度の最大化。
- パラメータは 2-gram の打鍵時間と出現頻度。
- 整数計画問題としてモデル化し、線形計画ソルバーで解こうとした。
- 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.
