Enabling Efficiency-Precision Trade-offs for Label Trees in Extreme Classification

Extreme multi-label classification (XMC) aims to learn a model that can tag\ndata points with a subset of relevant labels from an extremely large label set.\nReal world e-commerce applications like personalized recommendations and\nproduct advertising can be formulated as XMC problems, where the objective is\nto predict for a user a small subset of items from a catalog of several million\nproducts. For such applications, a common approach is to organize these labels\ninto a tree, enabling training and inference times that are logarithmic in the\nnumber of labels. While training a model once a label tree is available is well\nstudied, designing the structure of the tree is a difficult task that is not\nyet well understood, and can dramatically impact both model latency and\nstatistical performance. Existing approaches to tree construction fall at an\nextreme point, either optimizing exclusively for statistical performance, or\nfor latency. We propose an efficient information theory inspired algorithm to\nconstruct intermediary operating points that trade off between the benefits of\nboth. Our algorithm enables interpolation between these objectives, which was\nnot previously possible. We corroborate our theoretical analysis with numerical\nresults, showing that on the Wiki-500K benchmark dataset our method can reduce\na proxy for expected latency by up to 28% while maintaining the same accuracy\nas Parabel. On several datasets derived from e-commerce customer logs, our\nmodified label tree is able to improve this expected latency metric by up to\n20% while maintaining the same accuracy. Finally, we discuss challenges in\nrealizing these latency improvements in deployed models.\n