Icons of ID: No Free Lunch Theorems

I should serve you notice that "No Free Lunch" will prove a bad title for Bill's new book. Question: Did Dembski confer with David Wolpert over his deployment of NFL principles in "Can Evolutionary Algorithms Generate Specified Complexity?"? I already know that the answer is, "No." I've tried to point out on at least two prior occasions that Bill's use of NFL has major problems. Bill is entitled to ignore my opinions on NFL, but there are others who might be less easily dismissed when they weigh in. If Bill insists on going so far as putting Wolpert and Macready's theorem on the cover of his book, I think that there is going to be a high likelihood of major embarrassment over that. Fair warning.

Perhaps it is appropriate to point out that the anthology titled Why Intelligent Design Fails: A Scientific Critique of the New Creationism (edited by Matt Young and Taner Edis) which is coming this month from Rutgers University Press, contains, among other chapters, my chapter titled There Is a Free Lunch After All: Dembski's Wrong Answers to Irrelevant Questions. This chapter is mainly about Dembski's misuse of the No Free Lunch theorems and his so called displacement problem.

It looks like changing the tune after having encountered critique (especially from Wolpert, against whom Dembski had no chance as far as the NFL theorems were in question)Dembski made a very awkward attempt to alleviate embarrassment at being rebuffed by the author of the theorems in question - he tried to play down the role of the NFL theorems in his theory. Instead, he stressed the significance of what he calls displacement problem. Unfortunately for Bill Dembski, his appeal to the displacement problem has not improved his position at all but rather should add more embarrassment to him as the problem in point is a phantom, as discussed in detail in the above mentioned chapter.

Koons's accolade and his cry to Darwinists to accept Dembski's allegedly brilliant and illuminating analysis is especially funny given Koons's evident lack of familiarity with information theory and with the essence of the NFL theorems: in a letter to Science Insights (the organ of the National Association of Scholars -see vol. 7, No 5, 2003, at www.nas.org ) Koons wrote that the NFL theorems are part of information theory! This is news for all those having a minimal knowledge of either information theory or optimization theory.

Koons is in general a good comedian. In a blurb to Dembski's Intelligent Design he wrote that Dembski's law of conservation of information was a great breakthrough in information theory. However, after Dembaki alleged law was substantially dismantled by a number of critics, in his (more recent) mentioned letter to Science Insights Koons asserted that Dembski in fact did not suggest any new law but only showed how to apply the NFL theorems to biology, etc. He seemed not to realize that Dembski's pseudo-law and his attempts to apply the NFL theorems stand in no relation to each other. What a circus! With friends like Koons Dembski needs no adversaries.

Hey, Dr. Bill: What about admitting at least a single error for change? After all, you have a place to go - the barbecue stand in Riesel Tx is not a bad backup, is it.

Perhaps most significantly, however, we can admit our mistakes and receive instruction. The evolutionists cannot. Indeed, the moment they admit that we might have a point, they let the genie out of the bottle. To open evolutionary theory to critical scrutiny would destroy their monopoly over the study of biological origins.

The upshot of these theorems is that evolutionary algorithms, far from being universal problem solvers, are in fact quite limited problem solvers that depend crucially on additional information not inherent in the algorithms before they are able to solve any interesting problems. This additional information needs to be carefully specified and fine-tuned, and such specification and fine-tuning is always thoroughly teleological.

Many critics of Dembski's use of the "No Free Lunch" theorems take issue with it by pointing out that these theorems are based on averaging over all possible fitness landscapes, the vast majority of which are completely irrelevant, and represent problems that are not interesting to solve, because the fitness landscape looks like a random array of spikes.

In 1996 I showed that NFL is a symptom of conservation of information in search.

Since 1995 some have said that this suggests that NFL does not hold in the world, and I recently proved it. But it remains possible that the ?real-world? distribution approximates an NFL distribution closely.

Never mind. Found 'em.

RBH

All,

Sorry for the duplicate post. My browser said the connection had timed out on the first attempt, and I didn't realize the post might have succeeded.

RBH,

I have some papers, c.v., etc. on my home page, http://www.TomEnglishProject.com. Here's the one where I obtain NFL in terms of conservation of information:

English, T. M. "Evaluation of Evolutionary and Genetic Optimizers: No Free Lunch," in Evolutionary Programming V: Proceedings of the Fifth Annual Conference on Evolutionary Programming, pp. 163-169, 1996.

The following shows that NFL does not hold in the world, and treats search algorithms as operators on probability distributions on problems. The geometry of search in the space of distributions is quite interesting.

English, T. "No More Lunch: Analysis of Sequential Search," to appear.

Tom English:

Thanks for your comment and the reference to your articles. A few questions:

