\chapter{Learning and Evaluating Uncertainty in Implicit Feedback Recommender Systems}
\label{chater:implicit_learn}

In the previous chapter, we explored methods for uncertainty estimation in implicit feedback systems. All of the methods explored in there refrain from learning direct uncertainty representations. Instead, they focus on uncertainty signals incoming from either the data ($\usup$ and $\isup$), or from the relevance estimator, weather it is from the relevance output (Ensembles or MCDropout), or from the learned parameters (BayesianMLP).

Furthermore, in the case of explicit feedback models (Chapter \ref{chater:explicit}), we explored methods to explicitly represent uncertainty (see Section \ref{sec:distribution_based}). In particular, CPMF (\ref{eq:cpmf}) has been shown as one of the most promising uncertainty estimators in that case.

Therefore, this chapter will discuss methods to learn uncertainty representations based on implicit feedback data. In the next section we define the class of models to be considered. Then we describe \acrshort{aur} (\acrlong{aur}) \cite{wang2022rethinking}, which is to our concerns the only literature method to fit this class. Lastly, we propose two new general learning procedures that allow uncertainty representations to be learned, namely \acrlong{gbr} (\acrlong{gbr}) and \acrshort{gpr} (\acrlong{gpr}).

\section{Setup}
In this chapter, we explore gaussian methods, in which the relevance of a user-item interaction is modeled as $r_{ui} \sim \norm (\mu_{ui}, \sigma^2_{ui})$. In such case, $\mu_{ui}$ denotes the expected relevance of the interaction, and $\sigma^2_{ui}$ the uncertainty associated with it. The models' task is to predict these gaussian parameters for unseen user-item interaction.

Much likely to the previous section. Our dataset consists of a set of observed interactions $\mathcal{D^+}$ and a set of unobserved interactions $\mathcal{D^-}$. The observed ones are assumed to be relevant items to the user, while the unobserved are initially treated as irrelevant items. Therefore, the recommendation task consists in, for each user, finding which of the interactions in $D^-$ are more likely to be actually relevant ones.

The gaussian recommenders in this chapter will following the form,

\begin{align}
    \mu_{ui} &= F_\theta(u, i) \\
    \sigma^2_{ui} &= \exp \left( G_\gamma(u, i) \right)
\end{align}

Therefore, we need to learn two functions. First, the expectancy predictor $F$, parameterized by $\theta$ to predict the distribution's average for each interaction. And secondly, the variance predictor $G$, parameterized by $\gamma$ to predict the interaction variances. The exponential of $G$ is taken to ensure positive variances.

For now, we will assume that $F$ and $G$ are latent factor models, likewise Equation \ref{eq:mf2}. Nevertheless, this is only one of the many possible choices to model both the expectancy and uncertainty predictors. Now, to complete the framework, we need an algorithm that allow $F$ and $G$ to be learned from implicit signals. As follows, we describe three methods for this task: \acrshort{aur}, \acrshort{gbr} and \acrshort{gpr}.

\section{\acrlong{aur}}
The \acrshort{aur} method gives a numeric formulation to the implicit feedback problem. First, let $Y_{ui} = 1$ if user $u$ has interacted with item $i$ and $Y_{ui} = 0$ otherwise. In other words, the observed relevance of the interaction is set to the numeric value of 1 (0) if the interaction is observed (not observed). In this case, the likelihood of the model is given by,

\begin{equation}
\label{eq:likelihood_imp}
    \prob(R) = \prod_{u \in U} \prod_{i \in I} N(Y_{ui}|\mu_{ui}, \sigma_{ui}) = \prod_{u \in U} \prod_{i \in I} \frac{1}{\sigma_{ui}\sqrt{2\pi}} \exp \left[ - \frac{(\mu_{ui} - Y_{ui})^2}{2\sigma_{ui}^2} \right]
\end{equation}

Learning is then performed by maximising the log-likelihood through mini-batch gradient descent. Nevertheless, there are in practice much more unobserved interactions then observed ones. Therefore, to maintain balance and speed up training, only a fraction (randomly sampled) of the negative interactions for each user is used on each epoch. In our work, we will employ the same sampling criteria from Section \ref{sec:setup}. That is, N negative interactions from $D^-$ will be sampled for each positive from $D^+$.

\section{\acrlong{gbr}}
A standard principle to learn implicit feedback \acrshort{rs} is to predict the probability for each interaction to be relevant, likewise Section \ref{sec:setup}. In this case, loss functions such as binary cross-entropy are used. Following on this, \acrshort{gbr} offers a method to estimate probabilities of relevance and the uncertainties associated to them. The probability for the user $u$ to interact with item $i$ is modeled as,

