Large-scale Multi-label Learning with Missing Labels

Hsiang-Fu Yu; Prateek Jain; Purushottam Kar; Inderjit S. Dhillon

Source-linked AI summary

Large-scale Multi-label Learning with Missing Labels

Hsiang-Fu Yu, Prateek Jain, Purushottam Kar, Inderjit S. Dhillon

arXiv:1307.5101v3Jul 18, 2013cs.LG

TL;DR

The paper targets multi-label learning with extremely many labels and incomplete annotations. It formulates the problem as low-rank ERM, develops structure-exploiting optimization methods, and analyzes trace-norm generalization. The resulting methods outperform label-compression baselines on benchmarks and scale to a Wikipedia dataset with 213,707 labels.

Problem
Existing multi-label methods inadequately address both extremely large label spaces and missing labels, despite applications requiring scalable prediction from incomplete annotations.
Method
The paper learns a low-rank linear model in a general ERM framework, with loss-specific efficient algorithms and support for regularization and missing labels.
Results
The methods significantly outperform existing label-compression approaches on almost all benchmarks and scale to Wikipedia with 881,805 training samples and 213,707 labels.
Takeaways & Limitations
The framework unifies several label-compression methods while extending them to missing labels, scalable optimization, and formal excess-risk analysis.
Takeaways & Limitations
The theoretical analysis assumes labels are observed uniformly at random, and trace- versus Frobenius-norm regularization may induce different biases.

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses large-scale multi-label learning and missing labels through a low-rank ERM framework that unifies dimension-reduction methods, supports efficient optimization, and provides theoretical and empirical validation.

Motivation: Large-scale multi-label classification requires scalable models because millions of labels make independent binary classifiers memory-intensive and slow.For 10^4 labels and 10^6 features, Binary Relevance can require around 100 Gigabytes of memory.
Framework: The proposed approach learns a low-rank linear model in a general ERM framework, unifying label- and feature-dimensionality reduction while supporting multiple losses and regularizers.With squared-L2 loss, the formulation has a closed-form solution and recovers CPLST as a special case.
Missing labels: The framework handles missing labels, unlike most dimension-reduction formulations, addressing incomplete and noisy annotation in applications such as images and Wikipedia.The paper notes that human annotators often label only prominent or familiar categories.
Optimization: Efficient algorithms use alternating minimization, conjugate gradients, and loss-specific structure; for squared loss with trace-norm regularization, the method is O(d̄) faster than direct computation.Here d̄ is the average number of nonzero features in an instance.
Theory: Under isotropic data distributions, trace-norm methods achieve excess risk O(1/√(nL)), compared with O(1/√n) for full-rank learning.The analysis assumes labels are observed uniformly at random.
Evaluation: Experiments show significant improvements over recent label-compression methods on almost all benchmark datasets, while scaling to Wikipedia with 881,805 training samples and 213,707 labels.On Wikipedia, training time is orders of magnitude shorter than for several existing methods.

2 Problem Formulation

The paper formulates multi-label prediction as regularized ERM over a low-rank linear model, supporting missing labels and unifying dimensionality-reduction methods. Under squared-L2 loss, the formulation connects exactly to CPLST while enabling regularization, alternative losses, and missing-label handling.

2 Problem Formulation: The model predicts labels as f(x; Z) = ZT x, with Z ∈ R^(d×L), and learns Z through regularized empirical risk minimization.The loss is decomposable across labels, and the regularizer is applied to Z.
2 Problem Formulation: Low-rank structure captures correlated labels by restricting Z to a small number of latent factors, reducing effective parameters and controlling overfitting.The motivation is that significant label correlations can make the effective parameter count much smaller than d × L.
2 Problem Formulation: Known labels are indexed by Ω, while each label may be on, off, or missing under the paper’s standard missing-value setting.The loss is computed only over known labels when labels are missing.
2 Problem Formulation: The rank-constrained formulation is generally NP-hard, but convex losses permit alternating minimization, and squared-L2 loss yields closed-form solutions for fully observed labels.The non-convex rank constraint creates the computational difficulty.
2.1 Special Case: Squared-L2 loss: In the absence of missing labels, SVD solves the squared-L2 formulation optimally, and an appropriate regularizer and λ recover CPLST exactly.The equivalence is stated for the squared-L2 loss and full-label case.
2.1 Special Case: Squared-L2 loss: The ERM formulation gives CPLST a principled derivation and extends it with regularization, other loss functions, and missing-label support.The paper contrasts this with CPLST’s ad-hoc derivation and its inability to directly handle missing labels.

3 Algorithms

The algorithms optimize the low-rank model through factorized alternating minimization. Convex subproblems arise when either factor is fixed, while convergence guarantees and specialized solvers depend on the loss and data setting.

3 Algorithms: The low-rank matrix is factorized as Z = WHT, avoiding direct representation with d × L entries and allowing decomposable regularization.The factors have dimensions W ∈ R^(d×k) and H ∈ R^(L×k), with r(Z) decomposed into r1(W)+r2(H).
3 Algorithms: Alternating minimization updates W and H in turn; fixing either factor makes the objective convex.The method is applied to the rank-constrained objective, including missing-label settings.
3 Algorithms: For convex losses, the alternating sequence converges to a stationary point when both block minima are uniquely defined.With squared loss and fully observed labels, convergence to the global minimum is established when λ = 0 or X is orthogonal.
3 Algorithms: With W fixed, each row hj of H can be updated independently as a small-k linear classification or regression problem.Each update uses the known labels associated with label j.
3 Algorithms: With H fixed, updating W becomes a regularized linear classification or regression problem over |Ω| examples with transformed features ˜xij = hj ⊗ xi.This block is more involved because the variables are mixed through multiplication by X.
3 Algorithms: The implementation provides separate procedures for general-loss optimization with missing labels, including gradient and Hessian-vector computations.The procedures support iterative optimization of the W subproblem.

4. Return: vec

The paper develops structure-exploiting operations for large-scale optimization, especially for squared loss, and discusses kernel extensions and parallel execution. These methods reduce dependence on dense label observations while retaining the low-rank ERM framework.

4. Return: vec: Updating W directly requires solving a regularized least-squares problem with dk variables, which is infeasible when d is very large.A closed-form solution would require inverting a dk × dk matrix.
4. Return: vec: Conjugate Gradient is suitable when dk and |Ω| are large because it uses cheap iterative updates and can obtain good approximate solutions quickly.The main computational operations are gradient or Hessian-matrix-vector products.
4. Return: vec: Direct computation of the gradient and Hessian-vector product requires O(|Ω| d̄k) time, motivating faster procedures.The paper then exploits the structure of the transformed feature matrix.
4. Return: vec: For general twice-differentiable losses, the gradient and Hessian-vector product can each be computed in O((nnz(X) + |Ω| + d) × k) time.This assumes the loss derivative can be computed in constant time.
4. Return: vec: For squared loss with full labels, operations depend on nnz(Y) rather than |Ω|, and nnz(Y) is typically much smaller than nL.This makes alternating minimization efficient even when all nL entries are formally observed.
4. Return: vec: The squared-loss implementation uses O(nk + k^2) extra space and performs efficient gradient and Hessian-vector computations.The stated time expression combines sparse X and Y operations with lower-order factor terms.
4. Return: vec: Parallel BLAS can accelerate both algorithms through matrix multiplication, and experiments report speedups as the number of cores increases.The paper identifies matrix multiplication as a crucial shared subroutine.
4. Return: vec: The framework extends to nonlinear kernels through the Representer Theorem, replacing x with a kernel feature vector while preserving low-rank and trace-norm structure.Alternating minimization applies to the resulting kernelized objectives.

4 Generalization Error Bounds

The paper analyzes generalization for trace-norm-regularized ERM with randomly missing labels, comparing its bounds with Frobenius-norm regularization. The analysis identifies distributional settings, especially near-isotropic data, where trace-norm regularization can yield superior bounds.

Trace-Norm Generalization Analysis: The analysis studies excess-risk guarantees for trace-norm-regularized ERM despite missing labels, requiring random matrix theory because standard results do not apply directly.The paper introduces a novel Rademacher-average analysis for the interaction between feature vectors and missing labels.
Learning with Missing Labels: The model observes each training label vector at s uniformly random locations, with locations chosen independently of the data and labels.This missing-label process underlies the generalization analysis.
Limits and Tightness: The uniform-convergence analysis is essentially tight, but the two regularizers may induce different biases whose bias-variance trade-offs remain open.The paper notes that both formulations may suffer similar biases when label correlations are present.
Interpretation: When labels are sparsely observed, Frobenius regularization effectively trains independent label predictors on only O(n/L) examples per label, whereas shared predictors can use O(n) points.This supports the paper’s intuition that trace-norm regularization can capture cross-label dependencies more effectively under missing labels.

5 Experimental Results

Experiments evaluate LEML’s accuracy, scalability, loss functions, dimensionality reduction, and missing-label performance against label-compression and baseline methods across benchmark datasets.

Datasets: Experiments cover standard, high-dimensional, and very large-scale datasets, including Wikipedia with about 1M pages and 200K labels.Small datasets support comparisons with BCS and CPLST, while only LEML and WSABIE scale to eurlex, nus-wide, and wiki.
Results with full labels: LEML is consistently better than competing dimensionality-reduction methods across tested reduction ratios and remains competitive with or superior to BR.On bibtex and compphys, LEML outperforms BR; regularization also avoids the performance dips observed for CPLST on autofood and compphys.
Results with full labels: LEML is always superior or competitive with WSABIE across smaller datasets when using squared, logistic, or squared-hinge losses.The best loss varies by dataset, but LEML maintains the strongest overall comparison.
Results with full labels: On eurlex and nus-wide, LEML is clearly superior to WSABIE on all evaluation criteria, while on wiki it regains an advantage at k = 500.The evaluation uses top-K accuracy, Hamming loss, and average AUC; Hamming loss is omitted for the WSABIE comparison because its ranking is not directly converted to 0/1 labels.
Scalability: LEML reaches 0.9374 AUC on wiki in under 6 hours, whereas WSABIE reaches 0.9058 AUC after about 1.6 days.WSABIE’s first three epochs take about 7,000s, 16,000s, and 36,000s, respectively.

6 Conclusion

The paper develops an ERM framework for scalable multi-label learning with missing labels, using rank constraints, regularization, and structure-exploiting optimization. Its theory and experiments support improved generalization and performance, while leaving convergence guarantees and tighter risk bounds as open questions.

The framework addresses multi-label learning with missing labels using rank constraints and regularizers for scalability and efficiency.
Alternating minimization solves the resulting non-convex problem while exploiting loss structure to improve scalability.
The excess-risk analysis indicates better generalization for the proposed methods than existing approaches such as Binary Relevance, consistent with experiments.
Future work includes extending LEML to non-decomposable losses, proving global convergence conditions, and improving bounds beyond the uniform-convergence route.
The risk analysis proceeds through Rademacher averages and spectral norms, using Hölder’s inequality and random matrix theory.
Trace-norm analysis can exploit spectral-norm structure that Frobenius regularization cannot use when the spectral norm is much smaller.

B.4 Step 4: Calculating the Spectral norm of a Random Matrix

The spectral-norm analysis bounds the Rademacher average by controlling label-observation counts and random-matrix column concentration. The resulting theorem identifies when trace-norm regularization gains an advantage, especially under near-uniform labels and near-isotropic data.

The analysis conditions on a high-probability event controlling how often each label is observed.
Hölder’s inequality and random matrix theory convert the Rademacher-average bound into a spectral-norm calculation.
If some label is observed too often, with P = Ω(1), trace-norm regularization provides no benefit because the setting resembles fully observed labels.
When label observation is close to uniform, P = O(...), the analysis bounds the Rademacher average and consequently the excess risk.
For near-isotropic data with Σ ≫ σ1, the resulting bounds are superior; standard normal data gives σ1 = 1, Σ = d, and η = 1.
The uniform-convergence bounds are shown to be tight for general distributions, while isotropic distributions permit a tighter trace-norm bound.

C.2 Lower Bound for Frobenius Norm Regularization

The section constructs an isotropic, sub-Gaussian example showing that Frobenius norm regularization cannot achieve the trace-norm-style excess-risk bounds. The lower-bound argument uses a centered random-coordinate data distribution and partially observed labels.

Frobenius norm regularization cannot guarantee the same trace-norm-style bounds, even for isotropic distributions.
The construction uses an isotropic, sub-Gaussian data distribution and a loss function to establish a constant-probability lower bound.
For the constructed distribution, trace-norm regularization yields the improved excess-error guarantee predicted by Theorem 4.
The lower bound follows by showing that the relevant random matrix has large Frobenius norm with constant probability.

D.2 Detailed Results with Full Labels

The full-label experiments report results across multiple evaluation criteria. Separate tables cover top-1, top-3, top-5, Hamming-loss, and average-AUC performance.

Table 7 reports top-3 accuracy for fully observed labels.
Table 8 reports top-5 accuracy for fully observed labels.
Table 6 reports top-1 accuracy for fully observed labels.
Table 9 reports Hamming loss for fully observed labels.
Table 10 reports average AUC for fully observed labels.

D.3 Detailed Results with Missing Labels

The section reports comparisons under missing labels across several evaluation metrics and varying missing ratios and dimensionality-reduction rates. It also references fully observed-label comparisons across ranks and loss functions.

Missing-label results: Tables 11–15 report top-1, top-3, top-5, Hamming loss, and average AUC results for varying missing ratios and dimension-reduction rates.The missing-label evaluations are organized by metric across Tables 11–15.
Compared methods: The reported comparison includes LEML, BCS, CPLST, WSABIE, and k/L-based methods.These method names appear in the metric headings for top-k accuracy and average AUC.
Fully observed-label comparisons: Fully observed-label dimensionality-reduction comparisons evaluate various ranks using squared, logistic, squared-hinge, and weighted approximated-rank losses.SQ denotes squared loss, LR logistic loss, SH squared hinge loss, and WAR weighted approximated-rank loss.
Tabulated comparisons: Tables 10–15 provide the section’s tabulated comparisons for fully observed and missing-label settings.Tables 10 and 15 are identified as comparisons for dimensionality reduction on fully observed labels and missing labels, respectively.