AI designed keyboard layouts

[dessalines]

On desktop, I use the AI-designed Halmak Keyboard, and its had great results.

Rather than manually picking letter positions, Halmak was designed by an evolutionary algorithm, based on a given set of criteria, and sample text.

I designed the original english thumb-key layout manually, with trial-and-error, and based essentially on 3 criteria:

• Letter frequency
• Alternating thumbs
• Thumbs come from the bottom corners, so lower and edge tiles are easier than higher.

But I did not take into account things like bigrams / trigrams, and I don't know enough about evolutionary algorithms to do it.

Would anyone be interested in tackling this problem?

[domportera]

I started developing something to run an evolutionary algorithm on various thumb-key letter layouts (potentially with arbitrary dimensions, i.e. 3x3, 4x3). I know basically nothing about evolutionary algorithms but it seems like a fun thing to do. no promises though, it's not unlike me to not finish things lmao

I'm not sure that bigrams/trigrams are the best measure for two-thumb typing though, since the space bar and other punctuation can play a pretty big role. My plan is to just run the algorithm on [[some data set???]] of Normal Human Text and see what layouts come up

one of my key metrics here is thumb swipe direction - if the thumb swipes in the direction of its next key, then it's probably better

[dessalines]

Whoa nice! keep me updated on it's progress.

The most important metric to me, would be alternating thumbs bigrams, rather than swipe towards direction bigrams, but it'd be interesting to see what any of these come up with.

[domportera]

ya i think alternating thumbs are def more valuable. gonna have to set up a little "weights" system to tune what matters most.

but I just published a public version of my work in progress in case u ever wanna take a peek - https://github.com/domportera/KeyboardEvolution

[domportera]

I've done quite a bit of work on this so far and i'm pretty happy with how it's coming along. So far these considerations are more-or-less implemented

static readonly Weights FitnessWeights = new()
{
    Distance = 0.35,
    Trajectory = 0.5,
    HandAlternation = 1,
    HandCollisionAvoidance = 0.2,
    PositionalPreference = 0.6,
    SwipeDirection = 1
};

what are your thoughts on these weights in general? if they make sense. Hand collision avoidance refers to the sharing of the middle row by the thumbs

[dessalines]

Nice! Seems fine, but I'm sure you'll have to go through a process of testing and tweaking those values.

I know with a lot of these, they build an analyzer first, to measure how existing keyboards perform, given those set of criteria, and come up with a normalized score. Then they use evolutionary algorithms testing and refining tons of examples, thrown at the analyzer, to come up with the best possible layout.

But if you made the analyzer first, you could throw the messageease english, and thumbkey english keyboard at it, to see what their scores are.

[domportera]

yes i def will

so my approach is basically that each keyboard layout has its own "Fitness" and they are "fed" strings which then are "typed" to add to their overall fitness. I haven't yet fully implemented reproduction/mutation, but basically only the fittest x% of each round will be reproducing

currently keyboards are strictly randomly generated, though i was thinking of making a "preset" system so it doesnt have to reinvent the wheel every go-around

[HawksDarris]

Frequency Mapping

I like the frequency consideration of putting vowels on one side and consonants on the other, and I think you could take that to its logical conclusion to approach an optimum layout. I think it would be better to group keys based on their frequency as digraphs, and try to put the keys that are most likely to be beside each other on opposite sides of the keyboard. At present, there are some key combinations that are very common but aren't far from each other, so the user will generally type them with the same finger.

For example, in v4 keyboard, you have d in the corner of the e tile, but almost every English past tense verb ends with "ed," so that requires you to tap then slide on the same tile. It would be faster if d were located in the opposite column of e. Similarly, "th" is the most common digraph in English, and those are relatively close to each other on the v4 keyboard (maybe not enough to matter though).

I am looking at the code in the creator of the Halmak layout's genetics repo and it looks like it could be pretty easy to reproduce, but I am updating this comment now that I have seen domportera's approach because that actually looks like it will be better than what I was going to do lol

User-Driven Approach

If you implement this feature the user could make their own layout/configuration more easily, and open up the possibility of some user or group of users (other than us, I guess lol) figuring out how to get an AI to do it.

[domportera]

my repo is actually ready to be used I think! just needs to be run through an IDE as I don't have any command line arguments set up. settings are in Program.cs and KeyboardLayoutTrainer.Weights.cs. it currently is made to work with any json data set, just gotta set a tag to listen to. popular Reddit data sets work for me! just be mindful of ram bc my lazy ass loads the whole ass thing

[dessalines]

Sweet! Keep me updated, and I can add these layouts.

[domportera]

I recommend giving it a shot yourself! The results are heavily skewed by the weights and settings chosen. Project should be dead simple to run in an IDE, though I could compile a binary and create proper config support for you to mess around

[domportera]

I created a build with a settings file that is editable here, though you may want to check this commented file for what the settings do.

This is one of those applications you just wanna try to find the best settings for your needs through trial and error and then let it run for as long as possible (e.g. hours, days)

