Towards meta-learning for multi-target regression problems
Gabriel Jonas Aguiar Everton José Santana Saulo Martiello Mastelini Rafael Gomes Mantovani Sylvio Barbon Jr
cs.LG stat.ML





    

Towards meta-learning for multi-target 
regression problems
    
    
    Gabriel J. Aguiar 1,
    Everton J. Santana 1,
    Saulo M. Mastelini 2,
    Rafael G. Mantovani 3,
    Sylvio Barbon Jr 1

    1 Computer Science Department, Londrina State University, Londrina - PR, Brazil 

    2 Institute of Mathematics and Computer Sciences, University of São Paulo (ICMC/USP), São Carlos - SP, Brazil 

    3 Computer Engineering Department, Federal Technology University, Campus of Apucarana - PR, Brazil
    
 E-mail: gjonas@uel.br, evertonsantana@uel.br, mastelini@usp.br, rafaelmantovani@utfpr.edu.br, barbon@uel.br

    
=============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




Several multi-target regression 
methods were developed in the last years aiming at improving predictive performance by exploring inter-target correlation within the problem. However, none of these methods outperforms the others for all problems. This motivates the development of automatic approaches to recommend the most suitable multi-target regression method. 
In this paper, we propose a meta-learning system to recommend the best predictive 
method for a given multi-target regression problem. We performed experiments with a meta-dataset generated by a total of 648 synthetic datasets. These datasets were created to explore distinct inter-targets characteristics toward recommending the most promising 
method. In experiments, we evaluated four different 
algorithms with different biases as meta-learners.

Our meta-dataset is composed of 58 meta-features, based on: statistical information, correlation characteristics, linear landmarking, from the distribution and smoothness of the data, and has four different meta-labels.

Results showed that induced meta-models were able to recommend the best 
method for different base level datasets with a balanced accuracy superior to 70% using a Random Forest meta-model, which statistically outperformed the meta-learning baselines. 




Multi-target, Regression, Meta-learning


mlMLMachine Learning
mtlMtLMeta-learning
oobOOBOut-of-Bag

annANNArtificial Neural Network
svmSVMSupport Vector Machine
rfRFRandom Forest
xgbXGBoostExtreme Gradient Boosting
nbNBNaive Bayes
cdCDCritical Difference
cvCVCross-Validation

motcMOTCMulti-output Tree Chaining
stSTSingle-target
sstSSTStacking Single Target
ercERCEnsemble of Regressor Chains
mtrMTRMulti-target Regression
mlcMLCMulti-label Classification

rrmseaRRMSEAverage Relative Root Mean Square Error
rmseRMSERoot Mean Square Error
corCORCorrelation
linLINLinearity









§ INTRODUCTION


ml approaches have been providing significant advances in understanding and modeling problems from the broadest knowledge fields. A considerable part of the ml solutions takes advantage of supervised learning algorithms which explore the information, i.e., input and prediction target, from the problem data to learn a pattern. However, data from several real problems present more than one target. In this case, when a dataset presents multiple continuous targets, we call it a multi-target regression problem. 

Currently, there are several methods in the literature addressing this type of problem. The most straightforward approach, referred to as st regression, is to create a single model for each target disregarding the possible inter-target correlation. mtr is an alternative approach that, besides using the original input features, exploits the statistical correlation among the outputs. The mtr methods have been applied to solve many problems <cit.>, leading to improvement in the predictive performance over st methods. However, each method has specific characteristics and has been effective for different problems. 

Selecting the most suitable algorithm for a given problem requires extensive experimental evaluation, which demands massive computational resources (particularly processing time) and specialists <cit.>. On the other hand, a mtr method could be automatically selected when addressed as an output in an algorithm selection (or recommendation) problem by  mtl <cit.>.

The mtl core concept is to use the knowledge acquired from previous similar problems to recommend the most suitable algorithm, for a new unseen dataset. In the last years, mtl has been employed in different contexts, such as tasks to select <cit.>, rank <cit.> and predict <cit.> the performance of ml algorithms and employing them on a new dataset. 

