原信息與映射信息組合的多核學(xué)習(xí)降維方法

李 旭，王士同

江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無(wú)錫 214122

1 引言

分類算法中，如果樣本數(shù)據(jù)是線性不可分的，那么可以通過一個(gè)映射函數(shù)將樣本數(shù)據(jù)投影到高維空間中，從而在高維空間中能夠找到一個(gè)分類超平面[1]。核學(xué)習(xí)方法就是一種為解決數(shù)據(jù)線性不可分問題而產(chǎn)生的方法，早在1909年核方法[2]就已經(jīng)有理論證明和支撐，由Mercer提出的一系列基于數(shù)學(xué)證明的理論，即如今的Mercer定理便是這一理論支撐。目前，核方法在許多分類智能算法中都得到了比較成熟的發(fā)展，并且已經(jīng)取得了較為顯著的成效，如支持向量機(jī)（support vector machine，SVM）[3-5]、核鑒別分析（kernel fisher discriminant analysis）[6-7]等。

在核方法中，因?yàn)楹撕瘮?shù)的多種多樣，根據(jù)“沒有免費(fèi)午餐”定理（no free lunch theorem，NFL）[8]，任意的單一核函數(shù)無(wú)法適用于所有的具體任務(wù)場(chǎng)景。針對(duì)這一問題，Bach等[9]最早提出了多核學(xué)習(xí)的方法，他們提出的多核學(xué)習(xí)可以被看作是對(duì)核函數(shù)的集成學(xué)習(xí)，但與集成學(xué)習(xí)不同的是，集成學(xué)習(xí)針對(duì)的是多分類器系統(tǒng)的學(xué)習(xí)。

如今，對(duì)于核方法的研究已經(jīng)從單核發(fā)展到了多核，多核學(xué)習(xí)（multiple kernel learning，MKL）[10]已是核方法研究的重點(diǎn)。其內(nèi)容為，當(dāng)對(duì)一個(gè)目標(biāo)樣本進(jìn)行分類時(shí)，該目標(biāo)可能呈現(xiàn)出多種特征，需要從中選取出最適合的特征。多核學(xué)習(xí)可以把每一種特征都構(gòu)造成一個(gè)單獨(dú)的子核，然后把這些子核放到一個(gè)統(tǒng)一的框架內(nèi)，從而學(xué)習(xí)得到最優(yōu)的子核組合。多核學(xué)習(xí)的目標(biāo)就是將多個(gè)子核（或稱為基核）通過線性組合或非線性組合的學(xué)習(xí)方法得到一個(gè)多核函數(shù)（或者是一個(gè)多核矩陣，兩者只是表達(dá)方式不同），其實(shí)質(zhì)就是學(xué)習(xí)多個(gè)核函數(shù)的最優(yōu)凸組合[11]，得到這些特征所形成的單一核的權(quán)系數(shù)，從而組合成一個(gè)多核函數(shù)。

現(xiàn)實(shí)中，來(lái)源于圖像、視頻、文本等的樣本數(shù)據(jù)大都是上千維或者上萬(wàn)維的高維數(shù)據(jù)，直接應(yīng)用到各種算法中會(huì)導(dǎo)致所需求的內(nèi)存過于龐大，并且計(jì)算時(shí)間也會(huì)較長(zhǎng)，也就是會(huì)出現(xiàn)所謂的“維數(shù)災(zāi)難”問題。因此對(duì)于這些樣本數(shù)據(jù)來(lái)說，使用降維方法就是一種必要的手段。

降維就是為了避免產(chǎn)生高維度的維數(shù)災(zāi)難，以最大限度地保留高維數(shù)據(jù)的內(nèi)在信息為前提，將高維數(shù)據(jù)映射到低維空間中。各種降維的準(zhǔn)則形成了各種降維方法。

Lin等[12]在多核學(xué)習(xí)框架的基礎(chǔ)上提出了多核學(xué)習(xí)降維方法框架，并稱之為MKL-DR（multiple kernel learning for dimensionality reduction），它是由多種圖像描述子構(gòu)建多個(gè)基核，通過學(xué)習(xí)得到多個(gè)基核的組合權(quán)重系數(shù)，并將其構(gòu)造成一個(gè)多核矩陣的形式，結(jié)合降維方法并最終應(yīng)用到各種智能算法中。本文的工作便是在其基礎(chǔ)上進(jìn)行的。

近年來(lái)，流形學(xué)習(xí)已是降維領(lǐng)域的又一個(gè)研究熱點(diǎn)，結(jié)合流形學(xué)習(xí)的思想，即如果將外界的感知表示為高維空間中的點(diǎn)集，而這些感知輸入可能會(huì)有較強(qiáng)的相關(guān)性，可能會(huì)在一個(gè)低維流形上，或在低維流形的附近[13]，從有限的樣本數(shù)據(jù)中學(xué)習(xí)到潛在的流形問題從而達(dá)到降維目的，因此流形學(xué)習(xí)對(duì)降維有著重要意義。而核函數(shù)隱含地通過映射函數(shù)將數(shù)據(jù)投影到高維的特征空間，Lin等可能并未考慮某些隱含映射函數(shù)會(huì)否改變?cè)瓟?shù)據(jù)的流形結(jié)構(gòu)，因此便有了下文將原信息與映射信息結(jié)合的構(gòu)想和嘗試。

