Document Similarity

Question 1

Quali sono le 3 tecniche di document similarity?

Answer 1

1. Shingling: convertire documenti in sets, così che possa essere utilizzata una funzione di similarità
   per set, come quella di Jaccard;
2. Minhashing: convertire grossi set in piccole firme preservandone la similarità;
3. Locality-sensitive hashing: invece che comparare tutte le coppie di elementi, concentrarsi solo su
   quelle che possono essere più simili.
   In generale, si tratta di mettere all’interno di buckets gli elementi utilizzando delle funzioni di hash,
   così che solo gli elementi che hanno condiviso un bucket almeno una volta vengano presi in
   considerazione.

Question 2

Cos’è la similarità di Jaccard?

Answer 2

La similarità di Jaccard di due sets è una misura della loro intersezione diviso il numero totale di elementi.

Question 3

Qual è l’obiettivo del MinHash?

Answer 3

L’obiettivo è sostituire i sets di shingle poiché troppo ingombranti, anche se già sottoposti ad una funzione di hash, in signatures che preservino la loro natura e quindi anche la similarità.

È necessario rifarsi ad un costrutto, ossia la characteristic matrix, tipicamente sparsa. Questa è suddivisa in colonne che corrispondono ai sets, mentre le righe corrispondono ad elementi del set globale.
Quindi avremo un 1 alla riga “e” colonna “S” se “e” è un membro di “S”.
Per effettuare il minhasing di questa matrice, si effettua la permutazione di questa per righe, e il valore di minhash della colonna S sarà il numero della riga con il primo 1 nell’ordine permutato

Question 4

Cos’è la similarità delle signatures?

Answer 4

La similarità delle signatures è la frazione di minhash functions (righe) in cui sono uguali.
Ci si aspetta che questo valore sia approssimativamente uguale alla similarità di Jaccard dei sets.
Ovviamente, se consideriamo un miliardo di righe, sarà complicato effettuare la permutazione ciclica di queste, e quindi per risolvere questa problematica si utilizzano delle funzioni di hash random che mappano le righe in “k” buckets.
Quindi piuttosto che scegliere “n” permutazioni random, utilizzamo “n” funzioni di hash.
Si crea una matrice di signatures, di righe pari al numero di funzioni di hash e colonne pari al numero di colonne della characteristic matrix.

Question 5

A cosa serve la Locality-Sensitive Hashing? E come funziona?

Answer 5

Serve per ridurre il numero di coppie da comparare per la similarità
Consiste nell’effettuare l’hash degli elementi molte volte, così che gli elementi simili è più probabile
ritrovarli all’interno dello stesso bucket.
La similarità viene definita in base ad una soglia “t” che rappresenterà il numero minimo di righe in cui le firme devono essere uguali.
Soglia alta selezioni documenti molto simili, ma puoi perdere documenti che effettivamente sono simili ma che non superano questa data soglia, ma in questo modo eviti di etichettare documenti che effettivamente non sono simili

Ovviamente, gli elementi dissimili che finiscono nello stesso bucket saranno falsi positivi, mentre quelli
simili che non finiranno nello stesso bucket rappresentano i falsi negativi.
La matrice M viene suddivisa in “b” bande e “r” righe. Per ogni banda, si effettua l’hash di ogni colonna in una hash table di “k” buckets.
I candidati saranno le colonne che finiranno nello stesso bucket per almeno una banda.