Philosophical Multicore

Sometimes controversial, sometimes fallacious, sometimes thought-provoking, and always fun.

Archive for the ‘Keyboarding Theory’ Category

Should a keyboard layout optimize for hand alternation or for rolls?

Posted by Michael Dickens on January 9, 2010

Thanks to a really nice typing program called Amphetype, I have recently been able to collect some good data on my typing habits. I compiled some data and did a rudimentary analysis of my fastest and my slowest trigraphs. I analyzed my 180 fastest trigraphs and my 156 slowest trigraphs, classifying each one in one of three categories: fully alternating, alternating and rolling, or fully rolling. If it is fully alternating, then each key is typed on the opposite hand from the previous key. If it is fully rolling, then each key is typed on the same hand. And if the trigraph is alternating and rolling, then there are two consecutive keys on one hand, and the third key is on the other hand.

Among the fastest trigraphs, 10% were fully alternating, 75% were alternating and rolling, and 15% were fully rolling.

Among the slowest trigraphs, 21% were fully alternating, 38% were alternating and rolling, and 40% were fully rolling.

So what does this mean? First, let us remember that there are twice as many ways for a trigraph to be alternating and rolling as to be fully alternating or fully rolling. So given a random sample, we would expect a distribution of 25%, 50%, and 25%. The data I have isn’t totally accurate, but it should be pretty close. What’s clear from this data is that fully alternating keys and fully rolling are rarely very fast. Not only that, but you have to count down to the 13th fastest trigraph before you find one that isn’t alternating and rolling. So alternating and rolling is clearly the fastest possibility.

Now let’s look at the slowest trigraphs. These are more evenly distributed. But notice that there are not as many alternating and rolling trigraphs as you’d expect, and there are a lot more trigraphs that are fully rolling. So there are a lot of very slow trigraphs that are fully rolling.

As simple as this data may be, it still gives us some useful information. To optimize our keyboard, we should try to maximize combos where you type two keys on one hand and then switch to the other hand. Getting a computer to do this in practice, though, is tricky. My program is designed to use digraphs; it can use trigraphs with a small modification, but using trigraphs is orders of magnitude slower. We still may be willing to sacrifice speed for accuracy; but is there any way to still maximize our goal of two-keys-at-a-time using digraphs and not trigraphs? I certainly don’t see any way.

Posted in Keyboarding Theory, Keyboards | 5 Comments »

Why Only 30?

Posted by Michael Dickens on December 18, 2009

As you may have noticed, my keyboard designs have been limited to only the central 30 characters — on a traditional QWERTY keyboard these keys include the alphabet, period, comma, semicolon and slash. Why have I not expanded my program to include other keys? It is certainly not because those keys are in optimal positions already. Many of the keys outside of the main 30 have the very worst placement. So why not try to optimize them as well?

1. They are too hard to re-learn.

I have tried to learn a layout where the all of the keys were optimized, but it did not go well. I found myself completely unable to switch back and forth between it and QWERTY. The layout was simply too complicated, so I ended up just putting all the outlying keys back into their original positions.

2. Many of them rely on aesthetics that a computer program won’t notice.

Look at the number keys. They are neatly lined up in an easy-to-remember fashion. However, their order of frequency is not so simple. A computer algorithm would end up completely jumbling these numbers. It would also likely not put the open and close brackets next to each other, as well as numerous other aesthetic benefits. A computer program would simply miss these little nuances.

3. That program would be harder to write.

Yes, I admit it, I am somewhat driven by laziness. This new program would require modification of many parts of the program, and would make it harder to evaluate the keyboard’s score. The set of digraphs used to score the keyboards would be larger, causing both accuracy and program efficiency to suffer. Evaluating the score would require taking into account all four (or even five) rows, and the extra keys on the side. The score evaluation process would be much more complicated, and therefore harder to get right. Overall, I didn’t see the benefits as worth the effort.

Posted in Keyboarding Theory, Keyboards | 1 Comment »

New Keyboard Layout Project: Fast Typing Combinations

Posted by Michael Dickens on December 13, 2009

It’s been a while since I posted anything about the New Keyboard Layout Project. But I recently downloaded Amphetype and have been analyzing my typing patterns, using MTGAP 2.0. So I now have some results, and will probably get more in the future.

