机器学习:从公理到算法
上QQ阅读APP看书,第一时间看更新

5.3 字典学习与稀疏表示

在单类数据降维中,主成分分析的类表示是单位正交坐标系,非负矩阵分解的类表示是位于第一象限的非负坐标系。显然,这两种坐标系都非常特殊。如果进一步放松对类认知表示的要求,放弃坐标系中的坐标基向量线性无关的假设,是否可以呢?这就可以导出字典学习。

假设类认知表示既不是单位正交坐标系,又不是位于第一象限的非负坐标系,而是一个没有约束的广义坐标系,该坐标系中的坐标基允许线性相关。该组基向量的作用和现实中的字典类似,字典中的字也不是独立关系,因此,该组基向量通常称为字典。

与主成分分析与非负矩阵分解不同的是,在字典学习中,已知的是数据输出Y=[yrkd×N,未知的反而是数据输入X=[xrkp×N。同样地,有p > d

同样假设输入类认知表示与输出类认知表示相同,此时=[w1w2,…,wp]=WRd×p。注意到输入数据X未知,而输出数据Y已知,因此,此时定义的类相异性映射为输出类的类相异性映射,其中yk=(y1k,y2k,…,ydkT

由于类表示唯一公理成立,类紧致性准则要求在寻找最佳的类认知表示时,应最小化目标函数(5.13)。

满足最小化目标函数(5.13)要求的字典或者广义坐标系太多太多。这么多坐标系具有同样的性能,就可以应用奥卡姆剃刀准则将复杂的坐标系剔除。应用奥卡姆剃刀准则的关键在于设计复杂性度量。一个简单地度量坐标系复杂的标准是,在该字典下样本的坐标值越稀疏的,即其非零坐标值越少,零坐标值越多,则该坐标系越简单。在这样的假设下,一个坐标系的复杂度可以用其标度的N个对象的非零值坐标值个数来测度,即。奥卡姆剃刀准则要求最小化。考虑到L0度量缺少解析性,因此,一般使用L1度量来代替L0度量。

综合考虑类紧致性准则和奥卡姆剃刀准则,所求的坐标系应该最小化目标函数(5.14)。

其中类表示,即为字典,p为字典中基的个数或者字的个数,xk∈ℝp为数据yk∈ℝd在字典下的稀疏表示。公式(5.14)的第一项表示重构误差,第二项表示稀疏约束。其包含了两个子问题,一个是与4.3节类似的lasso问题用以求解数据在字典上的稀疏表示,第二个是根据表示结果求字典。

优化该问题仍然采用与NMF类似的交替更新策略,固定一项,更新另外一项。固定W,求解xk的过程请参考lasso算法。下面求解字典W。假设已获得N个数据Y=(h1h2,…,hN)∈ℝd×N的稀疏表示矩阵X=(x1x2,…,xN)∈ℝp×N,求解字典W可写成

这里采用K-SVDAharon M, Elad M, Bruckstein A. k-SVD: an algorithm for designing overcomplete dictionaries for sparse representation. IEEE Transactions on Signal Processing, 2006,54(11): 4311-4322.算法求解问题5.15。K-SVD采用逐列的方式更新字典,当更新第k个基向量时,式(5.15)可以写成

其中(XiX的第i行。这样,最小化问题转化为对的一个秩1矩阵逼近问题。因此可以对Ei做一次SVD分解,wi与(Xi的最优解就是Ei最大的奇异值对应的那一对奇异向量。由于(Xi的更新向量可能不再稀疏,为了不再增加X中非零元素的个数,只针对(Xi中的非零元素进行处理。(Xi中非零元素的索引表示字典wi参与了Y中哪些数据元素的构建,这些元素构成了Y的一个子集,因此,在考虑非零元素后,误差Ei代表了字典对这一数据子集在不考虑wi后的重构误差。

需要指出的是,稀疏表示不一定是字典学习,实际上,lasso回归也是稀疏表示,但字典学习一定是稀疏表示。