# A Semisupervised Feature Selection with Support Vector Machine

Authors: Kun Dai; Hong-Yi Yu; Qing Li
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Feature selection has proved to be a beneficial tool in learning problems with the main advantages of interpretation and generalization. Most existing feature selection methods do not achieve optimal classification performance, since they neglect the correlations among highly correlated features which all contribute to classification. In this paper, a novel semisupervised feature selection algorithm based on support vector machine (SVM) is proposed, termed SENFS. In order to solve SENFS, an efficient algorithm based on the alternating direction method of multipliers is then developed. One advantage of SENFS is that it encourages highly correlated features to be selected or removed together. Experimental results demonstrate the effectiveness of our feature selection method on simulation data and benchmark data sets.


---

## Body

## 1. Introduction

Feature selection, with the purpose of selecting relevant feature subsets among thousands of potentially irrelevant and redundant features, is a challenging topic of pattern recognition research that has attracted much attention over the last few years. A good feature selection method has several advantages for a learning algorithm such as reducing computational cost, increasing its classification accuracy, and improving result comprehensibility [1].Considering the usage of the class label information, feature selection methods can be classified into supervised methods, unsupervised methods, and semisupervised methods. Supervised feature selection methods usually use only information from labeled data to find the relevant feature subsets [2–4]. However, in many real, world applications, the labeled data are very expensive or difficult to obtain, which brings difficulty to create a large training data set. This situation arises naturally in practice, where large amount of data can be collected automatically and cheaply, when manual labeling of samples remains difficult, expensive and time consuming. Unsupervised feature selection methods could be an alternative in this case through exploiting the information conveyed by the large amount of unlabeled data [5, 6]. However, as these unsupervised algorithms ignore label information, important hints from labeled data are left out and this will generally downgrade the performance of unsupervised feature selection algorithms. The combination of both supervised methods and unsupervised methods is semisupervised approaches [7–10] which exploit the information of both labeled and unlabeled data. A good survey about semisupervised feature selection approaches can be found in [9].The performances of the most existing semisupervised feature selection methods are insufficient when there are several highly correlated features, which are all relevant to classification and the way they interact can help with the interpretability of the objective problem [11]. Given these premises, this paper provides two main contributions as follows.(i)
We present a novel semisupervised feature selection scheme based on support vector machine (SVM) and the elastic net penalty proposed by Zou and Hastie [12] combining l1 and l2 regularizations, termed SENFS.(ii)
In order to solve SENFS with the nondifferentiability of both the loss function and thel1-norm regularization term, an efficient algorithm based on the alternating direction method of multipliers (ADMM) [13] is developed.Compared with other semisupervised feature selection algorithms, SENFS provides the following benefits.(i)
It permits highly correlated features to be selected or removed together.(ii)
It performs automatic feature selection as part of the training process and can achieve better classification performance using the selected features.The effectiveness of SENFS is validated on simulated data and six benchmark semisupervised data sets. Our main finding is that SENFS can identify the features that are relevant to classification using the data set that consists of only a few labeled samples and many unlabeled samples.This paper is organized as follows. Section2 briefly introduces the methodology. In Section 3, we derive an iterative algorithm that yields the entire solution path based on ADMM to solve this proposed method. In Section 4, we evaluate the performance of this proposed method on both simulated and real-world data, followed by a summary in Section 5.


## 2. Methodology

Assume that all samples sampled from the same population generated by target concept consist ofp features. Given a set of samples X=(x1,…,xn)T, in which n is the number of samples, the ith sample or input vector xi of original feature D with p features is denoted by xi={xi1,xi2,…,xip}. The set X can be divided into two parts: labeled set Xl=(x1,…,xl)T for which labels yl=(y1,…,yl)T are provided with yi∈{-1,1}i=1l for binary problem and unlabeled set Xu=(xl+1,…,xl+u)T whose labels are not given, where l and u are the number of labeled and unlabeled samples, respectively, and n=l+u. Then, the generic goal of semisupervised feature selection is to find a feature subset D′ with d(d<p) features which contains the most informative features using both data information of Xl and Xu. In other words, the samples (x1′,…,xn′)T represented in the d-dimensional space can well preserve the information of the samples X=(x1,…,xn)T represented in the original p-dimensional space.We begin our discussion with the binary supervised feature selection based on the elastic net penalty. Wang et al. [11] proposed a supervised feature selection method based on SVM with the elastic net penalty term named doubly regularized support vector machine for binary classification problems, which solves the optimization of the following generic objective function over both the hyper plane parameters (β,β0):(1)minβ,β0C∑i=1nV(yig(xi))+λ1∥β∥1+λ2∥β∥222,
where the decision function is defined as g(x)=xβ+β0 and both λ1 and λ2 are tuning parameters, and C is the regularization parameter. V is the margin loss function; for example, hinge loss V(z)=H1(z)=max(1-z,0). The role of the l1-norm penalty is to allow selection, and the role of the l2-norm penalty is to help groups of highly correlated features get selected or removed together which is denoted by the grouping effect [11].As for semisupervised feature selection, consideringXl and Xu, inspired by the semisupervised learning algorithm TSVM [14], we apply the elastic net penalty for semisupervised feature selection (SENFS), which solves the following optimization task over both the hyper plane parameters (β,β0) and the unlabeled vector yu=(yl+1,…,yn)T:
(2)minβ,β0,yu∈{-1,+1}C∑i=1lV(yig(xi))+C*∑i=l+1nU(yig(xi))+λ1∥β∥1+λ2∥β∥222s.t.1u∑i=l+1nmax(0,yi)=c.The constraint in (2) is called the balancing constraint and is necessary to avoid the trivial solutions where all unlabeled samples are assigned to the same class. This constraint enforces a manually chosen constant c and an approximation of this constraint writes (1/n)∑i=1ng(xi)=2c-1 [15] with c. So the constraint can be rewritten as (1/u)∑i=l+1ng(xi)=(1/l)∑i=1lyi. V and U employ the same loss; for example, hinge loss V(z)=H1(z)=max(1-z,0).Obviously, the difficulty of the above optimization task consists in finding the optimal assignment for the unlabeled vectory and the hyper plane parameters (β,β0), which is a mixed-integer programming problem [16]. As described in [15], for a fixed (β,β0), argminyV(yg(x))=sign(g(x)). So the problem of (2) can be seen equivalently as
(3)minβ,β0C∑i=1lV(yig(xi))+C*∑i=l+1nU(|g(xi)|)+λ1∥β∥1+λ2∥β∥222s.t.1u∑i=l+1ng(xi)=1l∑i=1lyi.On the other hand, one effective approximation of the loss functionU(|z|) was a clipped variant [17] which can be expressed as
(4)U(|z|)=Rs(z)+Rs(-z)-(1-s),
where Rs(z) is the Ramp loss defined as Rs(z)=H1(z)-Hs(z) with Hs(z)=max(s-z,0),0≤s<1. In our experiments, the typical value of s is 0.3. The main reason to use the clipped symmetric hinge loss is the gain of sparsity in the number of support vectors yielded by the optimizer [17]. Then we can get
(5)minβ,β0C*∑i=l+1nU(|g(xi)|)=minβ,β0C*∑i=l+1n(Rs(z)+Rs(-z)-(1-s))=minβ,β0C*∑i=l+1n(H1(g(xi))+H1(-g(xi)))-C*∑i=l+1n(Hs(g(xi))+Hs(-g(xi))).From (5), we can know that solving the optimization problem (3) with the clipped symmetric hinge loss is equivalent to solving a classical SVM with the unlabeled samples counted twice with yi=1 when l+1≤i≤l+u and yi=-1 when l+u+1≤i≤l+2u, which are artificial labels. Therefore problem (3) can be rewritten as
(6)minβ,β0C∑i=1lV(yig(xi))+C*∑i=l+1l+2u(H1(yig(xi))-Hs(yig(xi)))+λ1∥β∥1+λ2∥β∥222s.t.1u∑i=l+1ng(xi)=1l∑i=1lyi.As we can seen from (6), when C≠0,C*=0, SENFS evolves into a supervised feature selection algorithm, and when C=0,C*≠0, it becomes an unsupervised model.In the following, we will illustrate how SENFS has the grouping effect for correlated features. The following theorem describes this point.Theorem 1.
Denote the solution to (6) by (β~,β~0) and β^0, the input jth feature by Fj, and the input kth feature by Fk. Then for any pair (j,k), one can have
(7)|β~j-β~k|≤2Mλ2∑i=1l|xij-xik|+2M′λ2∑i=l+1l+2u|xij-xik|,
where M and M′are positive finite constants. Furthermore, if the input features Fj and Fk are centered and normalized, then
(8)|β~j-β~k|≤2λ2(2l(1-ρl)+2u(1-ρu)),
where ρl and ρu are the sample correlations between Fj and Fk,ρl=∑i=1l(xij-x-.j)(xik-x-.k)/∑i=1l(xij-x-.j)2∑i=1l(xik-x-.k)2, x-.j=(1/l)∑i=1lxij, x-.k=(1/l)∑i=1lxik, and ρk=∑i=l+1l+2u(xij-x-.j′)(xik-x-.k′)/∑i=l+1l+2u(xij-x-.j′)2∑i=l+1l+2u(xik-x-.k′)2, x-.j′=(1/2u)∑i=l+1l+2uxij,x-.k′=(1/2u)∑i=l+1l+2uxik.The term|β~j-β~k| in (7) describes the difference between the coefficient paths of Fj and Fl. If both features are highly correlated, that is, ρ=1, Theorem 1 says that difference between the coefficient paths of them is almost 0, in which case both features will be selected or removed together. The upper bound in (7) or (8) provides a quantitative description for the grouping effect of SENFS.


