基于支持向量機(jī)的信息檢索方法研究

紀(jì) 凱，韓 棟

(1.安徽交通職業(yè)技術(shù)學(xué)院 土木工程系，安徽合肥230051;2.法國格勒諾布爾計(jì)算機(jī)實(shí)驗(yàn)室，法國伊澤爾省格勒諾布爾市38000)

1 引言

多媒體索引是從媒體數(shù)據(jù)中提取出特定的信息線索，然后根據(jù)這些線索在大量媒體數(shù)據(jù)中查找，檢索出具有相似特征的數(shù)據(jù)。它分為兩個(gè)主要層次:低層次信號特征(如顏色、質(zhì)地表述信息，例如直方圖等)和高層次的語義特征(如概念或者事件表述，例如定義跑步這個(gè)動(dòng)作等)?；谛盘柼卣鲗用?即低層次)的索引通過機(jī)器學(xué)習(xí)完全自動(dòng)化，因此用戶可以非常方便的使用，比如醫(yī)生對搜索出圖像中較暗或較亮的區(qū)域很感興趣。然而低層次的語義索引常常忽略文件中用戶最感興趣的語義信息，同時(shí)某些低級別特性表述也難以方便應(yīng)用。而高層次的以語義特征為基礎(chǔ)的索引方法卻有許多優(yōu)勢，是更自然更接近人類感知的查詢，但也是最困難的，因?yàn)榇嬖凇罢Z義鴻溝”問題。如圖1所示，在數(shù)據(jù)庫中搜索“美國總統(tǒng)奧巴馬喝啤酒”，就需要解決計(jì)算機(jī)存儲原始數(shù)據(jù)和人類認(rèn)知數(shù)據(jù)之間的語義鴻溝。其中一個(gè)解決方法是給定查詢，即手動(dòng)標(biāo)注數(shù)據(jù)庫，通過機(jī)器學(xué)習(xí)模型建立圖像視覺內(nèi)容和高層語義概念的聯(lián)系。這種方法對少量數(shù)據(jù)檢索非常有效，但隨著是數(shù)據(jù)集規(guī)模越來越大，需要更加耗時(shí)耗力的工作。因此需要基于機(jī)器學(xué)習(xí)理論的自動(dòng)搜索方法來完成此類任務(wù)，即通過低層次的語義知識，經(jīng)過訓(xùn)練標(biāo)注為正和負(fù)的樣本(即訓(xùn)練集)來生成模型，然后用此模型來預(yù)測未標(biāo)記的數(shù)據(jù)。

2 基于內(nèi)容的多媒體索引和檢索(CBMIR)

圖1 語義鴻溝示例

基于內(nèi)容(語義概念描述)CBMIR(Content－Based Multimedia Retrieval)的索引和檢索被認(rèn)為是下一代文件索引和檢索方法。它可以從低層次特征抽象出高層語義概念，比如關(guān)鍵字語義概念和文件系統(tǒng)進(jìn)行交互。但對于同一個(gè)概念，可以用不同的顏色和形狀進(jìn)行表述，因此如何將抽象語義概念與視覺功能關(guān)聯(lián)是并不容易，這需要在檢測時(shí)用相關(guān)概念知識來避免歧義。圖片和視頻概念索引是一個(gè)顯著的基于內(nèi)容的搜索。首先需要一個(gè)訓(xùn)練集樣本，對每個(gè)目標(biāo)概念注釋為正或負(fù)。通過監(jiān)督學(xué)習(xí)訓(xùn)練集的低級別特征描述生成檢測分類器。監(jiān)督學(xué)習(xí)結(jié)束后，語義表征的問題表示為:“給定一組低級別的特(X)和一組概念(C)，每個(gè)屬于低級別特征的樣品x(x∈X)最有可能屬于的那一個(gè)概念c(c∈C)?”。對于一組給定的N 個(gè)訓(xùn)練樣本{(x1，y1)，(x2，y2)，…，(xN，yN)}，其中輸入值xi(即低層次的特征向量)形成了一個(gè)特征空間X，輸出值yi(即目標(biāo)類)有一個(gè)屬于無限集合C的類標(biāo)注c。一個(gè)基于訓(xùn)練數(shù)據(jù)的分類規(guī)則就是對于給定一個(gè)新的輸入值x，找出概率最高的一個(gè)屬于概念集合C的某一個(gè)類c。如圖2，一個(gè)自動(dòng)檢索系統(tǒng)包括建模和索引。對于給定的一個(gè)目標(biāo)概念，比如飛機(jī)，在建模階段學(xué)習(xí)訓(xùn)練集的描述及其關(guān)聯(lián)標(biāo)注之間的關(guān)系，產(chǎn)生一個(gè)分類模型。索引階段是將該模型施加于未標(biāo)注的樣本(即測試集)。對于每組樣品，它會產(chǎn)生最大似然學(xué)習(xí)的一組預(yù)測分?jǐn)?shù)，檢索任務(wù)就可以通過測試樣品的預(yù)測分?jǐn)?shù)實(shí)現(xiàn)，即分?jǐn)?shù)靠前的被認(rèn)為是可能性最大的正確樣品類別。圖2中兩幅待分類圖片，第一個(gè)圖片是飛機(jī)的可能性是0.85，而第二個(gè)圖片是飛機(jī)的可能性是0.15，因此認(rèn)為第一個(gè)圖片是飛機(jī)的可能性最大。

