稀疏表示与字典学习

在文档分类任务中，通常将每个文档看作一个样本，每个字（词）看做一个特征，其在文档中的频率或次数作为特征的取值。特征的个数也就是词汇量的个数，这样给定一个文档，相当多的字是不出现在这个文档中的，于是矩阵的每一行都有大量的零元素，对于不同的文档，零元素出现的列往往不同。
当样本具有这样的稀疏表达之后，对学习任务来说会有不少好处，例如线性支持向量机之所以能在文本数据中有很好的性能，恰是由于文本数据在使用上述的字频表示之后具有高度的稀疏性，是大多数问题变得线性可分。同时，稀疏样本并不会造成存储上的巨大负担，因为稀疏矩阵已有很多高效的存储方法。
若给定数据集\(D\)是稠密的，即普通非稀疏数据，我们希望将其转化为“稀疏表示”（sparse representation）形式，例如在文档分类任务中，我们可以基于《现代汉语常用字表》得到数据的恰当稀疏，而在一般学习任务中，我们需要学习出这样一个“字典”，为普通稠密表达的样本找到合适的字典，将样本转化为合适的稀疏表示形式，使学习任务得以简化，模型的复杂度得以降低，通常称为“字典学习”（dictionary learning），亦称“稀疏编码”（sparse coding）。字典学习更侧重于学得字典的过程，而稀疏编码更侧重于对样本进行稀疏表达的过程。

给定数据集\(\{\pmb{x}_1,\pmb{x}_2,\cdots,\pmb{x}_m\}\)，字典学习最简单的形式为 \[\min_{\mathbf{B},\pmb{\alpha}_i} \sum_{i=1}^m ||\pmb{x}_i - \mathbf{B} \pmb{\alpha}_i||_2^2 + \lambda \sum_{i=1}^m ||\pmb{\alpha}_i||_1\] 其中\(\mathbf{B} \in \mathbf{R}^{d \times k}\)为字典矩阵，\(k\)称为字典的词汇量，通常由用户指定，\(\pmb{\alpha}_i \in \mathbf{R}^k\)则是样本\(\pmb{x}_i \in \mathbf{R}^d\)的稀疏表示。上式第一项是希望由\(\pmb{\alpha}_i\)能很好地重构\(\pmb{x}_i\)，第二项则是希望\(\pmb{\alpha}_i\)尽量稀疏。

与LASSO相比，上式较为复杂，除了需要学习类似于\(\pmb{w}\)的\(\pmb{\alpha}_i\)，还需要学习字典矩阵\(\mathbf{B}\)。不过，受LASSO的启发，可采用变量交替优化的策略来求解。

首先第一步，固定字典\(\mathbf{B}\)，若将目标公式按分量展开，其中不涉及\(\alpha_i^u \alpha_i^v (u \neq v)\)这样的交叉项，于是可参照LASSO的解法求解下式，从而为每个样本\(\pmb{x}_i\)找到相应的\(\pmb{\alpha}_i\)： \[\min_{\pmb{\alpha}_i} ||\pmb{x}_i - \mathbf{B} \pmb{\alpha}_i||_2^2 + \lambda ||\pmb{\alpha}_i||_1\] 第二步，以\(\pmb{\alpha}_i\)为初值来更新字典\(\mathbf{B}\)，此时可将目标公式写为 \[\min_{\pmb{B}} ||\mathbf{X} - \mathbf{B} \mathbf{A}||_F^2\] 其中\(\mathbf{X} = (\pmb{x}_1, \pmb{x}_2, \cdots, \pmb{x}_m) \in \mathbf{R}^{d \times m}\)，\(\mathbf{A} = (\pmb{\alpha}_1, \pmb{\alpha}_2, \cdots, \pmb{\alpha}_m) \in \mathbf{R}^{k \times m}\)，\(||·||_F\)是矩阵的Frobenius范数，定义\(||\mathbf{A}||_F = \sqrt{\sum_{i=1}^m \sum_{j=1}^n |a_{ij}|^2 }\)，类似向量的\(L_2\)范数，可衡量矩阵的大小。
上式有多种求解方法，常用的有基于逐列更新策略的KSVD。令\(\pmb{b}_i\)表示字典矩阵\(\mathbf{B}\)的第\(i\)列，\(\pmb{\alpha}_i\)表示稀疏矩阵\(\mathbf{A}\)的第\(i\)行，上式重写为 \[\begin{align} \min_{\mathbf{B}} ||\mathbf{X} - \mathbf{B} \mathbf{A}||_F^2 &= \min_{\pmb{b}_i} ||\mathbf{X} - \sum_{j=1}^k \pmb{b}_j \pmb{\alpha}^j||_F^2 \nonumber \\ &= \min_{\pmb{b}_i} ||(\mathbf{X} - \sum_{j \neq i} \pmb{b}_j \pmb{\alpha}^j) - \pmb{b}_i \pmb{\alpha}^i||_F^2 \nonumber \\ &= \min_{\pmb{b}_i} ||\mathbf{E}_i - \pmb{b}_i \pmb{\alpha}^i||_F^2 \nonumber \end{align}\]

