Dictionary Learning详解

第四十五次写博客，本人数学基础不是太好，如果有幸能得到读者指正，感激不尽，希望能借此机会向大家学习。本文主要对字典学习（Dictionary Learning）进行简要介绍，并对其中较为典型的K-SVD算法进行讲解。

预备知识：

$L_{0}$L0​范数

  $||{\bf{x}}||_{0}=$∣∣x∣∣0​=向量$\bf{x}$x中非零分量的数量

Frobenius（弗罗贝尼乌斯）范数

  对于矩阵${\bf{X}}\in{\Bbb{R}^{m\times{n}}}$X∈Rm×n，$||{\bf{X}}||_{F}=(\sum_{i=1}^{m}{\sum_{j=1}^{n}{x_{ij}^{2}}})^{1/2}$∣∣X∣∣F​=(∑i=1m​∑j=1n​xij2​)1/2，并且$||{\bf{X}}||_{F}^{2}=\sum_{j=1}^{n}{||{\bf{x}}^{j}||^2_2}=\sum_{i=1}^{m}{||{\bf{x}}_{i}||^2_2}$∣∣X∣∣F2​=∑j=1n​∣∣xj∣∣22​=∑i=1m​∣∣xi​∣∣22​，其中${\bf{x}}_{i}$xi​和${\bf{x}}^{j}$xj分别为${\bf{X}}\in{\Bbb{R}^{m\times{n}}}$X∈Rm×n的行向量和列向量。

推导过程：

字典学习与稀疏编码

  特征选择过程可以看做是将“感兴趣”的特征以外的特征全部赋值为零，即将数据集中的某一行（列）全部置零，“稀疏表示”（sparse learning）则是将数据集对应的（稀疏编码后的）矩阵中的某些元素赋值为零，这些元素并不必须位于某一行（列）上。采用稀疏表示的优点是，对于类似支持向量机等学习器期望用于学习的数据集是线性可分的，而稀疏化后的数据集在很大程度上满足这条属性，另外，稀疏的数据集并不会造成存储上的负担，因为现在已经有很多高效的存储稀疏矩阵的方法。
  对于稠密矩阵我们所期望的是对其进行“恰当稀疏”而不是“过度稀疏”，例如对于文本分类问题，如果我们使用《现代汉语大辞典》对文本进行编码，这样得到的数据集将是恰当稀疏的，但是使用《康熙字典》显然是过度稀疏的，因此，在一般的学习任务中，我们需要学习到一个可以对数据集进行恰当稀疏的“字典”，这个学习过程就被称为“字典学习”（Dictionary Learning），而之后通过该“字典”对样本进行编码的过程被称为“稀疏编码”（sparse coding）。

K-SVD简介

  假设字典矩阵为${\bf{D}}\in{\Bbb{R}^{n\times{K}}}$D∈Rn×K，$K$K代表字典的词数，$n$n代表原始样本的属性个数，${\bf{d}}_{i}$di​代表矩阵${\bf{D}}$D的第$i$i列，${\bf{y}}\in{\Bbb{R}^{n}}$y∈Rn是原始样本，${\bf{x}}\in{\Bbb{R}^{K}}$x∈RK是${\bf{y}}$y经过稀疏编码后的样本（即稀疏化样本），稀疏表示的目标是获得可以恰当表示原始样本、非零分量最少的稀疏化样本，即

$\min_{\bf{x}}{||{\bf{x}}||_{0}}$xmin​∣∣x∣∣0​

但是当$n&lt;K$n<K且$\bf{D}$D满秩时，上式有无穷多个解，因此需要一些约束条件使得解唯一，因此，以上各个参量需要满足

$(P_0)\min_{\bf{x}}{||{\bf{x}}||_{0}} \\ s.t.\quad{\bf{y}}={\bf{D}}{\bf{x}} \tag{1}$(P0​)xmin​∣∣x∣∣0​s.t.y=Dx(1)

或者

$(P_{0,\varepsilon})\min_{\bf{x}}{||{\bf{x}}||_{0}} \\ s.t.\quad||{\bf{y}}-{\bf{D}}{\bf{x}}||_{p}\leq{\varepsilon} \tag{2}$(P0,ε​)xmin​∣∣x∣∣0​s.t.∣∣y−Dx∣∣p​≤ε(2)

