Machine Learning and Algorithmic Information

Epicurus    341–270 BC

Principle of multiple explanations:
If more than one theory is consistent with the observations, keep all theories.

Sextus Empiricus    160-210

Validity of inductive reasoning:
‟When proposing to establish the universal from the particulars [...] induction will be insecure, since some of the particulars omitted in the induction may contravene the universal; while if one is to review all, one will be toiling at the impossible, since the particulars are infinite and indefinite.”

William of Ockham 1287-1347

Occam’s Razor Principle:
Entities should not be multiplied beyond necessity

Thomas Bayes    1701-1761

Bayes’ Rule:
The probability of hypothesis H being true given some data D is proportional to the learner’s prior belief in H multiplied by the conditional probability of D given H.

• Principle of multiple explanations
• Validity of inductive reasoning
• Occam’s Razor Principle
• Bayes’ Rule

These principles are often insufficient for determining the best induction.
For ages, the problem of induction has been considered to have no general solution...
until 1964, when Ray Solomonoff solved it by creating
the Algorithmic Information Theory framework.

A is to B as C is to D

    
If R is a relation that holds between A and B: R(A,B)
then the analogy says that the same relation holds between the two pairs: R(A,B) and R(C,D).

Understanding an analogy means:
find the most appropriate relation R

A : B :: C : D

Following (Cornuejols, 1996; Cornuejols & Ales-Bianchetti, 1998), we may say that "the most appropriate relation R" is the one that makes the quadruplet (A,B,C,D) simplest
or, in other words,
the one that achieves the best compression.

This is a special case of the induction principle.

A : B :: C : D

Such an analogy 𝒜 is often considered to obey the following axioms:

• identity:    𝒜(A,B,A,B)

Complexity minimization explains why these properties generally hold.

    
We call analogical equation the problem of finding the missing term x in an analogy:

A is to B as C is to x

Examples:

• Paris is to France as Helsinki is to ... ?
• ABC is to ABD as IJK is to ... ?

A : B :: C : x

\(\mathbf{x} = argmin(K(A, B, C, \mathbf{x}))\)

A : B :: C : x

abc : abd :: ppqqrr : x

abc : abd :: ppqqrr : x

Why should we consider it a "better" solution than, say, x = ppqqrd?

abc : abd :: ppqqrr : x

We have to compare two rules:

• increment the last item
• replace the last letter by d

This may explain why x = ppqqss would appear smarter.

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

rosa : rosam :: vita : x

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.

    
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    . . .

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

Prototype-based models can be used in unsupervised learning to group similar data points together (e.g. in marketing or recommender systems).

Prototype-based models can be used in unsupervised learning to group similar data points together.

A prototype is a point of the input space used to provide information about the distribution of data points.

Prototype-based models can be used in unsupervised learning to group similar data points together.

A prototype is a point of the input space used to provide information about the distribution of data points.

Intuitively, data are distributed "around" the prototypes.

One of the most famous prototype-based methods in machine learning is the K-Means algorithm.

Several improvements have been proposed (Learning Vector Quantization, Online Learning Vector Quantization, Self-Organizing Maps, Neural Gas algorithms, etc.).

One of the most famous prototype-based methods in machine learning is the K-Means algorithm.

You can watch nice Neural Gas demos

   see →

here

   see →

and there

Prototype-based models can be seen as compression methods:

Instead of describing data points by specifying their absolute coordinates,

Prototype-based models can be seen as compression methods:

Instead of describing data points by specifying their absolute coordinates,
one considers their coordinates relative to the closest prototype.

Prototype-based models can be seen as compression methods:

Instead of describing data points by specifying their absolute coordinates,
one considers their coordinates relative to the closest prototype.

We get smaller numbers, hence the compression.

The complexity of a point \(x_j\) in the dataset \(X\) is bounded by the complexity of its coordinates \((x_{j_1}, \dotsc, x_{j_d})\): $$ C(x_j) \leq C(x_{j_1}) + \dotsc + C(x_{j_d}).$$ where the complexity of coordinates depends on the precision \(\delta\) used to convert them into integers.
We get a "naive" upper bound of the complexity of the whole dataset \(X\): $$C(X) \leq \sum_j C(x_j).$$

