Genetic evolution & simulated annealing

[Glitchy-Tozier]

Hi, I was just wondering why you chose to use genetic evolution as your strategy to find an optimized layout. :)

From my research, simulated annealing seems really good in use-cases like this one. (Optimizing a keyboard seems pretty similar to the traveling salesman problem.)

[dariogoetz]

To be honest, I don't recall the reasoning. I believe that I was looking for optimization algorithms on crates.io and stumbled across genevo. It sounded interesting to me and I wanted to try it out. Many other crates that I found were more suited for "classical" n-dimensional space problems. I am sure that simulated annealing will perform well for the keyboard layout optimization, too.

Do you know a crate that could be used? Adding a new optimization algorithm next to the genevo one should not be hard. I just recently tried out the abc-algorithm (artificial bee colony). You can find it as a separate binary in the evolve-keyboard-layout crate. If you are interested, you can try adding a simulated-annealing approach. I would be happy to help and interested to see how it performs.

[dariogoetz]

Do you have a good idea?

Here's how I did it (I only implemented this for trigrams, but it could certainly also be applied to something like split_uppercase_letters). I had a HashMap with key = trigram-string and value = trigram-score.

{
  "aaa" : 938,
  "aab" : 689,
  usw,
  "sch" : 3790,
  usw,
  "zzz" : 278,
}

For each layout, I decided what trigrams had changed compared to the last one, then overwrote those trigrams in the HashMap. If I recall correctly, the testing-function returned that updated HashMap. Afterwards, I only had to sum up all values of the HashMap.

Basically, when comparing the old evaluation-function to the new one: Old: trig_score = evaluate(layout, all_trigrams); New: trig_score_hash_map = evaluate(layout, necessary_trigrams, old_trig_hash_map);

The issue I see with this approach (at least in my current realization) is that a change of individual keys leads to a change in the modifier expansions for corresponding uni-/bi-/trigrams (if the hand of a symbol on a higher layer changes, other modifier keys need to be pressed). Other modifier expansions mean other weights on the expanded ngrams. This means that not only the ngrams directly, but also the secondary bigrams (that are computed from the trigrams) change. The additional increase of "common bigrams", will then again change weights.

In ArneBab's code, the expansion of the trigrams is simplified a lot. He does not differentiate left and right modifiers (at least for trigrams; for uni- and bigrams, he does), that is why in his situation such an approach may work better.

I assume that in your example, the already expanded trigrams are shown (no uppercase symbols appearing anymore), otherwise, there would be several more steps before summing up would be possible. In "my" situation, where for each higher layer symbol, the corresponding modifiers of "the other hand" were taken, it is not anymore possible at that stage to determine which fractions of the trigrams relate to which "original" trigrams so that a chance could be tracked.

Example:
Suppose, we only have the trigrams "a-B-C", "d-E-C" and all symbols are on the right hand. This would give the following expansions (LS is left shift):
a-B-C -> a-b-c, a-LS-c, a-b-LS, a-LS-b, LS-b-c, LS-b-LS, b-LS-c, LS-LS-c
d-E-C -> d-e-c, d-LS-c, d-e-LS, d-LS-e, LS-e-c, LS-e-LS, e-LS-c, LS-LS-c

In particular, there is an expanded trigram that appears in both trigrams these would be aggregated in your HashMap.

If now the layout would be switched such that "b" is on the left hand (while acde remain), the corresponding expansion of a-B-C would not contain the expanded trigram LS-LS-c anymore; it would be RS-LS-c. In your HashMap, we would need to change the weight only for part of the entry for "LS-LS-c" as the part from the expansion of "d-E-C" remains the same.

Now imagine that the bigram "LS-c" is very common (for some reason) and leads to an additional increase (see the finger_repeats function with the critical value in ArneBab's code) if the weight of the secondary bigram "LS-c" coming from "LS-LS-c" is accounted for, but not, if the secondary bigram was gone. If now the switch of the letter "b" happens, the trigram "LS-LS-c" will be a "RS-LS-c" and the corresponding secondary bigram vanishes (or rather now is "RS-c") -> the additional increase does not happen -> "LS-c" has a very different weight overall.

I believe, that puzzling out what will change for "small changes to the layout" along all of these dependencies is quite error prone and difficult. That is why I, myself, am not fearless enough to try :)

[Glitchy-Tozier]

To be honest, I'm not 100% sure what "expansion of trigrams" means. How do we go from this "a-B-C" to this a-B-C -> a-b-c, a-LS-c, a-b-LS, a-LS-b, LS-b-c, LS-b-LS, b-LS-c, LS-LS-c instead of something like this:

