Evolution and the NFL theorems

_{Mark

December 30, 2007

Intelligent Design}

Share: Facebook; Twitter; LinkedIn; Flipboard; Print; Email

Ronald Meester CLICK HERE FOR THE PAPER Department of Mathematics, VU-University Amsterdam,

“William Dembski (2002) claimed that the NoFreeLunch-theorems from op-
timization theory render Darwinian biological evolution impossible. I
argue that the NFL-theorems should be interpreted not in the sense that the models can be used to draw any conclusion about the real biological evolution (and certainly not about any design inference), but in the sense that it allows us to interpret computer simulations of evolutionary processes. I will argue that we learn very little, if anything at all, about biological evolution from simulations. This position is in stark contrast with certain claims in the literature.”

This paper is wonderful! Will it be published? It vindicates what Prof Dembski has been saying all the time whilst sounding like it does not.

“This does not imply that I defend ID in any way; I would like to emphasise this from the outset.”

I love the main useful quote it is a gem!

“I will argue now that simulations of evolutionary processes only demonstrate good programming skills – not much more. In particular, simulations add very little, if anything at all, to our understanding of “real” evolutionary processes.”

“If one wants to argue that there need not be any design in nature, then it is hardly convincing that one argues by showing how a well-designed algorithm behaves as real life is supposed to do.”

Comments

I have to correct my correction in #179. With the clustering I impose, G (or, more properly V) essentially remains a uniform distribution over genome space, and, as I state in #178, once the fitness function is applied, S, remains essentially a uniform distribution with the fitness value being zero over the entire set. As I stated before, the Dirac delta function can be applied. Simply gather all of the "clusters" of the 100 trillion genomes that have "high fitness", i.e., at or extremely close to 1, into one point. Instead of taking the distribution over an interval, take it over that one point. In the real world, genomes that function can be thought of as "spectral lines", to borrow an analogy from physics. Just as spectral lines just are, so too, fit genomes just are.PaV_{January 4, 2008
January
01
Jan
4
04
2008
07:03 PM
7
07
03
PM
PDT}

Semiotic #177: "NFL Theoerms 1 and 2 of Wolpert and Macready (1997) implicitly assume uniform distributions on spaces of all possible functions (static and time-varying, respectively), not a uniform distribution on the search space (here, the space of all possible genomes)." The confusion comes a little bit from Haggstrom. He uses the sets V and S in two different ways. The first way he uses them is to generate the set of all genomes being generated from V, the set of nucleotides, and S, some subset of R, which is, in the case he uses, 3 billion. Later on, he uses V as the set of all genomes so generated and applies a fitness function to generate S, the set of all fitnesses of human genomes. In my post at #175, G should not be the space of all genomes, but S, the space of all genome fitnesses given the function f. But with that correction, I believe the argument still stands.PaV_{January 4, 2008
January
01
Jan
4
04
2008
06:39 PM
6
06
39
PM
PDT}

perlopp #176: "You confuse uniform distribution over the genome space with uniform distribution over the space of fitness functions." The conditions I impose on S render the set S 'essentially' a uniform distribution with the value of all the f(x)'s being zero. The NFLT apply.PaV_{January 4, 2008
January
01
Jan
4
04
2008
06:23 PM
6
06
23
PM
PDT}

Sorry, I meant PaV(175), not (171). Anyway, my comment regarding PaV's confusion was corroborated by Semiotic(177).perlopp_{January 4, 2008
January
01
Jan
4
04
2008
05:40 PM
5
05
40
PM
PDT}

