Efficient Per Query Information Extraction from a Hamming Oracle

From RationalWiki
(Difference between revisions)
Jump to: navigation, search
(C. Markov Search: pic)
(VI. Conclusions: NFLT)
Line 64: Line 64:
  
 
== VI. Conclusions ==
 
== VI. Conclusions ==
''By exploring a variety of algorithms we have demonstrated hat the simple Hamming oracle can be used with surprisingly different degrees of efficiency as measured by query count. The FOO Hamming oracle algorithm manages to extract approximately one bit of information per query indicating hat the oracle can be a significant source of information. In comparison, evolutionary search as modeled by Markov processes uses the Hamming oracle inefficiently. The success of a searches derives not from any intrinsic property of the search algorithm, but from the information available from the oracle as well as the efficiency of the search algorithm in the extraction of that information. A high level interactive simulation of algorithms showing their varying effectiveness in extracting active information using a Hamming oracle is available on line at.''
+
''By exploring a variety of algorithms we have demonstrated hat the simple Hamming oracle can be used with surprisingly different degrees of efficiency as measured by query count. The FOO Hamming oracle algorithm manages to extract approximately one bit of information per query indicating hat the oracle can be a significant source of information. In comparison, evolutionary search as modeled by Markov processes uses the Hamming oracle inefficiently. The success of a searches derives not from any intrinsic property of the search algorithm, but from the information available from the oracle as well as the efficiency of the search algorithm in the extraction of that information. A high level interactive simulation of algorithms showing their varying effectiveness in extracting active information using a Hamming oracle is available on line at www.evoinfo.org.''
 +
 
 +
That doesn't seem to be so surprising. Amusingly, it is a consequence of Dembski's favourite ''Now Free Lunch'' theorem, that an algorithm which outperforms all others for a certain oracle will be less efficient for other oracles. And it's a strength of the simpler built evolutionary algorithms that they work well with a great class of sensible oracles.
  
 
== Footnotes ==
 
== Footnotes ==

Revision as of 11:06, 11 March 2010

On March 9, 2010, William Dembski announced in his blog Uncommon Descent a New Peer Reviewed ID Paper - Deconstructing the Dawkins Weasel. Amusingly, Richard Dawkins isn't mentioned in the paper at all, or in its references (though those are at least not the usual sloppy copy-and-paste job we have seen in the earlier papers). No, the only hint that this has to do something with Richard Dawkins or evolution is the use of the phrase:

METHINKS*IT*IS*LIKE*A*WEASEL.

William Dembski - and his coauthors Winston Evert, George Montañez, and Robert J. Marks II - seem to think that they are criticizing Darwinian evolution by using their secret catch phrase.

But the main sentiment when reading Editing Efficient Per Query Information Extraction from a Hamming Oracle[1] is a sense of déjà vu - or even déjà fait. So, what is it about:

Contents

Abstract

Computer search often uses an oracle to determine the value of a proposed problem solution. Information is extracted from the oracle using repeated queries. Crafting a search algorithm to most efficiently extract this information is the job of the programmer. In many instances this is done using the programmer’s experience and knowledge of the problem being solved. For the Hamming oracle, we have the ability to assess the performance of various search algorithms using the currency of query count. Of the search procedures considered, blind search performs the worst. We show that evolutionary algorithms, although better than blind search, are a relatively inefficient method of information extraction. An algorithm methodically establishing and tracking the frequency of occurrence of alphabet characters performs even better. We also show that a search for he search for an optimal tree search, as suggested by our previous work, becomes computationally intensive.

Is there any surprise here? Evolutionary algorithms are somewhat inefficient. So why are they used?

  • They are relatively simple to program
  • They don't need much knowledge about the fitness function, so they work in many cases
  • They are quite stable

But of course, the more you know about the search space, the better you can tailor your algorithm. But this wastes a lot of thinking, i.e., a rare resource.

I Introduction

In their earlier works Conservation of Information in Search - Measuring the Cost of Success and The Search for a Search - Measuring the Information Cost of Higher Level Search, the term oracle wasn't used even once. Now, you find it over twenty times in the introduction alone. Maybe, the numerous comments on threads at UncommonDescent proposing this view have worked. Or, as DiEb put it in his [blog on Aug 26, 2009:

...And that's rather a pity: W. Dembski is a guy who is interested in information, and the amount of information which is transferred from a environment into the algorithm. He should be interested in the flow of this information: How is this information exchanged? The answer: Via the conversation with the oracle....[2]

Another quote: Oracles can be used with relative degrees of efficiency. In the most simple of examples using a needle in a haystack oracle, blind sampling without replacement outperforms blind sampling with replacement in terms of average query count. This seems to be obvious, but it is a new insight for William Dembski - in his draft to The Search for a Search - Measuring the Information Cost of Higher Level Search he thought of both searches as equivalent. So this paper - currently in peer review - should have underwent some serious changes.

II Information Measures

The authors present their definition of endogenous information I_{\Omega} and active information per query I_{\oplus}.

III Markov Models for Evolutionary Search

A. Markov Processes With an Absorbing State

Absolutely nothing new here. Everyone who does some analysis of Dawkins weasel- as DiEb or Tom English - came up with this. That is basic stuff. They should not only calculate the expectation, but also the variance. It's not much harder...

B. Information Measures in Markov Searches

Again, I_{\oplus} is defined, in this time for a special case.

