基于可信点的联合半监督学习

王 晓 波(天津大学 理学院，天津300072)



基于可信点的联合半监督学习

王 晓 波(天津大学 理学院，天津300072)

摘要：在半监督分类问题中，某些无标签的数据点很有可能属于某一特定的类，则这些点可被信任，应当被充分地利用去帮助学习正确的分类界面，从而提升图像分类的效果.因此，如何区分出可信点在半监督分类问题中显得尤为重要.针对该问题，提出一种联合的半监督学习方法，可以自适应地区分可信点，并且提出了相应的迭代优化分类器和可信点标签矩阵的算法，把分类器的归纳能力和无标签数据的标签直推化能力融合到了一个框架中，不需要额外的步骤去预测无标签数据的标签.在两个人脸数据库中大量实验验证了所提方法的可行性和有效性.

关键词：联合半监督学习；图像分类；可信点

研究有效的算法去实现图像分类是计算机视觉的一大热点.监督分类系统[1-2]依赖手工标注的带标签的数据特别耗费人力和财力，甚至有时候无法实现的.在大部分的情况下，数据集中的训练样本虽然很多，但是带标签的却很少.因此，如何充分利用那些无标签的数据就变得非常重要. 近些年提出了大量的半监督学习方法就是适合这种情况，主要可分为三种类型：直推式学习模型[3-6]、归纳式学习模型[7-8]和联合学习模型[9].直推式模型主要是基于标签在图中的传播，最优的预测标签则是标签和图的结构一致性的最大化.一些代表性的工作包括局部全局一致性(LGC)[4]，高斯域调和函数(GFHF)[5]，局部样条回归(LSR)[6]等等.虽然这些方法有理论上的保证，但不能用于预测训练样本之外的测试集，并且计算量很大.

归纳式模型利用无标签的数据去正则化分类器(保证分类界面通过的是数据低密度的区域).学习的分类器可用于分类训练样本中的无标签数据和训练样本之外的测试样本.从以能用于测试样本的角度看，归纳式模型在应用中更为实用.一些代表性的方法包括拉普拉斯回归(LR)[7]，弹性流行嵌入(FME)[8]，但这些方法需要额外的步骤去预测训练样本中无标签的数据的标签.

联合直推式和归纳式模型如ASL[9]同时学习分类器和预测训练样本中无标签数据的标签.该方法可用于测试样本且可扩展到大数据上，实验结果显示比传统基于图的方法更好.但是用所有无标签的数据去精细分类器一般达不到最优的分类效果.

为了同时克服以上所有的缺点，本文提出了一种新的联合半监督学习模型(简记为USSL_CP).该算法融合了三个优点：自动区分可信点、自适应地优化过程和计算有效性.

1基于可信点的联合半监督学习

直觉上，对于带标签的数据，希望学习分类器能很好地分开它们.即对于带标签的训练样本xi，其分类错误[公式(1)]应该很小.其中Xl∈Rd×nl是带标签的训练样本矩阵，Yl∈Rn1×C是标签矩阵，W∈Rd×C是要学习的分类器的参数矩阵，

(1)

b∈RC×1是偏差.1nl是nl维元素为1的列向量.

(2)

其中:P∈Rnu×c是Pjk形成的无标签数据的标签概率矩阵.tk∈Rc×1则是第k类别标签的指示向量.

最后基于可信点的联合半监督学习模型为：

minW,b,PJl(W,b)+Ju(W,b,P)

(3)

2优化算法过程

(4)

2) 固定无标签数据的标签概率矩阵P，优化模型参数W 和 b.将目标方程(3)重新写成一种紧致的矩阵形式：

(5)

目标函数(5)关于b求偏导为0，可得：

(6)

目标函数(5)关于W求偏导为0, 可得：

W=C-1A.

(7)

其中

为了使整个算法更为清晰，总结为算法1. 两步交替地迭代优化模型可知分类器的归纳能力受标签概率矩阵的影响，同时无标签数据的直推能力又取决于分类器.

