基于图结构的半监督字典学习

刘晗宇，王 迪，张 磊，张笑钦

(温州大学数理与电子信息工程学院，浙江温州 325035)

近年来，稀疏编码大量应用于图像去噪、图像分类[1]等方面．特别地，Wright等人[2]提出了一种基于稀疏表示的分类方法（SRC），Aharon等人[3]提出了K-SVD算法，这些方法只考虑了字典的稀疏表达能力而忽略了其判别能力．为了提高字典的判别能力，有关学者提出了一些有监督的字典学习算法，例如Zhang和Li[4]提出了具有判别性的K-SVD算法（D-KSVD），Yang等人[5]提出了 Fisher判别字典学习算法（FDDL），Jiang等人[6]提出了类别一致性 K-SVD算法（LC-KSCD），这类算法都是利用样本的类别信息来得到一个有判别能力的字典．有监督字典学习的性能很大程度上依赖于标签样本的个数，但有标签样本的获取是非常困难的，因此利用少量的有标签样本和大量的无标签样本共同训练字典即半监督字典学习成为了研究重点．Shrivastava等人[7]提出了半监督判别性字典学习算法（S2D2），Zhang等人[8]提出了一种在线的半监督字典学习算法（OSSDL）．因为已有的半监督字典学习方法很少考虑无标签样本与有标签样本之间的内在结构关系，无法将无标签样本的潜在类别信息融入到训练过程中，故字典的判别能力没有进一步加强．本文提出一种基于图结构的半监督字典学习方法（Graph-based Semi-supervised Dictionary Learning，G-SSDL）．具体来说：首先获得训练样本之间的稀疏编码，其体现了样本之间的相似度信息；然后运用特殊标签传播方法（SLP）[9]获得训练样本软标签，其蕴含了大量的有监督信息；最后利用训练样本的稀疏编码和软标签构造样本之间的图结构，并将其嵌入到字典学习框架中．

1 相关工作

1.1 稀疏编码问题

1.2 特殊标签传播

其中Iα是对角矩阵，它的对角元素jα是用来在迭代中平衡样本xj的原始标签信息和它受到近邻点的标签信息的影响的参数，式子（2）的迭代过程收敛于

1.3 混合软相似度

样本之间的成对约束包括正约束（Must-link）和负约束（Cannot-link）．通过SLP算法[9]获得无标签样本的标签信息后，成对约束可以利用样本之间的标签关系来获得更多的监督信息，因此对成对约束的研究具有重要意义．正负约束集的定义可以写成：

2 基于图结构的半监督字典学习

本部分为本文新算法．

2.1 图结构约束

通过一个稀疏表达能力和判别能力较强的字典，稀疏表示系数A能很好地保持样本的类别信息和空间结构信息．基于稀疏表示系数的空间结构性约束，可以定义最小化问题：

其中ai为任意样本xi在字典D下的表示系数，即为一个正数参数．（13）式可写成：

2.2 基于图结构的半监督字典学习模型

2.2.1 优化过程

针对模型的非光滑性，本文提出一种基于块坐标下降法（Block Coordinat Descent，BCD）的有效算法交替优化A0,iA,D来求解．另外对于迹运算tr(·)有：

首先固定D和 Ai(i = 1 ,… ,C )更新稀疏编码A0，获得以下子优化问题：

针对子优化问题（12），运用优化最小化算法（Majorization-minimization，MM）迭代求解．具体来说，对于A的第k步迭代值（记为A(k)），引入以下函数：

其中constant表示常数．

同样地，运用MM算法迭代求解子优化问题（18），即对于A的第k步迭代值A(k)，引入以下函数：

其中constant表示常数．

则A的第k+1步迭代值（记为 A(k+1)）可通过下式解决：

固定A（其中包括A0和 Ai）更新字典D，获得关于D的子优化问题：

字典D可通过以下交替方向乘子算法（ADMM）迭代求解，其中Y是拉格朗日乘子矩阵，∏Ξ是向集合的投影算子，μ是一个给定的正数．