本文中基于支持向量機(jī)的信息檢索的研究目的是研究基于內(nèi)容的圖像和視頻檢索方法，并由此嘗試應(yīng)用于其他領(lǐng)域，比如數(shù)據(jù)庫中遙感圖像分類技術(shù)。研究工作主要包括提出合適的文件描述和建立分類器的先進(jìn)機(jī)器學(xué)習(xí)技術(shù)兩個(gè)兩部分。其中第二部分將是研究的重點(diǎn)。

圖2 基本內(nèi)容多媒體檢索體系結(jié)構(gòu)

3 分類過程

分類是將一個(gè)實(shí)體中相似的部分結(jié)合成不同類別的過程。例如，書籍可以按他們的書名，作者或出版年份分類。在計(jì)算機(jī)科學(xué)中，分類本質(zhì)上是基于機(jī)器學(xué)習(xí)技術(shù)，目的是學(xué)習(xí)目標(biāo)類和每個(gè)樣品特性之間的關(guān)系。因此需要一些例子來學(xué)習(xí)這些關(guān)系，稱之為學(xué)習(xí)集。學(xué)習(xí)方法主要有兩種:監(jiān)督學(xué)習(xí)和和非監(jiān)督學(xué)習(xí)。在監(jiān)督學(xué)習(xí)中，訓(xùn)練集合中的每個(gè)例子是一對數(shù)據(jù)集，包含一個(gè)輸入樣本(例如直方圖等低級別的特征描述)和目標(biāo)輸出值(例如標(biāo)注為正或者負(fù))。通過學(xué)習(xí)算法分析該訓(xùn)練集來產(chǎn)生分類器。而第二類型的無監(jiān)督學(xué)習(xí)，可以發(fā)現(xiàn)在未標(biāo)注數(shù)據(jù)中的隱藏結(jié)構(gòu)問題。因?yàn)榇藭r(shí)數(shù)據(jù)是未標(biāo)記的，沒有最小化誤差。這在數(shù)據(jù)聚類問題中非常有用，其中最常用的算法是K－means(K－均值)。

監(jiān)督學(xué)習(xí)算法是此次研究主要采用的方法，它有判別模型和生成模型。生成模型是指定的聯(lián)合概率P(x，y)，包括低級別的特征矢量x和其相關(guān)聯(lián)的標(biāo)記y。概率估計(jì)常見方法是將含有目標(biāo)概念的數(shù)據(jù)的最大似然化，然后貝葉斯規(guī)則可以用來確定最可能的類。一方面，他們可以從部分標(biāo)注數(shù)據(jù)學(xué)習(xí)，也可以在增量學(xué)習(xí)中使用。另一方面，識別模型被用于模擬一個(gè)不可觀測變量y對所觀察到的變量x的依賴。它可以被用來模擬條件概率分布P(y|x)，從而實(shí)現(xiàn)從一個(gè)給定的x到y(tǒng)的預(yù)測。判別模型通常會對分類和不需要聯(lián)合分布的回歸過程產(chǎn)生非常好的效果。

一般而言，生成模型比判別模型在復(fù)雜學(xué)習(xí)任務(wù)表述依賴關(guān)系時(shí)更加靈活。然而，它需要比判別模型有更多的時(shí)間進(jìn)行訓(xùn)練，于是提出了內(nèi)核學(xué)習(xí)方法，一個(gè)典型例子就是支持向量機(jī)(SVM:Support Machine Learning)。其原理是希望用特殊的內(nèi)核以克服非線性分離數(shù)據(jù)的問題，即將初始數(shù)據(jù)投影到高維空間，然后線性化解決問題。下文將介紹基于監(jiān)督學(xué)習(xí)的支持向量機(jī)方法。

4 支持向量機(jī)

