### 【Python】淺談梯度下降與實作(下)：猙獰的變形者們

========================================

TeX All the Things
2. 本文中有些許高中數學，不會太硬，請放心咀嚼。

========================================

# -*- coding: utf-8 -*-
# 引用部分上一章之程式碼
#
# Shayne, 2019.10.09

import numpy as np
import matplotlib.pyplot as plt

# 給定隨機種子，使每次執行結果保持一致
np.random.seed(1)

def getdata(n):
# n為產生資料量
x = np.arange(-5, 5.1, 10/(n-1))
# 給定一個固定的參數，再加上隨機變動值作為雜訊，其變動值介於 +-10 之間
y = 3*x + 2 + (np.random.rand(len(x))-0.5)*20
return x, y

def plot_error(x, y):
a = np.arange(-10, 16, 1)
b = np.arange(-10, 16, 1)
mesh = np.meshgrid(a, b)

sqr_err = 0
for xs, ys in zip(x, y):
sqr_err += ((mesh[0]*xs + mesh[1]) - ys) ** 2
loss = sqr_err/len(x)

plt.contour(mesh[0], mesh[1], loss, 20, cmap=plt.cm.jet)
plt.xlabel('a')
plt.ylabel('b')
plt.axis('scaled')
plt.title('function loss')

# 實作 BGD
class my_BGD:
def __init__(self, a, b, x, y, alpha):
self.a = a
self.b = b
self.x = x
self.y = y
self.alpha = alpha

self.a_old = a
self.b_old = b

self.loss = None;

# Loss function
def mse(self):
sqr_err = ((self.a*self.x + self.b) - self.y) ** 2
return np.mean(sqr_err)

grad_a = 2 * np.mean((self.a*self.x + self.b - self.y) * (self.x))
grad_b = 2 * np.mean((self.a*self.x + self.b - self.y) * (1))

def update(self):
# 計算梯度

# 梯度更新
self.a_old = self.a
self.b_old = self.b
self.a = self.a - self.alpha * grad_a
self.b = self.b - self.alpha * grad_b
self.loss = self.mse();

# 實作 MBGD，繼承 BGD
class my_MBGD(my_BGD):
def __init__(self, a, b, x, y, alpha, batch_size):
super().__init__(a, b, x, y, alpha)

self.idx = 0
self.batch_size = batch_size

# 使用 np.random.permutation 給定資料取出順序
self.suffle_idx = np.random.permutation(len(x))

self.update_batch();

# 更新批次
def update_batch(self):
#每次更新時，採滾動的方式依次取出 N 筆資料
idx = self.suffle_idx[self.idx:self.idx+self.batch_size];
self.idx += self.batch_size

self.x_batch = self.x[idx]
self.y_batch = self.y[idx]

# Loss function
def mse(self):
sqr_err = ((self.a*self.x_batch + self.b) - self.y_batch) ** 2
return np.mean(sqr_err)

grad_a = 2 * np.mean((self.a*self.x_batch + self.b - self.y_batch) * (self.x_batch))
grad_b = 2 * np.mean((self.a*self.x_batch + self.b - self.y_batch) * (1))
self.update_batch();
return grad_a, grad_b

$$w_k^{(j+1)}=w_k^{(j)}-\alpha\nabla L(w_k)$$

$$j 為迭代次數，\alpha 為學習率，k為第k個權重$$

AdaGrad 的概念，就是對於學習率$\alpha$稍作修改，

$$\alpha'=\frac{\alpha}{\sqrt{\varphi(t)}}$$

$$\varphi_k(t)=\sum_{j=1}^{t}\left(g_k^j\right)^2$$

$$\varphi_k(t)=\varphi_k(t-1)+\left(g_k^t\right)^2$$

$$w_k^{(j+1)}=w_k^{(j)}-\frac{\alpha}{\sqrt{\varphi_k(t)}+\varepsilon}\nabla L(w_k)$$

$$其中k為第k個權重，g^j為過去第j次迭代之梯度值\mathrm{\nabla\ L}(w^j)，\varepsilon為極小值，為避免分母為零$$

※ 備註：關於$\varepsilon$值有多種說法，舉凡$10^{-6}$至$10^{-8}$都有。
實際使用時都可以，就是一個不為零極小值就好。

class my_AdaGrad(my_MBGD):
def __init__(self, a, b, x, y, alpha, batch_size):
super().__init__(a, b, x, y, alpha, batch_size)

# 梯度平方和累加項

# epsilon
self.e = 1e-6

