# Discriminative Label Relaxed Regression with Adaptive Graph Learning

Authors: Jingjing Wang; Zhonghua Liu; Wenpeng Lu; Kaibing Zhang
Journal: Computational Intelligence and Neuroscience
 (2020)

---

## Abstract

The traditional label relaxation regression (LRR) algorithm directly fits the original data without considering the local structure information of the data. While the label relaxation regression algorithm of graph regularization takes into account the local geometric information, the performance of the algorithm depends largely on the construction of graph. However, the traditional graph structures have two defects. First of all, it is largely influenced by the parameter values. Second, it relies on the original data when constructing the weight matrix, which usually contains a lot of noise. This makes the constructed graph to be often not optimal, which affects the subsequent work. Therefore, a discriminative label relaxation regression algorithm based on adaptive graph (DLRR_AG) is proposed for feature extraction. DLRR_AG combines manifold learning with label relaxation regression by constructing adaptive weight graph, which can well overcome the problem of label overfitting. Based on a large number of experiments, it can be proved that the proposed method is effective and feasible.


---

## Body

## 1. Introduction

Information technology is developing rapidly and has become a hot topic in recent years. We can get a lot of information from the data, but the dimension of the data is getting higher and higher [1]. On the one hand, the increase of data dimension makes the description of data samples more comprehensive and provides more bases for further analysis and processing of data samples [2]. On the other hand, the increase in the number of features will bring more redundant features, which not only put forward great requirements for hardware and software equipment to complete data processing but also directly affect the reliability and effectiveness of data analysis and processing results [3]. In order to effectively analyze and process the data, by mapping (or transforming) the original data to the low-dimensional space, the features that best reflect the intrinsic nature of the sample data can be obtained. This process is called feature extraction or data dimensionality reduction [4]. The core task of feature extraction or data dimensionality reduction is how to find out which features are most effective for the final data analysis and processing and how to retain the useful information in the data transformation process to the maximum extent. Feature extraction is always a key problem in pattern recognition, which will directly affect the design and performance of the classifier [5–7]. Feature extraction can not only reduce the dimension of data but also retain useful information in the data. It is also widely used in the processing and analysis of complex data.In recent years, the feature extraction method based on manifold learning has made remarkable achievements in nonlinear data analysis and research and has been widely used in nonlinear data processing and analysis. According to the current popular learning methods, the nonlinear characteristics and manifold structures of the sample data are usually distributed in low-dimensional space [8–11], and the traditional nonlinear subspace method is difficult to describe and extract the information effectively [12–14]. At present, the popular learning method is to obtain the embedded mapping of low-dimensional manifold structure and high-dimensional feature manifold of the sample and then complete the feature extraction of nonlinear information in the sample data [15–18].Discriminative Fisher embedding dictionary learning (DFEDL) algorithm simultaneously establishes Fisher embedding models on learned atoms and coefficients [19, 20]. In 2000, Tenenbaum from Stanford University published the first manifold learning method based on isometric mapping (ISOMAP) [21] in Science. ISOMAP method is a globally optimized method to preserve the manifold structure between data effectively by maintaining the geometric relationship between sample data (also known as geodesic distance). Roweis proposed a locally linear embedding (LLE) method in literature [22]. By constructing the reconstruction weight between each sample and the neighboring samples, this method can better preserve the manifold features between the neighboring samples when embedding in low-dimensional space [23–26]. Based on Roweis and Tenenbaum’s basic research on manifold learning, researchers proposed some improved feature extraction methods, including Laplacian eigenmap (LE) [27], local learning projection (LLP) [28], linear representation-based classifiers (CRC) [29], and linear regression classification (LRC) [30].Due to the validity of the least-squares regression method in data analysis and the completeness of statistical theory, it is widely used as a basic tool in many machine learning problems including discriminant analysis, clustering, multiview learning, multilabel classification, and semisupervised learning. Sun et al. [31] proposed a least-squares regression model based on generalized eigenvalue decomposition, and Suzanna et al. [32] proposed a weighted least-squares regression model. When solving the multilabel classification problem with least-squares regression, if the data points belong to different categories, then should be considered as the increase of the distance between the data. For example, in order to increase the distance between different types of data points, Leski [33] proposed a quadratic approximation least-square regression model based on misclassification error. However, this model only considers two categories of classification problems. In multilabel classification, the distances among data points from different classes are also expected to be as large as possible [34, 35], as well as in multilabel feature selection. Therefore, multiple least-squares regression models proposed by Leski [33] can be used simultaneously, but the time cost of algorithm implementation will be relatively high.The traditional label relaxation regression algorithm directly fits the original data without considering the local structure information of the data [36–38]. While the label relaxation regression algorithm for graph regularization considers local geometric information, its performance is largely dependent on graph construction [39, 40]. However, there are two defects in the construction of traditional graphs: first, it is largely influenced by the parameter values; second, it relies on the original data when constructing the weight matrix, which usually contains a lot of noise [41]. This makes the constructed graph often not to be optimal, which affects the subsequent work. To guarantee the global optima of the latent representation and graphs of all views, we integrate the graph completion and common representation learning into a joint optimization framework. [42–44]. Therefore, it is proposed to combine manifold learning with label relaxation regression and construct weight graph through adaptive method. At the same time, local identification information is added on the basis of original linear identification analysis so that the projection learning can grasp the local identification information to expand the identification of the projection. A label relaxation regression algorithm for image classification and feature extraction based on adaptive graph is proposed. In this paper, the main innovation points are as follows:(1)
The adaptive graph construction can rightly capture the local structure information of the data(2)
The problem of overfitting is avoided by introducing adaptive graph into the objective function of label relaxation regression(3)
In order to take full advantage of discriminant information, the global discriminant information based on the LDA is consideredThe rest of this paper is arranged as follows: Section2 briefly reviews DLSR and structured optimal graph. In Section 3, discriminative label relaxed regression with adaptive graph learning (DLRR_AG) is described in detail, and the convergence of the proposed algorithm is proved. Section 4 mainly provides a lot of experiments to verify the performance of the proposed algorithm. The last Section gives the conclusion.


## 2. Related Work

### 2.1. Discriminative Least-Squares Regression (DLSR) Algorithm

