Work on metalearning for algorithm selection has often been criticized because it mostly considers only the default parameter settings of the candidate base learning algorithms. Many have indeed argued that the choice of parameter values can have a significant impact on accuracy. Yet little empirical evidence exists to provide definitive support for that argument. Recent experiments do suggest that parameter optimization may indeed have an impact. However, the distribution of performance differences has a long tail, suggesting that in most cases parameter optimization has little effect on accuracy. In this paper, we revisit some of these results and use metalearning to characterize the situations when parameter optimization is likely to cause a significant increase in accuracy. In so doing, we show that 1) a relatively simple and efficient landmarker carries significant predictive power, and 2) metalearning for algorithm selection should be effected in two phases, the first in which one determines whether parameter optimization is likely to increase accuracy, and the second in which algorithm selection actually takes place.
The availability of a large number of classification learning algorithms together with the No Free Lunch theorem for classification present business users with a significant challenge, namely that of deciding which algorithm is likely to induce the most accurate model for their particular classification task. This selection process is further compounded by the fact that many classification learning algorithms include parameters, and the various possible settings of these parameters may give rise to models whose accuracy on the target classification task varies significantly. As a result, the algorithm selection problem in machine learning consists not only in choosing an algorithm, but rather in choosing an algorithm and an associated parameter setting. Formally, let:
L = fL1; L2; : : : ; Lng be a finite set of n classification learning algorithms (e.g., C4.5, Na¨ıve Bayes-NB, Backpropagation-BP, Support Vector Machine-SVM).
: : : PLkii be the set of parameter settings PLi = PL1i PL2i associated with Li, where each PLki represents one of the parameters of Li (e.g., PC1 4:5 =pruning indicator, PC2 4:5 =splitting criterion, : : :, PB1 P =number of hidden layers, PB2 P =learning rate, PB3 P =momentum term, : : :).
T = X Y be a training set for a classification task where X is a set of features and Y is a finite set of labels. I(L; P; T ) be the model induced by algorithm L with parameter setting P on some classification learning task T . Hence, I maps objects in X to labels in Y.
A(I) be the predictive accuracy of model I (typically measured by cross-validation).
The classification learning algorithm selection problem can be formulated as follows.
T for some classification learning task, find the pair (L ; P ) where L 2 L and P 2 PL , such that 8(L; P ) 2 L
PL A(I(L; P; T ))
A(I(L ; P ; T )).
The above formulation is generic in that it says nothing about the
process used to search the combined spaces of classification learning
algorithms and parameter settings to find the optimal algorithm.
Metalearning for classification learning algorithm selection is the specific
instance of that general problem wherein the search is effected by a
learning algorithm [
In practice, one has access to a set T = fT1; T2; : : : ; Tmg of m
training sets (corresponding to m classification learning tasks). For
each Tj , the learning algorithms in L, together with their parameter
settings, are used one at a time to induce a model on Tj . The pair
of classification learning algorithm and parameter setting that
maximizes A(I(L; P; Tj )) is recorded. Each Tj with its corresponding
winning pair becomes a training example for a (meta)learning
algorithm. Since storing complete learning tasks is unfeasible and likely
undesirable, one uses instead some characterization of learning tasks
by meta-features. Meta-features may be drawn from basic statistics
and information-theoretic measures (e.g., ratio of nominal features,
skewness, class entropy) [
One can now take a number of classification tasks, characterize
them via the function C, and record the corresponding meta-features
together with the accuracy of the best learning algorithm and
associated parameter setting. The classification learning algorithm
selection problem, as solved by metalearning, can then be reformulated as
follows.3
both a learning algorithm an associated parameter setting (e.g.,
see [
Given a set T m = f(C(T ); argmaxL2L;P 2PL A(I(L; P; T ))g of past classification learning episodes, together with a classification learning algorithm Lm, which may belong to L, and an associated parameter setting PLm : 1. Construct M = I(Lm; PLm ; T m). 2. For any training set T 0, (L ; P ) = M(T 0).
By convention, let PL0i denote the default parameter setting of Li, as determined by the implementation of Li under consideration (e.g., Weka, IBM SPSS Modeler). Most of the work in metalearning so far has addressed the above problem with the further assumption that for all learning algorithms the parameter setting is fixed to its default. This, of course, creates a much restricted, yet also greatly simplified, version of the selection problem, since the large, possibly infinite, space of parameter settings need not be considered at all. However, that restriction has also been the source of much criticism, and sometimes dismissal, by a part of the machine learning community, who has maintained that: Parameter Optimization Claim Parameter setting has a significant impact (for the better) on the predictive accuracy of classification learning algorithms.
It would seem that most metalearning researchers, and indeed most machine learning researchers, have taken this claim to be well founded, and considered ways to address it. There have been two main approaches.
Two-stage Metalearning. Some metalearning researchers have adopted a two-stage approach to metalearning, wherein they continue to use the restricted form of the Metalearning for Classification Learning Algorithm Selection problem to choose a learning algorithm, but then follow up with an optimization phase to find the best set of parameter values for the selected algorithm.4 The problem in this case, however, is that one may reach a suboptimal solution. Indeed, let L1 and L2 be two classification learning algorithms, such that, for some classification task T 0, M(T 0) = (L1; PL01 ). Then, L1 would be selected and its parameter setting optimized to PL1 . Yet, despite the fact that A(I(L1; PL01 ; T 0)) > A(I(L2; PL02 ; T 0)) (assuming the metalearner is accurate), it is entirely possible that there exists some parameter setting PLk2 of algorithm L2 such that A(I(L1; PL1 ; T 0)) < A(I(L2; PLk2 ; T 0)). In other words, the early greedy commitment to L1 makes it impossible to explore other parts of the combined spaces of learning algorithms and parameter settings.
Unrestricted Metalearning. Other metalearning researchers have
lifted the traditional restriction, and recently begun to design
solutions from the unrestricted Metalearning for Classification
Learning Algorithm Selection problem. Their systems seek to select
3 We recognize that it is possible to use metalearning to predict rankings of
learning algorithms (e.g., see [
Interestingly, and somewhat surprisingly, very few researchers have bothered to check the validity of the Parameter Optimization Claim. Yet, to the best of our knowledge —and as presented by most, it is just that: a claim. We have been hard-pressed to find any systematic study in the literature that addresses the impact of parameter settings over a wide variety of classification learning algorithms. What if the Parameter Optimization Claim does not hold in general? What if it only holds in some specific cases? Would it not be useful to know what these cases are? And what about using metalearning to characterize when the claim holds? We address these questions here. 2
There is one exception to our statement that the literature contains no
systematic study of the impact of parameter optimization on the
performance of classification learning algorithms, found in [
To make the relationship even clearer, consider Figure 2 that shows the cumulative distribution of the same datasets, where each successive bar represents the proportion of datasets for which the improvement in AUC due to parameter optimization is less than or equal to the value indicated on the x-axis in increments of 1%.
0 0 1 0 8 0 6
According to Figure 2, for 19% of the datasets considered parameter optimization offers no gain in performance. The ascent is actually very steep, as shown by the shaded portion of the distribution, reaching 80% of the datasets for an improvement in performance of no more than 5%. From 0% to 5%, the relationship is virtually linear (r=0.999) with a slope of 12. These results seem robust as an independent analysis of 129 datasets and 9 classification learning algorithms reveals that there is no gain in performance with optimization for about 15% of the datasets and 96% of the datasets exhibit less than 5% improvement.5
We note that the above analysis was not performed on a
peralgorithm basis. As stated, the differences in performance are
computed from among the best in 20 algorithms, which means that the
best optimized version could be obtained with algorithm A, while
the best default version for the same dataset would be obtained with
algorithm B. It is possible, however, that some classification
learning algorithms are more sensitive to parameter settings and may thus
be more likely to exhibit significant differences with parameter
optimization. It may be worthwhile in a future study to consider such
algorithm-level variation. In spite of this limitation, several
conclusions seem inescapable from the foregoing analysis:
1. Parameter optimization does not improve performance uniformly
across datasets.
5 There may be some overlap in the datasets used in this study and those used
in [
From a practitioner’s standpoint, the last two conclusions are particularly relevant. If no improvement is to be expected from parameter optimization, then one would gladly save the extra computational time required to effect it. Conversely, if a significant improvement can be expected and one is focused on maximizing predictive accuracy, then one would be willing to bear the extra cost. The question then, for such practitioners, is: Will the predictive accuracy on the classification learning task I am considering be improved by parameter optimization?
It should be obvious to machine learning researchers that if one labels the datasets falling under conclusion 2 above as no advantage and the datasets falling under conclusion 3 as advantage, one obtains a training dataset for a classification learning task. We propose to do exactly that and essentially take our own medicine, by applying machine learning to the problem of distinguishing between datasets that may benefit from parameter optimization and datasets that would not. Because our data consists of information about the performance of learning algorithms, this is an instance of metalearning. 3
As per standard metalearning practice, we build our training metadata by characterizing each of our 463 datasets by a set of metafeatures. However, because smaller datasets may produce unreliable meta-features, we remove from the analysis all of the datasets containing less than 100 instances. This leaves us with 326 datasets.
We use an existing R script that, for each dataset, creates a
metafeature vector by extracting over 68 meta-features, including
statistical and information-theoretic meta-features, landmarkers,
modelbased meta-features, and timing information [
The metalearning task consists in distinguishing datasets where parameter optimization is deemed to offer no advantage (class 0) from datasets where parameter optimization is likely to yield a performance advantage (class 1). Each meta-feature vector is labeled appropriately based on the observed difference in performance over its corresponding dataset. We use various threshold values to separate class 1 from class 0, as shown below.
There are two types of error our (meta)models can make. A false positive (FP) error is made when the model considers a class 0 dataset but labels it as class 1. When this happens, there is wasted effort in performing parameter optimization when no significant gain will be achieved by such optimization. Conversely, a false negative (FN) error is made when the model considers a class 1 dataset but labels it as class 0. When this happens, valuable parameter optimization is omitted and there is a resulting loss in predictive accuracy in the classification task under consideration. Assuming that a practitioner’s ultimate goal is to get the best accuracy possible on their specific classification task, one can argue that FN errors are more costly than FP errors, and thus should be minimized. This is, of course, is equivaT P lent to maximizing recall, R = T P +F N (where TP is the number of true positive classifications). Yet, one must be careful as it is trivial to maximize R by simply assigning all classification tasks to class 1. Clearly, this would defeat the purpose of the model and is unacceptable due to the unnecessary computational burden it places on the system. Hence, we focus on obtaining models with high recall, but also good precision, P = T PT+PF P .
We are faced at the metalevel with the same challenge of
selecting a (meta)learning algorithm adequate for the task at hand. We are
guided here by a desire for comprehensibility of the induced model
and the results of preliminary experiments. Hence, we use for our
metalearner, a decision tree learning algorithm, specifically Weka’s
J48, and implement the training and testing processes in
RapidMiner [
Threshold = 1.5 We begin by setting the threshold relatively low, assuming that there is an advantage to parameter optimization if the performance improvement exceeds 1.5%.
The default accuracy in this case is 61.96%, obtained by predicting class 1 uniformly. This, of course, produces maximum recall, R=100%, but very poor precision, P =61.96%.
Applying CFS selects the following mixed set of meta-features: attributes, kurtosis, joint entropy, NB, LDA and NN1. Further experimentation shows that performance can be improved still by using only joint entropy, NB and NN1. The confusion matrix is as follows.
This yields an accuracy of 79.17%, significantly above default, with both high recall R=86.14% and high precision P =81.31%. The decision tree is shown below. nn_1 <= 0.902439 | joint_entropy <= 0.606044: 0 (14.0/2.0) | joint_entropy > 0.606044 | | naive_bayes <= 0.952: 1 (208.0/30.0) | | naive_bayes > 0.952 | | | nn_1 <= 0.71134 | | | | joint_entropy <= 2.08461: 0 (2.0) | | | | joint_entropy > 2.08461: 1 (5.0) | | | nn_1 > 0.71134: 0 (12.0/2.0) nn_1 > 0.902439: 0 (85.0/15.0)
To further test the metamodel, we collected 42 independent
datasets with more than 100 instances each. It is possible that some
of these correspond to some of the tasks used in the training data.
However, all 463 training tasks have been binarized [
We extracted the meta-features of the 42 datasets, and ran the corresponding meta-feature vectors against the metamodel.6 The accuracy on the test datasets is 54.76%, which is rather poor given a default accuracy of 73.81%. However, the default is obtained by predicting class 0 uniformly. While the test accuracy is not very good, 6 As the results for the test datasets were obtained with a different set of classification learning algorithms and a different parameter optimization procedure, we are not entirely sure the comparison is fair. Yet, we feel there is value in including these results. recall is very high at R=90.91% (compared to R=0 for the default), with 10 of the 11 datasets of class 1 being predicted in class 1. This suggests that the model has picked up useful information to identify learning tasks where parameter optimization would be advantageous (i.e., expected improvement greater than 1.5%).
In addition to its own performance at the metalevel, we consider how the metamodel affects performance at the base level. To do so, we compare maxImp, the total amount of possible improvement due to parameter optimization to predImp, the amount of improvement one would obtain by using the metamodel. For each dataset d, let ld be d’s label, pd be d’s predicted class, and Id be the improvement one would experience if parameter optimization were used with d. Then, maxImp = X Id d i.e., maxImp is the sum of the individual improvement values across all of our 326 datasets. Here, maxImp = 949:26. Similarly, predImp = X d
Id if (pd = ld) ^ (ld = 1) 0 otherwise i.e., predImp is the sum of the improvement values for all datasets where the metamodel makes the correct class 1 prediction. We do not include correct class 0 predictions as these would artificially inflate the results. Here, predImp = 789:92. Hence, the metamodel would allow us to claim 83.21% of the total performance improvement available at the base level. 3.2
Threshold=2.5 We next raise the threshold, assuming that there is an advantage to parameter optimization if the performance improvement exceeds 2.5%.
The default accuracy in this case is 50.31%, obtained by predicting class 1 uniformly. This, again, produces maximum recall, R=100%, but very poor precision, P =50.31%.
Applying CFS selects the following mixed set of meta-features: kurtosis prep, normalized attribute entropy, joint entropy, NB, LDA, stump min gain and NN1. Further experimentation shows that performance can be improved still by using only kurtosis prep, normalized attribute entropy, joint entropy, NB and NN1. The confusion matrix is as follows.
This yields an accuracy of 74.52%, significantly above default, with both high recall R=84.15% and high precision P =70.77%. The decision tree is shown below. nn_1 <= 0.857143 | joint_entropy <= 0.606044 | | joint_entropy <= 0.508598 | | | kurtosis_prep <= 26.479217: 1 (2.0) | | | kurtosis_prep > 26.479217: 0 (2.0) | | joint_entropy > 0.508598: 0 (8.0) | joint_entropy > 0.606044 | | naive_bayes <= 0.969466: 1 (194.0/49.0) | | naive_bayes > 0.969466 | | | normalized_attribute_entropy <= 0.84991 | | | | kurtosis_prep <= 45.518635: 0 (2.0) | | | | kurtosis_prep > 45.518635: 1 (2.0) | | | normalized_attribute_entropy > 0.84991: 0 (7.0) nn_1 > 0.857143: 0 (109.0/15.0)
As with the threshold value of 1.5, using the metamodel against the test datasets produces poor accuracy (35.71% for a default of 88.10%), but recall is significantly better with R=60% (3 of the 5 datasets in class 1 are predicted correctly) against a default of R=0.
Considering performance at the base level, we have here predImp = 698:61, so that the metamodel would allow us to still claim 73.60% of the total performance improvement available. 3.3
Based on the distribution of performance improvements, raising the threshold will cause the majority class to shift to 0 and result in far fewer class 1 datasets. On the other hand, while fewer, correctly identifying these datasets offers the highest benefit to the practitioner as the expected improvement in accuracy with parameter optimization is rather significant. However, the metalearning task is also more difficult as the class distribution of the training data is rather skewed.
Setting the threshold to 5.0% results in a default accuracy of 83.44% with a model that predicts class 0 uniformly. While it was not possible in this case to improve on the default accuracy with the available set of meta-features, recall rose to R=25.94% (10 of the 54 datasets in class 1 are predicted correctly). Interestingly, CFS selected LDA and NN1, and while the tree induced without feature selection is a little larger than the previous ones, it also splits on NN1 at the root node. Using the metamodel against the test datasets produces reasonable accuracy (76.19%) but only because the test data is skewed in favor of class 0. Only two datasets belong to class 1 and neither is predicted correctly.
Setting the threshold to 10.0% results in a default accuracy of 96.93% again with a model that predicts class 0 uniformly. Only 10 datasets belong to class 1, making for a very imbalanced class distribution. Using all the meta-features, the induced decision tree has a slightly improved accuracy (97.85%), with recall R=30%. The root of the tree is mutual information. There are no datasets in our test set for which the improvement with parameter optimization exceeds 10%. 4
As mentioned previously, one of the biggest issues with parameter
optimization is the amount of time it takes to optimize the
parameters. In [
What this short study demonstrates is that it is possible to predict, with good recall value, whether parameter optimization will significantly increase a classification learning models accuracy by using the metafeatures of any particular dataset, which are less computationally intensive than the parameter optimization procedure. Of course, as the threshold increases, or as the expected performance improvement gets larger, the prediction becomes less accurate. Nevertheless, it is better than default.
One of the unexpected findings of our study, valid across almost
all metamodels, is that the root node of the decision tree is NN1. In
other words, a dataset’s performance on NN1 is indicative of whether
parameter optimization will significantly improve the performance
of learning algorithms trained against it. There are at least two
interesting things about this finding. First, it confirms prior work on
metalearning that suggest that landmarking meta-features are
generally better than other meta-features, especially NN1 and NB [
To further test the predictive power of NN1, we ran Weka’s linear regression on our dataset, without CFS, and with the target set to the actual percentage of accuracy improvement (Imp) observed for each dataset. The resulting model is shown below.
Imp = 1-------1-10680054370836..............40320578351434403303830963720599025881296351188122186793 ************** cskccmnasssssnlkualuottttttna_ernatituuuuuswtcsusrmmmmm1snoosaeippppp_esr_l_b_____+psi_e_summmsmrss1niitiaedio__tngenxanbpprfn_n__rrooamg++ameeprle+iippym_annarn++ta+++it+oino ++ -2.003 +
+
The correlation coefficient of the model is 0.40, and the relatively large multiplicative factor associated with NN1 in the model suggests its influence on the value of Imp. Furthermore, if we regress Imp on NN1 alone, we obtain the following very simple model. Imp =
The correlation coefficient of this simpler model is 0.44. There is still error in this model, and it will be interesting to see whether using only the NN1 metafeature could in general reasonably predict the datasets improvement if classification learning algorithm parameters are optimized. 5
We have showed that the observed improvement in performance due to parameter optimization in classification learning has a rather skewed distribution, with most datasets seeing none or very little improvement. However, there remains a portion of datasets for which parameter optimization has a significant impact. We have used metalearning to build a model capable of predicting whether parameter optimization can be expected to improve classification accuracy. As a result, it would seem that both current approaches to metalearning, the one that ignores parameter optimization and considers only default settings, and the other that applies parameter optimization in all cases, are misinformed. Instead, a two-phase approach where one first determines whether parameter optimization is likely to produce an improvement, and then if so applies it, is more appropriate.
Furthermore, one unexpected and very interesting side effect of our metalearning study is that our results show that good recall can be achieved at the metalevel, and that, with a very small set of efficient meta-features. In particular, it would appear that NN1 may serve as a great landmarker in this context.
For future work, it may be valuable to revisit error costs. In particular, we have argued here that FN errors were more costly than FP errors on the basis that practitioners are likely to wish to obtain the highest possible accuracy on their classification tasks. This is certainly also true when the computational cost of parameter optimization is prohibitive. Were computational cost not to matter, the best decision would be to always perform parameter optimization, and there would consequently be no need for a metamodel. In practice, however, it is well-known that parameter optimization is computationally intensive. As a result, FP errors may actually be rather costly, and possibly even more so than FN errors. In any case, there would seem to exist a range of operating conditions between these extremes, or different cost-benefits between FN and FP associated with parameter optimization. It may be interesting to perform a cost-sensitive analysis at the metalevel, for example, relating expected gain in performance (or threshold) and incurred cost. We cannot do this with the data available since we only have final performance improvement (after some fixed search time). We would need to re-run experiments to gather information about improvement over time allowed for optimization.