上式中$p$p常取$p=1,2,\infty$p=1,2,∞，不过这里只关注$p=2$p=2的情况，即

$(P_{0,\varepsilon})\min_{\bf{x}}{||{\bf{x}}||_{0}} \\ s.t.\quad||{\bf{y}}-{\bf{D}}{\bf{x}}||_{2}\leq{\varepsilon} \tag{3}$(P0,ε​)xmin​∣∣x∣∣0​s.t.∣∣y−Dx∣∣2​≤ε(3)

  稀疏编码广泛的应用于压缩、识别以及特征提取领域，用于求解这类问题的、最具有代表性的追踪算法（Pursuit Algorithm）【3】，通过预先假定由于编码的字典已知而且固定不变，这类方法简单可行，而且可以对稀疏编码的性能进行简单而快速的评价，实际上，他被广泛的应用在小波变换、轮廓波变换以及短时间傅里叶变换中。但是，他在很大程度上依赖于，事先确定的字典能否使得稀疏化样本恰当的表示原始样本，考虑到这个问题，我们需要一种通过不断拟合稀疏化样本来学习字典的算法。
  K-SVD算法作为K-Means算法过程的泛化，是由Michal Aharon等人于2006年提出的，用于在给定训练集后，在严格的稀疏化条件（式（1）、（2））下找出一个可以恰当表示这些样本的字典，该算法是一个交替迭代更新算法，即“根据字典对每个样本重新进行稀疏编码，并且根据稀疏化样本对字典进行更新”，这样做可以加快算法收敛速度，K-SVD算法可以与追踪算法（例如Basic Pursuit、Matching Pursuit、Orthogonal Matching Pursuit、FOCUSS等）灵活结合，最终得到字典以及原始样本的恰当稀疏化样本。

稀疏编码（Sparse Coding）

  “稀疏编码”（Sparse Coding）是根据原始样本$\bf{y}$y以及字典$\bf{D}$D，求得原始样本的稀疏表示$\bf{x}$x的过程，该过程类似于“原子分解”（Atom Decomposition），需要解决式（1）或（2）的优化问题，获得上述问题的精确解被证明是NP-hard的，因此经典的解法是采用可以获得近似解的“追踪算法”（Pursuit Algorithm）。
  追踪算法中最简单的是Matching Pursuit（简称MP）算法和Orthogonal Matching Pursuit（简称OMP）算法，这两种算法贪婪的按顺序选择字典中的每一列，计算过程中会涉及到字典列${\bf{d}}_{i}$di​与原始样本$\bf{y}$y的内积，并且包括最小二乘法的应用。第二个经典的追踪算法是Basic Pursuit（简称BP）算法，他通过将式（1）和（2）中的$L_0$L0​正则项替换为$L_1$L1​正则项，来使得问题“凸化”（convexification），Focal Under-determined System Solver (简称FOCUSS)与上述算法很相似，在FOCUSS中使用$L_p$Lp​正则项（ $p\leq{1}$p≤1 ）替换$L_0$L0​正则项，在稀疏编码问题中，$p&lt;1$p<1可以使得该方法求得的解与真实解更为接近，但是会使得问题变为“非凸”（non-convex），而且有可能最终陷入局部最优之中。另外，这两种算法可以采用Maximum A Posteriori（简称MAP）估计的思想来求解上述问题，MAP通过最大化后验概率

$P({\bf{x}}|{\bf{y}},{\bf{D}})\propto{P({\bf{y}}|{\bf{D}},{\bf{x}})P({\bf{x}})}$P(x∣y,D)∝P(y∣D,x)P(x)

