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 . If or if (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 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???