[PYTHON] Verstehe die Regeln und konvexen Funktionen von Armijo
Was ist die Gradientenmethode?
Was ist ungefähr die Gradientenmethode? "Durch wiederholtes Unterscheiden der unbekannten Funktion, die Sie suchen möchten, können Sie den Punkt finden, an dem die Steigung nahe bei 0 liegt, dh ** Minimum / Maximum ** (manchmal wird sie auf das Maximum / Minimum eingestellt ...)." ist.
Selbst wenn Sie so viel sagen, werden Sie möglicherweise gefragt: "Na und?" ...
Was mich glücklich macht, ist, dass ich plausible Funktionen aus Plots vieler Daten und Dingen erstellen kann, die analytisch schwer zu unterscheiden sind.
Regressionsanalyse
Eine plausible Funktion kann mit der Gradientenmethode aus einer großen Datenmenge abgeleitet werden.
Verwenden wir ein konkretes Beispiel. Angenommen, es gibt 50 Daten mit $ x_i, y_i $ im $ i $ th
Sie können es so zeichnen.
Wenn Ihnen gesagt wird: "Zeichnen Sie so eine gerade Linie in der Mitte!"
Ich denke, die meisten Leute ziehen eine so gerade Linie. Kurz gesagt, das Finden dieser geraden Linie wird nur als Regressionsanalyse gelesen.
Die Regressionsanalyse, wenn es eine Variable wie diese Funktion gibt, heißt übrigens ** einfache Regressionsanalyse **.
Als nächstes werde ich die ** Minimum-Square-Methode ** erläutern, eine der Methoden, die für die Regressionsanalyse erforderlich sind.
Minimum-Quadrat-Methode
Führen Sie die folgenden vier Schritte aus, um aus mehreren Daten eine plausible Funktion zu erstellen.
- Erstellen Sie eine entsprechende Funktion.
- Berechnen Sie das Quadrat, wie weit von den einzelnen Daten entfernt. (Der Trennungsgrad wird als ** Fehler ** bezeichnet.)
- Summieren Sie die Quadrate aller Datenfehler.
- Bestimmen Sie aus dem Ergebnis von 3. den Koeffizienten der in 1. erstellten Funktion und erstellen Sie eine plausible Funktion.
Werfen wir einen Blick auf jeden einzelnen.
1. Erstellen Sie eine entsprechende Funktion.
Dieses Mal sieht es wie eine gerade Linie aus, also habe ich eine Funktion mit einer Variablen vorbereitet. Das ultimative Ziel der Methode der kleinsten Quadrate ist es, $ a, b $ für diese Funktion zu finden.
\hat{y}_i = ax_i + b
Hier definieren wir die Variablen. $ x_i und y_i $ sind die Werte der $ i $ -ten Daten. Andererseits ist $ \ hat {y_i} $ der vorhergesagte Wert der $ i $ -ten Daten. Dieses $ \ hat {y_i} $ wird manchmal als ** vorhergesagter Wert ** bezeichnet.
Diese Funktion muss auch die Form entsprechend der Variation der Daten ändern.
2. Berechnen Sie das Fehlerquadrat der einzelnen Daten.
Diese blaue Linie ist der Fehler, und es ist notwendig, diese Länge einzeln zu untersuchen.
In der Formel kann der Fehler wie folgt geschrieben werden.
y_i - \hat{y_i} = y_i - (ax_i + b)
Wenn dies jedoch unverändert bleibt, ändern sich die positiven und negativen Werte in Abhängigkeit von der Größenbeziehung von $ y_i und \ hat {y_i} $, sodass es nicht möglich ist, einen reinen Fehler zu erhalten. Daher wird der Wert dieses Fehlers quadriert.
Dann ist das Quadrat des Fehlers
(y_i - \hat{y_i})^2 = (y_i - (ax_i + b))^2
Sie können so danach fragen.
Konzentrieren wir uns der Einfachheit halber nur auf die 20. Daten.
Diese Daten sind ungefähr $ (x_ {20}, y_ {20}) = (0,6, 4,5) $, also Also, wenn $ i = 20 $
\begin{align}
(y_{20} - \hat{y_{20}})^2
&= (y_{20} - (ax_{20} + b))^2\\
&= (4.5 - (a \times 0.6 + b))^2\\
&= \frac{9}{25}a^2+\frac{6}{5}ab +b^2-\frac{27}{5}a-9b+\frac{81}{4}
\end{align}
Es wird sein.
Auf diese Weise wird das Quadrat aller 50 Fehler berechnet.
3. Summieren Sie die Quadrate aller Datenfehler.
Wie der Titel schon sagt, wird die Summe dessen berechnet, was in 2. berechnet wurde. Wenn Sie es in einer mathematischen Formel schreiben,
\begin{align}
S
&=\sum_{i}^{N}{(y_i - \hat{y_i})^2} \\
&= \sum_{i}^{N}{(y_i - (ax_i + b))^2}\\
&= a^2(\sum_{i}^{N}x_i^2)+2a\sum_{i}^{N}{(bx_i-x_iy_i)}-2b\sum_{i}^{N}{y_i}+\sum_{i}^{N}y_i^2 + Nb^2
\end{align}
Es wird sein. Hier ist $ N $ die Anzahl der Daten, diesmal also 50.
$ A, b $, wenn diese Funktion $ S (a, b) $ das Minimum ist, ist die Variable, die Sie dieses Mal finden möchten.
4. Bestimmung von a und b
Die Gradientenmethode bestimmt dies. Da $ S (a, b) $ eine konvexe Funktion ist, wird der Minimalwert der Funktion von der Methode mit dem steilsten Gradienten oder dergleichen abgeleitet. Ich werde in Teil 2 ausführlich erklären.
Bis zu diesem Punkt ist es zu einem unverzichtbaren Wissen für die Durchführung der Gradientenmethode geworden, aber da es viele mathematische Gesichtspunkte enthält, ist es für die Leute in Ordnung, es zu überspringen und zu sagen: "Das will ich nicht!".
Hessen Matrix und semi-positive Werte
Dies ist ein Konzept, das zur Erklärung der folgenden konvexen Funktion erforderlich ist.
Was ist ** Hessen Prozession **?
$ n $ Für die Variablenfunktion $ f (x1, x2, ⋯, xn) $ Eine $ n × n $ -Matrix, deren> $ ij $ -Komponente $ \ frac {∂ ^ 2f} {∂x_i∂x_j} $ ist, wird als hessische Matrix bezeichnet.
Es gibt. (Referenz 2)
Mit anderen Worten
\begin{pmatrix}
\frac{∂^2f}{∂x^2_1} & \cdots & \frac{∂^2f}{∂x_1∂x_j}\\
\vdots & \ddots & \vdots \\
\frac{∂^2f}{∂x_i∂x_1} & \cdots & \frac{∂^2f}{∂x_i∂x_j}\\
\end{pmatrix}
Es ist so eine Matrix. Wie Sie sehen können, ist die Hessen-Matrix eine symmetrische Matrix.
** Halbfester Wert ** ist wie folgt definiert. (Referenz 1)
Wenn die symmetrische Matrix $ A $ "$ x ^ ⊤ Ax ≥ 0 $ für jeden Vektor $ x $" erfüllt, wird sie im Allgemeinen als halbfester Wert bezeichnet. Auch für "jeden Vektor $ x ≠ 0 $" Wenn $ x ^ ⊤ Ax> 0 $ ”erfüllt ist, wird dies als positiver Wert bezeichnet.
Aus der Definition ergibt sich ein halbfester Wert
- Für alle $ n $ dimensionalen reellen Vektoren $ \ bf {x} $ ist die quadratische Form $ bf {x} ^ ⊤ Abf {x} $ nicht negativ
- Alle eindeutigen Werte von $ A $ sind nicht negativ
- Eine reelle quadratische Matrix $ U $ existiert und kann ausgedrückt werden als $ A = U ^ ⊤ U $
- Alle großen Nebenmatrixausdrücke von $ A $ sind nicht negativ
Es kann gesagt werden, dass die Matrix, die erfüllt, ein halbregelmäßiger Wert ist. Wie ich später erklären werde, ist $ S $ eine konvexe Funktion, wenn die ** Hessen-Matrix $ \ Delta {S} $ ein semi-regulärer Wert ist. ** ** **
Nachdem Sie fertig sind, schauen wir uns die konvexen Funktionen an.
Konvexe Funktion
** Konvexe Funktion ** ist ein Konzept, das erforderlich ist, um eine globale Lösung zu erreichen, ohne in eine lokale Lösung zu fallen.
Mal sehen, wie es tatsächlich aussieht.
Betrachtet man die Formel,
λf(x) + (1 − λ)f(y) ≥ f(λx + (1 − λ)y)\\
0 ≤ λ ≤ 1
Eine Funktion, die die obigen Bedingungen erfüllt, wird als konvexe Funktion bezeichnet. Wenn Sie es kauen, "Der Punkt $ R (= f (z)) $, der zwischen den Punkten $ P (= f (x)) $ und dem Punkt $ Q (= f (y)) $ existiert, der auf der Funktion $ f $ existiert, ist eine gerade Linie. Wenn es kleiner ist als der auf $ PQ $ vorhandene Punkt $ S $, wird es als konvexe Funktion bezeichnet. " Es wird sein.
Wenn die zu optimierende Funktion eine konvexe Funktion ist, hat sie die gute Eigenschaft, dass die lokale optimale Lösung und die globale optimale Lösung übereinstimmen.
Sie können dies anhand der folgenden Abbildung verstehen.
Daher möchte ich ableiten, dass die oben erwähnte Funktion $ S $ mit dem kleinsten Quadrat eine konvexe Funktion ist. Um zu sagen, dass $ S $ eine konvexe Funktion ist, ist es ausreichend, wenn $ \ Delta {S} $ ein halb etablierter Wert ist.
\sum_{i}^{N}x_i^2 = s_{xx}, \sum_{i}^{N}x_i = s_x, \sum_{i}^{N}y_i^2 = s_{yy}, \sum_{i}^{N}y_i = s_y, \sum_{i}^{N}x_iy_i = s_{xy}
Wenn du sagst Die kleinste quadratische Funktion $ S $ ist
\begin{align}
S
&=a^2s_{xx}+2as_x-2as_{xy}-2bs_y+s_{yy}+Nb^2
\end{align}
Es wird sein. Wenn Sie versuchen, dies teilweise mit $ a bzw. b $ zu unterscheiden
\begin{align}
\frac{∂Q}{∂a}&=2s_{xx}a + 2s_xb - 2s_{xy}\\
\frac{∂Q}{∂b}&=2s_{x}a + 2Nb - 2s_{y}
\end{align}
Wenn Sie also $ S $ zu einer darauf basierenden hessischen Matrix machen
\begin{align}
\Delta{S}
&=
\begin{pmatrix}
\frac{∂^2f}{∂x^2} & \frac{∂^2f}{∂x∂y} \\
\frac{∂^2f}{∂y∂x} & \frac{∂^2f}{∂y^2}
\end{pmatrix}\\
&=
2
\begin{pmatrix}
s_{xx} & s_x \\
s_x & n
\end{pmatrix}
\end{align}
Es wird sein.
Aus Bedingung 1, die der obige halbpositive Wert ist, ist es ausreichend zu zeigen, dass "die quadratische Form von $ \ Delta {S} $ nicht negativ ist". $ \ Sum_ {i} ^ {N} x_i ^ 2 = s_ {xx}, \ sum_ {i} ^ {N} x_i = s_x $, also
\begin{align}
2
\begin{pmatrix}
t & k
\end{pmatrix}
\begin{pmatrix}
s_{xx} & s_x \\
s_x & n
\end{pmatrix}
\begin{pmatrix}
t\\
k
\end{pmatrix}
&=
2(s_{xx}t^2+2s_xtk + Nk^2)\\
&=
2(t^2\sum_{i}^{N}{x_i^2}+2tk\sum_{i}^{N}{x_i}+Nk^2)\\
&=
2\sum_{i}^{N}{(t^2x_i^2+2tkx_i+k^2)}\\
&=
2\sum_{i}^{N}{(tx_i+k)^2} ≥0
\end{align}
Da $ \ Delta {S} $ ein semi-regulärer Wert ist, können wir beweisen, dass die mit der Methode der kleinsten Quadrate erzeugte Zielfunktion $ S $ eine konvexe Funktion ist. Daraus ist ersichtlich, dass die durch die Methode der kleinsten Quadrate erzeugte Funktion eine konvexe Funktion ist und die lokale Lösung als optimale Lösung gilt.
Einzelheiten finden Sie in Referenz 1 Referenz 5 / 028c457880c0ec576e27 #% E6% 9C% 80% E5% B0% 8F% E4% BA% 8C% E4% B9% 97% E6% B3% 95% E3% 81% AF% E5% 87% B8% E9% 96% Schauen Sie sich A2% E6% 95% B0) an. Es war sehr leicht zu verstehen, weil ich es sogar bewiesen habe. Darüber hinaus lautet das Bild [Referenz 6](https://qiita.com/hiyoko9t/items/6742e7dc121cf4cbef09#%E5%87%B8%E8%A8%88%E7%94%BB%E5%95%8F%E9% Ich zitierte aus A1% 8C).
Definition der Differenzierung
Hier werde ich die Definition der Differenzierung erläutern, die in der unten erläuterten Regel von $ Armijo $ verwendet wird.
{\nabla}f(x_k)={\lim_{h \to 0}}\frac{f(x+h)-f(x)}{h}
Wenn der Fehler $ o (h) $ ist,
o(h) = \frac{f(x+h)-f(x)}{h} - {\nabla}f(x_k)
\begin{equation}
f(x+h) = f(x) + h{\nabla}f(x_k) + ho(h)\tag{1}
\end{equation}
Kann ausgedrückt werden als. Natürlich ist dies $ o (h) $
\lim_{h \to 0}o(h) = 0
Wenn jedoch $ h $ einen Wert annimmt, der nicht klein genug ist, kann $ o (h) $ nicht angegeben werden.
Armijo regiert
Die $ Armijo $ -Regel ist eine der Methoden zur Auswahl der Lernrate $ t $.
Setzen Sie diese Zielfunktion als $ f (x_k) $, wie oft $ k $ gelernt wurde.
Angenommen, Sie möchten $ d_k $ um die Lernrate $ t_k $ nach unten bewegen, um von $ x_k $ zu $ x_ {k + 1} $ an der nächsten Koordinate zu wechseln. Dann
\begin{equation}
f(\textbf{x}_{k+1})=f(\textbf{x}_k + t_k\textbf{d}_k)\tag{2}
\end{equation}
Kann geschrieben werden als.
Die Abstiegsrichtung $ d_k $, die hier zuerst erschien, ist
\begin{equation}
{\nabla}f(\textbf{x}_k)^\mathsf{T}\textbf{d}_k<0\tag{3}
\end{equation}
Es ist ein Vektor, der erfüllt. Dies bedeutet, dass wenn die Steigung $ \ nabla {f (x_k)} $ positiv ist, sie in die negative Richtung fällt, und wenn die Steigung $ \ nabla {f (x_k)} $ negativ ist, fällt sie in die positive Richtung. Es macht Sinn, wenn Sie darüber nachdenken. Außerdem kann $ d_k $ $ 1 $ lang sein, da die Ausrichtung nur wichtig ist.
Zurück zur Geschichte, wenn Gleichung (2) unter Bezugnahme auf Gleichung (1) transformiert wird
f(\textbf{x}_k+t_k\textbf{d}_k) = f(\textbf{x}_k) + t_k{\nabla}f(\textbf{x}_k)^\mathsf{T}\textbf{d}_k + t_ko(t_k)
Kann transformiert werden. Wenn Sie dies mit dem vor dem Schritt vergleichen
\begin{align}
f(\textbf{x}_{k+1}) - f(\textbf{x}_k) &=
f(\textbf{x}_k+t_k\textbf{d}_k) - f(\textbf{x}_k)\\ &= t_k{\nabla}f(\textbf{x}_k)^\mathsf{T}\textbf{d}_k + t_ko(t_k)\\
&= t_k({\nabla}f(\textbf{x}_k)^\mathsf{T}\textbf{d}_k + o(t_k))\tag{4}
\end{align}
Es wird sein. Da $ o (t_k) $ ein Fehler ist, wie oben beschrieben, ändert sich sein Wert hier, wenn $ t_k $ zunimmt, ignoriert ihn jedoch, wenn $ t_k $ ein ausreichend kleiner Wert wird. Ich kann.
Wenn $ t_k $ auf einen Wert gesetzt wird, der so klein ist, dass $ o (t_k) $ ignoriert werden kann, zeigt die Bedingung von Gleichung (3), dass die rechte Seite von Gleichung (4) negativ ist. Auch die linke Seite von Gleichung (4) ist eine wichtige Voraussetzung dafür, dass $ f (x_ {k + 1}) <f (x_k) $ ist, also natürlich negativ.
Von oben, wenn Sie ein wenig mit Gleichung (4) spielen
f(\textbf{x}_{k+1})-f(\textbf{x}_k) ≤ \gamma\beta^{l_k}{\nabla}f(\textbf{x}_k)^\mathsf{T}\textbf{d}_k\tag{5}\\
Stellen Sie jedoch jede Variable wie folgt ein.
\begin{cases}
\begin{align}
\gamma, \beta &\in (0, 1)\\
t_k &= \beta^{l_k}\\
l_k &= 0, 1, 2, 3 \cdots
\end{align}
\end{cases}
Dieser bedingte Ausdruck ist die Regel für $ Armijo $. Mit anderen Worten, $ t $, das diese Formel erfüllt, kann als Lernrate ausgewählt werden.
Lassen Sie uns nun Gleichung (5) sofort auflösen.
Gleichung (5) sollte auf beiden Seiten negativ sein, daher ist die rechte Seite multipliziert mit $ \ gamma $ größer als die linke Seite.
Die linke Seite ist nervig, um es zusammenzufassen
\begin{align}
p(t_k)
&= f(\textbf{x}_k+t_k\textbf{d}_k) - f(\textbf{x}_k)\tag{6}\\
(&= f(\textbf{x}_k+\beta^{l_k}\textbf{d}_k) - f(\textbf{x}_k))\\
\end{align}
Es wird sein. Wenn Sie versuchen, dies mit $ t_k $ zu unterscheiden,
\frac{d}{dt_k}p(t_k) = {\nabla}f(\textbf{x}_k+t_k\textbf{d}_k)^\mathsf{T}\textbf{d}_k\\
\frac{d}{dt_k}p(0) = {\nabla}f(\textbf{x}_k)^\mathsf{T}\textbf{d}_k\tag{7}
Kann mit transformiert werden. Da es einen ähnlichen Teil wie in Gleichung (5) gibt, wenn Sie versuchen, Gleichung (5) durch die Gleichungen (6) und (7) zu ersetzen,
p(t_k) ≤ {\gamma}\frac{d}{dt_k}p(0)t_k\tag{8}
Es wird sein.
$ \ frac {d} {dt_k} p (0) $ ist die Steigung der Tangentenlinie von $ p (t_k) $ bei $ t_k = 0 $, daher ist sie rot, wenn $ \ gamma = 1 $ (siehe unten). Wie eine Linie ist es eine Tangente an $ p () t_k $ bei $ t_k = 0 $.
Wenn sich $ \ gamma $ $ 0 $ nähert, konvergiert die Steigung dagegen gegen $ 0 $, wie durch die blaue Linie dargestellt.
Wenn hier $ \ beta = 0.5 $ festgelegt ist,
Es wird sein. Da $ l_k $ nur ganzzahlige Werte größer oder gleich $ 0 $ annimmt, nimmt $ t_k $ mit zunehmendem $ l_k $ ab und der Bereich ist
0<t_k≤1
Es wird sein. Es ist effizienter, wenn die Lernrate so groß wie möglich ist. Erhöhen Sie also $ l_k $ von $ 0 $ und übernehmen Sie den Wert, der Gleichung (5) erfüllt, als Lernrate. Mit dieser Regel kann die Auswahl der Lernrate optimal ausgewählt werden. Um dieses Problem zu implementieren, ist es jedoch erforderlich, die Form von $ p '(t) $ im Voraus zu erraten, sodass bei der Verwendung ein gewisser Einfallsreichtum erforderlich ist.
Diesmal Referenz 3, [Referenz 4](http: // www. Ich dachte basierend auf kana-lab.c.titech.ac.jp/lecture/lec.2007.1st.suurijouhou1/06.2007.05.24.UnconstrainedOpt.pdf).
Schließlich
Dieses Mal konnte ich die für die Gradientenmethode erforderliche Theorie bis zu einem gewissen Grad festigen. Wenn ich eine Chance habe, möchte ich mein Verständnis mit tatsächlichen Methoden vertiefen.
Verweise
・ Referenz 1: Optimierung und konvexe Funktion (Vorlesungsmaterial der Universität Tokio) ・ Referenz 2: Extremwertbeurteilung der multivariaten Funktion und der Hessen-Matrix ・ Referenz 3: Abstiegsmethode (Vorlesungsunterlagen der Universität Kyoto) ・ Referenz 4: [Problem der uneingeschränkten Optimierung (Vorlesungsmaterial der Nagoya University)](http://www.kana-lab.c.titech.ac.jp/lecture/lec.2007.1st.suurijouhou1/06.2007.05.24.UnconstrainedOpt .pdf) ・ Referenz 5: [Ich habe über die Vorzüge der stochastischen Gradientenabstiegsmethode nachgedacht](https://qiita.com/koshian2/items/028c457880c0ec576e27#%E6%9C%80%E5%B0%8F%E4%BA%8C % E4% B9% 97% E6% B3% 95% E3% 81% AF% E5% 87% B8% E9% 96% A2% E6% 95% B0) ・ Referenz 6: [Kontinuierliche Optimierung, die Sie beim maschinellen Lernen kennen sollten](https://qiita.com/hiyoko9t/items/6742e7dc121cf4cbef09#%E5%87%B8%E8%A8%88%E7%94 % BB% E5% 95% 8F% E9% A1% 8C)
Recommended Posts