I’ll follow Patrick’s lead and offer a few comments on another paper from the Evolutionary Informatics Lab. The paper analyzes Tom Schneider’s ev program, and while there are several problems with the analysis, I’ll focus on the first two sentences of the conclusions:
The success of ev is largely due to active information introduced by the Hamming oracle and from the perceptron structure. It is not due to the evolutionary algorithm used to perform the search.
To explain the authors’ terminology, active information is defined quantitatively as a measure of relative search performance — to say that something provides N bits of active information is to say that it increases the probability of success by a factor of 2N. The Hamming oracle is a function that reports the Hamming distance between the its input and a fixed target. The perceptron structure is another function whose details aren’t important to this post. Figure 1 shows how these three components are connected in an iterative feedback loop.
The Perceptron Structure
To evaluate the performance benefit of the perceptron structure, the authors feed it random inputs and monitor the resulting outputs. It turns out that the desired output occurs 1050 times more often than it would if the perceptron structure were unbiased. Given this huge probability amplification, we would expect that ev would be doomed without the perceptron structure. Nothing in the paper disabuses us of that expectation.
But in a later note, Robert Marks says that the perceptron structure is dispensable:
Furthermore, we did not claim that ev would fail to converge without the perceptron structure. The lack of a perceptron structure would merely cause ev to take longer to converge. Without a perceptron structure ev would be essentially be a simple version of the “METHINKS IT IS LIKE A WEASEL” presented by Richard Dawkins.
Had Marks actually tested this scenario, he would have found that without the perceptron structure, ev actually performs better by a factor of about 3 rather than taking longer. (My implementation of ev is here, and ev without the perceptron structure is here.) So in spite of everything they say in the paper, the perceptron structure is actually detrimental to search performance.
The problem with the authors’ analysis is that it considers the perceptron structure outside the context of ev. Considered by itself, there is only one aspect of the perceptron structure that is relevant to performance, namely the fraction of possible inputs that yield the desired output. But in the context of an evolutionary search, there is another aspect that is even more important, namely the impact of the perceptron structure on the shape of the objective function. The perceptron structure makes the objective function more difficult to navigate, and this difficulty more than outweighs the benefit of the perceptron structure’s bias toward the target.
The Hamming Oracle and Evolutionary Algorithm
The authors state that the Hamming oracle is a “rich source of active information”. To support this claim, they point out that the Hamming oracle works really well with certain search algorithms, which is true. But it’s also true that it doesn’t work well with other algorithms, e.g. algorithms that don’t follow gradients. And with algorithms that ascend rather than descend hills, performance is abysmal as the search actively avoids the target, i.e. it tries to maximize the Hamming distance. So the Hamming oracle is neither good nor bad in itself — it’s the partnership with the search algorithm that’s good or bad.
So it’s inaccurate to say that the success of ev is due to the Hamming oracle and not the evolutionary algorithm. We could say that it’s due to both of them, although it’s more precise to say that it’s due to the synergy between the two. The same is true, of course, for the success of Dawkins’ WEASEL, which the EIL also claims is not due to the evolutionary algorithm.
As far as I can tell, the authors’ only justification for denying credit to the evolutionary algorithm is the fact that there are other algorithms that work even better with the Hamming oracle. This is like saying that a house fire isn’t due to the candles that started it, since flamethrowers are more effective at starting fires.
In summary, the claim that ev’s success is due to the perceptron structure is incorrect, as the perceptron structure is actually detrimental to ev’s performance. It is also incorrect to say that ev’s success is due to the Hamming oracle and not to the evolutionary algorithm. The correct conclusion is that ev succeeds because the search algorithm and the objective function are sufficiently well-matched.