The Learning Power of Evolution

Vitaly Feldman, Leslie G. ValiantCOLT 2008 · OpenReview

Introduction

Biological evolution has produced systems of staggering complexity, from the intricate machinery of the cell to the cognitive capabilities of the human brain. To the casual observer, the efficiency with which evolution navigates the vast space of biological possibilities can seem almost magical. However, the field of theoretical computer science offers a more grounded perspective. This paper explores a rigorous mathematical framework that frames evolution not as a mystical optimization process, but as a constrained form of computational machine learning. By defining "evolvability" through the lens of Probably Approximately Correct (PAC) learnability, we can analyze evolution as an algorithm that learns complex functions over a polynomial number of generations.

The Problem of Efficiency

A central challenge in evolutionary biology is explaining how complex traits emerge within realistic timeframes. Consider human biology, which relies on a network of approximately 20,000 proteins. The expression of each protein is governed by a regulatory function of the others. If the class of these functions is too restrictive, it cannot support the complexity of life; if it is too broad, no evolutionary process could reliably find a viable configuration before the heat death of the universe.

The authors address this by asking a concrete question: How can we mathematically prove that evolution can efficiently find complex biological functions? The goal is to distinguish between efficient evolution—occurring in polynomial time relative to the complexity of the environment—and evolution that is only possible in an exponentially distant limit.

The Evolutionary Algorithm Framework

To model this process, the authors introduce a theoretical framework inspired by computational learning theory. An Evolutionary Algorithm is defined by the tuple $(R, \text{Neigh}, \mu, t)$, operating under strict biological constraints:

  • Representations ($R$): The genetic encoding, such as DNA sequences or protein-protein interaction networks.
  • Experiences ($X$): The environmental states or inputs the organism encounters.
  • Ideal Function ($f$): The target biological response that maximizes fitness in a given environment.
  • Neighborhood ($\text{Neigh}$) & Mutation ($\mu$): The set of reachable genetic variants and the probability of transitioning to them.
  • Tolerance ($t$): The minimum fitness advantage required for a mutation to be "seen" by natural selection and fixed in the population.

In this model, evolution proceeds by sampling the performance of mutations. If a mutation provides a performance boost exceeding the tolerance $t$, the population shifts toward it. If no such mutation exists, the model allows for neutral genetic drift. Crucially, the population size and the number of mutations explored are bounded by polynomials, reflecting the finite nature of biological systems.

Evolution as Statistical Query Learning

The most significant insight of this framework is the mathematical equivalence between evolvability and a specific type of machine learning known as Statistical Query (SQ) learning. Specifically, evolution functions as a form of correlational statistical query (CSQ) learning.

In SQ learning, an algorithm does not examine individual data points but instead makes queries about the statistical properties of the data distribution. Evolution "queries" its environment by testing how well a specific genetic mutation correlates with the ideal survival function $f$. This mapping demonstrates that evolution requires no "extra power" beyond what is available to standard learning algorithms; it is simply a highly constrained, decentralized learning process.

Theoretical Results and Limits

The framework allows for the formal classification of what can and cannot be evolved:

  1. Convergence: A class of functions is deemed "evolvable" if the algorithm converges to a representation that closely approximates the target function $f$ within a polynomial number of generations $g(n, 1/\epsilon)$, using a polynomial sample of environmental experiences.
  2. Evolvable Classes: The authors prove that certain logical structures, such as monotone conjunctions (AND rules without negations), are efficiently evolvable under uniform environmental distributions.
  3. Hard Limits: The framework proves that evolvable functions are a strict subset of SQ-learnable functions. For example, "decision lists" cannot be evolved independently of the environment's distribution. This suggests there are fundamental mathematical boundaries to what biological evolution can achieve, regardless of time.

Discussion and Future Directions

This computational approach to evolution opens several avenues for future research. One major open question is distribution-independent evolvability: identifying functions that can be evolved regardless of the specific environmental distribution. Additionally, the concept of evolutionary boosting—combining multiple "weak" evolutionary adaptations into a single "strong" trait—remains a challenge, as biological systems lack the centralized memory typically required for boosting algorithms.

Ultimately, this framework suggests that by studying the strict mechanisms of biological evolution, we may discover new, highly robust machine learning algorithms. By stripping away the "magic" of evolution, we gain a powerful tool for understanding both the history of life and the future of artificial intelligence.

Summary updated

BibTeX
@inproceedings{feldman2008learning,
  author = {Vitaly Feldman and Leslie G. Valiant},
  title = {{The Learning Power of Evolution}},
  booktitle = {Conference on Learning Theory},
  year = {2008},
  url = {https://openreview.net/forum?id=MWcSjP5_72},
}

Loading related content...

Figure