Multi-Component Nonnegative Matrix Factorization

1 Introduction

Finding an optimal data representation is a fundamental problem in many data analysis tasks [Tao et al., 2009; Liu et al., 2012]. A good data representation can typically reveal the latent structure of data and facilitate further processes such as clustering, classification and recognition. Nonnegative matrix factorization (NMF) as a fundamental approach for data representation has attracted great attentions because it possesses parts-of-whole interpretations and produces superior practical performance [Lee and Seung, 1999].

∗Corresponding author

Several variants of NMF have been proposed to seek for more effective data representation in the recent years. [Kong et al., 2011] proposed a robust formulation of NMF (RNMF) to deal with large noises by L2,1-norm. [Guan et al., 2012] then presented Manhattan NMF (MahNMF) to alleviate heavy tailed Laplacian noise. [Liu et al., 2012] developed a semi-supervised approach called constrained NMF (CNMF) that takes the label information as hard constraints to enforce data with the same label to have the same representations. Under the assumption that the data points nearby have more similar data representations than those far away, [Cai et al., 2011] proposed a graph regularized NMF (GNMF) to model the local manifold structure. Subsequently, [Wang et al., 2016b] proposed a correntropy induced metric based graph regularized NMF (CGNMF) to deal with noises and preserving the intrinsic geometric structure of data simultaneously. [Qian et al., 2016] adopted an approximation of Earth Movers Distance to utilize information of feature correlation. Additionally, LANMF [Liu et al., 2016] presented a largecone penalty framework to obtain attractive local solutions for NMF. Given a dataset with multiple types of features, [Liu et al., 2013] proposed a multi-view NMF (MultiNMF) which learns a consensus representation shared by multiple features. AMVNMF [Wang et al., 2016a] then extended MultiNMF to semi-supervised setting by enforcing data of same label have the same representations regardless of features.

These NMF-based approaches, which either incorporate regularization terms or prior information for more accurate learning, all tend to treat the features of data as a whole and obtain a single feature representation. However, it is well recognized that real data are complex and consist of components [Changpinyo et al., 2013; Ou et al., 2015]. Taken the Yale dataset 1 as an example, Figure 1 illustrates the face images consisting of multiple components including gender, facial expressions, ethnicity, and lighting direction (under which the images were taken), etc. Since each component mainly represents one subset of features and contains the specific information of the data, current NMFs are unable to distinguish these embedded components thus cannot adequately exploit diverse information among them, which may not lead to satisfactory representations. Hence, it becomes crucial to explore diverse information from multiple components in order to represent data more comprehensively and accurately.

1 http://www.cad.zju.edu.cn/home/dengcai/Data/FaceData.html

In fact, the representations learnt through multiple components will also enable us to understand data at a semantic level. For example, when clustering the Yale dataset, current NMFs get only one clustering solution (i.e., all face images of a subject being grouped into one cluster) based on global features of a single representation matrix. With representations of multiple components, multiple clustering solutions can be achieved. For example, one cluster of images can be faces with glasses and another can be faces with a happy expression.

To achieve this, we propose a novel multi-component nonnegative matrix factorization (MCNMF). It captures more comprehensive information and interprets data from different perspectives, by leveraging the multiple components. Instead of factorizing the data matrix into a single basis and representation matrix, MCNMF learns multiple representations based on different basis matrices. The Hilbert-Schmidt Independence Criterion (HSIC) [Gretton et al., 2005] which measures dependence in terms of a kernel dependence measure is applied as a diversity term. With this term, we explicitly coregularize different components to enforce the diversity of the jointly learned representations. An aggregated representation is then established by combining these multiple representations. To solve the objective function of MCNMF, we derive a new iterative updating optimization scheme, with its correctness and convergence being proven as well. Experiments on clustering have demonstrated that MCNMF not only improves the accuracy by the aggregated representation, but also captures different semantic properties of data.

2 Brief Intro to NMF

Given a nonnegative data matrix X = [x1, x2, . . . , xn] ∈ Rm×n , each data xf (1 ≤ f ≤ n) has m-dimensional features. NMF [Lee and Seung, 1999] aims to find a basis matrix W ∈ Rm×k and a representation matrix H ∈ Rk×n , where the product of the two matrices can well approximate the original matrix, represented as X ≈ WH, and k (usually k ≪ m) denotes the reduced dimension. Formally, NMF solves the following optimization problem to compute the optimal representation matrix H∗ :

