Funded Grants

Perception and analogy making in complex adaptive systems

What have we learned in five decades of research on artificial intelligence? Marvin Minsky, a founder of the field, has said that one major lesson is "Easy things are hard." Computers have accomplished feats considered to be the pinnacles of intelligence, such as beating the world chess champion, solving complex symbolic equations, proving original theorems in logic, and diagnosing diseases. Nonetheless, computers still perform poorly on some of the most natural tasks for humans: navigating around a crowded room without bumping into anyone, speaking and understanding language, and recognizing faces and other objects in photographs and in day-to-day life. A general ability to perceive patterns and recognize similarities among them---i.e., make analogies---is at the heart of intelligence in natural adaptive systems, and is precisely what today's computers lack.

Perception is a harder problem than chess-playing or equation-solving simply because it is so open-ended. Consider what goes into understanding, say, a photograph of a laughing girl on a swing in a playground, being pushed by two of her friends. The perceiver must determine, most basically, what are the relevant components of the scene---how the various lines, brightnesses colors, and textures fit together to make up the swing, the girl's mouth, or a patch of sand. Part of the swing set might be obscured from sight by a tree in the foreground; this must not interfere with its recognition. Abstract aspects of the scene must be recognized as well, such as "girl," "playground," "friend," and "having fun". The perceiver must determine that the swing, the girl, and the laugh are important components of the scene whereas the specific orientations of each blade of grass or the specific yellow hue of the sand are not. The description of the perceptual process of even this simple photograph could go on and on, and attests to the open-ended nature of perception.

Pattern-perception and analogy-making are not limited to humans or animals. Rather, they are continual modes of information processing in all intelligent systems in nature. The immune system, for example, perceives patterns related to the shapes of invaders, the sites and sizes of infections, the type and degree of cellular injury, and the similarity to previous infections in order to develop appropriate responses. Likewise, ant colonies recognize patterns of food distribution and of colony needs in order to develop foraging and task-allocation strategies. In these and other complex and adaptive systems, perception takes place via the collective actions and interactions of large numbers of relatively simple autonomous agents.

My research focuses on developing computer programs that can perceive patterns and analogies, using inspiration from pattern perception in complex adaptive systems. This work explores some of the most fundamental questions of artificial intelligence. How does a person (or how might a computer program) mentally explore the typically intractably huge number of possible ways of understanding what is going on and possible similarities to other scenes or situations? How does the perceiver continue to explore new possibilities when the stimuli are continually changing? More generally, how can we build a computer program that achieves this fluidity of perception evident in natural systems and avoids the brittleness that plagues present-day computers?

Douglas Hofstadter and I have developed a computer program called "Copycat" that addresses these questions. Copycat perceives patterns and makes analogies in the domain of letter strings, solving problems such as "If abc changes to abd, what is the analogous change to kkjjii?" In Copycat, the perception of objects, relationships, and analogies is carried out by a swarm of simple, relatively autonomous agents (analogous to individual ants in a colony or cells in the immune system) acting with no central control. The global perception of a scene or situation comes about as a result of many small, diverse, often redundant, and often fruitless explorations by these agents. This strategy allows the exploration of many different possible ways of understanding a situation to be carried out simultaneously, but at varying speeds and depths, which change continually as information is gathered about what is promising. Over time, a coherent perception is discovered and rival perceptual candidates fade out, though are never completely gone. This is similar to the way that exploration proceeds in the immune system, in ant colonies, and, we claim, in human cognition.

Copycat was shown to give human-like answers to a large set of letter-string analogy problems, many of which required what people consider to be sophisticated pattern recognition and creativity. While Copycat's perceptual abilities were promising, they were limited to the domain of letter strings. It remains to be demonstrated that such a system will work well on more realistic situations requiring a much larger repertoire of concepts, or that these ideas will be useful for understanding information processing in natural complex systems.

My current research is aimed at taking these two further steps. First, I am applying principles of pattern recognition gleaned from complex systems in nature to develop a computer program--a successor to Copycat--that can interpret and make analogies between visual images. Second, I am investigating the usefulness of such computational approaches for modeling pattern perception in natural complex systems such as the immune system.

Understanding the contents of images in a general way is one of the most challenging problems facing artificial intelligence. One legend in AI has it that in the 1960s Marvin Minsky gave the problem of general image understanding to a graduate student as a short-term summer project. This was one way he learned the "easy things are hard" lesson. Forty years later, the state-of-the-art image understanding systems work well only in narrowly defined domains and tinder restricted conditions within those domains; they do not seem to be easily generalizable. What is needed is the kind of fluid pattern-perception and analogy making abilities seen in Copycat, but brought to a much more sophisticated level.

In the 1960s Mikhail Bongard, a Russian computer scientist, developed a set of visual problems designed to capture the essence of pattern perception and analogy-making. Each problem presents the perceiver with 12 black-and-white line drawings, six on the left and six on the right. The task for the perceiver is to describe the difference between the left and right sets. For example, one Bongard problem consists of a left set containing only three sided shapes and a right set containing only four-sided shapes. Another problem, requiring more abstract perception, consists of a left set containing only horizontal shapes and a right set containing only vertical shapes. Bongard designed 100 such problems ranging from very simple and concrete to quite difficult and abstract. These problems capture many interesting and essential facets of visual pattern perception including those described above for the girl-in-swing photograph: perceiving concrete and abstract features and relationships, discovering which features and relationships are important and which can be ignored, separating figure from ground, hierarchically grouping features, and using context to guide the exploration of interpretations.

My research will build on the ideas of Copycat by developing a computer program that solves Bongard problems. Success in this approach will set the stage for tackling such difficult real-world image interpretation problems, including handwriting recognition, remote sensing, image database search, and medical image-processing. All currently suffer from the fact that no one knows how to get computers to perceive patterns, incorporate context, and make analogies in general ways. I also hope eventually to extend these ideas to other perceptual domains, such as speech understanding by computer, which likewise will not reach human level without the kinds of high-level perceptual abilities required for Bongard problems.

The ideas developed in this research may illuminate how information processing and pattern perception takes place in natural complex systems. Some researchers have described the immune system and other natural systems as "cognitive" in that they encode and process information, perceive patterns, make decisions, and learn from experience. However, the detailed processes by which these cognitive abilities come abort are still rat well understood. For example, immunologists Lee Segel and Irun Cohen have asked, "How do systems choose the right set of agents to perform appropriate actions with appropriate intensities at appropriate times?" This is the kind of question that my research attempts to address in the context of perception, and I believe the answers will apply broadly in complex systems studies. In general, computer models similar to the system I am proposing, which describe information processing in complex systems at a high level, might suggest concrete mechanisms as well as physical experiments to test for these mechanisms. High-level principles are much needed to help scientists make sense of the large amounts of data they encounter in studying complex systems in nature.