CIRCA : la technologie d’Applied Semantics au coeur des Adwords et des Adsense de Google [2]

Dans cette deuxième partie, nous allons détailler les principes de fonctionnement de la technologie CIRCA. La plupart des informations données ici sont tirées du « white paper » que la société Applied Semantics avait placé sur son site pour promouvoir sa technologie. [1]

La plupart des méthodes utilisées n’ont rien de révolutionnaires : on les retrouve dans de nombreuses applications de linguistique, de traitement du langage, dans des versions parfois plus sophistiquées. Le vrai talent d’Applied Semantics est sans doute de tenir la « promesse » contenue dans son nom : savoir faire de la « sémantique appliquée » et introduire la sémantique dans les « business models ».

Vers la première partie : »d’Oingo à Applied Semantics »

De nombreux termes des sciences du langage et en particulier de sémantique sont utilisés dans cet article. Pour ceux qui ne sont pas familiers avec ce jargon scientifique, la plupart des termes sont reliés à leur définition dans Wikipédia. N’hésitez pas à cliquer sur le lien pour en savoir plus…

ARCHITECTURE DE L’ONTOLOGIE CIRCA [2]

Le coeur de CIRCA est son ontologie.

Une ontologie est un système structuré de concepts, qui décrit les relations entre ces concepts. Ces relations sont décrites dans un graphe, et peuvent être de nature sémantiques, ou des hiérarchies (logiques de composition ou d’héritage, au sens « programmation objet » du terme).

Les ontologies permettent de « classer » intelligemment et efficacement les éléments, et notamment les éléments du langage.

L’ontologie CIRCA travaille à partir de triplets de trois composants [3] :
- les formes(« tokens » : les diverses formes que prend un mot dans un syntagme)
- les sens ou concepts(« meanings »)
- les syntagmes (« terms » [4])

Chaque syntagme est associé à un ou plusieurs « sens ». Dans l’exemple ci-dessous, on voit mieux cette logique en triplet à l’oeuvre, et la manière dont l’ontologie CIRCA « enregistre » l’information sur un syntagme.


Le syntagme « porte un enfant » est composé de trois « formes » : « porte » « un » et « enfant ». Si l’on prend la forme « porte » isolément, il est impossible de savoir s’il s’agit d’une porte, ou d’une forme conjuguée du verbe porter. Il est clair que les deux mots n’ont pas le même sens… Si l’on ne bâtit une ontologie qu’avec des formes isolées, les cas « ambigus » sont trop nombreux, et il est impossible de leur associer un sens.

D’où l’intérêt de stocker des syntagmes (des groupes de formes), qui eux peuvent être plus facilement associés avec un ou plusieurs sens [5].

Ici d’ailleurs, le syntagme peut être relié à deux sens :
- porte un enfant = est enceinte
- porte un enfant = tient un enfant dans ses bras

Cette relation est stockée dans l’ontologie de deux manières différentes :
- directement, sous la forme d’une entrée de type dictionnaire (porte un enfant = est enceinte)
- indirectement, par sa place dans la hiérarchie de l’ontologie (porte un enfant est relié au thème « obstétrique » par exemple)

Les relations dans l’ontologie

CIRCA utilise onze type de relations différentes entre les concepts [6]

-synonymie (bateau/navire)/ antonymie (bien / mal)
- similarité (analogie : syntagme différent, même champ sémantique, connotations différentes)
-hyperonymie (« cheval » a une race « Arabe »)
- appartenance (« l’équipier » appartient à une « équipe »)
-métonymie (relation entre le tout et ses parties : la « maison » a un « toit »)
- substance (le « parquet » est en « bois »)
- production (« Microsoft Corporation » produit « Microsoft Access »)
- attribut (« passé » et « futur » sont des attributs de « temps »)
- causalité (« voyager » est la cause de « se déplacer »)
- succession (il faut « payer » après avoir « acheté »)
- liens connexes (« chien » et « collier » concepts proches mais non reliés par les autres relations)

Chaque relation stockée dans l’ontologie se voit complétée par une « note » indiquant la « force » de la relation. Par exemple « chien » est une catégorie d’ « animal de compagnie » ainsi qu’une espèce. Mais le lien est plus fort avec « animal de compagnie » qu’avec espèce.

Mais cette « note » n’est pas la seule information quantitative stockée dans l’ontologie. Plusieurs données statistiques sont également incluses [7] :
- la probabilité qu’un syntagme soit utilisé avec un sens donné
- les fréquences relatives des différents syntagmes et formes.
- la fréquence d’utilisation d’un groupe de formes en tant que syntagme
etc…

Par ailleurs, des données linguistiques sont également incluses :
- catégorie syntaxique des formes et des syntagmes (est-ce un verbe ou un adjectif…)
- les « flexions » possibles (formes conjuguées, indication du genre, du pluriel)

Comment bâtir et enrichir l’ontologie

Si l’on en croit Applied Semantics, leur ontologie a été bâtie à partir de Wordnet, enrichie par le travail « humain » de plusieurs linguistes, aidés par des outils permettant d’enrichir automatiquement le système.

