說(shuō)明

介紹$1?bit$論文內(nèi)容。
原文鏈接：1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs | Semantic Scholar

ABS

實(shí)驗(yàn)證明在分布式機(jī)器學(xué)習(xí)的過(guò)程中能夠通過(guò)將同步所傳遞的梯度進(jìn)行量化（從$32$位到$1$位），同時(shí)加上量化容錯(cuò)機(jī)制能夠很好的加快整個(gè)訓(xùn)練過(guò)程。最值得注意的時(shí)，模型的收斂情況并沒(méi)有收到影響。

本文將該發(fā)現(xiàn)與$SGD,AdaGrad$, 自動(dòng)批量選擇, 雙緩沖區(qū),模型并行技術(shù)相結(jié)合設(shè)計(jì)了。意料之外的是，量化甚至能讓精度有一個(gè)很小的提升。

不同的模型在使用該方法后加速效果明顯。

1 Introduction and Related Work

現(xiàn)在上下文相關(guān)的深度神經(jīng)網(wǎng)絡(luò)模型基本都是通過(guò)反向傳播進(jìn)行訓(xùn)練（常用的例如$SGD$），而上述的模型的訓(xùn)練是非常耗時(shí)的。

注：上下文相關(guān)的神經(jīng)網(wǎng)絡(luò)應(yīng)該是指類似與解決翻譯問(wèn)題所用的模型。

使用分布式訓(xùn)練上述的模型已經(jīng)取得了一定成功。（這里介紹了一部分相關(guān)工作，這里不進(jìn)行贅述）

在分布式訓(xùn)練中，一個(gè)非常重要的問(wèn)題就是帶寬瓶頸的問(wèn)題：即各個(gè)節(jié)點(diǎn)訓(xùn)練一定時(shí)間之后需要進(jìn)行數(shù)據(jù)的發(fā)送（這不管是模型并行還是數(shù)據(jù)并行都會(huì)發(fā)生），而這個(gè)過(guò)程交換的數(shù)據(jù)量往往取決于模型的大小，而現(xiàn)在使用的模型一般都比較大，所以網(wǎng)絡(luò)的帶寬成為了分布式機(jī)器學(xué)習(xí)的一個(gè)瓶頸。

緩解這個(gè)方法一般有兩類方法：

1. 增加批量大小，這樣每輪會(huì)進(jìn)行的計(jì)算會(huì)增加，而參與通信的時(shí)間會(huì)相對(duì)減少；
2. 減少每一次通信的數(shù)據(jù)交換量。

本文提出的方法屬于第二種，同時(shí)本文更多關(guān)注的是將量化方法應(yīng)用于數(shù)據(jù)并行的分布式訓(xùn)練中。

2 Data-Parallel Deterministically Distributed SGD Training

