向量量化

向量量化（英语：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年代，向量量化亦使用于语音辨识，近年亦有研究将之使用在签名识别及影像特征搜寻上。实际应用上，训练完成的编码簿之中，与被识别目标(如语音讯号等)有最小误差的码向量，其对应的索引即代表识别的目标(使用者)。