同一些其他的多核學(xué)習(xí)的優(yōu)化方法相比，如丁躍[14]對(duì)于多核學(xué)習(xí)的優(yōu)化方法是在局部多核學(xué)習(xí)方法的基礎(chǔ)上向目標(biāo)函數(shù)增加正則項(xiàng)，并修改其選通函數(shù)的范數(shù)形式，解決了選通函數(shù)的參數(shù)冗余問題，并使之具有更強(qiáng)的泛化能力；奚吉等[15]基于核目標(biāo)排列準(zhǔn)則優(yōu)化核函數(shù)的參數(shù)選取，能夠同時(shí)求解分類器的方程和基核的組合系數(shù)，降低算法的時(shí)間復(fù)雜度。本文的多核學(xué)習(xí)優(yōu)化方法著重考慮了流形結(jié)構(gòu)對(duì)組合多核的影響，這也恰恰是這些優(yōu)化算法所沒有考慮的，其優(yōu)點(diǎn)在于能夠消除核函數(shù)可能產(chǎn)生的扭曲，缺點(diǎn)在于沒有準(zhǔn)確的方法選擇合適的圖像描述子，并且受實(shí)驗(yàn)環(huán)境的影響較大。

2 多核學(xué)習(xí)降維方法及相關(guān)概念

2.1 降維

降維[16]可分為線性降維以及非線性降維。早期的線性降維技術(shù)處理的是線性的樣本數(shù)據(jù)，并假設(shè)各樣本數(shù)據(jù)點(diǎn)間是相互獨(dú)立的，使用歐氏距離作為樣本點(diǎn)間的相似性度量，這樣通過降維方法處理后的低維樣本數(shù)據(jù)同高維樣本數(shù)據(jù)之間是有線性關(guān)系的。其中比較有代表性的線性降維方法有主成分分析（principal component analysis，PCA）、線性判別分析（linear discriminant analysis，LDA）。

前面介紹過，大多數(shù)的現(xiàn)實(shí)樣本數(shù)據(jù)都是非線性的，雖然可以通過某些策略使得線性降維方法近似地處理一些非線性的樣本數(shù)據(jù)，但無(wú)法保證其結(jié)果，因此隨之便出現(xiàn)了許多非線性的降維方法，如核主成分分析（kernel principal component analysis，KPCA）以及核鑒別分析（kernel Fisher discriminant analysis，KFDA）等。本文提到的核方法便是一種解決此問題的有效方法，使用核技巧對(duì)線性降維方法進(jìn)行“核化”[11]就能夠使得線性降維方法應(yīng)用到非線性的樣本數(shù)據(jù)中。

2.2 圖嵌入

許多降維方法可以采用圖結(jié)構(gòu)來(lái)描述樣本間的鄰接關(guān)系，具有簡(jiǎn)單、直接、有效等特點(diǎn)，具體地說，圖嵌入[17]為大多數(shù)的降維算法提供了統(tǒng)一的表達(dá)形式，即式（1）。使用圖嵌入可以將一個(gè)降維方法表示為一個(gè)完全圖G，并且圖中所有的頂點(diǎn)構(gòu)成數(shù)據(jù)集，設(shè)W=[w]∈IRN×N為親和矩陣，用ij來(lái)描述訓(xùn)練集樣本間的相似關(guān)系，因此親和矩陣W是一個(gè)非負(fù)矩陣，并且當(dāng)xi和xj相鄰時(shí)，有wij=wji＞0。通過保持樣本點(diǎn)間權(quán)值的相似性來(lái)尋找圖在低維空間中的嵌入（又稱為映射矩陣）表示，那么，最優(yōu)的線性嵌入映射v*∈IRd可以由下式獲得：

其中，X=[x1x2…xN]是數(shù)據(jù)集Set的矩陣形式；L=diag(W?1)-W是完全圖G的拉普拉斯矩陣。根據(jù)所要解決問題的性質(zhì)，會(huì)從式（1）的兩個(gè)約束條件中選擇一個(gè)用于系數(shù)優(yōu)化。若是選擇了第一個(gè)約束條件，則會(huì)在尺度歸一化的過程中使用到對(duì)角矩陣D=[dij]∈IRN×N，并有D=diag(W?1)。否則，若是選擇了第二個(gè)限制條件，需要構(gòu)造另一個(gè)由所有的頂點(diǎn)覆蓋數(shù)據(jù)集Set的完全圖G′。其中，L′是完全圖G′的拉普拉斯矩陣，W′=[w′ij]∈IRN×N是完全圖G′的親和矩陣。

