I am looking for some clues as to the type of algorithm/data structure or general field of CS to look into...

I have a collection of items that I would like to have a human subjectively compare such that I can derive some consistent dataset that can be queried for k nearest neighbours for a given item that is present in the data.

i.e. if I ask a human, given item A, which item is most similar, B or C (repeated over a set of such items)

I can later present back, when queried, here are the items most similar to A.

The desire is simply to record a person's subjective comparisons of a set of items and have a means to allow them to query it.

Any pointers as to algorithms or structures to read up on would be greatly appreciated.


Distance metric learning

It sounds like you want to learn a distance metric $D(\cdot,\cdot)$ on the items. If the human tells you that A is more similar to B than to C, then you learn that $D(A,B) < D(A,C)$ (probably). Based on many instances of this, you can learn a distance metric $D(\cdot,\cdot)$. Then, you can use $k$-nearest neighbors with this distance metric.


How does distance metric learning work? Well, you can do a search and you'll find a lot of material. Basically, you identify some features that you think might be relevant. So, let $f(A)$ denote the feature vector associated to $A$. Then you want to learn a distance metric of the form

$$D(A,B) = d(f(A),f(B))$$

where $d : \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}$ is the distance function that you want to learn. There are various methods for this. In one of them, we assume that $d$ takes the form

$$d(x,y) = (x-y)^\top A (x-y)$$

where $A$ is some positive semidefinite matrix that is to be learned. The training set gives us comparisons of the form $d(x_A,x_B) < d(x_A,x_C)$, i.e.,

$$(x_A-x_B)^\top A (x_A-x_B) < (x_A-x_C)^\top A (x_A-x_C).$$

You could then form a convex optimization problem of the form

minimize $||A||_F$

subject to $A \succeq 0$ and $(x_A-x_C)^\top A (x_A-x_C) < (x_A-x_B)^\top A (x_A-x_B)$ for all $x_A,x_B,x_C$ in the training set.

Here $||A||_F$ is the Frobenius norm. Also $A \succeq 0$ means that $A$ is positive semidefinite). (This can be expressed by writing $A=M^\top M$ and using the entries of $M$ as your unknowns, though sometimes it is easier to leave it in the form $A$.) Then we apply some algorithm for convex optimization to learn $A$ or $M$.

That's one example of a method; there are many others. For instance, you might add a margin to the inequality above, and require that $d(x_A,x_B) < d(x_A,x_C)-1$ (so they are well-separated).

The effectiveness will be partly determined both by the metric learning method you use, but the set of features you come up with are also extremely important. You'll want to use your domain knowledge about what attributes of items might be relevant or helpful in determining similarity. If you have good features, you'll probably find that distance metric learning is more effective.

To learn more

There are many schemes for distance metric learning. A websearch and a search on Google Scholar should turn up a bunch of candidates. You want to learn a distance metric from relative comparisons. See also https://en.wikipedia.org/wiki/Similarity_learning.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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