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

為了解決如何設定一個「好」學習率的問題,
自適應(Adaptive)的梯度下降有如雨後春筍般地冒了出來。

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

注意事項:
   1. 為了順利顯示數學式,請先安裝 google 套件:
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)
    
    def gradient(self):
        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))
        return grad_a, grad_b

    def update(self):
        # 計算梯度
        grad_a, grad_b = self.gradient()
        
        # 梯度更新
        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)
    
    def gradient(self):
        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

一、AdaGrad

AdaGrad 一詞來自於 adaptive gradient,即自適應梯度的意思。

在一般的梯度下降中,儘管權重們各自攜帶的係數不同,卻都使用相同的學習率。
最明顯的影響就是在迭代時,高次項的權重更新步伐大,低次項卻緩慢的蠕動,整個收斂過程沒有效率。

為了解決這個痛點,AdaGrad 應運而生。

Ada 家族有很多分支,像是 Adadelta、Adam、Adamax 等
我們先從之前的 BGD 延伸過來,其基本形式為:

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

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

AdaGrad 的概念,就是對於學習率$\alpha$稍作修改,
給一個隨時間變化的函數$\varphi(t)$,得到一個新的學習率:

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

這個$\varphi(t)$所描述的時間$t$,是指過去迭代的次數,
整個算法用文字描述就是「加總過去所有迭代的梯度值平方再開根號」。

這樣講似乎有點抽象,我們實際寫一次就知道了,
以$g^j表示第j次迭代之梯度值$:

第一次迭代:$\varphi(1)={(g^1)}^2$
第二次迭代:$\varphi(2)={(g^1)}^2+{(g^2)}^2$
第三次迭代:$\varphi(3)={(g^1)}^2+{(g^2)}^2+{(g^3)}^2$

看懂之後,把它們改寫成數學式:

$$\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}$都有。
               實際使用時都可以,就是一個不為零極小值就好。

剛也提到,AdaGrad 的計算規則是每個權重各自累加梯度平方和,
其效果就是讓權重走到陡坡時慢一點,走到緩坡時快一點。
因此迭代的收斂方向就會更明確,效率更高。

但 AdaGrad 的缺點也和優點一樣明顯:

隨著迭代的次數愈大,$\varphi(t)$也愈大,即$\alpha'$會逐漸接近零,直至停止。
由於不斷地累加梯度平方和,使得學習率一下子就趨近於零,
在迭代多次後,權重值基本上就在原地踏步,迭代強迫停止。

好的,優缺點都說完了,我們接著來實作 AdaGrad 吧。
經過分析,我們只需繼承 MBGD 、新增梯度平方和累加項與覆寫 update 函數即可。

class my_AdaGrad(my_MBGD):
    def __init__(self, a, b, x, y, alpha, batch_size):
        super().__init__(a, b, x, y, alpha, batch_size)
        
        # 梯度平方和累加項
        self.sum_grad_a = 0
        self.sum_grad_b = 0
        
        # epsilon
        self.e = 1e-6
        
    def update(self):
        self.a_old = self.a 
        self.b_old = self.b
        
        # 計算梯度
        grad_a, grad_b = self.gradient()
        
        # 累加梯度平方和
        self.sum_grad_a += grad_a ** 2
        self.sum_grad_b += grad_b ** 2
        
        # 梯度更新
        self.a = self.a_old - (self.alpha/np.sqrt(self.sum_grad_a+self.e)) * grad_a
        self.b = self.b_old - (self.alpha/np.sqrt(self.sum_grad_b+self.e)) * grad_b

        self.loss = self.mse();

再來是迭代用的主程式,來看一下 AdaGrad 的最佳化過程:

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

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

# 初始設定
alpha = 5

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

batch_size = 5

# 類別 MBGD 初始化
mlclass = my_AdaGrad(a, b, x, y, alpha, batch_size)

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))

也可以和 SGD 比較一下,主要可以觀察 AdaGrad 對於權重收斂方向的影響,
從結果看出相較於 SGD 的路徑,AdaGrad 會更有效率地朝最小值移動。

