基于主動學(xué)習(xí)的相關(guān)反饋算法研究

摘要：相關(guān)反饋（reference feedback）是信息檢索領(lǐng)域中一種常用技術(shù)，近年來，該技術(shù)被廣泛應(yīng)用與基于內(nèi)容的圖像檢索（CBIR）領(lǐng)域中，旨在通過用戶與圖像檢索系統(tǒng)間的交互過程，克服圖像底層特征與高層語義之間的語義鴻溝問題。本文將主動學(xué)習(xí)算法結(jié)合到相關(guān)反饋技術(shù)當(dāng)中，其目的是利用主動學(xué)習(xí)算法，從無標(biāo)記圖像集中選擇最具有信息化的部分圖像作為反饋圖像，減少用戶與系統(tǒng)之間的反饋次數(shù)。在COREL圖像庫和VOC圖像庫上，對基于主動學(xué)習(xí)的相關(guān)反饋技術(shù)進(jìn)行實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)結(jié)果證明了，基于主動學(xué)習(xí)的相關(guān)反饋技術(shù)可以有效提高圖像檢索系統(tǒng)的性能。

關(guān)鍵詞：基于內(nèi)容圖像檢索；相關(guān)反饋；主動學(xué)習(xí)；樣本選擇

中圖法分類號：TP391 文獻(xiàn)標(biāo)識號：A 文章編號：2095-2163（2013）04-

Research on Reference Feedback based on Active Learning

WU Weining， LIU Yang， GUO Maozu*， WANG Chunyu， LIU Xiaoyan

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin， 150001）

Abstract： Reference feedback is a common technique in the field of information retrieval. Recently， it has been widely applied in the task of content-based image retrieval （CBIR） in order to overcome the gap between low features and high semantic concepts by utilizing the user-computer interaction. This paper combines the active learning into reference feedback technique. The goal is to choose the most informative images in the unlabeled pool as returned images by using the active learning， and then reduces the feedback times. On the COREL database and VOC database， the paper evaluates the proposed method. The experimental results indentify that the reference feedback based on active learning can effectively enhance the performance of CBIR system.

Keywords： Content-based Image Retrieval； Reference Feedback； Active Learning； Sampling Strategy

0 引言

相對文本而言，圖像包含的內(nèi)容則要豐富得多。由于互聯(lián)網(wǎng)的發(fā)展，web上的圖片數(shù)量正日趨龐大，圖像包含的語義信息亦千差萬別，另外具有相同語義信息的圖像數(shù)量頁在與日俱增。因此，作為信息檢索中一個重要分支，基于內(nèi)容的圖像檢索（CBIR）已成為關(guān)注熱點(diǎn)。

CBIR方法是以一幅圖像作為單位，通過使用圖像領(lǐng)域的前沿技術(shù)，提取圖像的視覺特征，例如：顏色，紋理等。當(dāng)用戶查找圖像時，搜索引擎根據(jù)用戶所提供的圖像視覺特征，尋找與之相似的圖像。這一做法避免了TBIR策略存在的問題，可直接對圖像進(jìn)行操作。但是，由于圖像處理技術(shù)的局限性，單純提取圖像底層特征很難完整描述圖像包含語義信息，并且，圖像所屬的不同領(lǐng)域，所包含的視覺對象之間具有的空間信息等，也會對圖像的語義信息產(chǎn)生很大的影響。為了使搜索引擎能夠根據(jù)用戶提供的高層語義概念返回與用戶選擇圖像語義最為接近的圖像，相關(guān)反饋技術(shù)則提供了一種良好的實(shí)現(xiàn)途徑。該技術(shù)是使得檢索系統(tǒng)可根據(jù)算法選擇少部分圖像返回給用戶，用戶對這些圖像給出標(biāo)記信息，學(xué)習(xí)系統(tǒng)再從這些標(biāo)記圖像中進(jìn)行知識學(xué)習(xí)，并利用這些新知識提供新的檢索結(jié)果。

