向量量化

向量量化（英語：Vector quantization）是一個在訊號處理中的一個量化（離散化）方法。其為藉由樣本向量(prototype vector)的訓練來估算密度機率函數，並藉由此密度函數推估最有效的量化方案。此技術原用於資料壓縮，透過分割大數量的資料點(函數)，讓每個小群集都有相同的資料點，而這些小群集的所有資料就由其正中央的點作為代表，這點與k-平均演算法以及其他群集分析的特性相當。 向量量化所使用的密度分佈法的優勢在於，此種壓縮法對於高機率出現(密集)的資料誤差小，而對低機率(稀疏)的資料誤差大，故特別適用於大量且高維度的向量破壞性資料壓縮。 向量量化是競逐式學習的一種技巧，故與深度學習的自編碼器其中使用的自組織對應以及稀疏神經編碼有關係。

一維的例子

主條目：量化

向量量化其實就是找附近既定的點，來當作一個區間的代表，從而簡化資料量。參見下圖，在-1到1的數值都會近似為0，在1到3的數值都會近似為2，以此類推，這些數值都會以0, 2, 4, 6的整數表示出來，以二進位編碼可以用二位元表示之，從而壓縮了資料。然而，若是資料並非平均分散在-1到7之間，而是有疏密分佈，這樣的話把量化點取在0, 2, 4, 6便會造成誤差變大。為了要求失真達到最低，需要一個可以計算出使失真最小的少數代表向量(碼向量)，這組碼向量稱之為編碼簿(codebook)。

• 
  向量量化，一維的例子

定義

映射

為了要產生量化的編碼簿，需要以下是先定義及給定的資料：

1. 已知的向量源，作為訓練的樣本
2. 誤差測量方法，可以是方均根誤差等方法。
3. 編碼簿的大小，意即要把向量空間切分為幾個區域，量化為多少個值。

而計算的目的，就是為了尋找具有最小誤差的編碼簿，以二維的向量為例，如下圖，便是尋找那些紅色星星(編碼)與畫分空間的方法(藍色線段)。假設給定的向量樣本共有M個，每個的維度皆是k維，這些向量可以表示如下：$x_{m}={x_{(}m,1),\ \ x_{(}m,2),\ \ldots ,\ x_{(}m,k)\ },\ m=1,\ 2,\ \ldots ,\ M$

而要對應過去的目標向量，也就是編碼簿，假定編碼簿大小為N，也就是將劃分為N個區塊，同樣可以表示如下：

$y_{n}=\left\{y_{n,1},\ \ y_{n,2},\ \ldots ,\ y_{n,k}\right\},\ n=1,\ 2,\ \ldots ,\ N$

每個編碼簿裡的碼向量$y_{n}$都有一個對應的區塊$S_{n}$, 只要$x_{m}$落在$S_{n}$區塊內，就會透過向量量化對應到$y_{n}$。整個空間以$S$表示，$S_{i}$表示分割的子空間，對應函數為$Q$，這樣的映射表示如下：

$S=\left\{S_{1},\ S_{2},\ldots ,\ S_{n}\right\}$

$Q\left(x_{m}\right)=y_{n}\ \ \ \ if\ x_{m}\in S_{n}$

誤差計算

經過映射後產生的$y_{n}$與原本的$x_{m}$之間存在一個非負值的誤差，計為$d(x_{m},y_{n})$，這個誤差便是前述的誤差測量方法算出來的值。將所有d的加總寫為$D$，為求表示簡便，這裡使用最常見且最廣用的平方誤差做為範例：

$\textstyle D=\sum _{m=1}^{M}\|x_{m}-Q(x_{m})\|^{2}\displaystyle$
當然誤差的計算可以隨時更換，如增加權重、使用其他範數(norm)等等。這些誤差測量的方法的共通點為，他們的計算都是從誤差向量$x_{m}-Q(x_{m})$出發的，故這些誤差均可表示成此誤差向量的函數。而更複雜的誤差計算方法同樣的在其他資料壓縮領域有被使用，例如語音訊號處理等。
經過以上的步驟，向量量化的問題可以寫為：

