5.3　字典学习与稀疏表示

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

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

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

同样假设输入类认知表示与输出类认知表示相同，此时=［w1，w2，…，wp］=W∈Rd×p。注意到输入数据X未知，而输出数据Y已知，因此，此时定义的类相异性映射为输出类的类相异性映射，其中yk=（y1k，y2k，…，ydk）T。

由于类表示唯一公理成立，类紧致性准则要求在寻找最佳的类认知表示时，应最小化目标函数（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=（h1，h2，…，hN）∈ℝd×N的稀疏表示矩阵X=（x1，x2，…，xN）∈ℝp×N，求解字典W可写成

这里采用K-SVD算法求解问题5.15。K-SVD采用逐列的方式更新字典，当更新第k个基向量时，式（5.15）可以写成

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

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