[機械学習] 勾配降下法

[機械学習] 勾配降下法

 この記事は「微分と偏微分」に関する基礎的な知識を前提に書かれています。
 数学については、『Excel VBA 数学教室』の『数学事典』 を参照してください。

勾配降下法(最急降下法)のアルゴリズム

 ある関数の最小値を数値的に求める方法として、古くから勾配降下法(最急降下法)というアルゴリズムが知られています。勾配降下法は適当な所にボールを置いて手を離し、斜面に沿って転がしながら、最終的に落ち着いた場所を最小値とするようなイメージのアルゴリズムです。

勾配降下法による最小値の探索① 2次関数

 簡単な例として、2 次関数 $f(x)=x^2$ の最小値を勾配降下法で求めてみましょう。

 勾配法(最急降下法)の概念図

 この関数の点 $x$ における勾配(傾き)は導関数 $f'(x)=2x$ で与えられます。
 最初に適当な点(初期値)$x_0$ を決めます。
 どこでもいいのですが、とりあえず $x_0=2$ としておきます。
 初期値における勾配は
 
\[f'(x_0)=2x_0=4\]
です。上って行く方向とは逆に点を動かすために、この勾配に学習率とよばれる正の係数 $\alpha$ を掛けた値を $x_0$ から引いて(すなわち $x$ 軸の負の方向に点を移動させて)、その点を $x_1$ とします。
 
\[x_1=x_0-\alpha f'(x_0)=2-4\alpha\]
 $\alpha=0.1$ と決めると
 
\[x_1=2-0.4=1.6\]
となって、少しだけ原点に近づいたことがわかります。この点で再び勾配を計算します。
 
\[f'(x_1)=2\times 1.6=3.2\]
 先ほどと同じように、この勾配を使って次の点 $x_2$ を決めます。
 
\[x_2=x_1-\alpha f'(x_1)=1.6-0.1\times 3.2=1.6-0.32=1.28\]
 また少し原点に近づきました。さらに、これを繰り返して、$x_3,\ x_4,\ ......$ を求めていけば、いずれは最小値をとる場所(原点)に近い所に達します。一般化すると、$x_k$ は
 
\[x_k=x_{k-1}-\alpha f'(x_{k-1})\]
によって与えられます。以下のコードでは上記のアルゴリズムにしたがって最小値を探索しながら、Matplotlib を使って初期値から窪みの底まで移動する点の軌跡をプロットします。

# https://python.atelierkobato.com/steep/

# 勾配降下法 リストM1-A

# NumPyをインポート
import numpy as np

# matplotlib.pyplotをインポート
import matplotlib.pyplot as plt

# ★★★★★★★★★★

# 2次関数と導関数の定義

# 2次関数の定義
def func(x):
    return x**2

# func(x)の導関数
def dfunc(x):
    return 2*x

# ★★★★★★★★★★

# 2次関数グラフの描画

# Figureを作成
fig = plt.figure()

# FigureにAxesを1つ追加
ax = fig.add_subplot(111)

# Axesのタイトルを設定
ax.set_title("y = x**2", fontsize = 16)

# 軸ラベルを設定
ax.set_xlabel("x", fontsize = 16)
ax.set_ylabel("y", fontsize = 16)

# 軸範囲を設定
ax.set_xlim([-4, 4])
ax.set_ylim([0, 16])

# -4~4まで0.1刻みの数値の配列
x = np.arange(-4, 4, 0.1)

# グラフに描く関数
y = func(x)

# Axesに2次関数のグラフを灰色で描画
# 描画優先順位:zorder=1
ax.plot(x, y, color = "gray", zorder = 1)

# ★★★★★★★★★★

# 勾配降下法による最小値の探索

# xの初期値
x_init = 2

# xに初期値を代入
x = x_init

# 学習率α
alpha = 0.01

# 収束判定条件
eps = 0.001

# 繰返しの最大数
k_max = 1000

for k in range(1, k_max):
    x -= alpha * dfunc(x)

    # (x, f(x))を散布図にプロット
    # マーカーサイズ:s=5,描画優先順位:zorder=2
    ax.scatter(x, func(x), s = 5, color = "red", zorder = 2)

    # 勾配の絶対値がeps以下になったらループ終了
    if abs(dfunc(x)) < eps:
        break

print(x)
0.0004989540132102893

 Python 勾配法(最急降下法)

 実行結果を見ると、$x=0$ に近い値が計算されています。
 収束判定条件 eps をもっと小さくすれば、精度を上げることができます。グラフを見ると、初期値 $x=2$ から $x=0$ まで点が移動していく様子がわかります。

 $\alpha$ を大きくとれば、1 step の移動距離を増やすことができますが、あまり大きすぎると、最小値のある点を大きく超えて反復運動を始めてしまい、最小値に落ち着くまでかえって時間がかかることもあります。
 

勾配降下法による最小値の探索② 複数の極小値をもつ関数

 勾配降下法は初期値の近くの窪みに落ち込んでしまうので、最小値というよりは、極小値を探すアルゴリズムです。複数の極小値をもつ関数に勾配降下法を適用すると、$x$ の初期値の選び方によっては浅い窪みに落ちて抜け出せなくなってしまう可能性があります。このような関数を扱う場合は、複数の初期値を選んで極小値となる $x$ を計算させて $f(x)$ の値を比較します。

 例として、$f(x)=x\cos 2x$ という関数の $0 \leq x \leq 2\pi$ の範囲における最小値を見つけます。下のグラフを見て分かる通り、この関数は範囲内に 2 つの極小値をもっています。

 Python xcos2x 勾配法(最急降下法)

 $f(x)$ を微分すると、$f'(x)=\cos 2x-2x\sin 2x$ となります。
 初期値として $x_0=1,\ 2,\ 3,\ 4,\ 5$ の点を選んで、それぞれの地点から点を転がして極小値を計算してみます。

# https://python.atelierkobato.com/steep/

# 勾配降下法 リストM1-B

# NumPyをインポート
import numpy as np

# matplotlib.pyplotをインポート
import matplotlib.pyplot as plt

# ★★★★★★★★★★

# 関数の定義
def func(x):
    return x * np.cos(2*x)

# 導関数
def dfunc(x):
    return np.cos(2*x) - 2*x*np.sin(2*x)

# ★★★★★★★★★★

#グラフの描画

# Figureを作成
fig = plt.figure()

# FigureにAxesを1つ追加
ax = fig.add_subplot(111)

# Axesのタイトルを設定
ax.set_title("y = xcos2x", fontsize = 16)

# 軸ラベルを設定
ax.set_xlabel("x", fontsize = 16)
ax.set_ylabel("y", fontsize = 16)

# 0~2piまで0.1刻みの数値の配列を定義
x = np.arange(0, 2*np.pi, 0.1)

# 軸範囲を設定
ax.set_xlim([0, 2*np.pi])

# グラフに描く関数
y = func(x)

# Axesにグラフをプロット
# 描画優先順位:zorder=2
ax.plot(x, y, color = "gray", zorder = 1)

# ★★★★★★★★★★

# 勾配降下法による最小値の探索

# 学習率α
alpha = 0.01

# 収束判定条件
eps = 0.001

# 繰返しの最大数
k_max = 1000

# 初期値=1,2,3,4,5
for j in range(1, 6):
    x = j

    for k in range(1, k_max):
        x -= alpha * dfunc(x)

        # (x, f(x))を散布図にプロット
        # マーカーサイズ:s=5,描画優先順位:zorder=2
        ax.scatter(x, func(x), s = 5, color = "red", zorder = 2)

        # 勾配の絶対値がeps以下になったらループ終了
        if abs(dfunc(x)) < eps:
            break

    print([x, func(x)])
[1.7126812216608585, -1.6441856347311665]
[1.7129365062860407, -1.6441856354446078]
[1.7129352914978424, -1.644185636629165]
[4.764623978488434, -4.738647111643302]
[4.764718523880823, -4.7386471042280265]

 Python 勾配降下法(最急降下法)実行結果

 実行結果を見ると、2 つの極小値が発見されていて、$x=4.765$ あたりで最小値となることがわかります。グラフを見ると、初期値 $x_0=1,\ 2,\ 3$ からスタートした点は浅い窪みに、$x_0=4,\ 5$ からスタートした点は深い窪みに落ちていることがわかります。
 

勾配降下法による最小値の探索③ 2変数関数

 次は 2 変数関数 $z=f(x, y)$ の最小値を勾配降下法で計算してみましょう。
 曲面上の各点 $(x, y)$ における勾配 (gradient) は
 
\[\nabla f=\begin{pmatrix}\cfrac{\partial f}{\partial x}\\
\cfrac{\partial f}{\partial y}\end{pmatrix}\]
というベクトルで表され、その大きさは
 
\[|\nabla f|=\sqrt{\left(\frac{\partial f}{\partial x}\right)^2+\left(\frac{\partial f}{\partial y}\right)^2}\]
で計算できます。したがって、あるステップにおける点の位置は学習率 $\alpha$ を用いて
 
\[\begin{pmatrix}x_k\\ y_k\end{pmatrix}=
\begin{pmatrix}x_{k-1}\\ y_{k-1}\end{pmatrix}
-\alpha\begin{pmatrix}\left.\cfrac{\partial f}{\partial x}\right|_{x_{k-1}}\\\left.\cfrac{\partial f}{\partial y}\right|_{x_{k-1}}\end{pmatrix}\]
と表すことができます。例として $z=x^2+y^2$ の最小値を求めるコードを書いてみます。この関数の勾配を求めておきましょう。$z$ を $x$ と $y$ で偏微分すると
 
\[\frac{\partial z}{\partial x}=2x,\quad \frac{\partial z}{\partial y}=2y\]
となるので、この関数の各点における勾配は $\displaystyle\binom{2x}{2y}$、その大きさは $\sqrt{(2x)^2+(2y)^2}$ で与えられます。

# https://python.atelierkobato.com/steep/

# 勾配降下法 リストM1-C

# 必要なモジュールのインポート
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import axes3d

# -------------------------

# 関数の定義
def func(x ,y):
    return x**2 + y**2

# 勾配(グラディエント)
def grad(x, y):
    return np.array([2*x, 2*y])

# ★★★★★★★★★★

# Figureを追加
fig = plt.figure(figsize = (10, 6))

# 3DAxeSを追加
ax = fig.add_subplot(111, projection="3d")

# 軸ラベルを設定
ax.set_xlabel("x", size = 16)
ax.set_ylabel("y", size = 16)
ax.set_zlabel("z", size = 16)

# 格子点の作成
X, Y = np.mgrid[-10:10, -10:10]

# 高度の計算式
Z = func(X, Y)

# ワイヤーフレームを描画
ax.plot_wireframe(X, Y, Z, color = "blue", zorder = 1)

# 視点の設定
ax.view_init(45, 45)

# ★★★★★★★★★★

# 勾配降下法による最小値の探索

# 初期値の設定
x_init, y_init = (-8, -4)

# x,yに初期値を代入
x, y = (x_init, y_init)

# 学習率α
alpha = 0.01

# 収束判定条件
eps = 0.001

# 繰返しの最大数
k_max = 10000

for k in range(1, k_max):
    x -= alpha * grad(x, y)[0]
    y -= alpha * grad(x, y)[1]

    # (x, f(x))を散布図にプロット
    ax.scatter(x, y, func(x, y), s = 2, color = "red", zorder = 2)

    # 勾配の大きさの計算
    d = np.sqrt(grad(x, y)[0]**2 + grad(x, y)[1]**2)
    
    # 勾配の大きさがeps以下になったらループ終了
    if d < eps:
        break

print((x, y))
(-0.00044436178008024454, -0.00022218089004012227)

 Python 勾配降下法による2変数関数の最小値の決定
 
 曲面はワイヤーフレームで、点の軌跡は散布図で描いています。
 初期値から窪みに落ちてゆく様子がわかります。
 最終的には、ほぼ $(0, 0)$ の点に落ち着いています。

 細かい事を言えばきりがないのですが、中には勾配がどの点においても一定であるような関数も存在していて(たとえば $z=\sqrt{x^2+y^2}$)、そのような関数では窪みが尖っているので、極小値の近くに達しても勾配は一向に緩やかにならず、eps の判定にかかりません。それでも学習率の値を小さくして、繰り返し回数を十分に大きくとっておけば、勾配降下法のアルゴリズムにしたがって点は下へ下へと落ちていくので、最小値を発見することはできます。多少はステップごとに値が揺れますが、学習率の値が小さければ、窪みの中心付近における反復運動はとても小さくなります。

 ≫ 線型回帰モデル① 勾配降下法によるパラメータの決定