Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Definition 2 (Ranking [16, 25]). A ranking problem consists on finding the best mapping f <s> Abstract Rough set theory is a new approach to decision making in the presence of uncertainty and vagueness. Basic concepts of rough set theory will be outlined and its possible application will be briefly discussed. Further research problems will conclude the paper. <s> BIB001 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Definition 2 (Ranking [16, 25]). A ranking problem consists on finding the best mapping f <s> Preface. Acknowledgements. Notation and Symbols. Part I: Terminology and Theory. 1. Introduction. 2. Concepts. 3. Theoretical Background. Part II: Methods. 1. Introduction. 2. No-Preference Methods. 3. A Posteriori Methods. 4. A Priori Methods. 5. Interactive Methods. Part III: Related Issues. 1. Comparing Methods. 2. Software. 3. Graphical Illustration. 4. Future Directions. 5. Epilogue. References. Index. <s> BIB002 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Definition 2 (Ranking [16, 25]). A ranking problem consists on finding the best mapping f <s> This textbook provides a thorough introduction to the field of learning from experimental data and soft computing. Support vector machines (SVM) and neural networks (NN) are the mathematical structures, or models, that underlie learning, while fuzzy logic systems (FLS) enable us to embed structured human knowledge into workable algorithms. The book assumes that it is not only useful, but necessary, to treat SVM, NN, and FLS as parts of a connected whole. Throughout, the theory and algorithms are illustrated by practical examples, as well as by problem sets and simulated experiments. This approach enables the reader to develop SVM, NN, and FLS in addition to understanding them. The book also presents three case studies: on NN-based control, financial time series analysis, and computer graphics. A solutions manual and all of the MATLAB programs needed for the simulated experiments are available. <s> BIB003 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Definition 2 (Ranking [16, 25]). A ranking problem consists on finding the best mapping f <s> The original rough set approach proved to be very useful in dealing with inconsistency problems following from information granulation. It operates on a data table composed of a set U of objects (actions) described by a set Q of attributes. Its basic notions are: indiscernibility relation on U, lower and upper approximation of either a subset or a partition of U, dependence and reduction of attributes from Q, and decision rules derived from lower approximations and boundaries of subsets identified with decision classes. The original rough set idea is failing, however, when preference-orders of attribute domains (criteria) are to be taken into account. Precisely, it cannot handle inconsistencies following from violation of the dominance principle. This inconsistency is characteristic for preferential information used in multicriteria decision analysis (MCDA) problems, like sorting, choice or ranking. In order to deal with this kind of inconsistency a number of methodological changes to the original rough sets theory is necessary. The main change is the substitution of the indiscernibility relation by a dominance relation, which permits approximation of ordered sets in multicriteria sorting. To approximate preference relations in multicriteria choice and ranking problems, another change is necessary: substitution of the data table by a pairwise comparison table, where each row corresponds to a pair of objects described by binary relations on particular criteria. In all those MCDA problems, the new rough set approach ends with a set of decision rules playing the role of a comprehensive preference model. It is more general than the classical functional or relational model and it is more understandable for the users because of its natural syntax. In order to workout a recommendation in one of the MCDA problems, we propose exploitation procedures of the set of decision rules. Finally, some other recently obtained results are given: rough approximations by means of similarity relations, rough set handling of missing data, comparison of the rough set model with Sugeno and Choquet integrals, and results on equivalence of a decision rule preference model and a conjoint measurement model which is neither additive nor transitive. <s> BIB004 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Definition 2 (Ranking [16, 25]). A ranking problem consists on finding the best mapping f <s> Fuzzy Sets.- The Operation of Fuzzy Set.- Fuzzy Relation and Composition.- Fuzzy Graph and Relation.- Fuzzy Number.- Fuzzy Function.- Probabilisy and Uncertainty.- Fuzzy Logic.- Fuzzy Inference.- Fuzzy Control and Fuzzy Expert Systems.- Fusion of Fuzzy System and Neural Networks.- Fusion of Fuzzy Systems and Genetic Algorithms. <s> BIB005 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Definition 2 (Ranking [16, 25]). A ranking problem consists on finding the best mapping f <s> We propose a new fuzzy rough set approach which, differently from most known fuzzy set extensions of rough set theory, does not use any fuzzy logical connectives (t-norm, t-conorm, fuzzy implication). As there is no rationale for a particular choice of these connectives, avoiding this choice permits to reduce the part of arbitrary in the fuzzy rough approximation. Another advantage of the new approach is that it is based on the ordinal properties of fuzzy membership degrees only. The concepts of fuzzy lower and upper approximations are thus proposed, creating a base for induction of fuzzy decision rules having syntax and semantics of gradual rules. The proposed approach to rule induction is also interesting from the viewpoint of philosophy supporting data mining and knowledge discovery, because it is concordant with the method of concomitant variations by John Stuart Mill. The decision rules are induced from lower and upper approximations defined for positive and negative relationships between credibility degrees of multiple premises, on one hand, and conclusion, on the other hand. <s> BIB006 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Definition 2 (Ranking [16, 25]). A ranking problem consists on finding the best mapping f <s> Classification of ordinal data is one of the most important tasks of relation learning. This paper introduces a new machine learning paradigm specifically intended for classification problems where the classes have a natural order. The technique reduces the problem of classifying ordered classes to the standard two-class problem. The introduced method is then mapped into support vector machines and neural networks. Generalization bounds of the proposed ordinal classifier are also provided. An experimental study with artificial and real data sets, including an application to gene expression analysis, verifies the usefulness of the proposed approach. <s> BIB007 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Definition 2 (Ranking [16, 25]). A ranking problem consists on finding the best mapping f <s> In many application areas of machine learning, prior knowledge concerning the monotonicity of relations between the response variable and predictor variables is readily available. Monotonicity may also be an important model requirement with a view toward explaining and justifying, decisions, Such as acceptance/rejection decisions. We propose a modified nearest neighbour algorithm for the construction of monotone classifiers from data. We start by making the training, data monotone with as few label changes as possible. The relabeled data set can he viewed as a monotone classifier that has the lowest possible error-rate on the training data. The relabeled data is subsequently used as the training sample by a modified nearest neighbour algorithm. This modified nearest neighbour rule produces predictions that are guaranteed to satisfy the monotonicity constraints. Hence, it is Much more likely to be accepted by the intended users. Our experiments show that monotone kNN often outperforms standard kNN in problems where the monotonicity constraints are applicable. <s> BIB008 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> Definition 2 (Ranking [16, 25]). A ranking problem consists on finding the best mapping f <s> Along the years, rough set theory has earned a well-deserved reputation as a sound methodology for dealing with imperfect knowledge in a simple though mathematically sound way. This edited volume aims at continue stressing the benefits of applying rough sets in many real-life situations while still keeping an eye on topological aspects of the theory as well as strengthening its linkage with other soft computing paradigms. The volume comprises 11 chapters and is organized into three parts. Part 1 deals with theoretical contributions while Parts 2 and 3 focus on several real world data mining applications. Chapters authored by pioneers were selected on the basis of fundamental ideas/concepts rather than the thoroughness of techniques deployed. Academics, scientists as well as engineers working in the rough set, computational intelligence, soft computing and data mining research area will find the comprehensive coverage of this book invaluable. <s> BIB009
There are subtle differences between the two problems. Whereas in classification the order between classes is already defined and all patterns have to be assigned into at most one class, in ranking such does not hold. Think for instance on the Google TM or Yahoo TM search engines. When entering a search query, the result can vary from user to user for the same query. The search engine will look on its database and rank the results according to, for instance, user search history. Ranking approaches however go beyond the subject of this chapter. Depending on the problem, criteria can also represent a magnitude of importance or unimportance, a ratio, among others. This can generate datasets where order may not be explicitly represented. Different works tackled the ordinal problem assuming that data were monotone, i.e., where both criteria and classes were assumed to be ordered  BIB008  . Nevertheless, recent works argue that monotonicity constraint cannot be verified despite being however perfect representatives of an ordinal problem BIB007  . The following synthetic datasets depict some of those claims. To each point in Fig. 2a was assigned a class y from the set {1, 2, 3, 4, 5}, according to where ε ∼ N(0; 0.125 2 ) simulates the possible existence of error in the assignment of the true class to x x x. Data in Fig. 2b is uniformly distributed in the unit-circle, with the class y being assigned according to the radius of the point: y = x 2 1 + x 2 2 . These synthetic datasets are examples where order cannot be captured directly in the input space, but in an implicit feature space. Hence, the following question can be posed: How to capture order? Many models have been proposed towards this goal. But before answering that question, first a brief description of the most commonly used models is required. The following concepts will allow a better understanding of the most recent techniques discussed along this chapter. Starting by the OR domain, a classic multicriteria decision analysis (MCDA) approach is done by the representation of a specific aggregation model. Aggregation models are performed by aggregating different value or utility functions in order to be expressed by a single criterion. One aggregation model that we can think of a, for instance, the mean: The use of utility vs. value depends upon the problem. Whereas, utility functions are used in stochastic problems, value function are used in deterministic ones BIB002 . In brief, an aggregation model is a function U : R d → R, that maps criteria of the DM onto outcomes BIB002 . Utility functions are widely used, where the one presented in Equation (2) is an example of several other aggregation models. It has the advantage of considering both qualitative and quantitative criteria. The simplest additive case of an utility function is defined as follows: where U ∈ [0, 1]. For the interested reader Siskos  presents a good description of these methods. Fuzzy set theory is another topic with increasing interest on the scientific community. Its usage is not restricted only to the MCDA problem being however strongly defended thanks to its capability to handle uncertainty BIB006  . In general, fuzzy set theory presents a fundamental principle which describes a special type of sets which have degrees of membership through simple logical operators. Such can be described by any mapping function μ( Fig. 3a) consists of a valid representation for a given membership function. Moreover, it can represent knowledge in a if ... then way in a similar way to decision trees (DTs) BIB003 which will be described shortly. In much of the works currently present in the literature, fuzzy set theory usually appears along with rough sets. The latter field is however slightly different from the former. Rough Set theory not just handle uncertainty, but also incomplete information which can be present on data  . Even though new approaches on utility additive functions (UTA-UTilitès Additives  ) already tackle this problem, it has also been stated that rough and fuzzy set theory are complementary because of dealing with different kinds of uncertainty BIB006 . It was initially proposed by Pawlak  with the objective to provide a mathematical formulation of the concept of approximated (rough) equality of sets in a given space. In the rough set theory it is assumed that to every object there is an associated amount of information that describes it. This refers to the view that knowledge has a granular structure BIB009 BIB006 BIB004 BIB001 . Therefore, an important characteristic of rough sets theory is the identification of consistent data and assigning them into lower and upper approximations of setssee Fig. 3b ). More on the AI domain, in general, one tries to obtain valid generalisation rules, classifier, from data. Once a classifier has been designed, one has to assess its performance by estimating the error of the classifier for unseen examples. Classification error is expressed as a misclassification error defined by a "true misclassification rate" (here denoted as R * (d)). d(x x x) is the learner model with input data x x x. Breiman  defines this function as: Definition 3 (Accuracy Estimation  ). Take (x x x, y), x x x ∈ X, y ∈ Y, to be a new sample from the probability distribution P(A, j); i.e., But how can R * (d) be estimated? There are many approaches. One that this work will use is the cross-validation approach. Dataset D is randomly divided in subsets, with the same size as possible, e.g., where R ts is defined as where N v N/V and F any function which penalises each error BIB009 . One can now analyse the different learning methods for ordinal data. k-Nearest Neighbour (k-NN) is a simple method that interestingly has not been explored enough in the MCDA setting until very recently. It consists of a nonparametric method with the main objective to estimate the density function from sample patterns  . It extends the local region around a data point x x x until the k th nearest neighbour is found. The most represented class in the k-closest cases defines the predicted class. Fig. 4a-b) illustrates such procedure. DTs are another method that captured some interest for tackling MCDA problems, specially on the OR domain. DTs classify a pattern through a sequence of questions where the next question depends on the answer to the previous one. These trees are constructed as logical expressions as is illustrated in Fig. 4c-d) . This ability generates a powerful data analysis tool capable to obtain interpretable results  . Nodes are consecutively split where a stop-splitting rule is required that controls the growth of the tree. Neuron Networks are another kind of learning models. Multi-Layer Perceptron (MLP) is the most commonly used. A MLP is a layered structure consisting of nodes or units (called neurons) and one-way connections or links between the nodes of successive layers, such as the structure of Fig. 5a ). The first layer is called the input layer, the last layer is the output layer, while the ones in the middle are called the hidden layers. Input layer of neurons is only a vector where all data are introduced triggering the learning process. Data propagates through the network in a forward direction, on a layer-by-layer basis. Layers are constituted by several neurons which commonly have non-linear and differentiable activation functions. Support Vector Machines (SVM) are another popular learning mechanism. In its simple form, SVMs uses a linear separating hyperplane to create a binary classifier with a maximal margin. In cases where data cannot be linearly separable, data are transformed to a higher dimension than the original feature space-see Fig. 5b ). Such is done by choosing a given kernel function, representing the inner product in some implicit higher dimension space. Formally, a kernel function is defined . This transformation (φ ) can be achieved by several nonlinear mappings: e.g., polynomial, sigmoidal and radial basis functions. However, in a multiclass problem the usage of a binary SVM classifier can be limited. In order to improve this some heuristics and new formulations were proposed as an extension to the binary classification problem. Some of them encompass the OVO (OneVersus-One), OVA (One-Versus-All), DDAG (Decision Directed Acyclic Graph), single optimisation formulation, among others. Basically, OVO consists on the design of K(K-1)/2 binary classifiers where one class is discriminated against another. Similarly, and as the name suggests, OVA consists on the design of K binary classifiers where one class is compared against the others. Likewise the former heuristic, DAG, follow a similar procedure. The major difference is that prediction is made in a graph path manner where each node corresponds to a given binary classifier. In a completely different scenario, there are also techniques that try to define a single optimisation problem to solve the multiclass problem on SVMs. This Section provided some key concepts regarding techniques for learning from data. Knowing that still much more has to be covered, the interested reader is advised to OR and AI textbooks     BIB005  for more information. Next Sections will describe different methods using some of the aforementioned methodologies for learning multicriteria models on ordinal data problems.