【読解】 Binarized Neural Networks

# 0. Binarized Neural Networksとは
平易に換言すると、浮動小数点を使わない(2値化)NeuralNetworkの総称をBNNといい、その中のBinary NetやBinary Connectなど沢山ある手法の内の1つがBinarized Neural Networksという。最近だと、BNN-PYNQなどで用いられて有名になった。実装はTheanoで公開されている。一般的にBNN化することにより、精度は落ちるもののメモリ使用率が劇的に少なくなるという特徴を持つ。精度は下がると言えども、多少である。このため、FPGAの実装などに用いられることが多い。

なお、本稿で扱うBNNとはBinarized Neural Networksを指すこととする。
論文はこれ→https://arxiv.org/pdf/1602.02830.pdf

技術的な特徴としては、ActivationとWeightを2値化する。勾配は浮動小数点(実数)で持つ。

# 1. Deterministic (決定論的) v.s. Stochastic (確率論的) Binarization 

BNNでは重み(Weight)と活性値(Activations)を+1もしくは-1にしている。これを2値化という。

この2値化処理にはDeterministicとStochasticの2つの手法がある。


$Deterministic$:

```math
x^{b} = Sign(x) = \left\{
\begin{array}{ll}
+1 & if(x \geq 0), \\
-1 & otherwise,
\end{array}
\right.
```

$Where$:

$x^{b}$: Binarized variable (Weight/activationsの2値化された変数)
$x$: Real-valued variable (実数変数)

---

$Stochastic$:

```math
x^{b} = \left\{
\begin{array}{ll}
+1 & with\ probability & p = \sigma(x) , \\
-1 & with\ probability & 1 - p,
\end{array}
\right.
```

$Where$:

$\sigma$: hard sigmoid (ハードシグモイド関数)
$\sigma = clip(\frac{x+1}{2},\ 0,\ 1) = max(0, min(1, \frac{x+1}{2})).$

---

元々、決定論的なSign関数を考えていたんだだけれども、確率論的な関数の方が魅力的！となったそうです。しかし、ハードウェアに実装するにはランダムビット列の生成が重い処理だよねという話になったみたいで、これらの使い分けを以下のようにしたそうです。



| Time[^1] | Weight | Activation |
|:-----------:|:------------:|:------------:|
| Train | 決定論的 | 確率論的 |
| Inference | 決定論的 | 決定論的 |

[^1]: As a result, we mostly use the deterministic binarization function (i.e, the sign function), with the exception of activations at train-time in some of our experiments.



# 2. 勾配計算と累積について(Gradient Computation and Accumulation)
トレーニング時の入出力(Weight/Activation)は2値を用いる。しかし、勾配は実数値で蓄積しておく。結局は勾配法を使うので、浮動小数点を用いておかないと勾配が分からなくなるとのこと。探索による値のアップデート(勾配法)は、各重みに積算されていき、いづれ平均的な値に落ち着く。また、WeightやActivationにノイズを加えることで、一種の正則化効果を与えているそうだ。

これはDropoutの仕組みに近いらしい。Dropoutでは無作為に活性化関数の出力をゼロにする。しかし、BNNではWeightとActivationを二値化することでそれを実現しているらしい。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/95636/8d0aeacf-eb01-025a-d2e4-0ac9cd168d5a.png)

#3 離散化と勾配の伝搬 (Propagating Gradients Through Discretization)
$Sign$関数を微分した$Sign'$はeverywhereで勾配が0らしい。なので逆誤差伝搬できないらしい！！！

そこで、逆誤差伝搬する場合は、上位から伝搬してきた微分値を、そのまま下の層に伝えることにしたそうだ。これはstraight-through estimatorというらしい。

そこで決定論的な話がでてくる。

まずはSign関数の量子化。

```math
q = Sign(r),
```

勾配$\frac{\partial C}{\partial q}$の推定値$g_q$が既に得られているとする。この時、straight-through estimatorは、以下となる。

