Icons of ID: No Free Lunch Theorems

By PvM

In this installment of Icons of ID I will explore the evolution of the reliance of Dembski’s ID arguments on the No Free Lunch Theorems. While originally Dembski was suggesting that the “No Free Lunch Theorems” play a major role in his arguments against Darwinian pathways, he seems to have changed his tune when it was pointed out that his application of these theorems was flawed or as Wolpert, who is one of the original authors of the these theorems mentioned “written in jello” and “fatally informal and imprecise”.

1999

Dembski referred to the results being essentially a corollary of the No Free Lunch Theorems

It follows that the vast majority of fitness functions on the phase space that coincide with our original fitness function on the target but reshuffle the function on the partition elements outside the target will not land the evolutionary algorithm in the target (this result is essentially a corollary of the No Free Lunch theorems by Wolpert and Macready). Simply put, the vast majority of fitness functions will not guide E into the target even if they coincide with our original fitness function on the target (see Appendix 8).

This result refutes the claim that evolutionary algorithms can generate specified complexity, for it means that they can yield specified complexity only if such algorithms along with their fitness functions are carefully adapted to the complex specified targets they are meant to attain. In other words, all the specified complexity we get out of an evolutionary algorithm has first to be put into the construction of the evolutionary algorithm and into the fitness function that guides the algorithm. Evolutionary algorithms therefore do not generate or create specified complexity, but merely harness already existing specified complexity. Like a bump under a rug, the specified complexity problem has been shifted around, but it has not been eliminated.

Why Evolutionary Algorithms Cannot Generate Specified Complexity, Nov 1999

Let’s look at the definition of corollary

An immediate consequence of a result already proved. Corollaries usually state more complicated theorems in a language simpler to use and apply

  • A proposition that follows with little or no proof required from one already proven.
  • A deduction or an inference.
  • A natural consequence or effect; a result.

2001

Let’s look at the introduction of Dembski’s book “No Free Lunch”. Dembski not only introduced the book but also the origin of the title of the book as well as the relevance of these theorems to his arguments.

The title of this book, No Free Lunch, refers to a collection of mathematical theorems proved in the past five years about evolutionary algorithms. The upshot of these theorems is that evolutionary algorithms, far from being universal problem solvers, are in fact quite limited problem solvers that depend crucially on additional information not inherent in the algorithms before they are able to solve any interesting problems. This additional information needs to be carefully specified and fine-tuned, and such specification and fine-tuning is always thoroughly teleological. Consequently, evolutionary algorithms are incapable of providing a computational justification for the Darwinian mechanism of natural selection and random variation as the primary creative force in biology. The subtitle, Why Specified Complexity Cannot Be Purchased without Intelligence, refers to that form of information, known as specified complexity or complex specified information, that is increasingly coming to be regarded as a reliable empirical marker of purpose, intelligence, and design.

and

The Design Inference laid the groundwork. This book demonstrates the inadequacy of the Darwinian mechanism to generate specified complexity. Darwinists themselves have made possible such a refutation. By assimilating the Darwinian mechanism to evolutionary algorithms, they have invited a mathematical assessment of the power of the Darwinian mechanism to generate life’s diversity. Such an assessment, begun with the No Free Lunch theorems of David Wolpert and William Macready (see section 4.6), will in this book be taken to its logical conclusion. The conclusion is that Darwinian mechanisms of any kind, whether in nature or in silico, are in principle incapable of generating specified complexity. Coupled with the growing evidence in cosmology and biology that nature is chock-full of specified complexity (cf. the fine-tuning of cosmological constants and the irreducible complexity of biochemical systems), this conclusion implies that naturalistic explanations are incomplete and that design constitutes a legitimate and fundamental mode of scientific explanation.

Both from Introduction to No Free Lunch 10-01-2001

Since then various authors have pointed out the flaws in Dembski’s arguments and his reliance on the “No Free Lunch Theorems”, starting with Wesley Elsberry, Richard Wein, Mark Perakh and culminating with Wolpert, one of the original authors of these theorems.

Wesley Elsberry wrote on June 2001 on Talk.Origins

It’s my opinion that Dembski misconstrues or misunderstands what the NFL theorems say. I’ve passed word along that Dembski’s choice of “No Free Lunch” for the title of a book that is due out this fall sets him up for embarrassment. That’s still the title, so far as I know. It will be interesting to see how the reviews turn out.

2002

Now compare this with Dembski’s reversal

Given my title, it’s not surprising that critics see my book No Free Lunch as depending crucially on the No Free Lunch theorems of Wolpert and Macready. But in fact, my key point concerns displacement, and the NFL theorems merely exemplify one instance (not the general case). The basic idea behind displacement is this: Suppose you need to search a space of possibilities. The space is so large and the possibilities individually so improbable that an exhaustive search is not feasible and a random search is highly unlikely to conclude the search successfully. As a consequence, you need some constraints on the search – some information to help guide the search to a solution (think of an Easter egg hunt where you either have to go it cold or where someone guides you by saying “warm” and “warmer”). All such information that assists your search, however, resides in a search space of its own – an informational space. So the search of the original space gets displaced to a search of an informational space in which the crucial information that constrains the search of the original space resides. I then argue that this higher-order informational space (“higher” with respect to the original search space) is always at least as big and hard to search as the original space

Evolution’s Logic of Credulity: An Unfettered Response to Allen Orr by William Dembski

Or let’s look at the book description on ARN

But by employing powerful recent results from the No Free Lunch Theory, Dembski addresses and decisively refutes such claims.

No Free Lunch announcement on ARN

Or Koons’s review of “No Free Lunch”