# 初始設定
alpha = 5
alpha_sgd = 0.05

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

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

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

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

二、RMSprop

RMSprop 是 Root Mean Square propagation 均方根傳播法的縮寫。
該方法是 Geoff Hinton 提出的一種自適應學習率方法,參考文獻如下:
Neural Networks for Machine Learning

在 AdaGrad 中,人們面臨的問題是:訓練後期的速度緩慢得令人抓狂。
因為不斷累加的梯度平方和最終將演變成一個龐然大物。

另一方面,真的有需要讓第一次迭代的結果,影響到第 N 次迭代嗎?

答案是:不需要。

過去迭代的結果,其所產生的影響應該要隨著時間逐漸消失。
這就是 RMSprop 所提出來的改進。

在 AdaGrad 中,累加梯度的算法是如下:

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

而 RMSprop 則是於上式新增一個衰減係數$\rho$:

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

意思是加權平均當前的梯度值及過去所累加的值,權重$\rho$通常給定為 0.9。
這樣就能讓過去的梯度呈指數衰減,改善迭代過程停滯不前的困擾。

我們也可以把公式依次寫出來看看,同樣地以$g^j表示第j次迭代之梯度值$:

第一次迭代:$\varphi(1)=(0.1)\cdot{(g^1)}^2$
第二次迭代:$\varphi(2)=(0.9)\cdot\varphi(1)+(0.1)\cdot{(g^2)}^2$
第三次迭代:$\varphi(3)=(0.9)\cdot\varphi(2)+(0.1)\cdot{(g^3)}^2$

若將$\varphi(3)$單獨挑出來看:
$\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$

這裡就能看到隨著迭代次數增加,距離愈遠的梯度平方值的權重愈小。
除此之外,後續的計算都和 AdaGrad 相同:

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

回到實作上,恩... RMSprop 改動實在不多。
直接繼承 AdaGrad,再新增參數$\rho$與覆寫 update 函數即可。

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
        
        # 計算梯度
        grad_a, grad_b = self.gradient()
        
        # 修改累加梯度平方和的方式
        self.sum_grad_a = self.rho * self.sum_grad_a + (1-self.rho) * grad_a ** 2
        self.sum_grad_b = self.rho * self.sum_grad_b + (1-self.rho) * grad_b ** 2
        
        # 梯度更新
        self.a = self.a_old - (self.alpha/np.sqrt(self.sum_grad_a+self.e)) * grad_a
        self.b = self.b_old - (self.alpha/np.sqrt(self.sum_grad_b+self.e)) * grad_b

        self.loss = self.mse();

接著在主程式的地方,就直接把 AdaGrad 和 RMSprop 繪製在一起做比較吧:

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

batch_size = 5
rho = 0.9

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

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

plt.title('Initial')

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

    plt.plot((Ada.a_old, Ada.a), (Ada.b_old, Ada.b), 'ro-')
    plt.plot((RMS.a_old, RMS.a), (RMS.b_old, RMS.b), 'bo-')
    
    plt.title('iter='+str(i))

在學習率相同的情況下,RMSprop 的收斂速度比 AdaGrad 更快!
當 AdaGrad 還沉浸在自己的過去時,RMSprop 已經在最小值區域內打轉了。

三、Adam

講了幾個自適應梯度的方法,怎麼能夠少了動量呢?

Adam 顧名思義就是 Ada + momentum。
核心概念是把 RMSprop 的方法,再加上動量的計算組合而成。

有了前面的鋪墊,現在來看 Adam 就簡單多了。
先回顧一下上一篇所提到的動量計算,公式為:

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

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

到了 Adam 後,參數$\alpha$挪開,然後用和$\beta_1$來取代$\gamma$,如下:

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

另外,先前在 RMSprop 出現的累加梯度算法,到了這裡依舊存在。
把參數$\rho$替換為$\beta_2$:

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

通常預設$\beta_1$與$\beta_2$值為 0.9。

