深度學習最近在object recognition， speech recognition, machine translation, games, image generation等各個領域突飛猛進，都取得了state of the art的效果。越來越多的學術界以及工業界的研究人員将深度學習應用到傳統的領域， 推動這些領域的變革，以及整個AI領域的發展。相對于傳統的淺層學習， 深度學習模型複雜， 參數多，訓練和Inference的計算量大。以AlexNet為例：
網絡深度達到8層
參數規模超過 60M
一張圖檔的Inference需要約1G FLOPS
Object recognition中的其他重要的模型：VGG, GoogleNet , ResNet等都比AlexNet複雜， 參數規模有增減， 但計算量都增加了不少。比如100層的ResNet一張圖檔的Inference計算量超過了10G FLOPS。
這些問題給深度學習在伺服器端、移動端以及其他嵌入式裝置的應用帶來挑戰，主要集中在兩個層面
參數規模大：影響模型的部署和更新，同時會降低Cache命中率，增加Inference時間
Inference的latency過高: 計算量多大， AlexNet上一張圖檔的Inference在CPU上需要上百毫秒
這些都限制深度學習的發展。針對上述問題，一方面可以通過硬體來加速：Nvidia不停的釋出加速深度學習訓練、Inference的GPU，Google也推出了TPU等，以及很對團隊研究通過使用FPGA來加速。另一方面， 可以通過
結合硬體結構， 設計針對深度學習模型的量化壓縮、Inference加速算法。主要有：
parameter pruning & sharing
Low-rank factorization
Transfered/compact convolutional filters
Knowledge distillation
深度學習模型的量化壓縮算法是目前的一個研究熱點，每年在NIPS， ICLR等計算機頂級會議上都有很多相關的文章, 也獲得了學術界和工業界的認可，比如Song Han的Deep Compression算法獲得了2016年ICLR的“Best Paper Award"。在阿裡巴巴購物搜尋中， 我們訓練了大量的深度學習模型中， 運作在阿裡巴巴的伺服器叢集上， 使用CPU, GPU計算。由于GPU成本較高以及FPGA研發周期長， 而伺服器叢集有大量的CPU，是以我們設計了一套基于CPU的深度學習模型量化壓縮與Inference加速算法AQN： Alternating multi-bit Quantzation Network， 并在搜尋的相關業務上上線， 取得了非常不錯的效果。
為了優化GEMM，基于綜合比較，我們選擇了基于binary的量化算法， 并在此基礎上提出了新的量化算法（AQN）。Courbariaux M等首先提出了BinaryConnect， 将GEMM的每個參數以及每個輸入都量化成1個bit表示的$\{-1, 1\}$的算法，大幅壓縮模型大小，但模型精度降低了很多。Mohammad Rastegari等在此基礎上提出了XNOR Net，模型大小不怎麼變化， 但相對BinaryConnect模型精度大幅提升。 為了介紹AQN， 我們首先介紹XNOR Net。對于矩陣 $A \in \Re^{m \times n} $ 的binary 量化過程為：
可以表示為 ：
$$
A \approx \alpha \times A_b
其中:
\alpha \in \Re \ and \ \alpha \geq 0
A_b \in \{-1, +1\}^{m \times n}
由于$A_b$中所有的element都是$\{+1, -1\}$， 是以存儲該矩陣的時候可以用一個bit來表示矩陣中的一個element，當該bit為0時元素值為-1， 該bit為1時表示元素值為1。相比較于全精度(float)， 參數的壓縮比例約為32倍。參數$\alpha$以及$A_b$的推導過程為：
對于矩陣量化的誤差為:
error = \left\lVert A - \alpha A_b \right\rVert ^ 2
最小化$error$可以得到：
\alpha = \sum abs(A_{ij}) / (m*n)
A_b = sign(A)
我們定義二值化的op為:
\alpha, A_b=binarize(A)
将binary network應用到GEMM中。
\alpha_A, A_b = binarize(A)
\alpha_B, B_b = binarize(B)
GEMM(A,B) \approx \alpha_A \alpha_B B\_GEMM(A_b, B_b)
$B\_GEMM$表示二值矩陣的乘法。是以問題轉化為二值矩陣的乘法。 針對二值矩陣的乘法高效計算可以采用XNOR+POPCNT算法(POPCNT統計值為1的bit數)。首先假設$A_b$中的每個元素已經通過bit存儲 ，那麼矩陣乘法可以表示為
C_{ij}=K-2POPCNT(XNOR(A_{i,}, B_{,j}))
在$binarize$ op中， 參數$\alpha = \sum(A_{ij})/ (m * n)$， 是整個矩陣元素絕對值的平均值。一個優化的方法可以考慮根據原始矩陣$A$的每行計算一個系數$\alpha$， 或者每行中每$X$個連續的元素計算一個$\alpha$。 當$X=1$時， 退化成沒有量化。選擇适當的$X$不會顯著增加計算量，但能提升模型的性能。為了計算友善， 一般$X$是64的倍數。
使用1個bit來表示一個參數還是會引入了較大的誤差。為了降低這些誤差， 可以引入multi-bit XNOR。通過每次增加一個bit，量化上次的殘差，可以降低最終的誤差。假如 矩陣A通過$x$個bit量化， 那麼
\alpha_{A1}, A_{b1} = binarize(A)
\alpha_{A2}, A_{b2} = binarize(A-\alpha_{A1}A_{b1})
\cdot\cdot\cdot
是以multi-bit量化可以定義為:
\left[\alpha_{A1},\cdots,\alpha_{Ax}\right],\left[A_{b1},\cdots,A_{bx}\right] = multi-bit(A, x)
基于multi-bit的MatMul可以表示為：($A$用$x$個bit量化， $B$用$y$個bit量化)
GEMM(A,B) \approx \sum_{i=1}^{x}\sum_{j=1}^{y}\alpha_{Ai}\alpha_{Bi}B\_GEMM(A_{bi}, B_{bj})
上面的多個bit方案， 隻能保證每增加一個bit的時候， 對目前的殘差的量化最優的，但是不能保證整個過程是一個最優或是次優的量化方案。通過傳統的數值方法不能得到最優解， 因為目标函數不是關于$\{\alpha_i\},\{A_{bi}\}$的凸函數。是以我們設計了一種交替疊代的量化方案：AQN: Alternating multi-bit Quantzation Network。考慮這樣一個事實，對于$ error = \left\| A - \sum_{i=1}^{n} \alpha_i A_{b_i} \right\|^2$, 當給定$\{W_{b_i}\}$， $\{\alpha_i\}$是有解析解的. 令
A_b^{\ast}=\left[vec(A_{b_1})^T, vec(A_{b_2})^T,...,vec(A_{b_n})^T\right]
其中vec為将矩陣展開成向量操作。矩陣$A_b^{\ast} $的shape為$mn \times M_A$。那麼可以得出
\left[\alpha_{A1}, ..., \alpha_{An}\right] = (({A^{\ast}_b}^T {A^{\ast}_b)}^{-1}{A_b^{\ast}}^T A)^T
。 同理， 當$\{\alpha_i\}$給定的時候， $\{A_{b_i}\}$有全局最優解。是以我們采用交替疊代的方法， 疊代求解的算法為:
inputs: matrix ${A}$, iteration times $n$
get $\{\alpha_i, A_{b_i}\}$ with multi-bit XNOR method
REPEAT
$\left[\alpha_{A1}, ..., \alpha_{An}\right] = (({A^{\ast}_b}^T {A^{\ast}_b)}^{-1}{A_b^{\ast}}^T A)^T$
$\{A_{bi}\} = \mathop{\arg\min}_{\{A_{bi}\}} \left\| {A - \sum_{i}^{m}{\alpha_{i} A_{bi}}}\right\|^2 $}
n = n-1
UNTIL{n>0}
return $\{\alpha_i\}, \{A_{b_i}\}$
我們在X86-64指令集上基于Caffe架構實作了AQN算法，包含訓練和Inference部分， 并且在spell-check這樣一個task上上線。基于Caffe架構的一個重要原因是該架構簡單， 代碼量不大。由于Caffe是一個基于C++的DL架構， 通過簡單的封裝可以部署線上上。
目前有幾個開源的BNN算法lib， 但他們對intel intrinsic的應用并不好，參考這些開源代碼，我們實作了AQN的training和inference子產品。training和inference是分開， 是因為training和inference在我們的場景中是不一樣的。 training部分我們采用單機GPU訓練， inference主要是在搜尋的QP上，基于Intel broadwell 架構的CPU。
在training的過程中， 主要是對Caffe中的InnerProductLayer的input和$W$分别做基于AQN的approximation，然後再調用GEMM計算矩陣乘法。bp的時候分别采用量化後的結果計算$W_q$以及向下傳的residual。其中一個重要的細節就是clip。把$W$ clip到一個$\left[-x, x\right]$區間相當于增加了正則， 通常$x=1$。
在approximation之後再做GEMM，會增加training的計算量， 但由于training主要是離線的， 是以這些overhead還是可以接受的。 我們在GPU上實作了AQN的training部分， 和原始的InnerProduct相比， training的時間沒有增加多少， 下面訓練過程中的forward和backward流程
目前有一些基于binary量化的$B\_GEMM$實作，參考這些實作，基于avx2指令集， 我們在caffe中實作的AQN的Inference代碼，
初始化的時候， 将$W$通過AQN 量化得到$\{\alpha_{i}\}$以及$\{W_{bi}\}$
forward的時候， 對input量化， 得到對應的量化結果, 利用$B\_GEMM$(XOR+POPCNT)計算二值矩陣的乘法
我們在搜尋的query糾錯、以及一些開源的資料集合上對比了由于量化帶來的模型精度影響， 以及對GEMM速度的提升。query糾錯是一個基于LSMT的深度學習模型。LSTM是其中計算最主要的計算單元，其中包含了大量的GEMM算子。我們對比了使用多bit的AQN後對模型精度的影響以及LSTM單元的加速情況：
在上面的實驗中， 在$input$和$W$各使用2個bit量化的時候， 模型的accuracy有部分下降， 但LSTM單元的加速可以提升3倍，這可以確定模型能線上部署。同時我們在一個已經train好的LSTM模型上使用AQN進行量化， 我們分析了量化後的模型和原始模型之間數值上的RMSE， 并和目前最新的方法做了對比
對上面的對比可以看出， 經過AQN量化後的模型， 在數值上和原模型最接近， 大幅降低了數值上的誤差。為了判斷量化最終對模型性能的影響， 我們在開源的資料集Peen Tree Bank (PTB)上，在training的過程中， 結合AQN進行訓練， 并最終和其他目前最新的方法對比了在測試資料集上的模型性能
在上面的實作對比中， AQN對模型性能影響最小，效果比其他對比的方法好。在有些時候甚至超過了全精度的模型， 因為量化的過程相當于引入了模型的正則， 降低了噪音資料對模型的影響。
對了驗證AQN的inference的計算性能，我們和Intel的科學計算庫MKL對比了一下矩陣乘法的latency。統計了在基于Intel的broadwell架構的CPU上， 采用單線程計算了在不同場景下的latency
上面是對M比較小的時候的結果， 因為在實際的場景中， 需要inference的資料隻有一條， 比如：使用者輸入的query等。在AQN實作的過程中， 我們發現目前的Intel CPU指令集對POPCNT支援的不是很好， 但後下一代的CPU體系架構中， 相關的指令集得到了優化。相信在後面的CPU體系中， 基于 binary量化的相關算法， 在Inference上的加速能更上一個台階。同時，很多研究将基于binary量化的模型應用到GPU，FPGA上， 也取得了非常不錯的效果。
我們還考察了基于ternary的算法。ternary的一個想法是， 矩陣
A \approx \alpha A_t
其中
A_t \in \{-1, 0, 1\}^{m \times n}
基于XOR和POPCNT的ternary, binary矩陣運算需要對ternary部分引入mask，這樣可以在保持模型性能的同時， 降低對POPCNT的使用。
Pete Warden. Why GEMM is at the heart of deep learning
Yu Cheng, Duo Wang, Pan Zhou and Tao Zhang. A Survey of
Model Compression and Acceleration for Deep Neural Networks
Mohammad Rastegari, Vicente Ordonez, Joseph Redmon and Ali Farhadi. XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks
Zefan Li, Bingbing Ni, Wenjun Zhang, Xiaokang Yang and Wen Gao. Performance Guaranteed Network Acceleration via High-Order Residual Quantization
Matthieu Courbariaux, Itay Hubara, Daniel Soudry, Ran El-Yaniv and Yoshua Bengio. Binarized Neural Networks: Training Deep Neural Networks with Weights and Activations Constrained to +1 or -1
Fengfu Li, Bo Zhang, Bin Liu. Ternary Weight Networks
Abhisek Kundu, Kunal Banerjee, Naveen Mellempudi, Dheevatsa Mudigere, Dipankar Das, Bharat Kaul, Pradeep Dubey. Ternary Residual Networks
Hande Alemdar, Vincent Leroy, Adrien Prost-Boucle, Frédéric Pétrot. Ternary Neural Networks for Resource-Efficient AI Applications
Naveen Mellempudi, Abhisek Kundu, Dheevatsa Mudigere, Dipankar Das, Bharat Kaul, Pradeep Dubey. Ternary Neural Networks with Fine-Grained Quantization
Yiwen Guo, Anbang Yao, Hao Zhao, Yurong Chen. Network Sketching: Exploiting Binary Structure in Deep CNNs
Haojin Yang, Martin Fritzsche, Christian Bartz, Christoph Meinel. BMXNet: An Open-Source Binary Neural Network Implementation Based on MXNet
<a href="https://en.wikipedia.org/wiki/AVX-512">https://en.wikipedia.org/wiki/AVX-512</a>
Eriko Nurvitadhi, David Sheffield, Jaewoong Sim, Asit Mishra, Ganesh Venkatesh and Debbie Marr Accelerator Architecture Lab, Intel Corporation. Accelerating Binarized Neural Networks:
Comparison of FPGA, CPU, GPU, and ASIC
Mitsuru Ambai, Takuya Matsumoto, Takayoshi Yamashita, Hironobu Fujiyoshi. Ternary Weight Decomposition and Binary Activation Encoding for Fast and Compact Neural Networks