A Few Comments on A Vivisection of the ev Computer Organism

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.

Conclusions

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.

8 Replies to “A Few Comments on A Vivisection of the ev Computer Organism

  1. Elizabeth
    Ignored
    says:

    Thanks!

  2. petrushka
    Ignored
    says:

    Could we have a little background on ev, or a link to some background?

  3. Patrick
    Ignored
    says:

    Tom Schneider’s home page: http://www.ccrnp.ncifcrf.gov/~toms/
    His Ph.D. thesis: http://www.ccrnp.ncifcrf.gov/~toms/paper/schneider1986/latex/paper.pdf
    The ev paper, in various formats: http://www.lecb.ncifcrf.gov/~toms/paper/ev/

    I’m pleased to see this topic — ev is a particularly interesting use of a GA since it was used to verify conclusions that Dr. Schneider drew from his biological research.

  4. Patrick
    Ignored
    says:

    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.

    I’ve had a half-finished version of ev kicking around for a while and one of the issues I wanted to test was exactly this. It appears from the ev paper that the perceptron weight matrix is used just to introduce some non-linearity into the model of a recognizer. I suspect that the particular mechanism used is not particularly relevant to the results — it’s good to see that verified.

    I’m also starting to see a pattern from these authors. Both Dembski and Marks have made claims about ev without testing them. Ewert, Dembski, and Marks made claims about Dave Thomas’s Steiner GA implementation without testing them. Apparently being convinced that you’re right can save a lot of effort supporting your assertions.

  5. Joe G
    Ignored
    says:

    The correct conclusion is that ev succeeds because the search algorithm and the objective function are sufficiently well-matched.

    ev succeeds by design.

  6. Mike Elzinga
    Ignored
    says:

    Patrick: I’m also starting to see a pattern from these authors. Both Dembski and Marks have made claims about ev without testing them. Ewert, Dembski, and Marks made claims about Dave Thomas’s Steiner GA implementation without testing them. Apparently being convinced that you’re right can save a lot of effort supporting your assertions.

    This appears to be an extension of the general pattern of ID/creationism from its very beginning; to criticize science without ever having learned it or tested it.

  7. Patrick
    Ignored
    says:

    The history of ev is interesting reading as well: http://www.lecb.ncifcrf.gov/~toms/paper/ev/history.html

  8. Elizabeth
    Ignored
    says:

    Mike Elzinga: This appears to be an extension of the general pattern of ID/creationism from its very beginning; to criticize science without ever having learned it or tested it.

    Yes, training in empirical science rapidly teaches you that things ain’t necessarily so.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.