把上述二式結合在一起後,就可得到 Adam 算法:

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

最後又進到實作的部分了。

這邊夏恩一開始打算做多重繼承 SGDM 與 RMSprop。
後來想想算了,因為這樣會有菱形繼承的問題,程式會變得太難懂。

經過考慮後,還是繼承 MBGD 就好,其他再自行新增即可。

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
        
        # 梯度平方和累加項
        self.sum_grad_a = 0
        self.sum_grad_b = 0
        
    def update(self):
        self.a_old = self.a 
        self.b_old = self.b
        
        # 計算梯度
        grad_a, grad_b = self.gradient()
        
        # 累加動量
        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.sum_grad_a = self.beta2 * self.sum_grad_a + (1-self.beta2) * grad_a ** 2
        self.sum_grad_b = self.beta2 * self.sum_grad_b + (1-self.beta2) * grad_b ** 2
        
        # 梯度更新
        self.a -= (self.alpha*self.sum_Ma)/(np.sqrt(self.sum_grad_a)+self.e)
        self.b -= (self.alpha*self.sum_Mb)/(np.sqrt(self.sum_grad_b)+self.e)
        
        self.loss = self.mse();

主程式的部分則是要設定 Adam 的$\beta_1$與$\beta_2$參數:

# 初始設定
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))

在測試 Adam 的過程中,夏恩也注意到它有一些收斂上的問題:不穩定。

由於 Ada 系列的算法都會累積一段時間的梯度平方和,或稱二階動量。
隨著時間變化,二階動量會忽大忽小,這也是造成自適應算法不穩定的原因。

接著夏恩稍作搜尋,發現過去也有許多論文把 Adam 拿出來鞭打,例如:

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).」

    簡言之,作者認為 Adam 在某些特定的情況下會產生不收斂的問題,同時也
    提出改進方法,即 AMSGrad 算法,主要是針對二階動量的最大值給予限制。

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 系列的算法到後期的結果都不好,容易會收斂在較差的區域最小值,
    或收斂速度緩慢等等的問題。因此,作者建議採用一種混合式的訓練方法,即在一
    開始使用 Ada 算法,後期時改為 sgdm 算法,在迭代過程中,同時計算 sgdm 
    所對應的學習率,當 sgdm 的學習率趨於穩定,則切換優化算法。

    演算法設計如下: 

3. The Marginal Value of Adaptive Gradient Methods in Machine Learning
    作者原話:「We additionally study the empirical generalization capability of adaptive
                         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.」

    作者針對 Ada 系列算法砲火全開,連綿不絕,甚至直接表明說從業人員若要將 Ada 系列
    算法應用在神經網路的訓練上時,「最好再多考慮一下!」...    

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

小結

最後總結幾個優化算法的使用心得:

1. 優化算法沒有最好,只有最適合
    在實際使用上,夏恩最常用 sgdm 和 adam。有時候 sgdm 效果好;有時候卻是 adam 比較優。
    這跟資料的特性有關係,所以建議是都可以試試看,因此:
        1.1 請熟悉待分析的數據。
        
1.2 請熟悉不同優化算法的特性。

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

3. 打散數據是必須的
   
在 tensorflow 中有打散數據的參數可供使用者設定,請務必要記得使用。
    這個手法能避免某些特徵在幾個批次中密集出現,以降低演算法訓練時的偏差。

4. 多點人工也會多點智慧
    「
多點人工」的意思是使用者必須思考模型該如何設計;超參數如何影響模型,又
    該如何調整;優化算法的特性與其適用性;訓練過程之學習率設定與過擬合情況監控等。

從最初的 BGD 一路演化到 Adam,再往後還有許多。
例如限制二階動量的 AMSGrad、加入 Nesterov 概念的 Nadam、裁剪學習率的 Adabound 等。
由於上述這些算法沒有什麼創新的概念,夏恩這裡就不再多提。

