Bongard Problems

For LLMs:<br>Markdown<br>Open in ChatGPT<br>Open in Claude

Markdown<br>Open in ChatGPT<br>Open in Claude

Bongard problems are interesting puzzles; they’re sort of like Spot The Difference meets Raven’s Progressive Matrices. When presented with two sets of images, the challenge is to identify the latent property that is shared by everything on the left but absent (or different) from everything on the right.

Here’s a simple Bongard problem, created by Mikhail Moiseevich Bongard:

Bongard problem 10, by Mikhail Moiseevich Bongard

NoteReveal Solution

Solution: Shapes on the left form approximately triangular outlines, while shapes on the right form approximately quadrilateral outlines.

And here’s a trickier Bongard problem, created by Douglas Hofstadter:

Bongard problem 155, by Douglas Hofstadter

NoteReveal Solution

Solution: On the left, curves are longer than straight lines, while on the right, curves are shorter than straight lines.

I first learned about Bongard problems while reading Gödel, Escher, Bach, when Hofstadter introduced them in his chapter Artificial Intelligence: Prospects. I’ve returned to Hofstadter’s puzzles before, but Bongard problems are especially interesting because he used them to imagine, in 1979, what a visual reasoning program might look like:

First, he imagined a preprocessing stage that detects salient features that map to a mini-vocabulary of known concept terms like, line segment, or curve, or horizontal. From there, preprocessing applies its knowledge of elementary shapes to get to terms like, circle, or right angle, or vertex. There’s a resemblance here to what we now call representation learning. In image classifiers built as convolutional networks, the network learns internal representations useful for discriminating images, though as distributed numerical representations rather than as tidy vocabulary of named concepts. And CLIP is an especially interesting modern comparison because it learns image and text representations in a shared space, allowing natural-language descriptions to refer to learned visual concepts.

At this point in Hofstadter’s imaginary program, the picture is “understood” at the basic level of mapping input images to labels. The next stage is a search for high-level descriptions about the features. The program “looks around” to spot descriptors like to the right of, or perpendicular to, or evenly spaced. It can also build descriptions of descriptions , looking for regularities across the ways individual images have been described. There’s a resemblance here to modern work on relational reasoning, where models try to represent not only the objects in an image but also the relationships among them.

But simply generating more descriptions doesn’t solve a Bongard problem. The program also has to decide where to focus and which kinds of properties to filter for. A description can be perfectly true and still be useless for distinguishing the two sides. The right abstraction may only become visible after comparing several images, changing what seems important, and returning to an earlier description with a different idea of what to look for.

Hofstadter suggested various approaches and heuristics for making that search less brittle. He imagined templates and sameness-detectors that could trigger when several examples began to converge on the same description. There’s a loose modern parallel in some approaches to meta-learning, where models learn a space in which examples can be classified by their distance from a common prototype. He also suggested a semantic net in which “all the known nouns, adjectives, etc., are linked in ways which indicate their interrelations.” That sounds a lot like word embeddings.

A portion of Hofstadter’s proposed concept network for a Bongard problem-solving program

Importantly, Hofstadter didn’t want early concepts or hypotheses to be rigid. An idea that didn’t quite fit might be weakened, modified, or allowed to slip toward a related concept rather than simply discarded. A shape might be treated as a rough instance of something it doesn’t satisfy exactly, or a group of objects might become a single higher-level object once the problem suggests looking at it that way. There’s a connection here to analogical reasoning, where representations of relationships need to be flexible enough to map across different situations. More broadly, Hofstadter’s program depends on representations remaining tentative enough that higher-level hypotheses can change how the underlying images are described.

The chapter continues to dig into more layers of what this Bongard problem-solving program might require, and how it maps to various forms of recognition, grouping, filtering, and focusing. It’s not the only place in GEB where Hofstadter’s ideas map strangely well onto modern AI, but here he keeps circling two important assertions:

These fascinating problems are intended for pattern-recognizers, whether human or machine.

and

the...