Random Label Forests: An Ensemble Method with Label Subsampling For Extreme Multi-Label Problems (2024)

Abstract: Text classification is one of the essential topics in natural language processing, and each text is often associated with multiple labels. Recently, the number of labels has become larger and larger, especially in the applications of e-commerce, so handling text-related e-commerce problems further requires a large memory space in many existing multi-label learning methods. To address the space concern, utilizing a distributed system to share that large memory requirement is a possible solution. We propose “random label forests,” a distributed ensemble method with label subsampling, for handling extremely large-scale labels. Random label forests can reduce memory usage per computer while keeping competitive performances over real-world data sets.

## introduction text classification is one of the essential topics in natural language processing fields. there are many valuable applications, such as product categorization for e-commerce @xcite @xcite , coding diagnosis and procedures in medical records @xcite , and document tagging @xcite . usually, the prediction in the text classification can be multi-labeled. hence, a text classification problem falls into the category of multi-label classification, which is used to find the relevant labels of a data instance. for example, we can set the document content and tags in the document tagging problem as the feature and labels in a multi-label problem. recently, the number of labels has become larger and larger, especially in the applications of e-commerce. thus, an emerging topic is extreme multi-label learning (xml), which focuses on large-scale candidate labels, input instances, and input features. because of these three large-scale components, an xml method should further con-sider the model training time and memory usage in addition to the performance. a simple and classic way to solve a multi-label classification problem is by the one-versus-rest (ovr) method with linear models. however, the time complexity and model size directly depend on the number of labels and features. to handle problems with many labels, two existing extensions of ovr are developed: • dismec @xcite splits the label set into several subsets and lets each machine in a distributed system handle one subset. this way, the training time and model size per machine are reduced. let us go back to discussing the linear methods. although dismec and tree-based linear methods are reasonable solutions for xml problems, each method still has disadvantages. dismec can only handle a small number of labels, but not large-scale labels, on each machine. tree-based linear methods require large memory space to handle all the labels during the training. hence, we hope a method can take the advantages of dismec and tree-based methods without having their disadvantages. label subsampling is another way to divide an xml problem into more minor subproblems. rakel @xcite is a pioneer in using label subsampling with the ensemble method. after the label subsampling, rakel converts each small-scale multi-label subproblem to a multi-class one by considering every label combination as a new class label. this setting, referred to as "label powerset" in multi-label learning, is not scalable to xml because covering the predictions of highly large-scale labels by the powerset method is almost impossible. in this work, we utilize label subsampling and the distributed system to reduce the impact of the large-scale labels. specifically, each computer can solve a smaller xml subproblem via some existing xml methods, such as tree-based linear methods. hence, handling xml problems with billions of labels or more becomes practical. since we use the label subsampling technique with the tree-based linear method, we call this method "random label forests." let us list our contributions as follows. ## multi-label problems a multi-label classification problem aims to find a function f with the parameter θ that can predict whether a given instance x, which is a feature vector in r n , is associated with the label-j for @xmath0, . . . , m, where n and m are the feature dimension and the number of labels. we use 0/1 to indicate if an instance is associated without/with a label. hence, we can denote @xmath1, 1} m as the label vector of the instance @xmath2; θ) can be as close to y as possible. based on the definition above, past works @xcite @xcite utilize linear models to handle the multi-label classification problem, and other works @xcite @xcite @xcite use the different architectures of neural networks. although neural network models perform better in many fields, @xcite point out that the linear model is still a strong baseline for certain multi-label classification data. furthermore, the linear models are easy to understand and more explainable, so we focus on linear models in this work. ## distributed settings to address the memory issue using multiple computers to store a model can reduce the memory usage in each computer. in the past, dismec distributed the training and the storage of an ovr model to multiple computers. however, the setting is still not scalable to data with extremely many labels. hence, separating a treebased model into several computers is a possible solution because of the faster training and smaller model size than the ovr setting. therefore, we discuss the distributed training of a tree-based model in the following subsections. ## experiments section 3.2 discusses different distributed settings on tree-based models, so we first analyze which setting is the better choice over four smaller xml data sets in section 4.1. after deciding on the distributed setting, we compare three linear models: ovr, a tree-based model with all labels, and random label forests on six xml data sets in section 4.2. throughout this section, the label number m is shown after the name in each data set. we leave the details of data sets in appendix a and discuss the hyper-parameters in appendix b. to measure the performance of an xml model, we follow the works @xcite @xcite @xcite to use precision at 1, 3, and 5 as the metrics of the predictions. we discuss the model size in section 4.3, and the comparison of the training time is in section 4.4. ## conclusion this work proposes random label forests, a distributed ensemble method with label subsampling, and tree-based linear models as the backbone. random label forests give competitive performances using much less training time and memory usage in a machine. hence, handling a problem with extremely many labels becomes practical. for all methods considered and evaluated in this work, the backbone is a linear classifier. in the future, we plan to consider more sophisticated techniques, such as neural networks.