How can the input order of pairs into a neural network not matter (i.e. symmetry)?

Question

Let me explain, suppose we are building a neural network that predicts if two items are similar or not. This is a classification task with hard labels (0, 1) of examples of similar and dissimilar items. Suppose we also have access to embeddings for each item.

A naive approach might be to concat the two item embeddings, add a linear layer or two and finally perform a sigmoid (as this is binary classification) for the output probability.

However, that approach would mean that potentially inputing (x, y) to the model could give a different score from inputing (y, x) into it, since concat is not symmetric.

How can we go about overcoming this? What is the common practice in this situation?

So far I have thought about:

1. Whenever I input (x, y) I can also input (y, x) and always take the average prediction of both of them. But this feels like a hacky way of forcing the network to be symmetric, it doesn't make it learn the same thing despite of the input order.

2. Replacing concat with some other symmetric tensor operation. But what operation? Addition? Element-wise multiplication? Element-wise max? What's the "default"?

Answer 1

The problem you're describing is related to (if not a subset of) Shift Invariance. Shift invariance refers to any geometric translation of an input, but concatenation of a pair of tenors in 2 different ways $(x, y) \rightarrow (y, x)$ can be seen as translation with step equal to the shape of the tensors.

How to tackle lack of shift invariance? There is still not unanimous consensus on why deep neural network are not shift invariant, even though some papers pointed out that some convolution operations might be a core issue.

• Zhang proposed an alternative variation of pooling tat should enhance anti-aliased feature maps
• Chaman & Dokmanic focus instead on analyzing the impact of dawn sampling operations, suggesting a new subsampling operation as well to replace in the conventional down sampling approaches.

Starting from a completely different perspective, other papers analyze the impact of classic euclidean geometry, utilized not only in loss design (l1 and l2 norm for example), but also an underlying assumption of every classic deep learning model (despite non linear activation functions, every hidden layer is still a linear transformation of the form $w*x + b$). So instead of fixing linear operations or enforce good shift invariant feature maps, we change the geometry we're using to ensure that translation and rotations have no impact in the optimization of our objective.

• This paper is a good start if you feel brave enough to start experimenting with not euclidean approaches.

On a final note, I think that you first suggestion could be worth a shot if you rethink it this way:

• Present the model each time 2 pairs $(x, y)$ & $(y, x)$ and add a custom loss component to enforce the same prediction (could be literally MSE between the two outputs logits). This loss should at least give you a hint if it's possible for the model to become robust to this specific translation operation (if that loss component decrease over training time the answer is yes).

Answer 2

I answered a similar question here. So the goal here is to train a network which can tell whether the inputs $x$ and $y$ are "similar" or not. You can first build a model $f$ which "compresses" the high-dimensional input into a smaller embedding dimension. In the case of Xception this $f$ would be a mapping from a $299 \times 299 \times 3$ RGB image to a $2048$ "feature vector".

Now the classifier model $c(x, y)$ can be built as $c(x, y) = g(f(x) - f(y))$, where $g$ can be a very simple function without any trainable parameters like $g(\overline{d}) = 1 - e^{-\sum_i d_i^2}$ or something more complex. Clearly here $c(x, y) = c(y, x)$ and $c(x, x) = 0$.

With a custom $f$ and $g$ you can train this model end-to-end, or if your embeddings are fixed (or you use a pre-trained network $f$) it is also possible to just train the $g$.