Draft of a letter to JACIII

In their article The Search for a Search¹ the authors William Dembski and Robert Marks seem to assume that any search on a space induces a probability measure on the search space, as they write in section 3.1 (Active Information):

"Let U denote a uniform distribution on Ω characteristic of an unassisted search and φ the (nonuniform) measure of Ω for an assisted search. Let U(T) and φ(T) denote the probability over the target set T ∈_[sic]Ω."

Such an induced measure gives the probability to find a subset T of Ω when performing the corresponding search. But for the assisted searches mentioned in the text (a "perfect search" - "indicating an assisted search guaranteed to succeed" - and another search "indicating an assisted search guaranteed to fail"), such probability measures obviously do not exist! Thus these cases are not covered by their Theorem 1 (Horizontal No Free Lunch), as the Kullback-Leibler-distance is defined only for probability measures.

But perhaps the authors intended their theorem only to be valid for those searches which induce a measure on the search space - indeed, they use the term uninformed assisted searches when describing their results. Unfortunately, this term is not defined - neither in the current text, nor in their previous publications Conservation of Information in Search - Measuring the Cost of Success² or Efficient Per Query Information Extraction from a Hamming Oracle³.

Unfortunately, even in this case, the theorem does not work: assuming the easiest nontrivial case of guessing an element of a set with two elements (tossing a coin), Ω = {head, tail}, the two strategies naming an element at random (uniform distribution on $\backslash Omega\backslash ,$) and sticking with one element (dirac distribution) give the same success rate for a fair coin. The same result occurs when averaging over the probability of showing head (assuming that this probability is uniformly distributed on [0,1]), contradicting the statement of William Dembski and Robert Marks:

"Because the active entropy is strictly negative, any uninformed assisted search (φ) will on average perform worse than the baseline search". (Highlighting mine)

In my opinion, the fundamental problem stems from identifying the search space Ω_(n) and the space of (deterministic) searches. This is doubtless elegant, but does not seem to work.

References:

¹W. A. Dembski and R. J. Marks II, "The Search for a Search: Measuring the Information Cost of Higher Level Search," Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol. 14, No. 5, pp. 475-486, September 2010

²W. A. Dembski and R. J. Marks II, "Conservation of Information in Search: Measuring the Cost of Success," IEEE Trans. on Systems, Man and Cybernetics A, Systems and Humans, Vol. 39, No. 5, pp. 1051-1061, September 2009

³W. Ewert, G. Montanez, W. A. Dembski, and R. J. Marks II, "Efficient Per Query Information Extraction from a Hamming Oracle," Proc. of the 42nd Meeting of the Southeastern Symposium on System Theory, IEEE, University of Texas at Tyler, pp. 290-297, March 7-9, 2010

What is wrong with public debate?

R. Marks just informed me of his policy not to engage in correspondence with anyone publicly critical of him or his work and that independent of the validity or invalidity of the details of the exchange, these things are best discussed thoroughly before any public pronouncements.

Indeed, I wrote to R. Marks about my concerns regarding the Horizontal No Free Lunch theorem. And I sent the links to my blog entries. And these blog entries are critical of his work. But what is the problem?

1. my blogging could be totally unsubstantiated. In this case he really should ignore it - for any valid theory, you'll find thousands of idiots blogging about imagined problems.
2. my entries could be well-thought through, but ridiculously wrong. In this case, I made a fool out of myself in public- and he could criticize me for doing so.
3. there maybe something true in my blog entries: if these grains of truth aren't buried in filthy language, insults, etc., why should they be ignored?

