Improved Group Sparse Classifier

Abstract

This work proposes a new classifier based on the assumption that the training samples of a particular class approximately form a linear basis for any new test sample belonging to that class. This is not a new assumption; two previous works namely Sparse Classifier (Yang et al., 2009) and Group Sparse Classifier (Majumdar and Ward, 2009a) has been built upon it. However both the previous works are fraught with certain shortcomings. The two optimization algorithms proposed in the two previous works do not capture all the implications of the said assumption perfectly. This work, accounts for all the intricacies of the said assumption and consequently requires solving a new non-convex optimization problem. We have developed an elegant approach to solve the optimization problem based on Iterative Reweighted Least Squares method.

Our classifier is very flexible; the previous classifiers are actually two special cases of the said classifier. The proposed classifier has been rigorously compared against the previous ones stemming from the said assumption on benchmark classification databases. The results indicate that in most cases the proposed classifier is significantly better than the previous ones and in the worst case the proposed classifier is as good as the previous ones.

Introduction

Recently there has been an interest in a classification model where the training samples of a particular class are assumed to form a linear basis for approximately representing any new test sample belonging to that class. This assumption has led to the development of some new classifiers like the Sparse Classifier (SC) (Yang et al., 2009), Group Sparse Classifier (GSC) (Majumdar and Ward, 2009a) and its fast version called the Fast Group Sparse Classifier (FGSC) (Majumdar and Ward, 2009b). Formally, this assumption can be expressed as,

$$v_{k\text{,}\mathit{test}}={\alpha }_{k\text{,}1}{v}_{k\text{,}1}+{\alpha }_{k\text{,}2}{v}_{k\text{,}2}+\cdots +{\alpha }_{k\text{,}{n}_k}{v}_{k\text{,}{n}_k}+{\epsilon }_k\text{,}$$

where v_k,test is the test sample of the kth class, v_k,i is the ith training sample of the kth class, α_k,i is the weight corresponding weight and ε_k is the approximation error.

Geometrically this assumption implies that each class comprises of a few subspaces, and each subspace is spanned by some training vectors. The new test sample can be approximately represented as a union of these subspaces. To take a concrete example, consider the problem of face recognition. Faces appear in different poses – frontal, left profile, right profile, etc. Each of the poses can be assumed to lie on a subspace. If there are enough training samples, a few samples in each pose will be sufficient to capture the variability of that pose. Now if there is a new test sample, with a pose somewhere between frontal and left profile, then it may be expressed as a linear combination of the training samples in frontal and left profile poses. The relative contribution of the training samples in each pose will be decided by their weights (α).

All the aforementioned classifiers (SC, GSC and FGSC) determine the unknown weights (α_k,i’s) by solving different optimization problems and use these weights to determine the class of the test sample. The first step for all of them is to express the assumption in terms of all the training samples instead of just one class as in (1). In compact matrix vector notation it can be expressed as,

$$v_{k\text{,}\mathit{test}}=V\alpha +\epsilon$$

where $V=[v_{1\text{,}1}|\cdots |v_{n\text{,}1}|\cdots |v_{k\text{,}1}|\cdots |v_{k\text{,}{n}_k}|\cdots v_{C\text{,}1}|\cdots |v_{C\text{,}{n}_C}]$ and $\alpha =[{\alpha }_{1\text{,}1}\cdots {\alpha }_{1\text{,}{n}_1}\cdots {\alpha }_{k\text{,}1}\cdots {\alpha }_{k\text{,}{n}_k}\cdots {\alpha }_{C\text{,}1}\cdots {\alpha }_{C\text{,}{n}_C}{]}^{\prime }$.

Given v_k,test and V, the problem is to determine the class of the test sample. To achieve this from the said assumption, it is required to solve the unknown weight vector α. The way to do this is to solve an optimization problem of the following form,

$$\begin{array}{cc}\hfill \hat{\alpha }& =\underset{\alpha }{\min }\phi (\alpha )\hfill \\ \hfill & \text{s}.\text{t}.\Vert v_{k\text{,}\mathit{test}}-V\alpha {\Vert }_2⩽\sigma \hfill \end{array}$$

The objective function φ(α) contains prior information about the nature of α and the constraint arises from the assumption that the misfit is Normally distributed.

The different classification methods vary in their choice of the objective function. In SC (Yang et al., 2009) it is assumed that the weight vector α should be sparse and therefore employed the l₁-norm on the weight vector $(\Vert \alpha {\Vert }_1)$ as the objective function. The choice of the l₁-norm as a sparsifying function can be traced back to studies in statistics (Tibshirani, 1996) and signal processing (Chen et al., 2001). However the l₁-norm is not an appropriate choice in this case. This is because as pointed out in (Zou and Hastie, 2005) l₁-norm only selects a single sample from a group of correlated training samples. For the example of face recognition, it implies that, if the test sample is a pose between frontal and left profile, the SC (employing l₁-norm) will try to express the test sample either as a frontal or as a left profile, but not a combination of both. Clearly this is not desired.

To address this issue, the GSC was proposed by Majumdar and Ward (2009a). It employed a mixed norm for the objective function, given by $\Vert \alpha {\Vert }_{2\text{,}1}={\sum }_k\Vert {\alpha }_k{\Vert }_2$. This norm ensured that for a particular class, all the training samples were selected, but the number of classes selected is sparse (Huang and Zhang, 2008, Eldar et al., 2009). The GSC (also the FGSC which is a fast implementation of GSC) showed good results, but it is not perfect either. This is because the inner l₂-norm of the mixed norm selects all the training samples from a particular class. We again refer to the problem of face recognition. In this case, if a test image is somewhere between the left profile and frontal, this classifier will try to represent it as a combination of all the view – left, frontal and right. This is erroneous as well.

The SC and the GSC are two extremes – the SC only selects one sample from the entire class (in the extreme case) and the GSC selects all. Ideally we would like the classifier to represent the test sample only as a combination of the relevant subspaces and not all. For the face recognition problem, this means that if a test sample is somewhere between the left and frontal view, it should be only represented by training samples corresponding to these and not training samples from right profile view. Present classifiers like SC and GSC can not address this problem. This paper is dedicated to find methods to solve this shortcoming so that the classifier can operate between the two extremes.

The other issue we would tackle in this paper is the relaxation of the l₂-norm misfit (3). There is no reason (physical or mathematical) to assume that the misfit is normally distributed. In this work we would like to experiment with some other norms for the misfit.

This paper has two major contributions – (i) changing the objective function to address aforementioned issues; and (ii) changing the norm for the misfit. Both of these lead to new optimization problems which will solved in an efficient manner in this paper. The rest of the paper is divided into several sections. In the next section, the background of this work is discussed. The proposed classification model is discussed in Section 3. In Section 4, the optimization problem behind the proposed classifier is detailed out. The experimental results are described in Section 5. The conclusions of the work are discussed in Section 6.