Preference learning

In label ranking, the model has an instance space ${\displaystyle X=\{x_{i}\}\,\!}$ and a finite set of labels ${\displaystyle Y=\{y_{i}|i=1,2,\cdots ,k\}\,\!}$. The preference information is given in the form ${\displaystyle y_{i}\succ _{x}y_{j}\,\!}$ indicating instance ${\displaystyle x\,\!}$ shows preference in ${\displaystyle y_{i}\,\!}$ rather than ${\displaystyle y_{j}\,\!}$. A set of preference information is used as training data in the model. The task of this model is to find a preference ranking among the labels for any instance.

It was observed some conventional classification problems can be generalized in the framework of label ranking problem:[5] if a training instance ${\displaystyle x\,\!}$ is labeled as class ${\displaystyle y_{i}\,\!}$, it implies that ${\displaystyle \forall j\neq i,y_{i}\succ _{x}y_{j}\,\!}$. In the multi-label case, ${\displaystyle x\,\!}$ is associated with a set of labels ${\displaystyle L\subseteq Y\,\!}$ and thus the model can extract a set of preference information ${\displaystyle \{y_{i}\succ _{x}y_{j}|y_{i}\in L,y_{j}\in Y\backslash L\}\,\!}$. Training a preference model on this preference information and the classification result of an instance is just the corresponding top ranking label.

Instance ranking also has the instance space ${\displaystyle X\,\!}$ and label set ${\displaystyle Y\,\!}$. In this task, labels are defined to have a fixed order ${\displaystyle y_{1}\succ y_{2}\succ \cdots \succ y_{k}\,\!}$ and each instance ${\displaystyle x_{l}\,\!}$ is associated with a label ${\displaystyle y_{l}\,\!}$. Giving a set of instances as training data, the goal of this task is to find the ranking order for a new set of instances.

Object ranking is similar to instance ranking except that no labels are associated with instances. Given a set of pairwise preference information in the form ${\displaystyle x_{i}\succ x_{j}\,\!}$ and the model should find out a ranking order among instances.

If we can find a mapping from data to real numbers, ranking the data can be solved by ranking the real numbers. This mapping is called utility function. For label ranking the mapping is a function ${\displaystyle f:X\times Y\rightarrow \mathbb {R} \,\!}$ such that ${\displaystyle y_{i}\succ _{x}y_{j}\Rightarrow f(x,y_{i})>f(x,y_{j})\,\!}$. For instance ranking and object ranking, the mapping is a function ${\displaystyle f:X\rightarrow \mathbb {R} \,\!}$.

Finding the utility function is a regression learning problem which is well developed in machine learning.

The binary representation of preference information is called preference relation. For each pair of alternatives (instances or labels), a binary predicate can be learned by conventional supervising learning approach. Fürnkranz and Hüllermeier proposed this approach in label ranking problem.[6] For object ranking, there is an early approach by Cohen et al.[7]

Using preference relations to predict the ranking will not be so intuitive. Since preference relation is not transitive, it implies that the solution of ranking satisfying those relations would sometimes be unreachable, or there could be more than one solution. A more common approach is to find a ranking solution which is maximally consistent with the preference relations. This approach is a natural extension of pairwise classification.[6]