Why Classifying Search Algorithms is Essential

Citation

Woodward J & Swan J (2010) Why Classifying Search Algorithms is Essential. In: 2010 IEEE International Conference on Progress in Informatics and Computing (PIC-2010). Volume 1. 2010 IEEE International Conference on Progress in Informatics and Computing (PIC), Shanghai, China, 10.12.2010-12.12.2010. Piscataway, NJ, USA: IEEE, pp. 285-289. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5687448&abstractAccess=no&userType=inst

Abstract
In chemistry, the periodic table of elements was a huge leap of progress. It allowed elements to be placed in a table allowing their classification. More importantly, it allowed predictions to be made about their properties, and in some cases predictions about elements which had not even been discovered at the time the periodic table was proposed. We argue that the current state of search methodologies is analogous to the state of chemistry before the arrival of the periodic table, and such a classification system is well overdue. Many machine learning research papers are currently published on the premise that the proposed algorithm does better on a particular data set than another algorithm. This approach, while it does produce better results on the given data set, does not produce an understanding of why a particular algorithm performs well on a particular problem. The No Free Lunch Theorem, while stating this is impossible over all data sets, also provides a possible framework. We state why the performance table associated with No Free Lunch (which has rows and columns similar to the periodic table), which is exactly what we are looking for, is unworkable, as problems cannot be indexed or enumerated in practice. We believe the classification of algorithms and problems is the biggest issue facing machine learning today. Progress in science is often brought about by asking the right questions, before finding the answers, and it is this question we address in this paper. Therefore, the contribution of this paper is raising the profile of the challenge of classifying algorithms and problems. An underlying aim is to reduce the number of papers with titles of the form "Algorithm X Applied to Problem Y", or simply "A New Algorithm", as new algorithms should only be introduced with an intended class of problem instances in mind.

Keywords
bias; generalization; induction; machine learning; no free lunch theorems; optimization; search