そろそろ最強のキーボード配列を決めたい。
サマリ
量子アニーリングでキーボードの配列を最適化するプログラムを書いた。
適当に回した結果それなりに良さそうなキーボード配列が得られた。
頑張ればもっと良い配列が得られそう。
今回得られた配列：
はじめに
せっかく最高の自作キーボードを作ったのだから、キーボード配列も最高の配列を作りたいと思いつつ1年が過ぎました。
Eucalyn配列はすごく良さそうなのですが、これは配列の最適解なのか？と考えると夜も眠れないので結局QWERTY配列を使っています。
とはいえ、そろそろキーボード配列を決めたいなと思っていたところ、アニーリングによる最適化ができそうだと気づいたので、量子アニーリングで最強のキーボード配列の求解を試みます。
※ 私は特段量子アニーリングに詳しいわけではないので、 説明は間違っていたり雑だったりする可能性があるのであしからず。
考え方
キーへの文字の割当
さて、以下のような標準的な30キーの配置を考えていきます。
Q W E R T Y U I O P
A S D F G H J K L ;
Z X C V B N M , . /
当たり前ですがそれぞれのキーには1つづつ文字が割り当てられており、異なるキーには必ず異なる文字が割り当てられていることがわかります。
ここで、キーボードのキーに次のように番号を振っておきます。
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
すると、キー配列は1hot表現を使って表せます。
A B D E C ...となっているキーボード配列の例：
この0,1を取る1bitを以降は$x_{k,
c}$と表します。ここで、$k \in K, c \in C $、$K$はキーの集合、$C$は文字の集合です。
制約条件
キーに割り当てられる文字は1つ
各キーごとに、文字は1つしか割り当てられないので、先の図の縦の列について、全て足すと必ず1になる必要があります。つまり
$$
\sum_{k \in K } \left(1-\sum_{c \in C } x_{k,c} \right )^2 = 0
$$
のときこの制約を満たします。
文字が割り当てられるキーは1つ
各文字は一つのキーにしか割り当てられないので、先の図の横の行について、全て足すと必ず1になる必要があります。つまり
$$
\sum_{c \in C }\left(1-\sum_{k \in K } x_{k,c} \right )^2 = 0
$$
のときこの制約を満たします。
コスト
最適化に当たり、各bit間のコストを定義する必要があります。
今回は遊舎工房さんの評価方法やKeyboard Layout Analyzerを参考に、文字を打つときのコストを定義します。
以下、bloomと文字を打つときのコストを考えます。
Position cost
これはキーの位置によるコストです。ホームポジションはコストが低く、外側に行くほど大きいです。
次のようにコストを定義すると、QWERTYキーでbloomと打つときのコストは
4 2 2 3 4 4 3 2 2 4
2 1 1 1 3 3 1 1 1 2
4 4 3 2 4 3 2 3 4 4
$4 + 1 + 2 + 2 + 2 = 11$
となります。
Position costはキーを押す順番とは無関係に決まります。
(Consecutive) Hand Cost
同じ手で連続でキーを叩くときに加算されるコストです。
QWERTYキーでbloomと打つときは、loomが全て右手なのでlo,oo,omの3回分加算します。
(Consecutive) Finger Cost
同じ指で連続でキーを叩くときに加算されるコストです。
QWERTYキーでbloomと打つときは、looが全て右手薬指で打つキーになります。
Finger Costはloの1回分加算されます。ooの部分については同じキーのため後述のConsecutive Key Costを加算するためFinger Costは加算しません。
Consecutive Key Cost
連続で同じキーを叩くときに加算されるコストです。
QWERTYキーでbloomと打つときは、ooが同じキーなのでooの1回分加算します。
定式化
以上の内容を定式化すると次のようになります。
$$
\text{minimize} \quad H = H_{obj} + H_{1hot} + H_{unique} \\
H_{obj} = - \sum_{\substack{k_i, k_j \in K, k_i\neq k_j \\ c_m, c_n \in C, c_m\neq c_n}} J_{k_i,c_m,k_j,c_n} x_{k_i,c_m} x_{k_j,c_n} - \sum_{k\in K,c \in C} h_{k,c} x_{k,c} \\
H_{1hot} = - W_{1hot} \sum_{k \in K }\left(1-\sum_{c \in C } x_{k,c} \right )^2 \\
H_{unique} = - W_{unique} \sum_{c \in C }\left(1-\sum_{k \in K } x_{k,c} \right )^2
$$
ここで、$H_{obj}$ はコスト、$H_{1hot}$と$H_{unique}$は各制約条件です。
$-J_{k_i,c_m,k_j,c_n}$はビット間の相互作用を表す係数で、$x_{k_i,c_m}$と$x_{k_j,c_n}$の間のHand Cost, Finger Cost, Consecutive Key Costの合計です。
$-h_{k,c}$はビット自体がどの値を取りやすいかを表す係数で、$x_{k,c}$のPosition Costの合計です。
$W_{1hot}, W_{unique}$は各制約条件の制約違反を防ぐための重みです。
(量子)アニーリングで$H$を最小化することで、最もコストの小さい解を求解できます。
プログラム
githubに置きました。
アニーリングにはOpenJijを使っています。一応Simulated Quantum Annealing (SQA)で解いているので量子アニーリングと言っていいですよね。ダメですか。
入力にはサンプルとしてAlice's Adventures in WonderlandのChapter 1を入れています。それほど長い文章ではないので偏っているかもしれません。必要であれば文章を変えたりして試してみて下さい。
インストール
poetryを使っているので、インストールしていない人はpoetryを入れて下さい。
$ pip install poetry
依存ライブラリをインストールします。
OpenJijのインストールでコケる場合はCMakeのバージョンが古いことが原因の場合が多いです。
$ poetry install
実行
$ poetry run python -m quantum_keymap
解が出るとresult/配下にアニーリングのログと最小コスト時のキーマップ画像が保存されます。
必要に応じてquantum_keymap/__main__.pyを弄ってパラメータを変更して下さい。
特に制約条件の重みは入れる文章によってチューニングが必要かと思います。
結果
何回か回した結果そこそこ良さそうな配列が得られました。
母音,R,T,H,Nなどよく使うキーがホームポジションに並んでおり、普通に使えそうに見えます。
せっかくなので quantum配列 v0.0 とします。
他の配列との比較
Keyboard Layout Analyzer
で比較しました。
Simplefied Dvorakに負けとる……
圧倒的1位です！！！
Colemak等はQWERTYからの変更を少なくしていますし、Eucalyn配列は日本語入力用なので当たり前といえば当たり前ですね。
Keyboard Layout Analyzerの計算方法がわかればもう少し点数も上がると思います。
まとめ
量子アニーリングでキーボードの配列を最適化するプログラムを書きました。
得られたキーボード配列をベンチマークしたところ、英語入力では非常に良いスコアでした。
今後
アニーリングである程度良い配列が得られることがわかりましたが、次のような課題があります。
- 日本語を考慮していない
- pykakasiやmecabなどを使って形態素解析すれば同じようにできるはず
- z,x,cなどのキーは固定したい
- Shift、Space等のキーを考慮していない
- コストの計算に使っている文章が短い
- コーパスやwikipediaから文章を持ってくると良さそう
- パラメータチューニングが雑
- パラメータチューニングのやり方知らないので誰か教えて下さい
- 量子コンピュータで解いてない
- 誰かD-Waveで解いて下さい
気が向いたら改善します。
この記事はQWERTY配列で書きました。