2011-02-28: Designing an optimal keyboard layout for 1-finger use

Optimus Keyboard Layout

This is the final solution for my experiment to find the most optimal keyboard layout for use by one-finger or cursor+click movement:

  V D R N G F Q
  _ A E I O U _
  K H T S L B J
  X C W M Y P Z
  
The vowels in the second row would be enlarged to cover the width of the entire row.  

Background

The primary goal of the KType project is to improve communication for people with disabilities. I am developing an iPad app that presents the users with an on-screen keyboard with large keys that can be re-arranged easily for comfort and efficiency. The application makes communication easier by predicting what the user will type next. I analyzed how people talk on Twitter to create KType's prediction engine. Improving prediction is just one way to reduce the effort needed to communicate. Another way is to minimize the amount of movement required to type.

Motivation

The computer keyboard layout we are all familiar with is called QWERTY based on the first six letters in the top row. It was designed by C. L. Sholes in 1878 for using a typewriter with two hands and the letters were arranged in a special, non-alphabetical order to improve the speed of typing by minimizing jamming of the typewriter. Since computer keyboards don't jam, many people have tried to re-arrange the keyboard layout to improve typing efficiency; a layout popular among computer programmers is called Dvorak. But all of these layouts are optimized for users with two hands, ten fingers.

Potential users of KType might use head-tracking and blink-action to type. Existing keyboard layouts are inefficient for typing with a single finger or cursor+click movement. KType users could certainly benefit from a keyboard layout that requires the least amount of movement when typing with just one finger. With that goal in mind, I sought to design such a layout - the Optimus Keyboard Layout.

In addition to Optimus, KType will also provide QWERTY, DVORAK, ABCDEF keyboard layouts to users who are already accustomed to a particular layout and do not wish to switch.

What makes a keyboard optimal?

The 26 letters of the English alphabet can be rearranged into infinite ways on a flat surface. You can put all the keys in a straight line, arrange the consonants in a circle with the vowels in the middle, or break them into rows like regular computer keyboards. How can we measure if one keyboard layout is better than any other? To answer that question, I used a simple formula to calculate the score for each keyboard layout:

Keyboard Score = (Distance between a key and every other key) * (Frequency of that key-pair being used in regular typing)

The distance is relatively easy to calculate. Keys next to each other and above/below each other have a distance of one. Keys diagonal to each other have a distance of square-root of 2. If the keys are in a grid, it is trivial to compute the distances using the Pythagoras Theorem. Python even has a math.hypot function to make this easy.

The frequency for each combination of letters comes from my recent analysis of Twitter data that resulted in this letter-pair frequency table. I analyzed 9 million Tweets and obtained a list of the most common words and phrases used by over a hundred thousand users. Based on the frequency of use of each word and phrase, it was straightforward to calculate how often do two letters follow each other in common usage. Not surprisingly, the letters 'T' and 'H' are typed in a row most often, followed by 'I' and 'N', then 'E' and 'R'.

Example: 3-key layout

Imagine just three keys 'A', 'C', and 'T' arranged next to each other like [A][C][T]:

Distance between A and C                            1
Frequency of typing 'AC' or 'CA'               x  200  =  200 (for A, C)
Distance between A and T                            2
Frequency of typing 'AT' or 'TA'               x  500  = 1000 (for A, T)
Distance between C and T                            1
Frequency of typing 'CT' or 'TC'               x  100  =  100 (for C, T)
---------------------------------------------------------------------------
Total Keyboard Score                                   = 1300 (for A, C, T)

Lower keyboard scores mean the finger has to travel a shorter distance to type the most common words and phrases. To improve a keyboard layout, we just need to rearrange the letters such that letters most commonly typed in a row (like 'T' and 'H' or 'I' and 'N') are next to each other. In the above example, 'A' and 'T' are furthest apart at a distance of 2 and also typed the most often i.e. frequency of 500. We could easily re-arrange this keyboard to reduce the score as follows:

Optimized: 3-key layout

Re-arrange the three keys 'A', 'C', and 'T' to [C][A][T]:

Distance between A and C                            1
Frequency of typing 'AC' or 'CA'               x  200  =  200 (for A, C)
Distance between A and T                            1
Frequency of typing 'AT' or 'TA'               x  500  =  500 (for A, T)
Distance between C and T                            2
Frequency of typing 'CT' or 'TC'               x  100  =  200 (for C, T)
---------------------------------------------------------------------------
Total Keyboard Score                                   =  900 (for C, A, T)

