vault

Factorization Machines

7 min read

Factorization Machines

Factorization Machines (FM) are a model class introduced by Steffen Rendle in his 2010 ICDM paper “Factorization Machines” that generalizes Matrix Factorization to arbitrary feature interactions. The model treats every input feature — user ID, item ID, demographic features, context, side-information — as having its own latent vector, and the prediction is a sum of (a) per-feature linear weights and (b) latent-vector dot products between every pair of input features. With only (k × num_features) parameters, FM can model interactions among hundreds or thousands of features, which would otherwise require prohibitively many parameters for a fully-factored interaction model. FM became influential because it bridged the gap between recommender-specific MF (which only models user-item interactions) and general feature-aware classifiers (which can use arbitrary features but cannot scale to high-cardinality categorical features). The Rendle group’s libFM reference implementation made the model accessible, and FM-based architectures continue to underlie production CTR (Click-Through Rate) prediction systems through descendants like DeepFM and xDeepFM.

1. The Model

Let x ∈ ℝ^d be a feature vector representing a single (user, item, context) instance. The features are typically a sparse representation: for each categorical attribute (user ID, item ID, category, day of week), a one-hot encoding contributes to x; continuous features (price, age) contribute their values directly.

The Factorization Machine prediction is:

ŷ(x) = w_0  +  Σ_{i=1}^{d}  w_i · x_i  +  Σ_{i=1}^{d} Σ_{j=i+1}^{d}  ⟨v_i, v_j⟩ · x_i · x_j

where:

  • w_0 ∈ ℝ is a global bias.
  • w_i ∈ ℝ is a per-feature linear weight (one scalar per input feature).
  • v_i ∈ ℝ^k is a per-feature latent vector (one k-dimensional vector per input feature).
  • ⟨v_i, v_j⟩ = v_iᵀ · v_j is the dot product between two feature latent vectors.
  • x_i · x_j is the product of the two feature values; for one-hot features this is 1 if both are active and 0 otherwise.
  • The double summation is over all unordered pairs of distinct features, capturing pairwise interactions.

The key property: instead of learning a separate weight w_{i,j} for every pair of features (which would require O(d²) parameters), FM factorizes each pairwise weight as the dot product of two k-dimensional vectors, requiring only O(d · k) parameters total. For d = 10⁴ features and k = 16, this is 1.6 · 10⁵ parameters versus 5 · 10⁷ for a fully-parameterized quadratic model.

2. Connection to Matrix Factorization

When the feature vector x consists only of one-hot user and item indicators (and no other features), the FM prediction simplifies to:

ŷ(x_u, x_i) = w_0 + w_u + w_i + ⟨v_u, v_i⟩

which is exactly biased matrix factorization (μ + b_u + b_i + x_uᵀ · y_i). FM is therefore a strict generalization of MF: with only user and item features, it recovers MF; with additional features (categorical or continuous), it extends MF to use those features.

The interpretation is that every feature, not just user and item, has a latent vector. Latent vectors are pulled together when their features co-occur in observed examples and pulled apart when they do not. The model learns affinities between any pairs of features — user-item interaction, user-category interaction, user-day-of-week interaction, item-day-of-week interaction, etc. — through the same factorized parameterization.

3. Efficient Computation of the Pairwise Sum

The naive evaluation of the FM pairwise-interaction term is O(d² · k) per prediction — prohibitive for high-dimensional sparse x. Rendle showed the term can be computed in O(d · k) time:

Σ_{i<j} ⟨v_i, v_j⟩ · x_i · x_j  =  (1/2) · Σ_{f=1}^{k}  ( (Σ_{i=1}^{d} v_{i,f} · x_i)²  −  Σ_{i=1}^{d} v_{i,f}² · x_i² )

where v_{i,f} is the f-th component of feature i’s latent vector. The inner sums are single passes over the (sparse) feature vector, so the total cost per prediction is O(d_active · k) where d_active is the number of non-zero features in x. For sparse one-hot encodings this is the number of categorical attributes, typically a handful — extremely fast.

This trick makes FM tractable on datasets with millions of features, which is impossible for naive quadratic models.

4. Training

FM can be trained with stochastic gradient descent on any standard loss:

  • Squared error for regression / rating prediction.
  • Cross-entropy for binary classification (e.g., CTR prediction).
  • BPR-style pairwise loss for ranking.

The gradient of the pairwise-interaction term with respect to a single latent component v_{i, f} is:

∂ŷ / ∂v_{i,f}  =  x_i · ( Σ_{j=1}^{d} v_{j,f} · x_j  −  v_{i,f} · x_i )

which is also computable in O(d_active · k) time using the cached inner sums.

The reference implementation libFM supports SGD, Markov Chain Monte Carlo (MCMC), and Alternating Least Squares (ALS) optimizers. SGD is the most common in practice.

5. Higher-Order Factorization Machines

Rendle’s original paper also defined higher-order FMs that include three-way and higher feature interactions:

ŷ(x) = ... + Σ_{i<j<k} ⟨v_i, v_j, v_k⟩ · x_i · x_j · x_k

with appropriate factorized parameterizations. In practice, third-order interactions rarely help on real datasets, and the second-order FM is the version overwhelmingly used in production. The xDeepFM paper later proposed a different way to capture higher-order interactions via the Compressed Interaction Network (CIN) that has better empirical properties than higher-order FM.

6. When to Use FM

FM is appropriate when:

  • You have categorical features beyond user and item IDs (genre, day-of-week, device, location).
  • Pairwise feature interactions matter for the task.
  • The features are sparse (one-hot encodings); the trick in §3 is what makes FM efficient.
  • CTR prediction or similar context-aware ranking is the task.

Do not use FM when:

  • You have only user and item IDs — plain MF or BPR is simpler and equivalent.
  • Higher-order interactions matter substantially — use xDeepFM or deep models.
  • Continuous features with non-trivial transformations are critical — deep models can learn arbitrary transformations.

7. Strengths

  • Generalizes MF to arbitrary features. No need for a separate model architecture per signal type.
  • O(d · k) per-prediction cost despite modeling all pairwise interactions.
  • Strong CTR baseline. Widely deployed in industrial ad-ranking systems before being supplanted by deep variants.
  • Works with explicit and implicit feedback depending on the loss function.
  • Mature implementations. libFM, DeepFM, and many derivatives.

8. Weaknesses

  • Limited to pairwise interactions. Higher-order interactions need xDeepFM or deep models.
  • Linear in feature contributions per latent dimension. Cannot model conditional non-linearities; deep variants (DeepFM, xDeepFM) extend this.
  • Cold start partial. Cold features (a brand-new user ID) have no learned latent vector; cold side features (a new category) are handled if the new combination shares features with existing instances.

9. Pitfalls and Misconceptions

Treating FM as a purely user-item model. It is much more general — every feature gets a latent vector. The MF interpretation is just the special case with only user and item features.

Forgetting the efficient computation trick. Naive O(d²) evaluation makes FM unusable; the O(d · k) reformulation is essential.

Setting k too high. Like other factorization models, larger k overfits without enough data. Typical k = 8 to 64 for production CTR.

Using FM where deep models would be better. For tasks dominated by complex non-linear feature interactions, FM’s pairwise-only modeling is limiting. DeepFM adds a deep network branch; xDeepFM adds the CIN. Use them if pure FM underperforms.

10. See Also

Graph View

Backlinks