Showing posts with label Winston Ewert. Show all posts
Showing posts with label Winston Ewert. Show all posts

Friday, February 23, 2018

An Amazon Review: Still waiting for the ultimate book on Intelligent Design

I wrote a review at amazon for Dr. Robert J. Marks II's, Dr. Dr. William A. Dembski's, and Dr. Winston Ewert's book Introduction to Evolutionary Informatics (1st Edition):
We are all waiting for the ultimate book on Intelligent Design, written by R. Marks and W. Dembski. Instead we get a "textbook", another attempt to explain the concepts to laymen. I got the impression that the authors used this setting to avoid the necessary rigour: they just do not define terms like "search" which they use hundreds of times. This allows for a lot of hand-waving, like the following sentence on p. 174:

"We note, however, the choice of an algorithm along with its parameters and initialization imposes a probability distribution over the search space"

That unsubstantiated claim is essential for their following proofs on "The Search for a Search"!

And then there are details like this one:

p. 130: "For the Cracker Barrel puzzle [we got] an endogenous information of I = 7.15 bits"
p. 138: "We return now to the Cracker Barrel puzzle. We showed that the endogenous information [...] is I = 7.4 bits"

I tried to solve this conundrum, but I came up with I = 7.8 bits. I contacted the authors, but got no reply.
Not surprisingly, I gave it only two stars.

Some Details on the Cracker Barrel Puzzle

A more complete quote from p. 130 is:
For the Cracker Barrel puzzle, all of the 15 holes are filled with pegs and, at random, a single peg is removed. This starts the game. Using random initialization and random moves, simulation of four million games using a computer program resulted in an estimated win probability p = $0.007\,0$ and an endogenous information of $$I_\Omega = − \log_2\,p\;=\;7.15\,bits.$$
They didn't calculate the correct value, but they simulated the puzzle 4,000,000. A simulation is the most easy programmable way to get a result - but how good is it? It should be pretty good: performing one simulation is a Bernoulli trial with a probability of success $p_t$, the theoretical probability to win a single game by chance. Repeating 4,000,000 Bernoulli trials leads to a binomial experiment $B(4,000,000; p_t)$, so $\sigma = 0.000\,042$ for $p_t$ - that's why stating four positions after the decimal point isn't overconfident: assuming that there is no systemic error, then the probability that the actual value $p_t$ lies within $0.007\,00 \pm 0.000\,05$ is $77\%$.

Giving three significant digits for $I_\Omega$ oversells the power of their experiment slightly: this implies that they expect $p_t$ to be in the interval $[0.007\,067;0.007\,065]$ with a reasonable probability - but the probability is at best about $44\%$.

Confining themselves to only two significant digits on p. 138: $I_\Omega = 7.4\;bits$ yields much more reliable results: again, assuming that there is nothing systematically wrong with their calculation, they can say that $p_t$ is in $[0.005\,72;0.006\,30]$ with a probability of more than $99.999\,99\%$! Well done...

Or not: it is very improbably that both values are correct. Very, very, very, very - using the most favourite estimations, then the second result should only occur with a probability of less than $10^{-98}$ if the first experiment was correctly implemented. It is even worse the other way around: $10^{-112}$.

Which value is correct?

Not surprising the answer: both are wrong - the three authors somehow botched the implementation of even the easiest way to approach the question - a simulation. How can I be so cock-sure? I simulated it myself - 4,000,000 times - and got a value of $p = 0.004\,5$. Then, I calculated the theoretical value by enumerating all possible games and their respective probabilities: again, $p = 0.004\,5$. Then, I published part of my code at The Sceptical Zone, and thankfully, Roy and Corneel also implemented a simulation - which got compatible results. Lastly, Tom English programmed the problem much more cleverly, getting exactly the same results as I (I just had to wait for mine much longer...)

Why didn't the authors do the same?

Monday, January 29, 2018

The Search Problem of William Dembski, Winston Ewert, and Robert Marks

