# 向量量化

# 介绍

“矢量量化”。听起来很吓人。“残差矢量量化”听起来更吓人，对大多数人来说甚至毫无意义。事实证明，只要看几张图片，这些算法就很容易理解，甚至连小孩都能理解——呃……如果孩子愿意的话。当然，可以有复杂的方法来实现这些算法，我们稍后会介绍一些，但基础非常简单。

残差矢量量化 (RVQ) 是一种数据压缩技术，可用于最先进的神经音频编解码器，例如 Google 的SoundStream和 Facebook/Meta AI 的Encodec ，而这些编解码器又构成了AudioLM (Google) 和MusicGen (Facebook)等生成音频模型的支柱。它也是 Lucidrain 库的主题vector-quantize-pytorch，我们将在最后使用它，因为它非常快而且非常好用。

什么是 RVQ 以及它如何工作？

首先，我们应该考虑常规矢量量化 (VQ)。VQ 已经存在了几十年，它出现在涉及压缩的信号处理的许多领域中。

两个类比

城市和城镇： RVQ 就像物流中经常出现的“枢纽辐射”图：以航空旅行为例，其中主要城市是“枢纽”（芝加哥、洛杉矶、亚特兰大），您可以从那里乘坐较小的航班到达较小的城市和城镇。VQ 就像用最近的城镇替换每个地址 - 这会产生很多向量！RVQ 意味着我们有一个简短的枢纽列表，然后从每个枢纽我们都有一个较小城市的列表，然后我们可以从中得到将较小城市连接到附近城镇的列表。

数字和位数：从一维来看，RVQ 就像我们用位数表示数字一样。我们不是为从 0 到 9999 的每个整数创建 10,000 个单独的类别，而是使用 4 个“码本”（用于千位、百位、十位和个位），由 0 到 9 的十位数字组成。4 * 10 = 40，比 10,000 少很多！我们甚至可以使用更多码本将小数点右侧的“残差向量”变得更小，从而以任意精度表示实数。

# 矢量量化 = 划分空间

“矢量量化”实际上是将数据点的空间划分为一组离散的区域。换句话说，我们对空间进行“分区”。

假设我们在空间中有一堆点：

图 1.一组数据点，又称“向量”。对于计算机科学家来说，每个点的坐标(x,y)定义一个“矢量”。（对于数学家和物理学家来说，“矢量”从原点指向每个点，但这种区别对我们来说并不重要。）

现在将空间划分成一堆区域。我们可以采取多种形式来做到这一点。现在，只需考虑我用颜色手绘的两个例子和一组平铺的正方形。有“更花哨”的算法可以以最“适合”数据的方式划分空间（例如，参见下面的“k-Means”）。我们可以稍后介绍像第三幅图这样的方案。 (a)手工 (b)正方形 (c)Fancy（图片来源：芬兰阿尔托大学）

图 2.划分或“量化”空间的方法示例，又称“分区方案” 。

接下来，我可以用方块做更多的代码工作，所以让我们从那里开始吧。😉

让我稍微形式化一下：我们将让变量“ ”控制正方形的数量n_grid。因此，对于我们的二维示例，将有n_grid 方形区域。

通过矢量量化，我们为每个区域赋予一个索引值（例如，5x5 方格的索引值为 0 到 24），然后用区域的索引替换每个矢量的值。

图 3. （整数）每个区域的索引。

对于数据点所代表的每个“向量”，我们不再使用(x,y) 坐标对，而是其所在区域的（整数）索引。

注意：我们已经从每个点需要两个浮点数变为只需要一个整数值。在二维中，由此获得的“节省”或数据压缩量可能并不明显，但请记住：当我们以后处理大量维度时，此方案将为我们节省大量数据。

如果我们想要与索引相匹配的坐标，我们将使用每个区域的质心。从这个意义上讲，向量是“量化的”，因此它们只能采用区域质心给出的值。在以下示例中，质心显示为红色：

