Free lunches for neural network search

ABSTRACT

In this paper we prove that for a variety of practical situations, the no-free-lunch (NFL) theorem does not apply to algorithms that search the space of artificial neural networks, such as evolutionary algorithms. We find, in particular, that, while conditions under which NFL applies exist, these require extremely restrictive symmetries on the set of possible problems which are unlikely encountered in practice. In other words, not all algorithms are equally good at finding neural networks that solve problems under all possible performance measures: a superior search algorithm for this domain does exist.

REFERENCES

• 1: A. Floares. Genetic programming and neural networks feedback linearization for modeling and controlling complex pharmacogenomic systems. In I. Bloch, A. Petrosino, and A. Tettamanzi, editors, Fuzzy Logic and Applications, 6th International Workshop, WILF 2005, Revised Selected Papers, volume 3849 of Lecture Notes in Computer Science, pages 178--187, Crema, Italy, Sept. 15-17 2005. Springer.
• 2: D. B. Fogel , L. J. Fogel , V. W. Porto, Evolving neural networks, Biological Cybernetics, v.63 n.6, p.487-493, 1990 [doi>10.1007/BF00199581]
• 3: F. Gruau. Cellular encoding of genetic neural networks. Technical report 92-21, Laboratoire de l'Informatique du Parallilisme. Ecole Normale Supirieure de Lyon, France, 1992.
• 4: Frédéric Gruau , Darrell Whitley , Larry Pyeatt, A comparison between cellular encoding and direct encoding for genetic neural networks, Proceedings of the First Annual Conference on Genetic Programming, July 28-31, 1996, Stanford, California
• 5: Christian Igel , Marc Toussaint, On classes of functions for which No Free Lunch results hold, Information Processing Letters, v.86 n.6, p.317-321, 30 June 2003 [doi>10.1016/S0020-0190(03)00222-9]
• 6: C. Igel and M. Toussaint. A no-free-lunch theorem for non-uniform distributions of target functions. Journal of Mathematical Modelling and Algorithms, 3:313--322, 2004.
• 7: U. Johansson, T. Lofstrom, R. Konig, and L. Niklasson. Building neural network ensembles using genetic programming. In G. G. Yen, L. Wang, P. Bonissone, and S. M. Lucas, editors, Proceedings of the 2006 IEEE Congress on Evolutionary Computation, pages 2239--2244, Vancouver, 6-21 July 2006. IEEE Press.
• 8: W. Kirchherr, M. Li, and P. Vitanyi. The miraculous universal distribution. Mathematical Intelligencer, 19:7--15, 1997.
• 9: H. Kitano. Designing neural networks using genetic algorithms with graph generation system. Complex Systems, 4(4):461--476, Aug. 1990.
• 10: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 11: W. B. Langdon, S. J. Barrett, and B. F. Buxton. Genetic programming for combining neural networks for drug discovery. In R. Roy, M. Koppen, S. Ovaska, T. Furuhashi, and F. Hoffmann, editors, Soft Computing and Industry Recent Applications, pages 597--608. Springer-Verlag, 10-24 Sept. 2001. Published 2002.
• 12: Foundations of genetic programming, Springer-Verlag New York, Inc., New York, NY, 2002
• 13: James L. McClelland , David E. Rumelhart, Explorations in parallel distributed processing: a handbook of models, programs, and exercises, MIT Press, Cambridge, MA, 1988
• 14: D. J. Montana and L. Davis. Training feedforward neural networks using genetic algorithms. In N. S. Sridharan, editor, Proceedings of the Eleventh International Joint Conference on Artificial Intelligence IJCAI-89, volume 1, pages 762--767, Detroit, MI, 20-25 Aug. 1989. Morgan Kaufmann, Palo Alto, CA.
• 15: D. E. Moriarty and R. Miikkulainen. Hierarchical evolution of neural networks. In Proceedings of the 1998 IEEE World Congress on Computational Intelligence, pages 428--433, Anchorage, Alaska, USA, 5-9 May 1998. IEEE Press.
• 16: Riccardo Poli , Mario Graff , Nicholas Freitag McPhee, Free lunches for function and program induction, Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms, January 09-11, 2009, Orlando, Florida, USA [doi>10.1145/1527125.1527148]
• 17: R. Poli, W. B. Langdon, and N. F. McPhee. A field guide to genetic programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk, 2008. (With contributions by J. R. Koza).
• 18: João Carlos Figueira Pujol , Riccardo Poli, Evolving the Topology and the Weights of Neural Networks Using a Dual Representation, Applied Intelligence, v.8 n.1, p.73-84, January-February 1998 [doi>10.1023/A:1008272615525]
• 19: J. C. F. Pujol , R. Poli, Synthesis of neural networks using a two-dimensional approach, Evolution of engineering and information systems and their applications, CRC Press, Inc., Boca Raton, FL, 1999
• 20: C. Schumacher, M. D. Vose, and L. D. Whitley. The no free lunch and problem description length. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages 565--570. Morgan Kaufmann, 2001.
• 21: M. J. Streeter. Two broad classes of functions for which a no free lunch result does not hold. In Proc. Genetic and Evolutionary Computation Conference GECCO-2003, pages 1418--1430. Morgan Kaufmann, 2003.
• 22: A. Tsakonas, V. Aggelis, I. Karkazis, and G. Dounias. An evolutionary system for neural logic networks using genetic programming and indirect encoding. Journal of Applied Logic, 2(3):349--379, 2004.
• 23: Darrell Whitley , Jonathan Rowe, Focused no free lunch theorems, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389254]
• 24: D. Whitley, T. Starkweather, and C. Bogart. Genetic algorithms and neural networks - optimizing connections and connectivity. Parallel Computing, 14(3):347--361, Aug. 1990.
• 25: D. Whitley and J. P. Watson. Complexity theory and the no free lunch theorem. In E. K. Burke and G. Kendall, editors, Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, chapter 11, pages 317--339. Springer US, 2005.
• 26: Bernard Widrow , Rodney Winter, Neural Nets for Adaptive Filtering and Adaptive Pattern Recognition, Computer, v.21 n.3, p.25-39, March 1988 [doi>10.1109/2.29]
• 27: D. Wolpert and W. Macready. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1):67--82, April 1997.
• 28: J. R. Woodward and J. R. Neil. No free lunch, program induction and combinatorial problems. In C. Ryan, T. Soule, M. Keijzer, E. P. K. Tsang, R. Poli, and E. Costa, editors, Genetic Programming, Proceedings of EuroGP'2003, volume 2610 of LNCS, pages 475--484, Essex, 14-16 Apr. 2003. Springer-Verlag.
• 29: B.-T. Zhang and H. Muhlenbein. Evolving optimal neural networks using genetic algorithms with Occam's razor. Complex Systems, 7:199--220, 1993.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.m Miscellaneous

General Terms:
Algorithms, Performance

Keywords:
evolutionary algorithms, neural networks, no-free-lunch