×

Learning valued preference structures for solving classification problems. (English) Zbl 1187.68394

Summary: This paper introduces a new approach to classification which combines pairwise decomposition techniques with ideas and tools from fuzzy preference modeling. More specifically, our approach first decomposes a polychotomous classification problem involving \(m\) classes into an ensemble of binary problems, one for each ordered pair of classes. The corresponding classifiers are trained on the relevant subsets of the (transformed) original training data. In the classification phase, a new query is submitted to every binary learner. The output of each classifier is interpreted as a fuzzy degree of preference for the first in comparison with the second class. By combining the outputs of all classifiers, one thus obtains a fuzzy preference relation which is taken as a point of departure for the final classification decision. This way, the problem of classification is effectively reduced to a problem of decision making based on a fuzzy preference relation. Corresponding techniques, which have been investigated quite intensively in the field of fuzzy set theory, hence become amenable to the task of classification. In particular, by decomposing a preference relation into a strict preference, an indifference, and an incomparability relation, this approach allows one to quantify different types of uncertainty in classification and thereby supports sophisticated classification and postprocessing strategies.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
91B08 Individual preferences

Software:

ElemStatLearn
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allwein, E. L.; Schapire, R. E.; Singer, Y., Reducing multiclass to binary: a unifying approach for margin classifiers, J. Mach. Learning Res., 1, 113-141 (2001) · Zbl 1013.68175
[2] De Baets, B.; Van de Walle, B.; Kerre, E., Fuzzy preference structures and their characterization, J. Fuzzy Math., 3, 373-381 (1995) · Zbl 0839.90002
[3] Chow, C. K., An optimum character recognition system using decision functions, Trans. Electron. Comput., 6, 247-253 (1957)
[4] Dietterich, T. G.; Bakiri, G., Solving multiclass learning problems via error-correcting output codes, J. Artificial Intelligence Res., 2, 263-286 (1995) · Zbl 0900.68358
[5] Dubois, D.; Prade, H.; Smets, P., Representing partial ignorance, IEEE Trans. Systems Man Cybernet. A, 26, 3, 361-377 (1996)
[6] Dubuisson, B.; Masson, M. H., A statistical decision rule with incomplete knowledge about classes, Pattern Recognition, 26, 1, 155-165 (1993)
[7] Fodor, J.; Roubens, M., Fuzzy Preference Modelling and Multicriteria Decision Support (1994), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0827.90002
[8] Fodor, J.; Roubens, M., Valued preference structures, European J. Oper. Res., 79, 277-286 (1994) · Zbl 0812.90005
[9] J. Fürnkranz, Round robin rule learning, in: ICML-2001, Proc. 18th Internat. Conf. Machine Learning, Williamstown, MA, 2001, pp. 146-153.; J. Fürnkranz, Round robin rule learning, in: ICML-2001, Proc. 18th Internat. Conf. Machine Learning, Williamstown, MA, 2001, pp. 146-153.
[10] Fürnkranz, J., Round robin classification, J. Mach. Learning Res., 2, 721-747 (2002) · Zbl 1033.68086
[11] J. Fürnkranz, E. Hüllermeier, Pairwise preference learning and ranking, in: Proc. ECML-2003, 13th European Conf. Machine Learning, Cavtat-Dubrovnik, Croatia, September 2003.; J. Fürnkranz, E. Hüllermeier, Pairwise preference learning and ranking, in: Proc. ECML-2003, 13th European Conf. Machine Learning, Cavtat-Dubrovnik, Croatia, September 2003.
[12] Ha, T. M., The optimum class-selective decision rule, IEEE Trans. Pattern Anal. Mach. Intell., 19, 6, 608-615 (1997)
[13] Hastie, T.; Tibshirani, R.; Friedman, J., The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2001), Springer: Springer Berlin · Zbl 0973.62007
[14] Herbrich, R., Learning Kernel Classifiers (2002), MIT Press: MIT Press Cambridge, MA · Zbl 1504.68002
[15] Hoeting, J. A.; Madigan, D.; Raftery, A. E.; Volinsky, C. T., Bayesian model averaging: a tutorial, Statist. Sci., 14, 4, 382-417 (1999) · Zbl 1059.62525
[16] Hüllermeier, E.; Fürnkranz, J., Learning label preferences: ranking error versus position error, (Proc. IDA-05, 6th Internat. Symp. Intelligent Data Analysis, Madrid, Lecture Notes in computer science, Vol. 3646 (2005), Springer: Springer Berlin), 180-191 · Zbl 1141.68568
[17] Klement, E. P.; Mesiar, R.; Pap, E., Triangular Norms (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 1007.20054
[18] M. Kukar, I. Kononenko, Reliable classifications with machine learning, in: Proc. European Conf. Machine Learning, ECML, 2002, pp. 219-231.; M. Kukar, I. Kononenko, Reliable classifications with machine learning, in: Proc. European Conf. Machine Learning, ECML, 2002, pp. 219-231. · Zbl 1014.68805
[19] T.M. Mitchell, The need for biases in learning generalizations, Technical Report CBM-TR-117, Rutgers University, 1980.; T.M. Mitchell, The need for biases in learning generalizations, Technical Report CBM-TR-117, Rutgers University, 1980.
[20] Orlovski, S., Decision-making with a fuzzy preference relation, Fuzzy Sets and Systems, 1, 155-167 (1978) · Zbl 0396.90004
[21] Ovchinnikov, S.; Ozernoy, V., Using fuzzy binary relations for identifying noninferior decision alternatives, Fuzzy Sets and Systems, 25, 21-32 (1988) · Zbl 0645.90001
[22] Perny, P.; Roy, B., The use of fuzzy outranking relations in preference modelling, Fuzzy Sets and Systems, 49, 33-53 (1992) · Zbl 0765.90003
[23] Platt, J., Probabilistic outputs for support vector machines and comparison to regularized likelihood methods, (Smola, A. J.; Bartlett, P.; Schoelkopf, B.; Schuurmans, D., Advances in Large Margin Classifiers (1999), MIT Press: MIT Press Cambridge, MA), 61-74
[24] Schölkopf, B.; Smola, A. J., Learning with Kernels: Support Vector Machines, Regularization, Optimization and Beyond (2001), MIT Press: MIT Press Cambridge, MA
[25] Setnes, M.; Babuska, R., Fuzzy relational classifier trained by fuzzy clustering, IEEE Trans. Systems Man Cybernet., 29, 5, 619-625 (1999)
[26] E. Smirnov, I. Sprinkhuizen-Kuyper, G. Nalbantov, S. Vanderlooy, Version space support vector machines, in: Proc. ECAI-06, 17th European Conf. Artificial Intelligence, Riva del Garda, Spain, 2006, pp. 809-810.; E. Smirnov, I. Sprinkhuizen-Kuyper, G. Nalbantov, S. Vanderlooy, Version space support vector machines, in: Proc. ECAI-06, 17th European Conf. Artificial Intelligence, Riva del Garda, Spain, 2006, pp. 809-810.
[27] Zadeh, L. A., Fuzzy sets, Inform. Control, 8, 338-353 (1965) · Zbl 0139.24606
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.