Analogical reasoning is a central problem both for human cognition and for arti cial learning. Many aspects of this problem remain unsolved, though, and analogical reasoning is still a di cult task for machines. In this paper, we consider the problem of analogical reasoning and assume that the relevance of a solution can be measured by the complexity of the analogy. This hypothesis is tested in a basic alphanumeric micro-world. In order to compute complexity, we present speci cations for a prototype language used to describe analogies. A few elementary operators for this language are exposed, and their complexity is discussed both from a theoretical and practical point of view. We expose several alternative de nitions of relevance in analogical reasoning and show how they are related to complexity.
Analogical reasoning is a fundamental ability of human mind which consists in
establishing a mapping between two domains based on common representations.
Analogies are involved in particular in the use of metaphors, humour [
The question of relevance is central in analogical reasoning in the sense that
it de nes the quality of the considered mappings. Because in nitely-many
common properties can be found between two objects, a relevance measure has to be
found to disqualify properties of little interest [
Inspired by some previous works [
In order to study general properties of proportional analogy, Douglas Hofstadter
introduced a micro-world made up of letter-strings [
We consider a slightly modi ed version of Hofstadter's problem. Our modications correspond to an extension of the micro-world.
First, we consider an additional base alphabet: the number alphabet. This alphabet adds an in nite number of elements to the problem but does not make the base problem more complicated. Furthermore, this addition encourages the use of user-de ned base structures and raises the issue of transfer between di erent domains. In particular, the analogy equation ABC : ABD :: 123 : x seems very basic for a human mind while it corresponds to a change of representation from the world of letters to the world of numbers. Besides, the use of other base alphabets can be justi ed by some prior knowledge of the users: for instance, it can be thought that the problem ABC : ABD :: QWE : x will admit a simple solution for any system familiar with the English keyboard layout. 3
Secondly, we consider a mapping from numbers to any base alphabet. This operation was discarded by Hofstadter's rules but seems important to us. The problem ABC : ABD :: ABBCCC : x relies on a such a mapping: the string ABBCCC is naturally described as \n-th letter of the alphabet repeated n times for n 2 f1; 2; 3g".
The third major di erence between our approach and Hofstadter's original works lies in the consideration of descriptive groups. While Hofstadter's approach is merely descriptive, we adopt a generative formalism in which the way strings were formed is taken into account. The static description of copy-groups, successor-groups or predecessor-groups is replaced in our framework by methods such as copy, succession or predecession. 2.2
Complexity-based description In this paper, we will focus on the resolution of analogy equations of the form A : B :: C : x where x is unknown. We submit that the solution of such an equation is given by x = arg minx C(A; B; C; x) where the function C corresponds to the (minimum) description length for the four terms. Such a hypothesis is related to the well-known philosophical principle of Occam's razor stating the best choice is the shortest.
A strict de nition for the description length is o ered by algorithmic theory of
information with Kolmogorov complexity [
In practice, this quantity is not calculable, hence only upper-bounds are used to estimate the complexity of an object. An upper-bound corresponds to a restricted choice of programs or equivalently to the choice of a limited Turing Machine. In this paper, we consider a particular machine by de ning an elementary language. The language we develop is an ad hoc construction encoding a theory of the domain of interest.
We do not consider here pre x codes, ie. decodable codes in which no code word can be the pre x of another code word. To cope with decoding, we consider that the code is space-delimited, which means that costless delimiters are present in it. This idea is in use in the Morse code for example. Morse code encodes letters by sequences of dashes and dots (ie. with a binary alphabet). A full word is given by a succession of letters separated by short breaks. These breaks are not part of the Morse code but are used to indicate the transition from one letter to another. In such contexts, the delimiters are supposed to be processed by the physical layer of the system, hence to ensure a uniquely decodable code while having no in uence on complexity. 2.3
A generative language Based on the speci cations listed above, we develop a prototype language designed to produce and solve analogies. We present here the global characteristics of our language.
As mentioned, a major di erence between our perspective and Hofstadter's
works is the generative point of view. Largely inspired by Leyton's theory of
shapes [
In order to integrate this sequential transformation of an original string, we consider that the machine has access to a one-dimensional discrete tape. At each time step, the machine writes on this tape or modi es the previously written string. Thus, the base operation consists in copying the alphabet onto the tape. Thus, the generative procedure consists in a sequence of operations read from left to right and separated by commas. The operations are applied one by one and refer to understandable manipulations. Even if any operation may be incorporated to the language, we will consider here only a restricted set of prede ned transformations, called operators fO1; O2; : : : g. The complexity of an operator is independent of the operation it performs. An upper bound of this complexity is the rank of the operator in the list of operators. For instance, the complexity of operator O1 is equal to 0, no matter how complex the corresponding operation actually is.
Besides, the instruction next_block is used to move to the next term in the analogy de nition. For the analogy A : B :: C : D, the order of the blocks is A, B, C and D.
The core of the language is the use of a triple memory: a long-term domain memory, a long-term operator memory and a short-term memory. A string or a new operator can be put into short-term memory by means of the instruction let. The short-term memory can be accessed with the key instruction mem.
More precise information on the exact grammar chosen for the language can be found as supplementary material on the authors' webpage. The list of operators available for the language determines the bias of the machine. The more operators are given to the system, the more sophisticated the obtained expressions can be.
The most basic set of programs is empty: it corresponds to a system capable of giving letters one by one only. Such a system is su cient in some contexts. Consider for example the real problem of learning declension in a language. In order to learn a declension, students learn by heart a single example and transfer the acquired knowledge to new words. This corresponds for instance to the analogy rosa : rosam :: vita : vitam for a simple Latin declension. This analogy is encoded by the following code: let(`r',`o',`s',`a'), let(`v',`i',`t',`a'), let(?, next_block, ?, 'm'), mem, 0, mem, 2, next_block, mem, 0, mem, 1; 5
This program has to be interpreted as follows: In the rst line, the groups `rosa' and `vita' are put in short-term memory. The second line de nes a new operator which displays the argument, switches to the next block, displays the argument again and nally adds the character `m'. The third line retrieves the just-de ned operation and applies it successively to the two words, also retrieved from memory.
In order to build e ective descriptions for more complex systems, additional operators can be de ned. A list of possible operators is given in table 1. The strength of the proposed language lies in its use of a triple memory to access elements of di erent nature: a long-term domain memory Md storing domain descriptions (e.g. alphabets), a long-term operator description Mo storing system procedures to modify objects, and a short-term memory storing temporary elements. Managing memory is of major importance when it comes to producing programs of minimal length.
The access to elements in long-term memories Md and Mo is hidden in the language for simplicity purpose, but it cannot be ignored. The designation of support alphabets (alphabet, numbers, utf8, qwerty-keyboard...), hence of the domain, and the designation of operators (copy, sequence, find...) are treated as proper nouns to encapsulate an access to an ordered memory. The rank of entities in memory is a characteristics of the machine and cannot be changed.
The user is in charge of the management of short-term memory. Entities (operators or strings) are stored in memory with the let meta-operator and accessed with the mem meta-operator. For example, the instruction let(`a') will store the generation of a but the string is not written on the band. It will be written only when invoked from memory. The short-term memory is organized as a stack (hence last-in rst-out): the parameter given to the mem operator is the depth of the element in the stack.
Using short-term memory is not compulsory to describe a string: the language syntax does not prevent from repeating identical instructions. However, in a context of nding a minimal description (which is the purpose of our framework), using memory is an important way to pool identical entities.
The principles outlined in previous section form a simpli ed grammar for our generative language. They are not su cient yet to calculate the complexity of an analogy. The missing step is the formation of a binary code from an instruction.
The basic idea we use to obtain an e cient code consists in using a positional code in lists. This code associates element 0 to the blank symbol, 0 to element 1 and increments of 1 bit at for each element (0, 1, 00, 01, 10...). Using this code, the complexity of the n-th element of a list is dlog2 ne.
The global description of the language is organized as a list of lists: a word is designated by the path inside the sequence of lists. For instance, the code for the character d corresponds to the code of domain memory (1), alphabet (0) and d (01), hence 1,0,01. The code is not self-delimited: the delimiter is the comma symbol and can delimit a blank symbol. For instance, the number 2 is encoded by 1,,00. Because a language word corresponds necessarily to a tree leaf, the code is uniquely decodable.
The complexity of an instruction is determined from the corresponding code. We propose to consider that the complexity corresponds directly to the number of bits required in the code. For instance, the complexity of the character 2 will be the number of bits in 1,0,0, hence C(2) = 3. The same reasoning is applied to any instruction, including complex instructions describing complete analogies.
A way to build a cognitively plausible language encoding would consist in evaluating the ordering based on human experiments. Such experiments will have to be made in future research. 3.2
Relevance of a description
Several acceptable instructions can generate a given string. For example, the
string abc can be produced either by alphabet, sequence, 3; (instruction 1)
or `a',`b',`c'; (instruction 2) or alphabet, sequence, 2, `c';
(instruction 3). These three instructions do not seem equally satisfying from a human
7
point of view. We submit that the di erence in terms of relevance can be
quantied by their description length. Using a speci c code description, the description
lengths for the three previous instructions are respectively DL1 = 8, DL2 = 10
and DL3 = 12. In this example, it is clear that the instruction with minimal
description length corresponds to the most relevant description of the string. As a
rst step of our reasoning, we state that the most relevant generative description
of a string is the description of minimal description length. An upper-bound for
the Kolmogorov complexity of a string is de ned as the description length of
the most relevant instruction which outputs the string of interest. Despite the
huge restriction applied to a general UTM by the choice of our language, the
complexity remains non computable: its computation requires an exploration of
all instructions producing the string, hence of an in nite space. Several solutions
can be adopted in order to build the optimal program. First, greedy approaches
would impose a research bias by the mean of a locally optimal exploration of
the space of programs. Additionally to this guided exploration of the space of
programs, a resource-bounded research can be considered [
Relevance of a solution for an analogy equation Using the version of Kolmogorov complexity obtained by our system as described above, it is possible to apply the minimum complexity decision rule.
In order to evaluate the way human beings react to analogy problems, we proposed an experiment with several Hofstadters analogy problems.
Participants were 68 (36 female), ages 16-72, from various social and educational backgrounds. Each participant was given a series of analogies. The series were in the same order for all participants, and some questions were repeated several times in the experiment. All analogies had in common the source transformation ABC : ABD. The main results are presented in Table 2.
The results presented in Table 2 con rm that in most cases the most chosen solution corresponds to a minimum of cognitive complexity. The complexity is calculated here using our small language and the coding rules exposed earlier. Its limits are visible with the two examples ABC : ABD :: 135 : x and ABC : ABD :: 147 : x. In these examples, the language fails at describing the progression of the sequence \two by two" (1-3-5-7) or \three by three" (1-4-7-10) which would decrease the overall complexity.
However, despite the simplicity of the language used to calculate the complexity, it is noticeable that the most frequent solution adopted by the users corresponds a complexity drop. This property is not veri ed with only two problems: for the problem ABC : ABD :: 122333 : x, the large value of the complexity in the most frequent case is due to the limitations of the language which fails at providing a compact description of the complete analogy because of a too rigid grammar. In the case of the analogy ABC : ABD :: XYZ : x, adding the circularity constraint has a cost in the language, while it seems to be a natural operation for human beings.
The experiment also reveals a major weakness of our modeling: The descriptions provided by our language are static and do not depend on the environment. 9 On the contrary, the variations of the average answering time and the changes in the answers (when a same problem is repeated at several places) indicates clearly that having faced similar structures in the past helps in solving a new analogy. Finally, the relative relevance of two solutions is not necessarily su cient to explain human preference in this matter, though. For instance, on the rst problem, a large majority of people choose the IJL answer despite the small complexity di erence. This possible divergence is related to research biases which are not taken into account in our approach. This e ect is particularly visible with the more di cult analogy equation ABC : ABD :: AABABC : x. Very few humans notice the structure A-AB-ABC, hence the corresponding solution x = AABABCD. However, the structure A-AB-ABC is perceived as more relevant when presented.
We have shown that complexity o ers a criterion to compare two given solutions to an analogy equation. This sole property is not su cient in practice to obtain an analogy solver. Since the space of solutions is in nite, additional hypotheses must be considered in order to restrict the exploration space. 4
In this paper, we proposed to interpret analogical reasoning as a complexity minimization problem and to solve an analogy equation by taking the solution minimizing total complexity. Our approach relies on a restricted Turing machine: we proposed basic rules de ning a small language adapted to Hofstadter's analogies. The language has been chosen to be generative (hence consistent with Leyton's theory of shapes) and not self-delimited (which allows compression with unspeci ed parameters). We gave general principles governing such a language. The system is exible in the choice of the operations that can be involved for the description of an analogy. This language is associated to a code directly used in the computation of complexity. We use this code to measure the relative relevance of descriptions for a same string and the global relevance of a solution to an analogy. We used this code to measure the complexity of several analogies and noticed that the minimum complexity solution corresponds in most cases to the most frequent solution given by human beings.
Although the considered case might seem restrictive, our approach applies on a wider range of problems. Humans often justify their analogies with a semantic description. We consider our developed language as such. Similar languages can be developed for other analogies. Several issues remain open. A future research would be to develop a system able to generate descriptions automatically, hence to solve analogy equations automatically. The question of the performance evaluation of an analogy solver remains open: our framework measures only the relevance of a single solution. Some work has to be done to o er either a theoretical measure of the global quality for an analogy solver or an experimental validation of its e ciency. Finally, a real investigation on an extension of this language to other domains is needed in order to conclude on its actual generalization properties. Acknowledgments. This research is supported by the program Futur & Ruptures (Institut Mines Telecom).