```math
g_r = {g_q}^1 |r| \leq 1 ・
```

この時、$r$があまりにも大きすぎると勾配が著しく悪化する。このため、勾配が大きい場合は消去する。

$1_{|r| \leq 1} $はHard-tanhを介す勾配の伝搬と見なせる。

このHard-tanh、すなわちpiece-wise linear activation functionは以下のような形になる。

$Htanh(x) = Clip(x,\ -1,\ 1) = max(-1, min(1,\ x))$

次に隠れ層に対して、

 * Activationに対してSign関数を用いる。

 * Weightに対しては、境界値をを-1から1の間に制限。多分これは入力画像も同じ。Weightの更新によって$W^r$が境界値を超えるときは、クリッピングをする。ようは-1を超えるときは-1で、1を超えるときは1にする。これを数式的に量子化させると$w^b = Sign(w^r)$こんな感じになる。

---

ここでアルゴリズムのおさらい。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/95636/8d0aeacf-eb01-025a-d2e4-0ac9cd168d5a.png)

まずフォワード:
1. 各レイヤごとに重みを決定論的/確率論的にバイナライズ化。もちろんClipも行う。
2. バイナライズ化された入力値(前のレイヤの出力×重み)を掛ける。すなわち、$a_n w_n$となる。これを$s_n = a_n w_n$とする
3. 次に$s_n$をバッチノーマライゼーションする。これを$a_n$とする。
4. 最終層以外の$a_n$をバイナライズ化する。最終出力はバイナライズ化しない。

次にバックワード:
偏微分して確率と決定的でActivationかけるだけ。

学習レート:
EDLを使う。

# 4. Training
# 4.1. Loss
損失関数には2乗ヒンジ損失(square hinge loss)を用いる。
$l(y) = max (0, 1 - ty)$
このバッチ分の合算値が損失となる。
$l = \sum l(y)$
ターゲットt(正解)は-1 or +1であり、推定値yも-1 or +1である。このため、お互い-1か+1で正解しているとき損失は0になる。
もし誤差がある場合、1 - (-1)となり、誤差が出てくる。

Inferenceの時は、Argmaxが分類の推定となる。

# 4.2. Optimizer
OptimizerはAdamとExponentially decaying learningを併用して使う。ようは学習率を最初は大きく、勾配が滑らかになったら学習率を下げていく方法。Optimizerに乗っかっているので、Batch normalizationにExponential moving averageを載せてあげなくてもいいみたい。

もし、Optimizer側でEDLを使わないのであれば、Batch normalization側でEMAを使ってあげるとよい？



# A. Batch Normalization
<img width="505" alt="20170616154548.png" src="https://qiita-image-store.s3.amazonaws.com/0/95636/3b69df41-ac28-bdd3-0760-1ed90f0d34d2.png">

Exponential Moving Averageを用いたBatchnormalizationの場合、mean, varに指数移動平均を掛ける必要がある。
これを保存しておく。数式でいうところの以下が各mean, varである。

${\sigma_\beta}^2$: var
${\mu_\beta}$: mean

よって、${\mu_\beta}$, ${\sigma_\beta}^2 = ema({\mu_\beta}, {\sigma_\beta}^2)$を得る。

Forward:
順方向(Inference)に限った場合は、上記で得られたmean, varに加えて、gamma、beta、epsを保持しておき、以下で計算する。


$\hat{x_i} \longleftarrow \frac{x_i-\mu_\beta}{\sqrt{{\sigma_\beta}^2 + \epsilon}}$
$y_i \longleftarrow \gamma\hat{x_i} + \beta$

![image.png](https://qiita-image-store.s3.amazonaws.com/0/95636/4bc9ffde-b738-fd22-c228-e8d8b48a7b2b.png)
これを上記式で計算すると、以下になる。
![image.png](https://qiita-image-store.s3.amazonaws.com/0/95636/73caf1d0-ef8c-b830-3301-0cb9cae12089.png)
これはTensorflowの計算結果と一致している。