机器学习经典算法：k-SVD 前面为什么加个 k?-轻识

11、字典学习思想

人类知识的发展历程比较复杂，我们简单点将其看成一个迭代过程：一代人的知识积累下来，再传授给下一代，下一代人除了使用已有知识外，还会对知识作进一步提升和扩展，然后继续传授给下一代。如此往复，不断进步。

然而知识从广义上看非常宽泛，我们不妨将其作一个简化，假设知识可以用一个字典来表示，那么知识的形成和应用也简化为两个步骤：建字典和查字典。

这里隐藏着如下一些大致要求，

字典尽量建得全面完备，以满足各个方面各个角度的不同应用。概括地说，就是具有完备性甚至允许冗余性。
而查字典往往是为了解决某一个特定问题，因此涉及到的具体知识点会比较有限，反映在所谓的稀疏性上。概括地说，就是具有稀疏性而不失精准。

从机器学习的角度来看，我们需要将这两点数学化，那么该如何办到呢？

¸转化为数学问题

我们将上面的所提到的几个关键点用简单的数学概念表示如下：

数据矩阵，用表示，每一列表示一个样本；
字典矩阵，用表示，而列向量表示字典中的词条，称为原子（atom）；
稀疏表示，即查字典，用矩阵乘法表示，即，其中的列表示一个样本的系数向量。

2k-SVD 方法

我们的出发点是观察到的个随机变量根据线性模型用个潜在变量表示

\mathbf{y}=\mathbf{D} \mathbf{x}, \quad \mathbf{y} \in \mathbb{R}^{l}, \quad \mathbf{x} \in \mathbb{R}^{m}, \;m>l

是一个未知的矩阵，通常有。即使是已知矩阵，也容易看出该任务并没有唯一解，因此需要加入约束条件，比如此处我们采用稀疏性约束。

令观测值为，，这也是唯一已知信息。我们的任务是获取字典的原子（即的列）以及假定为稀疏的系数向量；也就是说，我们将建立输入观察（向量）的稀疏表示。本文的主题 -SVD 就是实现这个任务的一种方法。至于为什么叫这个名字，文末有讨论。

首先，令

\mathbf{Y}:=\left[y_{1}, \ldots, y_{N}\right]

\mathbf{D}:=\left\{d_{1}, \ldots, d_{m}\right\}

\mathbf{X}:=\left[x_{1}, \ldots, x_{N}\right]

其中是输入对应的表示系数向量，这里简称系数向量。

然后，所谓的字典学习任务被转换为以下具体优化问题，

\begin{aligned} \min_{\mathbf{D}, \mathbf{X}} & \|\mathbf{Y}-\mathbf{D} \mathbf{X}\|_\mathrm{F}^{2} \\ \text{s.t.} \quad \left\|x_{n}\right\|_{0} &\leq T_{0},\; n=1,2, \ldots, N. \end{aligned}

其中是阈值，表示范数，表示向量中不为的数的个数。

这是一个非凸优化任务，可以迭代式求解。然而，和都未知，都需要求解。这种情况很常见，一般可以将两者分开优化：假设我已知，优化你；再假设你已知，优化我；交替迭代以致收敛。

因此，每一次迭代包括两个阶段，

第 1 阶段：假设是固定的，针对，进行优化。
第 2 阶段：假设系数向量是固定的，并针对的列进行优化。

在 -SVD 中，对上述步骤作了稍微改动：在优化的列时，对的某些元素也同时进行更新。

这也是 -SVD 与更标准的优化技术的关键区别，这样做似乎可以提高实际性能。

¸第 1 阶段：稀疏编码

假设已知，即从前一次迭代中获得的值。那么，此时的优化任务就变成了

\begin{aligned} \min_{\mathbf{X}} & \|\mathbf{Y}-\mathbf{D} \mathbf{X}\|_\mathrm{F}^{2} \\[1em] \text { s.t. } \left\|x_{n}\right\|_{0} & \leq T_{0}, \quad n=1,2, \ldots, N \end{aligned}

由于 Frobenius 范数的定义可知，这相当于解如下个独立的优化任务，

\begin{aligned} \min_{x_{n}} & \left\|{y}_{n}-\mathbf{D} x_{n}\right\|^{2} \\[1em] \text { s.t. } \left\|x_{n}\right\|_{0} &\leq T_{0}, \quad n=1,2, \ldots, N \end{aligned}

这个问题并不好处理，不妨转变一下思路，比如考虑以下优化任务，则可以实现类似的目标：

\begin{aligned} \min_{x_{n}} & \left\|x_{n}\right\|_{0} \\[1em] \text { s.t. }\; \left\|y_{n}-\mathbf{D} x_{n}\right\|^{2} & <\epsilon, \quad n=1,2, \ldots, N \end{aligned}

其中是一个常数，作为误差的上界。

上式的任务可以通过任何一种最小化求解器来求得，例如 OMP。

而带有约束的优化问题，可以利用拉格朗日乘子法将其转化为无约束优化问题，

\begin{aligned} \min_{\mathbf{D,\ X}}{\|\mathbf{Y}-\mathbf{DX}\|^2_\mathrm{F}}+\lambda\|\mathbf{x}_i\|_1 \end{aligned}

这里我们用代替了，主要是因为更加便于求解。

¸第 2 阶段：字典更新

从第 1 阶段获得，。

现在的目标是针对的列进行优化，注意，算法中是逐列分别处理的。

