Principle:Dotnet Machinelearning Matrix Factorization
| Knowledge Sources | |
|---|---|
| Domains | Machine Learning, Recommendation Systems, Linear Algebra |
| Last Updated | 2026-02-09 12:00 GMT |
Overview
Matrix factorization decomposes a sparse user-item interaction matrix R into two low-rank matrices P and Q such that R is approximately equal to P multiplied by Q transposed, enabling prediction of missing entries for recommendation and collaborative filtering tasks.
Description
In recommendation systems, the interaction between m users and n items is represented as a sparse matrix R of size m x n, where observed entries represent ratings, clicks, or purchases. Most entries are missing (unobserved). Matrix factorization finds two dense matrices:
- P of size m x k (user latent factor matrix)
- Q of size n x k (item latent factor matrix)
such that for each observed entry R(u, i), the dot product of the u-th row of P and the i-th row of Q approximates the true value. The k latent factors capture abstract concepts (e.g., genre preference, quality perception) that explain the observed interaction patterns.
Predictions for unobserved entries are computed as:
R_hat(u, i) = P(u, :) . Q(i, :)^T + b
where b is a global bias term. This enables recommending items to users based on predicted affinity scores.
Usage
Matrix factorization is the standard approach for:
- Collaborative filtering: Recommending products, movies, music, or content based on similar users' behavior
- Rating prediction: Estimating how a user would rate an unseen item
- Missing value imputation: Filling in sparse matrices when the data is believed to have low-rank structure
- Dimensionality reduction: Representing high-dimensional sparse user/item interactions as dense low-dimensional embeddings
Theoretical Basis
Problem Formulation
Given a partially observed matrix R with observed entries indexed by the set Omega, the goal is to minimize:
min_{P, Q} SUM_{(u,i) in Omega} (R(u,i) - P(u,:) * Q(i,:)^T)^2 + lambda_p * ||P||^2 + lambda_q * ||Q||^2
The first term is the reconstruction error over observed entries only. The regularization terms lambda_p and lambda_q prevent overfitting by penalizing large factor values, which is critical because the model has k * (m + n) parameters but only |Omega| observations (typically |Omega| is much less than m * n).
Stochastic Gradient Descent (SGD)
LIBMF uses stochastic gradient descent to optimize the factorization. For each observed entry (u, i, r):
- Compute the prediction error: e = r - P(u,:) * Q(i,:)^T
- Update user factors: P(u,:) <- P(u,:) + eta * (e * Q(i,:) - lambda_p * P(u,:))
- Update item factors: Q(i,:) <- Q(i,:) + eta * (e * P(u,:) - lambda_q * Q(i,:))
where eta is the learning rate. The updates are performed over multiple passes (epochs) through the shuffled set of observed entries.
Parallel SGD via Data Partitioning
LIBMF achieves parallelism by partitioning the sparse matrix into blocks. The matrix is divided into a grid of nr_bins x nr_bins blocks. At each step, a set of non-overlapping blocks (no shared rows or columns) is selected, and SGD updates within each block proceed independently on separate threads. This avoids write conflicts on the P and Q factor vectors without requiring locks.
The partitioning satisfies the constraint that if blocks (a, b) and (c, d) are processed simultaneously, then a != c and b != d. This guarantees that no two threads write to the same row of P or the same row of Q concurrently.
Loss Functions
LIBMF supports multiple loss functions selected via the fun parameter:
| Loss Function | Formula | Use Case |
|---|---|---|
| Squared error (L2) | (r - p . q^T)^2 | Explicit rating prediction |
| Absolute error (L1) | r - p . q^T| | Robust rating prediction |
| KL-divergence | r * log(r / (p . q^T)) - r + p . q^T | Non-negative data (counts) |
| Logistic loss | log(1 + exp(-r * p . q^T)) | One-class / implicit feedback |
Non-negative Matrix Factorization (NMF)
When the do_nmf flag is set, LIBMF constrains all entries of P and Q to be non-negative. This is achieved by projecting negative values to zero after each SGD update. NMF produces more interpretable factors (e.g., topic proportions) but may converge more slowly.
Rank Selection
The approximation rank k (number of latent factors) controls the bias-variance tradeoff:
- Small k (e.g., 8-16): High bias, low variance; captures only the strongest patterns; fast training
- Large k (e.g., 128-256): Low bias, high variance; captures subtle patterns but risks overfitting; slower training
In practice, k is selected via cross-validation (supported by MFCrossValidation) or by monitoring validation error during training (supported by MFTrainWithValidation).