TU Darmstadt / ULB / TUbiblio

Efficient Pairwise Classification and Ranking

Park, Sang-Hyeun ; Fürnkranz, Johannes (2007)
Efficient Pairwise Classification and Ranking.
Report, Bibliographie

Kurzbeschreibung (Abstract)

Pairwise classification is a class binarization procedure that converts a multi-class problem into a series of two-class problems, one problem for each pair of classes. While it can be shown that for training, this procedure is more efficient than the more commonly used one-against-all approach, it still has to evaluate a quadratic number of classifiers when computing the predicted class for a given example. In this paper, we propose a method that allows a faster computation of the predicted class when weighted or unweighted voting are used for combining the predictions of the individual classifiers. While its worst-case complexity is still quadratic in the number of classes, we show that even in the case of completely random base classifiers, our method still outperforms the conventional pairwise classifier. For the more practical case of well-trained base classifiers, its asymptotic computational complexity seems to be almost linear. We also propose a method for approximating the full class ranking, based on the Swiss System, a common scheme for conducting multi-round chess tournaments. Our results indicate that this adaptive scheme offers a better trade-off between approximation quality and number of performed comparisons than alternative, fixed schemes for ordering the evaluation of the pairwise classifiers.

Typ des Eintrags: Report
Erschienen: 2007
Autor(en): Park, Sang-Hyeun ; Fürnkranz, Johannes
Art des Eintrags: Bibliographie
Titel: Efficient Pairwise Classification and Ranking
Sprache: Englisch
Publikationsjahr: 2007
URL / URN: http://www.ke.informatik.tu-darmstadt.de/publications/report...
Kurzbeschreibung (Abstract):

Pairwise classification is a class binarization procedure that converts a multi-class problem into a series of two-class problems, one problem for each pair of classes. While it can be shown that for training, this procedure is more efficient than the more commonly used one-against-all approach, it still has to evaluate a quadratic number of classifiers when computing the predicted class for a given example. In this paper, we propose a method that allows a faster computation of the predicted class when weighted or unweighted voting are used for combining the predictions of the individual classifiers. While its worst-case complexity is still quadratic in the number of classes, we show that even in the case of completely random base classifiers, our method still outperforms the conventional pairwise classifier. For the more practical case of well-trained base classifiers, its asymptotic computational complexity seems to be almost linear. We also propose a method for approximating the full class ranking, based on the Swiss System, a common scheme for conducting multi-round chess tournaments. Our results indicate that this adaptive scheme offers a better trade-off between approximation quality and number of performed comparisons than alternative, fixed schemes for ordering the evaluation of the pairwise classifiers.

ID-Nummer: TUD-KE-2007-03
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik > Knowledge Engineering
20 Fachbereich Informatik
Hinterlegungsdatum: 24 Jun 2011 15:26
Letzte Änderung: 05 Mär 2013 09:49
PPN:
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen