PaperlayerView exact revision on arXiv

Source-linked AI summary

Jointly Learning Structured Analysis Discriminative Dictionary and Analysis Multiclass Classifier

Zhao Zhang, Weiming Jiang, Jie Qin, Li Zhang, Fanzhang Li, Min Zhang, Shuicheng Yan

arXiv:1905.11543v1cs.CV

TL;DR

The paper addresses the cost and separation of sparse coding and classification in dictionary-learning methods. It proposes ADDL, which jointly learns structured dictionaries, projected sparse representations, and an analysis classifier using an l2,1-norm constraint. Experiments on real image databases report superior performance and time efficiency compared with several dictionary-learning methods.

  • Problem

    Existing dictionary-learning approaches can require costly l0/l1-based coding and an extra sparse reconstruction step for each test sample.

  • Method

    ADDL jointly learns class-structured dictionaries, projective sparse representations, and an analysis linear classifier, using l2,1-regularized coefficients and analytical incoherence.

  • Results

    Experiments on several real image databases demonstrate superior performance and time efficiency compared with several dictionary-learning methods.

  • Takeaways & Limitations

    The unified analysis mechanism avoids extra sparse reconstruction for new test data while jointly considering representation and classification.

Abstract

from arXiv · show

In this paper, we propose an analysis mechanism based structured Analysis Discriminative Dictionary Learning (ADDL) framework. ADDL seamlessly integrates the analysis discriminative dictionary learning, analysis representation and analysis classifier training into a unified model. The applied analysis mechanism can make sure that the learnt dictionaries, representations and linear classifiers over different classes are independent and discriminating as much as possible. The dictionary is obtained by minimizing a reconstruction error and an analytical incoherence promoting term that encourages the sub-dictionaries associated with different classes to be independent. To obtain the representation coefficients, ADDL imposes a sparse l2,1-norm constraint on the coding coefficients instead of using l0 or l1-norm, since the l0 or l1-norm constraint applied in most existing DL criteria makes the training phase time consuming. The codes-extraction projection that bridges data with the sparse codes by extracting special features from the given samples is calculated via minimizing a sparse codes approximation term. Then we compute a linear classifier based on the approximated sparse codes by an analysis mechanism to simultaneously consider the classification and representation powers. Thus, the classification approach of our model is very efficient, because it can avoid the extra time-consuming sparse reconstruction process with trained dictionary for each new test data as most existing DL algorithms. Simulations on real image databases demonstrate that our ADDL model can obtain superior performance over other state-of-the-arts.

I. INTRODUCTION

The paper proposes ADDL, an analysis-based framework that jointly learns structured dictionaries, sparse representations, and classifiers to improve discrimination while reducing coding and classification cost.

  • I. INTRODUCTION: Existing dictionary-learning methods commonly use l0 or l1 sparsity constraints and separate coding from classifier training, making learning and prediction time-consuming.Test samples often require an additional sparse reconstruction step before classification.
  • I. INTRODUCTION: ADDL unifies analysis discriminative dictionary learning, projective sparse representation, and analysis classifier training in one model.The framework learns structured dictionaries, projective sparse codes, and linear classifiers jointly.
  • I. INTRODUCTION: ADDL uses an l2,1-norm constraint to obtain row-sparse coefficients without the costly l0/l1 constraints.The analysis mechanism predicts coefficients through learned projections rather than requiring sparse reconstruction for every test sample.
  • I. INTRODUCTION: The framework learns class-specific sub-dictionaries, sub-projections, and sub-classifiers designed to be independent and discriminating across classes.For class l, cross-class reconstructions and classifier responses are encouraged to be nearly null and sparse.
  • I. INTRODUCTION: The analysis projection bridges data and sparse codes, whose approximations are then used to train the analysis classifier.This design replaces direct residual-based classification with classification over projected code estimates.

III. STRUCTURED ANALYSIS DISCRIMINATIVE DICTIONARY LEARNING (ADDL)

