Locality-sensitive hashing

Mål: Hitta dokument med en Jaccard-likhet på minst t

Den allmänna idén med LSH är att hitta en algoritm som, om vi matar in signaturer för två dokument, talar om för oss att de två dokumenten bildar ett par som kan komma att ingå i ett kandidatpar eller inte, dvs. att deras likhet är större än en tröskel t. Kom ihåg att vi använder signaturernas likhet som en representant för Jaccard-likheten mellan originaldokumenten.

Specifikt för min-hash signaturmatris:

• Hash kolumnerna i signaturmatrisen M med hjälp av flera hash-funktioner
• Om 2 dokument hashasar i samma hink för minst en av hash-funktionerna kan vi betrakta de 2 dokumenten som ett kandidatpar

Nu är frågan hur man skapar olika hash-funktioner. För detta gör vi en bandpartition.

Bandpartition

Här är algoritmen:

• Dela upp signaturmatrisen i b band, varje band har r rader
• För varje band, Hashar du dess del av varje kolumn till en hashtabell med k hinkar
• Kandidatkolumnpar är de som hashar till samma hink för minst ett band
• Sätt b och r så att du fångar upp de mest likartade paren, men få icke likartade par

Det finns några få överväganden här. Helst vill vi för varje band att k ska vara lika med alla möjliga kombinationer av värden som en kolumn kan anta inom ett band. Detta kommer att motsvara identitetsmatchning. Men på detta sätt kommer k att vara ett stort antal vilket är beräkningsmässigt ogenomförbart. Exempel: Om vi har 5 rader i ett band. Om elementen i signaturen är 32 bitars heltal blir k i detta fall (2³²)⁵ ~ 1,4615016e+48. Du kan se vad som är problemet här. Normalt sett brukar k ligga runt 1 miljon.

Tanken är att om två dokument är likartade så kommer de att dyka upp som kandidatpar i minst ett av banden.

Val av b & r

Om vi tar b stort, dvs. fler hash-funktioner, minskar vi r eftersom b*r är en konstant (antal rader i signaturmatrisen). Intuitivt betyder det att vi ökar sannolikheten att hitta ett kandidatpar. Detta fall är likvärdigt med att ta ett litet t (likhetströskel)

Säg att din signaturmatris har 100 rader. Överväg 2 fall:

b1 = 10 → r = 10

b2 = 20 → r = 5

I det andra fallet är chansen större att 2 dokument förekommer i samma hink minst en gång eftersom de har fler möjligheter (20 mot 10) och färre element i signaturen jämförs (5 mot 10).

Högre b innebär lägre likhetströskel (högre falskt positiva) och lägre b innebär högre likhetströskel (högre falskt negativa)

Låt oss försöka förstå detta med hjälp av ett exempel.

Inställning:

• 100k dokument lagrade som signaturer av längd 100
• Signaturmatris: 100*100000
• Brute force-jämförelse av signaturer kommer att resultera i 100C2 jämförelser = 5 miljarder (ganska mycket!)
• Låt oss ta b = 20 → r = 5

Tröskelvärde (t) för likhet (t): 80 %

Vi vill att två dokument (D1 & D2) med 80 % likhet ska hashasheras i samma hink för minst ett av de 20 banden.

P(D1 & D2 identiska i ett visst band) = (0,8)⁵ = 0,328

P(D1 & D2 liknar inte varandra i alla 20 band) = (1-0,328)^20 = 0,00035

Detta innebär att vi i detta scenario har ~.035 % risk för falskt negativa resultat vid 80 % likartade dokument.

Och vi vill att två dokument (D3 & D4) med 30 % likhet inte ska hashasheras i samma hink för något av de 20 banden (tröskelvärde = 80 %).

P(D3 & D4 är identiska i ett visst band) = (0,3)⁵ = 0.00243

P(D3 & D4 liknar varandra i minst ett av de 20 banden) = 1 – (1-0.00243)^20 = 0.0474

Detta innebär att vi i detta scenario har ~4,74% chans att få ett falskt positivt resultat @ 30% likartade dokument.

Så vi kan se att vi har en del falskt positiva resultat och få falskt negativa resultat. Dessa andelar kommer att variera med valet av b och r.

Vad vi vill ha här är något som liknar nedan. Om vi har två dokument som har en likhet som är större än tröskelvärdet ska sannolikheten för att de delar samma hink i minst ett av banden vara 1 annars 0.

Det värsta fallet blir om vi har b = antalet rader i signaturmatrisen enligt nedan.

Det allmänna fallet för alla b och r visas nedan.

Välj b och r för att få den bästa S-kurvan i.e minsta falskt negativa och falskt positiva frekvens

LSH summary

• Tuning M, b, r för att få fram nästan alla dokumentpar med liknande signaturer, men eliminera de flesta par som inte har liknande signaturer
• Kontrollera i huvudminnet att kandidatpar verkligen har liknande signaturer