Skip to main content
main-content
Top

Hint

Swipe to navigate through the chapters of this book

2016 | OriginalPaper | Chapter

Genetic Programming Model Regularization

Authors: César L. Alonso, José Luis Montaña, Cruz Enrique Borges

Published in: Computational Intelligence

Publisher: Springer International Publishing

share
SHARE

Abstract

We propose a tool for controlling the complexity of Genetic Programming models. The tool is supported by the theory of Vapnik-Chervonekis dimension (VCD) and is combined with a novel representation of models named straight line program. Experimental results, implemented on conventional algebraic structures (such as polynomials), show that the empirical risk, penalized by suitable upper bounds for the Vapnik-Chervonenkis dimension, gives a generalization error smaller than the use of statistical conventional techniques such as Bayesian or Akaike information criteria.
Literature
2.
go back to reference Alonso, C.L., Montaña, J.L.. Puente, J.: Straight line programs: a new linear genetic programming approach. In:Proceedings of the 20th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp. 571–524 (2008) Alonso, C.L., Montaña, J.L.. Puente, J.: Straight line programs: a new linear genetic programming approach. In:Proceedings of the 20th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp. 571–524 (2008)
3.
4.
go back to reference Berkowitz, S.J.: On computing the determinant in small parallel time using a small number of processors. Inf. Process. Lett. 18, 147–150 (1984) MathSciNetCrossRefMATH Berkowitz, S.J.: On computing the determinant in small parallel time using a small number of processors. Inf. Process. Lett. 18, 147–150 (1984) MathSciNetCrossRefMATH
5.
go back to reference Bernadro, J., Smith, A.: Bayesian Theory. Willey, New York (1994) Bernadro, J., Smith, A.: Bayesian Theory. Willey, New York (1994)
6.
go back to reference Burguisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic Complexity Theory. Springer, New York (1997) Burguisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic Complexity Theory. Springer, New York (1997)
7.
go back to reference Cherkassky, V., Yunkian, M.: Comparison of model selection fo regression. Neural Comput. 15(7), 1691–1714 (2003) CrossRefMATH Cherkassky, V., Yunkian, M.: Comparison of model selection fo regression. Neural Comput. 15(7), 1691–1714 (2003) CrossRefMATH
8.
go back to reference Gabrielov, A.N., Vorobjov, N.: Complexity of Computations with Pfaffian and Noetherian Functions, Normal Forms, Bifurcations and Finiteness Problems in Differential Equations. Kluwer, Dordrecht (2004) Gabrielov, A.N., Vorobjov, N.: Complexity of Computations with Pfaffian and Noetherian Functions, Normal Forms, Bifurcations and Finiteness Problems in Differential Equations. Kluwer, Dordrecht (2004)
9.
go back to reference Giusti, M., Heinz, J.: La Détermination des Points Isolés et la Dimension dúne Varieté Agebrique Peut se Faire en Temps Polynomial, Computational Algebraic Geometry and Commutative Algebra, Symposia Matematica XXXIV, Eisenbud, D, Robbiano, L. (eds.), pp. 216–256. Cambridge University Press, Cambridge (1993) Giusti, M., Heinz, J.: La Détermination des Points Isolés et la Dimension dúne Varieté Agebrique Peut se Faire en Temps Polynomial, Computational Algebraic Geometry and Commutative Algebra, Symposia Matematica XXXIV, Eisenbud, D, Robbiano, L. (eds.), pp. 216–256. Cambridge University Press, Cambridge (1993)
10.
go back to reference Giusti, M., Heintz, J., Morais, J., Morgentern, J.E., Pardo, L.M.: Straight line programs in geometric elimination theory. J. Pure Appl. algebra 124, 121–146 (1997) MathSciNet Giusti, M., Heintz, J., Morais, J., Morgentern, J.E., Pardo, L.M.: Straight line programs in geometric elimination theory. J. Pure Appl. algebra 124, 121–146 (1997) MathSciNet
11.
go back to reference Goldberg, P., Jerrum, M.: Bounding the vapnik-chervonenkis dimension of concept classes parametrizes by real numbers. Mach. Learn. 18, 131–148 (1995) MATH Goldberg, P., Jerrum, M.: Bounding the vapnik-chervonenkis dimension of concept classes parametrizes by real numbers. Mach. Learn. 18, 131–148 (1995) MATH
12.
go back to reference Gori, M., Maggini, M., Martinelli, E., Soda, G.: Inductive inference from noisy examples using the hybrid finite state filter. IEEE Trans. Neural Networks 9–3, 571–575 (1998) CrossRef Gori, M., Maggini, M., Martinelli, E., Soda, G.: Inductive inference from noisy examples using the hybrid finite state filter. IEEE Trans. Neural Networks 9–3, 571–575 (1998) CrossRef
13.
go back to reference Heintz, J., Roy, M.F., Solerno, P.: Sur la Complexité du Principe de Tarski-Seidenberg. Bulletin de la Societé Mathematique de France 118, 101–126 (1990) MathSciNetMATH Heintz, J., Roy, M.F., Solerno, P.: Sur la Complexité du Principe de Tarski-Seidenberg. Bulletin de la Societé Mathematique de France 118, 101–126 (1990) MathSciNetMATH
14.
go back to reference Koza, J.: Genetic Programming: on the Programming of Computers by Means of Natural Selection. The MIT Press, Cambridge (1992) Koza, J.: Genetic Programming: on the Programming of Computers by Means of Natural Selection. The MIT Press, Cambridge (1992)
15.
go back to reference Nikolaev, N.Y., Iba, H.: Regularization approach to inductive genetic programming. IEEE Trans. Evol. Comput. 5(4), 359–375 (2001) CrossRef Nikolaev, N.Y., Iba, H.: Regularization approach to inductive genetic programming. IEEE Trans. Evol. Comput. 5(4), 359–375 (2001) CrossRef
16.
go back to reference Okley, H.: In: Kinnear, K. (ed.) Advances in Genetic Programming. Two scientific applications of Genetic Programming: Stack filters and nonlinear fitting to chaotic data, pp. 369–389. MIT Press, Cambridge (1994) Okley, H.: In: Kinnear, K. (ed.) Advances in Genetic Programming. Two scientific applications of Genetic Programming: Stack filters and nonlinear fitting to chaotic data, pp. 369–389. MIT Press, Cambridge (1994)
17.
go back to reference Poli, R., Cagnoni, S.: In: Koza, J.R., Deb, K., Dorigo, M., Fogel, D.B., Garzon, M., Iba, H., Riolo, R.L. (eds.) Evolution of Pseudo-coloring Algoritms for Image Enhancement with Interactive Genetic Programming, pp. 269–277. MIT Press, Cambridge (1997) Poli, R., Cagnoni, S.: In: Koza, J.R., Deb, K., Dorigo, M., Fogel, D.B., Garzon, M., Iba, H., Riolo, R.L. (eds.) Evolution of Pseudo-coloring Algoritms for Image Enhancement with Interactive Genetic Programming, pp. 269–277. MIT Press, Cambridge (1997)
18.
go back to reference Shaoning, P., Kasabov, N.: Inductive vs transductive inference. global vs local models: SVM, TSVM and SVMT for gene expression classification problems. In: Proceedings IEEE International Joint Conference on Neural Networks, vol. 2, pp. 1197–1202 (2004) Shaoning, P., Kasabov, N.: Inductive vs transductive inference. global vs local models: SVM, TSVM and SVMT for gene expression classification problems. In: Proceedings IEEE International Joint Conference on Neural Networks, vol. 2, pp. 1197–1202 (2004)
19.
go back to reference Tackett, W.A., Carmi, A.: In: Kinnear, K. (ed.) The Donut Problem: Scalability and Generalization in Genetic Programming, Advances in Genetic Programming. MIT Press, Cambridge (1994) Tackett, W.A., Carmi, A.: In: Kinnear, K. (ed.) The Donut Problem: Scalability and Generalization in Genetic Programming, Advances in Genetic Programming. MIT Press, Cambridge (1994)
20.
go back to reference Tenebaum, J.B., Griffiths, T.L., Kemp, C.: Theory Based Bayesian Models of Inductive Learning and Reasoning. Trends in Cognitive Sciences, Kingston, vol. 10(7), pp. 309–318 (2006) Tenebaum, J.B., Griffiths, T.L., Kemp, C.: Theory Based Bayesian Models of Inductive Learning and Reasoning. Trends in Cognitive Sciences, Kingston, vol. 10(7), pp. 309–318 (2006)
21.
go back to reference Vapnik, V., Chervonenkis, A.: Ordered risk minimization. Autom. Remote Control 34, 1226–1235 (1974) MathSciNetMATH Vapnik, V., Chervonenkis, A.: Ordered risk minimization. Autom. Remote Control 34, 1226–1235 (1974) MathSciNetMATH
22.
go back to reference Vapnik, V.: Statistical Learning Theory. Willey, New York (1998) Vapnik, V.: Statistical Learning Theory. Willey, New York (1998)
Metadata
Title
Genetic Programming Model Regularization
Authors
César L. Alonso
José Luis Montaña
Cruz Enrique Borges
Copyright Year
2016
DOI
https://doi.org/10.1007/978-3-319-23392-5_6

Premium Partner