探究巨量多標籤分類中使用樹狀線性方法之所需空間

Abstract

巨量多標籤分類問題旨在從大量標籤中找出與給定資料相關之標籤。針對此分類問題，基於標籤樹的線性模型 (tree-based linear models) 是種簡單而有效率的方法。然而，鮮少研究專注於該方法的所需空間分析。許多過去的研究假定該方法訓練出的模型過大，進而使用權重修剪等方法減少模型大小，但這卻可能導致模型預測能力變差。在這篇論文中，我們透過理論和實驗分析樹狀線性模型在資料的向量為稀疏的狀況下所耗費的空間。此一對於資料的稀疏假設常見於文本分類的問題中。我們發現在樹狀方法在該假設之下會有很多資料特徵在訓練二元分類器時不會被使用到，導致學習到的權重向量包含許多零值。因此，使用稀疏矩陣儲存這些權重可以大幅的節省所需空間。實驗結果顯示，在多標籤文本分類問題之中，相對於標準的二元相關 (binary relevance) 方法，樹狀模型可以省下高達 95% 的儲存空間。該研究結果也提供在訓練樹狀模型之間可以估計模型大小的方法。因此，若估計模型大小已符合空間資源限制，使用者可避免使用權重修剪等方法更動模型。

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.