Conservation of Information in Search - Measuring the Cost of Success
(→F. Random Mutation) |
m (→E. Partitioned Search: sp) |
||
| Line 72: | Line 72: | ||
|What's that all about? Imagine an alphabet of 32 letters - including {A,B,...,Z,*} and our weasel-phrase. Then the phrase could also be encoded by 28 5-bit words. One 5-bit word is only correct, if all 5 bits are correct. Therefore, we get the same expressions for ''N''=32, ''L''=28, ''W''=28 and ''N''=2, ''L''=140 and ''W''=28. | |What's that all about? Imagine an alphabet of 32 letters - including {A,B,...,Z,*} and our weasel-phrase. Then the phrase could also be encoded by 28 5-bit words. One 5-bit word is only correct, if all 5 bits are correct. Therefore, we get the same expressions for ''N''=32, ''L''=28, ''W''=28 and ''N''=2, ''L''=140 and ''W''=28. | ||
|-valign="top" | |-valign="top" | ||
| − | |Equations (22) and (23) are special cases for <math>W = L</math> and <math>W =1</math>. If <math>N^{-frac{L}{W}} | + | |Equations (22) and (23) are special cases for <math>W = L</math> and <math>W =1</math>. If <math>N^{-\frac{L}{W}} \ll 1</math>, we can make the approximation <math>p_W \approx Q^W\;N^{−L}</math> from which it follows that the active information is |
<math>I_+ \approx W\;\log_2{Q}</math>. (25) | <math>I_+ \approx W\;\log_2{Q}</math>. (25) | ||
Revision as of 18:32, 13 October 2009
Contents |
Introduction
William A. Dembski, Senior Member, IEEE, and Robert J. Marks II, Fellow, IEEE wrote an article titled: Conservation of Information in Search: Measuring the Cost of Success for IEEE TRANSACTIONS ON SYSTEMS,MAN, AND CYBERNETICS—PART A: SYSTEMS AND HUMANS, VOL. 39, NO. 5, SEPTEMBER 2009 (the article can be found here) In his blog Uncommon Descent, W. Dembski states that this peer-reviewed article is about Intelligent Design:
“”Our critics will immediately say that this really isn’t a pro-ID article but that it’s about something else (I’ve seen this line now for over a decade once work on ID started encroaching into peer-review territory). Before you believe this, have a look at the article. In it we critique, for instance, Richard Dawkins METHINKS*IT*IS*LIKE*A*WEASEL (p. 1055). Question: When Dawkins introduced this example, was he arguing pro-Darwinism? Yes he was. In critiquing his example and arguing that information is not created by unguided evolutionary processes, we are indeed making an argument that supports ID.
|
I blogged about this earlier, and at the moment, I'm trying to do a side-by-side critique of the parts of the paper I'm interested in, namely two examples of chapter III: EXAMPLES OF ACTIVE INFORMATION IN SEARCH (pp. 1055-1056):
- E. Partitioned Search
- F. Random Mutation
I started to do so on my blog, but I think that rationalwiki is better suited for this purpose.
III. EXAMPLES OF ACTIVE INFORMATION IN SEARCH
E. Partitioned Search
| Original Text | Annotiations |
|---|---|
| Partitioned search [12] is a “divide and conquer” procedure best introduced by example. | The name partitioned search seems to be an invention of R. Marks and W. Dembski. The reference is made to Dawkins's book The Blind Watchmaker in which the phrase can't be found. (See Tom English's blog) |
| Consider the L = 28 character phrase
|
This is indeed a phrase which is used in Dawkins's book - in an algorithm with which Dawkins explained the idea of cumulative selection. |
| Suppose that the result of our first query of L =28 characters is
|
An example of the egregious humorous skills of Dembski and Marks: backwards, we get:
That's no problem, as the first phrase of the algorithm can be arbitrarily chosen |
| Two of the letters {E, S} are in the correct position. They are shown in a bold font. In partitioned search, our search for these letters is finished. | At least, that's the way Dembski's and Marks's search works |
| For the incorrect letters, we select 26 new letters and obtain
|
LISTEN*ARE*THESEDESIGNED*TOO
hilarious. And an sign that we don't see the output of an actual program, but something imagined to be a run of their algorithm. BTW, the fitness function would have to encode the position of the correct letters, and the possible outcomes of the function wouldn't be a totally ordered set, but only partially ordered (what's better:
That's at least unusual, and perhaps a reason that no one else uses partitioned search. Another view (Tom English, again): we are looking at 28 independent searches, one for each letter of the target. The fitness function for each search is 1 if the letter is correct, 0 otherwise. |
| Five new letters are found, bringing the cumulative tally of discovered characters to {T, S,E, ∗,E, S,L}. All seven characters are ratcheted into place. The 19 new letters are chosen, and the process is repeated until the entire target phrase is found. | This ratcheting into place is special for the algorithm: the algorithm described in Dawkins's book doesn't show it. |
Assuming uniformity, the probability of successfully identifying a specified letter with sample replacement at least once in Q queries is , and the probability of identifying all L characters in Q queries is
|
This supports the reading as L independent searches: the search for the sentence is completed if all of the searches for the single letters are finished. A little bit less banal would be , the expected number of queries. Interestingly, this can be stated as a finite sum
If N is big, we have
|
| For the alternate search using purely random queries of the entire phrase, a sequence of L letters is chosen. The result is either a success and matches the target phrase, or does not. If there is no match, a completely new sequence of letters is chosen. To compare partitioned search to purely random queries, we can rewrite (5) as
|
Here, is simply . Putting in the values , , we get , while partitioned search takes 104.55 queries on average (the approximation via the harmonic number yields 106.03, not too shabby).
|
| For L =28 and N =27 and moderate values of Q,we have p << q corresponding to a large contribution of active information. The active information is due to knowledge of partial solutions of the target phrase. Without this knowledge, the entire phrase is tagged as “wrong” even if it differs from the target by one character. | So, how big is this active information? For p, it was calculated in section III, A as , and using the same approximation, we get (that's only true-ish for small values of Q and large alphabets...) But what does this mean? How does active information contribute to anything? At the moment, the reasoning seems to be circular: the active information is great (as the probability of a success is great), therefore the active information contributed much.
|
The enormous amount of active information provided by partitioned search is transparently evident when the alphabet is binary. Then, independent of L, convergence can always be performed in two steps. From the first query, the correct and incorrect bits are identified. The incorrect bits are then complemented to arrive at the correct solution. Generalizing to an alphabet of N characters, a phrase of arbitrary length L can always be identified in, at most, queries. The first character is offered, and the matching characters in the phrase are identified and frozen in place. The second character is offered, and the process is repeated. After repeating the procedure times, any phrase characters not yet identified must be the last untested element in the alphabet.
|
Wow, the hangman game. In detail. |
| Partitioned search can be applied at different granularities. We can, for example, apply partitioned search to entire words rather than individual letters. Let there be W words each with L/W characters each. Then, partitioned search probability of success after Q queries is
|
What's that all about? Imagine an alphabet of 32 letters - including {A,B,...,Z,*} and our weasel-phrase. Then the phrase could also be encoded by 28 5-bit words. One 5-bit word is only correct, if all 5 bits are correct. Therefore, we get the same expressions for N=32, L=28, W=28 and N=2, L=140 and W=28. |
Equations (22) and (23) are special cases for and . If , we can make the approximation from which it follows that the active information is
With reference to (6), the active information is that of W individual searches: one for each word. |
So, for , we get As stated before: we have L individual searches...
|
F. Random Mutation
| Original Text | Annotiations |
|---|---|
In random mutation, the active information comes from the following sources.
|
|
| We now offer examples of measuring the active information for these sources of mutation-based search procedures. | |
| 1) Choosing the Fittest of a Number of Mutated Offspring: | |
| In evolutionary search, a large number of offspring is often generated, and the more fit offspring are selected for the next generation. When some offspring are correctly announced as more fit than others, external knowledge is being applied to the search, giving rise to active information. As with the child’s game of finding a hidden object, we are being told, with respect to the solution, whether we are getting “colder” or “warmer” to the target. | The evaluation of the fitness function introduces external knowledge. |
Consider the special case where a single parent gives rise to children. The single child with the best fitness is chosen and used as the parent for the next generation. If there is
even a small chance of improvement by mutation, the number of children can always be chosen to place the chance of improvement arbitrarily close to one. |
children? What is wrong with n, k, j?
|
To show this, let be the improvement in fitness. Let the cumulative distribution of be . Requiring there be some chance that a single child will have a better fitness is assured by requiring or, equivalently, .
|
So, is our fitness function. Why not. The rest is basic math.
|
Generate children, and choose the single fittest. The resulting change of fitness will be , where is the change in fitness of child . It follows that so that the probability the fitness increases is
| |
Since , this probability can be placed arbitrarily close to one by choosing a large enough number of children . If we define success of a single generation as better fitness, the active information of having children as opposed to one is
|
Now, that's quite a surprise: until now, success meant finding the target. For a single step of our search, the average active information was defined. And now, we look at something quite different. And we get a new baseline...
BTW, the minus sign is an obvious error:
|
, and the probability of identifying all L characters in Q queries is
(22)
, the expected number of queries. Interestingly, this can be stated as a finite sum
.

, where
is the Lth
(23)
. Putting in the values
,
, we get
, while partitioned search takes 104.55 queries on average (the approximation via the harmonic number yields 106.03, not too shabby).
, and using the same approximation, we get
(that's only true-ish for small values of Q and large alphabets...) But what does this mean? How does active information contribute to anything? At the moment, the reasoning seems to be circular: the active information is great (as the probability of a success is great), therefore the active information contributed much.
queries. The first character is offered, and the matching characters in the phrase are identified and frozen in place. The second character is offered, and the process is repeated. After repeating the procedure
. (24)
and
. If
, we can make the approximation
from which it follows that the active information is
. (25)
As stated before: we have L individual searches...
children. The single child with the best fitness is chosen and used as the parent for the next generation. If there is
be the improvement in fitness. Let the cumulative distribution of
. Requiring there be some chance that a single child will have a better fitness is assured by requiring
or, equivalently,
.
is our fitness function. Why not. The rest is basic math.
, where
is the change in fitness of child
. It follows that
so that the probability the fitness increases is
(26)
, this probability can be placed arbitrarily close to one by choosing a large enough number of children