Then the multiplicative algorithm is derived to infer W and H [Lee and Seung, 2001]. Obviously, this standard NMF regards the features of data as a whole, so can be considered as a single component approach. Arguably, the semantic aspects of data is much richer than what a single component can capture. To understand data thoroughly and in-depth, we propose our multi-component NMF (MCNMF) in the following.

3 MCNMF

3.1 Objective Function

Assuming X comes with V components, we use H(i) ∈ Rk(i)×n to denote the representation with k(i) -dimensional features that corresponds to the i-th (i ∈ {1, 2, . . . , V }) components, and W(i) be the corresponding representation matrix of H(i) . Then the product of eachW(i)H(i) should well approximate X, i.e., X ≈ W(i)H(i) , from each perspective. To seek for multiple optimal representations {H(i) ∗ }Vi=1 , we have the following function:

This will allow us to factorize X straightforwardly. However, it may fail to explore the diverse information of multiple components effectively as each H(i) could be very close to or even same as each other.

For any data, xf , it comes with a pair of components, i and j. xf 's latent distinct information of each component cannot be fully explored unless its representations of two components, i.e., h(i) f and h(j) f , are enforced to be independent to each other. Given n data vectors, we assume that each ith component is drawn from X space and the jth component from Y space. Then, in essence, we aim to learn a mapping function G of their representations from S := {(h(i) 1 , h(j) 1 ), (h(i) 2 , h(j) 2 ), . . . , (h(i) n , h(j) n )} ⊆ X × Y, i.e., G: X → Y, to minimize the dependence between data representations in the X and Y.

To do so, we employ the Hilbert-Schmidt Independence Criterion (HSIC) due to its simplicity and neat theoretical properties such as exponential convergence. HSIC computes the square of the norm of the cross-covariance operator over the domain X × Y in Hilbert Space. As an effective measure of dependence, the HSIC has been applied to several machine learning tasks recently [Song et al., 2007; Zhang and Zhou, 2010; Niu et al., 2010]. Mathmatically, an empirical estimate of the HSIC [Gretton et al., 2005] is defined as

where K(i) and K(j) are the centered Gram matrices of kernel functions defined over H(i) and H(j) . R = I - 1n eeT , where I is an identity matrix and e is an all-one column vector.

Thus, to explore the diverse information from more components, we extend (3) and combine it with (2) to produce the following function:

where α is the parameter of the diversity regularization term. The first term represents the error between X and the product of the basis and representation matrices in different components. The second term ensures that any two of V representations be diverse to each other.

Here, we use the inner product kernel for HSIC, i.e., K(i) = H(i) T H(i) . For notational convenience, we ignore the scaling factor (n1)-2 of HSIC, and rewrite (4) to form the final objective function as

After obtaining the optimal representation H(i) ∗ of each component, the final aggregated representation H∗ can be obtained by combining all H(i) ∗ , i.e., H∗ = [H(1) ∗ , H(2) ∗ , . . . ,H(V ) ∗ ] ∈ R∑Vi=1 k(i)×n .

3.2 Optimization

The optimization problem in (5) is not convex in both variablesW(i) and H(i) , so it is infeasible to find the global minimum. In addition, as the matrix R contains negative values, it is technically challenging to solve (5) directly. Here we propose an algorithm that separates the optimization of (5) to two subproblems and optimizes them iteratively, which guarantees each subproblem converges to the local minima.

W(i) -subproblem: Updating W(i) with H(i) fixed in (5) leads to a standard NMF formulation [Lee and Seung, 2001], so the updating rule forW(i) is

H(i) -subproblem: When updating H(i) with W(i) in (5) fixed, we need to solve the following function:

We then introduce a Lagrange multiplier matrix η = [ηpq] ∈ Rk×n for the nonnegative constraint on H(i) . Utilizing ‖A‖2F = tr(AT A), we obtain the following function:

Setting the derivative of J ′ (H(i) ) to be 0 with respect to H(i) , we have

Following the Karush-Kuhn-Tucker (KKT) condition for the nonnegativity of H(i) , we have the following equation:

Because R contains negative values, we decompose R into two nonnegative parts for ensuring H(i) ≥ 0 in each iteration:

where R+pq = (|Rpq|+Rpq)/2 and R-pq = (|Rpq|-Rpq)/2. Substituting (11) into (10), we obtain

This is the fixed point equation whose solution must satisfy at convergence. Denote Ra = R+ ∑Vj=1,j̸=i K(j)R-, Rb = R- ∑Vj=1,j̸=i K(j)R+, Rc = R-∑Vj=1,j̸=i K(j)R-, Rd = R+ ∑Vj=1,j̸=i K(j)R+, then given an initial value of H(i) , the successive update of H(i) is:

The correctness of the updating rule (13) can be guaranteed by the following theorem.

Theorem 1. If the updating rule of H(i) converges, then the final solution satisfies the KKT optimality condition.

Proof of Theorem 1. At convergence, H∞ = Ht+1 = Ht = H, where t denotes the t-th iteration, i.e.,

Then for each H(i) pq , we have

which is equivalent to (12). □

We can now prove the convergence of the updating rule, by making use of an auxiliary function as in [Lee and Seung, 2001]. The definition of the auxiliary function is as follows:

Definition 1. A function G(Q, Q′ ) is an auxiliary function of the function J(Q) if G(Q,Q′ ) ≥ J(Q) and G(Q,Q) = J(Q) for any Q, Q′ .

The auxiliary function gives rise to the following lemma [Lee and Seung, 2001]:

Lemma 1. If G is an auxiliary function of J, then J is non-increasing under the update rule Qt+1 = arg minQ G(Q, Qt ).

Under the constraint in (11), we now have the specific form of the auxiliary function G(H(i) , H(i) ′ ) for the objective function J(H(i) ) in (7) based on Lemma 2.

Lemma 2. The function

is an auxiliary function for J(H(i) ) in (7).

Proof of Lemma 2. We find upper bounds for each of the two positive terms by the following lemma [Ding et al., 2010],

Lemma 3. For any nonnegative matrices S ∈ Rn×n , B ∈ Rg×g , F ∈ Rn×g and F′ ∈ Rn×g , with S and B being symmetric, then the following inequality holds

Then, we have following inequations:

To obtain lower bounds for the remaining terms, we use the inequality z > 1 + log z, ∀z > 0 [Ding et al., 2010] and have

Collecting all bounds, we have the final auxiliary function in Lemma 2. □

Based on the lemmas 1 and 2, we can prove the convergence of the updating rule (13).

Theorem 2. The optimization problem (7) is nonincreasing under the iterative updating rule (13).

Proof of Theorem 2. Lemma 2 provides a specific form G(H, H′ ) of the auxiliary function for J(H) in the problem (7). We can have the solution for minHG(H,H′ ) by the following KKT condition

which gives rise to the updating rule in (13). Following Lemma 1, under this updating rule the objective function values of J(H) in (7) will be non-increasing. □

Bulk of the computation depends on the matrix multiplication in the updating rules (13) and (6), the complexity of updating W(i) and H(i) is O(mnk(i) ) and O(∑Vj=1,j̸=i (k(j)n2 + nk(j) 2 )), respectively. So the overall computation of MCNMF is O(∑Vi=1 (∑Vj=1,j̸=i k(j)n2 + k(i)mn)).

4 Experiments

4.1 Dataset

We carried several experiments on the following benchmark datasets to show the effectiveness of MCNMF. The Yale contains 11 facial images for each of 15 subjects. Sample images are shown in Figure 1. For each subject, its face images are either in different facial expressions (such as happy or sad), or configurations (such as with or without glasses). The ORL 2 dataset consists of 400 facial images belonging to 40 different subjects. Similar to the Yale dataset, the images were taken with various lighting and facial expressions. The Notting-Hill [Cao et al., 2015] is a video face dataset, which is derived from the movie "Notting Hill". The faces of 5 main casts were used, including 4660 faces in 76 tracks. The COIL20 image library 3 is composed of 1440 images for 20 objects. The 72 images of each object were captured by a fixed camera at a pose intervals of 5 degree. For this dataset, we regard the different poses and shapes as components.

4.2 Experiment Setup

We first compared MCNMF against the standard NMF [Lee and Seung, 2001] to verify the effectiveness of exploring diverse information from multi-components, and then with the state-of-the-arts: RNMF [Kong et al., 2011], GNMF [Cai et al., 2011], Cauchy NMF [Liutkus et al., 2015] and LANMF [Liu et al., 2016]. For each compared method, the parameters were set according to the parameter settings in original papers. For MCNMF, we varied the regularization parameter α within [0.01, 0.05] with 0.01 interval and fixed the number of components V = 3 (more discussion in next subsection). In addition, we set each k(i) equals to number of clusters according to the groundtruth of each dataset. The dimensions of obtained optimal representations H∗ for all the compared methods were all set to be k = ∑Vi=1 k(i) for fair comparison.

4.3 Performance Analysis

