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