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

  • $\begingroup$ 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). $\endgroup$ – D.W. Aug 2 '18 at 16:35
  • $\begingroup$ Thanks for sharing your thoughts. I updated the question to clarify the input-output mapping. $\endgroup$ – Daniel Aug 2 '18 at 16:47
  • $\begingroup$ 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). $\endgroup$ – Daniel Aug 2 '18 at 16:48
  • 1
    $\begingroup$ 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) $\endgroup$ – D.W. Aug 2 '18 at 18:59
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Aug 2 '18 at 18:59

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.