Pav (175):
You can’t argue that the “clustering” I propose has in any significant way changed the uniform distribution of G, the space of all possible genomes.
NFL Theoerms 1 and 2 of Wolpert and Macready (1997) implicitly assume uniform distributions on spaces of all possible functions (static and time-varying, respectively), not a uniform distribution on the search space (here, the space of all possible genomes). My best guess as to the source of your confusion is that Dr. Dembski often predicates that the search target is distributed uniformly on the search space. That's not equivalent to the assumption of a uniform distribution on functions with the search space (genomes) as their domain. Does that make sense to you? I did in fact argue in 159, in which I blur the "trees" in an attempt to make the "forest" visible, that if function f is drawn uniformly from the set of all functions from genomes to fitness values, then f is almost certainly algorithmically random. If you imposed a topology on the space of genomes prior to drawing f, then the fitness landscape is almost certainly disorderly in the extreme. If you can find order in f, then the orderliness you have observed generally can be exploited in algorithm to compress f. But then f is not algorithmically random (by definition). As I said before, when you say that you expect to see regularities in randomly drawn functions, you are saying the random distribution is not uniform. If you define or transform the topology of the space of genomes to obtain regularity after drawing f, then you are, loosely speaking, adding information.Semiotic 007_{January 4, 2008
January
01
Jan
4
04
2008
01:38 PM
1
01
38
PM
PDT}

PaV(171), You confuse uniform distribution over the genome space with uniform distribution over the space of fitness functions. It is the latter that is relevant to the NFL Theorem. Double fault. Game Haggstrom. New balls.perlopp_{January 4, 2008
January
01
Jan
4
04
2008
01:01 PM
1
01
01
PM
PDT}

Here is the critical passage from Haggstrom’s paper: Thus—and since fitness landscapes produced by (7) are extremely unlikely to exhibit any significant amount of clustering—we can safely rule out (7) in favor of fitness landscapes exhibiting clustering, thereby demonstrating the irrelevance of Dembski’s NFL-based approach. Note in this context that it is to a large extent clustering properties that make local search algorithms (such as A) work better than, say, blind search: the gain of moving from an x , an element of V, to a neighbor y with a higher value of f is not so much this high value itself, as the prospect that this will lead the way to regions in V with higher values of f. (p.13) If we’re going to argue, then let’s argue about this. His critical remark is that a genome one mutation away from a genome of high fitness will, on average, be zero; hence, no “clustering.” In the paragraph right above where the quoted remark is taken, Hoggstrom says that no one would believe that a ‘fitness landscape’ wherein a genome one step away, or one mutation, away from a high fitness genome would have a fitness of zero since this would mean, e.g., that a human genome that experienced one mutation somewhere along its length would not be capable of producing life. Yet that is what the ‘independent’ distribution of NFLT seems to imply. Thus, realistic fitness functions can have nothing to do with a uniform distribution and NFLT. I think Haggstrom is wrong, and for the following reason: Let’s start with the space of all possible genomes. That space has cardinality 4^3,000,000,000 per Haggstrom. Let’s just round it off to 10^1,000,000,000 elements. This is roughly the space of all permutations of length 3,000,000,000 nucleotides. In Nature, there are how many species? A trillion. Ten trillion. Let’s take a hundred million, for arguments’ sake. And let’s say that each one of these “high fitness”(=“life”) genomes has a trillion similar permutations that are also “high fitness” (= “life”). We know that all of these genomes exist in the genome space above. Haggstrom would tell us, however, that none of these genomes are next to one another in genome space; therefore it’s not a realistic comparison. Well I propose to make it realistic. How shall we do that? By “clustering” each of the trillion viable genomic permutations around each of the 100 trillion living genomes. If we mentally try to visualize what’s going on, we can look down on a sea of two-dimensional space. At each location, that is, each point, of this two-dimensional space we find a permutation of a 3,000,000,000 long genome. As we look down onto this 2D space, these 100 trillion “high fitness” genomes, along with each of their trillion “high fitness” permutations, are randomly dispersed on this plane. What we’re going to do is to “pull together” all of these trillion of “high fitness” permutations to form a cluster. (After all, they’re ‘independent’ of one another) We end up with 100 million clusters, consisting of one trillion permutations. We could have, admittedly, “clustered” all 10^25 (100 trillion x one trillion) together. But, if we were to do a blind search for just that one cluster, it would be much harder to find than having 100 trillion “clusters” (of a trillion permutations) throughout the space of all possible genomes. Now in this configuration of genome space we have “clustering”; in fact, we have it to a staggering degree: viz., one trillion viable permutations per genome. So, if the human genome were to experience a mutation anywhere along its length, the likelihood of it not being viable would be 1 in a trillion. So, again, we have the space of all possible genomes within which are to be found, randomly (again, giving the best possibility of being found by search), 100 trillion “clusters” of a trillion permutations. Once we’ve pulled all these permutations together and formed 100 trillion “clusters” of a trillion permutations each, then the space, G, of all possible genomes is smaller by roughly 10^25 genomes. But 10^25 represents 1/4,000,000,000 of G, leaving G essentially unaffected in size. Now, what we have left is a uniform distribution of size 10^1,000,000,000 among which are to be found generously realistic “clusters” of genomes for every living being imaginable. The odds of hitting the target, that is, any one of the 100 trillion “clusters” of genome permutations, through blind search is 10^25/10^1,000,000,000= 1 in 10^4,000,000. You can’t argue that the “clustering” I propose has in any significant way changed the uniform distribution of G, the space of all possible genomes. Nature must navigate this way using, per Haggstrom, Darwin’s algorithm A (reproduction-mutation-selection) to find its way through this uniform distribution. But since it is a uniform distribution, we know that it’s no better than ‘blind search’, and we know that G is to Vast for blind search to work. This is where the Explanatory Filter, that Dembski describes, would tell us that since randomness cannot explain the “discovery” of living genomes, then design is involved.PaV_{January 4, 2008
January
01
Jan
4
04
2008
12:02 PM
12
12
02
PM
PDT}