式（1）的優(yōu)化問題可以轉(zhuǎn)換成一個(gè)更直觀的表示：vTX=[vTx1vTx2…vTxN]表示投影，圖的拉普拉斯矩陣L（或L′）是投影樣本點(diǎn)間的鄰接距離，對(duì)角矩陣D用于加權(quán)地合并投影樣本點(diǎn)到原點(diǎn)的距離。更準(zhǔn)確地說，式（1）與下面的問題等價(jià)：

優(yōu)化問題（2）的約束條件表明圖嵌入模型僅僅需要投影樣本點(diǎn)到原點(diǎn)的距離或者是投影樣本點(diǎn)間的鄰接距離（以vTx表示）。通過改變親和矩陣W（或W′）和對(duì)角矩陣L（或L′）的值，例如PCA、LPP（locality preserving projection）等的降維算法都可以用式（1）表示。

2.3 多核學(xué)習(xí)

由于特征空間的維數(shù)可能很高，甚至是無(wú)窮維的，使用映射函數(shù)將特征空間中的樣本投影到更高的維數(shù)是極其困難的，所幸可以使用核方法解決這一問題。

（核函數(shù)）對(duì)所有x，z∈χ，χ?IRn，若有函數(shù)k:IRn×IRn→IR滿足：

則稱函數(shù)k為核函數(shù)。其中?是從輸入空間χ到特征空間Γ的映射，＜，＞表示內(nèi)積。

使用核函數(shù)就不用直接去計(jì)算高維甚至是無(wú)窮維特征空間中的內(nèi)積，而且不必關(guān)心如何選擇映射函數(shù)?(x)以及如何實(shí)現(xiàn)映射，只需要選擇合適的核函數(shù)[18]。常見的核函數(shù)包括線性核函數(shù)、多項(xiàng)式核函數(shù)、高斯核函數(shù)、拉普拉斯核函數(shù)、Sigmoid核函數(shù)等。當(dāng)選擇具體的核函數(shù)時(shí)，若不清楚使用哪個(gè)核函數(shù)的效果好，則可以先選擇高斯核函數(shù)進(jìn)行嘗試。

多核學(xué)習(xí)就是將不同特性的核函數(shù)進(jìn)行組合，以期望能獲得多類核函數(shù)的優(yōu)點(diǎn)，得到更優(yōu)的映射性能。組合的方法多種多樣，包括線性組合的合成方法、多核擴(kuò)展的合成方法等。

本文主要使用了線性組合的方法。下面主要介紹線性組合的方法。設(shè)有M個(gè)核函數(shù)km(x，z)（由于Km(i，j)=km(x，z)，可以使用核矩陣Km的形式表示核函數(shù)km(x，z)），通過線性組合可以將幾個(gè)基核表示成全局核函數(shù)k(x，z)（或核矩陣K，原因同上）。

（1）直接求和核

（2）加權(quán)求和核

（3）加權(quán)多項(xiàng)式拓展核

其中，核函數(shù)kp(x，z)（或核矩陣Kp）是核函數(shù)k(x，z)（或核矩陣K）的多項(xiàng)式擴(kuò)展。

實(shí)際上，SVM算法是一個(gè)用于二分類的分類器，對(duì)于樣本點(diǎn)數(shù)據(jù)，有xi∈IRd，yi∈{-1，+1}是類標(biāo)簽，那么SVM算法的判別式為f(x)=＜w，?(x)＞+b，通過優(yōu)化求解則可以得到從而可得：

2.4 多核學(xué)習(xí)降維框架

Kim等[20]提出，在給定的凸集內(nèi)核中學(xué)習(xí)得到最優(yōu)內(nèi)核并與用于二進(jìn)制數(shù)據(jù)的核Fisher判別分析（KFDA）相結(jié)合，從而提高核Fisher判別分析的性能。Lin等則在Kim提出的方法基礎(chǔ)上考慮通過多核學(xué)習(xí)來(lái)建立各種特征表示數(shù)據(jù)的維度的一般框架，即多核學(xué)習(xí)降維框架MKL-DR，這個(gè)框架可以應(yīng)用到有監(jiān)督學(xué)習(xí)、無(wú)監(jiān)督學(xué)習(xí)和半監(jiān)督學(xué)習(xí)算法中。本文只將這個(gè)框架應(yīng)用到了有監(jiān)督學(xué)習(xí)，無(wú)監(jiān)督學(xué)習(xí)與半監(jiān)督學(xué)習(xí)的降維過程同有監(jiān)督學(xué)習(xí)過程是一致的。下面就多核學(xué)習(xí)降維框架MKL-DR進(jìn)行詳細(xì)介紹。

2.5 核函數(shù)的選擇

