稀疏表示与字典学习

【稀疏表示】

将数据集 $D$ 考虑成一个矩阵，其每行对应于一个样本，每列对应于一个特征，特征选择所考虑的问题是特征具有稀疏性，即矩阵中的诸多列与当前学习任务无关，通过特征选择去除这些列，则模型训练过程仅需在较小的矩阵上进行，训练的难度可能会有所降低，涉及的计算和存储开销也会减少，学习到的模型的可解释性也会提高

考虑另一种稀疏性，即 $D$ 所对应的矩阵中存在诸多零元素，但这些零元素并非以整行、整列的形式存在，当数据集具有这样稀疏表达形式时，与特征选择去除某些特征类似，对于训练过程来说会有不少好处，同时稀疏样本并不会造成存储上的巨大负担

假设给定的数据集 $D$ 是稠密的，如果能学习出一个“字典”，将样本转换为合适的稀疏表示（Sparse Representation）形式，从而使得学习任务得以简化，模型复杂度得以降低，这被称为字典学习（Dictionary learning），或稀疏编码（Sparse coding）

这两种称呼稍有区别，字典学习更侧重于习得字典的过程，而稀疏编码更侧重于对样本进行稀疏表达的过程，由于两者通常是在同一个优化求解过程中完成的，因此通常不做进一步区分

需要注意的是，对于稀疏表示来说，恰当的稀疏性足以让学习任务变得简单可行，而过度的稀疏性未必能给学习任务带来更多的好处

【字典学习】

基本形式

给定数据集 $D=\{\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_n\}$，字典学习的最简单形式为：

$$\min_{\mathbf{B},\boldsymbol{\alpha}_i} \sum_{i=1}^n \Vert \mathbf{x}_i - \mathbf{B}\boldsymbol{\alpha}_i \Vert_2^2 + \lambda \sum_{i=1}^n \Vert \boldsymbol{\alpha_i} \Vert_1$$

其中，$\mathbf{B}\in \mathbb{R}^{d\times k}$ 为字典矩阵；$k$ 为超参，称为字典的词汇量，用于控制字典的规模，以影响稀疏程度；$\boldsymbol{\alpha}_i\in\mathbb{R}^k$ 是样本 $\mathbf{x}_i\in \mathbb{R}^d$ 的稀疏表示

在上式中，第一项的目标是希望通过 $\boldsymbol{\alpha}_i$ 能够很好地重构 $\mathbf{x}_i$，第二项的目标则是希望 $\boldsymbol{\alpha}_i$ 尽量稀疏

求解方法

受坐标下降法的启发，通常采用变量交替优化的策略来求解上式

首先，固定字典 $\mathbf{B}$，将上式按照分量展开，可以看出其中不涉及 $\alpha_i^u,\alpha_i^v,u\neq v$ 这样的交叉项，即：

$$\min_{\boldsymbol{\alpha}_i} \Vert \mathbf{x}_i-\mathbf{B}\boldsymbol{\alpha}_i \Vert_2^2+\lambda\Vert \boldsymbol{\alpha}_i \Vert_1$$

该式可参考坐标下降法求解，从而为每个样本 $\mathbf{x}_i$ 找到相应的 $\boldsymbol{\alpha}_i$

接着，固定 $\boldsymbol{\alpha}_i$ 来更新 $\mathbf{B}$​，此时有：

$$\min_{\mathbf{B}} \Vert \mathbf{X}-\mathbf{B}\mathbf{A} \Vert_F^2$$

其中，$\mathbf{X}=(\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_n)\in \mathbb{R}^{d\times n}$，$\mathbf{A}=(\boldsymbol{\alpha}_1,\boldsymbol{\alpha}_2,\cdots,\boldsymbol{\alpha}_n)\in\mathbb{R}^{k\times n}$

该式有多种求解方法，常用的有基于 K-Means 与 SVD 算法思想的逐列更新策略的 K-SVD 算法，即令 $\mathbf{b}_i$ 表示字典矩阵 $\mathbf{B}$ 的第 $i$ 列，$\boldsymbol{\alpha}^i$ 表示稀疏矩阵 $\mathbf{A}$ 的第 $i$ 行，此时有：

$$\begin{align*} \min_{\mathbf{B}} \Vert \mathbf{X}-\mathbf{B}\mathbf{A} \Vert_F^2 &= \min_{\mathbf{b}_i} \Vert \mathbf{X} - \sum_{j=1}^k\mathbf{b}_j\boldsymbol{\alpha}^j \Vert_F^2 \\ &= \min_{\mathbf{b}_i} \Vert (\mathbf{X} - \sum_{j\neq i}\mathbf{b}_j) - \mathbf{b}_i\boldsymbol{\alpha}^i \Vert_F^2 \\ &= \min_{\mathbf{b}_i} \Vert \mathbf{E}_i - \mathbf{b}_i \boldsymbol{\alpha}^i \Vert_F^2 \end{align*}$$

在更新字典的第 $i$ 列时，其他各列都是固定的，因此 $\mathbf{E}_i=\sum\limits_{j\neq i} \mathbf{b}_j \boldsymbol{\alpha}^j$ 是固定，因此最小化上式只需要对 $\mathbf{E}_i$​ 进行奇异值分解以取得最大奇异值所对应的正交向量

然而，直接对 $\mathbf{E}_i$ 进行奇异值分解会同时修改 $\mathbf{b}_i$ 与 $\boldsymbol{\alpha}^i$，从而可能破坏 $\mathbf{A}$ 的稀疏性

为避免发生这种情况，K-SVD 对 $\mathbf{E}_i$ 和 $\boldsymbol{\alpha}^i$ 进行专门处理，使 $\boldsymbol{\alpha}^i$ 仅保留非零元素，$\mathbf{E}_i$ 仅保留 $\mathbf{b}_i$ 与 $\boldsymbol{\alpha}^i$​ 的非零元素的乘积项，然后再进行奇异值分解，这样就保持了第一步所得到的稀疏性

在初始化字典矩阵 $\mathbf{B}$ 后，反复迭代上述两步，最终即可求得字典 $\mathbf{B}$ 和样本 $\mathbf{x}_i$ 的稀疏表示 $\boldsymbol{\alpha}_i$