Talk:No free lunch in search and optimization

From Wikipedia, the free encyclopedia

Good article No free lunch in search and optimization was one of the Engineering and technology good articles, but it has been removed from the list. There are suggestions below for improving the article to meet the good article criteria. Once these issues have been addressed, the article can be renominated. Editors may also seek a reassessment of the decision if they believe there was a mistake.
This article is within the scope of the following WikiProjects:

Contents

[edit] older entries

When I checked the link at Most of these references can be obtained from... not only were the files not available, but the citations were incorrect and/or incomplete. 22:34, 21 November 2006 (UTC)

A request/challenge--somebody might try translating this explanation (and others like it) into English, so that the rest of us can figure out how it might apply to our fields. I do appreciate the critique of Dembski's application but need more examples in familiar (as opposed to jargon) terms.

[edit] Factually incorrect figure

The figure is incorrect, and has to go. In fact, when all cost functions are equally likely, each algorithm observes each possible sequence of cost values with equal likelihood, so there is no specialist / generalist trade-off of the sort depicted in the plot. To state that more precisely, if there are N domain elements and M codomain elements (distinct costs), then the probability that an arbitrarily chosen algorithm will observe values in an arbitrarily chosen sequence is M-N.

At the risk of seeming like I'm engaged in self-promotion, I'm going to take a shot at rewriting this article. The touted "simple explanation" is not freely accessible online, and it happens that I gave a very simple explanation during a student's thesis defense in 1994. I will try to respond to the "request / challenge" above, but part of me says that into every life a little math must fall. NFL is inherently about probability distributions on functions and sequences. ThomHImself 00:54, 11 March 2007 (UTC) Tom English


[edit] "The No Free Lunch Theorem" is not the point

Section 3 of Wolpert and Macready (1997) gives two NFL theorems, not one. The 1995 tech report and the 1997 article of W&M both refer to theorems, plural, in the titles. This makes reference to the theorem something of an embarrassment. Beyond that, people who state the theorem rarely, if ever, state the first NFL theorem (the one they seem to have in mind). Instead they state their favorite interpretations.

The fact is that the actual NFL theorems are not as interesting as their immediate implications. That is why I am moving this article to "No Free Lunch in Search and Optimization," with "No-free-lunch theorem" redirecting here. ThomHImself 21:10, 11 March 2007 (UTC) Tom English

Note that double redirects do not work, so that if you do move this page, you will need to update any double redirects that are created as a result of the move. The What Links To No-free-lunch_theorem special page will help in locating them. -- Cat Whisperer 21:18, 11 March 2007 (UTC)

[edit] More changes to come

A figure will clarify the introduction.

Watch for sections giving a gentle introduction to NFL and formalizing NFL.

I made a large number of changes without logging in. Sorry, but I'm a neophyte, and didn't know I wasn't logged in. ThomHImself 05:25, 29 March 2007 (UTC)

[edit] Deleted folkloric theorem from introduction

It is somewhat humorous that someone added to the introduction precisely what I document as mathematical folklore in a later section on "the" NFL theorem:

Put simply, the theorem says that over the average of all possible solution landscapes, no search algorithm is on average better than any other.

No one who makes this claim ever cites both an article and a theorem number. There is no such theorem in the writings of Wolpert and Macready. Furthermore, at the point where the sentence was added, there had been no mention whatsoever of a theorem. The article is now about NFL in search and optimization, and the folkloric theorem is just one aspect of that. ThomHImself 06:16, 29 March 2007 (UTC)

[edit] Deleted "Additional Notes" message

I took this out, and I would be interested in knowing what's going on:

==Additional Notes==
This is also referenced by the infamous Pascal. If this is heard, please disbelieve him.

ThomHImself 23:34, 26 April 2007 (UTC)

[edit] Math typesetting

Thanks to whomever cleaned up the math typesetting in "Synopsis of NFL in mathematical terms." I will see later if I can't use <math> to improve some other stuff. —The preceding unsigned comment was added by ThomHImself (talk • contribs) 05:05, 29 April 2007 (UTC).

[edit] Moved Info on Baylor Lab