C. Markov Search

Now, several examples are given.

  • (A) K children with a single mutation

One of the most annoying habits of W. Dembski and his friends is to use anything but the standard notation. Numerous times they were made aware of the theory of evolutionary strategies, which dates back into the neolithicum of computer science, the 1960s. So, this algorithm is just a variant of a ES(1,k) evolutionary strategy - one parent, k children. The authors give us the transition matrix for this case.

  • (B) Ratchet Strategy

To everybody else known as ES(1+1) (the next generation exists from the parent and a single child). Again, the mutation is the change of exactly one element in the string, which is a little bit unusual, but works fine. Again, the transition matrix is calculated, a pic is drawn and even a conclusion is made:

Results : Figure 2(B) shows the active information per query for the ratchet strategy given different alphabet sizes and message lengths. Increasing the message length does not appear to significantly change the efficiency of active information extraction. However, increasing the alphabet size has a rather noticeable effect.

Well, here the authors should really have used the exact solution instead of the numerical one: they came very close to it in an earlier paper (where they called this algorithm optimization by mutation with elitism), and it was stated here at RationalWiki:

The expected number of queries for this version of the \mathbf{ES}(1+1) is

\mathbf{E}(Q) = (N-1) \cdot \mathcal{H}_{(1-\beta) L} \cdot L
so that the average information per query is
I_{\oplus}= \frac{\log(N)}{N-1}  \frac{1}{\mathcal{H}_{(1-\beta) L}}
  • \beta\,: rate of correct letters to start with
  •  \mathcal{H}_{k} k-th harmonic number
The effect of \frac{\log(N)}{N-1} is noticeable, the effect of of \frac{1}{\mathcal{H}_{(1-\beta) L}} less so.
  • (C) Mutating Children With a Fixed Mutation Rate
example for L=24, N ∈ {0,..,15}
Again, a \mathbf{ES}(1,k) algorithm, this time the version which is generally agreed to be used in Dawkins weasel: the letters in the parent string are mutated with a fixed mutation rate for a couple of children, which are the next generation. The question which rate of mutation - and which size of a population - should be used for the case N=27 and L=28 has been answered - for instance - here. So the result of this section is - again - no surprise:

Results : As illustrated in Figure 2(C), this algorithm has a slow decline in information per query until it suddenly collapses when the mutation rate becomes too high. If, for example, we are within a single character of identifying a phrase, then a mutation rate that gives on average, say, 10 mutations will take a long time to take the final small step to perfection.

  • (D) Optimizing the Mutating Schedule for Children

Something - slightly - new. The mutation rate is not fixed, but evaluated in dependence of the value of the fitness function. Of course, optimizing the mutation probability has always been of interest[3]. The concrete computation for every value from {0,\dots, L} seems to be quite labor-intensive, though.

IV. Frequency of Occurrence Hamming Oracle Algorithm

While all algorithms described in the earlier section were random algorithms, here a deterministic one is given. It fares much better than the evolutionary algorithms, at least for the concrete oracle. But as stated above, evolutionary algorithms often work under different circumstances. Imagine for instance an oracle which doesn't state the number of correct letters in a phrase, but the length of the longest correct subphrase. Or the number of correct letters in a row counted from the beginning of the phrase. Or the product of the number of correct consonants and the number of correct vowels and spaces: The algorithms of (A), (B), (C) will still get the result, and (D), too - though it looses its advantages over the other three. But the charmingly called FOOHO algorithm will fail.

V. Optimal Hamming Search: A Search for the Search

This should have been the main part of the paper. Unfortunately, it is a little bit short, and though some numbers are stated, no calculations are given. It could have profited from definitions of the basic terms, like search. And some estimations would have be fine. So, it is just not much.

VI. Conclusions

By exploring a variety of algorithms we have demonstrated hat the simple Hamming oracle can be used with surprisingly different degrees of efficiency as measured by query count. The FOO Hamming oracle algorithm manages to extract approximately one bit of information per query indicating hat the oracle can be a significant source of information. In comparison, evolutionary search as modeled by Markov processes uses the Hamming oracle inefficiently. The success of a searches derives not from any intrinsic property of the search algorithm, but from the information available from the oracle as well as the efficiency of the search algorithm in the extraction of that information. A high level interactive simulation of algorithms showing their varying effectiveness in extracting active information using a Hamming oracle is available on line at www.evoinfo.org.

That doesn't seem to be so surprising. Amusingly, it is a consequence of Dembski's favourite Now Free Lunch theorem, that an algorithm which outperforms all others for a certain oracle will be less efficient for other oracles. And it's a strength of the simpler built evolutionary algorithms that they work well with a great class of sensible oracles.

Footnotes

In the most simple of examples using a needle in a haystack


  1. Efficient Per Query Information Extraction from a Hamming Oracle, Winston Ewert, George Montañez, William A. Dembski, Robert J. Marks II (pdf)
  2. [DiEbLog Aut 26, 2009
  3. Global Properties of Evolution Processes (Appendix) by H. J. Bremermann, M. Rogson, S. Salaff in Natural Automata and Useful Simulations, H.H. Pattee, E.A.Edelsack, L.Fein, and A.B.Callahan (eds), Spartan Books, Washington D.C, 1966

See also

Personal tools
Namespaces

Variants
Actions
Navigation
Community
Tools
support