This post arose from a feeling in a few conversations that I wasn't being crisp enough or epistemically virtuous enough when discussing the relationship between gradient-based ML methods and natural selection/mutate-and-select methods. Some people would respond like, 'yep, seems good', while others were far less willing to entertain analogies there. Clearly there was some logical uncertainty and room for learning, so I decided to 'math it out' and ended up clarifying a few details about the relationship, while leaving a lot unresolved. Evidently for some readers this is still not crisp or epistemically virtuous enough!
I still endorse this post as the neatest explanation I'm aware of relating gradient descent to natural selection under certain approximations. I take the proof of the limiting approximation to be basically uncontroversial[1], but I think my discussion of simplifying assumptions (and how to move past them) is actually the most valuable part of the post.
Overall I introduced three models of natural selection
All three are (in the limit of small mutations) performing gradient steps. The third one took a bit more creativity to invent, and is probably where I derived the most insight from this work.
All three are still far from 'actual real biological natural selection'!
Another point I didn't touch on in this post itself is what to make of any of this.
For predicting the nature of ML artefacts, I don't think speciation is relevant, so that's a point in favour of these models. I do think population-dependent dynamics (effectively self-play) are potentially very relevant, depending on the setting, which is why in the post I said,
As such it may be appropriate to think of real natural selection as performing something locally equivalent to SGD but globally more like self-play PBT.
One main conclusion people want to point to when making this kind of analogy is that selecting for thing-X-achievers doesn't necessarily produce thing-X-wanters. i.e. goal-misgeneralisation aka mesa-optimisation aka optimisation-daemons. I guess tightening up the maths sort of shores up this kind of conclusion?[2]
Thomas Kwa has a nice brief list of other retrodictions of the analogy between gradient-based ML and natural selection.
How much can we pre-dict? When attempting to draw more specific conclusions (e.g. about particular inductive biases or generalisation), I think in practice analogies to natural selection are going to be screened off by specific evidence quite easily. But it's not clear that we can easily get that more specific evidence in advance, and for more generally-applicable but less-specific claims, I think natural selection gives us one good prior to reason from.
If we're trying to draw conclusions about intelligent systems, we should make sure to note that a lot of impressive intelligence-bearing artefacts in nature (brains etc.) are grown and developed within-lifetime! This makes the object of natural selection (genomes, mostly) something like hyperparameters or reward models or learning schedules or curricula rather than like fully-fledged cognitive algorithms.
In a recent exchange, 1a3orn shared some interesting resources which make similar connections between brain-like learning systems and gradient-based systems. More commonalities!
Sometimes people want to understand the extent to which natural selection 'is optimising for' something (and what the exact moving pieces are). Playing with the maths here and specifying some semantics via the models has helped sharpen my own thinking on this. For example, see my discussion of 'fitness' here
The original pretheoretic term 'fitness' meant 'being fitted/suitable/capable (relative to a context)', and this is what Darwin and co were originally pointing to. (Remember they didn't have genes or Mendel until decades later!)
The modern technical usage of 'fitness' very often operationalises this, for organisms, to be something like number of offspring, and for alleles/traits to be something like change in prevalence (perhaps averaged and/or normalised relative to some reference).
So natural selection is the ex post tautology 'that which propagates in fact propagates'.
If we allow for ex ante uncertainty, we can talk about probabilities of selection/fixation and expected time to equilibrium and such. Here, 'fitness' is some latent property, understood as a distribution over outcomes.
If we look at longer timescales, 'fitness' is heavily bimodal: in many cases a particular allele/trait either fixes or goes extinct[3]. If we squint, we can think of this unknown future outcome as the hidden ground truth of latent fitness, about which some bits are revealed over time and over generations.
A 'single step' of natural selection tries out some variations and promotes the ones which in fact work (based on a realisation of the 'ex ante' uncertain fitness). This indeed follows the latent fitness gradient in expectation.
In this ex ante framing it becomes much more reasonable to treat natural selection as an optimisation/control process similar to gradient descent. It's shooting for maximising the hidden ground truth of latent fitness over many iterations, but it's doing so based on a similar foresight-free local heuristic like gradient descent, applied many times.
How can we reconcile this claim with the fact that the operationalised 'relative fitness' often walks approximately randomly, at least not often sustainedly upward[4]? Well, it's precisely because it's relative - relative to a changing series of fitness landscapes over time. Those landscapes change in part as a consequence of abiotic processes, partly as a consequence of other species' changes, and often as a consequence of the very trait changes which natural selection is itself imposing within a population/species!
So, I think, we can say with a straight face that natural selection is optimising (weakly) for increased fitness, even while a changing fitness landscape means that almost by definition relative fitness hovers around a constant for most extant lineages. I don't think it's optimising on species, but on lineages (which sometimes correspond).[5]
In further (unpublished) mathsy scribbles around the time of this post, I also played with rederiving variations on the Price equation, and spent some time thinking about probabilities of fixation and time-to-fixation (corroborating some of Eliezer's old claims). These were good exercises, but not obviously worth the time to write up.
I was also working with Holly Elmore on potential insights from some more specific mechanisms in natural selection regarding intragenomic conflict. I learned a lot (in particular about how 'computer sciencey' a lot of biological machinery is!) but didn't make any generalisable insights. I do expect there might be something in this area though.
The connections here were part of a broader goal of mine to understand 'deliberation' and 'control'. I've had a hard time making real progress on this since (in part due to time spent on other things), but I do feel my understanding of these has sharpened usefully. Spending some time closely pondering the connection between different optimisation procedures definitely provided some insights there.
I recently came across the 'complex systems' kind of view on adaptation and control and wonder if I might be converging in that direction.
The biggest puzzle-piece I want to see cracked regards the temporal extent of predictors/deliberators. Greater competence seems tightly linked to the ability to do 'more lookahead'. I think this is one of the keys which gives rise to 'deliberate exploration'/'experimentation', which is one of my top candidate intelligence explosion feedback loops[6]. My incomplete discussion of deliberation was heading in that direction. Some more recent gestures include some disorganised shortform discussion and my planner simulator conjecture:
something like, 'every (simplest) simulator of a planner contains (something homomorphic to) a planner'.
The proofs demonstrate that all three models of natural selection perform a noisy realisation of a gradient step (in the limit of small mutations).
As I called out in the post, I didn't pay much attention to step size, nor to the particular stochastic distribution of updates. To my mind, this is enough to put the three models of natural selection equivalent to something well within the class of 'stochastic gradient methods'[7]. 'SGD' is often used to refer to this broader class of methods, but it might be a bit misleading to use the term 'SGD' without qualification, which after all is often used to refer to a more specific stochastic gradient implementation.
nostalgebraist calls me out on this
the noise in your model isn't distributed like SGD noise, and unlike SGD the the step size depends on the gradient norm.
which is the most attentive criticism I've had of this post.
Aren't we stretching things quite far if we're including momentum methods and related, with history/memory-sensitive updates? Note that natural selection can implement a kind of momentum too (e.g. via within-lifetime behavioural stuff like migration, offspring preference, and sexual selection)! Neither my models nor the 'SGD' they're equivalent to exhibit this.
nostalgebraist's dissatisfaction notwithstanding; these are good criticisms but appear miss a lot of the caveats already present in the original post. ↩︎
I never thought this conclusion needed shoring up in the first place, and in the cases where it's not accepted, it's not clear to me whether mathing it out like this is really going to help. ↩︎
In cases where the relative fitness of a trait corresponds with its prevalence, there can be a dynamic equilibrium at neither of these modes. Consider evolutionary stable strategies. But the vast majority of mutations ever have hit the 'extinct' attractor, and a lot of extant material is of the form 'ancestor of a large proportion of living organisms'. ↩︎
Though note we do see (briefly?) sustained upward fitness in times of abundance, as notably in human population and in adaptive radiation in response to new resources, habitats, and niches becoming available. ↩︎
Now, if the earlier instances of now-extinct lineages were somehow evolutionarily 'frozen' and periodically revived back into existence, we really would see that natural selection pushes for increased fitness. But because those lineages aren't (by definition) around any more, the fitness landscape's changes over time are under no obligation to be transitive, so in fact a faceoff between a chicken and a velociraptor might tell a different story. ↩︎
I think exploration heuristics are found throughout nature, some 'intrinsic curiosity' reward shaping gets further (e.g. human and animal play), but 'deliberate exploration' (planning to arrange complicated scenarios with high anticipated information value) really sets humans (and perhaps a few other animals) apart. Then with cultural accumulation and especially the scientific revolution, we've collectively got really good at this deliberate exploration, and exploded even faster. ↩︎
e.g. vanilla SGD, momentum, RMSProp, Adagrad, Adam, ... ↩︎
Analogies are often drawn between natural selection and gradient descent (and other training procedures for parametric algorithms). It is important to understand to what extent these are useful and applicable analogies.
Here, under some modest (but ultimately approximating) simplifying assumptions, natural selection is found to be mathematically equivalent to an implementation of stochastic gradient descent.
The simplifying assumptions are presented first, followed by a proof of equivalence. Finally, a first attempt is made to consider the effect of relaxing each of these assumptions and what departure it causes from the equivalence, and an alternative set of assumptions which retrieves a similar equivalence is presented.
Summary of simplifying assumptions
It is essential to understand that the equivalence rests on some simplifying assumptions, none of which is wholly true in real natural selection.
(NB assumptions 5 and 6 will be addressed in detail and amended later)
Proof
Setup and assumptions
Let us make some substantial modelling simplifications, while retaining the spirit of natural selection, to yield an 'annealing style' selection process.
We have continuous genome
Mutations are distributed according to probability density
We also consider the case of mutations very small relative to the genome, tending to infinitesimal.
Selection is stochastic, but monotonically determined by the fitness differential, according to selection function
The population alternates between a single parent and its two offspring, one of which is selected to become the next generation's parent.
Theorem
Now consider a binary fission from
Define the next 'step',
So the distribution over
Call the mutation
by considering the directional derivative of
Now characterising
At this point it is clear that our step procedure depends, stochastically, on how closely the direction of the mutations match the fitness function's gradient.
By inspecting the expected value of the step direction,
and finally, by noticing the integral of an odd function [3] in
Thus the update between steps,
By similar inspection of
So natural selection in this form really is nothing but an implementation of unbiased stochastic gradient descent!
Discussion of simplifying assumptions
To what extent are the simplifying assumptions realistic? What happens to the equivalence when we relax any of the assumptions?
Fixed 'fitness function'
In real natural selection, the interaction between a changing environment and a dynamic distribution of organisms collaborating and competing leads to a time- and location-dependent fitness function.
Variable fitness functions can lead to interesting situations like evolutionarily stable equilibria with mixtures of genotypes, or time- or space-cyclic fitness functions, or (locally) divergent fitness functions, among other phenomena.
Such a nonstationary fitness function is comparable to the use of techniques like self-play in RL, especially in conjunction with Population-Based Training, but is less comparable to vanilla SGD.
As such it may be appropriate to think of real natural selection as performing something locally equivalent to SGD but globally more like self-play PBT.
Continuous fixed-dimensional genome and radially-symmetric mutation probability density
Moving from a continuous to a discrete genome means that the notion of a gradient is no longer defined in the same way, but we can still talk about empirical approximate gradients and differences.
The mechanisms which introduce mutations in real natural selection are certainly symmetrical in certain ways, but probably not in any way which straightforwardly maps to radial symmetry in a fixed-dimensional vector space.
Without radial symmetry, much of the mathematics goes through similarly, but instead of an unbiased estimate of the gradient direction, it is biased by the mutation sampling. As such, we might think of real natural selection as performing a biased stochastic gradient descent.
A comparison may be made to regularisation techniques (depending on whether they are construed as part of the training procedure or part of the objective function), or to the many techniques exploiting bias-variance tradeoffs in sampling-based gradient-estimation for RL, though these tend to be deliberately chosen with variance-reduction in mind, while natural selection may not exhibit such preferences.
Limit case to infinitesimal mutation
In reality, mutations are not infinitesimal, but in practice very small relative to the genome. If we do not take the limit, instead of an exact directional derivative, we find an empirical-approximate directional derivative, yielding empirical-approximate stochastic gradient descent.
This means that in real natural selection, the implied 'step size' or 'learning rate' is coupled with the particulars of the selection strength, the variance of the stochastic gradient, and the degree of empirical approximation applied. In contrast, stochastic gradient descent per se need not couple these factors together.
A degenerate population of 1 or 2
If we expand the population to arbitrary size, it is possible to retrieve the equivalence with additional assumptions.
Instead of a parent individual and cloned and mutated offspring individuals, considering parent and offspring populations, the same reasoning and proof is immediately applicable if we assume that mutations arise sufficiently rarely to be either fixed or lost before the next mutation arises. In this case
Of course this is not true for real natural selection.
If instead we allow for multiple contemporary mutant populations, an identical treatment can not be applied.
No recombination or horizontal transfer
One of the most fascinating and mathematically complicating aspects of real natural selection is multiple heredity of genome elements, whether via horizontal transfer or sexual recombination.
The preceding proof of equivalence for natural selection and stochastic gradient descent rests on a model which does not include any notion of multiple heredity.
Recovering the equivalence allowing arbitrary population size and recombination
Interestingly, the 'complicating' factor of multiple heredity provides a way to retrieve the equivalence in the presence of multiple contemporary mutations, as long as we continue to consider the limit of infinitesimal mutations.
For a single-heredity population, with multiple contemporary mutant subpopulations, we must either model 'only one winner', or model an ongoing mixture of subpopulations of varying sizes, either of which
On the other hand, in a multiple-heredity population, assuming eventually-universal mixing, and crucially continuing to assume a fixed fitness function (independent of the population mixture), a particular mutation must either fix or go extinct [4] .
Proof sketch
So let us consider (instead of
In the time between
Assuming fixed fitness, and infinitesimal mutations, we can represent the probability of fixation by time
This relies on all in-flight mutations not affecting the fitness differential, and thus
Summary of additional assumptions
In particular, this means no speciation.
NB we also rely on 4. the limit to infinitesimal mutations, in an additional capacity. We also exclude all 'self-play-like' interactions arising from the larger population by relying further on 1. fixed 'fitness function'.
It may be feasible to retrieve a similar equivalence without excluding population-dependent fitness interactions with a different framing, for example considering gradients over 'mixed strategies' implied by population distributions.
Conclusion
Natural selection, under certain conditions, carries out an implementation of stochastic gradient descent. As such, analogies drawn from one to the other are not baseless; we should, however, examine the necessary assumptions and be mindful of the impact of departures from those assumptions.
In particular, two sets of assumptions are presented here which together are sufficient to retrieve an equivalence:
or, keeping assumptions 1 to 4 and relaxing assumptions 5 and 6
This is not enough to cover all instances of real natural selection, but provides an approximate mapping from many instances.
Assumptions 2 and 3 together yield 'unbiased' SGD, and in their absence varying degrees of bias arise.
Assumption 1 rules out, most importantly, 'self play' and 'population-based' aspects of natural selection, which have other analogies in machine learning but which are firmly absent from vanilla SGD.
Further work could uncover other parameters of the emergent SGD, such as the variance of the implied gradient, the size of the implicit learning rate, the bias caused by relaxing assumption 3, or quantify the coupling between those factors.
Further scrutiny, especially of the assumptions related to population, 1, 5, 6, and 7, could better quantify the effect of making weaker or different assumptions.
Many thanks to Peter Barnett, my alpha interlocutor for the first version of the proof presented, and draft reader.
This can be justified in a few ways
- If fitness is something like an Elo rating then a Boltzmann distribution is implied
- If we want to extend the two-individual case to the n-individual case but remain invariant to the arbitrary choice of 'baseline' fitness score, then a normalised ratio of exponentials is implied
- We may further appeal to the maximum entropy property of Boltzmann distributions as a natural choice
↩︎The directional derivative in question is, for
Cautious readers may note that the integral as presented is not posed in the right coordinate system for its integrand.
By a coordinate transformation from Euclidean to hyperspherical coordinates, centred on
where we use the fact that the hyperspherical Jacobian
If we do not have a fixed fitness function, and in particular, if it is allowed to vary dependent on the distribution of the population, there are many evolutionarily stable equilibria which can arise where some trait is stably never fixed nor extinguished, but rather persists indefinitely in some proportion of the population. (A classic example is sex ratios.) ↩︎
We can be more precise if we have
Here we impose on
The various 'in-flight' and intervening mutations in the proof also therefore implicitly carry with them
In practice we should expect