### The King of Bad Math: Dembski's Bad Probability

It's time to take a look at one of the most obnoxious duplicitous promoters of Bad Math, William Dembski. I have a deep revulsion for this character, because he's actually a decent mathematician, but he's devoted his skills to creating convincing mathematical arguments based on invalid premises. But he's careful: he does his meticulous best to hide his assumptions under a flurry of mathematical jargon.

For today, I'm going to focus on his paper Fitness Among Competitive Agents.

One of the arguments that he loves to make, and which is at the heart of this paper, is what he calls the No Free Lunch (NFL) theorem. NFL states that "Averaged over all fitness functions, evolution does no better than blind search."

Now, first, let's just take a moment to consider the meaning of NFL.

In Dembski's framework, evolution is treated as a search algorithm. The search space is a

The evolutionary search starts at some arbitrary node. It proceeds by looking at the edges exiting that node, and computes the fitness of their targets. Whichever edge produces the best result is selected, and the search algorithm progresses to that node, and then repeats the process.

How do you test how well a search process works? You select a fitness function which describes the desired outcome, and see how well the search process matches your assigned fitness. The quality of your search process is defined by the limit as maxlength approaches infinity:

So - what does NFL really say?

"Averaged over all fitness functions": take every possible assignment of fitness values to nodes. For each one, compute the quality of its result. Take the average of the overall quality. This is the quality of the directed, or evolutionary, search.

"blind search": blind search means instead of using a fitness function, at each step just pick an edge to traverse randomly.

So - NFL says that if you consider every possible assignment of fitness functions, you get the same result as if you didn't use a fitness function at all.

This is just a really fancy way of using mathematical jargon to create a tautology. The key is that "averaged over all fitness functions" bit. If you average over all fitness functions, then

Now, in the paper that I linked to, he's responding to someone who showed that if you limit yourself to

Dembski's response to this (sorry I'm not quoting directly; he only posts the paper in PDF which I can't cut and paste from), is to go into a long discussion of

The example he uses for this is a chess tournament: if you create a fitness function for chess players from the results of a serious of tournaments, you can wind up with results like player A can consistently beat player B; B can consistently beat C, and C can consistently beat A.

That's true. Competitive fitness functions

You're still selecting

In my taxonomy of statistical errors, this is basically modifying the search space: he's essentially arguing for properties of the search space that eliminate any advantage that can be gained by the nature of the evolutionary search algorithm. But his only argument for making those modifications have nothing to do with evolution: he's carefully picking search spaces that have the properties he want, even though they have fundamentally different properties from evolution.

It's all hidden behind a lot of low-budget equations which are used to obfuscate things. (In "A Brief History of Time", Steven Hawking said that his publisher told him that each equation in the book would cut the readership in half. Dembski appears to have taken that idea to heart, and throws in equations even when they aren't needed, in order to try to prevent people from actually reading through the details of the paper where this error is hidden.)

For today, I'm going to focus on his paper Fitness Among Competitive Agents.

One of the arguments that he loves to make, and which is at the heart of this paper, is what he calls the No Free Lunch (NFL) theorem. NFL states that "Averaged over all fitness functions, evolution does no better than blind search."

Now, first, let's just take a moment to consider the meaning of NFL.

In Dembski's framework, evolution is treated as a search algorithm. The search space is a

*graph*. (This is graph in the discrete mathematics sense: a set of discrete nodes, with a finite number of edges to other nodes.) The nodes of the graph in this search space are "outcomes" of the search process at particular points in time; the edges exiting a node correspond to the possible changes that could be made to that node to produce a different outcome. To model the quality of a nodes outcome, we apply a fitness function, which produces a numeric value describing the fitness (quality) of the node.The evolutionary search starts at some arbitrary node. It proceeds by looking at the edges exiting that node, and computes the fitness of their targets. Whichever edge produces the best result is selected, and the search algorithm progresses to that node, and then repeats the process.

How do you test how well a search process works? You select a fitness function which describes the desired outcome, and see how well the search process matches your assigned fitness. The quality of your search process is defined by the limit as maxlength approaches infinity:

- For all possible starting points in the graph:

- Run your search using your fitness metric for maxlength steps to reach an

end point.

- Using the desired outcome fitness, compute the fitness of

the end point

- Compute the ratio of your outcome to the the maximum result

the desired outcome. This is the quality of your search for this length

- Run your search using your fitness metric for maxlength steps to reach an

