\chapter{Estimating and Evaluating Uncertainty in Implicit Feedback Recommender Systems}
\label{chater:implicit}

Recommender Systems (RS) help users discover items in item catalogs. In general, for each user, the majority of the items are not relevant; therefore, the system's task is to select and present personalized recommendation lists to each individual user. In most RS domains, the item catalog is huge, meaning that users will have interacted with only a tiny fraction of the items. This is known as \textit{sparsity} \cite{grvcar2006data}. It means the system must infer the user's preferences from a relatively small amount of information, leading sometimes to the generation of unsuccessful recommendations. Other factors that make it difficult to make good recommendations include changes in user mood and changes in user preferences over time. Due to the challenges of modelling ever-changing preferences from sparse feedback, there can be high uncertainty in the recommendations that an RS makes to its users \cite{mazurowski_estimating_2013}. 

Traditionally, implicit feedback recommender systems -- those based on unary interaction data (e.g. click, purchase, watch, listen) and with no explicit feedback given -- learn to predict individual user-item interaction likelihood \cite{hu2008collaborative}. Nevertheless, the circumstances under which each interaction likelihood is predicted may vary. For instance, the sparsity is often unevenly distributed among users and items, meaning that the amount of information to support each prediction is different. Moreover, the difficulty of providing good recommendations vary depending on the user profile. On a movie recommendation domain, it is easier to give relevant recommendations to a user that only watches one genre of movies than to another with more varied preferences.

Given these varying circumstances around given predictions it is important for an RS to quantify its uncertainty. Estimates of prediction uncertainty can help the RS detect which of its recommendations are more or less likely to be incorrect \cite{hernando_incorporating_2013}. 



% The RS can use these estimates in a variety of ways. The simplest is to expose them to the user: a recommendation can be accompanied by a number, a text or a visual that shows how sure or unsure the RS is that the user will like the recommendation. If a poor recommendation (one that the user does not like) is accompanied by a declaration of high uncertainty, for example, user trust may not be lost in the way that it might have been if there had been no declaration of uncertainty. As well as exposing uncertainty estimates to users, an RS may use the uncertainty estimates internally. For example, it may use them to decide how many uncertain recommendations to show (perhaps none when building trust, perhaps more when aiming for serendipity); or a hybrid RS may use them to decide when to call on different recommendation algorithms.

The following Section (\ref{sec:setup}) formulates the uncertainty estimation problem for implicit feedback RS. Section \ref{sec:methods} proposes some techniques for solving this problem. Experiments are described in Section \ref{sec:results2} along with their results. In Section \ref{sec:related}, we review some related work that can be relevant to further work on RS uncertainty. Finally, Section \ref{sec:conclusion} contains our conclusions.

\section{Background}
\label{sec:setup}

Essentially, RS are designed to retrieve, from a large catalog, those items that are most relevant to each user. To achieve it's goal, the system must be able to predict (or score) the user-item interaction relevance. Based on the predicted relevances, the system then select the top-$K$ items for a given user.

Formally, define all user-item pairs as $\mathcal{D} = \{(u, i) | u \in U, i \in I\}$, where $U$ and $I$ are the sets of users and items in the system, respectively. We tackle the implicit feedback case, where users interact with items by clicking on them, buying them, and so on. We denote the set of observed user-item interactions by $\mathcal{D}^+ \subset \mathcal{D}$. The set of unobserved interactions is represented similarly by the symbol $\mathcal{D}- = \mathcal{D}- \mathcal{D}^+$. Then, in order to predict the relevance of previously unseen user-item pairs, the RS must learn a model $F_\theta(u, i) = r_{ui}$, parameterized by $\theta$, from the observed interactions.

With this setup, 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}.



In this work, we employ cross-entropy loss for every recommender. Nevertheless, we remark that ranking-based losses, such as Bayesian Personalized Ranking \cite{rendle2012bpr}, could also be used instead, without affecting the uncertainty estimation methods that we will explore in Section \ref{sec:methods}.

