Ranking Preserving Nonnegative Matrix Factorization

Jing Wang, Feng Tian, Weiwei Liu, Xiao Wang, Wenjie Zhang, Kenji Yamanishi

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.

Conceptual framework of RPNMF, integrating original data (X) with ordinal relations (L) to produce an orderly low-dimensional representation (H).

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.

Comparison of data representations: (a) original data with ordinal constraints, (b) latent space learned by standard NMF, and (c) latent space learned by RPNMF, showing superior cluster separation and ranking preservation.

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

Abstract

Nonnegative matrix factorization (NMF), a well-known technique to find parts-based representations of nonnegative data, has been widely studied. In reality, ordinal relations often exist among data, such as data i is more related to j than to q. Such relative order is naturally available, and more importantly, it truly reflects the latent data structure. Preserving the ordinal relations enables us to find structured representations of data that are faithful to the relative order, so that the learned representations become more discriminative. However, current NMFs pay no attention to this. In this paper, we make the first attempt towards incorporating the ordinal relations and propose a novel ranking preserving nonnegative matrix factorization (RPNMF) approach, which enforces the learned representations to be ranked according to the relations. We derive iterative updating rules to solve RPNMF's objective function with convergence guaranteed. Experimental results with several datasets for clustering and classification have demonstrated that RPNMF achieves greater performance against the state-of-the-arts, not only in terms of accuracy, but also interpretation of orderly data structure.
BibTeX
@inproceedings{wang2018ranking,
  author = {Jing Wang and Feng Tian and Weiwei Liu and Xiao Wang and Wenjie Zhang and Kenji Yamanishi},
  title = {{Ranking Preserving Nonnegative Matrix Factorization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/385},
}
Figure