【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.稀疏表示与字典学习
不妨把数据集$D$考虑成一个矩阵，其每行对应于一个样本，每列对应于一个特征。特征选择所考虑的问题是特征具有“稀疏性”，即矩阵中的许多列与当前学习任务无关，通过特征选择去除这些列，则学习器训练过程仅需在较小的矩阵上进行，学习任务的难度可能有所降低，涉及的计算和存储开销会减少，学得模型的可解释性也会提高。
现在我们来考虑另一种稀疏性：$D$所对应的矩阵中存在很多零元素，但这些零元素并不是以整列、整行形式存在的。在不少现实应用中我们会遇到这样的情形，例如在文档分类任务中，通常将每个文档看作一个样本，每个字（词）作为一个特征，字（词）在文档中出现的频率或次数作为特征的取值；换言之，$D$所对应的矩阵的每行是一个文档，每列是一个字（词），行、列交汇处就是某字（词）在某文档中出现的频率或次数。那么，这个矩阵有多少列呢？以汉语为例，《康熙字典》中有47035个汉字，这意味着该矩阵可有4万多列，即便仅考虑《现代汉语常用字表》中的汉字，该矩阵也有3500列。然而，给定一个文档，相当多的字是不出现在这个文档中的，于是矩阵的每一行都有大量的零元素；对不同的文档，零元素出现的列往往很不相同。
当样本具有这样的稀疏表达形式时，对学习任务来说会有不少好处，例如线性支持向量机之所以能在文本数据上有很好的性能，恰是由于文本数据在使用上述的字频表示后具有高度的稀疏性，使大多数问题变得线性可分。同时，稀疏样本并不会造成存储上的巨大负担，因为稀疏矩阵已有很多高效的存储方法。
那么，若给定数据集$D$是稠密的，即普通非稀疏数据，能否将其转化为“稀疏表示”（sparse representation）形式，从而享有稀疏性所带来的好处呢？需注意的是，我们所希望的稀疏表示是“恰当稀疏”，而不是“过度稀疏”。仍以汉语文档为例，基于《现代汉语常用字表》得到的可能是恰当稀疏，即其稀疏性足以让学习任务变得简单可行；而基于《康熙字典》则可能是过度稀疏，与前者相比，也许并未给学习任务带来更多的好处。
显然，在一般的学习任务中（例如图像分类）并没有《现代汉语常用字表》可用，我们需学习出这样一个“字典”。为普通稠密表达的样本找到合适的字典，将样本转化为合适的稀疏表示形式，从而使学习任务得以简化，模型复杂度得以降低，通常称为“字典学习”（dictionary learning），亦称“稀疏编码”（sparse coding）。这两个称谓稍有差别，“字典学习”更侧重于学得字典的过程，而“稀疏编码”则更侧重于对样本进行稀疏表达的过程。由于两者通常是在同一个优化求解过程中完成的，因此下面我们不做进一步区分，笼统地称为字典学习。
字典亦称“码书”（codebook）。
字典学习亦称“码书学习”（codebook learning）。
给定数据集$\{\mathbf{x}_1, \mathbf{x}_2, … , \mathbf{x}_m \}$，字典学习最简单的形式为：
\[\min_{\mathbf{B,\alpha_i}} \sum_{i=1}^m \parallel \mathbf{x}_i - \mathbf{B \alpha}_i \parallel _2^2 + \lambda \sum_{i=1}^m \parallel \mathbf{\alpha}_i \parallel_1 \tag{1}\]其中$\mathbf{B} \in \mathbb{R}^{d \times k}$为字典矩阵，$k$称为字典的词汇量，通常由用户指定，$\mathbf{\alpha_i} \in \mathbb{R}^k$则是样本$\mathbf{x}_i \in \mathbb{R}^d$的稀疏表示。显然，式(1)的第一项是希望由$\mathbf{\alpha}_i$能很好地重构$\mathbf{x}_i$，第二项则是希望$\mathbf{\alpha}_i$尽量稀疏。
与LASSO相比，式(1)显然麻烦得多，因为除了类似于这里式(3)中$\mathbf{w}$的$\mathbf{\alpha}_i$，还需学习字典矩阵$\mathbf{B}$。不过，受LASSO的启发，我们可采用变量交替优化的策略来求解式(1)。
首先在第一步，我们固定住字典$\mathbf{B}$，若将式(1)按分量展开，可看出其中不涉及$\alpha_i^u \alpha_i^v \ (u \neq v)$这样的交叉项，于是可参照LASSO的解法求解下式，从而为每个样本$\mathbf{x}_i$找到相应的$\mathbf{\alpha}_i$：
\[\min_{\mathbf{\alpha}_i} \parallel \mathbf{x}_i - \mathbf{B \alpha}_i \parallel_2^2 + \lambda \parallel \mathbf{\alpha}_i \parallel _1 \tag{2}\]在第二步，我们固定住$\mathbf{\alpha}_i$来更新字典$\mathbf{B}$，此时可将式(1)写为：
\[\min_{\mathbf{B}} \parallel \mathbf{X} - \mathbf{BA} \parallel _F ^2 \tag{3}\]其中$\mathbf{X} = (\mathbf{x}_1, \mathbf{x}_2 , … , \mathbf{x}_m) \in \mathbb{R}^{d\times m}, \ \mathbf{A} = (\mathbf{\alpha}_1, \mathbf{\alpha}_2, … , \mathbf{\alpha}_m) \in \mathbb{R}^{k \times m}$，$\parallel \cdot \parallel_F$是矩阵的Frobenius范数。式(3)有多种求解方法，常用的有基于逐列更新策略的KSVD。令$\mathbf{b}_i$表示字典矩阵$\mathbf{B}$的第$i$列，$\mathbf{\alpha}^i$表示稀疏矩阵$\mathbf{A}$的第$i$行，式(3)可重写为：
\[\begin{align} \min_{\mathbf{B}} \parallel \mathbf{X} - \mathbf{BA} \parallel _F^2 &= \min_{\mathbf{b}_i} \left \| \mathbf{X} - \sum_{j=1}^k \mathbf{b}_j \mathbf{\alpha}^j \right \| _F^2 \\&= \min_{\mathbf{b}_i} \left \| \left( \mathbf{X} - \sum_{j \neq i} \mathbf{b}_j \mathbf{\alpha}^j \right) - \mathbf{b}_i \mathbf{\alpha} ^i \right \| _F ^2 \\&= \min_{\mathbf{b}_i} \left \| \mathbf{E}_i - \mathbf{b}_i \mathbf{\alpha}^i \right \| _F ^2 \end{align} \tag{4}\]在更新字典的第$i$列时，其他各列都是固定的，因此$\mathbf{E}_i = \sum_{j\neq i} \mathbf{b}_j \mathbf{\alpha}^j$是固定的，于是最小化式(4)原则上只需对$\mathbf{E}_i$进行奇异值分解以取得最大奇异值所对应的正交向量。然而，直接对$\mathbf{E}_i$进行奇异值分解会同时修改$\mathbf{b}_i$和$\mathbf{\alpha}^i$，从而可能破坏$\mathbf{A}$的稀疏性。为避免发生这种情况，KSVD对$\mathbf{E}_i$和$\mathbf{\alpha}^i$进行专门处理：$\mathbf{\alpha}^i$仅保留非零元素，$\mathbf{E}_i$则仅保留$\mathbf{b}_i$与$\mathbf{\alpha}^i$的非零元素的乘积项，然后再进行奇异值分解，这样就保持了第一步所得到的稀疏性。
初始化字典矩阵$\mathbf{B}$之后反复迭代上述两步，最终即可求得字典$\mathbf{B}$和样本$\mathbf{x}_i$的稀疏表示$\mathbf{\alpha}_i$。在上述字典学习过程中，用户能通过设置词汇量$k$的大小来控制字典的规模，从而影响到稀疏程度。
2.式(4)的推导
这个公式难点在于推导$\mathbf{BA} = \sum_{j=1}^k \mathbf{b}_j \mathbf{\alpha}^j$。大致的思路是$\mathbf{b}_j \mathbf{\alpha}^j$会生成和矩阵$\mathbf{BA}$同样维度的矩阵，这个矩阵对应位置的元素是$\mathbf{BA}$中对应位置元素的一个分量，这样的分量矩阵一共有$k$个，把所有分量矩阵加起来就得到了最终结果。推导过程如下：
\[\begin{align} \mathbf{BA} &= \begin{bmatrix} b_1^1 & b_2^1 & \cdots & b_k^1 \\ b_1^2 & b_2^2 & \cdots & b_k^2 \\ \vdots & \vdots & \ddots & \vdots \\ b_1^d & b_2^d & \cdots & b_k^d \\ \end{bmatrix}_{d \times k} \cdot \begin{bmatrix} \alpha_1^1 & \alpha_2^1 & \cdots & \alpha_m^1 \\ \alpha_1^2 & \alpha_2^2 & \cdots & \alpha_m^2 \\ \vdots & \vdots & \ddots & \vdots \\ \alpha_1^k & \alpha_2^k & \cdots & \alpha_m^k \\ \end{bmatrix}_{k \times m} \\&= \begin{bmatrix} \sum_{j=1}^k b_j^1 \alpha_1^j & \sum_{j=1}^k b_j^1 \alpha_2^j & \cdots & \sum_{j=1}^k b_j^1 \alpha_m^j \\ \sum_{j=1}^k b_j^2 \alpha_1^j & \sum_{j=1}^k b_j^2 \alpha_2^j & \cdots & \sum_{j=1}^k b_j^2 \alpha_m^j \\ \vdots & \vdots & \ddots & \vdots \\ \sum_{j=1}^k b_j^d \alpha_1^j & \sum_{j=1}^k b_j^d \alpha_2^j & \cdots & \sum_{j=1}^k b_j^d \alpha_m^j \end{bmatrix}_{d\times m} \end{align}\] \[\begin{align} \mathbf{b}_j \mathbf{\alpha}^j &= \begin{bmatrix} b_j^1 \\ b_j^2 \\ \vdots \\ b_j^d \end{bmatrix} \cdot \begin{bmatrix} \alpha_1^j & \alpha_2^j & \cdots & \alpha_m^j \end{bmatrix} \\&= \begin{bmatrix} b_j^1 \alpha_1^j & b_j^1 \alpha_2^j & \cdots & b_j^1 \alpha_m^j \\ b_j^2 \alpha_1^j & b_j^2 \alpha_2^j & \cdots & b_j^2 \alpha_m^j \\ \vdots & \vdots & \ddots & \vdots \\ b_j^d \alpha_1^j & b_j^d \alpha_2^j & \cdots & b_j^d \alpha_m^j \end{bmatrix}_{d\times m} \end{align}\]求和可得：
\[\begin{align} \sum_{j=1}^k \mathbf{b}_j \mathbf{\alpha}^j &= \sum_{j=1}^k \begin{pmatrix} \begin{bmatrix} b_j^1 \\ b_j^2 \\ \vdots \\ b_j^d \end{bmatrix} \cdot \begin{bmatrix} \alpha_1^j & \alpha_2^j & \cdots & \alpha_m^j \end{bmatrix} \end{pmatrix} \\&= \begin{bmatrix} \sum_{j=1}^k b_j^1 \alpha_1^j & \sum_{j=1}^k b_j^1 \alpha_2^j & \cdots & \sum_{j=1}^k b_j^1 \alpha_m^j \\ \sum_{j=1}^k b_j^2 \alpha_1^j & \sum_{j=1}^k b_j^2 \alpha_2^j & \cdots & \sum_{j=1}^k b_j^2 \alpha_m^j \\ \vdots & \vdots & \ddots & \vdots \\ \sum_{j=1}^k b_j^d \alpha_1^j & \sum_{j=1}^k b_j^d \alpha_2^j & \cdots & \sum_{j=1}^k b_j^d \alpha_m^j \end{bmatrix}_{d\times m} \end{align}\]得证。
将矩阵$\mathbf{B}$分解成矩阵列$\mathbf{b}_j, j=1,2,…,k$带来一个好处，即矩阵列与列之间无关，因此可以分别优化各个列，即将$\min_{\mathbf{B}} \left | … \mathbf{B} … \right |_F^2$转化成了$\min_{\mathbf{b}_i} \left | … \mathbf{b}_i … \right | _F^2$，得到第三行的等式之后，再利用KSVD算法求解即可。
3.KSVD
字典矩阵$\mathbf{B}$中的每一列$\mathbf{b}_j$也称为原子（atom）。KSVD主要是以奇异值分解为核心来逐列更新字典矩阵的原子。
针对式(4)，我们进行如下处理：$\mathbf{\alpha}^i$仅保留非零元素，$\mathbf{E}_i$则仅保留$\mathbf{b}_i$与$\mathbf{\alpha}^i$的非零元素的乘积项。
因此式(4)的优化目标就变为了：
\[\min_{\mathbf{b}_i} \left \| \mathbf{E}'_i - \mathbf{b}_i \mathbf{\alpha}^{'i} \right \| _F ^2\]接下来对$\mathbf{E}’_i$进行奇异值分解分解：
\[\mathbf{E}'_i = U \Sigma V^T\]我们把最大的奇异值记为$\sigma_{max}$，其对应的左奇异向量为$U$的第一列，记为$u_{max}$，对应的右奇异向量为$V$的第一列，记为$v_{max}$。则我们更新$\mathbf{b}_i$和$\mathbf{\alpha}^{‘i}$为：
\[\mathbf{b}_i = u_{max}\] \[\mathbf{\alpha}^{'i} = \sigma_{max} v_{max}^T\]这样我们只更新了$\mathbf{\alpha}^i$的非零部分，从而没有破坏$\mathbf{A}$的稀疏性。并且，我们可以看到，在字典更新这一步，$\mathbf{b}_i$和$\mathbf{\alpha}^i$都会被更新。
我们之所以用最大奇异值对应的向量更新$\mathbf{b}_i$和$\mathbf{\alpha}^{‘i}$，是因为第一列的奇异值分解代表了最大贡献的方向，这样能最小化重建误差，即尽可能的接近$\mathbf{E}’_i$。