If prototypes \(\{p_k\}\) are introduced, the complexity of \(X\) is now: $$ C(X) \leq \sum_k C(p_k) + \sum_i C(x_j|\{p_k\})$$ where: \(C(x_j|\{p_k\}) = \min_k C(x_j-p_k).\)

If the dataset exhibits some structure, suitable prototypes can be found and this estimate of \(C(X)\) will turn out to be significantly smaller that the "naive" one (hence the compression).

Conversely, and quite remarkably, this expression can be used to find the best prototype set \(\{p_k\}\) (Cilibrasi & Vitányi, 2005).

Now consider a classification task as an example of supervised learning.
The problem is to associate a label (e.g. blue/red/dark) to each data point.

Now consider a classification task as an example of supervised learning.
The problem is to associate a label (e.g. blue/red/dark) to each data point.

Prototype-based models are routinely used for this.

In doing so, they offer a compressed version of the classification.

In a classification task, we consider a dataset \(X\) of \(|X|\) points \(x_j\). Each \(x_j\) is supposed to belong to a class labelled as \(y_j\). The problem is to learn which label \(y_j\) taken from the set of labels \(Y\) corresponds to \(x_j\).

The complexity of the classification is bounded by the amount of information required by rote learning. $$C(\{(x_j, y_j)\} | X) \leq \sum_j C(\{y_j\}) \approx \sum_j |X| \times \log(|Y|)$$

A prototype-based model \(\mathcal{M}\) would deduce the label of all points from those of its \(K\) prototypes \(\{p_k\}\), in the hope that: $$\beta(x_i) = y_i$$

A prototype-based model \(\mathcal{M}\) would deduce the label of all points from those of its \(K\) prototypes \(\{p_k\}\), in the hope that: $$\beta(x_i) = y_i$$ The decision function \(\beta\) just returns the label of the closest prototype.

For instance, if the point is closer to prototype 3 (labeled "blue") than to any other prototype, the decision function will return "blue".

The complexity of the model is given by the complexity of its prototypes and their labels: $$C(\mathcal{M}) \leq \sum_k C(p_k) + K \times \log (|Y|).$$ Now: $$C(\{(x_j, y_j)\} | X) \leq C(\mathcal{M}) + \sum_{i,j} {C((x_j, y_j)} | X, \mathcal{M})$$ Since the decision function \(\beta\) is just a loop over the prototypes, \(C((x_j, y_j) | X, \mathcal{M}) = 0\). So \(C(\{(x_j, y_j)\} | X)\) is found to be much smaller if \(K \ll |X|\) than if we only rely on rote learning.

The complexity of the model is given by the complexity of its prototypes and their labels: $$C(\mathcal{M}) \leq \sum_k C(p_k) + K \times \log (|Y|).$$ Now: $$C(\{(x_j, y_j)\} | X) \leq C(\mathcal{M}) \ll \sum_j |X| \times \log(|Y|)$$ We just have to remember the prototypes and their label to retrieve all labels, hence the compression.

This is only true, however, if the model \(\mathcal{M}\) is perfect.

This is only true, however, if the model \(\mathcal{M}\) is perfect.

If not: \(C((x_j, y_j) | X, \mathcal{M}) \neq 0\).

For each misclassified point, we may just specify its index the correct value of its label. $$C(\{(x_j, y_j)\} | X, \mathcal{M}) \leq \sum_{i=1}^{|X|} (C(i) + C(y_i)) \times \mathbb{I}(y_i \neq \beta(x_i))$$ where \(\mathbb{I}\) is a function that converts a Boolean value into 0 or 1.

This is only true, however, if the model \(\mathcal{M}\) is perfect.

If not: \(C((x_j, y_j) | X, \mathcal{M}) \neq 0\).

More simply, if there are \(n\) misclassified points, we get: $$\sum_{i,j} C((x_j, y_j) | X, \mathcal{M}) \leq n \times (\log(|X|) +\log(|Y|)).$$

To sum up: $$C(\{(x_j, y_j)\} | X) \leq \sum_k C(p_k) + K \times \log (|Y|) + n \times (\log(|X|) +\log(|Y|))$$ If \(n\) is small, this may still represent a huge compression as compared to rote learning. The right-hand side of this inequality can be used as a loss-function to determine the best prototype-based classification.