設(shè)有一數(shù)據(jù)集Set有N個(gè)樣本，每個(gè)樣本由M種描述子表示其特征，令并有dm:χm×χm→0?IR+為應(yīng)用于第m個(gè)描述子的距離函數(shù)。使用各種描述子會(huì)使得數(shù)據(jù)的表現(xiàn)形式各不相同，Lin等使用核矩陣的形式統(tǒng)一各描述子。通過將數(shù)據(jù)的特征以及對(duì)應(yīng)的距離函數(shù)相結(jié)合，就能夠得到M個(gè)不同的基核矩陣{Km}Mm=1，有：

其中，σm叫作帶寬，是一個(gè)正值常量，對(duì)于徑向基函數(shù)的最終效果有著重大影響。由于采用了描述子以及距離函數(shù)，這些基核在處理可視化的學(xué)習(xí)任務(wù)時(shí)，會(huì)很方便而有效。式（13）中的核矩陣Km并不能保證是半正定的，在處理時(shí)，計(jì)算核矩陣最小的特征值，如果是負(fù)值，則將該特征值的絕對(duì)值加到核矩陣的每一個(gè)對(duì)角線元素上去。獲取M個(gè)核矩陣后，通過式（8）、式（9）、式（13）就能夠求得一組核權(quán)重系數(shù)的全局最優(yōu)解 {β1，β2，…，βM}，這組解就是M個(gè)由數(shù)據(jù)特征構(gòu)造的基核的核權(quán)重系數(shù)。

這里的徑向基核函數(shù)會(huì)使得數(shù)據(jù)在特征空間的流形結(jié)構(gòu)扭曲，破壞了原數(shù)據(jù)的流形結(jié)構(gòu)，因此本文希望能夠通過將一部分原信息與特征空間信息結(jié)合從而保持原數(shù)據(jù)的流形結(jié)構(gòu)，以此來(lái)達(dá)到改善降維效果的目的。

2.6 多核降維算法

多核學(xué)習(xí)降維中的核化過程同核PCA算法中的核化過程類似，不同點(diǎn)在于多核學(xué)習(xí)選擇的是多個(gè)基核的線性組合。

令?:x→Γ表示從低維特征向高維投影空間的映射關(guān)系，這個(gè)映射關(guān)系隱含在核矩陣中，通過?能將訓(xùn)練數(shù)據(jù)映射到高維的希爾伯特空間。

并且，式（1）、式（2）所表示的問題可以簡(jiǎn)化為解決XLXTv=λXL′XTv特征值問題，也就是說在映射后的訓(xùn)練集中可以找到這個(gè)最優(yōu)解v，可以表示為：

將映射后的樣本?(xi)替換式（2）中的xi，那么投影v將只在vT?(xi)中出現(xiàn)。vT?(xi)能夠通過核方法計(jì)算，如下：

IK(i)是樣本xi的核矩陣表示；KM(N，i)是第M個(gè)基核矩陣K(N，i)的值。

為了計(jì)算方便，先從低維的映射投影代替考慮高維的映射投影，再?gòu)牡途S情況下推廣到高維。由式（2）及式（16），可以定義一維空間中的多核學(xué)習(xí)降維的約束優(yōu)化如下：

其中，同式（5）、式（6）比較，新增的約束條件式（22）的目的是為了確保組合核的權(quán)系數(shù)為正數(shù)。

由式（16）可以看出，樣本系數(shù)向量α以及核權(quán)重系數(shù)向量β決定了一維投影v。為了將其推廣到多維的投影中，設(shè)有P個(gè)樣本系數(shù)向量，定義為：

每個(gè)一維向量投影vi由樣本系數(shù)向量αi以及核權(quán)重向量β決定。最終得到的投影V=[v1v2…vP]將樣本投影到P維的歐幾里德空間。形如一維的情況，投影后的樣本可以寫為：

從簡(jiǎn)單的一維情況推廣到多維的情況，那么，優(yōu)化問題式（20）應(yīng)用到多維映射投影拓展為下式：

如圖1，（a）～（d）依次為每個(gè)特征下的輸入空間、基核的再生核希爾伯特空間（reproducing kernel Hilbert space，RKHS）、組合核的再生核希爾伯特空間、投影后的歐幾里德空間。

3 多核學(xué)習(xí)優(yōu)化方法

上文對(duì)核函數(shù)的選擇以及Lin等的相關(guān)工作進(jìn)行了詳細(xì)的介紹，下文介紹新方法思路和系數(shù)優(yōu)化。

3.1 新方法介紹

式（13）中，核函數(shù)km(xi，xj)通過式（5）可以表述為：

其中，?(xi)就是樣本xi到高維的希爾伯特空間的投影。

根據(jù)原信息與特征信息組合的思路，現(xiàn)將xi按列向量的形式添加到其投影中，有：

Fig.1 4 kinds of spaces in multiple kernel learning for dimensionality reduction圖1 多核學(xué)習(xí)框架中數(shù)據(jù)在四種空間中的變化示意圖