Chapter 4, on evolutionary algorithms, is in some ways the crux of the book. It is here that Dembski discusses the No Free Lunch theorems that give the book its title. Dembski demonstrates that so-called “evolutionary” (or trial-and-error) algorithms cannot generate CSI. Instead the problem of generating CSI is simply pushed back from a high CSI result to a very high CSI fitness function. A fitness function is a function that differentially “rewards” or “selects” different trials, whether these trials be algorithms, behavior patterns, neural-net configurations, or biological genotypes. To solve a problem using an evolutionary algorithm, the designer must find a fitness function that can enable the sort of evolution likely to lead to an acceptable solution to the problem. Where there is a large amount of CSI required to solve a problem directly, the NFL theorems entail that an equally large quantity of CSI is required to find a suitable fitness function. I hope that committed Darwinists will accept this brilliant and illuminating analysis. Even if you are convinced that Dembski is completely wrong about Darwinism, he has made an indispensable contribution to the development of the information-theoretic analysis of evolution. I hope that relatively few commit the genetic fallacy of rejecting Dembski’s work on the grounds that he holds “scientifically incorrect” opinions on other maters.

Koons reviews NFL

Or from the Conservative BookClub, we find What are the “No Free Lunch” theorems, and how do they undercut Darwinian theory and support Intelligent Design?

Dembski’s THE DESIGN REVOLUTION: ANSWERING THE TOUGHEST QUESTIONS ABOUT INTELLIGENT DESIGN mentions

  1. Displacement and the No Free Lunch Principle How do the No Free Lunch theorems undercut Darwinian theory and support intelligent design?

On ISCID Iain Strachan

Many critics of Dembski’s use of the “No Free Lunch” theorems take issue with it by pointing out that these theorems are based on averaging over all possible fitness landscapes, the vast majority of which are completely irrelevant, and represent problems that are not interesting to solve, because the fitness landscape looks like a random array of spikes.

I would have to say that I also share this worry. I was aware of the No Free Lunch theorems long before I was aware that Dembski had written a book with the same name and I initially wondered if this might provide a theoretical underpinning to the idea that design cannot be achieved without intelligent input. But then precisely the same objection occurred to me (that the generality of the result severely limited its relevance to practical problem solving), and I felt that one should be cautious in citing the NFL theorems to justify the design hypothesis.

It may be that I have misunderstood Dembski’s argument, and I would certainly like to see him respond to this criticism.

Dembski did not respond on this thread. Nor on this thread where Iain raised the same issue.

Relevant Links:

Information Theory, Evolutionary Computation, and Dembski’s Complex Specified Information by Wesley Elsberry and Jeffrey Shallit

Dembski mistakenly invokes the “No Free Lunch” theorems of [95] as justification for his view that evolutionary computation cannot generate CSI. The NFL theorems compare efficiency between algorithms and characterize averaged performance over all cost functions, but Dembski’s claim is not about average performance: Dembski makes the universal claim that for all evolutionary computation, no instance of CSI can be attributed to any such computation. Dembski’s initial summary of the NFL theorems characterize them as establishing a problem of “regress” to a “higher-order phase space.” This does not appear to reflect what is actually discussed in the papers Dembski cites on NFL. (Search for “regress” in the text of “No Free Lunch theorems for search”, “No Free Lunch theorems for optimization”, and “On the futility of blind search” comes up empty.) The point made by Wolpert and Macready is not that a search of the space of fitness functions must be conducted, but rather that one must examine the fitness function of interest in order to select an algorithm which will perform more efficiently given that fitness function. This is a far cry from Dembski’s assertion of some “regress” in finding the source of information seen in the output of an algorithm.

Wesley Elsberry collected a number of good essays

THE NO FREE LUNCH THEOREMS AND THEIR APPLICATIONS TO EVOLUTIONARY ALGORITHMS By Mark Perakh

Orr on Boston Review: Book Review: No Free Lunch

Dembski responds to Orr Sheer versus Real Possibilities

The No Free Lunch Theorems and Their Application to Evolutionary Algorithms By Mark Perakh

While essentially Orr’s critical remarks are well taken, their formulation was insufficiently careful from a mathematician’s viewpoint so it may create a distorted impression of what Orr had in mind. Indeed, in a private communication Orr, who is a biologist, provided an explanation of his actual views on the subject of the NFL theorems’ application to Darwinian evolution, and these views are essentially in accord with a proper interpretation of the NFL theorems. Since, however, the rendition of that problem in Orr’s review of Dembski’s book may be confusing for unprepared readers, I will try to clarify the problem by first explaining in way as simple as possible the NFL theorems, and second, briefly discussing their misapplication by Dembski.

The Table of Contents and Preface to William Dembski’s upcoming book, “No Free Lunch.”

Yin-Yang: No-Free-Lunch Theorems for Search at the 1995 International Conference on Genetic Algorithms (ICGA-95)

William Dembski’s treatment of the No Free Lunch theorems is written in jello By David Wolpert

Recent Results on No-Free-Lunch Theorems for Optimization by Christian Igel, Marc Toussaint

On Classes of Functions for which No Free Lunch Results Hold by Christian Igel, Marc Toussaint

In a recent paper it was shown that No Free Lunch results hold for any subset F of the set of all possible functions from a finite set X to a finite set Y iff F is closed under permutation of X. In this article, we prove that the number of those subsets can be neglected compared to the overall number of possible subsets. Further, we present some arguments why problem classes relevant in practice are not likely to be closed under permutation.

No Free Lunch Theorems for Search (1995) by David H. Wolpert, William G. Macready

No Free Lunch Theorems for Optimization (1996) by David H. Wolpert, William G. Macready

No Free Lunch Theorems: Many good links by Martin Sewell

Critiques and reviews of the works of William Dembski at infidels.org

NO FREE LUNCH: Why Specified Complexity Cannot Be Purchased without Intelligence From the Book – WATCH FOR IT!