# BinaryConnect: Training Deep Neural Networks with binary weights during propagations
作者：Matthieu Courbariaux, Yoshua Bengio, Jean-Pierre David
論文連結：https://arxiv.org/abs/1511.00363
整理by: [chewei](https://hackmd.io/@WTuIbJANSB26DiAX-WL4Sg)

- - - - -

## 0. 論文貢獻
本篇論文提出了BinaryConnect的 ***"方法"*** 來實現把在訓練中forward跟back propagations的權重以**二元化**後**累加**（accumulated）的方式代替**乘法**運算（multiply-accumulate operations）

$\Rightarrow$大量降低耗電(power-hungry)及空間（space）使用率

## 1. 本篇論文的研究基石
***Noisy weights：*** 指的是權重參數加入隨機性的情況，這種隨機性可能來自於訓練數據的內在噪聲、初始化過程、或是訓練過程中使用的某些正則化技術。這種噪聲有時可以幫助模型避免過度適應訓練數據（overfitting）。

在Stochastic Gradient Descent (SGD)中，***保持期望值的高精度比高精度來的重要***，也就是只要權重的***期望值***相同，加入Noisy weights是可以有效防止overfitting發生的。

回到論文主題Binarize來看，其實這種二元化就是將權重離散化，跟Noisy weights概念相似，因此也是可以達到防止***overfitting且提高效率***的效果。
## 2. Deterministic vs stochastic binarization
>此部份與下一篇BNNs相同，在BNNs中將會探討何者較適合被用在架構內

***Deterministic function（AKA Sign function）：***

$$x^b =
\text{Sign}(x) = \begin{cases}
+1 & \text{if } x \geq 0, \\
-1 & \text{otherwise},
\end{cases} $$
$x^b$ 是binarized後的變數
x 是轉換前的真實變數

***Stochastic function:***

$$x^b =
\begin{cases}
+1 & with \, probability \,\, p=\sigma(x),\\
-1 & with \, probability \,\, 1-p,
\end{cases}
$$

***$\sigma$是"hard sigmoid" 函式:***

$$
\sigma(x)=\text{clip}(
\frac{x+1}{2} \quad,0,1)=
\text{max}(0,\text{min}(1,\frac{x+1}{2}))
$$
## 3. Propagations vs updates
> 探討在"參數傳遞"和"SGD更新參數"時是否皆有必要進行離散化（二元化）。

**前向傳播（forward-propagation）：**
給定DNN的輸入後，一層一層**計算單元**(unit)**的激活函數**(activations)直到最後一層。

**後向傳播（back-propagation）：**
給定DNN的輸出後，一層一層往前**計算梯度**(gradient)直到第一層。

**參數更新（parameter update）：**
在每一層計算完梯度後，會以剛才1.**計算好的梯度**2.**先前的參數值**用來**更新參數**(update parameter)。

$\rightarrow$ 作者根據以下演算法各步驟拆分開來看，發現在**更新參數**（parameter update）時，SGD所需的較高的精度來進行細微的改變（這些微小的改變是通過梯度下降獲得的），因此在這個部份的參數**不會被Binarize**。

$\rightarrow$ 只有在**前向傳播（forward-propagation）**，**後向傳播（back-propagation）** 時的參數會做**Binarize**
<details>
<summary>SGD with BinaryConnect演算法</summary>

**Requitre:**
1. minibatch 的輸入及目標
2. 前一個參數$w_{t-1}$(weights)
3. $b_{t-1}$(biases)
4. 學習率$\eta$

**Ensure:**
更新後參數$w_t$和$b_t$

1.**前向傳播（forward-propagation）：**

$$
\begin{align*}
& w_b\leftarrow\text{binarize}(w_{t-1}) \\
& \text{ For } k=1 \text{ to } \text{ L ,}\text{ compute } a_k \text{ knowing } a_{k-1},w_b \text{ and } B_{t-1}
\end{align*}
$$
2.**後向傳播（back-propagation）：**
$$
\begin{align*}
& \text{Initialize output layer's activations gradient}\frac{\partial C}{\partial a_L} \\
& \text{For k=L to 2 ,compute}\frac{\partial C}{\partial a_{k-1}}\text{ Knowing }\frac{\partial C}{\partial a_k}\text{ and }w_b
\end{align*}
$$
3.**參數更新（parameter update）：**
$$
\begin{align*}
& \text{Compute}\frac{\partial C}{\partial w_b}\text{ and }\frac{\partial C}{db_{t-1}}\text{Knowing}\frac{\partial C}{\partial a_k}\text{and}a_{k-1} \\
& w_t\leftarrow\text{clip}(w_{t-1}-\eta\frac{\partial C}{\partial w_b}) \\
& b_t\leftarrow b_{t-1}-\eta\frac{\partial C}{\partial b_{t-1}}
\end{align*}
$$
</details>

## 4.Clipping

在每次**參數更新後**對其做clipping達到正則化效果，並把參數限制在+/-1，其作法如第2.點公式。

## 5.實驗
1.以Deterministic function的方式做二元化，並且在inference時使用**二元化後的參數進行檢測** 。

2.以Stochastic function的方式做二元化，但此二元化計算完後會將權重**轉換回real-valued的權重進行檢測** 。

結果如下圖：
$$\text{Error Rate}$$
> 二元化後的準確率不減反增，作者認為這是因為二元化可視為一種Dropout
## Reference
Dropout
DropConnect