Oops.
If p(f) is the probability that a human will refer to function f, ...
I should have said explicitly describe instead of refer to. I can refer to functions with no physical realization, but if I explicitly describe a function, the description is a physical realization. To make the notion of explicit description concrete, think in terms of writing a program that computes the function.Semiotic 007_{January 4, 2008
January
01
Jan
4
04
2008
10:45 AM
10
10
45
AM
PDT}

Michaels7 (170):
Finally, what does it say in any relation to NFL?
Nothing. What are your impressions of Meester's paper?
NFL is just one aspect in an ID world.
The field of evolutionary informatics, which Marks and Dembski are committed to exploring, has its origin in NFL. Dr. Dembski has given a lot of attention to simulation of evolution. Thus the topics of this thread are worthwhile.Semiotic 007_{January 4, 2008
January
01
Jan
4
04
2008
10:29 AM
10
10
29
AM
PDT}

kairos (169):
The problem is: provided that in every real search we cannot do more than, say, 10^80 iterations, what’s the sense in discarding my example on the base of differences in P’s that could never be effective in the real world?
Sorry, but I don't understand what you're asking.Semiotic 007_{January 4, 2008
January
01
Jan
4
04
2008
09:53 AM
9
09
53
AM
PDT}

kairos,
I and T did specify in their paper that no situation for NFL would arise in the real world
Thanks very much for telling me that. They devote just a few sentences to the observation, and I had no recollection it. At the end of A No-Free-Lunch Theorem for Non-Uniform Distributions of Target Functions, Igel and Toussaint write,
The probability that a randomly chosen distribution over the set of objective functions fulfills the preconditions of theorem 5 has measure zero. This means that in this general and realistic scenario the probability that the conditions for a NFL-result hold vanishes. [...] It turns out that in this generalized scenario, the necessary conditions for NFL-results can not be expected to be fulflled.
This is all they say on the matter. It's a clever and concise argument against "NFL in the world," but I'm not sure of the logic of supposing that the probability distribution on functions is itself random. I'd be interested to hear what Dr. Dembski makes of this double stochasticity. Even if you buy the reasoning of Igel and Toussaint, their conclusion is not really the end of the story. Despite the all-or-nothing sound of "no free lunch," NFL is a matter of degree. There are distributions on functions for which algorithms differ at most slightly in their distributions on performance values. English works this out in excruciating mathematical detail in another of the papers of 2004 that prove the necessary and sufficient condition, No More Lunch: Analysis of Sequential Search. The mass of equations makes me want to vomit, but figures 1, 3, and 4 are the only graphical depiction of generalized NFL I have seen. (They illustrate something Marks and Dembski emphasize, namely that a search algorithm "shuffles" the function.) English emphasizes that most functions have exorbitant Kolmogorov complexity -- an observation complementary to that of Igel and Toussaint. If p(f) is the probability that a human will refer to function f, I can give a persuasive argument (not really a proof, because no one knows much about p) that the distribution p is not even approximately one for which there is NFL. The gist is that there are common f for which almost all f o j cannot arise in practice. The situation is messier with fitness functions "in" biological evolution, because they are hypothetical constructs.Semiotic 007_{January 4, 2008
January
01
Jan
4
04
2008
09:41 AM
9
09
41
AM
PDT}

