一種運動數(shù)據(jù)檢索的相關(guān)反饋算法

陳松樂，孫正興，張 巖，李 騫

（1.南京大學計算機軟件新技術(shù)國家重點實驗室，江蘇南京210046；2.南京郵電大學寬帶無線通信與傳感網(wǎng)教育部重點實驗室，江蘇南京210003）

一種運動數(shù)據(jù)檢索的相關(guān)反饋算法

陳松樂1，2，孫正興1，張 巖1，李 騫1

（1.南京大學計算機軟件新技術(shù)國家重點實驗室，江蘇南京210046；2.南京郵電大學寬帶無線通信與傳感網(wǎng)教育部重點實驗室，江蘇南京210003）

本文提出了一種基于RankBoost的運動數(shù)據(jù)檢索相關(guān)反饋算法.該算法具有以下二個方面的特點：首先，以KNN-DTW作為RankBoost集成學習的弱排序器，在適應變長多變量時間序列（Variable-Length Multivariate Time Series，VLMTS）數(shù)據(jù)的同時，利用RankBoost的集成性與高效性解決相關(guān)反饋實時性要求與VLMTS數(shù)據(jù)計算復雜度高的矛盾；其次，以本文提出的最小化排序經(jīng)驗損失和泛化損失風險作為RankBoost集成學習目標，有效地克服了相關(guān)反饋小樣本學習環(huán)境下的過擬合問題.在CMU動作庫上的實驗結(jié)果驗證了該方法的有效性.

運動捕獲數(shù)據(jù)；相關(guān)反饋；RankBoost；排序損失

1 引言

目前，在基于內(nèi)容的運動數(shù)據(jù)檢索（Content-Based Motion data Retrieval，CBMR）［1］領(lǐng)域，一些研究者已經(jīng)開始嘗試使用相關(guān)反饋技術(shù)來進一步提高檢索性能，然而現(xiàn)有的CBMR相關(guān)反饋僅采用了以類間類內(nèi)差比值［2］以及平均歸一化折扣累積增益［3］為規(guī)則進行特征權(quán)重調(diào)整的啟發(fā)式方法.啟發(fā)式方法由于缺乏明確的優(yōu)化目標，很難取得令人滿意的效果［4］，而在圖像等基于內(nèi)容的多媒體信息檢索領(lǐng)域，相關(guān)反饋技術(shù)已由最初的啟發(fā)式特征權(quán)重調(diào)整發(fā)展到在線學習機制［4］.CBMR亟需要引入有效的機器學習方法以準確捕捉用戶的主觀檢索意圖.

與其他機器學習問題相比，小樣本和實時性要求是相關(guān)反饋學習算法面臨的主要挑戰(zhàn).小樣本問題是指反饋學習算法只能從用戶獲取數(shù)量有限的學習樣本，極易產(chǎn)生過擬合問題［5，6］.實時性則要求反饋學習算法必須足夠快以滿足用戶和系統(tǒng)的實時交互需求.此外，在圖像等基于內(nèi)容的多媒體信息檢索領(lǐng)域，檢索對象通常采用向量表示，而CBMR的檢索對象為連續(xù)的姿態(tài)形成的動作，是一種典型的變長多變量時間序列（Variable-Length Multivariate Time Series，VLMTS），其通常采用行（列）數(shù)相同但列（行）數(shù)不等的矩陣進行表示［7］.由于不同動作在時間軸上存在局部非線性形變，一方面導致了很難采用統(tǒng)一的向量空間進行表示，另一方面需要采用彈性匹配以準確地度量不同序列模式的相似程度，計算復雜度較高，而運動數(shù)據(jù)的高維性使得這一問題更加突出.

基于在線分類或者優(yōu)化的相關(guān)反饋技術(shù)在基于內(nèi)容的圖像檢索（Content-Based Image Retrieval，CBIR）中已有大量研究，支持向量機（Support Vector Machine，SVM）和Boosting是兩種最具有代表性的判別式相關(guān)反饋方法［8］.在CBIR中，SVM相關(guān)反饋方法普遍采用的徑向基等核函數(shù)一般都以向量作為輸入，但CBMR中的檢索對象為VLMTS數(shù)據(jù)，如何構(gòu)建滿足Mercer定理條件并能夠?qū)崟r計算的基于序列距離的核函數(shù)仍然是研究者面臨的一個復雜問題［9］.Boosting作為一種封裝器特征選擇技術(shù)在小樣本學習環(huán)境下極易產(chǎn)生過擬合問題［10］，而CBIR中用來克服 Boosting學習面臨的小樣本等問題的貝葉斯分類器［11］、模糊特征對比模型［12］以及BiasMap算法［13］很難應用于VLMTS數(shù)據(jù)，導致這些解決方法并不適用于CBMR系統(tǒng).

