Evolvability

ABSTRACT

Living organisms function in accordance with complex mechanisms that operate in different ways depending on conditions. Darwin's theory of evolution suggests that such mechanisms evolved through variation guided by natural 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 article, we suggest such a theory. We treat Darwinian evolution as a form of computational learning from examples in which the course of learning is influenced only by the aggregate fitness of the hypotheses on the examples, and not otherwise by specific examples. We formulate a notion of evolvability that distinguishes function classes that are evolvable with polynomially bounded resources from those that are not. We show that in a single stage of evolution monotone Boolean conjunctions and disjunctions are evolvable over the uniform distribution, while Boolean parity functions are not. We suggest that the mechanism that underlies biological evolution overall is “evolvable target pursuit”, which consists of a series of evolutionary stages, each one inexorably pursuing an evolvable target in the technical sense suggested above, each such target being rendered evolvable by the serendipitous combination of the environment and the outcomes of previous evolutionary stages.

REFERENCES

• 1: Bäck, T., Fogel, D. B., and Michalewisz, Z. (Eds.). 1997. Handbook of Evolutionary Computation. Oxford Univ. Press, Oxford, UK.
• 2: Berjerano, G. Pheasant, M., Makunin, I., Stephen, S., Kent, W. J., Mattick, J. S., and Haussler, D. 2004. Ultraconserved elements in the human genome. Science 304, 1321--1325.
• 3: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 4: Bürger, R. 2000. The Mathematical Theory of Selection, Recombination, and Mutation. Wiley, Chichester, UK.
• 5: Darwin, C. 1859. On the Origin of Species by Means of Natural Selection. John Murray, London, UK.
• 6: Dermitzakis, E. T., Raymond, A., and Antonarakis, S. E. 2005. Conserved nongenic sequences—An unexpected feature of mammalian genomes. Nat. Rev. Genet. 6, 2(Feb.), 151--157.
• 7: Drake, J. W., Charlesworth, B., Charlesworth, D., and Crow, F. J. 1998. Rates of spontaneous mutation. Genetics 148, 1667--1686.
• 8: Andrzej Ehrenfeucht , David Haussler, A general lower bound on the number of examples needed for learning, Information and Computation, v.82 n.3, p.247-261, Sep. 1989 [doi>10.1016/0890-5401(89)90002-3]
• 9: Vitaly Feldman, Evolvability from learning algorithms, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374465]
• 10: Paul Fischer , Hans Ulrich Simon, On learning ring-sum-expansions, SIAM Journal on Computing, v.21 n.1, p.181-192, Feb. 1992 [doi>10.1137/0221014]
• 11: Fisher, R. A. 1930. The Genetical Theory of Natural Selection. Oxford Univ. Press, Oxford, UK.
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: David Helmbold , Robert Sloan , Manfred K. Warmuth, Learning integer lattices, SIAM Journal on Computing, v.21 n.2, p.240-266, April 1992 [doi>10.1137/0221019]
• 14: Hoeffding, W. 1963. Probability inequalities for sums of bounded random variables. J. Amer. Stat. Assoc. 58, 13.
• 15: Michael Kearns, Efficient noise-tolerant learning from statistical queries, Journal of the ACM (JACM), v.45 n.6, p.983-1006, Nov. 1998 [doi>10.1145/293347.293351]
• 16: Michael Kearns , Leslie Valiant, Cryptographic limitations on learning Boolean formulae and finite automata, Journal of the ACM (JACM), v.41 n.1, p.67-95, Jan. 1994 [doi>10.1145/174644.174647]
• 17: Michael J. Kearns , Umesh V. Vazirani, An introduction to computational learning theory, MIT Press, Cambridge, MA, 1994
• 18: Kimura, M. 1968. Evolutionary rate at the molecular level. Nature 217, 624--626.
• 19: Kumar, S., and Subramanian, S. 2002. Mutation rates in mammalian genomes. Proc. Nat. Acad. Sci. 99, 803--808.
• 20: Maynard-Smith, J. 1982. Evolution and the Theory of Games. Cambridge Univ. Press, Cambridge, UK.
• 21: Papadimitriou, C. H. 1994. Computational Complexity. Addison-Wesley, Reading, MA.
• 22: Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988 [doi>10.1145/48014.63140]
• 23: Roff, D. A. 1997. Evolutionary Quantitative Genetics. Chapman & Hall, New York.
• 24: Ros, J. P. 1993. Learning Boolean functions with genetic algorithms: A PAC analysis. In Foundations of Genetic Algorithms, L. D. Whitley, Ed., Morgan-Kaufmann, San Mateo, CA, 257--275.
• 25: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• 26: Leslie G. Valiant, Robust logics, Artificial Intelligence, v.117 n.2, p.231-253, March 2000 [doi>10.1016/S0004-3702(00)00002-3]
• 27: Valiant, L. G. 2006. Knowledge infusion. In Proceedings of the 21st National Conference on Artificial Intelligence. (AAAI06). 1546--1551.
• 28: Wagner, G. P., and Altenberg, L. 1996. Complex adaptations and the evolution of evolvability. Evolution 50, 3, 967--976.
• 29: Ingo Wegener, Theoretical Aspects of Evolutionary Algorithms, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.64-78, July 08-12, 2001
• 30: Wright, S. 1968--1978. Evolution and the Genetics of Populations, A Treatise. University of Chicago Press, Chicago, IL.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Self-modifying machines (e.g., neural networks)

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms, Theory

Keywords:
Evolvable, PAC learning, SQ learning