雖然乍看之下 Ada 家族好像很複雜很可怕,但背後的想法都差不多。
只要靜下心來,拿起紙筆把公式寫過,再把程式實作一輪,相信就能有更深入的體會。

關於梯度下降的文章與各類教學早就多到滿出來。
那為什麼夏恩還是想要寫這一個系列文章呢?

其實這次想寫梯度下降的原因,主要是想解開一些自己的困惑。
別人的文章再怎麼看,那也是別人的知識,跟自己無關。

若非自己親手做過寫過,那些知識就如浮雲,風一吹就散了。
夏恩是希望透過講解與實作,以加深自己對於梯度下降算法的理解。

目前看來,效果還不錯。
親手把程式寫過一次,感覺非常踏實。

參考資料

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. 深度學習最全優化方法總結比較
15. Adam那麼棒,為什麼還對SGD念念不忘
16. 機器/深度學習-基礎數學(三):梯度最佳解相關算法
17. 深度学习优化函数详解(4)-- momentum 动量法
18. 从 SGD 到 Adam —— 深度学习优化算法概览(一)
19. 一文告訴你Adam、AdamW、Amsgrad區別和聯繫
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)
    
    def gradient(self):
        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))
        return grad_a, grad_b

    def update(self):
        # 計算梯度
        grad_a, grad_b = self.gradient()
        
        # 梯度更新
        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)
    
    def gradient(self):
        # 隨機取一筆資料進行計算
        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)
        return grad_a, grad_b

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)
    
    def gradient(self):
        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

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
        
        # 計算梯度
        grad_a, grad_b = self.gradient()

        # 動量累加
        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)
    
    def gradient(self):
        
        # 往前多走一點
        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();
        return grad_a, grad_b
    
class my_AdaGrad(my_MBGD):
    def __init__(self, a, b, x, y, alpha, batch_size):
        super().__init__(a, b, x, y, alpha, batch_size)
        
        # 梯度平方和累加項
        self.sum_grad_a = 0
        self.sum_grad_b = 0
        
        self.e = 1e-6
        
    def update(self):
        self.a_old = self.a 
        self.b_old = self.b
        
        # 計算梯度
        grad_a, grad_b = self.gradient()
        
        # 累加梯度平方和
        self.sum_grad_a += grad_a ** 2
        self.sum_grad_b += grad_b ** 2
        
        # 梯度更新
        self.a = self.a_old - (self.alpha/np.sqrt(self.sum_grad_a+self.e)) * grad_a
        self.b = self.b_old - (self.alpha/np.sqrt(self.sum_grad_b+self.e)) * grad_b

        self.loss = self.mse();
        
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
        
        # 計算梯度
        grad_a, grad_b = self.gradient()
        
        # 累加梯度平方和
        self.sum_grad_a = self.rho * self.sum_grad_a + (1-self.rho) * grad_a ** 2
        self.sum_grad_b = self.rho * self.sum_grad_b + (1-self.rho) * grad_b ** 2
        
        # 梯度更新
        self.a = self.a_old - (self.alpha/np.sqrt(self.sum_grad_a+self.e)) * grad_a
        self.b = self.b_old - (self.alpha/np.sqrt(self.sum_grad_b+self.e)) * grad_b

        self.loss = self.mse();
        
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
        
        # 梯度平方和累加項
        self.sum_grad_a = 0
        self.sum_grad_b = 0
        
    def update(self):
        self.a_old = self.a 
        self.b_old = self.b
        
        # 計算梯度
        grad_a, grad_b = self.gradient()
        
        # 動量累加
        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.sum_grad_a = self.beta2 * self.sum_grad_a + (1-self.beta2) * grad_a ** 2
        self.sum_grad_b = self.beta2 * self.sum_grad_b + (1-self.beta2) * grad_b ** 2
        
        # 梯度更新
        self.a -= (self.alpha*self.sum_Ma)/(np.sqrt(self.sum_grad_a)+self.e)
        self.b -= (self.alpha*self.sum_Mb)/(np.sqrt(self.sum_grad_b)+self.e)
        
        self.loss = self.mse();