在更新字典的第\(i\)列时，其他各列都是固定的，因此\(\mathbf{E} = \mathbf{X} - \sum_{j \neq i} \pmb{b}_j \pmb{\alpha}^j\)是固定的，于是最小化上式原则上只需对\(\mathbf{E}_i\)进行奇异值分解以取得最大奇异值所对应的正交向量。然而，直接对\(\mathbf{E}_i\)进行奇异值分解会同时修改\(\pmb{b}_i\)和\(\pmb{\alpha}_i\)，从而可能破坏\(\mathbf{A}\)的稀疏性。为了避免这种情况，KSVD对\(\mathbf{E}_i\)和\(\pmb{\alpha}_i\)进行专门处理：\(\pmb{\alpha}_i\)仅保留非零元素，\(\mathbf{E}_i\)则仅保留\(\pmb{b}_i\)与\(\pmb{\alpha}_i\)的非零元素的乘积项，然后再进行奇异值分解，这样就保持了第一步所得到的稀疏性。

具体过程如下：
定义集合\(\pmb{w}_i = \{ j| 1 \leq j \leq N, \pmb{\alpha}^i(j) \neq 0\}\)为用到\(\pmb{b}_i\)所有信号集合\(\{\pmb{x}_i\}\)的索引所构成的集合，即\(\pmb{\alpha}^i(j) \neq 0\)的点的索引值。定义\(\mathbf{\Omega}_i\)为\(m \times |\pmb{w}_i|\)矩阵，他在\((\pmb{w}_i(j), j)\)处的值都为1，其他点为0。定义\(\pmb{\alpha}_R^i = \pmb{\alpha}^i \mathbf{\Omega}_i\)、\(\mathbf{X}_R^i = \mathbf{X} \mathbf{\Omega}_i\)、\(\mathbf{E}_R^i = \mathbf{E}_i \mathbf{\Omega}_i\)，则三者分别为\(\pmb{\alpha}^i\)、\(\mathbf{X}\)、\(\mathbf{E}_i\)中去掉零输入后的收缩结果，\(\mathbf{X}_R^i\)为当前用到原子\(\pmb{b}_i\)的样本集合，\(\mathbf{E}_R^i\)为去掉不受原子\(\pmb{b}_i\)影响的样本后，如果不考虑\(\pmb{b}_i\)在受其影响的样本中成分时，带来的误差。\(\pmb{\alpha}_R^i\)的长度为\(|\pmb{w}_i|\)，\(\mathbf{X}_R^i\)和\(\mathbf{E}_R^i\)是\(k \times |\pmb{w}_i|\)矩阵。 \[||\mathbf{E}_i \mathbf{\Omega}_i - \pmb{b}_i \pmb{\alpha}^i \mathbf{\Omega}_i||_F^2 = ||\mathbf{E}_R^i - \pmb{b}_i \pmb{\alpha}_R^i||_F^2\] \(\mathbf{E}_R^i\)做SVD分解，则\(\mathbf{E}_R^i = \mathbf{U} \Delta \mathbf{V}^T\)，，令\(\tilde{\pmb{b}}_i\)为\(\mathbf{U}\)的第一列，则\(\tilde{\pmb{b}}_i\)为\(\pmb{b}_i\)的更新结果。同时，用\(\mathbf{V}\)的第一列和\(\Delta(1,1)\)的乘积更新\(\pmb{\alpha}_R^i\)。在逐列更新完成后用新字典\(\tilde{\mathbf{B}}\)做稀疏分解，并判断是否达到停止条件（停止条件可以是既定的迭代次数后者重构信号和原信号之间的误差率），已决定迭代是否继续。
在上述字典学习过程中，用户能通过设置\(k\)的大小控制字典的规模，从而影响稀疏程度。