1. I am confused by the dates you indicated. As far as I am aware, Wolpert's NFL theorems for supervised learning appeared in 1996, and Wolpert-Macready's NFL theorems for search, in 1997, but you refer to 1995 and 1996 in regard to the theorems for search.

2. Have you communicated with Dave Wolpert regarding your proof that the NFL theorems are invalid for the real world problems, and if you did, what his reaction was? (I believe, Wolpert and Macready themselves admitted that their theorems are not very instrumental for solving real world problems, but your approach seems to be even more radical, is it?)

3. Regardless of what Wolpert or other experts may think of it, your discourse is beyond of what non-experts in optimization theory can comprehend. Therefore, IMHO, referring to the averaging as a point negating Dembski's use of the NFL theorems as alegedly proving the impossibility of evolution (which can be easily understood by laymen) seems to be justified. I discussed this point with Dave Wolpert and he did not offer objections to the use of the averaging argument. Cheers, Mark

More on references

NFL might have become something useless to Dembski if we had been more open to an unusual perspective. The first discussion of algorithmic complexity and NFL came soon after Wolpert and Macready released their tech report. Search for Kihong Park in the 1995 archive at http://www.aic.nrl.navy.mil/galist/. His comments were outstanding, but Wolpert dismissed them, and I was scurrying too much to contemplate learning new math.

I don't know a publication that clearly justifies the claim that run-to-run optimizer adaptation can be immunized against teleology. But consider uniformly sampling the space of optimizer parameters and evaluating the different parameter vectors on a sample of instances drawn according to the problem distribution. The problem distribution is given, and the sample of possible parameter vectors is uninformed, so there can be no teleology. Dembski would claim, perhaps, that it would take a great deal of time to get good results with this approach, but I predict otherwise. To be 99% sure of obtaining a parameter vector with performance ranked in the top percentile requires only a sample of 458 vectors. Massively parallel computers support simultaneous evaluation of many more vectors than that. Thus it may take no longer to discover good optimizer parameters than to evaluate one instance of the optimizer.

Is this invocation of brute-force parallel computation cheating? I'm no biologist, but I hear that nature is plagued with it.

Do the arguments of this paper contradict the evidence of remarkable adaptive mechanisms in biota? The question is meaningful only if one regards evolutionary adaptation as function optimization. Unfortunately, that model has not been validated. It is well known that biota are components of complex, dynamical ecosystems. Adaptive forces can change rapidly and nonlinearly, due in part to the fact that evolutionary adaptation is itself ecological change. In terms of function optimization, evaluation of points changes the fitness function. The Conservation Lemma [from which NFL derives] clearly does not apply to such a process.

Indeed, throughout there is a marked elision of the formal details of the biological processes under consideration. Perhaps the most glaring example of this is that neo-Darwinian evolution of ecosystems does not involve a set of genomes all searching the same, fixed fitness function, the situation considered by the NFL theorems. Rather it is a co-evolutionary process. Roughly speaking, as each genome changes from one generation to the next, it modifies the surfaces that the other genomes are searching. And recent results indicate that NFL results do not hold in co-evolution.

Tom English:
Thanks for the clarification. I am familiar with Wolpert's NFL theorems for supervised learning and W-M theorems for optimization to the extent of their published papers (and to the extent allowed by not being a professional mathematician). I did not know, though, that they had predecessors. After W-M paper appeared in 97, there were a few papers wherein limitations of the NFL theorems were discussed. I asked Dave about his opinion of those papers and he largely dismissed them (it was about two years ago, so I don't have references at hand). However, he admitted that the NFL theorems are crude tools shedding light on the relationship between fitness functions and search algorithms but their practical significance is very limited. You seem to be very well versed in the matter, so it'd be interesting if you exchanged views with Dave. He promised to publish a paper (again with Macready) in which to prove that the NFL theorems are invalid in the case of co-evolution - but we are waiting for it for more than a year. Just two weeks ago I asked him once again about that proof but he did no answer my question. It looks like you have such proof, don't you. At least it seems to follow from some of the sentences in your preceding comment. If this is indeed so, it is important as proof that the NFL theorems are of no consequence for biological evolution which is always a co-evolution (search changes the fitness landscape). It is a pity I did not know about the proof in question (if it indeed exists) when writing the chapter for the anthology from Rutgers - it would be a nice argument against Dembski. Anyway, that anthology is supposed to be for general audience, so we could not use sophisticated math in it. I consulted with Wolpert when writing it and he had no critical objection to my text. The loose rendition of the unexspurgated theorem, as you named it, seems to approach the matter from a slightly different angle as compared with the original NFL theorem by W-M: although identical distributions translate also into identical means, the opposite is not necessarily true. Your rendition looks therefore as a broader statement than the NFL theorem by W-M, but on the other hand it is more restrictive in that it limits the types of distributions. Or perhaps I am confused, but don't feel that you owe me any explanation - amateurs do not deserve detailed replies. Cheers, Mark

