The Search for a Search - Measuring the Information Cost of Higher Level Search/Critique of the Draft
The following is a critique of a previous draft of the paper. Some of the problems mentioned here were rectified, others seems to be still there...
Original Text | Annotations |
---|---|
Abstract—Many searches are needle-in-the-haystack problems, looking for small targets in large spaces. In such cases, blind search stands 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 idea of the annotations is to show the problems in this article of Dembski and Marks, problems which seem to lead to a erroneous formulation of the Horizontal No Free Lunch Theorem and a fault in its proof. An example ( Shell Game ) is constructed on which Dembski's and Marks's theorem doesn't work. |
Index Terms — No Free Lunch Theorems, active information, active entropy, assisted search, endogenous information |
Section I. Introduction (annotated)
Original Text | Annotations |
---|---|
Conservation of information theorems [15], [44], especially the No Free Lunch Theorems (NFLT’s) [28], [51], [52], show that without prior information about the search environment or the target sought, one search strategy is, on average, as good as any other. | There is a condition for a search-strategy in the No Free Lunch Theorems to be on average, as good as any other: it has to be a search without repetition. The original paper are quite explicit in this regard, and it seems to be clear - you can construct a worse search by looking at the same place each time. So, though this seems to be obvious, it is a crucial point for the evaluation of the paper of Marks and Dembski. |
Accordingly, the difficulty of an unassisted—or blind—search problem [9] is fixed and can be measured using what is called its endogenous information. | What is called endogenous information? This should read: what Marks and Dembski call endogenous information..., as they invented this phrase in their previous paper. For a finite search space Ω and a subset T - the target - this is ![]() |
The amount of information externally introduced into an assisted search can then be measured and is called the active information of the search [33]. Even moderately sized searches are virtually certain to fail in the absence of information concerning the target location or the search space structure. Knowledge concerning membership in a structured class of problems, for example, can constitute search space structure information [50]. | It isn't directly measured, it's more the other way round: For a succesful search, Dembski and Marks define the active information as the endogenous information.... |
Endogenous and active information together allow for a precise characterization of the conservation of information. |
... at least in the sense that for a successful search, the endogenous information at the beginning of the search equals exactly - but not surprisingly - the active information at its end... |
The average active information, or active entropy,of an unassisted search is zero when no assumption is made concerning the search target. If any assumption is made concerning the target, the active entropy becomes negative. This is the Horizontal NFLT. It states that an arbitrary search space structure will, on average, result in a worse search than assuming nothing and simply performing an unassisted search. | This active entropy is quite a strange animal and will be defined in this article. The conclusion of the Horizontal NFLT seems to be wrong, and the failure in its reasoning will be discussed later. |
The Horizontal NFLT addresses how changing a search space structure affects average search performance, but it does not address the difficulty of finding a search capable of locating a particular target. That is the job of the Vertical NFLT, which characterizes the information costs of searching higher-level search spaces for successful lower-level searches. Such higher-level searches are amenable to the same endogenous/active information analysis as lower-level searches. | The Vertical NFLT won't be discussed here. |
As one might expect, no active information in the “search for a search” translates to zero active information in the lower-level search (which means that, on average, the lower-level search so found cannot do better than an unassisted search). This result holds for still higher level searches such as a “search for a search for a search” and so on. Thus, without active information introduced somewhere in the search hierarchy, none will be available for the original search. If, on the other hand, active information is introduced anywhere in the hierarchy, it projects onto the original search space as active information. |
Consider therefore the minimally acceptable active information required for a successful search. In searching for such a search, a higher-level search will need to introduce a certain amount of active information. How much? According to the Vertical NFLT, the cost of this higher-level active information increases exponentially with respect to the active information required in the lower-level search space. The Vertical NFLT therefore reveals that a “search for a search” yielding minimally acceptable active information in the original search space is a much more difficult problem than simply searching the original space directly. Based on computational difficulty, one should therefore generally choose an arbitrary unassisted search over “searching for a good search.” |
That sounds - well - absurd at first. For a successful search, the minimally acceptable active information is the whole endogenous information, by definition... |
Section II. Information in Search (annotated)
Original Text | Annotations |
---|---|
All but the most trivial searches require information about the search environment (e.g., smooth landscapes) or target location (e.g., fitness measures) if they are to be successful. Conservation of information theorems [15], [28], [44], [51], [52] show that one search algorithm will, on average, perform as well as any other and thus that no search algorithm will, on average, outperform an unassisted, or blind, search. But clearly, many of the searches that arise in practise do outperform blind unassisted search. How, then, do such searches arise and where do they obtain the information that enables them to be successful? | In fact, only the most trivial search (Searching for the haystack in a haystack) requires no fitness measures. At least, if you care for a successful search. |
A. Unassisted Search
Original Text | Annotations |
---|---|
Exhaustive search, random sampling, random walks, and searches along Brownian motion paths all exemplify blind search, a.k.a. unassisted search. In a blind or unassisted search, no prior information concerning the location of the target or the structure of the search space is available. Such a search therefore assumes a uniform probability distribution on the search space. Given any knowledge about the target location or the search space structure constitutes information and voids this assumption [33]. | Random walks and searches along Brownian motion do assume prior information of the structure of the search space: you have to have a concept of neighbours, or nearness, i.e., some (not discrete!) metric. |
For example, given a deck of 52 cards face down and the task of choosing the A♠, and given no information about the location of the cards or how they are laid out, one rightly assumes each card has the same probability of turning up the A♠. This uniformity assumption is Bernoulli’s principle of insufficient reason, which states that in the absence of any prior information, “we must assume that the events ... have equal probability” [2], [36]. Uniformity is equivalent to the assumption that the search space is at maximum informational entropy. | Wow, nothing wrong here! Minor beef: The references - Bernoulli's ars coniectandi - that's utterly pretentious. And the second one, Papoulis's Probability, Random Variables, and Stochastic Processes hints to pages 537-542 - again - where you find nothing about an uniformity assumption. |
B. Assisted Search
Original Text | Annotations |
---|---|
De?ne an assisted search as any procedure that provides more information about the search environment or candidate solutions than a blind search. The classic example of an assisted search is the Easter egg hunt in which instead of saying “yes” or “no” to a proposed location where an egg might be hidden, one says “warmer” or “colder” as distance to the egg gets smaller or bigger. This additional information clearly assists those who are looking for the Easter eggs, especially when the eggs are well hidden and blind search would be unlikely to ?nd them. Information about a search environment can also assist a search. A maze that has a unique solution and allows only a small number of “go right” and “go left” decisions constitutes an information-rich search environment that helpfully guides the search. | Just to stress a point: the Easter eggs are hidden first, then searched. They don't pop up somewhere during the search - or magically change their position. That's a search as it is generally understood. Of course, there is nothing wrong with a moving target: But you should say so if you are looking for one. Or when you change the rules of the search: for instance, if you expect that an egg is found at each step of the process (quite absurd, isn't it?) |
Suppose now denotes an arbitrary search space. In general, assume is a compact metric space with metric D, though for most theorems and calculations assume is finite (in which case D is a discrete metric). Let ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
Just checking: ![]() ![]() ![]() ![]() ![]() |
If we now let ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
And come the problem: Without any warning R. Marks and W. Dembski state that they are now looking at arbitrary subsets ![]() ![]() ![]() ![]()
or that
But most subsets of R. Marks and W. Dembski don't talk about a search with n steps any longer in any meaningful way, they are describing a one-step search in a bigger space, i.e., |
But all these tildes are superfluous. Dropping them, we see that the probabilistic connection between a blind search and an assisted search can be entirely characterized in terms of a search space ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
Yes, you can drop the tildes. But you have to be careful. And the next paragraph shows that you are not... |
For convenience, we adopt the following notation (here “:=” indicates a definition):
![]()
![]()
![]() |
Here, the lack of the tildes add to the confusion. Do Marks and Dembski speak about the original search space ![]() ![]() |
Section III. Active Information and no Free Lunch (annotated)
Original Text | Annotations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Gauging the effectiveness of assisted search in relation to blind search is our next task. Random sampling with respect to the uniform probability U sets a baseline for the effectiveness of blind search. For a ?nite search space with K elements, the probability of locating the target T has uniform probability
![]() |
That's only true for a single guess... | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
We assume that we can always do at least as well as uniform random sampling. The question is, how much better can we do? Given a small target T in ![]() ![]() |
... but the Easter egg example indicates that Dembski and Marks aren't talking about a single guess, they are talking about a search, i.e., a sequence of guesses. So, what's the difference? Look at the original search, a sequence of ![]() ![]() ![]() ![]() ![]() ![]() ![]() Now, take the set ![]() That's a bit of a difference! As stated earlier, to represent a search in the original space in | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
An instructive way to characterize the effectiveness of assisted search in relation to blind search is with the likelihood ratio |
An example: Shell Game
Imagine a shell game. Three shells, and one, two or even three peas. Then Then
There are Let's look at two strategies:
Both strategies induce a measure on
Following the traditions of the No Free Lunch Theorems, the average is taken by assuming that all nonempty subsets T are equally likely to be searched for. We see that clever search fares better on average than uniform search when looking at the original problem. But that's not what W. Dembski and R. Marks are doing. In fact, they look at all subsets That's what all of R. Marks's and W. Dembski's idea is about: on average, our clever search does as good - or as bad - as the uniform search. But that's nonsense: Most of the subsets of But what if we look only at subsets Then we get a problem in the next section: For the formulation and the proof of their Horizontal No Free Lunch theorem, a partition of |
A. Active Information
Original Text | Annotations |
---|---|
De?ne the active information of an assisted search as
![]() ![]() ![]() When the target T is clear from context, we suppress the superscript T and simply write |
Have a look at our example: For ![]() ![]() A-ha... That's less than the weight of the sun in grams... |
Active information measures the effectiveness of assisted search in relation to blind search using a conventional information measure. It [33] characterizes the amount of information [8] that ![]() |
The blind search of the NFLT is by the way not the uniform search of R. Marks and W. Dembski: it explicitly is a search without repetition, i.e., if ![]() ![]() |
The maximum value that active information can attain is ![]() the minimum it can attain is |
Now, some new concepts are introduced. We'll stick to our example and have a look at ![]() ![]() ![]() |
In the difference ![]() Endogenous information represents the fundamental difficulty of the search in the absence of any external information. Like other log measurements (e.g., dB), the active information in (III.3) is measured with respect to a reference point. Here endogenous information based on blind search serves as the reference point. |
|
The endogenous information bounds the active information in (III.3).
![]() ![]() |
And indeed, ![]() ![]() |
The second term in (III.3), is the exogenous information.
![]()
|
![]() ![]() |
Active information as defined in (III.3) could also be measured with respect to other reference points. We therefore define the active information more generally as ![]() ![]() for |
Impressive, but usually we're only concerned with finite sets, discrete metrics, etc. Seems to be difficult enough to get that math right... |
B. Horizontal No Free Lunch
Original Text | Annotations |
---|---|
Since the mid-1990s, several conservation of information theorems for search have been proved [15], [28], [44], [51], [52]. The upshot of these theorems — also known as No Free Lunch (NFL) theorems — is that even though a given search may outperform other searches for specific targets, when averaged over the distinct ways searches may differ, no search outperforms any other. Thus, in particular, random search, on average, performs as well as any other. The following No Free Lunch theorem (NFLT) underscores this parity of average search performance. |
Now, we come to the core of the problem |
Theorem III.1. Horizontal No Free Lunch. Let
Then |
Wow, that's a mouthful. First ![]() ![]() ![]() ![]() ![]() ![]()
To explain it with the example of our Easter egg hunt: if you think you have a clever algorithm to work for your egg hunt, you don't expect it to work when
But in the calculation of |
Proof: The expression in (III.6) is immediately recognized as the negative of the Kullback-Leibler distance [8]. Since the Kullback-Leibler distance is always
nonnegative, the expression in (III.6) does not exceed zero. Equality is achieved iff for each |
Impressing, elegant, inapplicable. |
Because the active entropy is strictly negative unless the two probability measures |
This idea is not only counter-intuitive, it seems to be wrong: yes, if you include sets which don't resemble a search into the calculation of your average, then the assisted search perform worse. But even our simple example has shown that this isn't true in the real world... |
Corollary III.1. Horizontal No Free Lunch: No Information Known. Given any probability measure on |
An example of: ex falsum quodlibet |
Remarks. If no information about a search exists, so that the underlying measure is uniform, then, on average, any other assumed measure will result in negative active information, thereby rendering the search performance worse than random search. |
|
Proof: Using ![]() From Theorem III.1, the expression in (III-B) is nonpositive. ♦ |
A proof for a corollary? Seems to be more of a lemma, then. |
Section IV The Search for a Good Search
Just a short summary of a further problem: In this section, a probabilistic hierarchy on top of is introduced:
is the collection of all probability measures on
. It is claimed (and hopefully proven) that
is itself a compact metric space with Borel sets, so the process can be reiterated to get
and so on. Define for convenience
,
,
, and voilà, you have quite something!
Now, an important integral is introduced to link the different spaces : For an arbitrary probability measure
on
(and therefore
), define
![](../../I/6a5a707f2d91ee4b76578f6772a1c9ba.png.webp)
.
This is a vector-valued integration and no less than three references are given for it:
- Nicolae Dinculeanu, Vector Integration and Stochastic Integration in Banach Spaces, New York: Wiley, (2000)
- I. M. Gelfand, Sur un Lemme de la Theorie des Espaces Lineaires, Comm. Inst. Sci. Math. de Kharko. 13(4) (1936): 35–40.
- B. J. Pettis, On Integration in Vector Spaces, Transactions of the American Mathematical Society 44 (1938): 277–304.
So, we're talking about Bochner integrals or even Pettis-Gelfand integrals. Very interesting stuff! Only one problem: Though Marks and Dembski undertook some pain to get the space right over which they are integrating, they have a problem with the function in this integral: The Bochner (and Pettis-Gelfand integral) is defined for a function
, where
is a measure-space and
is a Banach space, i.e., a complete normed vector space.
And though this works out for , you get a problem for
:
Example: Let be a deck of cards.
can be seen as a discrete metric space. Let's try to calculate
for
being the uniform probability measure. Then
Conclusion
When W. Dembski and R Marks state their Horizontal No Free Lunch theorem, they talk about an exhaustive partition of Ω all of whose partition elements have positive probabilities. You can build a partition of Ω of elements of the form only if
.
In this case, the whole result is trivial: If you are allowed only one shot onto an unknown target, just shoot at random!
But for bigger m, i.e., searches as they are generally understood (and described in their paper as assisted searches), the theorem falls flat. And with it, the rest of the paper.