Slideshow Dessalles Telecom Paris

Understanding Artificial Intelligence
through Algorithmic Information Theory

Morphological Analogies

Morphological analogies

Morphological analogies concern the morphology of words.

semantic analogy: "king is to queen as man is to woman"
morphological analogy: "king is to kings as queen is to queens"

Morphological analogies match different grammatical forms of a same word. They concern the symbols themselves, not their semantics.

Example of morphological analogy

Latin’s accusative case

rosa : rosam :: vita : x

Source: transformation of "rosa" into "rosam".
Possible interpretation: add letter "m" at the end of the radical.

Target: the same transformation may apply to the target ("vita"). The result would be x = "vitam".

BUT other transformations are also possible (for instance: always answer "rosam")
Can we compute the ‘correct’ transformation?

Computing morphological analogies

In (Murena et al., 2020), we introduced a simple language to implement morphological transformations.

let, ?0 : ?0, m, let
mem, ?0 = rosa
::
mem, ?0 = vita

line 1: define a function based on a variable ?0 that adds m to it
line 2: Call this function with variable ?0 = rosa
line3: Move to the second half of the analogy
line 4: Call this function with variable ?0 = vita

Computing morphological analogies

rosa : rosam :: vita : x

1. We use this simple language to try transformations that can solve the analogical equation.

2. We only keep transformations that match the two first terms (source) (rosa → rosam) and can also be applied to the third term (in the target) (vita).

3. The algorithm is almost brute force, as there are few such candidate transformations.

4. We keep the simplest transformation.

Computing morphological analogies

And it works!

The algorithm has been used to guess the fourth term of morphological analogies.

Our algorithm based on minimum of complexity (here named NLG_COMP) favourably compares with a state-of-the-art method NLG_PROP (Fam & Lepage, 2018) on the dataset SIGMORPHON’16 . . .

Computing morphological analogies

This example illustrates the fact that Kolmogorov complexity can inspire powerful learning algorithms. 🙂