The methods for uncertainty estimation herein can be applied to a wide class of recommender algorithms, that is, there are several possible choices for $F_\theta$. Where possible, we will employ the well-known matrix factorization (MF) algorithm \cite{hu2008collaborative}. MF consists in learning a $D$-dimensional latent vector for each user and item. To predict $r_{ui}$, the user and item embeddings are combined, as follows,

\begin{align}
    F_\theta(u, i) = p_u^t q_i
\label{eq:mf2}
\end{align}

\noindent
where $p_u$ and $q_i$ are the user and item latent representations, respectively. In this case, $\theta = \{\{p_u\}_{u \in U}, \{q_i\}_{i \in I}\}$.

Furthermore, as explained in Section \ref{sec:intro}, we also want to use some uncertainty estimation methods that apply to neural models. For our neural recommender, we will use one of the simplest and most popular algorithms: He et al.'s Multi-Layer Perceptron (MLP) recommender \cite{he2017neural}. In this case, 

\begin{align}
    F_\theta(u, i) = \text{MLP}(p_u || q_i)
\label{eq:MLP}
\end{align}

\noindent
where $||$ is a concatenation operator and $\theta = \{\{p_u\}_{u \in U}, \{q_i\}_{i \in I}, \theta_{MLP}\}$. The 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 &= \text{Sigmoid}(w_L^t f_{L-1})
\end{align}
\noindent
where $W_l$ is the weight matrix for hidden layer $l$ and $w_{L}$ is the output layer's weight vector. The Sigmoid activation in the output layer scales the output to $[0, 1]$.

For both the MF and the MLP, the parameters are learned by mini-batch gradient descent, minimizing the binary cross-entropy loss. On each training epoch, the training data consists of the observed interactions $D^+$ and an $N$-sized randomly-selected sample of non-observed interactions from $D^-$, where $N$ is a hyperparameter.

We now turn our attention to uncertainty estimation methods. We use $\sigma_{ui}$ to denote the uncertainty associated with the predicted relevance $r_{ui}$.

\section{Uncertainty Estimation Methods}
\label{sec:methods}

Recommendation uncertainty has several causes, including sparsity of data, modeling choices, and stochastic learning algorithms. For this reason, methods for uncertainty estimation in the field are very diverse. In this section, we present several methods for uncertainty estimation, making clear which recommender algorithms they can be used with.

One of the most notable sources of uncertainty is sparsity. For this reason, the amount of available data offers good baseline estimates of recommendation uncertainty \cite{mazurowski_estimating_2013}. Furthermore, these estimates can be used with any recommendation algorithm. In the past, they have been used for explicit feedback recommenders, but here we use them in the implicit setting. These estimates can be user-centric or item-centric. Hence, following \cite{mazurowski_estimating_2013}, we define the following uncertainty metrics,

\begin{align}
    \usup : \sigma_{ui} = - \#u  \label{eq:usup} \\
    \isup : \sigma_{ui} = - \#i  \label{eq:isup}
\end{align}
\noindent
where $\#u$ and $\#i$ denote the number of observed interactions for the user and the item, respectively. The clear drawback of these uncertainty estimates is that they are either at user-level or at item-level, that is $r_{ui}$ is defined solely based on the user, or the item, but not on the user-item interaction. Nevertheless, they have the advantage of needing no additional learning and can be easily plugged into any system.

Beyond uncertainty introduced by the data, every recommender algorithm has its own uncertainty issues. Consider, for example, models that are based on representation learning, such as MF, where vector embeddings are learned as a latent representation for each user and item. For such models, the uncertainty surrounding the learning of such representations will affect the system recommendations. In fact, MF is known to suffer from learning instability \cite{gabbolini2022instability,pena2020combining}. 

In the case of explicit feedback, ensembles have been successful at estimating the uncertainty of MF rating predictions \cite{mazurowski_estimating_2013}. But, explicit feedback MF is only one of many algorithms that can benefit from ensembling. In fact, an ensemble can be used to estimate uncertainty for any model that relies on a stochastic mechanism, such as random parameter initialization or stochastic learning protocols. This is the case for implicit feedback MF (Eq.\ \ref{eq:mf2}) and also any neural network model, and in particular the MLP model (Eq.\ \ref{eq:MLP}).\footnote{An ensemble of neural models is often referred to as a Deep-Ensemble \cite{lakshminarayanan2017simple}.}

