玫瑰花瓣教给我们的归纳法启示

原文

What Rose Petals Teach Us about Induction

Richard Hamming famously used to ask his colleagues at Bell Labs this question: “What is the most important problem in your field, and why aren’t you working on it?” To which they probably replied, “Look, Dick, it’s eight-thirty in the morning. I haven’t even had my coffee yet. Who starts a conversation like that?”

Still, it’s a good question, isn’t it? For me, the answer is obvious: “Is there a general method for induction?” Now, you might think that the human race has a pretty good handle on induction, what with the scientific method and statistics and all that. But no: there’s a gap in the very foundation of our understanding, a gap we can only cross occasionally and haphazardly.

Hume called it the problem of induction; a catchier name is the No Free Lunch theorem, although it’s about as far from being a “theorem” as it’s possible to get. And it is simply this: there is no general, systematic way to go from observation to understanding.

If you haven’t encountered it before, it’s likely you don’t see what the big deal is. Don’t we all do this all the time, without even thinking about it? We do, but we don’t know how we do it, which means we don’t know how to teach it, how to automate it, or even if we’re doing it right.

What’s needed is a simple, concrete example which illustrates the idea without any particular need for mathematical sophistication. I’m going to give just such an example, show how various algorithmic approaches fare, and try to explain the unavoidable trade-off at the heart of the problem.

If all goes well, you’ll not only learn something important about one of the most fundamental unsolved problems out there, you’ll have developed a practical intuition that will help you understand, for example, why François Chollet introduced the ARC-AGI benchmark, why AI researchers keep talking about world models, and what it means to say the transformer architecture hits a sweet spot for language models.

The Game

Let’s start with a bit of nerd folklore, traditionally passed down by a friend who knows the trick and judges you to be the kind of person who will enjoy it. I’ve replicated the experience as nearly as possible here. You don’t have to solve it, necessarily, but you do have to make an honest effort if you want to fully grasp the underlying lesson.

'); import('/demos/rose-petals/widget.js') .then(module => module.loadRosePetalsWidget('#rose-petals-widget')) .catch(error => { console.error('Unable to load Rose Petals widget.', error); document.getElementById('rose-petals-widget').hidden = true; });

play Petals Around the RoseWikipedia page

All done? Great! What method did you use? Could you teach your method to a child? Could you write a program that implements your method? No? Well, I can’t either. That’s what this article is about. But let’s give it a shot anyway, using some off-the-shelf machine learning algorithms, and see if that tells us anything.

Spoilers Ahead!

Algorithmic Approaches

Here’s what I did. Different machine learning algorithms were shown a gradually increasing number of examples; each example consists of the numeric values of the five dice rolls as well as the correct number of petals around the rose for those dice. Each algorithm, in its own way, learns a function which maps those dice rolls to the number of petals. Then, its performance is evaluated on a different set of examples, ones it hasn’t seen before and wasn’t trained on. Whatever number the function outputs is rounded to the nearest integer and marked correct only if it exactly matches the true number of petals; if it’s off by even 0.5, it’s marked incorrect. The test accuracy is the proportion of dice rolls that it gets correct. Once a given algorithm has reached 100% accuracy, we deem that it’s saturated the benchmark and stop. The minimum number of examples needed to reach 100% accuracy is marked with a point and shown as the $N$ in the legend.

(By the way, the full source code and summary report are available on GitHub if you’re interested in the gory details.)

In a minute we’ll go case-by-case to try to understand why each approach fared well or badly, but first let’s just take a look at the high-level results:

Summary chart of different approaches

Even at a glance, there are already some very interesting conclusions we can draw from the graph. First of all, it’s obvious that some of them solve it almost immediately, some struggle for a long time before noticing the pattern, and some never solve it at all. So there’s something that makes some approaches better or worse than others at this specific problem.

It’s also interesting that each curve seems to follow the same characteristic shape, even across fundamentally different learning algorithms. Each appears to require a certain minimum number of examples before it even starts to learn anything, but once it catches on progress becomes rapid and quickly reaches 100%. Perhaps this mirrors your own experience?

The obvious question, then, is why do different algorithms need different numbers of examples to “solve” petals around the rose? Is it just random? Is it opaque and unknowable, and we just have to try different approaches at random? Not at all.

Inductive Bias

The key concept is called inductive bias. A model’s inductive bias is, roughly speaking, a combination of its priors and its assumptions; that is, the kind of patterns it tends to prefer or be a good match for, and the structure that it requires any possible solution to have.