通常采用$BP$進(jìn)行模型的訓(xùn)練，過(guò)程可以被概述為下列的兩個(gè)方程：
KaTeX parse error: Undefined control sequence: \part at position 114: …^{t+N-1}\frac {\?p?a?r?t? ?F_{\lambda}(o(\…
上述過(guò)程對(duì)應(yīng)反向傳播求導(dǎo)和梯度下降進(jìn)行更新。

2.1 Data-Parallel Distributed SGD

上述的方程可以進(jìn)行分布式計(jì)算，只需要將方程$(2)$的梯度計(jì)算部分按照節(jié)點(diǎn)的個(gè)數(shù)，讓每個(gè)處理一部分?jǐn)?shù)據(jù)，然后進(jìn)行梯度的計(jì)算，計(jì)算完成后，相加即可得到某個(gè)時(shí)刻的梯度。

$perfectoverlap$：選取合適的工作節(jié)點(diǎn)個(gè)數(shù)能夠讓計(jì)算和數(shù)據(jù)交換進(jìn)行最優(yōu)的并行化，也就是通信資源和計(jì)算資源同時(shí)飽和。
$$T_{calc}(\hat{K})=T_{comm}(\hat{K})$$
也就是選取$K$讓每輪的通信時(shí)間和計(jì)算時(shí)間相等，這樣當(dāng)通信完成是下一輪的計(jì)算也完成可以繼續(xù)進(jìn)行通信。

計(jì)算時(shí)間可以被分解成固定的計(jì)算時(shí)間和可變的計(jì)算時(shí)間兩部分。固定的計(jì)算時(shí)間一般是完成一些必要的操作時(shí)間所花費(fèi)的時(shí)間，而可變計(jì)算時(shí)間往往會(huì)根據(jù)模型的大小，批量大小發(fā)生改變。

$Figure1$展示了當(dāng)節(jié)點(diǎn)個(gè)數(shù)下降到通信時(shí)間與計(jì)算時(shí)間相等時(shí)獲得的加速。

$\hat{K}$可以通過(guò)如下公式進(jìn)行計(jì)算：
$$\hat{K}=\frac{N/2?T_{calc}^{frm}+C?T_{calc}^{post}}{\frac{1}{Z}{T}_{comm}^{float}?T_{calc}^{upd}}$$
各參數(shù)的含義：（設(shè)模型的大小為$M$）

• $N$：批量的大小。
• $T_{calc}^{frm}$：計(jì)算梯度所花費(fèi)的時(shí)間，大約為$\frac{M}{FLOPS}$。
• $C$：一個(gè)常量，使用特殊方法處理所攜帶的常數(shù)。
• $T_{calc}^{post}$：后續(xù)進(jìn)行處理所需要的時(shí)間，例如使用$AdaGrad,momentum$需要花費(fèi)的額外時(shí)間（需要和$C$相乘才能獲取實(shí)際時(shí)間），大約為$\frac{M}{r}$，$r$為內(nèi)存的帶寬。
• $Z$：數(shù)據(jù)傳輸之前的壓縮率，在本文中將$32$位壓縮成$1$位，那么$Z=32$。
• $T_{comm}^{float}$：不壓縮梯度進(jìn)行通信所需要花費(fèi)的時(shí)間，大約為$\frac{M}{b}$，$b$為兩個(gè)結(jié)點(diǎn)之間的網(wǎng)絡(luò)帶寬。
• $T_{calc}^{upd}$：參數(shù)服務(wù)器將受到的梯度用于更新所需要的時(shí)間，大約為$\frac{M}{r}$。

上面的公式的理解：

分母是實(shí)際進(jìn)行通信的時(shí)間，分子計(jì)算所有$N$個(gè)數(shù)據(jù)會(huì)花費(fèi)的時(shí)間，而前面的推斷需要讓每個(gè)結(jié)點(diǎn)的計(jì)算時(shí)間和通信時(shí)間相等，由于在分布式機(jī)器學(xué)習(xí)中每個(gè)結(jié)點(diǎn)擁有的數(shù)據(jù)量是相同的，所以分子的計(jì)算時(shí)間除以$K$就是每個(gè)結(jié)點(diǎn)的計(jì)算時(shí)間，讓兩者相等并將$K$移到方程的一邊即可得到上面的公式。上面計(jì)算時(shí)間的計(jì)算出現(xiàn)了一個(gè)除以$2$，這在下一小節(jié)會(huì)解釋。

2.2 Double Buffering with Half Batches

上一節(jié)的公式里面出現(xiàn)了除以$2$是因?yàn)槭褂昧穗p緩沖區(qū)。整個(gè)過(guò)程將每一個(gè)批量會(huì)分成大小相等的兩部分放入緩沖區(qū)中，當(dāng)前一部分計(jì)算完成后，開(kāi)始計(jì)算后一部分，這個(gè)時(shí)候前一部分即可進(jìn)行通信，當(dāng)后一部分計(jì)算完成的時(shí)候，即可進(jìn)行通信，此時(shí)又可以從緩沖區(qū)讀取下一個(gè)批量的前一部分，所以每次實(shí)際上只計(jì)算了整個(gè)批量的一半，所以上面會(huì)出現(xiàn)除以$2$。

2.3 Potential Faster-Than-Fixed-Cost Communication

當(dāng)通信時(shí)間降到固定計(jì)算時(shí)間之下時(shí)，那么此時(shí)上面的計(jì)算公式將不再適用。此時(shí)整個(gè)系統(tǒng)的限制在于固定的計(jì)算時(shí)間，通信很難飽和。此時(shí)在使用雙緩沖區(qū)就沒(méi)有什么意義了，因?yàn)榇藭r(shí)的通信帶寬是足夠的，而雙緩沖區(qū)是為了緩解通信的壓力。

2.4 Relation to Hogwild/ASGD

異步更新能夠增加并行度，但是并沒(méi)有改變基礎(chǔ)性的東西。

3 1-Bit SGD with Error Feedback

將需要交換的數(shù)據(jù)進(jìn)行壓縮，將其壓縮為一位的數(shù)據(jù)，這樣能夠減少數(shù)據(jù)的交換量，從而減少通信的瓶頸。