The classification training samples are givenN numbers, and these samples xi,yii=1N fall into CC≥2 classes, where yi∈1,2…,c is the class label of xi, and xi is a data point in Rm. The linear equation can be satisfied as follows:(1)XW+eNtT≈Y,where X=x1,x2,…,xnT∈RN×m and Y=fy1,fy2,…,fyNT∈RN×C. For the ith class, i=1,2,…,c, fi=0,…0,1,0,…,0︸i−1T∈Rc, W is a transformation matrix in Rm×c, t is a translation vector in Rc, and eN=1,1,…,1∈RN is a vector with all 1 s.Each column vector in Y is of a binary regression type, with the target of class jth being “+1” and the target of the rest being “0.” We can drag these binary outputs far away along two opposite directions. That is, with a positive slack variable, we hope the output will become for the sample grouped into “1” and for the sample grouped into “0.” This treatment can help enlarge the distance between the classes and mapping data point.LetB∈RN×C be a constant matrix, in which the ith row and jth column element Bij is defined as(2)Bij=+1,ifyi=j,−1,otherwise.Each element inB corresponds to the direction of the drag. Performing the above ε drag on each element of Y, matrix M∈RN×C records these ε. The residual can be obtained as follows:(3)XW+eNtT−Y+B⊗M=0,where ⊗ is the Hadamard matrix product operator.The objective function of DLSR can be obtained as follows:(4)minW,t,MXW+eNtT−Y−B⊗MF2+λWF2,s.t.M≥0,where λ is a positive regularization parameter. By solving the optimization problem of equation (4), the optimal W and t can be obtained:(5)W=XTHX+λIm−1XTHR,t=RTeN−WTXTeNN,where Im is a m×m identity matrix and H=IN−1/NeNeNT, in which IN is a N×N identity matrix, and R=Y+B⊗M∈RN×C.


### 2.2. Structured Optimal Graph

It is well known that the data in high-dimension space is usually embedded in low-dimensional manifold [40]. It is a key success factor to preserve local manifold structure information for graph-based methods. The local manifold structure is captured by the similarity matrix, which determines the ultimate performance of graph-based methods.Suppose that there areN training samples from c classes which are denoted by X=x1,x2,…,xN∈RN×m, where N is the number of samples used for classifier training, while all N samples are used for determination of S, where m is the dimension of observed data, and xi=i=1,2,…,N∈Rm×1 is the i-th sample for sample set X. For any sample xi, it can be connected by all other samples with probability sij, where sij is an element of similarity matrix S∈RN×N. If the distance of two samples is closer, the greater their probability (or similarity) will be, and vice versa. Therefore, the similarity sij between xi and xj is inversely proportional to their distance. The similarity sij can be obtained by solving the following equation:(6)min∑i,jxi−xj22Sij+αSij2,s.t.∀i,siT1=1,0≤sij≤1,where Si∈RN×1 is a vector whose jth element is sij in similarity matrix S and α is a regularization parameter. The second item in equation (6) is mainly to avoid trivial solutions.It is the ideal state for each sample to includec-nearest-neighbor numbers. That is to say, each Siji=1,2,…,N in similarity matrix S has exact c connected components. In fact, the obtained similarity matrix S in equation (6) does not meet this requirement in most cases. The problem can be solved as follows. The spectral analysis has an important equation as follows:(7)∑i,jfi−fj22Sij=2TrFTLSF,where F=f1,f2,…,fN∈RN×C is a class label matrix corresponding to the observed data X, LS=D−ST+S/2 is the Laplacian matrix, and matrix D is a diagonal matrix whose ith entry is ∑jSij+Sij/2.If the rank of Laplacian matrixLS equals to N−C, namely, rankLS=N−C, the obtained similarity matrix S will include exact C connected components [45]. By combining the constraint to equation (6), equation (6) is written as(8)min∑i,jxi−xj22Sij+αSij2.In order to solve equation (6), the ith smallest eigenvalue of Laplacian matrix LS is denoted by σiLS. It is well-known that the solutions of positive semidefinite matrix are more than zero. Laplacian matrix LS is positive semidefinite, so σiLS≥0. Based on rankLS=N−C, ∑i=1CσiLs=0 is satisfied [45]. According to KyFan’s Theorem [46], we have(9)∑i=1CσiLs=minFTF=ITrFTLSF.Therefore, based on equation (9), equation (8) can be rewritten as(10)min∑i.jxi−xj22sij+αsij2+2λTrFTLSF,s.t.∀i,siT1=1,0≤sij≤1,FTF=I.


## 2.1. Discriminative Least-Squares Regression (DLSR) Algorithm

The classification training samples are givenN numbers, and these samples xi,yii=1N fall into CC≥2 classes, where yi∈1,2…,c is the class label of xi, and xi is a data point in Rm. The linear equation can be satisfied as follows:(1)XW+eNtT≈Y,where X=x1,x2,…,xnT∈RN×m and Y=fy1,fy2,…,fyNT∈RN×C. For the ith class, i=1,2,…,c, fi=0,…0,1,0,…,0︸i−1T∈Rc, W is a transformation matrix in Rm×c, t is a translation vector in Rc, and eN=1,1,…,1∈RN is a vector with all 1 s.Each column vector in Y is of a binary regression type, with the target of class jth being “+1” and the target of the rest being “0.” We can drag these binary outputs far away along two opposite directions. That is, with a positive slack variable, we hope the output will become for the sample grouped into “1” and for the sample grouped into “0.” This treatment can help enlarge the distance between the classes and mapping data point.LetB∈RN×C be a constant matrix, in which the ith row and jth column element Bij is defined as(2)Bij=+1,ifyi=j,−1,otherwise.Each element inB corresponds to the direction of the drag. Performing the above ε drag on each element of Y, matrix M∈RN×C records these ε. The residual can be obtained as follows:(3)XW+eNtT−Y+B⊗M=0,where ⊗ is the Hadamard matrix product operator.The objective function of DLSR can be obtained as follows:(4)minW,t,MXW+eNtT−Y−B⊗MF2+λWF2,s.t.M≥0,where λ is a positive regularization parameter. By solving the optimization problem of equation (4), the optimal W and t can be obtained:(5)W=XTHX+λIm−1XTHR,t=RTeN−WTXTeNN,where Im is a m×m identity matrix and H=IN−1/NeNeNT, in which IN is a N×N identity matrix, and R=Y+B⊗M∈RN×C.