Our hypothesis holds that mtl can be applied to mtr problems and recommend the most suitable method for new unseen problems. Thus, in this study, we propose a recommendation system able to predict the best mtr method for a new dataset. For such, experiments were carried out with meta-datasets generated with a total of 648 synthetic regression problems, also generated to explore the different inter-targets characteristics. In the experiments, the st approach and three mtr methods were evaluated: sst <cit.>, motc <cit.> and  erc <cit.>. Thus, the meta-knowledge was generated with different datasets, with different biases, often used for multi-target benchmarking <cit.>. In the experiments, we compared nb, rf, xgb and svm as meta-learners using their default hyperparameter values.

This paper is structured as follows. Section <ref> presents the background on using mtl for mtr; section <ref> describes the experimental methodology; the results are discussed in section <ref>; finally, the conclusions and future work are presented.






§ BACKGROUND




Many ml algorithms have been proposed for different prediction tasks. However, the 'No free lunch' theorem <cit.> states there is no one algorithm suitable for every dataset. A possible solution is to recommend the best algorithm for each problem.

The notion of algorithm recommendation problems was introduced in <cit.>, grounded on selecting one algorithm from a portfolio of options. Given a set of datasets 𝒫 composed of instances from a distribution 𝒬; a set of algorithms 𝒜; and a performance measure  ℳ : 𝒫 × 𝒜→ℝ; 
the algorithm recommendation problem is to find a mapping m : 𝒫→𝒜 that optimizes the expected performance measure for the instance problems described in 𝒬.

In practice, there are some alternatives to induce this mapping between algorithms 
and datasets/problems: 
 one of them is through the mtl <cit.>.
The core concept of  mtl is to exploit past learning experiences in a particular type of task and solutions by adapting learning algorithms and data mining processes.
This is done by extracting features from a dataset, named as meta-features, to represent a dataset and the performance of the ml algorithms when applied on it. The relation between meta-features and the ml performance provides information to select the most suitable algorithm for new datasets. Thus, ml algorithms are applied to a meta-dataset, whose examples are described in terms of meta-features, to induce a meta-model.

In the last years, mtl has been used for: 
algorithm selection <cit.>, 
segmentation algorithm recommendation <cit.>, and hyperparameter tuning <cit.>.






 §.§ Multi-target regression


mtr is related to the problems with multiple continuous outputs. In this way, to solve these problems a function or a collection of functions ℋ that models the relationship from input (𝒳) to output (𝒴) is created. If 𝒳 is composed of m input variables and 𝒴 has d targets, the prediction problem can be stated as:


    ℋ: 𝒳_1 … m𝒴_1 … d


Then, for each vector that belongs to 𝒳, ℋ is capable of predicting an output vector that is the best approximation of the true output vector <cit.>.

mtr methods might use one of two main procedures: Algorithm Adaptation or Problem Transformation <cit.>. The first one adapts well-known algorithms, such as: ann; rf and svm, to deal with multiple outputs, modeling the problem at once. On the other hand, problem transformation methods modify the original input task aiming at exploring the correlation among the targets. 
Spyromitros-Xioufis et al. <cit.> proposed two problem transformation methods that contributed notably to the area:  sst and erc. The sst method builds one model for each target d, which are iteratively stacked to the input, and induced new d models over the augmented input. The prediction of these last models are the final predictions.

Differently, the erc method creates regressors based on a different order of the targets. For each order, models are trained sequentially: the model that is trained for the second response considers the model trained for the first one. Both models are used in the induction of the third regressor, and so forth. In the end, for each target, the prediction is the average of the predictions of the trained regressors.

These both methods inspired the development of new mtr methods <cit.>. One of them, the motc <cit.>, is a method that requires less memory and training time than ERC, besides generating an interpretation of the targets' dependencies. It creates regressors from a tree built based on correlation assessment of the targets. The training of the models is performed from the leaves to the root, stacking the models' predictions as new inputs.






 §.§ Meta-learning for Multi-target regression


