Answers.Body: <p>Take a vector: <span class="math-container">$V_1 = [v_1, v_2, ..., v_n]$</span><br />
  Calculate the max: <span class="math-container">$m_1 = \max V_1 = v_i$</span><br />
  Shuffle the vector: <span class="math-container">$V_2 = mix(V_1)$</span><br />
  Calculate the max: <span class="math-container">$m_2 = \max V_2 = v_j$</span></p>
  <p>The only possible outcome is that <span class="math-container">$m_1 = m_2$</span></p>
  <p>taking the maximum creates an invariance... if you keep on staking convolution and max pooling, ending up with a single value, then you are totally invariant to translation, instead if you stop before that, you are &quot;almost&quot; invariant&quot;</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-01T14:22:00.297Z
Answers.LastActivityDate: 2023-09-01T14:22:00.297Z
Answers.UserDisplayName: Alberto
Answers.Body: <p>When you apply a convolutional layer to an image <span class="math-container">$x$</span>, you obtain a certain list of values:</p>
  <p><span class="math-container">$$h_1(x), h_2(x), h_3(x), ..., h_n(x) \tag 1$$</span></p>
  <p>where each <span class="math-container">$h_i$</span> is just the function that applies the convolutional filter to a particular patch of the image, and <span class="math-container">$n$</span> equals the number of patches (determined by the size of the filter, the size of the image, and the stride).</p>
  <p>If the image <span class="math-container">$x$</span> consists of a solid blank background with some shape drawn on it, and you translate that shape within the image boundaries, producing a new image <span class="math-container">$x'$</span>, now when you pass that in you'll get:</p>
  <p><span class="math-container">$$h_1(x'), h_2(x'), h_3(x'), ..., h_n(x') \tag 2$$</span></p>
  <p>The point is that the list of values (2) is just a shuffling of the list of values (1). For example, if <span class="math-container">$h_i(x)$</span> is the result of lining up the kernel with the top-left of the shape in <span class="math-container">$x$</span>, then for some <span class="math-container">$j$</span> the function <span class="math-container">$h_j$</span> will correspond to that same position for <span class="math-container">$x'$</span>, and so <span class="math-container">$h_j(x')=h_i(x)$</span>.</p>
  <p>(This is not quite correct if the stride of the convolution is bigger than one - in that case what list of values you end up with depends on how the position of the shape in the image lines up with the stride, but the list (2) will still be &quot;approximately&quot; a shuffling of (1))</p>
  <p>Now if the next step of your network involves piping all these values into some symmetric function such as <strong>max</strong> or <strong>sum</strong> or <strong>mean</strong>, the output of the network is guaranteed to be the same for <span class="math-container">$x'$</span> as for <span class="math-container">$x$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-04T20:12:07.957Z
