Seminar on Evolvability, Natural Algorithms and Learning
We will discuss the organization at the preparatory meeting.
A preparatory meeting will take place on January 16th at 4pm. Kurt Mehlhorn will introduce the subject and we will discuss organizational matters.
Persons interested in the seminar should enter their name
at Doodle Poll.
The goal of the seminar is to understand the following three papers.
- Leslie G. Valiant: Evolvability
Abstract: Living organisms function according to complex mechanisms that
operate in different ways depending on conditions. Evolutionary theory
suggests that such mechanisms evolved as result of a random search guided
by selection. However, there has existed no theory that would explain
quantitatively which mechanisms can so evolve in realistic population
sizes within realistic time periods, and which are too complex. In this paper
we suggest such a theory. Evolution is treated as a form of computational
learning from examples in which the course of learning is influenced only
by the fitness of the hypotheses on the examples, and not otherwise by the
specific examples. We formulate a notion of evolvability that quantifies
the evolvability of different classes of functions. It is shown that in
any one phase of evolution where selection is for one beneficial behavior,
monotone Boolean conjunctions and disjunctions are demonstrably evolvable
over the uniform distribution, while Boolean parity functions are
demonstrably not. The framework also allows a wider range of issues in
evolution to be quantified. We suggest that the overall mechanism that
underlies biological evolution is evolvable target pursuit, which consists
of a series of evolutionary stages, each one pursuing an evolvable target
in our technical sense, each target being rendered evolvable by the
serendipitous combination of the environment and the outcome of previous
- Leslie Valiant: A Theory of the Learnable
ABSTRACT: Humans appear to be able to learn new
concepts without needing to be programmed explicitly in
any conventional sense. In this paper we regard learning as
the phenomenon of knowledge acquisition in the absence of
explicit programming. We give a precise methodology for
studying this phenomenon from a computational viewpoint.
It consists of choosing an appropriate information gathering
mechanism, the learning protocol, and exploring the class of
concepts that can be learned using it in a reasonable
(polynomial) number of steps. Although inherent algorithmic
complexity appears to set serious limits to the range of
concepts that can be learned, we show that there are some
important nontrivial classes of propositional concepts that
can be learned in a realistic sense.
- Bernard Chazelle: Natural Algorithms
We provide further evidence that the study of complex
self-organizing systems can benefit from an algorithmic
perspective. The subject has been traditionally viewed
through the lens of physics and control theory. Using tools
typically associated with theoretical computer science, we
settle an old question in theoretical ecology: bounding the
convergence of bird flocks. We bound the time to reach
steady state by a tower-of-twos of height linear in the number
of birds. We prove that, surprisingly, the tower-of-twos
growth is intrinsic to the model. This unexpected result
demonstrates the merits of approaching biological dynamical
systems as natural algorithms and applying algorithmic
techniques to them.
- Background Material
At Starlings on Otmor you can find
a video of a flock of starlings. STARFLAG, the
Web page of an EU-project on studying starlings in flight is also interesting. The paper by
Cucker and Smale is a predecessor of Chazelle's work.
Kearns is an important background paper for Valiant's paper on Evolvability, and Feldman is a follow-up paper.
I will put more papers into this directory without explicitly mentioning them in the text.
Somebody should set up a wiki for this course.
Last modified: Mon Feb 23 13:27:44 CET 2009