Sunday, September 2, 2012

Some Annotations to the Previous Post

1. Joe, at this point I'd advice students to draw a decision tree. Some would draw one with six nodes in the first layer, representing the machines $M_1, M_2, ... , M_6$ and then 36 nodes in the second layer, representing each of the possible outcomes from $1,2,...,6$ for each of the machines. At each of the branches, they put the possibility to get from one node to the next, and at the end of the the diagram they write down the 36 probabilities for the outcomes which they get by multiplying the probabilities on the branches which lead to the outcome. However, others would opt for a much easier design, summarizing the machines $M_2, M_3, ..., M_6$ as $\overline{M_1}$, and the non-desirable outcomes $\{1,2, ...,5\}$ as $\overline{6}$, which leads to the following graph:

Friday, August 31, 2012

Could you please correct your miscalculation, Dr. Dembski?

William A. Dembski wrote "a long article […] on conservation of information. " at Evolution News and Views (ENV), an outlet of the Discovery Institute. Others have commented on more sophisticated problems, either at Uncommon Descent or at The Skeptical Zone. Here I want just to correct some simple math which occurs in a toy example used in the article:
To see how this works, let's consider a toy problem. Imagine that your search space consists of only six items, labeled 1 through 6. Let's say your target is item 6 and that you're going to search this space by rolling a fair die once. If it lands on 6, your search is successful; otherwise, it's unsuccessful. So your probability of success is 1/6. Now let's say you want to increase the probability of success to 1/2. You therefore find a machine that flips a fair coin and delivers item 6 to you if it lands heads and delivers some other item in the search space if it land tails. What a great machine, you think. It significantly boosts the probability of obtaining item 6 (from 1/6 to 1/2).

Friday, May 25, 2012

Is the average active information a suitable measure of search performance?

