# 類神經網路的 ReLU 及其常數時間複雜度實作
> 資料整理: [jserv](https://wiki.csie.ncku.edu.tw/User/jserv)

## 類神經網路的激勵函數

ReLU 全名為 Rectified Linear Unit，中譯為「修正線性單元」，是種類神經網路中激勵函數 (activation function，也可翻譯為活化函數)。所謂的激勵函數，用意是增加類神經網路裡頭的非線性特徵。早期尚未發展出深層網路時，時常被拿來做資料預測的演算法是[線性回歸法](https://en.wikipedia.org/wiki/Linear_regression) (linear regression)，正如字面上的意義，線性回歸法只能用來預測呈線性分佈的資料，非線性的關係就難以用這樣的函數來描述。但現實生活中大部分的現象都是非線性，例如[美國人的收入與年齡之間的關係呈曲線分佈](https://www.reddit.com/r/dataisbeautiful/comments/1dqsxn/us_total_money_income_distribution_by_age_2012/)，這樣要給定一個年紀的人，去預測他的收入，就顯然難以利用線性回歸。因此，為解決更複雜的問題，人們就發展出了帶有非線性特徵的 [Logistic Regression](https://medium.com/@chih.sheng.huang821/%E6%A9%9F%E5%99%A8-%E7%B5%B1%E8%A8%88%E5%AD%B8%E7%BF%92-%E7%BE%85%E5%90%89%E6%96%AF%E5%9B%9E%E6%AD%B8-logistic-regression-aff7a830fb5d)，開始可解決簡單的二分法問題。

然而一個 Logistic Regression 的能力還是有限，[即便是二分法都有無法正確分類的狀況](https://youtu.be/hSXFuypLukA?list=PLJV_el3uVTsPy9oCRY30oBPNLCo89yu49&t=3388)，因此為了得到更強大的函數，數學家嘗試串接多個 Logistic Regression，形成初步的類神經網路。
> 對照參閱台大電機系[李宏毅](https://speech.ee.ntu.edu.tw/~tlkagk/)教授的[機器學習線上課程](https://www.youtube.com/c/HungyiLeeNTU/playlists)。

ReLU 定義如下:
$$
ReLU(x) =
\begin{cases}
x & \text{if } x \geq 0 \newline
0 & \text{if } x \lt 0
\end{cases}
$$

ReLU 計算量小，只要判斷輸入是否大於 `0`，沒有指數運算。


## 常數時間度 ReLU 實作

思路：由於 ReLU 函數要判斷輸入數值的正負，但浮點數的操作成本較高，於是我們可引入 union，讓 float 和 int (有號整數) 共用同一段記憶體空間 (針對 LP64 data model):

float ReLU(float x)
{
    union {
        float f;
        int32_t i;
    } out = { .f = x };
    ...
}

首先我們回顧有號整數的表達方式，為了方便圖解，下列圖示以 8 位元的整數 (即對應到 C 語言的 `int8_t`，定義於 `<stdint.h>` 標頭檔)
> sign bit 為 `0` 時，表示該數值為「正」，數值為 $0 \times 2^0$ (最右邊的位元) + $0 \times 2^1$ (右邊數來第二個位元) + $1 \times 2^2$ (右邊數來第三個位元) = 4 (十進位)

> sign bit 為 `1` 時，表示該數值為「負」，右側 7 個位元表示數值 $2^7 - 4 = 124$，這編碼採用[二補數](https://hackmd.io/@sysprog/binary-representation)

[二補數](https://hackmd.io/@sysprog/binary-representation)看似不直觀，但可縮減運算的成本。例如十進位的 $-4$ 和 $-1$ 相加，透過[二補數](https://hackmd.io/@sysprog/binary-representation)運作如下:

從上圖右方起逐位元進行加法運算，連帶 sign bit 也可運算，超過 8 位元能表達的位元 (即上圖左下的 `1`) 就直接捨棄，這樣就讓電路設計變得單純。

另外，在[二補數](https://hackmd.io/@sysprog/binary-representation)系統中，對有號數的位移 (shift) 概念上也跟無號整數相同，但為了確保最終結果的正負號一致，需要額外的運算規則:
> 當你將有號整數右移，需要在左側填補一致的 sign bit

知曉[二補數](https://hackmd.io/@sysprog/binary-representation)系統及有號整數右移的規則後，我們考慮 `~(out.i >> 31)` 這個表示方式，其實相當於取參數 `x` 的 sign bit，分為以下兩種狀況:
* 若 $x < 0$，則 `~(out.i >> 31)` 得到運算結果是 `000...00` (32-bits)
* 若 $x >= 0$，則 `~(out.i >> 31)` 得到運算結果是 `111...11` (32-bits)

再將 `x` 和上述 `~(out.i >> 31)` 進行 AND 運算，即為 ReLU 函數的定義。

程式碼列表如下:

#include <stdint.h>
// 當輸入 x 大於等於 0 時，回傳 x，否則回傳 0
float ReLU(float x) {
    /* 宣告一個 union，由兩個 field 組成
     * 一個型態為 float，用以儲存原本的資料
     * 一個型態為 int，用以進行位移運算
     * 由於 union 中的所有欄位共用同一份記憶體
     * 且 float 和 int32_t 都佔四個 byte
     * 因此對 i 操作時等同於在變更 f 的值
     */
    union {
        float f;
        int32_t i;
    } out = {.f = x}; /* 將資料存入 union */
    /* 由於 int32_t 是有號數型態，因此位移時是採用算數位移（帶號）
     * 將此數向右位移 31 次，會使 4 個 byte 被 sign 值填滿
     * （若非負則為 0，否則為 1）
     * 將其反相後，即成為 & 運算的遮罩
     * 以此遮罩與原本的資料做 & 運算，若非負則內容不變
     * 否則會全部變成 0
     */
    out.i &= ~(out.i >> 31);
    /* 將處理完的結果以 float 的型態回傳 */
    return out.f;
}

## ReLU 與其他激勵函數的比較


[Sigmoid function](https://en.wikipedia.org/wiki/Sigmoid_function) 作為 Logistic Regression 的激勵函數，是這個算式當中非線性特徵的由來。由於 Logistic Regression 的目的是做分類，其輸出是一個機率值，故其值域會介於 $[0, 1]$ 之間。在[反向傳播演算法](https://www.youtube.com/watch?v=ibJpTrp5mcE&list=PLJV_el3uVTsPy9oCRY30oBPNLCo89yu49&index=12) (Backpropagation) 發明後，人們發現在計算神經網路中每一層結點的參數時，由於 Sigmoid 會把 $(- \infty , \infty)$ 的輸入映射到 $[0, 1]$ 之間，會造成在反向傳播參數時每一層的數字愈算愈小，到最後幾層的數字全都是 0 的梯度消失 (Gradient Vanishing) 現象。後來出現的 [Hyperbolic tangent function (tanh)](https://en.wikipedia.org/wiki/Hyperbolic_function)（長高了的 Sigmoid，其值域在 $[-1, 1]$ 之間）也有類似的問題。

因此，在[ Yoshua Bengio 的論文](http://proceedings.mlr.press/v15/glorot11a/glorot11a.pdf) (第 318 頁) 中，提到以 ReLU 取代其它激勵函數的好處：

> The rectifier activation function allows a network to easily obtain sparse representations.
> ......
> Apart from being more biologically plausible, sparsity also leads to mathematical advantages (see previous section).
> ......
> Computations are also cheaper: there is no need for computing the exponential function in activations, and sparsity can be exploited.

統整論文的描述:
* ReLU 較容易使得神經網路的結構變得稀疏，因為算出來參數為負的結點被視為沒有貢獻，因此輸出為 0，相當於是從神經網路中被拿掉了
* ReLU 的行為比較符合生物學當中觀察到的神經活化現象（全有全無律，也就是在刺激不夠大的時候，神經根本不會有反應回饋出現的現象）
* ReLU 的計算量比較小

> 在神經生理方面，當刺激未達一定的強度時，神經元不會興奮，因此不會產生神經衝動。如果超過某個強度，才會引起神經衝動。ReLU 較好捕捉這個生物神經元的特徵。

因此， ReLU 成為現代訓練類神經網路時，常用的激勵函數之一。

延伸閱讀:
* [深度學習：使用激勵函數的目的、如何選擇激勵函數](https://mropengate.blogspot.com/2017/02/deep-learning-role-of-activation.html)