Journal of Machine Learning Research 2 (2002),
pp. 721-747. Submitted 08/01; published 03/02
Postscript and PDF versions of this document are
available from here.
© 2002 Johannes Fürnkranz
Round Robin Classification
Austrian Research Institute for Artificial Intelligence
Schottengasse 3, A-1010 Wien, Austria
In this paper, we discuss round robin classification (aka pairwise
classification), a technique for handling multi-class problems with
binary classifiers by learning one classifier for each pair of
classes. We present an empirical evaluation of the method,
implemented as a wrapper around the RIPPER rule learning
algorithm, on 20 multi-class datasets from the UCI database
repository. Our results show that the technique is very likely to
improve RIPPER's classification accuracy without having a high risk
of decreasing it.
More importantly, we give a general theoretical analysis of the
complexity of the approach and show that its run-time complexity is
below that of the commonly used one-against-all technique. These
theoretical results are not restricted to rule learning but are also
of interest to other communities where pairwise classification has
recently received some attention.
Furthermore, we investigate its properties as a general ensemble
technique and show that round robin classification with C5.0 may
improve C5.0's performance on multi-class problems. However, this
improvement does not reach the performance increase of boosting, and
a combination of boosting and round robin classification does not
produce any gain over conventional boosting.
Finally, we show that the performance of round robin classification
can be further improved by a straight-forward integration with