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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.