Work is not information

Suppose you are searching for a DNA sequence that translates to a protein with certain properties. To simplify matters, let's say you know magically that the sequence is 300 bases in length. You might roll a fair four-faced die 300 times to guess a sequence, and then conduct an experiment to see if the guess is correct. Clearly, there is no knowledge of the specific problem manifest in the die-rolling procedure.

Now let's say you do 1000 repetitions of the die-rolling procedure, and conduct 1000 experiments to check the randomly generated DNA sequences. The probability of "hitting the target" with a "query" of nature increases. But does this mean that you exploited more knowledge about the problem than you did previously? Of course not. It means only that you did more work.

In their recently published article, Conservation of Information in Search: Measuring the Cost of Success, Bill Dembski and Bob Marks sometimes measure work and call it active information. They claim,

Active information captures numerically the problem-specific information that assists a search in reaching a target.

But in Section III.A they demonstrate otherwise:

Multiple queries clearly contain more information than a single query. Active information is therefore introduced from repeated queries.

Now wait just a gol-dern minute, Billy Bob! The first sentence says that a procedure doing more work yields more information about the solution to the problem than a procedure doing less work. The second says that the procedure doing more work has more more information about how to solve the specific problem than a procedure doing less work. The error here is not just equivocal use of the word information. The authors go on to calculate a gain in active information for repetition of an utterly uninformed procedure.

Dembski and Marks commit the same errors in Section III.F.1, where they show that increasing the number of offspring in an evolutionary search increases the probability of obtaining an offspring more fit than the parent. To make this probability gain into active information, they redefine the search as just one generation of the evolutionary search they originally considered.

The fact that you can gain information by doing work does not imply that work is itself information.

[1/2/2010: I contradicted myself in saying "repetition of an utterly uninformed procedure" after predicating that "you know magically that the sequence is 300 bases in length." In a forthcoming post, I will explain that what Dembski and Marks call the endogenous information of a search problem seems endogenous only if one ignores magical circumscription of the solution space.]

Blunder in the new Dembski-Marks paper

The recently published conference paper of Dembski and Marks, Bernoulli’s Principle of Insufficient Reason and Conservation of Information in Computer Search contains an enormous, undebatable, and embarrassing error in the argument regarding the so-called "search for a search."

Search algorithms explore a finite space of solutions Ω. An algorithm basically selects a solution in Ω, examines the solution, and decides which solution to select next. It repeats this until it has made Q selections. It is crucial to the arguments of Dembski and Marks that search algorithms have the capacity for randomizing their decisions. To randomize a decision is to base it, at least in part, on inputs from a random source. (Think of flipping a fair coin repeatedly and feeding the sequence of outcomes into a computer program. The inputs would permit the program to randomize its decisions.)

Dembski and Marks believe that people search for search algorithms in a higher-order space Ω₂. They write,

Let Ω₂ be the finite space of all search algorithms on the search space Ω.

The word I've emphasized is wrong, wrong, and wrong. The set of all randomized search algorithms is infinite, not finite. Section III.A and the "proof" of Equation (7) in Appendix B are based on a false premise.

Consider making just one randomized decision between alternative solutions ω₁ and ω₂ in Ω, with the probability of choosing ω₁ equal to p. The set of all possible values for p is infinite, and therefore the set of all randomized algorithms for making the decision is infinite.

---

Some technical details

For a fixed representation of randomized algorithms (e.g., probabilistic Turing machines reading i.i.d. uniform bits from an auxiliary tape), the set of probabilities p possible in a randomized dichotomous decision is countably infinite. There is no upper bound on the size and running time of the randomized decision algorithm.

The set of probabilities [0, 1] is uncountably infinite. Thus, while every randomized search algorithm implements a random search process, vanishingly few random search processes correspond to randomized search algorithms. Relatively few randomized search algorithms are fast enough and small enough to solve a problem in practice. We humans necessarily prefer small randomized search algorithms that make decisions rapidly.

Bad theology and bad science

[Formerly on the Sidewiki at Uncommon Descent:]

The founder of this blog, William A. Dembski, has proclaimed that "intelligence creates information" [source]. He and other proponents of intelligent-design creationism (IDC) hold that information is physical, like matter and energy, and that intelligence is purposeful and natural, though immaterial and unobservable. IDC calls for science to consider the possible physical existence of something immaterial and unobservable that purposefully creates physical stuff out of nothing.