Introduction to Evolutionary Informatics, by Robert J. Marks II, the “Charles Darwin of Intelligent Design”; William A. Dembski, the “Isaac Newton of Information Theory”; and Winston Ewert, the “Charles Ingram of Active Information.” World Scientific, 332 pages.
Classification: Engineering mathematics. Engineering analysis. (TA347)
Subjects: Evolutionary computation. Information technology–Mathematics.1
Search is a central term in the work of Dr. Dr. William Dembski jr, Dr. Winston Ewert, and Dr. Robert Marks II (DEM): it appears in the title of a couple of papers written by at least two of the authors, and it is mentioned hundreds of times in their textbook "Introduction to Evolutionary Informatics". Strangely - and in difference from the other central term information, it is not defined in this textbook, and neither is search problem or search algorithm. Luckily, dozens of examples of searches are given. I took a closer look to find out what DEM see as the search problem in the "Introduction to Evolutionary Informatics" and how their model differs from those used by other mathematicians and scientists.

Monday, May 25, 2015

The Natural Probability on M(Ω)

Two weeks ago, Dr. Winston Ewert announced at Uncommon Descent a kind of open mike. He put up a page at Google Moderator and asked for questions. Unfortunately, not many took advantage of this offer, but I added three questions from the top of my head. The experience made me revisit the paper A General Theory of Information Cost Incurred by Successful Search again, and when I tried - as usual - to construct simple examples, I run into further questions - so, here is another one:

In their paper, the authors W. Dembski, W. Ewert, and R. Marks (DEM) talk about something they call the natural probability:

Processes that exhibit stochastic behavior arise from what may be called a natural probability. The natural probability characterizes the ordinary stochastic behavior of the process in question. Often the natural probability is the uniform probability. Thus, for a perfect cube with distinguishable sides composed of a rigid homogenous material (i.e., an ordinary die), the probability of any one of its six sides landing on a given toss is 1/6. Yet, for a loaded die, those probabilities will be skewed, with one side consuming the lion’s share of probability. For the loaded die, the natural probability is not uniform.
This natural probability on the search space translates through their idea of lifting to the space of measures $\mathbf{M}(\Omega)$:
As the natural probability on $\Omega$, $\mu$ is not confined simply to $\Omega$ lifts to $\mathbf{M}(\Omega)$, so that its lifting, namely $\overline{\mu}$, becomes the natural probability on $\mathbf{M}(\Omega)$ (this parallels how the uniform probability $\mathbf{U}$, when it is the natural probability on $\Omega$, lifts to the uniform probability $\overline{\mathbf{U}}$ on $\mathbf{M}(\Omega)$, which then becomes the natural probability for this higher-order search space).
As usual, I look at an easy example: a loaded coin which always shows head. So $\Omega=\{H,T\}$ and $\mu=\delta_H$ is the natural measure on $\Omega$. What happens on $\mathbf{M}(\Omega)= \{h\cdot\delta_H + t\cdot\delta_T|0 \le h,t \le 1; h+t=1 \}$? Luckily, $$(\mathbf{M}(\{H,T\}),\mathbf{U}) \cong ([0,1],\lambda).$$ Let's jump the hoops:
  1. The Radon-Nikodym derivative of $\delta_H$ with respect to $\mathbf{U}$ is $f(H) = \frac{d\delta_H}{d\mathbf{U}}(H) = 2$, $f(T) = \frac{d\delta_H}{d\mathbf{U}}(T) = 0$
  2. Let $\theta \in \mathbf{M}(\{H,T\})$, i.e., $\theta= h\delta_H + t\delta_T$. Then$$\overline{f}{(\theta)} = \int_{\Omega} f(x)d\theta(x)$$ $$=f(H)\cdot\theta(\{H\}) + f(T) \cdot\theta(\{T\})$$ $$=2 \cdot h$$
Here, I have the density of my natural measure on $\mathbf{M}(\Omega)$ with regard to $\overline{\mathbf{U}}$, $$d\overline{\delta_H}(h\cdot\delta_H + t\cdot\delta_T) = 2 \cdot h \cdot d\overline{\mathbf{U}}(h\cdot\delta_H + t\cdot\delta_T).$$ But what is it good for? For the uniform probability, DEM showed the identity $$\mathbf{U}=\int_{\mathbf{M}(\Omega)}\theta d\overline{\mathbf{U}} .$$ Unfortunately, for $\int_{\mathbf{M}(\Omega)}\theta d\overline{\delta_H}$, I get nothing similar: $$\int_{\mathbf{M}(\Omega)}\theta d\overline{\delta_H} = \frac{2}{3}\delta_H + \frac{1}{3}\delta_T$$

So, again, what does this mean? Wouldn't the Dirac delta function be a more natural measure on $\mathbf{M}(\Omega)$?

I hope that Dr. Winston Ewert reacts to all of the questions before Google Moderator shuts down for good on June 30, 2015...

