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...

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

For an introduction to this post, take a look here. As I ended part 4 quite abruptly, this section starts in the middle of things....

Part 4: 45' 00" - 52' 50"

Topics: What is Conservation of Information? Example continued.

William Dembski: These tickets have probability 1/2, 1/2, 1/2, 1/2, and this one ticket has probability 1. If I happen to get this ticket, I have probability 1/2 of choosing curtain 1, but it is also probability 1/9 of getting that ticket. When you run the numbers, at the end of the day, by using these tickets, I'm not better of than I was originally. It is still only a probability of 1/3 of finding curtain 1, of finding the prize there. Once one factors in how did I limit myself to these tickets in the first place. Going from this whole space to this, that is information intensive. I have ruled out certain possibilities, that incurs an information cost. As I said, the cost is 5/9. It is really just an accounting thing. That is what conservation of information is. Once you factor in the information that it takes to get the search, get a search which has improved the probability for finding your original target, we haven't gained anything. It is called Conservation of Information, as the problem can even get worse. At this case, we have broken even, we are back to 1/3 for the probability of getting the prize, but let's say, you really want to improve the probability, you want to guarantee that you get that prize with this tickets. Well, then you have got only one ticket that will work for you.

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

For an introduction to this post, take a look here. There is some interaction with the audience (15'30" - 18'00") which I wasn't able to understand fully. Any help is appreciated!

Part 3: 12' 45" - 31' 25"

Topics: What is an evolutionary search?

William Dembski: Now let's add this next term evolutionary. What does evolutionary - when we put it in front of search - add to the discussion? I think it changes one key aspect here. Whereas we were looking at some query feedback, now this query feedback takes the form of fitness: how good is it? Query feedback can be quite general. Maybe the query feedback is nothing, when we examine it. Or maybe the query feedback may just say "I'm in the target" or "I'm not in the target". That would be very simple. Fitness is going to give some sort of range of values that ideally identify how close am I to the target.

William Dembski: There are examples of evolutionary search. There is the Dawkins' weasel example from his book "The Blind Watchmaker", that is the one I'm going to focus on here. Then there are various - what I would regard as - embellishments of that, because I don't think that there is anything fundamentally new about them. There is MSU's Avida program, Tom Ray's Tierra, Schneider's ev. What is at the heart of these programs that these are computer programs which mimic - try to mimic - Darwinian evolutionary processes. What are they supposed to show? That is interesting. Look at the history of this field of evolutionary computing and there is a reason why people wanted to do evolution in the computer. That is because the computer would allow evolution to be done in real time, because we cannot really see it in real time in the wild.

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.

William Dembski's talk at the University of Chicago

Invited by Leo Kadanoff, William Dembski spoke on Aug 15, 2014 at the University of Chicago's "Computations in Science" seminar. Jerry A. Coyne - a professor in the department of ecology and evolution at the same university - questioned the judgement of the seminar's organizers. Afterwards, the Discovery Institute was very pleased with its paladin William Dembski.

"The talk itself and the Q&A afterward, which were at a pretty high level, went very well."

, and they loved a concluding remark by Leo Kadanoff:

I think the ball is in the court of people who believe in evolution. They have to deal with these questions. ...Bill has made his case and we should all go home and think.

At William Dembski's former blog Uncommon Descent, a video of the talk-cum-questions was posted on Sep 14, 2014:

This video has gotten very little resonance. To make it easier to access, I have created a transcript, which I will publish on this blog in a short series of posts. Obviously, the usual caveats apply: I'm not a native speaker, but I tried my best to understand and reproduce the talk as truthfully as possible. I apologize in advance for my errors, which inevitably have occurred, and I'm grateful for any correction.

How "official" is the video?

The question arose: who actually taped the talk? Some student, who then put it up on youtube? I think that it is a work of members of the Discovery Institute:

1. The youtube channel MissIngaNiball on which the video is presented seems to belong to Robert Marks (wikipedia, American Loons), or at least a member of his family (in which case a predilection for feeble puns would be hereditary).
2. Two stills taken from the video are credited to Paul Nelson (wikipedia, American Loons)in the Discovery Institute's article.

Dembski's talk: Part 1 - 5

• Part 1: Introduction, What is information?
• Part 2: What is is a search?
• Part 3: What is is an evolutionary search?
• Part 4: What is Conservation of Information?
• Part 5: What is Conservation of Information? Example continued

Dembski's and Mark's "The Search for a Search": Trying to work out one of their examples

Three years ago, on April 1st, 2010, W. Dembski's and R. Marks's paper The Search for a Search^[1] was accepted for publication. Recently, W. Dembski referred to it as a seminal paper in his article Before They've Even Seen Stephen Meyer's New Book, Darwinists Waste No Time in Criticizing Darwin's Doubt at the Discovery Institute's Evolution News and Views.. The first result of their paper is the Horizontal No Free Lunch Theorem which shows that average relative performance of [assisted] searches never exceeds unassisted or blind searches. Hopefully this paper is covered at the 2013 Summer Seminar on Intelligent Design In the natural sciences from July 12-20, 2013 in Seattle, WA - at least in the past, Marks and Dembski have been speakers at this seminar. Wouldn't it be a nice warm-up exercise for all these bright students gathered in Seattle to work out an example of an assisted search and see for themselves how the Horizontal No Free Lunch theorem works? I just ask because I haven't seen any such example calculated by Marks, Dembski or one of their students. They have mentioned a few kinds of assisted searches - like Dawkins's weasel, the Easter Egg hunt, etc., but they have never shown how those fit their model.

So I tried to work out a kind of simplified Easter Egg hunt in the language of Dembski and Marks - and I invite everyone to try to elaborate similar examples. My claim: any search which uses a kind of feedback (an oracle, a fitness function, etc.) cannot be described meaningfully in the terms of Marks and Dembski - which cast a doubt on their far-reaching conclusions about assisted searches in general. But see for yourself:

Evolutionary Algorithms in Conservation of Information in Search

work in progress :-)

