Locality-Constrained Concept Factorization

1 Introduction

Data representation is a fundamental problem in many real world applications such as pattern recognition, computer vision, image clustering etc. Especially linear data representations, such as principal component analysis (PCA), locality preserving projection (LPP) [He and Niyogi, 2003; He et al., 2005], independent component analysis (ICA), nonnegative matrix factorization (NMF) [Lee and Seung, 1999] and concept factorization (CF) [Xu and Gong, 2004], have been widely used in these data analysis tasks.

Matrix factorization has been frequently used in linear data representation. Given a data matrix X, the above algorithms aim to find two or more matrix factors whose product is a good approximation to the original matrix. One factor consists of a set of new basis vectors which reveals the latent semantic structure, and the other factor can be considered as the coefficients (also referred as encodings) where each data point is a linear combination of the found bases. In real applications, the dimension of the new basis vectors is usually much smaller than that of the original data matrix. This gives rise to a compact representation of the data points which can facilitate other learning tasks such as clustering and classification.

NMF and CF have attracted great attention as efficient matrix decomposition methods. NMF aims to decompose a data matrix X into two matrix factors U and V so that UV provides a good approximation to X. The CF model is a variation of NMF in that each cluster is expressed by a linear combination of the data points and each data point is represented by a linear combination of the cluster centers. The major advantage of CF over NMF is that the NMF algorithm can only be performed in the original feature space of the data points, but the CF method can be performed on any data representation space, so that it can be kernelized and the powerful idea of the kernel method can be applied [Xu and Gong, 2004].

Since the dimension of the decomposed factors is much smaller than that of the original matrix, both NMF and CF map the data from high dimensional space to a low dimensional representation and obtain a sparse encoding of the data. However, the sparsity obtained by these methods does not always satisfy locality conditions. Since the local points share the greatest similarity, it would be more natural to represent the basis vectors using a few nearby anchor points, which leads to a more efficient representation of the data.

Recently, Cai et al. [Cai et al., 2011] proposed a Locally Consistent Concept Factorization approach to encode the geometrical information of the data space, which can extract the document concepts with respect to the intrinsic manifold structure. This method is able to discover the local geometrical structure, but does not always satisfy the locality conditions as we mentioned before. As to add sparseness constraint to the matrix factorization, Hoyer [Hoyer, 2004] showed how explicitly incorporating the notion of 'sparseness' improves the found decompositions. However, there is no work that includes locality and sparsity constraints at the same time to the best of our knowledge.

In this paper, we introduce a novel matrix factorization algorithm, called Locality-constrained Concept Factorization (LCF) which imposes a locality constraint onto the traditional concept factorization. By requiring the concepts (basis vectors) to be as close to the original data points as possible, each data can be represented by a linear combination of only a few nearby basis concepts, thus achieving sparsity and locality at the same time.

To achieve this goal, we incorporate the idea of Local Coordinate Coding [Yu et al., 2009] into the original objective function of concept factorization. And we also propose a multiplicative algorithm to efficiently solve the corresponding optimization problem.

2 Background

Factorization of matrices is generally non-unique, and a number of different methods of doing so have been developed by incorporating different constraints.

Suppose we have n data points {xi}ni=1 . Each data point xi ∈ Rm is m-dimensional and is represented by a vector. The vectors are placed in the columns and the whole data set is represented by a matrix X = [x1, · · · , xn] ∈ Rm×n. NMF aims to find an m × k matrix U and a k × n matrix V where the product of these two factors is an approximation to the original matrix, represented as X ≈ UV. Each column vector of U, ui, can be regarded as a basis and each data point xi is approximated by a linear combination of these k bases, weighted by the components of V: xi ≈ ∑kj=1 ujvji.

The speciality of NMF is that it enforces that all entries of the factor matrices must be non-negative. One limitation of NMF is that the non-negative requirement is not applicable to applications where the data involves negative number. The second is that it is not clear how to effectively perform NMF in the transformed data space so that the powerful kernel method can be applied.

Concept Factorization is proposed striving to address the above problems while inheriting all the strengths of the NMF method. In the CF model, we rewrite the NMF model by representing each base (cluster center) uj by a linear combination of the data points uj = ∑i wijxi where wij ≥ 0. Let W = [wij ] ∈ Rn×k , CF tries to decompose the data matrix satisfied the following condition

Using the Frobenius norm to qualify the approximation, CF tries to minimize the following objective function

3 Locality-constrained Concept Factorization

In this section, we introduce our Locality-constrained Concept Factorization (LCF) algorithm, which takes the locality constraint as an additional requirement. The algorithm presented in this paper is fundamentally motivated from the concept of local coordinate coding [Yu et al., 2009].

3.1 The Objective Function

First we introduce the concept of coordinate coding.

