# Ranking problem (single instance before others)

Suppose I am trying to learn function $f$ for a ranking-like objective:

The mapping: ranking one element at the top and the rest at the bottom.

More formally, suppose each input instance $I_i$ contains some items: $$I_i = \{ 1, 2, \cdots, k\}$$ The output of each instance is the variable $y_i$ ($y_i \in \{ 1, 2, \cdots, k \}$) is an index in the instance. So the input-output mapping is: $$I_i \rightarrow y_i$$

Learning the mapping: Suppose we want to learn this mapping. For each index $j$ in $I_i$, we extract a feature vector $x_i^j$. So we will have a collection of vectors $x_i^1, ...., x_i^k$. The learning problem can be formulated as following: $$\forall j\neq y_i \Rightarrow f(x_i^{y_i}) > f(x_i^{j})$$

Now the question is, whether it is possible to reduce this problem to the existing well-known problems (e.g. linear classifiers $f(x) = w^T x$):

Here is a proposal:

• Training: first, form the difference representations:

$$\forall j \neq y_i \Rightarrow z_i^j \triangleq x_i^{y_i} - x_i^j$$

I argue that we can use traditional linear-classifier frameworks to learn mappings from $z_i^j \rightarrow +1$:

$$\max_f \sum_{I_i} \sum_{j \in I_i} \ell ( f(z_i^j), +1)$$

• Prediction: given an instance $I_i$, select the best scoring index: $$\hat{y}_i = \arg\max_{j \in I_i} f(x^j_i)$$

• What is the problem that you want to reduce? I presume the $y_i$'s are the inputs; what are the desired outputs? The $x$'s? If so, the problem seems trivial: it seems like you can choose each $x_i$ separately, say by setting $x_i=(0,0,\dots,0,1,0,\dots,0)$ with a $1$ in the $y_i$'th position. Am I misunderstanding something? As always, when there is an efficient solution, there is an efficient reduction (the reduction first solves the problem, then maps to a trivial instance that has the desired solution). – D.W. Aug 2 '18 at 16:35
• Re. the selection of $x$: you're right. But I am assumign that $x$ vectors (i.e. my feature vectors) are given to me (and not selected by me). The only thing that I get to pick is the design of the function $f(.)$ (or its weight vector). – Daniel Aug 2 '18 at 16:48
• I see. Do you require the function $f$ to come from a particular function class? If not, what prevents me from just choosing a truth table for it in a way that trivially makes all the inequalities true? i.e., set $f(x_i^{y_i})=1$ for all $i$, and set $f(x_i^j)=0$ for all $i,j$ such that $j \ne y_i$. Or, use linear programming (treating each entry in the truth table for $f$ as a variable) to find a truth table that satisfies all the inequalities. (continued) – D.W. Aug 2 '18 at 18:59
• It still seems like there is an efficient polynomial-time algorithm to find $f$; so it trivially follows that there will be an efficient polynomial-time algorithm to reduce to anything else you want. – D.W. Aug 2 '18 at 18:59