News

Loading...

Friday, May 16, 2008

Dembski and the NFL Theorems

OK everyone, I promise that this is the last ID post from me for a while. (If Gene posts on the topic though, I will almost certainly comment on the thread.)

Anyway, what I will quickly do here is summarize the No Free Lunch (NFL) theorems, and then William Dembski's attempt to apply them in the arena of the origin of life. Despite the official shrugging off by experts, I think Dembski has hit upon an incredibly powerful argument, and if he did nothing else worthwhile in his career (some might say this is true!) he would still be a genius.

OK so first let's go over the NFL theorems: Basically they show that no optimization algorithm can outperform another, over the entire domain of all possible problems. Now this is a shocking result, and if it doesn't shock you, you probably don't grasp what it is saying. So let me put the result in a concrete way, using an example that others (I think maybe the original authors?) have used.

Suppose the problem is to find the highest elevation on a landscape, where the surface is divided into a finite number of sectors. You have to choose a search algorithm to find that highest spot, where you start at some random location and can only see the elevation of adjacent sectors.

So the NFL says that, over all possible landscapes (and of course this is spelled out formally in the proof), there is no reason that any one search algorithm would do better than another. In particular, the algorithm that says, "Look around you, and go up the steepest incline" does no better on average than an algorithm that says, "Pick a direction at random and then head that way." Even more incredible, the first algorithm doesn't even outperform the algorithm that says, "Look around and go towards the lowest elevation available."

(I confess that this last part seems crazy to me; you would think it would be easy to show that the first algorithm weakly dominates the third, but apparently over the entire class of landscapes it doesn't. I asked an expert if he could intuitively explain this, perhaps by describing just one landscape where the third one does better, but he either never replied or admitted he couldn't put it into simple terms.)

OK so are we all set on what the NFL theorems say? The reason for their name is that of course, if you know something beforehand about the type of problem you want to solve--equivalent to knowing which subset of possible landscapes your algorithm will encounter--then it is easy to find algorithms that will outperform others. But there is "no free lunch"; you can't search a little bit to determine the type of landscape, and then pick the appropriate algorithm. (Because that would itself just be an original algorithm facing the entire domain of possible landscapes...) So you have to assume a priori knowledge of the answer before setting up the search, and hoping to have better than random chance of finding the answer.

I hope you now see where this is going. In the evolution debate, an ignorant creationist might say, "Random chance can't explain the complexity of life! Just watch a fetus developing in the womb! You call that a crap shoot??" But of course, the sophisticated answer is that Darwinian evolution doesn't rely merely on chance, it relies on random mutations which are then acted upon by natural selection.

So what Dembski tried to argue is that this is begging the question; it is trying to get a free lunch out of nature. The biologists would concede that mere trial-and-error could not, even with billions of years to operate, have possibly given rise to life as we know it. But Dembski then invokes the NFL theorems. Over the domain of all possible environments, why should we expect the algorithm of natural selection to "find" these complex arrangements of matter? Again, in general there is no reason to suppose that natural selection would do any better than random chance, unless the landscape for this "problem" (i.e. the conditions on earth over the last few billion years) happened to be in the subset of possible landscapes where natural selection outperforms random chance. And so, Dembski concludes, if you admit that it would be crazy to suppose chance alone gave rise to life, then the NFL theorems force you to admit that random chance + natural selection is also just as "lucky" for yielding life.

Now then, what has been the official response to this argument? Read Wolpert (one of the NFL authors) here, and biologist Allen Orr here (page 4). The official response is that the NFL theorems don't apply to biological evolution, because there is no fixed landscape. Rather, there are multiple creatures "optimizing" on a landscape that includes each other, so the landscape itself changes. In Orr's words:

Another problem with Dembski’s arguments concerns the N.F.L. theorems. Recent work shows that these theorems don’t hold in the case of co-evolution, when two or more species evolve in response to one another. And most evolution is surely co-evolution. Organisms do not spend most of their time adapting to rocks; they are perpetually challenged by, and adapting to, a rapidly changing suite of viruses, parasites, predators, and prey. A theorem that doesn’t apply to these situations is a theorem whose relevance to biology is unclear.

