Efficient Loss-Based Decoding on Graphs For Extreme Classification
This addresses extreme classification problems for applications requiring efficient handling of massive label sets, representing an incremental improvement over existing frameworks.
The paper tackles extreme classification problems with large label sets by introducing a flexible framework using graph-induced output codes with efficient loss-based decoding, offering a tradeoff between accuracy, model size, and prediction time. Experimental results show the method is competitive with state-of-the-art algorithms.
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.