Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Performance Measures <s> This paper reviews the supervised learning versions of the no-free-lunch theorems in a simplified form. It also discusses the significance of those theorems, and their relation to other aspects of supervised learning. <s> BIB001 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Performance Measures <s> In many disciplines, such as social and behavioral sciences, we often have to do ordinal classification by assigning objects to ordinal classes. The fundamental objective of ordinal classification is to create an ordering in the universe of discourse. As such, a decision tree for ordinal classification should aim at producing an ordering which is most consistent with the implicit ordering in the input data. Ordinal classification problems are often dealt with by treating ordinal classes as nominal classes, or by representing the classes as values on a quantitative scale. Such approaches may not lead to the most desirable results since the methods do not fit the type of data, viz. ordinal data, concerned. In this paper, we propose a new measure for assessing the quality of output from an ordinal classification approach. We also propose an induction method to generate an ordinal decision tree for ordinal classification based on this quality perspective. We demonstrate the advantage of our method using results from a set of experiments. <s> BIB002 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Performance Measures <s> Classical learning algorithms from the fields of artificial neural networks and machine learning, typically, do not take any costs into account or allow only costs depending on the classes of the examples that are used for learning. As an extension of class dependent costs, we consider costs that are example, i.e. feature and class dependent. We present a natural cost-sensitive extension of the support vector machine (SVM) and discuss its relation to the Bayes rule. We also derive an approach for including example dependent costs into an arbitrary cost-insensitive learning algorithm by sampling according to modified probability distributions. <s> BIB003 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Performance Measures <s> The area under the ROC (receiver operating characteristics) curve, or simply AUC, has been traditionally used in medical diagnosis since the 1970s. It has recently been proposed as an alternative single-number measure for evaluating the predictive ability of learning algorithms. However, no formal arguments were given as to why AUC should be preferred over accuracy. We establish formal criteria for comparing two different measures for learning algorithms and we show theoretically and empirically that AUC is a better measure (defined precisely) than accuracy. We then reevaluate well-established claims in machine learning based on accuracy using AUC and obtain interesting and surprising new results. For example, it has been well-established and accepted that Naive Bayes and decision trees are very similar in predictive accuracy. We show, however, that Naive Bayes is significantly better than decision trees in AUC. The conclusions drawn in this paper may make a significant impact on machine learning and data mining applications. <s> BIB004 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Performance Measures <s> We analyse 18 evaluation methods for learning algorithms and classifiers, and show how to categorise these methods with the help of an evaluation method taxonomy based on several criteria. We also define a formal framework that make it possible to describe all methods using the same terminology, and apply it in a review of the state-of-the-art in learning algorithm and classifier evaluation. The framework enables comparison and deeper understanding of evaluation methods from different fields of research. Moreover, we argue that the framework and taxonomy support the process of finding candidate evaluation methods for a particular problem. <s> BIB005 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Performance Measures <s> The proportion of successful hits, usually referred to as "accuracy", is by far the most dominant meter for measuring classifiers' accuracy. This is despite of the fact that accuracy does not compensate for hits that can be attributed to mere chance. Is it a meaningful flaw in the context of machine learning? Are we using the wrong meter for decades? The results of this study do suggest that the answers to these questions are positive. ::: ::: Cohen's kappa, a meter that does compensate for random hits, was compared with accuracy, using a benchmark of fifteen datasets and five well-known classifiers. It turned out that the average probability of a hit being the result of mere chance exceeded one third (!). It was also found that the proportion of random hits varied with different classifiers that were applied even to a single dataset. Consequently, the rankings of classifiers' accuracy, with and without compensation for random hits, differed from each other in eight out of the fifteen datasets. Therefore, accuracy may well fail in its main task, namely to properly measure the accuracy-wise merits of the classifiers themselves. <s> BIB006 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Performance Measures <s> Nowadays the area under the receiver operating characteristics (ROC) curve, which corresponds to the Wilcoxon-Mann-Whitney test statistic, is increasingly used as a performance measure for binary classification systems. In this article we present a natural generalization of this concept for more than two ordered categories, a setting known as ordinal regression. Our extension of the Wilcoxon-Mann-Whitney statistic now corresponds to the volume under an r-dimensional surface (VUS) for r ordered categories and differs from extensions recently proposed for multi-class classification. VUS rather evaluates the ranking returned by an ordinal regression model instead of measuring the error rate, a way of thinking which has especially advantages with skew class or cost distributions. We give theoretical and experimental evidence of the advantages and different behavior of VUS compared to error rate, mean absolute error and other ranking-based performance measures for ordinal regression. The results demonstrate that the models produced by ordinal regression algorithms minimizing the error rate or a preference learning based loss, not necessarily impose a good ranking on the data. <s> BIB007 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Performance Measures <s> Ordinal regression (OR -- also known as ordinal classification) has received increasing attention in recent times, due to its importance in IR applications such as learning to rank and product review rating. However, research has not paid attention to the fact that typical applications of OR often involve datasets that are highly imbalanced. An imbalanced dataset has the consequence that, when testing a system with an evaluation measure conceived for balanced datasets, a trivial system assigning all items to a single class (typically, the majority class) may even outperform genuinely engineered systems. Moreover, if this evaluation measure is used for parameter optimization, a parameter choice may result that makes the system behave very much like a trivial system. In order to avoid this, evaluation measures that can handle imbalance must be used. We propose a simple way to turn standard measures for OR into ones robust to imbalance. We also show that, once used on balanced datasets, the two versions of each measure coincide, and therefore argue that our measures should become the standard choice for OR. <s> BIB008 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Performance Measures <s> Breast Cancer Conservative Treatment (BCCT) is considered nowadays to be the most widespread form of locor-regional breast cancer treatment. However, aesthetic results are heterogeneous and difficult to evaluate in a standardized way. The limited reproducibility of subjective aesthetic evaluation in BCCT motivated the research towards objective methods. A recent computer system (BCCT.core) was developed to objectively and automatically evaluate the aesthetic result of BCCT. The system is centered on a support vector machine (SVM) classifier with a radial basis function (RBF) used to predict the overall cosmetic result from features computed on a digital photograph of the patient. However, this classifier is not ideal for the interpretation of the factors being used in the prediction. Therefore, an often suggested improvement is the interpretability of the model being used to assess the overall aesthetic result. In the current work we investigate the accuracy of different interpretable methods against the model currently deployed in the BCCT.core software. We compare the performance of decision trees and linear classifiers with the RBF SVM currently in BCCT.core. In the experimental study, these interpretable models shown a similar accuracy to the currently used RBF SVM, suggesting that the later can be replaced without sacrificing the performance of the BCCT.core. <s> BIB009 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Performance Measures <s> Ordinal classification is a form of multiclass classification for which there is an inherent order between the classes, but not a meaningful numeric difference between them. The performance of such classifiers is usually assessed by measures appropriate for nominal classes or for regression. Unfortunately, these do not account for the true dimension of the error. The goal of this work is to show that existing measures for evaluating ordinal classification models suffer from a number of important shortcomings. For this reason, we propose an alternative measure defined directly in the confusion matrix. An error coefficient appropriate for ordinal data should capture how much the result diverges from the ideal prediction and how "inconsistent" the classifier is in regard to the relative order of the classes. The proposed coefficient results from the observation that the performance yielded by the Misclassification Error Rate coefficient is the benefit of the path along the diagonal of the confusion matrix. We carry out an experimental study which confirms the usefulness of the novel metric. <s> BIB010 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Performance Measures <s> Benchmarking pattern recognition, machine learning and data mining methods commonly relies on real-world data sets. However, there are some disadvantages in using real-world data. On one hand collecting real-world data can become difficult or impossible for various reasons, on the other hand real-world variables are hard to control, even in the problem domain; in the feature domain, where most statistical learning methods operate, exercising control is even more difficult and hence rarely attempted. This is at odds with the scientific experimentation guidelines mandating the use of as directly controllable and as directly observable variables as possible. Because of this, synthetic data possesses certain advantages over real-world data sets. In this paper we propose a method that produces synthetic data with guaranteed global and class-specific statistical properties. This method is based on overlapping class densities placed on the corners of a regular k-simplex. This generator can be used for algorithm testing and fair performance evaluation of statistical learning methods. Because of the strong properties of this generator researchers can reproduce each others experiments by knowing the parameters used, instead of transmitting large data sets. <s> BIB011
After considering the advantages and disadvantages, goals achieved and open issues of the techniques presented in previous sections, the discussion of how to measure the performance of such techniques has not been debated much. Usually, a learning process consists in two main phases: A cross-validation phase and an estimation of the model performance (F represented in Equation (5)) on a real-world scenario (also known as the testing phase). In both situations, one has to analyse the performance of a model given certain parametrization and its behaviour in a non controllable environment, respectively. Herein, the question that one obviously poses is: How much did the model err? Or, how much the prediction differs from the real outcome? Given certain assumptions of models design, it is clear, as we will shortly show, that the metric chosen for this task is crucial. It is interesting to see that in contrast to the plethora of existing methods concerning multicriteria learning, only recently we witnessed some concerns to this issue BIB010 BIB011 BIB002 , disregarding advances performance made on the broader field of machine learning BIB005 . Knowing that "no free lunch" theorems state that there is not an algorithm that can be superior on all problems in regard to classification accuracy BIB001 , the assessment of an appropriate learning method given a specific problem is desirable BIB005 . For classification problems, MER (Misclassification Error Rate) is currently one of the most used measures. Its widely use make it a de facto standard when comparing different learning algorithms by just counting the misclassifications occurred. In other problems domains, it is usual to penalise the misclassifications by weighting them by the magnitude of the error to avoid uneven results. When such happens, MAE (Mean Absolute Error) and MSE (Mean Squared Error) measures are usually the most appropriate choices. Summing, the performance of a classifier can be assessed in a dataset D through respectively, where g(.) corresponds to the number assigned to a class, N = card(D), and C x x x and C x x x are the true and estimated classes. However, this assignment is arbitrary and the numbers chosen to represent the existing classes will evidently influence the performance measurement given by MAE or MSE. A clear improvement on these measures would be to define them directly from the confusion matrix CM (a table with the true class in rows and the predicted class in columns, with each entry n r,c representing the number of instances from the r−th class predicted as being from c−th class): where K is the number of classes. We will always assume that the ordering of the columns and rows of the CM is the same as the ordering of the classes. This procedure makes MAE and MSE independent of the numbers or labels chosen to represent the classes. To a certain degree, these two measures are better than MER because they take values which increase with the absolute differences between 'true' and 'predicted' class numbers and so the misclassifications are not taken as equally costly. In order to avoid the influence of the numbers chosen to represent the classes on the performance assessment, it has been argued that one should only look at the order relation between 'true' and 'predicted' class numbers. The use of Spearman's rank correlation coefficient, R s , and specially Kendall's tau-b, τ b , is a step in that direction   . For instance, in order to compute R s , we start by defining two rank vectors of length N which are associated with the variables g(C) and g( C). There will be many examples in the dataset with common values for those variables; for these cases average ranks are used. If p p p and q q q represent the two rank vectors, then R s = As we can see, Spearman's coefficient is still dependent on the values chosen for the ranks representing the classes and so it is not completely appropriate to measure the performance of ordinal data classifiers. More importantly, R s looses information about the absolute value of the classes. Kendall's coefficient τ b has been advocated as a better measure for ordinal variables because it is independent of the values used to represent classes  . Its robustness is achieved by working directly on the set of pairs corresponding to different observations. However, there are limitations: By working only with the relative order of elements, it loses information about the absolute prediction for a given observation. Other attempts have considered the analysis of the learner behaviour on a ROC (Receiver Operating Characteristic) curve or its equivalent, AUC (Area Under Curve). Despite empirical evidences of AUC providing more desirable properties when compared to accuracy  only recently this topic was not only re-proposed but also new evidences of its advantages were shown BIB004 . In this work, AUC is demonstrated as an objective measure for selecting the best learning model, but, and most important, refers to the need of developing better measures for learner design and performance assessment BIB004 . In this line of research, in  it is compared different ROC measurements. However, and despite the assumptions made, ROC derived measures that assess a ranking for different performance do not quantify the performance achieved by a learner BIB007 . Such analysis, although with different purposes, has been conducted by BIB006 using Cohen's kappa statistic. On the other way, the discussion was revamped by Baccianella et al BIB008 through an analysis of different derivations of MSE and MAE metrics for ordinal problems. This work is key since it debates two main issues incurred on the performance measurement of learners for this type of classification problems: Imbalanced classes and classes with equal penalisation costs. In order to avoid the former problematic, a derivation from MAE is presented by averaging the deviations per class. In the same line, the coefficient r int was recently introduced, taking into account the expected high number of ties in the values to be compared  . In fact, the variables C and C are two special ordinal variables. Because there are usually very few classes compared to the number of observations, these variables will take many tied values (most of them, in fact In BIB010 a different approach was taken. Even though the adaptation of the MAE and MER to a confusion matrix form surpasses standard forms, there are still issues regarding these metrics. Some of the vicissitudes as mentioned in BIB010 encompass: Equally misclassification costs, metrics unable to evaluate example dependent costs BIB003 or metrics more proper to ranking problems. Having Cardoso and Sousa identified some key advantages of using the CM form, and given the merit of both MAE and MER fundamental principles, they proposed a new one that takes advantage of all as a single optimisation problem. This new metric chooses pairs of observations from the CM that do not contradict the relative order given by the classifier and the true relative class order which minimise the cost of a global optimisation procedure. The choice is done in a way that minimises the deviation of the pairs to the main diagonal while maximising the entries values in the path that cross the CM. This was formalised as  where the minimisation is performed over all possible paths from (1,1) to (K,K). γ and β were defined based upon empirical experiments. Other techniques can also go through data generators methodologies where one can control the statistical properties herein aiding in the learners benchmark BIB011 . More importantly, techniques capable to manipulate Bayes error rate can foster new lines of research where fair learners comparison BIB006 and the development of new ones can take place. In BIB010 it is raised a question that interesting enough has not been debated since BIB002 in the ordinal context. As one knows, the usage of such metrics in the design of classifiers can be done on two distinct situations. A first use is 'externally' to the classifier, using the metric to select the best parametrization of the classifier (usually when performing a cross-validation procedure). A second possibility is to embed the new metric in the classifier design, adapting the internal objective function of the classifier, replacing loss functions based on standard measures by a loss function based on the proposed measure. For instance, the standard loss function of a neural network based on the square of the error or on cross-entropy could be replaced by an error evaluated by an appropriate metric BIB004 . Lee BIB002 accomplished such for the design of ordinal trees, but since then few works have addressed this subject in the ordinal context. It is interesting that only recently we saw a significant growth of the awareness of this topic importance. Even though some works have already tackled this issue, all lack on concretely assessing the performance of a given ordinal learning model. Until now, new metrics have been designed and compared against MAE followed by some reasoning. The problem resides how close a metric is in expressing accuracy. Different prosaically strategies can pass through the definition of prior costs for each class BIB009 or, when using a given set of different metrics, a meta-metric to assess the performance of metrics should be in place as suggested by Cardoso BIB010 .