图 4.质心位置因此，每个蓝点实际上将被最近的红点替换。从这个意义上讲，我们已经“量化”了向量（因为我们已经量化了空间本身）。

术语：质心位置的集合称为“码本”。当我们想要使用实际的向量值（在空间中）时，我们通过查找码本将码本索引转换为（质心）位置。

因此，显示数据点、区域索引和质心的完整（尽管笨拙）图片如下所示：

图 5.显示数据点、区域索引和质心位置的详细图表。对于我们选择的坐标，码本（即索引到质心位置的映射）如下所示：

指数	向量
0	(-0.4,-0.4)
1	(-0.2,-0.4)
...	...

# 重建误差

当我们进行这种量化（即用最近的质心替换向量）时，质心位置自然会与原始数据向量本身有点“偏离”。网格越细，区域越小，误差越小。对于 2D 网格，误差约为$h^2$,h是网格间距(h= 1/5 = 0.2)。

注意：请注意，码本中的向量不是“基础向量”：我们不添加码本向量的线性组合，因为这不是“量化”（并且会将数据点数量与原始数据相同，导致几乎没有压缩）。VQ 通过使用最接近的码本向量来近似数据点，帮助我们解决拥有大量数据点的一些问题，而 RVQ 中的 R 使我们能够增加空间内良好“分辨率”的提供，而无需极长的码本。

让我们检查一下随着网格间距的变化（即随着变化），误差如何变化。

图 6.误差与分辨率的关系图，其中线性轴（左）和对数轴（右）。请注意，计算成本将随区域数量而变化，即n_grid 。 lowest error (for n_grid=200) = 0.019903707672610238

因此，使用的“网格线”越多，误差越低，但代价是什么？要得到 0.02 的误差，我们需要区域。而在高于 2 的维度中，更高分辨率/更低误差的“成本”会大幅增加：将分辨率翻倍尺寸，计算成本增加了。（想象 =32、64、128、…）

但我们不需要均匀地覆盖整个空间！这就是残差矢量量化的用武之地。您可以直接跳到 RVQ 部分。接下来我们将选一个可选的题外话来了解另一种划分空间的方法，即“k-Means”算法。

提示：另一个关键点：通过替换矢量的所有坐标值（即 d浮点数）与单个整数，VQ 实现了数据压缩（与整数相比，浮点数占用的位数是其倍数）。对于大量维度，无论采用何种分区方案，这种压缩都可能非常显著。

# k-均值（分区方案）

说明：关于 k-Means 的讨论实际上对于理解 (R)VQ 并不重要。一点也不。老实说，这完全可以跳过。所以……只有你真的很好奇才读。否则就跳到残差矢量量化部分。

k-Means 算法是另一种划分空间的方法，这种方法不使用静态方块，而是允许我们的区域和质心“跟随数据”。k-Means 通常用于初始化神经编解码器（例如 SoundStream、Encodec 等）的 RVQ 码本，之后神经网络的其余训练算法可能会进一步细化码本。

我们将从下面显示的一堆数据点（小黑圈）和一组k“质心”用大彩色圆圈表示。（它们实际上还不是“质心”，但我们会到达那里）。图 7. k- Means的初始状态，显示没有任何“成员”的数据（黑点）和随机质心位置（大彩色点）这就是我们的起点。然后我们要做的就是，根据每个点最接近的质心来为其着色。 ![](images/t2m/newplot (1).png) 图 8。k - Means的第一步：根据哪个质心（大点）最接近，将数据点的“成员”分配给不同的聚类。请注意，此图中的“质心”还不是真正的质心。我们将在下一步中修复它们。下一步是使用分配给每个质心的点重新计算质心位置。这些质心只是这些点的平均值。

![](images/t2m/newplot (2).png) 图 9. k-Means 的下一步：移动质心，使其位于每个聚类的中间 …但现在，由于移动了质心，一些点的最近邻成员资格可能已经发生了变化。因此，我们重新计算这些：

