A Gentle Introduction to EASE: Embarrassingly Shallow Autoencoders for Sparse Data
An Introduction to Collaborative Filtering
The central idea behind collaborative filtering is to recommend items to users based solely on their past interactions. We have a set of users and a set of items, where each user can rate many items and each item can be rated by many users. Collaborative filtering uses this interaction data to predict and recommend new items.
Notably, this approach does not use item metadata (like descriptions, weight, or cost) or user metadata (like age or region). It relies purely on the user-item interaction history.
Collaborative filtering algorithms typically start with a rating matrix $R$, where rows represent users and columns represent items. The entry $r_{ui}$ in this matrix represents the rating given by user $u$ to item $i$. This rating matrix is central to all collaborative filtering methods.
Suppose we want to recommend items to a user $u$. Our strategy will be to estimate the ratings user $u$ might give to the items they haven't seen yet. We can then recommend the items with the highest estimated ratings. In this article, we will discuss methods for estimating these ratings.
There are two main types of collaborative filtering algorithms: model-based and memory-based. Memory-based collaborative filtering is a simpler, more direct approach and will be the focus of this article.
An Introduction to Memory-Based Collaborative Filtering
Memory-based collaborative filtering is further divided into two categories: user-based collaborative filtering and item-based collaborative filtering.
Let's say we want to estimate the value of $r_{ui}$ (the rating user $u$ might give to item $i$). In user-based collaborative filtering, the idea is to find users who are similar to user $u$. We then aggregate the ratings these similar users have given to item $i$, weighted by their similarity score. Mathematically, this is represented as:
$$\hat{r}_{ui} = \sum_{u^\prime \in U_i} \operatorname{sim}(u, u^\prime) \cdot r_{u^\prime i},$$where $U_i$ is the set of users who have rated item $i$, and $\operatorname{sim}(u, u^\prime)$ is a similarity function (ideally giving a value between 0 and 1) that measures how similar users $u$ and $u^\prime$ are.
In item-based collaborative filtering, we find items similar to item $i$. We then aggregate the ratings given by the same user $u$ to these similar items, weighted by their similarity score. Mathematically, this is given by:
$$\hat{r}_{ui} = \sum_{i^\prime \in I_u} \operatorname{sim}(i, i^\prime) \cdot r_{u i^\prime}$$Here, $I_u$ represents the set of items already rated by user $u$.
In practice, item-based collaborative filtering is often preferred over user-based. This is because user interests can change frequently, whereas the nature of an item remains relatively stable. Therefore, we will focus on item-based collaborative filtering for the rest of this article.
Matrix Formulation
Let $I$ represent the set of all items. Suppose we have an item-item similarity matrix $W$, where $W \in \mathrm{R}^{|I| \times |I|}$. The $(i,j)$-th entry of $W$ represents the similarity $\operatorname{sim}(i, j)$.
Now, consider the matrix product $RW$. What does the $(u, i)$-th entry of this product represent? The $u$-th row of $R$ is the rating vector for user $u$, and the $i$-th column of $W$ represents the similarity of item $i$ to all other items.
When we take the dot product of the $u$-th row of $R$ and the $i$-th column of $W$, we are computing:
$$\sum_{i^\prime \in I} \operatorname{sim}(i, i^\prime) \cdot r_{u i^\prime}$$This is exactly the formula for $\hat{r}_{ui}$ we've seen earlier. Note that before computing the product $RW$, we impute missing values of $R$ with zero.
Thus, the entire problem of item-based collaborative filtering boils down to finding a good item-item similarity matrix $W$. Once we have $W$, we can use the product $RW$ for recommendations
The goal of this article is to introduce EASE, a method for learning this matrix $W$
Introduction to EASE
The EASE Objective
In EASE, the goal is to learn a weight matrix $W$ by minimizing the following objective:
$$\begin{aligned} \min_{W} \quad & \|R - RW \|_F^2 + \lambda \| W \|_F^2 \\ \text{subject to} \quad & \operatorname{diag}(W) = 0 \end{aligned}$$where $\lambda > 0$ is the regularization parameter.
Let's break down the components of this objective. The first term, $\|R - RW \|_F^2$, is the reconstruction loss; it ensures that the estimated ratings are as close as possible to the actual ratings. The second term, $\lambda \| W \|_F^2$, is the regularization term. It forces the entries of $W$ to be small.
The constraint $\operatorname{diag}(W) = 0$ is particularly critical. Without this constraint, the optimization would result in a trivial solution where $W$ is the identity matrix $I$. Since $R \cdot I = R$, the identity matrix would yield perfect reconstruction error. This isn't what we want, and hence the constraint.
This objective has a closed-form solution. In the next section, we will derive this solution step by step.
Solving EASE
We can decompose the original objective by observing that the squared Frobenius norm of a matrix is equal to the sum of the squared Euclidean norms of its individual columns. This allows us to break the problem into independent optimization problems for each column $w_i$ of the weight matrix $W$:
$$\begin{aligned} \min_{w_i} \quad & \|Rw_i - r_i\|^2 + \lambda \| w_i \|^2 \\ \text{subject to} \quad & W_{ii} = 0 \end{aligned}$$
for each $i = 1,\ldots, |I|$. Here, $w_i$ represents the $i$-th column of $W$, and $r_i$ represents the $i$-th column of $R$. We can rewrite this in a compact matrix form by stacking the regularization term into the least squares objective:
$$\begin{aligned} \min_{w_i} \quad & \left\| \begin{bmatrix} R \\ \sqrt{\lambda} I \end{bmatrix}w_i - \begin{bmatrix} r_i \\ 0 \end{bmatrix} \right\|^2 \\[4pt] \text{subject to} \quad & I_iw_i = 0 \end{aligned}$$
where $I_i$ is the $|I| \times |I|$ matrix with zeros everywhere except for a $1$ at the $(i, i)$-th entry.
This objective now takes the standard form of a constrained least squares problem:
$$\begin{aligned} \min_{x} \quad & \|Ax - b\|^2 \\ \text{subject to} \quad & Cx = d \end{aligned}$$
The solution to such a problem is obtained by solving the KKT conditions:
$$\begin{bmatrix} 2A^T A & C^T \\ C & 0 \end{bmatrix} \begin{bmatrix} \hat{x} \\ \hat{z} \end{bmatrix} = \begin{bmatrix} 2A^T b \\ d \end{bmatrix}$$
Here, $\hat{z}$ represents the Lagrange multiplier.
Note: If you're interested in the derivation of the KKT conditions, I encourage you to read Stephen Boyd's VMLS. In fact, I encourage you to read the whole book.
In our specific context, we define $A$ as:
$$A = \begin{bmatrix} R \\ \sqrt{ \lambda } I \end{bmatrix}$$
We can compute $A^TA$ as follows:
$$\begin{align*} A^TA &= \left( \begin{bmatrix} R \\ \sqrt{ \lambda } I \end{bmatrix} \right)^T \begin{bmatrix} R \\ \sqrt{ \lambda } I \end{bmatrix} \\[4pt] &= \begin{bmatrix} R^T & \sqrt{ \lambda } I \end{bmatrix} \begin{bmatrix} R \\ \sqrt{ \lambda } I \end{bmatrix} \\[4pt] &= R^TR + \lambda I \end{align*}$$
It is important to note that this matrix is invertible. The matrix $A$ has linearly independent columns because the identity matrix $I$ (stacked at the bottom) has linearly independent columns. Since $A$ and $A^TA$ share the same null space, the linear independence of $A$'s columns guarantees that $A^TA$ is invertible.
Furthermore, we have $C = C^T = I_i$, $d=0$, and:
$$b = \begin{bmatrix} r_i \\ 0 \end{bmatrix}$$
We can compute $A^Tb$ as:
$$\begin{align*} A^Tb &= \begin{bmatrix} R^T & \sqrt{ \lambda } I \end{bmatrix} \begin{bmatrix} r_i \\ 0 \end{bmatrix} \\[2pt] &= R^Tr_i \end{align*}$$
Substituting these back into the KKT conditions for a specific $i$, we get:
$$\begin{bmatrix} 2(R^T R + \lambda I) & I_i \\ I_i & 0 \end{bmatrix} \begin{bmatrix} \hat{w_i} \\ \hat{z} \end{bmatrix} = \begin{bmatrix} 2R^T r_i \\ 0 \end{bmatrix}$$
The first line of this system yields the equation:
$$2(R^TR + \lambda I)w_i + I_i \hat{z} = 2R^Tr_i$$
Since this equation holds the same form for every column $i$, we can generalize it to the full matrix form. The term $I_i \hat{z}$ isolates the $i$-th entry of $\hat{z}$, so when combining all columns, these terms form a diagonal matrix. Dropping the constant $2$, we arrive at:
$$(R^TR + \lambda I)W + \operatorname{diag}(z_1, \ldots, z_{|I|}) = R^TR$$
Here, $\operatorname{diag}(z_1, \ldots, z_{|I|})$ is a diagonal matrix containing the Lagrange
multipliers. We can now solve for $\hat{W}$:
$$\hat{W} = (R^TR + \lambda I)^{-1} \left( R^TR - \operatorname{diag}(z_1, \ldots, z_{|I|}) \right)$$
To simplify the solution, let us define the matrix $\hat{P}$ as:
$$\hat{P} = (R^TR + \lambda I)^{-1}$$
The equation can be expressed in terms of $\hat{P}$ as:
$$\begin{align*} \hat{W} &= \hat{P} \left( R^TR - \operatorname{diag}(z_1, \ldots, z_{|I|}) \right) \\[4pt] &= \hat{P} \left( (\hat{P}^{-1} - \lambda I) - \operatorname{diag}(z_1, \ldots, z_{|I|}) \right) \\[4pt] &= \hat{P}\hat{P}^{-1} - \hat{P}(\lambda I + \operatorname{diag}(z_1, \ldots, z_{|I|})) \\[4pt] &= I - \hat{P} \cdot \operatorname{diag}(\lambda + z_1, \ldots, \lambda + z_{|I|}) \end{align*}$$
We now apply our original constraint: $\operatorname{diag}(\hat{W}) = 0$. For the diagonal entries of $\hat{W}$ to be zero, the diagonal entries of $\hat{P} \cdot \operatorname{diag}(\lambda + z_1, \ldots, \lambda + z_{|I|})$ must equal 1. Mathematically, this implies:
$$\hat{P}_{ii} \cdot (\lambda + z_i) = 1 \implies (\lambda + z_i) = \frac{1}{\hat{P}_{ii}}$$
Substituting this back into the equation for $\hat{W}$, we get the final closed-form solution:
$$\hat{W} = I - \hat{P} \cdot \operatorname{diag}\left( \frac{1}{\hat{P}_{11}}, \ldots, \frac{1}{\hat{P}_{|I||I|}} \right)$$
This allows us to define every entry of the weight matrix $W$:
$$\hat{W}_{ij} = \begin{cases} 0, &\quad \text{if $i=j$} \\[6pt] -\frac{\hat{P}_{ij}}{\hat{P}_{jj}}, &\quad \text{if $i \neq j$} \end{cases}$$
Conclusion
I hope you enjoyed this article. The original EASE paper does not fully establish the context nor does it detail the mathematical derivations. In this article, however, we have discussed the foundational concepts and derived the solution from first principles.