How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Meta-Learning <s> Different researchers hold different views of what the term meta-learning exactly means. The first part of this paper provides our own perspective view in which the goal is to build self-adaptive learners (i.e. learning algorithms that improve their bias dynamically through experience by accumulating meta-knowledge). The second part provides a survey of meta-learning as reported by the machine-learning literature. We find that, despite different views and research lines, a question remains constant: how can we exploit knowledge about learning (i.e. meta-knowledge) to improve the performance of learning algorithms? Clearly the answer to this question is key to the advancement of the field and continues being the subject of intensive research. <s> BIB001 </s> How Complex Is Your Classification Problem?: A Survey on Measuring Classification Complexity <s> Meta-Learning <s> The classifier accuracy is affected by the properties of the data sets used to train it. Nearest neighbor classifiers are known for being simple and accurate in several domains, but their behavior is strongly dependent on data complexity. On the other hand, there are data complexity measures which aim to describe properties of the data sets. This work aims to show how data complexity measures can be efficiently used to predict the behavior of the Nearest Neighbor classifier. Seven data complexity measures and seventeen real datasets are used in the experimental study. Each data complexity measure is analyzed individually in order to find a relationship between its value and the accuracy of the classifier on a given dataset. No single measure used is good enough to predict the behavior of the Nearest Neighbor classifier. However, the combination of these measures provides a powerful tool to predict the accuracy of the Nearest Neighbor classifier. <s> BIB002
In Meta-learning (MtL), meta-knowledge about the solutions of previous problems is used to aid the solution of a new problem BIB001 . For this, a meta-dataset composed of datasets for which the solutions are known is usually built. They must be described by metafeatures, which is how the complexity measures are mainly used in this area. Some works previously described have made use of meta-learning, so they also fall in this category (e.g., , , and ). The work of is one of the first to present a general meta-learning framework based on a number of data complexity measures. employ the data complexity measures to characterize classification problems in a meta-learning setup designed to predict the expected accuracy of some ML techniques. compare classifier selection using cross-validation with meta-learning. BIB002 use the data complexity measures F1, F2, F3, N1, N2, T1, and T2 to predict the behavior of the NN classifier. In , an MtL recommender system able to predict the expected performance of noise filters in noisy data identification tasks is presented. For such, a meta-learning database is created containing meta-features, characteristics extracted from several corrupted datasets, along with the performance of some noise filters when applied to these datasets. Along with some standard meta-learning meta-features, the complexity measures N1 and N3 have a higher contribution to the prediction results. More recent works on meta-learning include: Cruz et al. , , , , and . In , for example, all of the complexity measures described in this work were employed to generate regression models able to predict the accuracies of four classifiers with very distinct biases: ANN, decision tree, kNN, and SVM. The estimated models were effective in such predictions. The top-ranked meta-features chosen by one particular regression technique (Random Forest-RF) were N3, N1, N2, density, and T1. All of them regard neighborhood-based information from the data (in the case of density, in the form of a graph built from the data). Another interesting usage of the complexity measures in the meta-analysis of classification problems is presented in . There, an instance space is built based on metafeatures extracted from a large set of classification problems, along with the performance of multiple classifiers. Among the meta-features used are the complexity measures F3, F4, L2, N1, and N4. The instance space framework provides an interesting overview of which are the hardest and easiest datasets and also to identify strengths and weaknesses of individual classifiers. The paper also presents a method to generate new datasets that better span the instance space.