I just don't get it.

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 Ω₁ 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 T₁ = {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 T₁:

• α_a1(T₁)= 1/64


• β_a1(T₁) = 1/2


• γ_a1(T₁) = 1

And we can calculate - according to (3.1) (10) the active information of these measures for various sets and combinations, e.g.
I₊(β_a1|α_a1(T₁)){a1} = log₂1/2 - log₂1/64 = 5.

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

I₊(γ_a1|α_a1(T₁)){b1} = log₂0 - log₂1/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 Ω₁ above. What does

Σ α_a1{T_i} × I₊(γ_a1|α_a1){T_i}

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{T_i} × I₊(γ_Ti|α_Ti){T_i}

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!

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 Ω₁ 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 Ω₂ is {(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)}

Of course, the target has to be changed accordingly to T_Q, where T_Q ∈ [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, T₂ = {(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 Ω₂, and the probability of a successful search for T₂ can be seen immediately: it's |T₂|/|Ω₂| = 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 T₂ doesn't represent any target in the original space Ω₁! 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~={T_i}_i=1^N be an exaustive partition of Ω all of whose partition elements have positive probability with respect to ψ

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

A silent death of the Horizontal no Free Lunch theorem

The only reply I got for my concerns regarding W. Dembski's and R. Marks's article The Search for a Search - and its Horizontal No Free Lunch theorem - was an email from R. Marks, stating that he'd look into it.
Now, two weeks later, R. Marks took the article from his list of publications. The Evolutionary Informatics lab has still an announcement, basically the abstract of the article:

Many searches are needle-in-the-haystack problems, looking for small targets in large spaces. In such cases, blind search can stand no hope of success. Success, instead, requires an assisted search. But whence the assistance required for a search to be successful? To pose the question this way suggests that successful searches do not emerge spontaneously but need themselves to be discovered via a search. The question then naturally arises whether such a higher-level “search for a search” is any easier than the original search. We prove two results: (1) The Horizontal No Free Lunch Theorem, which shows that average relative performance of searches never exceeds unassisted or blind searches. (2) The Vertical No Free Lunch Theorem, which shows that the difficulty of searching for a successful search increases exponentially compared to the difficulty of the original search.

The given link doesn't lead to the article any longer, but to their earlier opus Conservation of Information in Search - neither the term vertical nor the term horizontal appear in this article.

In his first podcast with Casey Luskin, W. Dembski promised that this article was something like a nail to the coffin of evolution. I assume that W. Dembski will explain how he was wrong with this assessment in his next interview...

One if by land, and two if by sea...

Or, in the Intelligent Design version: Two lanterns contain the same information as one lantern, ergo, they come by land...

Horizontal No Free Lunch Theorem

You keep using that word. I do not think it means what you think it means

Inigo Montoya


In their upcoming paper The Search for a Search: Measuring the Information Cost of Higher Level Search W. Dembski and R.Marks introduce a Horizontal No Free Lunch Theorem.

At Uncommon Descent, I tried to reach W. Dembski with the following post which is - of course - awaiting moderation at the moment.

The Horizontal No free Lunch Theorem doesn't work for a search of length m > 1 for a target T ⊆ Ω:

Let Ω be a finite search-space, T ⊆ Ω the target - a non-empty subset of Ω. A search is a (finite) sequence of Ω-valued random variables (φ₁, φ₂, ..., , φ_m). A search is successful, if φ_n ∈ T for one n, 1 ≤ n ≤ m.

I suppose we do agree here. Now, we look at a search Φ as a Ω^m-valued random variable, i.e., Φ := (φ₁, φ₂, ..., , φ_m).

When is it successful? If we are still looking for a T ⊆ Ω we can say that we found T during our search if

Φ ∈ Ω^m \ (Ω \ T)^m

Let's define Θ as the subspace of Ω^m which exists from the representations of targets in Ω, i.e.,

Θ := {Ω^m \ (Ω \ T)^m|T non-empty subset of Ω}

Obviously, Θ is much smaller than Ω^m.

But this Θ is the space of feasible targets. And if you take an exhaustive partition of Θ instead of Ω^m in Theorem III.1 Horizontal No Free Lunch, you'll find that you can indeed have positive values for the active entropy as defined in the same theorem.

But that's not much of a surprise, as random sampling without repetition works better than random sampling with repetition.

But if you allow T to be any subset of Ω^m, your results get somewhat trivial, as you are now looking at m independent searches of length 1 for different targets.

The searches which you state as examples in this paper and the previous one all work with a fixed target, i.e., elements of Θ. You never mention the possibility that the target changes between the steps of the search (one possible interpretation of taking arbitrary subsets of Ω^m into account).

So, I'm faced with two possibilities:

1. You didn't realize the switch from stationary targets to moving ones when you introduced searching for an arbitrary subset of Ω^m
2. You realized this switch to a very different concept, but chose not to stress the point.