Multicriteria Models for Learning Ordinal Data: A Literature Review <s> MCDA Methods <s> Abstract This paper serves as an introduction to the Analytic Hierarchy Process — A multicriteria decision making approach in which factors are arranged in a hierarchic structure. The principles and the philosophy of the theory are summarized giving general background information of the type of measurement utilized, its properties and applications. <s> BIB001 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> MCDA Methods <s> In the first part of this paper, we describe the main features of real-world problems for which the outranking approach is appropriate and we present the concept of outranking relations. The second part is devoted to basic ideas and concepts used for building outranking relations. The definition of such outranking relations is given for the main ELECTRE methods in Part 3. The final part of the paper is devoted to some practical considerations. <s> BIB002 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> MCDA Methods <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> BIB003 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> MCDA Methods <s> Prologue. 1. Introduction to the Classification Problem. 2. Review of Classification Techniques. 3. Multicriteria Decision and Classification Techniques. 4. Preference Disaggregation Classification Methods. 5. Experimental Comparison of Classification Techniques. 6. Classification Problems in Finance. 7. Conclusions and Future Perspective. References. Subject Index. <s> BIB004 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> MCDA Methods <s> Many real-world AI problems (e.g. in configuration) are weakly constrained, thus requiring a mechanism for characterizing and finding the preferred solutions. Preference-based search (PBS) exploits preferences between decisions to focus search to preferred solutions, but does not efficiently treat preferences on defined criteria such as the total price or quality of a configuration. We generalize PBS to compute balanced, extreme, and Pareto-optimal solutions for general CSP's, thus handling preferences on and between multiple criteria. A master-PBS selects criteria based on trade-offs and preferences and passes them as optimization objective to a sub-PBS that performs a constraint-based Branch-and-Bound search. We project the preferences of the selected criterion to the search decisions to provide a search heuristics and to reduce search effort, thus giving the criterion a high impact on the search. The resulting method will particularly be effective for CSP's with large domains that arise if configuration catalogs are large. <s> BIB005 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> MCDA Methods <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> MCDA Methods <s> In order to discover interesting patterns and dependencies in data, an approach based on rough set theory can be used. In particular, Dominance-based Rough Set Approach (DRSA) has been introduced to deal with the problem of multicriteria classification. However, in real-life problems, in the presence of noise, the notions of rough approximations were found to be excessively restrictive, which led to the proposal of the Variable Consistency variant of DRSA. In this paper, we introduce a new approach to variable consistency that is based on maximum likelihood estimation. For two-class (binary) problems, it leads to the isotonic regression problem. The approach is easily generalized for the multi-class case. Finally, we show the equivalence of the variable consistency rough sets to the specific risk-minimizing decision rule in statistical decision theory. <s> BIB007 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> MCDA Methods <s> Evolutionary Multi-Agent System approach for optimization (for multi-objective optimization in particular) is a promising computational model. Its computational as well as implemental simplicity cause that approaches based on EMAS model can be widely used for solving optimization tasks. It turns out that introducing some additional mechanisms into basic EMAS-such as presented in the course of this paper elitist extensions cause that results obtained with the use of proposed elEMAS (elitist Evolutionary Multi-Agent System) approach are as high-quality results as results obtained by such famous and commonly used algorithms as NSGA-II or SPEA2. Apart from the computational simplicity especially important and interesting aspects of EMAS-based algorithms it is characteristic for them a kind of soft selection which can be additionally easily adjusted depending on a particular situation-in particular it is possible to introduce auto-adapting selection into such systems. Such a kind of selection seems to be especially important and valuable in solving optimization tasks in uncertain or ldquonoisedrdquo environments. In the course of this paper the model and experimental results obtained by elEMAS system in solving noisy multi-objective optimization problems are presented and the general conclusion is as follows: EMAS-based optimization system seems to be more effective alternative than classical (i.e. non agent-based) evolutionary algorithms for multi-objective optimization, in particular, in uncertain environment, it seems to be better alternative than NSGA-II algorithm. <s> BIB008 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> MCDA Methods <s> Introducing elitism into evolutionary multi-agent system for multi-objective optimization proofed to be smooth both conceptually and in realization. Simultaneously it allowed for obtaining results with comparable high quality to such referenced algorithms as Non-dominated Sorting Genetic Algorithm (NSGA-II) or Strength Pareto Evolutionary Algorithm (SPEA2). What is more, applying mentioned agent-based computational paradigm for solving multi-criteria optimization tasks in ldquonoisyrdquo environments mainly because of-characteristic for EMAS-based approach-a kind of soft selection allowed for obtaining better solutions than mentioned referenced algorithms. From the above observations the following conclusion can be drown: evolutionary multi-agent system (EMAS) (and being the subject of this paper elitist evolutionary multi-agent system (elEMAS) in particular) seems to be promising computational model in the context of multi-criteria optimization tasks. In previous works however the possibility of applying elEMAS for solving constrained multi-objective optimization task has not been investigated. It is obvious however that in almost all real-life problems constraints are a crucial part of multi-objective optimization problem (MOOP) definition and it is nothing strange that among (evolutionary) algorithms for multi-objective optimization a special attention is paid to techniques and algorithms for constrained multi-objective optimization and a variety-more or less effective-algorithms have been proposed. Thus, the question appears if effective constrained multi-objective optimization with the use of elitist evolutionary multi-agent system is possible. In the course of this paper preliminary answer for that question is given. <s> BIB009 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> MCDA Methods <s> Combinatorial problems such as scheduling, resource allocation, and configuration have many ::: attributes that can be subject of user preferences. Traditional optimization approaches compile ::: those preferences into a single utility function and use it as the optimization objective when ::: solving the problem, but neither explain why the resulting solution satisfies the original ::: preferences, nor indicate the trade-offs made during problem solving. We argue that the ::: whole problem solving process becomes more transparent and controllable for the user ::: if it is based on the original preferences. We show how the original preferences can be used ::: to control the problem solving process and how they can be used to explain the choice ::: and the optimality of the detected solution. Based on this explanation, the user can refine ::: the preference model, thus gaining full control over the problem solver. <s> BIB010 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> MCDA Methods <s> In order to discover interesting patterns and dependencies in data, an approach based on rough set theory can be used. In particular, dominance-based rough set approach (DRSA) has been introduced to deal with the problem of ordinal classification with monotonicity constraints (also referred to as multicriteria classification in decision analysis). However, in real-life problems, in the presence of noise, the notions of rough approximations were found to be excessively restrictive. In this paper, we introduce a probabilistic model for ordinal classification problems with monotonicity constraints. Then, we generalize the notion of lower approximations to the stochastic case. We estimate the probabilities with the maximum likelihood method which leads to the isotonic regression problem for a two-class (binary) case. The approach is easily generalized to a multi-class case. Finally, we show the equivalence of the variable consistency rough sets to the specific empirical risk-minimizing decision rule in the statistical decision theory. <s> BIB011 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> MCDA Methods <s> This article describes the original Analytic Hierarchy Process (AHP) as it is implemented in the software package Expert Choice. We demonstrate its application through a practical example. In particular, we discuss problem modelling, pairwise comparisons, judgement scales, derivation methods, consistency indices, synthesis of the weights and sensitivity analysis. Finally, the limitations of the original AHP along with the new proposed development are explained. <s> BIB012 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> MCDA Methods <s> Outranking methods constitute an important class of multicriteria classification models. Often, however, their implementation is cumbersome, due to the large number of parameters that the decision maker must specify. Past studies tried to address this issue using linear and nonlinear programming, to elicit the necessary preferential information from assignment examples. In this study, an evolutionary approach, based on the differential evolution algorithm, is proposed in the context of the ELECTRE TRI method. Computational results are given to test the effectiveness of the methodology and the quality of the obtained models. <s> BIB013 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> MCDA Methods <s> Most multicriteria decision methods need the definition of a significant amount of preferential information from a decision agent. The preference disaggregation analysis paradigm infers the model's parameter values from holistic judgments provided by a decision agent. Here, a new method for inferring the parameters of a fuzzy outranking model for multicriteria sorting is proposed. This approach allows us to use most of the preferential information contained in a reference set. The central idea is to characterize the quality of the model by measuring discrepancies and concordances amongst (i) the preference relations derived from the outranking model, and (ii) the preferential information contained in the reference set. The model's parameters are inferred from a multiobjective optimization problem, according to some additional preferential information from a decision agent. Once the model has been fitted, sorting decisions about new objects are performed by using a fuzzy indifference relation. This proposal performs very well in some examples. <s> BIB014 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> MCDA Methods <s> In many real-world multiobjective optimization problems one needs to find solutions or alternatives that provide a fair compromise between different conflicting objective functions-which could be criteria in a multicriteria context, or agent utilities in a multiagent context-while being efficient (i.e. informally, ensuring the greatest possible overall agents' satisfaction). This is typically the case in problems implying human agents, where fairness and efficiency requirements must be met. Preference handling, resource allocation problems are another examples of the need for balanced compromises between several conflicting objectives. A way to characterize good solutions in such problems is to use the leximin preorder to compare the vectors of objective values, and to select the solutions which maximize this preorder. In this article, we describe five algorithms for finding leximin-optimal solutions using constraint programming. Three of these algorithms are original. Other ones are adapted, in constraint programming settings, from existing works. The algorithms are compared experimentally on three benchmark problems. <s> BIB015 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> MCDA Methods <s> Bank rating refers to the analysis of a bank's overall viability, performance and risk exposure. Within the recent financial turmoil, bank rating has become extremely important. Typically, bank rating is performed through empirical procedures that combine financial and qualitative data into an overall performance index. This paper presents a case study on the implementation of a multicriteria approach to bank rating. The proposed methodology is based on the PROMETHEE II method implemented in an integrated decision support system. Special emphasis is put on the sensitivity of the results with regard to the relative importance of the evaluation criteria and the parameters of the evaluation process. <s> BIB016 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> MCDA Methods <s> In this paper, we use experimental economics methods to test how well Analytic Hierarchy Process (AHP) fares as a choice support system in a real decision problem. AHP provides a ranking that we statistically compare with three additional rankings given by the subjects in the experiment: one at the beginning, one after providing AHP with the necessary pair-wise comparisons and one after learning the ranking provided by AHP. While the rankings vary widely across subjects, we observe that for each individual all four rankings are similar. Hence, subjects are consistent and AHP is, for the most part, able to replicate their rankings. Furthermore, while the rankings are similar, we do find that the AHP ranking helps the decision makers reformulate their choices by taking into account suggestions made by AHP. <s> BIB017 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> MCDA Methods <s> In this paper the authors review the developments of the analytic hierarchy process (AHP) since its inception. The focus of this paper is a neutral review on the methodological developments rather than reporting its applications that have appeared since its introduction. In particular, we discuss problem modelling, pair-wise comparisons, judgement scales, derivation methods, consistency indices, incomplete matrix, synthesis of the weights, sensitivity analysis and group decisions. All have been important areas of research in AHP. <s> BIB018 </s> Multicriteria Models for Learning Ordinal Data: A Literature Review <s> MCDA Methods <s> The Analytic Hierarchy Process (AHP) provides the objective mathematics to process the inescapably subjective and personal preferences of an individual or a group in making a decision. With the AHP and its generalization, the Analytic Network Process (ANP), one constructs hierarchies or feedback networks, then makes judgments or performs measurements on pairs of elements with respect to a controlling element to derive ratio scales that are then synthesized throughout the structure to select the best alternative. <s> BIB019
From Fig. 6 , one can define methodologies which follow the whole process. Analytic Hierarchy Process (AHP) is one of such kind of frameworks BIB001 . After having the problem analysed and criteria selected, usually performed by an expert (or DM), it considers through an hierarchical approach each criteria BIB001 . However, recent reviews have argued that AHP results may not be the most desirable ones BIB017 BIB012 BIB018 . Mentioning that there is no clear evidence that AHP provides its users with their "best" decision BIB017 , or in more detail, identifying the limitations in each step on the process BIB012 . Even though the Analytic Network Process (ANP) was introduced as a generalisation over AHP (a feedback network capable to adjust weights) BIB018 BIB019 , few work has been done for the ordinal case. ELECTRE BIB004 BIB002 and PROMETHEE BIB004 BIB016  are two well known methods that, like AHP, can consist at most by the five steps illustrated in Fig. 6 BIB012 . Both techniques arose from the foundations of the outranking relation theory (ORT) BIB004 . In simple words, it consists of checking the outranking relation among instances which permits to conclude whether an instance x x x (p) outranks instance x x x (q) . Meaning, that instance x x x (p) will be better for the DM than x x x (q) . This is achieved if there are enough statements to confirm (concordance) or to refute that (discordance). The two aforementioned methods require some preferential information which has to be defined by the DM. However, it may be difficult for the DM to understand the meaning of the preferences  . To overcome this, different improvements over the methods have been conducted. One of them was through the usage of evolutionary algorithms. Evolutionary algorithms (EAs) came in a way to reproduce Darwin's theory of the survival of the fittest. EAs are also referred as populational meta-heuristics meaning that they work on the population space of solutions  . EAs generally encompasses on three major steps: 1) Gather a set of solutions; 2) Select a possible subset of candidates on that set of solutions and allow them to reproduce. Reproduction consists mainly on creating new solutions from the selected ones by crossover and mutation operators; 3) Finally, the process is repeated for the set of new solutions until a stopping criteria is achieved. Swiki in BIB008 BIB009 introduced an elitist evolutionary agent 2 system to solve multicriteria optimisation problems. By trying to reproduce biological mechanisms, an elitist group is introduced in the evolutionary architecture proposal. The final solution identified by the elitist group would indicate the desirable one which will dominate other possible solutions identified by other groups. Some hybrid approaches are also present in the literature BIB013 BIB014 . In BIB014 an outranking combined with an EA was proposed thanks to an indifference measure. Since preference modelling is cumbersome, authors used a population based meta-heuristic to generate the best solutions. An agent would then decide the best one. An approach proposed by Doumpos BIB013 comprehends the usage of concordance and discordance measures into a credibility index of an outranking method. This will assess the outranking relation among several alternatives. Since incomparable relations can occur, an EA is used to infer the parameters of the outranking method. In a complete different setting, constraint programming tries to explore all possible combination of solutions thoroughly. Despite this being highly computational expensive, Junker in BIB005 BIB010 argues that an interactive approach has its advantages over state of the art techniques. It is also claimed that current existing methods do not express a clear explanation of the reason for one alternative being more preferable than another. In other words, a performance of 98% does not express which option is the best based on the original preferences. Using a special utility function to define preferences order in BIB010 a lexicographic optimal scheme is applied. Since lexicographic approach establish some ranking over the preferences order  BIB010 , authors also permute the order of alternatives search. Bouveret BIB015 explores the idea in which characterises good solutions where multiple criteria have to be handled through the use of lexicographic algorithms. Other methods incorporate cooperative algorithms which take part in the learning process from diverse sources of information and by different decision criteria BIB007 BIB011 . Methods with such properties are named Dominance-based Set Approach (DRSA) BIB007 which deal with the problem of multicriteria classification using maximum likelihood estimation. The problem is then solved by an optimal object reassignment algorithm. In BIB011 a stochastic DRSA approach is introduced. The rationale behind this method is to assess object class probability from an interval of classes. Rough set theory is another field that one can count with when tackling MCDA. One interesting aspect is that rough set have the ability to produce a model of rule induction similar to data mining, knowledge discovery and machine learning BIB006 . In BIB006 authors extend the fuzzy set theory to rough sets theory in order to avoid as much as possible meaningless transformation of information. Rule induction is made through decision rules induced from dominance-based rough approximations of preference-ordered decision classes BIB003 . Let us now analyse in more depth contributions made to each node in the multicriteria methods process.