Exploring space efficiency in a tree-based linear model for extreme multi-label classification
Extreme multi-label classification (XMC) aims to identify relevant subsets from numerous labels. Among the various approaches for XMC, tree-based linear models are effective due to their superior efficiency and simplicity. However, the space complexity of tree-based methods is not well-studied. Many past works assume that storing the model is not affordable and apply techniques such as pruning to save space, which may lead to performance loss. In this work, we conduct both theoretical and empirical analyses on the space to store a tree model under the assumption of sparse data, a condition frequently met in text data. We found that, some features may be unused when training binary classifiers in a tree method, resulting in zero values in the weight vectors. Hence, storing only non-zero elements can greatly save space. Our experimental results indicate that tree models can achieve up to a 95% reduction in storage space compared to the standard one-vs-rest method for multi-label text classification. Our research provides a simple procedure to estimate the size of a tree model before training any classifier in the tree nodes. Then, if the model size is already acceptable, this approach can help avoid modifying the model through weight pruning or other techniques.
Code (0)
등록된 구현이 없습니다.
Tasks
Extreme Multi-Label ClassificationMulti-Label ClassificationMUlTI-LABEL-ClASSIFICATIONMulti Label Text ClassificationMulti-Label Text Classificationtext-classificationText ClassificationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Extreme Learning Tree
The paper proposes a new variant of a decision tree, called an Extreme Learning Tree. It consists of an extremely random tree with non-linear data transformation, and a linear observer that provides predictions based on …
NonZero: Interaction-Guided Exploration for Multi-Agent Monte Carlo Tree Search
Monte Carlo Tree Search (MCTS) scales poorly in cooperative multi-agent domains because expansion must consider an exponentially large set of joint actions, severely limiting exploration under realistic search budgets. W…
A Hierarchical Spectral Method for Extreme Classification
Extreme classification problems are multiclass and multilabel classification problems where the number of outputs is so large that straightforward strategies are neither statistically nor computationally viable. One stra…
ClassificationGeneral ClassificationTree DecompositionEstimating a Directed Tree for Extremes
We propose a new method to estimate a root-directed spanning tree from extreme data. A prominent example is a river network, to be discovered from extreme flow measured at a set of stations. Our new algorithm utilizes qu…
Causal DiscoveryCausal InferencePD-Sparse : A Primal and Dual Sparse Approach to Extreme Multiclass and Multilabel Classification
We consider Multiclass and Multilabel classification with extremely large number of classes, of which only few are labeled to each instance. In such setting, standard methods that have training, prediction cost linear to…
ClassificationGeneral ClassificationText Classification