1.4.2　如何實現無損壓縮

假設Alice需要把一個數據集（可能無限大）從遙遠的半人馬座星系傳輸給地球上的Bob，假設如下，圖1-15是傳輸編碼數據的示意圖。

● ，表示一個標記，詞表大小。

● Alice和Bob都有足夠的計算資源。

● 假設現在已經傳輸了，Alice會將下一個編碼為后傳輸給Bob。

● Alice希望最小化傳輸的數據量S，以比特數量來衡量。

先看一下基準傳輸方法。由于的可能性有256（詞表大小）種，所以可以表示為一個8比特的整數（1字節）。假如，編碼后用表示，這時需要傳輸的數據量為8比特（）。

圖1-15　傳輸編碼數據

另外，Alice要將上面的傳輸步驟寫成一份新的代碼，在傳輸數據之前給到Bob。這樣傳輸一個大小為n的數據集的代價可以表示為

　　（1-1）

接下來從信息論角度解釋一下基準的信息量。

基準方法對于的分布沒有先驗知識，因此其概率分布是一個離散均勻分布。此時信息量表示為

　　（1-2）

因此，可被看作信息量。

提示　信息論的創始人克勞德·艾爾伍德·香農（Claude Elwood Shannon）定義了信息量的概念，信息量被用來衡量一個離散隨機變量的不確定性。假設服從概率分布，且有一個詞匯表，那么的信息量就是用比特數來表示的，公式表示為

　　（1-3）

這意味著，一個“事物”的信息量取決于它出現的概率。

我們可以任意選擇一個詞匯表，比如二進制數據，它可以很容易地被分成8比特的字節。每字節有0～255，共256種可能的取值，所以需要用8比特來表示1字節。這里其實有一個隱含的假設：0～255每個取值出現的概率都是相等的，也就是滿足如下關系。

　　（1-4）

事實上，的最大值就是在是均勻分布時取到的。當是1字節時，比特。也就是說，如果不是均勻分布，那么可以用少于8比特的編碼來表示1字節。這就是各種“壓縮”算法的理論基礎。

在介紹了基準方法之后，接下來介紹基于神經網絡的無損壓縮方法。

假設我們想要利用一個自回歸神經網絡來實現壓縮，以如下場景為例。

Alice首先把一個自回歸神經網絡（如GPT）的訓練代碼發送給Bob。這個網絡的輸入是，輸出是下一個數據的概率分布。注意，網絡的“大小”是由決定的，但網絡的權重是由初始化并不斷訓練得到的。可以把網絡的參數看作的一個函數。圖1-16是概率分布的示意圖（縱坐標為概率，示意圖中的概率為參考示例，無實際意義）。

圖1-16　當前傳輸數據的概率分布

雖然網絡的權重是由Alice和Bob各自獨立地初始化和訓練的，但是由于他們使用相同的方法和隨機種子，導致他們的初始權重相同，并會隨著數據的傳輸而保持同步更新，因此是的函數。

假設Alice已經把發送給了Bob，現在她要把編碼成并發送給Bob。由于此時Alice和Bob根據相同的代碼和相同的數據訓練了相同的網絡，因此他們對的概率分布也有相同的預測。為簡便起見，便省略條件部分，直接寫作。

考慮使用算術編碼的二分查找法來把編碼成，假設取值為0、1、2、3的概率分別為0.2、0.25、0.22、0.175。如果要把編碼成，可以用以下區間查找的選擇來表示。每一次的區間選擇都有兩種可能的結果：左區間（向左）或右區間（向右）。

如果使用1表示向右，0表示向左，那么查找過程便可以表示為一個長度為3的動作序列。

● 。

● 剛好可以用一個3比特的二進制數字表示。

Alice將這個動作序列編碼為一個3比特的二進制數字，發送給Bob。

● 等價于二分查找的次數。

● 在這個例子里，。

Bob收到后，得到的過程如下所示。

（1）Bob也預測得到分布。

（2）根據代表的動作序列，復現二分查找的過程，得到0.687 5這個有限精度的實數。

（3）找到這個實數所在的區間是第4個區間，則Bob解碼。

這樣一來，Alice就將把按照Alice和Bob共同掌握的概率分布編碼成，并且把它無損地傳輸給Bob。Bob也可以按照同樣的概率分布把解碼為。這個過程比基準方法節省了很多傳輸的數據量。原本需要傳輸8比特，現在只需要傳輸3比特。圖1-17是整個過程的示意圖。

圖1-17　算術編碼的二分查找過程