Mark,

Most people find my theoretical writing difficult, and I am here because I want to explain things in plain language. If my replies are too detailed, give me a nudge in the ribs.

I suppose you have "practical significance" with respect to biological evolution in mind. In nature the fitness function is nonstationary, the search is random, points are revisited, and the domain of fitness functions cannot be defined as a finite set. These are four substantial violations of the suppositions of the original NFL theorems.

I don't have a coevolution proof. And precisely what to prove is less than obvious. I will give it some thought.

My NFL theorem applies to infinitely many distributions of test functions, while Wolpert and Macready's applies to just one. Mine refers simply to sequences of observed values, while theirs refers to histograms of values. Sequences are simpler for various reasons, and some important aspects of NFL are easy to miss when working with histograms. As you say, "although identical distributions translate also into identical means, the opposite is not necessarily true."

Would someone mind explaining to me (here or with a link) what the NFL theorems actually state? Specifically the if...then part.

Would someone mind explaining to me (here or with a link) what the NFL theorems actually state?

Tom, I'm having difficulty understanding your paper "Evaluation of Evolutionary and Genetic Optimizers: No Free Lunch"
(http://www.tomenglishproject.com/EP96.pdf). I can't even work out where you actually state your NFL theorem! Could you please help.

Richard,

I don't think that's particular crude. In 1994 I served on the thesis committee of a student addressing function optimization. In his defense he said the ultimate goal was to obtain an optimizer that was superior for all functions, and I pointed out that optimizing a uniformly drawn function was equivalent to "optimizing" the value of a uniform random variable. In the following year, a student who had attended the defense learned of the NFL tech report before I did, and brought me a copy.

Various people understood that no optimizer could be generally superior on "purely random" fitness landscapes prior to 1995. Wolpert and Macready were the first to work out the details, and they did so extremely well, though not without errors.

Something I should have said earlier, and that fits reasonably well here, is that the main NFL results directly address neither evolutionary computation nor biological evolution. Take away the flamboyant attack on fuzzy thinking in EC, and what remains is an outstanding treatment of deterministic sequential search. To debunk the notion that an evolution-inspired algorithm could be generally superior to others, Wolpert and Macready reason about a deterministic sequential simulation of the algorithm. Unfortunately, most of the NFL results cannot be related to EC, and certainly not to evolution, through simulation.

Hi, Richard.

The interesting thing about it, from the "Icons of ID" perspective, is that the central result is the Conservation Lemma, in which I show that information is conserved in search. NFL follows easily from that. Incidentally, that is the first theoretical paper I ever wrote, so forgive the rough spots.

I wonder if there is a connection between conservation of information in my sense and conservation of complex specified information. I tried to grasp an answer for myself, but the Jello went squish. I would love to hear what someone who has gotten information through a side channel has to say.

Tom

I think it can also be crudely explained like this: in a purely random fitness landscape it doesn't matter how you search, because any point is as likely to be a good one as any other.

— Richard Wein

Hi, Richard. The interesting thing about it, from the "Icons of ID" perspective, is that the central result is the Conservation Lemma, in which I show that information is conserved in search. NFL follows easily from that. Incidentally, that is the first theoretical paper I ever wrote, so forgive the rough spots. I wonder if there is a connection between conservation of information in my sense and conservation of complex specified information. I tried to grasp an answer for myself, but the Jello went squish. I would love to hear what someone who has gotten information through a side channel has to say. Tom

If one cannot derive an expectation from the previously sampled points, then any search algorithm cannot do better than blind search.

As far as I can tell, Dembski has several importantly different definitions of "complex specified information"/"specified complexity" and alternates between them regularly depending on what is convenient.  You might be interested in this page on Definitional Complexity.

When they claim that "evolution can't produce new information" they generally mean things like new genes.  However, "information" in this colloquial sense is easy to evolve (duplication and divergence of genes under natural selection), so they have to come up with something abstruse and intimidating to make this claim appear defensible.

Let me see if I have this right.

If the search space is random, then no specific optimizer can do better on average than a random search can.

How does this pertain to optimizing strategies? In other words, instead of picking a specific optimizer, pick a strategy and tune that strategy to each search space encountered. I think this has been answered, but I want to make sure.

Speaking of information gain, I got around to reading Kimura's paper on it about a month ago. It really is an elegant proof.

Under no selection the probability that a new allele goes to fixation is 1/N. If instead, that allele is selected for the probability that it goes to fixation is about 1. Therefore, the "information" gained through selection is equivilent to the uncertianity lost: H(1/N)-H(1) = -log(1/N)/N = log(N)/N. This holds better for larger N.

Reed,

If you present a test function to a search algorithm and it responds with the sequence of values it observed, there are many ways to measure the quality of the sequence. What we consider the search to be doing is a matter of how quality is measured. For instance, in optimization the objective is sometimes to locate the minimum of the function with as few evaluations as possible. The quality measure, then, is the index of the first occurrence of a minimum in the sequence of observed values.

When there is NFL in search, all search algorithms are indistinguishable by all measures of quality, including measures of optimization quality. That is a very strong statement. There are some non-NFL distributions of test functions for which all search algorithms are indistinguishable under some measure of quality.

Now it happens that there is serious misunderstanding of optimization and NFL. Wolpert and Macready make many comments about optimization speed in their 1997 article, but their theorems do not support that. There is no way to look at a sequence of observed values and tell how long it took the search algorithm to generate it. A fast algorithm and a slow one can visit the domain points in the same order, giving the same value sequence. Optimization quality can be a count of function evaluations, as I illustrated above, but optimization speed cannot be made into a quality of the value sequence.

Wolpert and Macready seem to make counts into speed by assuming that the running time of all search algorithms is linearly proportional to the number of function evaluations. But almost all search algorithms running in linear time are too big to exist in the world. Most of those that are impractically large are not functionally equivalent to smaller algorithms (i.e., they are incompressible). Some are functionally equivalent to smaller, slower search algorithms. The slower algorithm not only does the search, but spends time decompressing itself.

Thus there are intrinsically slower search algorithms. This means that counting function evaluations is a bad way to measure time. The NFL reasoning of Wolpert and Macready does not lead to the conclusion that all algorithms have identical average optimization speed. On the contrary, no algorithm has better average optimization speed than blind search, but some have worse. You may get the impression from some of Wolpert and Macready's writing that everything "balances out" but their argument is asymmetric, and is very much geared toward debunking naive beliefs about evolutionary computation.

The situation with NFL and optimization is much more complicated than Dembski seems to have realized.

Under the theorems' assumption of a uniform distribution of problems, an uninformed optimizer is optimal. To be 99.99% sure of getting a solution better than 99.999% of all candidate solutions, it suffices to draw a uniform sample of just 921,029 solutions. Optimization is a benign problem with rare instances that are hard.

— Tom English

I hope critics will drop the averaging complaint. The proof of the main theorem demonstrates identical distributions which have, of course, identical means.

— Tom English

In January 1995, Wolpert and Macready disseminated over the Internet a tech report proving a conservation law for optimizer performance. But they referred to "no free lunch." They knew of Schaffer's work when they prepared their 1997 TEC article, but said nothing of it. They also did not cite any of the NFL work that had been published in the two years following the tech report. Thus most people are unaware that researchers other than Wolpert and Macready did substantive work prior to 1997. I supplied my 1996 paper to Bill Macready, and you will find my sufficient condition for NFL in the 1997 article.

— Tom English

I suppose you have "practical significance" with respect to biological evolution in mind. In nature the fitness function is nonstationary, the search is random, points are revisited, and the domain of fitness functions cannot be defined as a finite set. These are four substantial violations of the suppositions of the original NFL theorems.

— Tom English

Back to the topic: Gene duplication constitutes a violation of one of the assumptions (fixed finite search space) of NFL, and my proof that information is conserved in search goes poof. And that is as things should be, for it is trivial to demonstrate information gain in a population of genomes with gene duplication and divergence.

— Tom English

Under no selection the probability that a new allele goes to fixation is 1/N. If instead, that allele is selected for the probability that it goes to fixation is about 1. Therefore, the "information" gained through selection is equivilent to the uncertianity lost: H(1/N)-H(1) = -log(1/N)/N = log(N)/N. This holds better for larger N.

— Reed A. Cartwright

"Information" in Shannon's sense is always associated with a stochastic variable --- the "information" could take any value depending on which stochastic variable we study, which is why it is important to specify exactly what the "information" is about. Which stochastic variable do you have in mind here?

— Erik

Also, I wonder if you didn't mean to write H(1/N) = log(N) instead of H(1/N) = log(N) / N.

Tom English: you have shed a new light on Wolpert-Macready's paper, and I need some time to digest it. Until now, I had some general idea about the limitations of the NFL theorems, but now you have provided some specifics which I would like to think about. I still think it'd be interesting if you discussed it with David. As to Dembski, there is not much to discuss as he is confused on an elementary level despite his PhD in math. Cheers, Mark

It looks like Igel and Toissant have proven that for the overwhelming majority of fitness functions encountered in the real world the NFL theorems do not hold. Ha! I am really curious what Wolpert thinks about it. I'll ask him. Most of the other links given in the post that started this thread do not work.

The uniform averaging over literally all cost functions works to the critic's advantage, since it makes optimization benign. Nonetheless, we should complain about it, because it is highly unrealistic (and it was not intended to be realistic).

I have not read Schaffer's article, but perhaps it's emphasis is on learning/inference rather than optimization. In any case, Wolpert & Macready also did not cite the previous work by Wolpert in their 1997 article.

Wolpert & Macready's 1997 article contains a NFL theorem for time-dependent cost functions and the domain of a continuous cost function can be binned into, say, 10^100000 bins and replaced by the (finite) set of center points of the bins. The NFL theorem is also not restricted to non-random search. Thus, of the four objections listed, only the revisiting of points is a valid objection (albeit not one I would recommend).

Until now, I had some general idea about the limitations of the NFL theorems, but now you have provided some specifics which I would like to think about.

It looks like Igel and Toissant have proven that for the overwhelming majority of fitness functions encountered in the real world the NFL theorems do not hold.

Unfortunately, "On Classes of Functions for which No Free Lunch Results Hold" proceeds from a false "theorem" that was circulating in the literature, namely that there is NFL for a function distribution if and only if it is uniform on a set of functions closed under permutation (c.u.p.). Their dismissal of NFL hinges on the fact that the number of c.u.p. sets is finite and relatively small. But I had proved in 1996 that the NFL distributions are uncountable. Oops. I doubt there's much to salvage in the paper.

— Tom English

Erik wrote: "Information" in Shannon's sense is always associated with a stochastic variable --- the "information" could take any value depending on which stochastic variable we study, which is why it is important to specify exactly what the "information" is about. Which stochastic variable do you have in mind here? Reed A. Cartwright replied: The probability of the substitution of a new allele.

Erik wrote: "Information" in Shannon's sense is always associated with a stochastic variable --- the "information" could take any value depending on which stochastic variable we study, which is why it is important to specify exactly what the "information" is about. Which stochastic variable do you have in mind here? Reed A. Cartwright replied: The probability of the substitution of a new allele.

Hi to all: While Panda's Thumb was off, I had an exchange of messages with Dave Wolpert. (For the record, the chapter on NFL in the forthcoming anthology from Rutgers was initially planned to be written by somebody recommended by Dave with him as the second co-author. However, those guys he recommended all finked out. Then I volunteered, as the last resort, to save the chapter by writing it myself - with Dave, again, as a co-author. While I was hitting the keybord, Dave decided that he did not wish to appear in the byline, not because of anything he disagreed with in my text, but rather because there was some misunderstanding among the NFL list members (including the anthology's editors) on matters not related to the gist of the chapter. I was left to do it on my own, which I did.

