0
$\begingroup$

I have a set of vectors in a vector space and I'm looking for some score that measures how "distinct" each vector is from the others.

I suppose this is a well-known problem but I have no idea how to call it or how to search for it.

enter image description here

To explain what I mean, suppose the points are some vectors in a vector space (not necessarily 2-dimensional). I'm looking to assign a score to each vector such that the vector which is the most "distinct" (the farthest from the others in some sense) has the highest score. In this example, the yellow vector would probably have the highest score and the red and blue would have the lowest.

In my particular case each vector represents a policy in two-agent reinforcement learning. I'm trying to capture the notion that similar policies would have similar performance when playing against any given agent. In other words, if I keep only a subset of the policies, I should remove those with the lowest score (because the remaining ones form a good representation of the policy space). In the picture above, the blue vector could be removed because the red vector is quite similar.

Is there a name for such a score for vectors in a set? What types of scores exist? Where can I find more information about this topic? I guess I could use some form of clustering but I'm not sure this is the best option.

$\endgroup$

1 Answer 1

1
$\begingroup$

Multiple methods come to mind. Here are a few ideas. The first one is very easy to implement and the other ones are clustering methods, for which many implementations exist already:

  • Use cosine distance or another metric to compute a pairwise distance matrix of each point against every other points. You end up with a square matrix of size (N, N) where N is the number of points. You can then find the furthest point by taking the one that maximizes the sum of each row.
  • KMeans clustering to identify clusters of points that are close to each other. KMeans will compute centroids for a predefined number of clusters.
  • Agglomerative clustering starts by assigning each point to a different cluster and group them based on a similarity metric (bottom-up approach)
  • Divisive clustering start with all the points and divide them step by step (top-down approach)

Agglomerative and divisive clustering give you hierarchical clusters, and you can choose the granularity that fits your needs.

$\endgroup$

Your Answer

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

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