结合包光滑性的半监督多示例核学习方法*

潘强

（珠海城市职业技术学院经济管理学院）

0 引言

在半监督多示例算法研究中，获取现实样本的概念标记需要花费大量的人力和时间，因此在学习过程中利用未标记样本，能提升学习器性能的半监督学习算法引起研究者的兴趣。目前半监督多示例学习的研究主要是使用示例层次的标签传播和带约束的优化方法[1-3]。文献[4]提出了一种示例层次的半监督多示例学习算法，它把示例概念标记的确定归结为一个带损失项和正则化项的优化问题，在假设空间中寻找一个假设，使之同时满足：1)训练误差最小；2)假设复杂度最低；3)假设在已知的数据点上尽可能光滑。在第3)中的光滑性定义是指示例空间意义上的，即考虑假设在所有包中的示例上的光滑程度。该方法把在单示例半监督学习中的基于流形正则化的方法[5]应用到多示例学习问题中，但存在几个不足：1)该方法所考虑的假设是以示例为变量，并不是对原问题的直接求解；2)该方法要求解一个约束条件数量较多的最优化问题，求解的代价巨大；3)该最优化问题不满足Representer定理[6]的条件，无法直接转化为标准的RKHS空间上的优化问题。

本文提出一种直接利用未标记包进行半监督多示例学习的算法，它在正则化框架中展开，直接在多示例的假设空间中寻找一个假设，满足上述3个条件，不同的是本文并不考虑假设对于单个示例的复杂度和光滑性。实现包层次的半监督学习，关键是定义包的光滑性。本文先用核映射的方法得到一个关于所有包（有标记和无标记）的相似度矩阵，然后对其表示的包计算其图拉普拉斯，通过对文献[6]工作的扩展，得到多示例半监督核。设有标记多示例数据集为BL={bag1,bag2,…,bagnl} 和 未 标 记 集 为BU={bag1,bag2,…,bagnu}，在整个包空间中通过已知的样本（不考虑标签）建立一个图拉普拉斯矩阵刻画其分布的光滑性，通过该矩阵修改一个已经存在的多示例核，得到一个与样本依赖的核。形式上有：

其中，k是一个普通的多示例核；M是一个光滑性度量，由所有“看得见”的样本 Ball决定；f是一个向量实值函数，可以认为f借助空间的光滑性度量修改了原有多示例核的数值，使之更为准确地反映数据的空间分布。

1 结合包光滑性半监督多示例核

1.1 包空间光滑性度量

基于半监督核[4,7]与多示例核[8-9]的研究，提出一种结合包光滑性的半监督多示例核的概念。先定义多示例包的图拉普拉斯，然后说明这种刻画单示例流形的手段也适用于多示例场合。

定义1多示例样本的图拉普拉斯MMI

MMI= LP，其中L=D－W，W为多示例样本的基于Heat Kernel的Gram矩阵，且有：

在定义1中，d(Bi,Bj)为两个包之间的距离。流形是一种低维的嵌入，而这种嵌入的基础是样本点在空间的一种相邻关系。但对于多示例包，距离的定义与单示例的场合不同，包之间没有直观的相邻关系。在以往的研究中3种包间距离的定义列为表1。

表1 包间距离定义

在表1中，包中心距离定义为取包中所有示例的平均值作为包中心点，计算两个包中心点的欧氏距离；包最近点距离为取两个包中示例的欧氏距离中的最小值作为两个包的距离；Min-Max距离是把包进行Min-Max扩展为一个2n维的向量，其中前n维为所有属性在包中示例上取得的最小值，后n维为所有属性在包中示例上取得的最大值，每两个包之间使用欧氏距离计算。

以往的研究表明，包中心距离和包最近点距离并不能很好反映其分布规律[10]。而 Min-Max距离对包的属性进行了扩展，仅考虑示例在各个属性上取值的边界，实质上仅是一种数理统计手段。这些距离的定义均存在一个缺陷，即它们所反映的仅是每个包本身的特性，而没有考虑到整个示例空间的分布规律。

