Melanie Mitchell's Ph. D. thesis (with Douglas Hofstadter. A system that make analogies between character strings (it has an emergent behavior).

For example:
abc -> abd, bcd -> ?
Copycat should answer bce, but also bcd...

It inspired F. Parmentier's BAsCET.

Here is what is said in Mitchell ? (she kindly allowed me to cite her):

Copycat's task is to use the concepts it possesses to build perceptual structures -- descriptions of objects, links between objects in the same string, groupings of objects in a string, and correspondences between objects in different strings -- on top of the three "raw", unprocessed strings given to it in each problem. The structures the program builds represent its understanding of the problem and allow it to formulate a solution. Since for every problem the program starts out from exactly the same state with exactly the same set of concepts, its concepts have to be adaptable, in terms of their relevance and their associations with one another, to different situations. In a given problem, as the representation of a situation is constructed, associations arise and are considered in a probabilistic fashion according to a parallel terraced scan in which many routes toward understanding the situation are tested in parallel, each at a rate and to a depth reflecting ongoing evaluations of its promise.

Copycat's solution of letter-string analogy problems involves the interaction of the following components:

  • The Slipnet: A network of concepts, each of which consists of a central node surrounded by potential associations and slippages. A picture of some of the concepts and relationships in the current version of the program is given in Figure 1. Each node in the Slipnet has a dynamic activation value which gives its current perceived relevance to the analogy problem at hand, and which therefore changes as the program runs. Activation also spreads from a node to its conceptual neighbors, and decays if not reinforced. Each link has a dynamic resistance value which gives its current resistance to slippage. This also changes as the program runs. The resistance of a link is inversely proportional to the activation of the node naming the link. For example, when opposite is active, the resistance to slippage between nodes linked by opposite links (e.g. successor and predecessor) is lowered, and the probability of such slippages is increased.
  • The Workspace: A working area in which the letters composing the analogy problem reside and in which perceptual structures are built on top of the letters.
  • Codelets: Agents that continually explore possibilities for perceptual structures to build in the Workspace, and, based on their findings, attempt to instantiate such structures. (The term "codelet" is meant to evoke the notion of a "small piece of code", just as the later term "applet" in Java is meant to evoke the notion of a small application program.)
    Teams of codelets cooperate and compete to construct perceptual structures defining relationships between objects (e.g., "b is the successor of a in abc", or "the two i's in iijjkk form a group", or "the b in abc corresponds to the group of j's in iijjkk", or "the c in abc corresponds to the k in kji"). Each team considers a particular possibility for structuring part of the world, and the resources (codelet time) allocated to each team depends on the promise of the structure it is trying to build, as assessed dynamically as exploration proceeds. In this way, a parrallel terraced scan of possibilities emerges as the teams of codelets, via competition and cooperation, gradually build up a hierarchy of structures that defines the program's "understanding" of the situation with which it is faced.
  • Temperature, which measures the amount of perceptual organization in the system. As in the physical world, high temperature corresponds to disorganization, and low temperature corresponds to a high degree of organization. In Copycat, temperature both measures organization and feeds back to control the degree of randomness with which codelets make decisions. When the temperature is high, reflecting little perceptual organization and little information on which to base decisions, codelets make their decision more randomly. As perceptual structures are built and more information is obtained about what concepts are relevant and how to structure the perception of objects and relationships in the world, the temperature decreases, reflecting the presence of more information to guide decisions, and codelets make their decisions more deterministically.

Figure 1: Part of Copycat's Slipnet. Each node is labeled with the concept it represents (e.g., A-Z, rightmost, successor, etc.). Some links between nodes (e.g. rightmost-leftmost) are connected to a label node giving the link's relationship (e.g., opposite). Each node has a dynamic activation value (not shown) and spreads activation to neighboring nodes. Activation decays if not reinforced. Each link has an intrinsic resistance to slippage, which decreases when the label node is activated.

                  A<------->B<------>      ...          X<-------->Y<--------->Z
                  |                                                            |
                  |           rightmost                successor               |
                  |               |                         |                  |
                  |               |####### opposite ########|                  |
                  |               |            #            |                  |
                  |           leftmost         #       predecessor             |
                  v                            #                               v
               first  ------------------------------------------------------  last


Bibliography

Mitchell ?
Melanie Mitchell. Analogy-Making as a Complex Adaptive System. L. Siegel and I. Cohen (editors), Design Principles for the Immune System and Other Distributed Autonomous systems. New York: Oxford University Press.

Links

http://www2.psy.uq.ed.au/CogPsych/Copycat/
This page contains a Java Applet of Copycat. Thanks to alfimp for this link.