edit: it seems like my thumb trajectory calculations are flipped vertically - gonna have to investigate this

[dessalines]

I'm super busy with my other projects, so I'd like to see what its output looks like for some sample runs.

[penn5]

I wrote a script to generate keyboards using similar criteria to domportera's, it produced this layout:

+---+---+---+
|q  |   |   |
| c | j | p |
| z |   |   |
+---+---+---+
|x  |   |   |
| r | h | eg|
|f v|b k| o |
+---+---+---+
|l  |   |  y|
| n | t | i |
|s m|w d|u a|
+---+---+---+

[dessalines]

Doesn't look bad, but its also not placing the top used letters on the center keys. s and a probably shouldn't be swipes.

[penn5]

It's weighted quite heavily against using the top row of keys for frequent letters. I found that it's actually fine in usage for these letters.
I'll be open sourcing the code used to generate the layout anyway, so you will be able to tune the weights as you want.

[domportera]

Here's one layout I generated after 1000 generations. I think there's room for improvement in the weights used, though it's very trial-and-error. I also tried to set the weights to something that I think penn5 and dessalines would prefer, though my own weights (and even keyboard dimensions) would differ, and I'll be running those as well. For example, I think FitnessWeights.PositionalPreference (i.e. prefer keys towards the center/bottom, avoid the top row) should be 0 - I want to let go of any assumptions the weights provide about what is most efficient and let the results arrive there naturally - I think they would given the current location of the space bar.

I also think that diagonals should be wherever possible, which can be specified by the RedistributeKeyCharactersBasedOnFrequency in accordance with the FitnessWeights.CardinalPreference vs FitnessWeights.DiagonalPreference or will arrive naturally by increasing the keyboard dimensions

I also like the idea of a 4x3 layout with the system/modifier keys in either in the center with two columns on either side, or duplicated on both sides. We have available horizontal real estate currently, and the fitness levels obviously benefit from additional keys and fewer swipes.

I've also been toying with the idea of having a complete mirrored layout on either side of the center modifier row. Currently my system is not equipped to handle duplicate keys in a layout though.

Something I may also want to do is make "trajectory" calculations only apply in the case that the same thumb has to be used twice in a row.

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

Using the following settings & weights

  "ParentCount": 2,
  "ChildrenPerParent": 20,
  "GenerationCount": 1000,
  "EntriesPerGeneration": -1,
  "Seed": -1,
  "PresetType": "ThumbKeyEngV4NoSymbols",
  "CharacterSetString": "abcdefghijklmnopqrstuvwxyz\u0027",
  "UseStandardSpaceBar": true,
  "MutationFactor": 1.0,
  "UseRandomMutation": true,
  "MutationExponent": 2,
  "UseKeySpecificSwipeDirectionPreferences": false,
  "RedistributeKeyCharactersBasedOnFrequency": false,
  "AllowCardinalDiagonalSwaps": true,
  "PreferSwipesInOppositeDirectionOfNextKey": false,
  "FitnessWeights": {
    "Distance": 0.3,
    "Trajectory": 0.5,
    "HandAlternation": 1.5,
    "HandCollisionAvoidance": 0.2,
    "PositionalPreference": 0.05,
    "SwipeDirectionPreference": 0.1
  },
  "CardinalPreference": 0.4,
  "DiagonalPreference": 0,
  "CenterPreference": 1,
  "CharacterSubsitutions": [
    {
      "Original": "\u2019",
      "Replacement": "\u0027"
    }
  ],
  "KeysTowardsCenterWeight": 0.1,
  "PositionPreferencesSerialized": [
    {
      "Dimensions": {
        "ColumnX": 3,
        "RowY": 3
      },
      "PositionPreferences": [
        [
          0.4,
          0,
          0.4
        ],
        [
          1,
          0.7,
          1
        ],
        [
          1,
          1,
          1
        ]
      ]
    },
    {
      "Dimensions": {
        "ColumnX": 4,
        "RowY": 3
      },
      "PositionPreferences": [
        [
          0.2,
          0,
          0,
          0.2
        ],
        [
          1,
          0.8,
          0.8,
          1
        ],
        [
          1,
          1,
          1,
          1
        ]
      ]
    },
    {
      "Dimensions": {
        "ColumnX": 4,
        "RowY": 4
      },
      "PositionPreferences": [
        [
          0.4,
          0,
          0,
          0.4
        ],
        [
          0.9,
          0.7,
          0.7,
          0.9
        ],
        [
          1,
          1,
          1,
          1
        ],
        [
          1,
          1,
          1,
          1
        ]
      ]
    }
  ],

[dessalines]

Nice. The bigrams and trigrams seem okay as well.

Let me know if you'd like any of these added to test them out.

[penn5]

My code does trajectory only in the case of repeated thumb. But it is much less customisable than yours. Unfortunately I don't know enough C# to help with yours, but I do prefer setting bottom weighting to 0 to be honest.

It's interesting that your algorithm uses 1000 iterations - it may be more efficient to use a hill-climbing algorithm which will eventually reach an optimal state. Essentially you just say that all generations are defined by swapping two keys (or a key with a gap). I found it very efficient on my machine.