So - what does NFL really say?

"Averaged over all fitness functions": take every possible assignment of fitness values to nodes. For each one, compute the quality of its result. Take the average of the overall quality. This is the quality of the directed, or evolutionary, search.

"blind search": blind search means instead of using a fitness function, at each step just pick an edge to traverse randomly.

So - NFL says that if you consider every possible assignment of fitness functions, you get the same result as if you didn't use a fitness function at all.

This is just a really fancy way of using mathematical jargon to create a tautology. The key is that "averaged over all fitness functions" bit. If you average over all fitness functions, then

*every node*has the same fitness. So, in other words, if you consider a search in which you can't tell the difference between different nodes, and a search in which you don't look at the difference between different nodes, then you'll get equivalently bad results.Now, in the paper that I linked to, he's responding to someone who showed that if you limit yourself to

*competitive*fitness functions (loosely defined, that is, fitness functions where the majority of times that you compare two edges from a node, the target you select will be the one that is better according to the desired fitness function), then the result of running the search will, on average, be better than a random traversal.Dembski's response to this (sorry I'm not quoting directly; he only posts the paper in PDF which I can't cut and paste from), is to go into a long discussion of

*pairwise*competitive functions. His focus is on the fact that a pairwise fitness function is not necessarily transitive: if it says A is fitter than B, and B is fitter than C, then that doesn't necessarily mean that it will say A is fitter that C.The example he uses for this is a chess tournament: if you create a fitness function for chess players from the results of a serious of tournaments, you can wind up with results like player A can consistently beat player B; B can consistently beat C, and C can consistently beat A.

That's true. Competitive fitness functions

*can*have that property. But if you're considering evolution,*that doesn't matter*. In an evolutionary process, you'd wind up picking one, two, or all three as the fittest. That's what speciation*is*. In one situation, A is better, so it "wins". Starting from the same point, but in a slightly different environment, B is better, so it wins.You're still selecting

*a*better result. The fact that you can't always select one as best doesn't matter. And it doesn't change the fundamental outcome, which Dembski doesn't really address, that competitive fitness functions*do*produce a better result that random walks.In my taxonomy of statistical errors, this is basically modifying the search space: he's essentially arguing for properties of the search space that eliminate any advantage that can be gained by the nature of the evolutionary search algorithm. But his only argument for making those modifications have nothing to do with evolution: he's carefully picking search spaces that have the properties he want, even though they have fundamentally different properties from evolution.

It's all hidden behind a lot of low-budget equations which are used to obfuscate things. (In "A Brief History of Time", Steven Hawking said that his publisher told him that each equation in the book would cut the readership in half. Dembski appears to have taken that idea to heart, and throws in equations even when they aren't needed, in order to try to prevent people from actually reading through the details of the paper where this error is hidden.)

## 46 Comments:

"(sorry I'm not quoting directly; he only posts the paper in PDF which I can't cut and paste from)"

You can, even if you are just using Adobe Reader. Click the button just to the right of the button with a hand icon, an I-beam cursor with the legend "Select". Or pick "Tools" "Basic" "Select". Select and copy. Of course, fancy formatting and characters may not come through properly, depending on the receiving program.

Nice post.

By Anonymous, at 11:28 AM

He'll also have to manually remove all the paragraph marks at the end of each line.

By Orac, at 12:10 PM

"You can, even if you are just using Adobe Reader."

This is only true if the pdf file has not been protected. I have many pdf papers for which I cannot use the copy function.

By Anonymous, at 12:20 PM

Mind if I check my intuitive understanding of the NFL theorems with you? I interpreted it as follows, but I'm no operational researcher.

You can have algorithms that are good at a great many things - for the sake of graphicality consider an algorithm to produce a washing machine, another to produce a toaster, and a "null algorithm" that does nothing. The NFL theorems say that no such algorithm can be consistently better than the null algorithm - for example, if you try to use the toaster algorithm in place of the washing machine algorithm you'll get burnt shirts, which is a worse outcome than if you hadn't done anything at all.

These are all blind algorithms - the toaster algorithm, for example, takes no account of the fact that its product is likely to set fire to the laundry. If, however, you choose a non-blind algorithm, the problems evaporate.

An example of such a non-blind algorithm might be an engineering company producing a product for a customer. The "target space" in this case is basically "whatever the customer wants", which can be determined by contact with the customer. If the customer wants a toaster, they'll get a toaster. If they want a washing machine, they'll get a washing machine. Such non-blind searches can consistently perform better than average.

