From Complexity to Intelligence
Lecturers:
Jean-Louis Dessalles
Pierre-Alexandre Murena
→ other AI courses
Objectives
The mathematical notion of complexity has been invented 50 years ago to solve issues related to machine learning, randomness and proof theory. Complexity corresponds to the size of algorithms (and not to their speed; see caveat below). Complex objects cannot be described by short algorithms. The notion led to the development of Algorithmic Information Theory (AIT). Complexity and AIT have more recently been shown essential to address aspects of human intelligence, such as perception, relevance, decision making and emotional intensity. These aspects of cognition were sometimes considered mysterious and unpredictable. They can be regarded now as resulting in part from computations based on complexity and its converse, simplicity. For instance, abnormally simple situations such as a coincidence (two colleagues having dressed in purple independently) or a remarkable lottery draw (e.g. 1-2-3-4-5-6) are systematically perceived as unexpected and interesting. The design of intelligent systems must take advantage of this sensitivity of the human mind to complexity and to simplicity.
Caveats:
- This course does not address the notion of "computational complexity" which measures the speed of algorithms.
- This course is not about Complex Systems either (for this, see TPT-09: Emergence in complex systems).
Content
This course begins with an introduction to the mathematical notion of complexity (also known as Kolmogorov complexity). The notion will be shown to be useful for the study of reasoning, for the definition of relevance (interestingness, unexpectedness), and for machine learning. We will also explore applications to the study of perception (hidden shapes, pattern recognition), of decision making (subjective probability), of responsibility and of emotional intensity.
All these aspects will be studied using concrete examples. Half of the time will be devoted to personal work in lab sessions.
Slides
Validation
Students will also be asked to make a small original contribution and to present it orally.
They will also have to answer a short quiz on the last day.
→
Answers to the 2019 quiz.
You are expected to choose a topic of study, and to do something for this project (typically write a small program).
The topic of the project must be related to complexity.
Please indicate your choice using the link above, not later than Thursday 15:00pm of the Athens week.
On Thursday night of the Athens week, we expect:
- a couple of slides to explain what you are studying (this year: IN PDF FORMAT)
DON’T SEND ANYTHING THROUGH E-MAIL
Use the upload link.
Before the end of the Athens week, you’ll upload a small text describing your project and what you found
(typically: two pages, more if there are images)
This text should present:
- Your name, date and context
- The problem addressed
- What you did + what you found
- A bit of theoretical reflection/extension about what you did.
- A bibliography (with weblinks)
So don’t forget to
upload:
- your slides (on thursday night)
- your text
- your program
We hope you’ll enjoy doing this. We also hope you’ll enjoy others’ presentations.
Short bibliography
- Chaitin, G. J. (2004). On the intelligibility of the universe and the notions of simplicity, complexity and irreducibility. In W. Hogrebe & J. Bromand (Eds.), Grenzen und Grenzüberschreitungen, XIX, 517-534. Berlin: Akademie Verlag.Devine, S. D. (2014). Algorithmic information theory: Review for physicists and natural scientists. .
- Chaitin, G. J. (2005). Meta Math! The quest for Omega. Vintage Books, ed. 2006.
- Chater, N. (1999). The search for simplicity: A fundamental cognitive principle?. The Quarterly Journal of Experimental Psychology, 52 (A), 273-302.
- Li, M. & Vitányi, P. (1993). An introduction to Kolmogorov complexity and its applications (3rd ed.). New York: Springer Verlag, ed. 1997.
- Solomonoff, R. J. (1997). The discovery of algorithmic probability. Journal of Computer and System Sciences, 55 (1), 73-88.
- Solomonoff, R. J. (1978). Complexity-based induction systems: Comparisons and convergence theorems. IEEE transactions on Information Theory, 24 (4), 422-432.
- Vitányi, P. & Li, M. (2001). Simplicity, information, Kolmogorov complexity and prediction. In A. Zellner, H. A. Keuzenkampf & M. McAleer (Eds.), Simplicity, inference and modelling: Keeping it sophisticatedly simple, 135-155. Cambridge, UK: Cambridge University Press.
- Zenil, H. (2013). A computable universe: understanding and exploring nature as computation. World Scientific.
In French:
- Delahaye, J.-P. (1994). Information, complexité et hasard. Paris: Hermès, ed. 1999.
- Delahaye, J-P. (2013). Mesurer la complexité des objets numériques. 1024 - Bulletin de la Société Informatique de France, 1, 35-53.