勾配降下法
Overview
次のような制約条件のない最適化問題を考えます。
$ Minimize \quad 5x^2 - 6xy + 3y^2 + 6x - 6y
ここで、$ f(x, y) = 5x^2 - 6xy + 3y^2 + 6x - 6yとし、$ f(x, y) = kを満たす点の集合を考えると下図のようになります。つまりさまざまな$ kに対して等高線が描けます。
https://gyazo.com/ce9615a75b3decfd758d44b350bd417b
一方で$ fの瞬間の傾き（勾配）$ \nabla f = \begin{pmatrix} \frac{\partial f}{\partial x} \\ \frac{\partial f}{\partial y} \\ \end{pmatrix}を考えます。極値においては$ \nabla f=0となるので、そのような点が見つかれば計算は終了です。
Coding
初期値はわからないので、ランダムに値$ xを与えます。その後、初期値を導関数$ df(x)に代入し解きます。おそらくいきなり$ 0とはならないでしょう。そこで、初期値$ xから、解いた値を引きます。すると、新しい値$ x（移動後の$ x）が得られます。この工程を繰り返しやっていくと最終的に導関数は$ 0に近づきます。
次の最小値を計算してみます。
$ f(x, y) = 5x^2 - 6xy + 3y^2 + 6x - 6y
$ \nabla f = \begin{pmatrix} \frac{\partial f}{\partial x} \\ \frac{\partial f}{\partial y} \\ \end{pmatrix} = \begin{pmatrix}10x-6y+6\\-6x+6y-6\\ \end{pmatrix}
code: Python
import numpy as np
import matplotlib.pyplot as plt
class GradientDescent:
"""
勾配降下法アルゴリズム.
"""
def __init__(self, f, df, alpha=0.01, eps=1e-6):
"""
f: 最小化したい関数
df: 導関数
alpha: 学習率
eps: 許容誤差
"""
self.f = f
self.df = df
self.alpha = alpha
self.eps = eps
self.path = None
def solve(self, init):
"""
init: パラメータの初期値
最適解はデータ属性x_に保存され、最適値はデータ属性opt_に保存されます.
"""
x = init
path = []
grad = self.df(x)
path.append(x)
while (grad**2).sum() > self.eps**2:
x = x - self.alpha * grad
grad = self.df(x)
path.append(x)
self.path_ = np.array(path)
self.x_ = x
self.opt_ = self.f(x)
code: Python
def f(xx):
x = xx0
y = xx1
return 5 * x**2 - 6 * x * y + 3 * y**2 + 6 * x - 6 * y
def df(xx):
x = xx0
y = xx1
return np.array(10 * x - 6 * y + 6, -6 * x + 6 * y - 6)
algo = GradientDescent(f, df)
initial = np.array(1, 1)
algo.solve(initial)
print(algo.x_)
print(algo.opt_)
# 初期値（始点）をプロット
plt.scatter(initial0, initial1, color='k', marker='o')
# 収束までの点の移動をプロット
plt.plot(algo.path_:, 0, algo.path_:, 1, color='k', linewidth=1.5)
xs = np.linspace(-2, 2, 300)
ys = np.linspace(-2, 2.300)
# 等高線をプロット（http://ailaby.com/contour/）
xmesh, ymesh = np.meshgrid(xs, ys)
xx = np.r_xmesh.reshape(1, -1), ymesh.reshape(1, -1)
levels = -3, -2.9, -2.8, -2.6, -2.4, -2.2, -2, -1, 0, 1, 2, 3, 4
plt.contour(xs, ys, f(xx).reshape(xmesh.shape), levels=levels, colors='k', linestyles='dotted')
plt.show()
--------------------------------------------------------------------------
3.45722846e-07 1.00000048e+00
-2.9999999999997073
--------------------------------------------------------------------------
https://gyazo.com/e006caf2b1ff516f3543ed065dedf38b
Alphaの値を変えてみます。
code: Python
import numpy as np
import matplotlib.pyplot as plt
def f(xx):
x = xx0
y = xx1
return 5 * x**2 - 6 * x * y + 3 * y**2 + 6 * x - 6 * y
def df(xx):
x = xx0
y = xx1
return np.array(10 * x - 6 * y + 6, -6 * x + 6 * y - 6)
xmin, xmax, ymin, ymax = -3, 3, -3, 3
algos = []
initial = np.array(1, 1)
alphas = 0.1, 0.2
for alpha in alphas:
algo = GradientDescent(f, df, alpha)
algo.solve(np.array(initial))
algos.append(algo)
xs = np.linspace(xmin, xmax, 300)
ys = np.linspace(ymin, ymax, 300)
xmesh, ymesh = np.meshgrid(xs, ys)
xx = np.r_xmesh.reshape(1, -1), ymesh.reshape(1, -1)
fig, ax = plt.subplots(1, 2)
levels = -3, -2.9, -2.8, -2.6, -2.4, -2.2, -2, -1, 0, 1, 2, 3, 4
for i in range(2):
axi.set_xlim((xmin, xmax))
axi.set_ylim((ymin, ymax))
axi.set_title('alpha={}'.format(alphasi))
axi.scatter(initial0, initial1, color='k', marker='o')
axi.plot(algosi.path_:, 0, algosi.path_:, 1, color='k', linewidth=1.5)
axi.contour(xs, ys, f(xx).reshape(xmesh.shape), levels=levels, colors='k', linestyles='dotted')
plt.show()
https://gyazo.com/68696c5cc689d98eb762c16703f1aa46
右図は、学習率が大きすぎるため、収束していないことがわかります。