朱昌明　梅成就　周日貴　魏萊　章夏芬

摘要：為克服傳統(tǒng)多視角分類(lèi)器無(wú)法充分最小化結(jié)構(gòu)風(fēng)險(xiǎn)的不足，提出基于Universum的多視角全局和局部結(jié)構(gòu)風(fēng)險(xiǎn)最小化模型。該模型采用Universum學(xué)習(xí)，利用有標(biāo)簽樣本生成大量包含分類(lèi)信息的無(wú)標(biāo)簽樣本，從而增加分類(lèi)器性能。這些信息有利于最小化結(jié)構(gòu)風(fēng)險(xiǎn)。通過(guò)在Mfeat、Reuters和Corel等3個(gè)多視角數(shù)據(jù)集上的試驗(yàn)可以發(fā)現(xiàn)，該模型可以提高多視角分類(lèi)器的性能，并可以更好地應(yīng)用到多視角數(shù)據(jù)集的分類(lèi)問(wèn)題中。

關(guān)鍵詞：

Universum學(xué)習(xí)； 多視角； 結(jié)構(gòu)風(fēng)險(xiǎn)

中圖分類(lèi)號(hào)： TP181

文獻(xiàn)標(biāo)志碼： 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引言

多視角分類(lèi)器可以用于處理多視角數(shù)據(jù)集的分類(lèi)。以圖1為例，假設(shè)有

一個(gè)網(wǎng)頁(yè)數(shù)據(jù)集X，它有4個(gè)樣本，每個(gè)樣本是一個(gè)網(wǎng)頁(yè)，且這4個(gè)樣本被平均分為2類(lèi)，一類(lèi)是與科學(xué)有關(guān)的網(wǎng)頁(yè)

[WTHX]x[WTBX]1和

[WTHX]x[WTBX]2，另一類(lèi)是與藝術(shù)娛樂(lè)有關(guān)的網(wǎng)頁(yè)

[WTHX]x[WTBX]3和

[WTHX]x[WTBX]4。對(duì)每個(gè)網(wǎng)頁(yè)而言，有3類(lèi)信息，分別是文本（text）、圖像（image）和視頻（video）。每類(lèi)信息可以被視為樣本的一個(gè)視角。若用

[WTHX]x[WTBX]（v）i來(lái)表示第i個(gè)樣本的第v個(gè)視角，則X（v）={

[WTHX]x[WTBX]（v）1，

[WTHX]x[WTBX]（v）2，

[WTHX]x[WTBX]（v）3，

[WTHX]x[WTBX]（v）4}表示數(shù)據(jù)集的第v個(gè)視角。因此，數(shù)據(jù)集X也可以被寫(xiě)為X={X（1），X（2），X（3）}。把這樣的X稱(chēng)為多視角數(shù)據(jù)集。多視角分類(lèi)器的目的在于通過(guò)學(xué)習(xí)已經(jīng)標(biāo)記的多視角樣本的信息訓(xùn)練出一個(gè)分類(lèi)器，對(duì)未知的多視角樣本進(jìn)行類(lèi)別標(biāo)定。針對(duì)多視角分類(lèi)器的設(shè)計(jì)而提出的學(xué)習(xí)過(guò)程被稱(chēng)為多視角學(xué)習(xí)[1]。多視角學(xué)習(xí)如今已被廣泛運(yùn)用于多視角聚簇[2]、手寫(xiě)數(shù)字識(shí)別[3]、人類(lèi)姿勢(shì)識(shí)別[4]、圖像識(shí)別[57]等領(lǐng)域，并取得了不錯(cuò)的成績(jī)。

傳統(tǒng)的多視角分類(lèi)器旨在最小化結(jié)構(gòu)風(fēng)險(xiǎn)，即最小化經(jīng)驗(yàn)風(fēng)險(xiǎn)（對(duì)訓(xùn)練樣本的識(shí)別誤差）與泛化風(fēng)險(xiǎn)（對(duì)測(cè)試樣本的預(yù)測(cè)誤差）之和。最小化結(jié)構(gòu)風(fēng)險(xiǎn)意味著多視角分類(lèi)器對(duì)訓(xùn)練樣本和測(cè)試樣本在總體上有較好的分類(lèi)性能。再者，一般情況下，由于數(shù)據(jù)

