本文: [转寄][转贴][删除][修改][回复][作者:dragondevil][人气:217]
发信人: dragondevil(流星※苍龙出海), 信区: Algorithm
标  题: Vector Quantization介绍
发信站: 瀚海星云 (2008年12月04日00:55:52 星期四), 站内信件 WWWPOST

前几天有人问，所以抽时间随便写点。

在高维信息（有损）压缩中，较常用的一个方法是VQ，矢量量化。
所谓VQ，和SQ，Scalar Quantization相对。

为此先讲下非一致量化的一般准则：平均量化误差绝对值最小化。
这是假定量化噪声为白噪的前提下，使矩即稳态噪声能量最小化的等价条件。
当量化噪声谱非白，则此准则失效。这种情形这里且略过。
对一维量，假若确定了量化点，则任一输入对应到量化点，应取距离范数最小者。
对有限个量化点，应在被量化变量分布密度函数大的区间密而在密度小的区间稀疏。
以上两点易证。

以二维情形为例，如果两个维度的坐标分布无关，则各自进行SQ。
如果两个维度分布有关，例如总分布在x1=x2附近，则采用VQ，使量化点分布在x1=x2附
近，避免在远离该直线的区间放置量化点，以达到量化点数最小化同时量化误差最小化
（请重复第二段中的定义）。
这符合量化的一般原理：在被量化变量分布密度大的区间密并在密度小的区间稀疏。
这个区间是二维及以上空间的子集时，称为VQ；
该区间指一维空间子集时，称为非一致SQ。

现在有了VQ的第一个要点：被量化向量的分布密度函数。
通常很难得到这个函数的连续代数表述，往往以统计集直接表示。
于是对统计集遍历性和分布可靠性需进行分析。

然后是VQ的第二个要点：从分布密度函数到量化点集。
量化的目的是为了降低数据率，在二进制系统下，量化点集的势总为2^k。
分布密集的地方量化点密集，分布稀疏的地方量化点稀疏。
这仍然基于量化噪声为白噪的假设，这并不总是成立，所以以上命题并不总是成立。

最后是VQ的第三个要点：从一个输入到量化点，即量化编码过程。
在空间所定义的距离范数下，离输入最近那个量化点的序号，就是输出。
解码过程，就是把序号通过查表对应到量化点坐标。

现在总合起来，看看有些什么研究点：
1、训练集遍历性和分布可靠性

这是基于VQ所应用的领域的特性的研究，在此略过。

2、最优VQ的生成

经典的方法，是空间分裂的迭代法：先求全空间的重心，作为量化点；再求投影方差最
大的方向，使量化点在这个方向上分裂为两个点，这两个点连线的垂平面分割空间；对
每个点对应的空间部分，先移动该点到其重心；求投影方差最大的方向，再次分裂。

该迭代很复杂，基于训练集，和被量化量分布连续假设。迭代中，当量化点移动，则空
间分割变化，量化点再次移动到变化后的空间分割的重心，就需要一次收敛，不妨称为
内迭代。点分裂若在内迭代途中加进来，简直可以使这个迭代不可控。

实际上只有钟型连续分布，该迭代在有限步才能得到一个较优解，并在无限步有可能得
到最优解。在一般不太理想的分布下，无限步收敛到最优解是不可能的。有限步解的优
解性更是值得怀疑。

主要的研究，是怎么配置好这个迭代。例如处理好分裂点选择，分裂时机、方向，分裂
数，分裂和内迭代的关系。要想一劳永逸解决这个问题几乎是不可能的，慑于庞大的训
练集带来的复杂度和获得并描述高维分布函数的困难性。

个人觉得要解决好这个问题，还是应该从高维分布函数入手。毕竟这是一个局部化的问
题，获得一个较优解，完全可以先武断的指定分布函数的不同部分（假若他们可以明显
的分开的化）各自分配多少个量化点名额。最终解的优化使得初始边界被改变毕竟是远
小于初始分割尺度的。代数解法提供了更快的“收敛”性，这避免了交互影响的迭代中
最重要也是最困难的收敛控制问题。

另一个角度，VQ的有用性，基于分布函数的非均布性。总可以通过空间变换来平坦该分
布函数，至少将分布函数分段后是可以逐段进行的。这种方法面临的困难就是，变换后
的空间，其范数并不直接对应原空间中的范数，所以一次得到最优解总是不可能的。但
作为一个很好的初值赋予，再借由高效稳定的迭代收敛来实现局部最优解是可行的。

VQ的全局最优解绝对是一个世纪级的难题。

3、编码算法
VQ的编码可以通过Voronoi图来理解：由空间中的一个不重复点集形成的分划，将空间分
割成与点集的元素一一对应的部分。任一点对应的空间部分中的任意点，到原点集中任
意点的距离中，到该部分对应点的距离最小。输入落在Voronoi图的一个部分，则量化为
该部分对应的量化点。

一条思路，是通过定位输入属于Voronoi图的部分来定位量化点。难点在高维Voronoi图
的生成和描述。
另一条思路，是启发式的，将Voronoi图中相邻的部分对应的量化点作为邻居形成图，从
图中任意点，可启发式搜索到目标量化点。难点在高维Voronoi图的生成。
还可以用一般的计算几何结构，将量化点基数排列，首先排除离得比较远的点。难点在
高维空间分划的储存量巨大，很难降低。
所以最常用的方法，是逐个判定求最近。VQ的目标是压缩，所以量化点集总不会太大。

--

    不管我活着
    还是我死去
    我都是一只牛虻
    快乐的飞来飞去
※ 来源:·瀚海星云 bbs.ustc.edu.cn·[FROM: 118.112.13.176]