(Though the following doesn't include any maths, the reader is expected to be familiar with William Dembski's and Robert Marks's paper The Search for a Search and should have glanced at On a Remark by Robert J. Marks and William A. Dembski)

One of my problems with the modeling of searches by William Dembski and Robert Marks is that I don't see how every assisted search can be described as a probability measure on the space of the feasible searches. But nevertheless, Winston Ewert insisted that

All assisted search, irrespective of the manner in which they are assisted, can be modeled as a probably distribution biased towards selecting elements in the target.
Marks and Dembski claim that the average active information is a measure of search performance - at least they write in their remark:
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.
Their erratum seems indeed to proof the remark in a slightly modified way:
Given a uniform distribution over targets of cardinality k, and baseline uniform distribution, the average active information will be non-positive
(The proof of this statement in the erratum is correct - at least as far as I can see...)
So, lets play a game: From a deck of cards one is chosen at random. If you want to play, you have to pay 1\$, and you get 10\$ if you are able to guess the card correctly. But you are not alone, there are three other people A, B and (surprisingly) C who'll announce their guesses first. They use the following search strategies:
  • A: he will announce a card according to the uniform distribution
  • B: he will always announce ♦2
  • C: He has access to a very powerful oracle, which gives him the right card. Unfortunately - due to an old superstition - he is unable to say ♦2, so every time this card appears he will announce another one at random
Which strategy will you follow? Siding with player A or B gives you a chance of 1/52 for a correct guess, so you will loose on average ca. 81¢ per game. However, if you pose your bet with C, you will win 8.81$ a game in the long run! That's because the probability of a correct guess is 1/52 for both our players A and B, while C's chance for success is 51/52.

But what would Marks, Dembski or Ewert do? They calculate the average active information according to the formula given in the erratum. This E[I+] is 0 for player A, but -∞ for B and C. As negative active information on average renders the search performance worse than random search, they have to stick with player A.

So, either average active information is not a good measure of search performance, or not every assisted search, irrespective of the manner in which they are assisted can be modeled as a probably distribution. Or it is a bit of both...

Thursday, May 24, 2012

A new erratum for Dembski's and Marks's The Search for a Search

Last month, I made a post On a Remark by Robert J. Marks and William A. Dembski where I addressed errors in a section of Dembski's and Marks's paper The Search for a Search. I exchanged emails over this with Winston Ewert, one of the people at The Evolutionary Informatics Lab ( a former?/grad? student of Marks). He informed me:
You also make brief mention that the HNFLT proof assumes a partition of the search space and thus cannot handle the overlapping targets. This is problematic because any target on the original search space will become an overlapping target on the multi-query search space. I think you are correct on this point. Thanks for bringing it to our attention. We've added a description of the problem as well as an alternate proof for the uniform case on overlapping targets to the pdf: http://evoinfo.org/papers/2010_TheSearchForASearch.pdf.
Here are some thoughts:

Tuesday, May 15, 2012

9,000!

9,000! is the proud headline of a post by Barry Arrington at Uncommon Descent. The whole thing reads:
The post before this one was UD’s 9,000th. Thank you to all of our readers for your support as we celebrate this milestone.
So congratulations! But a comment by SCheesman pours a little water into the celebratory wine:
I wish I could celebrate, but I fear 9000 is a reflection of a vast inflation in the number rate of postings in the last year or two, with a corresponding decline in comments.
I owe a good deal of what I know today about ID from UD, both from a scientific and theological perspective, and used to enjoy the long threads and back-and-forth between proponents and opponents.
But now, many, if not most posts get nary a comment, and the ones engendering some debate often are lost in the crowd. Since the recent purge of participants who failed to pass what amounted to a purity test, it’s been pretty quiet here. The most lively recent discussion featured a debate between OEC’s and YEC’s. Now I enjoy that sort of thing (like on Sal Cordova’s old “Young Cosmos” blog), but it’s hardly what UD used to be known for.
Maybe the new format gets more visitors than it used to, but I’d be interested in seeing the stats, including comments per post, posts per month, unique visitors etc. over the last few years.
I miss the old days. I expect a lot of us do.
I'll try to satisfy the curiosity as good as I can.
Posts per month

Monday, April 23, 2012

Uncommon Descent in numbers

Uncommon Descent was started in April 2005 as the “Intelligend Design WebLog of William Dembski”. Since then some 200,000 comments (77 per day) were made to 8,600 (3.4 per day) posted articles.
That's not shabby: I don't think that Panda's thumb (including AtBC) or the discussion board at www.RichardDawkins.net are more busy, though PZ Myers would probably be disappointed by such a low turn out.

Saturday, April 21, 2012

On a Remark by Robert J. Marks and William A. Dembski

Abstract

In their 2010 paper The Search for a Search: Measuring the Information Cost of Higher Level Search, the authors William A. Dembski and Robert J. Marks II present as one of two results their so-called Horizontal No Free Lunch Theorem. One of the consequences of this theorem is their remark: 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. This is quite surprising, as one would expect in the tradition of the No Free Lunch theorem that the performances are equally good (or bad). Using only very basic elements of probability theory, this essay shows that their remark is wrong - as is their theorem.

Definitions

The situation is quite simple: There is a set $\Omega_1$ - the search space - with $N$ elements, so w.l.o.g. $\Omega = \{1,\,\ldots,\,N\}$. Let $T_1 \subset \Omega_1$ denote the target. At first assume that $T_1$ consists of a single element. To find this element $T_1$ you have $K$ guesses and you aren't allowed to guess the same element twice. Such a sequence of $K$ different guesses can be described as an ordered $K$-tuple $(n_1,\,n_2,\,\ldots,\,n_K)$ of $K$ pairwise different numbers and is called a search. The $\frac{N!}{(N-K)!}$ different searches build the space $\Omega_K$. A search strategy is a probability measure $\mathbf{Q}$ on $\Omega_K$. Such a measure can be given by assigning a probability $\mathbf{Q}((n_1,\,n_2,\,\ldots,\,n_K)) = q_{(n_1,\,n_2,\,\ldots,\,n_K)}$ for each of the (pure) strategies $(n_1,\,n_2,\,\ldots,\,n_K)$ in $\Omega_K$: $q_{(n_1,\,n_2,\,\ldots,\,n_K)}$ is the probability to choose the strategy $(n_1,\,n_2,\,\ldots,\,n_K)$ from $\Omega_K$. So obviously, $q_{(n_1,\,n_2,\,\ldots,\,n_K)} \ge 0\; \forall (n_1,\,n_2,\,\ldots,\,n_K)\in\Omega_K$ and $\sum_{(n_1,\,n_2,\,\ldots,\,n_K) \in \Omega_K} q_{(n_1,\,n_2,\,\ldots,\,n_K)} =1 $. Random search (i.e., the random search strategy) correspond to the uniform distribution $\mathbf{U}$ on $\Omega_K$, i.e. $\mathbf{U}((n_1,\,n_2,\,\ldots,\,n_K)) = \frac{(N-K)!}{N!}$. Any other search strategy is called an assisted search. This shows the small scope of the concept of an assisted search in the papers of Dembski and Marks: it is not possible to encode the influence of an oracle or a fitness function into the measure $\mathbf{Q}$, so most examples presented by the authors (like partioned search or easter egg hunt are not covered by this model. The performance of a search strategy $\mathcal{P}(\mathbf{Q},\delta_{T_1})$ for finding an element $T_1 \in \Omega_1$ is defined as the probability to name $T_1$ in one of the $K$ guesses of the search.
Some calculations
Using the characteristic function $\chi_{\{n_1,\,n_2,\,\ldots,\,n_K\}}(T_1)= \left\lbrace \begin{array}{cl} 1 & if\;T_1 \in \{n_1,\,n_2,\,\ldots,\,n_K\} \\ 0 & otherwise \end{array} \right. $ this probability can be written as: $\mathcal{P}{(\mathbf{Q},\delta_{T_1})} = \sum_{(n_1,\,n_2,\,\ldots,\,n_K) \in \Omega_K} q_{(n_1,\,n_2,\,\ldots,\,n_K)} \cdot \chi_{\{n_1,\,n_2,\,\ldots,\,n_K\}}(T_1)$ The characteristic function is independent of the order of the elements $n_1, n_2, \ldots n_K$. So the expression can be streamlined using instead of the space of ordered n-tuples $\Omega_K$ the space $\mathfrak{P}_K(\Omega_1)$ of subsets $\{n_1,\,n_2,\,\ldots,\,n_K\}$ with $K$ elements of $Q_1$. This space has ${N \choose K}$ elements. $\mathbf{Q}$ on $\Omega_K$ gives instantly rise to a measure on $\mathfrak{P}_K(\Omega_1)$ - again called $\mathbf{Q}$ - by setting: $ \mathbf{Q}(\{n_1,\,n_2,\,\ldots,\,n_K\}) = \sum_{\sigma \in S_K} q_{(\sigma_1(n_1),\,\sigma_2(n_2),\,\ldots,\,\sigma_K(n_K))}.$ Here, $\sigma = (\sigma_1,\sigma_2,\ldots,\sigma_K)$ are the $K!$ elements of the group of permutations of $K$ elements, $S_K$. Thus, the probability to search successfully for $T_1$ is $\mathcal{P}{(\mathbf{Q},\delta_{T_1})} = \sum_{\{n_1,\,n_2,\,\ldots,\,n_K\} \in \mathfrak{P}_K(\Omega_1)} \mathbf{Q}(\{n_1,\,n_2,\,\ldots,\,n_K\}) \cdot \chi_{\{n_1,\,n_2,\,\ldots,\,n_K\}}(T_1).$ But how does this search perform on average - assuming that the underlying measure is uniform? The underlying measure gives the probability with which a target element is chosen: if there is a uniform underlying measure $\mathbf{U}_{\Omega}$, each element $1,2,\ldots, N$ is a the target with a probability of $\frac{1}{N}$. The average performance is given by: $\mathcal{P}{(\mathbf{Q},\mathbf{U}_{\Omega})} =\sum_{l=1}^N \frac{1}{N}\sum_{\{n_1,\,n_2,\,\ldots,\,n_K\} \in \mathfrak{P}_K(\Omega_1)} \mathbf{Q}(\{n_1,\,n_2,\,\ldots,\,n_K\}) \cdot \chi_{\{n_1,\,n_2,\,\ldots,\,n_K\}}(l)$ $= \frac{1}{N}\sum_{\{n_1,\,n_2,\,\ldots,\,n_K\} \in \mathfrak{P}_K(\Omega_1)} \mathbf{Q}(\{n_1,\,n_2,\,\ldots,\,n_K\}) \cdot \left(\sum_{l=1}^N \chi_{\{n_1,\,n_2,\,\ldots,\,n_K\}}(l)\right)$ $= \frac{1}{N}\sum_{\{n_1,\,n_2,\,\ldots,\,n_K\} \in \mathfrak{P}_K(\Omega_1)} \mathbf{Q}(\{n_1,\,n_2,\,\ldots,\,n_K\}) \cdot K $ $=\frac{K}{N} \sum_{\{n_1,\,n_2,\,\ldots,\,n_K\} \in \mathfrak{P}_K(\Omega_1)} \mathbf{Q}(\{n_1,\,n_2,\,\ldots,\,n_K\})$ $=\frac{K}{N}.$ This holds for every measure $\mathbf{Q}$ on the space of the searches, especially for the uniform measure, leading to the
Special Remark: If no information about a search for a single element exists, so that the underlying measure is uniform, then, on average, any other assumed measure will result in the same search performance as random search.
But perhaps this result depends on the special condition of an elementary target? What happens when $T_m = \{t_1, t_2, \ldots, t_m\} \in \mathfrak{P}_m(\Omega _1)$? Then a search is seen as a success if it identifies at least one element of the target $T_m$, thus $\mathcal{P}{(\mathbf{Q},\delta_{T_1})} = \sum_{\{n_1,\,n_2,\,\ldots,\,n_K\} \in \mathfrak{P}_K(\Omega_1)} q_{\{n_1,\,n_2,\,\ldots,\,n_K\}} \cdot \max_{t \in T_m}\{\chi_{\{n_1,\,n_2,\,\ldots,\,n_K\}}(t)\}.$ Calculating the average over all elements of $\mathfrak{P}_m(\Omega_1)$ results in: $\mathcal{P}{(\mathbf{Q},\mathbf{U}_{\mathfrak{P}_m(\Omega_1)})} = \frac{1}{{N \choose m}} \sum_{T \in \mathfrak{P}_m(\Omega_1)} \sum_{\{n_1,\,n_2,\,\ldots,\,n_K\} \in \mathfrak{P}_K(\Omega_1)} q_{\{n_1,\,n_2,\,\ldots,\,n_K\}} \cdot \max_{t \in T_m}\{\chi_{\{n_1,\,n_2,\,\ldots,\,n_K\}}(t)\}.$ $=\frac{1}{{N \choose m}} \sum_{\{n_1,\,n_2,\,\ldots,\,n_K\} \in \mathfrak{P}_K(\Omega_1)} q_{\{n_1,\,n_2,\,\ldots,\,n_K\}} \sum_{T \in \mathfrak{P}_m(\Omega_1)} \max_{t \in T_m}\{\chi_{\{n_1,\,n_2,\,\ldots,\,n_K\}}(t)\} $ $=\frac{1}{{N \choose m}} \sum_{\{n_1,\,n_2,\,\ldots,\,n_K\} \in \mathfrak{P}_K(\Omega_1)} q_{\{n_1,\,n_2,\,\ldots,\,n_K\}} \cdot \left({N \choose m} - {N-K \choose m}\right) $ $= \frac{{N \choose m} - {N-K \choose m}}{{N \choose m}} \sum_{\{n_1,\,n_2,\,\ldots,\,n_K\} \in \mathfrak{P}_K(\Omega_1)} q_{\{n_1,\,n_2,\,\ldots,\,n_K\}} $ $= \frac{{N \choose m} - {N-K \choose m}}{{N \choose m}} = 1-\frac{(N-K)(N-K-1)\ldots (N-K-m+1)}{N(N-1)\ldots (N-m+1)}.$ Again the probability of a successful search - and by definition the performance - is on average independent of the measure used on the space of the searches! (Note that the expression becomes $\frac{K}{N}$ for $m=1$ and $1$ for $N-K < m$). The result of this calculation is the
Less Special Remark: If no information about a search for a target exists other than the number of elements the target exists from, so that the underlying measure is uniform, then, on average, any other assumed measure will result in the same search performance as random search.
As the performance of the random search and any other search doesn't differ on any subset of targets of fixed cardinality, the next remark is elementary:
General Remark: If no information about a search exists, so that the underlying measure is uniform, then, on average, any other assumed measure will result in the same search performance as random search.
Obviously this General Remark negates the
Remark of Dembski and Marks: 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.
Consequences for the Horizontal No Free Lunch Theorem
There is much critique on this theorem out there, e.g., "A Note Regarding ``Active Entropy". The previous paragraphs add to this: Dembski's and Marks's remark is a direct consequence of the theorem, and as the remark is wrong, the theorem can't be right, neither. How is it possible for two mathematicians to err on such a crucial point? Perhaps they were seduced by the elegance of their argument: the calculations in the sections above are simple and a little bit clumsy. Dembski and Marks smartly augmented the original search space $\Omega_1$ and identified it with the space of pure search strategies $\Omega_K$. For each original target $T_1$ a corresponding target $\tilde{T_1}$ can be found in $\Omega_K$, such that a simple search $(n_1, \ldots, n_K)$ is successful when it is an element of $\tilde{T_1}$. So the problem of searching by $K$ guesses on $\Omega_1$ is reduced to a simple guess on $\Omega_K$. The problem which they overlooked: the corresponding targets aren't nice subsets. Especially if $K>1$, then the corresponding sets for two different targets in the original space have always a non-empty intersection. Nevertheless, Dembski and Marks use an exhaustive partition of the augmented space in their proof of the Horizontal No Free Lunch theorem, but there is no such partition into subsets which makes sense in the framework of their argument.
Conclusion
Dembski and Marks have introduced their concept of Active Information using a great number of examples. Their model for an assisted search works only for one or two of these examples. The theoretical results presented in The Search for a Search seem not to work at all. That leaves the Active Information as being a new performance measure, but it can't be seen how it improves the understanding of the concept of information in connection with search algorithms.