Now, when replying to my questions in regard to Tom English's and Igel & Toissant's ideas, Dave consented to my partially quoting on PT from his replies.

Here is a quote from Dave's reply to my first inquiry:

>>>Are Igel and Toissant the collaborators of Whitley's? As I recall,
their results characterize whether a subset of the set of all fitness
functions obeys NFL exactly. I never saw the significance of those
results; averaged over all subsets *outside* of those they characterize,
you still have NFL.

It's just like the meaninglessness of Kolmogorov complexity
arguments. You still have zero a priori reason to believe that the
"fitness functions encountered in the real world" favor one algorithm
or another.

Tom English doesn't have anything new to add, as I recall.<<<<

MP: And here is a quote from his reply to my second inquiry.

>>>The *subsets* for which NFL exactly holds may well be a tiny fraction
of all *subsets*. (Not of all functions - that's impossible, since NFL
holds for the subset of all functions.)

And so what? What are the implications for real-world learning/search?

If you know ahead of time (!!!) that your search will be over a
particular subset of all functions, then *of course* in general
algorithm A may outperform algorithm B. That's nothing more than a
(dull) special case of our inner product formula.<<<

MP: Of all the above, I construe his remark about distinguishing between "all functions" and "all subsets" as quite enlightening. While Igel/Toissant's theorem about subsets closed under permutation looks sound, the conclusion that only a tiny fraction of functions (in fact, of subsets, which is a very different story) encountered in the real world meet their condition, in the light of Wolpert's explanation, is not that important. I think I have more or less clarified the matter for myself, mostly in favor of Dave's position.

