Back Propagation

⊕ 類神經的神經元示意圖

所以這是如何跟類神經網路關聯接一起的？一個簡單的類神經網路為了簡化，我省去了 Bias term b^{(l)}。可以這樣表示 我這邊使用 a 表示 summation, z 表示 activation 的輸出，有些文章會採用反過來的表示方式。：

\begin{aligned} a_i^{(1)} &= \sum_j w^{(1)}_{ij} \cdot x_i & z_i^{(1)} &= f(a_i^{(1)}) \\ a_i^{(2)} &= \sum_j w^{(2)}_{ij} \cdot z_j^{(1)} & z_1^{(2)} &= f(a_i^{(2)}) \\ &\cdots & & \cdots \\ a_i^{(l)} &= \sum_j w^{(l)}_{ij} \cdot z_j^{(l-1)} &z_i^{(l)} &= f(a_i^{(l)}) \end{aligned}

接著我們會定義 cost function (或稱為 loss function)，比方說 Mean Squared Error：

C(Y, \hat Y) = \frac{1}{n} \sum_i^n \left(Y_i - \hat{Y}_i\right)^2

類神經的 Forward Propagation 就是帶入資料 X 跟權重 w 計算出預測值 z_i^{(l)}，而 Back Propagation 就是利用 cost 來找出一組更好 w_{ij} 來使的 C 更小。

怎麼做？從 \frac{∂ C}{∂ \color{red}C} = 1 開始、 \frac{∂ C}{∂ \color{red}z_i^{(l)}}, \frac{∂ C}{∂ \color{red}a_i^{(l)}}, \frac{∂ C}{∂ \color{red}w_{ij}^{(l)}}, \frac{∂ C}{∂ \color{red}z_i^{(l-1)}} ...\frac{∂ C}{∂ \color{red}a_i^{(1)}}，最後算到 \frac{∂ C}{∂ \color{red}w_{ij}^{(1)}}，求出每一個 \frac{∂ C}{∂ w_{ij}} 之後我們就可以利用 Gradient Descent 法來找出更好的 w_{ij}

w_{ij} \leftarrow w_{ij} - \eta \frac{∂ C}{∂ w_{ij}}

注意到了嗎？這跟前面所敘述的 Reverse-Mode AD 是一樣的計算過程，這代表我們可以利用它來取代Back Propagation 跟 AD 都應用了 chain rule 來計算，不同的是使用 AD 的技巧後不再需要推導公式。手動推導的 Back Propagation 演算法。

為什麼類神經要用 Reverse-Mode AD?

Jacobian matrix 是一個 f: ℝ^n \rightarrow ℝ^m 的所有偏導數所組合而成的矩陣：

\mathbf {J} = \begin{bmatrix} \frac {\partial f_{1}}{\partial x_{1}} & \cdots & \frac {\partial f_{1}}{\partial x_{n}}\\[0.5em] \vdots &\ddots &\vdots \\[0.5em] \frac {\partial f_{m}}{\partial x_{1}} & \cdots & \frac {\partial f_{m}}{\partial x_{n}} \end{bmatrix}

Reverse-Mode AD 就是一次算一個 row，Forward-Mode AD 則是一次算一個 column。由於類神經網路是一個 n \gg m 的函數，用 Reverse-Mode AD 有效率了不少。

Wengert Tape

其中一個作法是使用 Wengert Tape ，這個資料結構追蹤順向計算的過程，Reverse-Mode AD 時則是會反過來計算。

為了簡化，這邊將計算的過程推廣成三種形式： 變數、單變數函數、雙變數函數。這邊的實作參考自 Edward Kmett 所寫的 ad 自動微分函式庫。注意：為了方便實作跟解釋，我的實作有稍微變化過。

• x （或是 y） 表示這個計算的輸入節點 x, y（反向的達到了前述第 3 點）
• dx （或是 dy） 表示輸入對這個計算的影響 \frac{∂f}{∂x}, \frac{∂f}{∂y}，也就是前述第 2 點的\color{green}\text{綠色}部份。
• ss 表示這個計算對於整個計算的影響 \frac{∂ Y}{∂ f}，也就是前述第 1 點的\color{blue}\text{藍色}部份。

from collections import namedtuple
Var = namedtuple('Var', ['ss'])
Un  = namedtuple('Un',  ['x', 'dx', 'ss'])
Bin = namedtuple('Bin', ['x', 'y', 'dx', 'dy', 'ss'])

這樣就可以下面的這段程式來表達 sin(x) + x \cdot y \bigg\vert_{x = 3, y = 1} 的順向計算過程為了簡化，我省去了當下計算的輸出數值v(f(x))

⊕ 這邊我小小的作弊了一下，直接使用 Dict 來方便更新 ss 的值。

⊕ 這張圖表示順向計算時所累計的數值

⊕ 這張圖表示節點之間的相依關係

from math import *
def box(v=0):
    return {'value': v}

x = Var(box())
y = Var(box())
sin_x = Un(x, cos(1), box())
x_times_y = Bin(x, y, 1, 3, box())
Y = Bin(sin_x, x_times_y, 1, 1, box())

Wengert Tape 就是紀錄輸入變數及這一連續的計算過程。