## 3. Algorithm for SENFS

The alternating direction method of multipliers (ADMM) developed in the 1970s and is well suited to distributed convex optimization and in particular to large-scale problems arising in statistics, machine learning, and related areas. The method is closely related to many other algorithms, such as the method of multipliers [18], Douglas-Rachford splitting [19], Bregman iterative algorithms [20] for l1 problems, and others.In this section, we first propose an efficient algorithm to solve SENFS based on ADMM by introducing auxiliary variables and reformulating the original problem. Then prove its convergence property and get the adjustment principle for penalty parameters. Finally describe the stopping criterion and computational cost.


### 3.1. Deriving ADMM for SENFS

It is hard to solve the model (6) directly due to the nondifferentiability of three loss functions and a l1-norm term. In order to derive an ADMM algorithm, we introduce some auxiliary variables to handle these nondifferentiable terms.LetXl={(xij)i=1,j=1l,p} denote labeled data, let Xu={(xij)i=l+1,j=1l+2u,p} denote unlabeled data, and let Yl,Yu be diagonal matrixes with their diagonal elements to be the vector yl=(y1,…,yl)T and yu=(yl+1,…,yl+2u)T, respectively. The constrained problem in (6) can be reformulated into an equivalent form
(9)minβ,β0C∑i=1l(hi)++C*∑i=l+1l+2u(ai)+-C*∑i=l+1l+2u(bi)++λ1∥t∥1+λ22∥β∥22s.t.{h=1l-Yl(Xlβ+β01l)a=1u-Yu(Xuβ+β01u)b=s1u-Yu(Xuβ+β01u)t=β1u∑i=l+1n(xiβ+β0)=r,
where h=(h1,…,hl)T,  a=(a1,…,a2u)T, and b=(b1,…,b2u)T, 1l is an l-column vector of 1s and 1u is an 2u-column vector of 1s, and r=(1/l)∑i=1lyi. The Lagrangian function of (9) is
(10)l(γ)=C∑i=1l(hi)++C*∑i=l+1l+2u((ai)+-(bi)+)+λ1∥t∥1+λ22∥β∥22+uhT(1l-Yl(Xlβ+β01l)-h)+uaT(1u-Yu(Xuβ+β01u)-a)+ubT(s1u-Yu(Xuβ+β01u)-b)+vT(β-t)+q(r-1u∑i=l+1n(xiβ+β0)).In problem (10), γ={β,β0,h,a,b,t,uh,ua,ub,v,q}, and uh, ua, and ub are dual variables corresponding to the constraints h=1l-Yl(Xlβ+β01l), a=1u-Yu(Xuβ+β01u), and b=s1u-Y(Xuβ+β01u), respectively, v is corresponding to the constraint t=β, and q is a scalar corresponding to the balancing constrain. As in the method of multipliers, we form the augment Lagrangian
(11)L(γ)=l(γ)+μ12∥1l-Yl(Xlβ+β01l)∥22+μ22∥1u-Yu(Xuβ+β01u)∥22+μ32∥s1u-Y(Xuβ+β01u)∥22+μ42∥β-t∥22+μ52∥r-1u∑i=l+1n(xiβ+β0)∥22,
where μ1,μ2,μ3,μ4>0 are parameters. Problem (11) is the form of ADMM, which consists of the following iterations:
(12)(βk+1,β0k+1,hk+1,ak+1,bk+1,tk+1)=argminβ,β0,h,a,b,tL(β,β0,h,a,b,t,uhk,uak,ubk,vk,qk),uhk+1=uhk+μ1(1l-Yl(Xlβk+1+β0k+11l)-hk+1),uak+1=uak+μ2(1u-Yu(Xuβk+1+β0k+11u)-ak+1),ubk+1=ubk+μ3(s1u-Yu(Xuβk+1+β0k+11u)-bk+1),vk+1=vk+μ4(βk+1-tk+1),qk+1=qk+μ5(r-1u∑i=l+1n(xiβk+1+β0k+1)).The efficiency of the iterative algorithm (12) lies on whether the first equation of (12) can be solved quickly. According to the theory of ADMM, these variables (β,β0), h,a,b, and t are updated in an alternating or sequential fashion, which accounts for the term alternating direction. So we can get(13)(βk+1,β0k+1)=argminβ,β0L(β,β0,hk,ak,bk,tk,uhk,uak,ubk,vk,qk),hk+1=argminhL(βk+1,β0k+1,h,ak,bk,tk,uhk,uak,ubk,vk,qk),ak+1=argminaL(βk+1,β0k+1,hk+1,a,bk,tk,uhk,uak,ubk,vk,qk),bk+1=argminbL(βk+1,β0k+1,hk+1,ak+1,b,tk,uhk,uak,ubk,vk,qk),tk+1=argmintL(βk+1,β0k+1,hk+1,ak+1,bk+1,t,uhk,uak,ubk,vk,qk).For the first equation in (13), it is equivalent to the following convex optimization:
(14)(βk+1,β0k+1)=argminβ,β0λ22∥β∥22+uhT(1l-Yl(Xlβ+β01l)-h)+uaT(1u-Yu(Xuβ+β01u)-a)+ubT(s1u-Yu(Xuβ+β01u)-b)+vT(β-t)+q(r-1u∑i=1u(xiβ+β0))+μ12∥1l-Yl(Xlβ+β01l)-h∥22+μ22∥1u-Yu(Xuβ+β01u)-a∥22+μ32∥s1u-Yu(Xuβ+β01u)-b∥22+μ42∥β-t∥22+μ52∥r-1u∑i=l+1n(xiβ+β0)∥22.The objective function in the above minimization problem is quadratic and differentiable, and since(βk+1,β0k+1) minimizes this function by definition, the optimal solution can be found by solving a set of linear equations(15)((λ2+μ4+μ5u2∑i=l+1nxiT∑i=l+1nxi)I+μ1XlTXl+(μ2+μ3)XuTXuμ1XlT1l+(μ2+μ3)XuT1u+μ5u∑i=l+1nxiT1lTXl+(μ2+μ3)1uTXu+μ5u∑i=l+1nxi1ulμ1+2u(μ2+μ3)+μ5)(βk+1β0k+1)=(XlTYlT(uhk+μ1(1-hk))+XuTYuT(uak+ubk+μ2(1-ak)+μ3(s-bk))-vk+(qk+μ5r)∑i=l+1nxiTu+μ4tk1lTYlT(uhk+μ1(1-hk))+1uTYuT(uak+ubk+μ2(1-ak)+μ3(s-bk))+qk+μ5r).In (15), I is a p×p unit matrix and the coefficient matrix is a (p+1)×(p+1) matrix, independent of the optimization variables. For large p, small n setting, the term XlTXl in the coefficient matrix will be a positive low rank matrix with rank at most l while the term XuTXu in the coefficient matrix will be a positive low rank matrix with rank at most 2u. Therefore, the coefficient matrix is also low rank matrix with rank at most (2u+1). And if we use CG to solve the problem (15), it will converge in less than (2u+1) steps [21].For the second equation in (13), it is equivalent to solving
(16)hk+1=argminhC∑i=1l(hi)++(uhk)T(1l-Yl(Xlβk+1+β0k+11l)-hk+1)+μ12∥1l-Yl(Xlβk+1+β0k+11l)-hk+1∥22.In order to solve (16), we need the following Proposition [22].Proposition 2.
Letsλ(w)=argminx∈ℝλx++0.5∥x-w∥22 where λ>0. Then
(17)sλ(w)={w-λw>λ,00≤w≤λ,ww<0.Combined with Proposition2 and
(18)∥uhk∥222μ1+(uhk)T(1l-Yl(Xlβk+1+β0k+11l)-hk+1)+0.5μ1∥1l-Yl(Xlβk+1+β0k+11l)-hk+1∥22=0.5μ1∥uhkμ1+1l-Yl(Xlβk+1+β0k+11l)-hk+1∥22,we can updatehk+1 according to Corollary 3.Corollary 3.
The update ofhk+1 in (16) is equivalent to
(19)hk+1=SC/μ1(1l+uhkμ1-Yl(Xlβk+1+β0k+11l)),
where Sλ(w)=(sλ(w1),…,sλ(wl)).For the third equation in (13), it is equivalent to solving (20):
(20)ak+1=argminaC*∑i=l+1l+2u(ai)++(uak)T(1u-Yu(Xuβk+1+β0k+11u)-ak+1)+μ22∥1u-Yu(Xuβk+1+β0k+11u)-ak+1∥22.Combined with Proposition2 and
(21)∥uak∥222μ1+(uak)T(1u-Yu(Xuβk+1+β0k+11u)-ak+1)+0.5μ2∥1u-Yu(Xuβk+1+β0k+11u)-ak+1∥22=0.5μ2∥uakμ2+1u-Yu(Xuβk+1+β0k+11u)-ak+1∥22,we can updateak+1 according to Corollary 4.Corollary 4.
The update ofak+1 in (20) is equivalent to
(22)ak+1=SC*/μ2(1u+uakμ2-Yu(Xuβk+1+β0k+11u)),
where Sλ(w)=(sλ(w1),…,sλ(w2u)).For the fourth equation in (13), it is equivalent to solving
(23)bk+1=argminbC*∑i=l+1l+2u(bi)++(ubk)T(s1u-Yu(Xuβk+1+β0k+11u)-bk+1)+μ32∥s1u-Yu(Xuβk+1+β0k+11u)-bk+1∥22.
In order to solve (23), we need the following proposition.Proposition 5.
Letgλ(w)=argminx∈ℝλx++0.5∥x-w∥22, where λ<0. Then
(24)gλ(w)={w-λw>0,ww<0.Proof.
The functionλx++0.5∥x-w∥22 is strongly convex, so it has a unique solution. Therefore, by the subdifferential calculus [23], gλ is the unique minimizer of the following equation:
(25)0∈λ∂(x+)+x-w,
where ∂(x+) is the subdifferential of the function x+. According to [23], ∂(x+) can be expressed as
(26)∂(x+)={1x>0,{p:p∈[0,1]}x=0,0x<0.
With (25) and (26), we can get the desired result.
Then, combined with Proposition5 and
(27)∥ubk∥222μ3+(ubk)T(s1u-Yu(Xuβk+1+β0k+11u)-bk+1)+0.5μ3∥s1u-Yu(Xuβk+1+β0k+11u)-bk+1∥22=0.5μ3∥ubkμ3+s1u-Yu(Xuβk+1+β0k+11u)-bk+1∥22,
we can update bk+1 according to Corollary 6.Corollary 6.
The update ofbk+1 in (23) is equivalent to
(28)bk+1=G-C*/μ3(s1u+ubkμ3-Yu(Xuβk+1+β0k+11u)),
where Gλ(w)=(gλ(w1),…,gλ(w2u)).For the fifth equation in (13), it is equivalent to solving
(29)tk+1=argmintλ1∥tk+1∥1+(vk)T(βk+1-tk+1)+0.5μ4∥βk+1-tk+1∥22.Solving (29) can be done efficiently using soft threshold, and we can update tk+1 according to Corollary 7.Corollary 7.
The update oftk+1 in (29) is
(30)tk+1=Tλ1/μ4(vkμ4+βk+1),
where Tλ(w)=(tλ(w1),…,tλ(wp)), and tλ(w)=sgn(w)max{0,|w|-λ}.According to the theory of ADMM,∥s1k∥2, ∥s2k∥2, ∥s3k∥2, and ∥s4k∥2 must be small below some certain threshold δ. Considering the auxiliary variables in (11), we expect that ∥1l-Yl(Xlβ+β01l)-h∥2,∥1u-Yu(Xuβ+β01u)-a∥2, ∥s1u-Yu(Xuβ+β01u)-b∥2, and ∥β-t∥2 also must be small. Therefore, in our experiment, algorithm for SENFS stops whenever
(31)∥s1k∥2<δ,∥s2k∥2<δ,∥s3k∥2<δ,∥s4k∥2<δ,∥1l-Yl(Xlβ+β01l)-h∥2<lδ,∥1u-Yu(Xuβ+β01u)-a∥2<2uδ,∥s1u-Yu(Xuβ+β01u)-b∥2<2uδ,∥β-t∥2<pδ.Finally, we can get the algorithm for SENFS. The detailed procedure of the algorithm ADMM for SENFS is summarized in Algorithm8 as follows.Algorithm 8.
ADMM algorithm for SENFS.Input. Labeled data set {xi,yi}i=1l; unlabeled data set {xi}i=l+1n; tuning parameters λ1 and λ2; regularization parameter C.Output. Selected feature set.Step  1. Initialize β0,β00,h0,a0,b0,t0,uh0,ua0,ub0,v0, and q0.Step  2. If (31) is satisfied, go to Step  3; otherwise,
(1)
updateβk+1 and β0k+1 according to (15);(2)
updatehk+1, ak+1, bk+1, and tk+1 according to Corollaries 3–7, respectively;(3)
updateuhk+1,uak+1,ubk+1,vk+1, and qk+1 according to (12).Step  3. Get the best feature subset according to βjk+1,j=1,…,p. If βjk+1=0, the corresponding jth feature is abandoned; otherwise, it is selected as an important feature.


### 3.2. Convergence Analysis and Computational Cost

The convergence property of Algorithm8 can be derived from the theory of the alternating direction method of multipliers. According to the standard convergence theory of ADMM, Algorithm 8 satisfies the dual variable convergence [24]. So Theorem 9 holds.Theorem 9.
Suppose that(β*,β0*) is one of solution of (5). Then the following property holds:(32)C∑i=1lH1(yi(xiβk+β0k))+C*∑i=l+1l+2u(H1(yi(xiβk+β0k))-Hs(yi(xiβk+β0k)))+λ1∥βk∥1+λ2∥βk∥222=C∑i=1lH1(yi(xiβ*+β0*))+C*∑i=l+1l+2u(H1(yi(xiβ*+β0*))-Hs(yi(xiβ*+β0*)))+λ1∥β*∥1+λ2∥β*∥222.As for the computational issue, it is hard to predict the computational cost because it depends on the all the penalty parameters. According to our experience, we only need to iterate a few hundred iterations to get a reasonable result. On the other hand, the efficiency of Algorithm8 lies mainly on whether we can quickly solve the linear equations (15). And the computational cost for solving (15) is O(l2p+4u2p).


### 3.3. Varying Penalty Parameter

In order to make performance less dependent on the initial choice of the penalty parameter, it is necessary to use different penalty parameters. According to our experiment experience, the penalty parametersμ1,μ2,μ3, and μ4 have a huge influence on the performance and the number of iterations involved, so adaptive selections of them are performed.Forμ1, let f(β,β0)=C∑i=1l(hi)++C*∑i=l+1l+2u(H1(yi(xiβ+β0))-Hs(yi(xiβ+β0)))+λ1∥β∥1+0.5λ2∥β∥22, and the constraint conditions are h=1l-Yl(Xlβ+β01l) and the constraint of (3). The optimization task (6) is equivalent to
(33)W(β,β0)=f(β,β0)+uhT(1l-Yl(Xlβ+β01l)-h)+q(r-1u∑i=l+1n(xiβ+β0))+μ12∥1l-Yl(Xlβ+β01l)-h∥22+μ52∥r-1u∑i=l+1n(xiβ+β0)∥22.The necessary optimality conditions for the problem (6) are dual feasibility as
(34)0∈∂f(β*,β0*)∂β*-XlTYlTuh*-q*u∑i=l+1nxiT.
Since βk+1 minimizes W(βk+1,β0k+1,uhk,qk) by definition, we have that
(35)0∈∂f(βk+1,β0k+1)∂βk+1-XlTYlT(uhk-μ1(1l-Yl(Xlβk+1+β0k+11l)-hk))-qku∑i=l+1nxiT-μ5u×∑i=l+1nxiT(r-1u∑i=l+1n(xiβk+1+β0k+1))=∂f(βk+1,β0k+1)∂βk+1-XlTYlTuhk+1-qk+1u×∑i=l+1nxiT+μ1XlTYlT(hk-hk+1).Compared with (34), (35) means that the quantity μ1XlTYlT(hk-hk+1) can be viewed as a residual for (34), and let s1k+1=μ1XlTYlT(hk-hk+1).Forμ2, let f(β,β0) = C∑i=1lH1(yi(xiβ+β0)) + C*∑i=l+1l+2u((ai)+-Hs(yi(xiβ+β0)))+λ1∥β∥1+0.5λ2∥β∥22, and the constraint conditions are a=1u-Yu(Xuβ+β01u) and the constraint of (3). Through the same solving process as parameter μ1, we can get the residual s2k+1=μ2k+1XuTYuT(ak-ak+1). Similarly, we can get the residual s3k+1=μ3k+1XuTYuT(bk-bk+1) for parameter μ3 and s4k+1=μ4k+1XuTYuT(tk+1-tk) for parameter μ4. With these residuals, we can get a simple scheme to update μ1,μ2,μ3, and μ4, respectively, according to Corollary 10.Corollary 10.
The update ofμ1,μ2,μ3,μ4 is(36)μ1k+1={τincrμ1kif∥1l-Yl(Xlβk+β0k1l)-hk∥2>θ∥s1k∥2μ1kτdecrif∥s1k∥2>θ∥1l-Yl(Xlβk+β0k1l)-hk∥2μ1kotherwise,μ2k+1={τincrμ2kif∥1u-Yu(Xuβk+β0k1u)-ak∥2>θ∥s2k∥2μ2kτdecrif∥s2k∥2>θ∥1u-Yu(Xuβk+β0k1u)-ak∥2μ2kotherwise,μ3k+1={τincrμ3kif∥s1u-Yu(Xuβk+β0k1u)-bk∥2>θ∥s3k∥2μ3kτdecrif∥s3k∥2>θ∥s1u-Yu(Xuβk+β0k1u)-bk∥2μ3kotherwise,μ4k+1={τincrμ4kif∥β-t∥2>θ∥s4k∥2μ4kτdecrif∥s4k∥2>θ∥β-t∥2μ4kotherwise,where τincr>1,τdecr>,  and θ>1 are parameters. Typical choices might be τincr=τdecr=2 and θ=10.


## 3.1. Deriving ADMM for SENFS

It is hard to solve the model (6) directly due to the nondifferentiability of three loss functions and a l1-norm term. In order to derive an ADMM algorithm, we introduce some auxiliary variables to handle these nondifferentiable terms.LetXl={(xij)i=1,j=1l,p} denote labeled data, let Xu={(xij)i=l+1,j=1l+2u,p} denote unlabeled data, and let Yl,Yu be diagonal matrixes with their diagonal elements to be the vector yl=(y1,…,yl)T and yu=(yl+1,…,yl+2u)T, respectively. The constrained problem in (6) can be reformulated into an equivalent form
(9)minβ,β0C∑i=1l(hi)++C*∑i=l+1l+2u(ai)+-C*∑i=l+1l+2u(bi)++λ1∥t∥1+λ22∥β∥22s.t.{h=1l-Yl(Xlβ+β01l)a=1u-Yu(Xuβ+β01u)b=s1u-Yu(Xuβ+β01u)t=β1u∑i=l+1n(xiβ+β0)=r,
where h=(h1,…,hl)T,  a=(a1,…,a2u)T, and b=(b1,…,b2u)T, 1l is an l-column vector of 1s and 1u is an 2u-column vector of 1s, and r=(1/l)∑i=1lyi. The Lagrangian function of (9) is
(10)l(γ)=C∑i=1l(hi)++C*∑i=l+1l+2u((ai)+-(bi)+)+λ1∥t∥1+λ22∥β∥22+uhT(1l-Yl(Xlβ+β01l)-h)+uaT(1u-Yu(Xuβ+β01u)-a)+ubT(s1u-Yu(Xuβ+β01u)-b)+vT(β-t)+q(r-1u∑i=l+1n(xiβ+β0)).In problem (10), γ={β,β0,h,a,b,t,uh,ua,ub,v,q}, and uh, ua, and ub are dual variables corresponding to the constraints h=1l-Yl(Xlβ+β01l), a=1u-Yu(Xuβ+β01u), and b=s1u-Y(Xuβ+β01u), respectively, v is corresponding to the constraint t=β, and q is a scalar corresponding to the balancing constrain. As in the method of multipliers, we form the augment Lagrangian
(11)L(γ)=l(γ)+μ12∥1l-Yl(Xlβ+β01l)∥22+μ22∥1u-Yu(Xuβ+β01u)∥22+μ32∥s1u-Y(Xuβ+β01u)∥22+μ42∥β-t∥22+μ52∥r-1u∑i=l+1n(xiβ+β0)∥22,
where μ1,μ2,μ3,μ4>0 are parameters. Problem (11) is the form of ADMM, which consists of the following iterations:
(12)(βk+1,β0k+1,hk+1,ak+1,bk+1,tk+1)=argminβ,β0,h,a,b,tL(β,β0,h,a,b,t,uhk,uak,ubk,vk,qk),uhk+1=uhk+μ1(1l-Yl(Xlβk+1+β0k+11l)-hk+1),uak+1=uak+μ2(1u-Yu(Xuβk+1+β0k+11u)-ak+1),ubk+1=ubk+μ3(s1u-Yu(Xuβk+1+β0k+11u)-bk+1),vk+1=vk+μ4(βk+1-tk+1),qk+1=qk+μ5(r-1u∑i=l+1n(xiβk+1+β0k+1)).The efficiency of the iterative algorithm (12) lies on whether the first equation of (12) can be solved quickly. According to the theory of ADMM, these variables (β,β0), h,a,b, and t are updated in an alternating or sequential fashion, which accounts for the term alternating direction. So we can get(13)(βk+1,β0k+1)=argminβ,β0L(β,β0,hk,ak,bk,tk,uhk,uak,ubk,vk,qk),hk+1=argminhL(βk+1,β0k+1,h,ak,bk,tk,uhk,uak,ubk,vk,qk),ak+1=argminaL(βk+1,β0k+1,hk+1,a,bk,tk,uhk,uak,ubk,vk,qk),bk+1=argminbL(βk+1,β0k+1,hk+1,ak+1,b,tk,uhk,uak,ubk,vk,qk),tk+1=argmintL(βk+1,β0k+1,hk+1,ak+1,bk+1,t,uhk,uak,ubk,vk,qk).For the first equation in (13), it is equivalent to the following convex optimization:
(14)(βk+1,β0k+1)=argminβ,β0λ22∥β∥22+uhT(1l-Yl(Xlβ+β01l)-h)+uaT(1u-Yu(Xuβ+β01u)-a)+ubT(s1u-Yu(Xuβ+β01u)-b)+vT(β-t)+q(r-1u∑i=1u(xiβ+β0))+μ12∥1l-Yl(Xlβ+β01l)-h∥22+μ22∥1u-Yu(Xuβ+β01u)-a∥22+μ32∥s1u-Yu(Xuβ+β01u)-b∥22+μ42∥β-t∥22+μ52∥r-1u∑i=l+1n(xiβ+β0)∥22.The objective function in the above minimization problem is quadratic and differentiable, and since(βk+1,β0k+1) minimizes this function by definition, the optimal solution can be found by solving a set of linear equations(15)((λ2+μ4+μ5u2∑i=l+1nxiT∑i=l+1nxi)I+μ1XlTXl+(μ2+μ3)XuTXuμ1XlT1l+(μ2+μ3)XuT1u+μ5u∑i=l+1nxiT1lTXl+(μ2+μ3)1uTXu+μ5u∑i=l+1nxi1ulμ1+2u(μ2+μ3)+μ5)(βk+1β0k+1)=(XlTYlT(uhk+μ1(1-hk))+XuTYuT(uak+ubk+μ2(1-ak)+μ3(s-bk))-vk+(qk+μ5r)∑i=l+1nxiTu+μ4tk1lTYlT(uhk+μ1(1-hk))+1uTYuT(uak+ubk+μ2(1-ak)+μ3(s-bk))+qk+μ5r).In (15), I is a p×p unit matrix and the coefficient matrix is a (p+1)×(p+1) matrix, independent of the optimization variables. For large p, small n setting, the term XlTXl in the coefficient matrix will be a positive low rank matrix with rank at most l while the term XuTXu in the coefficient matrix will be a positive low rank matrix with rank at most 2u. Therefore, the coefficient matrix is also low rank matrix with rank at most (2u+1). And if we use CG to solve the problem (15), it will converge in less than (2u+1) steps [21].For the second equation in (13), it is equivalent to solving
(16)hk+1=argminhC∑i=1l(hi)++(uhk)T(1l-Yl(Xlβk+1+β0k+11l)-hk+1)+μ12∥1l-Yl(Xlβk+1+β0k+11l)-hk+1∥22.In order to solve (16), we need the following Proposition [22].Proposition 2.
Letsλ(w)=argminx∈ℝλx++0.5∥x-w∥22 where λ>0. Then
(17)sλ(w)={w-λw>λ,00≤w≤λ,ww<0.Combined with Proposition2 and
(18)∥uhk∥222μ1+(uhk)T(1l-Yl(Xlβk+1+β0k+11l)-hk+1)+0.5μ1∥1l-Yl(Xlβk+1+β0k+11l)-hk+1∥22=0.5μ1∥uhkμ1+1l-Yl(Xlβk+1+β0k+11l)-hk+1∥22,we can updatehk+1 according to Corollary 3.Corollary 3.
The update ofhk+1 in (16) is equivalent to
(19)hk+1=SC/μ1(1l+uhkμ1-Yl(Xlβk+1+β0k+11l)),
where Sλ(w)=(sλ(w1),…,sλ(wl)).For the third equation in (13), it is equivalent to solving (20):
(20)ak+1=argminaC*∑i=l+1l+2u(ai)++(uak)T(1u-Yu(Xuβk+1+β0k+11u)-ak+1)+μ22∥1u-Yu(Xuβk+1+β0k+11u)-ak+1∥22.Combined with Proposition2 and
(21)∥uak∥222μ1+(uak)T(1u-Yu(Xuβk+1+β0k+11u)-ak+1)+0.5μ2∥1u-Yu(Xuβk+1+β0k+11u)-ak+1∥22=0.5μ2∥uakμ2+1u-Yu(Xuβk+1+β0k+11u)-ak+1∥22,we can updateak+1 according to Corollary 4.Corollary 4.
The update ofak+1 in (20) is equivalent to
(22)ak+1=SC*/μ2(1u+uakμ2-Yu(Xuβk+1+β0k+11u)),
where Sλ(w)=(sλ(w1),…,sλ(w2u)).For the fourth equation in (13), it is equivalent to solving
(23)bk+1=argminbC*∑i=l+1l+2u(bi)++(ubk)T(s1u-Yu(Xuβk+1+β0k+11u)-bk+1)+μ32∥s1u-Yu(Xuβk+1+β0k+11u)-bk+1∥22.
In order to solve (23), we need the following proposition.Proposition 5.
Letgλ(w)=argminx∈ℝλx++0.5∥x-w∥22, where λ<0. Then
(24)gλ(w)={w-λw>0,ww<0.Proof.
The functionλx++0.5∥x-w∥22 is strongly convex, so it has a unique solution. Therefore, by the subdifferential calculus [23], gλ is the unique minimizer of the following equation:
(25)0∈λ∂(x+)+x-w,
where ∂(x+) is the subdifferential of the function x+. According to [23], ∂(x+) can be expressed as
(26)∂(x+)={1x>0,{p:p∈[0,1]}x=0,0x<0.
With (25) and (26), we can get the desired result.
Then, combined with Proposition5 and
(27)∥ubk∥222μ3+(ubk)T(s1u-Yu(Xuβk+1+β0k+11u)-bk+1)+0.5μ3∥s1u-Yu(Xuβk+1+β0k+11u)-bk+1∥22=0.5μ3∥ubkμ3+s1u-Yu(Xuβk+1+β0k+11u)-bk+1∥22,
we can update bk+1 according to Corollary 6.Corollary 6.
The update ofbk+1 in (23) is equivalent to
(28)bk+1=G-C*/μ3(s1u+ubkμ3-Yu(Xuβk+1+β0k+11u)),
where Gλ(w)=(gλ(w1),…,gλ(w2u)).For the fifth equation in (13), it is equivalent to solving
(29)tk+1=argmintλ1∥tk+1∥1+(vk)T(βk+1-tk+1)+0.5μ4∥βk+1-tk+1∥22.Solving (29) can be done efficiently using soft threshold, and we can update tk+1 according to Corollary 7.Corollary 7.
The update oftk+1 in (29) is
(30)tk+1=Tλ1/μ4(vkμ4+βk+1),
where Tλ(w)=(tλ(w1),…,tλ(wp)), and tλ(w)=sgn(w)max{0,|w|-λ}.According to the theory of ADMM,∥s1k∥2, ∥s2k∥2, ∥s3k∥2, and ∥s4k∥2 must be small below some certain threshold δ. Considering the auxiliary variables in (11), we expect that ∥1l-Yl(Xlβ+β01l)-h∥2,∥1u-Yu(Xuβ+β01u)-a∥2, ∥s1u-Yu(Xuβ+β01u)-b∥2, and ∥β-t∥2 also must be small. Therefore, in our experiment, algorithm for SENFS stops whenever
(31)∥s1k∥2<δ,∥s2k∥2<δ,∥s3k∥2<δ,∥s4k∥2<δ,∥1l-Yl(Xlβ+β01l)-h∥2<lδ,∥1u-Yu(Xuβ+β01u)-a∥2<2uδ,∥s1u-Yu(Xuβ+β01u)-b∥2<2uδ,∥β-t∥2<pδ.Finally, we can get the algorithm for SENFS. The detailed procedure of the algorithm ADMM for SENFS is summarized in Algorithm8 as follows.Algorithm 8.
ADMM algorithm for SENFS.Input. Labeled data set {xi,yi}i=1l; unlabeled data set {xi}i=l+1n; tuning parameters λ1 and λ2; regularization parameter C.Output. Selected feature set.Step  1. Initialize β0,β00,h0,a0,b0,t0,uh0,ua0,ub0,v0, and q0.Step  2. If (31) is satisfied, go to Step  3; otherwise,
(1)
updateβk+1 and β0k+1 according to (15);(2)
updatehk+1, ak+1, bk+1, and tk+1 according to Corollaries 3–7, respectively;(3)
updateuhk+1,uak+1,ubk+1,vk+1, and qk+1 according to (12).Step  3. Get the best feature subset according to βjk+1,j=1,…,p. If βjk+1=0, the corresponding jth feature is abandoned; otherwise, it is selected as an important feature.


## 3.2. Convergence Analysis and Computational Cost

The convergence property of Algorithm8 can be derived from the theory of the alternating direction method of multipliers. According to the standard convergence theory of ADMM, Algorithm 8 satisfies the dual variable convergence [24]. So Theorem 9 holds.Theorem 9.
Suppose that(β*,β0*) is one of solution of (5). Then the following property holds:(32)C∑i=1lH1(yi(xiβk+β0k))+C*∑i=l+1l+2u(H1(yi(xiβk+β0k))-Hs(yi(xiβk+β0k)))+λ1∥βk∥1+λ2∥βk∥222=C∑i=1lH1(yi(xiβ*+β0*))+C*∑i=l+1l+2u(H1(yi(xiβ*+β0*))-Hs(yi(xiβ*+β0*)))+λ1∥β*∥1+λ2∥β*∥222.As for the computational issue, it is hard to predict the computational cost because it depends on the all the penalty parameters. According to our experience, we only need to iterate a few hundred iterations to get a reasonable result. On the other hand, the efficiency of Algorithm8 lies mainly on whether we can quickly solve the linear equations (15). And the computational cost for solving (15) is O(l2p+4u2p).


## 3.3. Varying Penalty Parameter

In order to make performance less dependent on the initial choice of the penalty parameter, it is necessary to use different penalty parameters. According to our experiment experience, the penalty parametersμ1,μ2,μ3, and μ4 have a huge influence on the performance and the number of iterations involved, so adaptive selections of them are performed.Forμ1, let f(β,β0)=C∑i=1l(hi)++C*∑i=l+1l+2u(H1(yi(xiβ+β0))-Hs(yi(xiβ+β0)))+λ1∥β∥1+0.5λ2∥β∥22, and the constraint conditions are h=1l-Yl(Xlβ+β01l) and the constraint of (3). The optimization task (6) is equivalent to
(33)W(β,β0)=f(β,β0)+uhT(1l-Yl(Xlβ+β01l)-h)+q(r-1u∑i=l+1n(xiβ+β0))+μ12∥1l-Yl(Xlβ+β01l)-h∥22+μ52∥r-1u∑i=l+1n(xiβ+β0)∥22.The necessary optimality conditions for the problem (6) are dual feasibility as
(34)0∈∂f(β*,β0*)∂β*-XlTYlTuh*-q*u∑i=l+1nxiT.
Since βk+1 minimizes W(βk+1,β0k+1,uhk,qk) by definition, we have that
(35)0∈∂f(βk+1,β0k+1)∂βk+1-XlTYlT(uhk-μ1(1l-Yl(Xlβk+1+β0k+11l)-hk))-qku∑i=l+1nxiT-μ5u×∑i=l+1nxiT(r-1u∑i=l+1n(xiβk+1+β0k+1))=∂f(βk+1,β0k+1)∂βk+1-XlTYlTuhk+1-qk+1u×∑i=l+1nxiT+μ1XlTYlT(hk-hk+1).Compared with (34), (35) means that the quantity μ1XlTYlT(hk-hk+1) can be viewed as a residual for (34), and let s1k+1=μ1XlTYlT(hk-hk+1).Forμ2, let f(β,β0) = C∑i=1lH1(yi(xiβ+β0)) + C*∑i=l+1l+2u((ai)+-Hs(yi(xiβ+β0)))+λ1∥β∥1+0.5λ2∥β∥22, and the constraint conditions are a=1u-Yu(Xuβ+β01u) and the constraint of (3). Through the same solving process as parameter μ1, we can get the residual s2k+1=μ2k+1XuTYuT(ak-ak+1). Similarly, we can get the residual s3k+1=μ3k+1XuTYuT(bk-bk+1) for parameter μ3 and s4k+1=μ4k+1XuTYuT(tk+1-tk) for parameter μ4. With these residuals, we can get a simple scheme to update μ1,μ2,μ3, and μ4, respectively, according to Corollary 10.Corollary 10.
The update ofμ1,μ2,μ3,μ4 is(36)μ1k+1={τincrμ1kif∥1l-Yl(Xlβk+β0k1l)-hk∥2>θ∥s1k∥2μ1kτdecrif∥s1k∥2>θ∥1l-Yl(Xlβk+β0k1l)-hk∥2μ1kotherwise,μ2k+1={τincrμ2kif∥1u-Yu(Xuβk+β0k1u)-ak∥2>θ∥s2k∥2μ2kτdecrif∥s2k∥2>θ∥1u-Yu(Xuβk+β0k1u)-ak∥2μ2kotherwise,μ3k+1={τincrμ3kif∥s1u-Yu(Xuβk+β0k1u)-bk∥2>θ∥s3k∥2μ3kτdecrif∥s3k∥2>θ∥s1u-Yu(Xuβk+β0k1u)-bk∥2μ3kotherwise,μ4k+1={τincrμ4kif∥β-t∥2>θ∥s4k∥2μ4kτdecrif∥s4k∥2>θ∥β-t∥2μ4kotherwise,where τincr>1,τdecr>,  and θ>1 are parameters. Typical choices might be τincr=τdecr=2 and θ=10.


## 4. Experimental Evaluation

This section examines the performance of SENFS with respect to its feature selection and test error on simulated data and six benchmark data sets. In order to evaluate the effectiveness of SENFS, we compare SENFS with an existing semisupervised feature selection algorithm: Spectral [10], and a supervised feature selection algorithm: DrSVM [11], which also has the characteristics of grouping effect. On the other hand, in order to evaluate the quality of selected features, SVM was executed on these selected features. The experiments are run on a desktop with Pentium(R) 2.0 G CPU, 1.99 G main memory. The programs are compiled in Windows system with Matlab in version R2009a.The limited number of samples prohibits having enough and independent training and testing data for performance evaluation. It is very common to apply accross-validation (CV) in this scenario. We used 5-fold CV: we partitioned the data set into five complementary subsets of equal size. Four subsets were used as training data; the remaining subset served as test data. We repeated this process five times such that each of the five subsets was used exactly once as test data. To get more reliable estimate, we performed the 5-fold CV for 10 times and the experimental results are average results over test data sets. Moreover, finding the appropriate value of the tuning parameter pairλ1 and λ2 is essential for the performance of SENFS. We employed 10-fold CV over a large grid.


### 4.1. Simulation

We evaluate the performance of SENFS using two parameters: the correlation between relevant features denoted byρ, the number of labeled samples, and the degree of overlapping among classes denoted by d. Consider 2-class problem in which the samples are lying in a p dimensional space with the first 10 dimensional being relevant to classification and the remaining features being noise, where the correlation between the first 10 features is ρ. The number of samples is 300 with p=500. For the samples from +1 class, they are sampled from a normal distribution with mean and covariance as follows:
(37)α+=(d,…,d︸10,0,…,0︸p-10),∑=(∑10×10*010×(p-10)0(p-10)×10I(p-10)×(p-10)),
where the diagonal elements of ∑* are 1 and the off-diagonal elements are all equal to ρ. The −1 class has a similar distribution expect that its mean is:
(38)α-=(-d,…,-d︸10,0,…,0︸p-10).To evaluate the effect of the correlation between relevant features, SENFS is compared with Spectral and DrSVM, measured by the number of selected features with two labeled samples andd=1. The results are summarized in Table 1. As shown in Table 1, on this simulated data, when the relevant features are highly correlated (e.g., ρ=0.9), Spectral and DrSVM tend to keep only a small subset of the relevant correlated variables and overlook the others, while the SENFS tends to identify all of them, due to the grouping effect. These three methods seem to work well in removing irrelevant features.Table 1
Comparisons of selected features and their standard errors (in parenthesis).Frelevant is the number of selected relevant features and Fnoise is the number of selected noise features.
ρ
SENFS
Spectral
DrSVM
F
relevant
F
noise
F
relevant
F
noise
F
relevant
F
noise
0
6.2 (0.28)
5.6 (0.28)
4.75 (0.22)
5.9 (0.29)
5.41 (0.27)
5.7 (0.15)
0.5
7.2 (0.01)
3.9 (0.05)
6.88 (0.1)
6.2 (0.24)
6.83 (0.31)
5.4 (0.17)
0.9
8.9 (0.04)
2.1 (0.11)
8.32 (0.09)
4.15 (0.15)
8.1 (0.08)
4.55 (0.22)The effects of the number of labeled samples on test error over the top 10 selected features are summarized in Figure1 with d=1 and ρ=0.9. As can be seen, the test errors of SENFS, Spectral, and DrSVM decrease with the increase of the number of labeled samples, but SENFS seems to achieve the best classification performance when the number of labeled samples is varying, which may imply that SENFS can make better use of the labeled samples than spectral and DrSVM. The supervised feature selection method DrSVM achieves the worst results because it only relies on the few labeled samples and discards the large amount of unlabeled samples.Figure 1
Test error versus the number of labeled samples.In Table2, the effect of the degree of overlapping among classes on test error over the top 5 selected features is evaluated with two labeled samples and d=1 and ρ=0.9, also reporting the typical computational time of our experimental campaign. As we can see, SENFS seems to have the best prediction performance. When d is small, the two classes overlap largely and in this case, other methods achieved worse performance compared with SENFS. However, SENFS, solving the programming problem (6) needing an iterative procedure, requires more computational time than the other methods as you can see in Table 2. It is noted that the absolute values are not as important as the relative differences between the individual methods.Table 2
Comparisons of test errors, computational time needed, and their standard errors (in parenthesis).
d
SENFS
Spectral
DrSVM
Test error
Time
Test error
Time
Test error
Time
1
9.4 (0.12)%
6.7 (1.1)
15.7 (0.27)%
5.5 (1.0)
17.1 (0.31)%
6.1 (1.2)
2
8.7 (0.13)%
6.4 (0.2)
14.2 (0.14)%
5.3 (0.1)
16.2 (0.27)%
5.8 (0.2)
3
7.5 (0.02)%
5.9 (0.4)
12.3 (0.07)%
4.7 (0.1)
14.6 (0.11)%
4.9 (0.2)


### 4.2. Application to Benchmark Data Sets

Several benchmark data sets are selected to test the performance of SENFS, which are used as benchmark data sets in [7, 8] to test the performances of semisupervised algorithms. These benchmark data sets consist of 9 semisupervised learning data sets. We did not test the SSL6, SSL8, and SSL9 data sets since the SSL6 data set includes six classes, the SSL8 data set contains too many samples (n is over one million) and the SSL9 data set has too many dimensions (p is over ten thousand). The names and characteristics of the left six data sets are given in Table 3.Table 3
Data sets used in the experiments.n, p, and l are the number of samples, features, and labeled samples, respectively.
Data set
n
p
l
Digit1
1500
241
10 or 100
USPS
1500
241
10 or 100
COIL2
1500
241
10 or 100
BCI
400
117
10 or 100
g241c
1500
241
10 or 100
g241n
1500
241
10 or 100In this study, we examine performance evaluation through 5-fold cross-validation that is, we randomly select four fifths of the unlabeled samples, plus all the labeled samples, for SENFS, Spectral, and DrSVM to select optimal feature subsets, while leaving the remaining one fifth for testing test error on the selected features using SVM, where all the labeled samples are used for training SVM. The results measured by test error are reported in Table4. As can be seen, SENFS outperforms the semisupervised and supervised feature selection methods on all the six data sets when l=10 and l=100. When l=10, Spectral performs the second best, on USPS, COIL2, and BCI data sets, while DrSVM performs the second best on Digit1, BCI, g241c and g241n data sets when l=100.Table 4
Comparisons of test errors and their standard errors (in parenthesis) on benchmark data sets.
Dataset
SENFS
Spectral
DrSVM
l
=
10
l
=
100
l
=
10
l
=
100
l
=
10
l
=
100
Digit1
15.1 (0.04)%
4.28 (0.12)%
17.7 (0.09)%
8.7 (0.15)%
21.35 (0.05)%
5.85 (0.16)%
USPS
21.17 (0.03)%
11.1 (0.24)%
29.87 (0.15)%
12.6 (0.31)%
31.8 (0.12)%
17.3 (0.3)%
COIL2
36.1 (1.04)%
13.6 (0.98)%
37.7 (1.3)%
16.9 (0.91)%
47.2 (0.8)%
31.2 (1.1)%
BCI
43.9 (0.23)%
33.8 (0.24)%
49.87 (0.15)%
42.1 (0.31)%
47.8 (0.12)%
36.7 (0.8)%
g241c
32.8 (1.14)%
24.9 (1.12)%
42.8 (1.29)%
32.7 (1.5)%
41.75 (1.1)%
26.0 (1.6)%
g241n
37.6 (0.83)%
24.3 (0.24)%
45.7 (0.3)%
33.6 (0.51)%
41.8 (0.32)%
25.7 (0.67)%


## 4.1. Simulation

We evaluate the performance of SENFS using two parameters: the correlation between relevant features denoted byρ, the number of labeled samples, and the degree of overlapping among classes denoted by d. Consider 2-class problem in which the samples are lying in a p dimensional space with the first 10 dimensional being relevant to classification and the remaining features being noise, where the correlation between the first 10 features is ρ. The number of samples is 300 with p=500. For the samples from +1 class, they are sampled from a normal distribution with mean and covariance as follows:
(37)α+=(d,…,d︸10,0,…,0︸p-10),∑=(∑10×10*010×(p-10)0(p-10)×10I(p-10)×(p-10)),
where the diagonal elements of ∑* are 1 and the off-diagonal elements are all equal to ρ. The −1 class has a similar distribution expect that its mean is:
(38)α-=(-d,…,-d︸10,0,…,0︸p-10).To evaluate the effect of the correlation between relevant features, SENFS is compared with Spectral and DrSVM, measured by the number of selected features with two labeled samples andd=1. The results are summarized in Table 1. As shown in Table 1, on this simulated data, when the relevant features are highly correlated (e.g., ρ=0.9), Spectral and DrSVM tend to keep only a small subset of the relevant correlated variables and overlook the others, while the SENFS tends to identify all of them, due to the grouping effect. These three methods seem to work well in removing irrelevant features.Table 1
Comparisons of selected features and their standard errors (in parenthesis).Frelevant is the number of selected relevant features and Fnoise is the number of selected noise features.
ρ
SENFS
Spectral
DrSVM
F
relevant
F
noise
F
relevant
F
noise
F
relevant
F
noise
0
6.2 (0.28)
5.6 (0.28)
4.75 (0.22)
5.9 (0.29)
5.41 (0.27)
5.7 (0.15)
0.5
7.2 (0.01)
3.9 (0.05)
6.88 (0.1)
6.2 (0.24)
6.83 (0.31)
5.4 (0.17)
0.9
8.9 (0.04)
2.1 (0.11)
8.32 (0.09)
4.15 (0.15)
8.1 (0.08)
4.55 (0.22)The effects of the number of labeled samples on test error over the top 10 selected features are summarized in Figure1 with d=1 and ρ=0.9. As can be seen, the test errors of SENFS, Spectral, and DrSVM decrease with the increase of the number of labeled samples, but SENFS seems to achieve the best classification performance when the number of labeled samples is varying, which may imply that SENFS can make better use of the labeled samples than spectral and DrSVM. The supervised feature selection method DrSVM achieves the worst results because it only relies on the few labeled samples and discards the large amount of unlabeled samples.Figure 1
Test error versus the number of labeled samples.In Table2, the effect of the degree of overlapping among classes on test error over the top 5 selected features is evaluated with two labeled samples and d=1 and ρ=0.9, also reporting the typical computational time of our experimental campaign. As we can see, SENFS seems to have the best prediction performance. When d is small, the two classes overlap largely and in this case, other methods achieved worse performance compared with SENFS. However, SENFS, solving the programming problem (6) needing an iterative procedure, requires more computational time than the other methods as you can see in Table 2. It is noted that the absolute values are not as important as the relative differences between the individual methods.Table 2
Comparisons of test errors, computational time needed, and their standard errors (in parenthesis).
d
SENFS
Spectral
DrSVM
Test error
Time
Test error
Time
Test error
Time
1
9.4 (0.12)%
6.7 (1.1)
15.7 (0.27)%
5.5 (1.0)
17.1 (0.31)%
6.1 (1.2)
2
8.7 (0.13)%
6.4 (0.2)
14.2 (0.14)%
5.3 (0.1)
16.2 (0.27)%
5.8 (0.2)
3
7.5 (0.02)%
5.9 (0.4)
12.3 (0.07)%
4.7 (0.1)
14.6 (0.11)%
4.9 (0.2)


## 4.2. Application to Benchmark Data Sets

Several benchmark data sets are selected to test the performance of SENFS, which are used as benchmark data sets in [7, 8] to test the performances of semisupervised algorithms. These benchmark data sets consist of 9 semisupervised learning data sets. We did not test the SSL6, SSL8, and SSL9 data sets since the SSL6 data set includes six classes, the SSL8 data set contains too many samples (n is over one million) and the SSL9 data set has too many dimensions (p is over ten thousand). The names and characteristics of the left six data sets are given in Table 3.Table 3
Data sets used in the experiments.n, p, and l are the number of samples, features, and labeled samples, respectively.
Data set
n
p
l
Digit1
1500
241
10 or 100
USPS
1500
241
10 or 100
COIL2
1500
241
10 or 100
BCI
400
117
10 or 100
g241c
1500
241
10 or 100
g241n
1500
241
10 or 100In this study, we examine performance evaluation through 5-fold cross-validation that is, we randomly select four fifths of the unlabeled samples, plus all the labeled samples, for SENFS, Spectral, and DrSVM to select optimal feature subsets, while leaving the remaining one fifth for testing test error on the selected features using SVM, where all the labeled samples are used for training SVM. The results measured by test error are reported in Table4. As can be seen, SENFS outperforms the semisupervised and supervised feature selection methods on all the six data sets when l=10 and l=100. When l=10, Spectral performs the second best, on USPS, COIL2, and BCI data sets, while DrSVM performs the second best on Digit1, BCI, g241c and g241n data sets when l=100.Table 4
Comparisons of test errors and their standard errors (in parenthesis) on benchmark data sets.
Dataset
SENFS
Spectral
DrSVM
l
=
10
l
=
100
l
=
10
l
=
100
l
=
10
l
=
100
Digit1
15.1 (0.04)%
4.28 (0.12)%
17.7 (0.09)%
8.7 (0.15)%
21.35 (0.05)%
5.85 (0.16)%
USPS
21.17 (0.03)%
11.1 (0.24)%
29.87 (0.15)%
12.6 (0.31)%
31.8 (0.12)%
17.3 (0.3)%
COIL2
36.1 (1.04)%
13.6 (0.98)%
37.7 (1.3)%
16.9 (0.91)%
47.2 (0.8)%
31.2 (1.1)%
BCI
43.9 (0.23)%
33.8 (0.24)%
49.87 (0.15)%
42.1 (0.31)%
47.8 (0.12)%
36.7 (0.8)%
g241c
32.8 (1.14)%
24.9 (1.12)%
42.8 (1.29)%
32.7 (1.5)%
41.75 (1.1)%
26.0 (1.6)%
g241n
37.6 (0.83)%
24.3 (0.24)%
45.7 (0.3)%
33.6 (0.51)%
41.8 (0.32)%
25.7 (0.67)%


## 5. Conclusion

This paper has proposed a novel semisupervised feature selection algorithm based on SVM and the elastic net penalty. The whole methodology of SENFS and the solution path based on ADMM have been described in detail in this paper. The experimental results illustrate that SENFS can identify the relevant features and encourage highly correlated features to be selected or removed together.Future work will address how these selected features interpret their semantic relationship with the data they are selected from, which can be used for unknown data analysis, and extend SENFS to be suitable for multiclass case.



---

*Source: 416320-2013-12-04.xml*