Tom English: although I am not responsible for Wolpert's remarks in your address, I feel embarrassed as they came in response to my inquiry and therefore I apologize (I did not expect such a wording from Dave). In my inquiry I did not give him any opinions on your contribution, so his response is solely his initiative and his opinion. Mark

Mark,

No need for apology. I have worked on NFL from 1995 to the present. Wolpert published the opus magnum in 1997 and turned to other research topics. You perceive him as the authority because he wrote the seminal paper, but I think that's a poor criterion.

Most people love to see others extend their work. Others suffer serious cases of NIH (Not Invented Here). There is a reason you have never managed to get Wolpert to respond favorably to work other than his own. There is a reason you have gotten no coevolution work out of him.

As I suggested above, I have emphasized that conservation (unfortunately renamed "no free lunch") is a matter of degree, and will never be absolute in the real world. One of the major points of my latest paper is that search transforms one probability distribution on the functions into another, and the degree of divergence from a precise NFL distriction is preserved in the transformation. The question of whether there could be precise conservation in the real world has been open since 1995, and I resolved it this year arguing in terms of Kolmogorov complexity.

These things have a way of working themselves out in time. Other researchers and I have recently made great progress in conservation. There will be a lot to emerge over the next couple years. And this may be very disturbing for someone who wants everything to stay put.