def update(self):
self.a_old = self.a
self.b_old = self.b

# 計算梯度

# 累加梯度平方和

# 梯度更新

self.loss = self.mse();

# =============================================== #
# 隨機產生一組資料
x, y = getdata(51)

# 繪製誤差空間底圖
plot_error(x, y)
# =============================================== #

# 初始設定
alpha = 5

# 從 -9 開始，能看得更明顯
a = -9; b = -9

batch_size = 5

# 類別 MBGD 初始化

plt.plot(a, b, 'ro-')
plt.title('Initial, loss='+'{:.2f}'.format(mlclass.mse())+'\na='+
'{:.2f}'.format(a)+', b='+'{:.2f}'.format(b))

# 開始迭代
for i in range(1, 11):
mlclass.update()
print('iter='+str(i)+', loss='+'{:.2f}'.format(mlclass.loss))

plt.plot((mlclass.a_old, mlclass.a), (mlclass.b_old, mlclass.b), 'ro-')
plt.title('iter='+str(i)+', loss='+'{:.2f}'.format(mlclass.loss)+'\na='+
'{:.2f}'.format(mlclass.a)+', b='+'{:.2f}'.format(mlclass.b))

# 初始設定
alpha = 5
alpha_sgd = 0.05

a = -9; b = -9
batch_size = 5

# 類別初始化
sgd = my_MBGD(a, b, x, y, alpha_sgd, batch_size)

plt.plot(a, b, 'bo-', label='SGD')
plt.legend(loc='upper right')

# 開始迭代
for i in range(1, 11):
sgd.update()
plt.plot((sgd.a_old, sgd.a), (sgd.b_old, sgd.b), 'bo-')

## 二、RMSprop

RMSprop 是 Root Mean Square propagation 均方根傳播法的縮寫。

Neural Networks for Machine Learning

$$\varphi(t)=\varphi(t-1)+\left(g^t\right)^2$$

$$\varphi(t)=\rho\cdot\varphi(t-1)+(1-\rho)\cdot\left(g^t\right)^2$$

$\varphi(3)=(0.9)^2\cdot(0.1)\cdot{(g^1)}^2+(0.9)\cdot(0.1)\cdot{(g^2)}^2+(0.1)\cdot{(g^3)}^2$

$$w^{(j+1)}=w^{(j)}-\frac{\alpha}{\sqrt{\varphi(t)}+\varepsilon}\nabla L(w)$$

class my_RMSprop(my_AdaGrad):
def __init__(self, a, b, x, y, alpha, batch_size, rho):
super().__init__(a, b, x, y, alpha, batch_size)

self.rho = rho

def update(self):
self.a_old = self.a
self.b_old = self.b

# 計算梯度

# 修改累加梯度平方和的方式

# 梯度更新

self.loss = self.mse();

# 初始設定
alpha = 2
a = -9; b = -9

batch_size = 5
rho = 0.9

# 類別初始化
RMS = my_RMSprop(a, b, x, y, alpha, batch_size, rho)

plt.plot(a, b, 'bo-', label='RMSprop')
plt.legend(loc='upper right')

plt.title('Initial')

# 開始迭代
for i in range(1, 11):
RMS.update()

plt.plot((RMS.a_old, RMS.a), (RMS.b_old, RMS.b), 'bo-')

plt.title('iter='+str(i))

$$V^{(j)}=\gamma V^{(j-1)}+\alpha\nabla L(W^{(j)})$$

$$其中，\alpha為學習率，\gamma為動量參數$$

$$V^{(j)}=\beta_1\cdot V^{(j-1)}+(1-\beta_1)\cdot\nabla L(W^{(j)})$$

$$\varphi(t)=\beta_2\cdot\varphi(t-1)+(1-\beta_2)\cdot\left(g^t\right)^2$$

$$w^{(j+1)}=w^{(j)}-\frac{\alpha\cdot V^{(j)}}{\sqrt{\varphi(t)}+\varepsilon}$$

class my_Adam(my_MBGD):
def __init__(self, a, b, x, y, alpha, batch_size, beta1, beta2):
super().__init__(a, b, x, y, alpha, batch_size)

self.beta1 = beta1
self.beta2 = beta2
self.e = 1e-6

# 動量累加項
self.sum_Ma = 0
self.sum_Mb = 0

# 梯度平方和累加項

def update(self):
self.a_old = self.a
self.b_old = self.b

# 計算梯度

# 累加動量
self.sum_Ma = self.beta1 * self.sum_Ma + (1-self.beta1) * grad_a
self.sum_Mb = self.beta1 * self.sum_Mb + (1-self.beta1) * grad_b