針對CBMR相關(guān)反饋中VLMTS數(shù)據(jù)在線學習面臨的小樣本與實時性要求問題，本文提出了一種基于RankBoost［14］的相關(guān)反饋算法，在CMU動作庫［15］上的實驗結(jié)果表明該算法具有較好的檢索精度和較快的響應速度.

2 CBMR相關(guān)反饋算法RankBoost-RF

本節(jié)首先介紹RankBoost-RF算法的弱排序器，然后給出其學習目標，最后給出具體算法描述.

2.1弱排序器：KNN-DTW

本文采用姿態(tài)布爾幾何特征［16］與關(guān)節(jié)對距離特征［3］作為姿態(tài)的特征表示.設(shè)F=｛fk，k=1，…，d｝為姿態(tài)特征集合，采用動態(tài)時間彎曲算法（Dynamic Time Warping，DTW）［17］計算實例在每個特征fk上的兩兩彈性匹配距離分別為反饋過程中用戶標記的相關(guān)實例集和不相關(guān)實例集，定義特征fk對實例xi的評分函數(shù)為：

RankBoost-RF以KNN-DTW作為集成學習的弱排序器，一方面能夠利用KNN僅需距離測度的特點克服VLMTS數(shù)據(jù)難以采用統(tǒng)一向量空間進行表示的不足并以DTW算法適應其彈性匹配需求，另一方面能夠利用RankBoost的集成性在離線處理中計算庫中實例在每個特征上的兩兩彈性匹配距離，而RankBoost在特征空間搜索的高效性則有利于解決運動數(shù)據(jù)的高維性問題，從而為反饋算法的高效性提供了基礎(chǔ).

2.2學習目標：最小化排序經(jīng)驗損失與泛化損失風險

設(shè)X為庫中所有動作實例構(gòu)成的集合，Y=｛-1，+1｝描述實例是否和查詢相關(guān).若xi∈X和查詢相關(guān)則yi=+1，yi=-1則表示xi和查詢不相關(guān).在相關(guān)反饋過程中，反饋算法通過在用戶標記的訓練集上的學習，得到評分函數(shù)H：x→R，使得和查詢越相關(guān)的實例評分越高.設(shè)XU為從庫中隨機抽取的動作實例集（XU中的實例是否和查詢相關(guān)未知）XU構(gòu)成 H的驗證集.設(shè) θ為閾值，對于xi∈XT，若H（xi）≥θ，則xi被H認定和查詢相關(guān)，若H（xi）＜θ，則xi被H認定和查詢不相關(guān)，即：

在檢索過程中，根據(jù)庫中只包含極少與查詢相關(guān)實例這一基本假設(shè)［19］，PR＜＜0.5，因此Ru隨著的減小而減小.固定閾值θ，不妨假設(shè)H能夠?qū)M行正確的排序（在小樣本學習環(huán)境下，該假設(shè)容易得到滿足），通過分析應用H對XT排序后中實例之間的位置關(guān)系，可得到如下結(jié)論：XU中的實例越遠離中的實例（即XU中的實例越鄰近中的實例越小，因此H在XU上的排序損失風險越小.

根據(jù)這一結(jié)論，我們可以用XT上的排序結(jié)果來評估H的排序損失風險.本文采用具有偏序關(guān)系的實例對（Pairwise）［14］來量化排序后不同集合中實例之間的位置關(guān)系.在使用H對XT進行排序后，XU中的實例和中的實例的遠離程度可通過偏序?qū)χg的平均距離表示，即：

