  The construction of multiclass classifiers from binary classifiers is studied
in this paper, and performance is quantified by the regret, defined with
respect to the Bayes optimal log-loss. We start by proving that the regret of
the well known One vs. All (OVA) method is upper bounded by the sum of the
regrets of its constituent binary classifiers. We then present a new method
called Conditional OVA (COVA), and prove that its regret is given by the
weighted sum of the regrets corresponding to the constituent binary
classifiers. Lastly, we present a method termed Leveraged COVA (LCOVA),
designated to reduce the regret of a multiclass classifier by breaking it down
to independently optimized binary classifiers.