支持向量機(jī)(SVM)是一種非常流行和有效的數(shù)據(jù)分類學(xué)習(xí)方法。它的基本思想是，對于屬于一個(gè)或兩個(gè)類的一組數(shù)據(jù)樣本，SVM是通過一個(gè)盡可能寬的分界區(qū)間，發(fā)現(xiàn)一個(gè)可以完美分離d維數(shù)據(jù)(到其兩個(gè)類)的超平面，并最大化這兩個(gè)類到超平面距離。

圖3 二維空間線性分離

SVM的最大邊緣超平面和超平面是通過兩類樣本的訓(xùn)練獲得的。圖3給出了SVM應(yīng)用于二維空間線性分離，如圖所示，在邊緣上的樣本稱為支持向量，H表示超平面，它可以分離黑色和白色的樣品。然而，由于數(shù)據(jù)樣本通常不是線性可分離的，SVM的引入“內(nèi)核誘導(dǎo)特征空間”的概念，通過內(nèi)核函數(shù)將其中的數(shù)據(jù)映射到一個(gè)可以分離的高維空間。通常，內(nèi)核函數(shù)是基于樣品(描述體)的相似性，提供了比給定類的描述符本身更多的信息。

為了找到超平面分離器，利用拉格朗日算子選擇支持向量的一個(gè)定義超平面的子集。這個(gè)過程有很大的好處，因?yàn)橹蜗蛄亢喕图铀倭怂饕牡谝浑A段(即建立模型)，其中只有一部分支持向量會影響新樣本的索引。即對于一個(gè)二元分類問題，給定一個(gè)大小為n的訓(xùn)練集T:

其中xi和yi分別表示訓(xùn)練矢量和目標(biāo)值T中第i個(gè)樣本，并且i=1，…，N。分類超平面被定義為:

其中Φ(.)是從數(shù)據(jù)集 Rd映射到更高維的Hilbert希爾伯特空間H，〈.，.〉表示在H超平面的點(diǎn)積，決定函數(shù)f(x)為:

支持向量機(jī)的目標(biāo)是找到一個(gè)最佳超平面與兩個(gè)預(yù)定義的類之間的最大間隔。這可通過轉(zhuǎn)化為求解下面的二次優(yōu)化問題來獲得:

通過定義一個(gè)映射z=Φ(x)的變換將d維輸入向量x映射到(通常較高)d維向量z。目標(biāo)是選擇一個(gè)Φ()，以便新的訓(xùn)練數(shù)據(jù){Φ(xi)，yi}是一個(gè)可分的超平面。值得注意的是，Φ(xi)是與其他Φ(xj)的點(diǎn)積。也就是說，如果知道公式(即內(nèi)核)，即對于用在高維特征空間中的點(diǎn)積:

則不必直接處理映射z=Φ(xi)。最流行的內(nèi)核是徑向基函數(shù)(Radial Basis Function，RBF)，也被稱為高斯核函數(shù)，被定義為:

其中，|.|是 L2 歐式范數(shù)，xi，xj是兩個(gè)不同的輸入向量，σ是一個(gè)可調(diào)高斯參數(shù)，可通過固定交叉驗(yàn)證。這導(dǎo)致了一個(gè)稱為內(nèi)核矩陣或“克矩陣”的對稱矩陣，它表示每對輸入矢量之間的相似性。原則上，可以使用唯一的相似的功能，導(dǎo)致內(nèi)核矩陣滿足默瑟條件(正定的特征值)。

5 結(jié)論

本文通過研究基于內(nèi)容的信息檢索方法，根據(jù)機(jī)器學(xué)習(xí)理論，提出利用支持向量機(jī)的方法建立圖像分類器，將用于訪問系統(tǒng)數(shù)據(jù)。由于目前沒有任何一種可適用于所有數(shù)據(jù)類型的分類器，應(yīng)根據(jù)不同數(shù)據(jù)不斷改進(jìn)提高現(xiàn)有方法。

［1］SMEULDERS，A.W.M.，WORRING，M.，SANTINI，S.，GUPTA，A.and JAIN，R.Content-based image retrieval at the end of the early years.IEEE Trans.Pattern Anal.Mach.Intell，2000.

［2］B.SAFADIand G.QUENOT.Evaluations ofmulti－learners approaches for concepts indexing in video documents.RIAO，Apr 2010:88 －91，Paris，F(xiàn)rance.

［3］徐險(xiǎn)峰.基于內(nèi)容的多媒體信息檢索技術(shù)［J］.現(xiàn)代情報(bào)，2005，(3).

［4］CORTES，C.and VAPNIK，V.Support－vector networks.Machine Learning，1995，20.

［5］SCHOLKOPF，B.and SMOLA，A.J.Learning with Kernels:Support Vector Machines，Regularization，Optimization，and Beyond.MIT Press，2001，Cambridge，MA，USA.