Abstract
Traditional Non-negative Matrix Factorization (NMF) is an unsupervised learning technique that often fails to leverage available label information. This paper presents Constrained Non-negative Matrix Factorization (CNMF), a semi-supervised framework that incorporates class labels as hard constraints. By requiring data points with the same label to share identical coordinates in the reduced feature space, CNMF produces more discriminative representations. Experimental results on face recognition benchmarks demonstrate that CNMF consistently outperforms standard NMF and graph-regularized variants in both clustering accuracy and mutual information without the need for manual hyper-parameter tuning.
Introduction
Non-negative Matrix Factorization (NMF) has become a fundamental tool in machine learning for its ability to learn parts-based representations of high-dimensional data. However, its purely unsupervised nature limits its effectiveness when partial label information is available. While semi-supervised extensions like Graph-regularized NMF (GNMF) have been proposed, they typically treat labels as "soft" constraints via regularization terms. These methods often require extensive manual tuning of regularization parameters and do not provide a mathematical guarantee that points from the same class will be grouped together in the latent space.
To address these limitations, this work introduces Constrained NMF (CNMF). Unlike previous approaches, CNMF treats label information as a "hard" constraint, physically forcing the decomposition to map same-class instances to the same coordinates.
Methodology
The core of CNMF lies in the redefinition of the coordinate matrix $V$ in the standard NMF objective $X \approx UV^T$. The authors introduce a label constraint matrix $A$ and an auxiliary matrix $Z$, such that $V = AZ$.
In this formulation:
- Matrix $A$ is an indicator matrix derived from known labels. If two data points belong to the same class, their corresponding rows in $A$ are identical.
- Matrix $Z$ is the learned representation.
By substituting $V = AZ$ into the NMF objective, the algorithm is constrained to assign identical coordinates to all points sharing a label. The authors developed iterative update rules for $U$ and $Z$ that are guaranteed to converge to a local optimum, providing a parameter-free learning process that avoids the complexities of hyper-parameter optimization.
Experimental Results
The performance of CNMF was evaluated on two standard datasets: the AT&T Face Database and the Yale Face Database. The evaluation focused on two primary metrics: Accuracy (AC) and Normalized Mutual Information (MI).
AT&T Face Database
On the AT&T dataset, which contains 400 images of 40 subjects, CNMF demonstrated significant improvements over baseline methods. As shown in Figure 1, CNMF maintains a higher accuracy and mutual information score across varying numbers of clusters compared to standard NMF, NTF, and graph-based methods like GNMF.
CNMF achieved an average accuracy of 82.7%, outperforming the next best method (NMF) by 3.4%.
Yale Face Database
The Yale dataset presents a greater challenge due to extreme lighting variations. Even in this difficult scenario, CNMF's hard constraints proved effective.
As illustrated in Figure 2, CNMF consistently yields higher MI scores and more stable accuracy than its competitors. It reached an accuracy of 59.2%, a 2.0% improvement over SemiGNMF.
Discussion and Conclusion
The primary advantage of CNMF is its ability to create highly discriminative clusters by enforcing label consistency directly within the factorization process. By moving from soft regularization to hard constraints, the model eliminates the need for parameter tuning, making it more robust and easier to deploy in real-world scenarios.
However, the "hard" nature of the constraints makes the algorithm sensitive to label noise; mislabeled data will inevitably distort the learned basis vectors. Future work may explore hybrid approaches that combine the stability of hard constraints with mechanisms to handle label uncertainty. Overall, CNMF represents a significant step forward in semi-supervised dimensionality reduction, offering a principled and efficient way to incorporate prior knowledge into matrix factorization.
Summary updated