ADDL jointly learns structured discriminative dictionaries, projective sparse codes, and an analysis multiclass classifier. Its analysis mechanism promotes class separation while using efficient sparse-code extraction and direct classification.

  • A. The Objective Function: ADDL jointly learns a structured dictionary, projective sparse coding coefficients, and an analysis linear multiclass classifier.The framework combines dictionary learning, representation, and classifier training in one model.
  • 2) Analysis sparse codes extraction function: ADDL uses an l2,1-norm regularizer to produce row-sparse coefficients, replacing the more costly l0- or l1-norm constraints used by many existing models.The paper motivates this choice by the efficiency of solving the l2,1-norm problem.
  • 1) Analysis incoherence promoting function: The dictionary objective combines reconstruction with an incoherence term that discourages samples from being represented by sub-dictionaries of other classes.For class l, the complementary representation D_l S̄_l is encouraged to remain small.
  • 2) Analysis sparse codes extraction function: The analysis projection P bridges data and sparse codes by approximating S_l with P_l X_l while suppressing projections of samples from other classes.The model explicitly seeks P_l X_j ≈ 0 for j ≠ l.
  • 3) Analysis multiclass classifier training function: The classifier is trained to approximate class labels from P_l X_l while producing nearly null outputs for samples from other classes.This design jointly considers representation and classification through the analysis mechanism.
  • 2) Analysis sparse codes extraction function: On ORL, ADDL produced nearly block-diagonal sparse codes and more accurate soft labels than the version without the analysis mechanism.The comparison uses the parameter setting α=0.1, τ=0.1, and λ=0.1.

B. Optimization

ADDL is optimized by alternating updates over its variables, with closed-form or simplified subproblems for the sparse codes, projection, classifier, and dictionary. Regularization and constraints are used to stabilize the computations.

  • B. Optimization: The optimization initializes D, P, and W randomly with unit F-norm and alternates minimization steps over the model variables.The procedure is summarized as an alternating optimization algorithm.
  • B. Optimization: With D and P fixed, S is updated using an l2,1-norm formulation and Λ is refreshed from the row norms of S.The update uses Λ as a diagonal reweighting matrix, with Λ_ii = 1/(2||S_i||_2).
  • B. Optimization: With S and W fixed, P is optimized from a reduced problem whose closed-form solution uses γI to avoid singularity in inverse computations.The paper sets γ=10^-4 and adds γI because XX^T may be singular.
  • B. Optimization: With P fixed, W is updated by solving its reduced classifier-training formulation and setting the derivative with respect to W to zero.The resulting update is presented as a closed-form expression.
  • B. Optimization: With S fixed, each sub-dictionary D_l is updated through a constrained problem using a dictionary-atom norm bound for computational stability.The derivation uses a Lagrange dual function and may discard the multiplier matrix to reduce complexity.
  • B. Optimization: The dictionary update adds γI to S_l S_l^T + αS_l S_l^T to avoid singularity and stabilize inversion.The paper notes that invertibility is not guaranteed before this regularization.

C. Convergence Analysis

The paper analyzes ADDL as an alternate convex search procedure. Under the stated boundedness, continuity, solvability, and uniqueness conditions, it establishes monotonic convergence and properties of accumulation points.

  • C. Convergence Analysis: ADDL is formulated as an alternate convex search algorithm for a bi-convex optimization problem over its variable blocks.The objective has a lower bound of 0, and the alternating steps optimize the corresponding variable groups.
  • C. Convergence Analysis: The ADDL sequence converges monotonically under the alternate convex search theorem applied to its solvable variable updates.The proof uses the bi-convex structure and the objective's lower bound.
  • C. Convergence Analysis: The generated sequence has at least one accumulation point, and all accumulation points are local optima with the same objective value.This conclusion follows from boundedness and uniqueness of the S and W subproblem solutions when τ>0.
  • C. Convergence Analysis: If P and D have unique solutions, the paper derives an additional convergence conclusion for the ADDL sequence.The argument invokes the corresponding uniqueness condition in the alternate convex search theorem.