本文使用最小化R（H）代替?zhèn)鹘y(tǒng)的最小化訓練集上的分類誤差［11］或者排序損失［13］學習目標，并將其稱之為最小化排序經(jīng)驗損失與泛化損失風險（Minimizing Ranking Experience Loss and Generalization Loss Risk，MR-EL&GLR）學習目標.一方面，R（H）越小，則訓練集上的排序損失就越小，H的排序經(jīng)驗損失也就越??；另一方面，R（H）越小，則驗證集上的排序損失也就越小，隱含著H的泛化損失風險也就越小.對于在訓練集上具有較好排序能力的若干個排序器，RankBoost-RF算法采用MR-EL&GLR作為學習目標能夠進一步篩選出具有較低泛化風險的排序器，從而能夠有效解決其在相關(guān)反饋小樣本學習環(huán)境下的過擬合問題.

2.3RankBoost-RF算法描述

以KNN-DTW為弱排序器并以MR-EL&GLR為學習目標的RankBoost-RF算法如算法1所示.算法在迭代過程中根據(jù)訓練集和驗證集上的加權(quán)排序損失確定弱排序器及其權(quán)重并分別更新訓練集和驗證集中每個偏序?qū)Φ臋?quán)重.

算法1 RankBoost-RF算法

輸入：

2）從動作庫中隨機抽取的實例集XU；

過程：

4）For t=1，…，T

4.1）進行弱排序?qū)W習，獲得弱排序器ht；

4.2）計算ht的權(quán)重

4.5）H=H+αtht；

End for

5）使用H計算庫中實例的評分，排序后將top-N個候選動作返回.

3 實驗設(shè)計與結(jié)果分析

3.1實驗數(shù)據(jù)集與評價標準

來源于CMU［15］運動捕獲數(shù)據(jù)庫包含實例數(shù)較多的17類動作構(gòu)成了實驗數(shù)據(jù)集，共含有658個實例，其組成和示意圖如表1和圖1所示.

表1　三維人體動作庫構(gòu)成

本文主要通過平均查全率和查準率來評估檢索性能.為了模擬實際的檢索過程，我們從每個動作類別中隨機抽取10個動作進行檢索，最后我們將每次檢索結(jié)果的平均值作為不同方法的平均檢索性能.

3.2學習目標有效性評估

為驗證學習目標MR-EL&GLR的有效性，我們將其和最小化訓練集上的分類誤差和排序損失這兩種傳統(tǒng)的相關(guān)反饋學習目標進行對比.為避免不同算法的影響，我們采用Boosting集成學習框架并使用相同的KNN-DTW學習器來評估這三種學習目標的反饋性能. Boosting集成學習的迭代次數(shù)統(tǒng)一設(shè)置為20，對于RankBoost-RF，設(shè)置參數(shù)β為0.5，每次隨機抽取的實例數(shù)|XU|為100.每輪反饋中用戶標記的樣本數(shù)設(shè)定為20，查準率基數(shù)N為30.圖2給出了三種學習目標前5次反饋的平均查準率對比.

圖2中反饋次數(shù)為0對應的檢索性能為通過內(nèi)容匹配獲得的首次檢索結(jié)果.從圖2可以看出，最小化訓練集上分類誤差和排序損失的學習目標盡管在反饋后期取得了較好的反饋性能，然而在反饋初期特別是在首次反饋時，反饋性能甚至低于首次檢索結(jié)果.本文提出的學習目標MR-EL&GLR取得了最好的反饋性能，實驗結(jié)果表明以MR-EL&GLR作為學習目標的Rank-Boost-RF算法能夠有效克服相關(guān)反饋小樣本學習環(huán)境下的過擬合問題.

3.3反饋有效性評估

我們實現(xiàn)了CBMR中目前已有的根據(jù)特征的類間類內(nèi)差比值（VRII-RF）［2］以及特征的平均歸一化累計折扣增益（AnDCG-RF）［3］這兩種反饋算法以和Rank-Boost-RF算法進行對比.圖3給出了三種反饋算法前5次反饋平均查準率對比.

圖3表明VRII-RF算法的反饋效果最差，其檢索性能只在首次反饋中得到了較大的提高.AnDCG-RF算法的反饋性能略優(yōu)于VRII-RF算法.基于學習的Rank-Boost-RF算法的反饋性能明顯優(yōu)于基于啟發(fā)式規(guī)則調(diào)整的VRII-RF和AnDCG-RF反饋算法.圖4進一步給出了三種反饋算法經(jīng)過5次反饋后獲得的平均查全率-查準率曲線，可以看出本文提出的RankBoost-RF算法取得了較理想的反饋效果.