Tom. I've tried to work through your paper, but I just can't get it. Is there any way you can state your result in simplified terms? I'm used to thinking of NFL theorems in the form "NFL results hold for function distributions meeting such-and-such conditions". Can your theorem be expressed in this way?

The main problem with using the NFL theorem as an argument against evolution is that there is no obvious cost function. The evolutionary process may be thought of as local optimization of a (changing) function that measures the reproductive success, but this function is not what interests creationists. Creationists are more interested in functions that measure the impressiveness of biological features. Such a function depends on peculiarities of the human mind and is not intrinsic to the evolutionary process.

— Erik

My point with the impossibility of defining a finite domain is that the genome grows through duplication of genes and other phenomena. In NFL the search must visit every point exactly once. So if you say that biological evolution visits every genome in a finite set, you imply that it is possible that it visits one longer than any in the set, a contradiction. Part of the problem here is that we have no reason to believe that biological evolution ever halts.

— Tom English

I agree entirely that there is no obvious fitness function. Some people I respect persist in seeing biological evolution as optimization, but I have trouble seeing optimization in culling of the less fit.

— Tom English

Why can't creationists take the fitness function to be reproductive success, and the performance measure to be increase in functional complexity (in some suitable sense) over a given time (i.e. number of evaluations)? The concept of functional complexity may not be intrinsic to the evolutionary process, but that doesn't mean that creationists can't use it as their performance measure, does it?

— Richard Wein

Tom English: Perhaps my attitude to Wolpert as an authority is indeed partially due to his having published the seminal article. It reminds me though of an old Russian joke. A radio station answers questions from listeners. One listener asks, "Is it true that Tchaikovski was a pederast?" The radio station answers, "Yes, this is true. However, some people also like him for his music." Besides the fact that Wolpert authored a seminal paper, I happen also to like that paper. I believe it is a very good one. Wolpert indeed has lately abandoned the NFL affair. Oddly, in his recent message to me he suggested that, since he is fed up with that matter, perhaps I take over the mantle of the defender of his theorems. This was absurd as I am not at all qualified to do so, so I even did not reply anything to that idea. As to your theorem, unfortunately the link to it did not work when I tried to read your article, so I have no opinion of it while I readily admit it may perhaps affect my view of Wolpert's theorem. Richard Wein seems to have read it and wrote that it is hard to comprehend. I highly respect Wein's intelligence, so, if he has problems with comprehending your paper, I expect to have such problem as well, and therefore I am joining him in the appeal to you to provide, if possible, an explanation of your theorem in terms as simple as possible (although you certainly owe us nothing). Thank you, and best wishes. Mark

The main problem with using the NFL theorem as an argument against evolution is that there is no obvious cost function. The evolutionary process may be thought of as local optimization of a (changing) function that measures the reproductive success, but this function is not what interests creationists. Creationists are more interested in functions that measure the impressiveness of biological features.

— Erik

I find Fig. 1 of Igel and Toussaint's paper "Recent Results on NFL Theorems For Optimization" (arxiv.org/pdf/cs.NE/0303032) useful for illustrating the various elements of the NFL optimization scenario.

— Richard Wein

To apply the NFL theorems to biological evolution I propose that we take as our objective function the reproductive potential of the organism, i.e. how good it is at reproducing. I propose that we take as our performance measure the greatest functional complexity found by the algorithm. I'm using "functional complexity" to mean the sort of complexity which we see in biological organisms and want to explain.

— Richard Wein[/quote

I find this exercise unremarkable and unnecessary. I think it loses all its appeal when we are careful to write "information about X" instead of reifying the concept by calling it merely "information". We don't need to compute entropies in order to arrive at the obvious qualitative conclusion that knowing about selection of an allele gives us information about the fixation of the same allele, nor can I think of a sensible interpretation of the quantitative result that the information about the fixation is log(N)/N, nor is this the kind of process that creationists dispute.

— Erik

Erik wrote: (the performance measure must be a function of only the sequence of the values of the objective function that the search algorithm encounters).
I don't think there is such a limitation insofar as we are discussing the NFL theorems as such (such a limitaion may, though, possibly arise in some specific applications of the NFL theorems). In many optimization scenarios, performance measure can be, for example, simply the number of iterations the search needs to reach a certain pre-selected value of the fitness function (obvioulsy, this particular choice of the performance measure is not very well suited for biological evolution, but Erik's statement seemed to be meant as a general idea for optimization searches). Perhaps also some other possible performance measures can be imagined not meeting Erik's limitation - to state it, a rigosous proof would be needed with exceptions determined. Just $0.02.