Answers.Text: As you pointed out the new output (feature map) is just a shuffling of the "original'', thanks to the equivariant property of the convolution operation.  In the last paragraph, if you mean something like global (max or average) pooling then of course it will be invariant. Your last paragraph, though help me realized the importance of the symmetric function. At the end of the day, FCNs achieve translation invariance without pooling, so we don't need pooling at all. The question still remains though. Why bothering with max pooling? How it leads to a NN that is translationally invariant?
Answers.UserDisplayName: Antonios Sarikas
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-04T21:15:08.050Z
Answers.Text: @adosar Can you give an example of a network with max pooling that you think would still be tranlationally invariant without max pooling?
Answers.UserDisplayName: Jack M
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-04T21:45:02.887Z
Answers.Text: Replace all `MaxPooling` with `Conv` and then just take a `GlobalMaxPooling` before the `Dense` layer.
Answers.UserDisplayName: Antonios Sarikas
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-04T21:50:09.310Z
Answers.Text: Seel also this [question](https://ai.stackexchange.com/questions/18157/does-a-fully-convolutional-network-share-the-same-translation-invariance-propert/28596#comment62219_28596). I am completely lost :).
Answers.UserDisplayName: Antonios Sarikas
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-02T16:23:53.523Z
Answers.LastActivityDate: 2023-09-02T16:23:53.523Z
Answers.UserDisplayName: Jack M
Body: <p>I am trying to understand how translation invariance is achieved in CNNs. For example, consider the following simple binary classification problem: predicting whether the letter that appears on an image is <code>A</code> or <code>B</code>.</p>
  <p>We want our network to be translation invariant. That is, if we translate our input, the final output (i.e. the predicted probability) should be the same in both the original and the translated version of the image. Mathematically, we want:</p>
  <p><span class="math-container">$$y = f(T(x)) = f(x)$$</span></p>
  <p>where <span class="math-container">$x$</span> is the original image and <span class="math-container">$T(x)$</span> its translated version. For example, in the following image:</p>
  <p><a href="https://i.sstatic.net/6JPhc.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/6JPhc.png" alt="enter image description here" /></a></p>
  <p>our output <span class="math-container">$y$</span> must be the same.</p>
  <p>Can someone explain how this translation invariance is achieved with the <code>MaxPooling</code> layers?</p>
  <p><strong>My view (possibly wrong)</strong></p>
  <p>First, I will present how I understand the network achieves this translation invariance and then I will provide an explanation why we need pooling.</p>
  <ol>
  <li>Given that the feature maps of a CNN are equivariant (thanks to the convolution operation) as we translate the input these feature maps vary in the same way. That is, if a feature was present in position <span class="math-container">$x$</span> of the feature map, after we translate the image by <span class="math-container">$T$</span>, it will appear now in position <span class="math-container">$T(x)$</span>. Visualizing this:</li>
  </ol>
  <p><a href="https://i.sstatic.net/56Fkv.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/56Fkv.png" alt="enter image description here" /></a></p>
  <p>And as we go deeper into the network where it learns to recognizes <code>A</code> or <code>B</code>, these feature maps will follow the same behavior. So assuming multiple <code>Conv</code> layers (reducing the dimensionality, e.g. from input <code>28x28</code> to <code>2x2</code>) eventually we will get either a <code>black</code> (presence of <code>A</code>) or a <code>white</code> pixel (not presence of <code>A</code>).</p>
  <ol start="2">
  <li>The case where I think <code>MaxPooling</code> is useful is if we consider a slightly different input image such as in the following example.</li>
  </ol>
  <p><a href="https://i.sstatic.net/xwch1.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/xwch1.png" alt="enter image description here" /></a></p>
  <p>Now the <code>\</code> edge has move slightly to the right compared to the <code>/</code>. This slight translation is captured by the first <code>Conv1</code> layer. But what about the <code>Conv2</code> layer? Will it be able to detect the presence of the edge?
  <a href="https://i.sstatic.net/XNf96.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/XNf96.png" alt="enter image description here" /></a></p>
  <p>This might not be the case as shown in the final image. In the right figure we must detect a face, but if the relative positions are slightly changed (mouth is translated slightly downwards), then we might not detect the face at all.</p>
  <p>However, if we use a <code>MaxPooling</code> layer between <code>Conv1</code> and <code>Conv2</code> then we will get the same feature map as in the case of the original image (putting the feature again into &quot;focus&quot; for the next layer).</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-01T13:03:26.977Z
Comments.Text: I'm not sure I understand your problem with the last example (with the face). Translation invariance is where if we slide the image contents around inside the image boundaries, the function output remains the same. If you slide just the mouth down, you're not doing that - you're actually distorting the image. The function output should be allowed to change in that case.
Comments.UserDisplayName: Jack M
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-01T15:40:30.800Z
Comments.Text: @JackM The second example is about the usefulness of `MaxPooling` (this is my view, probably wrong) not about the translation invariance. I try to explain how translation invariance is achieved in the first (`1.`) part.
Comments.UserDisplayName: Antonios Sarikas
Tags: <deep-learning><convolutional-neural-networks><feature-extraction><max-pooling>
Title: How translation invariance is achieved in CNNs?
UserDisplayName: Antonios Sarikas
ThreadText: # How translation invariance is achieved in CNNs?
  
  (Asked by: username_0 on 2023-09-01)
  
  I am trying to understand how translation invariance is achieved in CNNs. For example, consider the following simple binary classification problem: predicting whether the letter that appears on an image is `A` or `B`.
  
  We want our network to be translation invariant. That is, if we translate our input, the final output (i.e. the predicted probability) should be the same in both the original and the translated version of the image. Mathematically, we want:
  
  $$y = f(T(x)) = f(x)$$
  
  where $x$ is the original image and $T(x)$ its translated version. For example, in the following image:
  
  [![enter image description here](https://i.sstatic.net/6JPhc.png)](https://i.sstatic.net/6JPhc.png)
  
  our output $y$ must be the same.
  
  Can someone explain how this translation invariance is achieved with the `MaxPooling` layers?
  
  **My view (possibly wrong)**
  
  First, I will present how I understand the network achieves this translation invariance and then I will provide an explanation why we need pooling.
  
  1. Given that the feature maps of a CNN are equivariant (thanks to the convolution operation) as we translate the input these feature maps vary in the same way. That is, if a feature was present in position $x$ of the feature map, after we translate the image by $T$, it will appear now in position $T(x)$. Visualizing this:
  
  [![enter image description here](https://i.sstatic.net/56Fkv.png)](https://i.sstatic.net/56Fkv.png)
  
  And as we go deeper into the network where it learns to recognizes `A` or `B`, these feature maps will follow the same behavior. So assuming multiple `Conv` layers (reducing the dimensionality, e.g. from input `28x28` to `2x2`) eventually we will get either a `black` (presence of `A`) or a `white` pixel (not presence of `A`).
  
  2. The case where I think `MaxPooling` is useful is if we consider a slightly different input image such as in the following example.
  
  [![enter image description here](https://i.sstatic.net/xwch1.png)](https://i.sstatic.net/xwch1.png)
  
  Now the `\` edge has move slightly to the right compared to the `/`. This slight translation is captured by the first `Conv1` layer. But what about the `Conv2` layer? Will it be able to detect the presence of the edge?
  [![enter image description here](https://i.sstatic.net/XNf96.png)](https://i.sstatic.net/XNf96.png)
  
  This might not be the case as shown in the final image. In the right figure we must detect a face, but if the relative positions are slightly changed (mouth is translated slightly downwards), then we might not detect the face at all.
  
  However, if we use a `MaxPooling` layer between `Conv1` and `Conv2` then we will get the same feature map as in the case of the original image (putting the feature again into "focus" for the next layer).
  
  **Tags:** deep-learning, convolutional-neural-networks, feature-extraction, max-pooling
  > **Comments:**
  > **username_1**: I'm not sure I understand your problem with the last example (with the face). Translation invariance is where if we slide the image contents around inside the image boundaries, the function output remains the same. If you slide just the mouth down, you're not doing that - you're actually distorting the image. The function output should be allowed to change in that case.  
  > **username_0**: @JackM The second example is about the usefulness of `MaxPooling` (this is my view, probably wrong) not about the translation invariance. I try to explain how translation invariance is achieved in the first (`1.`) part.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2023-09-01. Score: 4
  
  Take a vector: $V\_1 = [v\_1, v\_2, ..., v\_n]$  
  Calculate the max: $m\_1 = \max V\_1 = v\_i$  
  Shuffle the vector: $V\_2 = mix(V\_1)$  
  Calculate the max: $m\_2 = \max V\_2 = v\_j$
  
  The only possible outcome is that $m\_1 = m\_2$
  
  taking the maximum creates an invariance... if you keep on staking convolution and max pooling, ending up with a single value, then you are totally invariant to translation, instead if you stop before that, you are "almost" invariant"
  
  
  ---
  
  ### Answer by username_1 on 2023-09-02. Score: 2
  
  When you apply a convolutional layer to an image $x$, you obtain a certain list of values:
  
  $$h\_1(x), h\_2(x), h\_3(x), ..., h\_n(x) \tag 1$$
  
  where each $h\_i$ is just the function that applies the convolutional filter to a particular patch of the image, and $n$ equals the number of patches (determined by the size of the filter, the size of the image, and the stride).
  
  If the image $x$ consists of a solid blank background with some shape drawn on it, and you translate that shape within the image boundaries, producing a new image $x'$, now when you pass that in you'll get:
  
  $$h\_1(x'), h\_2(x'), h\_3(x'), ..., h\_n(x') \tag 2$$
  
  The point is that the list of values (2) is just a shuffling of the list of values (1). For example, if $h\_i(x)$ is the result of lining up the kernel with the top-left of the shape in $x$, then for some $j$ the function $h\_j$ will correspond to that same position for $x'$, and so $h\_j(x')=h\_i(x)$.
  
  (This is not quite correct if the stride of the convolution is bigger than one - in that case what list of values you end up with depends on how the position of the shape in the image lines up with the stride, but the list (2) will still be "approximately" a shuffling of (1))
  
  Now if the next step of your network involves piping all these values into some symmetric function such as **max** or **sum** or **mean**, the output of the network is guaranteed to be the same for $x'$ as for $x$.
  
  > **Comments:**
  > **username_0**: As you pointed out the new output (feature map) is just a shuffling of the "original'', thanks to the equivariant property of the convolution operation.  In the last paragraph, if you mean something like global (max or average) pooling then of course it will be invariant. Your last paragraph, though help me realized the importance of the symmetric function. At the end of the day, FCNs achieve translation invariance without pooling, so we don't need pooling at all. The question still remains though. Why bothering with max pooling? How it leads to a NN that is translationally invariant?  
  > **username_1**: @adosar Can you give an example of a network with max pooling that you think would still be tranlationally invariant without max pooling?  
  > **username_0**: Replace all `MaxPooling` with `Conv` and then just take a `GlobalMaxPooling` before the `Dense` layer.  
  > **username_0**: Seel also this [question](https://ai.stackexchange.com/questions/18157/does-a-fully-convolutional-network-share-the-same-translation-invariance-propert/28596#comment62219_28596). I am completely lost :).  
  
  ---
  
  