2012--Super-Bit Locality-Sensitive Hashing

Super-BitLocality-SensitiveHashing

JianqiuJi ,JianminLi ,ShuichengYan ,BoZhang ,QiTian

StateKeyLaboratoryofIntelligentTechnologyandSystems,

TsinghuaNationalLaboratoryforInformationScienceandTechnology(TNList),

DepartmentofComputerScienceandTechnology,

TsinghuaUniversity,Beijing100084,China

jijq10@,

{lijianmin,dcszb}@

DepartmentofElectricalandComputerEngineering,

NationalUniversityofSingapore,Singapore,117576

eleyans@nus.edu.sg

DepartmentofComputerScience,UniversityofTexasatSanAntonio,

OneUTSACircle,UniversityofTexasatSanAntonio,SanAntonio,TX78249-1644

qitian@cs.utsa.edu

Abstract

Sign-random-projectionlocality-sensitivehashing(SRP-LSH)isaprobabilisticdimensionreductionmethodwhichprovidesanunbiasedestimateofangularsim-ilarity,yetsuffersfromthelargevarianceofitsestimation.Inthiswork,wepro-posetheSuper-Bitlocality-sensitivehashing(SBLSH).Itiseasytoimplement,whichorthogonalizestherandomprojectionvectorsinbatches,anditistheoreti-callyguaranteedthatSBLSHalsoprovidesanunbiasedestimateofangularsim-ilarity,yetwithasmallervariancewhentheangletoestimateiswithin(0,π/2].Theextensiveexperimentsonrealdatawellvalidatethatgiventhesamelengthofbinarycode,SBLSHmayachievesigni cantmeansquarederrorreductioninestimatingpairwiseangularsimilarity.Moreover,SBLSHshowsthesuperiorityoverSRP-LSHinapproximatenearestneighbor(ANN)retrievalexperiments.1Introduction

Locality-sensitivehashing(LSH)methodaimstohashsimilardatasamplestothesamehashcodewithhighprobability[7,9].ThereexistvariouskindsofLSHforapproximatingdifferentdistancesorsimilarities,e.g.,bit-samplingLSH[9,7]forHammingdistanceand 1-distance,min-hash[2,5]forJaccardcoef cient.AmongthemaresomebinaryLSHschemes,whichgeneratebinarycodes.BinaryLSHapproximatesacertaindistanceorsimilarityoftwodatasamplesbycomputingtheHammingdistancebetweenthecorrespondingcompactbinarycodes.SincecomputingHammingdistanceinvolvesmainlybitwiseoperations,itismuchfasterthandirectlycomputingotherdis-tances,e.g.Euclidean,cosine,whichrequiremanyarithmeticoperations.Ontheotherhand,thestorageissubstantiallyreducedduetotheuseofcompactbinarycodes.Inlarge-scaleapplications

[20,11,5,17],e.g.near-duplicateimagedetection,objectandscenerecognition,etc.,weareoftenconfrontedwiththeintensivecomputingofdistancesorsimilaritiesbetweensamples,thenbinaryLSHmayactasascalablesolution.

1.1Locality-SensitiveHashingforAngularSimilarity

Formanydatarepresentations,thenaturalpairwisesimilarityisonlyrelatedwiththeanglebetweenthedata,e.g.,thenormalizedbag-of-wordsrepresentationfordocuments,images,andvideos,andthenormalizedhistogram-basedlocalfeatureslikeSIFT[18].Inthesecases,angularsimilarity

a,b canserveasasimilaritymeasurement,whichisde nedassim(a,b)=1 cos 1( )/π.Here

a,b denotestheinnerproductofaandb,and · denotesthe 2-normofavector.

OnepopularLSHforapproximatingangularsimilarityisthesign-random-projectionLSH(SRP-LSH)[3],whichprovidesanunbiasedestimateofangularsimilarityandisabinaryLSHmethod.Formally,inad-dimensionaldataspace,letvdenotearandomvectorsampledfromthenormaldistributionN(0,Id),andxdenoteadatasample,thenanSRP-LSHfunctionisde nedashv(x)=sgn(vTx),wherethesignfunctionsgn(·)isde nedas