a = a
B = LS + b
C = LS + c

=>  a-B-C = a-LS-b, LS-b-LS, b-LS-c

I don't understand how that many weird letter combinations can be created from the trigram a-B-C. Could you explain it to me?

[dariogoetz]

You can find an explanation of the expansion on ArneBab's page (though in German): https://hg.sr.ht/~arnebab/evolve-keyboard-layout, section called "1.4. Buchstabensplitting".

The idea is that if you use a modifier, you press it (shortly) before the actual key and hold it until just before hitting the next key. Each combination you have in mind for the base key (a/b/c) then also applies to the corresponding modifier.
aBC ->
a-Shift(b)-c (Shift of b is pressed directly after a and released just before pressing (shift of, but close enough to) c),
a-b-Shift(c) (Shift of c is pressed directly after b),
a-Shift(b)-Shift(c) (Shift of b is pressed directly after a and released just before pressing Shift of c),

Also, as the key and its modifier are pressed and released shortly after one another (however, the base key is always pressed after the modifier), each individual higher-layer key itself gives new bigrams (B -> Shift(b)-b). This gives:
aBC ->
a-Shift(b)-b (Shift of b is pressed directly after a and pressed just before pressing b),
Shift(b)-b-c (Shift of b is pressed directly before pressing b and b is released (together with its Shift) before pressing (Shift of, but close enough to) c),
Shift(b)-b-Shift(c) (Shift of b is pressed before b and b is released (together with its Shift) before pressing Shift of c),
b-Shift(c)-c (Shift of c is pressed directly after b and pressed just before pressing c),
Shift(b)-Shift(c)-c (Shift of b is released just before pressing Shift of c and Shift of c is pressed before pressing c).

Note that for keys on a layer that requires two modifiers, also trigrams from only one symbol can occur: greek alpha -> Mod3-Mod4-a and Mod4-Mod3-a. Trigrams on those layers can expand to something like 30 trigrams involving modifiers.

[Glitchy-Tozier]

So, I finally have stored up enough brain power to re-read your last two messages and reply.
Apart from it being scary, I still don't quite see how an elaborate splitting of ngrams breaks the HashMap-plan. The storage of data might indeed become more complicated, but (as far as I can see) still possible.
Using your example ( a-B-C -> a-b-c, a-LS-c, a-b-LS, a-LS-b, LS-b-c, LS-b-LS, b-LS-c, LS-LS-c), this would be the result:

HashMap {
    "a-B-C": HashMap {
        "a-b-c": 93619,
        "a-LS-c": 32894,
        "a-b-LS": 9389,
        "a-LS-b": 892394,
        "LS-b-c": 9382,
        "LS-b-LS": 98293,
        "b-LS-c": 982,
        "LS-LS-c": 922,
    }
    "d-E-C": HashMap {...}
}

This could then be iterated through, subtracting the individual scores from the respective metrics (finger-repeats, for example).

That being said, my main thought is that it seems somewhat wasteful to re-calculate large parts of layouts when very few keys are switched. This may be most noticeable in Simulated Annealing, but it should also help when using other algorithms; I assume, especially towards the end, that you won't be making many enormous changes on a pretty optimized layout.

---

Something else, what are the biggest time-wasters overall? I think you once told me that it wasn't even the evaluation itself. Can't find that conversation though.

[dariogoetz]

The idea to remember the expansion for each ngram is good, I think. But I still see issues:

1. It would still be very complex to keep track of all the changes that need to be "rolled back" and "computed new" for each ngram.
2. There is a mechanism in place that increases the weight of individual (expanded) ngrams if their weight exceeds a certain threshold. Such a mechanism exists in the ngram mapper as well as in some metrics (e.g. finger repeats). This assumes that the weight of the expanded ngrams is already aggregated from all unexpanded ngrams where they might appear from. In your "HashMap" idea, these individual occurrences are separate (grouped by the unexpanded ngram that they are generated from) and would need to be aggregated first.

Anyway... I don't want to say that it's impossible, only it will be very complicated and prone to errors. Maybe I see it too pessimistically or missed some things that might make it possible.

But you are very welcome to give it a try. :)

Regarding you question about which operations take time, here is a flamegraph of 100 random evaluations:

You can see that the main sections are:

1. groupby_sum: Aggregate all expanded ngrams after expansion and sum their respective weights.
2. split_trigram_modifiers: Expand the trigrams.
3. evaluate_trigram_metrics: Trigram metric evaluation, split in half between irregularity and the rest (from the rest, secondary_bigrams has the largest portion)