將式（29）代入式（28），并記k′m為新的核函數(shù)，可得到：

使用現(xiàn)在的核函數(shù)k′m代替徑向基核函數(shù)，并依舊用Km(i，j)=km(xi，xj)表示這個(gè)新的核函數(shù)k′m，這樣上文中優(yōu)化問題的所有表達(dá)式就不需要進(jìn)行任何改動(dòng)。

從經(jīng)驗(yàn)上來(lái)說，多核學(xué)習(xí)中增加了一個(gè)新的核函數(shù)對(duì)其降維效果有正向的作用，其實(shí)質(zhì)就是增加了對(duì)數(shù)據(jù)描述的一個(gè)角度，當(dāng)然，特征的選擇要考慮空間和時(shí)間效率以及是否必要等方面。

Lin等的多核學(xué)習(xí)框架中使用徑向基核函數(shù)能夠無(wú)限逼近任意的曲線函數(shù)。而一個(gè)復(fù)雜函數(shù)會(huì)有一個(gè)線性部分，因此這里將線性核當(dāng)作其線性部分。

同時(shí)，若將式（30）添加一個(gè)加權(quán)系數(shù)δ，如式（31）?？梢杂^察到，式（31）就是式（11）所表示的加權(quán)多項(xiàng)式拓展核的形式。

圖2為新的多核函數(shù)組合示意圖。

Fig.2 Linear combination of new multiple kernel function圖2 新多核函數(shù)的線性組合示意圖

式（30）、式（31）這種組合是強(qiáng)耦合方式，因此這一對(duì)核優(yōu)化后得到的核權(quán)重系數(shù)將會(huì)是相同的或相關(guān)的，并且使用強(qiáng)耦合的方式會(huì)由于線性核與徑向基核的值域問題可能導(dǎo)致無(wú)法得到好的結(jié)果。

從上面的思路出發(fā)，式（30）若是使用弱耦合的方式則可以表示為：

設(shè)式（32）所表示的新核函數(shù)優(yōu)化得到其核權(quán)重系數(shù)βm，則有：

由于式（32）是一種弱耦合，那么可以直接將βmδ1與βmδ2分別表示為線性核權(quán)重系數(shù)βm1與高斯核權(quán)重系數(shù)βm2，并可通過下文的系數(shù)優(yōu)化方法得到。

使用線性核能夠保持更多原數(shù)據(jù)的信息量，從而更好地保持原數(shù)據(jù)的流形結(jié)構(gòu)，那么從式（32）可以看出，其實(shí)質(zhì)就是增加了與高斯核使用相同特征信息的線性核。那么直接使用線性核可以減少?gòu)牟煌嵌让枋鰯?shù)據(jù)所需要的特征信息，即減少了選擇的描述子，從而在空間上減少了需要的特征信息。在本文中，減少所需要的特征信息即是縮減了選擇的描述子的個(gè)數(shù)，因此可以省去一部分用于計(jì)算圖像描述子的時(shí)間，提高時(shí)間效率。

3.2 系數(shù)優(yōu)化

由于直接優(yōu)化式（25）是很困難的，可以使用交替優(yōu)化的方法優(yōu)化得到A和β。每次迭代固定其中的一個(gè)值A(chǔ)或β，然后下次迭代交換為另一個(gè)值固定，直到得到的值收斂或是達(dá)到最大迭代次數(shù)。正常情況下，無(wú)法判斷值的收斂性，因此需要設(shè)置合適的迭代次數(shù)。

當(dāng)優(yōu)化值A(chǔ)時(shí)：固定β并且根據(jù)列向量u有||u||2=trace(uuT)，因此式（25）的優(yōu)化問題可以轉(zhuǎn)化為：

式（34）優(yōu)化問題是一種跡的比值問題。根據(jù)文獻(xiàn)[21]及文獻(xiàn)[22]，通過將上述問題轉(zhuǎn)化為ratio trace問題，最終可以得到優(yōu)化的值A(chǔ)*=[α1α2…αP]。其中α1，2，…，P的最優(yōu)解問題就是求解一個(gè)最小化廣義特征值問題，取下式前P個(gè)最小特征值所對(duì)應(yīng)的特征向量：

當(dāng)優(yōu)化值β時(shí)：固定A值并且根據(jù)列向量u有||u||2=uTu，因此式（25）的優(yōu)化問題可以轉(zhuǎn)化為：

其中：

同式（34）比較，新增的約束條件β≥0導(dǎo)致了這個(gè)問題不再是廣義的特征值問題。實(shí)際上，這個(gè)問題是一種非凸的二次約束二次規(guī)劃問題（quadratically constrained quadratic program，QCQP），然而已知的是這個(gè)問題是難以解決的，因此使用一種放縮方法，引入大小為M×M的輔助矩陣B，有：

