
%---------------------------------------PROBLEM FORMALIZATION-----------------------------------------------
\vspace{-0.1cm}

\section{Problem Formalization in the Stream Setting }
\label{sec:problemformalization}

\vspace{-0.2cm}

The main differences between the batch and the stream settings as far as  the contextual preference mining problem is concerned  may be summarized as follows:
\vspace{-0.2cm}
\begin{itemize}
\item \textit{Input data}: to each sample bituple $(u,v)$ collected from the stream of clicks from a user on a site, is associated a timestamp $t$ standing for the time the user made this implicit choice. In this case, consider for example that the object represented by the tuple $u$ was clicked first that the object represented by $v$ (which may suggest that $u$ is preferred to $v$), or even the object represented by $v$ has not been clicked by the user. Let $T$ be the infinite set of all timestamps. So, the input data from which a preference model will be extracted is a  \textit{preference stream} defined as a possibly infinite set $P \subseteq Tup(R) \times Tup(R) \times T$ which is \textit{temporally consistent}, that is, if $(u,v,t) \in P$ then $(v,u,t) \notin P$. The triple $(u,v,t)$ that we will call \textit{temporal bituple}, represents the fact that the user prefers tuple $u$ over tuple $v$ at the time instant $t$.

\item \textit{Output}: the preference model to be extracted from the preference stream is a \textit{temporal BPN}, that is,  a sequence of BPNs $< PNet_t : t \in \mathbb{N} > $. At each instant $t$ the algorithm is ready to produce a preference model $PNet_t$ which will be used to predict the user preferences at this moment.
    %Notice that for the BPN $PNet_t$ at instant $t$, the preference order $>$ appearing in its probability table is indexed by $t$. For instance, let us suppose that $PNet_t$ is the BPN depicted in Figure \ref{fig:subfigureExample}(c). Then the conditional probability associated to attribute B is: $P[b_1 >_t b_2 | C = c_1] = 0.6]$.

    \item \textit{The preference order induced by a BPN at each instant $t$}: At each instant $t$ we are able to compare tuples $u$ and $v$ by employing the Preference Model $PNet_t$ updated with the elements of the preference stream until the instant $t$. The preference order between $u$ and $v$ is denoted by $>_t$ and is obtained as illustrated in example \ref{exorder}.

    \item \textit{The accuracy and comparability rate at instant $t$}: The quality of the preference model $PNet_t$ returned by the algorithm
     at instant $t$ is measured by considering a finite set $Test$ of preference samples arriving at the system after instant
       $t$,  that is, by considering  a finite set $Test$ whose elements are of the form $(u,v,t')$ with $t' \geq t$. Let
       $\cal P$ be the (non temporal) preference database obtained from $Test$ by removing the timestamp $t'$ from its
        elements. The \textit{acc} and \textit{CR} measures of the preference model
   $PNet_t$ obtained at instant $t$ are evaluated according to the formulae given in the previous section applied to the (static) BPN $PNet_t$ and the non temporal preference database $\cal P$.

\end{itemize}
\vspace{-0.2cm}

 Fig. \ref{fig:testtraining} illustrates the dynamic process of mining and testing  the preference models from the preference stream.
%
\begin{figure}[t]
	\centering
		\includegraphics{figures/training-test.eps}
\vspace*{-1cm}
	\caption{The dynamics of the mining and testing processes through time}
	\label{fig:testtraining}
\end{figure}
%
In fact, as we will see in the following section, the mining algorithm is able to produce the preference model by using a reduced set of \textit{statistics} extracted from the training sets $T_i$.% at the instant $t$ it is requested to act.
%The entire sets $T_i$ of the preference samples stream are not needed in the mining process.
%The statistics used at instant $t_3$ in order to infer the preference model at this instant is obtained by incrementing the statistics at instant $t_1$ with the statistics extracted from the  preference samples arrived between $t_2$ and $t_3$. We suppose that the preference samples arrived between $t_1$ and $t_2$ are used only for testing the preference model $PNet_1$ and not for training the preference model $PNet_2$.

Now we are ready to state the problem of Mining Contextual Preferences in a Preference Stream:

\vspace{-0.1cm}
\textit{Input}: a relational schema $R(A_1,A_2,...,A_n)$, and a preference stream over $R$.

\vspace{-0.2cm}
\textit{Output}: whenever requested, return a $BPN_t$ over $R$ having good accuracy and comparability rate, where $t$ is the time instant of the request.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
