[PYTHON] CNN Acceleration Series ~ FCNN: Einführung des Fourier Convolutional Neural Network ~

Überblick

Mit dem Aufkommen des Convolution Neural Network (CNN) hat das Gebiet der Bilderkennung große Fortschritte gemacht. Beginnend mit AlexNet wurden verschiedene Netzwerke wie VGGNet und GoogLeNet vorgeschlagen und haben ihre Auswirkungen gezeigt. Obwohl es sich um ein solches CNN handelt, besteht der Nachteil darin, dass es viel Zeit in Anspruch nimmt, da die Faltungsoperation schwer ist. Sein Gewicht ist derart, dass die vollständig verbundene Schicht vollständig ignoriert werden kann, und wenn der Faltungsprozess beschleunigt werden kann, kann die Lernzeit erheblich reduziert werden. Daher fällt die Beziehung ** Faltung im räumlichen Bereich = Elementprodukt im Frequenzraum ** auf. In diesem Artikel werde ich die grundlegende Faltungstheorie im Frequenzbereich erläutern. Ich konnte keine Artikel auf Japanisch finden und versuche mein Bestes, um sie aus den Zeitungen zu lesen. Bitte weisen Sie darauf hin, dass es einige Fehler und Missverständnisse geben kann.

Die in diesem Artikel behandelten Artikel sind

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

ist.

Inhaltsverzeichnis