式（43）中的em是第m個(gè)元素為1，而其余元素為0的列向量；式（44）是一個(gè)半正定約束，也就是指式中的矩陣是一個(gè)半正定矩陣。因此式（41）所示的是一個(gè)非凸二次約束二次規(guī)劃問題的半正定放縮求解方法，然后就可以使用已經(jīng)較為成熟的SDP工具箱求解。其實(shí)，令式（44）中的B=ββT就可以看到式（41）等價(jià)于式（38）。B=ββT是非凸的，將其放縮為B?ββT。根據(jù)Schur補(bǔ)定理，式（44）等價(jià)于B?ββT（相關(guān)推導(dǎo)可以參考文獻(xiàn)[23]）。

式（41）中的約束條件是線性的，且其變量個(gè)數(shù)是關(guān)于M的二次式的，一般情況下，取得描述子的個(gè)數(shù)M都比較小，一般取M=4～10。相對(duì)其他的一些降維算法，Lin等提到多核學(xué)習(xí)降維算法的瓶頸在于如何處理計(jì)算復(fù)雜度為Ο(N3)的廣義特征值問題。

在多核學(xué)習(xí)降維算法系數(shù)優(yōu)化訓(xùn)練過程的交替優(yōu)化前，需要選擇β或A其中一個(gè)變量進(jìn)行初始化。若是選擇β，則令其所有的元素的值相等且其和為1，從而使得所有的基核的權(quán)重相等；若選擇A，令其滿足AAT=I就可以了。從經(jīng)驗(yàn)出發(fā)，選擇第二個(gè)初始化方法可以得到更穩(wěn)定的優(yōu)化結(jié)果，本文實(shí)驗(yàn)也是選擇的首先初始化值β。

3.3 系數(shù)優(yōu)化算法流程

步驟1初始化親和矩陣W及W′以及基于特征描述子的多個(gè)基核

步驟2初始化核權(quán)重向量β。

步驟3計(jì)算式（35）中的以及式（36）中的，然后通過式（37）對(duì)A進(jìn)行優(yōu)化求解。

步驟4計(jì)算式（39）中的以及式（40）中的然后通過式（41）以及SDP工具箱對(duì)β進(jìn)行優(yōu)化求解。

步驟5判斷是否達(dá)到最大迭代次數(shù)，未達(dá)到則轉(zhuǎn)步驟3；達(dá)到則輸出核權(quán)重向量β以及樣本系數(shù)向量A。

3.4 測(cè)試

設(shè)測(cè)試樣本為z，將其投影到低維空間可以表示為：

然后采用分類算法中的最近鄰法則等對(duì)測(cè)試數(shù)據(jù)進(jìn)行后續(xù)的處理操作，從而獲得測(cè)試數(shù)據(jù)的新類標(biāo)簽，最終與測(cè)試數(shù)據(jù)的原類標(biāo)簽對(duì)比得到分類算法的識(shí)別率。

4 實(shí)驗(yàn)

本文使用線性判別分析算法（即LDA）展示多核學(xué)習(xí)降維新方法，實(shí)驗(yàn)大部分是基于Lin等的工作，不同之處在于圖像描述子的選擇與使用。

4.1 數(shù)據(jù)集

本文實(shí)驗(yàn)使用的是由Li等整理的Caltech-101數(shù)據(jù)集[24]，總共有102個(gè)文件夾，對(duì)應(yīng)102個(gè)不同的類別，包括101個(gè)對(duì)象類別（如人臉、蝴蝶、圖案等）以及1個(gè)背景類別，每個(gè)類別包含的圖片數(shù)量各不相同，最少的為31張，最多的為800張，總共有9 146張圖片，每張圖片的大小大約為300×200像素。

4.2 圖像描述子與基核

本文沿用Lin等所選擇的一些特征描述子，再結(jié)合本文式（13）所示的徑向基核公式形成基核。

GB-Dist：隨機(jī)從圖像矩陣中選取400個(gè)邊緣化像素，然后用幾何模糊描述子處理選擇的像素。使用文獻(xiàn)[25]中的式（2）所表示的距離函數(shù)應(yīng)用到本文的式（13）生成一個(gè)基核。

GB：與GB-Dist描述子的不同點(diǎn)就是沒有使用幾何模糊描述子而直接用對(duì)應(yīng)的距離公式構(gòu)造基核。

SIFT-Dist：和GB-Dist構(gòu)造基核的過程一樣，只是使用了SIFT描述子代替GB描述子。

SIFT-SPM：將3個(gè)不同尺度的SIFT描述符應(yīng)用于每個(gè)圖像的均勻采樣網(wǎng)格，并從所有圖像的局部特征使用k均值聚類生成視覺詞。然后，基核通過文獻(xiàn)[26]中的匹配空間金字塔來(lái)構(gòu)建。

