Dans le domaine du traitemant du langage naturel (NLP), la converison de mots en vecteurs numériques est une étape fondamentale. Word2Vec s'est imposé comme une référence en capturant les relations sémantiques entre les termes. Avec l'explosion des données structurées sous forme de réseaux, l'algorithme DeepWalk a vu le jour, adaptant les concepts de Word2Vec pour apprendre des représentations de nœuds dans un graphe via des marches aléatoires.

1. Word2Vec : Dépasser les limites du One-Hot

Le problème du codage binaire

Initialement, les mots étaient représentés par des vecteurs "one-hot", où un seul bit est actif pour chaque mot du dictionnaire :

// Exemple simplifié de vecteurs One-Hot
"serveur"  -> [1, 0, 0, 0, 0]
"client"   -> [0, 1, 0, 0, 0]
"données"  -> [0, 0, 1, 0, 0]

Cette méthode pose deux problèmes majeurs : une dimensionnalité explosive proportionnelle à la taille du lexique, et une absence totale de notion de proximité (la distance entre deux vecteurs est toujours idenitque).

La solution : Les plongements (Embeddings)

Word2Vec transforme ces données éparses en vecteurs denses de faible dimension. Dans cet espace, des mots partageant un contexte similaire se retrouvent géographiquement proches.

// Représentations denses fictives
v_ordinateur = [0.12, -0.45, 0.88]
v_clavier    = [0.15, -0.42, 0.82]
v_foret      = [-0.78, 0.11, -0.05]

Ici, v_ordinateur et v_clavier présentent une forte similarité cosinus, reflétant leur lien conceptuel.

2. Stratégies d'apprentissage : CBOW et Skip-gram

Le framework Word2Vec repose sur deux architectures distinctes :

• CBOW (Continuous Bag of Words) : Prédit un mot cible en fonction des mots qui l'entourent.
• Skip-gram : À partir d'un mot central, tente de prédire les mots de son voisinage (contexte).

C'est l'approche Skip-gram que DeepWalk utilise, car elle s'avère plus performante pour capturer les structures locales complexes.

3. Mécanique du modèle Skip-gram

Soit une séquence de jetons \( s_1, s_2, ..., s_n \). Pour chaque jeton \( s_i \), l'objectif est de maximiser la probabilité d'observer les jetons voisins compris dans une fenêtre de taille \( k \).

La fonction d'objectif consiste à maximiser la log-vraisemblance :

\[ \mathcal{L} = \frac{1}{n} \sum_{i=1}^{n} \sum_{-k \le j \le k, j \neq 0} \log P(s_{i+j} | s_i) \]$$

L'usage du logarithme transforme les produits de probabilités en sommes, ce qui stabilise le calcul des gradients lors de la rétropropagation et évite les problèmes d'underflow numérique.

4. L'architecture neuronale

Le modèle se compose d'une structure simple à trois couches :

1. Couche d'entrée : Reçoit l'indice du mot (souvent via un vecteur one-hot).
2. Couche cachée (Embedding) : Une matrice de poids \( W \) de dimension \( V \times D \) (où \( V \) est la taille du vocabulaire et \( D \) la dimension du vecteur souhaitée).
3. Couche de sortie : Utilise une fonction Softmax pour générer une distribution de probabilité sur tout le vocabulaire.

5. DeepWalk : Du texte aux structures de graphes

L'innovation de DeepWalk réside dans une analogie puissante : considérer un nœud comme un mot et une marche aléatoire comme une phrase.

La Marche Aléatoire (Random Walk)

Au lieu de parcourir le graphe de manière exhaustive (BFS ou DFS), DeepWalk génère des séquences de nœuds en partant d'un point \( u \) et en choisissant uniformément au hasard un voisin pour l'étape suivante. Cette méthode permet de simuler une exploration fluide du réseau.

# Exemple de chemin généré par une marche aléatoire
Nœud_A -> Nœud_C -> Nœud_B -> Nœud_E -> Nœud_F

Ces séquences sont ensuite injectées dans le modèle Skip-gram comme s'il s'agissait de phrases naturelles.

6. Pourquoi DeepWalk fonctionne-t-il ?

Le principe fondamental est la co-occurrence. Si deux nœuds apparaissent fréquemment ensemble dans des marches aléatoires, cela signifie qu'ils sont structurellement proches dans le graphe. Par conséquent, l'optimisation forcera leurs vecteurs de représentation à converger dans l'espace latent.

• Fréquence élevée : Similarité structurelle forte -> Vecteurs proches.
• Fréquence faible : Indépendance structurelle -> Vecteurs éloignés.

7. Comparaison synthétique

DeepWalk a ouvert la voie à de nombreuses techniques de "Graph Embedding", permettant d'appliquer des algorithmes de machine learning classiques (classification, clustering) sur des données de réseaux complexes comme les réseaux sociaux ou les systèmes de recommandation.