I am curious how recent research CTC Code relate to this discussion. Including latest research there are three independent codes with DNA, Histone and CTC. How many more patterns will be found that are not currently in evolutionary models? And how do these models account for such non-trivial repeats. Does this favor a telic or non/telic process? Finally, what does it say in any relation to NFL? Kairos, Your note about computational process I think must be acknowleged. NFL is just one aspect in an ID world. Error checking cannot be accounted for by blind evolutionary processes. Life appears with computational design characteristics of logical and/ors, that conserve core processes, but allow variation on the edges. And I always thought of compression algorithms as a sign of intelligent input. From Science daily...
But what was the development that permitted this advance in gene usage? The RNA polymerase II has developed a structure composed of repeats of a 7 amino-acid sequence. In humans this structure – termed “carboxyterminal domain” or CTD – is composed of 52 such repeats. It is placed exactly at the position where RNA emerges from RNA polymerase II. In less complex organisms the CTD is much shorter: a worm has 36 repeats, and yeast as few as 26, but many single-cell organisms and bacteria have never developed an obvious CTD structure.
reference link: http://www.sciencedaily.com/releases/2007/12/071214094106.htm It appears the "mechanisms" of life are arrived at by conditional logic and precise placements thru a core of patterned "meta-codes" that interact and/or overlay each other depending on developmental sequences, functional purpose, and conditional error processing. Can these be considered layers of Meta-codes? If it is a code, then life can be unlocked. Original papers... TRANSCRIPTION: Seven Ups the Code Jeffry L. Corden http://www.sciencemag.org/cgi/content/summary/318/5857/1735 hattip: creationsafaris.com Metacodes of Life, sounds like a very good project, or book title. Newton believed he would find order in the Cosmos and the solar system. Now, ID must focus on order within. I personally think a greater focus of ID research can be in unraveling similar structures like Histone and CTD. I think this is just the beginning. The very tip of knowledge unfolding on what will be found layers of significant grand orders, not "illusions."Michaels7_{January 4, 2008
January
01
Jan
4
04
2008
08:14 AM
8
08
14
AM
PDT}

#159 Semiotic "The necessary and sufficient condition for NFL did not appear until 2004. But now that we have it, ad hoc arguments like kairos’ in 125 are inappropriate. If you want to establish that there is no free lunch, then you must prove that p(f) = p(f o j) for all fitness functions f and for all permutations j of the domain of fitness functions (space of genotypes)." But you know that in this sense no NFL should be present in the real world (I and T did specify in their paper that no situation for NFL would arise in the real world). The problem is: provided that in every real search we cannot do more than, say, 10^80 iterations, what's the sense in discarding my example on the base of differences in P's that could never be effective in the real world?kairos_{January 4, 2008
January
01
Jan
4
04
2008
03:41 AM
3
03
41
AM
PDT}

#151 perlopp "From Wikipedia: While chronos is quantitative, kairos has a qualitative nature" Good joke; but it's inappropriate here. It's me who have noticed that your argument about p^2 and p/k lacks any quantitative meaning in the real world ;-)kairos_{January 4, 2008
January
01
Jan
4
04
2008
02:48 AM
2
02
48
AM
PDT}