来对优化目标${\bf{x}}$x直接进行估计求解，该算法假定${\bf{x}}$x的各个分量满足高斯分布而且是独立同分布的。之前介绍过的Lagrange Multipliers可以将约束条件转化为惩罚项加入到优化目标中，然后迭代的执行带权最小二乘法，采用类似于解决带有$L_2$L2​正则项优化问题的方法解决上述问题，这个算法类似于之前介绍过的“近端梯度下降”（Proximal Gradient Descent，简称PGD）。
  实验证明上述算法在稀疏化样本$\bf{x}$x足够稀疏时会有更好的表现，而字典矩阵$\bf{D}$D的好坏决定了$\bf{x}$x的稀疏度，进而影响了稀疏编码的性能，因此字典学习对于稀疏编码过程是十分重要的。

K-SVD算法

  通过前面的介绍，我们得知K-SVD算法是K-Means算法的一种拓展，那么是如何拓展的呢？之前在原型聚类算法族中介绍过K-Means，该算法的目标是求得一组可以代表原始数据集的“原型向量”，在这里我们将这些向量称为“向量量化”（Vector Quantization，简称VQ），每个VQ都与其所代表的各个样本点直接相关，即每个样本点都被划分到距离其最近的VQ下，令${\bf{y}}_{i}\in{\Bbb{R}}^{n}$yi​∈Rn代表第$i$i个原始样本，${\bf{D}}=\{{\bf{c}}_{1},{\bf{c}}_{2},\dots,{\bf{c}}_{K}\}\in{\Bbb{R}^{n\times{K}}}$D={c1​,c2​,…,cK​}∈Rn×K代表$K$K个VQ，那么有

${\bf{y}}_{i}\approx{{\bf{D}}{\bf{x}}_{i}} \tag{4}$yi​≈Dxi​(4)

其中，${\bf{x}}_{i}={\bf{e}}_{j}\in{\Bbb{R}^{K}}$xi​=ej​∈RK是一个第$j$j个分量为1的单位向量，而$j$j是${\bf{y}}_{i}$yi​所属的簇标记。上式与式（3）中的约束条件非常相似，但是式（3）中的向量$\bf{x}$x是任意$K$K维向量，因此，K-SVD是K-Means的一种拓展，下面首先简要回顾K-Means算法，然后再逐渐推广到K-SVD。

a. 向量量化的K-Means算法
  将${\bf{D}}=\{{\bf{c}}_{1},{\bf{c}}_{2},\dots,{\bf{c}}_{K}\}$D={c1​,c2​,…,cK​}看做一个字典，那么该字典的“词数”是$K$K，数据集中的所有样本点都围绕着（欧式）距离其最近的VQ（即字典中的“词”），即每个样本点属于且仅属于某个VQ，沿用之前的变量标志，上述讨论可以表示为

$\forall_{k\neq{j}}||{\bf{y}}_{i}-{\bf{D}}{\bf{e}}_{j}||^2_2\leq{||{\bf{y}}_{i}-{\bf{D}}{\bf{e}}_{k}||^2_2}$∀k̸​=j​∣∣yi​−Dej​∣∣22​≤∣∣yi​−Dek​∣∣22​

可以看出K-Means算法是稀疏编码的一种特殊情况，即只有一个词（原子）参与构建${\bf{y}}_{i}$yi​，并且${\bf{x}}_{i}$xi​中的相关系数被设置为1。这样，每个样本的稀疏编码的最小均方差（MSE）可以表示为

$e_{i}^{2}=||{\bf{y}}_{i}-{\bf{D}}{\bf{x}}_{i}||^2_2$ei2​=∣∣yi​−Dxi​∣∣22​

数据集整体稀疏编码的MSE可以表示为

$E=\sum_{i=1}^{N}{e_{i}^{2}}=\sum_{i=1}^{N}{||{\bf{y}}_{i}-{\bf{D}}{\bf{x}}_{i}||^2_2}=||{\bf{Y}}-{\bf{D}}{\bf{X}}||^2_F \tag{5}$E=i=1∑N​ei2​=i=1∑N​∣∣yi​−Dxi​∣∣22​=∣∣Y−DX∣∣F2​(5)

其中${\bf{Y}}\in{\Bbb{R}^{n\times{N}}}$Y∈Rn×N和${\bf{X}}\in{\Bbb{R}^{K\times{N}}}$X∈RK×N分别是原始数据集和稀疏化后的数据集，VQ的训练就是得到一个可以最小化式（5）的字典$\bf{D}$D，该优化目标可以表示为