算法 1：基于可信点联合半监督学习 (USSL_CP)

各参数的初始值Winit,binit,σinit,θinit.

Fort

(10)

1)公式(4)更新无标签数据的概率矩阵P

2)公式(7)和(6)更新分类器参数W和b

end

输出：分类器参数W和b, 概率矩阵P.

3实验

3.1数据集的描述

为了评价本文提出的联合半监督学习方法的有效性，分别在ORL数据库[10]，和YALE-B数据库[11]两个数据库上做了相应的实验.两个数据库都是相应的人脸数据库，将原始的灰度图像用PCA进行降维.重要的数据指标如表1所示.

表1数据集描述

#样本个数#特征维数#类数ORL40064440Yale-B2414102438

3.2实验设置

为评价本文提出的联合半监督学习方法的可行性和有效性，实验比较了最具代表性的直推式半监督学习方法高斯域调和函数(GFHF)[5]和最具代表性的归纳式半监督学习方法拉普拉斯回归(LapReg)[7]，还有最具代表性的联合学习方法自适应的半监督学习方法(ASL)[9]，以及最具代表性的监督学习方法支持向量机(SVM)[12].

实验重复10次去计算平均分类准确率和标准差以及用不同个数的带标签数据来测试算法对带标签数据的敏感性.随机从每类选取1，3,5个带标签的数据点，剩余的作为无标签的数据.对于直推式的模型，由于不能用于测试集的预测，仅仅计算其训练样本中无标签数据的识别率.对于归纳式的方法，随机选取33%的数据做测试集，其余的样本随机划分为带标签的和无标签的数据.并计算了训练样本中无标签数据的识别率和测试集的识别率.

对于本文的参数θ从0～0.1的范围内调整，每次调整的步长0.01.参数σ从0～1之间调整，每次调整的步长为0.1. SVM则用的是默认参数值, GFHF是无参的模型，对于LapReg，两个正则化参数在调整{10-5,10-4,…,104,105}. 对于ASL，它的参数r从1～2 之间调整，每次调整的步长为0.1，报告的结果为最佳参数下所得出的结果.

表2不同比较方法在ORL数据库上的平均分类准确率及偏差

ORLSVMGFHFLapRegASLUSSL_CPkl=1测试集无标签64.83±4.1265.50±2.44NA65.87±1.7366.58±3.7466.38±2.3467.50±3.8667.66±1.4071.83±3.0468.00±1.27kl=3测试集无标签87.83±2.7386.87±1.53NA85.15±1.7884.53±2.3785.79±2.5488.50±1.0886.00±2.6389.50±1.3987.82±1.67kl=5测试集无标签94.16±0.8394.25±1.11NA89.83±2.2690.37±3.0192.01±2.3193.50±0.1892.83±1.3995.00±1.5397.85±1.39

注：kl-每类带标签的数据样本个数；NA-不可无法获得的结果

表3不同比较方法在Yale-B数据库上的平均分类准确率及偏差

Yale-BSVMGFHFLapRegASLUSSL_CPkl=1测试集无标签57.32±4.1056.26±3.59NA45.98±3.3753.34±4.5353.37±4.3259.22±4.6959.38±3.5660.94±3.9261.03±2.73kl=3测试集无标签90.36±2.3289.83±2.56NA79.82±1.7991.51±1.6592.83±1.5796.14±1.1696.59±1.8596.69±1.4695.14±1.06kl=5测试集无标签98.10±0.7698.29±0.98NA89.96±2.3897.38±1.0598.16±1.0799.00±0.8799.21±0.5399.10±0.6799.340.23

3.3分类性能比较

表2、表3中报告了不同的算法在两个数据库上的平均识别率和标准差.从这些表的数据可以得出，本文提出的USSL_CP模型优于其他的方法.同时得出当带标签的数据量增大的时候，分类效果也比其他的方法好.特别是当每类带标签数据的个数从1增加到3时，分类识别率有明显地提升.

3.4收敛性