D. Classification Approach

For a new sample, ADDL obtains projective sparse codes by applying P and then computes soft labels by applying W. The largest soft-label entry determines the predicted class.

  • D. Classification Approach: A new test sample x_new is embedded onto P to obtain its projective sparse codes without sparse reconstruction over the learned dictionary.The resulting code is P x_new.
  • D. Classification Approach: The classifier computes the soft-label vector f_new = W P x_new from the projected sample representation.The vector has c entries corresponding to the classes.
  • D. Classification Approach: The hard class label is assigned by selecting the index of the largest entry in f_new.The rule is arg max_i f_new_i.

IV. DISCUSSION: RELATIONSHIP ANALYSIS

The paper positions ADDL in relation to several closely related dictionary-learning algorithms.

  • ADDL is explicitly compared with other closely related dictionary-learning algorithms.

A. Connection to the DPL algorithm [3]

ADDL generalizes DPL by adding sparse coding regularization within its analysis-based formulation.

  • A. Connection to the DPL algorithm [3]: DPL is recovered as a special case of ADDL when the sparse constraint is ignored.The comparison is stated for the objective under the ideal sparse-code condition.

B. Connection to the DLSI algorithm [15]

ADDL relates to DLSI through its treatment of inter-class dictionary independence and sparse coding.

  • B. Connection to the DLSI algorithm [15]: ADDL encourages independence between sub-dictionaries by minimizing reconstruction of other-class samples through each class-specific sub-dictionary.This differs from DLSI's direct incoherence-promoting formulation.
  • B. Connection to the DLSI algorithm [15]: ADDL and DLSI both seek class-discriminative representations under ideal conditions where sub-dictionaries are independent.
  • B. Connection to the DLSI algorithm [15]: DLSI is a special case of ADDL when the analysis codes-extraction condition is imposed and l1-norm regularization replaces ADDL's sparse l2,1-norm constraint.

D. Connection to the JDL algorithm [36]

This block describes ADDL's relationship to JDL and the experimental setup and convergence evaluation used for ADDL.

  • D. Connection to the JDL algorithm [36]: JDL promotes small within-class and large between-class coding scatter, whereas ADDL minimizes an analysis sparse-codes extraction term.
  • D. Connection to the JDL algorithm [36]: JDL is treated as a special example of the ADDL formulation.JDL uses shared and class-specific dictionaries, while ADDL obtains discriminative projective sparse codes through an analysis codes-extraction term.
  • V. SIMULATION RESULTS AND ANALYSIS: The experiments evaluate ADDL on four face databases, one object database, and one scene-category database using repeated random train-test splits.Accuracy is averaged over 10 runs for fair comparison with existing dictionary-learning methods.
  • A. Convergence Analysis: The convergence experiment uses six datasets and examines objective-function values across iterations under dataset-specific training selections.
  • A. Convergence Analysis: The objective value is non-increasing and converges to a fixed value, typically within fewer than 20 iterations.

B. Parameter Selection Analysis

ADDL performs well across a broad range of parameter settings, while ablations show that all three model terms contribute to classification. Face-recognition experiments further report competitive performance across dictionary sizes and datasets.

  • Parameter sensitivity analysis: ADDL performs well across a wide range of parameter selections, indicating that its recognition performance is insensitive to the tested model parameters.The analysis varies pairs among α, λ, and τ while fixing the third parameter; accuracies above 97.5% are highlighted across the tested ranges.
  • Ablation analysis: Removing the analysis sparse-code extraction term reduces accuracy to 1%, while removing either remaining term is less harmful but still inferior to the complete model.The sparse-code extraction term bridges reconstruction and classifier training, and the authors conclude that all three constraints are important.
  • Face recognition: On MIT CBCL, ADDL’s advantage is more pronounced with limited training data, exceeding competitors by more than 1.5% when using two images per category.The comparison is based on the reported recognition results for the MIT CBCL face database.
  • Face recognition: ADDL maintains higher CMU PIE recognition accuracy than its competitors even with relatively small dictionaries and is also superior in the reported ROC comparisons.The dictionary-size experiment uses K=340, 680, 1020, 1360, 1700, and 2040; ROC curves use ten training samples per class.
  • Face recognition: ADDL outperforms competing methods across all tested MIT CBCL dictionary sizes, with recognition rates increasing as the number of atoms grows.The experiment evaluates K=20, 30, 40, 50, and 60 using six training images per person.
  • Face recognition: On UMIST, ADDL outperforms competing methods and remains superior when the dictionary contains only two atoms per category.The reported UMIST experiment uses α=0.01, τ=0.001, and λ=0.001.

