This spring, a book was published that proposes to change fundamentally the direction of research in artificial intelligence. Fluid Concepts and Creative Analogies, by Douglas Hofstadter and the Fluid Analogies Research Group (BasicBooks, 1995), challenges many deep assumptions of AI work today, and lays out a program of research that will annoy some, inspire others, and entertain many.
This month's column follows Hofstadter, a Pulitzer Prize-winning author and Indiana University computer scientist, as he takes on the entire artificial-intelligence community. Along the way, I'll touch on what Hofstadter has been up to the past 15 years, since the Pulitzer.
It begins, though, with a reminiscence_.
Bloomington, Indiana in the late 1970s was the kind of place you think of when you hear the words "college town." Rich with small-town flavor, seasoned by the advantages a major university brings. (And of course the disadvantages: Even people who hated football memorized the season schedule, so as to avoid the traffic jams on football weekends.) There were places, like the Runcible Spoon coffeehouse, that everyone knew about, and yet that somehow seemed to be the province of the savvy few. The savvy few were cliques of students and ex-students living a bohemian life of cappuccino and crash pads, of low income and high intellectual stimulation. More ex-students than you would think. Graduates and dropouts from the university seemed to find it hard to leave Bloomington, and the size of the ex-student population was enormous.
I was one of them. For money, I was working at a computer store maintaining Alpha Micro Systems and CP/M boxes. For intellectual stimulation, I was hanging out at the Runcible Spoon, freelancing for an early hacker rag that I thought of as Intelligent Machines Journal (though it had just changed its name to InfoWorld), and maintaining ties with the computer-science department from which I had recently received a master's degree.
I had stopped by the computer science department office in Lindley Hall one summer afternoon on some business or other, and the departmental secretary/student/assistant started raving about a new professor who had just been hired and would be starting that fall semester. The faculty apparently thought they had achieved a coup in landing this character, whose name meant nothing to me. Among other things, the departmental secretary/et cetera told me, he was the son of a Nobel Prize-winning physicist.
Later that day, I checked the fall schedule to see what this prodigy was teaching. The description of his first class was so bizarre that I decided on the spot to sign up to audit.
The class turned out to be all about Hofstadter's Big Book, a fat, ring-bound, Xeroxed tome printed in an ugly monospace font with no page numbers anywhere. He'd been shipping it around to publishers without success and was soliciting feedback from the class.
Among the memories I have of that class, this one stands out: pages and pages of puzzles. Mostly picture puzzles, like, which picture does not belong in this group? And visual analogies; I remember being challenged to think how to write a computer program that would solve visual analogies.
I was struck by the idea that something so frivolous and entertaining could be meat for computer programs. I was soon to learn that pretty much everything Hofstadter was interested in was like that: puzzling, clever, entertaining, and, on the surface, frivolous. I was struck also by the sheer number of these puzzles and soon learned that it was also a characteristic of Hofstadter not to use just one example to make an important point if he could come up with eighty. But I was chiefly struck by the difficulty of the visual-analogy problems. Clearly, exploring even a small corner of this domain would take dissertation-scale effort, and I was already making my plans to leave Bloomington for California, and computer science for computer journalism.
The book, Gödel, Escher, Bach: An Eternal Golden Braid, was picked up by Basic Books soon after that (back then, when intercaps were less universal, the publisher spelled its name as two words). It won a Pulitzer Prize and was reviewed widely, so it's probably not necessary to summarize that book here, which is fortunate, since GEB is a complex weaving (sorry, braiding) of many threads. But certain threads run through that book, the current book, and Hofstadter's intervening work.
GEB was about intelligence and artificial intelligence, among other things, including typeface design, wordplay, and analogies.
While he was writing the "Metamagical Thomas'' column in Scientific American, Hofstadter focused on puzzles and wordplay (even the title is an anagram). But the column (and the book of the same name) also had deep things to say about creativity, the mind, and the Turing test.
The Mind's I, written with Daniel Dennett, presents some philosophical musings on minds, brains, and programs.
This year, Hofstadter published his fourth fat book, and this one is where the speculations and obsessions start to pay off.
Fluid Concepts and Creative Analogies is the report of Hofstadter and his students' work over the past 15 years in creating programs that solve analogies problems. The coauthor listed on the spine of the book is the Fluid Analogies Research Group (FARG), which refers to Hofstadter's students and ex-students of the past 15 years.
I'd better say up front that Hofstadter and FARG haven't come up with a program that solves visual analogies. That's still in the future. Analogies are central to the group's work, though. Hofstadter believes that analogies are central to intelligence, and hence to artificial-intelligence research. That belief underlies all the work of FARG, and, it seems to me, all the conclusions in the book.
Hofstadter began exploring analogies in his childhood, but the beginning of his serious attempts to create computer programs capable of dealing "intelligently" with analogies was a project called "Seek-Whence."
The name Seek-Whence is, as you would expect from Hofstadter, a play on words. The program solves number-sequence problems, like "What is the next item in the sequence '1, 4, 9, 16, _'?" The program is supposed to seek the rule whence the sequence came. When he presented the number-sequence problem to students in his first AI class, Hofstadter gave them many examples of sequences for which a successful program should be able to predict the next term, such as:
Hofstadter's approach was to model, as closely as possible, the way he himself attacked such problems. He wasn't concerned with making the best sequence solver, but with making the best model of what a human being does in solving number-sequence problems. He wanted to model that mental activity.
The problem with modeling human mental activity is that you need some theory about what human mental activity is. This presupposes the existence of some kind of broad agreement about the nature of mental processes; otherwise how do you characterize what it is you're modeling? And agreement about the nature of mental processes does not exist. That's why psychologists and cognitive researchers have repeatedly turned to overt behavior or neural physiology for the content of their theories. There just is no widely accepted theory of mental processes, like what the mind is doing in solving number-sequence problems, for example.
Hofstadter's response to this dilemma was direct. He cut the Gordian knot and relied on introspection. He knew what steps he himself took in solving these problems, what blind alleys he was likely to explore, what errors he was prone to. And that's what his Seek-Whence program was supposed to model.
This very personal approach led him into trouble at least once. Because Hofstadter has a lot of "number savvy," he built a lot of number savvy (27 is a cube, a number ending in 5 may be a power of 5, and so on) into his first program. Reflecting on it later, he realized that this was exactly the wrong approach if what he wanted to explore was general intelligence. The more his program relied on knowledge of properties of numbers in solving the number-sequence problems, the less it was using general strategies of problem solving. He had, as he later characterized it, fallen into the expert-systems trap: the idea that the key to intelligence is knowledge and more knowledge. Hofstadter was morally certain that that view was just plain wrong.
He went back to the drawing board and took his students with him. Marsha Meredith ultimately wrote the program that would be known as Seek-Whence, and by the time it was done, a number of ideas that would be central to the entire FARG research program had emerged, including:
Two programs written by the FARG group over the next few years dealt in greater detail with first five central ideas just listed.
"Jumbo" is a program for solving anagrams, specifically those syndicated newspaper puzzles called "Jumbles.'' The program Jumbo is so careful in avoiding the "expert-systems trap" that it doesn't even have a dictionary----extraordinary in a program that is attempting to identify words.
Some of the central ideas took explicit form in Jumbo.
The simultaneous exploration became what Hofstadter calls a "parallel terraced scan," a search strategy inspired by the Hearsay II speech-understanding project led by Raj Reddy. A parallel terraced scan explores different paths in parallel to different depths, working, Hofstadter assures us, much like sorority rush in Bloomington.
Another element of the architecture is the coderack. The procedural content of Jumbo is encoded in minimalist codelets that reside in a coderack and are invoked at random, but with a probability influenced by decisions the program is making. These decisions are the cumulative result of the working of codelets, so the whole process is, Hofstadter says, self-sensitive and self-driven.
Whatever "intelligence" or problem-solving ability the program has emerges from the semirandom action of these codelets, rather than being coded in. This is exactly the claim of emergent intelligence sometimes made by neural-net proponents, but Jumbo is fundamentally different from a neural net. For one thing, it operates at a much higher level.
FARG next turned its collective eye upon the game of "Numble" in which the goal is to construct a given number from a set of five other numbers and the operations of addition, subtraction, and multiplication. Each of the five can be used at most once, and numbers can be grouped with parentheses; for example, Make 114 from 11, 20, 7, 1, and 6. The Numbo program tackled such puzzles very much as Jumbo tackled Jumbles puzzles. That's the most interesting thing about the program, in fact. Hofstadter and FARG are interested in finding general mechanisms of creativity and intelligence, so it is particularly significant that Jumbo and Numbo could almost be described as being the same program, applied to different domains.
That idea is taken much further in the chapter that describes the Tabletop program. Tabletop originated with Hofstadter explaining analogy problems to one listener or another across the table at the Runcible Spoon coffeehouse.
Hofstadter pushed around cups and spoons on his side of the table and then invited the listener to "do the same thing." Since the listener's side of the table often had a different set and configuration of objects, the reader often had to generalize the concept "do the same thing" in interesting ways.
Tabletop operated in a very small domain, but its "do the same thing" concept scales up to larger domains. Hofstadter describes variations on the theme: BattleOp, Op-Platte, and other anagrams name possible programs for larger domains. Ob-Platte would tackle problems like, "What is the Ob (river) of Kansas?" (Answer, the Platte.) Or "What is the Vatican City of Indiana?" "What is the Athens of Georgia?"
There's a lot more detail in the book regarding these programs. And I haven't described the most substantial of FARG's programs, CopyCat, a program that solves letter-string analogy puzzles such as "The string abc is changed into abd. Now do the same thing to the string xyz." "The string abc is changed into abd. Now do the same thing to the string mrrjjj."
Then there's Letter Spirit, a program in the works for designing typefaces. But it's more important to summarize some of the book's criticisms of "traditional" artificial-intelligence work.
Among the points are these, paraphrased in my terms:
Here are the solutions to the number-sequence puzzles presented in this column:
Here are some possible solutions to the letter-string puzzles: The string abc is changed into abd. Now do the same thing to the string xyz. Sure, there's xya, but how about wyz? You might consider at what level(s) you are drawing analogies if you come up with that; Hofstadter speaks of the analogy between the successor and predecessor relationships.
The string abc is changed into abd. Now do the same thing to the string mrrjjj. You might come up with mrrkkk, but isn't mrrjjjj better? But the analogy you have to draw to come up with this is pretty abstract: You're mapping alphabetical position onto run length.
Here are the solutions to the Ob-Platte puzzles:
Copyright © 1995, Dr. Dobb's JournalEnter Douglas Hofstadter
Seeking Whence
1, 2, 2, 3, 3, 3, 4, 4, 4, 4, _
2, 3, 5, 7, 11, 13, 17, 19, _
3, 5, 11, 17, 31, 41, 47, 59, _
1, 1, 3, 4, 2, 2, 5, 6, 7, _
2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, _
Themes of the Research
Numb and Number
Runcible Ruminations
Hofstadter's Critique(s) of AI
Hofstadter goes beyond this, with some scathing critiques of some specific computer models. His approach, he says, differs from expert systems and neural nets, taking a "middle ground" between these high- and low-level approaches. Time will tell whether Hofstadter's research program will inspire others to take the middle ground, but one thing is clear: He has presented an original approach to AI and done so in a very entertaining way.Solutions to the Puzzles
Here's the solution to the Numbo puzzle: Make 114 from 11, 20, 7, 1, and 6. Chances are you came up with 20*6-7+1 rather than the apparently simpler (20-1)*6. Why is that?