PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse coding for multitask and transfer learning

Andreas Maurer, Massimiliano Pontil, Bernardino Romera-Paredes

arXiv:1209.0738v3cs.LGstat.ML

TL;DR

The paper asks whether sparse task representations can support multitask and transfer learning while allowing the shared dictionary to be learned. It jointly learns dictionaries and sparse codes, derives generalization bounds for both settings, and reports advantages over competing methods in experiments.

  • Problem

    The paper studies multitask and transfer learning when task predictors may share a sparse representation in a learnable dictionary on a high- or infinite-dimensional space.

  • Method

    The method jointly learns a K-dimensional dictionary and ℓ1-constrained task codes, with predictors represented by dictionary atoms in a Hilbert space.

  • Results

    Theoretical bounds cover multitask learning and learning to learn, while experiments indicate that sparse coding outperforms independent task learning and competing multitask methods.

  • Takeaways & Limitations

    Sparse coding is presented as a promising approach to multitask learning that can produce significant improvements over competing methods.

  • Takeaways & Limitations

    In learning to learn, increasing the number of training tasks reduces the risk of being misled, whereas increasing examples per task does not help.

Abstract

from arXiv · show

We investigate the use of sparse coding and dictionary learning in the context of multitask and transfer learning. The central assumption of our learning method is that the tasks parameters are well approximated by sparse linear combinations of the atoms of a dictionary on a high or infinite dimensional space. This assumption, together with the large quantity of available data in the multitask and transfer learning settings, allows a principled choice of the dictionary. We provide bounds on the generalization error of this approach, for both settings. Numerical experiments on one synthetic and two real datasets show the advantage of our method over single task learning, a previous method based on orthogonal and dense representation of the tasks and a related method learning task grouping.

1. Introduction

The paper applies sparse coding and dictionary learning to multitask learning and learning to learn, choosing a shared dictionary when task predictors have sparse representations. It provides theoretical and experimental support for this approach in both settings.

  • 1. Introduction: The method represents task predictors as sparse linear combinations of dictionary atoms in high- or infinite-dimensional spaces.The dictionary is learned from many tasks and then used either on those tasks or on new tasks from the same environment.
  • 1. Introduction: Many tasks provide enough data to estimate a useful shared dictionary while retaining sparse-coding benefits for individual tasks.
  • 1. Introduction: The analysis covers both multitask reuse of the learned representation and transfer to new tasks from the same environment.
  • 1. Introduction: The work combines sparse coding, multitask learning, and learning to learn within a unified approach.
  • 1. Introduction: The approach extends to Hilbert spaces, allowing nonlinear predictors through reproducing kernel Hilbert spaces.

2. Method

The proposed method jointly learns a bounded dictionary and sparse task codes by minimizing empirical loss across tasks in a Hilbert space. Its sparsity assumption is encoded through an ℓ1 constraint on each code vector.

  • 2. Method: The method studies predictors in a finite- or infinite-dimensional Hilbert space and fixes a dictionary size K.
  • 2. Method: DK contains K-dimensional dictionaries represented as linear maps from R^K to H, with each atom having norm at most 1.The dictionary dimension K acts as a regularization parameter.
  • 2. Method: Cα constrains each code vector γ in R^K by ∥γ∥1 ≤ α, implementing the method’s sparsity assumption.The parameter α is the second regularization parameter.
  • 2. Method: The training dataset contains T learning tasks, each represented by m input-label pairs.
  • 2. Method: Under a noiseless model with a true dictionary and bounded code norms, the objective can attain zero when the chosen dimensions and sparsity bounds are sufficiently large.
  • 2. Method: The objective minimizes the average loss over tasks and examples while jointly selecting the dictionary and task codes.The implementation seeks minimizing dictionary and code vectors, but exact minimization is not guaranteed because the problem is non-convex.

3. Learning bounds

The paper derives learning bounds for sparse dictionary-based multitask and transfer learning, identifying when shared sparse structure improves generalization and when it does not. The analysis also connects the method to sparse coding and characterizes task-clustering and sample-size effects.

  • Scope: The bounds analyze method (1) in both multitask learning and learning-to-learn settings, including a special sparse-coding case.The method learns a dictionary and task-specific coefficient vectors under sparse representations.
  • Multitask learning: When data are high-dimensional and T is large enough, the bound can yield a significant advantage over learning tasks independently.For uniform data on the unit sphere with m ≪ d, S∞(X) ≈ 1/m, producing a term of order ln K/m.
  • Multitask learning: For essentially one-dimensional data, S∞(X) = S1(X), making the bound worse by a factor of ln K than standard independent-task bounds.The passage attributes this to the limited potential benefit of multitask learning in low-dimensional data.
  • Multitask learning: Overestimating the true dictionary size K* can be offset by proportionally more tasks, while the required sample size changes only as m → (ln K*/ln K)m.Under the noiseless generative model, the minimum in (1) remains zero when K ≥ K* and α ≥ α*.
  • Multitask learning: Concatenating two unrelated task groups preserves the generative model, and with correct parameters the total excess risk increases only on the order of 1/√m, independent of K.The method is reported to find clusters of mutually related tasks.
  • Comparison: Compared with subspace learning, the proposed method is favored for large K when there are correspondingly many tasks and the task coefficients are sparse.Subspace learning can outperform it when K is small, K < m, and the coefficient vector uses the entire dictionary span.
  • Learning to learn: In learning to learn, increasing the number of training tasks reduces the risk of being misled by their draw, whereas increasing within-task sample size does not.The transfer-learning bound contains a term of order 1/√(mT), reflecting this environment-sampling effect.
  • Connection to sparse coding: In the m → ∞ noiseless limit, the transfer-learning result improves on the earlier sparse-coding bound by avoiding its additional term of the stated order.The paper assumes tasks are drawn from a measure on the unit ball but does not require them to be sparse combinations of a dictionary in this special-case analysis.

4. Experiments

The experiments evaluate SC-MTL against independent and multitask baselines in synthetic and real multitask or transfer settings. Results show strong performance, with sensitivity to dictionary size and sparsity, and an advantage on optical-character tasks with missing pixels.

  • Experimental design: SC-MTL is compared with ridge regression, MTFL, GO-MTL, and sparse coding across synthetic and two real datasets.The experiments assess both multitask learning and learning to learn, including parameter-sensitivity analyses.
  • Synthetic experiment: Synthetic tasks use sparse combinations of randomly sampled dictionary atoms, with noisy sphere-valued inputs and linear responses.The setup varies dictionary size, dimension, sparsity, code norm, noise, per-task sample size, and number of training tasks.
  • Synthetic experiment: SC-MTL outperforms the remaining approaches as the number of training tasks increases in the first synthetic experiment.This experiment fixes K = 10, d = 20, s = 2, α = 10, m = 10, and σ = 0.1.
  • Synthetic experiment: SC-MTL is not too sensitive to K′ when K′ ≥ K, still outperforming RR and MTFL at K′ = 4K, but degrades quickly when K′ < K.The observed behavior agrees qualitatively with the theoretical analysis.
  • Synthetic experiment: SC-MTL has greater advantage when sparsity is stronger, while GO-MTL and MTFL outperform it when s/K > 0.6.The comparison is reported for multitask and transfer error as a function of the sparsity ratio s/K.
  • Learning to learn optical character recognition: On NIST transfer tasks, the protocol trains on 190 pairwise tasks, tunes on 45 validation tasks, and evaluates on 45 disjoint target tasks.The target tasks use ten characters selected from those not assigned to training or validation.
  • Sparse coding of images with missing pixels: On Binary Alphadigits, SC-MTL shows an advantage over trace norm regularization for transfer learning, while ridge regression performs significantly worse.The comparison uses 100 new images and includes sparse coding with all pixels known as a reference.
  • Sparse coding of images with missing pixels: SC-MTL dictionaries learned from images with 25% missing pixels are compared with sparse-coding dictionaries learned from complete images.The analysis assumes ten underlying atoms, one for each digit.

5. Summary

The paper applies sparse coding to multitask learning and learning to learn, supporting the approach with Hilbert-space bounds and experiments. It reports advantages over independent task learning and dense task representations, while identifying extensions to structured sparsity and nonlinear dictionaries.

  • Learning bounds justify sparse coding for multitask learning and learning to learn, with dependence on data-dependent measures of intrinsic dimensionality.The bounds hold in a Hilbert space setting.
  • Numerical simulations indicate significant improvements over independent task learning and dense representations of tasks.
  • Structured sparsity norms, including group Lasso, are proposed as future extensions for modeling tasks divided into groups.The corresponding code sets encourage sparse codes using only a few groups.
  • Nonlinear dictionary learning with functions in a reproducing kernel Hilbert space is identified as another natural extension.

Appendix

The appendix presents the proofs of Theorems 1 and 2 and introduces the notation and auxiliary results needed for them.

  • The appendix begins by introducing notation and auxiliary results before presenting proofs of Theorems 1 and 2.

A. Notation and tools

This section establishes the mathematical setting, sample notation, and code-vector constraint used throughout the analysis. It works in a finite- or infinite-dimensional Hilbert space and defines multisamples across tasks.

  • The analysis uses a finite- or infinite-dimensional Hilbert space H with an inner product and norm.The operator norm is defined for bounded linear operators on H.
  • A sample consists of input-label pairs from the unit ball of H and the real numbers, while a multisample collects samples across T tasks.
  • Vectors in R^K use γ or β notation, with the Euclidean and ℓ1 norms defined in that space.

A.1. Covariances

The section defines covariance-based quantities for multisamples and relates them to the data’s effective dimensionality. Their ratio compares total covariance trace with the largest-eigenvalue scale.

  • For each task sample x, the section introduces an empirical covariance operator and uses it to define two multisample quantities.
  • S1 is bounded by 1 when all data points lie in the unit ball, and it equals the trace of the total covariance.
  • S∞ is at least the largest eigenvalue of the total covariance, and S∞ ≤ S1, with equality only when all task data are one-dimensional.
  • The ratio S1(X) / S∞(X) serves as a crude measure of effective dimensionality and can be large for high-dimensional task distributions.

A.2. Concentration inequalities

This section introduces coordinate replacement notation and sets up the bounded-difference concentration result for independent variables.

  • The notation x_k←y denotes replacing the k-th coordinate of x with y.The resulting object is (x_1, …, x_{k−1}, y, x_{k+1}, …, x_n).
  • The bounded difference inequality is presented as the concentration tool used in the subsequent theorem.The text attributes part (i) to McDiarmid (1998) and gives a proof of part (ii) in Maurer (2006).
  • Theorem 3 considers a function F mapping X^n to the real numbers and defines quantities A and B.
  • The theorem assumes independent X-valued random variables X=(X_1,…,X_n) and an independent identically distributed copy X′.It states a concentration result for any s>0.

A.3. Rademacher and Gaussian averages

This section defines Rademacher and Gaussian averages and records concentration and comparison results used to control function-class complexity.

  • Rademacher variables are independent uniform random variables on {−1,1}, while orthogaussian variables are independent standard normal variables.The notation σ is reserved for Rademacher variables and ζ for standard normal variables.
  • Rademacher and Gaussian averages are defined for subsets of R^n to support complexity bounds for function classes.The section cites standard learning-theory treatments and states that these concepts are useful for learning theory.
  • For a function class F evaluated on a sample x, the induced set F(x) consists of the vectors of function values on the sample points.This set is a subset of R^n.
  • The empirical Rademacher and Gaussian complexities of F on x are denoted R(F(x)) and G(F(x)).
  • Theorem 4 bounds an expected supremum quantity Φ by the expected empirical Rademacher average.For product measure μ, it states E_x∼μ[Φ(x)] ≤ E_x∼μ R(F(x)).
  • Theorem 5 and Corollary 6 provide high-probability uniform bounds for [0,1]-valued function classes.Their proof applies bounded differences to Φ and to the Rademacher complexity, together with a union bound.
  • Lemma 7 transfers Rademacher-average bounds through coordinatewise Lipschitz functions.It applies when each ψ_i satisfies a common Lipschitz condition.
  • Gaussian averages can be used in place of Rademacher averages, and Slepian’s lemma compares suitable Gaussian processes.

B.1. Multitask learning

This section develops generalization bounds for the multitask dictionary-learning method by combining concentration, complexity estimates, and optimization over sparse task representations.

  • B.1. Multitask learning: The proof of Theorem 1 begins with Hoeffding’s inequality and a uniform bound on estimation error.
  • B.1. Multitask learning: Theorem 10 gives a high-probability bound for T multitask distributions over H×R with fixed dictionary size K.The result is obtained from the preceding concentration and complexity estimates.
  • B.1. Multitask learning: The proof uses bounded differences, Rademacher and Gaussian complexity bounds, union bounds, and extreme-point arguments.Gaussian-process comparisons are introduced to bound the dictionary-dependent term.
  • B.1. Multitask learning: The analysis controls dictionary-task combinations under per-task coefficient constraints ∥γ_t∥_1≤1 and dictionary atom constraints ∥D e_k∥≤1.The bound ∥Dγ_t∥≤∥γ_t∥_1≤1 follows from these constraints.
  • B.1. Multitask learning: Replacing coefficient constraints or dictionary constraints changes the complexity analysis and yields alternative bounds.The text considers covering subsets of the ℓ2-ball and a Frobenius or Hilbert–Schmidt dictionary constraint.
  • B.1. Multitask learning: The excess-risk analysis compares the learned dictionary with an optimal dictionary and combines Hoeffding and proposition-based bounds.The component estimates are combined using a union bound.
  • B.1. Multitask learning: With a shared constraint P_t∥γ_t∥_1≤αT and retained atom constraints, the K factor in the second term disappears.The modified constraint is weaker than imposing ∥γ_t∥_1≤α for every task and can permit a smaller minimum.
  • B.1. Multitask learning: The transfer-learning proof decomposes the target into empirical-risk estimation and expected future-task empirical risk.The Lasso-like task algorithm is used to estimate task risks, while dictionary selection controls the future-task term.
Loading 1209.0738v3…