Friday, September 26, 2014

Conservation of Information in Evolutionary Search - Talk by William Dembski - part 2

For an introduction to this post, take a look here. This is quite a short section, with some annotations from me.

Part 2: 09' 40" - 12' 45''

Topics: What is a search?

William Dembski: We talked about information. Let's now look at that second key term "Search". What is a search. There are seven key components in a search.

William Dembski: You have a search space, you have a target - we are looking for something in the search space. There is initialization - where do we start off? There is a query limit - how many things in the search space can we check out? There is query feedback - when we have checked out, when we have located some item - what is it telling us about itself in terms of how it relates to the target? There is an update rule - once we have queried something, what do we query next? And then finally a stop criterion - when do we stop? How do we know that we have done enough? This is very general.

Sunday, July 14, 2013

Dembski's, Ewert's and Marks's Concept of a Search Applied to Exhaustive Searches

At Uncommon Descent, Winston Ewert, co-author of the paper A General Theory of Information Cost Incurred by Successful Search, writes:
"The search is defined to be a six-tuple consisting of the initiator, terminator, inspector, navigator, nominator, and discriminator. The paper studies the question of picking a search at random, and that would imply picking each of the six components at random. We did not consider it necessary to specifically state that each individual component was also selected at random. That would seem to be implied.
So, let $\Omega = \{\omega_1, \omega_2, \dots, \omega_N\}$ be our finite search space with $N$ elements. We are looking for a single element $\omega_k$, so we try to maximize the fitness function $f = \chi_{\omega_k}$. To keep everything finite, we don't allow repetitions, i.e., in our search each place can only be visited once. This is - as Macready and Wolpert observed - always possible by keeping a look-up table and thus doesn't change the set-up. Therefore, our search is completed in at most $N$ steps.
(BTW: The claim that "each of the six components [is picked] at random" seems not to apply to the inspector: this is a fixed function for a search - in our case, the inspector returns the value of the fitness function. Of course, you can say that we pick the inspector at random out of the set of the one possible inspector.)
Let's take a look at all the searches which are ended by their terminator only after the $N$-s step, i.e., the subset of all exhaustive searches. The price question: What is the probability to find the target in such an exhaustive search? Until now, everyone looking at such problems would have thought that this probability is one: we certainly visited $\omega_k$ and spotted that the function $f$ takes it maximum there. But in the world of Dembski, Ewert, and Marks it is not, as a random discriminator takes its toll - and discriminators aren't obliged to return the target if it was found and identified...
Counterintuitive? That is a flattering description: the discriminator's purpose seems to be to turn even a search which is successful by all human standards into a guess to fit the idée fixe that each search can be "represented" by a measure on the search space.
Addendum: We can drop the condition of not having repetitions in our searches and just look at those searches which are terminated only after the whole search space was visited: terminators with this property exist. Such searches may have length $N$, but can be much longer. The result is the same: the probability of finding the target during a complete enumeration of the search space is (much) less than one. I have to ask: What good is a model in which an exhaustive search doesn't fare much better than a single guess?

Saturday, July 13, 2013

Questioning Information Cost - A reply to Winston Ewert

Over at Uncommon Descent, Winston Ewert (one of the three authors of the paper A General Theory of Information Cost Incurred by Successful Search) answers in the article "Questioning Information Cost to "a number of questions and objections to the paper" I raised. He states fives points, which I will address in this post. Obviously, I'll give my reply at Uncommon Descent, too, but their format doesn't allow for mathematical formulas, so it is easier to make a first draft here. I thank Winston Ewert for his answers, but I'd appreciate some further clarifications.
Firstly, Dieb objects that the quasi-Bayesian calculation on Page 56 is incorrect, although it obtains the correct result. However, the calculation is called a quasi-Bayesian calculation because it engages in hand-waving rather than presenting a rigorous proof. The text in question is shortly after a theorem and is intended to explicate the consequences of that theorem rather than rigorously prove its result. The calculation is not incorrect, but rather deliberately oversimplified.
Fair enough. So it's not a quasi-Bayesian calculation, but a Bayesian quasi-calculation. I will amend my post (Please show all your work for full credit...) by Winston Ewert's explanation.
Secondly, Dieb objects that many quite different searches can be constructed which are represented by the same probability measure. However, if searches were represented as a mapping from the previously visited points to a new point (as in Wolpert and Macready’s original formulation), algorithms which derive the same queries in different ways will be represented the same way. Giving multiple searches the same representation is neither avoidable nor inherently problematic.
The problem is that Dembski's, Ewert's and Marks's construction of the representation does not only depend on the discriminator (see the next point), but on the target, too. Take $\Omega = \{1,2,3,4\}$ and two searches with two steps:
  • The first search consist just of two random guesses, i.e., at each step, one of the numbers is given with probability $1/4$.
  • The second search has two guesses, too. But at the first step, $1$ is taken with probability $7/16$ and each other number with $3/16$, while at the second step, one is omitted from the guess and each other number it guessed with a probability of $1/3$.