The fastest trigraphs to type almost all are either a type of one key on one hand followed by two keys on the other hand, or they are a roll on one hand in one direction. Most of the slowest trigraphs alternate hands every time, and a good number of them are all on one hand in awkward combinations. The fastest words have easy rolls on both hands: what is currently the fastest word, “should” with an average of 176 WPM (hint: my average typing speed is about 85 WPM), uses a combination of hand alternations and easy rolls. In QWERTY, “should” would be typed as “jeaior”. The “ul”/”io” combination is very fast; also, “od”/”ar” is very fast, and the difference between the finger strokes to type “o” and “d” are very brief because the two letters in between are typed too fast. (Does that make sense?)

I will report more fast combinations after the program gets enough data for some better results.

Posted in Keyboarding Theory, Keyboards, New Keyboard Layout Project | Leave a Comment »

Biases of Genetic Algorithms and Simulated Annealing

Posted by Michael Dickens on September 7, 2009

Both genetic algorithms and simulated annealing have a serious problem: they get stuck. There are some possible layouts which could be very good, but which the algorithm will never get to since it requires getting past a certain hurdle. So how can this be solved?

1. Let a layout live and mutate for a while before you kill it. The problem with this is one of memory. You’re going to need some really huge arrays to hold all of those layouts.

2. Make one or a few keys inactive. This was inspired by a bug which led to some interesting results. The idea here is that you make a particular letter cost nothing, and run the algorithm as normal. If this letter was acting as a “wall” preventing the algorithm from getting to a good layout, the wall will be taken down. Then, after a few iterations, insert the letter again. I tried this out, and it had minimal effect. On the other hand, it didn’t slow the program down by much, either.\

3. Make one or a few scoring criteria inactive. This could more effectively break down potential walls than #2. This is tricky to implement reliably, though. If you rotate through the scoring criteria, making each one inactive in turn, then the definition of “best” changes every generation and so the program never comes to a stopping point. If you remove each criterion for a few generations but only one time, then you don’t know if it is adequately hurdle-skipping. And then there’s the added problem that the actual fitness will be reduced, and that has to be balanced somehow.

Are there any other methods that could actually work?

Posted in Computer Science, Keyboarding Theory, Keyboards, Math, New Keyboard Layout Project, Programming | 2 Comments »

Simulated Annealing vs. Genetic Algorithm

Posted by Michael Dickens on September 7, 2009

When I read about simulated annealing, I considered implementing it instead of a genetic algorithm. But I decided not to. Why? Simulated annealing relies on the assumption that the best layout is next to the second best layout, which is next to the third best layout, etc. But this is likely to be untrue. The second best keyboard probably looks nothing like the best keyboard. But genetic algorithms avoid this problem, through repetition. The “all star” round contains many very good layouts, so it is more likely to converge on the best layout.

But when I saw some results, I had to reconsider. Simulated annealing is seemingly much faster. But how can we get it to converge on the best possible layout? Could we do something like simulated annealing, but then repeat it and pool all the best layouts and evolve those using a genetic algorithm?

I ran some empirical tests, and it turns out that simulated annealing is indeed many times faster than a comparable genetic algorithm. Chris Johnson sent me some source code, and it turns out that it is indeed much faster.

Simulated annealing works sort of like a “smart” genetic algorithm with a pool size of only one. Instead of just making any old mutation, it looks for good mutations to make. This allows much faster convergence. But this strategy, as well as the genetic algorithm strategy, can sometimes skip over very good layouts, or even the best. I will explain in a later post, coming soon.

Posted in Computer Science, Keyboarding Theory, Keyboards, Math, New Keyboard Layout Project, Programming | 2 Comments »

New Keyboard Layout Project: Overview

Posted by Michael Dickens on August 19, 2009

https://mtgap.wordpress.com/2009/08/18/new-keyboard-layout-project-efficient-genetic-algorithm-optimization/

For p = 48, b = 16, k = 1, o = 1024, q = 2048, the program got the best layout possible in just over fifteen minutes. Considering that to find the best layout by brute force would take a billion times longer than the universe has existed for, that’s a pretty impressive feat.