It is remarkable that proponents of IDC, most of whom believe in a supernatural Creator, attribute the design of living things to natural intelligence. Until recent years, a more coherent IDC held that intelligence was "non-natural." The view was unlikely, however, to make its way into science curricula of public schools, given that federal case law prohibits instruction in the supernatural. Evidently IDC strategists realized this, and shifted to intelligence is natural, but not material as a matter of expedience. No leading proponent stepped forward to announce the change in stance and offer an explanation. It makes a muddle of IDC, both logically and theologically.

All who oppose IDC, be they theistic, non-theistic, anti-theistic, deistic, or agnostic, agree that scientific explanations cannot include the famous "then a miracle occurs" step — even those who believe that miracles really do occur. And a claim that an invisible, immaterial entity has created something physical with evident purpose is indeed a claim of a miracle.

I think you should be more explicit here in step two.

Scientists work to explain the wonders of nature, not "unexplain" them by accepting that they are miracles due to purposeful intervention of something invisible. The history of science is full of cases in which the seemingly unexplainable was explained. As a practical matter, scientists can never give up trying to show that the wondrous is not miraculous.

Source bluffing by Dembski and Marks

In their September 2009 article in IEEE SMC-A, Dembski and Marks cite a book outside the literature on evolutionary computation as their source for the (1,2)-EA [evolutionary algorithm] which they do not identify as a (1,2)-EA. I had guessed that they had googled to locate a source with a title that would not telegraph to editors and reviewers, "This is an evolutionary algorithm."

It turns out that my guess was not so bad. DiEb has located the book online. Furthermore, s/he has found that the evolutionary algorithm it presents is quite different from the one that Dembski and Marks analyze. Is it "by chance or by design" that Dembski and Marks neglect to specify where in the book the algorithm is presented?

DiEb slyly points out that Dembski and Marks demonstrate in another book-reference that they know to give the range of pages... though they give the wrong range.

Join together to report scholarly misconduct?

Edit (9 Oct 2009): Friends and respected acquaintances have persuaded me to rebut the article of Dembski and Marks in the peer-reviewed literature, and not to fuel the "Expelled" propaganda campaign of the intelligent design movement by lodging complaints of scholarly misconduct.

In my opinion, Dembski and Marks engaged in scholarly misconduct in their article Conservation of Information in Search: Measuring the Cost of Success. I will respond by lodging complaints with the academic institutions that employ the authors. I had planned on supplying readers with contact information and encouraging them to send their own letters of complaint. Now I believe that letters with many signatories would command more respect.

At most academic institutions, there are established procedures for responding to credible allegations of scholarly misconduct by faculty members. Allegations are typically reviewed by committees comprised mostly of ordinary faculty members — people who generally want to make fair decisions. Perhaps Dembski is safe. It would be nonetheless interesting to see a "secularized" Baptist university sanction one author, and a Baptist seminary let the other off the hook.

I must emphasize that the issue is not ID per se. Deceptive manipulation of a scholarly forum to advance any socio-political agenda whatsoever is wrong. As some of you know, I actually protested Baylor University's refusal to let Bob Marks display his "Evolutionary Informatics Lab" webpages with the standard disclaimer promulgated by the American Association of University Professors. What animates me to demand academic freedom is precisely what animates me to demand academic integrity.

Technical language goes nowhere with administrators and academic integrity committees. Furthermore, people may have a hard time seeing that Dembski and Marks misconstrued Dawkins. Here are some transgressions that are relatively easy to establish:

1. The authors analyze two closely-related computational methods without giving their conventional names, without indicating that they have been analyzed many times in the literature, and without citing prior analysis. This is egregious in light of the fact that their analyses did not appear in the paper until I explained one of the methods to Marks, provided its name, suggested analyzing it, and indicated that there were many analyses of it in the literature.
2. The authors mathematically formalize a computational method described informally in a popular-science book by Richard Dawkins, and attribute their formal method to Dawkins. That is, they mention neither that they are disambiguating an ambiguous text, nor that their disambiguation is highly controversial. This is egregious in light of the fact that Dembski has offered elsewhere several distinct interpretations of the text, and has emphasized its ambiguity.
3. The authors falsely attribute the term partitioned search, an apt name for their own formalization, to Dawkins. The attribution heightens the impression that they are relating straightforwardly Dawkins' precise meaning.

Speaking to motivation is tricky, but necessary, I think:

1. The authors submitted the article to a broad-scope journal with editors unlikely to recognize methods coming from the field of evolutionary computation. They evidently did not want to draw attention to the fact that parts of the paper needed the scrutiny of specialists in evolutionary computation. One of the analyses is a rehash of old results, and the other has no apparent utility in engineering.
2. Dembski has engaged in what he calls "cultural war" for many years, and the prominent atheist and evolutionary biologist Dawkins is his arch enemy. Dembski's socio-political ends take precedence over academic honesty in the article. He could not score a categorical hit on Dawkins without unequivocally representing Dawkins' work as something he and Marks knew how to analyze. In fact, the dubious interpretation makes for a very simple analysis. Following publication of the article, Dembski revealed his agenda on the Web:

   Our critics will immediately say that this really isn’t a pro-ID [intelligent design] 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.

   But soon after that, Dembski emphasized the ambiguity of Dawkins' description of his computational method, and decided that Dawkins used a method other than the one he and Marks analyzed — a method much harder to analyze. He also reported that he had communicated recently with Dawkins on the matter, and this brings to the fore the question of why he did not ask Dawkins for clarification prior to publication of the article. Evidently getting an unqualified "critique" of Dawkins through peer review was more important than honestly reporting that he and Marks had analyzed a mathematically convenient interpretation of Dawkins.

Some rumination

Dembski and Marks write, "Partitioned search [12] is a 'divide and conquer' procedure best introduced by example." Italicizing the term and placing a reference immediately after it is significant. By convention, this indicates that the term comes literally from the indicated source. There is, of course, no instance of "partitioned search" in reference [12], The Blind Watchmaker. Students might claim plausibly that they did not know the convention, but not a pair of highly experienced scholars.

There is utterly no way to warp Dawkins' description of how his Weasel program operated into D&M's partitioned search. Perhaps I'm underestimating the academic integrity committees. If they saw Dawkins' description of the Weasel program juxtaposed with D&M's description of partitioned search, they might sense that something's rotten in Texas.

How would an honest and responsible scholar go about disambiguating an algorithm in a popular science book? Obviously he would contact the author, if possible. Dembski has communicated with Dawkins plenty of times in the past, and has communicated with him about the Weasel program since publication of the article. Considering the controversy over the Weasel program, there was absolutely no justification for excluding Dawkins from the loop. This lends credence to the claim that Dembski and Marks chose to engage in false attribution because it served an ulterior purpose.

D&M did not know how to analyze the active information of Dawkins' algorithm, so they pinned on Dawkins an algorithm they felt was "close enough," and that they knew how to analyze. (I am sure that they did not know how to analyze Dawkins' algorithm because the article includes an analysis of a restricted form of it.) Whether partitioned search was "close enough" or not is irrelevant. The issue is that D&M had no justification for flat declaration that it was Dawkins' algorithm.

Back to the task

It would be good, I think, to mail a cover letter, a synopsis of the allegations like that I provided above, and somewhat detailed evidence. For instance, I would quote from my email to Marks, as in my last entry. It would be nice if Wesley were to provide a synopsis of Dembski's weaseling on the Weasel. I can give a succinct and simple explanation that D&M analyzed the (1,2)-ES and the (1+1)-ES, as well as a demonstration that they needed to keep reviewers from looking at prior analyses of ES's.

What I have in mind is to prepare the materials, put them on display for comments, revise, and then solicit signatures. I'd like to hear if you think many people would join in if I prepared something along the lines of what you've seen here. Should I just go it alone?

ADDENDUM

See Jeffrey Shallit's remarks on acknowledging priority at Recursivity.

Resolving a moral dilemma

I made a promise to Bob Marks that I would not divulge my correspondence with him regarding drafts of the paper that IEEE SMC-A published last month. But I did not know that he and Dembski would resort to trickery to get the paper through peer review, and, after considerable agonizing, I've decided that the better course is to break my word.