Re-arranging the keys reduced the total keyboard score without any change in the frequency of typing different letter combinations. This 30% improvement in score means the same text can be typed faster and require less movement. For users who find it difficult to move their hands, this could be a remarkable improvement.

By this metric, the new Optimus keyboard should be significantly better than QWERTY, DVORAK, and alternatives.

Re-arranging keys is hard

To make it even possible to design an optimal keyboard, I had to place some restrictions on the layout:

  • It must be a grid of keys (10×3, 9×3, 7×4, 6×5)
  • The keys must be directly next to or above/below each other, unlike the QWERTY layout where 'A' is not directly under 'Q'
  • Blank key slots are allowed because the only grid layout with exactly 26 slots are 1×26 and 2×13
  • All keys must be the same size (keyboard-score calculations get complex otherwise; would also have to worry about overlap/collisions)

These restrictions mean that I could be ignoring a more efficient keyboard layout (possibly circular) but given the fact that almost every keyboard in existence is close to a grid (3 rows of 10 keys) and the iPad has a rectangular screen, a grid-like layout will work for my users. The closer the grid is to a square, the lower the score is. I prefer 7×4 (28 key slots) grid because it is closer to square than 9×3 (27 key slots) and only has two blanks as compared to 6×5 (30 key slots) grid with 4 blanks. Additionally, the KType interface is suited quite well for 4 rows of letters.

The 26 alphabets could be arranged into a grid of 7×4 in over 10^29 ways, into a grid of 6×5 in over 10^32 ways. Planet Earth has only 10^50 atoms so given the current state of technology and my dwindling savings account, it is impossible to simulate every possible keyboard layout and calculate its score to find Optimus. In computer science terms, this is problem is in NP.

Reddit & Computer Science to the rescue

After realizing that I was trying to find a perfect solution to an uncomputable problem, I decided to put my four years of college to use. I dug into complexity theory articles and papers to see if someone has solved this exact problem but that effort was fruitless. I turned to reddit/r/compsci subreddit and rephrased my problem into more understandable terms: How would you seat 26 people in a big room of cubicles such that people who like each other a lot end up sitting close to each other? While I did not get an exact answer (and neither did I expect one), I got a lot of leads: genetic optimization, dynamic programming, distance preserving embedding graphs, facilities problem, k-means clustering, and simulated annealing.

I was very interested in using genetic algorithms to evolve a better keyboard from two or more good keyboards but found it impossible to combine two keyboard layouts into a new one. How would one combine the QWERTY and DVORAK layouts to create a new generation in one-pass anyway? I had similar issues in applying k-means clustering, graph layouts etc. to my problem. I don't mean it is impossible to use these methods, I just couldn't find a logical, simple way to apply these solutions to my problem. After fiddling with tons of algorithms, I found that simulated annealing works pretty nicely for this particular problem.

Update 2011-02-28, 1:25pm: Redditor deong mentioned that this problem is called Quadratic assignment problem, which is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems.

Algorithms behind Optimus

I tried three different methods to find the most optimal keyboard. I started with the simplest algorithm I could think of:

Random Grid

Step 1: Select a grid size: 7x4 (or 10x3, 9x3, 6x5)
Step 2: Randomly put all the alphabets into the grid
Step 3: Calculate the score
Step 4: Swap two or more keys and recalculate score
Step 5: If score in Step 4 is 'progressively better' than Step 3, keep the new layout
Step 6: Repeat Step 4 about 100,000 times

Each time the above program was run, I would get a new keyboard layout with the lowest possible score that random swapping could achieve. I ran the script 10,000 times for 7×4 grid and here are the three best layouts:

Rank #1, Score: 130575410797

  _ J Y M L D Z
  Q B U O A N G
  X P R E T I C
  _ V F S H W K
Rank #2, Score: 130676148330

  _ K W H S F V
  X C I T E R P
  Q G N A O U B
  _ Z D L M Y J
Rank #3, Score: 130683308691

  V F S H W K _
  P R E T I C Z
  B U O A N G Q
  J Y M L D X _

Notice that the keys 'E', 'T', 'H', are always adjacent to each other and generally towards the center. Similarly 'I', 'N', 'A' are adjacent and close to the center. In practical terms, all three of these keyboards are equally good but the problem with them is that I cannot definitively tell if they are optimal or not. They just look so random!

