Posted by Shivakumar Viswanathan on November 26, 2006 at 19:58:50:
Howdy all,
I'm due to present on Tuesday but my hands are a bit too full
with dissertation writing at the moment to pull together a
presentation so I thought we could read this interesting paper
instead.
Its a paper by Leslie Valiant (surprisingly) titled "Evolvability"
and was posted very recently on the repository of Harvard's
Electronic Colloquium on Computational Complexity server.
(the URL follows below). :) We may be looking at an imminent invasion
of COLT people into EC once this gets published in whatever journal
it has been submitted to.
Apart from his somewhat hasty dismissal of all of EC research in one
sentence, it lays out some interesting hypotheses about the technical
relation between evolutionary learning and cognitive learning which I
think merits some consideration (esp wrt coevolution).
- Shiva
--------------------------------------------------------
Evolvability
ECCC Report TR06-120, accepted on Sep 18, 2006.
http://eccc.hpi-web.de/eccc-reports/2006/TR06-120/index.html
Abstract: Living cells function according to complex mechanisms that
operate in different ways depending on conditions. Evolutionary theory
suggests that such mechanisms evolved as a result of a random search
guided by selection and realized by genetic mutations. However, as some
observers have noted, there has existed no theory that would explain
quantitatively which mechanisms can so evolve, and which are too complex.
In this paper we provide such a theory. As a starting point, we relate
evolution to the thory of computational learning, which addresses the
question of the complexity of recognition mechanisms that can be derived
from examples. We derive a quantitative notion of evolvability. The notion
quantifies the limited sizes of populations and the limited numbers of
generations that need to be sufficient for the evolution of significant
classes of mechanisms. It is shown that in any one phase of evolution
where selection is for one beneficial behavior, certain specific classes
of mechanisms are demonstrably evolvable, while certain others are
demonstrably not.
Keywords: evolution,, learning,, complexity
-------------------------------------------------------