$\min_{{\bf{D}},{\bf{X}}}{||{\bf{Y}}-{\bf{D}}{\bf{X}}||_{F}^{2}} \\ s.t.\quad\forall{i}\exists{k},{\bf{x}}_{i}={\bf{e}}_{k} \tag{6}$D,Xmin​∣∣Y−DX∣∣F2​s.t.∀i∃k,xi​=ek​(6)

  K-Means采用迭代交替更新的策略，即在每轮迭代中交替执行对字典$\bf{D}$D的更新和对数据集的重新稀疏化编码，可以证明式（6）中优化目标的下界是零，而且在迭代进行的过程中，该优化目标会单调递减或保持不变，算法伪代码如下图所示

图1 VQ的K-Means算法

上图中$J$J是当前迭代次数，每轮迭代分为两步：稀疏编码（Sparse Coding）和字典更新（Codebook Update），在稀疏编码阶段为每个样本${\bf{x}}_{i}$xi​分配给距离其最近的词${\bf{c}}_{j}(j=1,2,\dots,K)$cj​(j=1,2,…,K) ，并将其加入到集合$R_{j}(j=1,2,\dots,K)$Rj​(j=1,2,…,K)中，然后在下一阶段使用这些被分配到$R_{j}$Rj​中的原始样本的均值来更新所属词${\bf{c}}_{j}$cj​。

b. K-Means算法的泛化
  通过之前的讨论可知，普通的字典学习问题可以看做是上述问题的泛化，字典中的每个词都参与构建样本点${\bf{y}}_{i}$yi​，${\bf{x}}_{i}$xi​也不限于只有一个非零分量，即${\bf{y}}_{i}$yi​可以看做是词的线性组合，类似式（6）该问题可以表示为

$\min_{{\bf{D}},{\bf{X}}}{||{\bf{Y}}-{\bf{D}}{\bf{X}}||_{F}^{2}} \\ s.t.\quad\forall{i}\exists{k},||{\bf{x}}_{i}||_{0}&lt;T_{0} \tag{7}$D,Xmin​∣∣Y−DX∣∣F2​s.t.∀i∃k,∣∣xi​∣∣0​<T0​(7)

其中$T_0$T0​是预先设置好的阈值，如果将${\bf{x}}_{i}$xi​的稀疏度做为优化目标，那么根据式（2）的约束条件上式还可以写成如下形式

$\min_{{\bf{D}},{\bf{X}}}\sum_{i=1}^{m}{||{\bf{x}}_{i}||_{0}} \\ s.t.\quad{||{\bf{Y}}-{\bf{D}}{\bf{X}}||_{F}^{2}}&lt;\varepsilon \tag{8}$D,Xmin​i=1∑m​∣∣xi​∣∣0​s.t.∣∣Y−DX∣∣F2​<ε(8)

这篇文章着重对式（7）进行优化，同样采用类似K-Means中的迭代交替优化，在每轮迭代中，在“稀疏编码”阶段固定字典$\bf{D}$D，并对样本重新执行稀疏编码，可以采用任何一种可以求解该问题的追踪算法。
  在稀疏编码完成后就可以进入“字典更新”阶段了，这个阶段需要根据稀疏化样本$\bf{X}$X对字典$\bf{D}$D进行更新，方法是每次只将$\bf{D}$D中的某一列（一个词）${\bf{d}}_{k}$dk​更新为$\tilde{{\bf{d}}}_{k}$d~k​，同时保持字典$\bf{D}$D中的其他列（词）不变，这类似于其他泛化K-Means的字典学习方法，但是K-SVD与这些算法有一个很大的区别，他同时更新${\bf{d}}_{k}$dk​和“$\bf{X}$X中与${\bf{d}}_{k}$dk​相关的系数”，第二个更新项可以表示为$\{{\bf{x}}_{T}^{k}(i)|1\leq{i\leq{K}},{\bf{x}}_{T}^{k}(i)\neq{0}\}${xTk​(i)∣1≤i≤K,xTk​(i)̸​=0}，其中${\bf{x}}^{k}$xk表示矩阵$\bf{X}$X的第$k$k行（${\bf{x}}_{k}$xk​表示矩阵$\bf{X}$X的第$k$k列），${\bf{x}}^{k}(i)$xk(i)表示矩阵$\bf{X}$X的第$k$k行的第$i$i个分量，由于之后每次更新字典中的其他列都需要依赖上一次更新后的$\bf{X}$X，这是从梯度下降（Gradient Decent）到高斯-赛德尔优化方法（Gauss-Seidel Optimization Method）的转变，因此这种方法可以加快收敛速度。由于该阶段同时更新了字典$\bf{D}$D和稀疏化样本$\bf{X}$X，因此有些人认为可以将“稀疏编码”阶段跳过直接进行“字典学习”，由于稀疏化样本得不到恰当的更新，最终会导致算法陷入局部最优。

