Locality-sensitive hashing

Mål: Find dokumenter med Jaccard-sammenfald på mindst t

Den generelle idé med LSH er at finde en algoritme, der, hvis vi indtaster signaturer af 2 dokumenter, fortæller os, om disse 2 dokumenter danner et kandidatpar eller ej, dvs. om deres lighed er større end en tærskel t. Husk, at vi tager signaturernes lighed som en erstatning for Jaccard-ligheden mellem de oprindelige dokumenter.

Specifikt for min-hash signaturmatrix:

• Hash kolonner i signaturmatrix M ved hjælp af flere hash-funktioner
• Hvis 2 dokumenter hash’er i samme spand for mindst en af hash-funktionerne kan vi tage de 2 dokumenter som et kandidatpar

Nu er spørgsmålet, hvordan man skaber forskellige hash-funktioner. Til dette formål foretager vi en båndpartition.

Bandpartition

Her er algoritmen:

• Opdel signaturmatrixen i b bånd, hvor hvert bånd har r rækker
• For hvert bånd, hash’es sin del af hver kolonne til en hashtabel med k spande
• Kandidatkolonnepar er dem, der hash’es til den samme spand for mindst 1 bånd
• Tune b og r for at fange de fleste lignende par, men få ikke lignende par

Der er få overvejelser her. Ideelt set ønsker vi for hvert bånd at tage k som værende lig med alle mulige kombinationer af værdier, som en kolonne kan antage inden for et bånd. Dette vil svare til identitetsmatchning. Men på denne måde vil k være et enormt tal, som er beregningsmæssigt uigennemførligt. F.eks.: Hvis et bånd har 5 rækker i det. Hvis elementerne i signaturen er 32 bit-integriteter, vil k i dette tilfælde være (2³²)⁵ ~ 1,4615016e+48. Du kan se, hvad der er problemet her. Normalt tages k omkring 1 million.

Tanken er, at hvis 2 dokumenter ligner hinanden, så vil de optræde som kandidatpar i mindst ét af båndene.

Valg af b & r

Hvis vi tager b stort, dvs. flere antal hash-funktioner, så reducerer vi r, da b*r er en konstant (antal rækker i signaturmatrixen). Intuitivt betyder det, at vi øger sandsynligheden for at finde et kandidatpar. Dette tilfælde svarer til at tage et lille t (lighedstærskel)

Lad os sige, at din signaturmatrix har 100 rækker. Overvej 2 tilfælde:

b1 = 10 → r = 10

b2 = 20 → r = 5

I 2. tilfælde er der større chance for, at 2 dokumenter optræder i samme spand mindst én gang, da de har flere muligheder (20 vs. 10), og færre elementer i signaturen bliver sammenlignet (5 vs. 10).

Højere b indebærer lavere lighedstærskel (højere falsk positive) og lavere b indebærer højere lighedstærskel (højere falsk negative)

Lad os prøve at forstå dette gennem et eksempel.

Setup:

• 100k dokumenter gemt som signatur af længde 100
• Signaturmatrix: 100*100000
• Brute force-sammenligning af signaturer vil resultere i 100C2 sammenligninger = 5 milliarder (ret meget!)
• Lad os tage b = 20 → r = 5

Tærskelværdi for lighed (t): 80%

Vi ønsker, at 2 dokumenter (D1 & D2) med 80% lighed skal hashes i den samme spand for mindst et af de 20 bånd.

P(D1 & D2 er identiske i et bestemt bånd) = (0,8)⁵ = 0,328

P(D1 & D2 ligner ikke hinanden i alle 20 bånd) = (1-0,328)^20 = 0,00035

Det betyder, at vi i dette scenarie har ~.035% chance for en falsk negativ @ 80% ens dokumenter.

Det er også ønsket, at 2 dokumenter (D3 & D4) med 30% lighed ikke skal hashes i den samme spand for nogen af de 20 bånd (tærskel = 80%).

P(D3 & D4 identisk i et bestemt bånd) = (0,3)⁵ = 0.00243

P(D3 & D4 er ens i mindst et af de 20 bånd) = 1 – (1-0.00243)^20 = 0.0474

Det betyder, at vi i dette scenario har ~4,74% chance for en falsk positiv @ 30% ens dokumenter.

Så vi kan se, at vi har nogle falske positive og få falske negative. Denne andel vil variere med valg af b og r.

Det, vi ønsker her, er noget som nedenfor. Hvis vi har to dokumenter, som har en lighed, der er større end tærsklen, skal sandsynligheden for, at de deler den samme spand i mindst et af båndene, være 1 ellers 0.

Det værste tilfælde vil være, hvis vi har b = antallet af rækker i signaturmatrixen som vist nedenfor.

Generaliseret tilfælde for ethvert b og r er vist nedenfor.

Vælg b og r for at få den bedste S-kurve i.e mindste falsk negative og falsk positive rate

LSH-sammenfatning

• Tune M, b, r til at få næsten alle dokumentpar med lignende signaturer, men fjerne de fleste par, der ikke har lignende signaturer
• Kontroller i hovedhukommelsen, at kandidatpar virkelig har lignende signaturer