『ML笔记』深入浅出字典学习2(Dictionary Learning)

一、理解K-SVD字典学习

• 字典学习也可简单称之为稀疏编码，字典学习偏向于学习字典 $\mathbf{D}$。从矩阵分解角度，看字典学习过程：给定样本数据集 $\mathbf{Y}$，$\mathbf{Y}$ 的每一列表示一个样本；字典学习的目标是把 $\mathbf{Y}$ 矩阵分解成 $\mathbf{D}$、$\mathbf{X}$ 矩阵：
  $$\mathbf{Y}\approx \mathbf{D}\mathbf{X}\text{\hspace{1em}(1)}$$
• 同时满足约束条件：$\mathbf{X}$ 尽可能稀疏，同时 $\mathbf{D}$ 的每一列是一个归一化向量。$\mathbf{D}$ 称之为字典，$\mathbf{D}$ 的每一列称之为原子；$\mathbf{X}$ 称之为编码矢量、特征、系数矩阵；字典学习可以有三种目标函数形式

• 第一种形式
  $$\mathbf{D},\mathbf{X}=\mathrm{argmin}\frac{1}{2}\Vert \mathbf{Y}-\mathbf{D}\mathbf{X}{\Vert }^2+\lambda \cdot \Vert \mathbf{X}{\Vert }_0\text{\hspace{1em}(2)}$$ 注意：这种形式因为 $L_0$ 难以求解，所以很多时候用 $L_1$ 正则项替代近似。

• 第2种形式
  D , X = arg ⁡ min ⁡ D , X { ∥ X ∥ 0 } st. ∥ Y − D X ∥ 2 ≤ ε (3) \begin{array}{l}{\mathbf D, \mathbf X=\underset{ \mathbf D, \mathbf X}{\arg \min }\left\{\| \mathbf X\|_{0}\right\}} \\ {\text {st.} \quad\| \mathbf Y- \mathbf D \mathbf X\|^{2} \leq \varepsilon}\end{array}\tag{3} D,X=D,Xargmin​{
  ∥X∥0​}st.∥Y−DX∥2≤ε​(3)注意：$\epsilon$是重构误差所允许的最大值。

• 第3种形式
  $$\begin{array}{l}\mathbf{D},\mathbf{X}=\underset{\mathbf{D},\mathbf{X}}{\mathrm{argmin}}\Vert \mathbf{Y}-\mathbf{D}\mathbf{X}{\Vert }^2\\ \text{st. }\Vert \mathbf{X}{\Vert }_0\le L\end{array}\text{\hspace{1em}(4)}$$ 注意：$L$ 是一个常数，稀疏度约束参数，上面三种形式相互等价!

因为目标函数中存在两个未知变量$\mathbf{D},\mathbf{X}$，K-SVD是字典学习的一种经典算法，其求解方法跟lasso差不多，固定其中一个，然后更新另外一个变量，交替迭代更新。

• 1. 如果 $\mathbf{D}$ 的列数少于 $\mathbf{Y}$ 的行数，就相当于欠完备字典，类似于PCA降维；
• 2. 如果 $\mathbf{D}$ 的列数大于 $\mathbf{Y}$ 的行数，称之为超完备字典；
• 3. 如果刚好等于，那么就称之为完备字典;

• 假设现在有了一个$N\ast T$的过完备字典 $\mathbf{D}$（比如前面所述图像傅里叶变换的所有频率的波），一个要表示的对象 $y$（要还原的图像），求一套系数$x$，使得$y=\mathbf{D}\mathbf{x}$，这里 $y$ 是一个已知的长为 $N$ 的列向量，$\mathbf{x}$ 是一个未知的长为 $T$ 的列向量，解方程！这是一个 $T$ 个未知数，$N$ 个方程的方程组，$T>N$，所以是有无穷多解的，线性代数中这样的方程很熟悉了。 上面我就随便举了个 $N=5,T=8$ 的例子，用来随便感受下。
  $$\left[\begin{array}{l}1\\ 2\\ 3\\ 4\\ 5\end{array}\right]=\left[\begin{array}{llllllll}1& 2& 3& 4& 5& 6& 7& 8\\ 0& 1& 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 1\\ 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0\end{array}\right]\times \left[\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\\ x_5\\ x_6\\ x_7\\ x_8\end{array}\right]$$