假设我们目前考虑更新；这样做是为了最小化（平方）Frobenius 范数。为此，我们可以将乘积写成秩 1 矩阵的和，即

\mathbf{D} \mathbf{X}=\left[d_{1}, \ldots, d_{m}\right]\left[x_{1}^{r}, \ldots, x_{m}^{r}\right]^{\top}=\sum_{i=1}^{m} d_{i} x_{i}^{r \top}

其中，对应矩阵的行。

请注意，在上述总和中，索引为的向量在当前迭代步骤中取其最近更新的值，而索引为的向量取在前一次迭代中得到的值。显然，该策略允许使用当前迭代步骤中最近更新的信息，一定意义上提高了迭代效率。

接着，我们将最小化外积矩阵（秩为 1）。

观察到这个乘积，除了的第列外，还涉及的第行；两者同时更新。

现在的任务就是求解一个秩 1 矩阵以最小化下式，

\left\|\mathbf{E}_{k}-{d}_{k} x_{k}^{r \top}\right\|_\mathrm{F}^{2}

其中，

\mathbf{E}_{k}=\mathbf{Y}-\sum_{i=1, i \neq k}^{m} d_{i} x_{i}^{r \top}

这个可以从下式中推得，

\begin{aligned} {\|\mathbf{Y}-\mathbf{DX}\|^2_\mathrm{F}} =&\left\|\mathbf{Y}-\sum^m_{i=1}\mathbf{d}_i\mathbf{x}^{r \top}_{i}\right\|^2_\mathrm{F} \\[1em]=&\left\|\left(\mathbf{Y}-\sum_{i\ne k}\mathbf{d}_i\mathbf{x}^{r \top}_{i}\right)-\mathbf{d}_k\mathbf{x}^{r \top}_{k}\right\|^2_\mathrm{F}\\[2em] =&\left\|\mathbf{E}_k - \mathbf{d}_k\mathbf{x}_{k}^{r \top} \right\|^2_\mathrm{F} \end{aligned}

换句话说，我们要寻找一个在 Frobenius 范数意义上最逼近误差矩阵的秩 1 矩阵。

上面从形式上看是一个最小二乘问题，自然可以利用最小二乘法来求解。但回想一下矩阵的 SVD 分解，容易知道这个小任务也可以通过矩阵的 SVD 给出的。但是，如果我们直接这样做，从第 1 阶段中获取到的关于的稀疏结构将会被破坏掉。

根据 -SVD，这可以通过关注活动集来绕过，即只涉及非零值的那些系数。

因此，我们首先在中搜索非零系数的位置，并令

\omega_{k}:=\left\{j_{k}, 1 \leq j_{k} \leq N: x_{k}^{r}\left[j_{k}\right] \neq 0\right\}.

然后，得到一个简化向量，其中表示集合中元素的个数，而只包含的非零元素的下标。

观察等式，不难发现当前感兴趣的列仅对中所有对应的那些列有贡献。

然后我们收集的对应列来构造矩阵，该矩阵包含与的非零元素位置相关的列，并选择以最小化下式，

\left\|\tilde{\mathbf{E}}_{k}-{d}_{k} \tilde{x}_{k}^{r \top}\right\|_\mathrm{F}^{2}

由 SVD 分解可得，然后令，其对应于最大的奇异值，以及令。由于，可知字典中的原子是单位向量。

后续将得到的更新值放在的对应位置，而后者现在至少有与以前一样多的零。在每次迭代中，误差都会减小，算法会收敛到局部最小值。

综上所述， -SVD 算法的每次迭代包括以下计算步骤。

1、初始化，即用范数归一化它的每一个列向量，并令。

2、第 1 阶段稀疏编码：用相关算法（如 OMP）解优化问题，获得稀疏编码表示向量，。

3、第 2 阶段字典更新：对于中的任何列，根据以下步骤进行更新：

从第 1 阶段计算所得的矩阵中确定第行中各非零元素的位置。
选择中与的第行非零元素位置对应的列，构建误差矩阵。
求的 SVD 分解：。
将的第列更新为最大奇异值对应的左奇异向量，即。
更新，将它的第行的非零元位置设为中的相应值。

4、如果满足收敛标准，则停止迭代；否则令，继续迭代。

¸为什么叫 k-SVD

名称的 SVD 部分非常明显。但是，读者可能想知道前面为啥要加一个。注意，这里的跟算法中的步骤没有关系，因为步骤可以用另一个字母表示。

那么它到底为啥要加上这个名头呢？实际上，该算法可以被认为是 -means 算法的推广。可以将代表每个簇的平均值视为字典的原子。在 -means 学习的第一阶段，给定每个簇的代表，执行稀疏编码方案；也就是说，每个输入向量都只分配一个簇。

因此，我们可以将 -means 聚类视为一种特殊的稀疏编码方案，它将一个系数向量与每个观察值相关联。请注意，此时每个系数向量只有一个非零元，根据与所有簇代表的最小欧几里德距离可得相应输入向量的簇。与 -SVD 字典学习的主要区别是每个观察向量可以与多个原子相关联；因此，相应系数向量的稀疏度可以大于。

此外，基于输入向量到簇的分配，在 -means 算法的第二阶段，执行簇代表的更新，但对于每个代表仅涉及分配给它的输入向量。这与 -SVD 的第二阶段的情况相似。不同之处在于每个输入观察可能与多个原子相关联。如果设，此时 -SVD 相当于 -means 算法。