- author = "Timo Koetzing and Frank Neumann and Reto Spoehel",
- title = "{PAC} Learning and Genetic Programming",
- booktitle = "GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation",
- year = "2011",
- editor = "Natalio Krasnogor and Pier Luca Lanzi and Andries Engelbrecht and David Pelta and Carlos Gershenson and Giovanni Squillero and Alex Freitas and Marylyn Ritchie and Mike Preuss and Christian Gagne and Yew Soon Ong and Guenther Raidl and Marcus Gallager and Jose Lozano and Carlos Coello-Coello and Dario Landa Silva and Nikolaus Hansen and Silja Meyer-Nieberg and Jim Smith and Gus Eiben and Ester Bernado-Mansilla and Will Browne and Lee Spector and Tina Yu and Jeff Clune and Greg Hornby and Man-Leung Wong and Pierre Collet and Steve Gustafson and Jean-Paul Watson and Moshe Sipper and Simon Poulding and Gabriela Ochoa and Marc Schoenauer and Carsten Witt and Anne Auger",
- isbn13 = "978-1-4503-0557-0",
- pages = "2091--2096",
- keywords = "genetic algorithms, genetic programming, Theory",
- month = "12-16 " # jul,
- organisation = "SIGEVO",
- address = "Dublin, Ireland",
-
DOI = "
doi:10.1145/2001576.2001857",
- publisher = "ACM",
- publisher_address = "New York, NY, USA",
- abstract = "Genetic programming (GP) is a very successful type of learning algorithm that is hard to understand from a theoretical point of view. With this paper we contribute to the computational complexity analysis of genetic programming that has been started recently. We analyse GP in the well-known PAC learning framework and point out how it can observe quality changes in the the evolution of functions by random sampling. This leads to computational complexity bounds for a simple tree GP algorithm for perfectly learning any member of a simple class of linear pseudo-Boolean functions. Furthermore, we show that the same algorithm on the functions from the same class finds good approximations of the target function in less time.",
-
notes = "
Not a linear GP system. No population. No crossover. Vandermonde identity. Chernoff bounds. Cites Feldman 2008/2009 and Valiant 1984 and 2009.
Also known as \cite{2001857} GECCO-2011 A joint meeting of the twentieth international conference on genetic algorithms (ICGA-2011) and the sixteenth annual genetic programming conference (GP-2011)",
