TY - JOUR
TI - Extreme classification under limited space and time budget
AU - Jasińska, Kalina
AU - Dembczyński, Krzysztof
AU - Karampatziakis, Nikos
TI - Extreme classification under limited space and time budget
AB - 
	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.
VL - 2016
IS - Volume 25
PY - 2017
SN - 1732-3916
C1 - 2083-8476
SP - 9
EP - 23
DO - 10.4467/20838476SI.16.001.6182
UR - https://ejournals.eu/en/journal/schedae-informaticae/article/extreme-classification-under-limited-space-and-time-budget
KW - supervised learning
KW - space and time complexity of learning algorithms
KW - extreme classification
KW - multi-class classification
KW - learning reductions