Constructing Multiclass Classifiers using Binary Classifiers Under
  Log-Loss
  The construction of multiclass classifiers from binary elements is studied in
this paper, and performance is quantified by the regret, defined with respect
to the Bayes optimal log-loss. We discuss two known methods. The first is one
vs. all (OVA), for which we prove that the multiclass regret is upper bounded
by the sum of binary regrets of the constituent classifiers. The second is
hierarchical classification, based on a binary tree. For this method we prove
that the multiclass regret is exactly a weighted sum of constituent binary
regrets where the weighing is determined by the tree structure.
  We also introduce a leverage-hierarchical classification method, which
potentially yields smaller log-loss and regret. The advantages of these
classification methods are demonstrated by simulation on both synthetic and
real-life datasets.