为了进一步在包距离中反映包的示例分布及其之间的关系，提出一种基于包概念表示的海明距离。首先在整个示例空间对示例进行聚类，按照文献[11]的观点，不同的簇可以看作是整个示例空间的不同概念，然后以一个布尔向量记录每一个包中是否包含属于某个聚类的示例（该向量称为概念向量），以该布尔向量作为包的表示计算海明距离作为包间距离。

定义2概念空间海明距离

在定义2中，HM为海明距离的计算函数。Concept算法把一个包表示为一个布尔向量，每一个分量表示该包是否包含属于某个簇的示例。算法 1展示了Concept算法的计算过程。

算法1Concept（包概念向量的计算）

输入：多示例数据集Ball，包B，聚类数目K

输出：包B所对应的概念向量表示C

定义2与表1中所定义的距离最大的不同之处在于它以聚类的方式考虑了整个示例空间的内在规律性。该聚类过程是半监督的，可以在训练数据集的基础上引入更多的未标记包进行聚类，使这种示例空间的概念估计更加准确。

在定义1中使用概念空间海明距离，可以得到描述包空间光滑性的图拉普拉斯。算法2描述了包的图拉普拉斯的计算过程。

算法2 MIGraphLaplacian（多示例样本图拉普拉斯的计算）

输入：多示例数据集Ball，参数P

输出：多示例样本的图拉普拉斯矩阵M

算法2的第2行初始化W为一个n×n方阵，其中n为所有包的个数。核函数选用RBF核，考虑到对于k维的包概念向量表示，其最小和最大海明距离分别为 0（全部相同）和 k（全部不同），因此第 7行RBF核的宽度参数取值为概念簇数目k的一半。参数p控制光滑性表示的复杂程度[5]，恰当设置p的值能使图拉普拉斯矩阵M反映真正的数据流形分布。

由于正包和负包的概念构成不同，它们与基准包（训练集）的海明距离存在明显的差距，这种平均距离之间的差异有助于确定一个较为准确的光滑性度量，可以定性地认为相似的包所包含的概念也应该是比较相似的。

1.2 半监督多示例核

通过多示例样本的图拉普拉斯定义，很容易计算出半监督多示例核。在整个示例空间进行聚类，构造包的概念表示，计算包之间的概念空间海明距离矩阵，进而计算出包的图拉普拉斯，沿用单示例数据依赖核的理论[4]，可以得到半监督多示例核。算法3描述了半监督多示例核的计算过程。

算法3MISSLKernel（半监督多示例核的计算）

输入：训练数据集Dtrain待映射数据库D，未标记数据集P，多示例核k

输出：半监督多示例核矩阵：K：D×Dtrain

由于未标记数据集的引入，算法3所返回的核矩阵不再仅仅依赖于训练数据集，由此实现多示例核的半监督化。考察算法3的第2行和第6行，均需要计算两个关于所有多示例包Dall的Gram矩阵，当Dtrain∪D∪P的数目较大时，这两行的计算量非常大。在一般情况下，P中的包数目会比较多，因为获取未标记包会比有标记包容易得多。由文献[12]、[13]可知，要使半监督学习有效，实际上并不需要太多的未标记样本，在算法中引入过多的未标记样本会增加复杂度甚至降低正确率。基于这样的考虑，对未标记数据随机抽样，选择其中的q%作为PointCloud。

另一方面，考察核映射的本质，实质是把每一个待输入学习器的样本先映射到一组基样本上，一般使用训练样本充当基准样本，即 BBase=Dtrain，在训练和测试的过程中，分别把有标记样本集 BL和待测试样本集BU映射到基准BBase上，把映射后的每一行作为原始数据的特征表示，用于训练和测试过程。但若训练数据的绝对数量较大，会导致映射后的数据维数过高，使训练和测试的复杂度大大增加。

本文提出了一种类似于文献[11]的简化策略，通过对Dtrain随机抽样限制其规模，然后把2p+1次抽样训练的学习器集成并进行多数投票。这是一种分治策略，训练若干个低维度数据集的复杂度远比训练一个高维度数据集要低，且在以往的研究中，这种分治后的集成被证明是有效的[11]。

2 实验和讨论

2.1 标准数据集实验