j (117):
It would be a simulation of Darwinian (nonteleological) evolution only if the “behavioral error” is assessed using a criterion that has been evolved nonteleologically (without any kind of built-in goal).
A fitness function merely says how good individuals are. The function may be obtained by measurements of physical individuals, and it should be clear in such a case that the measurements are in no way determined by human purpose. When a human encodes a function and supplies it as input to an implementation of an evolutionary algorithm, the teleos of the human does not infect the function. I have been on the merry-go-round with this issue before, so allow me to take a radically different tack: I recently used two methods to randomly generate many highly compressible functions. Random search consistently outperformed simple enumeration of candidate solutions, and a (1+1)-EA [evolutionary algorithm] consistently outperformed random search. The only teleology here is that I tried to make the distribution of functions uniform on a set of highly-compressible functions. I can't prove that I succeeded, but there is no doubt about my goal. Success in function optimization requires nothing like "teleological" functions.Semiotic 007_{January 3, 2008
January
01
Jan
3
03
2008
11:55 PM
11
11
55
PM
PDT}

Please note my comments at 162 and following that spent some time "awaiting moderation." j @ 164: I'm pleased to connect on the matter of competition. Sorry to miss 117. It's hard to keep up with this thread. Certainly Atmar takes the neo-Darwinian paradigm as given. I did not intend for the article to serve as justification of the paradigm, but to provide a more sophisticated view of simulation of evolution. The unfortunate aspect of the example is that it has an engineering, rather than biological, slant. The thing I hoped Atmar would make clear is that we can put abstract evolutionary principles to test without simulating biological organisms. If memory serves, he indeed emphasizes the principles, as opposed to the implementation details.Semiotic 007_{January 3, 2008
January
01
Jan
3
03
2008
10:31 PM
10
10
31
PM
PDT}

Atom (152):
In the 1997 paper, the authors also repeatedly claim that problem specific information must be included and utilized in the search, or else the resulting performance is the same as random search. This, they say, is how algorithms can do better than random search (by utilizing knowledge of the search space) which backs up Dembski/Marks’ work on active information as well as Meester’s claims.
But in 2000 we learned that almost all functions are algorithmically random, and that random search almost always locates a good value rapidly: Optimization Is Easy and Learning Is Hard in the Typical Function. There is no way to obtain information about a given algorithmically-random function without searching the function. And what kind of "design" procedure depends upon performing the task for which an algorithm is being designed? Algorithm design is futile in the face of randomness. But random search is effective when the function is algorithmically random. The first result along these lines (developed without the notion of algorithmic randomness) appeared in 1996. Wolpert and Macready knew about it, but never mentioned it, perhaps because it challenged their exposition of the NFL theorems. The 1997 NFL results of Wolpert and Macready are of theoretical importance, but they don't characterize search in the physical world, where functions are usually algorithmically-compressible in the extreme (far from algorithmically random). I don't think anyone knows whether some algorithm is generally superior to others in optimization of highly- compressible functions. If it should turn out that random search is not the "average" search, as it is in theory, then Marks and Dembski's definitions of intrinsic, extrinsic, and active information in terms of random search perhaps will not make the sense they do now. My current research suggests that you might want to save your stone tablets.Semiotic 007_{January 3, 2008
January
01
Jan
3
03
2008
08:50 PM
8
08
50
PM
PDT}

(For the record:) A correction: Above (117) I wrote,
the term “competition” — the word I say can only be a metaphor in Darwinian usage — isn’t defined [in the Atmar paper].
Actually, I suppose he can be considered to have defined it implicitly -- in one of the example quotes I gave, no less:
[T]he best...are retained to reproduce in the next generation...and ultimately the competitive exclusion of the least appropriate (”least fit”) is assured.
Thus, according to Atmar, "competition" is equivalent to "being successively retained", i.e., undergoing the process of 'natural selection'. So, again: "[T]echnically, there is no competition in Darwinian theory... [It's use] can only be considered metaphorical... (Thanks, Semiotic 007.) __________ metaphor - a figure of speech in which a word or phrase literally denoting one kind of object or idea is used in place of another to suggest a likeness or analogy between them (Merriam-Webster)j_{January 3, 2008
January
01
Jan
3
03
2008
07:28 PM
7
07
28
PM
PDT}