The evolutionary search is hunting for "whatever will help me survive in this environment", and it's determining this by contact with the environment. Thus it's a non-blind search and hence the NFL theorems don't apply.

By Lifewish, at 12:28 PM

Oh, by the way, in the last few hours you've been listed on about 4 ScienceBlogs blogs and counting. Expect to be swarmed :P

By Lifewish, at 12:29 PM

Excellent work! Maybe you could go to Uncommon Descent, Buffalo Bill's blog and beat up DaveScott (Springer). I must admit it would make me laugh to see them cry!

By J-Dog, at 12:30 PM

Good blog. I often address Dembski on my blog, Notes in Samsara.

By Mumon, at 12:33 PM

lifewish:

What Dembski does is even worse than what you're describing. He wants to argue that an evolutionary algorithm - a search algorithm with a fitness function - cannot produce better results than randomness. But the way that he does that is by talking about the averaged performance of all possible fitness functions.

He doesn't talk about what kind of performance you can get if you select

afitness function, even a bad one. He sticks to the composite of the average of all fitness functions - which is exactly equivalent to a random walk.By MarkCC, at 12:35 PM

Back in 1999, I commented on Dembski's then-new citation of NFL results:

"

The central question that Dembski poses concerning evolutionary algorithms is not one of comparative efficiency, but rather that of essential capacity. I find it difficult to see on what grounds Dembski advances NFL as a relevant finding concerning the capability of evolutionary algorithms to perform tasks. I ask Dembski to clarify his reasoning on this point."As Mark points out, Dembski has yet to clarify matters concerning this issue.

Wesley R. Elsberry

By Anonymous, at 12:52 PM

Grat post and great new blog. I look forward to more. Thaks for demonstrating in yet another way the vapidity of IDiots like Dembski.

By CanuckRob, at 1:03 PM

Another problem with the NFL argument to evolution:

Evolution doesn't use all possible fitness functions, it uses one specific fitness function: the phenome's chances of surving long enough to reproduce. So whether or not the search process is no better than random search when looking at all possible fitness functions isn't important. What's important is whether the search is better on random on the specific fitness function under consideration.

By Stormy Dragon, at 1:26 PM

Very nicely written post. Understandable even to me, a non mathematician. One more bunk argument busted.

By Anonymous, at 1:44 PM

Ok,

nowyou've got a shout-out from PZ. And well deserved, I should add.By jackd, at 1:50 PM

In an earlier paper called "Searching Large Spaces: Displacement and the No Free Lunch Regress", Dembski laid out his basic scheme in what he called the "fundamental theorem" of ID. The piece under consideration in this thread is an elaboration of one issue associated with that paper.

Dembski's argument founders on this simple point: "The evolutionary search starts at some arbitrary node."

Biological evolution does not start "at some arbitrary node". It starts on a node

already known to be sufficiently fit-- the population is reproducing successfully. In the terms of Dembski's Displacement Theorem paper, the population doesn't have to search for T, a small target in some large space, starting from some arbitrary point; it isalready in T. Biological evolution consists in 'finding' better (more fit) nodes that are also in T without "searching" for them.Moreover, evolutionary "search" does not sample the whole space of possible variants. It samples adjacent variants, where "adjacent" means "one application of one of the evolutionary operators away from the current node". Since most selectively relevant variables display nonzero local autocorrelations (

i.e.they are characterized by more or less smooth gradients rather than random topography in space and/or time), the population preferentially samples nodes that are also within T.In my less-than-humble opinion, the "search" metaphor for biological evolution is seductively and profoundly misleading.

By Anonymous, at 1:51 PM

In an earlier paper called "Searching Large Spaces: Displacement and the No Free Lunch Regress", Dembski laid out his basic scheme in what he called the "fundamental theorem" of ID. The piece under consideration in this thread is an elaboration of one issue associated with that paper.

Dembski's argument founders on this simple point: "The evolutionary search starts at some arbitrary node."

Biological evolution does not start "at some arbitrary node". It starts on a node