During the literature research, we did not find any papers employing mtl for mtr. However, in some studies, the authors investigated similar problems, such as mlc problems.

Considering ℒ the set of labels, differently from Single-label classification task, which there is just one label L_i ∈ℒ to predict for each dataset's example,  in mlc tasks the examples are associated with more than one label, i.e., it is necessary to learn how to associate the example with a subset of ℒ.

Similarly to the problem investigated in this paper, many mlc methods <cit.> were proposed, but there is few research concerning when each method is more efficient. 

To select a mlc method and configure their hyperparameters for a given dataset, de Sá et al. <cit.> applied Evolutionary Algorithms (EA). This study was carried using 31 MLC methods, in 3 different datasets. The EA selection outperformed or at least draw the baselines in most of the cases. 
Also in this direction, the pioneering research based on mtl was done by Chekina et al. <cit.>. They evaluated 11 different multi-label methods, grouping them into: Single-Classifier Algorithms and Ensemble-Classifier Algorithms. They performed experiments in 12 datasets of mlc from the literature. The results showed that employing mtl to select one method in mlc tasks 
is promising, since in most of the  experimented cases, to apply the recommendation through mtl was better than selecting one method for all tasks or selecting it randomly.

mlc tasks are similar to mtr tasks, since both deal with the prediction of multiple targets using a common set of features. The main difference is the type of the predicted variable: while in mlc the targets are binary, in mtr the outputs are continuous. Indeed, both tasks can be seen as a more general learning task of multi-target prediction with different types of variables to predict <cit.>. Therefore, given that mtl was successfully applied to select mlc methods, it is significant to experiment mtl to select mtr methods.






§ MATERIAL AND METHODS



Fig <ref> provides an overview of the adopted experimental methodology. First, we performed exhaustive experiments evaluating all the mtr methods in all available datasets. We also identified the best method for each dataset, selecting the one with the smallest rrmse. This information is used to define the meta-label.
At the same time, a set of measures, named meta-features, are also extracted to describe each dataset. 
We then unify the meta-feature values with the meta-labels to compose our meta-dataset.
Then, we can employ ML algorithms to predict the best mtr method for a new unseen dataset. 
The next subsections describe each one of these processes with details.










 §.§ Datasets