Your choice of performance measure c is inconsistent with your choice of objective/cost function f. Note that c(Y) is a function of only Y, which means that the performance measure only depends explicitly on the sequence of objective/cost function values discovered by the search algorithm.

— Erik

Erik wrote: (the performance measure must be a function of only the sequence of the values of the objective function that the search algorithm encounters). I don't think there is such a limitation insofar as we are discussing the NFL theorems as such (such a limitaion may, though, possibly arise in some specific applications of the NFL theorems). In many optimization scenarios, performance measure can be, for example, simply the number of iterations the search needs to reach a certain pre-selected value of the fitness function (obvioulsy, this particular choice of the performance measure is not very well suited for biological evolution, but Erik's statement seemed to be meant as a general idea for optimization searches). Perhaps also some other possible performance measures can be imagined not meeting Erik's limitation - to state it, a rigosous proof would be needed with exceptions determined.

— Mark Perakh

"Under the oracle-based model of computation any measure of the performance of an algorithm after m iterations is a function of the sample d_m^y. Such performance measures will be indicated by Phi(d_m^y). As an example, if we are trying to find a minimum of f, then a reasonable measure of the performance of [the search algorithm] might be the value of the lowest Y value in d_m^y: Phi(d_m^y) = min_i {d_m^y(i): i=1...m}. Note that measures of performance based on factors other than d_m^y (e.g., wall clock time) are outside the scope of our results." Wolpert & Macready (1997), IEEE Trans. Evol. Comp., 1:67-82

Well, Kimura went further in his paper calculating how much "information" would have accumulated since the Cambrian(?), and how much "information" was contained in our genome.

— Reed A. Cartwright

Dear All,

Sorry not to be responding. I am busy at a conference until Wednesday. People filled the room and stood in the doorway for my "No More Lunch" talk. I praised Wolpert and Macready's work, as always.

I met Robert Axelrod yesterday. By chance I had recently developed a minimalistic evolutionary algorithm, with much the flavor of Axelrod's models, to illustrate information gain in a process of random mutation and natural selection. I now believe it has scientific value.

Igel & Toussaint's actual theorem: the NFL result holds for a uniform probability distribution on a set of cost functions if and only if the set of functions is closed under permutation.

— Erik

The No Free Lunch (NFL) theorems--roughly speaking--state that all search algorithms have the save average performance over all possible objective functions...

— Igel & Toussaint

... we have shown that the statement "I'm only interested in a subset F of all possible functions, so the NFL theorems do not apply" is true with probability close to one (if F is chosen uniformly...)

— Igel & Toussaint

Richard Wein wrote: "That's a good point, which completely demolishes my argument. What more can I say?"
Bravo, Richard! You have set an example for all of us. What more can I say? Mark

I've tried to work through your paper, but I just can't get it. Is there any way you can state your result in simplified terms? I'm used to thinking of NFL theorems in the form "NFL results hold for function distributions meeting such-and-such conditions". Can your theorem be expressed in this way?

— Richard Wein

It is not necessary that every point is visited once. What is (formally) necessary is that no point is visited twice or more*, but this leaves the possibility that some points are not visited at all. Note, e.g., that Theorem 1 in Wolpert & Macready's 1997 paper holds for arbitrary m (smaller than the number of search space points), i.e. for samples of arbitrary size. If the theorem required every point to be sampled it would be very trivial and uninteresting!!

— Erik

I'm not sure what you mean by "fitness function" (see my reply to Richard Wein immediately below). I wrote that there no obvious cost/objective function, but there is an obvious quantity subject to (local) optimization: Reproductive success.

Besides the fact that Wolpert authored a seminal paper, I happen also to like that paper. I believe it is a very good one... provide, if possible, an explanation of your theorem in terms as simple as possible (although you certainly owe us nothing).

— Mark

Tom, a challenge: first, to note the obvious: if you can only get the message across to Richard, Mark and Eric you are reaching a rather limited audience. You can do better, and the aim of the challenge is to help.

It is of interest to know how the NFL theorem(s) apply, or not, to empirical biological situations. And, sorry to bring this up, it can be difficult to be empirical and uncountable at the same time. So as step 0 of the challenge (this may be the most wrenching part for you :)) I ask you to come down from the continuum, down even from countable, down, down to a number like three or two. Three would be fine although we'll have to add 1 later on.

The challenge is to work a concrete example.