tape = [x, y, sin_x, x_times_y, Y]

當計算 Reverse-Mode AD時，我們會將 tape 反過來累計：⊕ 注意到這邊的實作已經在前面建構這些節點的同時，將順向計算的過程給嵌進去了。

Y.ss['value'] = 1 # 從 ∂Y/∂Y = 1 開始
for cell in reversed(tape):
    if isinstance(cell, Bin):
        cell.x.ss['value'] += cell.ss['value'] * cell.dx
        cell.y.ss['value'] += cell.ss['value'] * cell.dy
    elif isinstance(cell, Un):
        cell.x.ss['value'] += cell.ss['value'] * cell.dx

Reverse Mode AD 就像這樣在一個 pass 就能算出所有輸入的偏導數

>>> x.ss['value'], y.ss['value']
(0.010007503399554585, 3)

剩下的就是實作一個易用的界面給使用者了，也就是只需要指定順向計算的過程。

>>> x = var(3)
>>> y = var(1)
>>> Y = sin(x) + x * y
>>> Y.value
3.1411200080598674
>>> Y.tape
Tape([<Var object at 0x7f84dbfed198>,
 <Unary object at 0x7f84e6968c50>,
 <Var object at 0x7f84e3e567b8>,
 <Binary object at 0x7f84e0dff4e0>,
 <Binary object at 0x7f84dbfed630>])
>>> Y.backprop()
>>> x.sensitivity
0.010007503399554585

Example: Softmax Regression

⊕ 我的「玩具版」 Reverse-Mode AD 實作函數庫放在這邊。

這次以 ML 常用的 iris 資料集作為範例，建構一個 Softmax Regression 來分類這些花朵。

from reverse_ad import *
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

iris = load_iris()
X = iris['data']
Y = iris['target']
X_train, X_test, Y_train, Y_test = train_test_split(X, Y)

這邊使用 Softmax Regression 做分類，用 Cross Entropy 做為 loss function。⊕ \begin{gathered} Softmax(X_i) = \frac{exp(X_i)}{\sum_k exp(X_i)} \\ f(X; W, B) = Softmax(W \times X + B) \\ Cost(Y, \hat Y) = \frac{-1}{|Y|}\sum_{y} \sum_{k} y_k \log(\hat{y}_k) \end{gathered}

def softmax(z):
    z_exp = [exp(i) for i in z]
    sum_z_exp = sum(z_exp)
    return [i / sum_z_exp for i in z_exp]

def reg(xs, w, b):
    return softmax([sum(w[i][j] * x for j, x in enumerate(xs)) + b[i]
                    for i in range(3)])

def categorical_cross_entropy(Y, Y_):
    loss = sum(sum(k * log(k_) for k, k_ in zip(y, y_)) for y, y_ in zip(Y, Y_))
    return -1 * loss / len (Y_)

用 Gradient Descent 來找到更好的 W 跟 B

⊕ 這邊需要先對標籤做 one-hot encoding 才會有跟公式輸出一致的維度。

from sklearn.metrics import accuracy_score
Y_encoded = OneHotEncoder().fit_transform(Y_train.reshape(-1, 1)).todense().tolist()
w = [[var(0) for _ in range(4)] for _ in range(3)]
b = [var(0) for _ in range(3)]
lr = 0.1

⊕ 使用 Reverse Mode AD 就不再需要每一個參數都再計算一次。

for epoch in range(1000):
    Y_predicted = [reg(x, w=w, b=b) for x in X_train]
    loss = categorical_cross_entropy(Y_encoded, Y_predicted)
    loss.backprop()
    for i in range(3):
        b[i] -= lr * b[i].sensitivity
        for j in range(4):
            w[i][j] -= lr * w[i][j].sensitivity
    if epoch % 10 == 0:
        accuracy = accuracy_score(Y_test, [tolabel(reg(x, w=w, b=b)) for x in X_test])
        print(f'{epoch: 5d} loss {loss.value} acc {accuracy}')

跑起來成果像是這樣：

    0 loss 1.098612288668108   acc 0.34210526315789475
   10 loss 0.84323472659183    acc 0.6578947368421053
   20 loss 0.716723873894274   acc 0.6578947368421053
   30 loss 0.6493242141034026  acc 0.6578947368421053
   40 loss 0.6030807982006535  acc 0.6578947368421053
   50 loss 0.5661515656844388  acc 0.6578947368421053
   60 loss 0.5340659822896819  acc 0.6578947368421053
   70 loss 0.5047568856139167  acc 0.6578947368421053
   80 loss 0.4771475569375817  acc 0.6578947368421053
   90 loss 0.45064476873213055 acc 0.6578947368421053
  100 loss 0.42493012219412674 acc 0.6578947368421053
  110 loss 0.39987107522910936 acc 0.7105263157894737
  120 loss 0.37549205547113373 acc 0.7105263157894737
  130 loss 0.3519881981460512  acc 0.7368421052631579
  140 loss 0.3297816399879364  acc 0.7631578947368421
  150 loss 0.30960905639139913 acc 0.868421052631579
  160 loss 0.2925264903210591  acc 0.9210526315789473