はじめに

　この記事は、PC初心者がプログラミングの勉強のために書いたものとなっています。ご了承ください。「#1. pythonと機械学習」では、線形回帰の予測式を最小二乗法で導出しました。今回はもう一つの方法である、勾配降下法を解説します。
(タイトルにpythonなんて文字がありますが、pythonのコードは一切出てきません)

最小二乗法との違い

　線形回帰では、残差平方和を関数にして、その関数が最小値となるようなパラメータ(回帰係数, 切片など)を求めます。残差平方和の関数(損失関数)は常に「下に凸」となるので、損失関数を偏微分して、その結果が0となるパラメータを算出する方法が「最小二乗法」となります。最小二乗法や残差平方和の関数は下記URLで説明しています。
#1. pythonと機械学習 ~ 最小二乗法

　勾配降下法では、損失関数上のとある点から、どのように動けば (どの向きに、どのくらい移動するか) 値を小さくできるかを考え、これの繰り返しで、最小値を求めます。

勾配降下法

二変数関数

L(x, y)

が、あるとします。今回はこの関数の最小値を勾配降下法で求めてみます。

どの向きに移動するればよいか?

　初めに、最小値を求めたい関数上に存在する、とある点

(u_k, v_k)

からどの向きに移動すれば、最小値に近づくかを考えます。ここでは、「どの向きに移動するか」のみを考えるので、「どのくらい移動するか」の問題は無視し、とある点からの移動量を微量、かつ、一定であるとします。

全微分

　関数の変化を微量とするので、全微分を用います。全微分を求めるには、片方の変数を固定して、もう片方の変数で偏微分します。

uで偏微分します。

L_u(u, v) = \frac{L(u + du, v) - L(u, v)}{du}\\

L(u + du, v) = L(u, v) + L_u(u, v)du\\

vで偏微分します。

L_v(u, v) = \frac{L(u, v + dv) - L(u, v)}{dv}\\

L(u + du, v) = L(u, v) + L_u(u, v)du\\

よって、点(u, v)からu,v動かすと

L(u + du, v + dv) = L(u, v) + L_u(u, v)du + L_v(u, v)dv\\

L(u + du, v + dv) - L(u, v) = L_u(u, v)du + L_v(u, v)dv\\

と、なります。変化量をdLで表すと、

dL(u,v) = L_u(u, v)du + L_v(u, v)dv\\

今回は点

(u_k, v_k)\\

から、移動させるので、

dL(u_k,v_k) = L_u(u_k, v_k)du + L_v(u_k, v_y)dv\\

変化量を求める式が導出できました。

全微分は下記URLで図も交えながら解説されています。
https://mathlandscape.com/total-derivative/

内積

　ここで、内積の公式を思い出します。ふたつのベクトルa, bがあるとします。ふたつのベクトルを成分表示で、

a = (a_1,a_2)

b = (b_1,b_2)

と、表せるとします。ベクトルa,bの内積は、

a・b = a_1b_1 + a_2b_2\\

a・b = |a||b|cosθ\\

この式は、上記の全微分した式に当てはめてみると、

dL(u_k,v_k) = L_u(u_k, v_k)du + L_v(u_k, v_y)dv\\

dL(u_k,v_k) = (L_u(u_k, v_k), L_v(u_k, v_y)) ・ (du,dv)\\

dL(u_k,v_k) = |(L_u(u_k, v_k), L_v(u_k, v_y))| |(du,dv)|cosθ\\

ここでは、移動量を一定としているので、変数はθのみになっています。とある点からL(uk, vk)を最も減少させる向きを探すので、

dL(u_k,v_k) = |(L_u(u_k, v_k), L_v(u_k, v_k))||(du,dv)|cosθ\\

が、最小値(θ = 180°のとき)となれば良いです。
θ = 180°ということは、ふたつのベクトル、

(L_u(u_k, v_k), L_v(u_k, v_y))\\　(du,dv)\\

が、逆向きとなっているとき、となります。
よって、とある点

(u_k, v_k)\\

から移動する向きは、ベクトル

(L_u(u_k, v_k), L_v(u_k, v_y))\\

の逆向き、ということがわかりました。

どのくらい移動すればよいか

　移動する向きが分かったので、次は移動量を求めます。理解しやすいよう一変数関数

y = x^2

で考えます。この関数のとある点の微分値と、一定の値aに⁻の符号をつけて、掛け合わせたとき、

(移動量) = -2ax

とある点と最小値(0,0)との距離が近ければ近いほど移動量は小さく、遠ければ遠いほど移動量は大きくなります。この性質は、二変数以上の関数でも当てはまります。

勾配降下法の公式

二変数関数

L(x, y)

上にある点

(u_k, v_k)\\

で偏微分して、定数η を掛けて、移動量を求めます(行列の形で書きます)。

\eta\begin{pmatrix}
L_u(u_k, v_k) \\
 L_v(u_k, v_y) \\
\end{pmatrix}\\

移動する向きは、ベクトル

(L_u(u_k, v_k) ,
 L_v(u_k, v_y) )\\

の逆向きなので、

-\eta\begin{pmatrix}
L_u(u_k, v_k) \\
 L_v(u_k, v_y) \\
\end{pmatrix}\\

となります。移動後の点

(u_k, v_k) → (u_{k + 1}, v_{k + 1})\\

とすると移動量は、

\begin{pmatrix}
u_{k + 1}\\
u_{k + 1}\\
\end{pmatrix} - \begin{pmatrix}
u_k\\
u_k\\
\end{pmatrix} = -\eta\begin{pmatrix}
L_u(u_k, v_k) \\
 L_v(u_k, v_y) \\
\end{pmatrix}\\

よって、

\begin{pmatrix}
u_{k + 1}\\
u_{k + 1}\\
\end{pmatrix}
=
\begin{pmatrix}
u_k\\
u_k\\
\end{pmatrix}
-
\eta\begin{pmatrix}
L_u(u_k, v_k) \\
 L_v(u_k, v_y) \\
\end{pmatrix}\\

勾配降下法の公式が導出できました。この式の計算を繰り返せば、最小値を求めることができます。

学習率η

　「どのくらい移動すればよいか」の項目でaと置いた値ですが、aの値が大きすぎると、何回計算を繰り返しても最小値(0,0)に収束できません。aの値が小さすぎると、最小値に収束するまで、膨大な計算回数が必要となります。なので、適切な学習率ηを指定する必要があります。

参考

勾配降下法とは
https://rikeiminimalist.blog.jp/archives/5929478.html