Tuesday, August 31, 2010

Horizontal No Free Lunch Theorem

In my previous post I criticized the Horizontal No Free Lunch theorem for searches consisting of at least two queries. But even in the case of a single assisted query, I can't get my head around it.

Dembski and Marks define an assisted query as any choice from Ω1 that provides more information about the search environment or candidate solutions than a blind search. As an example, they give for instance, we might imagine an Easter egg hunt where one is told “warmer” if one is moving away from an egg and “colder” if one is moving toward it.

The ultimate assisted search is no search at all, the unveiled Easter egg. So, imagine a blind (A), a drunken (B), and a seeing, sober (C) chess-player, and ask them to locate the White Dame (♕) on a chess board. (A) will be find it with a probability of 1/64, (C) with a probability of 1, and lets assume for (B) a probability of 1/2.

Then (A) represents the blind search, (B) an assisted search and (C) what the authors call a perfect search on our search space Ω = {a1,a2,....,h8} (|Ω|=64).

Imagine that ♕ is positioned on a1, so T1 = {a1}. Then we have three probability measures, αa1, βa1, and γa1 for each one of our players, which allow us to calculate the probability for each one to find T1:
  • αa1(T1)= 1/64

  • βa1(T1) = 1/2

  • γa1(T1) = 1

And we can calculate - according to (3.1) (10) the active information of these measures for various sets and combinations, e.g.
I+a1a1(T1)){a1} = log21/2 - log21/64 = 5.

So, the drunken player has more active information on the whereabouts of ♕ than the blind one.

I+a1a1(T1)){b1} = log20 - log21/64 = -∞

A more surprising result: if ♕ is on b1, but (C) sees it on a1, he is much less informed than (A).

But of course, γa1 isn't the right measure if ♕ is on b1, we would expect γb1: the idea of an assisted search seems to be that it assists to the right direction - for our Easter egg hunt: if your helper directs you always to the same place, whether there is an egg or not, he is no helper indeed, he's just a nuisance:

Trivially, a search helped in this way can't be differed from an unassisted search.

But I'm afraid that exactly what W. Dembski and R. Marks do in their Horizontal No Free Lunch Theorem: let's take the partition T~ = {{a1},{a2},...,{h8}} of our Ω1 above. What does

Σ αa1{Ti} × I+a1a1){Ti}

mean? Nothing else than that our seeing, sober man errs 63 times out of 64 when looking for ♕. That just doesn't make sense.

The meaningful expression would have been:

Σ αTi{Ti} × I+TiTi){Ti}

And while the first sum adds up to -∞ the latter one is not negative at all: it's just 6.

nota bene: I think this is the idea behind Rob's (R0b?) comment to my previous post. So, thanks Rob!

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?