4
$\begingroup$

I am reading the paper Design of an energy efficient accelerator for training of convolutional neural networks using frequency Domain Computation:

enter image description here

which uses Frequency Pooling, from Spectral Representations for Convolutional Neural Networks:

enter image description here


Question

For simplicity, let me assume there is no sinc interpolation, and the convolution kernels are stored in the frequency domain having the same size of the input ($N$ x $N$). My understanding of the frequency pooling in the proposed method is the following:

  1. On the forward-pass, we have that the lower frequencies components of the convolution output ($N$ x $N$) are shifted to the center of the representation.
  2. Next, the high frequency components outside of a central area (say $N/2$ x $N/2$) are discarded.
  3. Then, the remaining frequencies as passed to the next layers ( non-linear activation; convolution; frequency pooling; non-linear activation; and so on)

Here is an illustration, notice low frequencies are assumed to be in the center.

enter image description here

Given that, it seems that the discarded frequencies in the frequency pooling process do not contribute at all to the output. If that is the case, then all the frequencies that are discarded in all pooling layers, up to the last frequency pooling, would not be used for the computation of the final output.

Wouldn't this be equivalent to discarding all those frequencies in the input layer? I seem to be missing something very important on this.


EDIT:

Here is a GIST I put up that pinpoints my question. I hope that it makes things more clear.

$\endgroup$
7
  • 1
    $\begingroup$ Downsampling in a sparser domain... clever $\endgroup$ Aug 22 at 4:26
  • $\begingroup$ I've yet to dig deep but the key seems to be that spectral pooling is simply better than spatial pooling for images as they're predominantly low-frequency, so we keep much more info for same number of data points (as your examples confirm); they aren't meant to perfectly preserve the input. $\endgroup$ Aug 23 at 18:22
  • $\begingroup$ "as they're predominantly low-frequency". I do share these same thoughts. The thing is this paper shows results using MNIST, which have images, say $32 \times 32$. After two pooling layers, the outcome would be $8 \times 8$ that contains information based on only the equivalent components to those $8 \times 8$ in the original image. That being the case, I could be consider kind of misleading present it as superior to the traditional method without considering that the network output is relaying now on only a "Blur" of the input. $\endgroup$ Aug 23 at 18:36
  • $\begingroup$ What is also bothering me is that, in Design of an energy efficient accelerator for training of convolutional neural networks using frequency Domain Computation, the author mention that if the output is size $1 \times 1$, in which the iFFT output would be the same as its input. The issue is, given the spectral pooling applied in such way, the output would seem to rely only on the DC of the input. $\endgroup$ Aug 23 at 18:40
  • $\begingroup$ While it's a blur, it's still much more information per unit sample, and they demonstrate this with recovery of input. If it's $1 \times 1$ there's only DC to begin with, nothing's discarded: it's a trivial case. Granted I wonder what the pitfall of this is and why it's not the SOTA -- asked on it. $\endgroup$ Aug 23 at 22:20
4
$\begingroup$

Wouldn't this be equivalent to discarding all those frequencies in the input layer?

No, it won't for 2 facts:

  1. Just like a CNN isn't a linear regression due to having non linear function in between. So the Activation Layers on the frequency domain mean things are not propagated linearly in the forward pass.

  2. The filters are adaptive (Learned). Namely each layer will have a different response on the middle (Low Frequencies).

Basically what we see is cascaded low pass filters with non linear activation in between. The way I see it, the major advantage doing it so:

  1. There is a better understanding what we should pull and what not. Low frequency details are explicitly preserved.
  2. Computations are done with multiplications vs. convolutions. So for some dimensions combination it might be faster.

Example

In order to show, let's just apply a toy example using the building blocks of Design of an Energy Efficient Accelerator for Training of Convolutional Neural Networks Using Frequency Domain Computation.
Specifically how they describe the Spectra Pooling and Spectral Activation (See Section 3.4):

enter image description here

The code I created (1D Toy Example):

%<! Question 76875

clear();
close('all');

