Answers.Body: <p><em>locality of pixel dependencies</em> probably means that neighboring pixels tend to be correlated, while faraway pixels are <em>usually</em> not correlated. This assumption is usually made in several image processing techniques (e.g. filters). Of course, the size and the shape of the neighborhood could vary, depending on the region of the image (or whatever), but, in practice, it is usually chosen to be fixed and rectangular (or squared).</p>
  
  <p><em>stationarity of statistics</em> might mean that the values of the pixels do not change over time, so this could be related to <a href="https://en.wikipedia.org/wiki/Anisotropic_diffusion" rel="nofollow noreferrer">diffusion techniques</a> in image processing. <em>stationarity of statistics</em> might also mean that the values of the pixels do not change much in a spatial neighborhood, even though, stationarity, e.g. in reinforcement learning, usually means that something does not change <em>over time</em> (so, if that's the case, the terminology <em>stationarity</em> is at least misleading and confusing, in this context), so this might be related to the <em>locality of pixel dependencies</em> property. Possibly, <em>stationarity of statistics</em> could also indirectly mean that you can use the same filter to detect the same feature in different regions of the image.</p>
  
  <p>With <em>while their theoretically-best performance is likely to be only slightly worse</em> the authors probably thought that, theoretically, CNNs are not as powerful as feedforward neural networks. However, both <a href="https://ai.stackexchange.com/a/13319/2444">CNNs and FFNNs are universal function approximators</a> (but, at the time, nobody probably had yet investigated seriously the theoretical powerfulness of CNNs).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-31T01:19:11.047Z
Answers.Text: I really think in this case stationarity isnt regarding time, but spatial location (given no time exists-- im assuming you meant over the dataset) I think theyre saying alot of local statistics are common across multiple areas of the image (therefore a single convolved filter can be a useful featurization of multiple fields rather than just one)
Answers.UserDisplayName: mshlis
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-31T01:36:41.590Z
Answers.Text: @mshlis You might be right. This was my interpretation, given the usual meaning of stationarity (e.g. in reinforcement learning). However, if your interpretation is correct, then their terminology is highly confusing or misleading.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-31T02:06:21.607Z
Answers.Text: I completely agree, generally stationarity when referring to images draws on the distributions of the pixels themselves, but here it seems to be used based on the dependencies, treating the moving indices of the convolution to parametrize some from of process.
Answers.UserDisplayName: mshlis
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-31T09:19:33.110Z
Answers.Text: Thanks for the answer! Could you edit the part about stationarity of statistics? I don't think there's any temporal aspect to image processing at least in the context of the question. I can then accept the answer once that part of edited. Thanks again!
Answers.UserDisplayName: Shirish
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-31T10:12:24.217Z
Answers.Text: @ShirishKulhari You can view an image or a sequence of images as a flow over time, so this interpretation is not completely wrong. Have a look at certain image processing techniques that are based on diffusion.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-31T10:19:51.710Z
Answers.Text: @nbro: Oh, my bad. I can understand that a video could definitely be interpreted as a sequence of images as a flow over time, but I'm not clear on how a single, static image be interpreted as such. Could you elaborate about that in the answer, if possible?
Answers.UserDisplayName: Shirish
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-31T10:21:44.317Z
Answers.Text: @ShirishKulhari Essentially, a noisy image $\hat{f}$ of an original image $f$ might be viewed as an image of a sequence of images, $f, f_1, f_2, \dots, \hat{f}, \hat{f}_1, \dots$, that starts at the original image and goes through $\hat{f}$, so this sequence of images is part of a "flow". This is just an assumption or interpretation made by some image processing techniques, like anisotropic diffusion, which is used to denoise an image. If you're interested in this, have a look at the details of this technique.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-31T10:23:35.727Z
Answers.Text: @nbro: So denoising involves figuring out the transformation $f \to \hat f$ and inverting it?
Answers.UserDisplayName: Shirish
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-31T10:24:27.050Z
Answers.Text: @ShirishKulhari Yes, that's basically the idea.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-30T22:23:35.617Z
Answers.LastActivityDate: 2019-07-31T10:27:06.947Z
Answers.LastEditDate: 2019-07-31T10:27:06.947Z
Answers.UserDisplayName: nbro
Body: <p>I'm reading the <a href="https://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks.pdf" rel="nofollow noreferrer">ImageNet Classification with Deep Convolutional Neural Networks</a> paper by Krizhevsky et al, and came across these lines in the Intro paragraph:</p>
  
  <blockquote>
    <p>Their (convolutional neural networks') capacity can be controlled by varying their depth and breadth, and they also make strong and mostly correct assumptions about the nature of images (namely, <strong>stationarity of statistics and locality of pixel dependencies</strong>). Thus, compared to standard feedforward neural networks with similarly-sized layers, CNNs have much fewer connections and parameters and so they are easier to train, <strong>while their theoretically-best performance is likely to be only slightly worse</strong>.</p>
  </blockquote>
  
  <p>What's meant by "stationarity of statistics" and "locality of pixel dependencies"? Also, what's the basis of saying that CNN's theoretically best performance is only slightly worse than that of feedforward NN?</p>
  
Tags: <convolutional-neural-networks><terminology><papers>
Title: What is the meaning of "stationarity of statistics" and "locality of pixel dependencies"?
UserDisplayName: Shirish
ThreadText: # What is the meaning of "stationarity of statistics" and "locality of pixel dependencies"?
  
  (Asked by: username_0 on 2019-07-30)
  
  I'm reading the [ImageNet Classification with Deep Convolutional Neural Networks](https://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks.pdf) paper by Krizhevsky et al, and came across these lines in the Intro paragraph:
  
  > Their (convolutional neural networks') capacity can be controlled by varying their depth and breadth, and they also make strong and mostly correct assumptions about the nature of images (namely, **stationarity of statistics and locality of pixel dependencies**). Thus, compared to standard feedforward neural networks with similarly-sized layers, CNNs have much fewer connections and parameters and so they are easier to train, **while their theoretically-best performance is likely to be only slightly worse**.
  
  What's meant by "stationarity of statistics" and "locality of pixel dependencies"? Also, what's the basis of saying that CNN's theoretically best performance is only slightly worse than that of feedforward NN?
  
  **Tags:** convolutional-neural-networks, terminology, papers
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-07-30. Score: 3 | Accepted answer
  
  *locality of pixel dependencies* probably means that neighboring pixels tend to be correlated, while faraway pixels are *usually* not correlated. This assumption is usually made in several image processing techniques (e.g. filters). Of course, the size and the shape of the neighborhood could vary, depending on the region of the image (or whatever), but, in practice, it is usually chosen to be fixed and rectangular (or squared).
  
  *stationarity of statistics* might mean that the values of the pixels do not change over time, so this could be related to [diffusion techniques](https://en.wikipedia.org/wiki/Anisotropic_diffusion) in image processing. *stationarity of statistics* might also mean that the values of the pixels do not change much in a spatial neighborhood, even though, stationarity, e.g. in reinforcement learning, usually means that something does not change *over time* (so, if that's the case, the terminology *stationarity* is at least misleading and confusing, in this context), so this might be related to the *locality of pixel dependencies* property. Possibly, *stationarity of statistics* could also indirectly mean that you can use the same filter to detect the same feature in different regions of the image.
  
  With *while their theoretically-best performance is likely to be only slightly worse* the authors probably thought that, theoretically, CNNs are not as powerful as feedforward neural networks. However, both [CNNs and FFNNs are universal function approximators](https://ai.stackexchange.com/a/13319/2444) (but, at the time, nobody probably had yet investigated seriously the theoretical powerfulness of CNNs).
  
  > **Comments:**
  > **username_2**: I really think in this case stationarity isnt regarding time, but spatial location (given no time exists-- im assuming you meant over the dataset) I think theyre saying alot of local statistics are common across multiple areas of the image (therefore a single convolved filter can be a useful featurization of multiple fields rather than just one)  
  > **username_1**: @mshlis You might be right. This was my interpretation, given the usual meaning of stationarity (e.g. in reinforcement learning). However, if your interpretation is correct, then their terminology is highly confusing or misleading.  
  > **username_2**: I completely agree, generally stationarity when referring to images draws on the distributions of the pixels themselves, but here it seems to be used based on the dependencies, treating the moving indices of the convolution to parametrize some from of process.  
  > **username_0**: Thanks for the answer! Could you edit the part about stationarity of statistics? I don't think there's any temporal aspect to image processing at least in the context of the question. I can then accept the answer once that part of edited. Thanks again!  
  > **username_1**: @ShirishKulhari You can view an image or a sequence of images as a flow over time, so this interpretation is not completely wrong. Have a look at certain image processing techniques that are based on diffusion.  
  > **username_0**: @nbro: Oh, my bad. I can understand that a video could definitely be interpreted as a sequence of images as a flow over time, but I'm not clear on how a single, static image be interpreted as such. Could you elaborate about that in the answer, if possible?  
  > **username_1**: @ShirishKulhari Essentially, a noisy image $\hat{f}$ of an original image $f$ might be viewed as an image of a sequence of images, $f, f_1, f_2, \dots, \hat{f}, \hat{f}_1, \dots$, that starts at the original image and goes through $\hat{f}$, so this sequence of images is part of a "flow". This is just an assumption or interpretation made by some image processing techniques, like anisotropic diffusion, which is used to denoise an image. If you're interested in this, have a look at the details of this technique.  
  > **username_0**: @nbro: So denoising involves figuring out the transformation $f \to \hat f$ and inverting it?  
  > **username_1**: @ShirishKulhari Yes, that's basically the idea.  
  
  ---
  
  