为说明基于概念向量海明距离的半监督多示例核的有效性，在多示例学习的标准数据 Musk1和Musk2上，将本算法（MISSLK）与MIKernel算法[8]、基于表 1的 3种包间不同距离的半监督多示例核算法[14]进行比较测试。主要原因有：1)通过与MIKernel比较，说明PointCloud的方式对原有多示例核进行半监督化修改的有效性；2)与文献[14]中半监督多示例核算法的比较，说明本文的基于包概念表示的包间海明距离对于构造半监督多示例核的有效性。

实验设置如下：把数据集随机分成10份，其中1份作为测试集，余下9份作为训练集和PointCloud。首先初始化PointCloud为余下的9份，而训练集每次增加1份。数据集随机划分的过程并不考虑每份中正负包比例的平衡。10份数据轮流做测试，记录其正确率的平均值与训练数据比例之间的关系。Musk1和Musk2分别用k=13和k=16进行概念簇的计算。图拉普拉斯的指数参数取p=1.5。由于Musk1和Musk2数据集的规模都不大，因此使用全映射的方式，即不对BBase进行随机抽样之后再集成。由于MIKernel并不是半监督学习算法，所以在它的训练过程不使用PointCloud，每轮增加一份训练样本。学习器使用Weka的J48决策树，在Matlab中通过Spider开源项目调用Weka的实现。图1展示了实验结果。

在图1中，横轴表示训练样本的比例；纵轴表示算法在测试集上的正确率。图中每个点是10次实验结果的平均，其方差也在图中通过垂直的线段反映。D1、D2和D3分别代表文献[14]中的基于3种不同包间距离的半监督多示例核。从图1中可以看到，当训练过程中使用的有标记包数量较少时，本文的半监督算法能够对分类器的正确率有一定的正面贡献；在训练数据比例较低的情况下，本文的方法要比MIKernel好。但当训练数据比例增加时，本文的方法不如MIKernel，这种现象在以往的半监督学习中也被观察到，其原因是在训练数据过多时其本身确定的分布与未标记数据可能不同，从而会在训练过程中引入潜在的冲突，导致学习器的效率下降。此外，如果随意引入未标记数据并不会一直提升学习器的性能，也不是学习过程中使用的数据越多效果就越好，这一点从图1中正确率的波动可以看出，但基本趋势是有标记的训练样本越多其效果越好。总的来说，在大部分情况下，未标记数据包的引入能够提升学习器的泛化能力。

图1 标准数据集分类正确率比较

2.2 图像数据集实验

本文进一步在Corel Image 2000图像数据（简称Image2000）上测试本算法。为处理方便，选择与文献[2]中使用的经过预处理的Image2000数据集。预处理过程对每幅图像LUV颜色空间矩阵进行分块二维小波变换，对小波系数进行聚类，每个簇由一个9维特征向量表示。由于文献[2]采用的是对聚类数目自适应的聚类算法，数据集中每幅图像所包含的示例（簇）数量不一定相同。

Image2000包含20类图像，每个类有100幅。对于每一类数据，从中随机抽取25幅作为正例，并从其余的19类中随机抽取50幅作为负例构成规模为7的训练集；余下75幅同类图像加上从其余类中随机抽取150幅图像一起构成测试集，从而保持训练集和测试集中正负例的比例相同，防止学习器对数量较多的负例有过大的倾向。对于每一类，整个过程重复10次，记录每一类的准确率均值和方差。

本实验采用转导学习的方式对PointCloud进行构建，即假设测试数据集在训练的时候就已知，将整个测试数据集和剩余的数据看作未标记数据构建PointCloud。由于PointCloud规模较大，本文采取对PointCloud进行随机抽样后再集成的策略，限制PointCloud的规模。对PointCloud进行随机无回放抽样，每轮从中抽取100个样本，组成一个用于算法的PointCloud。共生成 3个不一样的PointCloud，用相同的训练数据集训练3个学习器之后进行投票集成。

在概念簇的计算中，参数k值设置为12，包的图拉普拉斯指数参数p=5。概念簇的个数设置是根据经验值得出的，由于在算法运行过程中可能有空簇的出现，因此设置稍大的k值即可，并不需要事先对k值进行精确的估算。分类器与2.1小节中的相同，均采用标准的SVM。表2记录了20个类别在上述实验设置下的分类正确率和方差。

