Sub-linear active learning strategy with approximate k-nn search
Inhaltsverzeichnis
Referenz
D. Gorisse, M. Cord, and F. Precioso. Salsas: Sub-linear active learning strategy with approximate k-nn search. Pattern Recognition, 44(1011):2343-2357, 2011.
DOI
http://dx.doi.org/10.1016/j.patcog.2010.12.009
Abstract
With the democratization of digital imaging devices, image databases exponentially grow. Thus, providing the user with a system for searching into these databases is a critical issue. However, bridging the semantic gap between which (semantic) concept(s) the user is looking for and the (semantic) content is quite difficult. In content-based image retrieval (CBIR) systems, a classic scenario is to formulate the user query, at first, with only one example (i.e. one image). In order to address this problem, active learning is a powerful technique which involves the user in interactively refining the query concept, through relevance feedback loops, by asking the user whether some strategically selected images are relevant or not. However, the complexity of state-of-the-art active learning methods is linear in the size of the database and thus dramatically slows down retrieval systems, when dealing with very large databases, which is no longer acceptable for users. In this article, we propose a strategy to overcome scalability limitations of active learning strategies by exploiting ultra fast k-nearest-neighbor (k -NN) methods, as locality sensitive hashing (LSH), and combining them with an active learning strategy dedicated to very large databases. We define a new LSH scheme adapted to χ2χ2 distance which often leads to better results in image retrieval context. We perform evaluation on databases between 5 K and 180 K images. The results show that our interactive retrieval system has a complexity almost constant in the size of the database. For a database of 180 K images, our system is 45 times faster than exhaustive search (linear scan) reaching similar accuracy.
Extended Abstract
Bibtex
@article{Gorisse20112343,
title = "SALSAS: Sub-linear active learning strategy with approximate k-NN search ",
journal = "Pattern Recognition ",
volume = "44",
number = "10–11",
pages = "2343 - 2357",
year = "2011",
note = "Semi-Supervised Learning for Visual Content Analysis and Understanding ",
issn = "0031-3203",
doi = "http://dx.doi.org/10.1016/j.patcog.2010.12.009",
url = "http://www.sciencedirect.com/science/article/pii/S0031320310005753 http://de.evo-art.org/index.php?title=Sub-linear_active_learning_strategy_with_approximate_k-nn_search",
author = "D. Gorisse and M. Cord and F. Precioso",
keywords = "Image retrieval",
keywords = "Active learning",
keywords = "Relevance feedback",
keywords = "Locality sensitive hashing",
keywords = "Scalability",
keywords = "Support vector machines "
}
Used References
no spaces in c&p of pdf as a gift of Elsevier
[1] J.Cheng,K.Wang,ActivelearningforimageretrievalwithCO-SVM,Pattern Recognition 40(2007)330–334.
[2] T.Huang,C.Dagli,S.Rajaram,E.Chang,M.Mandel,G.Poliner,D.Ellis,Active learning forinteractivemultimediaretrieval,ProceedingsoftheIEEE96(4) (2008) 648.
[3] E.Chang,S.Tong,K.Goh,C.Chang,Supportvectormachineconcept-dependent active learningforimageretrieval,IEEETransactionsonMultimedia2(2005).
[4] S.C.Hoi,R.Jin,J.Zhu,M.R.Lyu,Semi-supervisedSVMbatchmodeactive learning forimageretrieval,in:IEEEConferenceonComputerVisionand Pattern Recognition,2008,pp.1–7.
[5] Y.Rui,T.Huang,M.Ortega,S.Mehrotra,Relevancefeedback:apowertoolfor interactive content-basedimageretrieval,IEEETransactionsonCircuitsand Systems forVideoTechnology8(5)(1998)644–655.
[6] X.Zhou,T.Huang,Relevancefeedbackinimageretrieval:acomprehensive review, MultimediaSystems8(6)(2003)536–544.
[7]E.Chang,B.Li,G.Wu,K.Goh,Statistical learning foreffectivevisualinformation retrieval,in:IEEEInternationalConference onImageProcessing,2003,pp.609–612.
[8] Z.-H.Zhou,K.-J.Chen,H.-B.Dai,Enhancingrelevancefeedbackinimage retrieval usingunlabeleddata,ACMTransactionsonInformationSystem24(2) (2006) 219–244doi:http://doi.acm.org/10.1145/1148020.1148023.
[9] K.Yu,J.Bi,V.Tresp,Activelearningviatransductiveexperimentaldesign,in: Proceedings ofthe23rdInternationalConferenceonMachineLearning,ACM, 2006, pp.1081–1088.
[10] D.Gorisse,M.Cord,F.Precioso,Optimizationonactivelearningstrategyfor object categoryretrieval,in:IEEEInternationalConferenceonImageProces- sing, IEEE,2009.
[11]O.Chapelle,P.Haffner,V.Vapnik,Supportvectormachinesforhistogram-based imageclassification,IEEETransactionsNeuralNetworks(1999)1055–1064.
[12] V.Vapnik,StatisticalLearningTheory,Wiley-Interscience,NewYork,1998.
[13] N.Roy,A.McCallum,Towardoptimalactivelearningthroughsampling estimation oferrorreduction,in:Proceedingsofthe18thInternational Conference onMachineLearning,2001,pp.441–448.
[14] S.Tong,D.Koller,Supportvectormachineactivelearningwithapplicationsto text classification,TheJournalofMachineLearningResearch2(2002)45–66.
[15] A.Bordes,S.Ertekin,J.Weston,L.Bottou,Fastkernelclassifierswithonlineand active learning,JournalofMachineLearningResearch6(2005)1579–1619.
[16] L.Wang,X.Li,P.Xue,K.Chan,AnovelframeworkforSVM-basedimageretrievalon largedatabases,in:Proceedingsofthe13thAnnualACMInternationalConference on Multimedia,ACM,NewYork,NY,USA,2005,pp.487–490.
[17] A.Gionis,P.Indyk,R.Motwani,Similaritysearchinhighdimensionsvia hashing, in:VLDB’99:Proceedingsofthe25thInternationalConferenceon Very LargeDataBases,MorganKaufmannPublishersInc.,SanFrancisco,CA, USA, 1999,pp.518–529.
[18] J.Peng,D.R.Heisterkamp,Kernelindexingforrelevancefeedbackimage retrieval, in:IEEEInternationalConferenceonImageProcessing,2003.
[19] D.R.Heisterkamp,J.Peng,Kernelva-filesforrelevancefeedbackretrieval,in: ACM InternationalWorkshoponMultimediaDatabases,2003,pp.48–54.
[20] D.R.Heisterkamp,J.Peng,Kernelvectorapproximationfilesforrelevance feedback retrievalinlargeimagedatabases,MultimediaToolsApplication 26 (2)(2005)175–189,doi:http://dx.doi.org/10.1007/s11042-005-0454-4.
[21] N.Panda,E.Y.Chang,Efficienttop-khyperplanequeryprocessingformulti- media informationretrieval,in:Proceedingsofthe14thAnnualACMInter- national ConferenceonMultimedia,2006,pp.317–326.
[22] N.Panda,K.-S.Goh,E.Y.Chang,Activelearninginverylargedatabases, Multimedia ToolsandApplications31(3)(2006)249–267.
[23] N.Panda,E.Y.Chang,Exploitinggeometryforsupportvectormachine indexing, in:ProceedingsofSIAMInternationalConferenceonDataMining, 2005.
[24] M.Crucianu,D.Estevez,V.Oria,J.-P.Tarel,Hyperplanequeriesinafeature- space m-treeforspeedingupactivelearning,in:ProceedingsofJourne´ es Bases de Donne´ es Avance´ es, 2007,pp.1–2.
[25] P.Gosselin,M.Cord,S.Philipp-Foliguet,Combiningvisualdictionary,kernel- based similarityandlearningstrategyforimagecategoryretrieval,Computer Vision andImageUnderstanding110(3)(2008)403–417.
[26] K.Brinker,Incorporatingdiversityinactivelearningwithsupportvector machines, MachineLearningInternationalWorkshopthenConference,2003, pp. 59–66.
[27] P.Indyk,R.Motwani,Approximatenearestneighbors:towardsremovingthe curse ofdimensionality,in:Proceedingsofthe13thAnnualACMSymposium on TheoryofComputing,1998,pp.604–613.
[28] M.Datar,N.Immorlica,P.Indyk,V.Mirrokni,Locality-sensitivehashing scheme basedonp-stabledistributions,in:Proceedingsofthe20thAnnual Symposium onComputationalGeometry,2004,pp.253–262.
[29] Q.Lv,W.Josephson,Z.Wang,M.Charikar,K.Li,Multi-probeLSH:efficient indexing forhigh-dimensionalsimilaritysearch,in:Proceedingsofthe International ConferenceonVeryLargeDataBases,2007,pp.950–961.
[30] S.Tong,E.Chang,Supportvectormachineactivelearningforimageretrieval, in: ProceedingsoftheNinthACMInternationalConferenceonMultimedia, 2001, pp.107–118.
[31]M.Everingham,A.Zisserman,C.K.I.Williams,L.VanGool,Pascalvoc2006,2006.
[32] B.Scholkopf,A.Smola,LearningwithKernels:SupportVectorMachines, Regularization, Optimization,andBeyond,MITPress,2002.
[33] P.Gosselin,M.Cord,S.Philipp-Foliguet,Activelearningmethodsforinteractive image retrieval,IEEETransactionsonImageProcessing17(2008)1200–1211.
Links
Full Text
Sonstige Links
http://cedric.cnam.fr/~crucianm/src/echelle/FPrecioso.pdf slides
