Sparse Coding.

稀疏编码(Sparse Coding)是指给定一组基向量\(A = [a_1,...,a_M]\)，将输入样本\(x \in \Bbb{R}^D\)表示为基向量的线性组合：

\[x = \sum_{m=1}^{M} {z_ma_m} = Az\]

其中基向量的系数\(z = (z_1,...,z_M)^T\)称为输入样本$x$的编码(encoding)，要求$z$是稀疏的；基向量\(A\)也称为字典(dictionary)。

稀疏编码的特点：

  1. 计算量：稀疏性可以极大地降低计算量。
  2. 可解释性：稀疏编码只有少数非零元素，相当于将输入样本表示为少数几个相关的特征。
  3. 特征选择：稀疏性可以实现特征的自动选择，只选择和输入样本最相关的少数特征。

本文目录：

  1. 生物学背景
  2. 损失函数
  3. 训练方法
  4. OMP算法

1. 生物学背景

稀疏编码是受哺乳动物视觉系统中简单细胞感受野启发的模型。

在哺乳动物的初级视觉皮层(Primary Visual Cortex)中，每个神经元仅对处于其感受野中特定的刺激信号（比如特定方向的边缘、条纹等特征）做出响应。

外界信息经过编码后仅有一小部分神经元激活，即外界刺激在视觉神经系统的表示具有很高的稀疏性。编码的稀疏性在一定程度上符合生物学的低功耗特性。

2. 损失函数

给定输入向量\(x^1,...,x^N\)，其稀疏编码的损失函数包括重构误差(Reconstruction error)和稀疏惩罚项(Sparsity penalty),定义为：

\[L(A,z) = \sum_{n=1}^{N} {(|| x^n-Az^n ||^2 + ηρ(z^n))}\]

其中\(z = [z^1,...,z^N]\)；$ρ$是一个衡量稀疏性的函数；$η$是一个超参数，用来控制稀疏性的强度。

稀疏性衡量函数有多种选择，最直接的衡量向量$z$稀疏性的函数是$l_0$范数，即$z$中非零元素的个数:

\[ρ(z) = \sum_{m=1}^{M} {I(| z_m | > 0)}\]

但$l_0$范数不满足连续可导，是一个NP-hard的组合优化问题，对较大规模数据无法直接求解；

为使求解稀疏性问题变得可行，在实际中，稀疏性衡量函数通常使用$l_1$范数，将一个组合优化问题放松到一个凸优化问题来求解：

\[ρ(z) = \sum_{m=1}^{M} {| z_m |}\]

从下图可以看出，对于$l_p$范数，$p$越小，范数在0附近对应参数越稀疏。

3. 训练方法

给定输入向量\(x^1,...,x^N\)，需要同时学习基向量$A$和每一个输入样本对应的稀疏编码\(z = [z^1,...,z^N]\)。

稀疏编码的训练过程一般采用交替优化的方法：

(1). 固定基向量$A$，对每个输入$x^n$，计算其对应的最优编码$z^n$：

\[z^n = \mathop{\arg \min}_{z^n} || x^n-Az^n ||^2 + ηρ(z^n)\]

(2). 固定编码$z^n$，计算其最优基向量$A$：

\[A = \mathop{\arg \min}_{A} \sum_{n=1}^{N} {|| x^n-Az^n ||^2} + λ\frac{1}{2}|| A ||^2\]

其中λ是正则化系数。

4. OMP算法

在给定输入向量\(x^1,...,x^N\)和基向量$A$时，求稀疏编码\(z = [z^1,...,z^N]\)也可以采用正交匹配追逐算法(Orthogonal Matching Pursuit, OMP)。

1. MP算法

匹配追逐算法(Matching Pursuit, MP)是对信号进行稀疏分解的方法之一，将信号在完备字典库(即基向量$A$)上进行分解。

(1)基向量选择

信号\(x \in \Bbb{H}\)，从字典矩阵\(A = [a_1,...,a_M]\)中选择一个最为匹配的基向量，满足:

\[| <x, a_{r_0}> | = sup_{i \in (1,...,k)} | <x, a_{r_k}> |\]

信号$x$就被分解为在最匹配基向量方向上的投影分量和垂直于该基向量方向的残差$R_1f$两部分，即:

\[x = <x, a_{r_0}> a_{r_0} + R_1f\]

(2)迭代分解

对残差\(R_1f\)进行同样的分解，第$k$步可以得到：

\[R_kf = <R_kf, a_{r_k}> a_{r_k} + R_{k+1}f\]

经过$k$步分解后，信号$x$被分解为：

\[x = \sum_{n=0}^{k} {<R_nf, a_{r_n}> a_{r_n}} + R_{k+1}f\]

若残差\(R_{k+1}f\)在可接受范围内，则得到稀疏编码\(z_{r_n} = <R_nf, a_{r_n}>\)。

MP算法的几点说明：

  1. 基向量$A$属于Hilbert空间\(\Bbb{H}\)，即定义了完备的内积空间；
  2. 基向量$A$事先归一化处理，内积常用于计算一个矢量在一个方向上的投影长度，这时方向的矢量必须是单位矢量；
  3. MP算法是收敛的,因为\(R_kf = <R_kf, a_{r_k}> a_{r_k} + R_{k+1}f\)而且\(R_{k+1}f\)和\(a_{r_k}\)正交,平方得到:
\[||R_kf ||^2 = || R_{k+1}f ||^2 + | <R_kf, a_{r_k}> |^2\]

得出每一个残差值比上一次的小，故而收敛。

MP算法的缺点：

信号(残差)在已选择的基向量进行垂直投影是非正交性的，这会使得每次迭代的结果并不少最优的而是次最优的，收敛需要很多次迭代。

2. OMP算法

正交匹配追逐算法(Orthogonal Matching Pursuit, OMP)改进了MP算法，在分解的每一步对所选择的全部基向量与残差正交化处理，这使得在精度要求相同的情况下，OMP算法的收敛速度更快。

OMP算法初始基向量的选择与MP算法相同；在进行迭代分解时，OMP算法的残差与前面每个分量正交，而MP中仅与最近选出的那一项正交。

经过$k$步分解后，信号$x$被分解为：

\[x = \sum_{n=0}^{k} {λ_n a_{r_n}} + R_{k+1}f\]

其中参数λ可以通过最小二乘（Least Square）得到：

\[λ = argmin_{λ} || A_kλ - x ||^2\]

通过上述过程不难看出，对于MP算法，每次选择一个基向量后，其系数便固定了（由内积得到）；对于OMP算法，每一个基向量的选择伴随着之前所有基向量系数的更新。这个系数就是所求的稀疏编码。

关于MP算法和OMP算法更多的细节，可以参考Introduction to Matching Pursuit。