根據(jù)相關(guān)反饋過程的特點(diǎn)，主動學(xué)習(xí)技術(shù)可以有效地用于該過程。具體做法是通過采樣算法選擇對檢索系統(tǒng)最有利的部分樣例作為反饋圖像，并將這些圖像提交給用戶進(jìn)行標(biāo)記。使用主動學(xué)習(xí)技術(shù)選擇反饋圖像的目的是減少提升檢索系統(tǒng)性能所需要的反饋圖像數(shù)量，同時也一并減少用戶的工作量和提交反饋圖像標(biāo)記的次數(shù)。根據(jù)這一目的，本文提出一種基于主動學(xué)習(xí)算法的相關(guān)反饋技術(shù)，利用主動學(xué)習(xí)技術(shù)從大量無標(biāo)注待檢索圖像中選擇信息含量最大的圖像，將這些圖像作為反饋圖像，提交用戶進(jìn)行標(biāo)注，由此而減少用戶標(biāo)記反饋圖像的次數(shù)和數(shù)量，并提高CBIR系統(tǒng)的性能。本文主要工作和貢獻(xiàn)概述如下：根據(jù)CBIR圖像系統(tǒng)中給出的目標(biāo)圖像，學(xué)習(xí)一個直推向量機(jī)模型[1]（Transductive Support Vector， TSVM）；使用該模型對圖像庫中的所有待檢索圖像與目標(biāo)圖像的相似程度進(jìn)行預(yù)測；根據(jù)預(yù)測結(jié)果計(jì)算圖像對應(yīng)的信息熵值，選擇信息熵的絕對值最小的一組圖像作為反饋圖像，提交用戶獲取標(biāo)記信息；將標(biāo)注后的圖像用于進(jìn)一步學(xué)習(xí)直推向量機(jī)模型，上述訓(xùn)練過程迭代進(jìn)行，直至達(dá)到用戶滿意的檢索效果為止。結(jié)合提出的算法過程，本文在Visual Studio 2005平臺開發(fā)和實(shí)現(xiàn)了這一圖像檢索系統(tǒng)，并在COREL圖像庫上對系統(tǒng)性能進(jìn)行了實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)結(jié)果證明了系統(tǒng)的有效性。

1 相關(guān)工作

基于內(nèi)容的圖像檢索（CBIR）方法可以被視作機(jī)器學(xué)習(xí)領(lǐng)域中的分類問題，即根據(jù)所給出的待檢索圖像，學(xué)習(xí)一個分類模型，利用該模型將圖像庫中的圖像劃分為目標(biāo)圖像和非目標(biāo)圖像。在檢索過程中，一個首要的問題是如何克服圖像的底層特征與高層語義概念之間的語義鴻溝。為了解決這一問題，相關(guān)反饋技術(shù)通過向用戶提交查詢的方式，讓用戶提供一部分圖像的語義信息，根據(jù)反饋圖像中的語義信息，提升系統(tǒng)檢索的準(zhǔn)確度。另外，隨著用戶提交反饋次數(shù)的增加，學(xué)習(xí)系統(tǒng)逐步將反饋的圖像添加到學(xué)習(xí)系統(tǒng)的訓(xùn)練集中，并使用增量學(xué)習(xí)的方式，學(xué)習(xí)用戶提供的語義知識。值得注意的是，使用相關(guān)反饋技術(shù)的CBIR系統(tǒng)的學(xué)習(xí)方式與主動學(xué)習(xí)算法具有很大的相似性，因此，利用主動學(xué)習(xí)算法設(shè)計(jì)相關(guān)反饋，提升CBIR系統(tǒng)的精度，這一做法越發(fā)受到研究人員的廣泛重視，成為研究熱點(diǎn)。

目前，已有一些研究人員致力于將主動學(xué)習(xí)算法應(yīng)用于相關(guān)反饋技術(shù)中，并取得了良好的實(shí)際效果。這些做法可以分為兩大類。第一類是委員會投票方法[2，3]，此類做法的特點(diǎn)是在同一個圖像集上同時學(xué)習(xí)多個分類模型，并使用這些模型對同一個無標(biāo)注圖像的類別進(jìn)行投票，選擇分類模型差異程度最大的圖像作為反饋圖像；第二類是基于不確定度的反饋方法[1]，這類做法的特點(diǎn)是使用當(dāng)前分類模型對無標(biāo)注圖像的類別進(jìn)行預(yù)測，并根據(jù)分類模型的預(yù)測結(jié)果計(jì)算分類模型對圖像的置信度，再選擇當(dāng)前分類模型最不確定的圖像交由用戶進(jìn)行反饋。