Definition A coordinate coding is a pair (γ, C), where C ⊂ Rd is a set of anchor points, and γ is a map of x ∈ Rd to [γv(x)]v∈C ∈ R|C| such that ∑v γv(x) = 1. It induces the following physical approximation of x in Rd : γ(x) = ∑v∈C γv(x)v.

According to this definition, the CF model can be considered as a coordinate coding where the basis vectors uj = ∑i wijxi are a set of anchor points, and each column of V

contains the coordinates for each data point with respect to the anchor points. In order to add the local sparse constraint to the traditional concept factorization, we require that each original data point should be sufficiently close to only a few anchor points. This can be achieved by introducing the following term to measure the locality and sparsity penalty:

The above constraint incurs a heavy penalty if xi is far away from the anchor point uj while its coordinate vji with respect to uj is large. Therefore, by minimizing R, we essentially try to formalize our intuition that xi is close to the anchor points uj as much as possible, otherwise its coordinate with respect to uj tends to be zero.

With the locality constraint, our LCF algorithm reduces to minimize the following objective function:

with the constraint that W and V are non-negative matrices. The λ ≥ 0 is a regularization parameter.

3.2 The Algorithm

We introduce an iterative algorithm to find a local minimum for the optimization problem. The objective function can be rewritten as follows:

where Di = diag(|vi|) ∈ RK×K . Using the matrix property Tr(AB) = Tr(BA), ‖A‖2 = Tr(AT A) and Tr(A) = Tr(AT ), we have

Let ψjk and φki be the Langrange multiplier for constraints wjk ≥ 0 and vki ≥ 0, respectively. We define matrix Ψ =

[ψjk] and Φ = [φki], then the Langrange L is

Define K = XT X, define a column vector a = diag(K) ∈ RN . Let A = (a, · · · , a)T be a K ×N matrix whose rows are aT . Define a column vector b = diag(WT KW) ∈ RK . Let B = (b, · · · , b) be a K × N matrix whose columns are b. The partial derivatives of L with respect to W and V are:

Using the Karush-Kuhn-Tucker conditions (also known as the KKT conditions) ψjkwjk = 0 and φkivki = 0, we get the following equations:

The above equations lead to the following update rules:

We have the following theorem regarding the above iterative updating rules. Theorem 1 guarantees the convergence of the iterations in Eq. (4) and (5) and therefore the final solution will be a local optimum.

Theorem 1. The objective function O in Eq. (2) is nonincreasing under the update rules in Eq. (4) and Eq. (5). The objective function is invariant under these updates if and only if W and V are at a stationary point.

To prove Theorem 1, we use an auxiliary function similar to that used in the Expectation-Maximization algorithm.To make the proof complete, we restate the definition of auxiliary function and its property which will be used to prove the algorithm convergence.

Definition G(x, x′ ) is an auxiliary function for F(x) if the conditions

are satisfied.

Lemma 2. If G is an auxiliary function, then F is nonincreasing under the update

The equality F(xt+1 ) = F(xt ) holds only if xt is a local minimum of G(x, xt ). By iterating the updates in Eq. (6), the sequence of estimates will converge to a local minimum xmin = argminx F(x). Next, we will define an auxiliary function for our objective function and use Lemma 2 to show that the minimum of the objective function is exactly our update rule, thereby Theorem 1 is proved.

First, we prove the convergence of the update rule in Eq. (4). Considering any element wab in W, we use Fwab to denote the part of O which is only relevant to wab. Since the update is essentially element-wise, it is sufficient to show that each Fwab is nonincreasing under the update step of (4). We prove this by defining the auxiliary function G for Fwab as follows.

Lemma 3. The function

is an auxiliary function for Fwab , the part of O which is only relevant to wab.

Proof. Since G(w,w) = Fwab (w) is obvious, we only need to show that G(w, w(t) ab ) ≥ Fwab (w). To do this, we compare G(w, w(t) ab ) with the Taylor series expansion of Fwab (w):

Since

and

Then we define an auxiliary function for the update rule in Eq. (5). Similarly, let Fvab denote the part of O relevant to vab. Then the auxiliary function regarding vab is defined as follows.

Lemma 4. Function

is an auxiliary function for Fvab , the part of O which is only relevant to vab.

The proof is essentially similar to the proof of Lemma 3 and is omitted here due to space limitation. With the above lemmas, now we give the proof of Theorem 1.

Proof of Theorem 1: From Lemma 3 we know that G(w, w(t) ab ) is an auxiliary function for Fwab , and from Lemma 4 we know that G(v, v(t) ab ) is an auxiliary function for Fvab . According to Lemma 2, by solving w(t+1) = arg minw G(w, w(t) ab ), We obtain

and by solving v(t+1) = arg minz G(v, v(t) ab ), We obtain