## 2.2. Structured Optimal Graph

It is well known that the data in high-dimension space is usually embedded in low-dimensional manifold [40]. It is a key success factor to preserve local manifold structure information for graph-based methods. The local manifold structure is captured by the similarity matrix, which determines the ultimate performance of graph-based methods.Suppose that there areN training samples from c classes which are denoted by X=x1,x2,…,xN∈RN×m, where N is the number of samples used for classifier training, while all N samples are used for determination of S, where m is the dimension of observed data, and xi=i=1,2,…,N∈Rm×1 is the i-th sample for sample set X. For any sample xi, it can be connected by all other samples with probability sij, where sij is an element of similarity matrix S∈RN×N. If the distance of two samples is closer, the greater their probability (or similarity) will be, and vice versa. Therefore, the similarity sij between xi and xj is inversely proportional to their distance. The similarity sij can be obtained by solving the following equation:(6)min∑i,jxi−xj22Sij+αSij2,s.t.∀i,siT1=1,0≤sij≤1,where Si∈RN×1 is a vector whose jth element is sij in similarity matrix S and α is a regularization parameter. The second item in equation (6) is mainly to avoid trivial solutions.It is the ideal state for each sample to includec-nearest-neighbor numbers. That is to say, each Siji=1,2,…,N in similarity matrix S has exact c connected components. In fact, the obtained similarity matrix S in equation (6) does not meet this requirement in most cases. The problem can be solved as follows. The spectral analysis has an important equation as follows:(7)∑i,jfi−fj22Sij=2TrFTLSF,where F=f1,f2,…,fN∈RN×C is a class label matrix corresponding to the observed data X, LS=D−ST+S/2 is the Laplacian matrix, and matrix D is a diagonal matrix whose ith entry is ∑jSij+Sij/2.If the rank of Laplacian matrixLS equals to N−C, namely, rankLS=N−C, the obtained similarity matrix S will include exact C connected components [45]. By combining the constraint to equation (6), equation (6) is written as(8)min∑i,jxi−xj22Sij+αSij2.In order to solve equation (6), the ith smallest eigenvalue of Laplacian matrix LS is denoted by σiLS. It is well-known that the solutions of positive semidefinite matrix are more than zero. Laplacian matrix LS is positive semidefinite, so σiLS≥0. Based on rankLS=N−C, ∑i=1CσiLs=0 is satisfied [45]. According to KyFan’s Theorem [46], we have(9)∑i=1CσiLs=minFTF=ITrFTLSF.Therefore, based on equation (9), equation (8) can be rewritten as(10)min∑i.jxi−xj22sij+αsij2+2λTrFTLSF,s.t.∀i,siT1=1,0≤sij≤1,FTF=I.


## 3. Discriminative Label Relaxation Regression Algorithm Based on Adaptive Graph (DLRR_AG)

In this section, the motivation of our DLRR_AG is firstly introduced. Then, the optimum solution of DLRR_AG is given.


### 3.1. The Motivation of DLRR_AG

Traditional label relaxation regression algorithms directly fit the original data, which often results in overfitting. In general, to overcome overfitting, a regularization term is added to the target equation, and a regularization factor is used to balance the target equation and regularization term. In addition to this one, maintaining the information of local manifold structure plays a very important role in improving classification or clustering. There are two kinds of classical nearest-neighbor graphs, one is k-nearest-neighbor graph, and the other isε-nearest-neighbor graph. A large part of graph-based algorithms rely on these two methods to preserve local manifold structure information. However, two problems often occur when these two methods are used. First, the performance of graph learning is greatly affected by the parameter k or ε, the results of taking different parameter values are sometimes far apart, and the optimal value is not easy to determine, which requires a lot of experiments to obtain, which consumes a lot of time. Second, the traditional graph construction method requires two complicated steps: first, the corresponding weighted matrix should be constructed in adjacent graphs, and then the relaxation regression should be carried out. However, once the weighted matrix is generated from the most primitive observation data, it will not change any more. There is no flexibility. This kind of weighted matrix generated in advance is not practical in practical application, because the original observation data often contain a lot of errors, which will lead to the destruction of the local manifold structure. To solve this problem, we propose a relaxation regression algorithm for adaptive graph. The objective function of the algorithm is described as follows:(11)minW,MXW−Y−B⊗MF2+∑i.jWTxi−WTxj22sij+αsij2+2λTrFTLSF,s.t.M≥0,∀i,siT1=1,0≤sij≤1,FTF=I.In order to take advantage of intraclass discriminative information, the discriminant information based on the LDA is introduced into the objective function. Equation (11) can be rewritten as(12)minW,MXW−Y−B⊗MF2+∑i.jWTxi−WTxj22sij+αsij2+2λTrFTLSF+γTrWTSw−SbW,s.t.M≥0,∀i,siT1=1,0≤sij≤1,FTF=I,where Sw and Sb are the within-class scatter matrix and between-class scatter matrix, respectively.


### 3.2. Optimization of DLRR_AG

Equation (12) of the objective function is convex, so it is difficult to get the global optimal solution. Therefore, we can obtain the local optimal solution through continuous iteration. Because the target function contains four different variables, optimization solution (12) is not directly available; it requires an iterative solution to this problem (12). We propose an iterative algorithm to update the rules to solve these problems.


#### 3.2.1. Fixing W, M, and F to Update S

When other variables are fixed, exceptS, equation (12) can be transformed into(13)min∑i.jWTxi−WTxj22sij+αsij2+2λTrFTLSF,s.t.∀i,siT1=1,0≤sij≤1.According to equation (7), equation (13) can be rewritten as(14)min∑i.jWTxi−WTxj22sij+αsij2+λ∑i,jfi−fj22Sij,s.t.∀i,siT1=1,0≤sij≤1.Because it is independent for the similarity vector of each data point, we can solve the optimal problem for each sample as follows:(15)min∑i.jWTxi−WTxj22sij+αsij2+λ∑i,jfi−fj22Sij,s.t.∀i,siT1=1,0≤sij≤1.Letmij=WTxi−WTxj22, nij=fi−fj22, and dij=|mij+λnij; equation (15) can be rewritten as(16)minsi+12αdi22,s.t.siT1=1,0≤Sij≤1.


