Non-Negative Matrix Factorization (NMF)

The defining characteristic of NMF is the strict enforcement that all elements in the factor matrices W (document-topic) and H (topic-word) must be ≥ 0. This constraint forces a purely additive reconstruction of the original data.

• No negative weights mean no cancellation or subtraction between features
• Results in intuitive, parts-based representations where a document is a sum of its topics
• Contrasts with techniques like PCA or SVD, which allow negative components that are difficult to interpret semantically
• Mathematically, the objective is to minimize ||V - WH||_F subject to W ≥ 0, H ≥ 0

NMF is typically solved using iterative multiplicative update rules derived by Lee and Seung (1999). These rules guarantee non-negativity without explicit constraint enforcement.

• Update for H: H ← H * (W^T V) / (W^T W H)
• Update for W: W ← W * (V H^T) / (W H H^T)
• The element-wise multiplication and division ensure that if initialized with positive values, the matrices remain non-negative throughout optimization
• Convergence is guaranteed to a local minimum of the Frobenius norm objective
• Alternative solvers include projected gradient descent and coordinate descent methods

Each column of the H matrix represents a topic as a sparse, non-negative distribution over the vocabulary. Because contributions are additive, the top-weighted terms for each topic form highly coherent semantic clusters.

• A topic on 'machine learning' might show high weights exclusively for terms like algorithm, neural, training, gradient
• The sparsity induced by non-negativity often produces more distinct, separable topics than LDA in practice
• Each row of W gives the topic proportions for a document, representing exactly how much of each topic contributes to that document's term frequencies
• This dual interpretability makes NMF popular for exploratory text analysis and document clustering

NMF supports multiple loss functions that define how the reconstruction error is measured, each suited to different data characteristics.

• Frobenius Norm (||V - WH||_F): Assumes Gaussian noise; equivalent to minimizing squared error. Best for dense, normalized data
• Kullback-Leibler Divergence (D(V || WH)): Treats the factorization as a Poisson process; appropriate for count data like raw term frequencies
• The KL formulation corresponds to maximizing the likelihood under the assumption that V_ij ~ Poisson((WH)_ij)
• Choice of objective significantly impacts the sparsity and interpretability of the resulting factors

Unlike Latent Dirichlet Allocation (LDA), which is a generative probabilistic model, NMF is a deterministic matrix factorization. This distinction has practical implications for reproducibility and interpretation.

• NMF produces the same result given the same initialization and random seed, while LDA samples from a posterior distribution
• NMF makes no distributional assumptions about how documents are generated
• The absence of Dirichlet priors means NMF does not naturally model topic sparsity in documents, though regularization can be added
• For applications requiring exact reproducibility and deterministic outputs, NMF is often preferred over sampling-based methods

The NMF objective function is non-convex, meaning the solution depends heavily on the initial values of W and H. Poor initialization can lead to slow convergence or low-quality local minima.

• Random initialization: Simple but unreliable; multiple restarts are recommended
• NNDSVD (Non-negative Double SVD): Uses the SVD of the data matrix to seed factors, often yielding faster convergence and better solutions
• K-means clustering: Initialize H with cluster centroids for a data-driven starting point
• Best practice: Run NMF with multiple random seeds and select the factorization with the lowest reconstruction error
• Libraries like scikit-learn implement nndsvd or nndsvda as default initialization strategies

The foundational input data structure for NMF. A sparse matrix where rows represent documents, columns represent unique terms, and cell values represent term frequencies (often TF-IDF weighted). NMF factorizes this non-negative matrix V into two lower-rank non-negative matrices W (document-topic) and H (topic-term). The non-negativity constraint is critical because negative values in the DTM have no physical interpretation in text analysis.

The standard objective function for NMF optimization. The algorithm minimizes the squared Euclidean distance between the original matrix V and its reconstruction WH. The Frobenius norm is defined as the square root of the sum of absolute squares of matrix elements. Minimizing ||V - WH||²_F ensures the factorized matrices, when multiplied, approximate the original data as closely as possible while maintaining non-negative constraints.

The classic iterative optimization algorithm for NMF proposed by Lee and Seung. Instead of additive gradient descent, it uses element-wise multiplicative updates that naturally preserve non-negativity. The rules are:

• W update: W ← W ⊙ (VH^T) ⊘ (WHH^T)
• H update: H ← H ⊙ (W^TV) ⊘ (W^TWH) Where ⊙ is element-wise multiplication and ⊘ is element-wise division. Convergence is guaranteed because the Frobenius norm is non-increasing under these updates.

An alternative objective function for NMF that minimizes the generalized KL divergence between V and WH. This formulation is particularly suited for count data and Poisson-distributed text. The objective is: D(V || WH) = Σ(Vᵢⱼ log(Vᵢⱼ/(WH)ᵢⱼ) - Vᵢⱼ + (WH)ᵢⱼ). KL-NMF often produces sparser, more interpretable topics than Frobenius-based NMF because it penalizes reconstruction errors differently across frequency magnitudes.

The defining characteristic that distinguishes NMF from other matrix factorization techniques like PCA or SVD. Because all elements are constrained to be non-negative, NMF learns an additive, parts-based decomposition where topics are built by summing positive contributions. This contrasts with PCA's subtractive combinations. In text, this means each topic is represented by a positive weighted sum of words, making topics intuitively interpretable as collections of co-occurring terms without cancellation effects.

Regularization techniques applied to NMF to produce more interpretable, focused topics. By adding L1 regularization (lasso) penalties to the objective function, the algorithm forces many entries in W and H toward zero. This results in:

• Documents explained by fewer topics
• Topics defined by fewer, more specific words The sparsity parameter λ controls the trade-off between reconstruction fidelity and interpretability. Higher sparsity prevents topics from becoming diffuse mixtures of common words.