l₀-norm based structural sparse least square regression for feature selection

Highlights

• We impose l₀-norm inequality constraint to build the structural sparse LSR problem.

• We develop an adaptive algorithm to ensure the structural sparsity accurately.

• Theoretical results on the efficiency and effectiveness of our method are provided.

• Experimental results prove the superiority of our method over the state-of-the-arts.

Abstract

This paper presents a novel approach for feature selection with regard to the problem of structural sparse least square regression (SSLSR). Rather than employing the l₁-norm regularization to control the sparsity, we directly work with sparse solutions via l₀-norm regularization. In particular, we develop an effective greedy algorithm, where the forward and backward steps are combined adaptively, to resolve the SSLSR problem with the intractable $l_{r,0}$-norm. On the one hand, features with the strongest correlation to classes are selected in the forward steps. On the other hand, redundant features which contribute little to the improvement of the objective function are removed in the backward steps. Furthermore, we provide solid theoretical analysis to prove the effectiveness of the proposed method. Experimental results on synthetic and real world data sets from different domains also demonstrate the superiority of the proposed method over the state-of-the-arts.

Introduction

Feature selection, which has been widely identified as a key component in the area of machine learning (ML) and pattern recognition (PR), primarily addresses the problem of finding the most relevant and informative subset of features according to certain evaluation criterion [1]. It plays an important role in many aspects including compressing and understanding huge data, boosting the model generalization capability, improving the prediction accuracy, as well as accelerating the learning process.

From the perspective of evaluation strategy, feature selection mainly fall into two categories: wrappers [2] and filters [3]. Wrapper approaches require a build-in classifier to evaluate the candidate feature subset, while filter approaches evaluate the correlation between features based on a criterion indicative of the ability to separate the classes. In this paper, we focus on the latter.

Least square regression (LSR) and several variants of LSR [4], [5] have been widely applied in solving a number of ML and PR problems [6], [7]. As an important branch of LSR, structural sparse LSR (SSLSR) which adds the structural sparse regularization term or constraint to the classical LSR, has received increasing attention recently. Formally, SSLSR can be represented as the following constrained optimization problem:

$$\underset{\mathbf{W}}{\min }\mathcal{L}\left(\mathbf{W}\right):\underset{\mathbf{W}}{\min }\frac{1}{n}\parallel \mathbf{XW}-\mathbf{Y}{\parallel }_2^2,\mathrm{s}.\mathrm{t}.\parallel \mathbf{W}{\parallel }_{r,0}\le p$$

where $\mathbf{X}\in {\mathfrak{R}}^{n\times m}$ is the data matrix with n samples and m features, $\mathbf{Y}\in {\{0,1\}}^{n\times c}$ is the class label indicator matrix with n samples and c classes (${\mathbf{Y}}_{\mathit{ij}}=1$ if the i-th sample belongs to the j-th class, otherwise, ${\mathbf{Y}}_{\mathit{ij}}=0$). Then $\mathbf{W}\in {\mathfrak{R}}^{m\times c}$ indicates the correlation between features and classes. The i-th feature is selected if $\parallel {\mathbf{W}}_{(i,:)}\parallel \ne 0$, and ${\mathbf{W}}_{(i,:)}=\mathbf{0}$ means that the i-th feature is removed. The constraint $\parallel \mathbf{W}{\parallel }_{r,0}\le p$ guarantees that the number of nonzero rows of $\mathbf{W}$, i.e., the number of selected features, is no more than p. In other words, structural sparse constraint based on $l_{r,0}$-norm controls the sparsity in an explicitly way, serving the purpose of feature selection.

Recent developments to handle the non-convex l₀-norm [8] regularization lie in the following two aspects. The methods in the first major aspect create a smoothed convex approximation such as l₁-norm regularization [6], [9], [10]. Since the conditions [8], that ensures l₁-norm is an equivalent relaxation of l₀-norm, do not always hold, the term $\parallel \mathbf{W}{\parallel }_{r,1}\le p$ may fail to live up to the desired feature selection property, leading to prediction accuracy loss by shrinking both relevant and irrelevant features to zero. The second aspect includes several methods which attempt to directly cope with the l₀-norm via introducing auxiliary augmented functions [11], [12]. Nevertheless, additional terms mean excess variables and parameters, which may negatively affect the generalization capability of these algorithms. Besides, they often force reset of some non-zero rows of the auxiliary matrices, which may lead to error accumulation.

To remedy the drawbacks mentioned above, we develop an effective greedy algorithm to directly handle the challenging $l_{r,0}$-norm in Eq. (1). Our proposed algorithm starts with an empty feature set and alternates between forward and backward greedy steps during optimization. In the forward steps, we pick informative features which reduce the temporal square loss most among the remaining features. Meanwhile, redundant features with little contribution to minimizing the objective function are removed in the backward steps. For the sake of preventing the backward steps to erase the gains made in forward steps, we combine these two steps adaptively. Therefore, it is natural to constrain the number of selected features strictly less than p. Furthermore, we provide solid theoretical analysis to show the effectiveness of our proposed method. Experimental results on synthetic and different real world data sets also demonstrate its superiority over the state-of-the-arts.

Our main contributions are highlighted as follows:

• We develop a novel greedy algorithm to solve the SSLSR problem with $l_{r,0}$-norm by combining forward and backward steps adaptively.

• We offer theoretical guarantees, as well as the experimental results from diverse domains to support our method.

Throughout this paper, scalars, matrices, vectors, sets and functions are denoted as small, boldface capital, boldface lowercase, fraktur capital and script capital letters respectively. ${\mathbf{a}}_i$, ${\mathbf{A}}_{\mathit{ij}}$, ${\mathbf{A}}_{(i,:)}$ and ${\mathbf{A}}_{(:,j)}$ indicate the i-th element of $\mathbf{a}$, the element of $\mathbf{A}$ occurs in the i-th row and j-th column, the i-th row of $\mathbf{A}$ and the j-th column of $\mathbf{A}$ respectively. Moreover, $\forall r\ge 0$, we define the norm of any $\mathbf{a}\in {\mathfrak{R}}^{s\times 1}$ and $\mathbf{A}\in {\mathfrak{R}}^{s\times t}$ as

$$\parallel \mathbf{a}{\parallel }_r=\{\begin{array}{cc}{\left(\sum _{i=1}^s|{\mathbf{a}}_i{|}^r\right)}^{1/r}\hfill & \mathrm{if}r>0\hfill \\ \sum _{i=1}^s\parallel {\mathbf{a}}_i{\parallel }_0\hfill & \mathrm{if}r=0\hfill \end{array},\parallel \mathbf{A}{\parallel }_r={\left(\sum _{i=1}^s\sum _{j=1}^t|{\mathbf{A}}_{\mathit{ij}}{|}^r\right)}^{1/r}\mathrm{if}r>0\parallel \mathbf{A}{\parallel }_{r,0}=\sum _{i=1}^s\parallel \parallel {\mathbf{A}}_{(i,:)}{\parallel }_r{\parallel }_0,\parallel \mathbf{A}{\parallel }_{r,1}=\sum _{i=1}^s{\left(\sum _{j=1}^t|{\mathbf{A}}_{\mathit{ij}}{|}^r\right)}^{1/r}\mathrm{if}r>0$$

where $\parallel a{\parallel }_0=1$ if the scalar a is nonzero.