Five Years of "The Search for a Search"

The Journal of Advanced Computational Intelligence and Intelligent Informatics published the paper The Search for a Search: Measuring the Information Cost of Higher Level Search of William A. Dembski and Robert J. Marks II (DM) in its July edition in 2010. With the five year jubilee of the publication coming, it seems to be appropriate to revisit a pet peeve of mine...

(Shell game performed on Karl-Liebknecht-Straße in Berlin, photograph by E.asphys)

Imagine a shell game. You have observed the con artist for a while, and now you know:

1. The pea ends up under each of the three shells (left, middle, and right) with the same probability, i.e., $$P(Pea=left)=P(Pea=middle)=P(Pea=right)=1/3$$
2. If the pea ends up under the left or the middle shell, you are able to track its way. So, in these cases, you will find the pea with probability 1 $$P(Finding\,Pea|Pea=left)=P(Finding\,Pea|Pea=middle)=1$$
3. However, if the pea ends up under the right shell, in 999 times out 1000, you make a mistake during your tracking and be convinced that it is under the left or the middle shell - the probability of finding this pea is 1/1000$$P(Finding\,Pea|Pea=right)=1/1000$$

You are invited to play the game. Should you use your knowledge (method $M_1$), or should you chose a shell at random (method $M_2)$?

I wrote a letter to W. Dembski and R. Marks

After reading their article Conservation of Information in Search:
Measuring the Cost of Success in some detail, I decided to write to W. Dembski and R. Marks, just to hint them to some minor miscalculations: So, they have the chance to get at least the math straight in their peer-reviewed paper.

At uncommondescent.com, I tried to draw attendance of Willima Dembski to two minor errors in your IEEE paper ''Conservation of Information in Search – Measuring the Cost of Success'':

Could you correct the sign errors in equation (27) and on page 1057, left column, for Q?

More problematic is the next line: you speak about the active information per query, but you calculate the active information per generation, as you drop the factor -2 from Q ~ -2log(L)/log(1-2µ) and so reach

I+ ~ L/log(L) * log(1-2µ) instead of
I+ ~ L/(2*log(L)) * log(1-2µ).

So, I+ should be µ*L/ln(L) and not 2*µ*L/ln(L).

(I stumbled upon this when I calculated my approximation I+ ~ µ*L/H_((1-b)L) for the average number of queries Q ~ H_((1-b)L)/µ )

And there is a little problem with Fig. 2: all the paths seem to start with no correct bits at all - while the math in ch. III-2 assumes that half of the bits are correct.

Let L=100, µ=0.00005:

1. if you use b(eta) = .5 (as in your calculation) Q ~ 92,100 and I+ ~ 0.00109. Then, you should take other paths for your pic

2. if you use b(eta) = 0 (as in you figure) Q ~ 106,000 and I+ ~ 0.000943

The number in your text is I+ ~0.0022. That's wrong in any case.


Yours
Di***** Eb**

Don't get me wrong: I don't want to be just nit-picking. One sign error is no big deal, an even number of sign errors cancels itself out :-)
And the factor two? It's at least the same order of magnitude. (And no one know what magnitude is to be expected for active information, so even a factor 100 would not have been easily spotted). And I didn't mention all the inaccuracies in their references' section....

Another approach

I completed this little project here.

I thought about different ways to present my ideas on W. Dembski's and R. Marks's article Conservation of Information in Search: Measuring the Cost of Success, and tried a few out in the last posts. The section which I'm interested in is the description of three evolutionary algorithms they give on pp. 1055-1057. Here's another approach for III E - G:

Original Text	Annotiations
E. Partitioned Search
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 METHINKS∗IT∗IS∗LIKE∗A∗WEASEL. (19)	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 SCITAMROFN∗IYRANOITULOVE∗SAM. (20)	An example of the egregious humorous skills of Dembski and Marks: backwards, we get: mas*evolutionaryi*nformatics 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 OOT∗DENGISEDESEHT∗ERA∗NETSIL. (21)	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: METHINKS*IT*ISXXXXXXXXXXXXXX or XXXXXXXXXXXXXX*LIKE*A*WEASEL). That's at least unusual, and perhaps a reason that no one else uses partitioned search.
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 1 − (1 − 1/N)Q, and the probability of identifying all L characters in Q queries is q = (1 − (1 − 1/N)Q)L (22)	Yep, that's true. But why not doing a little math and giving us the expected number of queries? That would be a little bit less banal. And it's helpful if you want compare different algorithms
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 p =1 − (1 − (1/N)L)Q (23)	yup.
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 I+(p) = log(Q), and using the same approximation, we get I+(q) = L log(Q) (that's only true-ish for small values of Q and large alphabets...)
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, N − 1 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 N − 1 times, any phrase characters not yet identified must be the last untested element in the alphabet.	Wow, the hangman's 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 pW=(1 − (1 − N−L/W)Q)W. (24)	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 W = L and W =1.If N−L/W << 1, we can make the approximation pW ≈ QWN−L from which it follows that the active information is I+ ≈ W log2 Q. (25) With reference to (6), the active information is that of W individual searches: one for each word.	So, for W=L, we get I+(q) = L log(Q). My interpretation: virtually, this algorithm provides you with L fitness functions, one for each letter, indicating whether it is correct or not. BTW: I think it is surprising how the fitness functions get ignored during the whole article...

Evolutionary Algorithms in Conservation of Information in Search

work in progress :-)