Now I think this is a crushing admission of defeat by Orr. Here's why:

(1) Is he conceding that random mutation + natural selection can't explain how a single line of organisms could adapt to a lifeless world?? That's problematic because for one thing, intuitively it is a lot easier to see how the Darwinian story would work in a fixed environment. If you admit that the theory shows it doesn't work there, then I think it's little comfort to say, "But technically the assumptions of NFL don't hold for co-evolution, so it's an open question whether mutation+natural selection work when there are other organisms at work." It's problematic for a second reason because co-evolution can only kick in after the origin of the first form of life!!

(2) I realize there must be some subtlety in the proof, but I don't see why you couldn't easily incorporate the other organisms as part of the original "fixed" landscape. The NFL theorems have a very abstract, broad specification of the class of problems. E.g. it would have been silly had Orr said, "NFL only applies to a fixed landscape, but in the real world there are volcanoes that sometimes erupt." I.e. a volcano that erupted 18,456 time units after the start of the simulation could easily be incorporated as just another dimension in the original fitness landscape; the problems in general aren't really just 3D surfaces where the object is to find the highest point. That was just an easy picture to illustrate the results. So, take any one organism's point of view, and consider all the other organisms as just part of the landscape to which it is adapting. I don't see how this changes the problem. (BTW the game theoretic co-evolution paper that Wolpert put out later really didn't look anything like evolutionary models; there are players engaging in a tournament and finding a "champion" etc. I'm pretty sure even Wolpert himself acknowledges that those later models don't have much to do with the evolution argument.)

Incidentally, I had a short email exchange with Orr back in the day. I asked him point (1) above, something like, "Doesn't it seem odd that you are apparently admitting that evolution couldn't explain creatures adapting to a fixed, inorganic world, while you are saying it is capable of explaining adaptation to an even more complicated world?" He didn't answer that email. (I'm not saying this as a shocking example of his cowardice, I'm just reporting that he never answered that question.)

OK I promise no more new blog posts on ID from me for a while... We can argue in the comments if you'd like.

UPDATE: I found Orr's stand-alone review of Dembski's No Free Lunch. This has a much stronger response to the NFL argument than the one I quoted above, though I think it is still fairly weak. Orr raises a bunch of other good objections to Dembski, though.