Models with an inductive bias that matches the specific structure of a dataset will learn it quickly, sometimes from just a handful of examples. Less specific, more general models with a larger hypothesis space to explore need far more examples to pick up on any patterns. And a model that has the wrong inductive bias or makes assumptions that directly contradict the true structure of the problem will never be able to learn anything at all.

Let’s dive into the specific details of a few of these algorithms to understand what exactly it is that makes them a good or poor fit for this problem.

Naïve Linear Regression

Let’s start with an intentionally weak linear model that serves as a baseline:

naive linear results

What makes this approach “naïve” is that it simply uses five numeric features, one per die. Any ML enthusiast will tell you that’s stupid; but in a little bit we’ll see several other models that do just fine when fed the raw data in this format, so why should we spoon-feed the linear model?

You can see from the graph that this approach hasn’t made any progress, even after being shown 1,000 examples, but it’s actually worse than that: this algorithm cannot solve the problem. It never will; its inductive bias includes the assumption that the true model is linear in its parameters, which just isn’t true for this problem.

Consequently, this model is literally incapable of representing the true solution. I include it mainly as a warning for what happens when inductive bias goes wrong: make the wrong assumptions, and it’s not a matter of merely taking a little longer to catch on; you can end up with a model that just doesn’t work.

LR With Categorical Features

Of course, this is easily fixed using bog-standard feature engineering. One-hot encoding the dice rolls as categorical levels gives the model a better “vocabulary.”

categorical linear results

Now it can treat each face as a separate case, and is able to find the solution. But not, as you’ll note, particularly quickly. The reason for that is simple: it’s treating each die separately, and has to “relearn” the rule for each die independently. Now, if the petals rule were something like “take the sum of the first, middle, and last die, ignoring the other two” then that would pay dividends: the model is flexible enough to learn different parameters for different dice. However, since that’s not how the rule works, this approach is slightly slower.

Bincount Pivot

There’s actually an even better feature representation that allows linear regression to solve the problem very quickly. Instead of treating each die as a feature, why don’t we have six features, each of which represents the number of dice showing a particular value?

def bincount(X: npt.NDArray[np.int_]) -> npt.NDArray[np.int_]:
    return np.array([np.bincount(row, minlength=7)[1:7] for row in X])

This feature encoding makes the regression part trivial, and unsurprisingly it solves it with just $N=6$.

However, this doesn’t feel like the model is learning anything—we basically solved the problem for it. Once we have the idea to try this representation, we don’t even need to use regression, because the pattern is so obvious:

bubble chart

So, let’s look at some more general models that don’t feel like they’ve been hard-coded to solve this particular problem.

Fully Connected Neural Net

Neural networks are often sold as a way to avoid feature engineering. Sometimes that is true. Sometimes it just means asking a very flexible model to do the feature engineering for you, slowly, unreliably, and at great expense. That’s certainly the case here; the large, fully connected neural net we used is a very powerful, very general model, and it’s able to work from the raw features (without categorical encoding.) But it takes more than a thousand examples to solve it:

FCNN results

Note that this is after hyperparameter optimization: I let Optuna try hundreds of configurations—activation functions, layer sizes, learning rates—and out of millions of possible FCNN models, this was the best one. Let’s sit with that a minute, and really think about the decisions being made, and why they work.

First of all, sigmoid activation works best for this problem. That’s interesting because sigmoid is not often the best choice for modern deep learning networks, where “hinge” style activations like ReLU or SwiGLU usually work better. However, sigmoid makes it easy to construct step functions, so it wins here:

activation function hyperparameter optimization results

The other really interesting role of hyperparameters is tuning the overall “complexity” of the model. For example, there’s a strong global minimum near 150 neurons on the second hidden layer:

number of hidden neurons hyperparameter optimization results

Now, it doesn’t need anything like 150 hidden neurons to merely represent the solution, but industry experience has shown that neural nets need a lot of “extra” hidden neurons to learn solutions, because the random initialization means that only a subset will be primed to learn the “true” function. Still, if we give it too many, it gets lost in a high-dimensional maze, and if we give it too few, it will get stuck in a local minimum before finding a really good solution.

The reason I bring up hyperparameter optimization at all is to make the point that inductive bias isn’t just a function of the algorithm family you choose: most algorithms can (and should) be tuned to have just the right bias for a specific dataset, and that takes the form of both having the right structure (sigmoid activation in this case) and the right level of complexity (number of hidden neurons.)