• 这里可以引出一个名词，ill-posed problem(不适定问题)，即有多个满足条件的解，无法判断哪个解更加合适，这是更“落地”的应用场景，inverse problem(逆问题)，比如图像去噪，从噪声图中提取干净图。于是需要做一个约束。
• 加限制条件，要求 $\mathbf{x}$ 尽可能稀疏，怎么“稀疏”呢？就是 $\mathbf{x}$ 的 $0$ 尽可能多，即 $norm(x>0)$（零范数：非0元素个数）尽可能小。这样就有唯一解了吗？也还不是，如何能“约束”出各位合适的解，如何解，正是稀疏表示所研究的重点问题。比如后来有证明$D$满足一定条件情况下$x$满足 $norm(x,1)$即可还原原始数据等，这有不少大神开启这个领域的故事这里就不讲了。

二、K-SVD字典学习算法概述

• 给定训练数据 $\mathbf{Y}$，$\mathbf{Y}$ 的每一列表示一个样本，我们的目标是求解字典 $\mathbf{D}$ 的每一列(原子)。

2.1、随机初始化字典D

• 从样本集 $\mathbf{Y}$ 中随机挑选 $k$ 个样本，作为 $\mathbf{D}$ 的原子；并且初始化编码矩阵 $\mathbf{X}$ 为 $0$ 矩阵。

2.2、固定字典，求取每个样本的稀疏编码

• 编码过程采用如下公式：
  D , X = arg ⁡ min ⁡ D , X { ∥ X ∥ 0 } st. ∥ Y − D X ∥ 2 ≤ ε (5) \begin{array}{l}{\mathbf D, \mathbf X=\underset{ \mathbf D, \mathbf X}{\arg \min }\left\{\| \mathbf X\|_{0}\right\}} \\ {\text {st.} \quad\| \mathbf Y- \mathbf D \mathbf X\|^{2} \leq \varepsilon}\end{array}\tag{5} D,X=D,Xargmin​{
  ∥X∥0​}st.∥Y−DX∥2≤ε​(5)
• $\epsilon$ 是重构误差所允许的最大值。假设我们的单个样本是向量 $\mathbf{y}$，为了简单起见我们就假设原子只有这4个，也就是字典$\mathbf{D}=[{\alpha }_1、{\alpha }_2、{\alpha }_3、{\alpha }_4]$，且 $\mathbf{D}$ 是已经知道的；我们的目标是计算 $\mathbf{y}$ 的编码 $\mathbf{x}$，使得 $\mathbf{x}$ 尽量的稀疏。

• (1)、首先从${\alpha }_1、{\alpha }_2、{\alpha }_3、{\alpha }_4$中找出与向量 $\mathbf{y}$ 最近的那个向量，也就是分别计算点乘：$${\alpha }_1\ast \mathbf{y}、{\alpha }_2\ast \mathbf{y}、{\alpha }_3\ast \mathbf{y}、{\alpha }_4\ast \mathbf{y}$$ 然后求取最大值对应的原子$\alpha$。

• (2)、假设 ${\alpha }_2\ast \mathbf{y}$ 最大，那么我们就用 ${\alpha }_2$，作为我们的第一个原子，然后我们的初次编码向量就为：$$x_1=（0,b,0,0）$$b是一个未知参数。

• (3)、求解系数b：$$\mathbf{y}-b\ast {\alpha }_2=0$$ 方程只有一个未知参数$b$，是一个高度超静定方程，求解最小二乘问题。

