\vspace{-0.2cm}
\section{Background}
\label{sec:background}

In this section we briefly introduce the problem of mining contextual preferences in a batch setting. Please see \cite{ictai2012} for more details on this problem.
%In the next section, all the concepts introduced here are naturally generalized to the stream setting, by simply aggregating the time dimension.

\vspace{-0.2cm}
A \textit{preference relation} on a finite set of objects  $A = \{a_1, a_2,...,a_n\}$ is a strict partial order over $A$, that is a binary relation $R \subseteq A \times A$ satisfying the irreflexivity and transitivity properties. Typically, a strict partial order is represented by the symbol $>$. So if $>$ is a preference relation, we denote by  $a_1 > a_2 $ the fact that $a_1$ is preferred to $a_2$.

%\vspace{-0.2cm}
%\begin{definition}[Preference Database] \label{defi:amostrasDePreferencia}
\textit{Definition} 2.1 \textit{Preference Database}.
 \rm Let $R(A_1,A_2,...,A_n)$ be a relational schema. Let Tup($R$) be the set of all tuples over $R$. A \textit{preference database}  over $R$ is a finite set $\cal P$ $\subseteq$ Tup($R$) $\times$ Tup($R$)  which is \textit{consistent}, that is, if $(u,v) \in $ $\cal P$ then $(v,u) \not \in $ $\cal P$. The pair $(u,v)$, usually called \textit{bituple}, represents the fact that the user prefers \textit{the tuple $u$ to the tuple $v$}.
%\end{definition}

\vspace{-0.3cm}

\begin{example}
\label{ex:amostrasDePreferencias}
\rm Let $R(A,B,C,D)$ be a relational schema with  attribute domains given by \textbf{dom}$(A)$ = $\{a_1,a_2,a_3\}$, \textbf{dom}$(B) = \{b_1,b_2\}$, \textbf{dom}$(C)=\{c_1,c_2\}$ and \textbf{dom}$(D)=\{d_1,d_2\}$. Let $I$ be an instance over  $R$ as shown in Fig. \ref{fig:subfigureExample}(a). Fig. \ref{fig:subfigureExample} (b) illustrates a preference database over $R$, representing a sample provided by the user about his/her preferences over  tuples of $I$.
\end{example}

\vspace{-0.2cm}

\begin{figure}[b]
\centering
\begin{tabular}{ccc}
\begin{minipage}[t]{3.7cm}
{\begin{tabular}{|c|c|c|c|c|}
  \hline
  Id & A & B & C & D\\
  \hline
  $t_1$ & $a_1$ & $b_1$ & $c_1$ & $d_1$\\
  $t_2$ & $a_1$ & $b_1$ & $c_1$ & $d_2$\\
  $t_3$ & $a_2$ & $b_1$ & $c_1$ & $d_2$\\
  $t_4$ & $a_1$ & $b_2$ & $c_1$ & $d_2$\\
  $t_5$ & $a_2$ & $b_1$ & $c_2$ & $d_1$\\
  $t_6$ & $a_3$ & $b_1$ & $c_1$ & $d_1$\\
  \hline
  \end{tabular}\\
 \ \\
\hspace*{1.5cm}{\footnotesize (a)}
}
\end{minipage} &
\begin{minipage}[t]{1.5cm}
{\begin{tabular}{|c|}
  \hline
  ($t_1$,$t_2$)\\
  ($t_1$,$t_3$)\\
   ($t_4$,$t_5$)\\
  ($t_4$,$t_2$)\\
   ($t_5$,$t_6$)\\
  ($t_3$,$t_5$)\\
 ($t_4$,$t_1$)\\
  \hline
  \end{tabular}\\
 \ \\
\hspace*{0.5cm}{\footnotesize (b)}
}
\end{minipage}
&
\begin{minipage}{7cm}
{\includegraphics[width=7cm]{figures/redePreferencias.eps}\\
\vspace{0.3cm}
\hspace*{3cm} {\footnotesize(c)}}
\end{minipage}
\end{tabular}
\vspace*{-0.3cm}
\caption{\footnotesize (a) An instance $I$, (b) A Preference Database $\cal P$, (c) Preference Network \textbf{PNet}$_1$}
\label{fig:subfigureExample}
\end{figure}