SS-Dist/SS-SPM：這兩個(gè)基核的構(gòu)造和SIFT-Dist/SIFT-SPM相同，只是使用self-similarity描述子代替SIFT描述子。其中，設(shè)置self-similarity每一塊的大小為5×5，窗口半徑為40。

C2-SWP/C2-ML：使用文獻(xiàn)[27]中的C2特征描述子及文獻(xiàn)[28]中的C2特征描述子，能夠獲得高斯基核。

PHOG：限制pyramid level為2，并使用距離公式χ2。

GIST：首先將圖片的圖像大小調(diào)整為128×128像素，再使用GIST描述子生成一個(gè)高斯基核。

上面介紹的圖像描述子中的參數(shù)以及對(duì)應(yīng)使用的距離函數(shù)是相互獨(dú)立，即基核是相互獨(dú)立的。

Lin等的實(shí)驗(yàn)選擇了上面的10個(gè)基核進(jìn)行多核學(xué)習(xí)，本文則在其基礎(chǔ)上進(jìn)行了相近的實(shí)驗(yàn)，不同的是分別使用了4～10個(gè)基核，用于同單核學(xué)習(xí)以及本文的新方法進(jìn)行對(duì)照。

從上述的圖像描述子的介紹中可以看到，類似GB與GB-Dist、SIFT與SIFT-Dist等這樣的基核，僅僅在圖像描述子的使用方法和距離函數(shù)的使用上不同，使用的描述子是相同的。新方法中，使用線性核與高斯核結(jié)合的方式，則可以描述為在這一對(duì)圖像描述子中選擇一個(gè)較合適的來(lái)生成線性核與高斯核。

4.3 降維方法

LDA算法要求數(shù)據(jù)集全部要帶有標(biāo)簽，并且數(shù)據(jù)要保持高斯分布。下文的實(shí)驗(yàn)中，為了區(qū)分本文所做的優(yōu)化方法與Lin等的MKL-LDA（multiple kernel learning-lineardiscriminantanalysis）算法，將本文的優(yōu)化方法簡(jiǎn)記為MKL-LDAOPT，其使用的親和矩陣為：

其中，nyi是擁有相同標(biāo)簽yi的個(gè)數(shù)。

4.4 參數(shù)設(shè)置

Caltech-101數(shù)據(jù)集總共有102個(gè)類別，對(duì)應(yīng)設(shè)置為102個(gè)類標(biāo)簽，由于每一類的圖片個(gè)數(shù)各不相等，最少的為31張，最多的為800張，因此統(tǒng)一取整為每類取樣30張圖片。將這102×30個(gè)樣本分割為訓(xùn)練集與測(cè)試集，設(shè)每一類取到的訓(xùn)練樣本個(gè)數(shù)為Ntrain，則測(cè)試集樣本個(gè)數(shù)為30-Ntrain。實(shí)驗(yàn)中取Ntrain分別為5、10、15、20、25，并且為了消除取樣造成的影響，在不同的訓(xùn)練樣本個(gè)數(shù)Ntrain下重復(fù)20次實(shí)驗(yàn)取平均值，每次實(shí)驗(yàn)隨機(jī)選取訓(xùn)練樣本以及測(cè)試樣本。

對(duì)于式（13）高斯核函數(shù)中帶寬參數(shù)σm的初始化設(shè)置是較難尋到最優(yōu)值的，一般是從經(jīng)驗(yàn)角度出發(fā)，通過設(shè)置一些特殊值，如[0.001,0.01,0.1,0.5,1,1.5,2,5,10,15]等試驗(yàn)性地進(jìn)行尋參。這里將采用另外一種策略，根據(jù)Km前Ntrain列的和與其余列的和的比值來(lái)確定最終的σm值。

下面是確定帶寬參數(shù)的算法步驟：

步驟1通過經(jīng)驗(yàn)初始化一組σm的取值范圍以及期望值，左右界分別記為left和right。

步驟2令σm的值為(left+right)/2。

步驟3計(jì)算核矩陣Km，獲得Km前Ntrain列的和與其余列的和的比值ratio。

步驟4通過步驟3得到的比值ratio判斷移動(dòng)左右界，若比值ratio大于期望值，令left=(left+right)/2；反之則需要移動(dòng)右界，令right=(left+right)/2。

步驟5判斷有無(wú)越界，比值ratio與期望值之差小于某一閾值以及是否達(dá)到最大的迭代次數(shù)，若為假則轉(zhuǎn)到步驟2，否則退出迭代，并且輸出σm，那么就得到了一個(gè)全局較優(yōu)的σm值。

4.5 結(jié)論分析

