Answers.Body: <p>The problem you're describing is related to (if not a subset of) <a href="https://en.wikipedia.org/wiki/Shift-invariant_system" rel="noreferrer">Shift Invariance</a>. Shift invariance refers to any geometric translation of an input, but concatenation of a pair of tenors in 2 different ways <span class="math-container">$(x, y) \rightarrow (y, x)$</span> can be seen as translation with step equal to the shape of the tensors.</p>
  <p>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.</p>
  <ul>
  <li><a href="http://proceedings.mlr.press/v97/zhang19a/zhang19a.pdf" rel="noreferrer">Zhang</a> proposed an alternative variation of pooling tat should enhance anti-aliased feature maps</li>
  <li><a href="https://arxiv.org/pdf/2011.14214.pdf" rel="noreferrer">Chaman &amp; Dokmanic</a> 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.</li>
  </ul>
  <p>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 <span class="math-container">$w*x + b$</span>). 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.</p>
  <ul>
  <li><a href="https://arxiv.org/pdf/1611.08097.pdf" rel="noreferrer">This paper</a> is a good start if you feel brave enough to start experimenting with not euclidean approaches.</li>
  </ul>
  <p>On a final note, I think that you first suggestion could be worth a shot if you rethink it this way:</p>
  <ul>
  <li>Present the model each time 2 pairs <span class="math-container">$(x, y)$</span> &amp; <span class="math-container">$(y, x)$</span> and <strong>add a custom loss component</strong> 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).</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-27T13:10:08.487Z
Answers.LastActivityDate: 2022-01-27T13:10:08.487Z
Answers.UserDisplayName: Edoardo Guerriero
Answers.Body: <p>I answered a similar question <a href="https://ai.stackexchange.com/a/34049/32722">here</a>. So the goal here is to train a network which can tell whether the inputs <span class="math-container">$x$</span> and <span class="math-container">$y$</span> are &quot;similar&quot; or not. You can first build a model <span class="math-container">$f$</span> which &quot;compresses&quot; the high-dimensional input into a smaller embedding dimension. In the case of <a href="https://arxiv.org/abs/1610.02357" rel="nofollow noreferrer">Xception</a> this <span class="math-container">$f$</span> would be a mapping from a <span class="math-container">$299 \times 299 \times 3$</span> RGB image to a <span class="math-container">$2048$</span> &quot;feature vector&quot;.</p>
  <p>Now the classifier model <span class="math-container">$c(x, y)$</span> can be built as <span class="math-container">$c(x, y) = g(f(x) - f(y))$</span>, where <span class="math-container">$g$</span> can be a very simple function without any trainable parameters like <span class="math-container">$g(\overline{d}) = 1 - e^{-\sum_i d_i^2}$</span> or something more complex. Clearly here <span class="math-container">$c(x, y) = c(y, x)$</span> and <span class="math-container">$c(x, x) = 0$</span>.</p>
  <p>With a custom <span class="math-container">$f$</span> and <span class="math-container">$g$</span> you can train this model end-to-end, or if your embeddings are fixed (or you use a pre-trained network <span class="math-container">$f$</span>) it is also possible to just train the <span class="math-container">$g$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-28T16:07:21.797Z
Answers.Text: So in your version, I would take the difference between the f(x) and f(y) and then pass them through network g(x) instead of doing `g(concat(f(x), f(y))`? But does the loss changes? Do I still use binary cross entropy for classification or does my task change?
Answers.UserDisplayName: Michael
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-28T16:08:17.343Z
Answers.Text: I thought Siamese Networks that employ ranking losses were used to learn embeddings where similar objects are closer than dissimilar objects not to predict the similarity itself.
Answers.UserDisplayName: Michael
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-28T16:36:09.907Z
Answers.Text: Also, the difference is not symmetric either so.. problem not solved.
Answers.UserDisplayName: Michael
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-28T19:17:25.807Z
Answers.Text: Yes you still use binary cross entropy since your target is still a 0 / 1 prediction. You can take element-wise absolute value (or square them) to guarantee a symmetric model $c$.
Answers.UserDisplayName: NikoNyrh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-27T20:07:44.370Z
Answers.LastActivityDate: 2022-01-28T11:28:10.780Z
Answers.LastEditDate: 2022-01-28T11:28:10.780Z
Answers.UserDisplayName: NikoNyrh
Body: <p>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.</p>
  <p>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.</p>
  <p>However, that approach would mean that potentially inputing <code>(x, y)</code> to the model could give a different score from inputing <code>(y, x)</code> into it, since concat is not symmetric.</p>
  <p>How can we go about overcoming this? What is the common practice in this situation?</p>
  <p>So far I have thought about:</p>
  <ol>
  <li><p>Whenever I input <code>(x, y)</code> I can also input <code>(y, x)</code> 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.</p>
  </li>
  <li><p>Replacing concat with some other symmetric tensor operation. But what operation? Addition? Element-wise multiplication? Element-wise max? What's the &quot;default&quot;?</p>
  </li>
  </ol>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-27T12:23:57.980Z