which are exactly the same updates as in Eq. (4) and (5). Therefore, the objective function O in Eq. (2) is nonincreasing under these updates. □

4 Experiments

In this section, we show the data clustering performance of the proposed method, and compare the results with four other related methods using the same data set. The algorithms that we evaluated are listed below:

• Traditional K-means (Kmeans).
• Nonnegative Matrix Factorization (NMF) [Lee and Seung, 2001].
• Concept Factorization (CF) [Xu and Gong, 2004].
• Non-negative Matrix Factorization with Sparseness Constraints (SparseNMF) [Hoyer, 2004].
• Our proposed Locality-constrained concept Factorization (LCF).

We use two metrics to evaluate the clustering performance. One metric is accuracy (AC), which is used to measure the percentage of correct labels obtained. The second metric is the normalized mutual information (̂ MI). In clustering applications, mutual information is used to measure how similar two sets of clusters are. The definitions of these two metrics can be found in [Xu and Gong, 2004]. The performance is evaluated by comparing the cluster label of each sample with the label provided by the data set.

The evaluations were conducted for the cluster numbers ranging from 2 to 10. For each given cluster number k, we randomly chose k clusters and ran the test 10 times, and the final scores were obtained by calculating the average and variance over the 10 test runs. Since the evaluated methods whose clustering results depend on the initialization, each test run consists of 10 sub-runs from which we chose the best result to report.

In the experiments, the parameters were set to be the values that each algorithm can achieve its best results. For our LCF algorithm, the regularization parameter is set to be λ = 0.3.

4.1 Data Sets

The experiments are conducted on two data sets. One is the Yale Database, and the other is Cambridge ORL face database. The important statistics of these data sets are described below (also summarized in Table 1):

• The Yale database contains 165 gray scale images of 15 individuals. All images demonstrate variations in lighting condition (left-light, center-light,right-light), facial expression (normal, happy, sad, sleepy, surprised and wink), and with/without glasses.
• The ORL database contains ten different images of each of 40 distinct subjects, thus 400 images in total. For some subjects, the images were taken at different times, varying the lighting, facial expressions (open/closed eyes, smiling/not smiling) and facial details (glasses/no glasses). All the images were taken against a dark homogeneous background with the subjects in an upright, frontal position (with tolerance for some side movement).

In all the experiments, images are preprocessed so that faces are located. Original images are first normalized in scale and orientation such that the two eyes are aligned at the same position. Then the facial areas were cropped into the final images for clustering. Each image is of 32 × 32 pixels with 256 gray levels per pixel.

4.2 Clustering Results

Fig. 1 and 2 show the plots of accuracy and normalized mutual information versus the number of clusters for different algorithms on the Yale dataset. As can be seen, our proposed LCF algorithm consistently outperforms all the other algorithms. The detailed clustering results are shown in Table 2. The last row shows the average accuracy (normalized mutual information) over k. Comparing to the best algorithm other than our proposed LCF i.e. SparseNMF, our algorithm LCF achieves 4.41% improvement in accuracy and 5.69% improvement in normalized mutual information.

Fig. 3 and Fig. 4 show the graphical clustering results for the ORL data set. LCF obtains the best result for most of the cases. SparseNMF fails to consider the locality condition, and in some cases performs even worse than Kmeans. Table 3 shows the detailed clustering accuracy and normalized mutual information. Comparing to the best algorithm other than our proposed LCF algorithm, i.e., SparseNMF, LCF achieves

5.8% improvement in accuracy. For normalized mutual information, LCF achieves 6.4% improvement.

4.3 Learning the Overcomplete Basis

Usually, matrix factorization methods are used for dimension reduction in many applications. However, [Lee et al., 2007] shows that in some cases, it is desirable to learn the overcomplete basis. Here we evaluate the performance of our algorithm in this aspect. To show the performance for learing the overcomplete basis of our proposed algorithm, 150 data points from mixture of three Gaussians in a 2- dimensional space are randomly generated. NMF and LCF are conducted to obtain three basis vectors and cluster these data points into 3 clusters. Fig 5 shows that our LCF obtains better results than NMF. The bases obtained by NMF are far away from the original points. However, since we add a locality constraint, the three bases obtained by LCF exactly reside in the cluster centers, which leads to a better data representation.

5 Conclusions

In this paper we proposed a novel matrix factorization method, called Locality-constrained Concept Factorization (LCF). This method enforces a locality constraint onto the traditional concept factorization. By requiring the concepts (basis vectors) to be as close to the original data points as possible, each data can be represented by a linear combination of only a few nearby basis concepts, thus achieving sparsity and locality at the same time. The experimental results on two standard face databases have demonstrated the effectiveness of our approach over other matrix factorization techniques, especially for the data clustering applications.

Acknowledgments

This work was supported by the Fundamental Research Funds for the Central Universities under grant 2009QNA5024.