Abstract
Nonnegative Matrix Factorization (NMF) is a cornerstone technique for parts-based data representation, yet standard unsupervised NMF often fails to capture the inherent ordinal relationships between data points. This paper introduces Ranking Preserving Nonnegative Matrix Factorization (RPNMF), a novel framework that incorporates ordinal relations—such as "item A is more similar to B than to C"—directly into the learning process. By enforcing these relative rankings in the low-dimensional latent space using triplet constraints and a differentiable softplus loss, RPNMF produces more discriminative and structured representations. Experimental evaluations on diverse image and sequential datasets demonstrate that RPNMF significantly outperforms traditional NMF and state-of-the-art semi-supervised methods in both clustering and classification tasks.
Introduction
Nonnegative Matrix Factorization (NMF) is widely utilized in machine learning to discover latent structures in data, such as identifying facial features from portraits. However, standard NMF is purely unsupervised, relying solely on raw feature reconstruction. While semi-supervised variants exist, they typically depend on absolute labels or pairwise constraints (must-link/cannot-link), which are often expensive to acquire and fail to capture the nuanced relative structure inherent in real-world data.
In many applications, ordinal information is more naturally available than absolute labels. For instance, consecutive frames in a video are inherently more related than distant ones, and a human can easily judge that an image of an "apple" is more similar to a "banana" than to a "ball." Standard NMF provides no guarantee that these intuitive rankings are preserved in the learned latent space. RPNMF addresses this gap by treating rankings as a form of "free" supervision to guide the factorization process.
Methods
RPNMF modifies the standard NMF objective function by adding a ranking preservation term to the reconstruction error. The goal is to find a basis matrix $W$ and a representation matrix $H$ such that $X \approx WH$ while maintaining the specified ordinal relations.
Triplet Constraints and Loss Function
The core of RPNMF lies in triplet constraints. For every triplet $(i, j, q)$ where data point $i$ is known to be more related to $j$ than to $q$, the model encourages the distance between their learned representations ($h_i, h_j$) to be smaller than the distance between ($h_i, h_q$). To make this optimization tractable, the authors employ a Softplus loss function ($f(t) = \log(1 + \exp(t))$) to approximate a ReLU-based ranking loss, ensuring the objective function remains differentiable.
Optimization
The paper derives new multiplicative updating rules for $W$ and $H$, proving their convergence to a local minimum. Despite the added complexity of triplet constraints, the algorithm maintains linear complexity relative to the number of data points, ensuring scalability for large datasets.
Experimental Setup
The model was evaluated on several benchmark datasets to test its versatility across static and sequential data:
- Image Benchmarks: Yale and ORL (face recognition), Coil20 (object recognition), and NHill (faces from the movie Notting Hill).
- Sequential Datasets: Cartoon (video frames) and Hdm05 (motion capture data).
Ordinal relations were generated using $p$-nearest neighbors or temporal order, simulating scenarios where such information is readily available without manual labeling.
Results and Discussion
RPNMF consistently outperformed state-of-the-art methods like GNMF, MCNMF, and NMFCC across all benchmarks. On the NHill dataset, RPNMF achieved a clustering accuracy (AC) of 92.64%, a significant jump from standard NMF's 77.04%. Similar gains were observed in classification tasks, with RPNMF reaching 96.25% accuracy on the ORL dataset.
Qualitative analysis through visualization (as seen in the figure above) reveals that RPNMF creates much tighter and more logically ordered clusters. While standard NMF often produces overlapping or scattered representations that "flip" relative distances, RPNMF successfully preserves the intended structural hierarchy in the latent space.
Conclusion and Future Work
RPNMF demonstrates that incorporating ordinal relations significantly enhances the discriminative power of NMF. By leveraging "free" supervision from rankings, the model achieves superior performance in clustering and classification while maintaining computational efficiency.
Future research may focus on optimizing triplet selection, as the current model's performance depends on the quality of the provided ordinal set. Additionally, exploring automated hyperparameter tuning for the ranking penalty could further simplify the application of RPNMF to new domains.
Summary updated