Comments.Text: Out of interest, why in the example scenario do you have embeddings where "similar" items have dissimilar embeddings? Are you not in control of the encoder?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-27T12:50:56.780Z
Comments.Text: I never said that "similar" items have dissimilar embeddings. The embeddings are fixed and extracted from text with pretrained BERT. My problem is in the ordering that I should give each pair of item embeddings. My intuition says that the order shouldn't matter.
Comments.UserDisplayName: Michael
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-27T13:00:47.370Z
Comments.Text: If you mean to ask "Why do we need supervision for similarity if we can just calculate the similarity on the embeddings?" then I would say that is a good point that had not occured to me. I guess the fact that the embeddings are fixed is a valid reason. 
  
  The final layer can be "correcting actions" or a way to learn a threshold of "how similar is similar enough".
Comments.UserDisplayName: Michael
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-27T14:20:04.817Z
Comments.Text: Yes that is why I was asking. One of your solutions here - which sidesteps the symmetry issue - is to train such that the embeddings already solve your problem. This is how face recognition usually works. That could be part of an answer, but whether or not is worth mentioning depends on whether you are asking to solve your original problem (classifying pairs as similar), or whether you want to stay focused on the symmetry issue already presented in the question.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-27T14:22:37.203Z
Comments.Text: I don't know whether training embeddings for low distance when similar and high distance when different (triplet loss is a standard example) is used much in text systems. Chances are if you are using an embedding, it will be from some pre-trained general language model, which may be very expensive to train or re-train yourself.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-28T16:41:04.917Z
Comments.Text: It WAS very expensive so I considered it fixed and only ran it once to get the embeddings for all the text in my dataset.
Comments.UserDisplayName: Michael
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-28T16:42:33.300Z
Comments.Text: I think what is asked of me is a model that can tell, given two pairs, if they are similar or not based on a labeled dataset provided. As such, I don't think training to find good embeddings (e.g. Siamese networks) and then finding an arbitrary threshold to predict similarity for new data is more sensible than doing classification to begin with. How would I even find that threshold? Another nn? There is a recursion here somewhere...
Comments.UserDisplayName: Michael
Tags: <neural-networks><deep-learning><pytorch><feedforward-neural-networks>
Title: How can the input order of pairs into a neural network not matter (i.e. symmetry)?
UserDisplayName: Michael
ThreadText: # How can the input order of pairs into a neural network not matter (i.e. symmetry)?
  
  (Asked by: username_0 on 2022-01-27)
  
  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"?
  
  **Tags:** neural-networks, deep-learning, pytorch, feedforward-neural-networks
  
  > **Comments:**
  > **username_1**: Out of interest, why in the example scenario do you have embeddings where "similar" items have dissimilar embeddings? Are you not in control of the encoder?  
  > **username_0**: I never said that "similar" items have dissimilar embeddings. The embeddings are fixed and extracted from text with pretrained BERT. My problem is in the ordering that I should give each pair of item embeddings. My intuition says that the order shouldn't matter.  
  > **username_0**: If you mean to ask "Why do we need supervision for similarity if we can just calculate the similarity on the embeddings?" then I would say that is a good point that had not occured to me. I guess the fact that the embeddings are fixed is a valid reason.   The final layer can be "correcting actions" or a way to learn a threshold of "how similar is similar enough".  
  > **username_1**: Yes that is why I was asking. One of your solutions here - which sidesteps the symmetry issue - is to train such that the embeddings already solve your problem. This is how face recognition usually works. That could be part of an answer, but whether or not is worth mentioning depends on whether you are asking to solve your original problem (classifying pairs as similar), or whether you want to stay focused on the symmetry issue already presented in the question.  
  > **username_1**: I don't know whether training embeddings for low distance when similar and high distance when different (triplet loss is a standard example) is used much in text systems. Chances are if you are using an embedding, it will be from some pre-trained general language model, which may be very expensive to train or re-train yourself.  
  > **username_0**: It WAS very expensive so I considered it fixed and only ran it once to get the embeddings for all the text in my dataset.  
  > **username_0**: I think what is asked of me is a model that can tell, given two pairs, if they are similar or not based on a labeled dataset provided. As such, I don't think training to find good embeddings (e.g. Siamese networks) and then finding an arbitrary threshold to predict similarity for new data is more sensible than doing classification to begin with. How would I even find that threshold? Another nn? There is a recursion here somewhere...  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2022-01-27. Score: 5
  
  The problem you're describing is related to (if not a subset of) [Shift Invariance](https://en.wikipedia.org/wiki/Shift-invariant_system). 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](http://proceedings.mlr.press/v97/zhang19a/zhang19a.pdf) proposed an alternative variation of pooling tat should enhance anti-aliased feature maps
  * [Chaman & Dokmanic](https://arxiv.org/pdf/2011.14214.pdf) 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](https://arxiv.org/pdf/1611.08097.pdf) 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 by username_3 on 2022-01-27. Score: 1
  
  I answered a similar question [here](https://ai.stackexchange.com/a/34049/32722). 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](https://arxiv.org/abs/1610.02357) 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$.
  
  > **Comments:**
  > **username_0**: So in your version, I would take the difference between the f(x) and f(y) and then pass them through network g(x) instead of doing `g(concat(f(x), f(y))`? But does the loss changes? Do I still use binary cross entropy for classification or does my task change?  
  > **username_0**: I thought Siamese Networks that employ ranking losses were used to learn embeddings where similar objects are closer than dissimilar objects not to predict the similarity itself.  
  > **username_0**: Also, the difference is not symmetric either so.. problem not solved.  
  > **username_3**: Yes you still use binary cross entropy since your target is still a 0 / 1 prediction. You can take element-wise absolute value (or square them) to guarantee a symmetric model $c$.  
  
  ---
  
  