D. Object Recognition on ETH80 database

ADDL is evaluated on the ETH80 object database spanning eight object categories and reports better classification performance than competing methods. Its advantage over the other remaining methods exceeds 6%, while DPL is described as comparable.

  • Object recognition: ADDL achieves better average classification performance than the competing methods on the ETH80 object database.ETH80 contains 3,280 images from 80 objects across eight categories, each with ten subcategories and 41 viewpoints.
  • Object recognition: ADDL outperforms the other remaining methods by more than 6%, although DPL delivers a comparable result.The paper also reports several ETH80 classes reaching 100% classification accuracy.
  • Object recognition: Examples from eight ETH80 classes with 100% classification accuracy are shown in the accompanying figure.The figure presents image examples from classes with high classification accuracy.

E. Scene Category Recognition

On the fifteen-scene-category database, ADDL achieves higher recognition accuracy than competing models under the reported settings while also reducing computational cost. Its analytical incoherence term produces independent inter-class sub-dictionaries, and the method remains substantially faster in training and testing.

  • Recognition performance: ADDL obtains higher recognition accuracies than competing models on the fifteen-scene-category database, including when trained with 50 images per class.The section also reports individual-class recognition examples, with most confusion occurring between visually similar categories.
  • Mutual coherence: ADDL and DLSI achieve the smallest inter-class coherence values, indicating the most independent learned sub-dictionaries among the compared methods.The reported coherence comparison attributes this behavior to explicitly accounting for sub-dictionary independence.
  • Computational efficiency: ADDL is more than 20 times faster than KSVD and D-KSVD and about 100 times faster than LC-KSVD2 during training.The comparison uses training and testing time across CMU PIE, AR, and ETH80 databases.
  • Computational efficiency: In testing, ADDL is about 20 times faster than D-KSVD and LC-KSVD2 and about 25 times faster than KSVD.The competing methods spend substantial time on sparse coding and extra sparse reconstruction for each new test sample.

H. Comparison of l2,1-norm and l1-norm Regularizations

The experiments compare l2,1- and l1-norm regularization within ADDL and examine performance under increasing image noise. ADDL generally maintains higher accuracy than competing methods in noisy settings, while the paper frames its l2,1-norm design as a response to the computational cost of l0/l1 regularization.

  • Robustness to noise: Classification accuracy decreases for every evaluated method as the added-noise Variance increases.The reported noisy-image experiments compare methods across the two real image databases.
  • Robustness to noise: ADDL delivers higher classification accuracies than other methods in most tested noisy cases as image variance increases.The experiments use Gaussian noise with Variance values of 200, 400, 600, 800, and 1000 on MIT CBCL and UMIST.
  • Regularization comparison: ADDL uses sparse l2,1-norm regularization for coding coefficients rather than the costly l0- or l1-norm regularization used in the motivating comparison.The design is intended to reduce computational cost during training and testing while retaining discriminative dictionary learning.
  • Scope and conclusion: The paper concludes that ADDL performs well in both recognition performance and time efficiency on several widely used real image databases.The conclusion also identifies noise, unfavorable features, and corruptions in original data as factors that may reduce later representation and classification performance.
Loading 1905.11543v1…