# 累加梯度平方和

# 梯度更新

self.loss = self.mse();

# 初始設定
alpha = 3

a = -9; b = -9
batch_size = 5

beta1 = 0.5
beta2 = 0.9

# 類別初始化
mlclass = my_Adam(a, b, x, y, alpha, batch_size, beta1, beta2)

plt.plot(a, b, 'ro-')
plt.title('Initial')
plt.title('Initial, loss='+'{:.2f}'.format(mlclass.mse())+'\na='+
'{:.2f}'.format(a)+', b='+'{:.2f}'.format(b))

# 開始迭代
for i in range(1, 11):
mlclass.update()
print('iter='+str(i)+', loss='+'{:.2f}'.format(mlclass.loss))

plt.plot((mlclass.a_old, mlclass.a), (mlclass.b_old, mlclass.b), 'ro-')

plt.title('iter='+str(i))
plt.title('iter='+str(i)+', loss='+'{:.2f}'.format(mlclass.loss)+'\na='+
'{:.2f}'.format(mlclass.a)+', b='+'{:.2f}'.format(mlclass.b))

1. On the Convergence of Adam and Beyond
作者原話：「In many applications, e.g. learning with large output spaces,
it has been empirically observed that these algorithms fail to
converge to an optimal solution (or a critical point in nonconvex settings).」

2. Improving Generalization Performance by Switching from Adam to SGD
作者原話：「We investigate a hybrid strategy that begins training with an
adaptive method and switches to SGD when appropriate.
Concretely, we propose SWATS, a simple strategy which
Switches from Adam to SGD when a triggering condition is satisfied.」

或收斂速度緩慢等等的問題。因此，作者建議採用一種混合式的訓練方法，即在一
開始使用 Ada 算法，後期時改為 sgdm 算法，在迭代過程中，同時計算 sgdm
所對應的學習率，當 sgdm 的學習率趨於穩定，則切換優化算法。

演算法設計如下：

methods on several state-of-the-art deep learning models. We observe
that the solutions found by adaptive methods generalize worse than SGD,
even when these solutions have better training performance.」

算法應用在神經網路的訓練上時，「最好再多考慮一下！」...

夏恩覺得這作者應該是撿到火箭筒。

## 小結

1. 優化算法沒有最好，只有最適合
這跟資料的特性有關係，所以建議是都可以試試看，因此：
1.1 請熟悉待分析的數據。

1.2 請熟悉不同優化算法的特性。

2. 多種優化算法同時使用
既然都有論文這麼說了，那肯定有參考價值，但首先您得先看懂切換策略。

3. 打散數據是必須的

這個手法能避免某些特徵在幾個批次中密集出現，以降低演算法訓練時的偏差。

4. 多點人工也會多點智慧
「

該如何調整；優化算法的特性與其適用性；訓練過程之學習率設定與過擬合情況監控等。

## 參考資料

1. ML Lecture 3-1: Gradient Descent
2. An overview of gradient descent optimization algorithms
3. Intro to optimization in deep learning: Gradient Descent
4. Intro to optimization in deep learning: Momentum, RMSProp and Adam

5.   SGD算法比較
6.   深度學習優化器總結
7.   梯度下降優化算法綜述
8.   如何理解随机梯度下降
9.   浅谈对梯度下降法的理解
10. 優化器演算法Optimizer詳解
11. 深度学习笔记：优化方法总结
12. 自己动手用python写梯度下降
13. 深入浅出--梯度下降法及其实现
14. 深度學習最全優化方法總結比較
16. 機器/深度學習-基礎數學(三):梯度最佳解相關算法
17. 深度学习优化函数详解（4）-- momentum 动量法
18. 从 SGD 到 Adam —— 深度学习优化算法概览(一)
20. 详解梯度下降法的三种形式BGD、SGD以及MBGD
21. 深度學習優化函數詳解（5）-- Nesterov accelerated gradient (NAG)

## 附錄

# -*- coding: utf-8 -*-
# 梯度下降算法實作
#
# 備註：使用 MBGD 系列的類別時，請注意批次設定的問題。
#      這裡沒有把自動循環資料的功能弄上去，請自行開發...
#
# Shayne, 2019.10.22

class my_BGD:
def __init__(self, a, b, x, y, alpha):
self.a = a
self.b = b
self.x = x
self.y = y
self.alpha = alpha

self.a_old = a
self.b_old = b

self.loss = None

