Dembski and Marks (2009b) recently published a minimalistic (and simplistic) representation of a search problem consisting of a search space and a distinguished target set (blogger reactions: 1, 2, 3, 4, 5, 7). From the discussion in the paper and two other articles it is clear that the authors’ object of study is related to, though not equivalent to, the issues raised by Wolpert and Macready’s No Free Lunch theorems. Despite its minimalistic character, the Dembski-Marks representation is not less restrictive than the Wolpert-Macready representation of a search/optimization problem. The Dembski-Marks representation, i.e., a distinguished target in a search space, can easily be introduced as an extra feature in the Wolpert-Macready representation. However, it is not possible to introduce the full Wolpert-Macready representation within the Dembski-Marks representation. Indeed, the absence of a constant, distinguished target set is a prerequisite for all No Free Lunch theorems. It is therefore interesting to estimate how much of a restriction it is to make the Wolpert-Macready representation conform to the Dembski-Marks representation.
To this end, let denote a range of fitness values. Wolpert and Macready considered the average performance of optimization algorithms over the set of all fitness functions . Sharpened No Free Lunch theorems apply also to non-uniform probability measures over with special permutation symmetry (Igel and Toussaint). In this representation, a fitness function is identified with a problem instance; in particular, success criteria for search algorithms cannot refer to anything else than the fitness function values. A target is obtained by first letting and be the range of satisfactory and unsatisfactory fitness values, respectively. Second, it is necessary to restrict attention to only those fitness functions that map the target set into the satisfactory fitness range and the rest of the search space into the unsatisfactory fitness range. That is, the restriction is to a subset of functions with images and . It should be noted that the No Free Lunch theorem does not apply to the class of functions , because no probability measure on can have the necessary symmetry and search algorithms that visit points in before points in clearly have superior performance to other search algorithms. The conclusion of the No Free Lunch theorem, i.e., that all search algorithms have equivalent performance, is directly contradicted in this case—the theorem cannot apply.
How biased and severe the restriction from to is may be measured by the ratio
where denotes the number of elements of a finite set and at least is assumed to be finite. ( may be taken to be either finite or a continuum of finite measure, in which case denotes the Lebesgue measure where appropriate.)
Dembski and Marks use the word `information’ to mean certain probabilities and restrictions on logical possibilities arising from model assumptions. Their objections to model assumptions take the form of reified talk about information. Example:
“Simulations like Dawkins’s WEASEL, Adami’s AVIDA, Ray’s Tierra, and Schneider’s ev appear to support Darwinian evolution, but only for lack of clear accounting practices that track the information smuggled into them.” (Dembski and Marks, 2009b)
Assumptions are a necessary ingredient in any mathematical model or calculation. Dembski and Marks are as guilty of making model assumptions as anyone else. Adopting their terminology, the logarithm of the ratio may be termed information and taken to measure how strong a priori assumptions Dembski and Marks rely on in their discussions of search problems. Thus,
where is the fraction of satisfactory fitness values and is the relative size of the target. It is easily seen that, for a given , the minimum of is attained when . Furthermore, decreases with decreasing (assuming ). The smallest possible value of is . Therefore a lower bound on the amount of information smuggled by Dembski and Marks is obtained by inserting into the above equation, yielding
This lower bound is never attained in practice, at least not for large search spaces. For instance, most computer implementations make use of 64-bit floating-point numbers to represent real numbers. All numerical calculations are then carried out approximately to a relative precision of so that the case hardly ever is meaningful. A more realistic estimate in practice is therefore
or nats per search space point. The below figure shows how varies with (left) for fixed and (right) for fixed (note the logarithmic scales).
In the case of the Weasel program used by Dawkins to illustrate the difference between cumulative natural selection and random sampling, the search space consists of all 28-character sequences that can be formed from a symbol set consisting of 26 letters and a blankspace, giving . The target contains a single sequence, . The range of fitness values contains exactly different values since it is based on a Hamming distance and a single value is satisfactory so that . This gives , and nats. Thus, Dembski and Marks smuggle nats (or bits) of information into their analysis of the Weasel program. In order to reach the theoretical lower bound, which in this case is nats (or bits), the Weasel program must be modified so that fitness is evaluated on an absurdly biased scale with possible unsatisfactory fitness values for every possible satisfactory value.
The fundamental lesson here is that the Dembski-Marks approach to evaluating model assumptions is both arbitrary and a poor reflection of scientific reasoning. Model assumptions are not accepted or rejected based on a numerical measure of how many logical possibilities that are ruled out or how far probability distributions deviate from uniform measures. Rather, model assumptions are accepted or rejected based on predictive and descriptive accuracy, domain of applicability, ability to unify existing models and empirical knowledge, and so on. Merely talking about target sets requires assumptions that impose structure on the search space and processes related to it. Dembski and Marks (2009a) mention “a simple self-replicating molecule, an autocatalytic set, or a lipid membrane” as examples of biological targets. However, these chemical concepts presuppose model assumptions from physics, chemistry and biochemistry and they could hardly be independent of the chemical processes by which they are thought to arise. The same chemistry that allows us to define self-replicating molecules, autocatalytic sets and lipid membranes also has consequences for how such phenomena might arise in nature. In the language of the Dembski-Marks (or Wolpert-Macready) representation, this means that the target set (or fitness function) and the search algorithm are not independent of each other—they are both consequences of chemical model assumptions.
W. A. Dembski and R. J. Marks II. Life’s Conservation Law. (2009a) [Available at the authors' homepage.]
W. A. Dembski and R. J. Marks II. Conservation of Information in Search: Measuring the Cost of Success. IEEE Trans. Sys. Man. Cybernetics A 39:1051 (2009b) [Also available at the authors' homepage.]
W. A. Dembski and R. J. Marks II. The Search for a Search: Measuring the Information Cost of Higher Level Search. (2009c) [Available at the authors' homepage.]
C. Igel and M. Toussaint. No Free Lunch Theorem for Non-uniform Distributions of Target Functions. J. Math. Model. Algorithms 3:313 (2004) [eprint (different title): cs.NE/0303032]
D. H. Wolpert and W. G. Macready. No Free Lunch Theorems for Optimization. IEEE Trans. Evol. Comp. 1:67 (1997)
Update: Manual trackback from The Panda’s Thumb.