五、稀疏表示和字典学习

1. 对于 。构

   建矩阵 ，其内容为：

   

   其中每一行对应一个样本，每一列对应一个特征。

2. 特征选择所考虑的问题是：矩阵 中的许多列与当前学习任务无关。

   通过特征选择去除这些列，则学习器训练过程仅需要在较小的矩阵上进行。这样学习任务的难度可能有所降低，涉及的计算和存储开销会减少，学得模型的可解释性也会提高。

3. 考虑另一种情况： 中有大量元素为 0 ，这称作稀疏矩阵。

   当数据集具有这样的稀疏表达形式时，对学习任务来讲会有不少好处：

   • 如果数据集具有高度的稀疏性，则该问题很可能是线性可分的。对于线性支持向量机，这种情况能取得更佳的性能。
   • 稀疏样本并不会造成存储上的巨大负担，因为稀疏矩阵已经有很多很高效的存储方法。

4. 现在问题是：如果给定数据集 是稠密的（即普通的、非稀疏的），则能否将它转化为稀疏的形式？

   这就是字典学习 dictionary learning和稀疏编码sparse coding的目标。

5.1 原理

1. 字典学习：学习一个字典，通过该字典将样本转化为合适的稀疏表示形式。它侧重于学得字典的过程。

   稀疏编码：获取样本的稀疏表达，不一定需要通过字典。它侧重于对样本进行稀疏表达的过程。

   这两者通常是在同一个优化求解过程中完成的，因此这里不做区分，统称为字典学习。

2. 给定数据集 ，希望对样本 学习到它的一个稀疏表示 。其中 是一个 维列向量，且其中大量元素为 0 。

   一个自然的想法进行线性变换，即寻找一个矩阵 使得 。

3. 现在的问题是：既不知道变换矩阵 ，也不知道 的稀疏表示 。

   因此求解的目标是：

   • 根据 能正确还原 ，或者还原的误差最小。
   • 尽量稀疏，即它的分量尽量为零。

   因此给出字典学习的最优化目标：

   

   其中 称作字典矩阵。 称作字典的词汇量，通常由用户指定来控制字典的规模，从而影响到稀疏程度。

   • 上式中第一项希望 能够很好地重构 。
   • 第二项则希望 尽可能稀疏。

5.2 算法

1. 求解该问题采用类似LASSO的解法，但是使用变量交替优化的策略：

   • 第一步：固定字典 ， 为每一个样本 找到相应的 ：

     

   • 第二步：根据下式，以 为初值来更新字典 ，即求解： 。

     其中 ， 。写成矩阵的形式为：

     

     这里 为矩阵的 Frobenius范数（所有元素的平方和的平方根）。对于矩阵 ， 有

   • 反复迭代上述两步，最终即可求得字典 和样本 的稀疏表示 。

2. 这里有个最优化问题：

   

   该问题有多种求解方法，常用的有基于逐列更新策略的KSVD算法。

   令 为字典矩阵 的第 列， 表示稀疏矩阵 的第 行。 固定 其他列，仅考虑第 列，则有：

   

   令 ，它表示去掉 的稀疏表示之后，样本集的稀疏表示与原样本集的误差矩阵。

   考虑到更新字典的第 列 时，其他各列都是固定的，则 是固定的。则最优化问题转换为：

   

   求解该最优化问题只需要对 进行奇异值分解以取得最大奇异值所对应的正交向量。

3. 直接对 进行奇异值分解会同时修改 和 ， 从而可能破坏 的稀疏性。因为第二步 “以 为初值来更新字典 ” 中， 在更新 前后 的非零元所处的位置和非零元素的值很可能不一致。

   为避免发生这样的情况 KSVD 对 和 进行了专门处理：

   • 仅保留非零元素。
   • 仅保留 和 的非零元素的乘积项，然后再进行奇异值分解，这样就保持了第一步得到的稀疏性。