tag:blogger.com,1999:blog-7662180971131696505.post2194439318800877009..comments2011-03-18T04:54:31.658-07:00Comments on Reality Cheque: No Free Lunch Theorems (Part I)CJYmanhttp://www.blogger.com/profile/09584586119820275846noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-7662180971131696505.post-65500688474681588752008-03-01T05:28:00.000-08:002008-03-01T05:28:00.000-08:00This is the thread you said to post my question, w...This is the thread you said to post my question, which I did in the first comment. In order to make a valid mathematical argument, each individual step has to be well-defined. We're still stuck on step one. <BR/><BR/><B>Zachriel</B>: <I>Consider a landscape of a hundred billion trillion (10^23) elements with each element of the set having a random real-number value between 0 and 1.</I><BR/><BR/><Zachrielhttp://www.blogger.com/profile/11268229653808829377noreply@blogger.comtag:blogger.com,1999:blog-7662180971131696505.post-85881760415826581012008-02-29T13:24:00.000-08:002008-02-29T13:24:00.000-08:00CJYman:"What causes that fortuitous matching. Will...CJYman:<BR/>"What causes that fortuitous matching. Will non-intelligently guided process cause that? Please provide evidence."<BR/><BR/><B>Zachriel:<BR/>"This is a question we might discuss. But it has nothing to do with the No Free Lunch Theorems, except perhaps to frame the question."</B><BR/><BR/>Actually this has everything to do with the NFLT as it shows that only problem specific CJYmanhttp://www.blogger.com/profile/09584586119820275846noreply@blogger.comtag:blogger.com,1999:blog-7662180971131696505.post-13515301331992945132008-02-29T12:48:00.000-08:002008-02-29T12:48:00.000-08:00CJYman: "Or, another answer is that you only need ...CJYman: <BR/>"Or, another answer is that you only need two samples."<BR/><BR/><B>Zachriel:<BR/>"You also left this error uncorrected."</B><BR/><BR/>It was based on a misunderstanding of your point which I have clarified in the above 2 comments.<BR/><BR/>Furthermore, the effects of random search and how inefficient they actually are compared to the size of the probability space has been discussed CJYmanhttp://www.blogger.com/profile/09584586119820275846noreply@blogger.comtag:blogger.com,1999:blog-7662180971131696505.post-12416724968897922352008-02-29T12:41:00.000-08:002008-02-29T12:41:00.000-08:00Zachriel:"A random search will find a sample in th...<B>Zachriel:<BR/>"A random search will find a sample in the 99th percentile after just 916 samples with 99.99% confidence—this on a random landscape of a hundred billion trillion (10^23) elements. The choice of search algorithm doesn't matter, by the way. Even the most ingenious algorithm is no better than any other."</B><BR/><BR/>Oh yes, that is true as far as I can tell ... except for "even theCJYmanhttp://www.blogger.com/profile/09584586119820275846noreply@blogger.comtag:blogger.com,1999:blog-7662180971131696505.post-79211974972560392482008-02-29T12:03:00.000-08:002008-02-29T12:03:00.000-08:00Zachriel:"Not only did I state random landscape, I...<B>Zachriel:<BR/>"Not only did I state random landscape, I defined it (and you repeated it). You said we could add "problem specific information" to optimize our search strategy. This is incorrect. No such optimization is available."</B><BR/><BR/>My mistake. I actually misunderstood what you were getting at somewhere along the way.<BR/><BR/>The point that I was attempting to get at is that in CJYmanhttp://www.blogger.com/profile/09584586119820275846noreply@blogger.comtag:blogger.com,1999:blog-7662180971131696505.post-45392793702505592782008-02-20T14:03:00.000-08:002008-02-20T14:03:00.000-08:00I'm averse to moving forward until you correct som...I'm averse to moving forward until you correct some of your previous misstatements, but this is of interest. <BR/><BR/><B>Zachriel</B>: <I>We're not talking about a random search algorithm, but an evolutionary algorithm that seeks local optimums. No Free Lunch Theorems only apply when averaged over either all search spaces or all search algorithms. Biological evolution concerns a specific class Zachrielhttp://www.blogger.com/profile/11268229653808829377noreply@blogger.comtag:blogger.com,1999:blog-7662180971131696505.post-91549577926217284382008-02-20T13:51:00.000-08:002008-02-20T13:51:00.000-08:00CJYman: Now you're trying to tell me that random s...<B>CJYman</B>: <I>Now you're trying to tell me that random search *is* effective? Care to provide some evidence?</I><BR/><BR/>A random search will find a sample in the 99th percentile after just 916 samples with 99.99% confidence—this on a random landscape of a hundred billion trillion (10^23) elements. The choice of search algorithm doesn't matter, by the way. Even the most ingenious algorithm Zachrielhttp://www.blogger.com/profile/11268229653808829377noreply@blogger.comtag:blogger.com,1999:blog-7662180971131696505.post-29195296930961455652008-02-20T13:43:00.000-08:002008-02-20T13:43:00.000-08:00Zachriel: Consider a landscape of a hundred billio...<B>Zachriel</B>: <I>Consider a landscape of a hundred billion trillion (10^23) elements with each element of the set having a random real-number value between 0 and 1. How many samples must we take to be confident that we have found an element with a value in the 99th percentile?</I> <BR/><BR/><B>CJYman</B>: <I>Or, another answer is that you only need two samples.</I><BR/><BR/><B>Zachriel</B>: <IZachrielhttp://www.blogger.com/profile/11268229653808829377noreply@blogger.comtag:blogger.com,1999:blog-7662180971131696505.post-6517762402063265662008-02-20T13:38:00.000-08:002008-02-20T13:38:00.000-08:00Let's review. Zachriel: Consider a landscape of a ...Let's review. <BR/><BR/><B>Zachriel</B>: <I>Consider a <B>landscape</B> of a hundred billion trillion (10^23) elements with each element of the set having a random real-number value between 0 and 1. How many samples must we take to be confident that we have found an element with a value in the 99th percentile? <BR/><BR/>Can we optimize our search strategy beyond random sampling?</I><BR/><BR/><B>Zachrielhttp://www.blogger.com/profile/11268229653808829377noreply@blogger.comtag:blogger.com,1999:blog-7662180971131696505.post-55944794570913096792008-02-20T11:15:00.000-08:002008-02-20T11:15:00.000-08:00Zachriel, you seem to not understand the causal di...Zachriel, you seem to not understand the causal difference between a random search space and an organized search space, which according to information theory are low information and high information respectively thus confusing yourself. A simple question which would clear this up for you is: "what causes an organized search space and the problem specific information necessary for evolutionary CJYmanhttp://www.blogger.com/profile/09584586119820275846noreply@blogger.comtag:blogger.com,1999:blog-7662180971131696505.post-4094195839881093362008-02-14T16:13:00.000-08:002008-02-14T16:13:00.000-08:00Zachriel: Consider a landscape of a hundred billio...<B>Zachriel</B>: <I>Consider a landscape of a hundred billion trillion (10^23) elements with each element of the set having a random real-number value between 0 and 1. How many samples must we take to be confident that we have found an element with a value in the 99th percentile? </I><BR/><BR/><B>CJYman</B>: <I>Or, another answer is that you only need two samples.</I><BR/><BR/>After taking two Zachrielhttp://www.blogger.com/profile/11268229653808829377noreply@blogger.comtag:blogger.com,1999:blog-7662180971131696505.post-66683121526989861552008-02-14T14:10:00.000-08:002008-02-14T14:10:00.000-08:00Zachriel: "How many samples must we take to be con...<B>Zachriel: <BR/>"How many samples must we take to be confident that we have found an element with a value in the 99th percentile?<BR/><BR/>...<BR/><BR/>I take your silence as indicating that you don't really know about the capabilities and limitations of random search, and for whatever reason it doesn't concern you that you don't know—even though every algorithm is being compared to a random CJYmanhttp://www.blogger.com/profile/09584586119820275846noreply@blogger.comtag:blogger.com,1999:blog-7662180971131696505.post-20313084891203276682008-02-13T15:43:00.000-08:002008-02-13T15:43:00.000-08:00Zachriel: Can we optimize our search strategy beyo...<B>Zachriel</B>: <I>Can we optimize our search strategy beyond random sampling?</I><BR/><BR/><B>CJYman</B>: <I>The answer is in the NFLT. Add problem specific information.</I><BR/><BR/>What problem specific information can you add about a random landscape?Zachrielhttp://www.blogger.com/profile/11268229653808829377noreply@blogger.comtag:blogger.com,1999:blog-7662180971131696505.post-29731160296306987332008-02-13T15:40:00.000-08:002008-02-13T15:40:00.000-08:00Zachriel: How many samples must we take to be conf...<B>Zachriel</B>: <I>How many samples must we take to be confident that we have found an element with a value in the 99th percentile?</I><BR/><BR/>I take your silence as indicating that you don't really know about the capabilities and limitations of random search, and for whatever reason it doesn't concern you that you don't know—even though every algorithm is being compared to a random search. <Zachrielhttp://www.blogger.com/profile/11268229653808829377noreply@blogger.comtag:blogger.com,1999:blog-7662180971131696505.post-25191055095751020362008-02-13T14:27:00.000-08:002008-02-13T14:27:00.000-08:00Zachriel:"Can we optimize our search strategy beyo...<B>Zachriel:<BR/>"Can we optimize our search strategy beyond random sampling?"</B><BR/><BR/>The answer is in the NFLT. Add problem specific information. <BR/><BR/>And to the rest of your comment I say ... sure ... and ...?CJYmanhttp://www.blogger.com/profile/09584586119820275846noreply@blogger.comtag:blogger.com,1999:blog-7662180971131696505.post-41483148805805254292008-02-13T14:25:00.000-08:002008-02-13T14:25:00.000-08:00It's up to you to prove that my point is wrong. J...It's up to you to prove that my point is wrong. Just read through and see what I'm saying.<BR/><BR/>BTW: did you read my most recent post re: Moderation?CJYmanhttp://www.blogger.com/profile/09584586119820275846noreply@blogger.comtag:blogger.com,1999:blog-7662180971131696505.post-79135435218476293782008-02-13T14:24:00.000-08:002008-02-13T14:24:00.000-08:00You obviously haven't read through my case, since ...You obviously haven't read through my case, since nothing you have posted here negates my summary in the least.CJYmanhttp://www.blogger.com/profile/09584586119820275846noreply@blogger.comtag:blogger.com,1999:blog-7662180971131696505.post-86407626177547400012008-02-12T07:55:00.000-08:002008-02-12T07:55:00.000-08:00CJYman: "There is no universal evolutionary algori...<B>CJYman</B>: "<I>There is no universal evolutionary algorithm that will solve all optimization problems at better than random performance.</I>"<BR/><BR/>Correct. <B>A specific algorithm and an arbitary search space.</B> Many, indeed most, search spaces are highly chaotic. <BR/><BR/><B>CJYman</B>: "<I>Likewise, there is no optimization problem that just any evolutionary algorithm will be able Zachrielhttp://www.blogger.com/profile/11268229653808829377noreply@blogger.comtag:blogger.com,1999:blog-7662180971131696505.post-43406887446034673852008-02-11T16:42:00.000-08:002008-02-11T16:42:00.000-08:00CJYman: "There is no universal evolutionary algori...<B>CJYman</B>: "<I>There is no universal evolutionary algorithm that will solve all optimization problems at better than random performance.</I>"<BR/><BR/>That is correct, as was proven by Wolpert and Macready. Seeing as we're discussing random searches. <BR/><BR/>—<BR/>EXTRA CREDIT: <BR/><BR/>Consider a landscape of a hundred billion trillion (10^23) elements with each element of the set having Zachrielhttp://www.blogger.com/profile/11268229653808829377noreply@blogger.com