Bonsai: diverse and shallow trees for extreme multi-label classification (2019-04-17T00:00:00.000000Z)

TL;DR

A suite of algorithms, called Bonsai, is developed, which generalizes the notion of label representation in XMC, and partitions the labels in the representation space to learn shallow trees, and achieves the best of both worlds.

Abstract

Extreme multi-label classification (XMC) refers to supervised multi-label learning involving hundreds of thousands or even millions of labels. In this paper, we develop a suite of algorithms, called Bonsai, which generalizes the notion of label representation in XMC, and partitions the labels in the representation space to learn shallow trees. We show three concrete realizations of this label representation space including: (i) the input space which is spanned by the input features, (ii) the output space spanned by label vectors based on their co-occurrence with other labels, and (iii) the joint space by combining the input and output representations. Furthermore, the constraint-free multi-way partitions learnt iteratively in these spaces lead to shallow trees. By combining the effect of shallow trees and generalized label representation, Bonsai achieves the best of both worlds—fast training which is comparable to state-of-the-art tree-based methods in XMC, and much better prediction accuracy, particularly on tail-labels. On a benchmark Amazon-3M dataset with 3 million labels, Bonsai outperforms a state-of-the-art one-vs-rest method in terms of prediction accuracy, while being approximately 200 times faster to train. The code for Bonsai is available at https://github.com/xmc-aalto/bonsai.

Authors

Sujay Khandagale

2 papers

Rohit Babbar

4 papers

Han Xiao

1 papers

TL;DR

Abstract

Authors

References57 items

Accelerating Extreme Classification via Adaptive Feature Agglomeration

Gradient tree boosting with random output projections for multi-label classification and multi-output regression

Fast Training for Large-Scale One-versus-All Linear Classifiers using Tree-Structured Initialization

LdSM: Logarithm-depth Streaming Multi-label Decision Trees

Data scarcity, robustness and extreme multi-label classification

Block-wise Partitioning for Extreme Multi-label Classification

A no-regret generalization of hierarchical softmax to extreme multi-label classification

Does Tail Label Help for Large-Scale Multi-Label Learning?

Binary relevance for multi-label learning: an overview

Deep Learning for Extreme Multi-label Text Classification

Gradient Boosted Decision Trees for High Dimensional Sparse Output

AnnexML: Approximate Nearest Neighbor Search for Extreme Multi-label Classification

PPDsparse: A Parallel Primal-Dual Sparse Method for Extreme Classification

DiSMEC: Distributed Sparse Machines for Extreme Multi-label Classification

Extreme Multi-label Loss Functions for Recommendation, Tagging, Ranking & Other Missing Label Applications

Robust Extreme Multi-label Learning

Bag of Tricks for Efficient Text Classification

PD-Sparse : A Primal and Dual Sparse Approach to Extreme Multiclass and Multilabel Classification

Extreme F-measure Maximization using Sparse Probability Estimates

Sparse Local Embeddings for Extreme Multi-label Classification

User Conditional Hashtag Prediction for Images

LSHTC: A Benchmark for Large-Scale Text Classification

On power law distributions in large-scale taxonomies

Convolutional Neural Networks for Sentence Classification

FastXML: a fast, accurate and stable tree-classifier for extreme multi-label learning

Multi-label Classification via Feature-aware Implicit Label Space Encoding

On Flat versus Hierarchical Classification in Large-Scale Taxonomies

Distributed Representations of Words and Phrases and their Compositionality

Hidden factors and hidden topics: understanding rating dimensions with review text

Large-scale Multi-label Learning with Missing Labels

Multi-label learning with millions of labels: recommending advertiser bid phrases for web pages

Feature-aware Label Space Dimension Reduction for Multi-label Classification

ImageNet classification with deep convolutional neural networks

Multilabel Classification with Principal Label Space Transformation

An extensive experimental comparison of methods for multi-label learning

Item categorization in the e-commerce domain

Label Embedding Trees for Large Multi-Class Tasks

What Does Classifying More Than 10, 000 Image Categories Tell Us?

Multi-Label Prediction via Compressed Sensing

Multi-label Classification Using Ensembles of Pruned Sets

Decision trees for hierarchical multi-label classification

LIBLINEAR: A Library for Large Linear Classification

Multi-Label Classification: An Overview

Least squares quantization in PCM

A Simple and Effective Scheme for Data Pre-processing in Extreme Classification

Parabel: Partitioned label trees for extreme classi-ﬁcation with application to dynamic search advertising

Extreme Classification (Dagstuhl Seminar 18291)

International conference on machine learning (pp

Extreme Multi-label Loss Functions for Recommendation, Tagging, Ranking & Other Missing Label Applications –

Learning Taxonomy Adaptation in Large-scale Classification

The extreme classification repository: Multi-label datasets and code

Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)

Advances in neural information processing systems (pp

Effective and Efficient Multilabel Classification in Domains with Large Number of Labels

Publisher's Note

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence WSABIE: Scaling Up To Large Vocabulary Image Annotation

Machine Learning

Field of Study

Journal Information

Name

Page

Volume

Venue Information

Name

Type

URL

Alternate Names