2.2.2 无标签样本的标签信息

1）计算样本在第 i(i = 1 ,· ·,C )类的小字典下的稀疏表示系数

2）计算重构误差

3）样本的标签可以由最小化重构误差求得

3 实验结果

为了评估所提算法的分类性能，本节主要在4个数据集上进行分类实验，其中包括两大常见的手写数据集：MNIST（http://yann.lecun.com/exdb/mnist）和USPS[10]；人脸数据UMIST[11]以及COIL-20数据集（http://www.cs.columbia.edu/CAVE/software/softlib/coil20.php）．对于每个数据库，随机从每一类中选取τ个样本作为标签样本，v个样本作为无标签样本，剩下的样本作为测试样本．另外，为了更好地观察标签样本个数对算法的影响，单独对数据库COIL-20进行测试，在每类样本中随机选取35个作为训练样本，剩下的37个样本作为测试样本，在训练样本中随机选取2,3,4,5,6,7个样本作为标签样本，观察标签样本个数的改变对算法的影响．表1描述了这些数据集的具体信息．

表1 实验中所有数据集的描述Table 1 Description of Data Sets in the Experiment

在实验中参与比较的算法为：SRC[3]、三种有监督字典学习算法（DKSVD[4]、FDDL[5]、LCKSVD[6-7]）、两种半监督字典学习算法（OSSDL[8]和 S2D2[9]）．在本文算法中有几个比较重要的参数对实验效果有着至关重要的作用，其中包括在特殊标签传播方法（SLP）获得训练样本软标签过程中，用来在迭代中平衡样本xj的原始标签信息和它受到近邻点的标签信息的影响的参数元素αj．把有标签样本xj的参数αj设定为αl，无标签样本xj的参数αj设定为αu，根据文献[10]的经验，参数αl被固定为0，αu为0.999 999 999．除此之外本文算法中还有4个比较重要的参数，即同类样本之间的拉普拉斯矩阵与不同类样本之间的拉普拉斯矩阵的平衡参数σ，以及本文算法所提出的半监督字典学习模型中的平衡参数λ1,λ2,λ3．本文采用5折交叉验证的方法对每个数据集确定最优参数．针对每个数据集，重复10次实验，并计算这10次实验的平均分类精度

各算法在数据库的分类结果如表2所示．在MIST、USPS、UMIST数据集上对7种算法进行比较，可以看出本文所提算法（G-SSDL）在 3种真实数据集上的分类效果显著，这是因为本文的算法不仅将标签样本与无标签样本共同训练，而且还将无标签样本与标签样本的内在结构以及无标签样本的潜在类别信息融入到了我们的算法中，因此其分类性能优于其它算法．

表2 不同算法的分类准确率Table 2 Classification Accuracy of Different Algorithms

改变数据集COIL-20标签样本数，各算法的分类准确率如表3所示．当标签样本个数较少时，SRC和其它有监督学习算法——DKSVD、FDDL、LCKSVD的分类性能较差，原因在于有监督字典学习的性能很大程度上依赖于有标签样本的个数．本文所给算法G-SSDL有明显的分类优势．

表3 改变数据集COIL-20 标签样本数各算法的分类准确率Table 3 Classification Accuracy of Different Algorithms with Varied Number of Labeled Samples on Dataset COIL-20

4 总 结

本文所给算法G-SSDL将训练样本之间的稀疏编码和软标签所构造的图结构嵌入到字典学习框架中，通过图结构约束和同类样本的结构稀疏性，迫使无标签样本在字典学习过程中能够自动加入到其所在的样本类别中，并与其同类的有标签样本共享少数字典原子，从而提高字典的稀疏表达能力和判别能力．此外，针对模型的非凸非光滑性，本文提出一种基于块坐标下降法（Block Coordinate Descent，BCD）的有效算法．结果表明，本文算法比其它算法具有更好的分类性能．