(Bob has done a great deal of admirable work in computational intelligence, and I don't count him as a personal enemy. In fact, I recently joined with him in recommending an IEEE member for elevation to a higher rank.)

This is from a July 31, 2008, note that went, at his request, to his Yahoo address rather than through the (no doubt archived) Baylor email system:

Dawkins' weasel program implements a (1, λ)-ES, not partitioned search. In each generation, there are λ offspring. All points in the parent string are subject to mutation in all generations. The fittest of the offspring replaces the parent. Fitness is the number of positions containing correct letters. It is possible for fitness of the parent to decrease from one generation to the next. The mutation probability is "low," so offspring are concentrated in the neighborhood (naturally defined in terms of Hamming distance) of the parent, not uniformly distributed on a subspace of the solution space as you indicate.

I think your analysis of partitioned search makes for a good example, but you should not suggest in any way that you're analyzing Dawkins' algorithm. I would like to see you change the target sentence. In any case, the Bard (and Dawkins) wrote "methinks" as one word, not two.

It would be interesting to see an analysis of the active information of the (1, λ)-ES Dawkins used. There are plenty of published analyses of the (1, λ)-ES as a Markov process for λ = 1 [actually 2]. I'm not sure about greater values of λ. What you need is the probability that the process enters the state corresponding to the target string in Q or fewer time steps, expressed as a function of mutation probability and λ. Of course, you could fall back on simulation.

Marks did not respond to this particular note, but "ME*THINKS" turned into "METHINKS" in later drafts, and section III-F-2 of the published article addresses a (1,2)-ES [evolution strategy; sometimes it's instead "EA" for "evolutionary algorithm"] solving a restricted form of the problem solved by the Weasel program. Furthermore, section III-F-3 deals with the closely related (1+1)-ES.

It's not plausible, I think, that Marks ignored my note - he's responded to others since - and that he and Dembski subsequently happened to think of analyzing the evolutionary algorithms. The article neither gives the established names of the algorithms nor cites prior analyses in the literature. You have a good idea now of why I consider this to be academic misconduct.

Never look a gift weasel in the mouth

At least ten years ago, William Dembski misunderstood the description of the Weasel program in Richard Dawkins' 1986 book The Blind Watchmaker. (Take it from an experienced teacher of computer science: Some mathematicians cannot think algorithmically.) Many people have tried to persuade him that there is only one reasonable reading in the context of a book on biological evolution. His response has been to ignore context, and to play up ambiguity in his attempts to save face.

Now Dembski reports that "Oxfordensis" emailed him two Weasel programs, claiming that Dawkins ran Weasel1 in preparing the book, and Weasel2 for a demonstration in a 1987 TV show based on the book. The programs accord well with Dembski's misconceptions, so he has posted gelatinous "analysis" leading to the conclusion that "unless further evidence is presented, ... the single-mutation algorithm implemented by WEASEL1 is the one used by Dawkins in TBW."

I will save for another day the details of how Dembski got himself speared by looking a gift weasel in the mouth. Suffice it to say that both programs are easy to model formally as Markov chains, and that I, unlike Dembski and his colleagues at the Evolutionary Informatics Lab, actually bothered to do the math. (Furthermore, I translated the Weasels from Pascal to C++, and cross-checked my models and programs.) Dawkins gives an example run in which the number of correct characters in the parent goes from 3 to 22 in 19 generations. Dembski is perfectly happy to say that this is what we would expect from Weasel1. In fact, the probability that the program improves the parent so quickly (as quickly as it possibly can) is just .037.

It is quite unlikely that Dawkins used Weasel1 in preparing his book. The probability that a Weasel program like that described in Wikipedia (200 offspring per generation, mutation rate of .05) goes from 3 to 12 correct characters in generations 1 to 10, and from 12 to 22 correct characters in generations 10 to 20, is in the range of .05 to .06. (I am working on a Markov model that will yield a precise probability.) The likelihood of the conventional Weasel program, though low, is greater than that of the apocryphal Weasel1.

We cannot regard "Oxfordensis" as a reliable source of information on the program(s) Dawkins used. Thus, even though 32% of Weasel2 runs obtain the target sentence as quickly as the run in the TV show does, we must worry about a hoax. I will have more to say later as to whether a conventional Weasel program is more likely than Weasel2 to yield the run in the TV show.

Technical Details

Markov model source code: main.cpp. Modify constants according to comments, compile, and run. IOU a LaTeX document explaining the math behind the code.

Output files: weasel1.txt, weasel1-TBW.txt, weasel2.txt [8 MB]. The long lines of numbers give the probabilities of having 0 characters correct, 1 character correct, ..., and 28 characters correct after the specified number of transitions. In the "TBW" output, the initial state corresponds to generation 1, not generation 0 as in the other outputs. Thus 9, 19, and 42 transitions yield the probability distributions for generations 10, 20, and 43, respectively.