1
Kolmogorov complexity and Inductive inference
Kolmogorov complexity of an object, such as a piece of text, is the length of a
shortest computer program (in a predetermined programming language) that
produces the object as output. It is a measure of the computational resources
needed to specify the object.
MDL and learning decision tree
code the decision tree and exceptions to reach the minimum message length
2
Example
3
Example
4
Example
5
Example
6
Example
+ single exception
7
Example
+ single exception
8
How to code a decision tree and exceptions
1. Perfect tree
9
How to code a decision tree and exceptions
2. Imperfect tree
10
How to code a decision tree and exceptions
Perfect tree
Imperfect tree
Summary
11
Information sources
•  Tom Mitchell, Machine Learning
•  Peter Flach Book
•  http://work.caltech.edu/lectures.html
•  Li & Vitanyi, An Introduction to Komogorov Complexity and Its Applications