already known to be sufficiently fit-- the population is reproducing successfully. In the terms of Dembski's Displacement Theorem paper, the population doesn't have to search for T, a small target in some large space, starting from some arbitrary point; it isalready in T. Biological evolution consists in 'finding' better (more fit) nodes that are also in T without "searching" for them.Moreover, evolutionary "search" does not sample the whole space of possible variants. It samples adjacent variants, where "adjacent" means "one application of one of the evolutionary operators away from the current node". Since most selectively relevant variables display nonzero local autocorrelations (

i.e.they are characterized by more or less smooth gradients rather than random topography in space and/or time), the population preferentially samples nodes that are also within T.In my less-than-humble opinion, the "search" metaphor for biological evolution is seductively and profoundly misleading.

By Anonymous, at 1:51 PM

Rats. Sorry for the couble post.

By Anonymous, at 1:51 PM

Great job!

Of Dembski's two "big ideas," the NFL stuff was the harder for me to address, but you've explained it very clearly.

If I'd proposed his "Explanatory Filter" in my freshman combinatorics/probability class, I would have been redirected to the English department.

*sigh* Where's my PhD?

By ArtK, at 2:02 PM

As others have said, nice post.

A separate problem is with the search strategy. In a graph where the evolutionary search has to always choose the more fit route, you could imagine situations where evolution gets stuck on a local peak, but can't go through a lower fitness region to reach a higher peak. Yet Holland's genetic algorithms show why genetic combination searches complex fitness spaces (multi-peaked) quite broadly, and overcomes this problem.

By cw, at 2:57 PM

There's a nice summary of Dembski's mathmatical history on the Panda's thumb here.

A nice summary (which echoes markcc's and Wesley Elsberry's comments):

"Understanding the NFL theorems may require some work, but the basic flaw in Dembski's argument is easy, even trivial, to spot. It is that the NFL theorems only tell us something about the avergae performance of a fitness algorithm over all possible fitness landscapes. It tells us nothing about the performance of an algorithm on any given fitness landscape. End of discussion."

And another extremely important point:

"There are further difficulties, such as the fact that in evolution the fitness landscape coevolves with the organisms residing upon it, but there is no need to get into that here."

By Tim Hague, at 3:44 PM

Just to be clear, the NFL stuff was originally done by Wolpert and MacReady: http://www.no-free-lunch.org/WoMa95.pdf

and later published by the IEEE in 1996. There's also a whole kaboodle of refs here: http://www.no-free-lunch.org/

The basic premise is that no search algorithm can perform better than random search -- when averaged over all possible fitness LANDSCAPES. Not fitness FUNCTIONS as you said in this blogpost.

Since all possible landscapes include a large number of environments that have no structure to find, no search algorithm is going to work very well, ON AVERAGE. This is because most (all?) algorithms assume some sort of hill-to-climb, and as cw said above, genetic algorithms ala Holland solve some of the local maxima difficulties inherent to climbing the nearest hill.

For a little more detailed rant, see my previous comment to the second Information Theory blogpost on this site.

MS

By Michael Schippling, at 4:13 PM

Very nice exposition. The only unclear thing about it your description of Dembski as a "decent mathemetician." From your deconstruction, he either doesn't know what he's talking about or he is being intentionally deceptive. Or both.

By Anonymous, at 4:45 PM

anonymous:

I meant that Dembski is a good mathematician in the sense of a skillful one. He's not making mistakes because he doesn't know better - he's doing a very slick job of use math to support the argument he wants to make. He is lying, deliberately cooking up invalid mathematical models that he can then use to present convincing-looking proofs.

His argument in the linked paper about pairwise competition is valid math. It's just that he's subtly shifted the definitions so that what he's talking about is not the same thing as what he's allegedly refuting.

By MarkCC, at 4:53 PM

Another point to consider is that evolution works at the population level and not at the level of an individual, so I am not trying to 'survive', but my species is.

By Anonymous, at 5:34 PM

Richard Wein pointed out here that the laws of physics give rise to smooth genetic fitness landscapes. Dembski called his argument rubbish, and stated that continuous physical laws don't necessarily result in smooth fitness landscapes. Wein subsequently settled on a weaker claim - that the landscape is patterned, regardless of whether it's smooth.

But Wein was 100% correct the first time. The genetic fitness landscape is certainly smoother than average, and that smoothness is ultimately due to the continuity of physical laws. Dembski's response was both dead wrong and inflammatory.

By secondclass, at 5:38 PM

"

The basic premise is that no search algorithm can perform better than random search -- when averaged over all possible fitness LANDSCAPES. Not fitness FUNCTIONS as you said in this blogpost."The phrase used by Wolpert and MacReady was "cost functions", if you want to get picky. The set of all "cost functions" is the set of all mappings of items X in the domain to cost values Y in the range.