Suppose we have a population of land snails with three phenotypes, let's say three color morphs: light pink, brown, and striped. Let's say the fitnesses of the morphs are 1.1, 1.0 and 0.9 respectively.

The objective is to give the details of a scenario that is both life like and NFL like, that is, the conditions of NFL are satisfied. If this can be done, fine. If not, why not? To make the answer clear, give two scenarios, one life like and the other NFL like.

You have to fill in the blanks from here on:
We need a set of functions. What are they?
The set must be closed under permutations. What permutations? Do the permutations involve associating each of the morphs with each of the fitnesses?
We need a performance measure. What is it?

To go further you may need to consider a mutation that gives us green snails.

Explain the situation(s) with respect to classic NFL, that is, performance of evolution vs blind search.
Explain the situation(s) with respect to your NFL as conservation theorems: what, concretely, is conserved or not in which case?

If for any reason you are not able to work with so simple an example, come as close as possible.
And if you are willing to humor me on this, thanks very much!

Pete

-
"If you can't explain it to the cleaning lady, you don't understand it yourself".

Pete Dunkelberg, this isn't the realistic example you are seeking, but it is a concrete (if purely fictional) story:

Let me tell you about the intergalactic pet store Unipet's latest business concept: Make-a-pet. The customers of Unipet, coming from all over the universe, have a truly diverse set of preferences and it is difficult to keep a stockroom of pets so that they have something for everyone. For instance, the Beheians would never consider buying any pet that isn't "irreducibly complex". Other customers would never consider buying a pet that is "irreducibly complex". Unipet's strategic surveys and polls show that the number of customer profiles needed to accurately capture all customers is gigantic. Hence the need for Make-a-pet.

The idea behind Make-a-pet is that a pet is tailor-made based on the preferences of each individual customer. Since it is just impossible to learn even a fraction of all languages in the universe well enough to discuss the customer's rather involved preferences, the communication between the customers and the pet engineers is very crude: The pet engineers will show a pet and the customer will simply rate it by holding up a sign with a digit between 0 and 9 on it. (This customer-rating is the objective function.) Based on all previous ratings by the customer, the pet engineers will construct a new pet that hopefully receives a higher rating by the customer, and so on. (The strategy used by the pet engineers to construct new pets based on the customer's ratings of previously constructed pets is the search algorithm. The fact that the customer rating is the only communication between the customer and the pet engineers makes the search algorithm a "black-box" algorithm.) It goes without saying that the most expensive part of this process is the production of new pets, and it is desirable to minimize the number of pets that need to be produced before one with satisfactorily high customer-rating is discovered. But with Unipet's rather advanced technology, the company's experts reasoned that producing pets still beats having a storeroom with a gigantic zoo of pets.

Make-a-pet was neither a stellar success nor a miserable failure. The most remarkable thing about the Make-a-pet project was that it didn't seem to matter which strategy the pet engineers used. They tried hiring the best statisticians in the universe to infer the preferences of individual customers based on their ratings. They tried ignoring the previous ratings by the customer altogether and just follow a fixed sequence of pets. They tried making pets at random. They tried having a population of pets that was allowed to evolve by differential reproductive success without outside intervention, and picking pets at random from this naturally evolving population. (This is how biological evolution comes in. Letting pets evolve in an unconstrained fashion is just one search strategy among zillions of others.) No matter which strategy the pet engineers used, it turned out that, when averaged over a large number of customers, the number of pets that needed to be produced before one with a satisfactorily high customer rating was discovered was the same for all strategies. The best statisticians in the universe performed no better than a random number generator. (This is the NFL theorem.)

When Unipet's statisticians discovered this fact they started thinking about what must be true about the distribution of customer preferences. Theoretically, the preferences of a customer can be represented as a list of pairs between possible pets and ratings between 0 and 9. For instance, such a list could begin with

(giraffe, 0), (cat, 7), (rabbit, 6), (ill-tempered sea-bass, 2), ...

By swapping the scores of two or more pets in such a list, a new list can be created. For instance, swapping the scores of the rabbit and the ill-tempered sea-bass gives the list

(giraffe, 0), (cat, 7), (rabbit, 2), (ill-tempered sea-bass, 6), ...

The criterion for when the strategy used by the pet engineers makes no difference for the average performance is that: All preference lists that can be transformed into each other by swapping scores in the above manner must be equally probable. Preference lists which cannot be transformed into each other in the above manner may have different probabilities, though. (Tom English refers to such probability distributions as "block-uniform", with the blocks being sets of preference lists that can be transformed into other by swapping scores.)

If Unipet doesn't give up on the Make-a-pet project first, the company statisticians may refine the analysis in the future, taking into account that some pets are more expensive to produce than others. When nothing is known about the customer's preferences it makes sense to try the possibilities that are cheap to produce first. Such factors are presently beyond the scope of the analysis, though.