Generalized Discriminative Deep Non-Negative Matrix Factorization Based on Latent Feature and Basis Learning

1 Introduction

Data processing and analysis are of great importance in artificial intelligence area, and have a wide range of applications, such as face recognition [Karczmarek et al., 2019], computer vision [Buckler et al., 2018] and signal processing [Baraniuk, 2011]. However, a large amount of data collected from realword applications is often accompanied with irrelevant and redundant information, and the data usually exhibits highdimensionality. Such data probably results in a high computational cost in applications, and harms the generalization ability of a learning algorithm. To recover the latent representation and reduce the redundancy, various dimension reduction methods have been proposed, such as Principal Component Analysis (PCA) [Moore, 1981], Locally Preserving Projection (LPP) [He and Niyogi, 2003], Linear Discriminant Analysis (LDA) [Li and Yuan, 2004] and Non-negative Matrix Factorization (NMF) [Lee and Seung, 1999].

As a popular and promising dimensionality reduction method, NMF decomposes a non-negative data matrix X into a product of two non-negative matrices: the latent basis matrix W and the latent feature matrix H, and treats the feature matrix as the latent attribute representation of the original data. Due to the non-negativity constraints, NMF enables to learn part-based representation by only allowing additive combination, that leads to better interpretability in practice. As a variant of NMF, semi-NMF [Ding et al., 2008] relaxes non-negativity constraints on the basis matrix and the data matrix, which extends the applicability of NMF when the data is not strictly positive. It can be interpreted from the clustering perspective: the basis matrix contains cluster centroids, while the feature matrix indicates the cluster assignment. In addition to the above unsupervised NMF methods, semi-supervised NMF seeks to utilize the supervised prior label information in data. According to different ways of using the supervised information, these methods can be roughly categorized into hard constriant methods and soft constriant methods [Chen et al., 2022]. The hard constraint methods [Liu et al., 2011; Meng et al., 2019] learn exactly same representation for samples with same labels. In contrast, the soft constraint methods [Babaee et al., 2016; Lan et al., 2014] utilize partial label information by soft regularization, that allows for similar but distinct representations for samples associated with same labels.

The above methods essentially employ a single-layer structure, that only takes the shallow information of data into account. However, it is possible that data contains complex hierarchical structure information, which conventional singlelayered methods cannot extract. Therefore, deep NMF in a multi-layer structure has been proposed [Wisdom et al., 2017; Liu et al., 2017]. These methods build the multi-layer network by further decomposing either the feature matrix or the basis matrix into multiple components [Trigeorgis et al., 2016; Zhao et al., 2021]. They extract latent hierarchical features from the complex data, and obtain a multi-layer feature or basis representation. In addition, semi-supervised deep NMF [Trigeorgis et al., 2016; Meng et al., 2019] is proposed to further improve the performance by using a limited number of labels. Much success has been achieved by deep NMF, however, there are still some limitations. 1) Most deep NMF methods focus on feature decomposition, which fails to model high-level and local basis that consists of lowlevel representations, while recently proposed deep basis decomposition ignores the multi-layer feature representation of data. 2) Current NMF-based methods employ either deep or shallow models, but the shallow model cannot capture hierarchical representations, while the deep model does not always perform well when data is insufficient or exhibits simple representation. 3) Most deep NMF [Zhao et al., 2021] models are unsupervised and thus ignore the prior label information. Even though a few semi-supervised deep NMF models [Meng et al., 2019] are proposed, they usually impose hard constraint such that samples from the same class have exactly the same multi-layer representation, which is too restrictive in practice. Some graph regularized methods [Trigeorgis et al., 2016] implement soft constraint, but they need a quadratic complexity w.r.t. the number of samples, making it intractable on large-scale data.

To overcome these limitations, Generalized Deep NonNegative Matrix Factorization (GDNMF) is proposed, which generalizes several NMF and Deep NMF methods in a unified framework. GDNMF enables to extract hierarchical feature representations based on multi-level basis, by conducting both feature and basis decomposition (For Limitation 1). To further improve the latent representation, it mutually reinforces the shallow model and the deep model, such that both simple linear information and complex non-linear structure can be saved (For Limitation 2). Moreover, by treating the supervised information as soft constraints in multi-layer data representation, semi-supervised GDNMF is proposed to utilize the labels in a discriminative manner (For Limitation 3). An efficient optimization algorithm is developed in linear complexity w.r.t. the data size, and experimental results on five real-world datasets demonstrate its superior performance compared with state-of-the-art NMF-based methods. The contributions are summarized as follows:

1. A novel Deep NMF method, named GDNMF, is proposed by simultaneously performing deep factorization on features and bases, which enables to learn a hierarchical data representation based on multi-level basis.
2. GDNMF incorporates linear shallow model and nonlinear deep model in a single architecture, which is flexible enough to handle various practical applications and unifies several NMF and deep NMF methods.
3. Semi-supervised GDNMF is developed to use the limited label information in a discriminative way.
4. Extensive experiments on various real-world datasets verify the effectiveness of GDNMF.

2 RelatedWorks

2.1 Non-Negative Matrix Factorization (NMF)

For a non-negative data matrix X ∈ Rp×n + , NMF [Lee and Seung, 1999] decomposes X into a product of two lowdimensional non-negative matrices W and H. Semi-NMF [Ding et al., 2008] relaxes the non-negativity constraints on the data matrix X and the basis matrix W, leading to a wider range of applications. To encode geometrical information, GNMF [Cai et al., 2010] constructs an affinity graph over samples, and obtains improved generalization ability.

SeaNMF [Shi et al., 2018] uses a block coordinate descent algorithm, and incorporates the word-context semantic correlations into the model to discover topics for the short texts. IWNS-NMF [Sabzalian and Abolghasemi, 2018] is proposed to find localized and part-based representations. NMF-LCAG [Yi et al., 2019] introduces a locality constrained graph to discover the latent manifold structure of the data, where the weight matrix of graph and low-dimensional features of data can be learned together. KLS-NMF [Peng et al., 2021a] reveals inherent geometric property of the data, by learning local similarity and clustering in a mutually reinforcing way.

For semi-supervised NMF, CNMF [Liu et al., 2011] utilizes the partial label information as hard constriant, making samples from the same class share the same low-dimensional representations, and thus it guarantees that data with the same labels are grouped into the same clusters. Different from CNMF, DNMF [Babaee et al., 2016] utilizes the label information via a discriminative regularization, which does not necessarily map the samples with the same label into an identical latent representation. RDNMF-SLC [Tong et al., 2019] decomposes the data matrix into three matrices: basis matrix, auxiliary matrix and soft label constraint matrix, and learns a disciminative and robust feature representation. PCMF [Chen et al., 2019] seeks to make the data points from the same class more likely to be merged together in the latent space. CSNMF [Peng et al., 2021b] adopts a correntropy based loss function in constrained NMF to suppress the influence of outliers.

2.2 Deep NMF

Deep NMF has been proposed to explore hierarchical features from the complex data, which improves performance in terms of data representation and clustering. [Trigeorgis et al., 2016] proposes Deep semi-NMF (DSNMF), which progressively decomposes the original data matrix X into m+ 1 factors by X ≈ W1W2 · · ·WmHm. It automatically learns a hierarchy of representations for clustering. Different fromDSNMF, that factorizes the feature matrix layer by layer, [Zhao et al., 2021] proposes the deep nonnegative basis matrix factorization (DNBMF) that performs deep factorization on the underlying basis matrix by X = WmHm · · · H2H1. To make the basis vectors sparse, RDNBMF [Zhao et al., 2021] imposes a sparse-inducing regularization term on each layer, and achieves better performance in experiments. In GSDNMF [Fang et al., 2018], the L1 regularizers on both endmember and abundance matrices are imposed to promote sparsity, and the graph regularization in each layer is incorporated to remain the geometric structure. PDNMF [Zhao et al., 2022] adds a basis image reconstruction step to the successive steps of factorization, which helps the basis image to maintain robust feature representation. To enhance the discriminativity of learned features, DDSNnet [Wang et al., 2021] adpots similarity measurements between input data and hidden features as a regularization term, which is beneficial to preserve intrinsic information of original data.