3.4反饋效率與參數(shù)影響分析

我們在離線處理中計算庫中動作在每個特征上的兩兩DTW距離以提高反饋效率.相關(guān)反饋包含學習過程以及對庫中實例重新排序兩個階段.RankBoost-RF學習過程的時間復雜度為O（d×（n+l）×nlogn），排序過程的時間復雜度為O（A×T×n×logn+AlogA），其中，d為姿態(tài)特征數(shù)，n為用戶標記的樣本數(shù)，l為從庫中隨機抽取的實例數(shù)，A為庫中所有動作實例數(shù).在Intel（R）CoreTMi7-3770@3.40GH的PC上每輪反饋的平均響應時間小于0.5s，能夠滿足CBMR相關(guān)反饋的實時性要求. RankBoost-RF主要涉及3個參數(shù)，即R（H）中）所占的權(quán)重β，RankBoost的迭代次數(shù)T，以及隨機抽取的實例集XU的數(shù)量l.通過實驗分析可知，當β＞0，T≥20，l ≥100時，RankBoost-RF算法的反饋性能對于參數(shù)的不同取值并不敏感，均能夠取得較接近的最優(yōu)反饋性能.

4 總結(jié)與展望

本文提出了一種基于RankBoost的CBMR相關(guān)反饋算法.考慮到VLMTS數(shù)據(jù)表示形式的特殊性、彈性匹配距離計算的復雜性以及高維性，本文采用RankBoost為在線學習算法并以KNN-DTW構(gòu)建弱排序器.為了解決RankBoost在相關(guān)反饋小樣本學習環(huán)境下的過擬合問題，本文提出了MR-EL&GLR學習目標.實驗結(jié)果表明：本文提出的RankBoost-RF算法能夠有效解決CBMR小樣本學習環(huán)境下的過擬合問題并能夠滿足實時性要求；相比于CBMR中目前已有的相關(guān)反饋方法，本文方法具有更好的檢索精度和更快的響應速度.

在CBMR中，用戶的需求和理解和運動特征之間的映射是一個十分復雜的問題，如何利用相關(guān)反饋來進一步縮小用戶與計算機之間的語義鴻溝，仍是有待于深入研究的課題.此外，我們計劃引入手繪草圖等技術(shù)，以為用戶提供更加自然和便捷的查詢提交接口.

［1］LIU F，ZHUANG Y T，Wu F，et al.3D motion retrieval with motion index tree［J］.Computer Vision and Image Understanding，2003，92（2-3）：265-284.

［2］CHEN S L，SUN Z X，LI Y，et al.Partial similarity human motion retrieval based on relative geometry features［A］. Proceedings of 4th International Conference on Digital Home ［C］.Washington：IEEE Computer Society，2012.298-303.

［3］TANG J K T，LEUNG H.Retrieval of logically relevant 3D human motions by adaptive feature selection with graded relevance feedback［J］.Pattern Recognition Letters，2012，33（4）：420-430.

［4］HUANG T S，ZHOU X S.Image retrieval with relevance feedback：from heuristic weight adjustment to optimal learning methods［A］.Proceedings of 2001 International Conference on Image Processing［C］.Washington：IEEE Computer Society，2001.2-5.

［5］ZHOU X S，HUANG T S.Relevance feedback in image retrieval：a comprehensive review［J］.Multimedia Systems，2003，8（6）：536-544.

［6］WU K，YAP K H.Fuzzy SVM for content-based image retrieval［J］.IEEE Computational Intelligence Magazine，2006，1（2）：10-16.

［7］YOON H，YANG K，SHAHABI C.Feature subset selection and feature ranking for multivariate time series［J］.IEEE Transactions on Knowledge and Data Engineering，2005，17 （9）：1186-1198.

［8］HUANG W，GAO Y，CHAN K L.A review of regionbased image retrieval［J］.Journal of Signal Processing Systems for Signal Image and Video Technology，2010，59 （2）：143-161.

［9］LEI H S，SUN B Y.A study on the dynamic time warping in kernel machines［A］.Proceedings of the 2007 Third International IEEE Conference on Signal-Image Technologies and Internet-Based System［C］.Washington：IEEE Computer Society，2007.839-845.

