[PYTHON] Comprendre les règles et les fonctions convexes d'Armijo
Quelle est la méthode du gradient?
En gros, quelle est la méthode du gradient? "En différenciant à plusieurs reprises la fonction inconnue que vous voulez trouver, vous pouvez trouver le point où la pente est proche de 0, c'est-à-dire ** minimum / maximum ** (parfois elle s'installe au maximum / minimum ...)." est.
Même si vous en dites autant, on pourrait vous demander «Et alors?» ...
Ce qui me rend heureux, c'est que je peux créer des fonctions plausibles à partir de tracés de beaucoup de données et de choses difficiles à différencier analytiquement.
analyse de régression
Une fonction plausible peut être dérivée d'une grande quantité de données en utilisant la méthode du gradient.
Prenons un exemple concret. Supposons qu'il y ait 50 données avec $ x_i, y_i $ dans le $ i $ th
Vous pouvez le tracer comme ça.
Si on vous dit: "Tracez une ligne droite comme celle du milieu!"
Je pense que la plupart des gens tracent une telle ligne droite. En bref, trouver cette ligne droite est simplement lu comme une analyse de régression.
À propos, l'analyse de régression lorsqu'il existe une variable comme cette fonction est appelée ** analyse de régression simple **.
Ensuite, j'expliquerai la ** méthode du carré minimum **, qui est l'une des méthodes requises pour l'analyse de régression.
Méthode du carré minimum
Pour créer une fonction plausible à partir de plusieurs données, procédez comme suit.
- Créez une fonction appropriée.
- Calculez le carré de la distance par rapport à chaque donnée. (Le degré de séparation est appelé ** erreur **.)
- Additionnez les carrés de toutes les erreurs de données.
- A partir du résultat de 3., déterminez le coefficient de la fonction créée en 1. et créez une fonction plausible.
Jetons un coup d'œil à chacun d'eux.
1. Créez une fonction appropriée.
Cette fois, cela ressemble à une ligne droite, j'ai donc préparé une fonction à une variable. Le but ultime de la méthode des moindres carrés est de trouver $ a, b $ pour cette fonction.
\hat{y}_i = ax_i + b
Ici, définissons les variables. $ x_i et y_i $ sont les valeurs des $ i $ th données. D'autre part, $ \ hat {y_i} $ est la valeur prédite des $ i $ èmes données. Cette $ \ hat {y_i} $ est parfois appelée ** valeur prédite **.
Cette fonction doit également changer de forme en fonction de la variation des données.
2. Calculez le carré de l'erreur de chaque donnée.
Cette ligne bleue est l'erreur, et il est nécessaire d'étudier cette longueur une par une.
Dans la formule, l'erreur peut être écrite comme suit.
y_i - \hat{y_i} = y_i - (ax_i + b)
Cependant, si cela est laissé tel quel, le positif / négatif change en fonction de la relation de grandeur de $ y_i, \ hat {y_i} $, il n'est donc pas possible d'obtenir une erreur pure. Par conséquent, la valeur de cette erreur est au carré.
Alors le carré de l'erreur est
(y_i - \hat{y_i})^2 = (y_i - (ax_i + b))^2
Vous pouvez le demander comme ça.
Concentrons-nous uniquement sur les 20e données pour plus de simplicité.
Ces données sont approximativement $ (x_ {20}, y_ {20}) = (0,6, 4,5) $, donc Donc, si $ 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}
Ce sera.
De cette manière, le carré des 50 erreurs est calculé.
3. Additionnez les carrés de toutes les erreurs de données.
Comme le titre l'indique, la somme de ce qui a été calculé en 2. est calculée. Si vous l'écrivez dans une formule mathématique,
\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}
Ce sera. Ici, $ N $ est le nombre de données, donc cette fois il est de 50.
$ A, b $ quand cette fonction $ S (a, b) $ est le minimum est la variable que vous voulez trouver cette fois.
4. Détermination de a et b
La méthode du gradient détermine cela. Puisque $ S (a, b) $ est une fonction convexe, la valeur minimale de la fonction est dérivée de la méthode du gradient le plus raide ou similaire. J'expliquerai en détail dans la partie 2.
Jusqu'à présent, il est devenu une connaissance indispensable pour exécuter la méthode du gradient, mais comme il comprend de nombreux points de vue mathématiques, il est normal que les gens l'ignorent en disant "Je ne veux pas de ça!".
Matrice de Hesse et valeurs semi-positives
C'est un concept nécessaire pour expliquer la fonction convexe suivante.
Qu'est-ce que la ** procession de Hesse **?
$ n $ Pour la fonction variable $ f (x1, x2, ⋯, xn) $ Une matrice $ n × n $ dont le composant> $ ij $ est $ \ frac {∂ ^ 2f} {∂x_i∂x_j} $ est appelée une matrice de Hesse.
Il y a. (Référence 2)
En d'autres termes
\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}
C'est une telle matrice. Comme vous pouvez le voir, la matrice de Hesse est une matrice symétrique.
** La valeur semi-fixe ** est définie comme suit. (Référence 1)
Généralement, lorsque la matrice symétrique $ A $ satisfait "$ x ^ ⊤ Ax ≥ 0 $ pour tout vecteur $ x $", on l'appelle une valeur semi-fixe. Aussi, pour "tout vecteur $ x ≠ 0 $" Lorsque $ x ^ ⊤ Ax> 0 $ ”est satisfait, cela s'appelle une valeur positive.
De la définition qui est une valeur semi-fixe
- Pour tout vecteur réel $ n $ dimensionnel $ \ bf {x} $, la forme quadratique $ bf {x} ^ ⊤ Abf {x} $ est non négative
- Toutes les valeurs uniques de $ A $ ne sont pas négatives
- Une matrice carrée réelle $ U $ existe et peut être exprimée comme $ A = U ^ ⊤ U $
- Toutes les expressions matricielles mineures majeures de $ A $ sont non négatives
On peut dire que la matrice qui satisfait est une valeur semi-régulière. Comme je l'expliquerai plus tard, lorsque la ** matrice de Hesse $ \ Delta {S} $ est une valeur semi-régulière, $ S $ est une fonction convexe. ** **
Maintenant que vous êtes prêt, regardons la fonction convexe.
Fonction convexe
** La fonction convexe ** est un concept nécessaire pour parvenir à une solution globale sans tomber dans une solution locale.
Voyons à quoi cela ressemble réellement.
En regardant la formule,
λf(x) + (1 − λ)f(y) ≥ f(λx + (1 − λ)y)\\
0 ≤ λ ≤ 1
Une fonction qui satisfait aux conditions ci-dessus est appelée une fonction convexe. Si vous le mâchez, "Le point $ R (= f (z)) $ existant entre les points $ P (= f (x)) $ et le point $ Q (= f (y)) $ existant sur la fonction $ f $ est une ligne droite. Quand il est plus petit que le point $ S $ existant sur $ PQ $, on l'appelle une fonction convexe. " Ce sera.
Si la fonction à optimiser est une fonction convexe, elle a la bonne propriété que la solution optimale locale et la solution optimale globale correspondent.
Vous pouvez comprendre cela en regardant la figure ci-dessous.
Par conséquent, je voudrais déduire que la fonction des moindres carrés $ S $ mentionnée ci-dessus est une fonction convexe. Pour dire que $ S $ est une fonction convexe, il suffit que $ \ Delta {S} $ soit une valeur semi-établie.
\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}
Si tu le dis La fonction des moindres carrés $ S $ est
\begin{align}
S
&=a^2s_{xx}+2as_x-2as_{xy}-2bs_y+s_{yy}+Nb^2
\end{align}
Ce sera. Si vous essayez de différencier partiellement cela avec $ a et b $, respectivement
\begin{align}
\frac{∂Q}{∂a}&=2s_{xx}a + 2s_xb - 2s_{xy}\\
\frac{∂Q}{∂b}&=2s_{x}a + 2Nb - 2s_{y}
\end{align}
Donc, si vous créez $ S $ une matrice de Hesse basée sur ceci
\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}
Ce sera.
A partir de la condition 1 qui est la valeur semi-positive ci-dessus, il suffit de montrer que "la forme quadratique de $ \ Delta {S} $ est non-négative". $ \ Sum_ {i} ^ {N} x_i ^ 2 = s_ {xx}, \ sum_ {i} ^ {N} x_i = s_x $, donc
\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}
Puisque $ \ Delta {S} $ est une valeur semi-positive, nous pouvons prouver que la fonction objectif $ S $ créée par la méthode des moindres carrés est une fonction convexe. À partir de là, on peut voir que la fonction créée par la méthode des moindres carrés est une fonction convexe et que la solution locale est la solution optimale.
Pour plus de détails, voir Référence 1 Référence 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% Jetez un œil à A2% E6% 95% B0). C'était très facile à comprendre car je l'ai même prouvé. De plus, l'image est [Référence 6](https://qiita.com/hiyoko9t/items/6742e7dc121cf4cbef09#%E5%87%B8%E8%A8%88%E7%94%BB%E5%95%8F%E9% J'ai cité A1% 8C).
Définition de la différenciation
Ici, je vais vous expliquer la définition de la différenciation utilisée dans la règle de $ Armijo $ expliquée ci-dessous.
{\nabla}f(x_k)={\lim_{h \to 0}}\frac{f(x+h)-f(x)}{h}
Si l'erreur est $ o (h) $,
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}
Peut être exprimé comme. Bien sûr, ce $ o (h) $ est
\lim_{h \to 0}o(h) = 0
Cependant, lorsque $ h $ prend une valeur qui n'est pas assez petite, $ o (h) $ ne peut pas être spécifié.
Règles Armijo
La règle $ Armijo $ est l'une des méthodes pour sélectionner le taux d'apprentissage $ t $.
Définissez cette fonction objectif comme $ f (x_k) $ comme le nombre de fois que $ k $ a été appris.
Pour passer de $ x_k $ à $ x_ {k + 1} $ à la coordonnée suivante, supposons que vous vouliez vous déplacer dans la direction décroissante $ d_k $ du taux d'apprentissage $ t_k $. Puis
\begin{equation}
f(\textbf{x}_{k+1})=f(\textbf{x}_k + t_k\textbf{d}_k)\tag{2}
\end{equation}
Peut être écrit comme.
La direction de descente $ d_k $ apparue pour la première fois ici est
\begin{equation}
{\nabla}f(\textbf{x}_k)^\mathsf{T}\textbf{d}_k<0\tag{3}
\end{equation}
C'est un vecteur qui satisfait. Cela signifie que si la pente $ \ nabla {f (x_k)} $ est positive, elle tombera dans le sens négatif, et si la pente $ \ nabla {f (x_k)} $ est négative, elle tombera dans le sens positif. Cela a du sens quand on y pense. De plus, $ d_k $ peut avoir une longueur de $ 1 $ car l'orientation est seulement importante.
Revenant à l'histoire, si l'équation (2) est transformée en référence à l'équation (1)
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)
Peut être transformé. Si vous comparez cela avec celui avant l'étape
\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}
Ce sera. Ici, puisque $ o (t_k) $ est une erreur comme décrit ci-dessus, sa valeur change lorsque $ t_k $ augmente, mais ignorez-la lorsque $ t_k $ devient une valeur suffisamment petite. Je peux.
Si $ t_k $ est réglé sur une valeur si petite que $ o (t_k) $ peut être ignoré, la condition de l'équation (3) montre que le côté droit de l'équation (4) est négatif. De plus, le côté gauche de l'équation (4) est également une prémisse majeure que $ f (x_ {k + 1}) <f (x_k) $, donc elle est naturellement négative.
De ce qui précède, si vous jouez un peu avec l'équation (4)
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}\\
Cependant, définissez chaque variable comme suit.
\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}
Cette expression conditionnelle est la règle pour $ Armijo $. En d'autres termes, $ t $ qui satisfait cette formule peut être sélectionné comme taux d'apprentissage.
Maintenant, décomposons l'équation (5) immédiatement.
L'équation (5) doit être négative des deux côtés, donc le côté droit multiplié par $ \ gamma $ est plus grand que le côté gauche.
Le côté gauche est ennuyeux, donc pour résumer
\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}
Ce sera. De plus, si vous essayez de différencier cela avec $ t_k $,
\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}
Peut être transformé avec. Puisqu'il y a une partie similaire à l'équation (5), si vous essayez de remplacer l'équation (5) par les équations (6) et (7),
p(t_k) ≤ {\gamma}\frac{d}{dt_k}p(0)t_k\tag{8}
Ce sera.
$ \ frac {d} {dt_k} p (0) $ est la pente de la ligne tangente de $ p (t_k) $ à $ t_k = 0 $, donc elle est rouge quand $ \ gamma = 1 $ comme indiqué ci-dessous. Comme une ligne, c'est une tangente à $ p () t_k $ à $ t_k = 0 $.
D'autre part, lorsque $ \ gamma $ approche $ 0 $, la pente converge vers $ 0 $ comme le montre la ligne bleue.
De plus, si $ \ beta = 0.5 $ est défini ici,
Ce sera. Puisque $ l_k $ ne prend que des valeurs entières supérieures ou égales à $ 0 $, lorsque $ l_k $ augmente, $ t_k $ diminue et la plage est
0<t_k≤1
Ce sera. Puisqu'il est plus efficace d'augmenter le taux d'apprentissage autant que possible, augmentez $ l_k $ à partir de 0 $ et adoptez la valeur qui satisfait l'équation (5) comme taux d'apprentissage. En utilisant cette règle, la sélection du taux d'apprentissage peut être sélectionnée de manière optimale. Cependant, pour implémenter ce problème, il est nécessaire de deviner la forme de $ p '(t) $ à l'avance, donc une certaine ingéniosité est requise lors de son utilisation.
Cette fois, Référence 3, [Référence 4](http: // www. J'ai pensé basé sur kana-lab.c.titech.ac.jp/lecture/lec.2007.1st.suurijouhou1/06.2007.05.24.UnconstrainedOpt.pdf).
finalement
Cette fois, j'ai pu solidifier dans une certaine mesure la théorie requise pour la méthode du gradient. Si j'ai une chance, j'aimerais approfondir ma compréhension en utilisant des méthodes réelles.
Les références
・ Référence 1: Optimisation et fonction convexe (Matériel de conférence de l'Université de Tokyo) ・ Référence 2: Jugement de valeur extrême de la fonction multivariée et de la matrice de Hesse ・ Référence 3: Méthode de descente (supports de cours de l'Université de Kyoto) ・ Référence 4: [Problème d'optimisation sans contrainte (matériel de conférence de l'Université de Nagoya)](http://www.kana-lab.c.titech.ac.jp/lecture/lec.2007.1st.suurijouhou1/06.2007.05.24.UnconstrainedOpt .pdf) ・ Référence 5: [J'ai réfléchi aux mérites de la méthode de descente de gradient stochastique](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) ・ Référence 6: [Optimisation continue à connaître lors de l'apprentissage automatique](https://qiita.com/hiyoko9t/items/6742e7dc121cf4cbef09#%E5%87%B8%E8%A8%88%E7%94 % BB% E5% 95% 8F% E9% A1% 8C)
Recommended Posts