Recently, semi-supervised Deep NMF methods have been proposed to take advantage of the limited prior information. Deep Weakly-Supervised Factorization (Deep WSF) [Trigeorgis et al., 2016] constructs a Laplacian matrix based on the prior label knowledge and uses it to regularize the objective function. SGDNMF [Meng et al., 2019] utilizes the dualhypergraph Laplacian regularization to capture the high-order relations among data points and enforce the partial label information via a label constraint matrix. By introducing both the global loss and the central loss of the soft label constraint matrix, Deep DRNMF-SLC [Tong et al., 2019] acquires a hierarchical and discriminative data representation. Based on hierarchical non-linear feature extraction, JDSNMF [Moon and Lee, 2021] captures shared latent features from the complex multi-omics data.

Existing deep NMF methods focus on decomposing either the feature matrix or the basis matrix, and are typically constrained in either shallow architectures or deep architectures with hard constraints of labels. In contrast, the proposed GDNMF progressively factorizes both features and bases, so that hierarchical feature representation based on multi-level basis can be extracted. Moreover, it incorporates linear shallow model and non-linear deep model in a unified architecture, and is extended to utilize the label prior information in a discriminative manner.

3 Preliminary

3.1 Notations

The original data is presented as X = [x1, x2, · · · , xn] ∈ Rp×n , where the i-th column xi denotes a sample with p features. Let Y ∈ {0, 1}c×n represent the label matrix and c denote the number of classes. In the semi-supervised setting, only the first q samples (columns) of Y are labeled, and the rest (n-q) columns are zero. Let ˆX denote the reconstructed X i.e., ˆX = WH, where W ∈ Rp×k and H ∈ Rk×n denote the basis matrix and the feature matrix, respectively, and k is the latent dimension. Tr(·) denotes the matrix trace, ∥ · ∥F is the Frobenius norm with ∥X∥F = √Tr(XT X), and ⊙ denotes the element-wise product.

3.2 Deep NMF with Feature Decomposition

DSNMF [Trigeorgis et al., 2016] decomposes the feature matrix H into m layers according to:

where Hi = Wi+1Hi+1, i = 1, 2, · · · ,m- 1, Wi is the basis matrix of the i-th layer, and Hi is the corresponding feature matrix. Compared with shallow NMF, DSNMF enables to capture a better low-dimensional data representation. Non-linear DSNMF introduces a non-linear squashing function between successive layers to approximate the non-linear manifold in the data. However, only the basis matrix W1 learned in the first layer is directly related to the original data, which only reflects the shallow local information, and thus DSNMF cannot model high-level and local basis.

3.3 Deep NMF with Basis Decomposition

Different from deep feature factorization, DNBMF [Zhao et al., 2021] decomposes the basis matrix W by

where Wi = Wi+1Hi+1, i = 1, 2, · · · ,m - 1. By performing deep factorization on the basis matrix, it obtains the underlying basis matrix which can reflect the deep local characteristics of the samples. However, since only the feature matrix H1 in the first layer is directly related to X, it ignores hierarchical data representation.

4 Methodology

4.1 Deep Feature and Basis Decomposition

Currently, no deep feature decomposition method considers the high-level and local basis, while no deep basis counterpart can capture the hierarchical feature representation. To overcome the limitation, we propose to simultaneously decompose features and bases in deep NMF. Specifically, at the first layer of the deep model, we decompose the data matrix X ∈ Rp×n into three matrices: F1 ∈ Rp×k1 , S1 ∈ Rk1×k2 and G1 ∈ Rk2×n , and reconstruct X by

where F1 is the basis matrix, G1 is the feature matrix and S1 is an auxiliary matrix that stores the interactions between F1 and G1. Then the following deep factorization can be conducted for both basis matrix F1 and feature matrix G1. For basis decomposition, we iteratively decompose the basis matrix F1 layer by layer, according to Fi ≈ Fi+1SLi+1 , where Fi is the basis matrix at the i-th layer, and SLi is the corresponding auxiliary matrix. Thus, the basis decomposition can be expressed as:

where m1 is the number of layers for basis decomposition. Similarly, for feature decomposition, we iteratively decompose the feature matrix G1 layer by layer, according to Gi ≈ SRi+1Gi+1, where Gi is the feature matrix at the i-th layer, and SRi is the corresponding auxiliary matrix. Thus, the feature decomposition can be expressed as:

where m2 is the number of layers for feature decomposition.

Since real-word data may exhibit deep non-linear hierarchical structures, the linear decomposition may fail to capture possible non-linearity among different levels of the latent features and bases. To address this problem and enhance the model's expressibility, a non-linear function g(·) 1 is introduced for the transformation between successive layers, i.e. ˆFi = g(Fi+1SLi+1 ), and ˆGi = g(SRi+1Gi+1). Then the optimization problem is formulated as:

1 Some commonly used non-linear functions include x2 , sigmoid(x) and tanh(x). In experiments, we set g(x) = x2 .

The non-linear function g(·) applied between successive layers helps to extract features of classes that are non-linearly separable in the initial input space, which enhances the model's expressibility and improves the data representation. Moreover, Deep Feature and Basis Decomposition (Deep FBD) conducts deep decomposition on the basis matrix and the feature matrix simultaneously, which learns a hierarchical data representation based on multi-level basis. Fig. 1 shows an example of Deep FBD.

4.2 Incorporating Shallow and DeepModels

Deep NMF shows its performance advantage compared with classical NMF in previous works [Trigeorgis et al., 2016; Zhao et al., 2021], as it can deal with complex data and obtain hierarchical structure of latent representations. However, when data is insufficient or essentially exhibits a simple latent structure, which can be easily modeled by a linear mapping, the deep structure in deep NMF may complicate the learning process, usually at high computational cost. To address this problem, we propose to incorporate shallow linear model and deep non-linear model together in a unified architecture, to capture various types of information during data representation. To this end, instead of directly minimizing the difference between X and its reconstruction ˆF1S1 ˆG1 in (6), an extra linear representation of feature decomposition Gm2 from the last layer is used to approximate the difference X - ˆF1S1 ˆG1. Therefore, we formulate the optimization problem of Generalized Deep Non-Negative Matrix Factorization (GDNMF) as:

In (7), ˆF1S1 ˆG1 is obtained by a deep nonlinear model to capture non-linear complex hierarchical information, while WGm is modeled by a shallow linear model to capture linear information, withWbeing the linear basis matrix. Obviously, when the non-linear part is omitted, GDNMF becomes NMF [Lee and Seung, 1999]. When the linear part is omitted, GDNMF becomes DSNMF [Trigeorgis et al., 2016] and DNBMF [Zhao et al., 2021] once m1 = 1 and m2 = 1, respectively. In this way, GDNMF unifies and generalizes several existing NMF and Deep NMF methods, and thus it is flexible enough to handle various practical applications.

4.3 Semi-Supervised GDNMF

GDNMF actually ignores the prior label information, but utilizing such label information is the key for performance improvement. In this section, we propose Generalized Discriminative Deep Non-Negative Matrix Factorization (GD2NMF) to use the limited labeled data in the semisupervised setting.

Similar with the reconstruction of X in GDNMF, we consider that both deep information and shallow information contribute to the reconstruction of Y. Specifically, Y is reconstructed by a summation of linear transformations of deep nonlinear data representation Gm2 and shallow linear data representation G1. To this end, we propose a discriminative regularization that is expressed as:

where U and V are weight matrices, and Q is an auxiliary matrix defined as

In the semi-supervised setting, only the first q samples are associated with labels (q < n), and introducing Q helps (8) to focus on the reconstruction of the labeled ones. By combining (7) and (8), we obtain the optimization problem of GD2NMF:

where α is a positive hyperparameter that makes a tradeoff between unsupervised information and supervised information. Thanks to a soft constraint regularization, samples from the same class have similar hierarchical latent representations, rather than exactly the same multi-layer representation which is too restrictive in practice. Therefore, GD2NMF not only conducts factorization on features and bases by a joint architecture consisting of both shallow and deep models, but also utilizes label information in a discriminative manner, leading to improved generalization. An example of the frameworks of both GDNMF and GD2NMF is shown in Fig. 1.

5 Optimization Algorithm

In this section, we present the optimization algorithm for GD2NMF in (10), and the optimization algorithm of GDNMF can be simply developed by setting α = 0. The algorithm is divided into two stages: pre-training and fine-tune. For pre-training, we solve the sub-problems independently for all layers. Afterwards, we initialize the model in (10) by the pretrained weights and fine-tune it by an alternating algorithm with gradient backpropagation.

