周一至周五 | 9:00—22:00

基于Universum的多视角全局和局部结构风险最小化模型

作者:未知

  摘要:为克服传统多视角分类器无法充分最小化结构风险的不足,提出基于Universum的多视角全局和局部结构风险最小化模型。该模型采用Universum学习,利用有标签样本生成大量包含分类信息的无标签样本,从而增加分类器性能。这些信息有利于最小化结构风险。通过在Mfeat、Reuters和Corel等3个多视角数据集上的试验可以发现,该模型可以提高多视角分类器的性能,并可以更好地应用到多视角数据集的分类问题中。
  关键词:
  Universum学习; 多视角; 结构风险
  中图分类号: TP181
  文献标志码: A
  Abstract:
  In order to overcome the disadvantage of traditional multiview classifiers that can not fully minimize structural risk, a Universumbased multiview global and local structural risk minimization model is proposed. The model uses Universum learning, which uses labeled samples to generate a large number of unlabeled samples containing classification information so as to enhance the performances of classifiers. This information helps minimize structural risks. Experiments on three multiview data sets, i.e., Mfeat, Reuters and Corel, show that the model can improve the performance of multiview classifiers and can be better applied to the classification of multiview data sets.
  Key words:
  Universum learning; multiview; structural risk
  0引言
  多视角分类器可以用于处理多视角数据集的分类。以图1为例,假设有
  一个网页数据集X,它有4个样本,每个样本是一个网页,且这4个样本被平均分为2类,一类是与科学有关的网页
  [WTHX]x[WTBX]1和
  [WTHX]x[WTBX]2,另一类是与艺术娱乐有关的网页
  [WTHX]x[WTBX]3和
  [WTHX]x[WTBX]4。对每个网页而言,有3类信息,分别是文本(text)、图像(image)和视频(video)。每类信息可以被视为样本的一个视角。若用
  [WTHX]x[WTBX](v)i来表示第i个样本的第v个视角,则X(v)={
  [WTHX]x[WTBX](v)1,
  [WTHX]x[WTBX](v)2,
  [WTHX]x[WTBX](v)3,
  [WTHX]x[WTBX](v)4}表示数据集的第v个视角。因此,数据集X也可以被写为X={X(1),X(2),X(3)}。把这样的X称为多视角数据集。多视角分类器的目的在于通过学习已经标记的多视角样本的信息训练出一个分类器,对未知的多视角样本进行类别标定。针对多视角分类器的设计而提出的学习过程被称为多视角学习[1]。多视角学习如今已被广泛运用于多视角聚簇[2]、手写数字识别[3]、人类姿势识别[4]、图像识别[57]等领域,并取得了不错的成绩。
  传统的多视角分类器旨在最小化结构风险,即最小化经验风险(对训练样本的识别误差)与泛化风险(对测试样本的预测误差)之和。最小化结构风险意味着多视角分类器对训练样本和测试样本在总体上有较好的分类性能。再者,一般情况下,由于数据
  集通过聚簇的方式(如k均值、层次聚类、核聚类等)可以被分成多个子类,同一子类内的样本具有高相似度,而不同子类之间的样本相似度并不高。若把整个数据集所占据的空间视为全局空间,每个子类所占据的空间视为局部空间,则基于全局空间和局部空间所实现的结构风险最小化被称为全局和局部结构风险最小化(global and local structural risk minimization, GLSRM)[8]。GLSRM的典型模型为
  min JGLSRMJGLSRM=JG+ndi=1JLi+JGLS
  (1)
  式中:
  JG=Remp+Rreg表示全局结构风险(Remp为经验风险,Rreg为泛化风险);JLi=RLiemp+RLireg表示在第i个子空间中的局部结构风险(RLiemp为经验风险,RLireg为泛化风险);
  JGLS=f(JG-ndi=1JLi)
  表示全局结构风险与局部结构风险之间的差异;nd表示子空间个数。在当前的分类器设计中,GLSRM模型处于起步阶段,ZHU等[8]在2016年首次提出了该模型,但该模型仅被用在单视角问题中,这就给提升多视角问题的分类性能提供了一个契机。
  更进一步,当前传统多视角分类器普遍存在着分类性能提升有限的问题,这是由有标签训练样本不足而导致的。众所周知,有标签样本是事先知道类别标签的样本,它们可以提供用于分类器设计的有效分类信息和先验信息。然而,在现实世界中,有标签样本的数目是不多的,而且获取和标记该类样本需要消耗比较多的人力财力,故成本较大。这就使得传统的分类器性能受到有标签样本的限制。幸运的是,VAPNIK[9]在1982年提出用Universum学习来解决这一问题。Universum学习以有限的有标签样本为基础,通过分析这些样本之间的相似度,生成大量的无标签样本。这些无标签样本包含了原本有标签样本的一些分类信息,从而增加了更多有利于分类器设计的信息。在Universum学习的指导下,近几年出现了许多相关的分类器,如CHERKASSKY等[10]提出的Universum支持向量机(Universum support vector machine, USVM),LIU等[11]提出的半Universum支持向量机(selfUniversum support vector machine, SUSVM)。相关试验已经证实,在单视角问�}中,Universum学习可以带来更好的分类性能。   根据Universum学习和GLSRM模型所存在的提升空间,本文在Universum学习的基础上提出基于Universum的多视角GLSRM(Universumbased multiview GLSRM, UMGLSRM)模型,从而提升多视角分类器的性能。
  1UMGLSRM模型框架
  为解决有标签样本不足的问题,并把GLSRM模型应用到多视角问题中,本文提出了UMGLSRM模型。UMGLSRM模型由两步构成:第一步,利用Universum学习算法,以有标签样本为基础,生成大量无标签样本;第二步,把无标签样本和有标签样本应用到GLSRM模型框架中,并优化求解,得到相关的最优参数。
  1.1利用Universum学习算法生成无标签样本
  为证明UMGLSRM模型的有效性,采用Mfeat、Reuters和Corel等3个典型的多视角数据集[1213]。
  Mfeat数据集是多特征 (multiple features) 集,由0~9共10个数字的若干手写体数字构成。每个数字由若干个案例构成,每个案例就是一个人所写的数字样本。每个数字有6个视角,分别是分布相关性(fac)、Fourier系数(fou)、KarhunenLove系数(kar)、2*3窗口中的像素平均值(pix)、Zernike矩(zer)和形态特征(mor)。每个视角的特征数表示该视角的信息由多少个维度值加以描述。针对每个数字,选择2 000个手写体案例用于试验。表1为采用的Mfeat数据集的信息。
  Reuters数据集是Reuters RCV1/RCV2多语种数据集,由多种机器翻译的文档构成。该数据集中的文档分别用5种不同的语言写成,这5种语言分别是英语(EN)、法语(FR)、德语(GR)、意大利语(IT)和西班牙语(SP)。每个文档都可以转变成与自身语言不同的其他语言的文档。每种语言可被视为该数据集的一个视角。再者,该数据集中的文档又被分为6个类别,分别是C15、CCAT、E21、ECAT、GCAT和M11,每个类别又被视为一种视角。表2和3为采用的Reuters数据集的信息。在语言视角下(见表2),样本数是该语言标识的文档数目,特征数是该种语言文档的单词数目。在类别视角下(见表3),样本数是属于该类别的文档数目,比例是属于该类别的文档数目占所有文档数目的百分数。
  Corel数据集是一个图像数据集,取自多种不同类别的物体。选取该数据集中的10类物体。对于每类物体,选择100幅图像,总计1 000幅图像,即1 000个样本。每个样本有4个视角,分别为色彩柱状图(Colh)、色彩直方图分布(Colhl)、颜色矩(Colm)和共生纹理(Coot)。每个视角的特征数表示该视角信息由多少个维度值表示。表4为采用的Corel数据集的信息。
  首先,在测试准确率(即被准确分类的测试样本数占总的测试样本数的比例)上进行对比,见表6。从表6可知,UMGLSRM模型可以有效提升多视角数据集的分类性能。从方差看,UMGLSRM模型的性能相对平稳,不容易受到外界环境的影响。
  然后,在时间复杂度上进行对比,分析这4个模型在训练时间和测试时间上的差异,如表7所示。该表中,针对训练或测试时间,把MVML模型对每个数据集的训练或测试时间定为1,从而观察其他模型与MVML模型在时间上的倍数关系。从结果可知,在测试时间上,各模型相差不大。UMGLSRM模型的测试时间会增加1%~2%。在训练时间上,相比MVML模型,UMGLSRM模型的训练时间平均会增加10%,这主要是由UMGLSRM模型需要执行Universum步骤且模型相对复杂导致的。USVM模型与MVML模型的训练时间相当,这主要是因为前者即便需要�绦�Universum步骤,也只是一个单视角分类器,而后者是一个多视角分类器,两者在模型复杂度上相似。MVU模型是一个需要执行Universum步骤的多视角分类器,因此它比USVM模型和MVML模型复杂。然而,相比UMGLSRM模型,MVU模型相对简单。
  从分类和时间两方面综合分析可知,UMGLSRM模型的分类性能比其他模型的高,其多出来的时间是可以接受的,从而证明了UMGLSRM模型的有效性。
  3结束语
  多视角问题普遍存在于网页、视频、文本等分类问题中。为了处理多视角问题,相关的多视角分类器应运而生。传统的多视角分类器可以最小化结构风险,即使训练样本和测试样本的分类误差尽可能小,但存在两个问题:(1)暂时没有合适的模型能同时从全局和局部两个角度实现结构风险的最小化;(2)由于缺少足够的有标签样本进行训练,分类器性能提升空间受到限制。
  本文利用Universum学习生成大量包含分类信息的无标签样本,从而增加分类信息,并将其与单视角问题中已经提出的全局和局部结构风险最小化模型结合,用到多视角问题中,从而提出一个基于Universum的多视角全局和局部结构风险最小化模型,即UMGLSRM模型。在3个典型的多视角数据集上的试验验证了UMGLSRM模型可以以增加少量时间为代价,有效提升分类性能,同时具有较低的Rademacher复杂度。
  参考文献:
  [1]
  XU Yumeng, WANG Changdong, LAI Jianhuang. Weighted multiview clustering with feature selection[J]. Pattern Recognition, 2016, 53: 2535.
  [2]SUN Shiliang, ZHANG Qingqiu. Multipleview multiplelearner semisupervised learning[J]. Neural Processing Letters, 2011, 34: 229240.   [3]DENG Muqing, WANG Cong, CHEN Qingfeng. Human gait recognition based on deterministic learning through multiple views fusion[J]. Pattern Recognition Letters, 2016, 78: 5663. DOI: 10.1016/j.patrec.2016.04.004.
  [4]WU Fei, JING Xiaoyuan, YOU Xinge, et al. Multiview lowrank dictionary learning for image classification[J]. Pattern Recognition, 2016, 50: 143154. DOI: 10.1016/j.patcog.2015.08.012.
  [5]ZHU Songhao, SUN Xian, JIN Dongliang. Multiview semisupervised learning for image classification[J]. Neurocomputing, 2016, 208: 136142. DOI: 10.1016/j.neucom.2016.02.072.
  [6]WANG Huiyan, WANG Xun, ZHENG Jia, et al. Video object matching across multiple nonoverlapping camera views based on multifeature fusion and incremental learning[J]. Pattern Recognition, 2014, 47(12): 38413851. DOI: 10.1016/j.patcog.2014.06.019.
  [7]TZORTZIS G, LIKAS A. Kernelbased weighted multiview clustering[C]//IEEE 12th International Conference on Data Mining, 2012: 675684.
  [8]ZHU Changming, WANG Zhe, GAO Daqi. New design goal of a classifier: global and local structural risk minimization[J]. KnowlegdeBased Systems, 2016, 100: 2549. DOI: 10.1016/j.knosys.2016.02.002.
  [9]VAPNIK V. Estimation of dependences based on empirical data[M]. Springer, 2006.
  [10]CHERKASSKY V, DAI Wuyang. Empirical study of the Universum SVM learning for highdimensional data[J]. Lecture Notes in Computer Science, 2009, 5768: 932941.
  [11]LIU Dalian, TIAN Yingjie, BIE Rongfang, et al. SelfUniversum support vector machine[J]. Personal and Ubiquitous Computing, 2014, 18(8): 18131819. DOI: 10.1007/s0077901407979.
  [12]XU Yumeng, WANG Changdong, LAI Jianhuang. Weighted multiview clustering with feature selection[J]. Pattern Recognition, 2016, 53: 2535. DOI: 10.1016/j.patcog.2015.12.007.
  [13]ZHU Changming. Doublefold localized multiple matrix learning machine with Universum[J]. Pattern Analysis and Application, 2017, 20: 10911118. DOI: 10.1007/s1004401605489.
  [14]WANG Zhe, ZHU Yujin, LIU Wenwen, et al. Multiview learning with Universum[J]. KnowledgeBased Systems, 2014, 70: 376391. DOI: 10.1016/j.knosys.2014.07.019.
  [15]MENDELSON S. Rademacher averages and phase transitions in glivenkocantelli classes[J]. IEEE Transactions on Information Theory, 2002, 48(1): 251263.
  [16]KOLTCHINSKII V, PANCHENKO D. Rademacher processes and bounding the risk of function learning[M]. Springer: High Dimensional Probability II, 2000: 443459. DOI: 10.1007/9781461213581_29.
  (�辑赵勉)


常见问题解答