查看“︁向量量化”︁的源代码


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

== 一維的例子 ==
{{main|量化}}向量量化其實就是找附近既定的點，來當作一個區間的代表，從而簡化資料量。參見下圖，在-1到1的數值都會近似為0，在1到3的數值都會近似為2，以此類推，這些數值都會以0, 2, 4, 6的整數表示出來，以二進位編碼可以用二位元表示之，從而[[資料壓縮|壓縮]]了資料。然而，若是資料並非平均分散在-1到7之間，而是有疏密分佈，這樣的話把量化點取在0, 2, 4, 6便會造成誤差變大。為了要求[[誤差|失真]]達到最低，需要一個可以計算出使失真最小的少數代表向量(碼向量)，這組碼向量稱之為編碼簿(codebook)。
<gallery mode="nolines" widths="213" heights="59">
File:Vector Quantization 1d.png|alt=一維的例子|向量量化，一維的例子
</gallery>
== 定義 ==

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

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

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

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

<math> y_n=\left\{y_{n,1},\ \ y_{n,2},\ \ldots,\ y_{n,k}\right\},\ n=1,\ 2,\ \ldots,\ N </math>

每個編碼簿裡的碼向量<math>y_n</math>都有一個對應的區塊<math>S_n</math>, 只要<math>x_m</math>落在<math>S_n</math>區塊內，就會透過向量量化對應到<math>y_n</math>。整個空間以<math>S</math>表示，<math>S_i</math>表示分割的子空間，對應函數為<math>Q</math>，這樣的映射表示如下：

<math> S=\left\{S_1,\ S_2,\ldots,\ S_n\right\}</math>

<math> Q\left(x_m\right)=y_n\ \ \ \ if\ x_m\in S_n </math>

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

<math> \textstyle D=\sum_{m=1}^M  \|x_m-Q(x_m )\|^2\displaystyle </math> <br />當然誤差的計算可以隨時更換，如增加權重、使用其他[[範數]](norm)等等。這些誤差測量的方法的共通點為，他們的計算都是從誤差向量<math> x_m-Q(x_m ) </math>出發的，故這些誤差均可表示成此誤差向量的函數。而更複雜的誤差計算方法同樣的在其他資料壓縮領域有被使用，例如語音訊號處理等。<br />經過以上的步驟，向量量化的問題可以寫為：<blockquote>給定向量樣本及編碼簿大小，找到使平均誤差最小的編碼簿及空間劃分。</blockquote>

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

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

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

# 將每一量化向量質心<math>c_{i}</math>敏感度<math>s_i</math>增加相同的量
# 隨機選擇一個樣本點<math>P</math>
# 令選取之樣本點與各個量化向量質心的歐氏距離為<math>d(P, c_i)</math>
# 尋找能使距離減敏感度<math>d(P, c_i)-s_i</math>為最小的量化向量<math>c_{i}</math>
# 將該質心<math>c_{i}</math>朝向<math>P</math>移動一小段距離
# 將該質心之敏感度<math>s_i</math>設為0
# 回到步驟一

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

=== LBG演算法 ===
實際上的向量量化演算法首先在1980由Y. Linde, A. Buzo,  R. M. Gray 三位學者提出的<ref>{{Cite journal|title=An Algorithm for Vector Quantizer Design|url=https://ieeexplore.ieee.org/document/1094577/|last=Linde|first=Y.|last2=Buzo|first2=A.|date=1980-1|journal=IEEE Transactions on Communications|issue=1|doi=10.1109/TCOM.1980.1094577|volume=28|pages=84–95|issn=0090-6778|last3=Gray|first3=R.|access-date=2021-01-15|archive-date=2020-10-20|archive-url=https://web.archive.org/web/20201020192624/https://ieeexplore.ieee.org/document/1094577/|dead-url=no}}</ref>，現在被稱為LBG演算法。此演算法與[[k-means]]演算法雷同，內容為不斷調整映射範圍及量化向量位置，使誤差趨近於區域最小值。其疊代步驟如下：

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

<math>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}</math>
# 疊代計數器加一
# 回到步驟四，重複至誤差小於閾值。


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

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

==== 分裂法 ====

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

==== 最近相臨集結法 ====

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

<br />

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

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

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



<br />
[[Category:有损压缩算法]]