#### 3.2.2. Fixing S, W, and M to Update F

When other variables are fixed, exceptF, equation (12) can be transformed into(17)minTrFTLSF,s.t.FTF=I.The optimal solution ofF is formed from the eigenvectors of the c minimum eigenvalues in the LS.


#### 3.2.3. Fixing S, W, and F to Update M

When other variables are fixed, exceptM, equation (12) can be transformed into(18)minXW−Y−B⊗M22,s.t.M≥0.Let us now consider optimization in terms ofM∈RN×C. Given W and T, and let P=XW−Y record the regression error of n data points, then the optimization problem can be solved from the following aspects:(19)minP−B⊗MF2,s.t.M≥0.According to the square of matrix Frobenius norm, the fact that an element can be decoupled, (10) can be decoupled equivalently into n×c subproblems. For the ith row of the matrix and the jth column element Mij, we have(20)minMijPij−BijMijF2,s.t.M≥0,where Pij and Bij are the ith row and jth elements of P and B, respectively.Note thatBij2=1. Thus, we have Pij−BijMij2=Bij−PijMij2. Then, the optimization problem of equation (20) can be rewritten as(21)minMijBijPij−Mij2,s.t.Mij≥0.Obviously, the optimal solution of equation (21) is given as follows:(22)M=maxB⊗P,0.


#### 3.2.4. Fixing S, M, and F to Update W

Equation (12) is a constrained convex optimization problem. According to the properties of convex optimization, the local optimal solution is also the optimal solution of the whole. Next, this paper uses the iterative method to solve the optimal solution of equation (12).To solve W, given M, equation (12) is an unconstrained convex optimization problem for W. You just take the derivative of that and you set the derivative to 0 and you get W.When other variables fix, exceptW, equation (12) can be transformed into(23)minWXW−Y−B⊗MF2+∑i.jWTxi−WTxj22+γtrWTSw−SbW.LetN=Y+B⊗M, then the problem in (23) can be transformed into the following problem:(24)minWXW−NF2+λTrWTXLXTW+γtrWTSw−SbW=TrWTXTXW−WTXTN+λTrWTXLXTW+γtrWTSw−SbW=TrWTXTX+λXLXT+γSw−SbW−WTXTN⇒W=XTX+λXLXT+γSw−Sb−1XTN,where L=D−S is the graph Laplacian and D is a diagonal matrix whose diagonal elements Dii=∑jSij.


## 3.1. The Motivation of DLRR_AG

Traditional label relaxation regression algorithms directly fit the original data, which often results in overfitting. In general, to overcome overfitting, a regularization term is added to the target equation, and a regularization factor is used to balance the target equation and regularization term. In addition to this one, maintaining the information of local manifold structure plays a very important role in improving classification or clustering. There are two kinds of classical nearest-neighbor graphs, one is k-nearest-neighbor graph, and the other isε-nearest-neighbor graph. A large part of graph-based algorithms rely on these two methods to preserve local manifold structure information. However, two problems often occur when these two methods are used. First, the performance of graph learning is greatly affected by the parameter k or ε, the results of taking different parameter values are sometimes far apart, and the optimal value is not easy to determine, which requires a lot of experiments to obtain, which consumes a lot of time. Second, the traditional graph construction method requires two complicated steps: first, the corresponding weighted matrix should be constructed in adjacent graphs, and then the relaxation regression should be carried out. However, once the weighted matrix is generated from the most primitive observation data, it will not change any more. There is no flexibility. This kind of weighted matrix generated in advance is not practical in practical application, because the original observation data often contain a lot of errors, which will lead to the destruction of the local manifold structure. To solve this problem, we propose a relaxation regression algorithm for adaptive graph. The objective function of the algorithm is described as follows:(11)minW,MXW−Y−B⊗MF2+∑i.jWTxi−WTxj22sij+αsij2+2λTrFTLSF,s.t.M≥0,∀i,siT1=1,0≤sij≤1,FTF=I.In order to take advantage of intraclass discriminative information, the discriminant information based on the LDA is introduced into the objective function. Equation (11) can be rewritten as(12)minW,MXW−Y−B⊗MF2+∑i.jWTxi−WTxj22sij+αsij2+2λTrFTLSF+γTrWTSw−SbW,s.t.M≥0,∀i,siT1=1,0≤sij≤1,FTF=I,where Sw and Sb are the within-class scatter matrix and between-class scatter matrix, respectively.


## 3.2. Optimization of DLRR_AG

Equation (12) of the objective function is convex, so it is difficult to get the global optimal solution. Therefore, we can obtain the local optimal solution through continuous iteration. Because the target function contains four different variables, optimization solution (12) is not directly available; it requires an iterative solution to this problem (12). We propose an iterative algorithm to update the rules to solve these problems.


### 3.2.1. Fixing W, M, and F to Update S

When other variables are fixed, exceptS, equation (12) can be transformed into(13)min∑i.jWTxi−WTxj22sij+αsij2+2λTrFTLSF,s.t.∀i,siT1=1,0≤sij≤1.According to equation (7), equation (13) can be rewritten as(14)min∑i.jWTxi−WTxj22sij+αsij2+λ∑i,jfi−fj22Sij,s.t.∀i,siT1=1,0≤sij≤1.Because it is independent for the similarity vector of each data point, we can solve the optimal problem for each sample as follows:(15)min∑i.jWTxi−WTxj22sij+αsij2+λ∑i,jfi−fj22Sij,s.t.∀i,siT1=1,0≤sij≤1.Letmij=WTxi−WTxj22, nij=fi−fj22, and dij=|mij+λnij; equation (15) can be rewritten as(16)minsi+12αdi22,s.t.siT1=1,0≤Sij≤1.


### 3.2.2. Fixing S, W, and M to Update F

When other variables are fixed, exceptF, equation (12) can be transformed into(17)minTrFTLSF,s.t.FTF=I.The optimal solution ofF is formed from the eigenvectors of the c minimum eigenvalues in the LS.


