There Is a Free Lunch After All

| 14 Comments

This entry provides a link (at the bottom of the entry) to the full text of my chapter (chapter 11) in the anthology Why Intelligent Design Fails: The Scientific Critique of the New Creationism (WIDF, edited by Matt Young and Taner Edis, © Rutgers Univ. Press, 2004) posted on Talk Reason website. The publisher has granted permission to post this material online with the proviso that the posted text would not be either printed or otherwise downloaded without permission from Rutgers Univ. Press. The full title of the chapter is “There Is a Free Lunch After All: William Dembski’s Wrong Answers to Irrelevant Questions.”

The reason for posting this chapter right now becomes clear if we notice that many points discussed in that chapter have recently been revisited by several writers, in particular on the Panda’s Thumb (PT) weblog (for example, see this and this ). The points in question include

* distinction between “targeted” and “targetless” search algorithms,

* the merits and shortcomings of Dawkins’s evolutionary algorithms,

* Dembski’s misuse of the No Free Lunch theorems,

* his contrived “displacement problem,” etc.

Many points discussed in this chapter have also been briefly addressed in my article published in the Skeptic magazine (vol. 11, No 4, 2005). The text of that article is available online ( see here ). Moreover, the NFL theorems and their application to evolutionary algorithms have been briefly discussed online as well ( see this ).

It has to be pointed out that the discussion of Dembski’s “displacement problem” in this chapter as well as in the article in the Skeptic only covers the initial version of that “problem” as it was rendered by Dembski in his No Free Lunch book. More recently, Dembski had modified the “displacement problem,” and this newer rendition naturally was not yet discussed either in chapter 11 of WIDF or in the article in the Skeptic. The new version of that “problem” has been though briefly addressed here .

Read There Is a Free Lunch After All on Talk Reason .

14 Comments

The PDF says:

As Wolpert reports (2002), Wolpert and Macready (2003) have proven recently that the NFL theorems are invalid for coevolutionary algorithms,

referencing a paper listed in the bibliography as:

Wolpert, David H and William G. Macready. 2003 (to be published).

Has this second paper been published since this chapter was originally written, and what exactly was the proof?

Thanks.

To Coin: Yes, Wolpert-Macready’s paper in question was published after WIDF was published. I used to have a reference on my computer, but it melted in January when I had a fire in my home. I’ll try to find the reference, so it can be posted here. The proof, which is rigorously mathematical, is too convoluted to be explained in a comment here, it requires to see the entire paper.

Thanks.

Is Wolpert and Macready (2003) realy this paper?

Wolpert DH, Macready WG (2005) Coevolutionary free lunches. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 9(6): 721-735

Abstract: Recent work on the foundational underpinnings of black-box optimization has begun to uncover a rich mathematical structure. In particular, it is now known that an inner product between the optimization algorithm and the distribution of optimization problems likely to be encountered fixes the distribution over likely performances in running that algorithm. One ramilication of this is the “No Free Lunch” (NFL) theorems, which state that any two algorithms are equivalent when their performance is averaged across all possible problems. This highlights the need for exploiting problem-specific knowledge to achieve better than random performance. In this paper, we present a general framework covering most optimization scenarios. In addition to the optimization scenarios addressed in the NFL results, this framework covers multiarmed bandit problems and evolution of multiple coevolving players. As a particular instance of the latter, it covers “self-play” problems. In these problems, the set of players work together to produce a champion, who then engages one or more antagonists in a subsequent multiplayer game. In contrast to the traditional optimization case where the NFL results hold, we show that in self-play there are free lunches: in coevolution some algorithms have better performance than other algorithms, averaged across all possible problems. However, in the typical coevolutionary scenarios encountered in biology, where there is no champion, the NFL theorems still hold.

Bob

To follow up: I think Wolpert and Macready show that there is a free lunch, but you have to fight someone for it.

Bob

Yes, Bob, this is the paper I meant. Thanks for pointing to it. Whether or not the NFL theorems are valid for biological evolution (they are), including co-evolution (where they may be invalid in certain situations - see the referenced Wolpert/Macready’s paper) is irrelevant because the uniform average does not tell anything about the actual performance of search algorithms, as only the performance on a specific landscape is what counts, and there always are algorithms that outperform blind search on given specific landscapes, and this is true regardless of whether the landscape is co-evolving or not. Moreover, evolution is not a search for a target (contrary to what Dembski asserts), therefore his calculations of probabilities of finding a “target” are likewise irrelevant. Maybe I’ll write one more brief essay about it and post it here.

I note that last years Wolpert paper doesn’t reference Dembski. Funny that.

A bit off topic, but, Dr. Perakh: How does the work of Manfred Eigen apply to anything Dembski says? http://personal.anderson.ucla.edu/m[…]/27feb98.htm

To Ed Darrell: Eigen is a well known German scientist. I believe Dembski has mentioned him in some of his numerous publications, albeit I can’t provide a specific reference without a search. I don’t recall Eigen ever mentioning Dembski, although I can’t assert that he never did. Eigen’s views, however, have nothing to do with Dembski’s quasi-scientific exercises. Perhaps one example may suffice: Eigen wrote that information is a quantity that is not subject to conservation laws (which IMHO is correct). This statement is plainly incompatible with Dembski’s so called “law of conservation of information” which Dembski proclaimed to be the 4th law of thermodynamics, and Rob Koons claimed to be a great breakthrough in information theory (although a couple of years later the same Koons, displaying a funny lack of ken in the matters he endeavored to discuss, changed the tune and stated that Dembski did not claim to have discovered such a law - (see this). Anyway, any juxtaposition of Dembski and Eigen is immaterial because Eigen is a scientist of a high stature while Dembski is, as his former professor Jeff Shallit wrote, just a pseudo-mathematician whose torrent of publications contributed next to nothing to either math or to any field of science.

As I thought – but I’m concerned that we may be a little hasty in dismissing Eigen as having anything to say. For his work, Eigen won a Nobel Prize in Chemistry. That’s nothing to sneeze at.

Then along comes Dembski, claiming Eigen is in error, essentially, that “information” is conserved, when it isn’t. To my almost-lay perspective, it seems to me that when an ID advocate makes a claim which is counter to the work for which a great chemist won a Nobel, that ID advocate has a duty to explain why the differences exist. That such differences exist is one of the chief signs of crank science, according to physicist Jeremy Bernstein – and I just wondered if someone much better versed in the topic than I am could explain it that way.

Is there a chance we can recruit chemists to the cause? It sure would help here in Texas

Free lunch my foot - my lunch cost nearly five bucks! ;)

From triviatoday.com:

[July 9th] 1995: Electrician Terry Benson won $32-million in a British lottery by picking the serial number on a crane where he worked. The 61-year-old London resident said it was only the second time he’d ever played.

Clearly, the odds of these two numbers being identical are so extaordinary, the lottery must have been rigged. I mean designed. Yeah, that’s it. Designed.

Re ‘Clearly, the odds of these two numbers being identical are so extaordinary, the lottery must have been rigged. I mean designed. Yeah, that’s it. Designed.”

Well, the crane certainly didn’t evolve, ergo…

(Though otoh, I’ve heard that that type of crane is the state bird of several states…)

Henry

(Though otoh, I’ve heard that that type of crane is the state bird of several states…)

We have lots of them in Florida. Alas, they tend to chase out all the native species.

About this Entry

This page contains a single entry by Mark Perakh published on July 5, 2006 2:34 PM.

Target? TARGET? We don’t need no stinkin’ Target! was the previous entry in this blog.

Nature on Science Blogs is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.

Categories

Archives

Author Archives

Powered by Movable Type 4.381

Site Meter