Total cost of irregularity is affected by nomalization of ngram weights (using normalize.py)

[fredsilon]

Issue

Default ngrams are compared, one time not normalized, one time normalized using normalize.py. The resulting irregularity cost are expected to be equal, because the relative n-grams' distribution is unaffected by the normalization script. However, currently this is not the case.

Steps to reproduce

1. fresh clone of repository: git clone https://github.com/dariogoetz/keyboard_layout_optimizer.git
2. cd keyboard_layout_optimizer
3. cargo build --release
4. Prepare normalization (copy default ngrams)
   cp -r ngrams/deu_mixed_wiki_web_0.6_eng_news_typical_wiki_web_0.4 ngrams/deu_mixed_wiki_web_0.6_eng_news_typical_wiki_web_0.4_norm
5. Create normalized default ngrams:
   python scripts/ngrams/normalize.py ngrams/deu_mixed_wiki_web_0.6_eng_news_typical_wiki_web_0.4_norm
6. Evaluate default ngrams (here for noted layout)
   ./target/release/evaluate -n ngrams/deu_mixed_wiki_web_0.6_eng_news_typical_wiki_web_0.4 "zyuaqpbmlfjßcsieodtnrhvxüäöwg,.k"
   Irregularity Cost: 11.17
7. Evaluate normalized default ngrams (here for noted layout)
   ./target/release/evaluate -n ngrams/deu_mixed_wiki_web_0.6_eng_news_typical_wiki_web_0.4_norm "zyuaqpbmlfjßcsieodtnrhvxüäöwg,.k"
   Irregularity Cost: 16.93

Assumption of cause

I think there is an issue with layout_evaluation/src/metrics/trigram_metrics/irregularity.rs:

The sqrt not only affects the cost but somehow also the weighting.

[dariogoetz]

This might be due to the way the cost per trigram for the individual bigram metrics on the trigram-components are aggregated into the "irregurality" metric.

This is done with the formula (1.0 + first_bigram_cost) * (1.0 + second_bigram_cost) - 1.0 so that if one of the trigram's bigrams has no cost, the trigram can still have the cost of the other bigram (see layout_evaluation/src/metrics/trigram_metrics/irregularity.rs:67).

If this is simplified to first_bigram_cost * second_bigram_cost then (at least in your example) the numbers for the normalized and unnormalized corpus are identical.

However, this way, one loses the property to have costs for a trigram if one of the two components has no cost.

[fredsilon]

How is irregularity defined?

Citing README.md

irregularity - How often are the first and the second bigram in a trigram "bad" (wrt. to all bigram metrics)?

I read it as (by using an example): The trigram with bigram cost b1 = 51 and b2 = 51 should be "more irregular" than one with bigram costs b1 = 100 and b2 = 2. The core idea might be, that irregularity is high if both bigrams are costly, not just one of them. (even if the sum b1 + b2 is the same for both examples). That means one bad bigram is directly followed be another bad one.

Current individual irregularity cost formula rewritten as:
first_bigram_cost * second_bigram_cost + first_bigram_cost + second_bigram_cost:

Three arguments for removing the 2nd and 3rd term, und just leaving the first term:

1. The terms first_bigram_cost and second_bigram_cost are already part of the "standalone"-bigram cost itself. Their frequencys in the corpus are already evaluated using 2-grams.txt as source.
2. If treating "cost" as a physical quantity and calling its unit c, the original formula would add the units to c² + c ... which wouldn't work. (Maybe cost could somehow be seen as being related to one or several of physical quantities like strain, work, distance, time)
3. first_bigram_cost * second_bigram_cost would only be zero, if one of them is zero. However using my interpretation of the definition from README.md, this might be fine, as then the trigram is by definition not irregular.

---

Maybe also move sqrt from total_cost to individual_cost. (Supporting argument see ¹)

Maybe one of those versions for individual_cost:

Alternative 1:
sqrt(first_bigram_cost * second_bigram_cost) + first_bigram_cost + second_bigram_cost

(Only taking sqrt on the first term would retain the "physical unit argument".)

Alternative 2:
sqrt(first_bigram_cost * second_bigram_cost)

Alternative2 would be the geometric mean of both bigrams … don't know, if this is relevant … but maybe it could be related to the definition of irregularity somehow.

---

Slightly offtopic: I later want to play around with a different version of irregularity.

I define a irregularity factor irreg_factor (that ranges from 0 to 1) as:
irreg_factor = min(first_bigram_cost, second_bigram_cost) / max(first_bigram_cost, second_bigram_cost)