Formally, the principle is to train several models $F^{(k)}$, for $k = 1, \ldots, n$ using a different random initialization each time, and then calculate interaction relevance and uncertainty as follows:

\begin{align}
    r_{ui} &= \frac{\sum_{k=1}^n {F^{(k)}_{\theta}(u, i)}}{n} \label{eq:ensemble} \\
    \sigma_{ui} &= \frac{\sum_{k=1}^n \big( {F^{(k)}_{\theta}(u, i) - r_{ui} \big) ^2}}{n} \label{eq:ensemble_unc}
\end{align}

Bayesian Neural Networks (BNN) are another major tool tailored to uncertainty quantification in neural models. BNNs differ from their deterministic counterpart by treating the parameters as random variables \cite{goan2020bayesian}, which are assumed to follow some prior distribution $p(\theta)$. Given some training data $\mathcal{D}$, the posterior weight distribution, according to Bayes rule, is as follows,

\begin{align}
    p(\theta | \mathcal{D}) = \frac{p(\theta) p(D | \theta)}{p(D)}
\label{eq:bayes}
\end{align}

Calculating the posterior directly from Eq.\ \ref{eq:bayes} is generally not possible, because the data evidence, $p(D)$, is unknown. For this reason, inference methods such as Monte-Carlo Markov Chains (MCMC) \cite{geyer1992practical} and Variational Inference (VI) \cite{graves2011practical} are applied to approximate the exact posterior. More recently, Bayes By Back-propagation (BBB) has been proposed \cite{blundell2015weight}, a method that allows for the posterior weights distribution to be learned through back-propagation, just as the weights of a non-Bayesian network are learned by conventional back-propagation. Predictions can then be made using the estimated posterior. 

More precisely, the output's expected value $\mathbb{E}[F_\theta(u, i)]$ is a point prediction for the interaction relevance $r_{ui}$, and its variance $Var[F_\theta(u, i)]$ is an estimate of relevance uncertainty $\sigma_{ui}$. In practice, the values are estimated using samples $\theta_k, \ldots, \theta_k$ from the posterior, as follows,

\begin{align}
    r_{ui} &= \frac{\sum_{k=1}^n {F_{\theta_k}(u, i)}}{n} \label{eq:relevance} \\
    \sigma_{ui} &= \frac{\sum_{k=1}^n \big( {F_{\theta_k}(u, i) - r_{ui} \big) ^2}}{n} \label{eq:uncertainty}
\end{align}

Another uncertainty estimation method that is tailored to neural networks is MCDropout \cite{gal2016dropout}. The method, which can be thought of as an approximation of a Bayesian network, consists of taking multiple forward passes with dropout enabled at prediction time.\footnote{Conventionally, dropout is enabled at training time and combats overfitting. In MCDropout, it is enabled at prediction time to sample a space of predictions.} Formally, let $F^{(k)}$, for $k=1, \ldots, n$ denote $k$ predictions calculated with dropout enabled. Then, the final estimates for relevance and uncertainty follow according to Equations \ref{eq:ensemble} and \ref{eq:ensemble_unc}.

\section{Experiments}
\label{sec:results2}

In this section, we compare the uncertainty estimation methods proposed in the previous section, with the goal of answering the two research questions raised in Section \ref{sec:intro}. More specifically, we will compare RS that combine MF and MLP presented in Section \ref{sec:setup} with the uncertainty estimators discussed in Section \ref{sec:methods}. In Table \ref{tab:models}, we list all the models and uncertainty estimation methods that we consider.

