An Application of the No Free Lunch Theorem
 

Ok, so we have the No Free Lunch Theorem (NFLT). I can sort of understand this intuitively. However, while reading an article the other day in The New Yorker, I saw the following example:

"Consider a search for high ground on some unfamiliar, hilly terrain. You’re on foot and it’s a moonless night; you’ve got two hours to reach the highest place you can. How to proceed? One sensible search algorithm might say, “Walk uphill in the steepest possible direction; if no direction uphill is available, take a couple of steps to the left and try again.” This algorithm insures that you’re generally moving upward. Another search algorithm—a so-called blind search algorithm—might say, “Walk in a random direction.” This would sometimes take you uphill but sometimes down. Roughly, the N.F.L. theorems prove the surprising fact that, averaged over all possible terrains, no search algorithm is better than any other. In some landscapes, moving uphill gets you to higher ground in the allotted time, while in other landscapes moving randomly does, but on average neither outperforms the other."

This does not come across as intuitive for me. To me, it seems that if you choose a step up instead of a step down, on average, you would find higher ground. Though, it seems to be a pretty straightforward application of the NFLT. Any thoughts?

Re: An Application of the No Free Lunch Theorem
 

Well, if they tailored the terrain directly to the situation, and if the search algorithm could eventually reach the destination ("never ever go uphill" wouldn't work, obviously), then I guess it could work. For instance, if the algorithm is "go downhill and then continue in a straight line if you reach the bottom point" then that might be the ideal solution if you're on a small hill circled by a ditch circled by a rise that represents the highest point.

Re: An Application of the No Free Lunch Theorem
 

But I agree that "averaged over all possible terrains" doesn't really make sense at all. I think there's something fishy going on. How did they come up with their enumeration of terrain types? How did they evaluate each strategy for each terrain type? On what basis did they consider the frequency of the terrain type (or did they at all)? And how did they perform the "averaging?"

Re: An Application of the No Free Lunch Theorem
 

Sorry to post again here, but "over all possible problems" is very different from "over all terrain types found on Earth." If they're talking about theoretical "terrains," and the infinite set of them, that's a different story. It's still probably a good idea to head uphill if you're on Earth terrain. At any rate, it'll give you a better vantage point.

Re: An Application of the No Free Lunch Theorem
 

[ QUOTE ]
I think there's something fishy going on.

[/ QUOTE ]

Indeed there is. If you starting point happens to be the highest, you will not know, unless you have covered every other possible point on the terrain, that the best solution was not to move.

Hope this help with the fish! [img]/images/graemlins/smile.gif[/img]

Re: An Application of the No Free Lunch Theorem
 

Doesn't that just mean "stay in one place" can be the optimal search algorithm? [img]/images/graemlins/grin.gif[/img]

Re: An Application of the No Free Lunch Theorem
 

Do you have a link to the article, btw? I think some information is probably missing.

Re: An Application of the No Free Lunch Theorem
 

[ QUOTE ]
Do you have a link to the article, btw? I think some information is probably missing.

[/ QUOTE ]

I don't think there's much more there.

Re: An Application of the No Free Lunch Theorem
 

[ QUOTE ]
Doesn't that just mean "stay in one place" can be the optimal search algorithm? [img]/images/graemlins/grin.gif[/img]

[/ 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.

Re: An Application of the No Free Lunch Theorem
 

What if your algorithm is to take X steps from an initial position in every direction. Set a new initial position to the found high point. If no high point is found, increase X. Rinse and repeat.

Re: An Application of the No Free Lunch Theorem
 

[ 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?

Re: An Application of the No Free Lunch Theorem
 

[ 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.

Re: An Application of the No Free Lunch Theorem
 

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".

Re: An Application of the No Free Lunch Theorem
 

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."

Re: An Application of the No Free Lunch Theorem
 

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.