I’ve recently come across a fascinating blog post by Cambridge mathematician Tim Gowers. He and computational linguist Mohan Ganesalingam built a sort of automated mathematician which does the kind of “routine” mathematical proofs that mathematicians can do without backtracking. Their system was based on a formal theory of the semantics of mathematical language, together with introspection into how they solved problems. In other words, they worked through lots of simple examples and checked that their AI could solve the problems in a way that was cognitively plausible. The goal wasn’t to build a useful system (standard theorem provers are way more powerful), but to provide insight into our problem solving process. This post reminded me that, while our field has long moved away from this style of research, I think there’s still a lot to be gained from it.
Introspection has a long and distinguished history in the early days of AI:
- Newell and Simon’s General Problem Solver  was explicitly based on intuitions about how we solve problems, and they developed it by working through lots of examples by hand
- Lenat’s Automated Mathematician  was supposed to make mathematical conjectures based on heuristics that human mathematicians followed
- Hofstadter’s book Fluid Concepts and Creative Analogies  details AI systems which serve as cognitive models for a variety of toy problems. Some nice examples are Seek-Whence (for explaining number sequences) and Copycat (for letter string analogies).
Like Gowers’s work, these classic systems were intended primarily as cognitive models. Simon was inspired to work on AI when he did consulting work on group decision making for the air force and found that he didn’t have an adequate formalism for explaining their decision making process . Lenat was at least partially motivated by formalizing Polya’s notion of a heuristic, since he thought informal lists of heuristics probably oversimplified the process of mathematical discovery and suffered from hindsight bias . The idea was that translating our own heuristics into mathematically precise algorithms gives a more rigorous way of testing which strategies are capable of solving which problems.
But introspection has largely fallen out of favor in AI, at least the parts I’m familiar with (machine learning, vision, probabilistic inference). The field has a Behaviorist-like aversion to thinking about algorithms in terms of plausible mental representations and cognitive strategies. I can think of several plausible arguments against introspection:
- We already have rough outlines of a solution for most of the problems we’re interested in, and introspection won’t help us fill in any of the details.
- Computers are a different enough computational architecture from the brain that we can’t expect any insights to carry over. I.e., computers can perform billions of sequential operations per second (which often makes brute force a more viable strategy), whereas the brain has more effective associative memory and high-level representations.
- Introspection isn’t scientific, since different people will disagree. The explanations are likely just someone’s idealized story about what’s actually a much messier process. (E.g., cognitive scientist Jeff Shrager spent three years training to be a molecular biologist, and during this time, he couldn’t find any examples of the cross-domain analogies that cognitive scientists had touted as so fundamental to scientific discovery.)
- It’s hard to predict what range of problems an introspection-based strategy will generalize to.
As far as the first point, I think there are still plenty of hard problems for which we don’t even have the outlines of a solution. The remaining points seem hard to argue with, but they basically just show that introspection is a source of intuition rather than a rigorous way of evaluating algorithms. I’d say we have three major sources of intuition in our field:
- trying out models and algorithms in a variety of settings, both real-world applications and toy problems
- peer-reviewed research in cognitive science and neuroscience
Neuroscience and cog sci both had a large influence on both machine learning and computer vision in the early days, but as the field as matured, algorithms have made up a larger and larger part of our intuitions. Introspection is rarely mentioned.
In my own work on structure learning, my co-authors and I made several design decisions based on how human researchers would approach a problem. In my matrix decompositions work :
- we often come up with structured probabilistic models by first fitting a simpler one to the data, seeing if there are dependencies in the learned representation which aren’t captured by the model, and adding those explicitly to the model
- if we’re trying to do inference in a complex probabilistic model, it often works to initialize it from a simpler one
And for Gaussian process structure search :
- a good strategy for building up structured GP models is to try to model the residuals of the current model, and add the resulting kernel to the model
- when we use the above strategy, the previously learned kernel hyperparameters make a good initialization for the larger model
Of course, for the aspects of our algorithms that have already been well-explored (such as inference in particular models), we went with the standard approaches. There’s no point in thinking, “How would I try to factorize this matrix…” But since hardly anyone has explored how to structure model spaces in a way that’s searchable, these intuitions provided useful guidance in the design of our spaces of models.
Like any source of intuition, introspection is just a starting point. It’s not a rigorous scientific argument, and it ultimately needs to be backed up with math and experiments. What we really want is an explanation for the heuristics people use. In other words,
- figure out what regularities our heuristics are exploiting
- see if existing algorithms already exploit those same regularities
- if not, come up with one that does
- justify it theoretically and empirically
You can think of this as a sort of “inverse Bayesian optimization.” I’m currently working on taking the heuristics from my structure search papers and explaining mathematically why they work, so that we know in what set of situations they are appropriate. Hopefully this will result in a more general and more robust way to exploit the same structure.
 A. Newell, J. C. Shaw, and H. A. Simon. Report on a general problem-solving program. Tech report, 1958
 D. B. Lenat and J. S. Brown. Why AM and Eurisko appear to work. Artificial Intellgience, 1984.
 D. R. Hofstadter. Fluid Concepts and Creative Analogies: Computer Models of the Fundamental Mechanisms of Thought. Basic Books, 1996.
 H. A. Simon. Models of My Life. MIT Press, 1996.
 D. B. Lenat. The Nature of Heuristics. Tech report, 1980.
 R. B. Grosse, R. Salakhutdinov, W. T. Freeman, and J. B. Tenenbaum. Exploiting compositionality to explore a large space of model structures. UAI, 2012.
 D. Duvenaud, J. R. Lloyd, R. B. Grosse, J. B. Tenenbaum, Z. Ghahramani. Structure discovery in nonparametric regression through compositional kernel search. ICML, 2013.