An Application of the No Free Lunch Theorem

[gumpzilla]

[ QUOTE ]

Another way of saying it, is that for every possible search algorithm you can construct a terrain that is -EV. Therefore you can't design an algorithm better than any other.

[/ QUOTE ]

I'd never heard of this theorem before. It would be interesting to learn more about it.

That said, averaging over all possible cost functions can give you one measure of an algorithm's performance. But looking at how it performs against a realistic subset of cost functions, there can definitely be better or worse algorithms. "Always move downhill when possible" is going to be a very poor choice of algorithm for finding maxima.

And it seems to me that trying to use this theorem to discuss evolution, as Dembski is doing, is pretty laughable. For one thing, the whole context as I understand it - looking at survival as an optimization problem - already seems to spit out natural selection as a result, unless he's optimizing some particularly strange variable other than survivability. And trying to talk about how random mutation and natural selection aren't "better" than some other possible scheme misses the point as well, I think. The issue isn't whether random mutation and natural selection is the most efficient way to produce evolution, just whether it does at all. EDIT: Also, what exempts "intelligent change" from the NFL theorem, if you buy his line of reasoning?

[LuckOfTheDraw]

[ QUOTE ]
[ QUOTE ]

Another way of saying it, is that for every possible search algorithm you can construct a terrain that is -EV. Therefore you can't design an algorithm better than any other.

[/ QUOTE ]

I'd never heard of this theorem before. It would be interesting to learn more about it.

That said, averaging over all possible cost functions can give you one measure of an algorithm's performance. But looking at how it performs against a realistic subset of cost functions, there can definitely be better or worse algorithms. "Always move downhill when possible" is going to be a very poor choice of algorithm for finding maxima.

And it seems to me that trying to use this theorem to discuss evolution, as Dembski is doing, is pretty laughable. For one thing, the whole context as I understand it - looking at survival as an optimization problem - already seems to spit out natural selection as a result, unless he's optimizing some particularly strange variable other than survivability. And trying to talk about how random mutation and natural selection aren't "better" than some other possible scheme misses the point as well, I think. The issue isn't whether random mutation and natural selection is the most efficient way to produce evolution, just whether it does at all. EDIT: Also, what exempts "intelligent change" from the NFL theorem, if you buy his line of reasoning?

[/ QUOTE ]

ID is a joke. The article did a good enough job debunking Behe and Dembski's claims. And, I agree that Dembski's application of the NFL theorem to ID just doesn't work for the reason you stated. I was, however, a little intrigued by the NLF theorum itself (I had never heard of it either), and I was a little perplexed by the example given.

[Utah]

Hi LuckOfTheDraw. Thanks for starting the thread as it is very interesting.

In your two examples it is very easy to construct lanscapes where the random algorthim beats the pants off the "go up...side step up" algorithm. For example, you could be in a "flat bottom bowl" landspace and the amount of ground that could be covered in the "up..step" algorithm would never get you out of the flat bottm of the bowl. The random algorithm would FAR outperform the "up step" algorithm because at worst it will land on the flat bottom but occassionally it will land on the slope of the bowl.

Also, you need to make sure that you are not introducing prior knowledge of landscapes because if you do the NFLT theorem no longer applies. For example, you cannot assume that "flat bottom bowls" do not exist.

Now, I think someone brought up the point of not moving. Clearly, this is incorrect as this strategy is dominated for ALL landscapes by simple strategies such as "feel one step in each direction and take the highest point".

[madnak]

Which goes to show that the problem should be better-defined before bringing NFL into play. Clearly, even averaged across all terrain, some strategies are categorically superior to other within certain contextual frameworks.

Things that have to be defined include movement capability, observation capability, and the parameters of terrain generation. If the parameters are infinite, then I guess everything is equal, but that's just a case of getting "lost in infinity."

[toor]

You can just imagine the 2D case. The problem they state is equivalent to finding a global maximum on a function; f(x). Even assuming continuity of the function. It should be pretty easy to imagine that most of the time functions will wildly oscillate and thus you any given hill could be a local max but you would never know whether it was the global.