![](images/t2m/newplot (3).png) 图 10. k- Means的下一步：根据新的聚类位置重新分配点的聚类成员资格 …我们重复这个过程，直到满足某个停止标准。例如，我们可以只设置最大迭代次数，或者当质心停止移动或集群成员停止变化时，我们就可以停止，等等。对于这个演示，我们将只使用最大迭代次数。

因此，整个过程的电影看起来可以是这样的： ![](images/t2m/newplot (4).png) 图 11. （交互式）在此影片中，每个时间步骤要么是“集群成员资格”步骤，要么是“质心移动”步骤。

由于 k-Means 是一种“最近邻”算法，因此它的最终结果是根据“ Vornonoi 图”分组的一组向量，就像本文开头附近所示的那样，为了便于说明，我们将再次展示它： ![](images/t2m/vq_aalto_sm (1).png)

# 残差矢量量化（RVQ）

基本思想：“码本中的码本” RVQ 的诀窍是，不是使用单个高分辨率码本，而是使用“码本中的码本”，或者，如果你愿意的话，也可以使用“堆叠码本”。假设我们想将初始 5x5 网格的分辨率提高五倍。我们不使用 25x25 网格（计算成本将是原始网格的 25 倍），而是将一个小的 5x5 网格“放在”矢量量化的区域内，结果会怎样？

例如，在“中间”区域（区域 12），我们可以执行... 图 13. “码本中的码本”的图示，其中较小的 5x5 码本将相对于中间区域的码本。中间“主”方块中的蓝点与其对应的红色质心之间的差异将是“残差”。我们还将在“小”5x5 网格内量化它。这将用作原始码本“之后”使用的码本。我们将获得与 25x25 网格相同的分辨率，只是我们的计算成本将改为 2*(55)=50，而不是 2525=625！因此，我们的成本将比全网格方法小 12.5 倍。

有趣的是，如果我们只考虑残差，即主质心和所讨论向量之间的差异，那么我们可以对空间中的所有点使用相同的“下一级”码本！在下图中，我们将残差显示为从每个点延伸到其对应的最近质心的紫色线段：图 14.重定义域的图示，显示为连接向量（蓝点）与其最近的质心（红点）的紫色线段。此外，由于我们巧妙地将数据设置为以原点为中心(0,0)，我们可以将原始数据点视为相对于整个域的“质心”，即原点的“残差”！图 15.对于“0 级”码本，我们如何将数据点本身视为相对于原点的残差此外，由于我们巧妙地选择了坐标，对于下一个“级别”的量化，我们可以将下一级的码本取为前一个码本除以n_grid！情况并非总是如此；我只是觉得自己很聪明，也很懒惰。

# 量化算法

到目前为止，我们默认隐藏了代码。但为了真正了解 RVQ 方法，我将展示代码。

让我们编写一个多“层”嵌套码本的通用量化器。它将获取我们的数据点并返回各层码本索引。

将遵循 Google 2021 年论文“ SoundStream：一种端到端神经音频编解码器”第 4 页中的“算法 1”：图 16.SoundStream的 RVQ算法但我喜欢我的写作方式：

def quantizer(data, codebooks, n_grid=5):
    "this will spit out indices for residuals in a series of 'nested' codebooks"
    resids = data 
    indices = []
    for cb in codebooks:
        indices_l = get_region_membership(resids, codebook=cb)
        resids = resids - cb[indices_l]
        indices.append(indices_l)
    return np.array(indices)

# Make the nested codebooks
n_codebooks = 3
codebook = generate_codebook(n_grid)
codebooks = [codebook/n_grid**level for level in range(n_codebooks)]

indices = quantizer(data, codebooks)   # call the quantizer
display(indices)

下面显示indics结果：