Atom, perlopp, and others, You have to be careful when you talk about the "search space structure" and the "fitness landscape." In Wolpert and Macready's NFL framework, there is no topology associated with the search space -- not even an adjacency relation. A search algorithm may associate topology with the search space. (We humans must do just that to speak of the fitness landscape.) This is a form of prior information (perhaps misinformation) about the search problem. The "fitness landscape" is not really an NFL concept, and I mentioned it above only because people here seem to find it intuitive. A search algorithm is not given information on the structure of the search space as an input. Any such information must be embedded in the search algorithm itself. It amounts to prior belief about "what kind" of functions will be input.Semiotic 007_{January 3, 2008
January
01
Jan
3
03
2008
06:30 PM
6
06
30
PM
PDT}

I'd like to add that you definitely should expect coherence (structure, regularity) in the fitness landscapes of models of biological evolution, because algorithmically-random fitness functions cannot arise in physical reality. Those functions "contain" more information than the observable universe can "hold." That is, only for unrealistically small genomes do algorithmically-random fitness functions require less than 10^90 bits (Seth Lloyd's bound on the information storage capacity of the observable universe, not taking gravitational degrees of freedom into account) to encode. Let's say we have a uniform distribution on fitness functions that are "simple" enough (low enough in Kolmogorov complexity) for physical realization. Assume that the necessary and sufficient condition for NFL is not satisfied. As pointed out above, "not NFL" does not mean "free lunch in optimization." Whether some algorithm is generally superior in optimization performance to another under the distribution I described is, to my knowledge, an open question.Semiotic 007_{January 3, 2008
January
01
Jan
3
03
2008
05:32 PM
5
05
32
PM
PDT}

Atom(156), But why the nice correspondence of algorithm choice to search space structure? Way outside my field of expertise, but it is the way it works isn't it? There are no "choices" of algorithms, targets, or fitness functions. The malaria parasite that PaV talks about acquired resistance by mutation and reproduction. What other choices did it have? As far as I know, nobody claims that Intelligent Design was needed for resistance to develop. Rather than asking "why" one may ask "why not"? Again, you must be careful in applying the "second view" of NFL as there are additional assumptions regarding algorithms and samples. Not as clean-cut as "first view" NFL.perlopp_{January 3, 2008
January
01
Jan
3
03
2008
05:02 PM
5
05
02
PM
PDT}

PaV(154), A. What does the following mean? the ‘fitness function’ of that genome, at that particular point within all of genome space, per my calculation, is 1 to the 10^-155. What is your fitness function? Why is it low when it ought to be high? The two a.a. changes you mention are beneficial, thus increasing fitness, whatever it may be. B. Design must be inferred per the Explanatory Filter ????? C. “Game. Set. Match.” Doubt it. More like "Advantage Haggstrom"perlopp_{January 3, 2008
January
01
Jan
3
03
2008
04:47 PM
4
04
47
PM
PDT}

Dembski (2002) had nothing to say about NFL results other than those in W&M (1997). (Dembski made the same mistake that Meester did -- he did not survey the NFL literature. He gives evidence in recent papers of knowing a great deal more about NFL than he did in 2002.) Everyone should keep in mind that Haagstrom is criticizing Dembski's (2002) argument. Some of you are introducing your own ideas about NFL and arguing as though Dembski availed himself of them in 2002. Haagstrom is criticizing what Dembski said in 2002, not what he might say now, and not what you have to say now. If you model biological evolution in terms of a time-varying function from genotypes to fitness values, then Wolpert and Macready's (1997) Theorem 2 is possibly applicable, but not Theorem 1, which applies to static functions. (Does anybody here want to say that what constitutes fitness does not change as the environment changes?) Theorem 2 effectively assumes that the fitness function at time t "predicts nothing" about the fitness function at time t+1. That is, the fitness "landscape" is entirely "made over" at each time step. If the fitness landscape in your model of biological evolution generally does not change catastrophically (in the sense of catastrophism) from one time to the next, then Theorem 2 does not apply. You might choose to model evolution over an interval in which adaptive pressures change little -- I'm not sure of the biological relevance, but I'll allow the possibility. To apply Wolpert and Macready's (1997) Theorem 1, you would have to say that any fitness function is as likely as any other, and this is to say that the fitness function is almost certainly, though not certainly, algorithmically random (or very nearly so). That is, you would have to accept implicitly that the fitness landscape is almost certainly as jagged and incoherent (nearly everywhere) as you can imagine. Everyone modeling biological evolution believes that there is usually some sort of coherence in the fitness landscape -- people speak of plateaus, slopes, ridges, etc. If you expect to see features like those, then you do not believe that the assumptions of Theorem 1 are satisfied. The necessary and sufficient condition for NFL did not appear until 2004. But now that we have it, ad hoc arguments like kairos' in 125 are inappropriate. If you want to establish that there is no free lunch, then you must prove that p(f) = p(f o j) for all fitness functions f and for all permutations j of the domain of fitness functions (space of genotypes). This was established by two different proofs in three papers that passed independent peer reviews. In other words, there is no wiggle room. My comments are being held for moderation, so forgive me for overloading this one. A major reason much of what I say about NFL seems alien is that Wolpert and Macready, the authorities, never cited anyone else's work on NFL until 2005 -- and then it was at the behest of a reviewer. People often explore the literature by chaining backwards through the reference lists of papers. Since 2005, references to NFL publications other than Wolpert and Macready's have increased dramatically in number. Some important NFL results from years ago are only now gaining attention.Semiotic 007_{January 3, 2008
January
01
Jan
3
03
2008
04:36 PM
4
04
36
PM
PDT}