从表2中可以看出，算法对不同类别的分类正确率差异较大。这是由于不同类别的图像所构成的空间光滑性是不一样的，部分类别的规律性比较明显，因此使用半监督学习得到的结果可能较好。对比文献[2]中使用DD-SVM 对该数据集进行学习的结果，本文的算法能够在训练样本较小（特别是正例较少）的情况下取得大致相当的结果，因此可以认为在大部分的情况下，半监督学习发挥了作用。不同的数据集有不同的内在分布规律，本实验只是使用同一种距离度量计算光滑性，因此不是最优的。若能针对不同数据集学习一种距离度量，将会得到更好的结果。通过包光滑性被结合到半监督多示例核中，在一定程度上提高了分类准确率。通过考虑包的不同特征，可以在算法中定义不同的多示例核，基于海明距离的光滑性定义能有效地反映包层的数据分布特征。与此同时，未标记数据的利用与多示例核的选择是完全独立的，使该算法框架有更广泛的适应性。

表2 Image2000的分类正确率

3 结论

本文提出基于半监督核的多示例学习框架，未标记数据通过包光滑性被结合到半监督多示例核中，在一定程度上提高了分类准确率。通过考虑包的不同特征，可以在算法中定义不同的多示例核，基于海明距离的光滑性定义能有效地反映出包层在的数据分布特征。与此同时，未标记数据的利用与多示例核的选择是完全独立的，使该算法框架有更广泛的适应性。

[1]Rahmani R,Goldman S A. MISSL: Multiple-instance semi-supervised learning [C]//Proc 23rd Intl. Conf. Mach.Learn. ACM,New York,NY,USA,2006: 705-712.

[2]Chen Y,Wang J Z. Image categorization by learning and reasoning with regions [J]. J. Mach. Learn. Res.,2004,5:913-939.

[3]Zhu X,Ghahramani Z,Lafferty J. Semi supervised learning using gaussian fields and harmonic functions [C]//Proc 20th Intl. Conf. Mach. Learn. ACM,New York,NY,USA,2003:912-919.

[4]Yangqing Jia,Changshui Zhang. Instance-level Semisupervised Multiple Instance Learning [C]//Proc 23rd Intl. Conf. AAAI.AAAI Press,2008: 640-645.

[5]M Belkin,P Niyogi,V Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples [J]. J. Mach. Learn. Res.,2006,7:2399-2434.

[6]Cucker,F. and Smale,S. On the mathematical foundations of learning [J]. Bull. Amer. Math. Soc. (N.S.),2002,39: 1-49.

[7]Vikas Sindhwani,Partha Niyogi,and Mikhail Belkin. Beyond the point cloud: from transductive to semi-supervised learning[C]//Proc 22th Intl. Conf. Mach. Learn.,ACM,New York,NY,USA,2005: 824-831.

[8]Gartner T,Flach P A,Kowalczyk A,et al. Multi-instance kernels[C]//Proc 19th Intl. Conf. Mach. Learn. Morgan Kaufmann Publishers Inc.,San Francisco: CA,USA,179-186.

[9]Zhou Zhi-Hua,Sun Yu-Yin,Li Yu-Feng. Multi-instance learning by treating instances as non-I.I.D. samples[C]//Proc 26th Intl. Conf. Mach. Learn. Montreal,Quebec,Canada,2009:1249-1256.

[10]James Foulds,Eibe Frank. A Review of Multi-Instance Learning Assumptions[J]. Knowledge Engineering Review,2011,25(1):1-25.

[11]Zhou Zhi-Hua,Zhang Min-Ling. Solving multi-instance problems with classifier ensemble based on constructive clustering[J]. Knowl. Inf. Syst. ,2007,11(2): 155-170.

[12]Aarti Singh,Robert Nowak,Zhu Xiaojin. Unlabeled data:Now it helps,now it doesn't[C]// Proc NPIS 2008. 2008,22.

[13]Andrew Goldberg,Xiaojin Zhu,Aarti Singh,et al.Multi-manifold semi-supervised learning[C]//In Twelfth International Conference on Artificial Intelligence and Statistics (AISTATS),2009.

[14]张钢,印鉴,程良伦,等.半监督多示例核[J].计算机科学,2011,38(9):220-223.