1,z≥0sgn(z)=0,z<0

a,b Giventwodatasamplesa,b,letθa,b=cos 1( ),thenitcanbeproventhat[3]

Pr(hv(a)=hv(b))=θa,b

Thispropertywellexplainstheessenceoflocality-sensitive,andalsorevealstherelationbetweenHammingdistanceandangularsimilarity.

ByindependentlysamplingKd-dimensionalvectorsv1,...,vKfromthenormaldistributionN(0,Id),wemayde neafunctionh(x)=(hv1(x),hv2(x),...,hvK(x)),whichconsistsofKSRP-LSHfunctionsandthusproducesK-bitcodes.Thenitiseasytoprovethat

E[dHamming(h(a),h(b))]=Kθa,b

=Cθa,b

Thatis,theexpectationoftheHammingdistancebetweenthebinaryhashcodesoftwogivendatasamplesaandbisanunbiasedestimateoftheirangleθa,b,uptoaconstantscalefactorC=K/π.ThusSRP-LSHprovidesanunbiasedestimateofangularsimilarity.

SincedHamming(h(a),h(b))followsabinomialdistribution,i.e.dHamming(h(a),h(b))～

Kθa,bθa,bθitsvarianceisThisimpliesthatthevarianceofB(K,a,b

),(1 ).

dHamming(h(a),h(b))/K,i.e.Var[dHamming(h(a),h(b))/K],satis es

Var[dHamming(h(a),h(b))/K]=θa,b

(1 θa,b

)

Thoughbeingwidelyused,SRP-LSHsuffersfromthelargevarianceofitsestimation,whichleadstolargeestimationerror.Generallyweneedasubstantiallylongcodetoaccuratelyapproximatetheangularsimilarity[22,12,21].Thereasonisthatanytwooftherandomvectorsmaybeclosetobeinglinearlydependent.Thustheresultingbinarycodemaybelessinformativeasitseems,andevencontainsmanyredundantbits.Anintuitiveideawouldbetoorthogonalizetherandomvectors.However,oncebeingorthogonalized,therandomvectorscannolongerbeviewedasindependentlysampled.Moreover,itremainsunclearwhethertheresultingHammingdistanceisstillanunbiasedestimateoftheangleθa,bmultipliedbyaconstant,terwewillgiveanswerswiththeoreticaljusti cationstothesetwoquestions.

Inthenextsection,basedontheaboveintuitiveidea,weproposetheso-calledSuper-Bitlocality-sensitivehashing(SBLSH)method.Weprovidetheoreticalguaranteesthatafterorthogonalizingtherandomprojectionvectorsinbatches,westillgetanunbiasedestimateofangularsimilarity,yetwithasmallervariancewhenθa,b∈(0,π/2],andthustheresultingbinarycodeismoreinformative.Ex-perimentsonrealdatashowtheeffectivenessofSBLSH,whichwiththesamelengthofbinarycodemayachieveasmuchas30%meansquarederror(MSE)reductioncomparedwiththeSRP-LSHinestimatingangularsimilarityonrealdata.Moreover,SBLSHperformsbestamongseveralwidelyuseddata-independentLSHmethodsinapproximatenearestneighbor(ANN)retrievalexperiments.2Super-BitLocality-SensitiveHashing

TheproposedSBLSHisfoundedonSRP-LSH.WhenthecodelengthKsatis es1<K≤d,wheredisthedimensionofdataspace,wecanorthogonalizeN(1≤N≤min(K,d)=K)oftherandomvectorssampledfromthenormaldistributionN(0,Id).Theorthogonalizationprocedure

v12

v4v …… 此处隐藏：5781字，全部文档内容请下载后查看。喜欢就下载吧 ……