\begin{equation}
    \prob (Y_{ui} = 1) = \prob (r_{ui} > 0) = \prob (\norm (\mu_{ui}, \sigma^2_{ui}) > 0) = 1 - \Phi \left( \frac{-\mu_{ui}}{\sqrt{\sigma^2_{ui}}}\right) 
\end{equation}

\noindent Where $\Phi$ is the standard gaussian distribution cumulative distribution function. Naturally, the probability for a pair to be unobserved is,

\begin{equation}
    \prob (Y_{ui} = 0) = \prob (r_{ui} \leq 0) = \Phi \left( \frac{-\mu_{ui}}{\sqrt{\sigma^2_{ui}}}\right) 
\end{equation}


Therefore, the likelihood of the training data is given by,

\begin{equation}
\label{eq:likelihood_gbr}
    \prob(R) = \prod_{u \in U} \prod_{i \in I} \prob(Y_{ui} = 1)^{\delta_{ui}} \prob(Y_{ui} = 0)^{1 - \delta_{ui}}
\end{equation}

\noindent Where $\delta_{ui} = 1$ if u has interacted with i and $0$ otherwise. Notice that, although we employ the notation $Y_{ui} = 1$ and $Y_{ui} = 0$, this values are only labels indicating weather or not the user-item interaction were observed and not numeric values as in the case of \acrshort{aur}. We believe that \acrshort{gbr} follows a probabilistic formulation that better represents the binary nature of the implicit feedback data, e.g. click/not-click, watch/not-watch, etc. The learning follows the same as the previous: mini-batch gradient descent with negative interaction sampling.

\section{\acrlong{gpr}}
Another compelling objective used to learn implicit \acrshort{rs} is \acrshort{bpr}. This method is based on the principle that the observed interaction should always have a higher relevance than unobserved ones. Such principle is applied on a pairwise fashion, that is, considering two interactions (one observed, and one unobserved) at a time. Let $r_{ui}$ denote the relevance of item $i$ to user $u$. Then, $r_{uij} = r_{ui} - r_{uj}$ models how much user $u$ prefers item i over j.  Given a user $u$ and a pair of items $(i, j)$, the probability that the user $u$ will prefer item $i$ over $j$ can be modeled as

\begin{equation}
    P(i >_u j) = S(r_{uij})
\end{equation}

\noindent
where $S$ denotes the sigmoid function is is meant to constraint the probability to the $[0, 1]$ interval.

\acrshort{gbr} is a generalization of \acrshort{bpr} that allows uncertainty estimates to be learned on the same pairwise ranking principle introduced by \acrshort{bpr}. Again, we let $r_{ui} \sim \norm (\mu_{ui}, \sigma^2_{ui})$. Then, we model the pairwise preferences as,

\begin{equation}
    P(i >_u j) = P(r_{uij} > 0) = P(r_{uji} \leq 0)
\end{equation}

Now, because $r_{uji}$ is also normally distributed, we can explicitly calculate this probability,

\begin{align}
    P(r_{uji} \leq 0) &= P\left(\frac{r_{uji} - (\mu_{uj} - \mu_{ui})}{\sqrt{\sigma^2_{uj} + \sigma^2_{ui}}} \leq \frac{- (\mu_{uj} - \mu_{ui})}{\sqrt{\sigma^2_{uj} + \sigma^2_{ui}}} \right) \\ 
    &= \Phi \left( \frac{\mu_{ui} - \mu_{uj}}{\sqrt{\sigma^2_{uj} + \sigma^2_{ui}}}\right)
\end{align}

Where $\Phi$ is the standard gaussian distribution cumulative distribution function. Therefore, the likelihood of the training data (the known pairwise preferences) is given by,

\begin{equation}
\label{eq:likelihood_gpr}
    \prob(R) = \prod_{u \in U} \prod_{i \in I_u^+} \prod_{i \in I_u^-} \Phi \left( \frac{\mu_{ui} - \mu_{uj}}{\sqrt{\sigma^2_{uj} + \sigma^2_{ui}}}\right)
\end{equation}

Where $I_u^+ = \{i \in I | (u, i) \in D^+\}$ and $I_u^- = \{i \in I | (u, i) \in D^-\}$. For BPR, it was shown that optimizing the full likelihood is very slow \cite{rendle2009bpr}. Instead, a better approach is to sample positive-negative interaction pairs randomly among the known preferences and perform stochastic gradient updates. We follow the same principle with \acrshort{gpr}.