In the experiments, the meta-dataset was composed of 648 benchmarking synthetic datasets[The generated datasets are available for download in: http://www.uel.br/grupo-pesquisa/remid/?page_id=145]
, generated by following the procedure described in <cit.>. 
We used synthetic datasets to overcome the lack of real datasets that meet specifics scenarios of inter-targets dependencies, complexity levels from the input to output relations, and cover a different number of input features and targets. 
To create a wide possibility of datasets, the parameters of the dataset generator assumed the values presented in Table <ref>. The numeric targets were built upon math expressions of identity, quadratic, and cubic functions, or their combination. 



















 §.§ Meta-features


Each base-level dataset is represented by a vector of characteristics, the meta-features. In <cit.> the authors list some requirements that a meta-features must follow: they need to have good discriminative power, their extraction should not be computational complex and the number of meta-features should not be large to avoid overfitting.

In our meta-level experiments, a set of 58 meta-features were explored. They included measures from different categories: statistical information about the dataset (STAT), correlation between attributes and targets (COR), performance metrics related to a linear regression (LIN), distribution of the dataset (DIM) and smoothness of the data (SMO) <cit.>. 

It is important to mention that some of these meta-features were designed for problems with one single 
output. Since we are dealing with multi-target problems, the real value of the meta-features were aggregated, given that a meta-feature is extracted for each target. To overcome this problem, the meta-feature was extracted for each target, then the average, standard deviation, maximum and minimum was added to the set of meta-features <cit.>. Most of the meta-features values were extracted using the R package  <cit.>.
A complete list of the meta-features used in the experiments is presented in Table <ref>.











 §.§ Meta-labels


st approach and three mtr methods were explored in experiment: sst, erc <cit.> and motc <cit.>.
Even being the most simple, the st approach was included in the experimental setup because it can perform better than mtr methods in problems with limited inter-target dependency. On the other hand, the other three mtr methods were selected because they offer a proper trade-off between performance and time complexity, as concluded from <cit.>. 


These four different methods mentioned above were executed 
for every single base-level dataset. Their induced models were assessed in terms of rrmse evaluation measure defined in Equation <ref>, where N represents the number of instances, and y, ŷ and y represent, respectively, the true, predicted and mean values of the target.

svm was used as base regressor, performing a k-Fold cv resampling strategy, with k = 10. svm was chosen as base regressor due to its usage in the most of MTR Problem transformation literature <cit.>. The method with the smallest rrmse <cit.> was chosen as the best multi-target method for every dataset. The experiments were performed using the [https://github.com/smastelini/mtr-toolkit],
implemented in R. Thus, our meta-dataset was a multi-class meta-label with four different levels indicating the best mtr method or ST regression. The class distribution (%) in the meta-dataset is also presented in Table <ref>. 


    aRRMSE = 1/d∑^d_t=1√(∑_i=1^N (y_t^i - ŷ_t^i)^2/∑_i=1^N (y_t^i - y)^2)












 §.§ Meta-learners


Four ml algorithms, with different learning biases, were used as meta-learners: nb <cit.>, rf <cit.>, svm <cit.> and xgb <cit.>. These algorithms were selected due to their widespread use and capacity of high-performance models induction. The k-Fold cv resampling methodology was also adopted in the meta-level of the experiments to assess the predictive performance of the meta-learners, with k = 10 folds. 
All the ml algorithms were implemented in R, using the  package and their correspondent default hyperparameters.






 §.§ Evaluation measures and baselines


Seven evaluation metrics were used to assess the predictive performance of the induced models:  Accuracy,  Balanced per class accuracy, Precision, Recall, F-score (f1), Sensitivity and Specificity.

Besides, we used two different baselines from the mtl literature for comparisons: a model that always recommends the majority class for the whole dataset () and a model that provides random recommendations (). These baselines are widely used to endorse the need for a recommendation system <cit.>. 
Also, we used an upper-bound as the ground-truth ().








§ RESULTS AND DISCUSSION



The results were organized starting by exposing the results regarding the predictive performance of meta-models from different ML algorithms. Afterward, based on the RF meta-model performance, the meta-features were compared and discussed. Finally, some contributions and open issues related to mtl and mtr were presented.



 §.§ Predictive Performance


The predictive performance obtained by the four meta-learners and the baselines are presented as a radar chart in Fig. <ref>. 
In this figure, each line represents a meta-model and each vertex its related to a different performance measure. The larger the area in the radar chart, the better the meta-model.





Looking at the radar chart, it is possible to observe that all meta-models had a superior performance than  baseline for all metrics. The same occurs for , except for accuracy with nb, since  has 55.8% of accuracy, whereas the nb meta-model achieved 51.08%.
Still for this metric, rf obtained the best results with 70.83% of accuracy. Following the rf, the svm achieved 68.9% and xgb was the third, with 66.51% of accuracy. The only metric that rf meta-model did not obtain the higher value was Sensitivity, when nb was the best with 0.49. Regarding the other evaluation metrics, rf achieved the best results, with 0.86 of Specificity, 0.55 of Precision, 0.46 of Recall, 0.47 of F1 and 66.59% of Balanced per class accuracy.




Although three of four meta-models overcame the baselines for all metrics, the predictive performance did not achieve high values, which might be related to the meta-dataset imbalance problem. 
However, the superiority of the mtl recommending system regarding the baselines was confirmed by statistical tests. 
We used the Friedman test, with a significance level of α = 0.05. The null hypothesis is that the recommendation by the meta-models and by the baselines are similar.
Anytime the null hypothesis is rejected, the Nemenyi post hoc test can be applied, stating that the performance of the two approaches are significantly different if their corresponding average ranks differ by at least a cd value. When multiple algorithms are compared in this way, a graphic representation can be used to represent the results with the cd diagram, as proposed by Demšar <cit.>. 

The meta-models (rf, svm, xgb, nb) were compared with  (expected method), the  (which always predicts the sst) and  (the random selection of a method for each dataset), using the rrmse of the prediction as performance metric.
This analysis is shown in Fig. <ref>, using the results from the Nemenyi test.






As exposed in Fig. <ref>, no solution was similar to the , which was expected due to the predictive performance. However, the rf, svm, xgb are connected, which means they were similar and superior the baselines  and . This fact supports the benefit of using mtl recommending system in comparison to select a specific algorithm for every dataset or select it randomly.




 §.§ Relative importance of the meta-features 


rf meta-model was used to assess the importance of each meta-feature by using the RF Feature Importance metric. This metric is calculated by permuting the values of a feature in the oob samples and recalculating the oob error in the whole ensemble. In other words, if substituting the values of a meta-feature by random values results in error increase, this meta-feature is considered important. Otherwise, if the error decreases, the resulting importance is negative. Thus, the meta-feature is considered not important and should be removed from modeling. This procedure could be performed for each meta-feature toward explaining its impact <cit.>. Fig. <ref> shows the meta-feature importance for the meta-dataset.  









cor and lin meta-features achieved the higher values of importance, especially the Minimum value of distance of erroneous instances to a linear classifier (12.54), Minimum value of non-linearity of a linear classifier (12.51) and the Standard Deviation of the Maximum feature correlation to the output (11.37). Once the mtr method tries to explore the correlation between the features and the targets in different ways, their selection makes sense.
The number of targets, attributes and samples had low importance. This might have occurred because these meta-features did not influence in the predictive performance, showing that the mtr methods used in the experiments can deal with different numbers of targets, attributes and samples in the same way.



 §.§ Insights and open issues


 It is important to highlight the meta-label attribution was straightforward related to the highest predictive performance (low rrmse) based on the ranking of methods. Differences between the predictive performance of the mtr methods, independent of their magnitude, were not considered while building the meta-dataset. 
 
 Alternatively, the meta-label assessment could be performed by indicating two or more methods suitable to solve a given problem in the case of no statistical difference between their performances. However, this scenario poses an additional challenge to deal with a multi-label problem in the meta-level of the recommending system.
 
 Another important issue was the fact of meta-label assessment was made regarding only low predictive error of mtr methods. In some cases, e.g., Online Multi-target Regression <cit.>, the most proper method concerns to address a trade-off among predictive performance, memory, and time cost when predicting the output. This scenario demands additional information, as well as complexity, toward identifying the best mtr method to be learned by the recommending system.




















§ CONCLUSIONS AND FUTURE WORK



In this study, a framework for recommending mtr methods using meta-learning was presented. A meta-dataset, composed with 648 datasets used for mtr methods benchmark, was created for the induction of meta-models toward predicting the best one for a given dataset. Experiments performed with the meta-dataset and four meta-learners led to 70.83% of accuracy with RF, the best recommender. Besides, it overcame the baselines, and statistical tests showed that the recommendation system was better than select one for every task or selecting a method randomly. The analysis of meta-feature importance revealed that correlation between targets and error of a linear classifier were the most useful features to predict the performance of a mtr method for a given unseen dataset.

As future work, besides implementing more meta-features, we intend to use more mtr benchmarking datasets, in order to improve the generalization capability of the meta-models. Also, we expect to apply mlc to predict the mtr method and its base regressor. Further information related to the memory and time cost will be used to match the requirement of different scenarios, e.g., Online mtr.






§ ACKNOWLEDGEMENTS


The authors would like to thank the financial support of Coordination for the Improvement of Higher Education Personnel (CAPES) - Finance Code 001 -, the National Council for Scientific and Technological Development (CNPq) of Brazil - Grant of Project 420562/2018-4 - and São Paulo Research Foundation (FAPESP) - grant #2018/07319-6.


./bibliography/IEEEtran


