%0 Journal Article
%T Extreme classification under limited space and time budget
%A Jasińska, Kalina
%A Dembczyński, Krzysztof
%A Karampatziakis, Nikos
%J Schedae Informaticae
%V 2016
%R 10.4467/20838476SI.16.001.6182
%N Volume 25
%P 9-23
%K supervised learning, space and time complexity of learning algorithms, extreme classification, multi-class classification, learning reductions
%@ 1732-3916
%D 2017
%U https://ejournals.eu/en/journal/schedae-informaticae/article/extreme-classification-under-limited-space-and-time-budget
%X 
	We discuss a new framework for solving extreme classification (i.e., learning problems with an extremely large label space), in which we reduce the original problem to a structured prediction problem. Thanks to this we can obtain learning algorithms that work under a strict time and space budget. We mainly focus on a recently introduced algorithm, referred to as LTLS, which is to our best knowledge the first truly logarithmic time and space (in the number of labels) method for extreme classification. We compare this algorithm with two other approaches that also rely on transformation to structured prediction problems. The first algorithm encodes original labels as binary sequences. The second algorithm follows the label tree approach. The comparison shows the trade-off between computational complexity (in time and space) and predictive performance.