• [Was faltet](#Was faltet sich)
• [Lineare Faltung](#Lineare Faltung)
• [Rundfalten](# Umlauffalten)
• [Wie man lineare Faltung und Kreisfaltung ausgleicht](#Wie man lineare Faltung und Kreisfaltung ausgleicht)
• [Falten mit CNN](Falten mit #cnn)
• [Zum Frequenzbereich](#Zum Frequenzbereich)
• [2.2 Algorithmus](# 22-Algorithmus)
• [2.3 Implementierung und räumliche Berechnung](# 23-Implementierung und räumliche Berechnung)
• [3 Experiment](# 3-Experiment)
• [4 Über die Zukunft](# 4 - Über die Zukunft)
• [Versuchen Sie zu implementieren?](# Versuchen Sie zu implementieren)
• Anhang
• [Strikte Faltung und CNN](# Strikte Faltung und CNN)
• [Cooley-Turkey FFT-Algorithmus](# cooley-turkey-fft-Algorithmus)

Was ist Falten

Um die Faltung im Frequenzbereich richtig zu verstehen, betrachten wir zunächst die Faltung im räumlichen Bereich. Es gibt zwei Arten der Faltungsverarbeitung, die als ** lineare Faltung (gerade Faltung) ** und ** kreisförmige Faltung (kreisförmige Faltung) ** bezeichnet werden. Zuerst werde ich diese beiden erklären.

Ich werde die Variablen vorstellen, die im Folgenden zuerst verwendet werden.

• $ I \ cdots $ Eingabegröße
• $ F \ cdots $ Filtergröße
• $ O \ cdots $ Ausgabegröße

Lineare Faltung

Die lineare Faltung ist der in der folgenden Abbildung gezeigte Faltungsprozess. Auf diese Weise fühlt es sich an, als würde man an dem Punkt beginnen, an dem sich der rechte Rand des Filters und der linke Rand des Eingangs überlappen, und beim Durchgang enden. Ich werde es nicht veröffentlichen, da ich keine mathematische Formel benötige, aber bitte haben Sie Verständnis dafür, dass es so funktioniert. Und beachten Sie, dass diese lineare Faltung ** die Eingabe keine periodische Funktion ** ist.

Darüber hinaus gilt der folgende relationale Ausdruck für die Größe.

O = I + F - 1

In GIF ist $ I = 9 $ und $ F = 3 $, sodass die Ausgabegröße $ O = 9 + 3-1 = 11 $ ist.

Kreisfaltung

Die kreisförmige Faltung ist der in der folgenden Abbildung gezeigte Faltungsprozess. Es ist so, als würde man an dem Punkt beginnen, an dem sich der linke Rand des Filters und der linke Rand des Eingangs überlappen, und enden, wenn sich der rechte Rand des Filters und der rechte Rand des Eingangs überlappen. Dies ist genau der Unterschied zur linearen Faltung. In diesem Fall muss der ** Eingang eine periodische Funktion ** sein. Ich denke, es ist in Ordnung zu verstehen, dass zwei Enden, die jeweils durch ein lineares Faltungs-GIF dargestellt werden, nicht erforderlich sind, da die Eingabe eine periodische Funktion ist (ich denke, dass sie streng unterschiedlich ist, aber Strenge nicht besonders erforderlich ist. ).

Darüber hinaus gilt der folgende relationale Ausdruck für die Größe.

O = I - F + 1

In GIF ist $ I = 9 $ und $ F = 3 $, daher beträgt die Ausgabegröße $ O = 9 - 3 + 1 = 7 $.

Wie man lineare und kreisförmige Windungen ausgleicht

Damit lineare und kreisförmige Windungen gleich sind, müssen beide Enden der Eingabe mit Nullen aufgefüllt werden, so dass $ O = I + F -1 $. Sie können sehen, dass das Ausgabeergebnis gleich der linearen Faltung ist.

Falten in CNN

Welches ist nun die Faltungsoperation in CNN? Denken Sie unter dem Gesichtspunkt der Eingabe.

Die in das CNN eingegebenen Daten sind normalerweise ein Bild, und höchstwahrscheinlich ist dieses Bild ein Foto. Dies bedeutet, dass erwartet werden kann, dass das Bild keine Periodizität aufweist, es sei denn, das Bild wird als Muster erkannt. Dies bedeutet, dass der Eingang aperiodisch ist, sodass ** CNN eine lineare Faltung durchführen muss **.

Aber es ist noch zu früh, um daraus zu schließen. Bitte sehen Sie die Abbildung unten. Dies zeigt, wie der CNN gefaltet ist. Wie Sie sehen können, passiert der Filter nicht das Eingabebild, also ** machen wir in dieser Abbildung eine kreisförmige Faltung **. Dies bedeutet, dass ** die Informationen nicht korrekt ** aus der Faltungsoperation erhalten werden können. Unter der Annahme, dass ** die Eingabebilder periodisch vertikal und horizontal angeordnet sind (überlappend $ F -1 $) **, kann diese Faltung als korrekt angesehen werden.

Ich würde gerne sagen: "Welches ist es schließlich?", Aber ich muss noch über etwas nachdenken. Es ist ** Polsterung **, eine wesentliche Technologie für CNN. Diese Abbildung enthält nicht genug, aber ** die kreisförmige Faltung kann gleich der linearen Faltung sein **, wenn Sie so viele auffüllen, wie Sie benötigen. Wenn dann die als Auffüllen bezeichnete Verarbeitung korrekt auf das Eingabebild angewendet wird, kann eine lineare Faltung durchgeführt werden, und ** Informationen können korrekt aus der Faltungsoperation ** erhalten werden. In Artikel, den ich zuvor geschrieben habe besteht die Rolle des Auffüllens darin, "die Größe beizubehalten" und "alle Informationen am Rand zu erhalten". Das ist es. (Zum Zeitpunkt des Schreibens habe ich nicht so viel darüber nachgedacht wie über Tau, aber lol)

Dieser Vorgang des Auffüllens macht die Diskussion noch komplizierter. In Anbetracht des Schrittes, der dem Falten in CNN eigen ist, ... Diese Auffüllung wird häufig verwendet **, um die Größenverschlechterung des Ausgabebildes aufgrund der Faltung in CNN ** zu verhindern (oder zu verringern). Daher nimmt die Polsterbreite je nach Schritt zu oder ab, so dass ich die kreisförmige Faltung überhaupt nicht zu einer linearen Faltung machen möchte. Dann ist die Polsterbreite übermäßig oder unzureichend. Es gibt kein Problem, wenn die Polsterbreite groß ist, aber wenn sie klein ist, wird die Konvertierung in eine kreisförmige Faltung $ \ rightarrow $ lineare Faltung nicht korrekt durchgeführt.

Immerhin lautet die Schlussfolgerung ** "Faltung in CNN liegt zwischen linearer / zirkulärer Faltung" **. Es scheint wie "Ich ziehe so viel und die Schlussfolgerung ist mehrdeutig", aber es kann nicht geholfen werden, weil ich es nur sagen kann. Wenn es um strenge theoretische Diskussionen geht, unterscheidet es sich tatsächlich von den Annahmen.

Dies ist die Voraussetzung. Von hier aus werden wir endlich zur Theorie im Frequenzbereich übergehen. Übrigens, wenn Sie sich fragen "Was ist die mathematische Strenge?", Siehe [Anhang](#Strict Convolution and CNN).

Zum Frequenzbereich

Übrigens ist die bisherige Geschichte eine Zusammenfassung der Ergebnisse meiner Forschung hier und da, die ich beim Lesen der Zeitung für notwendig hielt. Es ist immer noch süß, aber ich denke, es ist okay, wenn Sie so viel im Sinn haben. Jetzt ist es Zeit, sich mit dem Inhalt des Papiers zu befassen. Die Rückausbreitung in Artikel 2.1 beschreibt nur den Teil, der CNN im räumlichen Bereich und CNN im Frequenzbereich vergleicht. Ich werde ihn also ausschneiden und aus 2.2 lesen. Das Papier wird übrigens nicht ins Japanische übersetzt, sondern übersetzt und hinzugefügt. Die Abbildungen in diesem Abschnitt stammen aus dem Papier.

2.2 Algorithmus

Es ist bekannt, dass ** Faltungsoperationen im räumlichen Bereich dem Elementprodukt im Fourier- (Frequenz-) Bereich ** entsprechen. Daher verwendet die Faltungsoperation im räumlichen Bereich den Fourier-Konverter $ \ mathcal {F} $ und seine inverse Operation $ \ mathcal {F} ^ {-1} $.

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

Kann ausgedrückt werden als. Das Symbol $ * $ repräsentiert jedoch die Faltungsoperation im räumlichen Bereich, und das Symbol $ \ otimes $ repräsentiert das Elementprodukt in der Matrixoperation. Es sollte beachtet werden, dass aufgrund der Natur des Elementprodukts ** $ f und g $ eine nahe Größe (oder eher eine gleiche Größe) ** haben müssen, um die obigen Gleichungsoperationen auszuführen. Im Allgemeinen sind die Eingabe (Größe $ I_h \ times I_w $) und der Filter (Größe $ F_h \ times F_w $) jedoch völlig unterschiedlich groß. Daher ist bei der Implementierung ein Auffüllen erforderlich, um der Größe des Eingangs und des Filters zu entsprechen. (Kann gekürzt werden) Zur Vereinfachung der Diskussion sei $ I_h = I_w = I $ und $ F_h = F_w = F $. Wir werden die Ausgabe auch auf $ O_h \ times O_w $ skalieren, was auch als $ O_h = O_w = O $ dargestellt wird. Stellen Sie außerdem die Anzahl der Eingangskanäle auf $ C $, die Anzahl der Filter auf $ M $ und die Größe des Mini-Batches auf $ B $ ein. Der Rechenaufwand für die Faltungsoperation im räumlichen Bereich ist kein Auffüllen, Schritt $ 1 $

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

Es wird sein. Wenn die Polsterbreite $ 2p $ beträgt und der Schritt $ s $ beträgt

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

nicht wahr.

Andererseits beträgt der Berechnungsbetrag in der Fourier-Region $ 2C_ {order} O ^ 2 \ log {O} $, wenn die Fourier-Transformation durch ** Fast Fourier Transformation (FFT) ** durchgeführt wird, die das Elementprodukt ist. Der Berechnungsbetrag für wird ausgedrückt als ** Beachten Sie, dass es sich um eine komplexe Operation handelt ** und $ 4O ^ 2 $. $ C_ {order} $ ist eine Konstante. Daher ist die Summe von $ 2C_ {order} O ^ 2 \ log {O} + 4O ^ 2 $ der Berechnungsbetrag für die Faltungsoperation in der Fourier-Region. Es scheint, dass $ O = I $ in der Zeitung.

Jeder Eingangskanal und Filter ist unabhängig, sodass Sie jeweils nur eine Fourier-Transformation durchführen müssen. Die Lerneffizienz kann für bestimmte Windungen verringert werden, aber die Fähigkeit, FFTs effektiv wiederzuverwenden, kann den Aufwand einer verringerten Effizienz überwiegen.

Das Ermitteln des Rechenaufwands für die Vorwärts- und Rückwärtsausbreitung macht die Überlegenheit von Faltungsoperationen im Fourier-Bereich deutlicher.

Es ist zu beachten, dass $ hier $ O = I - F + 1 $ oder $ O = \ left \ lceil \ cfrac {I - F + 2p} {s sowohl im räumlichen als auch im Frequenzbereich ist. } \ right \ rceil + 1 $$ bedeutet, dass es berechnet wird. Beachten Sie, dass sich ** von der vorherigen Diskussion unterscheidet, insbesondere in der Fourier-Region **. Wahrscheinlich wurde ein korrekter Vergleich des Rechenaufwands vorgenommen.

Wie aus dieser Tabelle hervorgeht, wird ** der Rechenaufwand im räumlichen Bereich durch das Produkt von 5 Termen ** dargestellt, während der Rechenaufwand im Fourierbereich ** das Produkt von bis zu 4 Termen ** ist. Es bedeutet, dass es vertreten ist. Grob gesagt ist die Reihenfolge des Berechnungsbetrags im räumlichen Bereich 5. Ordnung (genauer 7. Ordnung) und im Fourierbereich 4. Ordnung (genauer 5. Ordnung). Lassen Sie uns die Vorwärtsausbreitung tatsächlich berechnen und bestätigen, um zu sehen, wie effektiv dies ist.

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

Unter der Annahme, dass $ I = 16, 64 $ berechnet wird, ist $ O = I - F + 1 = 10, 58 $, also ungefähr der räumliche Bereich

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

Über die Fourierregion

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 Milliarden\\
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 Milliarden

• Da in der Veröffentlichung nicht angegeben ist, wie viel $ C_ {order} $ berechnet wurde, wurde $ C_ {order} = 16 $ übernommen, was ungefähr der Grafik entspricht.

Mit diesem Gefühl vergrößert sich der Unterschied mit zunehmender Größe der Eingabe.

2.3 Implementierung und räumliche Berechnung

Obwohl der Algorithmus eine sehr einfache Faltungsoperation in der Fourier-Region ist, gibt es zwei Hauptprobleme bei der Implementierung.

1. Die in der aktuellen GPU implementierte FFT, hauptsächlich CUDA-kompatibel mit NVIDIA-GPUs, ist für eine begrenzte Anzahl von FFTs mit großem Eingang optimiert, sodass sie für diesen Algorithmus nicht optimal ist.
2. Zum Halten des Fourier-transformierten Filters ist eine große Menge an Speicherfläche (räumliche Berechnungsmenge) erforderlich.

Die folgenden Optimierungen und Gegenmaßnahmen wurden für jedes Problem vorgeschlagen.

1. Implementierter [Cooley-Turkey FFT-Algorithmus](# cooleyturkey-fft-Algorithmus)

• Kann in Richtung des Mini-Batch-Kanals parallelisiert werden
• Ursprünglich kann 2D-FFT in Zeilen- und Spaltenrichtung parallelisiert werden.
• Aus dem oben Gesagten ist es möglich, mit diesem Algorithmus eine Fourier-Transformation für eine kleine und große Eingangsmenge effizient und schnell durchzuführen.

2. Speichern von Speicher durch Wiederverwenden (Überschreiben) des für jede Faltung verwendeten Speichers. Durch Ausnutzen der Tatsache, dass die Fourier-Transformation der Realwerteingabe zu einer symmetrischen Matrix wird, bleibt nur die untere Dreiecksmatrix (oder die obere Dreiecksmatrix) erhalten.

• Bei der Berechnung der Backpropagation aufgrund der Wiederverwendung des Speichers ist eine erneute FFT erforderlich
• Die Speichermenge, die durch Halten in einer dreieckigen Matrix erhalten bleiben soll, beträgt $ X ^ 2 \ Rightarrow \ frac {X (X + 1)} {2} $

Dies ist das Ende des theoretischen Aspekts. Der Rest sind die experimentellen Ergebnisse. Ich wollte, dass Sie etwas konkreter posten, welche Art von Berechnung voranschreitet ... Einige Fragen tauchten auf, als ich versuchte, sie zu implementieren ... Nun, dieser Bereich ähnelt dem normalen CNN Ich frage mich, ob es sich so verhalten sollte.

3 Experimentieren

Das Experiment wurde mit der GeForce GTX Titan-GPU von NVIDIA durchgeführt, um die Implementierung der CUDA Conv-GPU mit der maschinellen Lernumgebung Torch 7 zu vergleichen. Die im Experiment erhaltene Genauigkeit ist nicht aufgeführt, scheint jedoch innerhalb des Toleranzbereichs zu liegen.

Ändern Sie die Filtergröße, Eingangsgröße und Mini-Batch-Größe eines CNN und konzentrieren Sie sich dabei auf die zweite Schicht, in der die Anzahl der Eingangskanäle $ C = 96 $ und die Anzahl der Ausgangskanäle (dh die Anzahl der Filter) $ M = 256 $ beträgt. Die Ergebnisse der Experimente sind in der folgenden Abbildung dargestellt. In den meisten Fällen hat sich gezeigt, dass die Faltungsoperation im Fourier-Bereich schnell ist. Ein bedeutenderer Vorteil wird insbesondere in $ \ cfrac {\ partiell L} {\ partiell y_M} * x_C $ gesehen, das einen großen Zeitaufwand für die Berechnung hat. Dies liegt höchstwahrscheinlich daran, dass Sie einen Filter mit einer großen Filtergröße verwenden. Vor dem Anwenden von FFT ** wird der Filter auf die gleiche Größe wie der Eingang ** aufgefüllt, sodass Sie einen größeren Filter verwenden können.

• In Bezug auf diese Überlegung verwenden viele der aktuellen CNNs eine kleine Filtergröße unter dem Gesichtspunkt der Speicherersparnis. Wenn die FCNN-Implementierung unverändert bleibt, wird sie ohnehin eine große Menge an Speicher verbrauchen, sodass es möglicherweise schwierig ist, einen größeren Filter zu verwenden. Übrigens ist es unwahrscheinlich, dass die Implementierung verwendet wird. Eine andere speichersparende Technologie ist fest etabliert. Ich werde einen weiteren Artikel darüber schreiben.

Für CNN, das sich diesmal nur auf die 2. Schicht konzentrierte, diesmal auf die 1. bis 5. Schicht, ist das Ergebnis des Experiments durch Ändern der Mini-Chargengröße $ B $ in der folgenden Abbildung dargestellt. .. Es wurden keine Daten gesammelt, da der Gradient der Eingabeebene zur Eingabe nicht berechnet werden muss. In den meisten Fällen kann gelesen werden, dass es die schnellste oder zweitschnellste Geschwindigkeit aufweist. Darüber hinaus kann gesagt werden, dass FCNN in fast allen Fällen wirksam ist, da es insgesamt das schnellste ist. Es wird auch darauf hingewiesen, dass die Weiterleitungsausbreitung ziemlich schnell ist, was ** die Vorteile maximiert, z. B. wenn Schlussfolgerungen mithilfe eines trainierten Netzwerks gezogen werden **.

Schließlich ist es das experimentelle Ergebnis, wenn die Pooling-Schicht und die vollständig verbundene Schicht zu dem obigen CNN hinzugefügt werden. In diesem Experiment wird untersucht, ob Implementierungsdetails wie Auffüllen und Speicherzugriff die Leistung ändern. FCNN hat auch in diesem Experiment seine Überlegenheit bewiesen.

4 Über die Zukunft

Ich werde es in einer Kugel lassen.

• Erkundung von Möglichkeiten zum Erlernen von Filtern direkt in der Fourier-Region --Erläutern, wie nichtlineare Funktionen innerhalb der Fourier-Region verwendet werden --Dies macht die inverse Konvertierung überflüssig und beschleunigt sie.
• In der aktuellen Implementierung muss das Eingabebild auf die Größe einer Potenz von 2 aufgefüllt werden. Verbessern Sie dies.
• Untersuchen Sie den Effekt der Erhöhung der Filtergröße

Das Obige ist der Inhalt des Papiers. Es ist ein einfacher, aber leistungsstarker Algorithmus ~ Es scheint, dass seitdem verschiedene Studien durchgeführt wurden.

Möchten Sie es implementieren?

Ich würde es gerne implementieren ... aber ich habe einige Zweifel.

• Ist es notwendig, vor und nach der Faltungsoperation eine FFT / IFFT durchzuführen?
• In der schematischen Darstellung des Papiers sind die Anzahl der Eingangskanäle und die Anzahl der Ausgangskanäle gleich, aber die Anzahl der Ausgangskanäle der Faltungsschicht im räumlichen Bereich sollte von der Anzahl der Filter abhängen. ――Auch egal mit welchem Kanal Sie übereinstimmen, wie Sie ihn an dieser Dimension ausrichten, ist ein Problem.

Jeder von ihnen ist nicht in der Zeitung angegeben ... Es sollte sein, aber es kann subtil gelesen werden, nicht wahr? Zum Beispiel in [4 Über die Zukunft](# 4 - Über die Zukunft)

--Erforschen Sie Möglichkeiten, um Filter direkt in der Fourier-Region zu lernen --Erläutern, wie nichtlineare Funktionen innerhalb der Fourier-Region verwendet werden --Dies macht die inverse Konvertierung überflüssig und beschleunigt sie.

Da es so etwas wie sagt, scheint es, dass FFT / IFFT nur vor und nach der Matrixproduktoperation durchgeführt wird oder die Anzahl der Kanäle sich auf die gleiche Weise ändert wie CNN in der letzten Tabelle des Experiments, schreibe ich nicht direkt Es gibt jedoch eine Beschreibung, die der Fall zu sein scheint.

Ich habe auch nach späteren Artikeln gesucht und diese gelesen, aber es gab auch eine Beschreibung, wie man FFT nur einmal macht und alles in der Fourier-Region ausführt, also auch in diesem Bereich. Ich werde es diesmal nicht implementieren, weil ich nicht genug gelernt habe, um es einzuschließen. Ich kann das Unverständnis über die Fourier-Transformation nicht leugnen.

Blinddarm

Als Bonus werde ich einige mathematische Dinge posten.

Strikte Faltung und CNN

Betrachten Sie die folgende Faltung der Eingabematrix $ \ boldsymbol {A} $ und der Filtermatrix $ \ boldsymbol {W} $. Jedoch keine Polsterung, Schritt $ 1 $.

• Es tut mir leid, wenn der Index des nachfolgenden Matrixelements falsch ist.

\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)

Das Faltungsergebnis davon ist wie folgt.

\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}

Sie können die Regelmäßigkeit sehen. Verallgemeinern wir es. Wenn die Filtergröße $ F_h \ times F_w $ ist, ist die $ (i, j) $ -Komponente $ o_ {i, j} $ der Ausgabe

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}}}

Kann geschrieben werden als. Bitte beachten Sie, dass die Reihenfolge der Indexaddition für später geändert wurde.

Dies ist die Faltungsoperation in CNN. Es ist eine kreisförmige Faltung. Übrigens wird mathematisch die zweidimensionale diskrete Faltungsoperation durch die folgende Gleichung ausgedrückt.

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

Irgendwie wird $ f $ eingegeben, $ g $ wird als Filter angesehen und die Reihenfolge wird von der allgemeinen Formel umgekehrt. Außerdem nehmen $ k und l $ alle Werte an, für die der Index gültig ist. An diesem Punkt sind diejenigen, die "das" denken, scharf. Wenn dies in eine Matrix geschrieben ist (die Größen sind für jedes CNN gleich)

\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}

Es wird sein.

Wie Sie auf einen Blick sehen können, unterscheiden sich die Faltung in CNN und die in der Mathematik definierte Faltung. Dieser Unterschied ist der Unterschied zwischen kreisförmiger und linearer Faltung ... ** aber es ist tatsächlich anders **. Selbst wenn Sie ** Auffüllen anwenden, ist es nicht dasselbe ** wie in [Wie man lineare Faltung und kreisförmige Faltung ausgleicht](#Wie man lineare Faltung und kreisförmige Faltung ausgleichen kann) **. Ich werde es tatsächlich versuchen.

\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)

Wie

\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)

Es wird sein. Die Formen stimmen überein, die Anzahl der Ergänzungen für jedes Element ist gleich, aber die Indizes sind unterschiedlich. Dies bedeutet, dass ** CNN-Faltung eine von der mathematisch definierten Faltung ** getrennte Operation ist.

Dies war ein Blick in die Faltung dieses Artikels

Wenn es um theoretisch strenge Diskussionen geht, unterscheidet es sich tatsächlich von den Annahmen.

Das ist. Erstens war die Annahme, dass "CNN-Faltung eine mathematische Faltung ist", falsch **.

Sie fragen sich vielleicht: "Welcher Art von Definition entspricht die CNN-Faltung mathematisch oder gibt es eine entsprechende mathematische Definition?" Aber es gibt eine richtige mathematische Definition dafür. ** Gegenseitige Beziehung **.

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

Wie bei der mathematischen Faltung nehmen $ k und l $ alle Werte an, die gültige Indizes sind. Dies ist die gleiche Definition wie bei der CNN-Faltung, sodass Sie sich vorstellen können, dass Sie das gleiche Ergebnis erzielen.

Diese Interkorrelation berechnet, wie ähnlich die beiden Signale ($ f $ und $ g $) sind. Da es nicht so relevant ist, überlasse ich es der Referenzseite für Details, aber mit anderen Worten, der CNN-Filter ähnelt dem spezifischen Eingabemuster. Sie lernen die Verteilungsfunktion, die Sie verwenden.

Wichtig ist hier **, ob wir die Interkorrelation irgendwie in eine mathematische Faltung bringen können **. Der Prozess des Faltens und Faltens, der früher die Norm war, war eigentlich kein Falten, aber er würde die Grundlage der Diskussion abdecken und es wäre notwendig, alles zu überdenken. Forscher, die intensiv über die Interpretation von Filtern nachgedacht haben, werden weinen ...

Vergleichen wir die mathematische Faltung mit der CNN-Faltung beim Auffüllen.

\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)

Fühlt es sich nicht cool an? Zum Beispiel

\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)

Wie geht's

\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{=}_{Ändern Sie die Reihenfolge der Hinzufügung}
\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)

Und wurde das gleiche! Dies bedeutet, dass ** Interkorrelation und mathematische Faltung hoffentlich dieselbe Operation sein können **. In diesem Fall ist "arbeiten" eine Indexinversion, wenn sie diskret ist, und eine Plus- oder Minusinversion, wenn sie kontinuierlich ist.

Sie können sich den CNN-Filter also als Lernen eines invertierten Faltungsfilters vorstellen, und die Forscher müssen nicht weinen.

Cooley-Tukey-FFT-Algorithmus

Lassen Sie uns zunächst die Definition der diskreten Fourier-Transformation überprüfen. Betrachten Sie der Einfachheit halber einen eindimensionalen Vektor $ \ boldsymbol {x} $ mit einer Länge von $ N $ als diskrete Fourier-Transformation.

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}}

Es wird sein. Hier ist das imaginäre Symbol $ j $. Außerdem wird $ W_N = e ^ {-j \ frac {2 \ pi} {N}} $ als ** Umsatzfaktor ** bezeichnet. Der Grund wird später beschrieben. Diese Berechnungsmenge ist $ \ mathcal {O} (N ^ 2) $, aber diese Berechnung kann beschleunigt werden, vorausgesetzt, $ N $ ist gerade. Der Algorithmus heißt ** FFT: Fast Fourier Transformation ** und kann ausgedrückt werden als:

\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}} & (\weil in die erste und die zweite Hälfte unterteilt, W._{N/2}^{kp}Anzahl der Elemente von\frac{N}{2}Passen) \\
  &= \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)}} & (\weil die Summe der zweiten Hälfte p ist=Umstellung auf 0 Start) \\
  &= \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}

Per Definition wird $ W $ als Rotationsfaktor bezeichnet, da es einen Punkt auf dem Einheitsumfang darstellt, dessen Rotationswinkel ** im Uhrzeigersinn ** und $ \ frac {2 \ pi} {N} $ ist. .. Daher gilt der folgende relationale Ausdruck.

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

Dieser relationale Ausdruck ist im Grunde der Wert, wenn der Drehwinkel $ k \ pi $ ist. Diese Formel wird überall verwendet, um die FFT-Formel zu transformieren.

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