Optimal keyboards by Monte Carlo minimisation

Chatting in the cafeteria the other day someone mentioned that QWERTY keyboards where designed so that letters that appear next to each other often in English do not appear next to each other on a typewriter. This minimizes the possibility that typewriter brushes get stuck. I do not know anything about typewriter brushes, but I can recognize an optimization problem when I see it!

In order to attack the problem, I decided to make a physical model. I will treat letters as particles with a very short range interaction. I took a standard sample of the English language and counted how often letters appear next to each in each word. I then normalize the probability that two letters are next to each other. I now take this probability as being a sort of “energy”. I define the keyboard as a sort of lattice on which keys can live. Achieving the keyboard where letters that tend to appear next to each as seldom as possible consists in minimizing the energy.

The difficulty with this task is that we need to find the minimum in a very complex multi-dimensional surface which is likely to have several local minima. I decided to use Simulated Annealing together with a Monte Carlo type approach. In Metropolis Monte Carlo, a new state is generated. This leads to a change of energy de . If de<0 or if exp(de/T)<r (where r is a uniform random number between 0 and 1) the state is accepted. This allows to sample the canonical ensemble, without generating the full sample (this deals with the high dimensionality of the problem). If the effective temperature T is large, states are accepted very easily – which allows the system to jump out of local minima. If conversely the temperature is small, the system is pushed towards a local minimum.

I coded these concepts in python – feel free to download the code.

So now the results! First of all the “energy” of a qwert keyboard is 0.146.  A typical run of my code kicks up such a keyboard:

[‘u’, ‘k’, ‘g’, ‘s’, ‘m’, ‘w’, ‘n’, ‘z’, ‘c’, ‘a’]
[‘e’, ‘q’, ‘j’, ‘h’, ‘y’, ‘p’, ‘l’, ‘f’, ‘t’]
[‘o’, ‘i’, ‘r’, ‘d’, ‘v’, ‘b’, ‘x’]

This has an energy of 0.0261, almost ten times smaller than a qwert keyboard. I guess that the model could be significantly refined, here I show only the result of one run, but clearly since this is a code using pseudo random numbers, every run leads to a different keyboard. How should the results be viewed and compared? I admit I cannot readily think of a better way. Certainly it seems that most of the keyboards I kick up relegate the vowels to the edges of the keyboard, just like a normal qwerty board. I wonder whether this sort of approach could be used for other problems: is it possible that the Eurovision results  could be used to define interactions between countries and hence a “shape” of Europe consistent with the voting patterns. Mhhh???

Advertisements

About jakirkpatrick

I am a researcher in solar energy at the University of Oxford. I am interested in mathematics, programming and trying to understand why things work. I also like the great outdoors and riding my bike.
This entry was posted in Uncategorized. Bookmark the permalink.

4 Responses to Optimal keyboards by Monte Carlo minimisation

  1. Szaki says:

    There’s something missing from line 2 of paragraph 3.
    To the point: if you search for “optimal keyboard layout”, one of the things which keeps popping up towards the top of the list is the Dvorak layout. It seems that the consensus is that this is the best layout ever. 🙂 I wonder how it would score in your test.

  2. I will check it out tonight and let you know!

  3. Piers says:

    I believe the QWERTY keyboard was meant as some kind of compromise between typing efficiency and minimising the possibility of the brushes jamming. These days we don’t need to worry about jammy brushes. Perhaps it would be interesting to change your optimisation constraints to place the most regularly used letters or combinations of letters under fingers in some kind of dexterity ranking alternating between hands? This might lead to the fastest possible layout.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s