Abstract
In order to analyze and extract different structural properties of distributions, one can introduce different coordinate systems over the manifold of distributions. In Evolutionary Computation, the Walsh bases and the Building Block Bases are often used to describe populations, which simplifies the analysis of evolutionary operators applying on populations. Quite independent from these approaches, information geometry has been developed as a geometric way to analyze different order dependencies between random variables (e.g., neural activations or genes). In these notes I briefly review the essentials of various coordinate bases and of information geometry. The goal is to give an overview and make the approaches comparable. Besides introducing meaningful coordinate bases, information geometry also offers an explicit way to distinguish different order interactions and it offers a geometric view on the manifold and thereby also on operators that apply on the manifold. For instance, uniform crossover can be interpreted as an orthogonal projection of a population along an m-geodesic, monotonously reducing the theta-coordinates that describe interactions between genes.
Introduction
In Evolutionary Computation (EC), concepts like "building blocks" or "gene interactions" are central to understanding how search algorithms navigate the fitness landscape. However, these concepts are often treated heuristically. Researchers frequently employ tools like Walsh transforms to analyze population dynamics, yet these tools have historically remained disconnected from the broader mathematical framework of information theory and differential geometry.
This work bridges that gap by treating the space of all possible populations as a curved manifold of probability distributions. By applying the rigorous language of Information Geometry, specifically the dualistic geometry developed by Shun-ichi Amari, we can describe mutation, crossover, and selection not just as algorithmic steps, but as geometric movements—such as projections and rotations—within a well-defined space.
Coordinate Systems and Bases
A fundamental contribution of this analysis is the comparison of several bases used to represent distributions. By representing a distribution as a vector in a specific coordinate system, we can isolate different types of structural dependencies within a population.
- Walsh Basis: A traditional tool in EC, analogous to a Fourier transform for binary strings, used to decompose fitness functions and populations into frequency-like components.
- $\eta$-basis (Building Block Basis): This basis captures marginal probabilities (e.g., the frequency of a specific gene). A key insight of this paper is that the "Building Block Basis" (BBB) used in EC is mathematically identical to Amari’s $\eta$-basis.
- $\theta$-basis: This basis captures $k$-th order mutual dependencies. It describes how genes interact specifically, beyond what is predicted by their individual frequencies.
Geometric Interpretation of Evolutionary Operators
Information geometry defines "straight lines" on the manifold of distributions known as geodesics. There are two primary types: m-geodesics (linear mixtures of probabilities) and e-geodesics (linear mixtures of log-probabilities). Using these, we can interpret evolutionary operators as geometric transformations.
Crossover as a Projection
Uniform crossover can be interpreted as an orthogonal projection. Specifically, it moves a population along an $m$-geodesic toward a state with fewer dependencies. It effectively "flattens" higher-order interactions by setting the corresponding $\theta$-coordinates to zero while keeping marginals ($\eta$) fixed. This provides a rigorous proof that ordinary crossover generally reduces mutual information, destroying the structural content built up by selection.
Information Decomposition
Using the information-geometric version of the Pythagoras Theorem, where the Kullback-Leibler (KL) divergence acts as the squared distance, the total mutual information in a population can be perfectly decomposed into a sum of $k$-th order interactions. This allows for a definitive structural analysis: one can distinguish between a true 3rd-order interaction and a simple chain of 2nd-order interactions (like a Markov process).
Conclusion and Future Work
By mapping Walsh coefficients to information-theoretic quantities, this framework provides a bridge for researchers to move between EC theory and Information Theory. While these notes provide a powerful descriptive tool for understanding what happens during evolution, the next challenge is prescriptive: using these geometric insights to design new, superior search algorithms. Future work will focus on using these coordinate systems to analyze the complex, non-linear dynamics of evolution as it unfolds over time.
Summary updated