不過(guò)如果只是簡(jiǎn)單的將數(shù)據(jù)壓縮成一位，然后任由$SGD$進(jìn)行缺失數(shù)據(jù)的修正，那么這是很容易導(dǎo)致模型發(fā)散的。

為了防止模型的發(fā)散提出了錯(cuò)誤反饋機(jī)制，該機(jī)制并不會(huì)將丟失的精度給丟棄掉，而是會(huì)對(duì)其進(jìn)行記錄下一次更新的時(shí)候需要同時(shí)考慮之前丟失的精度。

整個(gè)過(guò)程可以用下面的公式來(lái)表述：
$$\begin{array}{rl}& G^{quant}(t)=Q(G(t)+\Delta (t?N))\\ & \Delta (t)=G(t)?Q^{?1}(G^{quant}(t))\end{array}$$
參數(shù)說(shuō)明：

• $G$：本輪計(jì)算出來(lái)的梯度。
• $Q$：量化函數(shù)，具體的，如果輸入大于$0$，則量化成$1$，輸出小于$0$，則量化成$0$，這樣就可以將原本需要用$32$位表示的梯度只用$1$位進(jìn)行表示。
• $G^{quant}$：量化后的梯度。
• $Q^{?1}$：反量化函數(shù)，輸入只能是$0$或者$1$，當(dāng)輸入是$1$的時(shí)候輸出是$1$，當(dāng)輸入是$0$的時(shí)候，輸出是$?1$。
• $\Delta$：梯度誤差。

上述的過(guò)程就是壓縮之后會(huì)記錄壓縮誤差，壓縮誤差在下一輪的時(shí)候繼續(xù)參與壓縮。

3.1 Aggregating the Gradients

本文使用的聚合算法的復(fù)雜度關(guān)于結(jié)點(diǎn)個(gè)數(shù)是$O(1)$（這里的描述有一點(diǎn)奇怪，但是大概的意思就是每個(gè)結(jié)點(diǎn)聚合的數(shù)據(jù)量為所有梯度的一部分）。

具體的過(guò)程如下：

• 如果有$K$個(gè)結(jié)點(diǎn)，那么每個(gè)結(jié)點(diǎn)會(huì)處理$\frac{1}{K}$的梯度。
• 每個(gè)結(jié)點(diǎn)會(huì)從其他的$K?1$個(gè)結(jié)點(diǎn)接收屬于自己處理的梯度部分。
• 收到后結(jié)點(diǎn)聚合自己負(fù)責(zé)的這一部分梯度。
• 聚合完成后分發(fā)給其他所有結(jié)點(diǎn)。

4 System Description

根據(jù)最佳節(jié)點(diǎn)個(gè)數(shù)的計(jì)算公式，至少存在三種方法能夠提升并行度：（也就是通過(guò)改變變量讓公式的結(jié)果變大）

1. 提升$N$：增加每輪處理的批量個(gè)數(shù)。
2. 增加$Z$：增加壓縮度。
3. 減少固定計(jì)算時(shí)間（固定計(jì)算時(shí)間減少意味著相同的計(jì)算時(shí)間中有更多的時(shí)間用于了梯度的計(jì)算）

本文的壓縮算法屬于第二種方法。

對(duì)于方法一本文的實(shí)驗(yàn)發(fā)現(xiàn)$N$的增加是有一個(gè)限制的，當(dāng)增大的太多時(shí)，整個(gè)模型可能會(huì)發(fā)散。同時(shí)本文發(fā)現(xiàn)一個(gè)成熟的模型能夠處理的$N$的值要大一些。

為了防止模型發(fā)散的情況，本文后面的實(shí)驗(yàn)會(huì)隔一定的時(shí)間增大$N$而不是一開(kāi)始就將$N$設(shè)置的很大，這樣能夠防止模型發(fā)散或是準(zhǔn)確率下降嚴(yán)重。

除了這些之外，學(xué)習(xí)率也是采用遞減的方式。

最后使用了$AdaGrad$進(jìn)行優(yōu)化，這樣模型會(huì)收斂的更快，同時(shí)這也使得批量大小能夠進(jìn)一步的增加。

本文的系統(tǒng)可以在三個(gè)不同的地方使用$AdaGrad$：

