A Gentle Introduction to Model-Based Collaborative Filtering and Funk SVD
In collaborative filtering algorithms, the core concept is to leverage past user-item interactions to recommend new items to a user. Given a user-item rating matrix $R$, our goal is to estimate the missing entries of this matrix and use these predictions to generate recommendations.
Collaborative filtering algorithms generally fall into two main categories: model-based and memory-based.
Memory-based algorithms are the simpler of the two, where missing entries are estimated based on the ratings of neighbors (similar users or items). I have written an in-depth article on memory-based collaborative filtering, which you can find here.
In contrast, model-based collaborative filtering involves learning user and item embeddings directly from the rating matrix. These embeddings are then used to approximate the missing entries.
Matrix factorization is a classic and widely adopted family of model-based algorithms. In this article, we will explore Funk SVD — a simple yet effective matrix factorization method.
Introduction to Funk SVD
The core idea behind Funk SVD, and matrix factorization methods in general, is to approximate the rating matrix $R$ as the product of two low-rank matrices, $P$ and $Q$:
$$\hat{R} = PQ^T$$
Suppose there are $m$ users and $n$ items, then $R \in \mathrm{R}^{m \times n}$. We define $P \in \mathrm{R}^{m \times f}$ and $Q \in \mathrm{R}^{n \times f}$. Usually, the dimension $f$ is significantly smaller than both $m$ and $n$, making $P$ and $Q$ low-rank matrices.
In this context, $P$ represents user embeddings and $Q$ represents item embeddings. Since both embedding types are $f$-dimensional vectors, we are effectively projecting both users and items into a shared $f$-dimensional latent space. Consequently, these models are often referred to as latent factor models.
Once the matrices $P$ and $Q$ are learned, the estimated rating $\hat{r}_{ui}$ for user $u$ and item $i$ is computed as the dot product of their respective embeddings:
$$\hat{r}_{ui} = p_{u}^T q_{i},$$where $p_{u}$ represents the $u$-th row of $P$ (user $u$'s embedding), and $q_{i}$ represents the $i$-th row of $Q$ (item $i$'s embedding).
Funk SVD Objective
The objective for Funk SVD is given by:
$$\underset{P, Q}{\text{minimize}} \sum_{(u, i) \in R_{\text{obs}}} (r_{ui} - p_{u}^T q_{i})^2 + \lambda \left( \sum_u \| p_u \|^2 + \sum_i \| q_i \|^2 \right) ,$$where $\lambda > 0$ is the regularization parameter.
The intuition behind this objective is straightforward: because the matrix $R$ is typically large and sparse, we iterate only over the observed (non-missing) entries. We seek to find matrices $P$ and $Q$ that best approximate these known ratings. The usual regularization term is included to prevent overfitting
Solving the Objective using Alternating Least Squares
The Alternating Least Squares Method is a popular iterative optimization technique used in many matrix factorization methods
The process involves alternating between two steps: first, we fix the matrix $P$ and solve for $Q$; next, we fix $Q$ and solve for $P$. We repeat this process until convergence.
Notice that our objective function:
$$L = \sum_{(u, i) \in R_{\text{obs}}} (r_{ui} - p_{u}^T q_{i})^2 + \lambda \left( \sum_u \| p_u \|^2 + \sum_i \| q_i \|^2 \right)$$is convex and symmetric with respect to $P$ and $Q$. This indicates the mathematical derivation for both steps will be identical. Alright, let's go through the first step
Step 1: Fix $Q$ and Solve for $P$
We solve for $P$ by solving for each $p_u$ separately and then putting them together. Since the objective function is convex, we can find the optimal $p_u$ by taking the derivative of $L$ with respect to $p_u$ and setting it to zero.
The derivative of the first term is computed as follows:
$$\begin{align*} \frac{\partial}{\partial p_u} \left( \sum_{(u, i) \in R_{\text{obs}}} (r_{ui} - p_{u}^T q_{i})^2 \right) &= 2 \sum_{i: r_{ui} \neq 0} (r_{ui} - p_{u}^T q_{i}) (-q_i) \\[4pt] &= -2 \sum_{i: r_{ui} \neq 0} (r_{ui} - p_{u}^T q_{i}) q_i \\[4pt] &= -2 \sum_{i: r_{ui} \neq 0} \big( r_{ui}q_i - ( p_{u}^T q_{i} ) q_i \big) \end{align*}$$Note that the term $p_{u}^T q_{i}$ is a scalar, so it is equivalent to $q_i^T p_u$. Also, since it's a scalar, it can be commuted with $q_i$. Thus, we can rearrange the terms as follows:
$$\begin{align*} \sum_{i: r_{ui} \neq 0} \big( r_{ui} q_i - (p_{u}^T q_{i}) q_i \big) &= \sum_{i: r_{ui} \neq 0} \big( r_{ui} q_i - (q_{i}^T p_u) q_i \big) \\[4pt] &= \sum_{i: r_{ui} \neq 0} \big( r_{ui} q_i - q_i(q_{i}^T p_u) \big) \\[4pt] &= \sum_{i: r_{ui} \neq 0} \big( r_{ui} q_i - (q_iq_{i}^T) p_u \big) \\[4pt] &= \sum_{i: r_{ui} \neq 0} r_{ui} q_i - \left( \sum_{i: r_{ui} \neq 0} q_iq_{i}^T \right) p_u \end{align*}$$Next, the derivative of the regularization term can be easily computed as follows:
$$\begin{align*} \frac{\partial}{\partial p_u} \left( \lambda \sum_u \| p_u \|^2 + \lambda \sum_i \| q_i \|^2 \right) &= \frac{\partial}{\partial p_u} \lambda \| p_u \|^2 \\[4pt] &= 2 \lambda p_u \end{align*}$$Combining these results, the gradient of the objective $L$ with respect to $p_u$ is given by:
$$\frac{\partial L}{\partial p_u} = -2 \left( \sum_{i: r_{ui} \neq 0} r_{ui} q_i - \left(\sum_{i: r_{ui} \neq 0} q_iq_{i}^T\right) p_u \right) + 2\lambda p_u$$We can solve for $p_u$ by setting this gradient to zero:
$$\begin{align*} 0 &= \frac{\partial L}{\partial p_u} \\[4pt] &= -2 \left( \sum_{i: r_{ui} \neq 0} r_{ui} q_i - \left(\sum_{i: r_{ui} \neq 0} q_iq_{i}^T\right) p_u \right) + 2\lambda p_u \\[4pt] &= -\sum_{i: r_{ui} \neq 0} r_{ui} q_i + \left(\sum_{i: r_{ui} \neq 0} q_iq_{i}^T\right) p_u + \lambda p_u \\[4pt] &= -\sum_{i: r_{ui} \neq 0} r_{ui} q_i + \left(\sum_{i: r_{ui} \neq 0} q_iq_{i}^T + \lambda I\right) p_u \end{align*}$$Thus, we get:
$$\left( \sum_{i: r_{ui} \neq 0} q_iq_{i}^T + \lambda I \right) p_u = \sum_{i: r_{ui} \neq 0} r_{ui} q_i$$Next, we show the matrix acting on $p_u$ is invertible. Let $Q^\prime$ be the matrix whose columns are the item vectors $q_i$ for which $r_{ui}$ is observed:
$$Q^\prime = \begin{bmatrix} \mid & & \mid \\ q_{i_1} & \cdots & q_{i_k} \\ \mid & & \mid \end{bmatrix}$$We can express the term in parentheses as:
$$\begin{align*} \sum_{i: r_{ui} \neq 0} (q_iq_{i}^T) + \lambda I &= Q^\prime (Q^\prime)^T + \lambda I \\ &= \begin{bmatrix} Q^\prime & \sqrt{\lambda} I \end{bmatrix} \begin{bmatrix} \left( Q^\prime \right)^T \\ \sqrt{\lambda} I \end{bmatrix} \\ &= \begin{bmatrix} \left( \left( Q^\prime \right)^T \right)^T & \left( \sqrt{\lambda} I \right)^T \end{bmatrix} \begin{bmatrix} \left( Q^\prime \right)^T \\ \sqrt{\lambda} I \end{bmatrix} \\ &= \left( \begin{bmatrix} \left( Q^\prime \right)^T \\ \sqrt{\lambda} I \end{bmatrix} \right)^T \times \begin{bmatrix} \left( Q^\prime \right)^T \\ \sqrt{\lambda} I \end{bmatrix} \end{align*}$$The matrix $$\begin{bmatrix} (Q^\prime)^T \\ \sqrt{\lambda} I \end{bmatrix}$$ has linearly independent columns because it is stacked with the identity matrix $\sqrt{\lambda} I$. This implies the product:
$$\sum_{i: r_{ui} \neq 0} (q_iq_{i}^T) + \lambda I = \left( \begin{bmatrix} \left( Q^\prime \right)^T \\ \sqrt{\lambda} I \end{bmatrix} \right)^T \times \begin{bmatrix} \left( Q^\prime \right)^T \\ \sqrt{\lambda} I \end{bmatrix}$$is invertible. Thus, the optimal $p_u$ is given by:
$$p_u = \left( \sum_{i: r_{ui} \neq 0} (q_iq_{i}^T) + \lambda I \right)^{-1} \sum_{i: r_{ui} \neq 0} r_{ui} q_i$$We compute this for all $u = 1, \ldots, m$ to form the matrix $P$.
Step 2: Fix $P$ and Solve for $Q$
Once $P$ is updated, we fix it and solve for $Q$. Due to the symmetry of the objective function, the derivation is identical to Step 1. The optimal item vector $q_i$ is given by:
$$q_i = \left( \sum_{u: r_{ui} \neq 0} (p_up_{u}^T) + \lambda I \right)^{-1} \sum_{u: r_{ui} \neq 0} r_{ui} p_u$$We solve for each $q_i$ to form the matrix $Q$, and alternate between these two steps until convergence.
Funk SVD Algorithm
The algorithm can be summarized as follows. First, we initialize the matrices $P$ and $Q$. Then, we repeat the following two update steps until convergence:
Step 1: For each user $u = 1, \ldots, m$, compute:
$$p_u = \left( \sum_{i: r_{ui} \neq 0} (q_iq_{i}^T) + \lambda I \right)^{-1} \sum_{i: r_{ui} \neq 0} r_{ui} q_i$$Step 2: For each item $i = 1, \ldots, n$, compute:
$$q_i = \left( \sum_{u: r_{ui} \neq 0} (p_up_{u}^T) + \lambda I \right)^{-1} \sum_{u: r_{ui} \neq 0} r_{ui} p_u$$Pitfalls of Funk SVD
Popularity Bias
The Funk SVD objective function relies solely on the non-missing entries of the user-item rating matrix. Since popular items are rated more frequently than unpopular ones, they constitute the majority of the terms in the objective function. Consequently, the algorithm prioritizes minimizing the error for these popular items to reduce the overall loss. As a result, the learned embeddings for popular items often acquire larger Euclidean norms, leading them to be recommended more often compared to niche items.
Exclusion of Metadata
Funk SVD relies exclusively on user-item interaction data. It ignores other potentially valuable signals. For example, it doesn't take into account the time of the iteraction: an interaction from a decade ago is treated with the same weight as a recent one. Furthermore, it ignores valuable user and item metadata. These limitations make the algorithm less ideal for complex real-world production systems. It is primarily used as a baseline for benchmarking.
Conclusion
I hope you enjoyed this article. We have discussed the general idea behind model-based collaborative filtering and examined the Funk SVD method in detail. We walked through the process step-by-step, starting from the intuition behind the objective to solving it mathematically. Finally, we discussed the algorithm's pitfalls, outlining when it is appropriate to use and when to avoid it.