\begin{table}[t]
    \centering
    \caption{Methods we compare.}
    \begin{tabular}{|c|ll|ll|} \hline
        Name & \multicolumn{2}{|c|}{Prediction model ($F$)} & \multicolumn{2}{|c|}{Uncertainty estimator} \\ \hline
        MF-NUS & ~~~~~~~~~~MF & (Eq.\ \ref{eq:mf2}) & ~$\usup$ & (Eq.\ \ref{eq:usup}) \\ \hline
        MF-NIS & ~~~~~~~~~~MF & (Eq.\ \ref{eq:mf2}) & ~$\isup$ & (Eq.\ \ref{eq:isup}) \\ \hline
        MF-Ensemble & ~~~~~~~~~~MF & (Eq.\ \ref{eq:mf2}) & ~Ensemble & (Eqs.\ \ref{eq:ensemble} -- \ref{eq:ensemble_unc}) \\ \hline
        MLP-NUS & ~~~~~~~~~~MLP & (Eq.\ \ref{eq:MLP}) & ~$\usup$ & (Eq.\ \ref{eq:usup}) \\ \hline
        MLP-NIS & ~~~~~~~~~~MLP & (Eq.\ \ref{eq:MLP}) & ~$\isup$ & (Eq.\ \ref{eq:isup}) \\ \hline
        BayesianMLP & ~~~~~~~~~~MLP & (Eq.\ \ref{eq:MLP}) & ~Bayesian inference (BBB) & (Eqs.\ \ref{eq:relevance} -- \ref{eq:uncertainty}) \\ \hline
        MCDropout & ~~~~~~~~~~MLP & (Eq.\ \ref{eq:MLP}) & ~Monte-Carlo Dropout & (Eqs.\ \ref{eq:ensemble} -- \ref{eq:ensemble_unc}) \\ \hline
        MLP-Ensemble & ~~~~~~~~~~MLP & (Eq.\ \ref{eq:MLP}) & ~Ensemble & (Eqs.\ \ref{eq:ensemble} - \ref{eq:ensemble_unc}) \\ \hline
    \end{tabular}
    \label{tab:models}
\end{table}

\subsection{Datasets}
We evaluate our models and uncertainty estimation methods  on two popular datasets: an implicit version of the Movielens 1M dataset \cite{harper2015movielens}\footnote{To make this dataset implicit, we simply treat every given rating as an implicit signal (1), ignoring the numeric rating value.} and one Pinterest dataset \cite{geng2015learning}.  Table \ref{tab:data} presents some summary statistics.

\begin{table}[t]
    \centering
    \caption{Datasets we use.}
    \begin{tabular}{|c|c|c|c|} \hline
        Dataset & Users & Items & Interactions \\ \hline
        Movielens & 6040 & 3416 & 1 Million \\ \hline
        Pinterest & 55187 & 9643 & 1.5 Million \\ \hline
    \end{tabular}
    \label{tab:data}
\end{table}

For both datasets, we use a user-based random data splitting method: 60\% of the interactions for each user are for training, 20\% for validation and 20\% for testing.

\subsection{Tuning}

MF and MLP have hyperparameters that need to be chosen. First, we set the user and item latent embeddings size $D$ to 128. Setting them to the same size gives a fair comparison. While it has been shown that both MF and MLP can benefit from even higher dimensions \cite{rendle2020neural}, $D=128$ gives us reasonable computational cost. Furthermore, to suppress the need to tune the number of training iterations, we employ early-stopping to end the learning phase when the MAP@5 (see Eq.\ \ref{eq:MAP}) on the validation set does not improve for three consecutive iterations.

We tuned our models using a Bayesian parameter search, assisted by Optuna \cite{optuna_2019}. We train each model 20 times by sampling the hyperparameters from the following:

\begin{itemize}
    \item For all models, learning rate is sampled from $[0.0001, 0.01]$ and $N$, the number of negative training instances per positive training instance, from $\{1, 2, ..., 20\}$.
    \item MF: The L2 penalty factor applied to the user and item factors was taken from $[10^{-6}, 10^{-4}]$.
    \item MLP: We use the same three-layer MLP as in \cite{he2017neural}. We also employ dropout on the training stage. The dropout rate is tuned in $[0, 0.2]$.
    \item BayesianMLP: We use a Bayesian MLP with the same architecture as our deterministic MLP. We use the same prior and tune the hyperparameters related to it across the exact same grid as used in \cite{blundell2015weight}. 
    \item Ensemble and sample sizes: We use $n=5$ in Eqs.\ \ref{eq:ensemble} -- \ref{eq:ensemble_unc}. We experimented with larger and smaller sample sizes, but found they all produced similar results.
\end{itemize}

