vault

Non-negative Matrix Factorization

5 min read

Non-negative Matrix Factorization

Non-negative Matrix Factorization (NMF) is a matrix decomposition technique introduced by Daniel Lee and H. Sebastian Seung in their seminal 1999 Nature paper “Learning the parts of objects by non-negative matrix factorization” and refined in their 2000 NeurIPS paper “Algorithms for Non-negative Matrix Factorization”. The defining constraint is that all entries of the factor matrices U ∈ ℝ_{≥0}^{m × k} and V ∈ ℝ_{≥0}^{n × k} are non-negative. Within recommender systems, NMF is a niche choice: it offers more interpretable latent factors than Funk SVD (the non-negativity constraint forces each factor to represent an “additive part” rather than allowing cancellation between positive and negative components), at some cost in predictive accuracy. NMF was originally developed for image and text analysis (where non-negativity of pixel intensities or word counts is natural), and was later adapted to collaborative filtering for cases where the non-negative constraint is itself meaningful — typically rating data on a non-negative scale, or count data where individual factors should represent additive contributions to total counts.

1. The Algorithm

Given a non-negative matrix R ∈ ℝ_{≥0}^{m × n}, NMF finds non-negative factor matrices U ∈ ℝ_{≥0}^{m × k} and V ∈ ℝ_{≥0}^{n × k} such that R ≈ U · Vᵀ. The objective is to minimize the reconstruction error subject to the non-negativity constraint:

min  ‖R − U · Vᵀ‖_F²    subject to    U ≥ 0,  V ≥ 0

where ‖·‖_F is the Frobenius norm (square root of the sum of squared entries).

The Lee & Seung 2000 paper proposed multiplicative update rules that preserve non-negativity at every step:

U[u, f]  ←  U[u, f]  ·  (R · V)[u, f]  /  (U · Vᵀ · V)[u, f]
V[i, f]  ←  V[i, f]  ·  (Rᵀ · U)[i, f]  /  (V · Uᵀ · U)[i, f]

These updates are guaranteed to monotonically decrease the loss. They preserve non-negativity because all quantities involved (factors, observed ratings, products) are non-negative — non-negative numerator divided by non-negative denominator times non-negative factor.

For sparse rating matrices, the update is restricted to observed entries (analogous to Funk SVD handling missing data), and SGD-based variants exist that are easier to scale.

2. Why Non-Negativity Yields Interpretability

The key conceptual difference between NMF and unconstrained MF is what the latent factors mean. In standard MF (Funk SVD, PMF), factors can be positive or negative, and the predicted rating Σ_f x_{u,f} · y_{i,f} can result from any combination of positive and negative contributions. A user might have factor 1 = +2, factor 2 = −1.5, and an item with factor 1 = +0.5, factor 2 = +1, contributing +1.0 and −1.5 respectively — a partial cancellation. The factors are not directly interpretable as “amounts of positive features.”

In NMF, all factors are non-negative. Each prediction Σ_f x_{u,f} · y_{i,f} is a sum of non-negative contributions. Each latent factor f represents an “additive feature” that is present in the user’s preference profile and present in the item’s content profile to some degree, with magnitude x_{u,f} and y_{i,f} respectively. This is what Lee & Seung called the “parts-based representation” — factors decompose the matrix into additive parts.

For movies, NMF factors might learn things like “amount of action content,” “amount of romance content,” etc., with each user having a non-negative degree of preference for each. The interpretability is qualitative — there is no guarantee any specific factor will correspond to a clean human-recognizable concept — but the structure is more amenable to inspection than unconstrained MF.

3. When to Use NMF

NMF is appropriate in recommender contexts when:

  • The interpretability of factors matters (regulated industries, explanation interfaces).
  • The data is naturally non-negative (count data, non-negative ratings).
  • Factors should additively contribute (no cancellation effects desired).

Do not use NMF when:

  • Predictive accuracy is the only goal — unconstrained MF typically beats NMF on RMSE/NDCG.
  • The data has natural negative values (e.g., 1-to-5 star ratings can be mean-centered to have negative entries; NMF cannot handle this without preprocessing).
  • You need implicit-feedback handling — NMF was designed for fully observed matrices; sparse-data adaptations are less mature than iALS.

4. Strengths

  • Interpretable factors. Parts-based representation is more amenable to inspection.
  • Mathematically clean updates. The multiplicative update rules are simple and provably monotonic.
  • Natural fit for non-negative data. Counts, intensities, non-negative ratings.
  • Connection to topic modeling. NMF is closely related to probabilistic topic models like LDA and pLSA.

5. Weaknesses

  • Lower predictive accuracy than unconstrained MF on standard benchmarks.
  • Multiplicative updates can be slow. Convergence is often slower than gradient methods.
  • Original formulation assumes fully observed matrix. Adaptations for sparse data exist but are less standard than Funk SVD.
  • Initialization-sensitive. NMF has multiple local minima (the factorization is not unique), and the result depends on initialization.

6. See Also

Graph View

Backlinks