Thursday, October 22, 2009

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 (φ1, φ2, ..., , φ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., Φ := (φ1, φ2, ..., , φ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.