Exploring Space Efficiency in a Tree-based Linear Model for Extreme Multi-label Classification (2024)

Abstract: 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 require less than 10% of the size of 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.

## introduction extreme multi-label classification (xmc) focuses on tagging a given instance with a relevant subset of labels from an extremely large label set. there is a wide range of applications, from online retail search systems @xcite to automatically tagging labels on a given article or web page @xcite . xmc problems are commonly encountered in real-world applications, especially in the area of text data. notably, @xcite provide many text data sets for xmc. many methods have been proposed to solve xmc for text data. for example, neural networks, particularly pre-trained language models, are effective due to their ability to understand context @xcite . however, linear methods with bag-of-words features remain very useful for xmc due to their simplicity and superior efficiency @xcite . linear methods are also competitive in certain circumstances @xcite . this motivates us to investigate the time and space complexity of linear methods in xmc problems in this work. among linear methods for multi-label problems, the simplest one-vs-rest (ovr) setting treats a multi-label problem with l labels as l independent binary problems, learning a weight vector w j for each label @xmath0, . . . , l}. however, for ovr in xmc, current computing resources become unaffordable as the training time and storage for w j 's grow linearly with l. an important line of research on reducing time and space is to construct a label tree @xcite @xcite . the label tree recursively decomposes the xmc problem into smaller ones, and each node in the tree only handles a subset of labels so that the overall training time grows with respect to o(log 2 l) instead of o(l) as shown in @xcite . however, we explain in section 2.2 that more classifiers are needed for a label tree compared to ovr. if weights of these classifiers are dense vectors in the same dimensionality of the input features, storing a tree-based model would need more space then ovr. to tackle this issue, nearly all past works on tree-based models such as @xcite ; @xcite ; @xcite apply weight pruning to change small non-zero entries to zero. however, our experiment in section 4 shows that weight pruning via an improper threshold can result in varying degrees of performance drops. this situation motivates us to study the model size of a tree-based model in practice. in this work, we focus on a less-studied aspect -the needed space to store a linear tree model for sparse data. data sparsity is ubiquitous in xmc. for example, for the bag-of-words features widely used in text classification, each instance only contains several non-zero entries. in the tree methods, each node handles a subset of labels and trains on instances corresponding to them. since the data are sparse, the training subset for a node may have some unused features, causing a reduction on the feature space. thus, if weight vectors are mapped back to the input feature space, many elements are zeros and we can use a sparse format to save the space. this property suggests that a tree model -despite having more classifiers -may still take less space than an ovr model. surprisingly, none of the papers investigate the actual size of a tree model; instead, pruning is directly applied. for sparse training data, we study this issue through theoretical analysis and experiments. our main finding is that for sparse data, a tree-based linear model is smaller than what people thought before. compared with the ovr approach, the model size is 10% or even less for problems with a large number of labels. our research suggests that one should not impose the pruning procedure without checking the model size, which can be easily calculated before the real training. the outline is as follows. section 2 defines the xmc problem and introduces two main linear approaches: ovr and tree-based methods. section 3 compares both the time complexity and the model size of the two approaches. we review some techniques to reduce the model size and discuss their potential issues in section 4. we explain the space-efficiency of tree-based linear models for sparse data in section 5. section 6 presents experimental results and conclusions are provided in section 7. this work is an extension of the first author's master thesis @xcite . additional materials including programs used for experiments are available at https://www.csie.ntu.edu.tw/~cjlin/ papers/multilabel_tree_model_size/ . ## linear methods for xmc to address xmc, there are two main categories for linear methods: the one-vs-rest (ovr) method and tree-based methods. in this section, we will introduce how these methods work. consider the multi-label classification problem involving l labels and ℓ training instances {(x i , y i )} ℓ @xmath1, where root {1, 2, 3, 4, 5, 6, 7, 8, 9} x @xmath2, and y @xmath3, 1} l is the l-dimensional label vector. for each label vector y i , if x i is associated with label j, then the j-th component of y i , denoted by y ij , is 1; otherwise, y @xmath4. ## time and space analysis for linear methods in this section, we compare both the training time and the model size for ovr and tree-based methods. the training-time analysis clearly demonstrates why people favor tree-based methods over ovr, while the model-size discussion highlights the expensive space cost with tree-based methods. although these methods are well documented, our descriptions may be the first to discuss the complexity of the model size in detail. through this section, we follow @xcite to assume the constructed label tree of depth d is balanced, as shown in figure 2 . that is, given the number of clusters k, we assume an ideal situation so that at each node, a clustering method splits its label subset to k equally sized clusters. by this design, a specified d max that is not too large to exhaust all labels results in a tree with depth @xmath5. thus, in our analysis of using the tree in figure 2 , only d appears in the time and space complexity. we further assume that each training instance x i has n non-zero elements on average. ## inherent pruning in tree-based methods for sparse data in this section, we explain that for sparse data, the number of weight values needed to be stored in a tree model can be much less than not only the huge value in (11), but also nl, the number of weight values in an ovr model. we stress that the model size reduction here is not achieved by applying any techniques. instead, it can be regarded as an innate advantage of tree-based methods and we call such reduction "inherent pruning." in the tree-based method, suppose we are training weight vectors at a tree node u. only a subset of all training instances (specifically, instances having any label in the label subset of u) are used. because the feature vectors are sparse, some features may have no values in the subset of training instances. we can remove the unused features before training a multi-label model for the node. alternatively, if our optimization algorithm for each binary classification problem (1) satisfies that • the initial w is zero, and • for unused features (i.e., feature value are zero across all instances), the corresponding w components are never updated, then we can conveniently feed the subset of data into the optimization algorithm and get a w vector with many zero elements. this way, we keep all weight vectors in all nodes to have the same dimension n. we can collect them as a large sparse matrix for easy use. we use the name "inherent pruning" because the tree-based method itself "prunes" weight values for unused features by not updating the corresponding weight components during training. our survey shows that few works, except jasinska-kobus et al. (2020), mentioned the identity. even though, jasinska-kobus et al. (2020) only briefly said that "the weight sparsity increases with the depth of a tree ... implies a significant reduction of space" without further discussion or experiments. ## experimental results in this section, we compare the model size of ovr and tree-based methods across several extreme multi-label text data sets. the statistics for these data sets are listed in ## conclusions in this work, we identify that the many unused features are the main reason for the space-efficiency of tree-based methods under sparse data conditions. our findings indicate that, for large data sets, the size of a tree model can be reduced to just 10% of the size of an ovr model. in practice, one can first calculate the tree model size as soon as the label tree is constructed. by doing so, we can check whether the model size exceeds the available memory before training any binary problem. this approach avoids directly changing the trained weights such as pruning, which carries the risks of compromising the performance.