首先，訓(xùn)練集已知的情況下，Platt提出一種貪心算法[4]，根據(jù)無標(biāo)記樣例對應(yīng)的未來期望誤差，從無標(biāo)記樣例集合中選擇訓(xùn)練樣例，目的是通過選擇未來期望誤差最小的樣例，逐步搜索主動學(xué)習(xí)算法的全局最優(yōu)解。但是，這一做法的缺點(diǎn)是，為了計(jì)算每個無標(biāo)記樣例的未來期望誤差，需要分別計(jì)算該樣例被添加正類標(biāo)記和負(fù)類標(biāo)記后對分類模型的影響，即多次重新訓(xùn)練分類模型。如果無標(biāo)記樣例數(shù)量巨大，這一做法的計(jì)算消耗很大，因此，很難滿足檢索系統(tǒng)的要求。近年來，支持向量機(jī)模型以其在小樣本學(xué)習(xí)問題上的卓越性能受到了廣泛關(guān)注。針對該支持向量機(jī)模型的啟發(fā)式主動學(xué)習(xí)算法也隨之得到了更多的研究與使用，例如：Schohn提出了一種啟發(fā)式的SVM主動學(xué)習(xí)算法，通過核空間將圖像的底層特征維度無限放大，獲得了一個特征維度數(shù)目遠(yuǎn)遠(yuǎn)高于樣本數(shù)量的稀疏空間，而主動學(xué)習(xí)的做法是選擇包含盡可能多的維度信息的樣例作為包含信息含量最高的樣例。事實(shí)證明，這種方法不但可以獲得近似于貪心算法的結(jié)果，而且運(yùn)行效率更高[5]。在該類做法中，包含維度信息最多的樣例主要集中在距離支持向量機(jī)的分類超平面較近的位置，因此，這一主動學(xué)習(xí)算法主要選擇距離分類界面最近的樣例作為反饋樣例。與Schohn的做法不同的是，Zhou提出了SSAIR算法[6]。該算法通過利用半監(jiān)督學(xué)習(xí)中的co-training算法，結(jié)合主動學(xué)習(xí)中的co-testing模式，使用co-training中訓(xùn)練得到的兩個分類模型對測試樣本進(jìn)行投票分類，最終，采用兩個分類模型產(chǎn)生分歧的樣本作為供用戶反饋的備選樣本。與其它用于該領(lǐng)域的主動學(xué)習(xí)算法不同的是，這一做法改變了傳統(tǒng)反饋圖像集由用戶在前次檢索中系統(tǒng)認(rèn)定的與待查詢圖像最相關(guān)的那些圖像來構(gòu)成的定則，而是通過分類模型的投票來選擇反饋圖像集，盡最大可能改進(jìn)檢索系統(tǒng)的性能。

以上兩類做法中，第一類方法需要同時學(xué)習(xí)多個模型，計(jì)算量和時間消耗較大，為了滿足圖像檢索系統(tǒng)的實(shí)時性要求，本文選擇第二類方法選擇反饋圖像。事實(shí)上，Schohn和Zhou提出的主動學(xué)習(xí)算法的共同特點(diǎn)是，認(rèn)為分類模型最不確定或者置信度最低的樣例是無標(biāo)記圖像中信息含量最大的樣例，在具體做法中則表現(xiàn)為多個分類模型彼此間分歧最大或者距離分類超平面最近的樣例，選擇這些樣例進(jìn)行標(biāo)記，可最大限度提高分類模型的性能。與這些方法不同的是，本文提出一種最大信息熵的主動學(xué)習(xí)算法，在所有無標(biāo)注樣例中，選擇樣例對應(yīng)的信息熵值最大的樣例點(diǎn)作為信息含量最大的樣例，并以此作為反饋樣例。算法的目的是在有限的檢索時間條件下，更加有效衡量樣例的信息含量，由此提高檢索系統(tǒng)的性能。

