Technical Report MSC-2019-07

Title: Efficient Loss-Based Decoding on Graphs for Extreme Classification
Authors: Itay Evron
Supervisors: Daniel Soudry
PDFCurrently accessibly only within the Technion network
Abstract: Classification is a popular task in the field of machine learning, in which learning algorithms are required to map instances to labels from a finite set of labels. In binary classification problems, the label set consists of only two labels. For instance, given an email we would like to determine whether it is spam. Binary tasks are well studied and often have simple and intuitive solutions.

In multiclass classification problems, the label set contains three or more labels. For example, given an image of an animal, we would like to determine which kind of animal appears in it. Due to the simplicity of binary classification learning algorithms, many solutions for multiclass problems reduce single multiclass problems to many binary subproblems.

Extreme classification problems, are multiclass problems, where the label set becomes extremely large. In this regime, the widely practiced reductions to binary subproblems become infeasible due to their excessive space and time complexity requirements, which are often linear in the number of classes.

We build on a recent extreme classification framework with logarithmic time and space \cite{Jasinska2016}, and on a well-known 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. The suggested framework is a time and space efficient scheme for both training and inference. Moreover, it allows using any loss function for decoding, potentially improving 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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2019
To the main CS technical reports page

Computer science department, Technion