Sageでスケール共役勾配法を試す
PRMLの第5章のニューラルネットワークの例題説明に良く出てくる「スケール共役勾配法」 Scaled Conjugate Gradientsという名前が出てきますが、Googleで検索しても 日本語のアルゴリズム説明が見当たらないので、オリジナルの論文を基にsageを使って 実装してみました。
スケール共役勾配法は、ヘッセ行列を計算することなく、共役勾配を求めることができる 貴重な手法です。
論文
スケール共役勾配法の論文は、Moller, M (1993), "A Scaled Conjugate Gradient Algorithm for Fast Supervised Learning" に紹介されています。
論文の終わりのアルゴリズム説明を書くと、
- 重みベクトル$w_1$、スカラー $\sigma > 0, \lambda_1 > 0, \bar{\lambda_1} = 0$ を選択
- success = trueなら、2次情報を計算 $$ \sigma_k = \frac{\sigma}{|p_k|}, $$ $$ s_k = \frac{E'(w_k + \sigma_k p_k) - E'(w_k)}{\sigma_k}, $$ $$ \delta_k = p_k^T s_k. $$
- スケール$s_k$は、 $$ s_k = s_k + (\lambda_k -\bar{\lambda_k}) p_k, $$ $$ \delta_k = delta_k + (\lambda_k -\bar{\lambda_k}) |p_k|^2 $$
- $\delta_k \le 0$ なら、ヘッセマトリックスを正定値にする、 $$ s_k = s_k + (\lambda_k - 2 \frac{\delta_k}{|p_k|^2} p_k, $$ $$ \bar{\lambda_k} = 2 (\lambda_k - \frac{\delta_k}{|p_k|^2}), $$ $$ \delta_k = - \delta_k \lambda_k|p_k|^2, \lambda_k = \bar{\lambda_k}. $$
- 刻み幅を計算、 $$ \mu_k = p_k^T r_k, \alpha_k = \frac{\mu_k}{\delta_k}. $$
- 比較パラメータを計算、 $$ \Delta_k = \frac{2\delta_k[E(w_k) - E(w_k + \alpha_k p_k)}{\mu_k^w}. $$
-
$\Delta_k \ge 0$なら、後退が正常に処理されており、
$$
w_{k+1} = w_k + \alpha_k p_k,
$$
$$
r_{k+1} = -E'(w_{k+1}),
$$
$$
\bar{\lambda_k} = 0, success = true.
$$
- k mod N = 0なら、アルゴリズムをリスタート： $$ p_{k+1} = r_{k+1} $$ そうでなければ、 $$ \beta_k = \frac{|r_{k+1}|^2 - r_{k+1} r_k}{\mu_k}, $$ $$ p_{k+1} = r_{k+1} + \beta_k p_k $$
- $\Delta_k \ge 0.75$ なら、スケールパラメータを減らす： $$ \lambda_k = \frac{1}{2}\lambda_k $$
- $\Delta_k \lt 0.25$なら、スケールを増やす： $$ \lambda_k = 4 \lambda_k $$
- 勾配方向 $ r_k \ne 0$なら、$ k = k + 1$とし、２に進む、 そうでなければ、終了し$w_{k+1}$を最小値として返す
テストデータの準備
スケール共役勾配法のテストは、図5.9
# Scaled Conjugate Gradients（スケール共役勾配法）
# 論文 A Scaled Conjugate Gradient Algorithm for Fast Supervised Leaning
# テストデータ
data = matrix([
[0.000000, 0.349486],
[0.111111, 0.830839],
[0.222222, 1.007332],
[0.333333, 0.971507],
[0.444444, 0.133066],
[0.555556, 0.166823],
[0.666667, -0.848307],
[0.777778, -0.445686],
[0.888889, -0.563567],
[1.000000, 0.261502],
]);
X = data.column(0)
T = data.column(1)
|
|
設定
ニューラルネットワークの設定は、逐次的勾配降下法とスケール共役勾配法の比較では
- 入力ユニット数1個（バイアス項を除く）
- 隠れ層ユニット数4個（バイアス項を除く）
- 出力ユニット数1個
# 入力1点、隠れ層3個、出力1点
N_in = 1
N_h = 4
N_out = 1
# 隠れ層の活性化関数
h_1(x) = tanh(x)
# 出力層の活性化関数
h_2(x) = x
|
|
ニューラルネットワークのクラス化
スケール共役勾配法では、何度もwの設定を変えたり、勾配を求めたりするため、 ニューラルネットワークをクラス化する方が便利です。
以下の様にニューラルネットワーク用のクラスを定義します。
class NeuralNetwork:
""" ニューラルネットワーク用のクラス（バイアス項を含む） """
def __init__(self, N_in, N_h, N_out, h_1, h_2, beta):
# N_in : 入力ユニットの数（バイアス項を除く）
# N_h : 隠れ層の数（バイアス項を除く）
# N_out: 出力ユニットの数
# h_1 : 隠れ層の活性化関数
# h_2 : 出力層の活性化関数
# beta : wの初期化分布β
self.N_in = N_in+1; self.N_h = N_h+1
self.N_out = N_out; self.h_1 = h_1
self.dif_h_1 = diff(h_1, x); self.h_2 = h_2
self.w_1 = matrix(RDF, [[gauss(0,beta) for i in range(self.N_in)] for j in range(self.N_h)])
self.w_2 = matrix(RDF, [[gauss(0,beta) for j in range(self.N_h)] for k in range(self.N_out)])
self.x_i = vector(RDF, self.N_in); self.y_k = vector(RDF, self.N_out)
self.z_j = vector(RDF, self.N_h); self.z_j[0] = 1
self.d_j = vector(RDF, self.N_h); self.d_k = vector(RDF, self.N_out)
# フィードフォワード
def feedForward(self, x):
# x : 入力値
self.x_i = vector(RDF, flatten([1, x]))
# フィードフォワード処理
for j in range(1, self.N_h):
self.z_j[j] = self.h_1(self.w_1.row(j)*self.x_i).n()
for k in range(self.N_out):
self.y_k[k] = self.h_2(self.w_2.row(k)*self.z_j).n()
return self.y_k
# バックプロパゲート処理
def backPropagate(self, t):
# t : 観測値
self.t = vector(RDF, flatten([t]))
self.d_k = self.y_k - self.t
for j in range(self.N_h):
self.d_j[j] = self.dif_h_1(self.z_j[j])*self.w_2.column(j)*self.d_k
return self.d_k
# 1/2 En(w)を返す
def En(self):
return 1/2*self.d_k*self.d_k
# ▽Enを返す
def gradEn(self):
dE_1 = [[self.d_j[j]*self.x_i[i] for i in range(self.N_in)] for j in range(self.N_h)]
dE_2 = [[self.d_k[k]*self.z_j[j] for j in range(self.N_h)] for k in range(self.N_out)]
return vector(RDF, flatten(dE_1 + dE_2))
# wを返す
def getW(self):
return vector(RDF, self.w_1.list()+self.w_2.list())
# wをセットする
def setW(self, w):
self.w_1 = matrix(RDF, self.N_h, self.N_in, w.list()[0:self.N_in*self.N_h])
self.w_2 = matrix(RDF, self.N_out, self.N_h, w.list()[self.N_in*self.N_h:])
|
|
逐次的勾配降下法による学習
比較のために、逐次的勾配降下法をニューラルネットワークのクラスを使って 実装します。
# 逐次勾配降下法による学習
def _learn_sg(net, X, T, eta, LEARN_COUNT):
for m in range(LEARN_COUNT):
for n in range(len(X)):
net.feedForward(X[n])
net.backPropagate(T[n])
# print net.En()
net.setW(net.getW() - eta*net.gradEn())
|
|
スケール共役勾配法による学習
スケール共役勾配法の学習アルゴリズムを実装します。
# Scaled Conjugate Gradients（スケール共役勾配法）
# 論文 A Scaled Conjugate Gradient Algorithm for Fast Supervised Leaning
def _learn_csg(net, X, T, LEARN_COUNT, RESET_COUNT):
lam_min = 1e-15
lam_max = 1e100
w_len = len(net.getW())
# ▽E(w), 1/2E(w)を返す
def gradE(w):
dE = vector(RDF, w_len)
net.setW(w)
E = 0
for n in range(len(X)):
net.feedForward(X[n])
net.backPropagate(T[n])
E += net.En()
dE = dE + net.gradEn()
return (dE, E)
# 初期値設定
sig0 = 1e-4
w = net.getW()
(dE, E) = gradE(w)
o_E = E
o_dE = dE
p = r = -dE
lam_bar = 0
lam = 1
success = true
k = 1
for k in range(1, LEARN_COUNT):
if success :
# ２次の計算が可能
sig = sig0/sqrt(p*p)
o_E = E; o_dE = dE
(dE, E) = gradE(w + sig*p)
s = (dE - o_dE)/sig
d = p*s
s = s + (lam - lam_bar)*p
d = d + (lam - lam_bar)*(p*p)
if d <= 0:
s = s + (lam - 2*d/(p*p))*p
lam_bar = 2*(lam - d /(p*p))
d = -d + lam*(p*p)
lam = lam_bar
mu = p*r
alpha = mu/d
(dE, E) = gradE(w + alpha*p)
delta = 2*d*(o_E - E)/(mu*mu)
if delta >= 0:
#print "update"
o_E = E; o_dE = dE; o_r = r
w = w + alpha*p
(dE, E) = gradE(w)
r = -dE
lam_bar = 0; success = true
k = k + 1
if k % RESET_COUNT == 0:
p = r
else:
beta = (r*r - r*o_r)/mu
p = r + beta*p
if delta >= 0.75:
lam = max(lam/2, lam_min)
else:
lam_bar =lam; success = false
if delta < 0.25:
lam = min(lam*4, lam_max)
if r.norm() == 0:
return
#print k, delta, E
net.setW(w)
|
|
# 出力関数
def _f(x, net):
y = net.feedForward(x)
return y[0]
|
|
# トレーニングデータのプロット
data_plt = list_plot(zip(X, T))
|
|
逐次的勾配降下法の結果
比較のために、逐次的勾配降下法での学習結果をプロットします。
500回の学習回数では、sin曲線に近づけません。
# 比較のために、逐次勾配降下法で解く
# 定数設定
eta = 0.1 # η（学習率）
LEARN_COUNT = 500
RESET_COUNT = 50
beta = 0.01
# ニューラルネットワークの生成
net = NeuralNetwork(N_in, N_h, N_out, h_1, h_2, beta)
# wの初期値を保存
saved_w = net.getW()
# 逐次勾配降下法による学習
_learn_sg(net, X, T, eta, LEARN_COUNT)
# 結果のプロット
var('x')
f_plt = plot(lambda x : _f(x, net), [x, 0, 1], color='red')
(data_plt + f_plt).show()
|
|
スケール共役勾配法の結果
スケール共役勾配法の学習結果をプロットします。
少ない学習回数でもかなり良くフィットしています。
# ニューラルネットワークの生成
net = NeuralNetwork(N_in, N_h, N_out, h_1, h_2, beta)
# 逐次勾配降下法と同じwをセット
net.setW(saved_w)
# スケール共役勾配法による学習
_learn_csg(net, X, T, LEARN_COUNT, RESET_COUNT)
# 結果のプロット
var('x')
f_plt = plot(lambda x : _f(x, net), [x, 0, 1], color='red')
(data_plt + f_plt).show()
|
|
Mを変えたスケール共役勾配法の結果
図5.9と同じようにMを1, 3, 10に変えた結果をプロットします。
M=10のような過学習の結果にはなりません、この辺は重みwの初期値の 分布を変えると変化することが分かりましたが、処理時間の関係で詳しくは調べていません。
# PRML fig. 5.9
# M=1
N_h = 1; net = NeuralNetwork(N_in, N_h, N_out, h_1, h_2, beta)
# スケール共役勾配法による学習
_learn_csg(net, X, T, LEARN_COUNT, RESET_COUNT)
# 結果のプロット
f_plt = plot(lambda x : _f(x, net), [x, 0, 1], color='red')
(data_plt + f_plt).show()
|
|
# M=3
N_h = 3; net = NeuralNetwork(N_in, N_h, N_out, h_1, h_2, beta)
# スケール共役勾配法による学習
_learn_csg(net, X, T, LEARN_COUNT, RESET_COUNT)
# 結果のプロット
f_plt = plot(lambda x : _f(x, net), [x, 0, 1], color='red')
(data_plt + f_plt).show()
|
|
# M=10
N_h = 10; net = NeuralNetwork(N_in, N_h, N_out, h_1, h_2, beta)
# スケール共役勾配法による学習
_learn_csg(net, X, T, LEARN_COUNT, RESET_COUNT)
# 結果のプロット
f_plt = plot(lambda x : _f(x, net), [x, 0, 1], color='red')
(data_plt + f_plt).show()
# 結果は、図5.9のM=10とは異なり、Over fittingは見えない
|
|
|
|