春暖花开

向量量化与乘积量化简介

向量量化-VQ

向量量化(Vector Quantization)是一个常见的压缩技术,广泛用于信号处理和数据压缩等领域。VQ 一个比较正式的定义是将一个向量空间中的点用其中的一个有限子集来进行编码的过程。它是一种基于块编码规则的有损数据压缩方法,基本思想是:将若干个标量数据组构成一个矢量,然后在矢量空间给以整体量化,从而压缩了数据而不损失多少信息。

VQ实际上就是一种逼近,它的思想和“四舍五入”有异曲同工之妙,都是用一个和一个数最接近的整数来近似表示这个数。用二维图像压缩来说明,将图像的每个像素点当作一个数据,跑一下 K-means 聚类,假设将图像聚为k类,就会得到每类的质心centroids,共k个,然后用这些质心的像素值来代替对应的类里的所有点的像素值。这样就起到了压缩的目的,因为只需要编码k个像素值(和图像每个像素点对这k个值的索引)就可以表示整张图像了。当然,这会存在失真。最偏激的情况是原图像每个像素就是一个类,那就没有失真了,当然也没有了压缩。

VQ 问题可以描述如下:给定一个已知统计属性的矢量源(也就是训练样本集,每一个样本是一个矢量)和一个失真测度,同时给定码矢的数量(也就是我们要把这个矢量空间划分为多少部分,或者说量化为多少种值),然后寻找一个具有最小平均失真度的码书(所有码矢的集合)和空间的划分。简单描述为:给定T(训练集)和N(码矢数目),找到能使Dave(平均失真度)最小的C(码书)和P(空间划分)。

如果 C 和 P 是上面最小化问题的一个解,那么需要满足两个条件:

  • 最近邻条件
  • 质心条件

乘积量化-PQ

乘积量化(Product quantization),这里的乘积是指笛卡尔积,其思想是把原向量空间分解为若干个低维向量空间的笛卡尔积,并对分解得到的低维向量空间分别做量化,这样每个向量就能由多个低维向量的量化 code 表示。

PQ 本质上是一种数据压缩表达方法,可用于相似搜索、模型压缩等领域,特别是深度神经网络的模型压缩上。PQ 算法可以理解为对 VQ 做了一次分治,首先把原始向量空间分解为 m 个低维向量空间的笛卡尔积,并对分解得到的低维向量空间分别做量化。对低维向量空间的量化同样是使用 K-means 算法。换句话描述就是,把原始 D 维向量(比如 D = 128 )分成 m 组(比如 m = 4 ),每组就是 D’ = D / m 维的子向量(比如 D’ = D / m = 128 / 4 = 32 ),各自用 K-means 算法学习到一个码本,然后这些码本的笛卡尔积就是原始 D 维向量对应的码本。

0%