基于Universum的多視角全局和局部結(jié)構(gòu)風(fēng)險最小化模型

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

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

關(guān)鍵詞：

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

中圖分類號： 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引言

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

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

[WTHX]x[WTBX]1和

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

[WTHX]x[WTBX]3和

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

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

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

min JGLSRMJGLSRM=JG+ndi=1JLi+JGLS

（1）

式中：

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

JGLS=f（JG-ndi=1JLi）

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

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

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

1UMGLSRM模型框架

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

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

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

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

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

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

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

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

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

3結(jié)束語

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

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

（編輯趙勉）