Per-key Heat-map

Step 1: Get an optimized keyboard using Random Grid method
Step 2: For each key in the keyboard, store its position in the grid and the keyboard score
Step 3: Repeat Step 1 about 10,000 times
Step 4: Find the key with the best position among all layouts and place it in that position
Step 5: Repeat Step 4 for all keys i.e. find best open position for each key
Step 6: Print the keyboard with best position for each key

I wrote this algorithm with the idea that if keyboards with letter 'E' in the second row, middle column most often get low scores then there is a good chance that 'E' belongs in the second row, middle column in the Optimus keyboard. It is also possible that keyboards with the letter 'T' in second row, middle column also get very low scores but not as low as 'E' in the same position. In that case we pick the next open position that 'T' has low scores in, and so on for each letter. I ran the script hundreds of times but not one keyboard scored better than any of the Random Grid keyboards, even though we combined optimized keyboard generated via the Random Grid algorithm. Applying 100,000 generations of randomized swapping to the final heat-map keyboard helped, but it was no different than starting with a completely random grid. So in the end, I abandoned this approach.

Fixed Vowel Row

Step 1: Set grid size to: 7x4
Step 2: Put '_AEIOU_' in the second row, randomly put consonants into rows 1, 3, and 4
Step 3: Calculate the score
Step 4: Swap two or more keys in rows 1, 3, or 4 and recalculate score
Step 5: If score in Step 4 is 'progressively better' than Step 3, keep the new layout
Step 6: Repeat Step 4 about 100,000 times

This method is almost identical to Random Grid with the exception that vowels are fixed in the second row. The idea behind this is three-fold:

  • With just 5 letters in second row, I can make the vowels larger and easier to click
  • Having a fixed row of vowels will make the keyboard easier to remember and provide a stable home row
  • Putting all the vowels in second row means no consonant will be more than 2 vertical units away from the vowels

I ran the above algorithm 100,000 times and was pleasantly surprised at the result. Every single time the best keyboard was the following:

Rank #1, Score: 135242359724

  V D R N G F Q
  _ A E I O U _
  K H T S L B J
  X C W M Y P Z

I also saw the following two layouts popup many times, notice how similar they are to the above layout:

Rank #2, Score: 135298507794
  V D R N G F Q
  _ A E I O U _
  C H T S L P J
  X K W M Y B Z
Rank #3, Score: 135428576171
  V D R N G F Q
  _ A E I O U _
  K C H T S M J
  X B W L Y P Z

I verified my code to ensure that I was indeed going through thousands of random keyboards and not the same random layout over and over again. Yet the exact same layout out of a possible combination of 10^19 (21-factorial permutations) kept showing up as the best result over and over again. Either I was constantly hitting the local minima or I had found Optimus. I wasn't sure. Time to graph it up.

Simulated Annealing

If you look at Step 5 of Random Grid and Fixed Vowel Row algorithms, you'll see I only keep a keyboard generated from swapping two or more keys if the new score is 'progressively better' than the previous score. Whether a new keyboard is considered progressively better or not directly affects how a random keyboard mutates over generations to achieve a lower score. The problem with iteratively generating improved keyboards from an initial random layout is getting stuck in local minima. Local minima is the state where after a number of generations, randomly swapping 2-6 keys over and over will not help lower the score of the keyboard. This doesn't mean we have achieved the best keyboard layout possible, but rather an entirely different layout would be required if we were to get any lower. This is similar to playing Sudoku where after getting the first 2-3 numbers fit, we find it impossible to solve the rest of the puzzle, because even though these 2-3 numbers fit a small section of the puzzle, they are not the correct values and thus do not align with the final solution.

One sure way of getting stuck in the local minima is to set the definition of 'progressively better' to mean strictly better: Only accept a new keyboard if its score is lower than the previous score. A good way to avoid getting stuck in local minima is to accept scores slightly worse than the previous score, in the hope that future generations will lower the scores fast enough to achieve global minima eventually. For us, global minima is the lowest possible score achievable by a keyboard, which by definition is the Optimus Keyboard Layout that we seek.