### 3.2.3. Fixing S, W, and F to Update M

When other variables are fixed, exceptM, equation (12) can be transformed into(18)minXW−Y−B⊗M22,s.t.M≥0.Let us now consider optimization in terms ofM∈RN×C. Given W and T, and let P=XW−Y record the regression error of n data points, then the optimization problem can be solved from the following aspects:(19)minP−B⊗MF2,s.t.M≥0.According to the square of matrix Frobenius norm, the fact that an element can be decoupled, (10) can be decoupled equivalently into n×c subproblems. For the ith row of the matrix and the jth column element Mij, we have(20)minMijPij−BijMijF2,s.t.M≥0,where Pij and Bij are the ith row and jth elements of P and B, respectively.Note thatBij2=1. Thus, we have Pij−BijMij2=Bij−PijMij2. Then, the optimization problem of equation (20) can be rewritten as(21)minMijBijPij−Mij2,s.t.Mij≥0.Obviously, the optimal solution of equation (21) is given as follows:(22)M=maxB⊗P,0.


### 3.2.4. Fixing S, M, and F to Update W

Equation (12) is a constrained convex optimization problem. According to the properties of convex optimization, the local optimal solution is also the optimal solution of the whole. Next, this paper uses the iterative method to solve the optimal solution of equation (12).To solve W, given M, equation (12) is an unconstrained convex optimization problem for W. You just take the derivative of that and you set the derivative to 0 and you get W.When other variables fix, exceptW, equation (12) can be transformed into(23)minWXW−Y−B⊗MF2+∑i.jWTxi−WTxj22+γtrWTSw−SbW.LetN=Y+B⊗M, then the problem in (23) can be transformed into the following problem:(24)minWXW−NF2+λTrWTXLXTW+γtrWTSw−SbW=TrWTXTXW−WTXTN+λTrWTXLXTW+γtrWTSw−SbW=TrWTXTX+λXLXT+γSw−SbW−WTXTN⇒W=XTX+λXLXT+γSw−Sb−1XTN,where L=D−S is the graph Laplacian and D is a diagonal matrix whose diagonal elements Dii=∑jSij.


## 3.2.1. Fixing W, M, and F to Update S

When other variables are fixed, exceptS, equation (12) can be transformed into(13)min∑i.jWTxi−WTxj22sij+αsij2+2λTrFTLSF,s.t.∀i,siT1=1,0≤sij≤1.According to equation (7), equation (13) can be rewritten as(14)min∑i.jWTxi−WTxj22sij+αsij2+λ∑i,jfi−fj22Sij,s.t.∀i,siT1=1,0≤sij≤1.Because it is independent for the similarity vector of each data point, we can solve the optimal problem for each sample as follows:(15)min∑i.jWTxi−WTxj22sij+αsij2+λ∑i,jfi−fj22Sij,s.t.∀i,siT1=1,0≤sij≤1.Letmij=WTxi−WTxj22, nij=fi−fj22, and dij=|mij+λnij; equation (15) can be rewritten as(16)minsi+12αdi22,s.t.siT1=1,0≤Sij≤1.


## 3.2.2. Fixing S, W, and M to Update F

When other variables are fixed, exceptF, equation (12) can be transformed into(17)minTrFTLSF,s.t.FTF=I.The optimal solution ofF is formed from the eigenvectors of the c minimum eigenvalues in the LS.


## 3.2.3. Fixing S, W, and F to Update M

When other variables are fixed, exceptM, equation (12) can be transformed into(18)minXW−Y−B⊗M22,s.t.M≥0.Let us now consider optimization in terms ofM∈RN×C. Given W and T, and let P=XW−Y record the regression error of n data points, then the optimization problem can be solved from the following aspects:(19)minP−B⊗MF2,s.t.M≥0.According to the square of matrix Frobenius norm, the fact that an element can be decoupled, (10) can be decoupled equivalently into n×c subproblems. For the ith row of the matrix and the jth column element Mij, we have(20)minMijPij−BijMijF2,s.t.M≥0,where Pij and Bij are the ith row and jth elements of P and B, respectively.Note thatBij2=1. Thus, we have Pij−BijMij2=Bij−PijMij2. Then, the optimization problem of equation (20) can be rewritten as(21)minMijBijPij−Mij2,s.t.Mij≥0.Obviously, the optimal solution of equation (21) is given as follows:(22)M=maxB⊗P,0.


## 3.2.4. Fixing S, M, and F to Update W

Equation (12) is a constrained convex optimization problem. According to the properties of convex optimization, the local optimal solution is also the optimal solution of the whole. Next, this paper uses the iterative method to solve the optimal solution of equation (12).To solve W, given M, equation (12) is an unconstrained convex optimization problem for W. You just take the derivative of that and you set the derivative to 0 and you get W.When other variables fix, exceptW, equation (12) can be transformed into(23)minWXW−Y−B⊗MF2+∑i.jWTxi−WTxj22+γtrWTSw−SbW.LetN=Y+B⊗M, then the problem in (23) can be transformed into the following problem:(24)minWXW−NF2+λTrWTXLXTW+γtrWTSw−SbW=TrWTXTXW−WTXTN+λTrWTXLXTW+γtrWTSw−SbW=TrWTXTX+λXLXT+γSw−SbW−WTXTN⇒W=XTX+λXLXT+γSw−Sb−1XTN,where L=D−S is the graph Laplacian and D is a diagonal matrix whose diagonal elements Dii=∑jSij.


## 4. Experiments