In their paper Conservation of Information in Search: Measuring the Cost of Success, William A. Dembski, Senior Member, IEEE, and Robert J. Marks II, Fellow, IEEE present three algorithms which could loosely be described as evolutionary. Idiosyncratically, they are labeled

1. Partitioned Search
2. Optimization by Mutation, and
3. Optimization by Mutation With Elitism

These procedures are discussed section II, part E and F (pp. 1055-1057), and some additional math is done in the appendix.

The algorithms and the examples given

The three algorithms are introduced or illustrated with an example, for which the parameters can be found in this table:

Algorithm	class	alphabet	length of target	Mutation	fitness function
Partitioned Search	none	{*,A,B,...Z} (27 el.)	28	every incorrect letter is mutated	position of correct letters
Optimization by Mutation	(1,2) ES	{0,1} (2 el.)	100	each letter is flipped with probability µ=0.00005	number of correct letters
Optimization by Mutation With Elitism	(1+1) ES	{0,1} (2 el.)	131*	exactly one letter is flipped	number of correct letters

^*Why 131b for the last algorithm? I could understand 133 ~ 28* log₂27, but 131?

References

Four references are given in the section under discussion:

• [3] M. Aigner, Discrete Mathematics. Providence, RI: Amer. Math. Soc., 2007.
• [12] R. Dawkins, The Blind Watchmaker: Why the Evidence of Evolution Reveals a Universe Without Design. New York: Norton, 1996.
• [32] D. J. C.MacKay, Information Theory, Inference and Learning Algorithms. Cambridge, U.K.: Cambridge Univ. Press, 2002.
• [34] A. Papoulis, Probability, Random Variables, and Stochastic Processes, 3rd ed. New York: McGraw-Hill, 1991, pp. 537–542.

The first one is unproblematic - though superfluous: it is given as a reference for the Lth harmonic number. The three other references are either problematic or at least indicating sloppy work:

1. Partitioned search [12] is a “divide and conquer” procedure best introduced by example. Richard Dawkins doesn't use the expression "partitioned search" in his book.

2. When μ << 1, the search is a simple Markov birth process [34] that converges to the target. The page numbers of the reference don't fit: it should be pp. 647-650, not pp. 537–542. But at least, page numbers are given!

3. To illustrate, consider a single-parent version of a simple mutation algorithm analyzed by McKay [32].David MacKay analyzes explicitly multi-parented algorithms, there is not much of a resemblance with Dembski's and Marks's procedure. And annoyingly, again, page numbers are omitted. MacKay's book has over 600 pages, only a few in Chapter III, 19 : Why have Sex? Information Acquisition and Evolution are dedicated to evolutionary algorithms.

But one has to be grateful for small things: At least these references weren't garbled like

[7] S. Christensen and F. Oppacher, “What can we learn from no free lunch? A first attempt to characterize the concept of a searchable,” in Proc. Genetic Evol. Comput., 2001, pp. 1219–1226.

Of course, it's about the concept of a searchable function. Not the first time, R. Marks and W. Dembski got that wrong.
Ann.: Tom English explained that errors in references are common in the engineering literature. So, I'll stop classifying the references of Dembski's and Marks's article as either superfluous or erroneous for now.