Wesley R. Elsberry

By Anonymous, at 5:59 PM

Evolution by natural selection is not an optimizing process at all, at least not in the sense that it optimizes the performance of the population or species. Rather, it usually optimizes the performance ("fitness") of individuals (or better yet: genes). Individual optima do not necessarily coincide with group, population or species optima. A case in point are genes on Y-chromosomes that cause fathers to produce only sons. Such a gene will spread (at the expense of X chromosomes) but it may cause population extinction (as soon as there are too few females). This has been predicted by W.D. Hamilton (in a famous Science paper "Extraordinary sex ratios", 1967 I think), and it has been observed in certain insects, and is being studied seriously as a potential tool to exterminate pest insects.

By Raevmo, at 6:05 PM

The reason you state why the NFL-theorem is a tautology is not really correct.

The fact that you average over all

fitness functions does not imply that every node has the same fitness. You cannot bring the averaging process inside the search algorithm.

As a counterexample consider that you only average over all smoothly varying fitness functions. The

fitness of every node will again be the same but the evolutionary search will perform better than random search.

The reason why NFL works is that almost all fitness functions are structureless random noise functions. On those functions no algorithm can do better than random search. Moreover, For every algorithm that uses some structure of the fitness function to improve the search one can also find fitness functions with an opposite structure for which the algorithm does it worse

(For evolutionary search these are

the functions with a spiked fitness maximum surrounded by a deep broad low fitness valley).

These remarks however do not alter the main conclusion of your post: nl. that Dembski consistently misuses these theorems in his crusade against evolution.

Keep up the good work.

By Raf Bocklandt, at 7:10 PM

I'm not seeing an RSS or ATOM feed link. Blogger should have an easy method to enable such things, if you wanted to be read more.

By Anonymous, at 7:29 PM

Wow but there's a lot of activity today. That's what happens when a ton of folks all link on the same day.

So, wrt to fitness functions/cost functions/fitness landspaces: I'm presenting it from a discrete math point of view: instead of a continuous landspace, I'm using a graph. Each point in the graph represents a state at a point in time; it has edges to represent states that can be transitioned to in one time unit. Given that representation, the difference between a fitness function and a fitness landspace is that they're duals: you can make it a fitness landscape by assigning a cost to the graph edges, and counting that cost against the evaluation function; or you can assign those numbers to the nodes of the graph. (The dual transformation is slightly more complicated than that, but that's the principle.) In a continuous domain, that transformation doesn't work so well. But discrete graphs work very nicely as a model of evolution.

In the discrete model, it works out pretty nicely; and the fitness functions do operate as the equivalent of a fitness landscape, but I think that the idea of an evaluation function is easier to understand that a landscape.

By MarkCC, at 7:47 PM

With respect to the combination of fitness function, I'm afraid my wording was rather imprecise. As I've mentioned, I'm still figuring out how to write for a non-expert audience.

When I talk about averaging functions, I'm talking about the average of their performance over all inputs. If you use all fitness functions, then you can show that for each function f, there's another function f', where f''s performance score is the opposite of fs. So if f gets a 1, f' gets a 0; etc. So each pair cancels, and you wind up with dead-average perfomance of random walk. (Again, I'm being a bit simplistic here: the shape of the graph and the fundamental fitness function affect the way that you can generate an opposite function - but that's exactly matched by the performance impact of that shape and fitness function on the average result of a random walk.)

By MarkCC, at 7:57 PM

Vis Landscape vs Cost Function.

OOPS...I guess I should at least (re-)read the abstracts of things I reference...I've been thinking about the problem from the gritty details of machine learning and can only deal with simpleminded mappings of theory to praxis... I'll go with markcc's discrete node/edge explanation of the confusion (in my brain).

As per physics being responsible for _smoother_ "fitness landscapes", I believe it goes back to my point about there being some environmental structure on which to hang your algorithm. It doesn't need to be smooth, but it needs to be ordered.

I promise not to say this again, but the useful order measurement is not straight forward Shannon Entropy, but what Gell-Mann & Lloyd describe as Effective Complexity.

MS

By Michael Schippling, at 9:43 PM

If you use all fitness functions, then you can show that for each function f, there's another function f', where f''s performance score is the opposite of fs. So if f gets a 1, f' gets a 0; etc. So each pair cancels, and you wind up with dead-average perfomance of random walk....So the toaster scorches the socks and the washing machine dissolves the crumpets? Or am I getting myself confused again?

