Bronze-level articleConservation of Information in Search - Measuring the Cost of Success

From RationalWiki
Jump to: navigation, search
The divine comedy

Creationism

Icon creationism.svg
Running gags
Jokes aside
Blooper reel
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.

As is frequently the case when creationists/cdesign proponentsists purport to analogize biological facts from information theory, active information (the use of which Dembski claims renders the weasel algorithm an incorrect analogy) is never concretely defined. It appears to simply mean the fitness function, which any genetic algorithm has (or there would be no point in creating it) and which, contra Dembski's implied claim, says nothing about a designer — the fitness function in a biological environment is simply the effect of the combination of selective pressures applied by environmental conditions at any given time. It may also mean the source of variation, which in Dawkins' algorithm is expressly identified as the chance of mutating any given letter and which in biology is held to be the combined effect of differing mutations and selective pressures experienced by different populations.

This article takes a closer look at two examples of chapter III: Examples of Active Information in Search (pp. 1055-1056):

  • E. Partitioned Search
  • F. Random Mutation

Contents

[edit] III. Examples of Active Information in Search

[…]

[edit] E. Partitioned Search

Original Text Annotations
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 a sign that we don't see the output of an actual program, but something imagined to be a run of their algorithm (this impression is furthered by Dembski's claim, contradicted by Dawkins' description of it, that the algorithm never mutates letters that are in place — those interested can code the algorithm themselves, or use any of many implementations of it published online, and see that this simply is not the case). By the way, 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. 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 1 - (1 - \frac{1}{N})^Q\,, and the probability of identifying all L characters in Q queries is

q = (1 - (1 - \frac{1}{N})^Q)^L\, (22)

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.
expected number of queries (L=28)
A little bit less banal would be \mathbf{E}(Q)\,, the expected number of queries. Interestingly, this can be stated as a finite sum

\mathbf{E}(Q) = \sum_{k=1}^L (-1)^{k+1} {L \choose k} \frac{1}{1-(1-1/N)^{k}}\,.

If N is big, we have

\mathbf{E}(Q) \approx \sum_{k=1}^L (-1)^{k+1} {L \choose k} \frac{N}{k}\,= N \mathcal{H}_L\,, where \mathcal{H}_L\, is the Lth harmonic numberWikipedia's W.svg — something we'll see again :-)

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-(\frac{1}{N} )^L)^Q\, (23)

