  In extreme classification problems, learning algorithms are required to map
instances to labels from an extremely large label set. We build on a recent
extreme classification framework with logarithmic time and space, and on a
general approach for error correcting output coding (ECOC) with loss-based
decoding, and introduce a flexible and efficient approach accompanied by
theoretical bounds. Our framework employs output codes induced by graphs, for
which we show how to perform efficient loss-based decoding to potentially
improve accuracy. In addition, our framework offers a tradeoff between
accuracy, model size and prediction time. We show how to find the sweet spot of
this tradeoff using only the training data. Our experimental study demonstrates
the validity of our assumptions and claims, and shows that our method is
competitive with state-of-the-art algorithms.