array([[10,  2,  5,  7,  5, 20,  4, 13, 19, 17, 16, 14, 24,  4, 22, 23,
         4, 21, 19, 11, 13, 12,  4, 18,  4],
       [10, 17,  3,  5, 17,  9,  3, 22,  7, 13, 14,  5,  3, 24, 18,  6,
        24,  6, 17,  8, 10,  1, 21, 12,  3],
       [11,  6, 12,  7, 15, 20, 23,  7, 17, 13,  8, 18,  2,  7, 15, 11,
        16, 20, 23, 13, 11, 24, 18, 10, 20]])

让我们通过尝试使用每一级码本重建原始数据来测试这一点。在下面，原始数据将以蓝色显示，其他颜色将显示使用越来越多码本进行量化的结果：

图 17.使用多级 RVQ 码本（橙色点）重建数据（蓝点）我们发现，使用的码本越多（层级），我们越能近似原始数据。最右边的图像的有效分辨率为555=125小方块，而是只使用在553=75二维中，这并不是一个巨大的节省，但让我们看看这对于更高维度来说有多么重要。

让d是维数，K是码本的数量（恐怕与 k-Means 中的 k 无关）。我们将用大量数据填充 d 维超立方体，并使用 RVQ 将其细分为嵌套的小超立方体组，并计算误差 - 以及如果我们使用常规 VQ 而不是 RVQ 所节省的计算成本。

注意：使用均匀的正方形/（超）立方体区域是一个非常愚蠢的想法。因为区域的数量将像n_grid ，实际上可能比我们拥有的数据向量数量大得多！我们将在下面尝试更复杂的分区方案。

#### label: fig-rvq-recon-highdim2
#### fig-cap: "Error for high-dimensional datasets using various levels of RVQ. 'cost savings factor' refers to the ratio of using regular VQ (at uniform resolution) vs RVQ"

d_choices = [2, 3, 4, 6]  # we can't go much higher with 5x5 uniform grids!
K_choices = [1,2,3,4]     # variable numbers of codebooks

npoints_hd = 1000  # points in high-dim spaces

print("Here we show the error for high-dimensional datasets using various levels of RVQ.")
print("'cost savings factor' refers to the ratio of using regular VQ (at uniform resolution)\nvs RVQ.")

for d in d_choices:
    print(f"\nd = {d}:")
    np.random.seed(1)
    data_hd = DATA_MIN + (DATA_MAX-DATA_MIN)*np.random.rand(npoints_hd, d)
    codebook0 = generate_codebook(n_grid, n_dim=d)
    codebooks = [codebook0/n_grid**level for level in range(max(K_choices))] # lets get this over with rather than in the loop
    for K in K_choices: 
        indices = quantizer(data_hd, codebooks)
        recon = data_hd*0
        for lil_k in range(K):   # reconstruct using all codebooks
            recon += codebooks[lil_k][indices[lil_k]]
        error = ((recon - data_hd)**2).mean()
        grid_0_points = n_grid**(d)
        rvq_points = grid_0_points*K 
        uni_res = grid_0_points**K # comparable uniform resolution
        savings = uni_res/rvq_points
        print(f"  K = {K}, error = {error:.2e}, cost savings factor = {savings:.1f}")
        pass

这里我们展示了使用不同级别的 RVQ 的高维数据集的误差。 “成本节省因子”是指使用常规 VQ（统一分辨率）与 RVQ 的比率。



d = 2:
  K = 1, error = 3.41e-03, cost savings factor = 1.0
  K = 2, error = 1.29e-04, cost savings factor = 12.5
  K = 3, error = 5.26e-06, cost savings factor = 208.3
  K = 4, error = 2.16e-07, cost savings factor = 3906.2

d = 3:
  K = 1, error = 3.37e-03, cost savings factor = 1.0
  K = 2, error = 1.29e-04, cost savings factor = 62.5
  K = 3, error = 5.31e-06, cost savings factor = 5208.3
  K = 4, error = 2.18e-07, cost savings factor = 488281.2

