M.Sc Thesis

M.Sc StudentEvron Itay
SubjectEfficient Loss-Based Decoding on Graphs for Extreme
DepartmentDepartment of Computer Science
Supervisors ASSOCIATE PROF. Daniel Soudry
Full Thesis textFull thesis text - English Version


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, 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 .