Suppose that someone has trained a nearest-neighbor algorithm based on some unknown metric. I have a large dataset of $N$ observations and $P$ features. For each observation, I am given $K$ indices corresponding to the $K$ "nearest" points in the (same) dataset.
What is the general type of strategy to learn this metric? Does this type of problem have a standard name? Are there any Kaggle-type competitions with such a task, or is this unusual?
Interesting question. If you supposed that the distance metric was some common one, of course you could just try all the common ones and see what is consistent with the nearest neighbors it returns.
I can't think of a way to learn this reliably, because you don't have any info about the actual distances. Maybe treat all nearest-neighbor pairs as having 'small' distance and the rest 'large' and training a deep model that tries to learn to predict it across pairs of points. Whatever it comes up with as a metric would approximate it.
This is called "distance metric learning" or "learning distance metrics". You can find many papers in the literature on this topic.
There are many algorithms for learning distance metrics. Some of them allow you to specify quadruplets $(x_1,x_2,x_3,x_4)$ where we are promised that $d(x_1,x_2) < d(x_3,x_4)$, and the task is to learn a distance matric $d$ that is consistent with this training set. You can then use such an algorithm for your task, by sampling $x_1$ randomly from your training set, sampling $x_2$ from one of the $K$ nearest neighbors to $x_1$, setting $x_3=x_1$, and sampling $x_4$ from one of the other $N-K-1$ non-neighbors.
One approach is to learn a Mahalanobis distance, i.e., a distance metric of the form $d(x,x') = \|Lx-Lx'\|_2$. This can be equivalently formulated as $d(x,x') = \sqrt{(x-x')^\top M(x-x')}$ where $M=L^\top L$. You can formulate the learning task as an optimization problem, and then use standard optimization methods to learn the matrix $L$ (or $M$). This learns a linear distance metric.
There are other approaches that attempt to learn a more complex, nonlinear distance metric using a neural network, e.g., $d(x,x') = \|N(x)-N(x')\|_2$, where $N$ is a neural network (thus, measuring distance using a Siamese network). Standard literature on training neural networks to measure image similarity describe a number of ways to learn such a network, and it could be applied to your situation as well by sampling triplets appropriately.
You might be interested in the metric-learn package for Python.
