# Maximizing AUC based on point cloud distance

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.

• What does it mean that a vector $x$ is closer to set of vectors $P$ than to a space $V$? – Jan Kukacka Sep 27 at 7:40
• 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|$ – Łukasz Grad Sep 27 at 7:44
• @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 – Alex R. Sep 27 at 17:58
• 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. – Jacques Wainer Oct 3 at 12:15
• @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. – Alex R. Oct 3 at 19:13

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.
• The ranking functions is already defined as the distance between $x$ and the positive/negative vectors. I’m asking how to optimize $x$. – Alex R. Sep 21 at 4:23
• 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. – daruma Sep 27 at 5:05