Clustering result. We applied k-means to the obtained representations H∗ for clustering. Since k-means is sensitive to the initial values, we repeated the clustering process 50 times to give the average performance. Moreover, since all the compared methods converge to local minimum, we ran each method 10 times to avoid randomness. Similar to the work [Cao et al., 2015], we adopted three widely used evaluation metrics accuracy (AC) [Liu et al., 2012], normalized mutual information (NMI) [Liu et al., 2012] and purity [Ding et al., 2006] to assess the quality of the results with a comprehensive evaluation. The final average clustering results along with standard deviations are reported in Table 1. As we can see, MCNMF outperforms the other methods against all metrics and gets the lowest standard deviations on 9 of 12 results, which demonstrate the robustness of MCNMF. Besides, it can be noticed that GNMF performs the second best in terms of AC, but not for other metrics. Especially, MCNMF outperforms GNMF with a large margin: 4.84% and 3.35% on the Yale and ORL, respectively. This is probably because that the images in both of the two datasets have more components, such as different lighting and expressions. Obviously, richer information has been explored and obtained for comprehensive representations, which brings significant improvements.

2 http://www.cad.zju.edu.cn/home/dengcai/Data/FaceData.html 3 http://www1.cs.columbia.edu/CAVE/software/softlib/coil20.php

Component study. We closely examined the learned representations for each component to analyze their latent semantics. In particular, we took the Yale dataset as an example. Like the previous experiment setting, we fixed the number of components V to 3, and applied k-means on the representation H(i) of each component to cluster the data into 3 clusters. The result is shown in Figure 2. We can see that the each representation has effectively captured some distinct information (such as unhappy or surprised expressions) which is reflected by a corresponding cluster. This result enables the understanding of the data from various perspectives in a semantic level, which would be hardly achievable by current NMFbased methods as they cannot identify components. Also, note that fromH(2) and H(3) , there is a common cluster: the right-lit faces. This is reasonable that although multiple representations usually describe data from different perspectives, they are not completely exclusive to each other mutually. We further tested MCNMF on a larger dataset COIL20. Again, the results are quite good and promising, with multiple clusters being obtained through different components (right rotation, pottery, etc). Figure 3 shows example results, due to page limitation.

Parameter analysis. We tested the effect of parameter α of MCNMF on the datasets. α varies from 0.01 to 0.05 with an increment of 0.01. Here we presented the accuracy of MCNMF with respect to α on Yale and ORL as examples. Seen from Figure 4, the accuracy varies slightly showing a relatively stable performance. Also, for all values of α, the performance of MCNMF is consistently better than NMF ( Table 1). For example, for Yale, the worst result of MCNMF is about 0.4182, while NMF only gets 0.4048.

We also tested the effect of the number of components V . Here we fixed α = 0.01 and varied V from 1 to 7 with an increment of 1. Seen from Figure 5, for both Yale and ORL, the accuracy with multiple components (V ≥ 2) is always better than MCNMF with V = 1 (NMF). Specifically, the accuracy increases sharply when V is tuned from 1 to 3, which indicates the effectiveness of MCNMF by exploring multiple components. Then the accuracy fluctuates slightly when V increases from 3 to 7. The fluctuation could be due to a compromise between the amount of features for each representation and the diverse information among them. When V

increases, more diverse information can be utilized. However, given a fixed k = ∑3i=1 k(i) , the increase of V will result in reduction of the feature dimension k(i) for each representation.

Convergence analysis. Having proven the convergence of our update rules of MCNMF in previous sections, here we experimentally demonstrate its convergence in Figure 6, where the horizontal axis is the number of iterations and the vertical axis is the value of objective function. It can be seen that the objective function values are non-increasing and drop sharply within 5 iterations on both datasets.

5 Conclusion

In this paper, we have proposed a Multi-Component Nonnegative Matrix Factorization (MCNMF) approach to find multirepresentation of data by exploring embedded latent components. Different from existing NMF-based approaches that seek for a single representation matrix, MCNMF learns multiple representations simultaneously. Utilizing Hilbert Schmidt Independence Criterion (HSIC) as a penalty term, MCNMF explicitly enforces the diversity of different data representations. Extensive experiments have demonstrated that MCNMF can not only obtain multiple representations with each one reflecting one property of data, but also improves the accuracy by aggregating multiple representations. For future work, we will extend MCNMF to semi-supervised MCNMF by utilizing the label information of data to obtain a much clearer correspondence with the real component of data.

Acknowledgements

This work was supported by Royal Society Newton Mobility grant, EU H2020 project (No. 691215) and National Natural Science Foundation of China (No. 61503281, 61502334).