One last thing about the FCNN. In this animation (which shows the response surface for only the first two dice for simplicity), we can watch its “understanding” evolve over time, gradually converging to the true solution:

FCNN learning response surface animation

We can see the model is learning, but it’s not learning it the way a human would. It’s not looking for rules, just building up and refining an intuition for where it’s “high” or “low.”

Deep Sets Neural Net

To try and do better, let's try Deep Sets, a moderately obscure architecture with a useful inductive bias: permutation invariance. The Deep Sets architecture^* bakes in the assumption that the order of the dice does not matter.

Deep Set architecture

Although this is a pretty exotic deep learning model, the code is almost embarrassingly simple with PyTorch, which is very good at letting us wire together neural networks with whatever topology we want:

class DeepSetNN(nn.Module):
    def __init__(self) -> None:
        super().__init__()
        self.phi = nn.Sequential(
            nn.Linear(6, 8),
            nn.ReLU(),
            nn.Linear(8, 1),
            nn.ReLU(),
        )
        self.rho = nn.Sequential(
            nn.Linear(1, 8),
            nn.ReLU(),
            nn.Linear(8, 1),
        )

    def forward(self, x: torch.Tensor) -> torch.Tensor:
        phi_x = self.phi(x)
        sum_phi = phi_x.sum(dim=1)
        return self.rho(sum_phi)

Since the true rule really does exhibit permutation invariance, this inductive bias should help it learn the pattern quickly, and in fact the difference is night and day:

Deep Set results

The Deep Sets model doesn’t have to “relearn” the rule separately for each die position; in fact, it’s basically getting five independent “lessons” from each example, allowing it to learn the rule perfectly from just six examples (a total of 30 dice).

However, the risk is high: suppose the true rule hadn’t been permutation invariant? Then the Deep Sets model would have been completely unable to learn the rule at all (just like the naïve linear example we first looked at) no matter how many examples it was shown.

Decision Trees

Finally, let’s try decision trees, which are often the best off-the-shelf models for structured, categorical data. We’ll use sklearn’s HistGradientBoostingRegressor, which can automatically bin the continuous dice values into categories.

All tree models share a particular inductive bias: they believe that the world is made of axis-aligned boxes. They carve up the feature space with rules like “is the third die showing at least a three? If so, is it five or less?” and so on. This results in sharp, axis-aligned decision boundaries, in contrast to the softer ones found by stacking sigmoids together:

Neural Network vs. Tree response surfaces

Now, in this case, that inductive bias turns out to be exactly correct. Faces are discrete, so “is this particular die a three or a five?” is exactly the kind of question a split can ask, and the tree doesn’t have to waste time laboriously bending smooth sigmoids into step functions the way the neural net did. But it’s not a perfect inductive bias either: nobody told the tree that dice are an unordered set, so like the categorical regression it has to re-discover the same rule at each die position, one split at a time.

That makes trees an interesting middle ground: not the wrong bias (naïve linear regression, which never solves it), not the perfect bias (Deep Sets, which solves it from six examples), but an “okay” bias that lands in the middle.

Scorecard

To summarize the summary:

Approach	Learning Speed	Inductive Bias	Limitations
Naïve linear regression	never	rule is linear function of face values	rule must be linear with respect to face values
Fully connected NN	slow	the rule is a smooth function of five numbers	needs a ton of data
LR, categorical features	medium	each die/face combination has its own effect	doesn’t consider interactions between dice
Decision tree	medium	rule is made of discrete, axis-aligned splits	struggles with smooth, rotated, or diagonal structure
LR, bincount pivot	fast	only the count of each face matters	no position-dependent rules, no interactions
Deep Sets NN	fast	dice are an unordered set	any position-dependent rule

Notice the trade-off running down the table: the stronger the inductive bias, the more closely it matches the real structure of the problem, the fewer examples needed. On the flip side, even a single bad assumption will completely break the model.

Did They Really Solve It?

Imagine if you had figured out the rule, and then were shown this generalization to twelve-sided dice. Such dice are dodecahedrons, so they have pentagonal faces. What’s the number of petals around the rose for the left die? For the right one?

d12 showing five and six with pips

If you had learned the rule “n-1 but only for odd n” then you would get it exactly wrong; but if you had listened to all the clues, and really understood the rule, you’d be able to answer immediately and confidently, even though you are generalizing well outside anything in the original training set.