The treatment of Baylor's Evolutionary Informatics Laboratory as part of the "great intelligent design conspiracy" was unjustified. We have to go on what the lab actually gives evidence of doing. What I see is a generalization of Dembski's ideas to what could be an entirely legitimate field of study. It is certainly the case that practitioners of evolutionary computation supply domain knowledge when they can, and that it is important to understand how this information affects the results obtained.

The text entered in the article reduced ultimately to argumentum ad hominem -- against Dembski, actually. Bob Marks has made outstanding contributions to engineering that not even an opponent of intelligent design like me questions. When he says he is engaged in legitimate scholarship, one has to suppose he is in the absence of evidence to the contrary. ThomHImself 23:21, 19 June 2007 (UTC)

[edit] Cullen Schaffer and conservation of generalization accuracy

NFL is in fact what I prefer to call conservation of search performance, in analogy with Schaffer's conservation of generalization accuracy (nonexistent article) in machine learning (no reference to conservation). This article could use a section relating NFL to conservation of generalization accuracy, but only when the main article exists.

Instead we got "Cullen Schaffer did it first, only it was a little different" editing that put his name in the introduction and at the head of the list of references. I have given positive suggestions, but to what entered the article, I will simply say no.

A little story: I sketched a proof of the first NFL theorem in 1994, during a public thesis defense. I asked the student what he hoped to accomplish by tweaking optimizers to get better performance on test functions. He said, of course, that he hoped to obtain a generally superior optimizer. After a brief pause, I responded that optimizing a uniformly drawn function was equivalent to optimizing the output of a uniform random number generator. The silence that fell over the room was remarkable. I was never so arrogant as to think I was the only person to complete such a shallow line of reasoning. Over the years, I have met various people who realized there was NFL before Wolpert and Macready called it that.

The substantive part of Wolpert and Macready's work is the information-geometric analysis of "alignment" of algorithms and problems. ThomHImself 23:59, 26 June 2007 (UTC)

I have added a couple sentences about NFL as conservation of search performance, along with an indication that conservation of generalization accuracy came first, in the overview. Somebody please write the other article and give Schaffer his due. ThomHImself 04:48, 27 June 2007 (UTC)

[edit] GA Tip

Perhaps images should be added to this. In the [Criterea], it says that articles should be illustrated. --Dan LeveilleTALK 08:54, 28 December 2007 (UTC)

Thanks, Dan. There used to be an illustration, but it was based on a common misunderstanding of NFL. The only clear illustration of how NFL "works" I have seen is a collection of three figures in the English (2004) paper. They convey technical detail, and adapting them for the article is not easy. I plan to decorate the introduction with something like Figure 4 – it fits with the final paragraph – though I worry about discouraging the general reader. The illustrations of a decision tree and the operation of the decision tree on objective functions would enhance the "formal synopsis" section. I would very much appreciate advice from anyone on this matter.ThomHImself (talk) 23:38, 15 January 2008 (UTC)
Good point. It is a hard situation. --Dan LeveilleTALK 01:24, 16 January 2008 (UTC)
See "Illustration" section below.ThomHImself (talk) 07:48, 18 January 2008 (UTC)

[edit] New section title

Regarding "Specified complexity, active information, and NFL": The unpublished papers coauthored by Dembski and Marks make no reference to intelligent design or to specified complexity. The notion of active information is very different from specified complexity, and is in itself reasonable. Marks seems to me an honest creationist who shares IDists' interest in information. The use of "active information" in arguments dismissing the success of computational simulations of evolutionary processes is undeniably analogous to the use of "specified complexity" in Dembski's earlier arguments. There is certainly the possibility that ID has again morphed. Thus I have opted to keep discussion of the two concepts together, but to avoid the suggestion that Marks is a member of the intelligent design movement.ThomHImself (talk) 20:24, 15 January 2008 (UTC)

I decided to tag both Dembski and Marks with a neo-creationism "see also." I've left it to the reader to decide if what I've described in neutral terms qualifies as neo-creationism. Marks has given science-oriented apologetics presentations around the world, so I think this is fair enough. I also added text to make it clear that Dembski and Marks' arguments that researchers "smuggle" active information into evolutionary simulations is analogous to Dembski's early arguments that researchers smuggle complex specified information into algorithms.ThomHImself (talk) 23:12, 15 January 2008 (UTC)

