Abstract
Traditional Non-Negative Matrix Factorization (NMF) often fails when data belongs to multiple distinct groups, such as different individuals' faces or various handwritten digits. This paper introduces MM-NMF, a novel algorithm that explicitly models the unique geometric structure of individual manifolds. By preventing "information leaks" between different classes, MM-NMF significantly improves clustering accuracy and produces more interpretable basis vectors.
Introduction
Non-Negative Matrix Factorization (NMF) is a fundamental technique in machine learning for dimensionality reduction and clustering. It decomposes a high-dimensional data matrix into two smaller, non-negative matrices: a "basis" matrix representing the building blocks of the data, and a "coefficient" matrix representing how to combine those blocks.
Modern approaches often rely on the "manifold assumption," which suggests that high-dimensional data actually lies on a much simpler, low-dimensional surface. However, most NMF variants assume all data resides on a single manifold. In reality, datasets like face databases or digit collections consist of multiple manifolds—one for each class. When these manifolds overlap or pass near each other in Euclidean space, standard algorithms may incorrectly connect points from different classes, blurring the boundaries and degrading clustering performance.
The MM-NMF Approach
The authors propose Multiple Manifold NMF (MM-NMF), which employs a three-step approach to respect class-specific geometry:
- Mining Intrinsic Geometry: Instead of using simple Euclidean distance, the algorithm uses $L_1$-norm minimization (sparse coding) to identify neighbors. This identifies points that can best reconstruct a specific data point, naturally selecting neighbors from the same manifold even if points from a different class are physically closer.
- Objective Function: The model combines standard NMF reconstruction error with two constraints:
- Sparsity: $L_1$ regularization on the coefficient matrix ensures each data point is represented by only a few basis vectors.
- Manifold Regularization: A term that ensures points neighboring each other on a manifold in the original space remain close in the low-dimensional representation.
- Optimization: The paper derives new multiplicative update rules for the basis ($U$) and coefficient ($V$) matrices, providing a mathematically guaranteed path to a local minimum.
Experimental Results
The algorithm was evaluated on the ORL Face Database (400 images of 40 individuals) and the USPS Handwritten Digits dataset. MM-NMF demonstrated significant quantitative improvements over standard NMF:
- ORL Faces: Clustering accuracy improved from 60.5% (Standard NMF) to 73.4% (MM-NMF).
- USPS Digits: Accuracy rose from 52.8% to 64.1%.
- Normalized Mutual Information (NMI): MM-NMF showed a consistent 10-13% improvement, indicating a much higher correlation between the clustering results and the ground truth.
Qualitative Insights
A key advantage of MM-NMF is the quality of the learned basis vectors. By respecting the multiple-manifold structure, the "parts" the algorithm learns become much more representative of specific classes.
As shown in the comparison above, standard NMF often produces basis vectors that are blurry mixtures of several different people. In contrast, the basis vectors produced by MM-NMF are much cleaner and more interpretable.
By using sparse reconstruction as a filter, the algorithm naturally selects points from the same manifold and ignores "intruder" points from intersecting manifolds, leading to these superior, class-specific basis vectors.
Conclusion and Future Work
While MM-NMF offers substantial gains in accuracy and interpretability, it introduces additional computational overhead due to the $L_1$ minimization pre-processing step. Future work may focus on optimizing this step or extending the manifold-specific approach to "multi-label" data, where individual points might belong to multiple manifolds simultaneously.
Summary updated