2 基于主動學(xué)習(xí)的相關(guān)反饋算法

2.1信息熵最大化采樣策略

本節(jié)詳細(xì)介紹了信息熵最大化這一采樣策略，為了方便理解，首先給出問題的基本概念。因?yàn)榛谙嚓P(guān)反饋技術(shù)的圖像檢索系統(tǒng)是一個迭代的學(xué)習(xí)過程，這里假定在第輪迭代中，訓(xùn)練集表示為，其中，分別表示訓(xùn)練樣例及其對應(yīng)的標(biāo)記信息。因?yàn)閳D像檢索可看作是將待檢索圖像劃分為正類和負(fù)類的過程，故有。本文使用TSVM作為分類模型，則在當(dāng)前迭代步中，TSVM算法學(xué)習(xí)的分類超平面為：

這里，和分別表示訓(xùn)練樣本和無標(biāo)記樣本在核空間的距離，是偏差項(xiàng)。對于任意一個無標(biāo)記樣本，不考慮相同的歸一化系數(shù)，該樣本與分類超平面之間的距離是：

鑒于TSVM模型僅能提供無標(biāo)記樣本與分類界面之間的距離，而無法提供樣本與對應(yīng)的類別標(biāo)記之間的精確概率輸出，為此，本文在這里使用了sigmoid函數(shù)，通過擬合的方法獲得樣本對應(yīng)類別標(biāo)記的后驗(yàn)概率值，即：

其中，參數(shù)和使用Platt[7]中的優(yōu)化算法，迭代求解得到。根據(jù)無標(biāo)記樣本對應(yīng)的后驗(yàn)概率值，無標(biāo)記樣本對應(yīng)的信息熵值可以通過下式計(jì)算：

根據(jù)計(jì)算得到的信息熵值，選擇信息熵值最大的樣本，作為本輪迭代中最適合加入到訓(xùn)練集中的無標(biāo)記樣本，，即：

2.2 基于主動學(xué)習(xí)的相關(guān)反饋過程

信息熵是信息論中反映樣本信息含量的指標(biāo)之一，鑒于此，信息熵也經(jīng)常在機(jī)器學(xué)習(xí)算法中作為樣本信息含量的度量標(biāo)準(zhǔn)。值得注意的是，在公式（5）中，分類模型對無標(biāo)注樣本的預(yù)測概率越接近于0.5，無標(biāo)注樣本對應(yīng)的信息熵值越大，該樣本的不確定程度也就越大。在這一點(diǎn)上，信息熵最大化采樣策略與基于不確定程度的采樣策略的目標(biāo)是一致的。在圖像檢索的相關(guān)反饋過程中，本文使用信息熵最大化采樣策略，由待檢索圖像中選擇反饋圖像，提交用戶做出標(biāo)記，將標(biāo)記后的樣本用于分類模型的訓(xùn)練過程，這個過程迭代進(jìn)行，直至用戶滿意為止。下面，給出了基于主動學(xué)習(xí)的相關(guān)反饋的算法過程。

算法：基于主動學(xué)習(xí)的相關(guān)反饋算法

輸入：標(biāo)記圖像集，無標(biāo)記圖像集，反饋圖像數(shù)量

輸出：檢索結(jié)果

BeginFor

（1）在標(biāo)記圖像集上學(xué)習(xí)TSVM分類模型，獲得公式（1）中的分類超平面；

（2）根據(jù)分類超平面，使用公式（2）計(jì)算每一個無標(biāo)記樣本與該分類界面之間的距離；

（3）通過公式（3）中的sigmoid函數(shù)擬合，獲得無標(biāo)記樣本對應(yīng)的后驗(yàn)概率值；

（4）使用公式（4）逐個計(jì)算無標(biāo)記樣本的信息熵值；

（5）選擇信息熵值最大的個無標(biāo)記樣本作為反饋圖像，提交給用戶進(jìn)行標(biāo)記；

（6），；

（7）如果用戶對當(dāng)前檢索結(jié)果滿意，則結(jié)束，否則返回步驟1，。

EndFor