I ran the Fixed-Vowel Row script with different values for 'progressively better':

  • SA=1.05: Accept keyboard if new score is less than 105% of previous score
  • SA=1.025: Accept keyboard if new score is less than 102.5% of previous score
  • SA=1.01: Accept keyboard if new score is less than 101% of previous score
  • SA=1.001: Accept keyboard if new score is less than 100.1% of previous score
  • SA=1: Accept keyboard if new score is less than previous score

The following graph shows the keyboard score over 1000 generations for each value of SA. Each of the five curves was generated by taking the lowest score for each generation from 1000 independent runs of the Fixed Vowel Row algorithm.

The horizontal axis is time i.e. the generation of each keyboard layout and vertical axis is the scaled-down keyboard score (100 = worst, 0 = best). Notice that the values for SA=1.001 are lower than those of SA=1 between generations 244 and 460. Both the lines approach 0 as time goes on. The graph for SA=1 gradually goes down to 0, without ever rising. The graph for SA=1.001 rises a few times and then falls down further towards zero. This is a visualization of the algorithm escaping the local minima. In the download section, you will find two Excel files in the zip file with more data showing the effect of the various SA values.

After examining these graphs I realized that if there is a completely different global minima, I'm not seeing any evidence for it. It appears to me that indeed the Fixed Vowel Row layout with score of 135242359724 is the most optimal layout I could come up with. I feel comfortable in saying that I have found Optimus.

Comparing Optimus to QWERTY, DVORAK etc.

Optimus is only useful if it is significantly better than the existing keyboard layouts. In designing Optimus, I made two types of changes:

  • Change the grid size to 7×4
  • Re-arrange the keys for optimal usage

As I mentioned above, the closer a grid is to a square, the lower the score will be. Consequently, a random 7×4 keyboard should have a lower score than a random 10×3 or 9×3 keyboard layout. In an example above I showed that re-arranging keys without changing grid size can significantly lower scores too.

To make direct comparisons with QWERTY/DVORAK possible, I also designed a 10×3 Random Grid keyboard:

Score: 234828339277 - QWERTY

  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 _ _
Score: 285170559534 - DVORAK

  _ _ P Y F G C R L _
  A O E U I D H T N S
  _ Q J K X B M W V Z
Score: 228186373801 - ABCDEF

  A B C D E F G H I _
  J K L M N O P Q R _
  _ S T U V W X Y Z _
Score: 142812598543 - Random Grid 10x3

  X V W H E R M B J _
  Z C D A T O U Y P _
  _ K G N I S L F Q _
Score: 130575410797 - Random Grid 7x4

  _ J Y M L D Z
  Q B U O A N G
  X P R E T I C
  _ V F S H W K
Score: 135242359724 - Fixed Vowel Row - Optimus
  
  V D R N G F Q
  _ A E I O U _
  K H T S L B J
  X C W M Y P Z

The Random Grid 10×3 layout is 40% better than QWERTY and 50% better than DVORAK. Surprisingly, the simple ABCDEF is better than both QWERTY and DVORAK when it comes to typing regular English words with one-finger but it is still no match for Random Grid 10×3. The absolute best layout is indeed Random Grid 7×4 but it is only marginally better than the best Fixed Vowel Row layout - Optimus.

I will be using this Optimus layout in the KType iPad application. The Optimus Keyboard Layout and all the other layouts I designed as part of KType are released under Creative Commons Attribution 3.0 Unported license. You are free to use these layouts in your products and projects freely. Feel free to contact me if you wish to discuss customizing these layouts to better suit your application.

Download Source Code

Download: ktype-design-optimus.zip (480 kb).

The file contains the following letter-pair frequency table, Python source code to generate the keyboard layouts using various algorithms, resulting keyboard layouts, and analysis of simulated annealing effects.

Letter-pair frequency table