集通過(guò)聚簇的方式（如k均值、層次聚類(lèi)、核聚類(lèi)等）可以被分成多個(gè)子類(lèi)，同一子類(lèi)內(nèi)的樣本具有高相似度，而不同子類(lèi)之間的樣本相似度并不高。若把整個(gè)數(shù)據(jù)集所占據(jù)的空間視為全局空間，每個(gè)子類(lèi)所占據(jù)的空間視為局部空間，則基于全局空間和局部空間所實(shí)現(xiàn)的結(jié)構(gòu)風(fēng)險(xiǎn)最小化被稱(chēng)為全局和局部結(jié)構(gòu)風(fēng)險(xiǎn)最小化（global and local structural risk minimization， GLSRM）[8]。GLSRM的典型模型為

min JGLSRMJGLSRM=JG+ndi=1JLi+JGLS

（1）

式中：

JG=Remp+Rreg表示全局結(jié)構(gòu)風(fēng)險(xiǎn)（Remp為經(jīng)驗(yàn)風(fēng)險(xiǎn)，Rreg為泛化風(fēng)險(xiǎn)）；JLi=RLiemp+RLireg表示在第i個(gè)子空間中的局部結(jié)構(gòu)風(fēng)險(xiǎn)（RLiemp為經(jīng)驗(yàn)風(fēng)險(xiǎn)，RLireg為泛化風(fēng)險(xiǎn)）；

JGLS=f（JG-ndi=1JLi）

表示全局結(jié)構(gòu)風(fēng)險(xiǎn)與局部結(jié)構(gòu)風(fēng)險(xiǎn)之間的差異；nd表示子空間個(gè)數(shù)。在當(dāng)前的分類(lèi)器設(shè)計(jì)中，GLSRM模型處于起步階段，ZHU等[8]在2016年首次提出了該模型，但該模型僅被用在單視角問(wèn)題中，這就給提升多視角問(wèn)題的分類(lèi)性能提供了一個(gè)契機(jī)。

更進(jìn)一步，當(dāng)前傳統(tǒng)多視角分類(lèi)器普遍存在著分類(lèi)性能提升有限的問(wèn)題，這是由有標(biāo)簽訓(xùn)練樣本不足而導(dǎo)致的。眾所周知，有標(biāo)簽樣本是事先知道類(lèi)別標(biāo)簽的樣本，它們可以提供用于分類(lèi)器設(shè)計(jì)的有效分類(lèi)信息和先驗(yàn)信息。然而，在現(xiàn)實(shí)世界中，有標(biāo)簽樣本的數(shù)目是不多的，而且獲取和標(biāo)記該類(lèi)樣本需要消耗比較多的人力財(cái)力，故成本較大。這就使得傳統(tǒng)的分類(lèi)器性能受到有標(biāo)簽樣本的限制。幸運(yùn)的是，VAPNIK[9]在1982年提出用Universum學(xué)習(xí)來(lái)解決這一問(wèn)題。Universum學(xué)習(xí)以有限的有標(biāo)簽樣本為基礎(chǔ)，通過(guò)分析這些樣本之間的相似度，生成大量的無(wú)標(biāo)簽樣本。這些無(wú)標(biāo)簽樣本包含了原本有標(biāo)簽樣本的一些分類(lèi)信息，從而增加了更多有利于分類(lèi)器設(shè)計(jì)的信息。在Universum學(xué)習(xí)的指導(dǎo)下，近幾年出現(xiàn)了許多相關(guān)的分類(lèi)器，如CHERKASSKY等[10]提出的Universum支持向量機(jī)（Universum support vector machine， USVM），LIU等[11]提出的半U(xiǎn)niversum支持向量機(jī)（selfUniversum support vector machine， SUSVM）。相關(guān)試驗(yàn)已經(jīng)證實(shí)，在單視角問(wèn)題中，Universum學(xué)習(xí)可以帶來(lái)更好的分類(lèi)性能。

