 |
| Visualisation d'un graphe sémantique. (moteur maison golang/ebitengine) |
Pour commencer… qu’est-ce qu’un graphe ?
Un graphe, c’est une structure de données composée de nœuds (aussi appelés sommets), reliés entre eux par des liens (ou arêtes).
C’est une structure très souple, qui permet de modéliser à peu près n’importe quel type de relation entre des éléments.
Dans bien des cas, structurer les données sous forme de graphe serait inutile ou excessif… mais dans d’autres, c’est un outil efficace.
Parmi les exemples les plus connus, on trouve les graphes sociaux, qui ont explosé avec l’essor des réseaux du même nom.
Dans un graphe social, chaque nœud représente une personne (ou plus exactement, un compte utilisateur sur un réseau).
Les plateformes les plus populaires comptent des millions, voire des milliards de nœuds.
Si deux personnes sont "amies", on trace un lien entre leurs deux nœuds.
Bob et Alice ont chacun un compte sur le réseau : ils sont donc représentés chacun par un sommet (ou nœud) dans le graphe. Comme Bob et Alice sont amis, on trace un lien (arête) entre leurs sommets respectifs. On répète cette opération pour chaque paire d’amis sur le réseau… ce qui donne un graphe massif, à l’image de la taille du réseau social.
(Bob) <--> (Alice)
Graphe sémantique
Ok pour les graphes sociaux, mais quel rapport avec Lexiflaire, les mots, la sémantique ?
On peut appliquer le même principe, mais cette fois, chaque sommet correspond à un mot (ou, comme on l’a vu dans l’article précédent, à un lemme), et chaque lien représente une similarité entre deux mots.
On peut imaginer qu’un mot sera relié à ses synonymes, à ses antonymes, ou à d’autres mots appartenant au même champ lexical.
Par exemple, roue sera lié à pneu, chaud à froid, ou encore locomotive à wagon.
Dans les graphes sociaux, les liens sont simples : si deux sommets sont amis, il y a un lien ; sinon, il n’y en a pas.
Dans le cas de notre graphe sémantique, c’est plus nuancé. Certains liens sont plus forts que d’autres.
Chaque lien a un poids mesurable, généralement exprimé entre 0 et 1 (ou en pourcentage).
Visuellement, un lien plus fort pourra être représenté par une ligne plus épaisse.
Par exemple, le lien entre rail et train sera — on peut l’imaginer — très fort, disons 80 %.
Le lien entre rail et wagon existera aussi, mais sera plus faible, peut-être autour de 50 %.
Et on construit ça comment ?
Repartons de la base : une partie de Lexiflaire.
Mot à deviner : wagon
Indice 1 : locomotive
Réponse 1 : train
Indice 2 : remorque
Réponse 2 : wagon
Pour chaque sommet, on enregistre le nombre d’occurrences (combien de fois ce mot apparaît dans une partie).
Pour chaque lien, on enregistre le nombre de cooccurrences (combien de fois ces deux mots ont été associés dans une paire).
Mais on ne s’arrête pas là.
La réponse wagon ne dépend pas uniquement de l’indice remorque, mais aussi du contexte donné par l’indice précédent, locomotive.
On va donc créer un lien supplémentaire entre locomotive et wagon : un lien plus indirect, mais pertinent.
En revanche, train et remorque n’ont pas nécessairement de lien, car la réponse train a été donnée avant l’apparition de l’indice remorque, donc aucune raison de créer un lien entre eux.
Avec uniquement cette partie :
-
Sommet locomotive = 1
-
Sommet train = 1
-
Sommet remorque = 1
-
Sommet wagon = 1
-
Lien locomotive – train = 1
-
Lien remorque – wagon = 1
-
Lien locomotive – wagon = 1
Continuons le processus, mais cette fois en prenant en compte l’ensemble des parties jouées dans Lexiflaire.
Que donnent les comptages globaux pour nos sommets et nos liens ?
-
Sommet locomotive = 21 972
-
Sommet train = 72 314
-
Sommet remorque = 12 627
-
Sommet wagon = 25 797
-
Lien locomotive – train = 9376
-
Lien remorque – wagon = 103
-
Lien locomotive – wagon = 2730
Comme on peut le constater, le nombre d’occurrences d’un sommet est bien supérieur au nombre de cooccurrences entre deux mots liés. Ce qui est parfaitement logique.
Dans un cas extrême, le nombre maximal de cooccurrences entre locomotive et train est limité par le nombre total d’occurrences du mot le moins fréquent, ici locomotive.
Comme nous l’avons vu dans l’article précédent, il y a environ 35 000 lemmes différents dans les parties de Lexiflaire.
Cela signifie : 35 000 sommets (ou nœuds) dans notre graphe.
Mais alors, combien de liens entre ces sommets ?
Plus de 2 millions.
Parmi eux, certains liens ont un comptage très faible, même lorsqu’ils relient deux mots très fréquents.
Prenons un exemple :
Le lien entre train et animal.
Ces deux mots sont très fréquents dans le jeu :
-
train apparaît environ 72 000 fois
-
animal, plus de 300 000 fois
Mais en y réfléchissant… un lien entre animal et train n’a pas vraiment de sens. Ou alors tiré par les cheveux.
Et pourtant, on retrouve 22 cooccurrences entre ces deux mots.
Un lien avec une valeur de 22, pour relier un mot aussi fréquent qu’animal (300 000 occurrences), c’est trop faible pour être représentatif.
On voit ici que le comptage brut ne suffit pas : il peut être trompeur, surtout lorsqu’il relie deux mots très fréquents sans réel lien sémantique fort.
Il faut donc normaliser ces valeurs.
Une première idée : la pondération par fréquence
Pour commencer simplement, on peut chercher à pondérer la valeur du lien par les fréquences des deux mots qu’il relie.
Voici la formule intuitive :
Poids(A-B) = Coocc(A,B) ÷ Moyenne des occurrences de A et B
Soit, en formule :
Poids(A-B) = Coocc(A,B) / ((Occ(A) + Occ(B)) / 2)
Exemple : locomotive ↔ train
-
Occ(locomotive) = 21 972
-
Occ(train) = 72 314
-
Coocc(locomotive, train) = 9376
On applique la formule :
Poids(locomotive-train) = 9376 / ((21972 + 72314) / 2) ≈ 0,19
Soit environ 19 % : on s’attendrait à nettement plus entre train et locomotive.
Mais c’est finalement logique : un mot comme train est relié à une grande diversité de concepts. Dans le graphe sémantique, train n’est pas seulement lié à locomotive, rail ou wagon. Il est aussi relié à des notions plus larges, parfois floues, culturelles, absurdes ou même anecdotiques.
Voici les mots liés à train, filtrés uniquement pour éviter les grossièretés (et parce qu’on n’est pas limité par la place) :
wagon 26.57%, locomotive 19.89%, gare 18.43%, rail 11.84%, ferroviaire 4.41%, tgv 4.03%, sncf 4.02%, chemineau 2.42%, avion 1.86%, dérailler 1.77%, caténaire 1.64%, bus 1.59%, vapeur 1.56%, cheminot 1.50%, funiculaire 1.32%, passager 1.26%, voiture 1.21%, véhicule 1.21%, voie 1.17%, tunnel 1.15%, railler 1.12%, quai 0.99%, billet 0.85%, voyage 0.85%, fer 0.84%, ticket 0.81%, locomotion 0.81%, chemin 0.79%, station 0.76%, charbon 0.72%, voyageur 0.61%, ferrer 0.50%, grève 0.42%, déraillement 0.40%, compartiment 0.40%, retard 0.40%, composter 0.40%, vitesse 0.37%, téléphérique 0.35%, cabine 0.35%, rapide 0.34%, arrêt 0.33%, ferré 0.30%, ligne 0.29%, rame 0.27%, barrière 0.27%, sifflement 0.26%, chauffeur 0.25%, moyen 0.24%, ensemble 0.23%, voyager 0.21%, poinçonner 0.21%, route 0.20%, réseau 0.19%, micheline 0.19%, terminus 0.19%, jouet 0.19%, siège 0.19%, accident 0.18%, express 0.18%, couchette 0.18%, arrière 0.18%, convoi 0.17%, passage 0.17%, bateau 0.17%, roue 0.16%, marchandise 0.16%, collision 0.15%, siffler 0.15%, déplacement 0.15%, camion 0.14%, usager 0.14%, rouler 0.14%, départ 0.13%, machine 0.13%, déportation 0.13%, classe 0.13%, cheminer 0.13%, caréner 0.13%, aiguillage 0.13%, fumée 0.12%, pilote 0.12%, wagonnet 0.12%, guichet 0.12%, destination 0.12%, cheminée 0.12%, coke 0.11%, long 0.11%, sifflet 0.11%, orient 0.11%, mine 0.11%, car 0.10%, itinéraire 0.10%, roule 0.10%, derrière 0.10%, cathéter 0.10%, navette 0.10%, place 0.09%, niveau 0.09%, engin 0.09%, suicide 0.09%, pont 0.09%, remorque 0.09%, bagage 0.09%, cheval 0.09%, aéroport 0.09%, crémaillère 0.08%, arriéré 0.08%, fret 0.08%, télésiège 0.08%, général 0.08%, longue 0.08%, manche 0.08%, câblé 0.08%, payant 0.08%, circuit 0.08%, météo 0.07%, indice 0.07%, valise 0.07%, voix 0.07%, atterrissage 0.07%, tortillard 0.07%, loco 0.07%, sortir 0.07%, fantôme 0.07%, correspondance 0.07%, vélo 0.07%, connexion 0.07%, horaire 0.06%, maquette 0.06%, chouchou 0.06%, touriste 0.06%, vagabond 0.06%, shoah 0.06%, western 0.06%, diligence 0.06%, signal 0.06%, fumé 0.06%, hangar 0.06%, avant 0.06%, moto 0.06%, rayer 0.06%, commun 0.06%, allure 0.05%, camp 0.05%, automobile 0.05%, désolé 0.05%, circulation 0.05%, thomas 0.05%, gars 0.05%, vite 0.05%, soute 0.05%, arrivée 0.05%, montagne 0.05%, ferry 0.05%, garer 0.05%, client 0.05%, chariot 0.05%, mdr 0.05%, déporter 0.05%, conduire 0.05%, gaz 0.05%, terminal 0.05%, caravane 0.04%, ville 0.04%, lactée 0.04%, manège 0.04%, stop 0.04%, raie 0.04%, dérayer 0.04%, mécanique 0.04%, fusée 0.04%, métal 0.04%, ancien 0.04%, embarquer 0.04%, piste 0.04%, crash 0.04%, vermeil 0.04%, billetterie 0.04%, déplacer 0.04%, sol 0.04%, aller 0.04%, simple 0.04%, devant 0.04%, roué 0.04%, agent 0.04%, manifestation 0.04%, wtt 0.04%, descendre 0.04%, heu 0.04%, vacance 0.04%, partir 0.04%, aérien 0.04%, dessus 0.04%, nomade 0.04%, machiniste 0.04%, entier 0.04%, aiguiller 0.04%, dessous 0.04%, modélisme 0.04%, poinçonneur 0.04%, chenille 0.03%, lieu 0.03%, routier 0.03%, dévier 0.03%, queue 0.03%, carambolage 0.03%, postérieur 0.03%, cocaïne 0.03%, clochard 0.03%, personne 0.03%, halte 0.03%, partie 0.03%, ram 0.03%, fraudeur 0.03%, généralité 0.03%, futur 0.03%, ferraille 0.03%, attendre 0.03%, hitler 0.03%, grand 0.03%, périphérie 0.03%, mécanicien 0.03%, fil 0.03%, calèche 0.03%, férié 0.03%, aiguilleur 0.03%, monter 0.03%, déporté 0.03%, ruche 0.03%, aide 0.03%, essieu 0.03%, téléski 0.03%, autoroute 0.03%, klaxon 0.03%, rai 0.03%, viaduc 0.03%, chanceler 0.03%, fin 0.03%, essence 0.03%, porte 0.03%, distance 0.03%, conteneur 0.03%, carte 0.03%, rapt 0.03%, tutelle 0.03%, retour 0.03%, plus 0.03%, taxi 0.03%, cockpit 0.03%, miniature 0.03%, syndicat 0.03%, bar 0.03%, omnibus 0.03%, composteur 0.03%, nazi 0.03%, réservation 0.03%, banquette 0.03%, escale 0.03%, embarquement 0.03%, tout 0.03%, mouvement 0.03%, port 0.03%, nord 0.03%, file 0.03%, support 0.03%, parking 0.03%, con 0.03%, auto 0.03%, terre 0.03%, pause 0.02%, petit 0.02%, cargaison 0.02%, prendre 0.02%, routière 0.02%, montmartre 0.02%, fourgon 0.02%, arrivé 0.02%, restaurant 0.02%, moderne 0.02%, angleterre 0.02%, russe 0.02%, vague 0.02%, arriver 0.02%, allemagne 0.02%, lit 0.02%, mer 0.02%, payer 0.02%, parcours 0.02%, tourne 0.02%, atterrir 0.02%, connard 0.02%, attelage 0.02%, quotidien 0.02%, téléférique 0.02%, chaudière 0.02%, sdf 0.02%, corail 0.02%, avancer 0.02%, merci 0.02%, pendaison 0.02%, remontée 0.02%, relatif 0.02%, fumer 0.02%, vacancier 0.02%, argent 0.02%, oublié 0.02%, parc 0.02%, fauteuil 0.02%, chaîne 0.02%, papier 0.02%, croupe 0.02%, caisse 0.02%, merde 0.02%, frontière 0.02%, garage 0.02%, gens 0.02%, circuler 0.02%, type 0.02%, tête 0.02%, bétail 0.02%, vie 0.02%, service 0.02%, lien 0.02%, monorail 0.02%, ballast 0.02%, marche 0.02%, ski 0.02%, poinçon 0.02%, autobus 0.02%, lyon 0.02%, objet 0.02%, garde 0.02%, première 0.02%, pilotage 0.02%, acier 0.02%, mort 0.02%, tarif 0.02%, panne 0.02%, capot 0.02%, gâter 0.02%, cinéma 0.02%, aiguisage 0.02%, global 0.02%, course 0.02%, sonnette 0.02%, internet 0.02%, détourner 0.02%, conduit 0.02%, révolution 0.02%, dû 0.02%, périphérique 0.02%, bois 0.02%, rapidité 0.02%, éviter 0.02%, barre 0.02%, accueil 0.02%, illégal 0.02%, métier 0.02%, bruit 0.02%, interdit 0.02%, ton 0.02%, diesel 0.02%, volant 0.02%, sur 0.02%, court 0.02%, virage 0.02%, inverse 0.02%, voleur 0.02%, rangement 0.02%, four 0.02%, voir 0.02%, chambre 0.02%, temps 0.02%, plan 0.02%, endroit 0.02%, sirène 0.02%, pipi 0.01%, vieux 0.01%, coffre 0.01%, foule 0.01%, rue 0.01%, vent 0.01%, énergie 0.01%, pièce 0.01%, nul 0.01%, débuter 0.01%, jeu 0.01%, feu 0.01%, maison 0.01%, film 0.01%, tourner 0.01%, enfant 0.01%, chaud 0.01%, faire 0.01%, guerre 0.01%, vache 0.01%, corde 0.01%, chien 0.01%, animal 0.01%, eau 0.01%
Bon, on peut noter que dans le top, au-dessus de 0,1 %, c’est très cohérent. En dehors de chemineau, qui n’a pas le même sens que cheminot, et de railler, mais ce sont des erreurs d’orthographe un peu particulières… Ensuite, c’est plus variable, mais ça reste acceptable.
Et c’est bien le problème : à 0,1 %, on s’attend à un lien bruité, à côté de la plaque. Là, on a des 0,1 %, voire 0,05 %, qui méritent leur place dans l’environnement sémantique de train. Mais c’est dû à la masse de données : il nous faut une transformation pour ça.
Log/Log
On ne va pas tout reprendre depuis le début, le changement est simple : on ajoute des logarithmes.
Je passe très vite sur le logarithme : un logarithme évolue beaucoup plus lentement que sa valeur. Par exemple : log(10) = 2, log(100) = 3, log(1000) = 4, etc.
Avant, on avait :
Poids(A-B) = Coocc(A, B) ÷ Moyenne des occurrences de A et B
Maintenant, on a :
Poids(A-B) = Log(Coocc(A, B)) ÷ Log(Moyenne des occurrences de A et B)
Je ne vais pas remettre toute la liste… mais quelques exemples :
le top — wagon 87,73 %, locomotive 84,99 %, gare 84,28 %, rail 80,15 %, ferroviaire 70,53 %.
Cette fois, les liens très forts sont, comme attendu, proches de 1 (enfin… de 100 %, mais c’est pareil).
Et pour des liens miniatures : vacancier 21,83 %, oublié 21,82 %, vache 21,77 %.
Cette transformation log/log a deux effets très utiles. D’abord, elle rend les poids plus lisibles et interprétables : on se retrouve avec une échelle plus intuitive, où les très fortes cooccurrences frôlent les 100% et les liens plus faibles tombent doucement sans être écrasés. Ensuite, elle permet de fixer des seuils empiriques, en observant visuellement les résultats :
-
> 65 % : lien fort
-
> 45 % : lien cohérent
-
> 30 % : lien éloigné mais encore acceptable
log(occ(A)) ou log(occ(B)). J’ajouterai sûrement un point à cet article si j’arrive à bien interpréter ces deux variantes.Et maintenant ?
Ce graphe pondéré, une fois nettoyé et transformé, devient une carte sémantique : chaque mot est relié à ses voisins par des liens dont l’intensité reflète une proximité d’usage. C’est déjà utile en soi, mais ce n’est qu’un début : on pourra en extraire des groupes de mots (par clustering, à venir). Et comme on l’a vu dans les illustrations, en ne gardant que les liens les plus forts, le graphe prend aussi une forme visuelle intéressante.
Dans le prochain article, on abordera un autre usage des données de Lexiflaire, avec un autre modèle : Word2Vec.
