Understanding Artificial Intelligence
through Algorithmic Information Theory

    

Induction:
A fundamental component of Intelligence

    

    

aiai.telecom-paris.fr


Induction is a fundamental component of intelligence.

Thanks to induction, humans and robots can
  • learn
  • recognize situations
  • detect new structures
  • make appropriate decisions
  • and much more.
Induction differs from Deduction.

Deduction generates knowledge through a proof.

All humans are mortal.
Socrates is human.
Therefore Socrates is mortal.

It is sometimes considered that deduction doesn’t produce new knowledge, as the conclusion was in some way already present, in a potential form, within the hypotheses.

Will it rain tonight?    
Arc.jpg

 Any intelligent being faces the problem of adapting to changing conditions, of deciding what to do next or what to believe next.
For this, deduction proves insufficient.
Induction is a process through which one can produce new knowledge from past experiences.

Induction is one of the oldest philosophical problems:
How can we extract general rules from limited data?
To be intelligent, induction must be guided.

Observe the following sequence.     12345
What symbol should come next?

Possible solutions:
  1. 6: because sequence of integers
  2. 7: because numbers k such that (7 × 10k + 71)/3 is prime.
  3. 1: because repetition of the sequence 12345
  4. 42: because roots of polynomial
        x6 – 57x5 + 715x4 – 3795x3 + 9724x2 – 11628x + 5040
Guessing what comes next is a fundamental issue. For instance:

Prediction: Knowing past weather, can I predict if it will rain?
Or in other words: continue the sequence
    (rain, rain, sun, rain, rain, sun, snow, mist, rain, rain)

Classification: Having observed a sequence of pairs (object, label), can I predict the label of a new object?
Or in other words: continue the sequence
    (object 1, label 1, object 2, label 2, ... , object n, label n, object n+1)
What is the best strategy for induction?        

    

1280px-Epikouros_BM_1843.jpg Epicurus    341–270 BC

Principle of multiple explanations:
If more than one theory is consistent with the observations, keep all theories.
What is the best strategy for induction ?        

    

Sextus.jpg 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.”
What is the best strategy for induction ?        

    
Do birds fly?
2560px-20180703_kiwi-sonya9_959_DxO.jpg West_Coast_National_Park_(11356314336).jpg
"some of the particulars omitted in the induction may contravene the universal"
240 440px-Southern_Cassowary_7071.jpg
What is the best strategy for induction ?        

    

William_of_Ockham.png William of Ockham 1287-1347

Occam’s Razor Principle:
Entities should not be multiplied beyond necessity
What is the best strategy for induction ?        

    

Thomas_Bayes.gif 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.
What is the best strategy for induction ?        

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