Une explication simple du Locality sensitive hashing

Dans cet article, je résume ce qu’est la méthode « Locality sensitive hashing ». L’article vient en complément de cette page wikipédia qui est blindée de formules mathématiques insupportables à lire.

Les références qui m’ont permises de comprendre la méthode : How to spot first stories on Twitter using Storm, Online Generation of Locality
Sensitive Hash Signatures et un tout petit peu la page wikipédia.

Objectif

Locality sensitive hashing est une méthode permettant de faciliter la comparaison d’individus statistiques à forte dimension. Pour cela, l’objectif va être de réduire la dimension de ces derniers. Les individus doivent être décrits par des variables quantitatives, jusque là je n’ai jamais vu une application avec des variables qualitatives. Mais ça doit être faisable avec des variables qualitatives ordonnées.

Principe

Précisions sur l’explication

Pour expliquer le principe, je vais fortement m’inspirer de ces slides (présentation à ACL 2010).

Pour simplifier l’explication, je vais utiliser des individus à 2 dimensions. Le principe est stupide car la dimension est faible (tout enté^ret d’utiliser la méthode est perdu), mais ça permet de faire des représentations graphiques en 2D très claires.

Théorie (sans formule bien-sûr)

Explication de base

L’objectif de cette méthode est de traduire les différents vecteurs sous forme de « code« . Ces codes sont (beaucoup) plus simples que les vecteurs en terme de dimension. Ainsi, plutôt que de comparer les vecteurs entre eux, nous utiliseront la distance de Hamming : il s’agit de faire un ET logique entre les différents codes deux à deux. Ce ET logique va retourner le nombre de digits communs aux deux codes et ainsi donner une valeur de similarité.

J’ai lu plusieurs fois qu’il est commun de ne pas s’arrêter à cette valeur de similarité et de calculer l’angle entre les deux vecteurs en utilisant la distance de Hamming obtenue. Plus l’angle est petit, plus les vecteurs analysés comme proches.

Si vous n’êtes pas familier avec le fonctionnement du cosinus, observez ce schéma en guise de rappel.

Comment passer d’un vecteur à un code? 

Rappelons que notre vecteur est exprimé sur un grand nombre de dimension avec des valeurs numériques. Notre code correspondant va être décrit par un nombre bien plus faible de dimension et (bien souvent mais pas obligatoirement) avec des valeurs binaires {0,1}.

Par exemple, notre vecteur « ind#1 » correspond à :

2.9     1.1     -7.2     -0.2     2     8.1     -7.9     1.98     9

Un code correspondant peut être :

1     0     1

Mais comment trouvé ce code donc?

Pour cela, on va utiliser un groupe de fonctions de hashage. A chaque fonction utilisée va résulter un digit du code. Ainsi, le code a autant de digit que de fonctions de hashage utilisées pour le créer. Par exemple, la fonction la plus simple serait de dire : « Si le point analysé est en dessous de la fonction alors je retourne 1, sinon je retourne 0 ».

Les fonctions de hashages doivent être suffisamment bien réparties dans l’espace métrique des vecteurs. Ainsi, les fonctions de hashage vont permettre d’exprimer des codes très similaires pour identifier deux vecteurs proches.

Explication graphique

Rappel : Lisez la partie Précisions sur l’explication.

Voilà ci-dessous deux individus (vecteurs) exprimés sur deux dimensions.

schema-1

Nous allons utiliser des fonctions de hashage linéaires. Si le point est situé au dessus de la fonction, nous ajouter à notre code le digit 1, si il est situé en dessous, nous ajoutons le digit 0. Pour le moment, le code à 0 digit.

Première fonction de hashage :

schema-1

Ainsi, le point rouge est au dessus de la première fonction de hashage et le point vert en dessous, soit :

codeDuPointRouge = 1
codeDuPointVert = 0

On continue avec une seconde fonction de hashage :

schema-1

On obtient les codes :

codeDuPointRouge = 1 1
codeDuPointVert = 0 1

Puis 5 autres fonctions :

schema-1

Ce qui donne les codes suivants :

codeDuPointRouge = 1 1 1 0 1 1 1

codeDuPointVert = 0 1 1 1 1 1 0

Une fois les codes obtenus, on peut les comparer. Plusieurs méthodes sont possibles et il est d’usure d’utiliser la distance de hamming (le ET logique : on compte le nombre de digits en commun).

Ainsi avec la distance de Hamming, on a la distance d :

d(codeDuPointRouge, codeDuPointVert) = 4

Explication visuelle de ce résultat :

1  1  1  0 1  1  1

0 1  1  1  1  1  0

Calcul de l’angle : 

Comme dit dans la partie Explication de base, il est courant de calculer l’angle entre les deux vecteurs et s’en servir de valeur de similarité. La formule est simple, on se sert du cosinus :

angle = cos(distanceDeHamming*Pi/tailleDuCode)

Attention cet exemple est mauvais

L’objectif de la méthode est de réduire la dimension en passant du vecteur de base au hashcode. Or dans notre exemple, on part d’un vecteur à deux dimensions à un code à 7 dimensions. C’est donc totalement mauvais de faire ce qui a été fait. J’ai fait ça uniquement pour l’aspect graphique facilement interprétable.

 

Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s