\section{Learning}
The three methods defined above provide general objective functions that allow models $F$ and $G$ to be learned. Nevertheless, we highlight the correlation between $\mu_{ui}$ and $\sigma^2_{ui}$ in every case: The higher the training error on learning an interaction relevance, the larger the uncertainty will be. In other words, increasing uncertainty may be a shortcut to account for a poor relevance fit. For this reason, learning $F$ and $G$ simultaneously may lead to to an inability learn the best relevance estimator.

For this reason, it was proposed by \cite{wang2022rethinking} to learn $F$ and $G$ sequentially. First, all the variances are fixed, assuming $\sigma^2 = 1$ for every interaction, to learn the expectancy estimator. Then, the learnt expectancy parameters are fixed and the variance ones are optimized. In their work, it was shown that this sequential training algorithm is superior than the jointly learning version in many cases, but not always. For that reason, we will experiment with both methods. We will denote the methods employing the joint and sequential learning with the suffixes J and S, respectively. 

\section{Recommending under uncertainty}

In Section \ref{sec:top_n_recommendation}, we described the traditional way that top-$n$ recommendations are given and also how uncertainty estimates can improve on it. Similarly, in the case of implicit feedback systems, recommendations are also conventionally given by ranking the candidate items according to their expected rating. Now, new methods of providing recommendations can also be derived given the availability of uncertainty estimates in the implicit case.

The AUR method proposes to score and rank the candidate items according too the rule,

\begin{equation}
    s_{ui} = \lambda \mu_{ui} + (1 - \lambda) \sigma_{ui}
\end{equation}

\noindent Where $\lambda$ is a hyper-parameter. At first, it might seems implausible that the model reward items with high estimate uncertainty. The reasoning behind this is that the candidate items are usually those labeled as unobserved interactions in the training data. This unobserved interactions are treated as $Y_{ui} = 0$ at training time. Therefore, having a high uncertainty means that the model found the training label to be questionable, and therefore, suggests that the interaction is likely to be observed in the future.

With our probabilistic methods, \acrshort{gbr} and \acrshort{gpr}, we can rank based on the probabilities of relevance, that is,

\begin{equation}
    s_{ui} = P(Y_{ui} = 1)
\end{equation}

We will refer to these as Uncertainty-Aware (UA) ranking.

\subsection{Results}

\victor{There is a lot to fix here. For now, models indexed by "-J" means learnt jointly, and with no index means sequential learning.}

\subsubsection{Movielens 1M}

\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{img/temp/accuracy_ML.pdf}
    \caption{Movielens accuracy}
\end{figure}

\begin{table}[]
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
 & MAP & UA MAP & MAP-Improvement & Recall & UA Recall & Recall-Improvement \\ \hline
AUR-S  & 0.518 & 0.522  & 0.738\%  & 0.158  & 0.160     & 0.828\%  \\ \hline
GBR-S  & 0.519 & 0.470  & -9.424\%  & 0.152  & 0.144     & -5.478\% \\ \hline
GPR-S  & 0.492 & 0.470  & -9.424\%  & 0.152  & 0.144     & -5.478\% \\ \hline
AUR-J  & 0.492 & 0.455  & -7.557\%  & 0.140  & 0.132     & -5.549\% \\ \hline
GBR-J & 0.462 & 0.480  & 3.924\%   & 0.133  & 0.139     & 4.47\%   \\ \hline
GPR-J  & 0.420 & 0.375  & -10.859\% & 0.094  & 0.078     & -17.5\%  \\ \hline
\caption{\victor{Maybe show only the improvement?}}
\end{tabular}
\end{table}

\subsubsection{Pinterest}
TBD

% \begin{figure}
%     \centering
%     \includegraphics[width=\linewidth]{img/temp/accuracy_P.pdf}
%     \caption{Pinterest accuracy}
% \end{figure}

% \begin{figure}
%     \centering
%     \includegraphics[width=\linewidth]{img/temp/corr_P.pdf}
%     \caption{Pinterest correlations}
% \end{figure}


% \begin{table}[]
% \begin{tabular}{|l|l|l|l|l|l|l|}
% \hline
%           & MAP   & UA MAP & MAP-Improvement & Recall & UA Recall & Recall-Improvement \\ \hline
% AUR       & 0.124 & 0.124  & -0.015\%        & 0.082  & 0.082     & -0.112\%           \\ \hline
% Pointwise & 0.121 & 0.121  & 0.235\%         & 0.083  & 0.082     & -0.326\%           \\ \hline
% Pairwise  & 0.105 & 0.095  & -8.938\%        & 0.069  & 0.064     & -7.679\%           \\ \hline
% \end{tabular}
% \end{table}