在上面的反饋過程中，每輪迭代中，檢索系統(tǒng)返回信息熵最大的一組樣本提交給用戶標(biāo)注，該做法可以減少迭代次數(shù)，在用戶可接受的范圍內(nèi)，盡可能多地提供標(biāo)注樣本用于訓(xùn)練。

3 實(shí)驗(yàn)結(jié)果與分析

3.1數(shù)據(jù)庫及實(shí)驗(yàn)設(shè)計(jì)

本實(shí)驗(yàn)使用COREL圖像庫中的3類圖像作為待檢索圖像，每類圖像包含100幅圖像，這3個圖像類別分別是鷹，魚和馬。本文分別提取每一幅圖像的特征組成樣本集合，使用TSVM作為分類模型，用于從CBIR系統(tǒng)中獲得檢索結(jié)果。在每一組實(shí)驗(yàn)中，首先，從待檢索圖像中隨機(jī)抽取一幅圖像作為目標(biāo)圖像，訓(xùn)練TSVM模型；根據(jù)該模型的預(yù)測結(jié)果，計(jì)算每一幅圖像的信息熵值，并選擇信息熵最大的五幅圖像作為反饋圖像（）；提交用戶標(biāo)記后，將反饋圖像和標(biāo)記用于訓(xùn)練TSVM模型，同時給出檢索結(jié)果；該過程循環(huán)進(jìn)行，直至達(dá)到結(jié)束標(biāo)準(zhǔn)為止。本文使用查全率（precision）作為圖像檢索結(jié)果的評價標(biāo)準(zhǔn)，其中，檢索系統(tǒng)劃分的相關(guān)圖像數(shù)量是100幅，召回圖像數(shù)量是20幅。

3.2實(shí)驗(yàn)結(jié)果

在表1和表2中，本文給出了反饋次數(shù)為5次，并使用不同的圖像底層特征條件下，在不同語義類別上，CBIR系統(tǒng)的檢索結(jié)果。從實(shí)驗(yàn)結(jié)果可以看出，使用最大墑作為樣本信息含量的度量標(biāo)準(zhǔn)，基于主動學(xué)習(xí)的相關(guān)反饋技術(shù)在圖像檢索系統(tǒng)中取得了良好的檢索結(jié)果。隨著反饋次數(shù)的增加，CBIR系統(tǒng)的檢索結(jié)果得到逐步提高。同時，表1和表2的對比還可以發(fā)現(xiàn)，顏色稀疏和相關(guān)圖組成的混合特征獲得了比SIFT特征更好的檢索結(jié)果，這是因?yàn)榍罢叩木S度高于后者，提供了更多的圖像底層語義信息，由此而提高了檢索效果。

表1 顏色稀疏和相關(guān)圖的混合特征條件下，不同反饋次數(shù)時，CBIR系統(tǒng)檢索精度

Tab. 1. Using sparse color and related features， different feedback times， the precision of CBIR system

初始值

反饋1次

反饋2次

反饋3次

反饋4次

反饋5次

鷹

0.71

0.724

0.73

0.628

0.732

0.75

馬

0.502

0.522

0.428

0.526

0.522

0.604

魚

0.494

0.538

0.504

0.536

0.572

0.468

表2 SIFT特征條件下，不同反饋次數(shù)時，CBIR系統(tǒng)檢索精度

Tab.2 Using SIFT features， different feedback times， the precision of CBIR system

初始值

反饋1次

反饋2次

反饋3次

反饋4次

反饋5次

鷹

0.5

0.756

0.39

0.71

0.774

0.622

馬

0.44

0.376

0.406

0.406

0.472

0.424

魚

0.25

0.314

0.22

0.358

0.23

0.334

在圖1和圖2中，本文給出了使用基于主動學(xué)習(xí)的相關(guān)反饋技術(shù)在CBIR系統(tǒng)中的檢索結(jié)果。除了使用COREL圖像庫作為檢索圖像庫之外，本文還增加了VOC圖像庫（包含20類，共計(jì)5 011幅圖像）作為檢索圖像庫，對所提出方法進(jìn)行實(shí)驗(yàn)驗(yàn)證。從圖1和圖2中可以看出，基于主動學(xué)習(xí)的相關(guān)反饋技術(shù)可以有效提升CBIR系統(tǒng)的檢索性能。