5.1 Pre-Training

In pre-training, for basis decomposition we solve the following sub-problem layer by layer,

It is a non-convex problem with non-negative constraint, so we fix Fi+1 to update SLi+1 , and vice versa, leading to

For feature decomposition, we independently solve a similar sub-problem for the i-th layer, i.e.,

Similarly, the closed form solutions are:

5.2 Fine-Tune

In the fine-tune stage, we solve the optimization problem of GD2NMF in (10) based on alternating optimization. Let O denote the objective value in (10). The algorithm repeats the following steps until convergence.

Update F

To optimize (10) over F, we solve the following sub-problem:

Based on the chain rule of derivatives, we get the gradient w.r.t. F for the i-th layer,

and the derivative w.r.t. F1:

Update S

Similarly, we can get the gradients w.r.t. SLi and SRi based on the chain rule,

Update G

The gradient w.r.t. Gi based on the chain rule is obtained as,

These gradients on updating F, S and G are propagated backwards in the multi-layer model, and in a specific layer, gradient descent is used to update the layer weights once gradients from the previous layer are received.

Update W, V and U

We derive the multiplicative update rules as follows:

5.3 Analysis on Computational Complexity

The detailed optimization, pseudocode and code of GD2NMF are provided in the supplement 2 . Let k1 and k2 denote the maximum latent dimensions of basis matrices and feature matrices, respectively. For pre-training, the computational complexities of basis decomposition and feature decomposition are O(m1(k1k2p + k2 1 p)) and O(m2(k1k2n + k2 2 n)), respectively. For fine-tune, the bottleneck is updating F, S and G, which needs O(m1k2pn), O((m1 + m2)k1pn) and O(m2k2n(c + k2)), respectively. Thus, the total time complexity of the algorithm is linear w.r.t. the data size.

6 Experiment

6.1 Experimental Settings

Datasets

Five real-world datasets, including ARface 3 , CMUPIE 4 , Yale 5 , Caltech101-20 6 and COIL20 7 , are used in experiments. The statistics of used datasets are reported in Table 1, and more details are given in the supplement.

Compared Methods

For unsupervised experiments, we compare GDNMF with six unsupervised NMF-based methods, including NMF [Lee and Seung, 1999], semi-NMF [Ding et al., 2008], GNMF [Cai et al., 2010], NeNMF [Guan et al., 2012], DSNMF [Trigeorgis et al., 2016] and DNBMF [Zhao et al., 2021]. For semi-supervised experiments, we compare GD2NMF with five semi-supervised NMF-based methods, including CNMF [Liu et al., 2011], DNMF [Babaee et al., 2016], Deep WSF [Trigeorgis et al., 2016], DENMF [Wu et al., 2019] and SGDNMF [Meng et al., 2019].

2 https://github.com/Gabrielx0098/GD2NMF

3 https://www2.ece.ohio-state.edu/ aleix/ARdatabase.html

4 https://www.cs.cmu.edu/afs/cs/project/PIE/MultiPie/MultiPie/Home.html

5 http://cvc.cs.yale.edu/cvc/projects/yalefaces/yalefaces.html 6 http://www.vision.caltech.edu/Image Datasets/Caltech101/ 7 https://www.cs.columbia.edu/CAVE/software/softlib/coil20.php

Configuration

In GDNMF and GD2NMF, the decay rate r, which is the ratio of dimensions between successive layers, is selected from {0.3, · · · , 0.7}, and the non-linear function g(·) is set to g(x) = x2 . The value of α used in GD2NMF is selected from {10-3 , 10-2 , · · · , 102 }. For deep NMF methods, the number of layers is set to m = 2. Non-linear function g(·) in DSNMF and Deep WSF is set to g(x) = 1.7159tanh(0.667x) as recommended by the authors. The value of p used in GNMF is selected from {2, 3, ..., 9}. Other hyperparameters used in the compared methods are set according to the recommendation of the original papers. For semi-supervised methods, in experiments we randomly select 10% data points as labeled data. To evaluate the clustering results, after obtaining the latent representation H, we run k-means on H for ten times with different initializations and calculate the mean results. In the experiment, three evaluation metrics, including cluster accuracy (ACC) [Xu et al., 2003], normalized mutual information (NMI) [Cai et al., 2008] and purity [Marutho et al., 2018] are used to measure the clustering performance. ACC computes the percentage of correctly predicted cluster labels, NMI is used in clustering applications to measure the similarity of two clusters, and Purity measures how well classes are distributed on various clusters.

