[PYTHON] Série d'accélération CNN ~ FCNN: Introduction du réseau neuronal convolutif de Fourier ~

Aperçu

Avec l'avènement du réseau neuronal à convolution (CNN), le domaine de la reconnaissance d'image a fait de grands progrès. A partir d'AlexNet, divers réseaux tels que VGGNet et GoogLeNet ont été proposés et ont montré leurs effets. Bien qu'il s'agisse d'un tel CNN, l'inconvénient est que cela prend beaucoup de temps car l'opération de convolution est lourde. Son poids est tel que la couche entièrement connectée peut être complètement ignorée, et si le processus de convolution peut être accéléré, le temps d'apprentissage peut être considérablement réduit. Par conséquent, ce qui attire l'attention est la relation ** convolution dans la région spatiale = produit d'élément dans l'espace fréquentiel **. Dans cet article, j'expliquerai la théorie de base de la convolution dans la gamme de fréquences. Je n'ai trouvé aucun article en japonais, alors je fais de mon mieux pour les lire dans les journaux. Veuillez noter qu'il peut y avoir des erreurs et des malentendus.

Les papiers traités dans cet article sont

• Fast Training of Convolutional Networks through FFTs; Michael Mathieu, Mikael Henaff, Yann LeCun; arXiv:1312.5851v5 [cs.CV] 6 Mar 2014

est.

table des matières

