2012--Super-Bit Locality-Sensitive Hashing(2)

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,http://www.77cn.com.cnterwewillgiveanswerswiththeoreticaljusti 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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库2012--Super-Bit Locality-Sensitive Hashing(2)在线全文阅读。