Which would be 1, if both bigrams are equal and would be between 0 and 1 for all other cases. (negative bigram_costs would be defined as 0).

• irreg_factor = 0, means ... not irregular ... only one bigram is bad, the other is fine (most likely due to a handswitch in that bigram)
• 0 < irreg_factor < 1 means, both are bad, but one is "less bad" ... therefore not totally irregular.
• irreg_factor = 1, means ... totally irregular ... both bigrams are equally bad

The factor could also be raised to the power of 0.25, 0.5, 2, 3, 4, whatever ... if the linear definition of "irregularity" does not fit well ... while still ranging from 0 to 1.

Of course the cost should also somehow take into account the absolute "badness" of one or both bigrams.

Could be the weighted average of both bigrams:
(a * max(first_bigram_cost, second_bigram_cost) + b * min(first_bigram_cost, second_bigram_cost)) / (a + b)

I also would remove sqrt from the total_cost function.¹

So we would have:

n = 1
a = 0.8
b = 0.2

irreg_factor = (min(first_bigram_cost, second_bigram_cost) / max(first_bigram_cost, second_bigram_cost))^n

weighted_average = (a * max(first_bigram_cost, second_bigram_cost) + b * min(first_bigram_cost, second_bigram_cost)) / (a + b)

individual_cost = irreg_factor * weighted_average

total_cost = sum(individual_cost[i])

Hopefully this is also not sensitive to ngram normalization.

Of course bigr_cost_1=100; bigr_cost_2=80 should induce more irregulary-cost than bigr_cost_3=80; bigr_cost_4=80. Which is not the case for e. g. n=1, a=0.5, b=0.5 … Hmm however, does it have to be like that? Still, the individual bigram cost are already part of 2-ngrams.txt cost. (I have to play around with this a little bit) ^^

---

Footnotes

1. My argument for removing sqrt from total_cost (it may reside at indiviual_cost, if there is cost1*cost2): All individual_cost should contribute equally to the total_cost. That means: By this definition, "irregulary" should be an individual rating of each individual trigram movement, not one of the whole collection of trigram movements of the curpus.
   Example: With individual costs i ... i1=100 and i2..i4=4, it should be total_cost_0 = sqrt(i1) + sqrt(i2) + sqrt(i3) + sqrt(i4) = 16. With total_cost_1 = sqrt(i1+i2+i3+i4) = 10.58 only the relatively huge i1 is contributing to the total_cost.
   (Could be intentional of course) ... However, sqrt somehow relates the individual costs indirectly.
   Another example:
   i1=100 and i2..i4=4 and i5=100 ... Intuition would suggest, that total_cost_2 should be >= 20 (related to the first example total_cost_1). However actually, it's
   total_cost_2 = sqrt(i1+i2+i3+i4+i5) = 14.56 ↩ ↩²

[dariogoetz]

Your argumentation makes sense to me. In particular, the point that the "linear" parts are already accounted for in the bigram metrics.

Regarding your suggestion of pulling the square root into the sum, I see your point as well. The square root of the sum approach is a heritage from the original implementation of the metric by ArneBab.

Applying your mentioned changes would be breaking many of the results of the existing layouts in the database, so I am not sure how to proceed.

[fredsilon]

Regarding the "linear" parts. I may have to revise my comment a bit.

While it is true, that those are already part of the standalone bigrams, they will however be weighted differently when part of irregularity due to the trigram-metric-weight and maybe also due to different fractions within 2-grams or 3-grams. (I think don't have a good complete overview of the correlation between bigrams, trigrams, their weighting and fractions, yet ^^).

---

Anyway regarding not breaking results:

One approach could be:

1. Keep the metric irregularity without breaking it.
2. Optional: Add some sort of "deprecated" or "hint" message to the evaluation output for the current metric. (Especially if the ngram-normalizing issue is really considered a bug …)
3. Thanks to your modular approach for implementing the metrics, one could add a new metric with a new name … name to be decided.

Another approach could be:

1. Revise irregularity metric with braking changes
2. Re-balance the default evaluation parameters:
   One could take the database results and try to minimize the impact to total cost by using the "least squares method" to find the default metric-weight of the revised irregularity.

---

I think I would go for solution one and implement a new metric with a new name. One could still take the idea of choosing a default metric weight for the new version with the "least squares method" if this is worth the effort … but this makes only sense, if it is seen as a replacement, which would only be the case, if "new irregularity" somehow aims for comparable layout flaws. I guess, time will tell how a revised metric will behave … which is also an argument to keep the old one and implement the revised version as a new metric.