These two searches are quite different: the first may produce a query $(1,1)$ with probability $1/16$, while the second never will. Now take a discriminator $\Delta$ which returns the target if it is in the query and otherwise another element in the query at random. Such a discriminator seems to be quite natural and it is certainly within the range of the definition on pages 35--36.
Now, the distribution which $\Delta$ infers on $\Omega$ depends on the target: if we are looking for $\{1\}$, we get:
  • First search: $\mu_{\{1\}}^1$ given by $\mu_{\{1\}}^1(\{1\}) = 7/16$, $\mu_{\{1\}}^1(\{2\})= \mu_{\{1\}}^1(\{3\})= \mu_{\{1\}}^1(\{4\})=3/16$
  • Second search: $\mu_{\{1\}}^2 = \mu_{\{1\}}^1$
These are two algorithms which don't derive the same queries albeit in different ways, but nonetheless they will be represented the same way!
In fact, if our target is $\{2\}$, we get other distributions:
  • First search: $\mu_{\{2\}}^1$ given by $\mu_{\{2\}}^1(\{2\}) = 7/16$, $\mu_{\{2\}}^1(\{1\})= \mu_{\{2\}}^1(\{3\})= \mu_{\{2\}}^1(\{4\})=3/16$
  • Second search: $\mu_{\{2\}}^2\{1\} = 14/96$, $\mu_{\{2\}}^2\{2\} = 44/96$, $\mu_{\{2\}}^2\{3\} = \mu_{\{2\}}^2\{4\}= 19/96$.
Frankly, this seems to be "inherently problematic".
Thirdly, Dieb objects that a search will be biased by the discriminator towards selecting elements in the target, not a uniform distribution. However, Dieb’s logic depends on assuming that we have a good discriminator. As the paper states, we do not assume this to be the case. If choosing a random search, we cannot assume that we have a good discriminator (or any other component). The search for the search assumes that we have no prior information, not even the ability to identify points in the target.
This seems to be a little absurd. Shouldn't your representation work for any discriminator - even a good one? If we are following Wolpert's and Macready's formulation, a blind search means that we try to maximize a characteristic function. So, the natural discriminator should return this maximum if it is found in a query. If it doesn't, we build a discriminator which does: we have the output of the inspector, so why not use it? If you are telling us that the output of the inspector may be false, then I'd use another inspector, one which gives us the output of the fitness function. If you say now that the output of the fitness function may be dubious, I'd say "tough luck: I maximize this function whether the function is right or wrong - what else is there to do?". These added layers of entities which have a hidden knowledge about the target which isn't inherent to the fitness function seem to be superfluous.
Fourthly, Dieb doesn’t see the point in the navigator’s output as it is can be seen as just the next element of the search path. However, the navigator produces information like a distance to the target. The distance will be helpful in determining where to query, but it does not determine the next element of the search path. So it cannot be seen as just the next element of the search path.
So, what is the difference between the inspector and the navigator? The navigator may take the output of the inspector into account, but nonetheless one could conflate both into a single pair of values - especially as you allow "different forms" for the inspector. So you could get rid of the third row of the search matrix.
Fifthly, Dieb objects that the inspector is treated inconsistently. However, the output of the inspector is not inconsistent but rather general. The information extracted by the inspector is the information relevant to whether or not a point is in the target. That information will take different forms depending on the search, it may be a fitness value, a probability, a yes/no answer, etc.
Sorry, I may have been confused by the phrase "The inspector $O_{\alpha}$ is an oracle that, in querying a search-space entry, extracts information bearing on its probability of belonging to the target $T$": if we look at the Dawkins's Weasel and take the Hamming-distance as the fitness function, each returned value other than $0$ tells us that the probability of belonging to the target $T$ for an element is zero itself, whether it is "METHINKS IT IS LIKE A WEASER" or "AAAAAAAAAAAAAAAAAAAAAAAAAAAA". I understand that you want to avoid the notion of proximity to a target, but your phrasing is misleading, too. Have you any example of a problem where the inspector returns a probability other than 0 or 1? In your examples, it seems to be always the output of a fitness function.
The authors of the paper conclude that Dieb’s objections derive from misunderstanding our paper. Despite five blog posts related to this paper, we find that Dieb has failed to raise any useful or interesting questions. Should Dieb be inclined to disagree with our assessment, we suggest that he organize his ideas and publish them as a journal article or in a similar venue.
It's always possible that I've misunderstood certain aspects of the paper. I would be grateful if you helped to clear up such misunderstanding. I hope that my comments above count as useful and at least a little bit interesting. I'm preparing an article, as I've promised earlier, but the work is quite tedious, and any clarification of the matters above. Furthermore, I'd like to know whether this "general framework" is still in use, or whether you have tried another way of representing searches as measures. Again, thank you Winston Ewert!

