2.2.2.1 Sparse Coding for Feature Extraction

In [18], the authors suggest that the spectral signatures of pixels belonging to the same class are assumed to approximately lie in a low-dimensional subspace. Pixel can be compactly represented by only a few sparse coefficients (sparse code). We adopt the sparse code as the input features, since extensive literature has examined the outstanding effect of SRC for a more discriminative and robust classification [17].

We assume that all the data samples $\mathbf{X}=[{\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_n]$, ${\mathbf{x}}_i\in R^{m\times 1}$, $i=1,2,\dots ,n$, are encoded into their corresponding sparse codes $\mathbf{A}=[{\mathbf{a}}_1,{\mathbf{a}}_2,\dots ,{\mathbf{a}}_n]$, ${\mathbf{a}}_i\in R^{p\times 1}$, $i=1,2,\dots ,n$, using a learned dictionary $\mathbf{D}=[{\mathbf{d}}_1,{\mathbf{d}}_2,\dots ,{\mathbf{d}}_p]$, where ${\mathbf{d}}_i\in R^{m\times 1}$, $i=1,2,\dots ,p$ are the learned atoms. It should be noted that the initial dictionary is generated by assigning equal number of atoms to each class. This means that for a K-class classification, there are $p_c=\frac{p}{K}$ atoms assigned to each class in a dictionary consisting of p atoms.

The sparse representation is obtained by the following convex optimization:

$\begin{array}{c}\mathbf{A}=\arg {\min }_{\mathbf{A}}\frac{1}{2}||\mathbf{X}-\mathbf{DA}|{|}_F^2+{\lambda }_1{\sum }_i||{\mathbf{a}}_i|{|}_1+{\lambda }_2||\mathbf{A}|{|}_F^2,\hfill \end{array}$

or rewritten in a separate form for each ${\mathbf{x}}_i$ as

$\begin{array}{c}{\mathbf{a}}_i=\arg {\min }_{{\mathbf{a}}_i}\frac{1}{2}||{\mathbf{x}}_i-{\mathbf{Da}}_i|{|}_2^2+{\lambda }_1||{\mathbf{a}}_i|{|}_1+{\lambda }_2||{\mathbf{a}}_i|{|}_2^2.\hfill \end{array}$

Note ${\lambda }_2>0$ is necessary for proving the differentiability of the objective function (see [2.1] in Appendix). However, setting ${\lambda }_2=0$ proves to work well in practice [25].

Obviously, the effect of sparse coding (2.1) largely depends on the quality of dictionary D. The authors in [18] suggest to construct the dictionary by directly selecting atoms from the training samples. More sophisticated methods are widely used in SRC literature, discussing on how to learn a more compact and effective dictionary from a given training dataset, e.g., the K-SVD algorithm [31].

We recognize that many structured sparsity constraints (priors) [18,32] can also be considered for dictionary learning. They usually exploit the correlations among the neighboring pixels or their features. For example, the SRC dictionary has an inherent group-structured property since it is composed of several class-wise subdictionaries, i.e., the atoms belonging to the same class are grouped together to form a subdictionary. Therefore, it would be reasonable to enforce each pixel to be compactly represented by groups of atoms instead of individual ones. This could be accomplished by encouraging coefficients of only certain groups to be active, like the group lasso [33]. While the performance may be improved by enforcing structured sparsity priors, the algorithm will be considerably more complicated. Therefore, we do not take into account any structured sparsity prior here, and leave them for our future study.

2.2.2.2 Task-Driven Functions for Classification

Classical loss functions in SRC are often defined by the reconstruction error of data samples [18,39]. The performances of such learned classifiers highly hinge on the quality of the input features, which is only suboptimal without the joint optimization with classifier parameters. In [34], the authors study a straightforward joint representation and classification framework, by adding a penalty term to the classification error in addition to the reconstruction error. The authors of [35,36] propose to enhance the dictionary's representative and discriminative power by integrating both the discriminative sparse-code error and the classification error into a single objective function. The approach jointly learns a single dictionary and a predictive linear classifier. However, being a semisupervised method, the unlabeled data does not contribute much to promoting the discriminative effect in [36], as only the reconstruction error is considered on the unlabeled set except for an “expansion” strategy applied to a small set of highly-confident unlabeled samples.

In order to obtain an optimal classifier with regard to the input feature, we exploit a task-driven formulation which aims to minimize a classification-oriented loss [25]. We incorporate the sparse codes ${\mathbf{a}}_i$, which are dependent on the atoms of the dictionary D that are to be learned, into the training of the classifier parameter w. The logistic loss is used in the objective function for the classifier. We recognize that the proposed formulation can be easily extended to other classifiers, e.g., SVM. The loss function for the labeled samples is directly defined by the logistic loss

$\begin{array}{c}L(\mathbf{A},\mathbf{w},{\mathbf{x}}_i,y_i)={\sum }_{i=1}^l\log (1+e^{-y_i{\mathbf{w}}^T{\mathbf{a}}_i}).\hfill \end{array}$

For unlabeled samples, the label of each ${\mathbf{x}}_{\mathbf{i}}$ is unknown. We propose to introduce the predicted confidence probability $p_{ij}$ that sample ${\mathbf{x}}_{\mathbf{i}}$ has label $y_j$ ($y_j=1$ or −1), which is naturally set as the likelihood of the logistic regression

$\begin{array}{c}{p}_{ij}=p(y_j|{\mathbf{w},\mathbf{a}}_i,{\mathbf{x}}_i)=\frac{1}{1+e^{-y_j{\mathbf{w}}^T{\mathbf{a}}_i}},y_j=1\text{or}-1.\hfill \end{array}$

The loss function for the unlabeled samples then turns into an entropy-like form

$\begin{array}{c}U(\mathbf{A},\mathbf{w},{\mathbf{x}}_i)={\sum }_{i=l+1}^{l+u}{\sum }_{y_j}{p}_{ij}L({\mathbf{a}}_i,\mathbf{w},{\mathbf{x}}_i,y_j),\hfill \end{array}$

which can be viewed as a weighted sum of loss under different classification outputs $y_j$.

Furthermore, we can similarly define $p_{ij}$ for the labeled sample ${\mathbf{x}}_i$, that is 1 when $y_j$ is the given correct label $y_i$ and 0 elsewhere. The joint loss functions for all the training samples can thus be written into a unified form

$\begin{array}{c}T(\mathbf{A},\mathbf{w})={\sum }_{i=1}^{l+u}{\sum }_{y_j}{p}_{ij}L({\mathbf{a}}_i,\mathbf{w},{\mathbf{x}}_i,y_j).\hfill \end{array}$

A semisupervised task-driven formulation has also been proposed in [25]. However, it is posed as a naive combination of supervised and unsupervised steps. The unlabeled data are only used to minimize the reconstruction loss, without contributing to promoting the discriminative effect. In contrast, our formulation (2.6) clearly distinguishes itself by assigning an adaptive confidence weight (2.4) to each unlabeled sample, and minimizes a classification-oriented loss over both labeled and unlabeled samples. By doing so, unlabeled samples also contribute to improving the discriminability of learned features and classifier, jointly with the labeled samples, rather than only optimized for reconstruction loss.

2.2.2.3 Spatial Laplacian Regularization

We first introduce the weighting matrix G, where $G_{ik}$ characterizes the similarity between a pair of pixels ${\mathbf{x}}_i$ and ${\mathbf{x}}_k$. We define $G_{ik}$ in the form of shift-invariant bilateral Gaussian filtering [37] (with controlling parameters ${\sigma }_d$ and ${\sigma }_s$)

$\begin{array}{c}{G}_{ik}=\exp (-\frac{d({\mathbf{x}}_i,{\mathbf{x}}_k)}{2{\sigma }_d^2})\cdot \exp (-\frac{||{\mathbf{x}}_i-{\mathbf{x}}_k|{|}_2^2}{2{\sigma }_s^2}),\hfill \end{array}$

which measures both the spatial Euclidean distance ($d({\mathbf{x}}_i,{\mathbf{x}}_k)$) and the spectral similarity between an arbitrary pair of pixels in a hyperspectral image. Larger $G_{ik}$ represents higher similarity and vice versa. Further, rather than simply enforcing pixels within a local window to share the same label, $G_{ik}$ is defined over the whole image and encourages both spatially neighboring and spectrally similar pixels to have similar classification outputs. It makes our spatial constraints much more flexible and effective. Using the above similarity weights, we define the spatial Laplacian regularization function

$\begin{array}{c}S(\mathbf{A},\mathbf{w})={\sum }_{i=1}^{l+u}{\sum }_{y_j}{\sum }_k^{l+u}{G}_{ik}||p_{ij}-p_{kj}|{|}_2^2.\hfill \end{array}$

2.2.4.1 Stochastic Gradient Descent

The stochastic gradient descent (SGD) algorithm [28] is an iterative, “online” approach for optimizing an objective function, based on a sequence of approximate gradients obtained by randomly sampling from the training data set. In the simplest case, SGD estimates the objective function gradient on the basis of a single randomly selected example ${\mathbf{x}}_t$

$\begin{array}{c}{w}_{t+1}=w_t-{\rho }_t{\mathrm{\nabla }}_{w}F({\mathbf{x}}_t,w_t),\hfill \end{array}$

where F is a loss function, w is a weight being optimized and ${\rho }_t$ is a step size known as the“learning rate”. The stochastic process $\{w_t,t=1,\dots \}$ depends upon the sequence of randomly selected examples ${\mathbf{x}}_t$ from the training data. It thus optimizes the empirical cost, which is hoped to be a good proxy for the expected cost.

Following the derivations in [25], we can show that the objective function in (2.9), denoted as $B(\mathbf{A},\mathbf{w})$ for simplicity, is differentiable on $\mathbf{D}\times \mathbf{w}$, and that

$\begin{array}{c}{\mathrm{\nabla }}_{\mathbf{w}}B(\mathbf{A},\mathbf{w})={\mathbb{E}}_{\mathbf{x},y}[{\mathrm{\nabla }}_{\mathbf{w}}T(\mathbf{A},\mathbf{w})+{\mathrm{\nabla }}_{\mathbf{w}}S(\mathbf{A},\mathbf{w})+\lambda \mathbf{w}],\hfill \\ {\mathrm{\nabla }}_{\mathbf{D}}B(\mathbf{A},\mathbf{w})={\mathbb{E}}_{\mathbf{x},y}[-\mathbf{D}{\mathit{\beta }}^{⁎}{\mathbf{A}}^{\mathbf{T}}+({\mathbf{X}}_t-\mathbf{D}\mathbf{A}){{\mathit{\beta }}^{⁎}}^T],\hfill \end{array}$

where ${\mathit{\beta }}^{⁎}$ is a vector defined by the following property:

$\begin{array}{c}{\mathit{\beta }}_{S^C}^{⁎}=0,{\mathit{\beta }}_S^{⁎}={({\mathbf{D}}_S^T{\mathbf{D}}_S+{\lambda }_2\mathbf{I})}^{-1}{\mathrm{\nabla }}_{{\mathbf{A}}_S}[T(\mathbf{A},\mathbf{w})+S(\mathbf{A},\mathbf{w})],\hfill \end{array}$

and S are the indices of the nonzero coefficients of A. The proof of the above equations is given in the Appendix.

2.2.4.2 Sparse Reconstruction

The most computationally intensive step in Algorithm 2.1 is solving the sparse coding (step 3). We adopt the feature-sign algorithm [39] for efficiently solving the exact solution to the sparse coding problem.

Remark on SGD convergence and sampling strategy. As a typical case in machine learning, we use SGD in a setting where it is not guaranteed to converge in theory, but behaves well in practice, as shown in our experiments. (The convergence proof of SGD [29] for nonconvex problems indeed assumes three times differentiable cost functions.)

SGD algorithms are typically designed to minimize functions whose gradients have the form of an expectation. While an i.i.d. (independent and identically distributed) sampling process is required, it cannot be computed in a batch mode. In our algorithm, instead of sampling one per iteration, we adopt a mini-batch strategy by drawing more samples at a time. Authors in [25] further pointed out that solving multiple elastic-net problems with the same dictionary D can be accelerated by the precomputation of the matrix ${\mathbf{D}}^T\mathbf{D}$. In practice, we draw a set of 200 samples in each iteration, which produces steadily good results in all our experiments under universal settings.

Strictly speaking, drawing samples from the distribution of training data should be made i.i.d. (step 2 in Algorithm 2.1). However, this is practically difficult since the distribution itself is typically unknown. As an approximation, samples are instead drawn by iterating over random permutations of the training set [29].