Multilabel Classification with Group Testing and Codes
Multilabel Classification with Group Testing and Codes
复制标题
DOI：
--
复制
发表时间：
2017-07
期刊：
影响因子：
--
通讯作者：
Shashanka Ubaru;A. Mazumdar
中科院分区：
文献类型：
--
作者：
Shashanka Ubaru;A. Mazumdar
近年来，我们在许多应用中遇到的多类和多标签分类问题，其类数非常大（10 3−10 6）。然而，每个实例只属于一个或几个类，即标签向量是稀疏的。在这项工作中，我们提出了一种基于组测试的新方法来解决这种具有稀疏标签向量的大型多标签分类问题。我们描述了各种组测试结构，并提倡使用连接Reed Solomon码和不平衡的双部展开图来解决极端分类问题。与现有的流行方法相比，所提出的方法在理论和实践上都有许多优点。我们的方法对二进制字母表进行操作，并可以利用已建立的二进制分类器进行学习。在学习问题中首次利用代码的纠错能力来纠正预测错误。即使分类器错误分类的数量呈线性增长，这些错误也会被完全纠正。建立了该方法的汉明损失误差界。更重要的是，我们的方法使用了一个简单的预测算法，不需要矩阵反演或解决优化问题，使得算法非常便宜。在不同数据集上的数值实验证明了该方法的优越性。
In recent years, the multiclass and mutlilabel classification problems we encounter in many applications have very large ( 10 3 − 10 6 ) number of classes. However, each instance belongs to only one or few classes, i.e., the label vectors are sparse. In this work, we propose a novel approach based on group testing to solve such large multilabel classification problems with sparse label vectors. We describe various group testing constructions, and advocate the use of concatenated Reed Solomon codes and unbalanced bi-partite expander graphs for extreme classification problems. The proposed approach has several advantages theoretically and practically over existing popular methods. Our method operates on the binary alphabet and can utilize the well-established binary classifiers for learning. The error correction capabilities of the codes are leveraged for the first time in the learning problem to correct prediction errors. Even if a linearly growing number of classifiers mis-classify, these errors are fully corrected. We establish Hamming loss error bounds for the approach. More importantly, our method utilizes a simple prediction al-gorithm and does not require matrix inversion or solving optimization problems making the algo-rithm very inexpensive. Numerical experiments with various datasets illustrate the superior performance of our method.