An empirical study of functional complexity as an indicator of overfitting in Genetic Programming

Leonardo Trujillo; Sara Silva; Pierrick Legrand; Leonardo Vanneschi

hal-00642530, version 1

An empirical study of functional complexity as an indicator of overfitting in Genetic Programming

Leonardo Trujillo () ¹, Sara Silva ^2, 3, Pierrick Legrand () ^4, 5, Leonardo Vanneschi ⁶

EuroGP (2011) 262-273

Abstract: Recently, it has been stated that the complexity of a solution is a good indicator of the amount of overfitting it incurs. However, measuring the complexity of a program, in Genetic Programming, is not a trivial task. In this paper, we study the functional complexity and how it relates with overfitting on symbolic regression problems.We consider two measures of complexity, Slope-based Functional Complexity, inspired by the concept of curvature, and Regularity-based Functional Complexity based on the concept of Holderian regularity. In general, both complexity measures appear to be poor indicators of program overfitting. However, results suggest that Regularity-based Functional Complexity could provide a good indication of overfitting in extreme cases.

1: Instituto Tecnológico de Tijuana
Instituto Tecnológico de Tijuana
2: Knowledge Discovery and Bioinformatics (KDBIO)
INESC-ID
3: Evolutionary and Complex Systems Group (ECOS Group)
CISUC
4: Institut de Mathématiques de Bordeaux (IMB)
CNRS : UMR5251 – Université Sciences et Technologies - Bordeaux I – Université Victor Segalen - Bordeaux II
5: ALEA (INRIA Bordeaux - Sud-Ouest)
INRIA – Université de Bordeaux – CNRS : UMR5251
6: Dipartimento di Informatica Sistemistica e Comunicazione (DISCo)
UNIVERSITÀ DEGLI STUDI DI MILANO-BICOCCA

hal-00642530, version 1
http://hal.archives-ouvertes.fr/hal-00642530
oai:hal.archives-ouvertes.fr:hal-00642530
From: Pierrick Legrand <>
Submitted on: Friday, 18 November 2011 11:28:15
Updated on: Monday, 21 November 2011 16:46:45

See detailed view

Associated documents

PDF :

DOI: 10.1007/978-3-642-20407-4_23

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Peer-reviewed conferences/proceedings</head>
<biblStruct type="inproceedings" xml:id="hal-00642530"><analytic>
<author><persName><forename>Leonardo</forename><surname>Trujillo</surname></persName>
<affiliation>
<orgName type="team">Instituto Tecnológico de Tijuana</orgName>
<country>MX</country>
<orgName type="institution">Instituto Tecnológico de Tijuana</orgName>
</affiliation>
</author>
<author><persName><forename>Sara</forename><surname>Silva</surname></persName>
<affiliation>
<orgName type="laboratory">KDBIO</orgName>
<orgName type="team">Knowledge Discovery and Bioinformatics</orgName>
<country>PT</country>
<orgName type="institution">INESC-ID</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">ECOS Group</orgName>
<orgName type="team">Evolutionary and Complex Systems Group</orgName>
<country>PT</country>
<orgName type="institution">CISUC</orgName>
</affiliation>
</author>
<author><persName><forename>Pierrick</forename><surname>Legrand</surname></persName>
<affiliation>
<orgName type="laboratory">IMB</orgName>
<orgName type="team">Institut de Mathématiques de Bordeaux</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5251</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">Université Victor Segalen - Bordeaux II</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Bordeaux - Sud-Ouest</orgName>
<orgName type="team">ALEA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université de Bordeaux</orgName>
<orgName type="institution">CNRS : UMR5251</orgName>
</affiliation>
</author>
<author><persName><forename>Leonardo</forename><surname>Vanneschi</surname></persName>
<affiliation>
<orgName type="laboratory">DISCo</orgName>
<orgName type="team">Dipartimento di Informatica Sistemistica e Comunicazione</orgName>
<country>IT</country>
<orgName type="institution">UNIVERSITÀ DEGLI STUDI DI MILANO-BICOCCA</orgName>
</affiliation>
</author>
<title type="main" level="a">An empirical study of functional complexity as an indicator of overfitting in Genetic Programming</title></analytic><monogr><title level="m" type="main">EuroGP</title><meeting>EuroGP</meeting><imprint><pubPlace><settlement>Turin</settlement><country>Italy</country></pubPlace><biblScope type="publicationDate">2011-00-00</biblScope><biblScope type="pp">262-273</biblScope></imprint></monogr><idno type="doi">10.1007/978-3-642-20407-4_23</idno><idno type="HALid">http://hal.archives-ouvertes.fr/hal-00642530</idno><idno type="HALFile">http://hal.archives-ouvertes.fr/hal-00642530/PDF/EuroGP_2011.pdf</idno></biblStruct>
</listBibl>
</listBibl>