稀疏表示分类
1. 机器学习中稀疏表示与字典学习1
字典学习也叫稀疏编码，但这两个称谓有稍稍的区别，“字典学习”侧重于描述学得字典的过层，而“稀疏编码”侧重于表述将原样本进行稀疏表达的过程。两者通常是在一个最优化求解过程中完成的，所以这两者不做进一步区分，笼统地认为是一个东西。
给定一个数据集
{
x
1
,
x
2
,
.
.
.
,
x
m
}
\ \{\boldsymbol{x_1,x_2,...,x_m}\}
{x1,x2,...,xm}，对此数据集进行字典学习的最简单形式为：
KaTeX parse error: Undefined control sequence: \norm at position 40: …}\sum_{i=1}^{m}\̲n̲o̲r̲m̲{\boldsymbol{x_…
其中
B
∈
R
d
×
k
\ B\in \bold{R}^{d\times k}
B∈Rd×k为字典矩阵，d表示样本特征维数，k表示此字典的词汇量，通常由用户指定。
α
i
∈
R
k
\ \alpha_i \in \bold{R}^k
αi∈Rk则是原始样本
x
i
\ \boldsymbol{x}_i
xi的稀疏表示。
可以注意到上式前一项是2范数的平方，目的是希望能很好的重构 x i \ \boldsymbol{x}_i xi，这在高光谱残差中是2范数；后一项是 α i \ \alpha_i αi的1范数，目的是希望它尽量稀疏，这在高光谱最优化求解过程中是0范数。所以两者是有一定的区别的，但本质目的是一样的。
在《机器学习》这本书中，描述的求解上述最优化问题的方法是迭代求解。
第一步，固定
B
\ \bold{B}
B，上面的问题转化为求解
α
i
\ \bold{\alpha_i}
αi，具体解法可以参照LASSO：
KaTeX parse error: Undefined control sequence: \norm at position 24: …bold{\alpha}_i}\̲n̲o̲r̲m̲{\boldsymbol{x}…
第二步，此时我们可以根据得到的
α
i
\ \bold{\alpha}_i
αi来更新字典
B
\ \bold{B}
B，最优化问题变成：
KaTeX parse error: Undefined control sequence: \norm at position 15: \min_\bold{B}\̲n̲o̲r̲m̲{\bold{X-BA}}_F…
显然，上式
X
=
(
x
1
,
x
2
,
.
.
.
,
x
m
)
∈
R
d
×
m
\ \bold{X}=(\boldsymbol{x_1,x_2,...,x_m})\in\bold{R}^{d\times m}
X=(x1,x2,...,xm)∈Rd×m，
A
=
(
α
1
,
α
2
,
.
.
.
,
α
m
)
∈
R
k
×
m
\ \bold{A}=(\boldsymbol{\alpha_1,\alpha_2,...,\alpha_m})\in\bold{R}^{k\times m}
A=(α1,α2,...,αm)∈Rk×m，KaTeX parse error: Undefined control sequence: \norm at position 3: \ \̲n̲o̲r̲m̲{·}_F表示矩阵的Frobenius范数，对于这个式子的常用解法为基于逐列更新策略的KSVD算法。
2. 稀疏表示分类2
假定共有n个训练样本，总共c类，并且对于第k类都有充足的训练样本，
A
k
=
[
x
k
,
1
,
x
k
,
2
,
.
.
.
,
x
k
,
n
k
]
∈
R
m
×
n
k
\ A_k=[x_{k,1},x_{k,2},...,x_{k,n_k}]\in\bold{R}^{m\times n_k}
Ak=[xk,1,xk,2,...,xk,nk]∈Rm×nk，其中
m
\ m
m样本的特征维数，
n
k
\ n_k
nk表示第k类中的训练样本数目。那么对于来自于第k类的任意测试样本
y
∈
R
m
\ y\in\bold{R}^m
y∈Rm，它都可以用第k类训练样本的线性组合近似表达：
y
=
α
k
,
1
x
k
,
1
+
α
k
,
2
x
k
,
2
+
.
.
.
+
α
k
,
n
k
x
k
,
n
k
\boldsymbol{y}=\alpha_{k,1}x_{k,1}+\alpha_{k,2}x_{k,2}+...+\alpha_{k,n_k}x_{k,n_k}
y=αk,1xk,1+αk,2xk,2+...+αk,nkxk,nk
但因为
y
\ \boldsymbol{y}
y的标签在一开始是不知道的，所以我们只好将其写作所有类别样本的线性组合。
y
=
A
α
\boldsymbol{y}=\boldsymbol{A\alpha}
y=Aα
其中
A
=
[
A
1
,
A
2
,
.
.
.
,
A
c
]
=
[
x
1
,
1
,
x
1
,
2
,
.
.
.
,
x
c
,
n
c
]
∈
R
m
×
n
\ \boldsymbol{A}=\boldsymbol{[A_1,A_2,...,A_c]}=[x_{1,1},x_{1,2},...,x_{c,n_c}]\in\bold{R}^{m\times n}
A=[A1,A2,...,Ac]=[x1,1,x1,2,...,xc,nc]∈Rm×n为所有类别全部样本的矩阵，按照类别有序放好的，
α
\ \bold{\alpha}
α为覆盖全样本的系数向量。
理想情况下 y \boldsymbol{y} y是应该仅由某一特定类别的系数 α k \ \bold{\alpha}_k αk所确定，所以在这里 α = [ 0 , . . . , 0 , α k , 1 , α k , 2 , . . . , α k , n k , 0 , . . . , 0 ] T ∈ R n \ \bold{\alpha}=[0,...,0,\alpha_{k,1},\alpha_{k,2},...,\alpha_{k,n_k},0,...,0]^T\in\bold{R}^n α=[0,...,0,αk,1,αk,2,...,αk,nk,0,...,0]T∈Rn在c足够大的情况下，应当为一稀疏向量。
如果
m
<
n
\ m \lt n
m<n，即特征维度小于样本数目时，上式是欠定的3，因此问题转为受约束条件的最优化问题：
KaTeX parse error: Undefined control sequence: \norm at position 55: …limits_{\alpha}\̲n̲o̲r̲m̲{\alpha}_0\\ s.…
求解此最优化问题是一个NP-hard问题，也就是无法找到最稀疏的解，但可以转为贪心算法求局部最优解，或者将0范数转为1范数，进而最问题变为求解凸松弛优化。又由于观测值是不精确的，所以约束条件不应该是严格等，所以改写如下：
KaTeX parse error: Undefined control sequence: \norm at position 55: …limits_{\alpha}\̲n̲o̲r̲m̲{\alpha}_1\\ s.…
当我们经过一系列算法后得到了
α
^
\ \hat{\bold{\alpha}}
α^，请注意它是一个近似解！接下来我们需要使用它来进行重构测试样本。我们前面说到，全样本
A
\ \boldsymbol{A}
A是根据类别有序放好的，那么
α
^
\ \hat{\bold{\alpha}}
α^中每个类别所对应的
α
^
k
\ \hat{\bold{\alpha}}^k
α^k的长度和位置都是确定的。
所以在类别划分时，我们可以定义一个残差来计算重构效果，重构效果好的那一类就是所求类别。
KaTeX parse error: Undefined control sequence: \norm at position 28: …boldsymbol{y})=\̲n̲o̲r̲m̲{\boldsymbol{y-…
3. SRC在高光谱中的应用4
3.1. 高光谱稀疏模型
假设
x
\ \boldsymbol{x}
x是一个具有
B
\ B
B维特征的样本，所有训练样本中有
K
\ K
K个类别，在第
K
\ K
K个类别中样本数目为
N
K
\ N_K
NK，第
k
\ k
k类样本用向量集表示如下：
{
a
j
k
}
j
=
1
,
.
.
.
,
N
k
\ \{ \boldsymbol{a}_j^k\}_{j=1,...,N_k}
{ajk}j=1,...,Nk
若
x
\ \boldsymbol{x}
x是属于第
k
\ k
k个类别，它的特征可以近似地处于一个低维的子空间中，这个子空间是由相同类的所有训练样本所定义的。并且此样本可以用训练样本的线性组合来近似表示如下：
x
≈
α
1
k
a
1
k
+
α
2
k
a
2
k
+
⋯
+
α
N
k
k
a
N
k
k
=
[
a
1
k
a
2
k
…
a
N
k
k
]
⏟
A
k
[
α
1
α
2
…
α
N
k
]
T
⏟
=
A
k
α
k
\begin{aligned} \boldsymbol{x}&\approx\alpha_1^k\boldsymbol{a}_1^k+\alpha_2^k\boldsymbol{a}_2^k+\dots+\alpha_{N_k}^k\boldsymbol{a}_{N_k}^k\\ &=\underbrace{[\boldsymbol{a}_1^k\quad\boldsymbol{a}_2^k\quad\dots\quad\boldsymbol{a}_{N_k}^k]}_{\boldsymbol{A}^k}\underbrace{[\alpha_1\quad\alpha_2\quad\dots\quad\alpha_{N_k}]^T}\\ &=\boldsymbol{A}^k\boldsymbol{\alpha}^k \end{aligned}
x≈α1ka1k+α2ka2k+⋯+αNkkaNkk=Ak
[a1ka2k…aNkk]
[α1α2…αNk]T=Akαk
其中
A
k
\ \boldsymbol{A}^k
Ak为
B
×
N
k
\ B\times N_k
B×Nk的字典矩阵，即每个类别的训练样本会有一个字典，列数表示第k类的训练样本数。
α
k
\ \boldsymbol{\alpha}^k
αk为一未知
N
k
\ N_k
Nk维矢量，其中的每一项表示在
A
k
\ \boldsymbol{A}^k
Ak中对应原子的丰度。在此模型中，
α
\ \boldsymbol{\alpha}
α已证明是一个稀疏矢量。
当输入一个测试样本时，它应该是处于所有
K
\ K
K类联合的子空间中的。因此对于一个测试样本
x
\ \boldsymbol{x}
x,它可以表示为所有字典和所有训练样本的一个线性组合。
x
=
A
1
α
1
+
A
2
α
2
+
⋯
+
A
K
α
K
=
A
1
…
A
K
⏟
A
[
α
1
…
α
K
]
⏟
α
=
A
α
\begin{aligned} \boldsymbol{x}&=\boldsymbol{A}^1\boldsymbol{\alpha}^1+\boldsymbol{A}^2\boldsymbol{\alpha}^2+\dots+\boldsymbol{A}^K\boldsymbol{\alpha}^K\\ &=\underbrace{\boldsymbol{A}^1\quad\dots\quad\boldsymbol{A}^K}_{\boldsymbol{A}}\underbrace{\begin{bmatrix}\boldsymbol{\alpha^1}\\\dots\\\boldsymbol{\alpha^K}\end{bmatrix}}_\boldsymbol{\alpha}=\boldsymbol{A\alpha} \end{aligned}
x=A1α1+A2α2+⋯+AKαK=A
A1…AKα
⎣⎡α1…αK⎦⎤=Aα
其中
A
\ \boldsymbol{A}
A为
B
×
N
\ B\times N
B×N矩阵，由所有类别训练样本组成。
α
\ \boldsymbol{\alpha}
α是一个
N
\ N
N维的稀疏向量，由原先每个类别的稀疏向量组成。需注意，在理想情况下，若测试样本
x
\ \boldsymbol{x}
x属于第
k
\ k
k类，那么除此类以外的其他所有类的稀疏向量
α
j
=
0
，
j
≠
k
\ \boldsymbol{\alpha}^j=0，j\neq k
αj=0，j=k。
3.2. 高光谱重建及分类
在这里，我们需要注意的是，上述稀疏模型中已知的部分是
A
\ \boldsymbol{A}
A，未知的部分是稀疏向量
α
\ \boldsymbol{\alpha}
α。因此当在考虑一个未知类别测试样本
x
\ \boldsymbol{x}
x输入时，我们首先应是想办法求稀疏向量
α
^
\ \hat{\boldsymbol{\alpha}}
α^，求解此向量的方法是解下面的最优化问题：
KaTeX parse error: Undefined control sequence: \norm at position 36: …lpha}}=\arg\min\̲n̲o̲r̲m̲{\alpha}_0\\ s.…
0范数定义为在稀疏向量中的非0项的个数。此NP-hard的最优化问题可以用贪心算法等进行求解。
当求解到了
α
^
\ \hat{\boldsymbol{\alpha}}
α^后，
x
\ \boldsymbol{x}
x的类别就可以直接确定了。在这之前我们需要回忆起，
α
^
\ \hat{\boldsymbol{\alpha}}
α^其实是由
α
^
k
\ \hat{\boldsymbol{\alpha}}_k
α^k拼接而成的，
α
^
k
\ \hat{\boldsymbol{\alpha}}_k
α^k的长度是与其对应类别的样本数一致的，所以当我们有了
α
^
\ \hat{\boldsymbol{\alpha}}
α^后，其实是可以将其拆解开的。在这里我们定义
x
\ \boldsymbol{x}
x与第k类的残差。
KaTeX parse error: Undefined control sequence: \norm at position 22: …boldsymbol{x})=\̲n̲o̲r̲m̲{\boldsymbol{x}…
然后
x
\ \boldsymbol{x}
x所对应的类别就是具有最小残差的那个类别：
C
l
a
s
s
(
x
)
=
arg
k
=
1
,
.
.
.
,
K
min
r
k
(
x
)
Class(\boldsymbol{x})=\arg_{k=1,...,K}\min r^k(\boldsymbol{x})
Class(x)=argk=1,...,Kminrk(x)
画一个图可如下表示：
最后取残差最小所对应的类别即为所求。
总结
字典学习也叫稀疏编码，在机器学习中，字典的components词汇量是由用户自己指定的，通过反复迭代更新求解稀疏向量 α i \ \bold{\alpha}_{i} αi和字典矩阵 B \ \bold{B} B。用户可以通过设置词汇量来控制字典规模，从而影响到稀疏程度。
在稀疏表示分类中，字典其实就是按照类别有序排列好的全样本集，在这个方法中，字典矩阵是固定不变的，即不对字典进行更新，仅求解测试样本 y \ \boldsymbol{y} y的稀疏向量。求解到全样本稀疏向量后，根据每个类训练样本数目，从全样本稀疏向量 α ^ \ \hat{\boldsymbol{\alpha}} α^中划分出 α ^ k \ \hat{\boldsymbol{\alpha}}_k α^k。进而通过重构求残差的方式，找到最小残差对应的类别即为所求。
Note that: KSVD算法是用来求解更新字典矩阵 B \ \bold{B} B的，因此在SRC中不需要使用到此算法。
-
周志华. 《机器学习》 . ↩︎
-
Yin, Jun, Zhonghua Liu, Zhong Jin和Wankou Yang. 《Kernel Sparse Representation Based Classification》. Neurocomputing 77, 期 1 (2012年2月): 120–28. https://doi.org/10.1016/j.neucom.2011.08.018. ↩︎
-
欠定方程组: 方程个数小于未知量个数的方程组。 对于方程组Ra=y,R为n×m矩阵,且n<m。则方程组有无穷多组解,此时称方程组为欠定方程组。 ↩︎
-
Chen, Yi, Nasser M. Nasrabadi和Trac D. Tran. 《Classification for Hyperspectral Imagery Based on Sparse Representation》. 收入 2010 2nd Workshop on Hyperspectral Image and Signal Processing: Evolution in Remote Sensing, 1–4. Reykjavik, Iceland: IEEE, 2010. https://doi.org/10.1109/WHISPERS.2010.5594882. ↩︎