\title{Round Robin Classification}
\author{\name Johannes F\"urnkranz \email juffi@oefai.at\\
\addr Austrian Research Institute for Artificial Intelligence \\
Schottengasse 3, A-1010 Wien, Austria}

\editor{Yoram Singer}

\maketitle

\begin{abstract}%
  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 \cfive\ may
  improve \cfive'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
  bagging.