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

<p><strong>The mapping:</strong> ranking one element at the top and the rest at the bottom.</p>

<p>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
$$</p>

<p><strong>Learning the mapping:</strong>
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}) &gt; f(x_i^{j}) 
$$</p>

<p>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$): </p>

<p>Here is a proposal: </p>

<ul>
<li><strong>Training</strong>: first, form the difference representations: </li>
</ul>

<p>$$
\forall j \neq y_i \Rightarrow z_i^j \triangleq x_i^{y_i} - x_i^j
$$</p>

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

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

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

<p>Please let me know if you have thoughts supporting/contradicting this proposal</p>

CC BY-SA 4.0
2018-08-02T16:35:30.090Z
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.
CC BY-SA 4.0
2018-08-02T16:47:25.247Z
Thanks for sharing your thoughts. I updated the question to clarify the input-output mapping.
Daniel
CC BY-SA 4.0
2018-08-02T16:48:42.013Z
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
CC BY-SA 4.0
2018-08-02T18:59:32.867Z
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.
CC BY-SA 4.0
2018-08-02T18:59:35.410Z
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.
<machine-learning>
Ranking problem (single instance before others)
Daniel
# Ranking problem (single instance before others)

(Asked by: username_0 on 2018-08-02)

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)
  $$

Please let me know if you have thoughts supporting/contradicting this proposal

**Tags:** machine-learning

> **Comments:**
> **username_1**: 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).  
> **username_0**: Thanks for sharing your thoughts. I updated the question to clarify the input-output mapping.  
> **username_0**: 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).  
> **username_1**: 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)  
> **username_1**: 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.  

---

## 0 answers