Even more impressive is q = 64. You might say, “Why in the heck was q so large in the first place?” My rationale was this: it’s the final round. You want to get the best possible layout. And even in the worst-case scenario, if q = 2048 the keyboard has a 99% chance of improvement. But it looks like that was excessive, because q = 64 has about a 50% chance of getting the best possible layout, and in only about ten minutes. (I ran it twice: one time it got the best layout, and the other time it got a layout that is very very close to the best, but not quite.) That all-star round with 1024 layouts and 2048 iterations was gobbling up a lot of time.

I am currently using this cost distribution. See my keyboarding page for an explanation of what these mean.

Inward roll:  -14
Outward roll:  -4
Same hand:      2
Same finger on...
    pinky:    100
    ring:      90
    middle:    70
    index:     55
Row change:    10
Home row jump: 40
	index: -30
To center:     10

Also, each position on the keyboard has a cost based on its difficulty to reach. These costs are not just based on my own assessment, but also on the placement of keys on some of the better keyboards out there.

 70 40 30 30 60   80 30 30 40 70
 10  4  0  0 30   30  0  0  4 10
 90 85 60 50 95   70 40 60 80 90

Normally the ring finger and pinky would cost 0 since no movement is required, but I wanted to keep E and T off of the pinky and E off of the ring finger. Those letters are far more common than any other, and it would put too much stress on those fingers.

And the best possible layout under this scoring system is:

k c f p b  j h u w .
o s a t d  l n e r i
q v , g z  ; m y x '

By the way, this layout is officially called MTGAP 3.2. You don’t have to worry about the version-numbering system; it’s a little erratic.

Is this really the best possible layout, or is the scoring system flawed? Let’s look at some of the problems with this layout.

-The fa/af digraph is fairly common. I assume that the program made it because the middle finger can handle same finger usage rather well (at least according to the scoring system). Also, if you’ve ever tried, it is exceptionally hard to find stuff to put on the same finger as ‘a’. It is usually placed on the pinky and then put with either a really rare letter like q or j, or with punctuation. But the algorithm thought it better to put a on the middle finger. Why?

To find out, I worked with rearranging some parts of the layout.

