\chapter{Recommender Systems}
\label{chapter:rs}

\acrlong{rss} are a response to ever-expanding choice and to information overload. An \acrshort{rs} uses data and algorithms to predict which candidate items may appeal to its users, often making these predictions in a personalised or contextualised way \cite{ricci2011introduction}. Ideally, it exposes its users to items (such as products, services, news articles or even people) that the users may not have discovered for themselves, and it helps users to manage the choice of which items to consume. \acrshort{rss} can be found in many different application domains, often employed at scale: for example, we find them in music and movie streaming services, in online shopping sites, in social media platforms, and in news story aggregators.

In this chapter, we will discuss the data and algorithms that \acrshort{rss} use, and also the topic of \acrshort{rs} evaluation. The field is huge and a comprehensive survey impossible. Our decisions over selection of material are guided by topics that underpin later chapters of this dissertation. 

We exclude from this chapter papers that propose specific methods for estimating the prediction and label uncertainty of recommendations, and the evaluation of these uncertainty estimates. These papers are covered in detail in subsequent chapters, where we bring our own contributions by: expressing these methods in a unified notation; critiquing them; proposing new methods; and including them in comprehensive empirical comparisons.

\section{Data in \acrlong{rss}}
\label{sec:data}

%All three stages of the recommendation workflow are guided by data. 
In practice, an \acrshort{rs} relies on diverse types of data to offer personalized suggestions. The types of data available guide the choice of recommendation algorithms. We split data into two: user-item interaction data, and non-interaction data. This somewhat high-level division reflects the fact that the emphasis in this dissertation is on interaction data. Accordingly, we review non-interaction, which we make no use of in the rest of this dissertation, in a more cursory way. We further subdivide the user-item interaction data into two, as per the previous chapter: explicit feedback and implicit feedback.

\subsection{User-item interaction data}

User-item interaction data is a record of a user's response to an item, e.g.\ one that she was exposed to or one that she consumed. Usually, it takes the form of explicit or implicit user feedback (see below). However, there could be other types of user-item interaction data; for example, a timestamp or contextual data such as the weather or location of the user at the point when the interaction was observed.

User-item interactions are the building blocks of \acrfull{cf}. \acrshort{cf} is one of the most notable classes of recommendation algorithms. In short, these algorithms recommend based on the preferences and behaviours of other similar users. They rely on finding patterns in user-item interactions to make personalized recommendations. In Section \ref{sec:scoring}, we will explore \acrshort{cf} in more detail.

\subsubsection{Explicit user feedback}

Often, after a user has consumed an item, an \acrfull{ers} may explicitly invite the user to \emph{rate} the item. Traditionally, \textit{explicit feedback} is given in the form of a star rating, i.e.\ a value chosen from a discrete scale, e.g., $1\star$ to $5\star$. The higher the rating, the more the user liked the item. For our work on explicit feedback in this dissertation, we use star ratings, but we note that there are other possibilities: explicit feedback could be binary (e.g.\ thumbs-up or thumbs-down) or even unary (where only thumbs-up is allowed). 

The use of numeric ratings, and of explicit feedback in general, has several advantages. First and foremost, they quantify the user sentiment towards the item. For example, if a user rates movie A with $5\star$ and movie B with $4\star$, the system can easily understand that the user prefers A over B. Furthermore, ratings can designate negative sentiment (e.g.\ where $1\star$ means that the user did not like the item). Finally, the fact that they are explicit also makes them more transparent: the users can choose which items they want to rate. 

On the other hand, there are also several widely-recognized issues involving explicit ratings. First, users are not always consistent with the way they rate items. In \cite{Amatriain-Et-Al-2009}, it was noted that, when prompted to re-rate previously-rated items, users often provided a value that differed from their original rating. Secondly, the user's choice of \emph{what} to rate and \emph{how} highly to rate it might be biased by a variety of social factors  \cite{cosley2003seeing}. For instance, a user might provide higher ratings to critically-acclaimed items.

In addition, explicit feedback is not easy to gather. The users must be willing to re-engage with the system, subsequent to consumption, by actively providing ratings in the expectation of receiving better recommendations in the future. For this reason, \acrshort{erss} are often bottle-necked by rating non-availability. Some \acrshort{erss} seek to overcome this problem using \acrfull{al} \cite{carraro2020active}, in which the system queries users for their feedback on items they are known to have consumed or predicted to have consumed, where the users and items are selected in the expectation of having an impact on system performance.

\subsubsection{Implicit user feedback}

There are other forms of feedback that are not explicitly given by the user. Some examples are searches, clicks, views, purchases, favourites, etc. These are referred to as \emph{implicit feedback}. Usually, implicit feedback is unary: all the feedback received is perceived as positive and equal, and this is what we will assume in this dissertation. However, in some cases, there may be degrees of importance assigned to implicit signals \cite{lerche2014using}. For instance, in online shopping, a click action is less important than an add-to-cart action, which, in turn, is less important than a purchase action. 

The advantages of implicit feedback are plenty. For one, it is much easier to collect: it is recorded as a side-effect of normal user interaction, rather than through a separate dialog. In addition, implicit feedback does not suffer from the aforementioned inconsistencies involving interpretation of rating scales.

On the downside, since it is most often unary, implicit feedback does not allow for negative sentiment. Where a user has been exposed to an item but did not interact with it, there is no clarity on whether the user found the item to be unappealing or whether she did not interact with the item for some other reason \cite{hu2008collaborative}. Also, even when there is an interaction it may not signal positive feedback, e.g.\ a mistaken click.