Voici comment Gil Elbaz, le PDG de la société décrivait la technologie CIRCA dans EContentMag en 2002 :


Gil Elbaz
La technologie propriétaire de CIRCA se base sur une vaste ontologie comportant des millions de mots, de sens, et de relations conceptuelles avec d’autres sens dans le langage humain. Considérée comme étant la plus importante base de données de connaissange générale – avec plus de 1,2 millions de mots, un demi-million de concepts, et dix millions de relations, CIRCA relie des mots et des phrases à son ontologie, réalise sur eux une analyse linguistique, détermine leur sens, et évalue le degré d’importance de ces « sens », rendant ainsi les ordinateurs plus efficaces dans la gestion et la recherche d’informations.

« CIRCA a pour objectif de déterminer quel est le sujet abordé réellement dans un document », explique Elbaz.
« Contrairement à d’autres moteurs de recherche traditionnels, comme Verity, Google, ou AltaVista- qui recherchent une information en se basant sur une chaîne de caractères précise [entrée par l’utilisateur], CIRCA relie les mots du document avec les concepts présents dans l’ontologie. Une fois que nous avons une représentation du sujet abordé dans le document, nous pouvons le résumer et le classer dans une catégorie ».

La technique fondamentale étudie la co-occurence des « sens » pour détecter de nouvelles relations possibles qui peuvent permettre de choisir entre deux sens pour le même syntagme. Si l’on prend le mot Java, il peut signifier une danse, une ile d’Indonésie ou un langage de programmation. S’agissant du langage Java, il est sans doute déjà associé, dans l’ontologie, avec « classes » et « Javascript » et « programme » … Mais il n’est pas forcément associé avec le mot « clavier ». Pourtant, la co-occurrence entre « clavier » et « Java=langage » sera plus forte qu’avec l’île et la danse. Conclusion : l’étude des co-occurences permet de compléter les informations contenues dans l’ontologie, pour autoriser des desambiguations futures…

Ces informations sont issues de l’analyse du « contexte » d’utilisation des syntagmes. Plus le système absorbe de textes différentes, plus il « apprend » à reconnaître le sens de ces syntagmes…

UTILISATION DE L’ONTOLOGIE POUR ANALYSER UN TEXTE

Le plus intéressant à étudier, c’est de voir comment CIRCA parvient à analyser un texte et lui attribuer un « sens ». Le processus se déroule en trois étapes :
- un prétraitement qui permet de « passer le texte au moulin » et de le transformer en éléments utilisables par les programmes
- une phase de « désambiguation »
- et enfin, la phase de sélection d’un « sens » ou d’un thème pour le texte.

Pré-processing

La phase de prétraitement consiste à faire subir au texte quatre traitements successifs :
- « tokenizer » : découper le texte en éléments simples
- attribuer une catégorie syntaxique aux formes
- reconnaître les entités nommées
- isoler les syntagmes

Le « tokenizer »

Le traitement consiste à découper le texte en distinguant les « formes », (les mots) contenus dans le texte, et à reconnaître les phrases et à les baliser. Le « tokenizer » exploite également les informations contenues dans les balises html. Il identifie aussi les « formes » particulières, comme les nombres, et la ponctuation. Certaines données sont conservées comme la position relative d’un mot dans le texte, tandis que d’autres sont enlevées, comme les balises HTML inutiles.

Attribuer une catégorie syntaxique

Le système cherche ensuite à attribuer une catégorie syntaxique à chaque forme [8]. Ce traitement élimine une source possible d’ambiguité (« porte » est-il un substantif, ou une forme verbale conjuguée ?).

Reconnaître les entités nommées

Il s’agit ici, à l’aide d’expressions régulières et d’autres règles, d’identifier des séquences particulières : adresses email, url, numéros de téléphone, et dates. Des règles heuristiques permettent de reconnaître d’autres types d’ « entités nommées » : noms de personnes, de lieux, de sociétés.

Isoler les syntagmes

La dernière phase de prétraitement consiste à isoler les syntagmes et à les relier au(x) syntagme(s) correspondant dans l’ontologie.

Désambiguation du sens des mots

Le travail n’est pas terminé, car dans bien des cas, plusieurs hypothèses subsistent quand au sens à attribuer à un syntagme, et même, plusieurs découpages en syntagmes peuvent coexister. Par exemple, le syntagme « casser sa pipe » peut être pris comme une expression synonyme de « mourir ». Mais si « pépé a cassé sa pipe en écume », alors il vaut mieux traiter la séquence en trois syntagmes différents. C’est l’étude du contexte qui permet d’évaluer quel est la solution « probablement juste ».

Cette étude du contexte consiste notamment en l’étude des co-occurences entre formes et syntaxes dans le texte. [9]

Donner du sens

La phase précédente a permis de déterminer un « sens » pour chaque terme et chaque syntagme pris isolément… De nombreux outils linguistiques informatisés s’arrêtent là. Mais CIRCA a pour objectif de déterminer de quoi parle un texte donné, afin de pouvoir par exemple le classer dans une catégorie ou une autre…

JPEG - 11.1 ko
schéma de l’ontologie CIRCA

La tâche est délicate : il s’agit d’identifier dans un texte le ou les concepts les plus importants. L’astuce consiste à ne plus mesurer la coocurrence des syntagmes, mais celle des « sens », dans le texte, pour déterminer quels sont les « sens probables ». Ensuite, plus un sens est fréquent, plus il y’a de chances qu’ils soient importants…

A ce stade, la « structure » du texte produit des effets de bords qui parasitent les résultats. Il est fréquent qu’un texte avec un sens précis soit accompagné de « sections » sans rapport avec ce sens… Cela arrive fréquemment sur une page de brèves dans un magazine : si on prend la « page » comme un texte unique, en déterminer le sens va être difficile. Le problème est le même avec une page HTML : il est fréquent qu’un « article » voisine sur la page avec des textes et des éléments de navigation (menus) qui n’ont rien à voir avec le texte principal de la page.

« Attribuer un sens » passe donc par l’identification de ces régions différentes, et par la recherche d’un sens pour chaque région. Certaines régions différentes seront reconnues, selon des règles heuristiques, comme non pertinentes, et ignorées.

A la fin du processus, le document se voit attribuer une liste ordonnée des sens les plus probables pour son contenu… Ce qui autorise bien des applications pratiques !

CIRCA et Adsense

L’une des applications de CIRCA est bien sûr de pouvoir déterminer le « sens » d’une page web pour l’associer automatiquement à une liste de mots clés. Ce qui permet d’afficher des publicités ciblées sur ces pages : c’est le coeur du fonctionnement du système Adsense de Google.

Mais le système est complexe et mérite un nouvel article à lui tout seul…

Philippe YONNET

BIBLIOGRAPHIE ET LIENS UTILES

http://www.appliedsemantics.com/

Le « white paper » d’Applied Semantics sur CIRCA – sur le site google-watch.org

Présentation Powerpoint de la technologie CIRCA – document d’Applied Semantics

Présentation de CIRCA dans EContentMag
http://www.econtentmag.com/Articles/ArticleReader.aspx?ArticleID=985&IssueID=117

Présentation du produit « Auto-Categorizer dans Infotoday
http://www.infotoday.com/it/may02/news15.htm
http://www.infotoday.com/it/jan02/news10.htm


[1] Ce document n’est plus disponible depuis le rachat de la société par Google.

[2] CIRCA est un acronyme qui signifie : Conceptual Information Retrieval and Communication Architecture (architecture d’extraction d’information conceptuelle et de communication

[3] subtilement différents de ceux du web sémantique, notamment dans leur hiérarchie, on se méfiera donc des analogies

[4] on notera que les termes utilisés par Applied Semantics sont d’une imprécision scientifique étonnante. Il est vrai que les sciences de type sémantique, sémiologie etc… sont des traditions françaises, et qu’il existe donc une terminologie précise en français, mais pas en anglais. Mais les termes anglo-saxons utilisés ici ne sont pas non plus les termes consacrés utilisés dans la littérature anglo-saxonne sur le sujet.

[5] Tout l’art de créer une ontologie consiste d’ailleurs à choisir ces fameux syntagmes : un syntagme peut regrouper des syntagmes plus petits. Si l’on ne prend que les plus petits syntagmes inférieurs, l’ontologie est de taille minimale, mais restera faiblement pertinente. Si l’on prend les syntagmes supérieurs, la taille de l’ontologie et sa complexité explosent de manière exponentielle, par contre, sa pertinence peut devenir bien meilleure.

[6] On peut en définir d’autres, mais souvent les ontologies utilisent moins de types de relations. L’ontologie CIRCA est particulièrement riche de ce point de vue. Elle reprend en fait la classification de Wordnet

[7] C’est l’ajout de ces statistiques et poids qui représente une avancée de CIRCA par rapport à Wordnet

[8] L’outil en oeuvre ici est un transducteur d’états finis, qui s’appuie sur une série de règles à la manière d’un système expert : le système calcule, en fonction des statistiques contenues dans l’ontologie, la probabilité que la forme appartienne à telle ou telle catégorie, avant que des règles déterminent le choix.

Un transducteur à états finis est un dispositif algorithmique qui sait « reconnaître » des séquences de symboles dans un texte, leur attribuer un état, changer dynamiquement cet état, et produire un texte modifié en sortie. Les fonctions de recherche/remplacement des traitements de texte sont des « transducteurs à états finis » simples.

[9] la mesure de la co-occurrence des mots a des applications directes en référencement, et sera l’objet d’un article à venir. Il s’agit de mesurer la probabilité qu’un couple ou un n-uplet de mots apparaissent ensemble dans un texte. Pour un couple de mots la formule est simple : soit n1 et n2 le nombre de fois où les mots m1 et m2 apparaissent dans un corpus de textes donné, et n12 le nombre de fois où ils apparaissent ensemble dans un même texte. La mesure de la co-occurence est donnée par c=n12/(n1 + n2 – n12).
Certains résultats de l’étude des co-occurences en sémantique sont intuitifs, d’autres pas du tout, comme souvent avec les outils basés sur les probabilités