In this presentation we describe an application of Kolmogorov complexity to analogical reasoning. 'Kolmogorov's algorithmic complexity' and 'application' seem opposites terms since the function defined by Kolmogorov is not computable. However, the evolution of the research on analogical reasonning without doubt leads to the underlying concepts of Kolmogorov complexity as to its formal definition. Let's consider the evolution that takes place form [Gentner'83], to [Holyaok&Tagart'89], to [Holyoak&Hummel'??], and finally [Hosftadter'95]. The proposal starts with very restrictive syntactical and structural constraints, and then moves on to more general heuristics. This is balanced by an increased use and quality of the domain knowledge. The CopyCat project [Mitchell'93], an instance of Hofstadter's proposal, shows a precise description of domain knowledge that involves a declarative part (the Splinet) as well as a procedural component (the codelets). The Slipnet is a graph describing the available concepts and their similarity relations. The codelets are short programs in charge of finding the instance of the concepts in the data. This led us to consider the representation of the domain knowledge as an extract of the Universal Turing Machine that the Kolmogorov complexity needs. The 'extract' notion indeed comes from the finite aspect of the graph. The Turing machines will be helpful in order to formalize the codelets (the procedural component of the knowledge). To perceive the graph organization in the universal Turing machine, we will refer to the fact that in order to construct a complex Turing machine it is always possible to use simpler machines and combine them ; these combinations may be described as relations in a graph. Having justified how Kolomgorov's formal setting maybe adapted to the analogical reasoning setting, we argue that it's inductive abilities are needed to solve the analogy problems. We show that the Minimum Description Length Principle computed with K can be used in order to created a normative criterion to select the best solution. To conclude, we will consider the calculability problem. Kolmogorov's complexity is not computable due to the infinite amount of Turing machines that the optimization process must consider in the universal Turing machine. Reducing the size of the Turing machine to an 'extract', we may now compute the optimum, but loosing the predictive properties. Our proposal is to 'explore' the universal Turing machine by constantly updating the extract. This type of process is quite standard when facing a complexity problem, but we do know in machine learning that exploration of hypothesis spaces must be controlled in order to avoid the overfitting problem. We will then mention how Vapnik's result on statistical learning [Vapnik'95] may be included to reduce this risk.

[Gentner'83] Gentner Drede, Structure Mapping : a theoretical framework for analogy, Cognintive Sciences Vol 7 No 2 pp 155-170, 1983
[Hofstadter'95] Hofstadter Douglas, Fluid concept and creative analogies, Basic Books, 1995
[Holyoak&Tagart'89] Holyoak & Tagart, Analogical Mapping by constraint satisfaction, Cognitive Sciences 13, 1989
[Hummel&holyoak'96] Hummel & Holyoak, LISA : a computational model of analogical inference and schema induction, Cognitive Science Society, 1996
[Mitchell'93] Mitchell Melanie, Analogy-making as perception, MIT press, 1993
[Vapink'95] Vapnik Vladimir N., the nature of statistical learning, Springer Verlag NY, 1995