Génération de graphe sémantique

 

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

On va prendre chaque paire indice / réponse, les lemmatiser, les ajouter au graphe si les sommets correspondants n’existent pas encore, et créer un lien entre eux s’il n’existe pas déjà.

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

On pourrait aller plus loin : lorsqu’un lien relie deux mots avec des fréquences très différentes, il n’est pas inintéressant de garder deux poids distincts, un pour chaque direction — un poids in et un poids out. Cela revient à ne diviser que par 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.

Lemmatisation

Première étape incontournable : la lemmatisation.

Lexiflaire, c’est plus de 15 millions de manches jouées.
Chaque manche contient en moyenne 2,3 indices et 2,3 propositions.

Ça nous fait environ 70 millions de tokens à traiter.
(un token, c’est une unité de texte — en gros, un mot.)

Mais il y a des doublons, beaucoup...

Prenons un exemple :

• "animal" apparaît 170 000 fois

• "animaux" : 30 000 fois

• "animale" (forme adjectivale féminine) : 2 400 fois

Est-ce vraiment utile de conserver toutes ces variantes comme des mots différents ?
Dans la majorité des traitements qu’on souhaite faire… non. Ce qu’on veut, c’est regrouper toutes ces formes sous une seule entrée logique : le lemme.

Dit autrement :

• Le lemme d’un nom, c’est sa forme au singulier.

• Le lemme d’un adjectif, sa forme au masculin singulier.

• Le lemme d’un verbe, son infinitif.

L’objectif : regrouper ce qui a le même sens, même si la forme change selon le genre, le nombre ou le temps.

Sans lemmatisation, le corpus contient environ 200 000 formes différentes.
Beaucoup ne sont que les déclinaison d'un même mot : pluriels, conjugaisons, féminins, fautes de frappe…

Après lemmatisation, ce chiffre tombe à environ 35 000 lemmes.
Pour cela, j’utilise Morphalou, développé par le CNRTL, qui référence plus de 540 000 formes fléchies correspondant à environ 68 000 lemmes.

Ambiguïtés grammaticales

Un même mot peut parfois dépendre de plusieurs lemmes.
Par exemple, minerais : est-ce une conjugaison du verbe miner, ou le pluriel du nom minerai ?

Une première règle simple s’applique :
-Si un mot est identique à un lemme, on choisit ce lemme-là.
Sinon, on hiérarchise les catégories grammaticales selon l’ordre :
nom > verbe > adjectif.

Et quand le mot est mal orthographié ?

Mais évidemment, pour pouvoir lemmatiser un mot, encore faut-il qu’il soit correctement orthographié. Les erreurs et fautes de frappe sont fréquentes — surtout dans un jeu de rapidité comme Lexiflaire, où on n’a pas toujours le temps de s’embêter avec les accents.

La correction orthographique, comme celle qu’on retrouve dans un traitement de texte ou un clavier de smartphone, existe… mais comment ça fonctionne ?

Elle s’appuie sur une structure appelée DAWG (Directed Acyclic Word Graph), qui permet de rechercher de manière « floue » dans un dictionnaire, grâce à la distance de Levenshtein.

Cette distance mesure le nombre minimal d’opérations (insertion, suppression, substitution) nécessaires pour transformer un mot en un autre. Par exemple, si l’on saisit « flimme », l’algorithme pourra proposer « flemme » ou « flamme », qui ne sont qu’à une distance de 1.

Dans notre cadre, ce mécanisme permet de limiter la perte de données liée aux fautes d’orthographe, même si environ 15 % des mots restent non corrigés, faute de correspondance claire.

Exemples concrets :

• "minerai" → c’est déjà un lemme, donc on le garde tel quel.

• "animaux" → correspond uniquement au lemme "animal" → on garde "animal".

• "minerais" → peut être le pluriel du nom "minerai" ou une forme du verbe "miner" → on donne la priorité au nom, donc on garde "minerai".

• "fllamme" → inconnu tel quel, mais il existe une seule correspondance à une distance de Levenshtein de 1 : "flamme", qui est un lemme → on garde "flamme".

• "flimme" → inconnu, deux correspondances à distance 1 : "flemme" et "flamme" → ambigu, on ignore ce mot.

Conclusion

Cette étape de lemmatisation constitue la base de tous les traitements à venir.
Le prochain article portera sans doute sur la création de graphes sémantiques, rendue possible par cette normalisation.

Reprise du blog : traitement des données de Lexiflaire

Le blog reprend du service, mais cette fois pour parler du traitement des données de Lexiflaire.

En 10 ans, plus de 15 millions de manches ont été jouées. Cela représente une masse de données considérable, pleine d’indices, de réponses... de jus de cerveau.

Désormais, ce blog suivra l'exploitation de ces données, en s’appuyant sur les techniques modernes de traitement du langage naturel. L’objectif : mieux comprendre les dynamiques du jeu, entraîner des modèles, et peut-être, à terme, donner naissance à un nouveau jeu de mots… ou à une version enrichie de Lexiflaire.

À suivre !