Letter 1 Letter 2 Frequency
HT2218229634
IN1922554842
ER1913206038
OT1651959574
EH1601011001
IT1487255208
NO1479860227
AN1265459126
AT1260648745
ET1258725651
ST1185232584
EN1171608838
OU1126932155
ES1107565465
OR1092265913
AH1022280805
IS960195483
EM918278103
GN909733510
AL839446797
FO823487673
EV801947989
AE797897656
AR796846722
NT794178903
EL789272000
DE783266966
AS773980698
IL759404506
OW751046502
LO734816471
MO698163757
DN678634049
OS648145027
DO643315365
OY633596100
AD616725699
HI609242985
TU596760119
HO586086517
BE575192703
EW572812083
AM572266367
AC565338092
GO559686660
DI549517237
AW537247331
IM521586389
SU507334794
AY502393165
IR486246571
IW450687179
EK428882955
RT421211358
EI407799929
RU407397030
CE407351197
CO403087197
EG382764462
GI378602448
HW368500309
IK360033022
EP354495878
CI346569568
AB335507570
FI328914371
CH323540014
MY316866458
IO309551788
HS305508336
BO303004287
AI298145659
EY296447167
OP295404717
EF290971651
KN280835232
AV279795408
EO262514383
AP261998245
AG255356395
NU254152765
LU254113954
CK248424708
IV247549005
LY243996318
TW242491399
DL240391532
PU237599233
GH232906631
TY222888273
RS216653503
AK211980140
BU211979402
NS211776426
AF193824730
OV192962716
CT188939364
RY188502168
DT188402546
CU186361403
DR185088727
LP184104242
GU178630271
FR178527639
KO174733777
FT171291497
LT161219491
IP161111324
SY156142943
GR153700734
JU152286241
LS151520422
GT149316256
PR143296724
BL138601267
NY138246852
DS134751885
MU132378859
MT127343629
FU125993561
DY121347072
AU119556041
KS119326917
IY113795309
CN113761460
DU113668234
SW111895723
PS111450787
EU110905976
MS109566195
KR103770406
CR101493632
BY101445176
BI101204181
NR100055146
GS98748538
LR97710011
BR95417380
EX89960199
NW87655828
HY85299649
AO79710648
FY77693099
MN77076264
CS76403037
LN76372421
CL75154679
HU74147418
BT69144648
FL69083270
MP68044740
MR63155285
PT62406896
WY60259788
RW59306342
LM58902094
HR58246149
KL58134151
GL55875832
FS55770806
KT55634609
PY55528363
JO53893753
DM50827500
BS49601932
LW48340561
IU47184174
HP46870843
GM46807175
UY45139207
FN44243974
BD42611310
DW42008116
BM41059508
DH40179641
UW39316423
HN38696521
IZ38554786
GY38354464
TX36283799
QU35324874
DG32666173
FM32426682
CY31746087
AZ31563140
DF30409074
HM29847179
EJ28237181
FG28104043
KU27621187
MW27257997
AJ25554812
KY25484182
HL23549529
BN23242247
EZ22969777
RV22195816
IJ21744779
GW19462601
CD19309807
FK17509243
DP17429475
FW17333850
CX16852097
NV16627871
IX16517246
PW15371993
FH15319896
YZ15225352
JN14670487
NP14354461
AX14148250
FP14133734
KW13722663
PX13701927
DV11802046
BG11632065
BW11303828
TV11233279
JS10902445
OX10533830
UZ10333128
CF9356896
GP8574159
DK8570548
SV8520590
UV8506988
BK8472017
KM8335180
CM7916579
BH7886184
JT7765266
HK7180195
DJ7161828
BF6484840
OZ6475488
EQ6240834
LV6235558
BC6163482
CW6027788
BP6008353
GK5464448
JY5153882
JM4982654
CP4754842
VY4660821
CG4065364
JL3738552
KP3637084
JR3527477
QS3172981
XY3111515
AQ2840475
HX2737927
IQ2443563
NX2323584
MV2300484
UX2103527
JK1830467
LZ1783769
TZ1728101
MX1668414
JW1639389
HV1541979
VW1430812
BX1253260
HJ1234409
FJ1215778
FX1201958
BJ1134450
QT1107381
BV992734
HQ988915
NZ982866
BQ957192
FV931569
GZ914489
CV878834
JP858104
PV847409
GJ841536
NQ812960
WX787716
CQ775845
OQ770656
DQ765843
SX741104
QR704695
GV665842
QY654502
QW497820
RX494117
SZ487502
HZ487323
DX473416
LX394765
MZ378236
LQ360847
WZ356981
CJ338473
DZ311653
CZ256072
GX163601
KV152321
GQ145178
RZ143610
FQ123009
VZ118481
BZ106094
FZ103771
KQ97577
MQ91807
VX86300
KZ69338
JV56091
PZ51385
PQ50243
QV35036
JQ30206
QX28116
JX16176
JZ5151
QZ3030
 
research/articles/progress_20110228.txt · Last modified: 2011/12/18 20:24 by chiragmehta
 
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki