Source-linked AI summary
Supervised Dictionary Learning
Julien Mairal, Francis Bach, Jean Ponce, Guillermo Sapiro, Andrew Zisserman
TL;DR
Sparse models have increasingly moved beyond reconstruction, but discriminative representations for multiple signal classes remained an open need. This paper jointly learns a shared dictionary and class-decision functions, improving digit classification and showing bilinear modeling is necessary for some texture tasks.
Problem
The paper addresses the need for discriminative sparse representations that model signals from multiple classes rather than only reconstructing them.
Method
The method jointly learns a shared dictionary and multiple linear or bilinear decision functions in a generative/discriminative sparse representation model.
Results
Discriminative dictionary learning dramatically improves basic linear SVM performance on digits, while bilinear modeling is necessary for some texture-classification cases.
Takeaways & Limitations
The framework provides an effective approach for learning shared dictionaries with multiple decision functions for image classification.
Takeaways & Limitations
The linear probabilistic model assumes Laplace priors for sparse coefficients, Gaussian signal generation, and independence across signal-coefficient-label triplets.
Abstract
from arXiv · showhide
It is now well established that sparse signal models are well suited to restoration tasks and can effectively be learned from audio, image, and video data. Recent research has been aimed at learning discriminative sparse models instead of purely reconstructive ones. This paper proposes a new step in that direction, with a novel sparse representation for signals belonging to different classes in terms of a shared dictionary and multiple class-decision functions. The linear variant of the proposed model admits a simple probabilistic interpretation, while its most general variant admits an interpretation in terms of kernels. An optimization framework for learning all the components of the proposed model is presented, along with experimental results on standard handwritten digit and texture classification tasks.
Apprentissage de dictionnaires supervis´e
Le travail propose un cadre supervisé pour représenter des signaux de classes différentes à l’aide d’un dictionnaire partagé et de multiples fonctions de décision. Il s’inscrit dans le passage de modèles parcimonieux reconstructifs vers des représentations discriminantes.
- Les représentations parcimonieuses sont adaptées aux tâches de restauration d’images, de sons et de vidéos.
- Des travaux récents cherchent à apprendre des représentations discriminantes plutôt que seulement reconstructives.
- Le cadre proposé apprend simultanément un dictionnaire partagé et de multiples fonctions de décision pour des signaux appartenant à plusieurs classes.
1 Introduction
Sparse and overcomplete image models represent signals as combinations of a few atoms from a learned dictionary, enabling strong performance in low-level image processing such as denoising.
- Related work: Learned sparse dictionaries represent signals with a few atoms and have achieved state-of-the-art results on low-level image-processing tasks, including denoising.These models were introduced for modeling spatial receptive fields of simple cells in the human visual system and are well adapted to natural images.
2 Supervised dictionary learning
The proposed supervised dictionary-learning model combines a shared sparse representation with class-specific decision functions, incorporating classification into sparse coding. Its generative and discriminative objectives learn the dictionary and model parameters jointly, with a trade-off between reconstruction and discrimination.
- Model formulation: Signals from p classes use one shared dictionary D and p decision functions acting on each signal and its sparse code α.Each decision function should be positive for its class and negative otherwise; D and the model parameters θ are jointly learned.
- Model formulation: The model includes linear coefficient-based decision functions and richer bilinear functions gi(x, α, θ) = xT Wiα + bi.The bilinear variant has more parameters and interprets Wi as an input-to-coefficient encoding filter.
- Supervised sparse coding: Supervised sparse coding explicitly combines the classical reconstructive term with a softmax discriminative cost, and its solution directly supports classification.The softmax costs are differentiable multiclass versions of logistic functions with properties similar to the SVM hinge loss.
- Model advantages: Compared with one dictionary per class, the shared dictionary allows multiple classes to share features while using sparse coefficients for classification.The learned representations are optimized for classification while retaining the sparse-representation framework.
- Learning objectives: The SDL-G objective learns D and θ by minimizing supervised sparse-coding costs with ℓ2 regularization and bounded dictionary-column norms.The column constraint prevents scaling D and α from transferring energy in a way that would overcome the sparsity penalty.
- Learning objectives: The SDL-D objective mixes generative reconstruction and discriminative classification, with µ controlling their trade-off.The discriminative component also encourages low costs for the correct class relative to the other classes through the softmax function.
3 Interpreting the model
The zero-bias linear model admits a probabilistic interpretation with Gaussian dictionary and classifier parameters, Laplace coefficient priors, and conditionally generated signals and labels. Generative and discriminative training correspond to MAP formulations, while the bilinear model is interpreted through product kernels.
- Linear probabilistic interpretation: The zero-bias linear model uses a shared dictionary and classifier parameters, Gaussian priors on W, Laplace priors on coefficients α_j, and Gaussian signal generation conditioned on D and α_j.The model also treats dictionary atoms as independent and signals as conditionally generated from their sparse reconstructions.
- Linear probabilistic interpretation: Labels are generated from W and α_j, and the triplets (α_j, x_j, y_j) are independent given D and W.This completes the graphical-model interpretation of training and classification for the linear formulation.
- Training interpretations: Generative training maximizes the joint likelihood of training signals and labels, and under MAP approximations is equivalent to the paper’s formulation in Eq. (5).The paper notes that the equivalence is established with details omitted.
- Training interpretations: Discriminative training maximizes label likelihood with respect to D and W, while the mixed formulation trades off generative and discriminative objectives.Generative components can add robustness to noise and occlusions in discriminative frameworks.
- Bilinear kernel interpretation: The bilinear model lacks a straightforward probabilistic interpretation but corresponds to logistic regression with a product of linear kernels on coefficients and input signals.The kernel is K(x_1, x_2) = α_1^T α_2 x_1^T x_2.
- Bilinear kernel interpretation: The signal-based kernel K generally performs similarly to the residual-based Fisher kernel K′ and often performs better with few training samples or noisy data.K′ uses decomposition residuals, whereas K substitutes the input signals for those residuals.
4 Optimization procedure
The optimization alternates supervised sparse coding with supervised dictionary updates, using block coordinate descent for the generative case and a continuation strategy for the discriminative model. Sparse coding is solved with fixed-point continuation, while dictionary and parameter updates use projected gradient descent to obtain a local minimum.
- Block coordinate descent: Block coordinate descent alternates supervised sparse coding over α with supervised updates of D and θ.The sparse-coding step fixes D and θ, whereas the dictionary-update step fixes the coefficients αj.
- Discriminative optimization: The discriminative update is generally nonconvex and may not decrease the first term of Eq. (6).A continuation method is used to reach a local minimum for this difficult problem.
- Continuation strategy: The algorithm gradually increases µ from the generative case to the discriminative one.It initializes D with a random Gaussian matrix and θ to zero, then loops over an increasing sequence 0 ≤ µ1 ≤ µ2 ≤ . . . ≤ µm ≤ 1.
- Supervised sparse coding: Fixed-point continuation solves supervised sparse coding because the problem is convex with an ℓ1 penalty when D and θ are fixed.The method is described as simple, efficient, and well adapted to the supervised sparse-coding problem.
- Dictionary and parameter updates: Projected gradient descent updates D and θ, producing a local minimum because the problem is generally nonconvex except when µ is close to 0.The paper reports that this local minimum has experimentally been found good enough for the formulation.
- Implementation details: Partial derivatives for bilinear decision functions are omitted because of space limitations.The omitted model uses gi(x, α, θ) = xT Wiα + bi.
5 Experimental validation
The experiments compare reconstructive and discriminative dictionary-learning variants with linear and bilinear decision functions. Evaluation covers handwritten-digit recognition, dictionary-only discriminativeness, and texture classification.
- Parameter selection: Parameter selection uses κ = 0.15 for unit-norm inputs, with smaller dictionaries such as k = 64 or k = 32 favored for discriminative tasks.The paper notes k = 256 as typical for reconstructive tasks but warns that larger parameter counts may promote overfitting in discriminative tasks.
- Handwritten digits: Experiments use MNIST and USPS handwritten-digit datasets with pairwise binary classifiers, one for each digit pair.MNIST contains 60,000 training and 10,000 test images; USPS contains 7,291 training and 2,007 test images.
- Dictionary discriminativeness: A USPS experiment tests whether SDL-D L dictionaries are intrinsically discriminative by discarding θ and classifying sparse-reconstruction coefficients with a linear SVM.The setup trains 10 one-versus-all classifiers, producing 10 dictionaries D and 10 parameter sets θ, then evaluates the dictionaries without θ.
- Handwritten digits: In digit recognition, the BL bilinear framework did not outperform L, plausibly because the task was simple enough for a linear model.The paper explicitly attributes the result to the view that a linear model is rich enough for the digit task.
- Texture classification: Texture experiments use two Brodatz textures, 12 × 12 patches, k = 64, and κ = 0.15 to compare all methods, including BL.The study is designed to determine when the bilinear framework is worth using.
6 Conclusion
The paper introduces discriminative supervised dictionary learning that uses sparse signal decompositions for image classification, learning a shared dictionary with multiple linear or bilinear decision functions. Future work will adapt the framework to shift-invariant models.
- The proposed approach exploits sparse signal decompositions for image classification while jointly learning a shared dictionary and multiple linear or bilinear decision functions.
- Future work will extend the framework to shift-invariant models commonly used in image processing but not readily generalized to sparse dictionaries.