c. K-SVD算法详细描述
  现在对K-SVD进行更详细的公式推导，在“稀疏编码”阶段，由于式（7）中的优化目标可以写为如下形式

$||{\bf{Y}}-{\bf{D}}{\bf{X}}||_{F}^{2}=\sum_{i}{||{\bf{y}}_{i}-{\bf{D}}{\bf{x}}_{i}||_2^2}$∣∣Y−DX∣∣F2​=i∑​∣∣yi​−Dxi​∣∣22​

因此，假设字典$\bf{D}$D固定，式（6）可以拆分成$N$N个优化问题，

$\min_{{\bf{D}},{\bf{X}}}{||{\bf{y}}_{i}-{\bf{D}}{\bf{x}}_{i}||_{2}^{2}} \\ s.t.\quad||{\bf{x}}_{i}||_{0}&lt;T_{0} \\ (i=1,2,\dots,N) \tag{8}$D,Xmin​∣∣yi​−Dxi​∣∣22​s.t.∣∣xi​∣∣0​<T0​(i=1,2,…,N)(8)

这些优化问题可以通过任何一种追踪算法求解，而且当$T_{0}$T0​足够小时，可以得到真实解的最佳近似。
  在“字典更新”阶段，式（7）中的优化目标可以写为

$||{\bf{Y}}-{\bf{D}}{\bf{X}}||_{F}^{2}=||{\bf{Y}}-\sum_{j=1}^{K}{{\bf{d}}_{j}{\bf{x}}_{T}^{j}}||_{F}^{2} \\ =||({\bf{Y}}-\sum_{j=1,j\neq{k}}^{K}{{\bf{d}}_{j}{\bf{x}}_{T}^{j}})-{\bf{d}}_{k}{\bf{x}}_{T}^{k}||_{F}^{2} \\ =||{\bf{E}}_{k}-{\bf{d}}_{k}{\bf{x}}_{T}^{k}||_{F}^{2} \tag{9}$∣∣Y−DX∣∣F2​=∣∣Y−j=1∑K​dj​xTj​∣∣F2​=∣∣(Y−j=1,j̸​=k∑K​dj​xTj​)−dk​xTk​∣∣F2​=∣∣Ek​−dk​xTk​∣∣F2​(9)

其中，${\bf{E}}_{k}$Ek​是使用除了${\bf{d}}_{k}$dk​以外的所有列（词）来构建原始样本集$\bf{Y}$Y的误差矩阵，式（7）可以重新写为

$\min_{{\bf{d}}_{k}}{||{\bf{E}}_{k}-{\bf{d}}_{k}{\bf{x}}_{T}^{k}||_{F}^{2}} \\ s.t.\quad\forall{i},||{\bf{x}}_{i}||_{0}&lt;T_{0} \tag{10}$dk​min​∣∣Ek​−dk​xTk​∣∣F2​s.t.∀i,∣∣xi​∣∣0​<T0​(10)

于是最小化式（10）只需要对${\bf{E}}_{k}$Ek​进行奇异值分解（SVD）以取得最大奇异值对应的正交向量即为${\bf{d}}_{k}$dk​，但是直接对${\bf{E}}_{k}$Ek​进行奇异值分解会破坏稀疏化样本集$\bf{X}$X的稀疏性，因此K-SVD采用另一种解决方法，令$\omega_k$ωk​表示原始样本集中那些由${\bf{d}}_{k}$dk​参与构建的样本的索引值集合，即