給定向量樣本及編碼簿大小，找到使平均誤差最小的編碼簿及空間劃分。

演算法訓練

上述使誤差最小的映射函數，意即編碼簿，需要透過樣本向量的訓練最佳化。基本的步驟如下：

1. 隨機選一個樣本點P
2. 將最靠近的量化向量質心朝向該樣本點移動一小距離
3. 回到步驟一

為了確保所有在編碼簿裡面的量化向量都使用到，可以增設一個敏感度參數，訓練步驟如下：

1. 將每一量化向量質心$c_{i}$敏感度$s_{i}$增加相同的量
2. 隨機選擇一個樣本點$P$
3. 令選取之樣本點與各個量化向量質心的歐氏距離為$d(P,c_{i})$
4. 尋找能使距離減敏感度$d(P,c_{i})-s_{i}$為最小的量化向量$c_{i}$
5. 將該質心$c_{i}$朝向$P$移動一小段距離
6. 將該質心之敏感度$s_{i}$設為0
7. 回到步驟一

上述的步驟需搭配疊代門檻使解答收斂，如模擬退火法。

LBG演算法

實際上的向量量化演算法首先在1980由Y. Linde, A. Buzo, R. M. Gray 三位學者提出的，現在被稱為LBG演算法。此演算法與k-means演算法雷同，內容為不斷調整映射範圍及量化向量位置，使誤差趨近於區域最小值。其疊代步驟如下：

1. 給定訓練樣本以及誤差閾值
2. 訂定初始碼向量
3. 將疊代計數器歸零
4. 計算總誤差值，若不為第一次，則檢查與前一次誤差值差距是否小於閾值。
5. 根據每一個訓練樣本與碼向量的距離d，找其最小值，定義為映射函數Q
6. 更新碼向量：將對應到同一個碼向量的全數訓練樣本做平均以更新碼向量。

$c_{n}^{i+1}={\frac {\sum _{Q\left(x_{m}\right)=c_{n}^{i}}x_{m}}{\sum _{Q\left(x_{m}\right)=c_{n}^{i}}1}}$

1. 疊代計數器加一
2. 回到步驟四，重複至誤差小於閾值。

LBG演算法十分依賴起始編碼簿，產生起始編碼簿的方法有以下幾種：

亂碼

隨機挑選要求數量的碼向量作為起始編碼簿

分裂法

1. 先算出所有樣本向量的重心(平均值)
2. 將目前的重心分裂成二倍個向量，並前後挪動一點距離使其分隔
3. 將新的向量作為叢聚的分類準則，重新分出二群樣本向量
4. 再次將樣本的分群中心算出
5. 回到步驟二，直至有足夠數量個碼向量。

最近相臨集結法

1. 先將樣本向量中每一個向量視為一個叢聚
2. 計算每個叢聚之間距離，取最小距離的二個叢聚合併之
3. 重複步驟二直至叢聚數量等於要求的編碼簿大小。

優點

向量量化常使用在有損資料壓縮，這個方法可以將多為度的向量空間壓縮至有限的離散子空間，向量維度同時被降低(僅需索引)，減少儲存空間，因而壓縮了資料。因為此方法會隨著資料密度分佈的變化影響權重，其壓縮的失真比例會隨著資料密度成反比。其具有簡單的解碼方式，僅須透過索引進行查表(Table lookup)即完成解碼。壓縮程度亦高，有較低的位元率。

缺點

編碼簿設計與壓縮需要耗費較多的時間，多數花費在尋找最近的碼向量以及計算向量距離；且壓縮後的影像品質與編碼本的好壞關聯度大，針對擁有不同統計特性的訊號，往往需要設計不同的編碼簿，才能夠實際使用上。

圖形辨識應用

在80年代，向量量化亦使用於語音辨識，近年亦有研究將之使用在簽名識別及影像特徵搜尋上。實際應用上，訓練完成的編碼簿之中，與被識別目標(如語音訊號等)有最小誤差的碼向量，其對應的索引即代表識別的目標(使用者)。