without that knowledge, you’re just as well off using any algorithm or random blind search. But with that information, you can find any word in log_2(N) tries (rather than N/2, on average, tries.)
Clarification: I do not mean that all algorithms will work equally well on this search space (I already hinted that binary search works incredibly well); rather, I mean that if you choose an algorithm randomly, on average, you are likely to acheive close to random performance by your choice.Atom_{January 3, 2008
January
01
Jan
3
03
2008
04:33 PM
4
04
33
PM
PDT}

PS by "nice correspondence", I mean lucky, fortuitous, and (obviously) well-suitedAtom_{January 3, 2008
January
01
Jan
3
03
2008
04:29 PM
4
04
29
PM
PDT}

Thanks perlopp. I only have one more comment for right now. You wrote:
But regardless of what the most general assumptions are, they cannot cover situations with the type of clustering you see in our biological applications; obviously nearest-neighbor type searches there beat blind search
I agree that clustering occurs in the search space of genomes (as Haggstrom's point on neutral mutations shows) and that local neighborhood hill-climbing algorithms are the correct choice for this structure. But why the nice correspondence of algorithm choice to search space structure? Since if we choose randomly a given algorithm for this search space, on average, we're just as likely to choose a poorly suited algorithm (less efficient than random search) as we are a well suited algorithm (more efficient). If we know nothing about this clustering, then we're likely to achieve rougly random search efficiency, since we do not take any advantage of this extra information. It is like trying to locate a word in a dictionary without knowing that the words are ordered alphabetically; without that knowledge, you're just as well off using any algorithm or random blind search. But with that information, you can find any word in log_2(N) tries (rather than N/2, on average, tries.) This is the point I make about needing extra information to narrow your choice of search algorithms for a given space. From my reading, Wolpert/Macready make this same point. It is also the point that Meester makes in why programmers using that information cannot be said to be models of dumb sheer luck, and how Marks/Dembski begin to quantify their Active Information. Your thoughts are welcomed.Atom_{January 3, 2008
January
01
Jan
3
03
2008
04:28 PM
4
04
28
PM
PDT}

Atom(152), A nice summary that I think adequately describes the arguments by Haggstrom and that I agree with. There is no claim that uniformity is ESSENTIAL, but it is the assumption of the theorem so for now that's what we have (I'll check out Semiotic's reference when I find the time). But regardless of what the most general assumptions are, they cannot cover situations with the type of clustering you see in our biological applications; obviously nearest-neighbor type searches there beat blind search. When you read W&M, the theorem is not stated explicitly assuming a uniform distribution but the result regarding equality of the two sums can be interpreted in that way and Haggstrom's probabilistic proof of NFLT is very illustrative. I don't know if Dr Dembski has realized this connection before. As for the "second view," W&M point out that the theorem in that setting is "less sweeping" which is certainly true if you look at it. If you want to apply it, you'd have to be very careful with details. This version also has a uniformity assumption, this time over the set of algorithms. Again, I think the application to biology is flawed as we can't choose algorithm randomly but are restricted to the Darwinian process of mutation etc. I think Haggstrom makes it perfectly clear that the uniformity assumption is fatally flawed but I'll be glad to hear counterarguments.perlopp_{January 3, 2008
January
01
Jan
3
03
2008
04:15 PM
4
04
15
PM
PDT}

PaV(153), 1. The question is if you think the uniformity assumption applies to the biological problems we are discussing here.perlopp_{January 3, 2008
January
01
Jan
3
03
2008
03:40 PM
3
03
40
PM
PDT}

perlopp #137: As to 1: That's how the NFL theorem is defined. As you say, it's one of the assumptions. So, no, I don't have a problem with the function used in the NFL having a uniform distribution. (Now I'm understanding a uniform distribution as a probability distribution having N elements of equal probability, the sum of which is 1 over the length of the discrete interval the sum of the N elements is taken over.) 2. I'm not talking about the malarial parasite doing a 'blind search' over the entire genome space of all organisms. Rather, I'm confining myself to the structure of its surrounding 'fitness space'. This space is searched for in a blind, that is, random fashion. Now whether that search has been conducted long enough to find a satisfactory target is irrelevant. What is relevant is that the search so conducted by the malarial parasite, is more thorough than the vast majority of animal species has ever conducted. The result of that search was that it could increase its fitness relative to chloroquine only through two a.a.s of one protein being changed. Thus the 'fitness function' of that genome, at that particular point within all of genome space, per my calculation, is 1 to the 10^-155. It's almost zero; but not zero. However, if you went three a.a.s away from the malarial parasites' genome, the 'fitness function' there would be, indeed, zero. Ascertaining this, given what Haggstrom says in his footnote #11, validates Dembski's use of the NFLT. This means that one CANNOT traverse genome space via 'blind search'. Darwinism is thus refuted. Design must be inferred per the Explanatory Filter. "Game. Set. Match."PaV_{January 3, 2008
January
01
Jan
3
03
2008
03:00 PM
3
03
00
PM
PDT}