[edit] Illustration

I think a simple illustration to go with the introduction would be two menus, one offering low prices to the vegan, and the other offering low prices to the carnivore. The prices on each menu would simply be those on the other, reordered. I would appreciate hearing from any passersby whether this would clarify.ThomHImself (talk) 07:48, 18 January 2008 (UTC)

I apologize for being slow in adding an illustration, and I appreciate Josedavid's attempt to improve the article by adding one. Unfortunately, the illustration was very similar to the one (taken from NFL.org) I discussed in "Factually incorrect figure" above. In the NFL framework, there really is no such thing as a specialized algorithm. Any two algorithms A and B have identically distributed performance values. They differ possibly in the problems for which they achieve given levels of performance. The illustrated situation simply cannot arise. The fact that such depictions of NFL are common indicates just how widespread misunderstanding of the fundamental working of NFL is.

Again, thanks to Josedavid for the effort, and I'm sorry to have to remove the work. I will try to get the promised illustration into the article by tomorrow.ThomHImself (talk) 02:01, 19 February 2008 (UTC)

OK, I now have in place the simplest correct illustration of NFL I've ever come by. I'm not happy with the fuzziness of the captions, and I'm going to take a shot (in my own due time, perhaps) at making an SVG, rather than PNG, image.ThomHImself (talk) 20:54, 19 February 2008 (UTC)

[edit] "Paring this down per WP:NPOV. Size and credulousness of section gave undue weight to ID proponents views."

Treatment of a topic in the encyclopedia is not endorsement. user:Odd Nature has been unable to provide a reliable source at Robert J. Marks II for his claim that Marks is an ID advocate, so he has come here to assert that Marks is an ID advocate. He obliterated a section here documenting the fact that Marks' active information is not equivalent to Dembski's specified complexity. The content was sourced. He also obliterated a section of Evolutionary Informatics Lab that included Mark Chu-Carroll's criticism of specified complexity and acknowledgment that active information might be useful. This looks like systematic removal of a balanced response, not a NPOV. Any human being, including Dembski, is capable of producing both bogus and useful ideas. We have to report on the ideas as ideas, and not engage in thinly veiled ad hominem attacks.

Odd Nature has a habit of deleting without discussing. I look forward to having my credulousness demonstrated to me in detail. BTW, I have a chapter highly critical of ID theory to appear in an edited volume this June. ThomHImself (talk) 09:17, 18 April 2008 (UTC)

[edit] Removing original research

I had little knowledge of Wiki policy when I began editing this article. There is a great deal of my original research here. Having since held others to WP:NOR in other articles, I am going to police myself here. ThomHImself (talk) 16:47, 24 April 2008 (UTC)

[edit] Introduction

The second paragraph elaborating the NFL metaphor was something that I have never seen in the literature, and was my WP:Synthesis. I thought long and hard about the figure, because I had neither contributed nor seen a good, simple figure in the NFL literature. Obviously this was my synthesis. It did not follow immediately from anything in the literature, and was supported only by my own authority. ThomHImself (talk) 17:07, 24 April 2008 (UTC)

[edit] Example: NFL in a roulette game

When the article passed GA review, a reviewer expressed vague doubts about this section, and I didn't understand what s/he was driving at. The example was entirely novel, reflecting how I understand my own formal results in the source I gave. To my knowledge, here is nothing like the example in the NFL literature. ThomHImself (talk) 17:21, 24 April 2008 (UTC)

[edit] Formal synopsis of NFL

The "functionally equivalent" algorithm was my invention. To my knowledge, neither it nor its functional equivalence to anything appears in the NFL literature. The nice concept of Phi-NFL distributions on objective functions was something I came by working on this article. I have not published it, and to my knowledge no one has published an equivalent concept. ThomHImself (talk) 17:41, 24 April 2008 (UTC)

[edit] Original NFL theorems

