Recommender Systems and Matrix Factorization

Definition A recommender system takes a user $u$ and a decision time $\tau$ and returns a ranked list of items, in three stages. Candidate generation selects the candidate set $\mathcal{C}_u \subseteq \mathcal{I}$, the items of the catalog $\mathcal{I}$ that may be recommended to this user at that time, for example the available items the user has not already completed. Scoring assigns each candidate $i$ a number $s(u, i)$ computed only from information recorded before $\tau$. Ordering lists the candidates by decreasing score, breaks ties by a stated rule and returns the first $k$, which needs $\lvert \mathcal{C}_u \rvert \ge k$ or a stated rule for shorter lists. The simplest scoring rule is the popularity baseline, which scores each item by the number of interactions it received in a training period that ends before $\tau$, so it gives every user the same order.

Definition Explicit feedback is a value a user supplies on purpose to state a preference, such as a rating $r_{ui}$ from 1 to 5 by user $u$ for item $i$. Implicit feedback is behavior recorded during use, such as a click, a completion or a purchase, from which a preference is inferred. In both cases only some user-item pairs are observed. Write $\Omega$ for the set of pairs $(u, i)$ with an observed rating or interaction. A pair outside $\Omega$ carries no value. It is not a rating of zero and not a recorded dislike. Whether a pair enters $\Omega$ depends on the user’s interest and also on exposure, meaning whether, where and how often the item was shown to the user, and exposure depends on the recommendation policy that was running when the data were collected. The resulting distortion of the observed data is called exposure bias.

Definition Content-based recommendation scores an item for a user by comparing the item’s attributes, such as topic, language, level and format, with a profile of the user’s interests, built from stated preferences or from the attributes of items the user responded to well. Collaborative filtering scores an item for a user from the observed interactions of many users with many items, without using item descriptions. Neighborhood methods predict from the responses of similar users to the same item, or of the same user to similar items, with similarity computed from co-observed interactions. Latent factor models such as matrix factorization learn a vector for each user and each item from the observed interactions. Hybrid systems combine both kinds of information.

Definition Suppose $m$ users and $n$ items have observed ratings $r_{ui}$ for the pairs in $\Omega$. Matrix factorization with latent dimension $d$ gives each user a vector $\mathbf{p}_u \in \mathbb{R}^d$ and each item a vector $\mathbf{q}_i \in \mathbb{R}^d$, and it predicts

where $\mu$ is a global intercept. User and item bias terms $b_u$ and $b_i$ are often added. Stacking the user vectors as the rows of an $m \times d$ matrix $P$ and the item vectors as the rows of an $n \times d$ matrix $Q$, the $m \times n$ matrix of all scores is $PQ^{\top}$ with $\mu$ added to every entry. The parameters are fitted to the observed ratings only, for example by minimizing

with a penalty weight $\lambda \ge 0$ chosen on validation data and the intercept left unpenalized. This objective is not jointly convex in $P$ and $Q$, so gradient methods and alternating least squares can end at different solutions from different starting values. The latent axes are not unique either. For any orthogonal $d \times d$ matrix $A$, replacing $P$ by $PA$ and $Q$ by $QA$ leaves every score and the penalty unchanged.

Definition Cold start is the situation of a user or an item with too little interaction history for the personalized estimate a model is meant to provide. A new user has no observed ratings or clicks, and a new item has not yet been shown or used. In the factorization objective above with $\lambda > 0$, the vector of an item with no observed ratings appears only in its penalty term, so its minimizing value is $\mathbf{q}_i = \mathbf{0}$, and the item’s score is $\mu$ for every user. In the same way a user without observed ratings gets $\mathbf{p}_u = \mathbf{0}$, and every item then scores $\mu$ for that user, a complete tie. If penalized bias terms $b_u$ and $b_i$ are added, the new item’s score becomes $\mu + b_u$, which contains nothing specific to the item, and the new user’s scores become $\mu + b_i$, the same order for every new user. With $\lambda = 0$ such a vector does not affect the objective at all and is not determined by the data.

Definition Fix a user $u$, a candidate set $\mathcal{C}_u$ with at least $k$ items, a relevance label $\mathrm{rel}(i) \ge 0$ for every candidate, and a ranked list whose item at position $r$ is $i_r$. With binary labels, 1 for relevant and 0 for not relevant, let $R_u \ge 1$ be the number of relevant candidates. The precision at $k$ and the recall at $k$ are

The discounted cumulative gain at $k$ is

and the normalized discounted cumulative gain, NDCG, is $\text{NDCG@}k = \text{DCG@}k / \text{IDCG@}k$. The ideal value $\text{IDCG@}k$ is the DCG at $k$ of the candidates sorted by decreasing relevance, the largest value any ordering of $\mathcal{C}_u$ can reach, so NDCG lies between 0 and 1. If every candidate has relevance 0, then $\text{IDCG@}k = 0$ and NDCG is undefined, as is recall, so a report states how such users are handled and how many there are. Ties in the scores are broken by a stated rule, and an average over users states whether every user counts equally. Some definitions use the gain $\mathrm{rel}(i_r)$ in place of $2^{\mathrm{rel}(i_r)} - 1$, and the two agree for binary labels.