PAC Learning and Genetic Programming

Created by W.Langdon from gp-bibliography.bib Revision:1.2031

@InProceedings{Koetzing:2011:GECCO,
  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)",
}

Genetic Programming entries for Timo Koetzing Frank Neumann Reto Spoehel