Understanding Artificial Intelligence
through Algorithmic Information Theory
Analogy making
and complexity
Why is analogical reasoning so fundamental?
- In mathematics and science: discover new concepts, or generalize notions to other domains
- Justice: use of relevant past cases
- Art: metaphors, parody, pastiche
- Advertising: similarity of products influence people
- Humour: jokes are often based on faulty analogies- teaching, XAI: good explanations are often analogies
- transfer learning: transfer of expertise to new domain
- Gills are to fish as lungs are to humans.
- Donald Trump is to the US as Vladimir Putin is to Russia
- Donald Trump is to Barack Obama as Barack Obama is to George Bush
- 37 is to 74 as 21 is to 42
- The sun is to Earth as the nucleus is to the electron
A is to B as C is to D
is also noted: A : B :: C : 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) simplestor, 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)
- symmetry: 𝒜(A,B,C,D) ⇒ 𝒜(C,D,A,B)
- central permutation: 𝒜(A,B,C,D) ⇒ 𝒜(A,C,B,D)
We call analogical equation the problem of finding the missing term x in an analogy:
A is to B as C is to x
or: A : B :: C : x Examples:- Paris is to France as Helsinki is to ... ?
- ABC is to ABD as IJK is to ... ?
A : B :: C : x
Following the induction principle, solving the analogical equation amounts to finding \(\mathbf{x}\) such that:
\(\mathbf{x} = argmin(K(A, B, C, \mathbf{x}))\)
where K designates Kolmogorov complexity.
A : B :: C : x
Doug Hofstadter is well-known for his original study of analogy. Let’s consider one of his favourite examples.
abc : abd :: ppqqrr : x
Have you come up with a solution?
abc : abd :: ppqqrr : x
Most people would instantly answerx = ppqqss. Why should we consider it a "better" solution than, say, x = ppqqrd?
abc : abd :: ppqqrr : x
x = ppqqss. x = ppqqrd. We have to compare two rules:- increment the last item
- replace the last letter by d
The second rule has two drawbacks in terms of complexity:
- - it introduces a constant, d.
- - if we do not want to lose the structure that led to the compression of ppqqrr, the rule should read:
"break the last item back into letters, and replace the last letter by d"