d = 4:
  K = 1, error = 3.36e-03, cost savings factor = 1.0
  K = 2, error = 1.32e-04, cost savings factor = 312.5
  K = 3, error = 5.34e-06, cost savings factor = 130208.3
  K = 4, error = 2.16e-07, cost savings factor = 61035156.2

d = 6:
  K = 1, error = 3.37e-03, cost savings factor = 1.0
  K = 2, error = 1.33e-04, cost savings factor = 7812.5
  K = 3, error = 5.35e-06, cost savings factor = 81380208.3
  K = 4, error = 2.16e-07, cost savings factor = 953674316406.2

不过，这些“成本节约因素”是人为设定的，因为我们仍然使用正方形/超立方体来表示区域，我们不需要以这种方式塑造它们，也不需要那么多。 (R)VQ 的优点在于，您可以指定所需的质心数量 - 即您希望代码本有多“长” - 并且即使维度数量激增，您也可以将其保持在某个可管理的数字。

因此，为了处理更高的维度，我们需要停止使用均匀的正方形，这样我们就可以得到一个小于几千个质心的码本“长度”（而不是刚才的数十万个，例如）。为了获取跟随数据的非均匀区域，我们将使用上面描述的 k-Means 方法。

让我们看看重建误差在高维度中的表现。

# 误差分析：指数收敛

我们可以尝试给定数量的（最初）随机质心，并尝试通过 k-Means 将它们与数据匹配。

我们的 RVQ 计算中不同级别的残差可能具有不同的数据分布。这意味着，我们不再像以前那样“共享（缩放）码本”，而是需要在每个“级别”重新计算一个新的码本。否则，我们将看不到 RVQ 的任何优势（相信我，我试过了）。

在下面的计算中，我们将改变维数、码本的长度和码本的数量，看看这些如何影响重建误差。

但是，我们不要使用我们的代码，而是使用 lucidrains 提供的精彩存储库：lucidrains/vector-quantize-pytorch

以下错误值集合是“一堆数字”，您可能不感兴趣。您可以随意滚动过去并跳到（部分）数字的图形表示。

注意：K=1 的 RVQ 与常规 VQ 相同。

图 18. （交互式）具有不同数据维度和码本长度的 4 个码本的重建误差表面图。因此，正如我们所料，更长的码本会有所帮助，而在更高的维度下，误差往往会更大。

这是同样的事情，但是用对数轴来表示误差： ![](images/t2m/rvq_newplot (1).png) 图 19. （交互式）具有不同数据维度和码本长度的 4 个码本的重建误差表面图。（对数 z 轴）现在让我们看一下码本长度为 2048 时的误差，其中我们改变了码本的数量： ![](images/t2m/rvq_newplot (2).png)

图 20.码本长度为 2048 且数据维度和码本数量 (K) 各异的重构误差。(对数 z 轴) 请注意，在最后一张图中，随着 K 的变化，我们看到直线1 ，并且 K 轴是线性的，误差轴是对数的。这意味着——这是一个重要的结论：

当我们将码本添加到 RVQ 算法中时，错误会呈指数减少！

这是 RVQ 方法的一大“卖点”：计算成本线性增加，但错误减少量却呈指数级增长。

# 附录：极高维度下的难度

然而，上述结果还表明，对于非常高的维度(例如，d>=128)，(R)VQ 提供的收益远不及低维，添加更多更大的码本对错误没有太大影响。

因此，在他们全新的第二篇论文使用改进的 RVQGAN 进行高保真音频压缩 (opens new window)中，Descript团队选择将数据投影到低维空间(d=8) 首先使用线性层，然后执行 RVQ，然后使用另一组线性层进行投影回来。

……现在就到此为止。我们还有很多话要说、可以做——例如，“如何使用 RVQ 进行反向传播？”——但这似乎是暂停讨论的好时机。

← smpl motionclip →