Training given pairs of similar values, not labels

Question

I have pairs of "similar" values $(x_i, y_i)$ drawn from a space $x_i, y_i \in S$, and want to train a neural network $N$ such that $N(x_i)$ would be "close" to $N(y_i)$ for all $i$, yet, to make it useful, the overall image of $N$ would be as spread apart as possible. Note that the training data says which values are similar, but does not imply that values from different pairs are necessarily different (i.e. these aren't labels).

Defining a cost function to be something like $\frac{1}{2} \sum_i \| N(x_i) - N(y_i) \|^2$ doesn't work, because $N(x) = 0$ would then be a trivial solution. Another option I considered is to require that, assuming the inputs are distributed with zero mean and unit variance, say, the outputs would be distributed with zero mean and unit variance too. I don't know how to efficiently enforce it though, or whether it would even give good results.

I see it as a kind of unsupervised learning with some "hints" provided.

So, my question is: what kind of problem is this? How to approach it? Can you direct me to any previous similar research?

Answer 1

I'm not convinced that a neural network is necessarily the right tool for this. When you have a hammer, it's tempting to think that everything looks like a nail... but sometimes the answer is "No, you dummy, that's a screw, use a screwdriver, not a hammer."

So, I'll comment on several kinds of methods you could explore, for your problem. I suggest you look into them all and see which works best in your specific application.

Clustering

It looks like your problem is basically a clustering problem. There are many standard algorithms for clustering data. For instance, if your space is $S=\mathbb{R}^n$, many clustering algorithms are known. There are also many clustering algorithms known that can work on any metric space. I recommend you take a look at https://en.wikipedia.org/wiki/Cluster_analysis to familiarize yourself with some of the standard methods, and look to see whether any of them might suit your application well.

Neural networks and autoencoders

If you are set on using a neural network (which, again, might not be the right attitude), an alternative approach might be to learn an auto-encoder for the data. This is a standard way to use neural networks for unsupervised learning. This basically asks the neural network to find a way to project high-dimensional data down to some lower-dimensional space, in a way that preserves as much as possible of the structure of the original data. Empirically, it often seems to be an effective way to do unsupervised learning.

You could train a neural network in this way, and then use it to project your inputs to the lower-dimensional space and measure distances in the projected space. There are standard training algorithms to fit an autoencoder.

See also https://en.wikipedia.org/wiki/Neural_network#Unsupervised_learning and https://en.wikipedia.org/wiki/Autoencoder.

Metric space embeddings

You might also want to look into the literature on metric space embeddings. A metric space embedding is a map $f:S \to \mathbb{R}^n$ from a metric space $S$ to $\mathbb{R}^n$, such that $f$ approximately preserves the distance metric on $S$. In other words, we seek to find $f$ such that

$||f(x)-f(y)||_2 \approx d_S(x,y)$$

for all or most $x,y \in S$. This is an embedding into $\mathbb{R}^n$ with the Euclidean norm (or into $\ell_2$ if we don't care about the dimension $n$).

There's been a lot of work on this subject, including the computational aspects of learning/finding such embeddings. See, e.g.,

• https://en.wikipedia.org/wiki/Machine_learning#Similarity_and_metric_learning and https://en.wikipedia.org/wiki/Similarity_learning#Metric_learning

• Embedding Finite Metric Spaces into Normed Spaces, Chapter 15 of Lectures on Discrete Geometry by Jiri Matousek.

• Distributional Scaling: An Algorithm for Structure-Preserving Embedding of Metric and Nonmetric Spaces. Michael Quist, Golan Yona. Journal of Machine Learning Research 5 (2004) pp.399-430.

• The CMU course CS 15-859(J): Algorithmic Applications of Metric Embeddings, especially Lectures 1 and 5.

• Finite Metric Spaces - Combinatorics, Geometry, and Algorithms. Nathan Linial. Proceedings of the International Congress of Mathematicians III, 2002.

• The Geometry of Graphs and Some of Its Algorithmic Applications. Nathan Linial, Eran London, Yuri Rabinovich. Combinatorica 15(2), 1995.

I'm not an expert on this subject, so there's probably more relevant work out there (e.g., in the machine learning or systems community).