Question

1. 对于 $ MathJax-Element-313 $ 。构

   建矩阵 $ MathJax-Element-314 $ ，其内容为：

   $ \mathbf D=\begin{bmatrix} x_{1,1}&x_{1,2}&\cdots&x_{1,n}\\ x_{2,1}&x_{2,2}&\cdots&x_{2,n}\\ \vdots&\vdots&\ddots&\vdots\\ x_{N,1}&x_{N,2}&\cdots&x_{N,n}\\ \end{bmatrix} $

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

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

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

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

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

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

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

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

5.1 原理

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

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

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

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

   一个自然的想法进行线性变换，即寻找一个矩阵 $ MathJax-Element-323 $ 使得 $ MathJax-Element-324 $ 。

3. 现在的问题是：既不知道变换矩阵 $ MathJax-Element-325 $ ，也不知道 $ MathJax-Element-359 $ 的稀疏表示 $ MathJax-Element-371 $ 。

   因此求解的目标是：
   

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

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

   $ \min_{\mathbf B,\vec{\alpha}_i}\sum_{i=1}^{N} ||\mathbf{\vec x}_i-\mathbf B\vec{\alpha}_i||_2^{2}+\lambda\sum_{i=1}^{N}||\vec \alpha_i||_1 $

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

   • 上式中第一项希望 $ MathJax-Element-371 $ 能够很好地重构 $ MathJax-Element-359 $ 。
   • 第二项则希望 $ MathJax-Element-371 $ 尽可能稀疏。

5.2 算法

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

   • 第一步：固定字典 $ MathJax-Element-370 $ ， 为每一个样本 $ MathJax-Element-359 $ 找到相应的 $ MathJax-Element-371 $ ：

     $ \min_{\vec \alpha_i} ||\mathbf{\vec x}_i-\mathbf B\vec{\alpha}_i||_2^{2}+\lambda\sum_{i=1}^{N}||\vec \alpha_i||_1 $

   • 第二步：根据下式，以 $ MathJax-Element-371 $ 为初值来更新字典 $ MathJax-Element-370 $ ，即求解： $ MathJax-Element-341 $ 。

     其中 $ MathJax-Element-342 $ ， $ MathJax-Element-343 $ 。写成矩阵的形式为：

     $ \mathbf X=\begin{bmatrix} x_{1,1}&x_{2,1}&\cdots&x_{N,1}\\ x_{1,2}&x_{2,2}&\cdots&x_{N,2}\\ \vdots&\vdots&\ddots&\vdots\\ x_{1,n}&x_{2,n}&\cdots&x_{N,n} \end{bmatrix}\quad \mathbf A=\begin{bmatrix} \alpha_{1,1}&\alpha_{2,1}&\cdots&\alpha_{N,1}\\ \alpha_{1,2}&\alpha_{2,2}&\cdots&\alpha_{N,2}\\ \vdots&\vdots&\ddots&\vdots\\ \alpha_{1,n}&\alpha_{2,n}&\cdots&\alpha_{N,n} \end{bmatrix}\\ $

     这里 $ MathJax-Element-344 $ 为矩阵的 Frobenius范数（所有元素的平方和的平方根）。对于矩阵 $ MathJax-Element-345 $ ， 有 $ MathJax-Element-346 $

   • 反复迭代上述两步，最终即可求得字典 $ MathJax-Element-370 $ 和样本 $ MathJax-Element-359 $ 的稀疏表示 $ MathJax-Element-349 $ 。

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

   $ \min_{\mathbf B}||\mathbf X-\mathbf B\mathbf A||_F^{2} $

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

   令 $ MathJax-Element-376 $ 为字典矩阵 $ MathJax-Element-370 $ 的第 $ MathJax-Element-360 $ 列， $ MathJax-Element-353 $ 表示稀疏矩阵 $ MathJax-Element-367 $ 的第 $ MathJax-Element-355 $ 行。 固定 $ MathJax-Element-356 $ 其他列，仅考虑第 $ MathJax-Element-360 $ 列，则有：

   $ \min_{\mathbf {\vec b}_i}||\mathbf X-\sum_{j=1}^{k}\mathbf {\vec b}_i\mathbf{\vec a}^{j}||_F^{2} =\min_{\mathbf {\vec b}_i}||(\mathbf X-\sum_{j=1,j\ne i}^{k}\mathbf {\vec b}_i\mathbf{\vec a}^{j})-\mathbf {\vec b}_i\mathbf{\vec a}^{i}||_F^{2} $

   令 $ MathJax-Element-358 $ ，它表示去掉 $ MathJax-Element-359 $ 的稀疏表示之后，样本集的稀疏表示与原样本集的误差矩阵。

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

   $ \min_{\mathbf {\vec b}_i}||\mathbf E_i-\mathbf {\vec b}_i\mathbf{\vec a}^{i} ||_F^{2} $

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

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

   为避免发生这样的情况 KSVD 对 $ MathJax-Element-375 $ 和 $ MathJax-Element-377 $ 进行了专门处理：
   

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