$\omega_k=\{i|1\leq{i\leq{N}},{\bf{x}}_{T}^{k}(i)\neq{0}\} \tag{11}$ωk​={i∣1≤i≤N,xTk​(i)̸​=0}(11)

下面构造这样一个矩阵${\bf{\Omega}}_{k}\in{\Bbb{R}}^{N\times{|\omega_k|}}$Ωk​∈RN×∣ωk​∣ ，矩阵中位于$(\omega_{k}(i),i)$(ωk​(i),i)上的这些元素全部赋值为1，其他位元素全部赋值为0，例如，词${\bf{d}}_{k}$dk​参与了所有原始样本的构建，那么$\omega_{k}=\{1,2,\dots,N\}$ωk​={1,2,…,N}，${\bf{\Omega}}_{k}\in{\Bbb{R}^{N\times{N}}}$Ωk​∈RN×N成为一个对角矩阵，且对角线上的所有元素的值为1。
  由于在该阶段字典中的词是依次更新的，因此当${\bf{d}}_{k}$dk​需要更新时，我们只需要关注与${\bf{d}}_{k}$dk​有关的系数即可，因此令${\bf{x}}_{R}^{k}\in{\Bbb{R}^{|\omega_{k}|}}$xRk​∈R∣ωk​∣仅包含${\bf{x}}_{T}^{k}$xTk​中那些与${\bf{d}}_{k}$dk​有关的分量，令${\bf{Y}}_{k}^{R}\in{\Bbb{R}^{n\times{|\omega_{k}|}}}$YkR​∈Rn×∣ωk​∣仅包含$\bf{Y}$Y中${\bf{d}}_{k}$dk​参与构建的原始样本，令${\bf{E}}_{k}^{R}\in{\Bbb{R}^{n\times{|\omega_{k}|}}}$EkR​∈Rn×∣ωk​∣仅包含${\bf{E}}_{k}$Ek​中与${\bf{d}}_{k}$dk​有关的误差，式（9）所示的优化目标可以写为

$||{\bf{E}}_{k}-{\bf{d}}_{k}{\bf{x}}_{T}^{k}||^2_F=||{\bf{E}}_{k}{\bf{\Omega}}_{k}-{\bf{d}}_{k}{\bf{x}}^{k}_{T}{\bf{\Omega}}_{k}||^2_F=||{\bf{E}}_{k}^{R}-{\bf{d}}_{k}{\bf{x}}_{R}^{k}||^2_F \tag(12)$∣∣Ek​−dk​xTk​∣∣F2​=∣∣Ek​Ωk​−dk​xTk​Ωk​∣∣F2​=∣∣EkR​−dk​xRk​∣∣F2​12)(()

这样就可以直接对${\bf{E}}_{k}^{R}$EkR​执行SVD来求得$\tilde{\bf{d}}_{k}$d~k​和${\bf{x}}_{R}^{k}$xRk​了，假设${\bf{E}}_{k}^{R}={\bf{U}}{\bf{\Delta}}{\bf{V}}^{T}$EkR​=UΔVT，那么可以令${\bf{U}}$U的第一列作为$\tilde{\bf{d}}_{k}$d~k​，而令${\bf{\Delta}}(1,1)$Δ(1,1)与${\bf{V}}$V的第一列的乘积作为${\bf{x}}_{R}^{k}$xRk​。需要注意的是，在“字典更新”阶段之前要保证字典中的词是经过正规化后的（一般采用$L_2$L2​正规化），并且保证在迭代过程中矩阵$\bf{X}$X中的每个元素保持不变或者逐渐趋于零，这样才能满足稀疏化条件。算法伪代码如下图所示

图2 K-SVD算法伪代码

实验证明该算法的并行版本，即在“字典更新”阶段保持$\bf{X}$X不变，只对$\bf{D}$D进行更新，是可行的，但是所得结果比较差。

---

参考资料

【1】 Aharon, M. , M. Elad , and A. Bruckstein . “K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation.” IEEE Transactions on Signal Processing 54.11(2006):4311-4322.