根據(jù)Universum學(xué)習(xí)和GLSRM模型所存在的提升空間，本文在Universum學(xué)習(xí)的基礎(chǔ)上提出基于Universum的多視角GLSRM（Universumbased multiview GLSRM， UMGLSRM）模型，從而提升多視角分類(lèi)器的性能。

1UMGLSRM模型框架

為解決有標(biāo)簽樣本不足的問(wèn)題，并把GLSRM模型應(yīng)用到多視角問(wèn)題中，本文提出了UMGLSRM模型。UMGLSRM模型由兩步構(gòu)成：第一步，利用Universum學(xué)習(xí)算法，以有標(biāo)簽樣本為基礎(chǔ)，生成大量無(wú)標(biāo)簽樣本；第二步，把無(wú)標(biāo)簽樣本和有標(biāo)簽樣本應(yīng)用到GLSRM模型框架中，并優(yōu)化求解，得到相關(guān)的最優(yōu)參數(shù)。

1.1利用Universum學(xué)習(xí)算法生成無(wú)標(biāo)簽樣本

為證明UMGLSRM模型的有效性，采用Mfeat、Reuters和Corel等3個(gè)典型的多視角數(shù)據(jù)集[1213]。

Mfeat數(shù)據(jù)集是多特征 （multiple features） 集，由0～9共10個(gè)數(shù)字的若干手寫(xiě)體數(shù)字構(gòu)成。每個(gè)數(shù)字由若干個(gè)案例構(gòu)成，每個(gè)案例就是一個(gè)人所寫(xiě)的數(shù)字樣本。每個(gè)數(shù)字有6個(gè)視角，分別是分布相關(guān)性（fac）、Fourier系數(shù)（fou）、KarhunenLove系數(shù)（kar）、2*3窗口中的像素平均值（pix）、Zernike矩（zer）和形態(tài)特征（mor）。每個(gè)視角的特征數(shù)表示該視角的信息由多少個(gè)維度值加以描述。針對(duì)每個(gè)數(shù)字，選擇2 000個(gè)手寫(xiě)體案例用于試驗(yàn)。表1為采用的Mfeat數(shù)據(jù)集的信息。

Reuters數(shù)據(jù)集是Reuters RCV1/RCV2多語(yǔ)種數(shù)據(jù)集，由多種機(jī)器翻譯的文檔構(gòu)成。該數(shù)據(jù)集中的文檔分別用5種不同的語(yǔ)言寫(xiě)成，這5種語(yǔ)言分別是英語(yǔ)（EN）、法語(yǔ)（FR）、德語(yǔ)（GR）、意大利語(yǔ)（IT）和西班牙語(yǔ)（SP）。每個(gè)文檔都可以轉(zhuǎn)變成與自身語(yǔ)言不同的其他語(yǔ)言的文檔。每種語(yǔ)言可被視為該數(shù)據(jù)集的一個(gè)視角。再者，該數(shù)據(jù)集中的文檔又被分為6個(gè)類(lèi)別，分別是C15、CCAT、E21、ECAT、GCAT和M11，每個(gè)類(lèi)別又被視為一種視角。表2和3為采用的Reuters數(shù)據(jù)集的信息。在語(yǔ)言視角下（見(jiàn)表2），樣本數(shù)是該語(yǔ)言標(biāo)識(shí)的文檔數(shù)目，特征數(shù)是該種語(yǔ)言文檔的單詞數(shù)目。在類(lèi)別視角下（見(jiàn)表3），樣本數(shù)是屬于該類(lèi)別的文檔數(shù)目，比例是屬于該類(lèi)別的文檔數(shù)目占所有文檔數(shù)目的百分?jǐn)?shù)。

Corel數(shù)據(jù)集是一個(gè)圖像數(shù)據(jù)集，取自多種不同類(lèi)別的物體。選取該數(shù)據(jù)集中的10類(lèi)物體。對(duì)于每類(lèi)物體，選擇100幅圖像，總計(jì)1 000幅圖像，即1 000個(gè)樣本。每個(gè)樣本有4個(gè)視角，分別為色彩柱狀圖（Colh）、色彩直方圖分布（Colhl）、顏色矩（Colm）和共生紋理（Coot）。每個(gè)視角的特征數(shù)表示該視角信息由多少個(gè)維度值表示。表4為采用的Corel數(shù)據(jù)集的信息。