（a） Car類別

初始檢索結(jié)果

使用相關(guān)反饋技術(shù)后的檢索結(jié)果

（b） Aeroplane類別

初始檢索結(jié)果

使用相關(guān)反饋技術(shù)后的檢索結(jié)果

圖1 VOC圖像庫上，使用基于主動學(xué)習(xí)相關(guān)反饋技術(shù)的圖像檢索結(jié)果

Fig.1 The retrieval results on VOC database by using feedback techniques based on active learning algorithm

（a） Eagle類別

初始檢索結(jié)果

使用相關(guān)反饋技術(shù)后檢索結(jié)果

初始檢索結(jié)果

使用相關(guān)反饋技術(shù)后檢索結(jié)果

圖2 COREL圖像庫上，使用基于主動學(xué)習(xí)相關(guān)反饋技術(shù)的檢索結(jié)果。

Fig.2 The retrieval results on COREL database by using feedback techniques based on active learning algorithm

4 結(jié)束語

本文利用了主動學(xué)習(xí)算法在選擇訓(xùn)練樣本方面，相對于隨機(jī)選擇方法的優(yōu)勢，提出了一種基于主動學(xué)習(xí)的相關(guān)反饋技術(shù)。在所提出的技術(shù)中，算法利用了分類模型最不確定的樣本可以提供更多反饋信息的特點(diǎn)，使用信息熵作為樣本信息含量的度量標(biāo)準(zhǔn)，選擇每輪迭代過程中，信息熵值最大的樣本作為反饋樣本，達(dá)到了增量學(xué)習(xí)，提升檢索系統(tǒng)性能的目的。本文使用COREL圖像庫和VOC圖像庫，對所提出方法的性能進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果證明所提出方法的有效性。

參考文獻(xiàn)

[1] CHEN J X. Active learning for transductive support vector machines with applications to text classification[J]. 計(jì)算機(jī)科學(xué). 2004， 31： 242-244.

[2] ABE N， MAMITSUKA H. Query learning strategies using boosting and bagging[C]//Proceedings of 15th International Conference on Machine Learning. Madison. WI， 1998： 1-9.

[3] SEUNG H， OPPER M， SOMPOLINSKY M. Query by committee[C]//Proceedings of 5th ACM Workshop on Computational Learning Theory. Pittsburgh， PA， 1992： 287-294.

[4] PLATT J. Fast training of support vector machins using sequential minimal optimization. advances in kernel methods： support vector learning[M]. Cambridge： MIT Press， 1998： 42-65.

[5] SCHOHN G， GOHN D. Less is more： active learning with support vector machine[C]// Proceedings of 17th International Conference of Machine Learning. Stanford， CA， 2000： 204-211.

[6] ZHOU Z H， CHEN K J， JIANG Y. Exploiting unlabeled data in content-based image retrieval[C]//Proceedings of the 15th European Conference on Machine Learning. Pisa， Italy： LNAI 3021， 2004： 525-536.

[7] PLATT J C. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances in Large Margin Classifiers[M]. Cambridge： MIT Press， 1999： 61-74.

基金項(xiàng)目：國家自然科學(xué)基金（61171185，61271346，60932008）；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金（20112302110040）

作者簡介：吳偉寧（1983-）.女，黑龍江寧安人，博士研究生.研究方向：機(jī)器學(xué)習(xí)，圖像檢索；

劉揚(yáng)（1976-）.男，吉林懷德人，博士，副教授.研究方向：機(jī)器學(xué)習(xí)，計(jì)算機(jī)視覺；

郭茂祖（1966-）.男，山東夏津人，博士后，教授，博導(dǎo).研究方向：計(jì)算生物學(xué)與生物信息學(xué)，機(jī)器學(xué)習(xí)與圖像理解；

王春宇（1979-）.男，遼寧寬甸人，博士研究生，講師.研究方向：生物信息學(xué)，并行計(jì)算；

劉曉燕（1963-）.女，山東泰安人，博士，副教授.研究方向：人工智能與生物信息學(xué)。

通訊作者： 郭茂祖