Introduction to Collaborative Filtering

In the era of digital content, recommender systems are the engines that drive user engagement. Whether it is Netflix suggesting your next binge-watch or Amazon highlighting products, these systems rely heavily on machine learning techniques to predict user preferences. For undergraduate students, understanding collaborative filtering is essential, as it forms the foundation of most commercial recommendation engines.

Collaborative filtering (CF) is a technique that makes automatic predictions about the interests of a user by collecting preferences from many users. The core assumption is that if person A has the same opinion as person B on one issue, they are more likely to have similar opinions on other issues. This article will guide you through the mathematical structures behind these systems, specifically focusing on the user-item matrix and the power of matrix factorisation.

The User-Item Matrix

The starting point for any collaborative filtering system is the user-item matrix, denoted as $R$. If we have $N$ users and $M$ items, $R$ is an $N \times M$ matrix where each entry $r_{ij}$ represents the rating given by user $i$ to item $j$. In practice, this matrix is extremely sparse because most users only interact with a tiny fraction of the total available items.

Consider a simple example with 3 users and 4 items:

| | Item 1 | Item 2 | Item 3 | Item 4 | |---|---|---|---|---| | User 1 | 5 | ? | 2 | 1 | | User 2 | ? | 4 | 5 | ? | | User 3 | 1 | ? | 3 | 5 |

The question marks represent missing data. Our goal is to predict these values to provide personalised recommendations.

Latent Factor Models

To fill the gaps in the matrix, we use latent factor models. We assume that both users and items can be represented in a shared, lower-dimensional space of size $k$. Each user $i$ is associated with a vector $u_i \in \mathbb{R}^k$, and each item $j$ is associated with a vector $v_j \in \mathbb{R}^k$. The predicted rating $\hat{r}_{ij}$ is the dot product of these two vectors:

$$\hat{r}_{ij} = u_i^T v_j$$

This approach assumes that there are underlying, unobserved factors (e.g., genre, tone, or complexity) that influence ratings. By mapping users and items into this latent space, we can estimate the missing values in the matrix.

Matrix Factorisation Explained

Matrix factorisation is the process of decomposing the large, sparse matrix $R$ into two smaller matrices, $U$ (user features) and $V$ (item features), such that $R \approx U^T V$. We learn these matrices by minimising the squared error between the known ratings and our predictions, often adding regularisation to prevent overfitting.

The objective function to minimise is:

$$\min_{U, V} \sum_{(i,j) \in S} (r_{ij} - u_i^T v_j)^2 + \lambda (|u_i|^2 + |v_j|^2)$$

Where $S$ is the set of known ratings and $\lambda$ is the regularisation parameter.

Worked Example: Simple Factorisation

Let us assume a 2D latent space ($k=2$). Suppose we have already learned the following vectors for User 1 and Item 2: $u_1 = [0.8, 0.2]^T$ $v_2 = [0.5, 0.9]^T$

To predict the rating for User 1 on Item 2: $\hat{r}{12} = u_1^T v_2 = (0.8 \times 0.5) + (0.2 \times 0.9)$ $\hat{r}{12} = 0.4 + 0.18 = 0.58$

If our scale is 1 to 5, this suggests a low interest, allowing the system to decide whether to recommend this item.

Worked Example: Gradient Descent Step

If we have a rating $r_{ij} = 5$ and our current prediction $\hat{r}{ij} = 3$, the error is $e{ij} = 5 - 3 = 2$. Using a learning rate $\eta = 0.1$, we update the vectors: $u_i \leftarrow u_i + \eta(e_{ij}v_j)$ $v_j \leftarrow v_j + \eta(e_{ij}u_i)$

If $v_j = [0.5, 0.9]$, the new $u_i$ becomes: $u_i = [0.8, 0.2] + 0.1(2 \times [0.5, 0.9]) = [0.8, 0.2] + [0.1, 0.18] = [0.9, 0.38]$

Common Mistakes

1. Ignoring Sparsity: Assuming the matrix is dense leads to massive computational overhead. Always use sparse matrix representations.
2. Overfitting: Failing to use regularisation ($\lambda$) causes the model to memorise the training data rather than generalising to new user-item pairs.
3. Cold Start Problem: Assuming collaborative filtering works for new users or items with no interaction history. It does not; you need content-based features for that.

FAQ

What is the difference between user-based and item-based CF? User-based CF finds similar users to recommend items, while item-based CF finds items similar to those a user has already liked.

Why use matrix factorisation over simple similarity? Matrix factorisation captures latent relationships that simple similarity metrics (like cosine similarity) miss, and it handles sparse data more robustly.

What is the 'cold start' problem? It occurs when a new user or item enters the system with no interaction history, making it impossible for pure collaborative filtering to make a prediction.

Conclusion

Collaborative filtering and matrix factorisation are powerful tools in the machine learning toolkit. By transforming sparse interaction data into meaningful latent vectors, we can predict user behaviour with high accuracy. To see these concepts in action with interactive visualisations, head over to MathInstructor AI and generate a free animated lesson on this topic.