每次迭代都是最小化目标函数，即每步迭代的目标函数是减小的，且目标函数值的下界为0，算法是收敛的.在2.60GHz主频和i5双核处理器，4 GB的内存的台式机上，四个数据库上，10步迭代已足够使得算法收敛稳定.

4结语

本文提出了一种联合的半监督学习模型，可以自适应地识别可信点.与以往的联合半监督学习方法相比，该模型不考虑那些起错误引导作用的无标签数据点，而是考虑可信点去帮助学习分类界面.从而达到更好的识别效果.并且提出了交替迭代优化模型参数和无标签数据的概率标签矩阵，把分类器的归纳能力和无标签的直推能力融入在一个框架下，不需要额外的步骤去预测无标签数据的标签，并且不需要构建拉普拉斯图矩阵，避免了较大的计算复杂度，即在理论上是可以扩展到大数据库上.

参考文献：

[1]LAZEBNIK S, SCHMID C, PONCE J. A sparse texture representation using local affine regions [J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 2005, 27(8): 1265-1278.

[2]LAZEBNIK S, SCHMID C, PONCE J. Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[C]// New York: IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2006, 2: 2169-2178.

[3]ZHU X, GOLDBERG A B. Introduction to semi-supervised learning [J]. Synthesis Lectures on Artificial Intelligence and Machine Learning, 2009, 3(1): 1-130.

[4]ZHOU D, BOUSQUET O, LAL T N,etal. Learning with local and global consistency [J]. Advances in neural information processing systems, 2004, 16(16): 321-328.

[5]ZHU X, GHAHRAMANI Z, LAFFERTY J. Semi-supervised learning using gaussian fields and harmonic functions[C]//Washington DC: ICML, 2003, 3: 912-919.

[6]XIANG S, NIE F, ZHANG C. Semi-supervised classification via local spline regression [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(11): 2039-2053.

[7]SINDHWANI V, NIYOGI P, BELKIN M, et al. Linear manifold regularization for large scale semi-supervised learning[C]// Bonn: Proc. of the 22nd ICML Workshop on Learning with Partially Classified Training Data, 2005. 28.

[8]NIE F, XU D, TSANG I W H,etal. Flexible manifold embedding: A framework for semi-supervised and unsupervised dimension reduction [J]. IEEE Transactions on Image Processing, 2010, 19(7): 1921-1932.

[9]WANG D, NIE F, HUANG H. Large-scale adaptive semi-supervised learning via unified inductive and transductive model[C]// New York: ACM Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data mining, 2014. 482-491.

[10]ORL Face Database [DB/OL]. http://www.cam-orl.co.uk/facedatabase.html.

[11]Yale Face Database [DB/OL]. http://cvc.yale.edu/projects/yalefaces/yalefaces.html.

[12]CHANG C C, LIN C J. LIBSVM: a library for support vector machines [J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2011, 2(3): 27.

Unified semi-supervised learning with confidence points

WANG Xiao-bo

(School of Science, Tianjin University, Tianjin 300072, China)

Abstract：In the question of semi-supervised classification, if data points have high confidence of belonging to a particular class, they should be well utilized for learning the correct classifier and thus can help boost the classification performance. So how to adaptively choose confidence points become very crucial in semi-supervised learning. To address the challenge, this paper proposed a unified semi-supervised learning model, which could adaptively distinguish confidence points, such that our new model is more effective for classification. Moreover, an efficient algorithm was also derived to alternatively optimize the model parameter and confidence matrix of the unlabeled data, such that the induction of classifier and the transduction of labels were unified into a framework, without needing an extra step to predict the label of unlabeled data. Extensive experimental results on two real-world data sets showed that the proposed unified semi-supervised learning model outperforms other related methods in most cases.

Key words：unified semi-supervised learning; image classification; confidence points.

中图分类号：O235

文献标识码：A

文章编号：1672-0946(2016)01-0067-04

作者简介：王晓波(1991-)，男，硕士，研究方向：模式识别、计算机视觉.

基金项目：国家自然科学基金(61379014)

收稿日期：2015-04-01.