[domportera]

nice! good thinking.

GenerationCount can be specified in the settings, I just chose 1000 this go-around somewhat arbitrarily. by hill-climbing - do you essentially mean "stop calculating once your improvement rate nears zero"? that would be simple to implement in my code for some instances, for example when you're looping through a consistent data set each time (i.e. if EntriesPerGeneration<= 0, it will consume the entire data set for each generation). but if cycling through a much larger data set in chunks it may not work, as different groups of texts will yield different fitness levels for the same layouts.

Currently, my generations are characterized by MutationFactor, UseRandomMutation, and MutationExponent, which all work together to determine what percentage of characters within a layout are shuffled around.

Here's a glimpse into how the variation between generations works

 public static void Reproduce(KeyboardLayout parent, Span<KeyboardLayout> childrenToOverwrite)
    {
        Key[,] parentKeys = parent.Traits;

        var random = parent.Random;
        float multiplicationFactor = 1f;

        foreach (var child in childrenToOverwrite)
        {
            child.OverwriteTraits(parentKeys);

            if (UseRandomMutation)
            {
                multiplicationFactor = random.NextSingle();

                if (MathF.Abs(MutationExponent - 1f) > 0.0001f)
                    multiplicationFactor = MathF.Pow(multiplicationFactor, MutationExponent);
            }

            float mutationFactor = MutationFactor * multiplicationFactor;
            child.Mutate(mutationFactor);
        }
    }
    ```

[penn5]

I see. Our ideas are quite similar but you're taking an unneccesarily complex approach to reproduction.

Given a "parent", we are trying to find a number of similar layouts. And the goal of the overall algorithm is to find the best layout that can exist, according to some rating function. If we define the "neighbour layouts" of a "parent" as all layouts which are identical to the parent, apart from two key spaces which have been swapped, we will be able to enumerate all states by reproduction. The trick is, you don't need to do anything random. Since there is always a single best state, it's very likely that taking the best state from any given position will get you closer to that single ideal state.

So, there's no need to be random. Just take the best neighbouring state and use that one.

Of course, you have to choose a starting layout. I did this by inputting the one used in ThumbKey, but you could also do it randomly.
A major enhancement to the algorithm is to implement stochastic hill climbing. This is because there are a number of issues with normal hill climbing: https://miro.medium.com/v2/resize:fit:672/1*ymMUv1hzqBYPL-fErH7vIQ.png

When there is no "higher" place to go (a neighbour layout with a better score) the algorithm just stops. Instead, it can restart with a new random layout and try to find a new best state, and at the end we pick the highest peak.

Baeldung has a good explanation of hill climbing if you're confused at any point

[domportera]

ah I see what you mean here, this makes sense to me. I'm taking a pretty dumb brute-force approach that may be better served by a more methodical approach like this one. thanks for filling me in on the science!

The reasons I did it this way were to both capitalize on the strengths of each layout (i.e. search neighboring layouts) at the same time as exploring other layouts if none of the current parents are ideal. If those more random layouts are better, they will become the new parents. I believe this expedites the process of getting 3/4 there, but the last 1/4 is asymptotic time at best

It's clear, however, that this approach requires a static data set, rather than one that has the potential to cycle (as in my current implementation if specified in the config) and for something as complex as language that should probably be as large as possible (the current one im working with has ~868,000 valid reddit comments). Running this properly to its conclusion (i.e. investigating every potential layout) has the possibility of being an EXTREMELY time consuming process, depending on breadth of the character set, though it's nice to have a mathematically defined endpoint.

[penn5]

My evaluation function was based on bigram frequency, rather than using full phrases. Using a mix of the two is probably the best solution.

[domportera]

I am definitely partial to using conversational texts as reference. I don't entirely trust a survey of literature for something like a daily conversation driver. That being said, bigrams, trigrams, quadrigrams, etc could be derived from the dataset as a means of optimization

[penn5]

Agreed. Use bigram frequency to find a half-decent layout quickly then improve it using full texts, imo

[jytou]

I think it would be better to group keys based on their frequency as digraphs, and try to put the keys that are most likely to be beside each other on opposite sides of the keyboard.

Most common digraphs on a modern keyboard are best typed using rolling motions on one hand rather than alternating hands. Think how easy, fast and accurate it is to type “qsdf” in Qwerty vs “qmsl” and you’ll get my point. Alternating hands was justified with purely mechanical typewriters because rolling wasn’t really possible when the keys needed so much weight and depth during pressing them, and alternating hands could help the fingers by using at least partially the wrists and forearms to type adjacent letters. But on modern keyboards, it doesn’t make much sense anymore.

[dessalines]

This is a thumb-based keyboard, so "rolling" doesn't make any sense.

[jytou]

This is a thumb-based keyboard, so "rolling" doesn't make any sense.

Indeed, sorry for the out-of-context comment. It definitely makes sense for “normal keyboards”, but totally irrelevant here.