Dictionary Learning详解（附带K-SVD算法）

Dictionary Learning详解

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

预备知识：

$L_0$范数

  $||\mathbf{x}|{|}_0=$向量$\mathbf{x}$中非零分量的数量

Frobenius（弗罗贝尼乌斯）范数

  对于矩阵$\mathbf{X}\in {\mathbb{R}}^{m\times n}$，$||\mathbf{X}|{|}_F=({\sum }_{i=1}^m{\sum }_{j=1}^n{x}_{ij}^2{)}^{1/2}$，并且$||\mathbf{X}|{|}_F^2={\sum }_{j=1}^n||{\mathbf{x}}^j|{|}_2^2={\sum }_{i=1}^m||{\mathbf{x}}_i|{|}_2^2$，其中${\mathbf{x}}_i$和${\mathbf{x}}^j$分别为$\mathbf{X}\in {\mathbb{R}}^{m\times n}$的行向量和列向量。

推导过程：

字典学习与稀疏编码

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

K-SVD简介

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

$$\underset{\mathbf{x}}{\min }||\mathbf{x}|{|}_0$$

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

$$\begin{gathered} (P_0)\underset{\mathbf{x}}{\min }||\mathbf{x}|{|}_0 \\ s.t.\mathbf{y}=\mathbf{D}\mathbf{x}\text{\hspace{1em}(1)} \end{gathered}$$

或者

$$\begin{gathered} (P_{0,\epsilon })\underset{\mathbf{x}}{\min }||\mathbf{x}|{|}_0 \\ s.t.||\mathbf{y}-\mathbf{D}\mathbf{x}|{|}_p\le \epsilon \text{\hspace{1em}(2)} \end{gathered}$$

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

$$\begin{gathered} (P_{0,\epsilon })\underset{\mathbf{x}}{\min }||\mathbf{x}|{|}_0 \\ s.t.||\mathbf{y}-\mathbf{D}\mathbf{x}|{|}_2\le \epsilon \text{\hspace{1em}(3)} \end{gathered}$$

  稀疏编码广泛的应用于压缩、识别以及特征提取领域，用于求解这类问题的、最具有代表性的追踪算法（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）是根据原始样本$\mathbf{y}$以及字典$\mathbf{D}$，求得原始样本的稀疏表示$\mathbf{x}$的过程，该过程类似于“原子分解”（Atom Decomposition），需要解决式（1）或（2）的优化问题，获得上述问题的精确解被证明是NP-hard的，因此经典的解法是采用可以获得近似解的“追踪算法”（Pursuit Algorithm）。
  追踪算法中最简单的是Matching Pursuit（简称MP）算法和Orthogonal Matching Pursuit（简称OMP）算法，这两种算法贪婪的按顺序选择字典中的每一列，计算过程中会涉及到字典列${\mathbf{d}}_i$与原始样本$\mathbf{y}$的内积，并且包括最小二乘法的应用。第二个经典的追踪算法是Basic Pursuit（简称BP）算法，他通过将式（1）和（2）中的$L_0$正则项替换为 L 1 L_1 L