• (4)、然后我们用$x_1$与${\alpha }_2$相乘重构出数据，然后计算残差向量：$$\mathbf{y}’=\mathbf{y}-b\ast {\alpha }_2$$ 如果残差向量y’满足重构误差阈值范围ε，那么就结束，否则就进入下一步；

• (5)、计算剩余的字典${\alpha }_1、{\alpha }_3、{\alpha }_4$与残差向量$\mathbf{y}’$的最近的向量，也就是计算
  $${\alpha }_1\ast \mathbf{y}’、{\alpha }_3\ast \mathbf{y}’、{\alpha }_4\ast \mathbf{y}’$$然后求取最大值对应的向量$\alpha$，假设${\alpha }_3\ast \mathbf{y}’$为最大值，那么就令新的编码向量为：$$x_2=（0,b,c,0）$$ $b、c$是未知参数。

• (6)、求解系数$b、c,$于是我们可以列出方程：
  $$\mathbf{y}-b\ast {\alpha }_2-c\ast {\alpha }_3=0$$方程中有两个未知参数$b、c$，我们可以进行求解最小二乘方程，求得$b、c$。

• (7)、更新残差向量 $\mathbf{y}’$：$$\mathbf{y}’=\mathbf{y}-b\ast {\alpha }_2-c\ast {\alpha }_3$$

• 如果 $\mathbf{y}’$ 的模长满足阈值范围，那么就结束，否则就继续循环，就这样一直循环下去。

2.3、逐列更新字典、并更新对应的非零编码

• 通过上面那一步，我们已经知道样本的编码。接着我们的目标是更新字典、同时还要更新编码。K-svd采用逐列更新的方法更新字典，就是当更新第$k$列原子的时候，其它的原子固定不变。假设我们当前要更新第$k$个原子$\alpha k$，令编码矩阵$X$对应的第$k$行为$xk$，则目标函数为：
  $$\Vert \mathbf{Y}-\mathbf{D}\mathbf{X}{\Vert }^2={\Vert \mathbf{Y}-\sum _{j=1}^{\mathrm{K}}{\alpha }_j\cdot {\mathbf{x}}_j\Vert }^2={\Vert \left(\mathbf{Y}-\sum _{j=k}{\alpha }_j\cdot {\mathbf{x}}_j\right)-{\alpha }_k\cdot {\mathbf{x}}_k\Vert }^2={\Vert {\mathbf{E}}_k-{\alpha }_k\cdot {\mathbf{x}}_k\Vert }^2$$
• 上面的方程，我们需要注意的是 ${\mathbf{x}}_k$ 不是把 $\mathbf{X}$ 一整行都拿出来更新（因为 ${\mathbf{x}}_k$ 中有的是零、有的是非零元素，如果全部抽取出来，那么后面计算的时候xk就不再保持以前的稀疏性了），所以我们只能抽取出非零的元素形成新的非零向量，然后 ${\mathbf{E}}_k$ 只保留 ${\mathbf{x}}_k$ 对应的非零元素项。

• 上面的方程，我们可能可以通过求解最小二乘的方法，求解 ${\alpha }_k$，不过这样有存在一个问题，我们求解的 ${\alpha }_k$不是一个单位向量，因此我们需要采用svd分解，才能得到单位向量 ${\alpha }_k$。进过svd分解后，我们以最大奇异值所对应的正交单位向量，作为新的 ${\alpha }_k$，同时我们还需要把系数编码 ${\mathbf{x}}_k$ 中的非零元素也给更新了(根据svd分解)。
  然后算法就在1和2之间一直迭代更新，直到收敛。

参考了作者：

• https://blog.csdn.net/abc13526222160/article/details/87936459
• https://blog.csdn.net/hjimce/article/details/50810129

今天的文章『ML笔记』深入浅出字典学习2(Dictionary Learning)分享到此就结束了，感谢您的阅读。