機械学習 – 確率的勾配降下法と Python の実装例

概要

ディープラーニングの最適化に使用されるアルゴリズムである確率的勾配降下法について解説します。

勾配降下法

確率的勾配降下法は勾配降下法が元になっています。勾配降下法については以下の記事を参照してください。

[blogcard url=”https://pystyle.info/ml-gradient-descent”]


アルゴリズム 最急降下法

  1. 初期値 w0\boldsymbol{w}_0 を決める。
  2. 勾配 f(wt;x)\nabla f (\boldsymbol{w}_t; \boldsymbol{x}) を計算し、f(wt;x)=0\nabla f (\boldsymbol{w}_t; \boldsymbol{x}) = \boldsymbol{0} の場合、終了する。
  3. 点を次のように更新する。

    wt+1=wtαf(wt;x) \boldsymbol{w}_{t + 1} = \boldsymbol{w}_t -\alpha \nabla f (\boldsymbol{w}_t; \boldsymbol{x})

  4. 2 に戻る。

確率的勾配降下法

データセットを x=(x1,x2,,xn)\mathbf{x} = (x_1, x_2, \cdots, x_n)、最適化対象のパラメータを w\mathbf{w} としたとき、目標関数 f(w;x)f(\mathbf{w}; \mathbf{x}) が以下のように各サンプルから計算される関数 fi(w;xi)f_i(\mathbf{w};x_i) の和の形で表せる場合を対象とします。

f(w;x)=i=1Nfi(w;xi) f(\mathbf{w}; \mathbf{x}) = \sum_{i = 1}^N f_i(\mathbf{w};x_i)

例えば、最小二乗誤差はサンプル xix_i に対応する正解を yiy_i、パラメータで表される関数の形状 (例 g(x)=ax+bg(x) = ax + b) を g(x)g(x) としたとき、

f(w;x)=1Ni=1N(g(w;xi)yi)2 f(\mathbf{w}; \mathbf{x}) = \frac{1}{N} \sum_{i = 1}^N (g(\mathbf{w}; x_i) – y_i)^2

と和で表す形になっています。

確率的勾配降下法は、すべてのサンプルを使って損失を計算する代わりに、ランダムに選んだサンプル1つで計算した fif_i の勾配でパラメータを更新します。


アルゴリズム 確率的最急降下法

  1. 初期値 w0\boldsymbol{w}_0 を決める。
  2. サンプルの1つ xix_i をランダムに選ぶ。
  3. 勾配 fi(wt;xi)\nabla f_i(\boldsymbol{w}_t;x_i) を計算する。
  4. 点を次のように更新する。

    wt+1=wtαfi(wt;xi) \boldsymbol{w}_{t + 1} = \boldsymbol{w}_t -\alpha \nabla f_i(\boldsymbol{w}_t; x_i)

  5. 2 に戻る。

確率的勾配降下法の実装例

データセット (x1,y1),(x2,y2),,(xN,yN)(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N) で関数 g(x)=ax+bg(x) = a x + b のパラメータを二乗誤差を最小化することで求めます。

二乗誤差は以下のように計算できます。

f(w;x)=1Ni=1N(g(xi)yi)2 f(\mathbf{w}; \mathbf{x}) = \frac{1}{N} \sum_{i = 1}^N (g(x_i) – y_i)^2
  1. 初期値 a0,b0a_0, b_0 を決める。
  2. サンプルの1つ xi,yix_i, y_i をランダムに選ぶ。
  3. 勾配 (g(xi)yi)2\nabla (g(x_i) – y_i)^2 を計算する。
  4. 点を次のように更新する。

    at+1=atαa1N(g(xi)yi)2=atα2N(g(xi)yi)xi a_{t + 1} = a_t -\alpha \frac{\partial}{\partial a} \frac{1}{N} (g(x_i) – y_i)^2 = a_t -\alpha \frac{2}{N} (g(x_i) – y_i) x_i

    bt+1=btαb1N(g(xi)yi)2=btα2N(g(xi)yi) b_{t + 1} = b_t -\alpha \frac{\partial}{\partial b} \frac{1}{N} (g(x_i) – y_i)^2 = b_t -\alpha \frac{2}{N} (g(x_i) – y_i)

  5. 2 に戻る。

In [1]:
import matplotlib.pyplot as plt
import numpy as np

np.random.seed(0)


def g(x, a, b):
    return a * x + b


# g(x) = 6x + 2 でデータを作成する。
a_true, b_true = 6, 2
xs = np.arange(-10, 10)
ys = g(xs, a_true, b_true)


def get_sample():
    """ランダムにサンプルを1つ選択する。"""
    i = np.random.randint(len(xs))
    return xs[i], ys[i]


a, b = 3, 8  # パラメータの初期値
lr_a, lr_b = 0.1, 2

max_steps = 50  # 反復回数

history = [(a, b)]
for _ in range(max_steps):
    # ランダムにサンプルを選ぶ。
    x, y = get_sample()

    a -= lr_a * 2 / len(xs) * (g(x, a, b) - y) * x
    b -= lr_b * 2 / len(xs) * (g(x, a, b) - y)

    history.append((a, b))
history = np.array(history)

print(f"Optimization is complete. a={a:.6f}, b={b:.6f}")
Python
Optimization is complete. a=6.006183, b=2.033849
In [2]:
# 損失関数 MSE (\sum_{i = 0}^N (ax + b - y)^2) の形状をプロットする。
A, B = np.mgrid[:11, :11]
Y = np.square(A[..., np.newaxis] * xs + B[..., np.newaxis] - ys).mean(axis=-1)


def draw_history(A, B, Y, history, elev=70, azim=-70):
    fig = plt.figure(figsize=(14, 6))
    fig.suptitle("MSE Loss", fontsize=16)

    # 勾配のベクトル図を作成する。
    ax1 = fig.add_subplot(121)
    ax1.grid()
    ax1.set_title("Contour")
    ax1.set_xlabel("$a$", fontsize=15)
    ax1.set_ylabel("$b$", fontsize=15)
    ax1.plot(history[:, 0], history[:, 1], "ro-", mec="b", mfc="b", ms=4)
    contours = ax1.contour(A, B, Y, levels=15)
    ax1.clabel(contours, inline=1, fontsize=10, fmt="%.2f")

    # グラフを作成する。
    ax2 = fig.add_subplot(122, projection="3d")
    ax2.set_title("Surface")
    ax2.set_xlabel("$a$", fontsize=15)
    ax2.set_ylabel("$b$", fontsize=15)
    ax2.set_zlabel("$loss$", fontsize=15)
    ax2.plot(history[:, 0], history[:, 1], "ro-", mec="b", mfc="b", ms=4)
    ax2.plot_surface(A, B, Y, alpha=0.3, edgecolor="black")
    ax2.view_init(elev=elev, azim=azim)

    plt.show()


draw_history(A, B, Y, history)
print(history[-1])
Python
[6.00618334 2.0338487 ]

ミニバッチ勾配降下法

ミニバッチ勾配降下法は、すべてのサンプルを使って損失を計算する代わりに、ランダムに選んだ bb 個のサンプルで計算した勾配でパラメータを更新します。1個のサンプルで計算する勾配よりデータすべての勾配に近づくので、収束が早くなります。


アルゴリズム 確率的最急降下法

  1. 初期値 w0\boldsymbol{w}_0 を決める。
  2. bb 個のサンプルをランダムに選ぶ。
  3. 勾配 xbatchfi(wt;x)\nabla \sum_{x \in batch} f_i(\boldsymbol{w}_t;x) を計算する。
  4. 点を次のように更新する。

    wt+1=wtαxbatchfi(wt;x) \boldsymbol{w}_{t + 1} = \boldsymbol{w}_t -\alpha \nabla \sum_{x \in batch} f_i(\boldsymbol{w}_t;x)

  5. 2 に戻る。

In [3]:
import matplotlib.pyplot as plt
import numpy as np

np.random.seed(0)


def g(x, a, b):
    return a * x + b


# g(x) = 6x + 2 でデータを作成する。
a_true, b_true = 6, 2
xs = np.arange(-10, 10)
ys = g(xs, a_true, b_true)


def get_sample(batch_size):
    """ランダムにサンプルを1つ選択する。"""
    i = np.random.randint(len(xs), size=batch_size)
    return xs[i], ys[i]


a, b = 3, 8  # パラメータの初期値
lr_a, lr_b = 0.01, 0.1

max_steps = 50  # 反復回数

history = [(a, b)]
for _ in range(max_steps):
    # ランダムにサンプルを選ぶ。
    x, y = get_sample(10)

    a -= lr_a * 2 / len(xs) * ((g(x, a, b) - y) * x).sum()
    b -= lr_b * 2 / len(xs) * (g(x, a, b) - y).sum()

    history.append((a, b))
history = np.array(history)

print(f"Optimization is complete. a={a:.6f}, b={b:.6f}")


draw_history(A, B, Y, history)
print(history[-1])
Python
Optimization is complete. a=6.000140, b=2.037621
[6.00014004 2.03762096]

コメント

コメントする