% Choosing Odd length for simplicity.
vS1 = [3; 1; 2; 1; 4; 1; 2; 1; 3];
vS2 = [1; 3; 1; 2; 1; 2; 1; 3; 1];

vF1 = [0; 0.25; 0.5; 0.75; 1; 0.75; 0.5; 0.25; 0];
vF2 = [1; 0.75; 0.5; 0.25; 0; 0.25; 0.5; 0.75; 1];


figure();
hStemObj = stem([vS1, vS2], 'filled');
set(hStemObj(2), 'marker', 'd');
title({['Signals at Entry']});
legend({['Signal #1'], ['Signal #2']});

figure();
hStemObj = stem([vF1, vF2], 'filled');
set(hStemObj(2), 'marker', 'd');
title({['Filters']});
legend({['Filter at Stage #1'], ['Filter at Stage #2']});

vS1F1 = vS1 .* vF1;
vS1F1 = SpectralActivation(vS1F1, 1); %<! Apply activation (Sigmoid)
vS1F1 = SpectralPooling(vS1F1, 3); %<! Remove 1 from each side

vS2F1 = vS2 .* vF1;
vS2F1 = SpectralActivation(vS2F1, 1); %<! Apply activation (Sigmoid)
vS2F1 = SpectralPooling(vS2F1, 3); %<! Remove 1 from each side

figure();
hStemObj = stem([vS1F1, vS2F1], 'filled');
set(hStemObj(2), 'marker', 'd');
title({['Signals After First Filter + Spectral Activation + Spectral Pooling']});
legend({['Signal #1'], ['Signal #2']});

vS1F2 = vS1F1 .* vF2;
vS1F2 = SpectralActivation(vS1F2, 1); %<! Apply activation (Sigmoid)
vS1F2 = SpectralPooling(vS1F2, 2); %<! Remove 1 from each side

vS2F2 = vS2F1 .* vF1;
vS2F2 = SpectralActivation(vS2F2, 1); %<! Apply activation (Sigmoid)
vS2F2 = SpectralPooling(vS2F2, 2); %<! Remove 1 from each side

figure();
hStemObj = stem([vS1F2, vS2F2], 'filled');
set(hStemObj(2), 'marker', 'd');
title({['Signals After Second Filter + Spectral Activation + Spectral Pooling']});
legend({['Signal #1'], ['Signal #2']});


figure();
hStemObj = stem([vS1F2 ./ vS1, vS2F2 ./ vS2], 'filled');
set(hStemObj(2), 'marker', 'd');
title({['Equivalent Filter (Output ./ Input)']});
legend({['Signal #1'], ['Signal #2']});


function [ vO ] = SpectralPooling( vI, kernelRadius )

    numSamples  = size(vI, 1);
    centerIdx   = ceil(numSamples / 2); %<! Assuming Odd
    
    vIdx = (centerIdx - kernelRadius):(centerIdx + kernelRadius);
    
    vO = zeros(numSamples, 1);
    vO(vIdx) = vI(vIdx);

end

function [ vO ] = SpectralActivation( vI, sigSlope )

    % Normalization: Non Linear Operation
    vO = (vI - mean(vI)) / std(vI);
    % In paper approximated by a linear function
    vO = 1 ./ (1 + exp(-sigSlope * vO));

end

So we have 2 input signals (Imagine this is their spectrum):

enter image description here

I chose 2 filters:

enter image description here

In practice the filters are learned. Hence they don't have any special meaning.

Now, let's see the result of the 2 signals when they go through Filter 1 (Since we're in frequency domain the filter is element wise multiplication) + Spectral Activation (Normalization + Sigmoid) + Spectral Pooling:

enter image description here

We can see that indeed only the center part of the signal is kept. Yet the values of each are not proportional. We'll have a deeper look after the next stage - Filter 2 + Spectral Activation (Normalization + Sigmoid) + Spectral Pooling:

enter image description here

Now, we can see even more narrower yet we can see each signal was filtered completely different. This is due to the non linear steps.

