Sunday, August 29, 2010

Search for Search Paper Finally Out

William A. Dembski informs us at Uncommon Descent that the paper A Search for a Search:Measuring the Information Cost of Higher Level Search (a collaboration with Robert Marks II) is finally published. To things are remarkable about his post:

• The comments are turned off
• It's so restrained - wasn't this paper once announced as a nail to the coffin of Darwinism?

One obvious flaw I found in an earlier draft of the paper is addressed: instead of talking about any searches, they are now talking about searches without repetition.

But I've still a(t least one) problem with this paper, which may be resolved by more careful reading over the next few days. As I wrote to Robert Marks:

I was a little bit irritated that the proof of the HNFLT still uses the
Kullback-Leibler distance, as I can't see how a non-trivial search-space
(i.e., a search spaces for a search existing from at least two queries)
can be exhaustively partitioned in a meaningful way.

Here's is an example I used earlier: Imagine a shell game with three shells where you are allowed to have two guesses. To put it more formally:

• The search space Ω1 is {1,2,3}

In section 2.1. Blind and Assisted Queries and Searches, Dembski and Marks describe how such searches can be construed as a single query when the search space is appropriately defined. They introduce an augmented search space ΩQ, existing from the sequences without repetition of length Q, i.e., the number of queries. In our case:

• The augmented search space Ω2 is {(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)}

Of course, the target has to be changed accordingly to TQ, where TQ ∈ [sic] ΩQ consists of all the elements containing the original target.

So, if in the original game the shell with the pea was No. 1, in our new space, T2 = {(1,2),(1,3),(2,1),(3,1)}. All of this seems to be sensible

Let's have a look at a search strategy, for instance:

• First, look under a random shell
• Second, look under another random shell

By such a strategy, a probability measure is introduced on Ω2, and the probability of a successful search for T2 can be seen immediately: it's |T2|/|Ω2| = 4/6 = 2/3. No surprise here.

In fact, any search strategy can be seen as a measure on ΩQ - and that's what Dembski and Marks are doing in the following. My problem: not any subset of ΩQ can be seen as a reasonable target for a search: The complement of T2 doesn't represent any target in the original space Ω1! And though this set can be measured by the measure introduced above (2/6), this measure doesn't make sense in the context of a search.

And that's what I don't understand about the Horizontal No Free Lunch Theorem (3.2). The first sentence is:

Let φ and ψ be arbitrary probability measures and let T~={Ti}i=1N be an exaustive partition of Ω all of whose partition elements have positive probability with respect to ψ

How can Ω2 partitioned in a sensible way? And why should I try to compare two search strategies on sets which they will never look for?

1. I'm surprised that nobody in the EIL and none of the reviewers noticed the glaring problems with the HFLT that you and others have pointed out. The section simply doesn't make sense.

Eq.(11) looks kind of like a negative Kullback-Leibler distance, but it isn't. It would be if Ψ(T_i) and Φ(T_i) were defined as the probability of an outcome T_i from the space T~, where T~ is a partition of Ω. But Ψ and Φ are defined as the probability of the outcome "success" from the space {"success", "no success"}. Summing Ψlog(Φ/Ψ) over T~ does not give us the negative relative entropy -- it gives us nonsense.

My guess is that Marks or Dembski looked at the definition of active information and thought, "Hey, that's the log-ratio of two probabilities. If we sum it over the sample space, weighted by one of the probabilities, we get relative entropy!" But they forgot that Ψ and Φ are not probabilities over a partition of Ω.

2. Yes, Dembski and Marks cannot say that we didn't try to point out the problems with the HFLT. But I was already a little bit disheartened a couple of weeks ago when I read Dembski's comment at Uncommon Descent:
Robert Marks is the corresponding author on the papers in question. It is appropriate for him to be the contact person for DiEb and anyone else about them. That said, I’m not sure where you’re getting the impression that Prof. Marks has made any concessions to DiEb. Is DiEb himself suggesting to you that major retractions are on the way? I meet with Prof. Marks weekly and the impression I get from him is that you all are not to be taken very seriously.

3. We had an exchange in email back in November and December about all this, and I thought a quick summary of my conclusions would be appropriate here. I suspect their theorems are fixable -- they are just doing a version of the No Free Lunch theorem and making the point that

* if you assign fitnesses randomly to genotypes, the space is so jaggy that natural selection gets mostly nowhere.
* Therefore, they say, if NS succeeds one is using a much-smoother-than-randomly-assigned fitness surface, and the Designer must have chosen that out of al possible fitness spaces,
* and here is this information calculation of how much information was built in by the Designer.
* So natural selection is not creating any information, it is already lying around courtesy of the Designer,
* natural selection is just putting it into the genome.