• [Qu'est-ce que le pliage](# Qu'est-ce que le pliage)
• [Convolution linéaire](# convolution linéaire)
• [Pliage circulaire](# Pliage circulant)
• [Comment égaliser la convolution linéaire et la convolution circulaire](# Comment égaliser la convolution linéaire et la convolution circulaire)
• [Pliage avec CNN](Pliage avec #cnn)
• [Vers la zone de fréquence](#To zone de fréquence)
• [2.2 Algorithme](# 22-Algorithme)
• [2.3 Implémentation et Calcul Spatial](# 23-Implémentation et Calcul Spatial)
• [3 Experiment](# 3-Experiment)
• [4 À propos du futur](# 4-À propos du futur)
• [Essayez de mettre en œuvre?](# Essayez de mettre en œuvre)
• Annexe
• [Strict convolution and CNN](# Strict convolution and cnn)
• [Algorithme FFT Cooley-Turquie](algorithme # cooley-turkey-fft)

Qu'est-ce que le pliage

Afin de bien comprendre la convolution dans la région fréquentielle, reconsidérons d'abord la convolution dans la région spatiale. Il existe deux types de traitement par convolution, appelés respectivement ** convolution linéaire (convolution droite) ** et ** convolution circulaire (convolution circulaire) **. Tout d'abord, je vais expliquer ces deux.

Je présenterai les variables qui seront utilisées par la suite en premier.

• $ I \ cdots $ Taille d'entrée
• Taille du filtre $ F \ cdots $
• $ O \ cdots $ Taille de sortie

Convolution linéaire

La convolution linéaire est le processus de convolution illustré dans la figure ci-dessous. De cette façon, on a l'impression de partir du point où le bord droit du filtre et le bord gauche de l'entrée se chevauchent, et de se terminer lors du passage. Je ne le posterai pas car je n'ai pas besoin d'une formule mathématique, mais comprenez bien que cela fonctionne comme ça. Et notez que cette convolution linéaire ** l'entrée n'est pas une fonction périodique **.

En outre, l'expression relationnelle suivante est valable pour la taille.

O = I + F - 1

Dans GIF, $ I = 9 $ et $ F = 3 $, donc la taille de sortie est $ O = 9 + 3-1 = 11 $.

Convolution circulaire

La convolution circulaire est le processus de convolution illustré dans la figure ci-dessous. C'est comme partir du point où le bord gauche du filtre et le bord gauche de l'entrée se chevauchent, et se terminer lorsque le bord droit du filtre et le bord droit de l'entrée se chevauchent. C'est exactement la différence avec la convolution linéaire, auquel cas l'entrée ** doit être une fonction périodique **. Je pense qu'il est normal de comprendre que l'entrée n'est pas nécessaire car l'entrée est une fonction périodique pour chacune des deux extrémités représentées par le GIF de convolution linéaire (je pense que c'est strictement différent, mais la rigueur n'est pas particulièrement requise. ).

En outre, l'expression relationnelle suivante est valable pour la taille.

O = I - F + 1

Dans GIF, $ I = 9 $ et $ F = 3 $, donc la taille de sortie est $ O = 9 --3 + 1 = 7 $.

Comment égaliser les convolutions linéaires et circulaires

Pour que les convolutions linéaires et circulaires soient égales, les deux extrémités de l'entrée doivent être remplies de zéro de sorte que $ O = I + F -1 $. Vous pouvez voir que le résultat de sortie est égal à la convolution linéaire.

Pliage en CNN

Maintenant, quelle est l'opération de convolution dans CNN? Pensez d'un point de vue d'entrée.

Les données entrées dans le CNN sont généralement une image, et très probablement cette image est une photo. Cela signifie que l'on peut s'attendre à ce que l'image ne présente pas de périodicité à moins que l'image ne soit reconnue comme un motif. Cela signifie que l'entrée est apériodique, donc ** CNN doit faire une convolution linéaire **.

Mais il est encore trop tôt pour conclure cela. Veuillez consulter la figure ci-dessous. Cela montre comment le CNN est plié. Comme vous pouvez le voir, le filtre ne passe pas par l'image d'entrée, donc ** dans cette figure, nous faisons une convolution circulaire **. Cela signifie que ** les informations ne peuvent pas être obtenues correctement ** à partir de l'opération de convolution. Cependant, en supposant que ** les images d'entrée sont périodiquement disposées verticalement et horizontalement (chevauchant $ F -1 $) **, cette convolution peut être considérée comme correcte.

J'aimerais dire: "Lequel est-ce après tout?", Mais j'ai encore quelque chose à penser. C'est du ** padding **, qui est une technologie essentielle pour CNN. Il n'y en a pas assez dans cette figure, mais ** la convolution circulaire peut être égale à la convolution linéaire ** si vous en complétez autant que vous en avez besoin. Ensuite, si le traitement appelé remplissage est appliqué correctement à l'image d'entrée, une convolution linéaire peut être effectuée, et ** les informations peuvent être obtenues correctement à partir de l'opération de convolution **. Dans article que j'ai écrit avant, le rôle du rembourrage est de "maintenir la taille" et "d'obtenir toutes les informations sur le bord". C'est tout. (Au moment d'écrire ces lignes, je n'y pensais pas autant que la rosée, mais lol)

Maintenant, ce processus de remplissage rend la discussion encore plus compliquée. Compte tenu de la foulée propre au pliage dans CNN, encore plus ... Ce remplissage est souvent utilisé ** pour empêcher (ou réduire) la dégradation de la taille de l'image de sortie due à la convolution dans CNN **. Par conséquent, la largeur du rembourrage augmente ou diminue en fonction de la foulée, donc je ne veux pas du tout faire de la convolution circulaire une convolution linéaire. Ensuite, la largeur du rembourrage sera excessive ou insuffisante. Il n'y a pas de problème si la largeur de remplissage est grande, mais si elle est petite, la conversion en convolution circulaire $ \ rightarrow $ convolution linéaire ne sera pas effectuée correctement.

Après tout, la conclusion est ** "La convolution dans CNN est entre la convolution linéaire / circulaire" **. Il semble que "je tire beaucoup et la conclusion est ambiguë", mais cela ne peut pas être aidé parce que je ne peux que le dire. Quand il s'agit de discussions rigoureuses en théorie, c'est en fait différent des hypothèses.

Telle est la prémisse. De là, nous allons enfin passer à la théorie de la gamme de fréquences. Au fait, si vous vous demandez "Quelle est la rigueur mathématique?", Veuillez consulter [Annexe](#Strict convolution et cnn).

Vers la gamme de fréquences

À propos, l'histoire à ce jour est un résumé des résultats de mes recherches ici et là, ce que j'ai jugé nécessaire en lisant l'article. C'est toujours doux, mais je pense que ce n'est pas grave si vous avez cela en tête. Il est maintenant temps d'entrer dans le contenu de l'article. La rétropropagation dans le papier 2.1 décrit uniquement la partie qui compare le CNN dans la région spatiale avec le CNN dans la région de fréquence, donc je vais le couper et lire à partir de 2.2. À propos, l'article n'est pas traduit en japonais mais traduit et ajouté. Les chiffres de cette section sont tirés du document.

2.2 Algorithme

Il est bien connu que l'opération de convolution dans le domaine spatial est équivalente au produit d'élément dans le domaine de Fourier (fréquence) **. Par conséquent, l'opération de convolution dans la région spatiale utilise le convertisseur de Fourier $ \ mathcal {F} $ et son opération inverse $ \ mathcal {F} ^ {-1} $.

f * g = \mathcal{F}^{-1}\big(\mathcal{F}_f(k) \odot \mathcal{F}_g(k)\big)

Peut être exprimé comme. Cependant, le symbole $ * $ représente l'opération de convolution dans la région spatiale, et le symbole $ \ otimes $ représente le produit d'élément dans l'opération de matrice. Il convient de noter qu'en raison de la nature du produit de l'élément, ** $ f et g $ doivent être de taille proche (ou plutôt de taille égale) ** pour effectuer les opérations d'équation ci-dessus. Cependant, en général, l'entrée (taille $ I_h \ fois I_w $) et le filtre (taille $ F_h \ fois F_w $) sont des tailles complètement différentes. Par conséquent, lors de sa mise en œuvre, un remplissage est nécessaire pour correspondre à la taille de l'entrée et du filtre. (Peut être coupé) Pour simplifier la discussion, soit $ I_h = I_w = I $ et $ F_h = F_w = F $. Nous allons également dimensionner la sortie à $ O_h \ times O_w $, qui est également représentée par $ O_h = O_w = O $. Définissez également le nombre de canaux d'entrée sur $ C $, le nombre de filtres sur $ M $ et la taille du mini-lot sur $ B $. Le montant du calcul de l'opération de convolution dans la zone spatiale n'est pas de remplissage, pas de 1 $

O^2 F^2 \quad (\because O = I - F + 1)

Ce sera. Si la largeur du rembourrage est $ 2p $ et la foulée est $ s $

O^2 F^2 \quad \left(\because O = \left\lceil \cfrac{I - F + 2p}{s} \right\rceil + 1 \right)

n'est-ce pas.

En revanche, la quantité de calcul dans la région de Fourier est $ 2C_ {order} O ^ 2 \ log {O} $ lorsque la transformation de Fourier est effectuée par ** Transformation de Fourier rapide (FFT) **, qui est le produit de l'élément. Le montant de calcul pour est exprimé comme ** Notez qu'il s'agit d'une opération complexe ** et $ 4O ^ 2 $. $ C_ {order} $ est une constante. Par conséquent, la somme de $ 2C_ {ordre} O ^ 2 \ log {O} + 4O ^ 2 $ est la quantité de calcul pour l'opération de convolution dans la région de Fourier. Il semble que $ O = I $ dans le papier.

Chaque canal d'entrée et chaque filtre sont indépendants, vous n'avez donc besoin d'effectuer qu'une transformée de Fourier sur chacun. L'efficacité de l'apprentissage peut être réduite pour certaines convolutions, mais la capacité de réutiliser efficacement les FFT peut l'emporter sur la surcharge d'une efficacité réduite.

Trouver la quantité de calcul pour la propagation avant et arrière rend la supériorité des opérations de convolution dans la région de Fourier plus apparente.

Il convient de noter que $ ici est $ O = I --F + 1 $ ou $ O = \ left \ lceil \ cfrac {I --F + 2p} {s dans les régions spatiale et fréquentielle. } \ right \ rceil + 1 $$ signifie qu'il est calculé. Notez que ** est différent de la discussion précédente, en particulier dans la région de Fourier **. Probablement, il a été arrangé pour faire une comparaison correcte du montant du calcul.

Comme on peut le lire dans ce tableau, ** la quantité de calcul dans la région spatiale est représentée par le produit de 5 termes **, tandis que la quantité de calcul dans la région de Fourier est ** le produit de jusqu'à 4 termes **. Cela signifie qu'il est représenté. En gros, l'ordre de la quantité de calcul dans le domaine spatial est le 5ème ordre (plus précisément le 7ème ordre), et dans le domaine de Fourier, il est le 4ème ordre (plus précisément le 5ème ordre). Calculons réellement et voyons quel effet cela aura sur la propagation vers l'avant.

B = 128 \quad C = 96 \\
M = 256 \quad F = 7

En supposant que $ I = 16, 64 $ est calculé, $ O = I --F + 1 = 10, 58 $, donc à propos de la zone spatiale

BCMO^2F^2 = 128 \times 96 \times 256 \times 10^2 \times 7^2 = 15,414,067,200 \simeq 15,4 milliards\\
BCMO^2F^2 = 128 \times 96 \times 256 \times 58^2 \times 7^2 = 518,529,220,608 \simeq 518,5 milliards

A propos de la région de Fourier

2C_{order}I^2(BM + BC + CM)\log{I} + 4BCMI^2 = 2 \times 16 \times 16^2 \times (128 \times 256 + 128 \times 96 + 96 \times 256) \log{16} + 4 \times 128 \times 96 \times 256 \times 16^2 = 1,581,554,875.654148 + 3,221,225,472 = 4,802,780,347.654148 \simeq 4,8 milliards\\
2C_{order}I^2(BM + BC + CM)\log{I} + 4BCMI^2 = 2 \times 16 \times 64^2 \times (128 \times 256 + 128 \times 96 + 96 \times 256) \log{64} + 4 \times 128 \times 96 \times 256 \times 64^2 = 37,957,317,015.69955 + 51,539,607,552 = 89,496,924,567.69955 \simeq 89,5 milliards

• Puisque le montant de $ C_ {commande} $ calculé n'est pas indiqué dans l'article, nous avons adopté $ C_ {commande} = 16 $, ce qui correspond approximativement au graphique.

Avec ce sentiment, la différence s'élargira à mesure que la taille de l'entrée augmente.

2.3 Implémentation et calcul spatial

Bien que l'algorithme soit une opération de convolution très simple dans la région de Fourier, il existe deux problèmes majeurs de mise en œuvre.

1. La FFT implémentée dans CUDA, qui est compatible avec les GPU actuels, principalement les GPU NVIDIA, n'est pas optimale pour cet algorithme car elle est optimisée pour un nombre limité de FFT avec de grandes entrées.
2. Une grande quantité de zone mémoire (quantité de calcul spatial) est nécessaire pour contenir le filtre transformé de Fourier.

Les optimisations et contre-mesures suivantes ont été proposées pour chaque problème.

1. Implémentation de [Algorithme FFT Cooley-Turquie](algorithme # cooleyturkey-fft) --Peut être parallélisé dans la direction du canal mini-batch

• À l'origine, la FFT 2D peut être parallélisée dans les directions des lignes et des colonnes.
• À partir de ce qui précède, il est possible d'effectuer efficacement et rapidement une transformée de Fourier sur une petite et une grande quantité d'entrée avec cet algorithme.

2. Sauvegarde de la mémoire en réutilisant (écrasant) la mémoire utilisée pour chaque convolution. De plus, en utilisant le fait que la transformée de Fourier de l'entrée de valeur réelle devient une matrice symétrique, seule la matrice triangulaire inférieure (ou matrice triangulaire supérieure) est conservée. --Re-FFT est nécessaire lors du calcul de la rétropropagation en raison de la réutilisation de la mémoire --La quantité de mémoire qui doit être conservée en la maintenant dans une matrice triangulaire est $ X ^ 2 \ Rightarrow \ frac {X (X + 1)} {2} $

C'est la fin de l'aspect théorique. Le reste, ce sont les résultats expérimentaux. Je voulais que vous signaliez un peu plus concrètement quel type de calcul est en cours ... Certaines questions se sont posées lorsque j'ai essayé de l'implémenter ... Eh bien, ce domaine est similaire à un CNN normal Je me demande s'il doit se comporter comme ça.

3 Expérience

L'expérience a été menée à l'aide du GPU GeForce GTX Titan de NVIDIA pour comparer l'implémentation du GPU CUDA Conv avec l'environnement d'apprentissage automatique Torch 7. La précision obtenue dans l'expérience n'est pas répertoriée, mais il semble qu'elle se situait dans la plage de tolérance.

Modifiez la taille du filtre, la taille d'entrée et la taille du mini-lot d'un CNN, en vous concentrant sur la deuxième couche où le nombre de canaux d'entrée est $ C = 96 $ et le nombre de canaux de sortie (c'est-à-dire le nombre de filtres) est $ M = 256 . Les résultats des expériences sont présentés dans la figure ci-dessous.  Dans la plupart des cas, l'opération de convolution dans la région de Fourier s'est avérée rapide. Un avantage plus significatif est vu, en particulier dans $ \ cfrac {\ partial L} {\ partial y_M} * x_C $$, qui a une grande quantité de calcul de temps. Il est fort probable que cela soit dû au fait que vous utilisez un filtre avec une grande taille de filtre. De plus, avant d'appliquer FFT, ** le filtre est complété à la même taille que l'entrée **, vous pouvez donc utiliser un filtre plus grand.

• En ce qui concerne cette considération, de nombreux CNN actuels utilisent une petite taille de filtre du point de vue de l'économie de mémoire. Certes, si l'implémentation FCNN reste telle qu'elle est, elle consommera de toute façon une grande quantité de mémoire, il peut donc être difficile d'utiliser un filtre plus grand. Au fait, l'implémentation telle qu'elle est est peu susceptible d'être utilisée. Une autre technologie d'économie de mémoire a été fermement établie. J'écrirai un autre article à ce sujet.

Ensuite, pour CNN, qui se concentrait uniquement sur la 2ème couche, cette fois, en se concentrant sur les 1ère à 5ème couches, le résultat de l'expérience en modifiant la taille du mini-lot $ B $ est montré dans la figure ci-dessous. .. Aucune donnée n'a été collectée car le gradient de la couche d'entrée vers l'entrée n'a pas besoin d'être calculé. Dans la plupart des cas, on peut lire qu'il possède la vitesse la plus rapide ou la deuxième plus rapide. De plus, on peut dire que le FCNN est efficace dans presque tous les cas car il est le plus rapide au total. Cela suggère également que la propagation vers l'avant est assez rapide, ce qui ** maximise ses avantages, comme lors de la réalisation d'inférences à l'aide d'un réseau formé **.

Enfin, c'est le résultat expérimental lorsque la couche de pooling et la couche entièrement connectée sont ajoutées au CNN ci-dessus. Cette expérience vise à voir si les détails d'implémentation tels que le remplissage et l'accès à la mémoire changent les performances. Le FCNN a également prouvé sa supériorité dans cette expérience.

4 À propos de l'avenir

Je vais le laisser dans une balle.

• Explorer les moyens d'apprendre les filtres directement dans la région de Fourier
• Explorer comment utiliser des fonctions non linéaires dans la région de Fourier
• Cela élimine le besoin de conversion inverse et la rend plus rapide.
• Dans l'implémentation actuelle, l'image d'entrée doit être rembourrée à la taille d'une puissance de 2, alors améliorez-la.
• Enquêter sur l'effet de l'augmentation de la taille du filtre

Ce qui précède est le contenu de l'article. C'est un algorithme simple mais puissant ~ Il semble que diverses études aient été menées depuis.

Voulez-vous le mettre en œuvre?

Je voudrais l'implémenter ... mais j'ai quelques doutes.

-Est-il nécessaire d'effectuer FFT / IFFT avant et après l'opération de convolution? --Dans le diagramme schématique du papier, le nombre de canaux d'entrée et le nombre de canaux de sortie sont les mêmes, mais le nombre de canaux de sortie de la couche de convolution dans la zone spatiale doit dépendre du nombre de filtres. De plus, quel que soit le canal auquel vous correspondez, la façon de l'aligner sur cette dimension est un problème.

Chacun d'eux n'est pas spécifié dans l'article ... Ça devrait l'être, mais on peut le lire subtilement, n'est-ce pas? Par exemple, dans [4 About the future](# 4-About the future)

--Explorez les moyens d'apprendre les filtres directement dans la région de Fourier

• Explorer comment utiliser des fonctions non linéaires dans la région de Fourier
• Cela élimine le besoin de conversion inverse et la rend plus rapide.

Parce que cela dit quelque chose comme, il semble que FFT / IFFT se fait uniquement avant et après l'opération du produit matriciel, ou le nombre de canaux change de la même manière que CNN dans le dernier tableau de l'expérience, je n'écris pas directement Cependant, il y a une description qui semble être le cas.

De plus, j'ai cherché et lu quelques articles ultérieurs, mais il y avait aussi une description de la façon de faire une FFT une seule fois et de tout exécuter dans la région de Fourier, donc cette région également. Je ne vais pas l'implémenter cette fois car je n'ai pas assez étudié l'inclure. Je ne peux pas nier le manque de compréhension de la transformation de Fourier.

appendice

En prime, je posterai des choses mathématiques.

Convolution stricte et CNN

Considérons la convolution suivante de la matrice d'entrée $ \ boldsymbol {A} $ et de la matrice de filtre $ \ boldsymbol {W} $. Cependant, pas de rembourrage, foulée 1 $.

• Je suis désolé si l'index des éléments suivants de la matrice est erroné.

\boldsymbol{A} = \left( \begin{array}[ccc]
  aa_{1, 1} & a_{1, 2} & a_{1, 3} & a_{1, 4} \\
  a_{2, 1} & a_{2, 2} & a_{2, 3} & a_{2, 4} \\
  a_{3, 1} & a_{3, 2} & a_{3, 3} & a_{3, 4} \\
  a_{4, 1} & a_{4, 2} & a_{4, 3} & a_{4, 4}
\end{array} \right) \qquad
\boldsymbol{W} = \left( \begin{array}[ccc]
  ww_{1, 1} & w_{1, 2} \\
  w_{2, 1} & w_{2, 2} \\
\end{array} \right)

Le résultat de la convolution est le suivant.

\begin{align}
  \boldsymbol{AW} &= \left( \begin{array}[ccc]
    aa_{1, 1}w_{1, 1} + a_{1, 2}w_{1, 2} + a_{2, 1}w_{2, 1} + a_{2, 2}w_{2, 2}
  & a_{1, 2}w_{1, 1} + a_{1, 3}w_{1, 2} + a_{2, 2}w_{2, 1} + a_{2, 3}w_{2, 2}
  & a_{1, 3}w_{1, 1} + a_{1, 4}w_{1, 2} +   a_{2, 3}w_{2, 1} + a_{2, 4}w_{2, 2} \\
    a_{2, 1}w_{1, 1} + a_{2, 2}w_{1, 2} + a_{3, 1}w_{2, 1} + a_{3, 2}w_{2, 2}
  & a_{2, 2}w_{1, 1} + a_{2, 3}w_{1, 2} + a_{3, 2}w_{2, 1} + a_{2, 3}w_{2, 2}
  & a_{2, 3}w_{1, 1} + a_{2, 4}w_{1, 2} + a_{3, 3}w_{2, 1} + a_{2, 4}w_{2, 2} \\
    a_{3, 1}w_{1, 1} + a_{3, 2}w_{1, 2} + a_{4, 1}w_{2, 1} + a_{4, 2}w_{2, 2}
  & a_{3, 2}w_{1, 1} + a_{3, 3}w_{1, 2} + a_{4, 2}w_{2, 1} + a_{4, 3}w_{2, 2}
  & a_{3, 3}w_{1, 1} + a_{3, 4}w_{1, 2} + a_{4, 3}w_{2, 1} + a_{4, 4}w_{2, 2}
  \end{array} \right) \\
  &= \left( \begin{array}[ccc]
    s\displaystyle\sum_{k=1}^{2}{\displaystyle\sum_{l=1}^{2}{a_{k, l}w_{k, l}}}
  & \displaystyle\sum_{k=1}^{2}{\displaystyle\sum_{l=1}^{2}{a_{k, l+1}w_{k, l}}}
  & \displaystyle\sum_{k=1}^{2}{\displaystyle\sum_{l=1}^{2}{a_{k, l+2}w_{k, l}}} \\
    \displaystyle\sum_{k=1}^{2}{\displaystyle\sum_{l=1}^{2}{a_{k+1, l}w_{k, l}}} 
  & \displaystyle\sum_{k=1}^{2}{\displaystyle\sum_{l=1}^{2}{a_{k+1, l+1}w_{k, l}}}
  & \displaystyle\sum_{k=1}^{2}{\displaystyle\sum_{l=1}^{2}{a_{k+1, l+2}w_{k, l}}} \\
    \displaystyle\sum_{k=1}^{2}{\displaystyle\sum_{l=1}^{2}{a_{k+2, l}w_{k, l}}}
  & \displaystyle\sum_{k=1}^{2}{\displaystyle\sum_{l=1}^{2}{a_{k+2, l+1}w_{k, l}}}
  & \displaystyle\sum_{k=1}^{2}{\displaystyle\sum_{l=1}^{2}{a_{k+2, l+2}w_{k, l}}}
  \end{array} \right)
\end{align}

Vous pouvez voir la régularité. Généralisons-le. Lorsque la taille du filtre est $ F_h \ fois F_w $, le $ (i, j) $ composant $ o_ {i, j} $ de la sortie est

o_{i, j} = \displaystyle\sum_{k=1}^{F_h}{\displaystyle\sum_{l=1}^{F_w}{a_{i+k-1, j+l-1}w_{k, l}}}

Peut être écrit comme. Veuillez noter que l'ordre d'ajout de l'indice a été modifié pour plus tard.

Il s'agit de l'opération de convolution dans CNN. C'est un pliage circulaire. À propos, mathématiquement, l'opération de convolution discrète bidimensionnelle est exprimée par l'équation suivante.

(g * f)_{i, j} = o_{i, j} = \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{i-k+1, j-l+1}g_{k, l}}}

D'une manière ou d'une autre, $ f $ est entré, $ g $ est considéré comme un filtre et l'ordre est inversé par rapport à la formule générale. De plus, $ k et l $ prennent toutes les valeurs pour lesquelles l'index est valide. À ce stade, ceux qui pensent «cela?» Sont vifs. Si cela est écrit dans une matrice (les tailles seront les mêmes pour chaque CNN)

\begin{align}
  \boldsymbol{g*f} &=　\left( \begin{array}[ccc]
    s\displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{2-k, 2-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{2-k, 3-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{2-k, 4-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{2-k, 5-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{2-k, 6-l}g_{k, l}}} \\
    \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{3-k, 2-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{3-k, 3-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{3-k, 4-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{3-k, 5-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{3-k, 6-l}g_{k, l}}} \\
  \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{4-k, 2-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{4-k, 3-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{4-k, 4-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{4-k, 5-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{4-k, 6-l}g_{k, l}}} \\
  \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{5-k, 2-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{5-k, 3-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{5-k, 4-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{5-k, 5-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{5-k, 6-l}g_{k, l}}} \\
\displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{6-k, 2-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{6-k, 3-l}g_{k, l}}}
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{6-k, 4-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{6-k, 5-l}g_{k, l}}} 
  & \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{6-k, 6-l}g_{k, l}}} \\
  \end{array} \right) \\
  &= \left( \begin{array}[ccccc]
    ff_{1, 1}g_{1, 1}
  & f_{1, 2}g_{1, 1} + f_{1, 1}g_{1, 2}
  & f_{1, 3}g_{1, 1} + f_{1, 2}g_{1, 2}
  & f_{1, 4}g_{1, 1} + f_{1, 3}g_{1, 2}
  & f_{1, 4}g_{1, 2} \\
    f_{2, 1}g_{1, 1} + f_{1, 1}g_{2, 1}
  & f_{2, 2}g_{1, 1} + f_{2, 1}g_{1, 2} + f_{1, 2}g_{2, 1} + f_{1, 1}g_{2, 2}
  & f_{2, 3}g_{1, 1} + f_{2, 2}g_{1, 2} + f_{1, 3}g_{2, 1} + f_{1, 2}g_{2, 2}
  & f_{2, 4}g_{1, 1} + f_{2, 3}g_{1, 2} + f_{1, 4}g_{2, 1} + f_{1, 3}g_{2, 2}
  & f_{2, 4}g_{1, 2} + f_{1, 4}g_{2, 2} \\
    f_{3, 1}g_{1, 1} + f_{2, 1}g_{2, 1}
  & f_{3, 2}g_{1, 1} + f_{3, 1}g_{1, 2} + f_{2, 2}g_{2, 1} + f_{2, 1}g_{2, 2}
  & f_{3, 3}g_{1, 1} + f_{3, 2}g_{1, 2} + f_{2, 3}g_{2, 1} + f_{2, 2}g_{2, 2}
  & f_{3, 4}g_{1, 1} + f_{3, 3}g_{1, 2} + f_{2, 4}g_{2, 1} + f_{2, 3}g_{2, 2}
  & f_{3, 4}g_{1, 2} + f_{2, 4}g_{2, 2} \\
    f_{4, 1}g_{1, 1} + f_{3, 1}g_{2, 1}
  & f_{4, 2}g_{1, 1} + f_{4, 1}g_{1, 2} + f_{3, 2}g_{2, 1} + f_{3, 1}g_{2, 2}
  & f_{4, 3}g_{1, 1} + f_{4, 2}g_{1, 2} + f_{3, 3}g_{2, 1} + f_{3, 2}g_{2, 2}
  & f_{4, 4}g_{1, 1} + f_{4, 3}g_{1, 2} + f_{3, 4}g_{2, 1} + f_{3, 3}g_{2, 2}
  & f_{4, 4}g_{1, 2} + f_{3, 4}g_{2, 2} \\
    f_{4, 1}g_{2, 1}
  & f_{4, 2}g_{2, 1} + f_{4, 1}g_{2, 2}
  & f_{4, 3}g_{2, 1} + f_{4, 2}g_{2, 2}
  & f_{4, 4}g_{2, 1} + f_{4, 3}g_{2, 2}
  & f_{4, 4}g_{2, 2}
  \end{array} \right) \\
\end{align}

Ce sera.

Comme vous pouvez le voir en un coup d'œil, la convolution dans CNN et la convolution définie en mathématiques sont différentes. Cette différence est la différence entre la convolution circulaire et la convolution linéaire ... ** mais elle est en fait différente **. Même si vous appliquez ** padding, ce ne sera pas le même ** que dans [Comment égaliser la convolution linéaire et la convolution circulaire](# Comment égaliser la convolution linéaire et la convolution circulaire) présenté précédemment **. Je vais vraiment l'essayer.

\boldsymbol{A} = \left( \begin{array}[cccccc]
  00 & 0 & 0 & 0 & 0 & 0 \\
  0& a_{1, 1} & a_{1, 2} & a_{1, 3} & a_{1, 4} & 0 \\
  0 & a_{2, 1} & a_{2, 2} & a_{2, 3} & a_{2, 4} & 0 \\
  0 & a_{3, 1} & a_{3, 2} & a_{3, 3} & a_{3, 4} & 0 \\
  0 & a_{4, 1} & a_{4, 2} & a_{4, 3} & a_{4, 4} & 0 \\
  0 & 0 & 0 & 0 & 0 & 0
\end{array} \right)

Comme

\boldsymbol{AW} = \left( \begin{array}[ccccc]
    aa_{1, 1}w_{2, 2}
  & a_{1, 1}w_{2, 1} + a_{1, 2}w_{2, 2}
  & a_{1, 2}w_{2, 1} + a_{1, 3}w_{2, 2}
  & a_{1, 3}w_{2, 1} + a_{1, 4}w_{2, 2} 
  & a_{1, 4}w_{2, 1} \\
    a_{1, 1}w_{1, 2} + a_{2, 1}w_{2, 2}
  & a_{1, 1}w_{1, 1} + a_{1, 2}w_{1, 2} + a_{2, 1}w_{2, 1} + a_{2, 2}w_{2, 2}
  & a_{1, 2}w_{1, 1} + a_{1, 3}w_{1, 2} + a_{2, 2}w_{2, 1} + a_{2, 3}w_{2, 2}
  & a_{1, 3}w_{1, 1} + a_{1, 4}w_{1, 2} + a_{2, 3}w_{2, 1} + a_{2, 4}w_{2, 2}
  & a_{1, 4}w_{1, 1} + a_{2, 4}w_{2, 1} \\
    a_{2, 1}w_{1, 2} + a_{3, 1}w_{2, 2}
  & a_{2, 1}w_{1, 1} + a_{2, 2}w_{1, 2} + a_{3, 1}w_{2, 1} + a_{3, 2}w_{2, 2}
  & a_{2, 2}w_{1, 1} + a_{2, 3}w_{1, 2} + a_{3, 2}w_{2, 1} + a_{3, 3}w_{2, 2}
  & a_{2, 3}w_{1, 1} + a_{2, 4}w_{1, 2} + a_{3, 3}w_{2, 1} + a_{3, 4}w_{2, 2}
  & a_{2, 4}w_{1, 1} + a_{3, 4}w_{2, 1} \\
    a_{3, 1}w_{1, 2} + a_{4, 1}w_{2, 2}
  & a_{3, 1}w_{1, 1} + a_{3, 2}w_{1, 2} + a_{4, 1}w_{2, 1} + a_{4, 2}w_{2, 2}
  & a_{3, 2}w_{1, 1} + a_{3, 3}w_{1, 2} + a_{4, 2}w_{2, 1} + a_{4, 3}w_{2, 2}
  & a_{3, 3}w_{1, 1} + a_{3, 4}w_{1, 2} + a_{4, 3}w_{2, 1} + a_{4, 4}w_{2, 2}
  & a_{3, 4}w_{1, 1} + a_{4, 4}w_{2, 1} \\
    a_{4, 1}w_{1, 2}
  & a_{4, 1}w_{1, 1} + a_{4, 2}w_{1, 2}
  & a_{4, 2}w_{1, 1} + a_{4, 3}w_{1, 2}
  & a_{4, 3}w_{1, 1} + a_{4, 4}w_{1, 2}
  & a_{4, 4}w_{1, 1}
\end{array} \right)

Ce sera. Les formes correspondent, le nombre d'ajouts pour chaque élément est le même, mais les index sont différents. Cela signifie que ** la convolution CNN est une opération distincte de la convolution définie mathématiquement **.

C'était un aperçu de la convolution de cet article

Lorsqu'il s'agit de discussions théoriquement rigoureuses, c'est en fait différent des hypothèses.

C'est. En premier lieu ** l'hypothèse selon laquelle "la convolution CNN est une convolution mathématique" était fausse **.

Vous vous demandez peut-être, "Alors à quel type de définition la convolution CNN correspond-elle mathématiquement, ou y a-t-il une définition mathématique correspondante?", Mais il existe une définition mathématique appropriée pour cela. ** Relation mutuelle **.

(g \star f)_{i, j} = o_{i, j} = \displaystyle\sum_{k}{\displaystyle\sum_{l}{f_{i+k-1, j+l-1}g_{k, l}}}

Comme pour la convolution mathématique, $ k et l $ prennent toutes les valeurs qui sont des index valides. Il s'agit d'une définition similaire à la convolution CNN, vous pouvez donc imaginer que vous obtiendrez le même résultat.

Cette intercorrélation calcule la similitude des deux signaux ($ f $ et $ g $). Comme ce n'est pas si pertinent, je laisserai le soin au site de référence pour plus de détails, mais en d'autres termes, le filtre CNN est similaire au modèle spécifique d'entrée. Vous apprenez la fonction de distribution que vous utilisez.

L'important ici est ** de savoir si nous pouvons d'une manière ou d'une autre amener l'intercorrélation dans une convolution mathématique **. Le processus de pliage et de pliage, qui était la norme, n'était pas en fait un pliage, mais il couvrirait la base de la discussion, et il faudrait tout reconsidérer. Les chercheurs qui ont beaucoup réfléchi à l'interprétation des filtres vont pleurer ...

Comparons la convolution mathématique avec la convolution CNN lors du remplissage.

\left( \begin{array}[ccccc]
  ff_{1, 1}g_{1, 1}
& f_{1, 2}g_{1, 1} + f_{1, 1}g_{1, 2}
& f_{1, 3}g_{1, 1} + f_{1, 2}g_{1, 2}
& f_{1, 4}g_{1, 1} + f_{1, 3}g_{1, 2}
& f_{1, 4}g_{1, 2} \\
  f_{2, 1}g_{1, 1} + f_{1, 1}g_{2, 1}
& f_{2, 2}g_{1, 1} + f_{2, 1}g_{1, 2} + f_{1, 2}g_{2, 1} + f_{1, 1}g_{2, 2}
& f_{2, 3}g_{1, 1} + f_{2, 2}g_{1, 2} + f_{1, 3}g_{2, 1} + f_{1, 2}g_{2, 2}
& f_{2, 4}g_{1, 1} + f_{2, 3}g_{1, 2} + f_{1, 4}g_{2, 1} + f_{1, 3}g_{2, 2}
& f_{2, 4}g_{1, 2} + f_{1, 4}g_{2, 2} \\
  f_{3, 1}g_{1, 1} + f_{2, 1}g_{2, 1}
& f_{3, 2}g_{1, 1} + f_{3, 1}g_{1, 2} + f_{2, 2}g_{2, 1} + f_{2, 1}g_{2, 2}
& f_{3, 3}g_{1, 1} + f_{3, 2}g_{1, 2} + f_{2, 3}g_{2, 1} + f_{2, 2}g_{2, 2}
& f_{3, 4}g_{1, 1} + f_{3, 3}g_{1, 2} + f_{2, 4}g_{2, 1} + f_{2, 3}g_{2, 2}
& f_{3, 4}g_{1, 2} + f_{2, 4}g_{2, 2} \\
  f_{4, 1}g_{1, 1} + f_{3, 1}g_{2, 1}
& f_{4, 2}g_{1, 1} + f_{4, 1}g_{1, 2} + f_{3, 2}g_{2, 1} + f_{3, 1}g_{2, 2}
& f_{4, 3}g_{1, 1} + f_{4, 2}g_{1, 2} + f_{3, 3}g_{2, 1} + f_{3, 2}g_{2, 2}
& f_{4, 4}g_{1, 1} + f_{4, 3}g_{1, 2} + f_{3, 4}g_{2, 1} + f_{3, 3}g_{2, 2}
& f_{4, 4}g_{1, 2} + f_{3, 4}g_{2, 2} \\
  f_{4, 1}g_{2, 1}
& f_{4, 2}g_{2, 1} + f_{4, 1}g_{2, 2}
& f_{4, 3}g_{2, 1} + f_{4, 2}g_{2, 2}
& f_{4, 4}g_{2, 1} + f_{4, 3}g_{2, 2}
& f_{4, 4}g_{2, 2}
\end{array} \right) \\
\left( \begin{array}[ccccc]
    aa_{1, 1}w_{2, 2}
  & a_{1, 1}w_{2, 1} + a_{1, 2}w_{2, 2}
  & a_{1, 2}w_{2, 1} + a_{1, 3}w_{2, 2}
  & a_{1, 3}w_{2, 1} + a_{1, 4}w_{2, 2} 
  & a_{1, 4}w_{2, 1} \\
    a_{1, 1}w_{1, 2} + a_{2, 1}w_{2, 2}
  & a_{1, 1}w_{1, 1} + a_{1, 2}w_{1, 2} + a_{2, 1}w_{2, 1} + a_{2, 2}w_{2, 2}
  & a_{1, 2}w_{1, 1} + a_{1, 3}w_{1, 2} + a_{2, 2}w_{2, 1} + a_{2, 3}w_{2, 2}
  & a_{1, 3}w_{1, 1} + a_{1, 4}w_{1, 2} + a_{2, 3}w_{2, 1} + a_{2, 4}w_{2, 2}
  & a_{1, 4}w_{1, 1} + a_{2, 4}w_{2, 1} \\
    a_{2, 1}w_{1, 2} + a_{3, 1}w_{2, 2}
  & a_{2, 1}w_{1, 1} + a_{2, 2}w_{1, 2} + a_{3, 1}w_{2, 1} + a_{3, 2}w_{2, 2}
  & a_{2, 2}w_{1, 1} + a_{2, 3}w_{1, 2} + a_{3, 2}w_{2, 1} + a_{3, 3}w_{2, 2}
  & a_{2, 3}w_{1, 1} + a_{2, 4}w_{1, 2} + a_{3, 3}w_{2, 1} + a_{3, 4}w_{2, 2}
  & a_{2, 4}w_{1, 1} + a_{3, 4}w_{2, 1} \\
    a_{3, 1}w_{1, 2} + a_{4, 1}w_{2, 2}
  & a_{3, 1}w_{1, 1} + a_{3, 2}w_{1, 2} + a_{4, 1}w_{2, 1} + a_{4, 2}w_{2, 2}
  & a_{3, 2}w_{1, 1} + a_{3, 3}w_{1, 2} + a_{4, 2}w_{2, 1} + a_{4, 3}w_{2, 2}
  & a_{3, 3}w_{1, 1} + a_{3, 4}w_{1, 2} + a_{4, 3}w_{2, 1} + a_{4, 4}w_{2, 2}
  & a_{3, 4}w_{1, 1} + a_{4, 4}w_{2, 1} \\
    a_{4, 1}w_{1, 2}
  & a_{4, 1}w_{1, 1} + a_{4, 2}w_{1, 2}
  & a_{4, 2}w_{1, 1} + a_{4, 3}w_{1, 2}
  & a_{4, 3}w_{1, 1} + a_{4, 4}w_{1, 2}
  & a_{4, 4}w_{1, 1}
\end{array} \right)

N'est-ce pas cool? Par exemple

\left( \begin{array}[ccc]
  gg_{1, 1} & g_{1, 2} \\
  g_{2, 1} & g_{2, 2} \\
\end{array} \right)
= \left( \begin{array}[ccc]
  ww_{2, 2} & w_{2, 1} \\
  w_{1, 2} & w_{1, 1} \\
\end{array} \right)

Que faire

\left( \begin{array}[ccccc]
  ff_{1, 1}g_{1, 1}
& f_{1, 2}g_{1, 1} + f_{1, 1}g_{1, 2}
& f_{1, 3}g_{1, 1} + f_{1, 2}g_{1, 2}
& f_{1, 4}g_{1, 1} + f_{1, 3}g_{1, 2}
& f_{1, 4}g_{1, 2} \\
  f_{2, 1}g_{1, 1} + f_{1, 1}g_{2, 1}
& f_{2, 2}g_{1, 1} + f_{2, 1}g_{1, 2} + f_{1, 2}g_{2, 1} + f_{1, 1}g_{2, 2}
& f_{2, 3}g_{1, 1} + f_{2, 2}g_{1, 2} + f_{1, 3}g_{2, 1} + f_{1, 2}g_{2, 2}
& f_{2, 4}g_{1, 1} + f_{2, 3}g_{1, 2} + f_{1, 4}g_{2, 1} + f_{1, 3}g_{2, 2}
& f_{2, 4}g_{1, 2} + f_{1, 4}g_{2, 2} \\
  f_{3, 1}g_{1, 1} + f_{2, 1}g_{2, 1}
& f_{3, 2}g_{1, 1} + f_{3, 1}g_{1, 2} + f_{2, 2}g_{2, 1} + f_{2, 1}g_{2, 2}
& f_{3, 3}g_{1, 1} + f_{3, 2}g_{1, 2} + f_{2, 3}g_{2, 1} + f_{2, 2}g_{2, 2}
& f_{3, 4}g_{1, 1} + f_{3, 3}g_{1, 2} + f_{2, 4}g_{2, 1} + f_{2, 3}g_{2, 2}
& f_{3, 4}g_{1, 2} + f_{2, 4}g_{2, 2} \\
  f_{4, 1}g_{1, 1} + f_{3, 1}g_{2, 1}
& f_{4, 2}g_{1, 1} + f_{4, 1}g_{1, 2} + f_{3, 2}g_{2, 1} + f_{3, 1}g_{2, 2}
& f_{4, 3}g_{1, 1} + f_{4, 2}g_{1, 2} + f_{3, 3}g_{2, 1} + f_{3, 2}g_{2, 2}
& f_{4, 4}g_{1, 1} + f_{4, 3}g_{1, 2} + f_{3, 4}g_{2, 1} + f_{3, 3}g_{2, 2}
& f_{4, 4}g_{1, 2} + f_{3, 4}g_{2, 2} \\
  f_{4, 1}g_{2, 1}
& f_{4, 2}g_{2, 1} + f_{4, 1}g_{2, 2}
& f_{4, 3}g_{2, 1} + f_{4, 2}g_{2, 2}
& f_{4, 4}g_{2, 1} + f_{4, 3}g_{2, 2}
& f_{4, 4}g_{2, 2}
\end{array} \right) \\
= \left( \begin{array}[ccccc]
  ff_{1, 1}w_{2, 2}
& f_{1, 2}w_{2, 2} + f_{1, 1}w_{2, 1}
& f_{1, 3}w_{2, 2} + f_{1, 2}w_{2, 1}
& f_{1, 4}w_{2, 2} + f_{1, 3}w_{2, 1}
& f_{1, 4}w_{2, 1} \\
  f_{2, 1}w_{2, 2} + f_{1, 1}w_{1, 2}
& f_{2, 2}w_{2, 2} + f_{2, 1}w_{2, 1} + f_{1, 2}w_{1, 2} + f_{1, 1}w_{1, 1}
& f_{2, 3}w_{2, 2} + f_{2, 2}w_{2, 1} + f_{1, 3}w_{1, 2} + f_{1, 2}w_{1, 1}
& f_{2, 4}w_{2, 2} + f_{2, 3}w_{2, 1} + f_{1, 4}w_{1, 2} + f_{1, 3}w_{1, 1}
& f_{2, 4}w_{2, 1} + f_{1, 4}w_{1, 1} \\
  f_{3, 1}w_{2, 2} + f_{2, 1}w_{1, 2}
& f_{3, 2}w_{2, 2} + f_{3, 1}w_{2, 1} + f_{2, 2}w_{1, 2} + f_{2, 1}w_{1, 1}
& f_{3, 3}w_{2, 2} + f_{3, 2}w_{2, 1} + f_{2, 3}w_{1, 2} + f_{2, 2}w_{1, 1}
& f_{3, 4}w_{2, 2} + f_{3, 3}w_{2, 1} + f_{2, 4}w_{1, 2} + f_{2, 3}w_{1, 1}
& f_{3, 4}w_{2, 1} + f_{2, 4}w_{1, 1} \\
  f_{4, 1}w_{2, 2} + f_{3, 1}w_{1, 2}
& f_{4, 2}w_{2, 2} + f_{4, 1}w_{2, 1} + f_{3, 2}w_{1, 2} + f_{3, 1}w_{1, 1}
& f_{4, 3}w_{2, 2} + f_{4, 2}w_{2, 1} + f_{3, 3}w_{1, 2} + f_{3, 2}w_{1, 1}
& f_{4, 4}w_{2, 2} + f_{4, 3}w_{2, 1} + f_{3, 4}w_{1, 2} + f_{3, 3}w_{1, 1}
& f_{4, 4}w_{2, 1} + f_{3, 4}w_{1, 1} \\
  f_{4, 1}w_{1, 2}
& f_{4, 2}w_{1, 2} + f_{4, 1}w_{1, 1}
& f_{4, 3}w_{1, 2} + f_{4, 2}w_{1, 1}
& f_{4, 4}w_{1, 2} + f_{4, 3}w_{1, 1}
& f_{4, 4}w_{1, 1}
\end{array} \right) \\
\underbrace{=}_{Changer l'ordre d'ajout}
\left( \begin{array}[ccccc]
    ff_{1, 1}w_{2, 2}
  & f_{1, 1}w_{2, 1} + f_{1, 2}w_{2, 2}
  & f_{1, 2}w_{2, 1} + f_{1, 3}w_{2, 2}
  & f_{1, 3}w_{2, 1} + f_{1, 4}w_{2, 2} 
  & f_{1, 4}w_{2, 1} \\
    f_{1, 1}w_{1, 2} + f_{2, 1}w_{2, 2}
  & f_{1, 1}w_{1, 1} + f_{1, 2}w_{1, 2} + f_{2, 1}w_{2, 1} + f_{2, 2}w_{2, 2}
  & f_{1, 2}w_{1, 1} + f_{1, 3}w_{1, 2} + f_{2, 2}w_{2, 1} + f_{2, 3}w_{2, 2}
  & f_{1, 3}w_{1, 1} + f_{1, 4}w_{1, 2} + f_{2, 3}w_{2, 1} + f_{2, 4}w_{2, 2}
  & f_{1, 4}w_{1, 1} + f_{2, 4}w_{2, 1} \\
    f_{2, 1}w_{1, 2} + f_{3, 1}w_{2, 2}
  & f_{2, 1}w_{1, 1} + f_{2, 2}w_{1, 2} + f_{3, 1}w_{2, 1} + f_{3, 2}w_{2, 2}
  & f_{2, 2}w_{1, 1} + f_{2, 3}w_{1, 2} + f_{3, 2}w_{2, 1} + f_{3, 3}w_{2, 2}
  & f_{2, 3}w_{1, 1} + f_{2, 4}w_{1, 2} + f_{3, 3}w_{2, 1} + f_{3, 4}w_{2, 2}
  & f_{2, 4}w_{1, 1} + f_{3, 4}w_{2, 1} \\
    f_{3, 1}w_{1, 2} + f_{4, 1}w_{2, 2}
  & f_{3, 1}w_{1, 1} + f_{3, 2}w_{1, 2} + f_{4, 1}w_{2, 1} + f_{4, 2}w_{2, 2}
  & f_{3, 2}w_{1, 1} + f_{3, 3}w_{1, 2} + f_{4, 2}w_{2, 1} + f_{4, 3}w_{2, 2}
  & f_{3, 3}w_{1, 1} + f_{3, 4}w_{1, 2} + f_{4, 3}w_{2, 1} + f_{4, 4}w_{2, 2}
  & f_{3, 4}w_{1, 1} + f_{4, 4}w_{2, 1} \\
    f_{4, 1}w_{1, 2}
  & f_{4, 1}w_{1, 1} + f_{4, 2}w_{1, 2}
  & f_{4, 2}w_{1, 1} + f_{4, 3}w_{1, 2}
  & f_{4, 3}w_{1, 1} + f_{4, 4}w_{1, 2}
  & f_{4, 4}w_{1, 1}
\end{array} \right) \\
\Leftrightarrow
\left( \begin{array}[ccccc]
    aa_{1, 1}w_{2, 2}
  & a_{1, 1}w_{2, 1} + a_{1, 2}w_{2, 2}
  & a_{1, 2}w_{2, 1} + a_{1, 3}w_{2, 2}
  & a_{1, 3}w_{2, 1} + a_{1, 4}w_{2, 2} 
  & a_{1, 4}w_{2, 1} \\
    a_{1, 1}w_{1, 2} + a_{2, 1}w_{2, 2}
  & a_{1, 1}w_{1, 1} + a_{1, 2}w_{1, 2} + a_{2, 1}w_{2, 1} + a_{2, 2}w_{2, 2}
  & a_{1, 2}w_{1, 1} + a_{1, 3}w_{1, 2} + a_{2, 2}w_{2, 1} + a_{2, 3}w_{2, 2}
  & a_{1, 3}w_{1, 1} + a_{1, 4}w_{1, 2} + a_{2, 3}w_{2, 1} + a_{2, 4}w_{2, 2}
  & a_{1, 4}w_{1, 1} + a_{2, 4}w_{2, 1} \\
    a_{2, 1}w_{1, 2} + a_{3, 1}w_{2, 2}
  & a_{2, 1}w_{1, 1} + a_{2, 2}w_{1, 2} + a_{3, 1}w_{2, 1} + a_{3, 2}w_{2, 2}
  & a_{2, 2}w_{1, 1} + a_{2, 3}w_{1, 2} + a_{3, 2}w_{2, 1} + a_{3, 3}w_{2, 2}
  & a_{2, 3}w_{1, 1} + a_{2, 4}w_{1, 2} + a_{3, 3}w_{2, 1} + a_{3, 4}w_{2, 2}
  & a_{2, 4}w_{1, 1} + a_{3, 4}w_{2, 1} \\
    a_{3, 1}w_{1, 2} + a_{4, 1}w_{2, 2}
  & a_{3, 1}w_{1, 1} + a_{3, 2}w_{1, 2} + a_{4, 1}w_{2, 1} + a_{4, 2}w_{2, 2}
  & a_{3, 2}w_{1, 1} + a_{3, 3}w_{1, 2} + a_{4, 2}w_{2, 1} + a_{4, 3}w_{2, 2}
  & a_{3, 3}w_{1, 1} + a_{3, 4}w_{1, 2} + a_{4, 3}w_{2, 1} + a_{4, 4}w_{2, 2}
  & a_{3, 4}w_{1, 1} + a_{4, 4}w_{2, 1} \\
    a_{4, 1}w_{1, 2}
  & a_{4, 1}w_{1, 1} + a_{4, 2}w_{1, 2}
  & a_{4, 2}w_{1, 1} + a_{4, 3}w_{1, 2}
  & a_{4, 3}w_{1, 1} + a_{4, 4}w_{1, 2}
  & a_{4, 4}w_{1, 1}
\end{array} \right)

Et est devenu le même! Cela signifie que ** l'intercorrélation et la convolution mathématique peuvent, espérons-le, être la même opération **. Dans ce cas, "to work" est une inversion d'index si elle est discrète, et une inversion plus ou moins si elle est continue.

Vous pouvez donc considérer le filtre CNN comme l'apprentissage d'un filtre à convolution inversé, et les chercheurs n'ont pas à pleurer.

Algorithme FFT Cooley-Tukey

Tout d'abord, vérifions la définition de la transformée de Fourier discrète en premier lieu. Pour simplifier, considérons un vecteur unidimensionnel $ \ boldsymbol {x} $ avec une longueur de $ N $ comme une transformée de Fourier discrète.

X_k = \mathcal{F}_{\boldsymbol{x}}(k) = \sum_{p=0}^{N-1}{x_p e^{-j\frac{2 \pi}{N}kp}} = \sum_{p=0}^{N-1}{x_p W_N^{kp}} \quad k = 0, 1, \ldots N-1 \\
W_N^{kp} = e^{-j\frac{2 \pi}{N}}

Ce sera. Ici, le symbole imaginaire est $ j $. De plus, $ W_N = e ^ {-j \ frac {2 \ pi} {N}} $ est appelé ** facteur de rotation **. La raison sera décrite plus tard. Ce montant de calcul est $ \ mathcal {O} (N ^ 2) $, mais ce calcul peut être accéléré en supposant que $ N $ est pair. L'algorithme s'appelle ** FFT: Fast Fourier Transformation ** et peut être exprimé comme:

\begin{align}
  X_{2k} = \mathcal{F}_{\boldsymbol{x}}(2k) &= \sum_{p=0}^{N-1}{x_p W_N^{2kp}} & \\
  &= \sum_{p=0}^{N-1}{x_p W_{N/2}^{kp}} & (\because W_N^{2kp} = e^{-j\frac{2 \pi}{N}2kp} = e^{-j\frac{2 \pi}{N/2}kp} = W_{N/2}^{kp}) \\
  &= \sum_{p=0}^{N/2-1}{x_p W_{N/2}^{kp}} + \sum_{p=N/2}^{N-1}{x_p W_{N/2}^{kp}} & (\car divisé entre la première moitié et la seconde moitié, W_{N/2}^{kp}Nombre d'éléments de\frac{N}{2}Correspondre) \\
  &= \sum_{p=0}^{N/2-1}{x_p W_{N/2}^{kp}} + \sum_{p=0}^{N/2-1}{x_{p+N/2} W_{N/2}^{k(p+N/2)}} & (\car la somme de la seconde moitié est p=Passer à 0 début) \\
  &= \sum_{p=0}^{N/2-1}{x_p W_{N/2}^{kp}} + \sum_{p=0}^{N/2-1}{x_{p+N/2} W_{N/2}^{kp}} & (\because W_{N/2}^{k(N/2)} = e^{-j\frac{2 \pi}{N/2}k(N/2)} = e^{-j2k \pi} = 1) \\
  &= \sum_{p=0}^{N/2-1}{(x_p + x_{p+N/2}) W_{N/2}^{kp}} \quad k = 0, 1, \ldots, \cfrac{N}{2} & \\

  X_{2k+1} = \mathcal{F}_{\boldsymbol{x}}(2k+1) &= \sum_{p=0}^{N-1}{x_p W_N^{(2k+1)p}} & \\
  &= \sum_{p=0}^{N-1}{x_p W_{N}^{p}W_{N/2}^{kp}} & \\
  &= \sum_{p=0}^{N/2-1}{x_p W_{N}^{p}W_{N/2}^{kp}} + \sum_{p=N/2}^{N-1}{x_p W_{N}^{p}W_{N/2}^{kp}} & \\
  &= \sum_{p=0}^{N/2-1}{x_p W_{N}^{p}W_{N/2}^{kp}} + \sum_{p=0}^{N/2-1}{x_{p+N/2} W_{N}^{p+N/2}W_{N/2}^{k(p+N/2)}} & \\
  &= \sum_{p=0}^{N/2-1}{x_p W_{N}^{p}W_{N/2}^{kp}} - \sum_{p=0}^{N/2-1}{x_{p+N/2} W_{N}^{p}W_{N/2}^{kp}} & \\
  &= \sum_{p=0}^{N/2-1}{(x_p - x_{p+N/2}) W_{N}^{p} W_{N/2}^{kp}} \quad k = 0, 1, \ldots, \cfrac{N}{2}-1 &
\end{align}

Par définition, $ W $ est appelé un facteur de rotation car il représente un point sur la circonférence unitaire dont l'angle de rotation est ** dans le sens des aiguilles d'une montre ** et $ \ frac {2 \ pi} {N} $. .. Par conséquent, l'expression relationnelle suivante est valable.

W_{2n}^{kn} = e^{-j\frac{2 \pi}{2n}kn} = e^{-j k \pi} = (-1)^k

Cette expression relationnelle est fondamentalement la valeur lorsque l'angle de rotation est $ k \ pi $. Cette formule est utilisée partout pour transformer la formule FFT.

<détails>

e^{jx} = \cos x + j \sin x

e^{j \pi} = \cos \pi + j \sin \pi \Leftrightarrow e^{j \pi} = -1 + j0 \\
\therefore e^{j \pi} + 1 = 0

\begin{align}
  e^{j(-k \pi)} &= \cos (-k \pi) + j \sin (-k \pi) \\
  &= (-1)^k \\
\end{align}

Recommended Posts