首先，在測(cè)試準(zhǔn)確率（即被準(zhǔn)確分類(lèi)的測(cè)試樣本數(shù)占總的測(cè)試樣本數(shù)的比例）上進(jìn)行對(duì)比，見(jiàn)表6。從表6可知，UMGLSRM模型可以有效提升多視角數(shù)據(jù)集的分類(lèi)性能。從方差看，UMGLSRM模型的性能相對(duì)平穩(wěn)，不容易受到外界環(huán)境的影響。

然后，在時(shí)間復(fù)雜度上進(jìn)行對(duì)比，分析這4個(gè)模型在訓(xùn)練時(shí)間和測(cè)試時(shí)間上的差異，如表7所示。該表中，針對(duì)訓(xùn)練或測(cè)試時(shí)間，把MVML模型對(duì)每個(gè)數(shù)據(jù)集的訓(xùn)練或測(cè)試時(shí)間定為1，從而觀察其他模型與MVML模型在時(shí)間上的倍數(shù)關(guān)系。從結(jié)果可知，在測(cè)試時(shí)間上，各模型相差不大。UMGLSRM模型的測(cè)試時(shí)間會(huì)增加1%～2%。在訓(xùn)練時(shí)間上，相比MVML模型，UMGLSRM模型的訓(xùn)練時(shí)間平均會(huì)增加10%，這主要是由UMGLSRM模型需要執(zhí)行Universum步驟且模型相對(duì)復(fù)雜導(dǎo)致的。USVM模型與MVML模型的訓(xùn)練時(shí)間相當(dāng)，這主要是因?yàn)榍罢呒幢阈枰獔?zhí)行Universum步驟，也只是一個(gè)單視角分類(lèi)器，而后者是一個(gè)多視角分類(lèi)器，兩者在模型復(fù)雜度上相似。MVU模型是一個(gè)需要執(zhí)行Universum步驟的多視角分類(lèi)器，因此它比USVM模型和MVML模型復(fù)雜。然而，相比UMGLSRM模型，MVU模型相對(duì)簡(jiǎn)單。

從分類(lèi)和時(shí)間兩方面綜合分析可知，UMGLSRM模型的分類(lèi)性能比其他模型的高，其多出來(lái)的時(shí)間是可以接受的，從而證明了UMGLSRM模型的有效性。

3結(jié)束語(yǔ)

多視角問(wèn)題普遍存在于網(wǎng)頁(yè)、視頻、文本等分類(lèi)問(wèn)題中。為了處理多視角問(wèn)題，相關(guān)的多視角分類(lèi)器應(yīng)運(yùn)而生。傳統(tǒng)的多視角分類(lèi)器可以最小化結(jié)構(gòu)風(fēng)險(xiǎn)，即使訓(xùn)練樣本和測(cè)試樣本的分類(lèi)誤差盡可能小，但存在兩個(gè)問(wèn)題：（1）暫時(shí)沒(méi)有合適的模型能同時(shí)從全局和局部?jī)蓚€(gè)角度實(shí)現(xiàn)結(jié)構(gòu)風(fēng)險(xiǎn)的最小化；（2）由于缺少足夠的有標(biāo)簽樣本進(jìn)行訓(xùn)練，分類(lèi)器性能提升空間受到限制。

本文利用Universum學(xué)習(xí)生成大量包含分類(lèi)信息的無(wú)標(biāo)簽樣本，從而增加分類(lèi)信息，并將其與單視角問(wèn)題中已經(jīng)提出的全局和局部結(jié)構(gòu)風(fēng)險(xiǎn)最小化模型結(jié)合，用到多視角問(wèn)題中，從而提出一個(gè)基于Universum的多視角全局和局部結(jié)構(gòu)風(fēng)險(xiǎn)最小化模型，即UMGLSRM模型。在3個(gè)典型的多視角數(shù)據(jù)集上的試驗(yàn)驗(yàn)證了UMGLSRM模型可以以增加少量時(shí)間為代價(jià)，有效提升分類(lèi)性能，同時(shí)具有較低的Rademacher復(fù)雜度。

參考文獻(xiàn)：

[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.

（編輯趙勉）