My statement in plain language of what Theorem 1 "says" was novel, and supported only by my own "authority." Similarly, my claim that the theorem implies much more than the "folkloric theorem" is unsupported, and furthermore reflects my bias. I will remove this bias throughout the article later. ThomHImself (talk) 17:51, 24 April 2008 (UTC)

[edit] Interpretation of NFL results

This section was full of common misinterpretation of the NFL results when I began editing the article. I replaced them with my own "wise" interpretation, synthesizing statements from published sources, and adding two longish paragraphs with no sources whatsoever. I have pruned this section to the interpretation that was in the article when I first came on the scene, plus qualifying remarks directly supported by sources. ThomHImself (talk) 18:12, 24 April 2008 (UTC)

[edit] Folkloric NFL theorem

That people substitute a plain-language statement for Wolpert and Macready's Theorem 1, and that they reduce the entire body of NFL results to that folkloric theorem, is a pet peeve of mine. This probably owes in part to the fact that it deemphasizes my own contributions. Characterization of the plain-language statement as a folkloric theorem occurs nowhere but here to my knowledge, and emphasis of the characterization definitely reflects my bias. Thus I have removed it from the article. ThomHImself (talk) 18:40, 24 April 2008 (UTC)

[edit] Overview and (A)NFL theorem

Omission of the (A)NFL theorem was originally oversight on my part. When I came upon it again, six years after first reading the paper proving it, I did not agree with authors' interpretation, and pondered how to treat their interpretation without contradicting different claims in the article. I should never have considered this. What is published is what should be reported here. My unpublished reservations have no place here.

The (A)NFL theorem deserves mention in the introduction. ThomHImself (talk) 19:26, 24 April 2008 (UTC)

The discussion of Kolmogorov complexity of functions and algorithms is reduced to theoretical finery with the inclusion of the (A)NFL theorem. To allow it to remain in Wikipedia now would serve merely to promote my own work. That is, Kolmogorov complexity is a confusing topic, and including it here tends to confuse the treatment of NFL. ThomHImself (talk) 19:56, 24 April 2008 (UTC)

[edit] Possibly defamatory claim about Robert J. Marks II

Please do not repeat the claim that Marks is a proponent of a certain ideology (see this diff) unless you can provide a source allowed by policy on reliable sources for living persons.

WP:BLP specifies immediate removal of possibly defamatory or otherwise damaging claims about living persons that are not sourced according to policy. This applies to all of Wikipedia -- talk pages etc., and not just articles. The three revert rule does not apply to defense of WP:BLP. Note in the diff above that I've done nothing but remove the possibly defamatory or otherwise damaging claim. ThomHImself (talk) 22:30, 24 April 2008 (UTC)

[edit] Suggestions for making this a GA again

[edit] Figure

I have twice removed factually incorrect figures from this article. Anyone who adds a figure should adapt it from a figure in the NFL literature (peer-reviewed article or published book), and not the one at the NFL website (it has already been in this article). ThomHImself (talk) 23:43, 24 April 2008 (UTC)

[edit] Elaboration and elucidation

With my removal of a massive amount of exposition that was my original research or reflected my personal opinion, some sections of the article are very thin. They need additional material that is not made up by the editor (don't repeat my violations of Wiki policy), but is directly supported by books or peer-reviewed papers on NFL. ThomHImself (talk) 23:43, 24 April 2008 (UTC)

[edit] Intelligent design and NFL

This section has been appropriated for polemics by anti-ID editors. I have been accused of conflict of interest in the matter, so I will do nothing with the section but defend Wikipedia policy on claims about living persons. There should be discussion of invocations of NFL by Dembski and Marks at Evolutionary Informatics Lab or in an article on active information. I recommend that someone who wants to make this a maintainable technical article simply delete the section. ThomHImself (talk) 23:43, 24 April 2008 (UTC)

[edit] A More Friendly Introductory Paragraph

I think this article could benefit from another sentence in the introduction explaining the topic to laypeople. As a computer science major unfamiliar with the topic, I found it confusing. —Preceding unsigned comment added by 69.143.161.239 (talk) 03:13, 8 May 2008 (UTC)