In this section, we perform a large number of experiments, and the experimental results can prove that our proposed DLRR_AG algorithm can achieve high classification accuracy. In order to prove the effectiveness of our DLRR_AG algorithm, six public image databases are used to validate our method. For the sake of contrast, the proposed DLRR_AG algorithm is compared with other typical feature extraction methods as follows:(i)
Collaborative representation-based classification (CRC) [29]: CRC is a combined result of machine learning and compressed sensing, which shows its good classification performance on face image data. Considering the training samples from a specific class and the query set as two linear subspaces, the classwise prototypes most correlated with the query set are learned, resulting in a condensed gallery set.(ii)
Linear regression classification (LRC) [30]: LRC has attracted a great amount of attention owning to its promising performance in face recognition. However, its performance will dramatically decline in the scenario of limited training samples per class, particularly when only single training sample is available for a specific person.(iii)
Flexible manifold embedding (FME) [45]: FME is a semisupervised manifold learning framework with good applicability. It can effectively utilize label information from labeled data as well as a manifold structure from both labeled and unlabeled data.(iv)
Joint global and local structure discriminant analysis (JGLDA) [46]: for linear dimension reduction, it preserves the local intrinsic structure, which characterizes the geometric properties of similarity and diversity of data by two quadratic functions.(v)
Flexible linear regression classification (FLRC) [47]: the inferences are based on the least-squares estimators of the model which have been shown to be coherent with the interval arithmetic defining the model and to verify good statistical properties.(vi)
Discriminative least-squares regression (DLSR) [34]: DLSR is to embed class label information into the LSR formulation such that the distances between classes can be enlarged. In order to implement this idea, a technique called ε-dragging is introduced to force the regression targets of different classes moving along with opposite directions.


### 4.1. Experiments on YALE Database

Yale faces a database of 15 people containing 165 photos. They were taken by 15 people under different lighting conditions and with different facial expressions. Each person took 11 pictures. In our experiment, each image was manually cropped to a size of 50 by 40 pixels. Figure1 shows the sample images of one of them.Figure 1
Sample face images from Yale database.In this experiment, the first 2, 3, to 6 images from each object are used for training set, and the rest is utilized for test set. In order to evaluate the algorithm more objectively, we will eliminate random effects on the algorithm in the process of implementation, and all the methods are repeated 10 times. The recognition rates of all algorithms are shown as Table1.Table 1
Average recognition rate of different methods on the Yale database (%).
MethodsThe number (or proportion) of the training samples per class2 (18.18%)3 (27.27%)4 (36.36%)5 (45.45%)6 (54.54%)CRC67.1466.7965.8370.0674.52LRC65.7362.9461.8969.7673.79FLRC66.1765.9867.8570.8574.85FME60.7362.9470.8971.8676.34JGLDA68.5569.4569.6475.4875.82DLSR67.3867.6266.0770.6075.48DLRR_AG69.1770.7170.6073.1076.55Bold values indicate the highest recognition rate of all methods.It can be seen from Table1 that we can draw two points. Firstly, the recognition performance of the proposed DLRR_AG method is better than DLSR method irrespective of the number of training samples. Secondly, our method is superior to all other methods, except when the training sample is 4.


### 4.2. Experiments on ORL Database

The ORL dataset includes 400 face images from 40 different objects, and each object has 10 face images. For some people, their images were taken at different time and different light; image content includes different facial expression and facial details. Figure2 shows the sample images of one of them.Figure 2
Sample face images from ORL face database.In this experiment, the training set was the first 3, 4, 5, and 6 images of each person, and the test set was the remaining images. All algorithms are repeated 10 times. The recognition rates of each algorithm are shown in Table2.Table 2
Average recognition rate of different methods on the ORL database (%).
MethodsThe number (or proportion) of the training samples per class3 (30%)4 (40%)5 (50%)6 (60%)CRC87.8691.2592.0093.75LRC82.1485.4289.5095.60FLRC86.5688.5093.2095.61FME83.0086.4290.1295.33JGLDA88.5589.6392.9393.61DLSR88.4590.2392.6693.25DLRR_AG88.9391.6794.5095.63Bold values indicate the highest recognition rate of all methods.We can clearly see from Table2 that the proposed DLRR_AG is superior to CRC, LRC, FLRC, FME, LRR JGLDA, and DLSR.


### 4.3. Experiments on Georgia Tech Database

The Georgia Tech face database contains photos of 50 people taken during two or three sessions and produced at Georgia Tech. In the database, each individual took 15 color JPEG images with a cluttered background and a resolution of 640 by 480 pixels. The faces in these pictures may be front and tilted, or they may be front or tilted. These images include the different expressions, illuminations, and proportions. Each image is manually cropped to 60 by 50 pixels. All images are converted to grayscale images in the experiment. Figure3 shows the sample images of one of them.Figure 3
Sample face images from Georgia Tech face database.In this experiment, the training set was the first 4, 5, to 8 images of each person, and the test set was the remaining images. Repeat the algorithm 10 times. The recognition rates of each algorithm are shown in Table3.Table 3
Average recognition rate of different methods on the Georgia Tech database (%).
MethodsThe number (or proportion) of the training samples per class4 (26.67%)5 (33.33%)6 (40.00%)7 (46.67%)8 (53.33%)CRC57.6461.4368.1171.2575.40LRC56.3659.6066.6770.0074.57FLRC58.2260.1867.1071.3875.20FME53.2858.5667.5570.2273.55JGLDA57.6859.3266.7968.9572.84DLSR50.5554.4065.3369.8872.10DLRR_AG59.2763.6068.2273.0075.42As can be seen from Table3, DLRR_AG performs well compared with all other algorithms on the Georgia Tech database. In particular, the performance of DLRR_AG is much higher than that of CRC.


### 4.4. Experiments on CMU PIE Database

The CMU PIE database contains 41,368 facial images. The images were taken by 68 people with different expressions, decorations, and postures. The acquisition of multiple images of each object is based on the premise of fixed expression and attitude, and the illumination is changed to obtain 14 face images, and then these images are cut to 32 × 32 pixels. Figure4 shows multiple images from an object.Figure 4
Some face images of one object from CMU PIE database.In this experiment, the first 4, 5, 6, 7, and 8 face images of each object are selected to act as training set, and the rest are taken as test set. The proposed algorithms are repeated for 10 times. The recognition rates of all algorithms are shown in Table4.Table 4
Average recognition rate of different methods on the CMU PIE database (%).
MethodsThe number (or proportion) of the training samples per class4 (19.05%)5 (23.81%)6 (28.57%)7 (33.33%)8 (38.10%)CRC79.4384.2787.6888.9992.20LRC70.7279.6182.8687.5789.62FLRC78.2280.2384.3688.4591.33FME70.9377.5281.3385.0786.96JGLDA78.5579.7879.9588.6388.69DLSR74.2580.2985.9888.7491.95DLRR_AG81.5084.7188.1589.7592.59Bold values indicate the highest recognition rate of all methods.From Table4, we can know that the proposed DLRR_AG can respectively obtain the best recognition performance in the corresponding comparison algorithms irrespective of the variations of training sample size.