This might feel kind of unfair, but machine learning people put a huge emphasis on evaluating a model’s “generalization performance,” that is, how well it does on examples outside what it was originally trained on. That proves that it actually learned some kind of rule or pattern instead of just memorizing specific examples.

However, you’ll note that none of the machine learning approaches I tried could actually do this. None of them are actually “looking” at the dice; they’re just looking at five numbers. There’s no way they could generalize to the twelve-sided case.

Of course, there are models which do take images as inputs, and in theory such models would at least have the raw information they need to learn the true rule. The problem is that current-gen vision models still kind of suck at visual reasoning. The paper Vision Language Models are Blind makes this point in a dozen different ways; we’re often so impressed that vision models can see anything that we overlook the fact that their grasp on the details is much worse than that of a five-year-old child.

That’s why François Chollet’s ARC-AGI benchmark is (probably) a good target: once vision models can solve that, they’ll be one step closer to true visual thinking. Of course, the long-term goal is world models; a model which can learn a coherent 3D model of the world around it would probably be able to solve petals around the rose the “right” way, by really understanding the spatial relationships of the pips.

Language Models

Let’s try to apply what we’ve learned. Petals Around the Rose is a toy problem, but the same kind of thinking can be applied to any kind of model, such as large language models.

It’s popular to dismiss LLMs as “just next token predictors.” This is technically true, but also kind of misses the point. Markov chains, RNNs, and transformers are all language models that can be described as “next token predictors,” but they don’t all work equally well. A better question to ask is: “What is this model’s inductive bias?”

A Markov chain (an $n$-gram model) assumes the next word depends on the previous $n$ words, and that each possible combination of $n$ words has a completely independent parameter. (Andrey Markov proposed using this language model over a century ago, making it the granddaddy of modern LLMs.) So, for a vocabulary of size $V$, there are $V^n$ parameters to learn. For even a smallish $n$ like 5, that already explodes the hypothesis space beyond what can be learned from even a huge text corpus like the entire internet. And, simultaneously, having a context window of only the previous 5 words is grossly inadequate for modeling real-world language. Like our FCNN above, this model suffers from having an inductive bias which is too weak.

RNNs tried to fix this problem by compressing the entire history into a single fixed-size state vector, updated one token at a time. But that compression is itself a brutal assumption: everything worth remembering about the past must survive being squeezed through a tiny bottleneck at every step. In practice, RNN models quickly lose the plot after a handful of sentences. Locally, the text they generate looks grammatically correct and meaningful, but zoom out a little and they’re basically nonsense generators. Like our naïve linear model, this model suffers from having an inductive bias which is too strong.

Transformers manage to hit a sweet spot: by keeping the recent history around as a working memory, and attending to different parts of it at different times, the transformer’s bias matches real structure in language: the referent of a pronoun, the subject of a verb, the parenthesis waiting to be closed. Not only that, but the particular structure of the transformer, basically a weighted sum of semantic vectors from the context window, has empirically been shown to somehow be a “good enough” match for the structure of real-world language found in the wild.

Transformers aren’t “smarter” than other possible language models, they just happen to land in that Goldilocks zone where their inductive bias is just right.

Greek Philosophy

Now, at this point you may be wondering, “If induction is so hard, how do we (human beings) do it?” This is an old question, and it’s worth looking at an old answer; in this case, at what Aristotle had to say about it.

Greek thought gave great primacy to deduction, but deduction relies on first principles (axioms) which are themselves unproven. Where do they come from? Aristotle didn’t have a complete answer, but he did recognize the problem and knew that humans could in fact do it. He called this faculty nous: our capacity to discover first principles.

It is not mere observation, a piling up of facts from sense; in his book on logic, Aristotle explained that nous is distinct from deduction, because deduction has to start from something. It’s the part of human reason that finds the pattern, that moves from the particular to the universal.

It’s hard to define, but if you solved Petals Around the Rose then I don’t need to define it for you: you experienced it yourself, first-hand.

Of course, Aristotle didn’t have the last word on the subject, either.

The Scientific Method

It’s important to point out that humans aren’t free of inductive bias, not by a long shot. The people who do induction for a living, who we usually call “scientists,” each have their own personal biases, and we as a species share a large number of irrational inductive biases.

To take one famous example, Einstein had an inductive bias towards pure geometry. It’s what led him first to special relativity and eventually to general relativity: the rock-hard, foundational belief that you could understand the universe by doing thought experiments to identify a few geometric axioms and working deductively from there. This bias worked well for him for relativity, and betrayed him when it came to quantum mechanics, where thinking of particles as points is simply the wrong intuition.