-You can’t switch i and a. i can only be paired with u, y, and punctuation. The spot above the middle finger is too good for y, so that won’t work. e is already using u and there isn’t really anything else for e to go with, so u is out. That just leaves punctuation. But the spot above the middle finger is still too good for punctuation. What does that leave? Pretty much nothing. f, though, is common enough that it can be placed in that spot. (By the way, if all this talk about letter frequency is confusing you, check out this graph.

-You can’t switch a and s. You end up with the exact same problem as you had initially: what do you put over the a?

-You can’t switch o and a. o has the same problem as a and i, only worse. Remember when I said that a is exceptionally hard to pair with other letters? Well, o and i have it even worse, and e has it worst of all.

So how have other layouts coped with this problem? By making sacrifices.

q w f p g  j l u y ;
a r s t d  h n e i o
z x c v b  k m , . /

Colemak copes with the problem by sacrificing some finger travel distance. Colemak has the lowest same finger usage of any layout I’ve seen, but it can only do this by making sacrifices. c is placed in a hard-to-reach position, for one.

Colemak actually copes remarkably well. Capewell and Arensito do not cope very well at all. They end up placing punctuation and rare letters where they shouldn’t be. Dvorak is even worse. So it looks like having the fa/af combination on the same finger is the best choice after all.

I will look for more potential problems later. Right now I’ve got some other fish to fry. As always, I welcome comments and feedback.

Posted in Keyboarding Theory, Keyboards, New Keyboard Layout Project | 8 Comments »

New Keyboard Layout Project: Efficient Genetic Algorithm Optimization

Posted by Michael Dickens on August 18, 2009

See part 1 and part 2.

I’m using a slightly modified algorithm, designed for increased performance.


Step 1: Create a pool containing p randomly-generated keyboard layouts.
Step 2: Score each keyboard according to a fitness function and sort the keyboards by score.
Step 3: Randomly delete half of the pool (giving preference to keyboards with lower fitness) and create a copy of each remaining keyboard.
Step 4: Mutate the copies by randomly swapping the positions of two keys m times.
Step 5: Repeat steps 2-4 until the best keyboard in the pool has not changed for b rounds.
Step 6: Place this best k keyboards in pool O and sort each keyboard in O by score.
Step 7: Repeat steps 2-6 until O contains o layouts.
Step 8: Repeat steps 2-4 using pool O until the best keyboard in the pool has not changed for q rounds.

I did some empirical testing and came up with an optimized algorithm. For p = 2048, b = 16, k = 32, o = 4096, q = 2048, it took five hours to come up with a layout with fitness 2304432 (remember that lower is better). But for p = 128, b = 16, k = 1, o = 1024, q = 2048, it took only one hour to come up with a layout with fitness 2304182, which is slightly better. Not only that, but the second set of values optimizes faster. I ran the first version twice, and each time came up with a different layout (one scored 2304432, the other scored worse). But when I ran the second version twice, I came up with the same layout both times. This means that it is probably the best possible layout given the criteria. Here’s the layout:


kcfpb jhuw.
osatd lneri
qv,gz ;myx'

Not bad, eh?

Soon, I will post a comparison of this layout and various other layouts. For now I’ll just say that this layout beats out MTGAP 2.0 on every criterion but one. Impressive, huh?

Posted in Keyboarding Theory, Keyboards, New Keyboard Layout Project | Leave a Comment »

Optimized Evolutionary Algorithm for Keyboard Design Part 2

Posted by Michael Dickens on August 11, 2009

Warning: Math-heavy post ahead. Read at your own risk.

In part 1, we looked at appropriate iteration numbers and mutation rates for when there is only one keyboard per pool. Let’s look at our algorithm:

Step 1: Create a pool containing p randomly-generated keyboard layouts.
Step 2: Score each keyboard according to a fitness function and sort the keyboards by score.
Step 3: Randomly delete half of the pool (giving preference to keyboards with lower fitness) and create a copy of each remaining keyboard.
Step 4: Mutate the copies by randomly swapping the positions of two keys m times.
Step 5: Repeat steps 2-4 until the best keyboard in the pool has not changed for b rounds.
Step 6: Place this best keyboard in pool O and sort each keyboard in O by score.
Step 7: Repeat steps 2-6 until the best keyboard in pool O has not changed for o rounds.
Step 8: Repeat steps 2-4 using pool O until the best keyboard in the pool has not changed for q rounds.

In this post, we will discuss the optimal value for b; that is, the number of rounds it iterates before it stops. Remember that it only stops if the best layout has not changed for b rounds. I will also discuss what happens when a keyboard gets “stuck”; that is, it is not yet optimal but there is no possible improvement.

Let’s look at when a layout will usually get stuck. Say every key is at its 2nd best possible position. The only way a mutation could improve the layout is if, when two keys are swapped, they both improve. Every key only has one possible better position (1 out of 29) so the chance of both keys improving is (1/29) * (1/29), or 1/841. Since the swap could go in either direction, we multiply the chance by two and get 1/420. So the chance of any particular mutation being an improvement is 1 out of 420. But there are 435 possible mutations. So the chance of at least one of them being an improvement is 1 - (419/420)^435, or ~0.65. Worst-case, the chance of finding this improvement is 1/435. So about 2000 rounds (1 - (434/435)^2000 ~ 0.99) are necessary to ensure that the improvement happens. But we can get away with a good deal less, since it’s likely that there will be more than one possible improvement.

But what if we’re satisfied with something worse? Then even fewer rounds are necessary. The chance of improvement is even higher if we are satisfied with every key being in the 3rd best position. Or the 4th.

Let’s assume that every key is in the 3rd best position. The chance of there being one possible improvement is ~0.67. We’d have to take about 2000 iterations to be 99% sure that we’ve found it. After only 500 iterations, we could be about 70% sure. But what if there are two possible improvements? Assuming that every key is in its 3rd best position, there is a 43% chance that there are two possible improvements. If there are two possible improvements, we can be 99% sure that we’ve found one of them after only 1000 rounds. So assuming that every key is in its best possible position, a reasonable value for b is around 500 to 1000.

But there is another factor to take into account: the size of the pool. Assume that the pool has 1000 keyboards in it. It is possible that one of these keyboards is better than all the others. Through the selection process, its “genes” will slowly take over the whole pool. So it’s entirely possible that every single keyboard is close “relative” to just one original keyboard. If they are all so similar, then the chance of improvement is higher since not just one layout could improve, but any layout could improve. So if there are 1000 keyboards then b doesn’t need to be so large. Just what b should be is harder to calculate.

Posted in Computer Science, Keyboarding Theory, Keyboards, Math, New Keyboard Layout Project, Programming | 4 Comments »

Optimized Evolutionary Algorithm for Keyboard Design Part 1

Posted by Michael Dickens on August 7, 2009

Warning: Math-heavy post ahead. Read at your own risk.

Trying to optimize a keyboard layout is tricky business. There are 30 factorial (30*29*28…) possible keyboard layouts. That’s about 10 to the 32nd power. This is far too many to search through every single possible keyboard layout to find the best. So an evolutionary algorithm (sometimes I call it a genetic algorithm, but there are subtle differences so that’s technically wrong) is a good way to find an optimal solution. This site provides a good introduction to genetic algorithms.

A keyboard optimization consists of several steps.

Step 1: Create a pool containing p randomly-generated keyboard layouts.
Step 2: Score each keyboard according to a fitness function and sort the keyboards by score.
Step 3: Delete the lowest-scoring half of the pool and create a copy of each remaining keyboard.
Step 4: Mutate the copies by randomly swapping the positions of two keys m times.
Step 5: Repeat steps 2-4 until an optimal keyboard is reached.

This is not the complete algorithm, as you will see later. And the fitness function is an entirely different matter. But even so, there are a few questions. What values should be used for p and m? How do we know when an optimal keyboard is reached?

I’ll start by answering that last question. I know of three ways to know when to stop. The first and simplest is to just run the algorithm for some predetermined number of rounds. The advantage to this is that it’s easy and doesn’t require much computing power. The disadvantage is that you don’t actually know if the resulting keyboard is the best you can get. To be very sure that the keyboard is the best you can get, you have to do a huge number of rounds, so if you really want to be sure then it’s not fast at all.

The second way is to stop when the best keyboard in the pool has reached a certain level of fitness. This can be tricky. You have to know what level of fitness you want. If you know that, this method can get you to exactly where you want but no better. The problem here is, what if it’s impossible to reach the desired level of fitness? Sometimes a keyboard will get “stuck” where it’s not yet at the optimal keyboard, but there is no possible improvement. Let’s imagine a scenario. Say that QWERTY is the perfect keyboard layout, and we’re trying to evolve towards it. QWERTY is of course not the perfect keyboard layout, but for the purpose of this exercise let’s say it is. Let’s say our algorithm has come up with this:

Current Optimal Keyboard-------QWERTY
QSCWD PO;IL------------------QWERT YUIOP
VEFBR UKYJM------------------ASDFG HJKL;
ZAXGT HN,./------------------ZXCVB NM,./

Let’s say that any possible change will make the keyboard worse. But it still hasn’t reached the optimal keyboard. So it’s stuck. It can’t change, so it can’t reach QWERTY. It has to get worse before it gets better. Are there any solutions to this problem? Perhaps; I’ll discuss this more later. What this shows for now is that the second method is not optimal.

The third method is this: look at the best keyboard layout in the pool and remember it. If the best layout stays the same for b rounds, that is, it isn’t replaced with any better keyboard, then we can be pretty sure that the algorithm will never find a better keyboard layout. This method can be unpredictable, but it is the most likely to efficiently find the best possible keyboard layout.

Now let’s revisit the problem of getting “stuck”. I know of three ways to fix this. Since these three are not mutually exclusive, any or all of them can be used.

The first method is fairly simple. Generate an optimized layout as described above. Then generate another optimized layout. Continue generating optimized layouts some number of times. Any of the three stopping methods described above can also be used here to decide when to stop. The difference here is that each resulting keyboard is created independently, so they don’t get “stuck”. Advantages: the layouts can be very different, and variety is good; getting stuck every time becomes extremely unlikely. Disadvantages: it’s very slow. To get really optimal results, this method can make the whole process take a thousand times longer or more.

The second method is to use roulette selection. Instead of deleting the worst half of the layouts in the pool, delete keyboards randomly. But not completely randomly: worse keyboards have a higher probability of being deleted. Advantages: it is much less likely that a layout gets stuck; it’s faster than the first method. Disadvantages: as with any random function, it’s unpredictable so it’s possible to completely miss a really good layout; this doesn’t matter so much, but it requires significantly more program code than there would be otherwise.

The third method involves increasing the value of m, the number of mutations. If there are more mutations per iteration, it will increase the potential for change. This allows a layout to get a lot better. But it also allows a layout to get a lot worse, so a high value for m will seriously slow down the program.

For most effective optimization, the first two methods will be used. Now let’s look at our new and improved algorithm.

Step 1: Create a pool containing p randomly-generated keyboard layouts.
Step 2: Score each keyboard according to a fitness function and sort the keyboards by score.
Step 3: Randomly delete half of the pool (giving preference to keyboards with lower fitness) and create a copy of each remaining keyboard.
Step 4: Mutate the copies by randomly swapping the positions of two keys m times.
Step 5: Repeat steps 2-4 until the best keyboard in the pool has not changed for b rounds.
Step 6: Place this best keyboard in pool O and sort each keyboard in O by score.
Step 7: Repeat steps 2-6 until the best keyboard in pool O has not changed for o rounds.
Step 8: Repeat steps 2-4 using pool O until the best keyboard in the pool has not changed for q rounds.

This is a bit longer, but still pretty simple. The remaining question is, what should the values be for the constants p, m, b, o and q?

Let us assume that p = 1 and m = 1 (that is, there is one layout in the pool, and a mutation swaps the positions of two keys). This makes it very simple to calculate b. We want to iterate long enough to be pretty sure that no improvement will be made. The keyboard that is least likely to improve is one where every key is in the best spot, except for two which are exactly swapped. So swapping those two keys is the only possible way to make the keyboard better. The probability of swapping those two keys is one out of 435 (two out of 30 chance to select one of the two keys multiplied by a one out of 29 chance to select the matching key).

Since If the keys to swap are being selected randomly, then b ≈ 1000. But if the key swaps are not actually random but are instead cyclical in a pseudorandom way, then after 435 iterations you can be guaranteed to hit the one swap that’s an improvement. So if there are no changes for 435 iterations, you can be positive that the keyboard is not going to get any better.

This can be extrapolated for higher values of m. Let’s say that m = 2. Worst-case scenario, the only possible improvement is two specific swaps. The probability of swapping those two pairs of keys is one out of 94612.5 (four out of 30 chance to select one of the four keys multiplied by a one out of 29 chance to select the matching key, multiplied by a two out of 30 chance to select a key from the remaining pair multiplied by a one out of 29 chance to select the matching key). We can then create a formula for any value of m where p = 1.

b = (1/29)^m * [(2m / 30) * (2(m-1) / 30) * (2(m-2) / 30) * . . . * (2(1) / 30)]

From this we can try to find an optimal value for m. We want to find a balance between mutability and efficiency. Perhaps the balance is as low as m = 1, since there are better ways to allow for mutability.

So we have m = 1 and b = 435. But should b really be such a large number? If it’s smaller, there will be a lower chance of reaching the optimal layout, but the program will run much faster. Instead of looking at the second best layout, let’s look at the third best. That is, there are two possible swaps that would be an improvement. The probability of getting one of these swaps in a random mutation is 1 out of 218. (This is of course an oversimplification; the second best layout might not be at all similar to the best layout. But this model works for our purposes.)

In general, if we are satisfied with the nth best layout, we should set b = (2n/30) * (1/29). You may say, Why would we compromise? Well, remember that we are later going to move on to an optimized pool O, and in this pool we can be more stingy. The average layout has about 218 possible improvements, so a layout with only, say, 50 possible improvements is going to be one of the better ones. To reach a layout with 50 possible improvements, only about 9 iterations are necessary. If we want a layout with only 5 possible improvement, 87 iterations are necessary. All things considered, that’s a pretty good equilibrium.

Now we must factor in what happens when we have p > 1; that is, there is more than one keyboard in the pool. Things become much more complicated. That will be the topic of discussion in part 2.

Posted in Computer Science, Keyboarding Theory, Keyboards, Math, New Keyboard Layout Project, Programming | 5 Comments »

 
%d bloggers like this: