Source-linked AI summary
Multi-Label Prediction via Compressed Sensing
Daniel Hsu, Sham M. Kakade, John Langford, Tong Zhang
TL;DR
Large-output multi-label prediction is expensive when labels are numerous, even though expected label vectors may be sparse. The paper combines compressed sensing with output coding to predict compressed labels and reconstruct sparse outputs using logarithmically many subproblems, with robustness guarantees.
Problem
Multi-label prediction becomes prohibitively expensive with very large label spaces, despite the often sparse structure of E[y|x].
Method
The method applies compressed sensing to output coding, predicts compressed label vectors, and uses sparse reconstruction to recover uncompressed labels.
Results
The approach requires only logarithmically many predictions in the number of labels and provides regret-transform robustness guarantees.
Takeaways & Limitations
Relatively few compressed-label predictions can recover accurate sparse label vectors in the evaluated multi-label tasks.
Takeaways & Limitations
When E[y|x] is not exactly k-sparse, using m = O(k log d) can incur an additional sparsity-error penalty.
Abstract
from arXiv · showhide
We consider multi-label prediction problems with large output spaces under the assumption of output sparsity -- that the target (label) vectors have small support. We develop a general theory for a variant of the popular error correcting output code scheme, using ideas from compressed sensing for exploiting this sparsity. The method can be regarded as a simple reduction from multi-label regression problems to binary regression problems. We show that the number of subproblems need only be logarithmic in the total number of possible labels, making this approach radically more efficient than others. We also state and prove robustness guarantees for this method in the form of regret transform bounds (in general), and also provide a more detailed analysis for the linear prediction setting.
1 Introduction
The paper addresses large-output multi-label prediction by exploiting sparsity in E[y|x] through compressed sensing and output coding. It reduces prediction to logarithmically many subproblems while providing robustness guarantees.
- Large label spaces make one-against-all prediction prohibitively expensive when d reaches 10^3 or 10^4.
- Output sparsity concerns E[y|x], which can differ substantially from sparsity in the realized label vector y.
- O(k log d) measurements can recover a k-sparse E[y|x], motivating compressed sensing for high-dimensional multi-label prediction.
- The method applies compressed sensing to output coding, predicting whether labels belong to subsets or their complements before reconstructing labels.
- The efficient output coding method requires only logarithmically many predictions in the number of labels d.
- The paper provides general regret-transform robustness guarantees and a more detailed analysis for linear prediction.
2 Preliminaries
The problem is formalized as learning a predictor for a high-dimensional label vector under output sparsity, evaluated by expected squared error relative to E[y|x].
- The goal is to learn F: X → Y with low expected ℓ2^2 error relative to E[y|x].
- The setting assumes a very large output dimension d while E[y|x] has only a few non-zero entries for each input x.
- A vector is k-sparse when it has at most k non-zero entries.
3 Learning and Prediction
The method compresses labels, predicts their compressed representation, and reconstructs sparse original labels. Its guarantees require reconstruction to degrade gracefully with prediction error and nonsparsity.
- 3.1 Compressing Labels: A linear map A compresses d-dimensional labels into m-dimensional representations, where m ≤ d and ideally m ≪ d.
- 3.2 Predicting Sparse Labels: The learner predicts E[Ay|x] from compressed labels, then composes this predictor with a reconstruction algorithm R.
- 3.2 Predicting Sparse Labels: Reconstruction algorithms seek a sparse vector whose compressed representation closely approximates the predicted compressed labels.
- 3.2 Predicting Sparse Labels: A valid reconstruction algorithm returns an f(k)-sparse vector with error controlled by prediction error and sparsity error through regret factors C1 and C2.
- 3.2 Predicting Sparse Labels: The reconstruction guarantee must be agnostic to unknown output sparsity and measurement noise, excluding methods requiring users to provide a noise bound.
- 3.2 Predicting Sparse Labels: The required number of matrix rows may depend on k and d, with the next section targeting constructions close to optimal.
4 Algorithms
The section presents compression functions and reconstruction algorithms for exploiting output sparsity, with guarantees linking reconstruction quality to prediction performance. Random matrices require few measurements, while several greedy methods provide linear output sparsity under RIP or coherence conditions.
- Compression Functions: Random Gaussian, Bernoulli, and Hadamard-based matrices provide RIP constructions with m scaling logarithmically in ambient dimension d.The listed Gaussian construction uses m = O(k log(d/k)); the Hadamard construction uses m = O(k log^5 d), with constants depending on δ and success probability.
- Compression Functions: The mild dependence of m on d substantially reduces the number of learning problems required by the reduction.The paper identifies this as a significant saving after applying the compressed-sensing reduction.
- Compression Functions: Coherence-based reconstruction requires m = O(k^2 log d), a factor k more than the requirement for (k, δ)-RIP.The dependence on d remains small despite the additional factor k.
- Reconstruction Algorithms: Theorem 1 makes approximate sparse regression sufficient for valid reconstruction on RIP matrices, with explicit regret factors.The theorem applies when A has (k + f(k), δ)-RIP and the reconstruction algorithm returns an f(k)-sparse solution satisfying the stated approximation condition.
- Reconstruction Algorithms: OMP, FoBa, and CoSaMP are greedy reconstruction methods; FoBa and CoSaMP have linear output sparsity under RIP, while OMP has a coherence-based guarantee.FoBa uses backward steps, CoSaMP selects larger column sets per iteration, and OMP selects columns greedily to fit h.
5 Analysis
The analysis formalizes compressed-sensing output coding, proving general regret guarantees and showing that linear prediction preserves accuracy under suitable compression.
- 5.1 General Robustness Guarantees: The regret transform bounds reconstruction error by compressed-prediction error plus a sparsity-error penalty.The bound applies to any valid reconstruction algorithm and suitable sensing matrix family.
- 5.1 General Robustness Guarantees: Output coding asks whether a label belongs to a subset or its complement, then reconstructs labels from the resulting predictions.
- 5.1 General Robustness Guarantees: The reduction uses exponentially fewer subproblems than SECOC while attaining a guarantee within a constant factor of SECOC.
- 5.1 General Robustness Guarantees: When m = O(k log d) < d, the method incurs a sparsity penalty measuring how far E[y|x] is from k-sparse.For small ℓp norm with 0 ≤ p < 2, this penalty decreases polynomially in k ≈ m/log d.
- 5.2 Linear Prediction: For linear prediction, a perfect predictor E[y|x] = B⊤x induces a perfect compressed predictor H = BA⊤.
- 5.2 Linear Prediction: Theorem 4 shows that compression does not magnify linear-prediction errors much, yielding sample-complexity bounds polynomial in k but logarithmic in d.The Gaussian sensing construction provides the stated high-probability analysis, with analogous guarantees for Bernoulli matrices.
6 Proofs
The proofs establish reconstruction error bounds through sparse approximation, restricted-isometry and coherence arguments, and concentration bounds for random sensing matrices.
- 6.1 Reconstruction Guarantees: The reconstruction proof decomposes y into its best k-sparse approximation and residual, then bounds error using the sensing residual and residual norms.
- 6.2 Proof of Theorem 2: Coherence and restricted-isometry arguments bound interactions among sparse components and complete the reconstruction proof.
- 6.2 Proof of Theorem 2: The OMP analysis compares intermediate solutions and controls residual reduction through coherence-based inequalities.The proof derives a bound of 14∥h − Ay∥2 2 for an intermediate reconstruction error.
- 6.2 Proof of Theorem 2: The matrix A{1:2k} isolates the first 2k columns, matching the support restriction used to control the OMP error.
- 6.3 Linear Prediction Analysis: The random-matrix analysis diagonalizes the covariance of prediction errors and applies a Chernoff bound for weighted χ2 variables.
7 Experimental Validation
Experiments on image and text tagging show that compressed predictions can recover accurate sparse labels, with performance depending on the number of measurements and reconstruction algorithm.
- 7.1 Data: The evaluation used two large-label datasets: 68,000 images with 1,000 retained labels and 16,000 web pages with 983 labels.Images averaged about four labels, while web pages averaged 19 labels; each dataset used half training and half testing.
- 7.2 Output Sparsity: Around k = 10, sparsity-error decay exponents were 0.50 for images and 0.55 for text, indicating non-ideal sparsity at small k.
- 7.4 Results: At m = 300 and 400, precision-at-k was nearly the same as one-against-all using m = 1024.Performance improved as the number of induced subproblems increased.
- 7.4 Results: All reconstruction algorithms matched or outperformed the baseline on mean-squared error except when m = 100.For small m, CoSaMP, Lasso, and correlation decoding performed better than OMP and FoBa because they can select correlated columns.
- 7.4 Results: Precision-at-k results were similar, but correlated columns did not necessarily help because they may not correspond to accurate label coordinates.
- 7.4 Results: The experiments demonstrate feasibility and robustness: relatively few compressed-label predictions sufficed to recover accurate sparse label vectors.