6.2 Experimental Results

Evaluation on Clustering Performance

Table 2 shows the clustering results of unsupervised methods and semi-supervised methods on five datasets, where the best and the second-best results are highlighted in boldface and underlined, respectively. From Table 2, we can see that for unsupervised methods, GDNMF outperforms other comparing methods in most cases. Specifically, on the CMUPIE dataset, compared with the second-best method, GDNMF achieves performance improvement by 9.63%, 8.85% and 18.83% in terms of ACC, NMI and Purity, respectively. On the ARface dataset, DSNMF achieves the best results and GDNMF performs the second-best. For semi-supervised methods, GD2NMF outperforms other comparing methods in most cases. On the CMUPIE dataset, compared with the second-best method (Deep WSF), GD2NMF achieves performance improvement by 9.24%, 7.7% and 11.65% in terms of ACC, NMI and Purity, respectively. Moreover, GD2NMF usually outperforms GDNMF, which validates the effectiveness of using the limited supervised information. The probable explanations for the performance superiority of GDNMF and GD2NMF can be summarized as follows: 1) They perform deep basis and feature decomposition simultaneously, which helps to learn a hierarchical data representation based on multi-level basis. 2) Both methods incorporate shallow model and deep model in a unified architecture, which can capture both linear and nonlinear information. 3) GD2NMF further improves the performance by utilizing prior information in a discriminative manner. However, GDNMF and GD2NMF didn't achieve the best results on ARface and COIL20, probably because the deep model is too complex for these two datasets, and more efforts should be paid for hyperparameter tuning.

Ablation Study 8

To evaluate the effectiveness of deep feature and basis decomposition in GD2NMF, we conduct an experiment to compare the clustering results of GD2NMF with its two degraded variants: GD2NMF with only basis decomposition (GD2NMFb) and GD2NMF with only feature decomposition (GD2NMFf ). The experiment is conducted on the CMUPIE, Yale and COIL20 datasets, and results are shown in Fig.2. Similar results are observed on other datasets. For fair comparison, the hyperparameters are set to the same values. From Fig.2, we can see that GD2NMF achieves better performance than both GD2NMFb and GD2NMFf on the three datasets, which validates our assumption that simultaneously performing deep factorization on features and bases leads to improved data representation and clustering performance.

To verify the effectiveness of incorporating deep and shallow models in GD2NMF, we conducted an experiment on CMUPIE to compare the performance of GD2NMF, GD2NMF in shallow architecture (GD2NMFs) and GD2NMF in deep architecture (GD2NMFd). In the experiment, we extract different number of classes from the original CMUPIE dataset, and generate six datasets by varying the number of classes from 20 to 60 by step 10. Results in NMI are shown in the left subfigure of Fig.3. Obviously, by combining shallow and deep models in a single architecture, GD2NMF consistently achieves a better performance than its two variants, which demonstrates that mutually reinforcing shallow and deep models indeed helps to boost the generalization performance. In addition, we conduct an experiment to evaluate the performance of GD2NMF by varying the number of layers from 1 to 5, and report the results in the right subfigure of Fig.3. We can see that a two-layer structure leads to the best performance. When the number of layers is greater than 2, its performance drops significantly, probably because the structure is too complex and easy to overfit.

8 More experimental results are provided in the supplement.

7 Conclusion

This paper proposes a novel deep NMF method, named GDNMF, which learns a hierarchical data representation based on multi-level basis by simultaneously performing deep factorization on the feature matrix and the basis matrix. GDNMF incorporates linear shallow model and non-linear deep model in a unified architecture, that generalizes several existing NMF-based methods. Moreover, semi-supervised GDNMF is proposed to utilize partial label information in a discriminative way. Experiments on five real-world datasets show the effectiveness of GDNMF.