The multi-label classification problem has generated significant interest in
recent years. However, existing approaches do not adequately address two key
challenges: (a) the ability to tackle problems with a large number (say
millions) of labels, and (b) the ability to handle data with missing labels. In
this paper, we directly address both these problems by studying the multi-label
problem in a generic empirical risk minimization (ERM) framework. Our
framework, despite being simple, is surprisingly able to encompass several
recent label-compression based methods which can be derived as special cases of
our method. To optimize the ERM problem, we develop techniques that exploit the
structure of specific loss functions - such as the squared loss function - to
offer efficient algorithms. We further show that our learning framework admits
formal excess risk bounds even in the presence of missing labels. Our risk
bounds are tight and demonstrate better generalization performance for low-rank
promoting trace-norm regularization when compared to (rank insensitive)
Frobenius norm regularization. Finally, we present extensive empirical results
on a variety of benchmark datasets and show that our methods perform
significantly better than existing label compression based methods and can
scale up to very large datasets such as the Wikipedia dataset.

本文研究多标记问题的通用经验风险最小化框架，提出了一种简单的框架，能高效地解决数据中存在缺失标记和标记量极大的问题。通过特定损失函数的结构，基于该框架设计了有效算法，进一步证明了该框架在存在缺失标记时的形式化过度风险边界。此外，对于低秩促进的迹 - 范数正则化，我们的风险界更紧，表现出更好的泛化性能。最后，在各种基准数据集上进行实验，证明了本方法的优越性以及其可扩展性。