Wednesday, July 3, 2013

Please show all your work for full credit...

(I promised a chapter-by-chapter critique of "A General Theory of Information Cost incurred by Successful Search". This is quite tedious work, so I wanted to make this little point up front - for full reading pleasure you have to be acquainted with (some of) the definitions used in the paper.)
(Nota Bene: In a reply to this post, Winston Ewert wrote on Uncommon Descent: "Dieb objects that the quasi-Bayesian calculation on Page 56 is incorrect, although it obtains the correct result. However, the calculation is called a quasi-Bayesian calculation because it engages in hand-waving rather than presenting a rigorous proof. The text in question is shortly after a theorem and is intended to explicate the consequences of that theorem rather than rigorously prove its result. The calculation is not incorrect, but rather deliberately oversimplified.")

On page 55 of their article "A General Theory of Information Cost incurred by Successful Search" (free download as pdf), the authors W. A. Dembski, W. Ewert and R. J Marks II (in future I'll refer to them as DEM) write:

To see how the probability costs ossociated with null and alternative searches relate, it is instructive to consider the following two quasi-Bayesian ways of reckoning these costs:
$\mathbf{P}$(locating $T$ via null search)=$\mathbf{P}$(null search locates T & null search is available)
=$\mathbf{P}$(null search locates T|null search is avail.) × $\mathbf{P}$(null search is avail.)
=$\mathbf{U}(T) \times 1$ [because the availability of null search is taken for granted]
=$p$.

$\mathbf{P}$(locating $T$ via alt. search)=$\mathbf{P}$(alt. search locates T & alt. search is available)
=$\mathbf{P}$(alt. search locates T|alt. search is avail.) × $\mathbf{P}$(alt search is avail.)
=$\mu(T) \times \overline{\mathbf{U}}(\overline{T}_q)$
$\le q\,\times\,p/q$
=$p$.
I have no problems with the results - at least if we can assume that the uniform measure is apt to be used on $\mathbf{M}(\Omega)$. But the equations seems to be a little bit fishy. Let me explain what I mean, using the most simple setting possible: Let $\Omega = \{0,1\}$, a set with two elements, and let $T=1$ be our target. Then $\mathbf{M}(\Omega)$ can be represented by the interval $[0;1]$: for $x \in [0;1]$, $\mu_x = (1-x) \delta_0 + x \delta_1$ is the measure with $\mu_x(\{1\}) = x$. We can even introduce an associated search $S_x := S_(\mu_x)$, which is in fact just a single guess on $\Omega$ distributed according to $\mu_x$. Ergo $\mathbf{E}(S_x) = x$. Now we can perform an experiment in two steps:
  1. Choose a measure $\mu_x \in \mathbf{M}(\Omega)$ at random.
  2. Try to locate $T$ using $S_x$.
This experiment can be represented by choosing (X,Y) on $[0;1] \times [0;1]$ according to the uniform distribution on the unit square: We look up a number x, which represents our measure, then a number y: if $y \le x$, we have located our target using $S_x$, otherwise not.
The picture displays the situation and allows us two answer some questions easily:
  • What's the probability to locate our target using the process above? Well, it's $p = 1/2$, represented by the whole green area
  • For a fixed $q$, what is the probability to choose $\mu_x$ and find our target? That's zero (or nil): the red line symbolizes this event, which is a null-set.
Dembski, Ewert, and Marks (DEM) obviously don't want to have this, that's why they don't look at $\{\theta \in \mathbf{M}(Q) | \theta(T) = q \}$, but at $\overline{T}_q = \{\theta \in \mathbf{M}(Q) | \theta(T) \ge q \}$. (pp. 53-54)
  • What's the probability to choose a measure for which the associated guess finds the target with a probability of at least q, i.e., $\overline{\mathbf{U}}(\overline{T}_q) $? That would be (1-q), easily to be seen in our case, but much more difficult to calculate for more complicated arrangements. DEM give a upper limit for this probability of $p/q$.
  • What is the probability of finding our target when we have chosen a measure in $\overline{\mathbf{U}}(\overline{T}_q)$? That depends on the measure, but it is at least $q$. On average, it is $\frac{1+q}{2}$: we get this by examining the darker green area...
  • What is the probability of choosing a measure in $\overline{\mathbf{U}}(\overline{T}_q)$ and finding the target? This is given by the darker green area, ergo $(1-q)\frac{1+q}{2}=\frac{1-q^2}{2}$
Now, the darker green area will always be smaller than the whole green area, not only in this simple example, but for all others, too. Therefore the statement: $$\mathbf{P}\text{(locating }T\text{ via alt. search}) \le p$$ is absolutely (and trivially) correct, as $\mathbf{P}\text{(locating }T\text{ via alt. search})$ is the probability of choosing an element of $\overline{\mathbf{U}}(\overline{T}_q)$ and finding the target using that element. But there is a problem in the equality $$\mu(T) \times \overline{\mathbf{U}}(\overline{T}_q) \le q\,\times\,p/q$$ While $\overline{\mathbf{U}}(\overline{T}_q) \le p/q$ we find that $$\mu(T) \ge q:$$ A measure taken from $\overline{T}_q$ will result in a search which finds the target with a probability of at least $q$. Above, we have seen, that the probability is on average $\frac{1+q}{2} > q$. So we cannot say anything about the size of $\mu(T) \times \overline{\mathbf{U}}(\overline{T}_q)$!. The shaded area in the picture shows $q\,\times\,p/q$: it has nothing to do with the probabilities which one can see so neatly in the graphic, it just happens to have the right area of $p$...
BTW: I don't think that we can split $\mathbf{P}$(alt. search locates T & alt. search is available) neatly into a product used by DEM, a little integrating would be necessary...
So, I wouldn't give full marks for this exercise, but perhaps I'm wrong?

Sunday, June 23, 2013

Review of "A General Theory of Information Cost Incurred by Successful Search" - Introduction

(For some background information, go here)

There are two main ways to apply mathematics: the first is to shed light on a subject and look for a deeper understanding, the second just wants to create the impression that something important is happening somehow. After looking into the article "A General Theory of Information Cost Incurred by Successful Search" (free download as pdf) I became convinced that the authors are following the second path.

The abstract states:

This paper provides a general framework for understanding targeted search. It begins by defining the search matrix, which makes explicit the sources of information that can affect search progress. The search matrix enables a search to be represented as a probability measure on the original search space. This representation facilitates tracking the information cost incurred by successful search (success being defined as finding the target). To categorize such costs, various information and efficiency measures are defined, notably, active information. Conservation of information characterizes these costs and is precisely formulated via two theorems, one restricted (proved in previous work of ours), the other general (proved for the first time here). The restricted version assumes a uniform probability search baseline, the general, an arbitrary probability search baseline. When a search with probability q of success displaces a baseline search with probability p of success where q > p, conservation of information states that raising the probability of successful search by a factor of q/p(>1) incurs an information cost of at least log(q/p). Conservation of information shows that information, like money, obeys strict accounting principles.
The general framework is introduced pp 26 — 38. In my next post, I'll try to relate it to the usual definitions, but I fail to see how this new frameworks improves e.g., the ideas of David Wolpert and William G. Macready significantly (NFLT at wikipedia). pp 38 — 45 provide examples, interestingly without applying the new framework to them. Then follow a couple of pages with sound math (pp. 45 — 61), it is just not clear what they have to do with the claims the authors are making. For their mathematics to work, they have to show that searches can be represented as measures. Indeed, the authors write:
"This representation will be essential throughout the sequel. (p. 37)
I will elaborate how I think that the authors failed to do so, and that the "representation" is at least a misnomer... Another point will be the subject of "Information Cost": this term isn't defined in the paper...