基于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.

（編輯趙勉）