PAC learning and genetic programming
Files
(Restricted Access)
Date
2011
Authors
Kotzing, T.
Neumann, F.
Spohel, R.
Editors
Krasnogor, N.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
GECCO'11: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, held in Dublin, Ireland, 12-16 July, 2011: pp.2091-2096
Statement of Responsibility
Timo Kötzing, Frank Neumann and Reto Spöhel
Conference Name
Genetic and Evolutionary Computation Conference (13th : 2011 : Dublin, Ireland)
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 analyze 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 linear 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.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
Copyright 2011 ACM