［10］KOHAVI R，SOMMERFIELD D.Feature subset selection using the wrapper method：overfitting and dynamic search space topology［A］.Proceedings of 1st International Conference on Knowledge Discovery and Data Mining［C］. California：Amer Assn for Artificial，1995.192-197.

［11］HUANG S H，WU Q J，LAI S H.Improved AdaBoost-based image retrieval with relevance feedback via paired feature learning［J］.Multimedia Systems，2006，12（1）：14-26.

［12］JIANG W，ER G，DAI Q H，GU J W.Similarity-based online feature selection in content-based image retrieval［J］.IEEE Transactions on Image Processing，2006，15（3）：702-712.

［13］ZHOU X S，GARG A，HUANG T S.Nonlinear variants of biased discriminants for interactive image retrieval［J］.Vision，Image and Signal Processing，IEE Proceedings，2005，152（6）：927-936.

［14］FREUND Y，IYER R，SCHAPIRE R E，et al.An efficient boosting algorithm for combining preferences［J］.Journal of Machine Learning Research，2003，4：933-969.

［15］CMU.Motion Capture Database［DB/OL］.http：//mocap.cs.cmu.edu/，2003.

［16］MULLER M，RODER T，CLAUSEN M.Efficient contentbased retrieval of motion capture data［J］.ACM Transactions on Graphics，2005，24（3）：677-685.

［17］SAKOE H，CHIBA S.Dynamic programming algorithm optimization for spoken word recognition［J］.IEEE Transactions on Acoustics，Speech and Signal Processing，1978，26（1）：43-49.

［18］LIU T Y.Learning to rank for information retrieval［J］. Foundations and Trends in Information Retrieval，2009，3 （3）：225-331.

［19］CRUCIANU M，F(xiàn)ERECATU M，BOUJEMAA N.Relevance feedback for image retrieval：a short survey［R］.Basel：DELOS2 European Network of Excellence（FP6），2004.

陳松樂 男，1976年生于江蘇淮陰.博士.現(xiàn)為南京郵電大學物聯(lián)網(wǎng)學院講師.主要研究方向為多媒體數(shù)據(jù)分析與處理、計算機視覺.

E-mail：chensongle@hotmail.com

孫正興（通信作者） 男，1964年生于江蘇張家港.博士.現(xiàn)為南京大學計算機科學與技術(shù)系教授、博士生導師.主要研究方向為智能人機交互、多媒體計算、計算機視覺.

E-mail：szx@nju.edu.cn

A Relevance Feedback Algorithm for Motion Data Retrieval

CHEN Song-le1，2，SUN Zheng-xing1，ZHANG Yan1，LI Qian1

（1.State Key Laboratory for Novel Software Technology，Nanjing University，Nanjing，Jiangsu 210046，China；2.Key Laboratory of Ministry of Education of China for Broadband Wireless Communication and Sensor Network Technology，Nanjing University of Posts and Telecommunications，Nanjing，Jiangsu 210003，China）

A relevance feedback algorithm based on RankBoost for content-based motion data retrieval（CBMR）is presented and has two characteristics.First，KNN-DTW is employed as the weak ranker for RankBoost ensemble learning. While adapting to variable-length multivariate time series（VLMTS）data，by taking the advantage of the ensemble and efficiency of RankBoost，it can resolve the conflict between the real-time requirement of relevance feedback and the high computational complexity of VLMTS data.Second，minimizing ranking experience loss and generalization loss risk proposed in this paper are used as the learning objective for RankBoost ensemble learning，which can effectively solve the over-fitting problem caused by small-sample training in relevance feedback.Experimental results on CMU action library verify the effectiveness of the proposed algorithm.

motion capture data；relevance feedback；RankBoost；rank loss

TP391.41

A

0372-2112（2016）04-0868-05

電子學報URL：http：//www.ejournal.org.cn 10.3969/j.issn.0372-2112.2016.04.016

2014-02-21；

2015-06-23；責任編輯：李勇鋒

國家高科技發(fā)展計劃（No.2007AA01Z334）；國家自然科學基金（No.61272219，No.61100110，No.61321491）；教育部新世紀優(yōu)秀人才資助計劃（No.NCET-04-0460）；江蘇省科技計劃（No.BE2010072，No.BE2011058，No.BY2012190，No.BY2013072-04）；計算機軟件新技術(shù)國家重點實驗室創(chuàng)新基金重點項目（No.ZZKT2013A12）