### 4.5. Experiments on AR Database

The AR face database [44] contains color face images of 120 people, and the total number of face images exceeds 4,000. Among them, 120 subjects were photographed twice with different facial expressions, light conditions, and shade, with a 14-day interval, and each person produced 26 images. In our experiment, out of the 26 facial images of 120 people, seven were selected from each stage, or 14 face images per person. Each image is manually cropped to 50 by 40 pixels. All images are converted to grayscale images. Figure 5 shows the sample images from one object.Figure 5
Sample face images from AR database.In this experiment, we obtained 14 images of unmasked faces from the first and second experiments. The images in the first stage (ranging from 3 to 7) were used as training images, and the face images in the second stage were used as test images. The proposed algorithms are repeated for 10 times. The experiment results are shown in Table5.Table 5
Average recognition rate of different methods on the AR database (%).
MethodsThe number (or proportion) of the training samples per class3 (21.43%)4 (28.57%)5 (35.71%)6 (42.86%)7 (50.00%)CRC70.7170.6073.1076.5577.38LRC66.7965.8370.0674.5275.12FLRC67.6266.0770.6075.4875.71FME70.8870.9673.3076.8577.84JGLDA68.5569.4569.6475.4875.82DLSR67.6266.0770.6075.4875.71DLRR_AG71.5072.1974.6777.2979.31Bold values indicate the highest recognition rate of all methods.As can be seen from Table5, compared with the proposed DLRR_AG algorithm, the classification results of CRC, LRC, FLRC, FME LRR, and JGLDA are poor. In other words, the proposed method can achieve the best recognition performance.


### 4.6. Experiments on UMIST Database

The UMIST face database contains a total of 575 facial images of 20 people. The 575 photos had all the poses of 20 people in the database, a mix of race, gender, and physical appearance. The views are different for each topic, between 19 and 48 views for each topic. The size of the face image in the view is 56 by 48 pixels. Figure6 shows example images of a person.Figure 6
Sample face images from the UMIST database.In this experiment, the first 1, 2 to 5 face images of each person are generally selected as the training set, while other images are used as the test images. The algorithm is repeated 10 times for each test. The experimental results are shown in Table6.Table 6
Average recognition rate of different methods on the UMIST database (%).
MethodsThe number (or proportion) of the training samples per class1 (21.05%)2 (26.31%)3 (31.58%)4 (36.84%)5 (42.10%)CRC46.7760.0071.5574.6884.33LRC48.5360.5671.7275.6384.60FLRC49.9360.8872.8776.2483.97FME56.2558.2869.7975.3183.29JGLDA53.1359.6769.6678.5987.80DLSR55.4560.0074.2580.2385.98DLRR_AG56.7861.6973.7981.6188.28Bold values indicate the highest recognition rate of all methods.As can be seen from Table6, when the training sample size is 3, the recognition rate of DLRR_AG algorithm is slightly lower than that of DLSR algorithm. However, the recognition rate of the proposed DLRR_AG algorithm is higher than other algorithms when the training sample size is not 3.


## 4.1. Experiments on YALE Database

Yale faces a database of 15 people containing 165 photos. They were taken by 15 people under different lighting conditions and with different facial expressions. Each person took 11 pictures. In our experiment, each image was manually cropped to a size of 50 by 40 pixels. Figure1 shows the sample images of one of them.Figure 1
Sample face images from Yale database.In this experiment, the first 2, 3, to 6 images from each object are used for training set, and the rest is utilized for test set. In order to evaluate the algorithm more objectively, we will eliminate random effects on the algorithm in the process of implementation, and all the methods are repeated 10 times. The recognition rates of all algorithms are shown as Table1.Table 1
Average recognition rate of different methods on the Yale database (%).
MethodsThe number (or proportion) of the training samples per class2 (18.18%)3 (27.27%)4 (36.36%)5 (45.45%)6 (54.54%)CRC67.1466.7965.8370.0674.52LRC65.7362.9461.8969.7673.79FLRC66.1765.9867.8570.8574.85FME60.7362.9470.8971.8676.34JGLDA68.5569.4569.6475.4875.82DLSR67.3867.6266.0770.6075.48DLRR_AG69.1770.7170.6073.1076.55Bold values indicate the highest recognition rate of all methods.It can be seen from Table1 that we can draw two points. Firstly, the recognition performance of the proposed DLRR_AG method is better than DLSR method irrespective of the number of training samples. Secondly, our method is superior to all other methods, except when the training sample is 4.


## 4.2. Experiments on ORL Database

The ORL dataset includes 400 face images from 40 different objects, and each object has 10 face images. For some people, their images were taken at different time and different light; image content includes different facial expression and facial details. Figure2 shows the sample images of one of them.Figure 2
Sample face images from ORL face database.In this experiment, the training set was the first 3, 4, 5, and 6 images of each person, and the test set was the remaining images. All algorithms are repeated 10 times. The recognition rates of each algorithm are shown in Table2.Table 2
Average recognition rate of different methods on the ORL database (%).
MethodsThe number (or proportion) of the training samples per class3 (30%)4 (40%)5 (50%)6 (60%)CRC87.8691.2592.0093.75LRC82.1485.4289.5095.60FLRC86.5688.5093.2095.61FME83.0086.4290.1295.33JGLDA88.5589.6392.9393.61DLSR88.4590.2392.6693.25DLRR_AG88.9391.6794.5095.63Bold values indicate the highest recognition rate of all methods.We can clearly see from Table2 that the proposed DLRR_AG is superior to CRC, LRC, FLRC, FME, LRR JGLDA, and DLSR.


## 4.3. Experiments on Georgia Tech Database