# Loss function
def mse(self):
sqr_err = ((self.a*self.x + self.b) - self.y) ** 2
return np.mean(sqr_err)

grad_a = 2 * np.mean((self.a*self.x + self.b - self.y) * (self.x))
grad_b = 2 * np.mean((self.a*self.x + self.b - self.y) * (1))

def update(self):
# 計算梯度

# 梯度更新
self.a_old = self.a
self.b_old = self.b
self.a = self.a - self.alpha * grad_a
self.b = self.b - self.alpha * grad_b
self.loss = self.mse();

class my_SGD(my_BGD):
def __init__(self, a, b, x, y, alpha):
super().__init__(a, b, x, y, alpha)

# 隨機取一筆資料進行計算
idx = np.random.randint(len(x))

grad_a = 2 * (self.a*self.x[idx] + self.b - self.y[idx]) * (self.x[idx])
grad_b = 2 * (self.a*self.x[idx] + self.b - self.y[idx]) * (1)

class my_MBGD(my_BGD):
def __init__(self, a, b, x, y, alpha, batch_size):
super().__init__(a, b, x, y, alpha)

self.idx = 0
self.batch_size = batch_size

# 使用 np.random.permutation 給定資料取出順序
self.suffle_idx = np.random.permutation(len(x))

self.update_batch();

# 更新批次
def update_batch(self):
#每次更新時，採滾動的方式依次取出 N 筆資料
idx = self.suffle_idx[self.idx:self.idx+self.batch_size];
self.idx += self.batch_size

self.x_batch = self.x[idx]
self.y_batch = self.y[idx]

# Loss function
def mse(self):
sqr_err = ((self.a*self.x_batch + self.b) - self.y_batch) ** 2
return np.mean(sqr_err)

grad_a = 2 * np.mean((self.a*self.x_batch + self.b - self.y_batch) * (self.x_batch))
grad_b = 2 * np.mean((self.a*self.x_batch + self.b - self.y_batch) * (1))
self.update_batch();

class my_SGDM(my_MBGD):
def __init__(self, a, b, x, y, alpha, batch_size, gamma):
super().__init__(a, b, x, y, alpha, batch_size)

# Momentum parameter
self.gamma = gamma

# 動量累加項
self.sum_Ma = 0
self.sum_Mb = 0

def update(self):
self.a_old = self.a
self.b_old = self.b

# 計算梯度

# 動量累加
self.sum_Ma = self.gamma * self.sum_Ma + self.alpha * grad_a
self.sum_Mb = self.gamma * self.sum_Mb + self.alpha * grad_b

# 梯度更新
self.a -= self.sum_Ma
self.b -= self.sum_Mb

self.loss = self.mse();

class my_NAG(my_SGDM):
def __init__(self, a, b, x, y, alpha, batch_size, gamma):
super().__init__(a, b, x, y, alpha, batch_size, gamma)

# 往前多走一點
a = self.a - self.sum_Ma
b = self.b - self.sum_Mb

grad_a = 2 * np.mean((a*self.x_batch + b - self.y_batch) * (self.x_batch))
grad_b = 2 * np.mean((a*self.x_batch + b - self.y_batch) * (1))
self.update_batch();

def __init__(self, a, b, x, y, alpha, batch_size):
super().__init__(a, b, x, y, alpha, batch_size)

# 梯度平方和累加項

self.e = 1e-6

def update(self):
self.a_old = self.a
self.b_old = self.b

# 計算梯度

# 累加梯度平方和

# 梯度更新

self.loss = self.mse();

def __init__(self, a, b, x, y, alpha, batch_size, rho):
super().__init__(a, b, x, y, alpha, batch_size)

self.rho = rho

def update(self):
self.a_old = self.a
self.b_old = self.b

# 計算梯度

# 累加梯度平方和

# 梯度更新

self.loss = self.mse();

def __init__(self, a, b, x, y, alpha, batch_size, beta1, beta2):
super().__init__(a, b, x, y, alpha, batch_size)

self.beta1 = beta1
self.beta2 = beta2
self.e = 1e-6

# 動量累加項
self.sum_Ma = 0
self.sum_Mb = 0

# 梯度平方和累加項

def update(self):
self.a_old = self.a
self.b_old = self.b

# 計算梯度

# 動量累加
self.sum_Ma = self.beta1 * self.sum_Ma + (1-self.beta1) * grad_a
self.sum_Mb = self.beta1 * self.sum_Mb + (1-self.beta1) * grad_b

# 累加梯度平方和
self.loss = self.mse();