# Training given pairs of similar values, not labels

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?

• What is the ultimate goal? It almost sounds like what you want is clustering. Could you rephrase your problem as a ranking problem, i.e., something like $N(x, y) > N(x^\prime, y^\prime)$ for all $(x,y) \in S$, $(x^\prime, y^\prime) \not\in S$? – alto Jun 22 '14 at 20:27
• @alto: I have an equivalence relation on $S$ and want to compute a quotient map of $S$ into a reduced-dimension $R^n$, giving me a semi-metric on $S$ consistent with the equivalence relation. Ultimately I have some hierarchical computation for which it is crucial that I can compute the semi-metric of elements in $S$ in time proportional to the dimension of $R^n$, thus I am interested in the vectors $N(x) \in R^n$ on their own, and cannot phrase the problem your way. – ybungalobill Jun 22 '14 at 21:26
• Does it have to be a neural network? – Yuval Filmus Jul 24 '14 at 1:32
• @YuvalFilmus: No, it can be any other self-learning representation of the function $N(x)$ that would give the desired properties. Since I posted this question I thought of requiring that the variance of each output node taken over the whole training set to be 1, say. Using a constrained gradient descent should give me the desired results. I haven't yet implemented this, but I assume it should give good results. In addition it would allow me to pre-train individual layers of the multi-level neural network, which is good. – ybungalobill Jul 24 '14 at 17:23

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.

## 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.,

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).