The problem of mining contextual preferences in the batch setting consists in extracting a \textit{preference model} from a preference database provided by the user. The  preference model is specified by a \textit{Bayesian Preference Network} defined next.

%\vspace{-0.2cm}

%\begin{definition}[Bayesian Preference Network (BPN)] 
\textit{Definition} 2.2 \textit{Bayesian Preference Network (BPN)}.
\rm A \textit{Bayesian Preference Network} (or BPN for short) over a relational schema $R(A_1,...,A_n)$ is a pair $(G,\theta)$ where: (1) $G$ is a directed acyclic graph whose nodes are attributes in
   $\{A_1,...,A_n\}$ and the edges stand for attribute dependency; (2) $\theta$  is a mapping that associates to each node of  $G$ a \textit{conditional probability table of preferences}, that is,  a finite set of conditional probabilities of the form  $P[E_2|E_1]$ where: (1) $E_1$ is an event expressed by the formula $(A_{i_1}=a_{i_1}) \wedge \ldots \wedge (A_{i_k}=a_{i_k})$ such that $\forall j \in \{1,...,k\}$, $a_{i_j} \in$ \textbf{dom}$(A_{i_j})$, and (2) $E_2$ is an event of the form ``$(B= b_1$) is preferred to   ($B=b_2)$'', where  $B$ is an attribute of $R$, $B\not=A_{i_j}$ $\forall j \in \{1,...,k\}$ and $b_1,b_2$ $\in$ \textbf{dom}$(B)$, $b_1 \not = b_2$.
%\end{definition}

\vspace{-0.3cm}

\begin{example}[BPN]\rm Let $R(A,B,C,D)$ be the relational schema of the Example \ref{ex:amostrasDePreferencias}. Fig. \ref{fig:subfigureExample}(c) illustrates a preference network \textbf{PNet}$_1$ over $R$.
\end{example}

\vspace{-0.2cm}

Each conditional probability $P[E_2|E_1]$ in a BPN table stands for a \textit{probabilistic} cp-rule, where the condition event $E_1$ is the \textit{context} and the  event $E_2$ is the \textit{preference}. %A probabilistic cp-rule associated to a node $X$ in the graph $G$ represents a degree of belief of preferring  some values for $X$ to other ones, depending on the values assumed by its parents in the graph.  
For instance $P[D=d_1 > D=d_2|C=c_1] = 0.6$  means that  the probability of $D=d_1$ be preferred to $D=d_2$ is $60\%$ given that $C= c_1$.

\vspace{-0.2cm}

%In classification tasks,  Bayesian Networks are used as a tool to classify tuples. In our preference mining scenario, BPNs  are used to compare pairs of tuples.
Before defining the accuracy, comparability rate and precision of a preference network, we  need to define the  \textit{strict partial order}  inferred by the preference network.
%For lack of space, we do not provide the rigorous definition of the order here, but only describe it by means of an example. For more details see \cite{manuscript}.


\vspace{-0.2cm}

