機器之心原創
作者：仵冀穎
編輯：Hao Wang
在網絡帶寬有限的年代，數據壓縮顯得尤為可貴。還記得美劇矽谷第一季裡面大殺四方的數據壓縮算法讓 pied piper 公司炙手可熱。高效的數據壓縮使得大型網絡應用能夠在移動端成為可能，其前景非常誘人。大數據時代的來臨，數據的體量和數據的增長速度都達到了一個前所未有的高度。隨著 5G 技術的快速發展，邊緣計算、物聯網、聯邦學習等應用需求及應用場景越來越多。在傳輸網絡和存儲能力有限的情況下，數據壓縮技術發揮了越來越重要的作用。在傳統數據壓縮算法不斷發展的同時，近年來深度學習網絡也應用於數據壓縮中獲得了很好的效果。
本文對數據壓縮的「前世今生」進行簡要的回顧，重點分析基於深度學習的有損壓縮、無損壓縮方法，對基於深度學習的數據壓縮進行了探討和展望。
1、數據壓縮背景知識
眾所周知，信息理論和機器學習之間具有很強的關聯性，人們經常把它們稱為「同一枚硬幣的兩面」。二者一個特別重要的聯繫體現在數據概率模型和數據壓縮方法之間的本質等價性。香農的信源編碼定理（Shannon-Fano Coding）可以看作是描述這一思想的基本定理，而哈夫曼編碼（Huffman Coding）、算術編碼（Arithmetic Coding）和最近發展起來的非對稱數字系統（Asymmetric Numeral Systems，ANS）等都是經典的基於統計模型實現數據壓縮的算法，即基於對信息中單個字符出現頻率的統計而設計的。除去以統計概率為基礎的方法外，經典的數據壓縮方法還包括基於字典模型的壓縮技術，例如 LZ77、LZ78、LZW 等，以及熵編碼 (Entropy Encoding)，遊程編碼 (Run-Length Encoding) 等。
我們在日常中經常用到的數據壓縮的工具基本都是上述幾種經典方法的變種、組合或優化，很少有單獨使用某一種技術。例如，gzip 的壓縮原理是：先使用 LZ77 算法的一個變種進行壓縮，對得到的結果再使用靜態或動態哈夫曼編碼的方法進行壓縮；bzip2 的壓縮原理為：使用了一個遊程編碼器進行編碼，接下來塊排序壓縮和 Move-to-Front(MTF ) 變換進一步產生大量相同符號，進一步使用另一個遊程編碼器進行編碼。最後結果用 Huffman 編碼，將一個消息頭與其打包；LZMA 是 Deflate 和 LZ77 算法改良和優化後的壓縮算法，而 Deflate 則是同時使用了 LZ77 算法與哈夫曼編碼的一個無損數據壓縮算法。但是，面對大數據時代的數據處理，傳統的數據壓縮方法顯得越來越力不從心，無法滿足大體量、快速增長和結構複雜等特徵的數據壓縮，尤其是實時數據壓縮的處理要求。
近年來，機器學習領域經歷了爆炸式的發展，一些研究人員使用傳統神經網絡模型在數據壓縮領域獲得了較好的效果。將原始圖像經由神經網絡處理後，僅需存儲神經網絡權重而無需存儲圖像本身的信息，從而在不降低圖像質量的情況下獲得了較高的壓縮比。以此為基礎，將神經網絡與其它壓縮技術結合、改進神經網絡結構、改進神經網絡的訓練算法等，進一步推進了神經網絡在數據壓縮中的應用。但是，神經網絡是淺層網絡，模型的收斂速度、穩定性、權值更新的有效性等都存在不足，此外，神經網絡依賴於有標籤的預訓練數據，這在實際應用場景中很難滿足。
2、基於深度學習的數據壓縮
深度學習的引入有效解決了傳統方法存在的問題。與傳統壓縮技術相比，基於深度學習的方法具有下列的天然優勢：
由於深度學習的參數是基於大量實際數據推導出來的，而傳統的數據壓縮編碼方法主要是基於先驗知識手工構建的，因此深度學習的優良內容自適應性優於基於信號處理的模型。深度學習的方法有效利用了較大的接受域 (Receptive Field)，因此不但能利用相鄰的信息還可以利用遠距離的樣本提高編碼效率，但傳統的編碼工具只利用相鄰的樣本，難以利用遠距離的樣本。基於深度學習的壓縮方法是靈活的，可以根據特定的域特徵進一步減少比特率，同時實現快速處理，深度學習的內部表示適合於現代數據處理。
與傳統神經網絡壓縮技術相比，基於深度學習的方法優勢在於：（1）基於多層網絡結構，深度學習模型具有較好的非線性映射能力，因此能有利於學習到數據（特別是圖像）的深層次特徵。（2）深度學習模型通過多層學習和權值微調的過程，提高了訓練速度，從而能滿足大體量數據壓縮的要求。（3）更深的學習層次能夠更加有效的去除掉冗餘數據特徵，從而獲得更高的壓縮比。
到目前為止，隨機神經網絡（Random Neural Network）、卷積神經網絡（Convolutional Neural Network，CNN）、遞歸神經網絡（Recurrent Neural Networks，RNN）、生成對抗網絡（Generative Adversarial Networks，GAN）、變分自動編碼器（(Variational) Auto-Encoder，VAE）等都陸續應用到了數據壓縮中。本文從近兩年重要學術會議的研究成果中選擇了基於 GAN 和 VAE 的兩種深度學習數據壓縮技術進行分析與討論。
1. GAN 在有損壓縮中的應用
論文標題：Deep generative models for distribution preserving lossy compression，NIPS2018
地址：https://arxiv.org/abs/1805.11057?context=stat
這篇文章提出了一種分布保持的有損壓縮系統（Distribution-Preserving Lossy Compression，DPLC）。該系統應用於圖像壓縮場景，在不同的壓縮比率下編碼器能夠生成與原始數據分布一致的編碼，其解碼器則以零比特率生成獨立同分布樣本，然後隨著比特率的增加逐漸產生包含更多原始圖像內容的重構，最終在足夠高的比特率情況下實現完美的重建。
對於隨機變量 X，令 P_X 表示 X 的分布，E_X[X] 表示期望。W~P_X 表示 W 遵從 P_X 的分布，X~Y 表示 X 和 Y 為同分布的。在標準的有損壓縮系統中，編碼器的任務是生成編碼 E: X→W，從而將原始輸入編碼為 R 比特的碼，解碼器的任務是將碼映射回原始空間 D: W→X，同時最小化某些失真度量 d:XxX，任務目標函數表示為：
在傳統壓縮方法中，E 和 D 具有典型確定性，因此不同的重構輸入的數量 X^：=D(E(x)) 由 2^R 限定，這就導致重建的 X^會出現降質的問題，例如引起圖像的模糊、模塊化等。為了解決這一問題，需要向目標函數中增加一個約束項，即「重構實例的分布遵循訓練數據的分布」：
增加這一約束項相當於學習了 R=0 時一般未知分布 P_X 的精確生成模型，考慮到生成模型，自然地我們就想到了引入 GAN。為了減少上式的鬆弛對平均值問題的偏差，將 D 分解為 D=G o B，其中 G 為生成模型（從固定的先驗分布 P_Z 中提取樣本作為輸入，訓練以最小化 P_G(Z) 和 P_X 之間的差異），B 為隨機函數（與原目標函數 E 一起訓練以最小化固定值 G 的失真）。瓦瑟斯坦距離（Wasserstein Distance）可以被定義為任意的運輸成本函數，因此適用於本文對於量化重建質量的失真度量 D。對於隨機變量 X 和 Y，Wasserstein 距離為：
其中 P(P_X，P_Y) 是 (X,Y) 的所有聯合分布的集合。令 (X,d』) 表示一個度量空間，我們設置 c(x,y)=d』(x,y) 時，通過 Kantorovich-Rubinstein 對偶得到:
其中 F1 是有界 1-Lipschitz 函數的一類 f:X->R。本文使用的生成模型 G 通過最小化 P_X 和 P_G(Z) 之間的 Wasserstein 距離來學習，學習的方法有兩種（i）通過 Wasserstein 自動編碼器（Wasserstein Autoencoder，WAE），其中 G o F 參數化 P_X 和 P_G(Z) 之間的耦合，或者（ii）通過 Wasserstein GAN（WGAN）。本文提出 Wasserstein++，將 WAE 和 WGAN 結合起來。將經過訓練的生成模型 G 與利用速率約束編碼器 E 和隨機函數 B 來實現本文提出的 DPLC 系統，從而在保證 P_X 和 P_X^在所有速率下都相似的同時，將 X 和 X^之間的失真減至最小。完整的 DPLC 見圖 1。
圖 1. DPLC 總體結構。
壓縮過程為了從原始數據中學習 G、B 和 E，將每個分量參數化為深度神經網絡，並通過隨機梯度下降（SGD）求解相應的優化問題。如前所述，G*可以通過 WGAN 或 WAE 學習。由於 WAE 框架自然的包含了一個編碼器，它能保證潛在空間 Z 的結構易於編碼，而使用 WGAN 則不具有這樣的特性。在本文的實驗中，我們觀察到使用 WAE 的圖像中邊緣的銳化程度弱於 WGAN。另一方面，由於 WAE 目標由於重建誤差項而嚴重懲罰了模式丟失，因此 WAE 比 WGAN 更不容易發生模式丟失。為了結合這兩種方法的優點，我們通過 Wd 的凸組合，提出了 Wd 的原形式和對偶形式的新的優化組合：
基於 G(Z) 或 G(F(X) 的偽樣本訓練 f，由於 F(X) 和 P_Z 之間的不匹配（在優化過程開始時更為明顯），這些樣本一般不會遵循相同的分布。因此需要做下面的調整：
基於 G(Z.~) 的樣本訓練 f，其中 Z.~=UZ+(1-U)F(X)，U~Uniform(0,1)。基於 F(X) 中的樣本訓練 G，計算 WGAN 和 WAE 的損失項。
本文在兩個標準的生成性建模基準圖像數據集上完成實驗，CelebA 和 LSUN 臥室，其中圖像都縮小到 64x64 解析度。圖 2 給出了不同方法的測試 MSE（越小越好）、重建 FID（越小越好）和條件像素方差 PV（越大越好）。CelebA 的結果顯示在最上面一行，LSUN 臥室的結果顯示在最下面一行。本文提出的 DPLC 模型的 PV 隨著速率的降低而穩定地增加，也就是說，它們生成的有效圖像內容逐漸多於 GC。
圖 2. 不同方法的實驗結果。
2. VAE 在無損壓縮中的應用：
論文標題：Bit-Swap: Recursive Bits-Back Coding for Lossless Compression with Hierarchical Latent Variables， ICML2019
地址：https://arxiv.org/abs/1905.06845
這篇文章探討了 Variational Auto-Encoding (VAE) 在壓縮技術中的應用，提出了一種 Bit-Swap 無損壓縮方法。根據經典的統計理論數據壓縮，任何數據分布都可以轉換成一種無損編碼，在這種編碼中，每個數據點都被編碼成一個與模型分配的負對數概率相等的比特數。當模型與真實的數據分布相匹配時，可以獲得最佳的預期碼長。因此，基於概率似然性設計的無損壓縮算法需要解決兩個問題：一是利用模型逼近真實數據分布，二是找到實用的壓縮算法滿足與此模型兼容的條件並保證碼長為-log p_θ(x)。本文引入 VAE，對原始概率分布進行多層分解，利用潛在變量模型計算原始數據的近似邊緣分布，與經典 ANS 壓縮技術相結合，實現快速的壓縮和解壓縮。
給定離散原始數據 x = (x1,..., xD)，其分布表示為 p_data，基於概率似然性設計的 ANS 無損壓縮機制為：使用概率 p_θ(x)，當其碼長滿足-log p_θ(x)=-log p_data(x) 時，得到的平均碼長 E[-log p_θ(x)] 接近數據 H(x) 的熵，即得到最優壓縮方案的平均碼長。ANS 使用一元概率分布或完全分解概率分布 p(x) 來編碼原始符號向量 x，從而產生-log p(x) 比特位。ANS 算法的狀態是具有堆棧結構的比特流：每次編碼符號時，其比特位都被推到堆棧的最右側；每次解碼符號時，比特位都從堆棧的最右側彈出。圖 3 給出 ANS 的工作機制。
圖 3. ANS 以類似堆棧的方式操作位流。
本文使用潛在變量模型計算原始數據 p_data(x) 的近似邊緣分布 p_θ(x)：
其中 z 為潛在變量。VAE 引入推理模型 q_θ(z|x) 來逼近模型後驗概率 p_θ(z|x)：
由於 D_KL>=0，通過聯合優化證據下限（Evidence Lower Bound，ELBO）和 log p_θ(x) 的下限，可以得到推理模型和生成模型如下：
編碼端的處理流程如下：
發送者發送一個使用先驗 p(z) 和 x 進行編碼得到的潛在樣本 z~q_θ(z|x)，使用 p_θ(x|z) 進行編碼；使用 q_θ(z|x) 從比特流中解碼得到 z，之後從比特流中減去-log q_θ(z|x) 長度的比特位；使用 p_θ(x|z) 對 x 進行編碼，向比特流中增加-log p_θ(x|z) 長度的比特位；使用 p(z) 對 x 進行編碼，向比特流中增加-log p_(z) 長度的比特位；最終得到了一個長度為 N_total:=N_init+log q_θ(z|x)-log p_θ(x|z)-log p_(z) 比特位的比特流，並發送給接收端。
接收端通過將 ANS 初始化為接收到的比特流來解碼數據，然後以相反的順序進行，並交換編碼和解碼操作。
當模型具有許多潛在變量時，在傳遞初始比特流 N_init 時就會帶來效率問題（這也是深度學習大量參數所帶來的問題）。為解決這一問題，本文使用層次潛在變量模型，即具有多個潛在變量且其採樣過程服從形式的馬爾可夫鏈的 VAE，如圖 4：
圖 4. 層次潛在變量模型。
此時近似邊緣分布 p_θ(x) 為：
為每個隱層 z_i 定義推理模型 q_θ(z_i|z_(i-1))，這樣可以基於變分界限計算邊緣概率 p_θ(x)，此時 ELBO 目標函數為：
在本文提出的 Bit-Swap 模型中，生成模型和推理模型的採樣過程都服從隨機變量之間的馬爾可夫鏈依賴關係。與標準 VAE 的處理類似，數據 x 是根據潛在變量 z_1 生成的。然而，z_1 不再是固定的先驗值，而是由第二個潛在變量 z_2 生成的。類似的，z_2 也不是固定先驗值，而是由第三個潛在變量 z_3 生成的，依此類推。這些嵌套依賴項使我們能夠遞歸地應用 bits back 參數。我們可以對第一個潛在變量應用 bits back 參數的前兩個步驟：首先解碼 z_1，然後直接編碼 x，這將向比特流中添加新的比特位，z_2,L 的進一步解碼操作將需要較少的初始比特來繼續。以類似的方式遞歸地應用第二個潛在變量 z_2 的 bits back 參數：首先解碼 z_2，然後編碼 z_1。Bit-Swap 所需的初始位的數量上限為：
本文提出的 Bit-Swap 數據壓縮算法完整的算法如下：
以三個隱藏層為例，Bit-Swap 的過程如圖 5 所示。
圖 5. Bit-Swap 過程示意。
本文在 ImageNet 的 32×32 像素隨機塊上訓練分層潛變量模型。為了測試，獨立於測試集拍攝了 100 幅圖像。100 幅圖像的壓縮比見表 1。這 100 幅圖像被裁剪成每邊 32 像素的倍數，這樣就可以用 32 個像素塊來擬合一個網格。網格被視為一個數據集，必須按順序處理才能被壓縮。作者在基線方案中使用相同的裁剪圖像，而不是先將圖像分成 32 x 32 像素的塊。
表 1. ImageNet 100 幅圖像的壓縮比（未縮放和裁剪）。
關於深度學習在數據壓縮中的應用，作者單獨建立了研究主頁，更新相關的研究成果並提供代碼、視頻下載等，感興趣的可以訪問 https://bair.berkeley.edu/blog/2019/09/19/bit-swap/。
3、基於深度學習的數據壓縮應用前景展望
由上文的分析和具體論文實例的結果可以看出，深度學習方法在處理數據壓縮問題時，不再像傳統方法一樣嘗試找到數據自身的統計特徵、數值特徵等，而是自動挖掘複雜結構的數據內在特徵。深度學習的數據挖掘和重構能力使得其能夠在保持數據特徵、保證編碼效果的同時獲得較高的壓縮比。
儘管應用效果很好，但深度學習方法還是存在自身局限性：
當數據量大、數據結構複雜時，深度學習的整體結構也會變得非常複雜，當進行較深層次的訓練時，模型所需要的時間會急速增長。由本文選擇的兩篇實例可以看到，作者在實驗中都將圖像進行了縮小處理，例如 32×32、64x64 大小的圖片，作者也在討論中提到，如果使用原始大小的圖片，計算時間和成本都會非常巨大；深度學習方法還是缺少對內在機理的分析，在不同的數據壓縮應用中還是以「黑盒」的方式使用，主要方法就是通過調整訓練層、參數等改進壓縮效果。
正如深度學習在其它機器學習場景中應用的情況，基於深度學習的數據壓縮獲得了讓人驚喜的效果，但仍然存在一些問題。不斷提升的視頻清晰度碼率，對低延遲網絡無比依賴的應用程式，以及一眾 VR 和 AR 設備的投入使用，在這樣的背景下，數據壓縮仍然是需要長期投入研究的領域。深度學習研究和在工業場景中的應用任重而道遠。
作者介紹：仵冀穎，工學博士，畢業於北京交通大學，曾分別於香港中文大學和香港科技大學擔任助理研究員和研究助理，現從事電子政務領域信息化新技術研究工作。主要研究方向為模式識別、計算機視覺，愛好科研，希望能保持學習、不斷進步。