All, Here is my understanding of the argument so far. Haggstrom, and those on here following his example (Semi 007, perlopp), seem to argue that: 1) the uniform distribution of P(f) is ESSENTIAL to the NFL theorems. (Without uniformity of P(f), the theorems do not hold.) 2) Biological fitness functions pertaining to any given organism are not distributed uniformly. Therefore 3) the NFL theorems do not apply to biology. If this is a straw-man, please forgive me, and present an equally simple presentation of your argument. (If that is the case, then please disregard what follows.) Now, it seems that Haggstrom and the others are only focusing on one aspect of the NFL theorems: one algorithm over the set of all optimization problems (F), distributed by P(f). There is also a second way in which they hold, namely, on one problem over the set of all algorithms (see Macready Wolpert 1997 and referenced paper [5] from that paper.) I'd lke to see this second view addressed as well. From my initial reading of (1997), it does not seem that the uniformity assumption is all that critical. The authors themsleves say in the paper that the uniform P(f) is only given as way of an example, but that it is not a pathological (unusual) case. I have only read the paper once and haven't worked through the mathematics yet, so I'm going from my initial (albeit recent) reading. In the 1997 paper, the authors also repeatedly claim that problem specific information must be included and utilized in the search, or else the resulting performance is the same as random search. This, they say, is how algorithms can do better than random search (by utilizing knowledge of the search space) which backs up Dembski/Marks' work on active information as well as Meester's claims. As I said, I still have a few papers to read and work through the relevant maths, so until then, I'll keep my comments light. I love the discussion, however. Perhaps Dr. Dembski can take a few minutes to chime in as to why the uniformity issue is not a fatal flaw to biological application? (He never seems to comment on the really interesting threads, but I'm sure everyone would benefit from his take.) AtomAtom_{January 3, 2008
January
01
Jan
3
03
2008
02:59 PM
2
02
59
PM
PDT}

Prev 1 2 3 4 5 … 9 Next

You must be logged in to post a comment.

Leave a Reply