After 3 years of pure maths, I really should be able to come up with better analogies :(

By Lifewish, at 10:57 PM

Writing for a lay-audience, my favorite way to describe the problem would be the continuous, not the discrete, case; I think it's easier to visualize.

It ought to be intuitively obvious that some search algorithms are clearly better than random for some surfaces. For example, if your surface is a simple cone, an algorithm that blindly seeks the center point from wherever it starts is more efficient than a random path about the cone's surface.

It's a little harder to take this analogy to

anysurface, but if you can get people to picture weird, fantastical surfaces with crags and spikes and cliffs, then it shouldn't be too difficult informally argue that even a finely tuned search algorithm that works for whole classes of surfaces, will eventually encounter a set for which it performs miserably.Thus random is as good as it gets if you try to tackle everything. Jack of all trades, master of none, as they say.

By Eric Wallace, at 1:42 AM

"Anonymous said...

Another point to consider is that evolution works at the population level and not at the level of an individual, so I am not trying to 'survive', but my species is.

"

This is a different Anonymous speaking now... Sorry - this kind of thinking was left behind a long time ago. The majority view is that selection acts at the individual level, not at the group/population/species level. Some (e.g. Dawkins) would go as far as to say selection acts at the genetic level...

By Anonymous, at 3:02 AM

A simple (if crude) way to sum up the NFL theorem is as follows: in a uniformly random fitness landscape (aka fitness function) it doesn't matter where you search next, because every point is as likely to be good or bad as every other point (more accurately, the probability distribution of the fitness at every point is uniform); therefore, no search strategy is any better than any other.

The NFL theorem is really quite uninteresting.

By Richard Wein, at 4:24 AM

Honestly, even beyond the points made above, I would question whether attempting to model evolution as a search function is even the appropriate thing to do in the first place.

If I understand correctly, when theorems like the NFL ones talk about an algorithm "doing better" than another algorithm, they're talking about whether or not the algorithm finds the absolute optimum result on the graph (or at least a better absolute optimum result than the other algorithm). Right? But we don't *care* about the absolute optimum result, not when we're talking about evolution. We just care about finding *an* optimal result. If it's just a local maxima, that's fine.

I don't think anyone has ever reasonably claimed evolution finds *absolute* optimal results-- just that it approaches results which are optimal *for some evolutionary niche*. Saying that an evolved organism is optimal for its niche and that a search algorithm solution is locally optimal seem to me intuitively identical statements. Since the "goal" (metaphorically speaking) of the biological evolutionary process is not to search for an optimal position on the landscape, but to find some local peak on that landscape and guard it jealously, I don't see why Dembski's theorems would be important even if they meant what he claims to think they do. One might as well claim the Bible is useless because it makes a poor cookbook.

Am I incorrect or missing something here?

By Andrew McClure, at 5:00 AM

Andrew, maximums (global or local) do not enter into it. For the purposes of NFL, a search is evaluated in terms of some function of the fitness values of the points traversed. This could be simply the highest fitness value discovered during the search. So we can say (per the NFL theorem) that, on a uniformly random fitness function, all algorithms attain the same highest fitness value on average after a given number of steps.

Note: the NFL theorem only considers algorithms which never visit the same point twice. It should be clear that a search algorithm which keeps visiting the same point over and over again will on average perform worse than one which keeps trying new points.

By Richard Wein, at 7:23 AM

P. S. It's just occurred to me that you might have been confused by Mark's assertion that the performance of the search is measured "by the limit as maxlength approaches infinity" (where "maxlength" is the number of steps). This assertion was incorrect. The number of steps is simply fixed at any value you like. Moreover, since the algorithm cannot return to previously visited points (aka nodes), it there cannot be more steps than there are points in the search space (since by then the search space will have been exhaustively searched).

In practice it is assumed that the number of points in the search space is so vast that the issues of revisiting previous points and exhausting the search space are irrelevant. The search space is usually a continuous one, and the NFL theorems (which apply only to discrete search spaces) are considered an approximation.

By Richard Wein, at 7:40 AM

I've only just read the Dembski paper that was the object of Mark's blog entry, and I think it's not all bad. (I should add here that I haven't read the Wolpert paper that Dembski claims to be responding to, so I can't evaluate Dembski's paper as a response to Wolpert's.)

The particular objection to his NFL argument that Dembski is addressing here is the objection that the NFL theorems do not apply to coevolutionary systems, i.e. ones involving "competitive agents" because the fitness of each agent depends on the other agents. In this paper, Dembski argues that we can contruct an absolute fitness value for each agent, i.e. a fixed fitness function over the search space. The search of this fitness function can then be considered an approximation to the coevolutionary search, and is subject to an NFL theorem. I'm not entirely convinced, but I think he may well have a good point. In fact, I've seen a similar argument made before (by someone who was no friend to Dembski).

Of course, the big problem with Dembski's paper is that it leaves unaddressed the more fundamental objection to his NFL argument, namely that the NFL theorems are all based on the assumption of a random fitness function, and that this doesn't correspond to the situation in the real world. Additionally, Dembski makes a number of typically deceptive remarks, such as his claim that "David Fogel ... look[s] to competitive environments in which NFL supposedly breaks down". He implies that Fogel was trying to overcome some sort of problem with NFL, when in reality all Fogel set out to do was show how effective a simple evolutionary algorithm could be (and he succeeded).

By Richard Wein, at 9:16 AM

Funny that Dembski spends time trying to prove that evolution doesn't work, considering that we can SEE that it does work in evolutionary computation, as it does, unfortunately, in the bacteria and viruses that we keep fighting. I just want to link here those of you with (probably institutional) access to mathscinet to the review that Wolpert wrote on Dembski's "No Free Lunch" book. For those who don't, I quote a bit:

I say Dembski "attempts to" turn this trick because despite his invoking the NFL theorems, his arguments are fatally informal and imprecise. Like monographs on any philosophical topic in the first category, Dembski's is written in jello. There simply is not enough that is firm in his text, not sufficient precision of formulation, to allow one to declare unambiguously `right' or `wrong' when reading through the argument. All one can do is squint, furrow one's brows, and then shrug.Nice blog, by the way!

By andres, at 12:46 PM

I was reluctant to post a comment on MarkCC's fine critique of Dembski's misuse of the NFL theorem(s) because it may smack of self-promotion, but here it is: chapter 11 (which I authored) in the anthology

Why Intelligent Design Fails(Rutgers Univ. Press, 2004, editors Matt Young and Taner Edis)is devoted to a rather detailed debunking of Dembski's misuse of the NFL theorems. When writing that chapter, I was in contact with David Wolpert who suggested no objections to my arguments. Regarding MarkCC's fine post, his rendition of the NFL theorem (just the first theorem for search, there are others as well) is not exactly true to the original rendition by Wolpert & Macready: in its original form it says nothing about evolution but only states that the probability of a given "sample" to be obtained in a search is the same for all searching "black-box" algorithms if averaged over all possible landscapes (the difference between fitness function and cost function is irrelevant - they are just opposite ways to speak about the same search results). It says nothing about specific fitness functions or specific algorithms which, if not averaged, may (and do) very well drastically outperform blind search. Dembski has never responded to my critique in any form, although I know for fact he is familiar with it. Overall, he favors saturating his writing with formulas mostly adding nothing to the argument but only serving as an embellishment and intimidation of poor laymen scared by mathematical symbols. There is a lot of anti-Dembski stuff at http://www.talkreason.org. Mark PerakhBy Mark Perakh, at 3:17 PM

NFL means natural selection is worthless if the environment changes very fast. Yawn.

By Anonymous, at 7:41 PM

OK, I think I follow what is going on in this particular formalism, but I don’t see the relevance to evolution. All biological organisms are multi-component and live in environments that have multiple characteristics. Doesn’t that make fitness into multi-dimensional functions? Such functions cannot be ordered, so what is being compared here? (I haven’t looked at any of the linked text, are the answers to be found there?)

By Anonymous, at 4:26 PM

Sports Pool

Play for FREE in our Office Pool,

and win FREE weekly prizes. Play

FREE now! http://www.officepoolgaming.com/

By Bimbo, at 11:39 PM

Great posting. Sorry to beat a selected-out horse, but one more comments about PDF's: some people create PDFs by scanning originals as graphics; in that case, it's impossible to grab the text without further OCR.

By Anonymous, at 8:21 AM

Thanks for causing me to think of it as node-exploration.

The node-choice is (obviously) random.

Succesful node choices (by the increased reproduction fitness test) are what is called evolution.

By josh narins, at 7:57 PM

Post a Comment

<< Home