• 在本地梯度量化之前；（可能會(huì)導(dǎo)致不一致性，但是可能對(duì)量化有益）
• 聚合結(jié)束后的數(shù)據(jù)交換期間；（可能會(huì)與量化沖突）
• 使用動(dòng)量平滑后；（可以減少內(nèi)存的使用和固定計(jì)算時(shí)間但是效果不好，因?yàn)榉逯当粍?dòng)量磨平了）

作者發(fā)現(xiàn)$AdaGrad$在量化后動(dòng)量平滑前使用效果最好。

為了也利用方法$3$，本文在使用數(shù)據(jù)并行的同時(shí)，在多$GPU$上做了模型并行。

5 Experimental Results

實(shí)驗(yàn)的細(xì)節(jié)可以在原文中找到。
論文的實(shí)驗(yàn)做的都是語(yǔ)音識(shí)別相關(guān)的，所以并沒(méi)有證明所有方面都適合該方法。

5.1 Cost Measurements

這一部分主要測(cè)量幾個(gè)耗時(shí)。

$T_{comm}^{float}$大約為$3?10ms$$。

$T_{calc}^{post}+T_{calc}^{upd}=18.2ms$。

$T_{calc}^{upd}\approx 9$。

$Table1$給出了$T_{calc}^{frm}$與批量大小的關(guān)系。

5.2 Effect of 1-Bit Quantization

$Table2$展示了不同的模式下的三種方式的對(duì)比，可以看出$1?bit$的效果并沒(méi)有受到太大的影響。

5.3 When to do AdaGrad?

$Table3$展示了在不同環(huán)節(jié)使用$AdaGrad$進(jìn)行優(yōu)化對(duì)于準(zhǔn)確率的影響，可以看出應(yīng)該在動(dòng)量平衡之前使用錯(cuò)誤率會(huì)更低，作者指出這可能是因?yàn)閯?dòng)量平滑減少了梯度的標(biāo)準(zhǔn)差從而導(dǎo)致$AdaGrad$的效果不好。

$partialgradients$代表量化前各個(gè)結(jié)點(diǎn)自身的梯度，$aggregategradient$代表量化后聚合的梯度。

5.4 Impact of MB-Size Selection and Double Buffering

這一部分講的是選取特別大的批量的時(shí)間耗時(shí)。從$Table3$中每一欄花費(fèi)的時(shí)間可以得到一些信息。

第二行的時(shí)間比第一行小主要是因?yàn)?#xff1a;第一行的實(shí)驗(yàn)選取了較大的批量大小。

第四行增加到了四個(gè)結(jié)點(diǎn)進(jìn)行數(shù)據(jù)進(jìn)行，同時(shí)每個(gè)結(jié)點(diǎn)進(jìn)行兩個(gè)$GPU$的模型并行導(dǎo)致整個(gè)的時(shí)間下降到$8.1h$.

第五行相比于第四行的下降則是因?yàn)榈谒男械膶?shí)驗(yàn)每$24h$選擇一次新的批量大小，而第五行每$72h$選擇一次。

第六行與第五行對(duì)比可以發(fā)現(xiàn)在這種情況下并沒(méi)有進(jìn)一步帶來(lái)速度的提升，不過(guò)當(dāng)使用雙重緩沖區(qū)了之后自動(dòng)選擇的批量大小將會(huì)有所下降。

第七行代表的是什么意思本人并沒(méi)有看懂。

$Table4$展示了固定不同的批量大小下雙重緩沖對(duì)于速度的影響。

5.5 Combination with Model Parallelism

下圖展示了不同的數(shù)據(jù)并行與模型并行的速率，可以發(fā)現(xiàn)在顯卡數(shù)量相同的情況下，只有$8\times 2$的時(shí)候模型并行提升了速率，在大多數(shù)情況下模型并并沒(méi)有提升速率，這代表著在大多數(shù)情況下模型并行沒(méi)有數(shù)據(jù)并行高效，這是因?yàn)槿绻褂媚Ｐ筒⑿袆t不能很好的利用緩存機(jī)制，模型并行的時(shí)候，每交換一次數(shù)據(jù)緩沖就會(huì)失效，而如果是更多的使用數(shù)據(jù)并行，那么就會(huì)減少一定緩存失效的次數(shù)。

5.6 Training a Production-Scale Model

表格中的$realign$代表將數(shù)據(jù)進(jìn)行對(duì)齊。

6 Conclusion

將通信傳播的通信量從$32$位降為$1$位，同時(shí)提出誤差反饋機(jī)制保證模型的收斂。

一位的量化能夠大大降低通信量從而減少通信所帶來(lái)的瓶頸。