Here, \mathbf{E}(Q)\,is simply N^L\,. Putting in the values N=27\,, L=28\,, we get \mathbf{E}(Q)\,  = 11,972,515,182,562,019,788,602,740,026,717,047,105,681\, \approx 1.19725 \cdot 10^{40}\,, 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 I_+(p)\; = log_2(Q)\,, and using the same approximation, we get I_+(q) = L \;log_2(Q)\, (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, 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 gameWikipedia's W.svg. 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

p_W=(1 - (1 - N^{-\frac{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^{-\frac{L}{W}} \ll 1\,, we can make the approximation p_W \approx Q^W\;N^{-L}\, from which it follows that the active information is

I_+ \approx W\;\log_2{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_2(Q).\, As stated before: we have L individual searches...

[edit] F. Random Mutation

Original Text Annotiations
In random mutation, the active information comes from the following sources.
  1. Choosing the most fit among mutated possibilities. The active information comes from knowledge of the fitness.
  2. As is the case of prolonged random search, in the sheer number of offspring. In the extreme, if the number of offspring is equal to the cardinality of the search space and all different, a successful search can be guaranteed.
  1. As for now, we didn't hear much about the fitness function. This is quite surprising...
  2. If you look at all elements, you have all the possible information, active or else...
We now offer examples of measuring the active information for these sources of mutation-based search procedures.

[edit] Choosing the Fittest of a Number of Mutated Offspring

Original Text Annotiations
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 \Phi\, 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. \Phi\, children? What is wrong with n, k, j?
To show this, let \Delta \kappa\, be the improvement in fitness. Let the cumulative distribution of \Delta \kappa\, be F_{\Delta \kappa}(x) = Pr[\Delta \kappa \leq x]\,. Requiring there be some chance that a single child will have a better fitness is assured by requiring Pr[ \Delta \kappa > 0] > 0\, or, equivalently, F_{\Delta \kappa}(0) < 1\,. So, \kappa\, is our fitness function. Why not. The rest is basic math.
Generate \Phi\, children, and choose the single fittest. The resulting change of fitness will be \Delta \kappa_{\max} = max_{1 \leq \phi \leq \Phi} \Delta \kappa_{\phi}\,, where \Delta \kappa_{\phi}\, is the change in fitness of child \phi\,. It follows that F_{\Delta \kappa_{\max}}(x) = F^{\Phi}_{\Delta \kappa} (x)\, so that the probability the fitness increases is

Pr[\Delta \kappa_{\max} > 0] = 1 - F^{\Phi}_{\Delta \kappa} (0)\, (26)

Since F{\Delta \kappa} (0) < 1\,, this probability can be placed arbitrarily close to one by choosing a large enough number of children \Phi\,. If we define success of a single generation as better fitness, the active information of having \Phi\, children as opposed to one is I_+ = - \log (\frac{1 - F^{\Phi}_{\Delta \kappa} (0)}{1 - F_{\Delta \kappa} (0)})\, 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:

\frac{1 - F^{\Phi}_{\Delta \kappa} (0)}{1 - F_{\Delta \kappa} (0)}\,=1 + \sum_{k=1}^{\Phi - 1} F_{\Delta \kappa}^k (0)\, \geq 1\,

[edit] Optimization by Mutation

Original Text Annotiations
Optimization by mutation, a type of stochastic search, discards mutations with low fitness and propagates those with high fitness. To illustrate, consider a single-parent version of a simple mutation algorithm analyzed by McKay [32]. A simple mutation algorithm analyzed by McKay. One would expect that this analysis is done in [32]
D. J. C.MacKay, Information Theory, Inference and Learning Algorithms. Cambridge, U.K.: Cambridge Univ. Press, 2002.
This is a book with more than 600 pages, which David MacKay thankfully put online. In Chapter III, 19 :Why have Sex? Information Acquisition and Evolution, a mutation algorithm is discussed briefly, 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? On the other hand, algorithms of this kind are studied since the 1970s, this is for instance an so called evolutionary strategy, more precisely, a (1,\Phi\,)ES.
Assume a binary (N =\;2\,) alphabet and a phrase of L bits. The ?rst query consists of L randomly selected binary digits.We mutate the parent with a bit-flip probability of \mu\, and form two children. The fittest child, as measured by the Hamming distance from the target, serves as the next parent, and the process is repeated. Choosing the fittest child is the source of the active information. When \mu \ll 1\,, the search is

a simple Markov birth process [34] that converges to the target.

What is a simple Markov birth process according to [34] A. Papoulis, Probability, Random Variables, and Stochastic Processes, 3rd ed. New York: McGraw-Hill, 1991, pp. 537–542. (The page numbers are wrong. Sloppy, isn't it?) On page 647, we read
A birth process is [a] Markoff chain x(t)\, consisting of a family of increasing staircase functions. The process x(t)\, (population size) takes the values 1,2,3,\ldots\, and increases by 1 at the discontinuity points t_i\, (birth times).
And on the next page:
If the birthrate is proportional to the population size n\,: \mu_n = n c \, then x(t)\, is called the simple birth process (the constant c is the birthrate per person).
To show this, let k[n]\, be the number of correct bits on the nth iteration. For an initialization of k_0\,, we show in the Appendix that the expected value of this iteration is

\overline{k[n]}= k_0 +(1-k_0)(1-(1-2\mu)^n)\, (28)

where the overbar denotes expectation. Example simulations are shown in Fig. 2. The endogenous information of the search is I_{\Omega} = \;L\, bits. Let us estimate that this information is achieved by a perfect search in G generations when \overline{k[G]}= \alpha L\, and \alpha\, is very close to one. Assume k_0 =\;\beta L\,. Then

G = \frac{\log(1-\alpha)-\log(1-\beta)}{\log(1-2\mu)}\,.

To show what? That this is a simple birth process? That is absurd, as a look at Fig. 2 shows. It is a birth process - for small \mu\,, but it is not a simple one. But that is not what the calculations are about: it's an estimation for the average number of generations it takes to complete the search. Using their appendix, I would have estimated this number by

 \mathbf{E}(G) = \frac{1}{2\mu} \sum^{L-1}_{k = \beta L} \frac{1}{L-k}\,=\frac{1}{2\mu} \sum^{(1-\beta)L}_{k=1} \frac{1}{k}\,= \frac{\mathcal{H}_{(1-\beta)L}}{2\mu}\,. The expected number of queries would be two times of this - as there are two children in each generation:

\mathbf{E}(Q) = \frac{\mathcal{H}_{(1-\beta)L}}{\mu}\,

In the end, it doesn't make much of a difference, as \mathcal{H}_{(1-\beta)L} \approx \ln((1-\beta)L)\,.

BTW, it's not complicated to make a similar approximation for an alphabet of N instead of 2 letters:

\mathbf{E}(G) = \frac{N \mathcal{H}_{(1-\beta)L}}{2 \mu}\, \Rightarrow \mathbf{E}(Q) =N \frac{\mathcal{H}_{(1-\beta)L}}{\mu}\,.


A reasonable assumption is that half of the initially chosen random bits are correct, and \beta = 1/2\,. Set \alpha =(L - (1/2))/L \,. Then, since the number of queries is Q = 2 G\,, the number of queries for a perfect search (I_+ = I_{\Omega}\,) is

Q  \approx \frac{2 \log(L)}{\log(1-2\mu)}\,. The average active information per query is thus I_{\oplus} \approx \frac{L}{\log(L)} \log(1-2\mu)\, or, since ln(1-2\mu) \approx -2\mu\, for \mu \ll 1\,

I_{\oplus} \approx \frac{2 \mu L}{\ln(L)}\,.

approx. vs. reality for L=100
  1. that should be Q  \approx - \frac{2 \log(L)}{\log(1-2\mu)}\,.
  2. the approximations (both are virtually identical) fall apart very quickly: it isn't sufficient to have \mu \ll 1\,, but \mu \cdot L \ll 1\,. For the example in Fig. 2, Marks and Dembski therefore take \mu = 0.00005\, for L = 100\,.
  3. the factor 2 got omitted, so the formula is about generations, not queries. The correct equation is I_{\oplus} \approx \frac{\mu L}{\ln(L)}\,


Here we have I_{\oplus}\,. But what's about the calculations of the previous paragraph? Remember I_+ =  \log (\frac{1 - F^{\Phi}_{\Delta \kappa} (0)}{1 - F_{\Delta \kappa} (0)})\,? Using the appendix, we get for the current problem

1 - F^{2}_{\Delta \kappa} (0) = 2(L-k)\mu\, and

1 - F_{\Delta \kappa} (0) = (L-k)\mu\;\,, so

I_+ = \log(2/1) = 1\;\,.

If we define success of a single generation as better fitness, the active information of having two children as opposed to one is I_+ = 1\;\,. What does this mean?

For the example shown in Fig. 2, I_{\oplus} \approx 0.0022 b\, per query. Just inserting the parameters of the example in Fig. 2 (L=100,\; \mu = 0.00005\,) into their wrong formula gives you this number. But there is another problem: for the math they made the assumption that half of the initially chosen random bits are correct (\beta = 1/2\,), while all the processes in Fig. 2 start with all of the initially chosen random bits being false (\beta = 0\,).
  1. \beta = 1/2\, \Rightarrow Q \approx 92,100\, and I_{\oplus} \approx 0.00109\,.
  2. \beta = 0\, \Rightarrow Q \approx 106,000\, and I_{\oplus} \approx 0.00094\,.

[edit] Optimization by Mutation With Elitism:

Original Text Annotiations
Optimization by mutation with elitism is the same as optimization by mutation in Section III-F2 with the following change. One mutated child is generated. If the child is better than the parent, it replaces the parent. If not, the child dies, and the parent tries again. Typically, this process gives birth to numerous offspring, but we will focus attention on the case of a single child. We will also assume that there is a single bit flip per generation. Interesting name: Generally, this well-known algorithm is called (1+1)ES. Though the single bit flip is an amusing twist, usually, the mutation procedure works like the one of the last paragraph, i.e., every bit is flipped with a certain probability \mu\,.
For L bits, assume that there are k matches to the target. The chance of improving the fitness is a Bernoulli trial with probability \frac{N-k}{N}\,. The number of Bernoulli trials before a success is geometric random variable equal to the reciprocal \frac{N}{N-k}\,. We can use this property to map the convergence of optimization by mutation with elitism. For discussion’s sake, assume we start with an estimate that is opposite of the target at every bit. The initial Hamming distance between the parent and the target is thus L. The chance of an improvement on the first flip is one, and the Hamming distance decreases to L - 1. The chance of the second bit flip to improve the fitness is \frac{L}{L-1}\,. We expect \frac{L}{L-1}\, flips before the next improvements. The sum of the expected values to achieve a fitness of L - 2 is therefore

\# flips(L-2) = 1 + \frac{L}{L-1}\,.

The whole section doesn't bring any new thoughts, just a new labeling: \# flips\, instead of \overline{k[n]}\,. It's just a shortcut for the math done in the appendix. Let's do the math for the usual mutation procedure, i.e., each letter is flipped with probability \mu\,. Then one would expect \frac{1}{(L-k)\mu}\, tries to get from k correct letters to (k+1) correct letters. Similar to the calculation above, starting with \beta L\, letters in place, we'll need

\mathbf{E}(Q) = \frac{\mathcal{H}_{(1-\beta)L}}{\mu}\, generations (here Q = G\,).

We can even use an alphabet with N letters, and get

\mathbf{E}(Q) = (N-1) \frac{\mathcal{H}_{(1-\beta)L}}{\mu}\,.


Likewise

\# flips(L-3) = 1 + \frac{L}{L-1} + \frac{L}{L-2}\,

or, in general,

\# flips(L-l) = \sum_{m=0}^{l-1} \frac{L}{L-m}\, (29)

It follows that

\# flips(L-l) = L[\mathcal{H}_L - \mathcal{H}_{L-l}]\, (30),

where

\mathcal{H}_L = \sum_{k=1}^L \frac{1}{k} \,

is the Lth harmonic number [3]. Simulations are shown in Fig. 3, and a comparison of their average with (30) is in Fig. 4. For l = L, we have a perfect search and

\# flips(0) = L \mathcal{H}_L\,.


This is shown in Fig. 5.

One flipped letter per phrase translates to a mutation rate of \mu = \frac{1}{L}\, on average. Here we can see that - for small \mu\, - (1+1)ES takes twice the number of generations as (1,2)ES - though the number of queries the same!

2) Optimization by Mutation and 3) Optimization by Mutation With Elitism are hopefully written by different authors - otherwise, the inconsistency of the notation would be embarrassing. And there is no need that the example for section 2) has 100 b, while the example for section 3) has 131 b (why 131?). Or that the algorithm in 2) start with 50 correct bits, while in 3) it starts at zero. Especially hard to understand is that the similarity of

\mathbf{E}(Q_{(1+1)ES}) = \frac{\mathcal{H}_{(1-\beta)L}}{1/L}\, and

\mathbf{E}(Q_{(1,2)ES}) = \frac{\mathcal{H}_{(1-\beta)L}}{\mu}\,

hasn't been spotted.

Since the endogenous information is L bits, the active information per query is therefore

I_{\oplus} = \frac{1}{\mathcal{H}_L}\, bits per query.

You get the same result for the (1+1)ES of the last section if you set \mu = 1/L\,:

I_{\oplus} \approx  \frac{L}{\mathcal{H}_L / \mu}\,=\frac{L}{L \mathcal{H}_L}\,= \frac{1}{\mathcal{H}_L}\,.

[edit] See also


Personal tools
Namespaces

Variants
Actions
Navigation
support
Community
Tools