ECCV2016に採択されたXNOR-Netについての解説．

この論文は畳み込みニューラルネットワークについて，2種類の効率的な近似を提案:

Binary-Weight-Networks
XNOR-Networks

Binary-Weight-Networksではフィルタの重みが2値で表現され，XNOR-Networksではフィルタの重みと入力の両方が2値で近似される．

f:id:noconocolib:20181221023042p:plain — Fig. 1: Binary-Weight-Networks and XNOR-Networks.

Preliminaries

$\langle \mathcal{I}, \mathcal{W}, * \rangle$ ：L-layer CNN architecture.
$\textbf{I} = \mathcal{I}_{l (l=1,\ldots,L)}$ ：入力集合．
$\textbf{W} = \mathcal{W}_{lk (k=1,\ldots,K^{l})}$ ：フィルタの重み集合．
$*$ ： $\mathcal{I}$ と $\mathcal{W}$ の畳み込み操作．

Binary-Weight-Networks

実際のCNNの重み $\textbf{W}\in \mathbb{W}$ を2値フィルタ $\textbf{B} \in \left\{+1, -1\right\}^{c\times w \times h}$ とscaling factor $\alpha \in \mathbb{R}^+$ を用いて推定したい．
畳み込み処理は以下のように近似できる

$\textbf{I} * \textbf{W} \approx (\textbf{I} \oplus \textbf{B}) \alpha$

重みを2値で表現することで，以下のメリットがある，

畳み込み処理を加算と減算のみで効率的に実装できる．
単精度の場合と比べてメモリ使用量を1/32まで効率化できる．

Estimating binary weights

重み $\textbf{W}$ の最適な近似 $\alpha\textbf{B}$ を得るために，以下の最適化問題を解く：

$J(\textbf{B}, \alpha) = ||\textbf{W} - \alpha \textbf{B}||^2$

$\alpha^{*}, \textbf{B}^{*} = argmin_{\alpha, \textbf{B}} J(\textbf{B}, \alpha)$

$J(\textbf{B}, \alpha) = \alpha^{2} \textbf{B}^{T} \textbf{B} - 2 \alpha \textbf{W}^{T} \textbf{B} + \textbf{W}^T \textbf{W}$

$\textbf{B} \in \left\{+1, -1 \right\}^n$ なので， $\textbf{B}^{T} \textbf{B}$ は定数 $n$ になる． $\textbf{W}^{T} \textbf{W}$ もまた定数になり，これを $c$ と置くと，目的関数は，以下のようになる．

$J(\textbf{B}, \alpha) = \alpha^{2} n - 2 \alpha \textbf{W}^T B + c$

定数項と正の値 $\alpha$ を無視すると， $\textbf{B}$ の最適解は，

$\textbf{B}^{*} = argmax_{\textbf{B}} { \textbf{W}^{T} B} \ \ s.t. \ \ \textbf{B} \in \left\{+1, -1 \right\}^n$

この最適化問題は，

$\textbf{B}_{i} = 1 \ \ if \ \ \textbf{W}_i \geq 0$
$\textbf{B}_{i} = -1 \ \ if \ \ \textbf{W}_i \lt 0$

とすることで解ける．つまり $\textbf{B}^{*} = sign(\textbf{W})$ ．

scaling factor $\alpha^{*}$ は， $J$ を $\alpha$ について微分することで求まる．

$\alpha^{*} = \frac{\textbf{W}^{T} \textbf{B}}{n}$

$\alpha^{*} = \frac{\textbf{W}^{T} sign(\textbf{W})}{n} = \frac{\sum{|\textbf{W}_i|}}{n} = \frac{1}{n} ||\textbf{W}||_{l1}$

まとめると，

2値重みフィルタ $\textbf{B}$ の最適値は重み $\textbf{W}$ のsignを取ればよく，
scaling factor $\alpha$ の最適値は重み $\textbf{W}$ の絶対値の平均を取ればよい．

Training Binary-Weights-Networks

Alg. 1にBinary-Weight-Networksの学習アルゴリズムを示す．

f:id:noconocolib:20181221031818p:plain — Fig. 2: Training a CNN with binary weights

XNOR-Networks

フィルタの重みだけでなく入力の2値化も実現するため，以下を定義する．

Binary Dot Product
Binary Convolution
Binary Gradient

Binary Dot Product

$\textbf{X}, \textbf{W} \in \mathbb{R}^{n}$ 間のドット積を近似したい．つまり， $\textbf{X} \textbf{W} \approx \beta \textbf{H}^{T} \alpha \textbf{B}$ ．目的の近似を達成するため，以下の最適化問題を解く．

$\alpha^{*}, \textbf{B}^{*}, \beta^{*}, \textbf{H}^{*} = argmin || \textbf{X} \odot \textbf{W} - \beta \alpha \textbf{H} \odot \textbf{B}||$

$\textbf{Y}_{i} = \textbf{X}_{i} \textbf{W}_{i}$ ， $\textbf{C}_{i} = \textbf{H}_{I} \textbf{B}_{i}$ ， $\gamma = \beta \alpha$ とすると，

$\gamma^{*}, \textbf{C}^{*} = argmin || \textbf{Y} - \gamma \textbf{C}||$

最適値は，

$\textbf{C}^{*} = sign(\textbf{Y}) = sign(\textbf{X}) \odot sign(\textbf{W}) = \textbf{H}^{*} \odot \textbf{B}^{*}$

$\gamma^{*} = \frac{\sum |\textbf{Y}_i|}{n} = \frac{\sum |\textbf{X}_i||\textbf{W}_{i}|}{n} \approx \Big( \frac{1}{n} ||\textbf{X}|| \Big) \Big( \frac{1}{n} ||\textbf{W}||\Big) = \beta^{*} \alpha^{*}$

Binary Convolution

入力とフィルタの重みを2値化した際のConvolutionの近似をFig. 2に示す． scaling factorが得られたとき， $\textbf{I}$ と $\textbf{W}$ との間に定義される畳み込みは，

$\textbf{I} * \textbf{W} \approx (sign(\textbf{I}) \circledast sign(\textbf{W})) \odot \textbf{K} \alpha$

$\circledast$ はXNORとbitcountを用いた畳み込み操作を意味する．Fig. 2から，バイナリ演算に比べて非バイナリ演算は非常に少ないことがわかる．

f:id:noconocolib:20181221034157p:plain — Fig. 2: Approximating a convolution using binary operations.

Binary Gradient

Forwardパスと同様に，Backwardパスにおける入力に対応する勾配 $g^{in}$ も2値化することができる．

Experimental Results

Double precisionのモデルと比べて，大幅な省メモリ化を達成できていることがわかる．

f:id:noconocolib:20181221041150p:plain — Fig. 3: Required memory for binary and double precision weights

Full Precisionのモデルと比較しても，十分良い分類性能を達成できていることがわかる．

f:id:noconocolib:20181221041321p:plain — Table 1: This table compares the final accuracies (Top1 - Top5) of the full precision network with our binary precision networks; Binary-Weight-Networks(BWN) and XNOR-Networks(XNORNet) and the competitor methods; BinaryConnect(BC) and BinaryNet(BNN).

References

Rastegari, Mohammad, et al. "Xnor-net: Imagenet classification using binary convolutional neural networks." European Conference on Computer Vision. Springer, Cham, 2016.