In their paper Conservation of Information in Search: Measuring the Cost of Success, William A. Dembski, Senior Member, IEEE, and Robert J. Marks II, Fellow, IEEE present three algorithms which could loosely be described as evolutionary. Idiosyncratically, they are labeled

1. Partitioned Search
2. Optimization by Mutation, and
3. Optimization by Mutation With Elitism

These procedures are discussed section II, part E and F (pp. 1055-1057), and some additional math is done in the appendix.

The algorithms and the examples given

The three algorithms are introduced or illustrated with an example, for which the parameters can be found in this table:

Algorithm	class	alphabet	length of target	Mutation	fitness function
Partitioned Search	none	{*,A,B,...Z} (27 el.)	28	every incorrect letter is mutated	position of correct letters
Optimization by Mutation	(1,2) ES	{0,1} (2 el.)	100	each letter is flipped with probability µ=0.00005	number of correct letters
Optimization by Mutation With Elitism	(1+1) ES	{0,1} (2 el.)	131*	exactly one letter is flipped	number of correct letters

^*Why 131b for the last algorithm? I could understand 133 ~ 28* log₂27, but 131?

References

Four references are given in the section under discussion:

• [3] M. Aigner, Discrete Mathematics. Providence, RI: Amer. Math. Soc., 2007.
• [12] R. Dawkins, The Blind Watchmaker: Why the Evidence of Evolution Reveals a Universe Without Design. New York: Norton, 1996.
• [32] D. J. C.MacKay, Information Theory, Inference and Learning Algorithms. Cambridge, U.K.: Cambridge Univ. Press, 2002.
• [34] A. Papoulis, Probability, Random Variables, and Stochastic Processes, 3rd ed. New York: McGraw-Hill, 1991, pp. 537–542.

The first one is unproblematic - though superfluous: it is given as a reference for the Lth harmonic number. The three other references are either problematic or at least indicating sloppy work:

1. Partitioned search [12] is a “divide and conquer” procedure best introduced by example. Richard Dawkins doesn't use the expression "partitioned search" in his book.

2. When μ << 1, the search is a simple Markov birth process [34] that converges to the target. The page numbers of the reference don't fit: it should be pp. 647-650, not pp. 537–542. But at least, page numbers are given!

3. To illustrate, consider a single-parent version of a simple mutation algorithm analyzed by McKay [32].David MacKay analyzes explicitly multi-parented algorithms, there is not much of a resemblance with Dembski's and Marks's procedure. And annoyingly, again, page numbers are omitted. MacKay's book has over 600 pages, only a few in Chapter III, 19 : Why have Sex? Information Acquisition and Evolution are dedicated to evolutionary algorithms.

But one has to be grateful for small things: At least these references weren't garbled like

[7] S. Christensen and F. Oppacher, “What can we learn from no free lunch? A first attempt to characterize the concept of a searchable,” in Proc. Genetic Evol. Comput., 2001, pp. 1219–1226.

Of course, it's about the concept of a searchable function. Not the first time, R. Marks and W. Dembski got that wrong.
Ann.: Tom English explained that errors in references are common in the engineering literature. So, I'll stop classifying the references of Dembski's and Marks's article as either superfluous or erroneous for now.

I'm annoyed.

Perhaps I'm easily annoyed. But every time I read the paper Conservation of Information in Search - Measuring the Cost of Success, I'm getting, well, pretty much distressed. I wanted to write a concise rebuke of this article, but you can't be concise: there is so much disturbing in it, often little things. Take for instance this innocuous little sentence

To illustrate, consider a single-parent version of a simple mutation algorithm analyzed by McKay [32].

The reader may be interested in McKay's analysis of a simple mutation algorithm, and follows the reference:

D. J. C.MacKay, Information Theory, Inference and Learning Algorithms. Cambridge, U.K.: Cambridge Univ. Press, 2002.

Thankfully, David J.C. MacKay (he seems to prefer this spelling) put his book online. And yes, it is a book, a textbook with over 600 pages. It's covering a wide range, so at least, Dembski and Marks should have given the pages which they thought to be relevant. Which they thought to be relevant is a key phrase, because a skimming of the book doesn't render anything resembling an analysis of a simple mutation algorithm like the one in the article: yes, there is Chapter III, 19 :Why have Sex? Information Acquisition and Evolution - but this is explicitly about algorithms with multiple parents, it just doesn't fit a single parent version - MacKay assumes for instance that the fitness of the parents is normally distributed, something you just can't have for a single parent version. So why do Marks and Dembski give MacKay as a reference? I have no idea.

And it's going on

Just checking the next reference: [34] A. Papoulis, Probability, Random Variables, and Stochastic Processes, 3rd ed. New York: McGraw-Hill, 1991, pp. 537–542. for this little piece of marginal information

When μ << 1, the search is a simple Markov birth process [34] that converges to the target.

You may say: At least, they are giving a page number. But it's the wrong one! Take out your 3rd edition of Papoulis's very good introduction to the theory of probability, and you'll find Markov birth processes on pp. 647 - 650: why can't they get at least the details right?