Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/71908
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | PAC learning and genetic programming |
Author: | Kotzing, T. Neumann, F. Spohel, R. |
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 |
Publisher: | ACM Press |
Publisher Place: | New York |
Issue Date: | 2011 |
ISBN: | 9781450305570 |
Conference Name: | Genetic and Evolutionary Computation Conference (13th : 2011 : Dublin, Ireland) |
Editor: | Krasnogor, N. |
Statement of Responsibility: | Timo Kötzing, Frank Neumann and Reto Spöhel |
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. |
Keywords: | Genetic programming PAC learning theory runtime analysis |
Rights: | Copyright 2011 ACM |
DOI: | 10.1145/2001576.2001857 |
Published version: | http://dx.doi.org/10.1145/2001576.2001857 |
Appears in Collections: | Aurora harvest Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_71908.pdf | Restricted Access | 511.41 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.