I don’t want to single out Einstein here: the exact same geometric bias may have led the entire field of physics down a blind alley with string theory and friends. (Although the jury is still out on that one.) It worked beautifully for some problems, and then just didn’t work at all on others.

To deal with this problem, we’ve developed an algorithm of sorts. If individuals have different inductive biases, you simply have to use more of them: throw thousands of the most brilliant, most creative brains at the problem and hope one of them, purely by chance, has a genetic predisposition to have an inductive bias ideally suited to solving the problem. Since we can’t know in advance which approach will pan out, we just brute force it in parallel. As anyone who’s experienced academia can tell you, this process is spectacularly inefficient and honestly a bit hard on the grad students, who are little more than grist for the mill in this process.

Arguments Against

There’s still a pretty big elephant in the room that we have to address. While it would surely be convenient if a general method for induction could be found, there are also some strong arguments that no such method exists, even in principle.

While there might be reason to believe the fundamental laws of nature must in some sense be very simple, there’s no reason at all to believe that all phenomena would even need to have any solution or explanation simpler than themselves. Emergent phenomena such as entropy, turbulence, and evolution arise out of complex systems and must be studied empirically. How can there be a general method for finding the right rule if, sometimes, there is no rule to find?

Paul Feyerabend wrote a book called Against Method. He took a long, hard look at the history of science as it was actually practiced and pointed out that science didn’t advance by any fixed, repeatable method; in fact, it is precisely when we abandon all methodology and best practice that great leaps forward occur. To be clear, he wasn’t against rigor or careful thinking, but against ossified, rigid methods, the kind that puts your brain on autopilot; in other words, precisely the kind of cargo cult adherence to prior art that tends to develop over time in any mature field. This suggests that any attempt to pin down some kind of general method of induction isn’t just doomed: it’s actively harmful.

Luckily for me, any potential for harm is purely a theoretical possibility, because as of right now we don’t have the faintest clue how to do it.

Summary of current progress

Promising Avenues

Actually, that’s not quite true: we’ve learned quite a bit about induction in the 400 years since Francis Bacon first took a stab at systematizing it. Machine learning is teaching us a lot about how learning works, both in terms of abstract theory and hard-won practice. Computer science reframes learning as search and optimization over a hypothesis space—and reminds us that computational efficiency often beats theoretical sophistication. Modern statistics contributes tools for analyzing endogeneity and causality. Cognitive psychology probes non-deductive reasoning with instruments like Raven’s Progressive Matrices, Guilford’s Alternate Uses Task (“how many uses for a brick can you think of?“), and the Remote Associates Test. Finally, the philosophy of science has lots of good advice on rejecting bad theories and testing hypotheses via the hypothetico-deductive method—though it has less to say about where good hypotheses come from in the first place.

So, I don't want to give the impression that people aren't working on the problem, or that we're not making progress. We absolutely are. But in its general form the problem of induction is still unsolved. In practice, we're still stuck with Feyerabend's "anything goes," Aristotle's ill-defined nous, and Feynman's quote-unquote "algorithm":^†

Write down the problem
Think really hard
Write down the solution

Conclusion

Why is induction hard? Why isn’t there a free lunch? I believe it’s ultimately computational—the space of all possible hypotheses is simply too large to blindly brute force. Therefore, in order to make headway, we need heuristics to guide us; some kind of insight to lead us towards reasonable hypotheses. When the heuristic happens to match the problem everything is grand, and when it doesn’t it’s like being lost on a foggy, moonless night.

You might think LLMs might be able to help with this but while they can do it a little, they’re not even as good at it as we are. If LLMs are a blurry JPG of the internet, which itself is a subset of all human knowledge, why would you expect them to have a capability that we haven’t figured out ourselves?

Our best approach is the collection of techniques and social structures we call “science,” which is a pretty inefficient process: scientific progress is measured in lifetimes spent for the smallest insight. It took us thousands of years to fit an ellipse through some points, or to realize that washing our hands was important. There’s got to be a better way.

We already have so many pieces of the puzzle… we just haven’t been able to put them together yet. Ironically, what’s needed is nous, that inductive leap to a single brilliant insight. Despite all the difficulties, I really feel like we’re getting closer, that someone will make a fundamental breakthrough soon. Maybe it will be you.