Historically, the \acrshort{rs} literature focused on \acrshort{ers}. This may be because the field was strongly driven by the Netflix Prize contest \cite{bennett2007netflix} and the MovieLens system\footnote{\url{https://movielens.org/}}, both of which provided the research community with datasets of numeric ratings. Subsequently, the enormous availability of implicit feedback in deployed systems, combined with its aforementioned advantages, has led to a drift in the field towards \acrfull{irss}. Furthermore, it has been shown in several cases that recommendations from models trained on implicit feedback are more satisfactory to the user \cite{zhao2018explicit}.

\subsection{Non-user-item interaction data}

There are many other types of data. Since they are not the focus of this dissertation, we only summarize them below.

\begin{description}
    \item[User demographic data:] 
        User information, such as age, gender, location, and other relevant attributes, can offer valuable insights for personalizing recommendations. By incorporating this data into recommendation algorithms, systems aim to provide more tailored and relevant content to users. In many cases, the use of user demographic data, along with user-item interactions, has proven effective, leading to recommendations that are more personalized and more accurate \cite{koren2008factorization, ghazanfar2010scalable, guo2017deepfm}. In particular, demographic data can be very helpful for cold-start users, who are novel to the system \cite{safoury2013exploiting}.

    \item[Item data and meta-data:] 
        An \acrshort{rs} may also use data that describes the items in its catalog. In the case of digital media, such as music, images, movies or e-books, this data might be extracted or mined from the digital format itself. More often, it takes the form of meta-data: descriptive attributes or features associated with the items, including text descriptions, genres, categories, keywords, user-assigned tags\footnote{If the tags for an item are aggregated, then they are an example of item meta-data; but if we preserve user-item-tag relations, then arguably this is an example of implicit feedback data.}, attribute-value pairs and so on. 
        Item descriptions, often referred to as item content, allow for a special class of recommenders to be used, known as \acrfull{cb} recommenders \cite{lops2011content}. In overview, \acrshort{cb} \acrshort{rss} compare the descriptions of candidate items with the contents of user profiles, which record descriptions of the items that the user likes. \acrshort{cb} \acrshort{rss} can perform well when there is abundant item information available. An advantage is their ability to work well even for cold-start users and infrequent users, who have provided no, or little, feedback data \cite{lika2014facing}. However, these systems face challenges when it comes to item discovery in parts of the catalog that are fresh to the user because they tend to recommend items that are closely related to those previously consumed.

    \item[Knowledge graphs:] 
        Knowledge graphs offer a promising avenue for improving recommendation quality by incorporating structured information about users, items, and their relationships. By enriching the representation of users and items with complex domain-specific knowledge, such as attributes and contextual information, the \acrshort{rs} might deliver more context-aware and semantically meaningful recommendations. For an extensive review on the matter, we refer to \cite{guo2020survey}.

    \item[Social networks:]
        Social networks are a special case of knowledge graph that may be incorporated into a \acrshort{rs}. Users often trust the opinions of their contacts more and are more similar to them due to social influences. An example of the usefulness of social networks to recommendation is presented in \cite{ma2011improving}.

    \item[Context data:] 
        Context data is any additional data that influences a user's preferences in a specific situation \cite{adomavicius2010context, verbert2012context}. Examples include the device the user is using, the consumption time and location, whether the user consumed the item alone or with companions, and so on.\footnote{There is an argument that context data is another form of user-interaction data, since it is often related to the consumption of an item  by a user.} 
    By incorporating context data, an \acrshort{rs} can match recommendations to the user's current context to provide suggestions that are contextualised, as well as personalised. Systems that utilize context data are known as \acrfull{ca} \acrshort{rss}. 
\end{description}

\section{Recommendation Workflow}
\label{sec:workflow}
%Recommender systems are meant to help the users navigating through a vast catalog of items. 
The ultimate task of an \acrshort{rs} is to provide each user with a top-$n$ set of \emph{personalized} and, perhaps, \emph{contextualized} recommendations. Conceptually, we can view this as a three-step process: candidate selection, scoring, and top-$n$ recommendation. This is illustrated in Figure \ref{fig:rec_workflow}. Of course, this is not intended as an \acrshort{rs} architecture: real systems will be much more complex. Rather, it offers a way of structuring the presentation of the recommender workflow. 

\begin{figure}[t]
    \centering
    \begin{tikzpicture}[node distance=3cm, auto]
        % Nodes
        \node [block] (candidate) {Candidate selection};
        \node [block, below of=candidate] (scoring) {Scoring};
        \node [block, below of=scoring] (topn) {Top-$n$ recommendation};
        
        % Arrows
        \path [line] (candidate) -- (scoring);
        \path [line] (scoring) -- (topn);
    
    \end{tikzpicture}
    \caption{Recommendation workflow.}
    \label{fig:rec_workflow}
\end{figure}

\begin{description}
    \item[Candidate selection:] The first step in the workflow is to select which subset of items from the catalog are \emph{plausible} recommendations. Items may be implausible for many reasons. Take as example a restaurant recommender for use on-the-move. Naturally, only restaurants in the proximity of the user should be considered. Another example is news recommendation. In this case, most news stories that are more than, let's say, a week old are irrelevant, and therefore should be removed from the candidate pool. Candidate selection is also key in achieving good response times. When the item catalog is huge, scoring all the available items might be too time consuming. One solution is to filter a subset of candidate items. Such filtering must be performed carefully, to avoid discarding too many items that could be relevant to the user.

    \item[Scoring:] With a filtered set of candidate items at hand, the system must now rank these items according to some criteria. A scoring function is defined as $F: U \times I \rightarrow \mathbb{R}$. For each user and item, it can give a real-valued score, such that if $F(u, i) > F(u, j)$, user $u$ is predicted to prefer item $i$ over item $j$. Scoring is unarguably the most researched matter in the \acrshort{rs} field. When explicit ratings are available, scoring is done through \emph{rating prediction}. When they are not, we resort to \emph{relevance prediction}. In Section \ref{sec:scoring}, we extensively describe methods for scoring in both explicit and implicit feedback-based recommenders.

    \item[Top-$n$ recommendation:] The final step is to select an $n$-sized subset of candidate items to present to the user. Often this is done by simply sorting the candidate items in decreasing order of their scores, and then selecting the first $n$ from the sorted set. However, this is not the only way of choosing the $n$ items. In some cases, for example, the system may choose one or more items that score lower in the sort order. This may be done to satisfy so-called beyond-accuracy objectives, such as diversity and serendipity. In Section \ref{sec:top_n}, we explain several common beyond-accuracy objectives and how top-$n$ recommendation can be performed in a way that favours them.
\end{description}

We will not say any more about candidate selection since it is usually domain-specific, often quite simple relatively speaking, and of lower relevance to the remainder of this dissertation. The next two sections present scoring and top-$n$ recommendation in more detail.

\section{Scoring}
\label{sec:scoring}

Scoring plays a pivotal role in the \acrshort{rs} workflow, serving as the critical bridge between the pool of candidate items and the final set of personalized recommendations. In essence, scoring involves the data-driven assessment of each candidate item's relevance to each user's inferred preferences. The scoring algorithms, which aim to assign numerical values to candidate items, are plentiful. They can be divided into two main groups: \acrfull{cb} and \acrfull{cf}. As previously stated, \acrshort{cb} \acrshort{rss} rely on item description data, and will not be further explored in this dissertation.

\acrshort{cf} leverages the wisdom of the crowd. It bases recommendations on the interaction data of other users and items.  \acrshort{cf} algorithms can be further divided into two sub-types: memory-based and model-based. Memory-based approaches, such as user-based and item-based collaborative filtering, use nearest-neighbour techniques to predict item ratings or item relevance from the user-interaction data of similar users or items. Model-based approaches, such as matrix factorization and neural network methods, use machine learning techniques to learn latent factors that represent user-item interactions. 

\acrshort{cf} is advantageous because it can infer subtle user preferences, especially when large amounts of feedback are available, either explicitly or implicitly given. However, \acrshort{cf} suffers from the \emph{sparsity} problem. Its performance may not be so good when there is little user-interaction feedback available or when users' preferences diverge significantly.

Hybrid systems can be created by integrating different recommendation methods, e.g.\ collaborative filtering and content-based \cite{burke2002hybrid}. Given that different recommender scoring algorithms work well in different scenarios, hybrid systems are a way of combining their strengths.

In this dissertation, as we have already said, the only data that we work with is user feedback data. Naturally, then, we will focus on \acrshort{cf} methods and, more specifically, on model-based \acrshort{cf}. There is a vast number  of specific models, including methods to work with explicit feedback and methods to work with implicit feedback. The next few subsections present some popular \acrshort{cf} methods --- ones that will be used in later chapters of this dissertation.

\subsection{Modeling user-item interactions}
\label{sec:models}

The power of an \acrshort{rs} comes from its ability to understand the users and the items in the system based on the available interactions, as well as any other data such as item descriptions. In several areas of machine learning, it is useful to learn latent representations for entities such that the system can understand how they relate to each other. \acrshort{rss} are no exception to this. Many model-based CF recommendation algorithms learn latent representations for their users and items. 

One of the first  \acrshort{rss} based on latent representations, and the most influential, is \acrfull{mf} \cite{funk2006netflix}. The idea is to represent users and items in a low dimension latent space. If the number of latent factors is denoted by $d$, then each user $u$ is represented by a vector $p_u$ and each item $i$ by a vector $q_i$, both of dimension $d$. Then, in the case of explicit feedback, we can compute predicted ratings by taking a dot product:
\begin{equation}
\label{eq:MF}
F_\theta(u, i) = p_u^T q_i
\end{equation}
where $\theta = \{\{p_u\}_{u \in U}, \{q_i\}_{i \in I}\}$ is the parameter set of the model. This seemingly simple model has proven effective, and became famous, by emerging during the Netflix recommendation challenge \cite{bennett2007netflix}. The interactions in the Netflix challenge were numeric ratings. But the same model can also be used in \acrshort{irs} by scaling the output properly \cite{hu2008collaborative}; see Section \ref{sec:learning_imp}.  

Recent research has shown that the inner product in Eq.\ \ref{eq:MF} is a very accurate way of representing user-item interactions and is not easily outperformed even by recent neural neural network models \cite{rendle2020neural}. Nevertheless, there are many extensions to the simple dot-product model. The simplest one is adding user and item biases to the equation. That is, 
\begin{equation}
\label{eq:MF_bias}
F_\theta(u, i) = p_u^T q_i + b_u + b_i
\end{equation}
where $b_u$ and $b_i \in R$ are scalars that model each user's and item's individual contributions to the prediction, and $\theta = \{\{p_u, b_u\}_{u \in U}, \{q_i, b_i\}_{i \in I}\}$. Other notable extensions include SVD++ and AsymmetricSVD \cite{koren2009matrix}.

More recently, \acrfull{nn} based models have gained traction in the \acrshort{rs} field. Several such models have been proposed \cite{cheng2016wide,he2017neural,naumov2019deep}, with some achieving impressive results. Several properties of neural networks explain their increasing use in this field. First, the flexibility of neural architectures allows for a wide variety of data inputs, making it relatively straightforward to combine interaction data with, e.g., user demographic data, item descriptions, and contextual data \cite{guo2017deepfm}. Second, neural networks are a great tool for latent representation learning, as shown by the success, for example, of variational auto-encoder recommenders \cite{liang2018variational}.

Later in this work, we will utilize one of the first and most popular \acrshort{nn} based recommenders, the \acrfull{mlp}, introduced in \cite{he2017neural}. Similarly to MF, this model also learns $d$-dimensional user and item embeddings, $p_u$ and $q_i$, but it then combines them through a \acrlong{mlp} neural network,
\begin{align}
    F_\theta(u, i) = \text{MLP}(p_u || q_i)
\label{eq:MLP}
\end{align}
where $||$ is a concatenation operator and $\theta = \{\{p_u\}_{u \in U}, \{q_i\}_{i \in I}, \theta_{MLP}\}$, $\theta_{MLP}$ being the parameters of the \acrshort{mlp}. The \acrshort{mlp} consists of a set of feed-forward layers $f_1, \ldots, f_L$, such that,
\begin{align}
    f_0 &= p_u || q_i \\
    f_l &= \text{ReLU}(W_l f_{l-1}), \quad \text{for} \, l \in 1, \ldots, L-1; \\
    f_L &= g(w_L^t f_{L-1})
\end{align}
\noindent
where $W_l$ is the weight matrix for hidden layer $l$, $w_{L}$ is the output layer's weight vector, and $\text{ReLU}(x) = \text{max}(0, x)$. In the output layer $f_L$, an activation function $g$ is used to scale the output to the desired interval (often to [0, 1] in the case of \acrshort{irs}).

\subsection{Learning from explicit feedback}
\label{sec:learn_exp}

In \acrshort{ers}, the known ratings are indicative of the users' preferences. Therefore, scoring can be performed through \emph{rating prediction}. Given a user $u \in U$ and item $i \in I$, the rating prediction task consists of designing or learning a function $F: U \times I \xrightarrow{} \real$, parameterized by $\theta$ that predicts user-item ratings.

One way to learn the model parameters $\theta$ (the user and item embeddings, $p_u$ and $q_i$ and any other parameters) is through gradient descent: their values are initialised with randomly-chosen values; the algorithm proceeds by sampling instances from the training set of known ratings, calculating the difference between the predicted and the actual ratings for these instances; and updating $p_u$ and $q_i$ through gradient descent to minimize these errors. In \acrshort{ers}, the most commonly used loss function is the Mean Squared Error (MSE). In this case, given a batch of training instances $\mathcal{B}$, the loss to be minimized is:
\begin{align}
    \label{eq:FunkSVDloss}
    \mathcal{L(\mathcal{B}|\theta)} = \frac{1}{\#\mathcal{B}} \sum_{(u, i, r_{ui}) \in \mathcal{B}} (r_{ui} - F_\theta(u, i))^2 + \lambda ||\theta||
\end{align}
where $\lambda$ is a regularization hyper-parameter, used to avoid overfitting, $||\cdot||$ denotes the Frobenius norm, and $\#$ denotes the cardinality of the set.

A \acrlong{mf} model learned with the MSE loss was popularized as FunkSVD \cite{funk2006netflix}, after its success at the Netflix prize challenge \cite{bennett2007netflix}. 

\subsection{Learning from implicit feedback}
\label{sec:learning_imp}

Implicit feedback differs drastically from the explicit case. In the latter, the relevance to the user of a given candidate item can be given by the prediction of a numeric rating. But, for the former, all the observed interactions are assumed to be equally relevant, even if this assumption is a simplification. Furthermore, with implicit unary data, we have no negative sentiment to learn from. For the purposes of learning, it is common to assume that unobserved interactions are less relevant than observed ones. This is a key assumption that underpins the learning objectives that will be explored in this section. Naturally, this assumption is also a simplification because unobserved interactions are very often only a case of the user having never been exposed to the item; other times, they are cases where the user was exposed to the item but, for whatever reason, did not interact with it. In summary, from the available implicit data, we take it that all interactions in $R$, that is observed interactions, are of equal relevance among themselves and of higher relevance than those in $R^- = \{(u, i) | u \in U, i \in I, (u, i) \notin R\}$, the unobserved interactions.

In the absence of explicit ratings, we must score the candidate items by inferring their \emph{relevance} to the user. Given a user $u \in U$ and item $i \in I$, the \textit{relevance prediction} task consists in designing or learning a function $F: U \times I \xrightarrow{} \real$, parameterized by $\theta$, that predicts user-item interaction relevance. The predominant objectives that suit implicit data can be categorized in two classes: point-wise and pair-wise. Below, we explore each of these classes. Nevertheless, we acknowledge that there are other classes of objectives, especially list-wise ones \cite{shi2010list}, that will not be explored in this dissertation because they are less popular.

\subsubsection{Point-wise objectives}
\label{sec:point}
Point-wise objectives, as the name suggests, score data points (interactions) individually. That is, during learning, the model's current prediction for the interaction is compared against an observed value. Now, because implicit feedback consists of unary observation data, we define the following labels for the interactions,
\begin{equation}
    Y_{ui} = \begin{cases}
    1, (u, i) \in R \\
    0, (u, i) \in R^-
    \end{cases}
    \label{eq:imp}
\end{equation}
Hence, learning from implicit feedback data has one major particularity. In the explicit case, the training set consists only of observed ratings (denoted $R$). In other words, unobserved interactions are treated as \emph{missing}. This is not the case for implicit data, where the unobserved interactions are part of the training set ($R^-$, labeled as $0$'s), along with the observed interactions ($R$, labeled as $1$'s).

Using this labeling (Eq.\ \ref{eq:imp}), the implicit feedback task closely resembles a classification task, with observed interactions treated as ones, and non-observed ones treated as zeros. Therefore, the same objective functions used in classification tasks can be used \cite{hu2008collaborative}. 

A very natural choice is to use the same \acrshort{mse} loss from before, but now on the labels from Eq.\ \ref{eq:imp}. An advantage is that it allows a model to be learned based from implicit data in the same way as with explicit ratings. In this case, the loss function be to be minimized is,
\begin{align}
    \label{eq:mse_loss}
    \mathcal{L(\mathcal{B}|\theta)} = \frac{1}{\#\mathcal{B}} \sum_{(u, i) \in \mathcal{B}} (Y_{ui} - F_{\theta}(u, i))^2 + \lambda ||\theta||
\end{align}
where, again, $\lambda$ is a regularization hyper-parameter that controls overfitting on the model's parameters $\theta$. While this is an easy approach, this objective treats the labels given to the observed and unobserved interactions as numerical values of 0 and 1, rather than as class labels. 

A more sound approach is to predict the probability of observing each label. \acrfull{bce} gives one way of doing this.

Formally, let $P(Y_{ui} = 1) = g(F_\theta(u, i))$, where $g$ is a function that bounds the model's outputs to $[0, 1]$, so that the outputs are well defined probabilities. Here, we will use the Sigmoid function, defined as $g(x) = 1 / (1 + e^{-x})$, but there are many other possible choices. Then, the likelihood of the observed data is,
\begin{equation}
\label{eq:bce_loss}
    \prob(R|\theta) = \prod_{u \in U} \prod_{i \in I} \prob(Y_{ui} = 1)^{Y_{ui}} \prob(Y_{ui} = 0)^{1 - Y_{ui}}
\end{equation}
where $\prob(Y_{ui} = 0) = 1 - \prob(Y_{ui} = 1)$. For numerical stability, during learning, we minimize the negative log-likelihood, subject to L2 regularization to avoid overfitting.\footnote{This form of regularization is equivalent to the input of spherical priors under the model parameters \cite{mnih2008probabilistic}.} In this case, the loss function for a data batch $\mathcal{B}$ is,
\begin{equation}
\label{eq:bce_loss2}
    \mathcal{L(\mathcal{B}|\theta)} = \frac{1}{\#\mathcal{B}} \sum_{(u, i) \in \mathcal{B}} -Y_{ui}\log\prob(Y_{ui} = 1) - (1 - Y_{ui}) \log\prob(Y_{ui} = 0) + \lambda ||\theta||
\end{equation}
%\derek{I'm probably being too fussy but: the right-hand side does not mention the batch $\mathcal{B}$.} \victor{Ur not! Fixed.}

In practice, regardless of the specific objective chosen, the parameters are learned by mini-batch gradient descent, minimizing the average batch loss on each step. One problem, though, is that the data is usually very imbalanced. This happens because the set of unobserved interactions $R^-$ is, in general, much larger than the set of observed ones $R$. To alleviate this issue, a sampling method is used. On each training epoch, the training data consists of the observed interactions $R$ and an ($\#R\times N$)-sized randomly-selected sample of non-observed interactions from $R^-$, where $N$ is a hyper-parameter. Algorithm \ref{alg:point} formally describes the method of sampling used with point-wise learning objectives.

\begin{algorithm}[t]
    \caption{Learning a \acrshort{cf} model from implicit feedback with Eq.\ \ref{eq:mse_loss} or \ref{eq:bce_loss2}.}
    \label{alg:point}
    \SetAlgoNlRelativeSize{-1}
    \KwData{The observed and unobserved set of interactions: $R$ and $R^-$.}
    \KwIn{$N$ the number of negative samples per positive; $\lambda$: the regularization strength; $\eta$: the learning rate.}
    \KwResult{$F$: The learned scoring function.}
    \SetAlgoNlRelativeSize{-1}
    \SetNlSty{textbf}{(}{)}
    \SetAlgoNlRelativeSize{-1}
    \SetNlSty{}{}{}

    Initialize model parameters $\theta$\;

    \While{not converged}{
        Sample an ($\#R\times N$)-sized batch of negative samples, $\mathcal{B^-}$, from $R^-$\;
        Construct the training data for the current epoch as $\mathcal{B} = \{R, \mathcal{B^-}$\}\;
        \For{each mini-batch $\mathbf{b} \subset \mathcal{B}$}{
            Compute the loss for the batch $\mathcal{L(\mathbf{b}|\theta)}$\;
            Compute the gradient with respect to the loss\;
            Update model parameters using gradient descent with learning rate $\eta$\;
        }
    }
\end{algorithm}

\subsubsection{Pair-wise objectives}
\label{sec:pair}

Pair-wise objectives score pairs of interactions to learn the most plausible ranking. Broadly, they are based on the principle that observed interactions should always have higher relevance than unobserved ones. Here, we will cover only the most popular among these objectives, \acrfull{bpr}, but there are others. One notable example is LambdaRank \cite{burges2010ranknet}. For comprehensive reviews on the matter, refer to \cite{burges2006learning, balakrishnan2012collaborative}.

Let $F_\theta(u, i)$ denote the relevance score of item $i$ to user $u$. For ease of notation, let $F_{uij} = F_\theta(u, i) - F_\theta(u, j)$. Then, $F_{uij}$ models how much user $u$ prefers item $i$ over $j$.  In \acrshort{bpr}, given a user $u$ and a pair of items $(i, j)$, the probability that the user $u$ will prefer item $i$ over $j$ is modeled as.
\begin{equation}
\label{eq:bprP}
    \prob(i >_u j) = \text{Sigmoid}(F_{uij})
\end{equation}
Again, the Sigmoid function is used to constrain model outputs to the $[0, 1]$ probability interval. Then, the likelihood of all the observed preferences is given by,
\begin{equation}
\label{eq:bpr}
    \prob(R) = \prod_{u \in U} \prod_{i \in R_{u\cdot}} \prod_{j \notin R_{u\cdot}} \prob(i >_u j)
\end{equation}

The \acrshort{bpr} loss function is the negative log-likelihood, subject to L2 penalty. It has been shown that optimizing the full likelihood is very slow \cite{rendle2009bpr}. Instead, a better approach is to sample positive-negative interaction pairs randomly and perform stochastic gradient updates. Therefore, the loss for each sampled interaction pair is,
\begin{equation}
\label{eq:bpr_loss}
    \mathcal{L}(u, i, j|\theta) = -\log(\prob{(i >_u j)}) + \lambda ||\theta||
\end{equation}
Algorithm \ref{alg:bpr} describes the \acrshort{bpr} learning procedure. 

\begin{algorithm}[t]
    \caption{Learning a \acrshort{cf} model from implicit feedback with  \acrlong{bpr} (Eq.\ \ref{eq:bpr_loss})}
    \label{alg:bpr}
    \SetAlgoNlRelativeSize{-1}
    \KwData{The observed and unobserved set of interactions: $R$ and $R^-$.}
    \KwIn{$\lambda$: the regularization strength; $\eta$: the learning rate.}
    \KwResult{$F$: The learned scoring function.}
    \SetAlgoNlRelativeSize{-1}
    \SetNlSty{textbf}{(}{)}
    \SetAlgoNlRelativeSize{-1}
    \SetNlSty{}{}{}

    Initialize model parameters $\theta$\;

    \While{not converged}{
        Sample one interaction $(u, i)$ from $R$\;
        Sample one negative interaction $(u, j)$, for the same user, from $R^-$\;
        Compute $P(i >_u j)$ with Eq.\ \ref{eq:bprP}\;
        Compute the negative log likelihood according to Eq.\ \ref{eq:bpr_loss}\; 
        Update model parameters using gradient descent with learning rate $\eta$\;
    }
\end{algorithm}

\section{Top-$n$ Recommendation}
\label{sec:top_n}

The last step of the recommendation workflow is to select a top-$n$ set of items to be presented to the user: for a user $u \in U$, the top-$n$ recommendation task consists of selecting $Z_u^n \subseteq C_u$, which is the set of $n$ items from $C_u$ that are predicted to be most appealing to $u$.

The scoring functions from the previous section, either in the form of predicted ratings (explicit feedback) or predicted relevance scores (implicit feedback), allow the system to rank items: the higher the predicted value for an interaction, the more pertinent we expect the item to be for the user. The top-$n$ recommendation task is conventionally performed by sorting the candidate items $C_u$ in descending order of their predicted ratings or relevance scores and then forming $Z_u^n$ by selecting the top-$n$ items from this sorted set. We will refer to these ways of doing top-$n$ recommendation as \acrfull{rabr}, in the case of \acrshort{ers}, and \acrfull{rebr}, for \acrshort{irs}.

Nevertheless, in many cases, and for many reasons, a system might use alternative methods for obtaining the top-$n$. For example, it may be that some `slots' in the top-$n$ must be reserved for sponsored items. Or, in a hybrid \acrshort{rs}, it may be necessary to combine the scores of the models that are part of the hybrid before sorting and selecting the top-$n$, or even to ensure a mix of items that get high scores from the models that are part of the hybrid \cite{Burke-2002}. In addition, for systems where \emph{beyond-accuracy} recommendation objectives are important, many researchers have proposed methods for \emph{re-ranking}\footnote{Re-ranking is a tool to incorporate beyond-accuracy objectives into the top-$n$ recommendation stage of a \acrshort{rs}. Nevertheless there are ways of incorporate these objectives into other stages, e.g.\ the scoring stage \cite{bertani2020combining, diez2019optimizing}} \cite{10.1145/2926720}. In summary, these methods aim to modify the order, or even change items in the recommendation list, in order to increase some beyond-accuracy criteria.

%These so-called \emph{beyond-accuracy} objectives are plenty. 
\cite{10.1145/2926720} presents a comprehensive review of the most-researched beyond-accuracy recommendation objectives. In the upcoming sections, we will introduce the concepts of diversity, serendipity, novelty and coverage. In addition, we will also discuss fairness and explainability. These two are not listed in \cite{10.1145/2926720}, but one can argue that they do deserve to be treated as additional beyond-accuracy objectives.

Later in this dissertation, we will also introduce novel forms of ranking that are uncertainty-aware: The final set of top-$n$ recommendations can then take into account the estimated prediction or label uncertainties of the recommendations.

\subsection{Diversity}

Top-$n$ diversity in recommender systems refers to the extent to which a recommendation list contains a wide range of distinct items, aiming to offer users a variety of choices. It is a measure of how dissimilar or different the items in the top-$n$ recommendations are from one another, and it plays a crucial role in enhancing user satisfaction and exploration of new content. In essence, diversity ensures that users are presented with a balanced and heterogeneous set of recommendations rather than a narrow selection of similar items.

%Many items in a system's catalog tend to be similar. For example, in a music \acrshort{rs}, many songs are from the same artist. Following on this example, recommending several songs from the same artist to a user might be very accurate if the user is known to like the artist. Nevertheless, this non-diverse list of recommendations would not be helpful on helping the users to find what they are looking for. Therefore, to better assist users navigating through the system, the given recommendation lists should be not only accurate but also diverse. \derek{I'm still not happy with this paragraph. (a) Same artists music is OK as one example, but it seems a narrow example, (b) ending the paragraph with talk of ``navigating'' doesn't seem useful. The point is: meaningful choice.}

%\victor{Alternative paragraph to the one above} 
Many items in a system's catalog tend to be similar. For example, in a music \acrshort{rs}, many songs are from the same artist; in a movie \acrshort{rs}, many movies will share genres. Therefore, the system may provide a list of recommendations composed of items that are similar among themselves, that is, a non-diverse recommendation list. The recommendations might be accurate, for example, recommending several songs from the same artist or movies of the same genre if the user is known to like that artist or genre. But, such low diversity means that the \acrshort{rs} does not (i) expose the user to much of the vast product catalog, and (ii) offer the user a \emph{meaningful choice} of recommendations.

We remark that, in this section, we present the most common definition of diversity in \acrshort{rss}, but there are others. One example is \emph{temporal diversity}, which refers to the difference in two recommendation lists given to the same user at different time points. For a more extensive review, see \cite{10.1145/2926720}.

\subsection{Serendipity}

Serendipity is a concept that derives from \emph{surprise}. In \acrshort{rs}, surprising recommendations are those that deviates from the user's expectations. Giving surprising recommendations is not necessarily hard. For instance, based on some item distance metric, items that are the furthest from the items in the user profile would likely be very surprising to the user. Nevertheless, these same surprising items would most likely not be relevant. For this reason, serendipity goes one step further from surprise. A serendipitous recommendation can be thought as a surprising, yet relevant, item.

Giving relevant recommendations is already a hard task in most cases. Now, finding relevant and surprising recommendations is a lot harder. But the difficulty of the process should not stop the system from trying to find them. Serendipity brings unexpected and delightful discoveries to users. Systems that prioritize serendipity can help alleviate recommendation fatigue, a situation where users are repeatedly shown the same type of content. By introducing serendipitous items, users are less likely to grow tired of the recommendations and are more likely to return to the platform \cite{fang2022alleviating}. Ultimately, serendipity contributes to overall user satisfaction. Users appreciate platforms that not only cater to their known preferences but also offer exciting, unanticipated recommendations that add value to their experience \cite{chen2019serendipity}.

%\derek{Good, but I would mention discovery.} \victor{I feel like I already do. Is there anything specific that you are missing?}

\subsection{Novelty}

The concept of novelty is closely related to serendipity. In fact, in the recommender systems literature, the terminologies often overlap. According to many authors, novelty also refers to recommendations that are not closely related to the user profile \cite{vargas2011rank, zhang2013definition, castells2021novelty}. Nevertheless, other researchers distinguish the concepts. According to \cite{herlocker2004evaluating}, a \emph{novel} recommendation is not necessarily \emph{surprising}. Take as example a movie recommender, where a certain user $u$ frequently consumes action movies. Now imagine $u$ gets recommended one action movie which they are unaware of. Such a recommendation is novel, but not surprising. 

In summary, novelty and serendipity share the idea that the item is \emph{unknown} to the user, but do not share the element of \emph{surprise}. In addition, \cite{kapoor2015like} extends the notion of novelty in the case of systems that support repeat consumption, e.g.\ music recommenders. In these sorts of systems, a novel item is not necessarily unknown by the user, but could be forgotten.

\subsection{Coverage}
\label{sec:coverage}

User coverage refers to the fraction of the users in the system to which the recommender is able to provide recommendations. Under this definition, coverage differs from the previous concepts in this section: it does not refer to individual recommendations or sets of recommendations, but instead, it reflects the recommender's ability to reach its users. There are several reasons why users might not be covered by the system. For example, as previously stated, CF-based \acrshort{rss} depend on interaction data, and are, therefore, unable to provide recommendations to extreme cold-start users -- that is, those who have not interacted with any item. Another possible cause for loss of coverage is computation delay: when the system is unable to compute recommendations in time \cite{liu2017related}.

Symmetrically, item coverage is the fraction of the item catalog that can get recommended. Item coverage is very dependent on the choice of recommendation algorithm. One extreme example is popularity-based recommenders: these systems simply recommend the most popular items to every user. In this case, only a tiny fraction of the items are ever recommended. Several other methods also suffer from popularity bias: the more popular an item is, the more it gets recommended. In fact, the mitigation of popularity bias is an active research field in \acrshort{rs} \cite{abdollahpouri2019managing, ahanger2022popularity}.

Finally, there is a third notion of coverage, which can, in fact, be defined for recommendation lists. In this case, it is the fraction of the desired number of recommendations that the system is able to provide to a user. Under this definition, the notion of coverage considers the possibility that users may be only partially covered. That is, if a system is programmed to present the top-$n$ recommendations to user, there may be cases where the system may only recommend $m < n$. This particular definition is relevant to \acrfull{ubf}, a ranking method that we will explore throughout this dissertation.

\subsection{Fairness}

Fairness in recommender systems encompasses multiple dimensions, depending on whether we view it from the user or item perspective. Recognizing these distinctions is essential to address biases and ensure equitable recommendations.

From the user perspective, fairness refers to treating users impartially, regardless of their demographic characteristics or preferences. Fairness entails avoiding algorithmic biases that could disproportionately impact certain groups.

From the item perspective, fairness involves providing visibility to all items in the system. A fair system should, for example, avoid the popularity bias -- the case where popular items are recommended very frequently and unpopular ones get almost no exposure. In addition, the system must avoid disfavoring certain item providers. A concrete example of unfairness happens in the music domain, where female singers get recommended less than male singers \cite{melchiorre2021investigating}.

There literature investigating fairness in \acrshort{rs} is growing. For a comprehensive survey on the matter, we refer to \cite{wang2023survey}. Recently, \cite{wang2023uncertainty} proposed the utilization of uncertainty estimates to ensure fairness in recommenders.

\subsection{Explainability}

Explainability has been a hot topic of discussion in all fields of machine learning in recent years, and the \acrshort{rs} field is no exception. Explainability in recommender systems can refer to the capability of providing transparency or interpretable reasons for why a specific recommendation was made. It involves making the recommendations, and perhaps the recommendation process, understandable to users, allowing them to comprehend why a particular item was suggested to them. Due to the increasing importance given to explainability, the literature in the field is evolving rapidly. Here, we only briefly describe its importance. A comprehensive survey on methods for explainability in \acrshort{rs} can be found in \cite{zhang2020explainable}.

Accompanying recommendations with an explanation has several purposes \cite{tintarev2010designing}. From the user point of view, explanations that increase transparency might also increase the user's trust in the system. Explanations might also increases persuasiveness: a well put explanation may persuade users to believe that certain items are relevant to them \cite{bellini2018knowledge}.

From the system point of view, explainability can assist in identifying and addressing biases in recommendation algorithms. By revealing the factors that influenced a recommendation, it becomes easier to detect and rectify any undesirable biases, ensuring fairness and ethical use of recommendation systems \cite{abdollahi2018transparency}.

\section{Evaluation}

In the evaluation phase of the development of a new \acrshort{rs}, the quality of the system's predictions and recommendations must be rigorously assessed. There are three primary evaluation approaches, \emph{offline}, \emph{online} and \emph{user trials}.

The offline evaluation of an \acrshort{rs} utilizes historical data. Much like other traditional \acrshort{ml} tasks, such as regression or classification, to evaluate a \acrshort{rs} offline, a \emph{test set} of known ratings or interactions is initially hidden while learning the scoring model from the remaining data. Then, this test set is used to assess the quality of given predictions and recommendations. The hold-out test set may be selected in several ways, we list the three most common:

\begin{description}
    \item [Random sampling:] The case where every interaction from $R$ is sampled with equal probability.
    \item [User-based sampling:] A certain amount of interactions $m$ from each user is sampled to compose the test set. For each user the $m$ interactions are sampled at random from the user profile $R_{u\cdot}$. To account for varying profile sizes, another variation of user-based sampling instead samples a certain fraction of the interactions in each user profile.
    \item [Chronological sampling:] In practice, user interactions are influenced by their past experiences. Therefore, in order to reflect reality, chronological sampling consists in taking the $m$ latest interactions for each user as the test set. Similarly to user-based sampling, a fraction of each user's profile can be taken instead.
\end{description}

Offline evaluation is typically the first form of evaluation that a \acrshort{rs} is subject to. This is mainly because it is cost-effective and efficient since it does not require real-time user interactions. In addition, it allows for the testing of various algorithms and configurations in a controlled environment.

Online evaluation takes the evaluation process beyond the controlled environment of offline testing and ventures into the real-world interactions between users and the recommender system. It consists in deploying the recommendation system in a live environment and continuously collecting data on user interactions with the system. It better reflects the dynamic nature of a \acrshort{rs} by assessing the algorithm's performance in a real-world setting. Another advantage is enabling adaptive algorithms that can continuously learn and improve. Despite its benefits, evaluating a system online is not straightforward. Conducting live experiments can affect user experiences, potentially leading to user dissatisfaction if recommendations are not optimal. In addition, online evaluation can be resource-intensive and potentially expensive. For these reasons, academic research often resorts exclusively to offline evaluation.

Finally, user trials involve gathering feedback from trial participants who interact with the system in a controlled way. This typically includes surveys, interviews, or feedback mechanisms within the application for users to provide their opinions on the recommendations. By directly querying the users about their experience, user trials allow the system to gather qualitative feedback on user satisfaction and perception of recommendations. Unfortunately, user trials are even harder to implement, because they rely on user cooperation and willingness to provide feedback. In addition, user opinions may be more subjective, and therefore, harder to evaluate quantitatively.

Since this dissertation exclusively uses offline evaluations, the remainder of this section covers offline evaluation in a little more detail.

\subsection{Evaluating rating predictions}

In \acrlong{ers}, scoring is performed through rating prediction. Therefore, predicted ratings can be compared against a held-out test set of known ratings. In this case, there are plenty of evaluation metrics to be borrowed from the regression literature. Among them, the most commonly used for rating prediction evaluation is the \acrfull{rmse}, mostly because it was the metric of choice in the Netflix prize challenge \cite{bennett2007netflix}. This metric simply compares the predicted ratings to the known ratings in the test set $T$, that is,
\begin{equation}
\label{eq:rmse}
    \text{RMSE} = \sqrt{\frac{\sum_{r_{ui} \in T} (F_{ui} - r_{ui})^2}{\#T}}
\end{equation}

Other alternatives are the \acrfull{mse}, which is the RMSE squared, and the \acrfull{mae}, defined as,
\begin{equation}
    \text{MAE} = \frac{\sum_{r_{ui} \in T} |F_{ui} - r_{ui}|}{\#T}
\end{equation}

\subsection{Evaluating top-$n$ accuracy}
\label{sec:eval_topn_acc}

Of much greater importance than evaluating rating predictions is to evaluate the top-$n$ recommendations \cite{herlocker2004evaluating, shani2011evaluating}. Indeed, for \acrshort{irs}, where explicit numeric ratings are not available, top-$n$ evaluation is the only option. Many metrics have been defined for evaluating the accuracy of top-$n$ recommendations. In general, these metrics are shared with the field of information retrieval, due to its similarity to the top-$n$ recommendation task. 

First, consider a test set of (held-out) interactions $T$. Now, let $T_u$ denote the set of items from users $u$'s interactions in $T$. In the case of \acrshort{irss}, $T_u = \{i | \langle u, i \rangle \in T\}$. But, for \acrshort{erss}, $T_u = \{i | \langle u, i, r_{ui} \rangle \in T \cap r_{ui} \geq \omega\}$. In the latter, $\omega$ is a threshold, used to avoid rewarding the system for recommending an item in the test set that received a poor rating. For example, in a $5\star$ rating scale, $\omega$ might be $4\star$: if a system recommends a test item that the user had rated 4 or $5\star$, then the recommendation is regarded as having been relevant to that user.

Two traditional metrics are Precision@$n$ and Recall@$n$. The precision and recall of the $n$-sized list of recommendations to user $u$, denote as $Z^n_u$, are given by:
\begin{equation*}
    \text{Precision@n}_u = \frac{\#\{Z_u^n \cap T_u\}}{n}
\end{equation*}
\begin{equation*}
    \text{Recall@n}_u = \frac{\#\{Z_u^n \cap T_u\}}{\#T_u}
\end{equation*}

The Precision@$n$ and Recall@$n$ of the system is reported as the average precision and recall among all users. That is,
\begin{align}
\label{eq:precision}
   \text{Precision@n} &= \frac{1}{\#U} \sum_{u \in U} \text{Precision@n}_u
\end{align}
\begin{align}
\label{eq:recall}
   \text{Recall@n} &= \frac{1}{\#U} \sum_{u \in U} \text{Recall@n}_u
\end{align}

Both precision and recall have a widely recognized issue when evaluating top-$n$ recommendations: they give equal importance to all the recommended items. In practice, the earlier an item appears in a list of recommendations, the more attention a user is likely to afford it and, ideally, the more relevant it should be to the user. Therefore, evaluation metrics should account for position in the top-$n$. Here we define two of the most commonly used position-aware recommendation accuracy metrics.

\begin{description}
    \item[\acrlong{map}:] The \acrshort{map} is a generalization of the traditional precision metric to account for the importance levels of the recommended items. To compute MAP, we first calculate the Average Precision (AP).  AP is calculated by summing up the precision values at each point where a relevant item is found in the recommendation list and then dividing by the total number of relevant items. Formally, for each user $u$, the Average Precision is calculated as,
    \begin{equation}
        \text{AP@n}_u = \frac{1}{\#T_u} \sum_{k=1}^{n} \text{Precision@k}_u \times \delta(Z_u^n(k) \in T_u)
    \end{equation}
    where $Z_u^n(k)$ is the k-th recommended item and $\delta(Z_u^n(k) \in T_u)$ is an indicator function that equals 1 if the item at position $k$ in the recommendation list is relevant for user $u$ -- that is, is in $T_u$ --, and 0 otherwise. Finally, to obtain the Mean Average Precision across all users, we calculate the average of the AP values,
    \begin{equation}
    \label{eq:map}
        \text{MAP@n} = \frac{1}{\#U} \sum_{u \in U} \text{AP@n}_u
    \end{equation}
    
    \item[\acrlong{ndcg}:] \acrshort{ndcg} measures the ranking\linebreak quality of recommended items, accounting for the position of relevant items in the list. It gives higher scores to relevant items that are ranked higher. The metric is composed of two components: 

    \begin{itemize}
        \item Discounted Cumulative Gain (DCG) calculates the cumulative relevance of recommended items, placing lower emphasis on items ranked lower in the list by using a logarithmic discount factor. DCG is computed as follows:
            \begin{equation}
            \text{DCG@n}_u = \sum_{k=1}^{n} \frac{2^{\delta(Z_u^n(k) \in T_u)} - 1}{\log_2(k+1)}
            \end{equation}
        \item Ideal Discounted Cumulative Gain (IDCG) represents the theoretical maximum possible DCG for a given set of relevant items. That is, if all items in $T_u$ are recommended before any other item $j \notin T_u$.
    \end{itemize}
    Finally, the Normalized Discounted Cumulative Gain (NDCG) is computed by dividing the DCG by the IDCG, which scales the DCG value between 0 and 1, and the system NDCG@$n$ is the average among all users:
    \begin{equation}
    \text{NDCG@n} = \frac{1}{\#U} \sum_{u \in U} \frac{\text{DCG@n}_u}{\text{IDCG@n}_u}
    \end{equation}
    
    % \item[\acrlong{mrr}:] The \acrshort{mrr} focuses on the position of the first relevant item in the recommendation list. It is the average of the reciprocals of the ranks of the first relevant item,
    % \begin{equation}
    %     \text{MRR} = \frac{1}{\#U} \sum_{u \in U} \frac{1}{\text{rank}_u}
    % \end{equation}  
    % where $\text{rank}_u = min_k : Z_u^{\#I}(k) \in T_u$ is the position in the recommendation list where the first relevant item appears. \db{So this has n=\#I. Is that the correct definition?} \victor{Ideally, I would like to define it for an n-sized list as all the others, but what happens if the first relevant item appears after the n-th position?}
\end{description}

\subsection{Beyond-accuracy top-$n$ recommendation evaluation}

As previously stated, there are several criteria, other than accuracy, that define what makes a good top-$n$ recommendation list. Therefore, there is also a plethora of metrics to evaluate beyond-accuracy recommendation criteria. Here, we describe some traditional ways of evaluating diversity, serendipity, novelty and user coverage.

\begin{description}
    \item[Top-$n$ diversity:] Top-$n$ diversity can be measured in several ways. In general, all the measures will rely on some item distance metric. Let $d(i, j)$ denote the distance between items $i$ and $j$. Then, the diversity in a list of recommendations can be calculated as the average distance between all the recommended items \cite{10.1145/2926720}. That is,
    \begin{equation}
        \text{Diversity}(Z_u^n) = \frac{\sum_{i \in Z_u^n} \sum_{j \in Z_u^n - i} d(i, j)}{n(n - 1)}
    \end{equation}
    
    \item[Serendipity:] Measuring serendipity is not straightforward, because it comprises surprise and relevance, two concepts that are hard to measure themselves. The general rule of thumb, as proposed by \cite{ge2010beyond}, is to measure it as,
    \begin{equation}
        \text{Serendipity}(Z_u^n) = \frac{\#\{Z_u^{\text{surprising}} \cap T_u\}}{n}
        \label{eq:serendipity}
    \end{equation}
    In this equation, $Z_u^{surprising}$ denotes the subset of the recommended items that are surprising according to some defined metric. One possibility is to use the minimum distance to the items in the user profile, that is,
    \begin{equation}
        Z_u^{\text{surprising}} = \{i \in Z_u^n | \min_{j \in R_{u\cdot}} d(i, j) > \epsilon\}
    \end{equation}
    where $\epsilon$ denotes the minimum distance for an item to be deemed surprising.

    \item[Novelty:] Measuring novelty in recommenders is very challenging because it is practically impossible to infer whether a user is unaware of an item. One crude, non-personalised way to estimate novelty is to use the recommended items' popularity. The idea is, the less the item is interacted with, the more likely the item is to be novel \cite{10.1145/2926720}. Formally,
    \begin{equation}
        \text{Novelty}(Z_u^n) = \frac{\sum_{i \in Z_u^n} - \log_2\left(\frac{\#R_{\cdot i}}{\#R}\right)}{n}
    \end{equation}

    \item[Coverage:] Here we give a definition to the third notion of coverage that we mentioned in Section \ref{sec:coverage} --- the one that applies to recommendations lists --- since this is most relevant to later chapters of this dissertation. To measure the coverage of a recommendation list, one may simply compare the number of recommendations the system is able to deliver to the user against the desired number of recommendations. Formally, let $\#Z_u$ denote the size of the recommendation list for user $u$ and $n$ the desired recommendation list size, then the coverage of the recommendation list is,
    \begin{equation}
        \label{eq:coverage}
        \text{Coverage}(Z_u) = \frac{\#Z_u}{n}
    \end{equation}
    The average coverage is then obtained by averaging the individual coverage of each user.
\end{description}

%\db{Does your coverage evaluation metric correspond to the user-based and item-based ways you were defining coverage in 2.4.4?} \victor{Great catch, this went totally unnoticed for me. I made it clear that we are defining user coverage here, and that item coverage is symmetrical.} \dgb{I'm still worried. (A) We have a notion of coverage in chapter 4, so we must get it all consistent. Is the notion in ch.4 the same as the notion here and in 2.4.4 (b) does the wording for user coverage in 2.4.4 really equal the formula? (c) You say we just change indexes to get item coverage. But this is not correct. There is no such thing as $Z_i$ --- it doesn't make sense. (d) In fact, there is not even such as thing as $Z_u$. In the Table of notation, it is $Z^n_u$ - but that is a minor problem compared to the (a) and (b).} \victor{My bad. I didn't give this too much attention and blundered on the solution of your former comment. (a) I've checked that the coverage notation is the same as in chapter for and I checked that the code does exactly what I present here. (b) Hmm. Indeed it did not. The formula version is a 'coverage proportion' for each user, where the text leaned towards a 0/1 (cover/non covered) formulation for each user. I proposed fixes to sec 2.4.4. (c) Ur right, I am not going to present a formula for item coverage (nor user coverage in the 0/1 case) because it's not relevant to our work. (d) Here we have to use $Z_u$ -- suppressing the superscript $n$ because this is a rec list with no pre-defined size. I don't think it needs to be in the table. But this comment was relevant to the previous metrics in this chapter. They were using $Z_u$ instead of $Z_u^n$, I fixed all of them.}


\subsection{Uncertainty in recommender systems}

Uncertainty is present in every machine learning task. In particular, supervised learning tasks, such as scoring in \acrshort{rss}, are subject to prediction uncertainty \cite{hullermeier2021aleatoric}. We note that rating prediction is a regression problem. That is, a model is learned and used to predict a real-valued response variable: the rating for a given interaction. Similarly, and as previously stated, relevance prediction, particularly with point-wise objectives, resembles a classifier. As a consequence of the uncertainty around the predicted scores (ratings or relevances) that are used for ranking, the top-$n$ recommendation stage of \acrshort{rss} is also subject to prediction uncertainty.

In addition to prediction uncertainty, \acrshort{irss} also suffer from label uncertainty, which is introduced by the assumption of relevance (irrelevance) for observed (unobserved) interactions. In fact, a similar issue also appears in classification problems from the general \acrshort{ml} literature \cite{brodley1999identifying}.

Although this chapter is a literature review, we are not going to review papers that look at RS uncertainty here. Instead, we will present our review of existing relevant work alongside our novel proposed methods and in a consistent notation in subsequent chapters. However, the ML literature has many methods for uncertainty estimation, so we will review them briefly here and relate them to subsequent parts of this dissertation.

% The aforementioned methods for uncertainty handling have different motivations, depending on the main source of uncertainty that they tackle. For this reason, in the following chapters we will systematically organize the methods for uncertainty estimation in \acrshort{rss} according to their tackled uncertainty source. \db{Not sure what the previous sentence means/refers to} As a consequence of proposing such taxonomy to classify them, we leave all the uncertainty estimators to be introduced to \Cref{chapter:explicit,chapter:implicit,chapter:implicit_learn}. That is, we introduce methods from the literature alongside our own new methods in the later chapters of the dissertation. We are careful in these later chapters to be explicit about which methods come from the literature and which are novel, as per \Cref{tab:explicit_models,tab:implicit_models4,tab:implicit_models5}. Furthermore, as mentioned in contributions \cref{sec:cont_exp,sec:cont_imp}, we present all of them in a common notation. 

\begin{description}
     \item[Probabilistic Regression:] There are regression techniques that model the target variable in the form of probability distributions. From these distributions, it is possible to infer the uncertainty using dispersion metrics, such as their variance. One example is the CPMF recommender model, that we explore in Chapter \ref{chapter:explicit}.

     \item[Prediction Intervals:] Instead of providing a single point prediction, regression models can be used to generate prediction intervals, which express a range of values within which the true target variable is likely to fall with a certain level of confidence. Prediction intervals may be derived from probabilistic regression methods, or from distribution-free methods, such as conformal predictions \cite{vovk2005algorithmic}.

     \item[Residual Analysis:] Analyzing the residuals (the differences between predicted and actual values) can help identify patterns of uncertainty in the model's predictions. EB-FunkSVD and EB-Linear (see Chapter \ref{chapter:explicit}) are examples of uncertainty estimation through residual analysis in \acrshort{rss}.

     \item[Ensemble Methods:] Ensemble methods can provide an indication of uncertainty by combining the outputs of multiple regression or classification models \cite{mendes2012ensemble, ren2016ensemble}. We have ensemble-based recommenders in both Chapter \ref{chapter:explicit} and Chapter \ref{chapter:implicit}.

     \item[Probabilistic Classification and Calibration:] Some classification algo-\linebreak rithms, such as logistic regression and naive Bayes, provide class probabilities. These probabilities represent the model's confidence in each class and can be used to assess uncertainty. Such probabilities are only useful if they are well calibrated \cite{dawid1982well, platt1999probabilistic}.
 \end{description}

% \db{This final subsection is still not quite working. As I said, it seems strange that the title is RS but the content is mostly ML. However, I think we can stick with this title but re-order:  make the last para become the second para (and rewrite a little bit). Then the subsection would tell the following story. Para 1: there is uncertainty is RS and ML. Para 2: although this chapter is a lit review, we're not going to review RS uncertainty because we do it alongside novel methods and in a consistent notation in subsequent chapters. Para 3: however, the ML lit has many methods, so we will review them briefly here and relate them to subsequent parts of this dissertation. I'm not sure that this will work. We can discuss.}

% \db{Another comment: Just like in chapter 1, it is noticeable that this subsection focuses on only one of the two types of uncertainty that appear in this dissertation: recommendation/prediction uncertainty but not mislabeling uncertainty (label uncertainty).}

% \victor{I made the specific changes that you suggested. Still, I am not happy with this section. Specially because it does not encompass all the new stuff from chapter 5. Also, I feel like it does not do what it is mean to: driving the tone into uncertainty before beginning the content chapters. I will revisit it soon.}

% \dgb{It is better but you may be right that it can be improved.}

%%%%%%%%%%%%%%%%%%%%%%%%% Old stuff 
% From those, we can derive several tools to assist the system. For instance, some hybrid systems must pick on-the-fly which of several models to draw their recommendation from. This decision might benefit from estimates of recommendation uncertainty. One simple approach would be to pick the least uncertain model. 

% Another concrete use-case is CoRec \cite{daCosta-Et-Al-2018}. CoRec employs a special form of data augmentation used two learn two rating prediction models simultaneously. The most certain predicted ratings from one recommender is used as input by the other -- that is, as if they were actual observed ratings -- and vice-versa.

% \derek{I'm not sure about these final 2 or 3 paragraphs. Haven't you said this already in Chapter 1. Why do we need an (incomplete) recap now?}


% \victor{Much like Section 2.3.5, this new section is here to introduce uncertainty in the context of top-n recommendations, because I moved the rest of the uncertainty discussion to Chapter 1. If you like it, we can try to make it more robust.}

% The recommendations provided by a \acrshort{rs} are subject to uncertainty. This is a consequence of the uncertainty around the predicted scores (ratings or relevances) that are used for ranking. From the scores and uncertainty estimates for the recommended items, some reasoning can be derived that can suggest what to expect from each recommendation list. For example, the average uncertainty in a list of recommendations may indicate how curated the recommender is for such user: the higher the average uncertainty, the least curated the list is. \derek{This doesn't work. ``curated'' is the wrong word. But I'm not sure what you're trying to say.}

% Moreover, items recommended under high uncertain may signal to a possibly \emph{novel} recommendation. Similarly, items recommended with a exceptionally high score and high uncertainty may be \emph{serendipitous}. Also, due to their high uncertainty, these same items may be those in need of an \emph{explanation} on why they are are suggested to the user.

% In addition, uncertainty estimates allows for alternative forms to select the top-$n$ recommendations. One example is \acrfull{prr}, a ranking method based on uncertainty method we introduce in Chapter \ref{chapter:explicit}.

% \derek{I understand the motivation. But it just feels too casual. Maybe if you move the stuff about ML (2.3.5)  towards the end of the chapter, then you can also include something there about uncertainty in RS, i.e.\ a brief recap of Chapter 1 (with a backward reference): why uncertainty arises; and why estimating it is useful.}

We are now ready to turn to our own contributions to this field.