\subsection{Evaluation}

To evaluate a model's recommendations, we obtain the top-$K$ recommendation list for each user, which we denote by $Z_u^K$. These are the $K$ candidate items that have highest predicted relevance score $r_{ui}$ for the user. Candidate items exclude those that the user has interacted with in the training and validation sets; candidates are therefore items that either the user has not interacted with or items that the user has interacted with but the user's interaction with the item is recorded in the test set. 

Let $\text{rel}_u$ be the items that $u$ has interacted with that are in the test set. Then, we evaluate a recommendation list according to its Mean Average Precision (MAP), averaged over all users: 

\begin{equation}
    \label{eq:MAP}
    \text{MAP@K} = \frac{1}{\#U} \sum_{u \in U} \sum_{j=1}^K \text{Precision@j}_u \times \delta\left(Z_u^K(j) \in \text{rel}_u\right)
\end{equation}
where
\begin{equation}
    \text{Precision@j}_u = \frac{\#\{Z_u^j \cap \text{rel}_u\}}{j}
\end{equation}
and where $\delta(Z_u^K(j) \in \text{rel}_u)=1$ if $Z_u^K(j)$, which is the $j$-th item in $Z_u^K$, is in $\text{rel}_u$ and $0$ otherwise.

\subsection{Results}
To answer \textbf{Q1} from Section \ref{sec:intro}, we compute the accuracy of the top-$K$ recommendations for different recommendation list sizes $K = 1, 2 \ldots, 10$. Figure \ref{fig:accuracy} shows the $MAP@K$ obtained in both datasets. Note that MF-NUS \& MF-NIS and MLP-NUS \& MLP-NIS are omitted because their MAP is the same as MF or MLP.

\begin{figure}[t]
    \centering
    \includegraphics[width=\linewidth]{img/AICS/accuracy.pdf}
    \caption{$MAP@K$ for $K = 1, 2 \ldots, 10$ for the Movielens (left) and Pinterest (right) datasets.}
    \label{fig:accuracy}
\end{figure}

The ensemble models, MF-ENSEMBLE and MLP-ENSEMBLE, show a remarkable MAP improvement over the baselines, MF and MLP. On the other hand, the BayesianMLP has similar performance to the deterministic MLP, and MCDropout has the worst performance on both datasets. Therefore, we found that some models that perform uncertainty estimation improve accuracy, others worsen it. Clearly, ensembling emerges as the most beneficial method with respect to accuracy.

To answer \textbf{Q2}, we analyze the accuracy of the models for users, grouped according to their average recommendation uncertainty. More precisely, we calculated the average uncertainty on each user's recommendation list, and split the users into 10 equal-sized uncertainty bins, where bin 1 will have the 10\% of users with the smallest average recommendation uncertainty and bin 10 will have those with the highest. Our intuition is that accuracy will fall as uncertainty grows. Figure \ref{fig:uncertainty} shows the results.

\begin{figure}[t]
    \centering
    \includegraphics[width=\linewidth]{img/AICS/MAP-Uncertainty.pdf}
    \caption{$MAP@10$ for users grouped according to the average uncertainty of their recommendation. The higher the bin index, the higher is uncertainty.}
    \label{fig:uncertainty}
\end{figure}

In line with our intuition, we see that MAP has a strong negative correlation with some of the uncertainty estimation methods. In particular, MF-Ensemble, MLP-Ensemble, MF-NUS and MLP-NUS appear to be those more strongly reflecting the expected behaviour. The results for $\usup$ show that mature users tend to get more accurate recommendations. In fact, $\usup$ has the strongest correlation to MAP in the Movielens dataset. On the other hand, in the Pinterest data, the MF-Ensemble is the one to achieve the strongest correlation. This, together with the earlier results in Figure \ref{fig:accuracy}, show that ensembling is not only a technique that can boost the accuracy of recommenders, but can also offer uncertainty estimates that correspond with the expected recommendation accuracy.

Other models to follow the expected behaviour are MCDropout in both datasets, and the BayesianMLP in the Pinterest dataset. Oddly, the BayesianMLP shows a growing MAP curve in the Movielens data, meaning that users with higher recommendation list uncertainties are getting higher accuracy, which is a result that needs further investigation. 

Models using $\isup$ do not show a very strong correlation between uncertainty and MAP with the exception of the last uncertainty bins in the Pinterest case. This too is a result that needs further investigation.

Largely, we believe that we have obtained a positive answer to \textbf{Q2}. For this research question, ensembling has, again, proven to be a great tool. Nevertheless, the simple and cheap $\usup$ metric can also provide good value with no computational cost added, in contexts where user-centric estimates suffice.

\section{Related Work}
\label{sec:related}

In this section, we briefly describe some related work %, to either acknowledging their contributions to implicit feedback RS uncertainty estimation in different setups to the one used throughout our work or to cite other relatable uncertainty estimation methods 
that could be further explored in RS research.

Bernardis et al.\ showed that there is a strong correlation between the eigenvalues of the item similarity matrix and the accuracy of item-based recommenders \cite{bernardis2019estimating}. Because of this, they propose an eigenvalue confidence index to measure the confidence level of the recommendations given to each user. Their method is suitable for both explicit and implicit recommendation tasks, and confidence can be thought of as the inverse of uncertainty. However, their method is applicable only to systems based on item similarity. Furthermore, like $\usup$, their confidence index is a user-centric measure, and therefore it lacks the granularity that is needed to differentiate the uncertainty of the individual items being recommended to a user.

Another method, which is superficially related to the ones employed herein but is actually quite different in its purpose, is the use of Gaussian embeddings for collaborative filtering. Gaussian embeddings are a generalisation of the embeddings used in many recommender algorithms. In \cite{dos2017gaussian}, Gaussian embeddings are learned by a matrix factorization algorithm; in \cite{jiang2020convolutional}, they are learned by a convolutional neural model. Gaussian embeddings give us non-deterministic user and item representations, capturing the uncertainty that there is in learning these representations. However, they do not quantify the uncertainty of item relevance to a user.

Neupane et al.\ \cite{neupane2021metaedl} propose a method for quantifying the amount of evidence available when providing recommendations to cold-start users. They propose a meta-evidential method for doing so. %Their method, not only predicts item relevance, it also assesses the amount of evidence available. 
We believe that, in future research, uncertainty could be inferred in a similar way. %Furthermore, due to the success of $\usup$ in our experiments, we can infer that cold-start users are those more negatively affected by uncertainty, and therefore, the systems could potentially benefit to some methods specifically tailored to this kind of user.

Finally, in the related field of Information Retrieval, Penha \& Hauff  explore uncertainty in neural learning-to-rank models \cite{penha2021calibration}. They obtain uncertainty estimates for a BERT ranker with the usage of Monte-Carlo Dropout and Deep-Ensembles, which we explained earlier. 
%Then, they explore whether exposing these estimates to users improves the intelligibility of the system's output. 
Their uncertainty-aware ranking method combines the predicted interaction relevance with their estimated uncertainties. They found that `shrinking' the relevance of interactions with high relevance can sometimes improve the system's recommendation accuracy. In a similar vein, but now using models based on Gaussian Processes, Guiver \& Snelson proposed to either shrink or increase the relevance of items based on their uncertainty to make the model more conservative or more risk-taking \cite{guiver2008learning}. However, their results are largely negative: they did not find this form of ranking to be more accurate. We leave the exploration of uncertainty-aware recommendation strategies similar to these for future research.

\section{Conclusion}
\label{sec:conclusion}

In this work, we explored methods for uncertainty estimation for implicit feedback recommender systems, exploring how the uncertainty estimates affect accuracy (\textbf{Q1}) and intelligibility regarding the recommender accuracy (\textbf{Q2}). Some of the methods had a positive impact on accuracy, others a negative impact. In particular, ensembling was the method showing the greatest accuracy improvements. Similarly, ensembling also was one of the top contenders when it came to correlation between accuracy and uncertainty, together with $\usup$, suggesting that these methods can help to identify which users are prone to receive the most or least accurate recommendations.

In addition, in the previous section, we highlighted some related work that can be useful for further exploration in the area. We hope that these, together with the promising results shown by our experiments will foment new research in this largely unexplored field.