\begin{example}[Preference Order]
\rm
\label{exorder}
Let us consider the BPN \textbf{PNet}$_1$ depicted in Fig. \ref{fig:subfigureExample}(c). This BPN allows to infer a preference ordering on tuples over $R(A,B,C,D)$.   According to this ordering, tuple $u_1 = (a_1,b_1,$\textbf{$c_1$},$d_1)$ is preferred to tuple  $u_2 = (a_2,b_2,$\textbf{$c_1$},$d_2)$. In order to conclude  that, we execute the following steps: (1) Let $\Delta(u_1,u_2)$ be the set of attributes where the $u_1$ and $u_2$ differ. In this example, $\Delta(u_1,u_2)$ = \{$A,B,D$\}; (2) Let min($\Delta(u_1,u_2)$) $\subseteq$ $\Delta(u_1,u_2)$ such that the attributes in min($\Delta$)  have no ancestors in $\Delta$ (according to graph $G$ underlying the BPN \textbf{PNet}$_1$). In this example min($\Delta(u_1,u_2)$) = \{$D$,$B$\}. In order to $u_1$ be preferred to $u_2$ it is necessary and sufficient that $u_1[D] > u_2[D]$ and $u_1[B] > u_2[B]$; (3) Compute the following probabilities:
 $p_1$ = probability that $u_1 > u_2$ = $P[d_1 > d_2|C = c_1]*P[b_1 > b_2|C = c_1]$ = 0.6 * 0.6 = 0.36; $p_2$ = probability that $u_2 > u_1$ = $P[d_2 > d_1|C = c_1]*P[b_2 > b_1|C = c_1]$ = 0.4 * 0.4 = 0.16. In order to compare $u_1$ and $u_2$ we select the higher between $p_1$ and $p_2$. In this example, $p_1 > p_2$ and so, we infer that $u_1$ is preferred to $u_2$. If $p_1 = p_2$ we conclude that $u_1$ and $u_2$ are incomparable.
\end{example}

\vspace{-0.2cm}

%\begin{definition}[Accuracy, Comparability Rate and Precision]
\textit{Definition} 2.3 \textit{Accuracy, Comparability Rate and Precision}.
%\label{precision-recall}
\rm Let \textbf{PNet} be a BPN over a relational schema $R$. Let  $\cal P$ be a \textit{test} preference database over $R$. The \textit{accuracy (acc)} of the \textbf{PNet}  with respect to $\cal P$ is defined by \mbox{acc(\textbf{PNet},$\cal P$)}= $\frac{N}{M}$, where $M$ is the number of bituples in  $\cal P$ and $N$ is the amount of bituples $(t_1,t_2)$ $\in$ $\cal P$ compatible with the preference ordering inferred by the \textbf{PNet} on the tuples $t_1$ and $t_2$. The \textit{comparability rate (CR)} is defined by \mbox{CR(\textbf{PNet},$\cal P$)}= $\frac{F}{M}$ where $F$ is the number of elements of $\cal P$ which are comparable by the \textbf{PNet}.
The  \textit{precision (prec)} is defined by   \mbox{prec(\textbf{PNet},$\cal P$)}= $\frac{acc}{CR}$ = $\frac{N}{F}$. Notice that each one of the three measures can be derived from the two others.
%\end{definition}


%\noindent \textbf{Parameters for calibrating the inferred order by taking into account the user \textit{undecidability} and \textit{inconsistency}}. Notice that in order to compare two tuples $u_1$ and $u_2$ according to the order described in Example \ref{exorder}, we simply ignore the probability $p_2$ which in some sort measures the user undecidability concerning his/her preferences over these tuples. Notice also that in order to infer a preference we simply consider the higher value between $p_1$ and $p_3$. The proximity of  $p_1$ and $p_3$ measures in some sort the user \textit{inconsistency} concerning his/her preferences over these tuples.  We could be more precise when defining the preference ordering induced by a BPN by considering  parameters $k_1$ and $k_2$ for calibrating respectively the user undecidability and inconsistency factors. That is: we say that $u_1$ is preferred to $u_2$ if the following conditions are verified: (1) $p_2 \leq k_1$ and (2) $p_1 \geq k_2(1-p_2)$. The first condition (resp. the second condition) controls how the user undecidability (resp. inconsistency) is taken into account in the inferred ordering. As $k_1$ increases (resp. as $k_2$ decreases)  user undecidability (resp. inconsistency)  importance decreases for deciding the preference ordering. The ordering considered in Example \ref{exorder} corresponds to  $k_1 = 1$ and $k_2 = 0$.



%The  problem of mining contextual preferences in the batch setting is the following:  Given a training preference database $T_1$ over a relational schema $R$ and a testing  preference database $T_2$ over $R$, find a BPN over $R$ having good precision and recall with respect to $T_2$.



