2
$\begingroup$

Let $V$ be an $n$ dimensional space with sets of positive class vectors $P$ and negative class vectors $N$. The task is to find a vector $x$ such that AUC is maximized, based on ranking generated by computing distances between $x$ and $P,V$. So in a sense, $x$ is closer to $P$ than to $V$. It looks like this doesn’t have a unique solution, but I’m curious if there is a really easy explicit solution to this, or a short algorithm? Or is this NP-hard?

Surely this is a well known classical problem? One algorithm that I think works is to sample triplets $(x,p,n)$ with one positive and one negative vector and then formulate the usual triplet loss:

$$L(x,p,n) = \max(0,\|x-p\|^2-\|x-n\|^2+\epsilon),$$

which pushes $x$ closer to $p$ and further from $n$. I’m just hoping for something easier.

Improve this question
$\endgroup$
5
  • $\begingroup$ What does it mean that a vector $x$ is closer to set of vectors $P$ than to a space $V$? $\endgroup$
    – Jan Kukacka
    Sep 27, 2018 at 7:40
  • $\begingroup$ Interesting problem. If you constraint the problem where $x$ is in $P$ or $N$, its obviously not NP-hard, and I think somewhat efficient solutions can be derived. In general case, you can consider only regions separated by hyperplanes $h_{n, p}(x)$ corresponding to $||x - p||_2 = ||x - n||_2$ for all $n, p$ in $N, P$, though I recall there are $O(m^n)$ of them, where $m = |P \cup N|$ $\endgroup$
    – Łukasz Grad
    Sep 27, 2018 at 7:44
  • $\begingroup$ @Jan Kukacka: oh, I just meant it in terms of the probabilistic definition of AUC, i.e. the probability a positive sample ranks above (is closer to $x$) than a negative sample $\endgroup$
    – Alex R.
    Sep 27, 2018 at 17:58
  • $\begingroup$ I dont we why placing $x$ on the mean of P is not one of the correct solutions - that is the placement of $x$ with the least average distant to $p \in P$ and likelly the distance to $n \in N$ will be on average larger. $\endgroup$
    – Jacques Wainer
    Oct 3, 2018 at 12:15
  • $\begingroup$ @JacquesWainer: That's not true, as being closer to $P$ is not enough. As an adhoc example, in 2-D, suppose the points P fall on the edge of a circle of radius 2 and points N fall on a circle of radius 1. Placing $x$ at the mean of P, the origin, would give you worse than random AUC, as every point of N would be closer to x than any point of P. In that case, you could place x anywhere outside the circle of radius 2 and do way better. This might not be the best example as one could argue that you just need to flip your predictions, but, I'm sticking to the original formulation of the problem. $\endgroup$
    – Alex R.
    Oct 3, 2018 at 19:13

1 Answer 1

Reset to default
-3
$\begingroup$

Let's say your query point is $y$. You could use the distance to the nearest neighbor in $P$ from $y$ as your ranking function (lower is better).

You could also train a SVM to rank order your $y_i$, if that's not overkill for the problem at hand.

PS: Sorry, my answer doesn't give you a vector.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The ranking functions is already defined as the distance between $x$ and the positive/negative vectors. I’m asking how to optimize $x$. $\endgroup$
    – Alex R.
    Sep 21, 2018 at 4:23
  • $\begingroup$ It looks like to me that $x$ is the separating hyperplane defined by a SVM. So, the well known classical problem would be to optimize a SVM on your classification problem. $\endgroup$
    – daruma
    Sep 27, 2018 at 5:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.