基于LDA分類算法的單核學(xué)習(xí)降維算法與多核學(xué)習(xí)降維算法的識(shí)別率如表1、表2所示。表2的MKL-LDAOPT實(shí)驗(yàn)中，當(dāng)圖像描述子個(gè)數(shù)M=4時(shí)，則使用的圖像描述子為GB、SIFT-SPM、SS-SPM、GB-SPM；當(dāng)圖像描述子個(gè)數(shù)M=5時(shí)，則使用的圖像描述子在表2中依上而下分別為GB、SIFTSPM、SS-SPM、C2-SWP、GIST和GB、SIFT-SPM、SS-SPM、C2-SWP、PHOG；當(dāng)M=6時(shí)，則使用的圖像描述子為GB、SIFT-SPM、SS-SPM、GB-SPM、GIST、PHOG。

為了同MKL-LDA OPT的結(jié)果進(jìn)行對(duì)比，表2中MKL-LDA的描述子個(gè)數(shù)M=4，5，6 時(shí) ，同 MKLLDA OPT所選擇的描述子是相同的，當(dāng)MKL-LDA的描述子個(gè)數(shù)M=7，8，9，10 時(shí)，則是依表1中的描述子從上至下逐個(gè)增加進(jìn)行實(shí)驗(yàn)所得。

從圖3中可以看出，由實(shí)線代表的多核學(xué)習(xí)降維方法的識(shí)別率明顯優(yōu)于由虛線代表的單核學(xué)習(xí)降維算法的識(shí)別率，驗(yàn)證了多核學(xué)習(xí)的優(yōu)越性。同時(shí)單核學(xué)習(xí)的實(shí)驗(yàn)結(jié)果也能夠證明在選擇圖像描述子時(shí)并非其效果越好，則在多核學(xué)習(xí)中使用效果就越好。

Fig.3 Recognition rate of SKL-DR and MKL-DR，MKL-DR OPT圖3 單核學(xué)習(xí)降維與多核學(xué)習(xí)降維的識(shí)別率

在表2和圖4中，MKL-LDA OPT的實(shí)驗(yàn)結(jié)果與MKL-LDA的實(shí)驗(yàn)結(jié)果相比較，可以觀察到二者使用的圖像描述子個(gè)數(shù)M都為4或5時(shí)，新方法的識(shí)別率已經(jīng)有了明顯的提高。

Table 1 Recognition rates of LDA-based classifiers on single kernel learning for dimensionality reduction algorithm表1 基于LDA分類算法的單核學(xué)習(xí)降維算法的識(shí)別率

Table 2 Recognition rates of LDA-based classifiers on multiple kernel learning for dimensionality reduction algorithm表2 基于LDA分類算法的多核學(xué)習(xí)降維算法的識(shí)別率

并且在圖4中，3條實(shí)線同另外的3條虛線非常貼合，表示使用新方法選擇了4或5個(gè)圖像描述子就幾乎能夠達(dá)到Lin等的方法選擇了7或8個(gè)圖像描述子時(shí)達(dá)到的算法識(shí)別率。

同時(shí)，可以看到在MKL-LDA的實(shí)驗(yàn)結(jié)果中，當(dāng)M=8時(shí)，其結(jié)果（即算法識(shí)別率）同M=9和M=10的實(shí)驗(yàn)結(jié)果相比幾乎沒有太大的提高。這也正如上文所說的，并不是選擇了越多的特征其描述越好。同時(shí)，本文新方法的實(shí)驗(yàn)結(jié)果也同MKL-LDA的情況一樣，當(dāng)M=6時(shí)，算法的識(shí)別率同M=5時(shí)的結(jié)果相比并未提高，并且可以對(duì)照當(dāng)M=5時(shí)，算法識(shí)別率有較大的差異。

Fig 4 Recognition rate of MKL-LDA and MKL-LDAOPT圖4 MKL-LDA與MKL-LDAOPT的識(shí)別率

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

本文引入流形學(xué)習(xí)的概念，并通過實(shí)驗(yàn)證明了將原信息與特征信息進(jìn)行組合的方法是有效的，并且減少了原方法所要選擇使用的圖像描述子的數(shù)量。同時(shí)計(jì)算每一個(gè)圖像描述子并構(gòu)建基核是很耗費(fèi)時(shí)間的，因此同達(dá)到的算法效果相同的原方法相比，減少圖像描述子能夠明顯縮短算法的運(yùn)行時(shí)間，從而在實(shí)際應(yīng)用中能夠提供一種更高效的思路。

文中使用原信息的全部信息與特征信息組合的方法并不好，因?yàn)槭褂迷畔⒌囊恍┚植啃畔⒕湍軌虮Ａ羝淞餍谓Y(jié)構(gòu)，而不需要所有的信息，這樣就會(huì)減少樣本的冗余，提高算法的時(shí)間效率。并且，文中第一次提到的線性核與高斯核的加權(quán)多項(xiàng)式拓展核的形式也不失為一種好的方法，不過需要找到一組合適的參數(shù)。

本文下一步將嘗試通過引用深度學(xué)習(xí)與流形學(xué)習(xí)相結(jié)合的思路對(duì)多核學(xué)習(xí)降維方法進(jìn)行優(yōu)化。