The Georgia Tech face database contains photos of 50 people taken during two or three sessions and produced at Georgia Tech. In the database, each individual took 15 color JPEG images with a cluttered background and a resolution of 640 by 480 pixels. The faces in these pictures may be front and tilted, or they may be front or tilted. These images include the different expressions, illuminations, and proportions. Each image is manually cropped to 60 by 50 pixels. All images are converted to grayscale images in the experiment. Figure3 shows the sample images of one of them.Figure 3
Sample face images from Georgia Tech face database.In this experiment, the training set was the first 4, 5, to 8 images of each person, and the test set was the remaining images. Repeat the algorithm 10 times. The recognition rates of each algorithm are shown in Table3.Table 3
Average recognition rate of different methods on the Georgia Tech database (%).
MethodsThe number (or proportion) of the training samples per class4 (26.67%)5 (33.33%)6 (40.00%)7 (46.67%)8 (53.33%)CRC57.6461.4368.1171.2575.40LRC56.3659.6066.6770.0074.57FLRC58.2260.1867.1071.3875.20FME53.2858.5667.5570.2273.55JGLDA57.6859.3266.7968.9572.84DLSR50.5554.4065.3369.8872.10DLRR_AG59.2763.6068.2273.0075.42As can be seen from Table3, DLRR_AG performs well compared with all other algorithms on the Georgia Tech database. In particular, the performance of DLRR_AG is much higher than that of CRC.


## 4.4. Experiments on CMU PIE Database

The CMU PIE database contains 41,368 facial images. The images were taken by 68 people with different expressions, decorations, and postures. The acquisition of multiple images of each object is based on the premise of fixed expression and attitude, and the illumination is changed to obtain 14 face images, and then these images are cut to 32 × 32 pixels. Figure4 shows multiple images from an object.Figure 4
Some face images of one object from CMU PIE database.In this experiment, the first 4, 5, 6, 7, and 8 face images of each object are selected to act as training set, and the rest are taken as test set. The proposed algorithms are repeated for 10 times. The recognition rates of all algorithms are shown in Table4.Table 4
Average recognition rate of different methods on the CMU PIE database (%).
MethodsThe number (or proportion) of the training samples per class4 (19.05%)5 (23.81%)6 (28.57%)7 (33.33%)8 (38.10%)CRC79.4384.2787.6888.9992.20LRC70.7279.6182.8687.5789.62FLRC78.2280.2384.3688.4591.33FME70.9377.5281.3385.0786.96JGLDA78.5579.7879.9588.6388.69DLSR74.2580.2985.9888.7491.95DLRR_AG81.5084.7188.1589.7592.59Bold values indicate the highest recognition rate of all methods.From Table4, we can know that the proposed DLRR_AG can respectively obtain the best recognition performance in the corresponding comparison algorithms irrespective of the variations of training sample size.


## 4.5. Experiments on AR Database

The AR face database [44] contains color face images of 120 people, and the total number of face images exceeds 4,000. Among them, 120 subjects were photographed twice with different facial expressions, light conditions, and shade, with a 14-day interval, and each person produced 26 images. In our experiment, out of the 26 facial images of 120 people, seven were selected from each stage, or 14 face images per person. Each image is manually cropped to 50 by 40 pixels. All images are converted to grayscale images. Figure 5 shows the sample images from one object.Figure 5
Sample face images from AR database.In this experiment, we obtained 14 images of unmasked faces from the first and second experiments. The images in the first stage (ranging from 3 to 7) were used as training images, and the face images in the second stage were used as test images. The proposed algorithms are repeated for 10 times. The experiment results are shown in Table5.Table 5
Average recognition rate of different methods on the AR database (%).
MethodsThe number (or proportion) of the training samples per class3 (21.43%)4 (28.57%)5 (35.71%)6 (42.86%)7 (50.00%)CRC70.7170.6073.1076.5577.38LRC66.7965.8370.0674.5275.12FLRC67.6266.0770.6075.4875.71FME70.8870.9673.3076.8577.84JGLDA68.5569.4569.6475.4875.82DLSR67.6266.0770.6075.4875.71DLRR_AG71.5072.1974.6777.2979.31Bold values indicate the highest recognition rate of all methods.As can be seen from Table5, compared with the proposed DLRR_AG algorithm, the classification results of CRC, LRC, FLRC, FME LRR, and JGLDA are poor. In other words, the proposed method can achieve the best recognition performance.


## 4.6. Experiments on UMIST Database

The UMIST face database contains a total of 575 facial images of 20 people. The 575 photos had all the poses of 20 people in the database, a mix of race, gender, and physical appearance. The views are different for each topic, between 19 and 48 views for each topic. The size of the face image in the view is 56 by 48 pixels. Figure6 shows example images of a person.Figure 6
Sample face images from the UMIST database.In this experiment, the first 1, 2 to 5 face images of each person are generally selected as the training set, while other images are used as the test images. The algorithm is repeated 10 times for each test. The experimental results are shown in Table6.Table 6
Average recognition rate of different methods on the UMIST database (%).
MethodsThe number (or proportion) of the training samples per class1 (21.05%)2 (26.31%)3 (31.58%)4 (36.84%)5 (42.10%)CRC46.7760.0071.5574.6884.33LRC48.5360.5671.7275.6384.60FLRC49.9360.8872.8776.2483.97FME56.2558.2869.7975.3183.29JGLDA53.1359.6769.6678.5987.80DLSR55.4560.0074.2580.2385.98DLRR_AG56.7861.6973.7981.6188.28Bold values indicate the highest recognition rate of all methods.As can be seen from Table6, when the training sample size is 3, the recognition rate of DLRR_AG algorithm is slightly lower than that of DLSR algorithm. However, the recognition rate of the proposed DLRR_AG algorithm is higher than other algorithms when the training sample size is not 3.


## 5. Conclusion

This paper presents a discriminative label relaxation regression algorithm based on adaptive graph (DLRR_AG) algorithm, which can effectively alleviate the overfitting problem caused by label relaxation by correctly capturing the local structure information of the original observed data. The main innovation of this paper has the following points. (1) The adaptive neighborhood graph can well capture the essential local structural information of the original data. (2) Label relaxation, manifold learning, and discriminant analysis are integrated into a unified framework. A large number of experiments in six public image databases show that the proposed method is superior to other related methods. Therefore, the proposed method is effective and feasible.



---

*Source: 8852137-2020-12-14.xml*