16 comments:

  1. Jared2:24 AM

    OK, first I'll explain the hill descent thing. This requires being more precise about the NFL theorems. You have a discrete search space and a discrete objective function on that space, and an algorithm that evaluates (or "visits") the function on points in the space without repetition, a total of n times. The result of the algorithm is the sequence of values of points it visits. For whatever performance measure you have on that result and whatever n you have, no algorithm does better than any other averaged over all possible objective function.

    Note in particular that the performance measure is not part of the algorithm, that all points evaluated by the algorithm count, and that repetition is not allowed. Obviously an algorithm that visits a fixed set of n points and returns the best result will weakly dominate an algorithm that visits the same fixed set of points and returns the worst result. Similarly, if your performance measure is the average value of visited points and repetition is allowed, an algorithm that visits 2 fixed points and then repeatedly visits the best of the 2 will weakly dominate an algorithm that repeatedly visits the worst of the same 2 points.

    Wolpert and Macready mention the hill-descending algorithm, "As an important clarification of this definition, consider a hill-descending algorithm. This is the algorithm that examines a set of neighboring points in and moves to the one having the lowest cost. The process is then iterated from the newly
    chosen point.... The point to note is that because a sample contains all the previous points at which the oracle was consulted, it includes the values of all the neighbors of the current point, and not only the lowest cost one that the algorithm moves to. This must be taken into account when counting the
    value of m."

    An intuitive example of a landscape where hill-descending does better than hill-climbing is not hard. Let's say our performance measure is the maximum point visited (this is quite normal--it's common in search optimization to remember the best point). We have a smooth landscape with hills and such, but with a number of randomly-placed spikes (very high value, but very small area). The spikes are frequent enough to be hit often, but are spread out enough relative to their size that the hill-climbing algorithm will quickly just find the local optima and move off. In other words, the hill-climbing/descending algorithms will overall follow the smooth hills and valleys. However, there is a negative correlation between the value of the spikes and the value of the surrounding landscape. Because the spikes are very high compared to the surrounding landscape, the winner will be the algorithm that hits the best spike. Because the hill-descending algorithm will move toward the best spikes and the hill-climbing algorithm will move away from them, the former will do better.

    Second, I will shoehorn (no offense) your argument into this framework. Let's say we have a big lifeless ocean in which life evolves from non-life. Let's say that during the early stages, the various evolving precursors are sufficiently infrequent that they don't really affect each other, so we can model this as follows. Our search space is small physical objects, and our objective function is: what is the average number of times this thing will approximately replicate itself over a given period of time if placed at random in this fixed, big lifeless ocean. NFL implies that if evolution does better than picking random small physical objects, it must be that the function is better for evolution than a function picked at random. We then conclude that the physical laws of the universe weren't picked at random, or something along those lines.

    There is a problem with the final sentence. Basically, this is an overly complex way, with serious potential technical flaws, of getting at deeper philosophical questions. The main way in which the objective function wasn't picked at random is that the universe has regular physical laws. To consider all possible functions as required you have to consider functions which vary in a completely chaotic and meaningless way with changes to the small physical objects. Probably the vast majority of the possible functions don't correspond to a universe with regular physical laws, especially if we're keeping the description of the function as "average number of replications" and varying the physical laws and other environmental conditions to obtain all possible functions. Whether the existence of regular physical laws is an argument for an intelligent creator is a valid philosophical question, but one that bears little relationship to biological evolution or the origin of life on Earth.

    ReplyDelete
  2. Jared,

    First of all, you're not the Jared that I sent this link to, right? If so I am extremely impressed. (Just because I didn't realize you were this quantitatively adept.)

    Second, thanks for the clarification about the hill descending stuff. It is really late so I will have to read it carefully tomorrow, but it looks like you have (or will have) cleared up my confusion.

    Third, I understand how you reached it, but I disagree with your conclusion here:

    Whether the existence of regular physical laws is an argument for an intelligent creator is a valid philosophical question, but one that bears little relationship to biological evolution or the origin of life on Earth.

    I think that that really is Dembski's main point; at the very least, it's my main point. It wouldn't bother me in any way if someone showed a movie of the entire history of the earth, and the neo-Darwinian story apparently played out perfectly. I would still maintain that the probability of everything being just right (charge on an electron, etc.) for that to unfold "naturally" was evidence of a conscious plan.

    And so no, I don't think the existence of coherent, simple, physical laws is irrelevant to the question of the origin of life, if we are agreed that they are necessary to explain it.

    I again refer people who haven't ever heard of this stuff, to this quick sampling of evidence of "fine tuning" in the laws of nature. It's not just organic chemistry (if these physicists are right).

    ReplyDelete
  3. Jared4:45 AM

    Bob,

    I'm a different Jared for sure. There's no need to apologize about it being late. I think we're not even in the same time zone.

    Anyway, my point was not so much to debate the merits of fine-tuning arguments as arguments for the existence of an intelligent creator, but rather to argue against the merits of this NFL argument as a fine-tuning argument. That is, I claim it's an extremely weak fine-tuning argument. I claim that the fact that the universe has regular physical laws at all is enough "tuning" to satisfy the NFL argument, whereas normally fine-tuning arguments claim that, as you say, the charge of the electron and other phsyical constants are just right.

    Let's compare two arguments. First,
    1. Life requires some sort of regular physical laws.
    2. Any sort of regular physical laws require an intelligent creator.
    3. We have life.
    4. Therefore, we have an intelligent creator.

    Second,
    1. Life requires very specific physical laws.
    2. Very specific physical laws require an intelligent creator.
    3. We have life.
    4. Therefore, we have an intelligent creator.

    In the first argument, you can eliminate step 1 and replace step 3 with "We have some sort of regular physical laws", because no one is actually going to dispute that.

    If you try that in the second argument, people will ask what you mean by "very specific" physical laws, so you have to keep the whole argument because the part about the laws being very specific for life is crucial.

    I claim the NFL argument is just step 1 in the first argument, and thus superfluous.

    Of course it's in some sense relevant to the origin of life that there are regular physical laws, but I think you know what I meant is that, as scientific theories proper, it's not relevant to biological evolution or the origin of life why the laws of physics are the way they are.

    Now, you probably correctly guess I also disagree about the merits of the fine-tuning argument more generally. This is in part because it's acceptable to me to say I simply don't know why we have regular laws of physics, let alone what probability distribution they were selected from in the context of a fine-tuning argument (or whether selecting them from a probability distribution even makes sense).

    ReplyDelete
  4. Because the spikes are very high compared to the surrounding landscape, the winner will be the algorithm that hits the best spike. Because the hill-descending algorithm will move toward the best spikes and the hill-climbing algorithm will move away from them, the former will do better.

    I realize it must be something like this, but I still don't see how it works. Is the landscape continuous? Because if so, how does the hill-descending algorithm ever get going up the huge spike? Wouldn't it turn around after the first step up the huge spike?

    So I'm imagining that there is some deal where there are landscapes where the big spikes are so incredibly steep that the algorithm "accidentally" goes 100 ft up, even though that is just one step on this spike, and then turns around. And then somehow there is no reason to expect the hill ascending one to do better than 100 ft.

    Is that basically right? I realize I'm hand-waving about the exact formulation but I'm just trying to understand why a hill-descending algorithm benefits from huge spikes.

    ReplyDelete
  5. Jared,

    Also, is there some trick where the domain of possible landscapes is infinite (or maybe even a continuum)? Because even though I understand how there could be one landscape where the hill-descending does better, it still seems like there ought to be "so many more" where this isn't true.

    But is that like saying there should be twice as many integers as there are odd integers?

    ReplyDelete
  6. Jared,

    I claim that the fact that the universe has regular physical laws at all is enough "tuning" to satisfy the NFL argument, whereas normally fine-tuning arguments claim that, as you say, the charge of the electron and other phsyical constants are just right.

    I understand the rhetorical force of your argument here, but I just want to point out that you conveniently chose "the existence of regular physical laws" to shatter the open-ended domain, when you could just as well have chosen any attribute of our universe.

    But if you had said, "We're actually not facing the domain of all possible universes, but one in which Ramen noodles exist. And it is not surprising that natural selection yields intelligent life in a world with Ramen noodles. NFL doesn't apply."...that wouldn't have been nearly as convincing.

    Let me put it another way. When the ignorant creationist throws the "random chance? ha!" objection to the biologist, surely it wouldn't be enough to say, "No no, we are saying random chance plus regular physical laws!"

    On the contrary, they want to claim that natural selection provides the mechanism through which this apparently designed complexity enters the scene.

    Anyway, you understand the position so I'll stop; I was mostly spelling it out again for onlookers.

    ReplyDelete
  7. Jared9:50 PM

    Bob,

    Continuity is not required or possible. I referred to "discrete" search spaces and objective functions. In fact, Wolpert and Macready prove the NFL theorems only for finite search spaces and functions (i.e., the range of the function is also finite). So, the concepts of continuity and discontinuity don't apply. The spike can just be a small flat region elevated from its surroundings, so if you hit it at all you're at the top. (They point out that in the case of computer search, you're always dealing with a finite domain and range. E.g., a ten-dimensional space over "real" numbers that are in fact 64-bit floating point numbers is just a finite space of size 2^640.)

    Because we're dealing with finite domains, there are no counting issues. As far as intuition about the count, I suspect that any imbalance among functions that "appear to have overall hills and valleys" is offset among the large majority of functions that don't "appear to have any structure". It's not intuitively clear how the count works for sure, but it's less counterintuitive than if you don't have an example at all where hill-descending beats climbing.

    You can find Wolpert and Macready's article at Wolpert's website:
    http://ti.arc.nasa.gov/people/dhw/optimization.php

    Returning to the issue of continuity, you can find an article here:
    http://hal.inria.fr/inria-00173209/en/
    which I have only skimmed, which claims that a weaker form of NFL holds for countably infinte domains and that NFL doesn't hold for continuous domains.

    ReplyDelete
  8. Jared,

    Continuity is not required or possible...The spike can just be a small flat region elevated from its surroundings, so if you hit it at all you're at the top.

    Ohhhhhh. Now I totally get it, and the NFL theorems seem trivial. But I guess that happens with any important proof. :)

    So the reason we intuitively think the uphill search ought to work, is that we hear "landscape" and picture something where a high point is adjacent to slightly lower points, etc. But there is no reason for the "landscape" to look like this.

    In reality it is just an assignment of different numbers (which we metaphorically call "elevation") to different x-y coordinates. And so if we don't impose any structure on how these elevations are distributed among the x-y plane, then of course everything does as well finding the highest point as random search.

    Is this it?

    ReplyDelete
  9. Bob,

    Yes, that's how it works.

    You can also see why I immediately honed in on the existence of regular laws of physics. Just as most possible "landscapes" in the x-y case are not what we'd normally consider landscapes, most possible "universes" in the NFL argument are not what we'd normally consider universes.

    Let me put it another way. When the ignorant creationist throws the "random chance? ha!" objection to the biologist, surely it wouldn't be enough to say, "No no, we are saying random chance plus regular physical laws!"

    This actually seems odd reading it again. If I claim that "natural selection (restricted single organism case) plus regular physical laws" is better than "random chance plus regular physical laws", an NFL argument can no more demolish it than it can demolish the claim that "hill climbing plus smooth landscapes" is better than "random chance plus smooth landscapes". It can only demolish the claim that, in every scenario whatsoever, "natural selection (RSOC)" is better than "random chance". I am then free to choose a restriction with rhetorical force, like "the existence of regular physical laws". The weakness of the argument is thus that it allows the choice of any restriction, including whichever restriction makes the best counterargument.

    ReplyDelete
  10. If I claim that "natural selection (restricted single organism case) plus regular physical laws" is better than "random chance plus regular physical laws", an NFL argument can no more demolish it than it can demolish the claim that "hill climbing plus smooth landscapes" is better than "random chance plus smooth landscapes".

    Right, and just to repeat my position, the issue is, "Why should there be a universe that is apparently selected such that natural selection yields intelligent life?"

    NFL shows us that in general we shouldn't expect this to be the case. NFL doesn't show us that with physical laws, you will get intelligent life; it's rather just inapplicable to that case.

    So the point of NFL is reinforce that it's not obvious natural selection "ought" to work.

    ReplyDelete
  11. "It wouldn't bother me in any way if someone showed a movie of the entire history of the earth, and the neo-Darwinian story apparently played out perfectly."

    And this is the key point the Creationism business tends to obscure. If the exact physical sequence of events described by NeoDarwinism really was what took place, it would make no difference at all on the issue upon which a philosophical simpleton like Dawkins thinks it is so decisive. This is what Kant noted over two centuries ago, and what was ignored in making Darwinism what Voegelin called 'a new creed for the semi-educated'.

    ReplyDelete
  12. No one has adduced the anthropic explanation (if explanation it is): the universe is built on rules requiring or facilitating the appearance of intelligent (well, or at least not entirely stupid all the time) life because otherwise we wouldn't be here observing and discussing it.

    ReplyDelete
  13. Gene said,

    And this is the key point the Creationism business tends to obscure.

    Well, right, I grant that a lot of six-day literalists say silly things. But when you get to the people actually writing books, I think the neo-Darwinists are more confused on this point than the ID'ers. E.g. Phillip Johnson is somewhat of a blowhard in general, but he does a good job laying out that Darwinism as taught in schools carries the extra philosophical punch that, "This is all a blind process. If you view it as natural forces playing out to achieve some pre-ordained goal, then you have misunderstood the theory." (I'm paraphrasing, that's not an actual quote from him.)

    And of course the famous book title is the Blind Watchmaker.

    ReplyDelete
  14. No one has adduced the anthropic explanation (if explanation it is): the universe is built on rules requiring or facilitating the appearance of intelligent (well, or at least not entirely stupid all the time) life because otherwise we wouldn't be here observing and discussing it.

    Right, but if a priori it is extremely unlikely that we should exist (and then wonder why we exist), that leaves two main explanations:

    (1) The rules were consciously chosen to yield life,

    (2) There are an infinite number of possible universes, and naturally we only exist in the small subset that can yield life.

    ReplyDelete
  15. Anonymous9:16 PM

    Welcome to wow gold our wow Gold and wow power leveling store. We wow gold are specilized, wow power leveling professional and reliable wow power leveling website for wow power leveling selling and wow gold service. By the World of Warcraft gold same token,we offer wow power leveling the best WoW service wow power leveling for our long-term and wow powerleveling loyal customers. wow powerleveling You will find wow powerleveling the benefits and value powerleveling we created powerleveling different from other sites. As to most people, power leveling they are unwilling to power leveling spend most of wow power leveling the time wow gold grinding money Rolex for mounts or rolex replica repair when replica rolex they can purchase Watches Rolex what they Rolex Watches are badly need. The Watch Rolex only way is to look Rolex Watch for the best place rs gold to buy cheap WOW gold. Yes! You find it here! Our WoW Gold supplying service has already accumulated a high reputation and credibility. We have plenty of Gold suppliers, which will guarantee our delivery instant. Actually, we have been getting Runescape Gold tons of postive feedbacks from our loyal RuneScape Money customers who really appreciate our service.

    ReplyDelete
  16. We offer WoW power leveling,World of Warcraft power leveling,Warhammer Online Power Leveling & Warhammer Power Leveling & Warhammer Online Gold,if you want buy cheap wow power leveling & honor power leveling,please come here to choose. you could find any kinds of powerleveling you want. Please remember,we are your online game helper. Please remember,we are your online game helper.please come here to choose. you could find anything you want.wow power leveling,wow power leveling,wow power leveling,wow power leveling,wow power leveling,wow powerleveling,wow powerleveling,wow powerleveling,wow powerleveling,wow powerleveling,Warhammer Online Power Leveling,war leveling,Warhammer leveling,Warhammer Power Leveling,Warhammer Online Gold,Warhammer Gold,WAR Power leveling,WAR Gold,world of warcraft power leveling,world of warcraft power leveling,world of warcraft power leveling,world of warcraft power leveling,world of warcraft power leveling,world of warcraft powerleveling,world of warcraft powerleveling,world of warcraft powerleveling,world of warcraft powerleveling,world of warcraft powerleveling,wow gold,wow gold,wow gold,wow gold,wow gold,world of warcraft gold,world of warcraft gold,world of warcraft gold,world of warcraft gold,world of warcraft gold,AOC Power Leveling,AGE OF CONAN Power Leveling,Warhammer Online Power Leveling,Warhammer Power Leveling,Warhammer Online Gold,Warhammer Gold,2 Moons Dil,MapleStory Mesos,Maple Story Mesos,MS Mesos,WARHAMMER ONLINE GOLD,Cheap WARHAMMER ONLINE GOLD,RuneScape Gold,RS Gold,RuneScape Money,RS Money,SilkRoad Gold,SilkRoad Online Gold,SRO Gold,EVE ISK,EVE Online ISK,Gaia Gold,2 Moons Dil,WOTLK power leveling,AOC Gold,AGE OF CONAN Gold,LOTRO Gold,Lord of the Rings Online Gold

    ReplyDelete