Let's do one more thing. If this could be replaced just by an LPF (With finite support, so it would do some "Pooling") then the ratio of the output to input of both signals would be the same (This what would have happened in an LTI system). Let's examine this ratio:

enter image description here

We can see that each signal was processed completely differently.
So, indeed as written to begin with, though the system discard high frequencies, it alters the remaining frequencies in a non linear manner. Hence it can not be replaced by a multiplication by a rectangular in the frequency domain.

$\endgroup$
3
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Peter K.
    Aug 27 at 20:17
  • 1
    $\begingroup$ @PeterK., I think in this case the comments are crucial part of the answer and the question. I'd be happy if you could revert that. $\endgroup$
    – Royi
    Aug 27 at 20:40
  • $\begingroup$ Unfortunately, I don't see an option for that. $\endgroup$
    – Peter K.
    Aug 28 at 19:06
0
$\begingroup$

Update: after a closer look, activation follows pooling, not precedes; this is much more explicit in the original paper. Furthermore, the cited paper uses linear approximations of nonlinearities (but not the original paper) to speed up compute.

The answer to OP's question is thus yes, the input's frequencies are discarded directly at the first layer's pooling.

Answer if nonlinearity precedes pooling

Wouldn't this be equivalent to discarding all those frequencies in the input layer?

Yes, but not directly. The idea is, the nonlinearity before the pooling first remaps input's frequencies, shifting some lows to highs and vice versa. Thus discarding e.g. near Nyquist isn't same as discarding input's near Nyquist.

This is particularly advantageous for images as they're predominantly low frequency - which maximizes information per sample preserved (as shown in the vs Max comparison). Another important distinction is in synthesis vs analysis information; a transform can prioritize latter on expense of former to benefit e.g. classification. Since weights are learned, this is automated.

Example

Idea's very similar to wavelet scattering:

  1. convolve with a filterbank tiling all frequencies
  2. take modulus
  3. convolve with lowpass

Complex modulus globally shifts all frequencies to lower. Lowpassing then loses much less information than we would without the modulus. Royi's answer shows another example.

Difference with the pooling paper is, the convolution kernels are learned - so one explanation is, they're learned such that the resulting representation is predominantly low frequency, thus pooling loses minimal information. If the task is compression, synthesis information is prioritized - if classification, analysis.

Discussion

Below was collapsed into chat but highlights an important disagreement with the other answer.

OverLordGoldDragon @Royi Before or after makes all the difference. If a non-linearity precedes pooling, it rearranges input's frequencies in a non-linear manner, thus there's no longer an LPF equivalent - is this not correct? To contrary, the normalization is merely scalar subtraction and division, which makes no difference (just dc removal and constant bin scaling - and even that happens after pooling in the paper). The paper's scheme can be replaced with LPF of input.

Royi @OverLordGoldDragon, Not at all. Take my code and try it with the order being reversed. Even without normalization, just with pure sigmoid where some values meet its edges you will get a result which ca not be replicated with LPF.

OverLordGoldDragon @ Royi Output before the sigmoid will perfectly replicate with an LPF - what's after pooling is immaterial. The question is about the effect on input's frequencies; if the input is lowpassed directly, then high frequencies are ignored entirely.
Clarifying, it's an LPF on top of filtering with the first weights, so LPF is actually the best case scenario - happening if the weights form an all-pass filter - else there's relative attenuation or incomplete frequency tiling.

Royi @ OverLordGoldDragon When I say filter, chose any filter you may apply on the Spatial Domain. If it is an elements wise multiplication on Frequency you can get the filter on spatial domain. But you won't find one which can replace the whole pipeline because of the non linear operations.

$\endgroup$
1
  • $\begingroup$ There is no question about discarding. This is explicitly said in the part of the question I posted in my answer. They work on a sub rectangle of the frequencies which is $ \beta \times \beta $. The way I understand it, by the drawing of the OP is if we can just replace it with simple linear operation. $\endgroup$
    – Royi
    Aug 26 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.