最適輸送によるキー配列最適化
1 注意書き
この記事は筆者が取り組んでいる事の中間報告のためにまとめたものであり，出力された結果は暫定解です．未実装のアイディアがいくつかあるため，今後の更新も楽しみにお待ちください．
2 前置き
自作キーボード沼にハマっている方はどこかのタイミングで直面するテーマ， QWERTY配列で本当にいいのか？ をここでは扱います． つまりは 物理的なキーと文字をどのように対応付けるか という問題を機械学習の枠組みで解決しようという内容になります．
QWERTY配列の問題点は多くの方が記事にまとめているためここで改めて整理することはしませんが，普及率以外の利点を挙げることは難しいです． そのため次世代の配列として，Dvorak配列 [1] やColemak配列をはじめとした英字向け配列や， Eucalyn, Tomisuke, Astarte, 大西配列といった日本語入力も考慮した配列が考案されています． このあたりは 比較記事 や 非標準配列コンテスト動画 などが非常にわかりやすいです．
学習コストや入力負担の軽減，タイピング速度の向上を目的に様々な配列が提案されていますが， 個人的にモヤモヤしていた点が どのような指標に基づいて最適化するか でした．
一般にホームポジションからなるべく動かずに多くの入力ができるのが良いとされており，定性的には同意できるのですが， ホームポジション以外の場所のコストをどのように設定するかは決め打ちされていることが多いです． またホームポジションからの物理的な距離でコストを設定しているケースもあり，直感に頼らないこの方針に賛同できる気持ちもある一方， 例えば物理的な距離が同じでも小指と薬指で打ちやすさが異なったり，そもそも手の大きさにも依存するよなぁと思う側面もありました． 友人と手の大きさを比べた際に関節0.5個分以上違った出来事が，私の懸念を強く印象付けています．
そのような出来事から，画一的な指標を設けるのは難しいのではないかという考えに至りました． Keyboard Layout Analyzer のような 評価サイトがあることは認識していますが，そこでの指標を最適化する配列が得られても， 自分にとって使いやすいものにはならないのではないかと考えました． つまりこの記事でやろうとしていることは， 直感的なパラメタ設定を一切せず，個々人へ最適化された配列を得るためのアプローチを提案する ということです．
3 最適化の方針概要
キー配列を最適化する時，一般的に以下の設計が必要だと思います．
- データセット: 各文字の頻度分布や統計情報を収集するためのテキストデータ
- 評価関数: 入力文字列を指定のキー配列で入力した際の評価値
- 最適化アルゴリズム: 上記の評価値を最大化するキー配列を探すためのアルゴリズム
筆者が注目しているのは主に評価関数の作り方です． 一般的にはホームポジションから離れた位置にあるキーや小指による操作・同じ指での連続入力に対して 損失を与える評価関数が設定されると思います．
今回用いたのは， Gromov-Wasserstein による入力文字と物理キーのマッチング です． 具体的には，入力文字の分布と2つの文字の距離(的なもの)をデータセットから作成し， 物理キーの分布は(現時点では)一様分布とし，2つの物理キーの距離はタイピングサイトで収集した計測時間として最適化問題を解きます．
まだ未実装のアイディアがあり，対象とした文字もアルファベットだけですが，現時点で最適化した結果は以下のとおりです． 片手側に母音が集まっているという点からも悪くない配列が得られているように思います．
----------------------------------------------
| 1 | 2 | 3 | 4 | 5 || 1 | 2 | 3 | 4 | 5 |
|----------------------------------------|
1 | F | C | T | H | V || G | X | J | E | P |
2 | Z | N | R | L | S || A | U | I | O | |
3 | Y | M | B | W | D || Q | K | | | |
----------------------------------------------4 最適化問題の詳細
Gromov-Wasserstein (GW) 自体の知名度があまり高くないかもしれませんが， このキーワードでググってもらうと披露宴の席次最適化の記事が出てくると思います． このように，2つの集合があり一方の要素を他方の要素と対応付けたい，けれど2つの集合の要素同士の距離を直接評価することはできない， 同じ集合の要素同士であれば評価できる，という状況で適用可能な最適輸送手法になります． 今回の場合，アルファベット(26文字)の集合と，物理キー(26個)の集合があり， 距離('a', '左shiftの右隣の物理キー') は定義できません． 一方で 距離('a', 'b') を，例えば「データセットの連続した2文字における’ab’の頻度の逆数」のように定めれば距離っぽいものが作れます． また 距離('左shiftの右隣の物理キー', '右手ホームポジションの人差し指キー') については「2つのキーの入力遷移時間」とすることでそれらしい値になります．
この概要を踏まえてきちんと定式化します．
- \(\Lambda \coloneqq \left\{ a, \dots, z \right\}\) : 文字としてのアルファベット集合
- \(\Gamma \coloneqq \left\{ A, \dots, Z \right\}\) : 物理キーの配列 (ここではQWERTY配列で見たアルファベットで物理キーを表記)
- \(\mu\) : \(\Lambda\)上の確率分布．\(\sum_{c\in \Lambda} \mu_{c} = 1\) で，データセットにおけるアルファベットの頻度から計算
- \(\nu\) : \(\Gamma\)上の確率分布．今回は一様分布とする．
- \(C_{c_1 c_2}\) : \(\Lambda\)上の距離的なもの．ただし非退化性も三角不等式も満たさないため距離にはならない．2つのアルファベット \(c_1, c_2\) に対して，データセットに含まれる連続した “\(c_1 c_2\)” または “\(c_2 c_1\)” のつづりの個数の逆数で定義
- \(D_{d_1 d_2}\) : \(\Gamma\)上の距離的なもの．ただし非退化性も三角不等式も満たさないため距離にはならない．2つの物理キー \(d_1, d_2\) に対して，タイピングサイトで計測した \(d_1 \to d_2\) または \(d_2 \to d_1\) の遷移時間の中央値で定義
このように記号をおくことで，キー配列最適化をGromov-Wassersteinの枠組みへ落とし込むことができます． \[ \min_{\pi \in \Pi(\mu, \nu)} \sum_{c_1, c_2 \in \Lambda} \sum_{d_1, d_2 \in \Gamma} \left( C_{c_1 c_2} - D_{d_1 d_2} \right)^2 \pi_{c_1 d_1} \pi_{c_2 d_2}, \] ここで \(\pi\) は \(\mu\) と \(\nu\) のカップリングと呼ばれるものです． これを最適にするカップリングを求めたうえで， scipy.optimize.linear_sum_assignment などを使い割当問題を解いてマッチングを得ます．
5 タイピングサイトによるデータ収集
先程の設定のうち，データセットから収集できないのは 物理キーにおける遷移時間 です． 実際の機械学習プロジェクトでもよくありますが，最も苦労するのは定式化でも最適化でもなくデータ収集だったりします． 私の把握する範囲において，キー入力の計測データを取得できるタイピングサイトは存在しませんので 自分で作るしかないという結論になりました． 現時点の実装状況は以下のとおりです．
- 実装済
- ユーザ登録・ログイン
- 英文・英単語でのタイピング画面
- 2つのキー入力の遷移時間を計測
- 未実装
- 計測データのダッシュボード
- 計測データのエクスポート機能
- 個別最適化の機能提供
- 収集データの多様化
- 誤入力分布の計測
- 日本語文章でのタイピング画面
- 個人的な見解では，この機能は不要だと考えています．詳細は 雑談 へ
まだ他ユーザへ機能提供できる状態ではありませんが，将来的には一般公開したいと考えています．
6 今後
冒頭にも書いたように今回のアプローチはまだ完遂していません．具体的には以下のアイディアも盛り込みたいと考えています．
- 誤入力情報の反映
- 計測の非対称性の考慮
- (現時点で)Aキーを入力後にFキーを入力する遷移時間と，Fキー後にAキーを入力する遷移時間のズレ
- 複数レイヤーを前提とした最適化
私もQWERTY配列から最適化配列へ移行したいため， 上記3つを実装した段階で一区切りつけてレビュー記事を書こうと考えています．
7 雑談
計測データ収集のためのタイピングサイトを作成しようと思った当初は， 日本語のためにローマ字入力オートマトンも実装しないとなぁ，と思っていましたが， 現在は必要ないと思っています．その理由は， 日本語文章における入力アルファベットの分布情報は原則的に， 数式において \(\mu, C\) にのみ反映されるという考えを私が採用しているためです． つまり「英文に含まれる “sa” を入力する速度と，日本語文章の途中に出てくる “さ(sa)” を入力する速度に違いはない」という 考えから，分布情報の違いは物理キーの情報 (\(\nu, D\)) に影響を与えないという前提を採用しているということです．
また実装中気づいたことですが，物理キー間の遷移時間を計測するという目的に対して， 一般的なタイピングサイトは最適ではないかもしれないとも思いました． 例えば今回のアプローチの場合，「QWERTY配列におけるyキーの後にjキーを入力した際の遷移時間」も 計測しておくのが好ましいです．一方で “yj” というつづりを含む英単語はほとんどありません． そのため今回作成したwebアプリでは，2-4文字の機械的に生成した文字列を中心にデータ収集をしています． これは前述の前提を採用しているからこそ使えるデータのため，その前提に立てない方にとっては信頼に値しないデータかもしれません．
といった感じでツッコミどころはありますが，ひとまずは設定した最初のゴールに向けて実装を進めていきます．