Saïd Radhouani
email: said.radhouani@imag.frjean-pierre.chevallet@imag.fr

Jean-Pierre Chevallet

Utiliser les liens pour adapter les moteurs de recherche aux spécificités du WEB

Keywords: Information, Représentation, Accès et Traitement Intelligent, WEB, Liens Hypertextes

Le WEB, hypertexte mondial, nécessite l'utilisation de moteurs de recherche pour retrouver l'information. Actuellement la notion de page WEB est communément utilisée comme atome d'information retourné à l'utilisateur. Les liens entre pages sont très peu utilisés pour améliorer la qualité des réponses. Nous proposons brièvement une utilisation simple des liens dans les pages WEB, et un niveau d'indexation indépendant de la page WEB, considérée comme granularité physique.

INTRODUCTION

Depuis son apparition, le WEB n'a cessé de progresser pour devenir une source formidable d'informations immédiatement disponibles. Toutefois, l'accès à l'information est devenu de plus en plus difficile car l'internaute est perdu dans la masse disponible. Devant la richesse du WEB en terme de pages et de liens, la navigation est évidement très limitée pour rechercher des informations et l'accès à l'information basé sur une requête semble plus efficace. En effet, les moteurs de recherche sur le WEB sont une aide inestimable pour rechercher une information. Actuellement, ils fonctionnent sur le principe qu'une page HTML ou tout autre fichier document, est l'atome d'information que l'internaute recherche. Ils tiennent peu compte du fait que le WEB est avant tout un système hypermédia issu des hypertextes. L'indexation se réalise donc au niveau de granularité de la page HTML et le réseau de liens entre les pages est peu exploité pour améliorer la qualité de la recherche d'information. Pourtant, il est clair que le découpage physique en page n'est pas forcément lié au contenu de la page. En effet, on trouve sur le WEB, des pages de tailles très différentes, certaines même contiennent l'équivalent d'un ouvrage complet.

Les moteurs de recherche du web sont basés sur des modèles booléens ou vectoriels de RI qui ont été développés pour des documents atomiques. Nous mettons en doute l'adaptation de ces modèles aux spécificités du WEB, en particulier pour des recherches plus précises au niveau des réponses. La question que nous voulons poser à travers ce document concerne le passage des moteurs de recherche actuels orientés plutôt vers le rappel, à des moteurs de recherche plus orientés vers la précision en tenant compte de la structure hypertextuelle de cet espace d'information.

Nous évoquons d'abord quelques méthodes d'utilisations de liens pour la recherche d'information. Ensuite, nous présentons quelques travaux d'évaluation des méthodes précitées, avant de discuter l'état actuel des travaux sur les liens. Nous concluons par une proposition brève pour l'utilisation des liens dans les pages WEB.

L'APPARITION DU WEB

En 1989, deux ingénieurs du CERN 1 de Genève, Timothy Berners-Lee et Robert Cailliau, eurent l'idée d'utiliser les liens hypertextes pour permettre la consultation simultanée de tous les sites serveurs d'Internet : par convention, cette date marque la naissance du World Wide Web. En 2000 existaient déjà 2 milliards de pages WEB, ayant chacune un nombre considérable de liens hypertextes. Le lien hypertexte est ainsi devenu le moyen principal pour naviguer sur Internet. Les documents entre lesquels on peut naviguer grâce aux liens sont écrits en langage HTML.

Nous pouvons donc considérer que le WEB est un gigantesque hypermédia issu des systèmes hypertextes. La richesse d'un document hypertexte réside non seulement dans son contenu informationnel mais également dans la richesse de ses liens et c'est ce qui complexifie l'élaboration d'un modèle bien précis pour l'hypertexte [Devlin, 1991]. Dans [Park, 1998], une étude a été menée afin de dégager les propriétés structurelles de l'hypertexte et de la définir dans un langage formel : l'hypertexte étant non structuré vu son aspect non linéaire présente un sérieux problème lors de la navigation [Aleese, 1990].

.

Recherche d'information sur le WEB

1 Centre européen pour la recherche nucléaire Les besoins en RI sur le WEB sont certainement très variés, comme le sont les types d'informations disponibles (cf. [START_REF] Prime | [END_REF]). Ces besoins ne sont pas pris en compte, tout comme ne sont pas pris en compte les types de pages différents. De fait, la plupart des moteurs considèrent que le WEB est un ensemble de documents atomiques et indépendants, dont la granularité est celle d'une page HTML. Ils ne tiennent pas compte du fait que le WEB est avant tout un ensemble de documents liés par des liens hypertextes et que les pages HTML indexées indépendamment les unes des autres perdent leur contexte. Pour ces raisons, différentes méthodes ont été développées afin d'utiliser les liens dans le processus de RI sur le WEB.

UTILISATION DES LIENS POUR LA RI

Dans la suite, nous évoquons quatre approches d'utilisation des liens pour la RI. Nous citons, également, quelques travaux qui ont concrétisé ces approches avec éventuellement certaines modifications.

.1 Le PageRank [START_REF] Brin | [END_REF] Cette approche est basée sur la notion de propagation de popularité. Le principe est d'évaluer l'importance d'une page en fonction de chaque page pointant vers elle. La propagation met en avant les pages qui jouent un rôle particulier dans le réseau des liens, avec l'hypothèse : "une page référencée par un grand nombre de pages est une bonne page". Cette mesure est une distribution de probabilité sur les pages. Elle mesure en fait la probabilité PR pour un internaute navigant au hasard, d'atteindre une page donnée P. Cette probabilité est d'autant plus forte que le nombre de pages qui réfèrent P est important. PR est donc fonction de la somme des probabilités des pages qui référencent P. Il faut aussi tenir compte du fait que les pages qui référencent P ont d'autres liens sortant vers d'autres pages que P. Il faut alors diviser cette probabilité par le nombre C de liens sortant des pages qui référencent P. Finalement, il faut tenir compte du fait qu'un internaute peut arriver sur une page quelconque sans suivre de liens (à partir de ses signets par exemple).

La formule proposée [START_REF] Brin | [END_REF] tient ainsi compte de la probabilité d de suivre effectivement les liens. La probabilité d'arriver à la page P sans suivre de liens est donc de (1-d). La formule de calcul du PageRank est alors la suivante :

PR(P) = (1-d) + d[(PR(P 1 )/C(P 1 ) + …. + (PR(P m )/C(P m ))]
(1) Avec d est une probabilité constante, C(P j ) = nombre de liens sortant de la page P j .

Cette mesure a tendance à mettre en valeur les pages qui sont référencées par des pages à forte probabilité. On remarque que la formule est récursive : la valeur du PageRank (score) d'une page P, est calculée par un algorithme itératif. Initialement, toutes les pages sont équiprobables, leur valeur de PageRank est alors égale à 1/N avec N est le nombre de documents de la collection. Un cycle d'itération propage les probabilités sur les liens. L'algorithme s'arrête théoriquement lorsqu'une nouvelle itération ne produit plus de modifications dans le graphe des valeurs de PR.

Ce calcul se fait lors de la phase d'indexation (indépendamment des requêtes). Cette valeur peut alors être utilisée à l'interrogation pour modifier l'ordre de pertinence des pages évaluées par le seul critère de comparaison du contenu. L'approche suivante tient compte de la requête dans la propagation de la pertinence sur les liens.

.2 L'approche de propagation de pertinence [START_REF] Crestani | [END_REF][START_REF] Savoy | [END_REF] Le principe de cette approche consiste à propager des valeurs de similarité de documents par rapport à une requête avec l'hypothèse suivante : "un document référencé par un grand nombre de documents pertinents est un bon document". La typologie du graphe des liens entre les pages est ici prise en compte au moment du calcul de la valeur de pertinence (Relevance Status Value RSV) des documents. Elle est alors fonction de la valeur de pertinence du document D i par rapport à la requête Q, mais elle va aussi dépendre des valeurs de pertinence des documents liés au document D i par rapport à la requête. Ainsi la valeur de pertinence finale notée RSV fin se calcule comme suit :

Q) (Di, RSV fin = Q) (Di, 0 RSV + ∑ = - ⋅ k j fin RSV 1 1 Q) (Dj, λ .
(2)

Avec : D i : un document. D j : les documents liés à D i .

Q : une requête. λ : une constante destinée à atténuer la propagation. K : le nombre de document reliés au document D j .

RSV fin : la pertinence finale du document Di par rapport à la requête Q. RSV 0 : la pertinence initiale du document Di basée sur le contenu. RSV fin-1 : est la pertinence du document Dj par rapport à la requête Q lors de l'avant dernière itération.

La première étape consiste à calculer la similarité entre une requête donnée et les documents de la collection. Cette valeur est notée RSV 0 (D i ,Q). La deuxième étape consiste à propager cette valeur dans le réseau de documents à travers un certain nombre de cycles en utilisant des facteurs de propagations. A chaque cycle, la pertinence d'un document change en fonction de la pertinence des documents voisins. Cette propagation peut être aussi mise en oeuvre en propageant une pertinence binaire, c'est à dire, une valeur qui est à 1 si le document est jugé pertinent, et à 0 s'il ne l'est pas.

.3 Le système probabiliste d'argumentation (PAS) [START_REF] Picard | [END_REF] Dans cette approche, au lieu de propager la valeur de similarité d'un document par rapport à une requête, on propage la probabilité qu'il soit pertinent. La première étape consiste à calculer la probabilité de pertinence d'un document D i notée P(D i |rank). A la deuxième étape, cette valeur de probabilité de pertinence est modifiée en fonction des valeurs de probabilités des documents voisins au document D i .

La contribution d'un document D j lié à D i est égale à P(D j |rank).P(Link) au lieu de utilisé dans l'approche de propagation de pertinence (cf. .3). (3) Dans [START_REF] Savoy | [END_REF], cette approche a été mise en oeuvre en utilisant seulement les sources2 d'évidence importantes en choisissant les meilleurs documents entrant D in et les meilleurs sortant D out au lieu d'utiliser tous les documents voisins à un document D i.

∑ = ⋅ k j i RSV 1 Q) (Dj,
.4 Algorithme de Kleinberg (HITS) [Kleinberg, 1998] Cette approche consiste à calculer la popularité (Hub) et l'autorité (Authority) d'un document et ce pour classer les documents résultats par rapport à une requête. L'hypothèse est : "Un document qui pointe vers beaucoup de bonnes Authorities est un bon Hub, et un document pointé par beaucoup de bons Hubs est une bonne Authority". Le principe est de calculer le nombre de documents qui pointent vers un document D i et celui des documents que D i pointe. Les Hubs (H) et les Authorities (A) sont calculés de la façon suivante :

) ( ) ( ) ( 1 D H D A j parent c i c D D i j ∑ ∈ + = . ( 4
) ) ( ) ( ) ( 1 D A D H j fils c i c D D j i ∑ ∈ + = .
(5)

Avec : c+1 : le nombre d'itérations.

Parent(D i ) : l'ensemble des documents qui pointent vers le document D i . Fils(D j ) : l'ensemble des documents que D i pointe.

Les Hubs et les Authorities sont initialisés à 1. Durant c+1 itérations, les documents sont répartis dans deux listes, l'une classée selon les Hub, l'autre selon les Authorities. La liste finale des documents classés peut être l'intersection de ces deux listes.

.

Autres utilisations des liens pour la RI

Les approches présentées ci-dessus ont été concrétisées dans des travaux avec éventuellement des modifications. Par exemple, le moteur de recherche google [START_REF] Brin | [END_REF] utilise le principe de PageRank : tout lien pointant de la page A à la page B est considéré comme un "vote" de la page A en faveur de la page B. Il procède également à une analyse de la page qui contient le lien. Les liens présents dans des pages jugées importantes ont plus de "poids", et contribuent ainsi à " élire" d'autres pages [Google].

Au lieu d'utiliser tous les liens entrants et sortants d'une page, [START_REF] Gurrin | [END_REF] a identifié deux types de liens, les liens structurels et les liens fonctionnels et utilise seulement ce dernier type pour la propagation de pertinence. Il a séparé les liens du web en deux types larges basés sur leur fonctions voulues quand ils sont créés : les liens structurels qui aident l'utilisateur à naviguer à l'intérieur d'un site et les liens fonctionnels qui peuvent être vus essentiellement comme des liens entre un document source et un document cible qui possèdent une similarité dans le contenu.

.6 Synthèse L'utilisation des liens pour la RI sur le WEB a été étudiée dans plusieurs travaux. Nous pouvons classer ces travaux en deux classes : l'utilisation des liens lors de la phase d'indexation (le PageRank), l'utilisation des liens lors de la phase d'interrogation (le système PAS, l'algorithme de Kleinberg, et l'approche de propagation de pertinence ). La différence entre ces deux classes est que lors de la phase d'indexation, les calculs se font indépendamment de la requête utilisateur, tandis que lors de l'interrogation, les calculs dépendent de la requête.

Dans les approches présentées ci-dessus, nous remarquons que l'utilisation des liens est utilisée comme une simple surcouche lors de l'indexation (respectivement lors de l'interrogation). C'est à dire, l'utilisation des liens est faite après avoir indexé (respectivement interrogé) les documents en se basant sur les méthodes basées sur le contenu. L'utilisation des liens sert, dans ces cas, à classer les documents résultats par rapport à une requête, et les index des documents ne sont plus modifiés une fois qu'ils sont construits par les méthodes classiques 3 . Ces raisons ont poussé Aguiar à s'interroger sur l'utilisation de l'information externe à un noeud (page) qui peut être utile lors de son indexation. Il pense que le fait d'indexer un noeud à partir de son seul contenu, risque d'avoir un index qui ne révèle pas précisément l'information véhiculée par ce noeud. Ainsi il propose de retrouver de l'information qui donne un contexte au contenu d'un noeud et la prendre en compte lors de l'indexation et lors de l'interrogation [Aguiar, 2002].

Nous avançons que l'échec de ces approches repose sur le fait de manipuler tous les liens (respectivement toutes les pages) de la même manière sans aucune distinction. Nous pensons qu'il ne faut pas utiliser les liens sans avoir analysé leur nature. Il faut comprendre leur rôle, en terme de description de l'information, avant de les utiliser. Aussi, il ne faut pas considérer systématiquement la page HTML comme étant la plus petite granularité d'information. Il faut comprendre la nature de chaque page ainsi que son rôle avant de l'utiliser. De manière évidente, il existe différents types de page : une page index est différente d'une page de contenu ou encore, une page de publicité est différente d'une page professionnelle, etc.

ÉVALUATION

Plusieurs travaux ont été menés sur l'utilisation des liens pour la RI sur le WEB mais, jusqu'à maintenant de nombreuses expériences ont montré qu'il n'y a pas de gain significatif par rapport aux méthodes de recherche basées seulement sur le contenu [START_REF] Savoy | [END_REF], [START_REF] Savoy | [END_REF], [START_REF] Gao | [END_REF].

Le système PAS (cf. .4) a été testé dans [START_REF] Savoy | [END_REF] en utilisant tous les documents voisins à un document D i . Dans [START_REF] Savoy | [END_REF], seuls les meilleurs documents entrant D in et les meilleurs sortant D out ont été utilisés. Dans ces deux travaux, les résultas ont été inférieurs aux résultats des méthodes de recherche classiques basées sur le contenu.

Pour l'approche de propagation, [START_REF] Savoy | [END_REF] ont utilisé tous les liens entrant et sortant des documents. Dans [START_REF] Savoy | [END_REF], les liens ont été sélectionnés avant de faire la propagation. Seuls les liens qui sortent des documents les mieux classés par rapport à la requête sont utilisés. Dans ces deux travaux, les résultats sont nettement inférieurs à ceux des méthodes classiques.

Pour l'algorithme de Kleinberg et la méthode de PageRank, les résultats sont médiocres [START_REF] Savoy | [END_REF]. A travers leurs travaux d'évaluation, les auteurs ont pu conclure que les méthodes de recherche basées sur les liens n'apportent pas des améliorations [START_REF] Savoy | [END_REF]. Ils se posent donc les questions suivantes : -Existe-t-il d'autres travaux qui peuvent confirmer ces résultats ? -Est-ce qu'on a bien choisi les valeurs des paramètres ? La même conclusion a été tirée du travail de sept autres chercheurs bien qu'ils aient combiné les méthodes basées sur le contenu avec les méthodes basées sur les liens [START_REF] Gao | [END_REF].

Toutefois, dans [START_REF] Craswell | [END_REF], les résultats issus des méthodes basées sur les liens ont été bien meilleurs que celles des méthodes basées sur le contenu. Le cas traité dans ce travail est la recherche de site et non d'information. Le résultat d'une requête est une URL, en général, la home page d'un site. Les auteurs ont comparé l'efficacité de deux méthodes de classement dans la recherche de site : -La méthode classique de classement basée sur le contenu. -La méthode de classement basée sur les liens (texte de l'ancre). Dans le cas de l'utilisation du texte de l'ancre seulement, pour chaque page p, ils construisent un document d'ancre qui contient tous les textes des ancres des liens qui pointent vers p. Ce document représente la description de la page p. Dans le cas basé sur le contenu, une indexation classique a été utilisée.

Dans leurs expérimentations, les auteurs ont utilisé 3 collections différentes de document web. Pour chaque collection, 100 requêtes ont été fixées. Les deux méthodes utilisent le même système de recherche et le même algorithme de classement. La différence réside dans le document index pour chaque page. Dans le cas de la méthode classique, un index classique a été utilisé. Tandis que dans le cas de la méthode basée sur les ancres, l'index c'est le document ancre. Les résultats de la méthode de classement basée sur les ancres sont deux fois meilleurs que ceux de la méthode classique. Donc l'information des ancres est plus utile que celle du contenu, et ce dans le processus de recherche de site.

DISCUSSION DES INSUFFISANCES DES MÉTHODES ACTUELLES

Les méthodes, qui ont été proposées pour extraire de l'information à partir des liens de navigation, traitent le WEB comme un graphe orienté dont les noeuds sont les pages HTML, et les arcs sont les liens de navigation entre les pages. Elles ne font pas de distinction entre les pages ou entre les liens. Pourtant il y a une différence entre une page contenant un livre et une page contenant quelques paragraphes, entre une page de contenu textuel et une page d'index ne contenant que des liens, entre une page personnelle et une page professionnelle, etc. De même pour les liens, il y a une différence entre un lien intra-page et un lien inter-page, entre un lien de publicité et un lien vers du texte, etc. 3 Pour l'indexation, les méthodes classiques indexent les documents seulement en se basant sur le contenu textuel. Pour l'interrogation, les méthodes classiques mesurent la correspondance entre les termes de la requête et les termes du document atomique.

Dans la suite, nous détaillons les insuffisances des méthodes existantes en présentant quelques limites des moteurs de recherche existants.

.

Limites des moteurs de recherche actuels

Les moteurs de recherche actuels se basent sur l'hypothèse que la plus petite granularité d'information recherchée par l'internaute est une page HTML. Pour cette raison, l'indexation se fait souvent au niveau de la page HTML d'une manière atomique et indépendante. Dans la réalité, cette hypothèse est souvent mise en échec. Par exemple, si les informations recherchées se trouvent dans une page 4 qui contient, en supplément des informations pertinentes, d'autres informations non pertinentes, l'utilisateur risque de devoir rechercher par lui même l'information qu'il recherche en parcourant le document proposé par le système. Pour rendre compte de cet état de fait, nous proposons une nouvelle mesure de qualité des résultats d'un SRI basé sur la densité de bonnes "informations" à l'intérieur d'un document fournit en réponse à une requête. Nous définissons la précision informationnelle comme le rapport entre le nombre d'informations pertinentes présentes dans le document et le nombre total d'informations que contient ce document. Par symétrie nous proposons la notion de rappel informationnel, comme le rapport entre le nombre d'informations présentes dans un document et le nombre d'informations pertinentes dans le corpus. Avec ces définitions, un document possède une qualité intrinsèque mesurée par ces deux facteurs : un document à forte précision informationnelle aura tendance à ne contenir que des informations pertinentes. Un document à fort rappel informationnel aura lui tendance à contenir à lui seul toute l'information pertinente disponible.

..1 L'atome de la page HTML : source de précision informationnelle faible

Dans un processus de RI, si le moteur de recherche retourne une page contenant tout un livre pour un utilisateur qui recherche juste une définition, le résultat est de faible précision informationnelle (donc bruité). Donc la notion de page HTML comme élément atomique d'une réponse de SRI n'est pas un bon choix. En fait, ce n'est pour nous qu'une simple contrainte physique. Pour cette raison, nous jugeons utile de se détacher de cette contrainte physique pour redéfinir la notion de "document" sur le WEB. Ainsi nous proposons de la manipuler avec plus de finesse en s'intéressant plus à sa structure logique interne.

..2 La page HTML indépendante : source de rappel informationnel faible

Lorsque nous indexons des pages HTML indépendamment les unes des autres, le résultat de la recherche est toujours une page indépendante. Par conséquent, si les informations sont dispersées dans plusieurs pages (ce qui est le cas fréquent), il y aura un silence dans le résultat. Le moteur de recherche ne va pas fournir toutes les informations, demandées par l'utilisateur, dans un seul document. Donc la contrainte d'une page HTML indépendante devient une source d'un rappel informationnel faible. L'hypothèse que la page HTML ou tout autre fichier document, est l'atome d'information que l'internaute recherche, est prise encore une fois à l'échec. Pour éviter le silence et fournir à l'utilisateur toutes les informations qu'il cherche, nous pensons que l'indexation ne doit plus se réaliser au niveau de granularité de la page HTML, et que le réseau de liens doit être exploité pour améliorer la qualité de la RI. Les pages doivent être indexées en fonction de leurs liens pour quelles ne perdent pas leurs contextes. Avant de pouvoir utiliser les liens il nous faudra les analyser car, comme nous allons voir dans la section suivante, les liens hypertextes sont typés implicitement et n'ont pas tous le même rôle.

LES LIENS SUR LE WEB SONT TYPÉS IMPLICITEMENT

Implicitement, il y a différents types de liens. Sémantiquement, les auteurs incluent parfois implicitement le type pour exprimer leurs intentions et ce par la description, dans le texte, de ce qui est pointé par le lien [Allan, 1996]. Nous trouvons, par exemple, "pour voir la définition cliquer ici" ou "pour voir les résultats cliquer ici", etc. Syntaxiquement, il y a les liens inter-pages (liens entre les pages dans le même site WEB), les liens intra-pages (liens entre les paragraphes dans la même page), les liens externes au site WEB, les liens de publicités, etc. Nous trouvons également des liens dont le but est de guider le lecteur dans sa navigation, par exemple, "haut de page" ou "page précédente", etc.

Nous pouvons donc conclure qu'il existe différents types de liens ou encore différentes raisons de créer les liens. Il faut les analyser et en fonction de leurs rôles, les utiliser dans le processus de RI.

Actuellement, les liens contiennent des informations qui sont encore cachées et qu'il faudrait expliciter pour les utiliser lors du processus de RI. Le texte de l'ancre de la page source contient parfois une description sur la page cible. Le contexte dans lequel l'ancre apparaît et les étiquettes qui, structurellement, précèdent la section là où le lien apparaît, contiennent des informations sur la pages cible [START_REF] Fürnkranz | [END_REF]. Syntaxiquement, l'analyse comparative des URLs source et destination contient aussi des informations.

SOLUTION PROPOSÉE

Comme solution nous proposons d'utiliser une nouvelle granularité d'information au lieu de la page atomique, par exemple, le paragraphe. Nous indexons les pages en fonction des liens entre elles pour qu'elles ne perdrent pas leur contexte. Comme réponse pertinente, nous proposons un chemin de lecture qui est un document virtuel formé de paragraphes dispersés dans une ou plusieurs pages. Ce document peut contenir le maximum d'information pertinente pour remplir le critère de rappel informationnel et éviter le silence, il peut aussi contenir le minimum d'information non pertinente, pour remplir le critère de précision informationnelle et éviter le bruit. 4 Bien sûr une page de grande taille Ainsi nous allons manipuler les sites WEB comme étant un ensemble de page inter-reliées contenant des information complémentaires. Nous allons essayer de regrouper ces informations dans un document en utilisant les liens typés et une nouvelle granularité. Ce document peut être une réponse contenant le maximum d'information susceptibles d'être pertinentes par rapport à une requête.

Les questions que nous posons donc sont : comment extraire les types de liens ? Quel(s) type(s) utiliser lors du processus de RI ? Comment se détacher de la notion physique de la page HTML ? Quelle granularité d'information utiliser ? Comment l'extraire ? Comment prendre en compte les informations dispersées ? et enfin, comment intégrer ces nouveaux concepts dans un modèle de RI, et plus précisément lors de la phase d'indexation ?

CONCLUSION

A travers ce papier, nous avons présenté quatre approches d'utilisation des liens pour la RI sur le WEB. Des expérimentations sur ces méthodes ont montré qu'il n'y a pas un gain significatif par rapport aux méthodes basées sur le contenu textuel seulement. Toutefois, de bons résultats ont été atteints dans un processus de recherche de site. Les approches actuelles utilisent le contenu textuel pour la recherche de document et les liens ne sont utilisés que pour la classification des pages. Ces approches sont utilisées comme des surcouches aux méthodes de RI classiques. Nous pensons aller beaucoup plus loin, en retenant les solutions existantes basées sur le texte et en les combinant avec de nouvelles solutions basées sur les liens qui représentent l'une des spécificités du WEB. De nouvelles pistes ont été ouvertes comme celle de l'indexation des chemins de lecture [Gery, 2002]. Il reste donc à prouver les potentialités des liens cachées pour adapter les moteurs de recherche actuels aux spécificités du WEB.

λ

  La probabilité d'un document D i est multipliée par les probabilités des liens entrants noté P(Link in ) et des liens sortants P(Link out ). Le degré de support d'un document noté DSP est alors calculé comme suit : DSP(D i ) = 1 -(1-P(D i | rank)) * [1 -P(D in | rank) * P(link in )] * [1 -P(D out | rank) * P(link out )].

  Traditionnellement, le processus de RI consiste à retrouver, à partir d'une collection de documents, les documents qui correspondent le mieux à la requête utilisateur. Dans les modèles les plus simples, une requête est formée par un ensemble de mots clés, et le Système de Recherche d'Information (SRI) doit trouver les documents qui contiennent ces mots.Avec l'apparition du WEB, les documents disponibles sont devenus très importants. Cette collection a de nouvelles caractéristiques : les données sont hétérogènes et distribuées sur plusieurs sites, de nouveaux médias autre que le texte sont accessibles (image, vidéo, son.), et les documents sont liés par des liens hypertextes. Ces nouvelles caractéristiques exigent de nouveaux critères de pertinence d'un document par rapport à une requête. En particulier l'information disponible dans la collection ne se résume plus au contenu textuel, et les traitements d'extraction des index doivent tenir compte de ces aspects multimédias. La pertinence, basée sur la correspondance entre les mots clés de la requête et le texte du document, est insuffisante. Il faut noter aussi qu'il est en général difficile pour l'utilisateur, de traduire un besoin d'information par une requête : il doit s'adapter à un langage artificiel d'interrogation, même s'il est très simple (quelques opérateurs). Il doit également se faire une image mentale (parfois fausse) sur comment le système produit ses résultats avec une série de mots composés par quelques opérateurs.

Les documents qui ont les meilleurs valeurs de probabilité de pertinence.


Leïla Kefi
email: leila.kefi@imag.fr

Catherine Berrut
email: catherine.berrut@imag.fr

Eric Gaussier
email: eric.gaussier@xrce.xerox.com

Modèle d'indexation de données peu symboliques dans des documents structurés : L'exemple du graphique dans un corpus de documents techniques

Keywords: indexation, documents structurés, donnée peu symbolique, graphique, contexte professionnel INdexation, structured documents, weakly symbolic data, graphics, professional context

Cet article s'intéresse à l'indexation des données ayant une sémantique pauvre dans des documents structurés. Le but est d'exploiter le contenu des données symboliques avoisinantes afin d'en extraire les fragments adéquats pour compléter l'indexation de la donnée non symbolique. Cette approche a été abordée dans le cadre concret d'une application dans un contexte professionnel : indexer les graphiques des documents techniques en exploitant le texte qui les accompagne. Cette indexation est articulée autour d'un modèle de représentation des graphiques tenant compte de la finalité de leur utilisation et du professionnalisme de leurs usagers, et d'un modèle d'extraction des termes d'indexation à partir du texte du document technique.

ABSTRACT. This paper deals with data with little semantics in structured documents. The aim is to exploit symbolic data in order to extract the adequate fragments to complete the nonsymbolic data indexation. This approach has been studied in a concrete application frame that has a professional context: indexing graphics in technical documentation exploiting the textual context in which they appear. This indexing is articulated around a representation model for graphics that takes into account their use and their professional users and an extraction model of the indexing terms from the text of technical documentation.

Introduction

Dans les systèmes de recherche d'information traditionnels, la recherche se fait sur le document en tant qu'entité indivisible. Lorsque le système manipule des documents structurés, ces derniers sont organisés selon une certaine hiérarchie, formant alors une arborescence de blocs, éventuellement un graphe. Un article sera, par exemple, composé d'un titre, d'une introduction, d'un certain nombre de sections, elles-mêmes composées de paragraphes et d'une conclusion. Selon le besoin de l'utilisateur, l'un de ces blocs peut représenter une réponse plus pertinente à sa requête que le document en entier. Il faut donc que les systèmes de recherche d'information puissent donner, en réponse à une requête, une partie d'un document, voire une reconstitution personnalisée de ce document.

Les blocs formant le document structuré, loin d'être indépendants, sont reliés entre eux par des relations qui permettent de donner au document une intégrité sémantique. Certaines recherches ont tenu compte de cette dépendance dans le but d'enrichir l'indexation d'un bloc par l'ajout des index des blocs avoisinants ou supérieurs hiérarchiquement (la notion de portée, par exemple).

Plus particulièrement, dans les documents structurés multimédia, cette utilisation du contenu sémantique des blocs avoisinants pour enrichir l'indexation d'un bloc non textuel est nécessaire. En effet, certains blocs, comme les images, manquent d'un langage permettant d'en exprimer la sémantique. Et même si ces blocs contiennent en eux-mêmes des informations permettant leur description, celle-ci reste pauvre sémantiquement et ne permet pas de représenter les données en question de façon suffisante et par conséquent de les retrouver efficacement.

Dans les approches actuelles, l'index d'un bloc sans sémantique est considéré comme étant fonction de l'ensemble des descripteurs des blocs avoisinants. Nous désirons aller au-delà de cette approche et considérer l'indexation du bloc sans sémantique comme étant fonction de certains fragments extraits des blocs alentours, l'extraction dépendant du bloc sans sémantique. Par conséquent, l'indexation de ce bloc tiendra de ce qui fait sens pour lui et non plus de ce qui fait sens autour de lui dans les blocs alentours. Son indexation dépendra alors de sa nature et de ce que l'on peut éventuellement en savoir, voire en extraire.

Nous avons souhaité aborder cette approche, dans une première étape, dans le cadre concret d'une application. Nous avons choisi l'usage des documents techniques de type manuels d'utilisation (des descriptions d'imprimantes). Ce choix a été, entre autres, motivé par le contexte professionnel dans lequel se situe cette application. Dans une telle application, l'usager et la finalité d'utilisation des documents nécessitent que le système réponde avec précision aux attentes de l'utilisateur. Ces aspects concernant l'usager, l'usage et la précision, nous ont semblé intéressants à considérer dans notre étude.

Dans les documents techniques, nous nous sommes plus particulièrement orientés vers le média graphique comme donnée non symbolique, car bien que des travaux sur l'analyse et l'indexation de ce média existent déjà, peu de recherche s'est concentrée sur l'enrichissement que peut apporter le contenu sémantique d'un autre média à son interprétation. Qui plus est, ce média offre un biais intermédiaire entre le « tout sens » et le « sans sens ». En effet, il a une sémantique pauvre, mais il peut être considéré comme un objet structuré qui offre des informations intrinsèques intéressantes ( traits, zooms, flèches, etc.) permettant une réflexion intéressante sur ce qui peut améliorer son indexation. Ainsi, nous désirons aussi décomposer le graphique pour l'indexer de façon précise au lieu de nous contenter de l'indexer globalement.

Nous nous intéressons, dans une première partie, à l'effet du contexte professionnel de l'application sur l'indexation des graphiques ( §2). Ensuite, nous considérons le graphique non plus comme un objet fermé et global non analysable, mais comme un objet contenant des informations de natures multiples qui améliorent son indexation ( §3). À partir de ces deux points, nous définissons un modèle de représentation des graphiques en adéquation avec leur nature et les besoins des utilisateurs ( §4).

Dans une seconde partie, nous nous penchons sur l'enrichissement de la donnée graphique par le contenu des blocs textuels qui l'entourent dans un document technique ( §5). Cette partie représente une étude préalable et concrète visant à démontrer la possibilité d'améliorer l'indexation du graphique par des fragments extraits des blocs de textes la commentant.

La recherche d'information dans les documents techniques à usages professionnels

Les documents techniques qui nous intéressent sont à usage professionnel. Cela nous amène à considérer trois points : Tout d'abord, ces documents sont fréquemment consultés par les utilisateurs, ce qui entraîne une certaine mémorisation visuelle des graphiques qu'ils contiennent. ( §2.1) Ensuite, ces documents véhiculent des savoirs et des savoir-faire propres à un champ technique particulier. Ainsi ils représentent aussi bien la description d'une machine, de son fonctionnement et des divers processus la concernant, que la description des procédures de réalisation d'une action technique dans un environnement précis. Cette finalité d'utilisation des documents techniques qui doit être prise en compte dans la description du graphique est détaillée dans §2.2.

Enfin, les utilisateurs de documents techniques sont très exigeants quant à l'information qu'ils recherchent, le système devra donc être orienté précision, d'où la nécessité d'une indexation spécifique : représenter les éléments intéressants de manière détaillée. ( §2.3)

Prise en compte des besoins et habitudes des utilisateurs

Les manuels d'utilisation des composants matériels sont des documents utilisés fréquemment par les professionnels. Ces utilisateurs connaissent le contenu des documents qu'ils manipulent et lorsqu'ils recherchent une information, ils souhaitent accéder à un fragment précis d'information qu'ils ont déjà vu et qu'ils connaissent : ils savent à priori ce qu'ils recherchent. Ils ne désirent pas trouver « un graphique décrivant l'écran d'affichage de l'imprimante DocuPrint N17 », mais ils veulent retrouver « le graphique qui décrit cet écran » et dont ils se rappellent.

Plus précisément, les professionnels se souviennent de la géométrie du graphique. Par exemple, ils peuvent vouloir retrouver le graphique décrivant le chargement d'incidents papiers dans le magasin d'alimentation manuelle et qui, dans leur souvenir, contient un zoom en haut à droite et une flèche descendante du côté gauche.

En fait, les graphiques des documents techniques contiennent des données géométriques (formes, traits, positions, zooms etc.) et de nombreuses expériences ont montré que lorsqu'une personne est confrontée à un énoncé de "spatialisation" organisant des objets les uns par rapport aux autres, elle construit mentalement une représentation de la scène [START_REF] Michel | Langage et cognition spatiale[END_REF]. Cette représentation mentale du graphique peut s'ancrer partiellement ou totalement dans la mémoire de l'utilisateur. On parlera, dans ce cas, de sa mémoire visuelle. La trace laissée par le graphique dans la mémoire de l'utilisateur peut ainsi représenter une requête probable pour retrouver le graphique en question. La prise en compte de la mémoire visuelle de l'utilisateur a donc une importance dans la représentation des graphiques des documents techniques et elle doit être prise en compte.

Prise en compte de la finalité d'utilisation

Les documents techniques permettent de répondre à deux grandes classes de requêtes :

-« Qu'est ce que 'x' ?» : Le document fournit alors des informations contribuant à l'énumération des composants de l'objet 'x', la description de leurs propriétés et de leurs fonctions (de l'objet 'x' et de ses composants). Le graphique est ainsi perçu comme une description de la sémantique de son contenu, avec une distinction entre un aspect descriptif et un aspect opératoire. Ce dernier aspect est une particularité des graphiques des documents techniques à usage professionnel et il doit nécessairement être pris en compte lors de la modélisation de tels graphiques.

Précision de l'indexation

Lors de la rédaction d'un texte technique, les auteurs de la documentation suivent des règles bien précises. Ils doivent se montrer particulièrement vigilants sur la pertinence de leurs phrases, l'homogénéité du texte, les styles de phrases et le vocabulaire employé.

Ceci est dû à la finalité d'utilisation des documents techniques et au « professionnalisme » de ses utilisateurs.

De même et pour les mêmes raisons, le langage d'indexation des graphiques doit être spécifique. D'un autre côté, lorsqu'ils recherchent une information, les utilisateurs des documents techniques désirent accéder au fragment du document qui les intéresse. Le système doit alors donner en réponse précisément ce fragment recherché. Il doit donc être orienté précision. Pour ce faire, l'indexation d'un graphique doit être détaillée et ses index doivent suivre une structure bien précise. Le maximum d'information le concernant devra être représenté ( §3) et rangé dans un schéma logique.

Le graphique des documents techniques: Des informations multiples à indexer

Le graphique dans les documents techniques est un média qui, une fois considéré comme un objet analysable et non plus comme une donnée élémentaire, contient une multitude d'informations. En effet, outre les informations internes qu'il est possible d'en extraire (traits, flèches, zoom, etc.), il s'agit d'un objet structuré ayant une sémantique qui même si elle n'est pas explicite dans celui-ci est mentionnée dans le texte qui le commente.

Dans ce qui suit, nous résumons les différentes interprétations possibles du graphique contenu dans la documentation technique :

-Le graphique est un objet complexe et multi-facettes, dont les éléments intéressants sont liés entre eux par des relations de composition. Par exemple, L'« Imprimante N17» est composée du « Magasin papier », de la « Poignée », etc. Ces éléments peuvent être soit des composantes matérielles, soit des formes particulières rajoutées par les auteurs pour exprimer une action, une énumération ou un agrandissement, etc.

-Le graphique est accompagné d'une description de la sémantique de son contenu, avec un aspect opératoire et un aspect descriptif.

-Le graphique est perçu comme un ensemble de formes géométriques disposées d'une manière particulière et ayant chacune un degré d'importance particulier.

-Le graphique visualisé s'imprime dans la mémoire visuelle des utilisateurs. Cette mémoire leur fournit alors un moyen d'accès aux graphiques. Certains objets de ce graphique auront plus d'impact sur leur mémoire visuelle que d'autres, selon l'importance de ces objets dans le graphique.

Les différents points énumérés ci-dessus représentent les grandes lignes qui nous ont guidés dans l'élaboration de notre modèle.

Proposition du modèle

La multiplicité de la nature des informations à indexer nécessite de définir un modèle pour la représentation des graphiques. Ces derniers étant structurés et multifacettes, nous avons choisi de nous inspirer d'un modèle supportant ces deux aspects: Le modèle EMIR². [START_REF] Mechkour | EMIR², un modèle étendu de représentation et de correspondance d'images pour la recherche d'informations. Application à un corpus d'images historiques[END_REF] Nous commençons donc par présenter synthétiquement le modèle EMIR² avant de décrire notre modèle, qui est capable de représenter complètement les graphiques des documents techniques.

Présentation de EMIR²

EMIR² est un modèle qui « considère comme représentation du contenu d'une image diverses interprétations de l'ensemble des objets images et des relations qui les lient.» [START_REF] Mechkour | EMIR², un modèle étendu de représentation et de correspondance d'images pour la recherche d'informations. Application à un corpus d'images historiques[END_REF] À chaque interprétation, ou plus exactement vue, est associé un modèle donnant une description des objets contenus dans l'image, des relations qui peuvent les relier et des opérations applicables sur ces descriptions.

EMIR² défini cinq vues :

-la vue physique correspond aux données brutes de l'image (matrice de pixels, dimensions, etc.), -la vue structurelle représente l'ensemble des éléments pertinents de l'image reliés par des relations de composition, -la vue symbolique représente l'interprétation sémantique des éléments contenus dans l'image, -la vue spatiale représente l'ensemble des objets géométriques associés aux contours des éléments contenus dans l'image et leurs inter-relations, -la vue perceptive représente l'ensemble des attributs visuels objectifs des éléments contenus dans l'image (couleur, texture et brillance).

Description de notre modèle

Contrairement au modèle que nous visons, le modèle EMIR² fait abstraction du domaine des images, de l'application particulière qui les manipule et du type des utilisateurs auquel elle est destinée. Donc, en tenant compte du média particulier vers lequel nous nous sommes orientés, il est apparu que la vue perceptive est inutile (il n'y a pas de couleurs, ni de textures dans les graphiques) et que des vues structurelles et spatiales adaptées aux graphiques doivent être définis. La vue graphique est, de ce fait, représentée par un graphe dont les noeuds sont les objets graphiques et les arcs les relations citées ci-dessus.

La vue spatiale

Cette vue permet de représenter les formes des objets graphiques et leurs dispositions les uns par rapport aux autres. Elle comporte donc des informations géométriques décrivant les objets spatiaux ainsi que leurs inter-relations (telles que leurs positions relatives). La forme des objets spatiaux est représentée par une combinaison d'éléments géométriques de base qui sont les points, les segments et les polygones.

La vue symbolique

Cette vue correspond à la représentation du contenu descriptif d'un graphique. Dans cette vue, sont représentés les propriétés du graphique et des objets graphiques.

À chaque objet structurel est associé un objet symbolique défini dans cette vue. Et à chaque objet symbolique correspondent des attributs décrivant l'objet en question. Des relations symboliques peuvent relier deux objets symboliques.

Il est important de noter que différents objets structurels peuvent avoir un seul objet symbolique qui leur correspond. Il s'agit du cas d'objets structurels équivalents auxquels nous associons un même objet symbolique afin d'éviter la redondance. Une pondération correspondant à l'importance de l'impact sur la mémoire visuelle de l'utilisateur est associée à chaque objet et relation entre deux objets de cette vue.

On distingue trois types de poids :

-Un poids affecté à l'objet selon l'impact de l'existence de cet objet dans le graphique sur la mémoire visuelle de l'utilisateur. Autrement dit, ce poids représente l'importance pour l'utilisateur de l'existence de l'objet en question dans le graphique.

-Un poids relatif à l'importance de la forme de l'objet graphique pour la mémoire visuelle de l'utilisateur. Ce poids représente donc l'importance pour l'utilisateur de la forme de l'objet.

-Un poids affecté à la relation liant deux objets correspondant à l'importance pour l'utilisateur de la position relative entre les deux objets.

Afin de mieux comprendre ces différents poids, nous prenons l'exemple de la figure 6: -à l'existence de l'objet Omv2 est associé le poids 1 : (Omv2, 1). L'utilisateur se rappellera à 100% du zoom, représenté dans cette vue par l'objet Omv2, présent dans le graphique en question.

-à la forme de l'objet Omv12 est associé le poids 0,8 : (Forme, Omv12, 0.8). L'utilisateur se rappellera à 80% de la forme de l'objet, du graphique en question, représenté dans cette vue par Omv12.

-à la relation entre les objets Omv2 et Omv21 est associé un poids 0,4 : (Omv21, Omv2, 0.4). L'utilisateur se rappellera à 40% que dans le graphique en question, l'objet représenté dans cette vue par Omv21, est contenu dans le contour de l'objet zoom, représenté par Omv2.

Enrichissement de l'indexation de la donnée non symbolique par les données symboliques avoisinantes

Dans ce paragraphe, nous nous intéressons à l'extraction des fragments contenus dans les blocs textuels entourant un graphique qui vont servir à son indexation.

En général, afin d'enrichir une donnée non symbolique par les données symboliques avoisinantes, deux problèmes apparaissent :

-Où et comment localiser les données symboliques qui peuvent enrichir la donnée qui nous intéresse, autrement dit celles qui contiennent des informations la concernant.

-Comment extraire les fragments permettant de d'enrichir la description de la donnée non symbolique à partir des blocs de données précédemment localisés.

Dans notre application sur les documents techniques, il s'agit de localiser le texte qui est en relation avec le graphique qui nous intéresse, afin d'en extraire par la suite les termes qui vont servir à « remplir » le modèle que nous avons proposé.

Localisation des données symboliques adéquates (les commentaires) :

La structure d'un document facilite l'identification de ses différentes entités. Ainsi, il est plus aisé de relier les entités symboliques aux entités non symboliques correspondantes.

Dans les documents structurés, il existe une propagation de l'information entre les blocs reliés par une relation de composition. Ainsi, dans les documents techniques, le graphique est relié à la section, au sous-chapitre et au chapitre qui le contiennent. Cette relation est mise en évidence par l'existence d'un lien entre le graphique et les titres respectifs de la section, le sous chapitre et le chapitre. En partant de la donnée non symbolique qui nous intéresse et en remontant vers la racine de la hiérarchie du document structuré, les titres des blocs rencontrés semblent être des données permettant d'enrichir notre donnée non symbolique. Il nous reste alors à trouver les blocs de données qui lui correspondent et qui la décrivent avec plus de précision. Autrement dit, dans le cas des documents techniques, il nous reste à trouver le paragraphe commentant le graphique.

Il existe deux types de liens qui peuvent relier un premier bloc et celui qu'il commente:

-les liens explicites: c'est le cas lorsque le texte référence directement le graphique (voir figure X, la figure x illustre…), -les liens implicites: il s'agit du cas où l'auteur n'utilise pas d'expression linguistique spécifique pour référencer le graphique.

Dans le cas d'une référence explicite, le fait qu'un graphique soit éloigné de son commentaire n'est pas gênant puisque le lecteur peut pointer le graphique à l'aide de la référence. Par contre, dans le cas d'une référence implicite si le graphique est trop éloigné de son commentaire alors l'information se perd au fur et à mesure de la lecture empêchant ainsi le lecteur d'effectuer la relation. Il s'agit, dans ce deuxième cas, d'étudier l'espace géographique dans lequel se situe le graphique afin de retrouver le bloc qui lui correspond.

Nous avons supposé dans un premier temps que un lecteur ne pouvant pas retrouver des liens implicites trop éloignés, l'auteur en a forcément tenu compte lors de la rédaction (ou mise en page). Le texte commentant le graphique est, dans ce cas, celui qui lui est le plus proche. Reste alors à extraire depuis ce bloc, les fragments ayant trait au graphique (selon le modèle que nous avons proposé).

Extraction des index dans le commentaire :

Le critère de qualité majeur d'un document technique est basé sur son efficacité et sa facilité d'utilisation. Pour répondre à cette contrainte, un certain nombre de règles est respecté par les rédacteurs techniques sur le plan de la forme textuelle. Ils doivent se montrer particulièrement vigilants sur la pertinence de leurs phrases, sur l'homogénéité du texte et les styles de phrases utilisés. Les auteurs suivent ainsi des règles bien précises lors de la rédaction d'un texte technique. Cela se traduit par l'existence d'une certaine régularité au niveau du document. Cette régularité peut être exploitée afin de retrouver des règles et des patrons linguistiques exploitables pour le repérage des index des graphiques. Exemples : « carte réseau » : SUBC SUBC, « panneau avant » : SUBC ADVB -dans le cas de la description d'une action, on parlera du patron ACT (le composant et l'action à y appliquer) :

ACT : Pouvant être ACT1 (action sans condition) ou ACT2 (action avec condition). Nous donnerons seulement un exemple de ACT1 :

Les résultats obtenus sont prometteurs, cependant une étude plus poussée devra être menée.

Exemples de requêtes/réponses

Nous avons traduit notre modèle dans le formalisme des graphes conceptuels (Sowa J.F. 1984) La requête Req2 permet de retrouver deux graphiques répondant à la requête. En rajoutant à cette requête l'aspect opératoire (Req3), la réponse se précise : nous obtenons ainsi un seul graphique, celui qui parmi les deux nous intéresse réellement.

Conclusion et perspectives

La définition d'un bon modèle d'indexation est un problème clé en recherche d'information. Lorsque les données à indexer sont peu symboliques, la tâche est encore plus délicate, car il faut pouvoir retrouver ailleurs les éléments décrivant le mieux ces données. Nous avons proposé un modèle pour décrire les aspects les plus pertinents des graphiques des documents techniques en tenant compte des

Figure 1 :

 1 Figure 1 : Exemple d'empreinte d'un graphique (a) sur la mémoire visuelle (b)

Figure 2 :

 2 Figure 2 : Exemples de graphiques à visée descriptive (a) et opératoire (b)

  Et le fait de dédier le système à des utilisateurs spécialisés entraîne qu'il faut prendre en compte, d'une part, une sémantique particulière, ce que nous ferons dans la vue opératoire, et d'une autre part, la mémoire visuelle de l'utilisateur et nous le ferons dans la vue dite mémoire visuelle.Nous avons ainsi abouti à un modèle dont les différentes vues et leurs interrelations sont schématisées dans la figure suivante :

Figure 3 :

 3 Figure 3 : Vue synthétique du modèle proposé 4.2.1. La vue physique C'est la vue la plus élémentaire d'un graphique. Elle rassemble les caractéristiques générales du graphique, telles que ses dimensions, sa résolution, sa matrice de pixels. 4.2.2. La vue structurelle Elle représente la décomposition d'un graphique en objets graphiques. Nous faisons la distinction entre les objets graphiques représentatifs (représentant un objet réel tel que une cartouche) et les objets graphiques illustratifs (représentant un zoom, une énumération, une main, etc.) À cette vue correspond une relation de composition « CONTIENT » reliant des objets graphiques entre eux. D'autres relations lient les objets illustratifs aux objets représentatifs. Ainsi, la relation « EQUIVAUT » relie un zoom ou une représentation plate et l'objet visé par l'objet illustratif, la relation « NUMEROTE » relie une numération et l'objet pointé, et la relation « ACTION_SUR » relie une flèche ou une main et l'objet sur lequel s'effectue l'action.

Figure 4 :

 4 Figure 4 : Exemple de vue descriptive d'un graphique

Figure 5 :

 5 Figure 5 : Exemple de vue opératoire d'un graphique

Figure 6 :

 6 Figure 6 : Exemple de vue mémoire visuelle d'un graphique

Figure 7 :

 7 Figure 7 : Blocs de textes correspondant à un graphique

Figure 8 :

 8 Figure 8 : Graphiques répondant aux requêtes Req1(a), Req2(b) et Req3(c)

  Notre but, à ce stade, étant de démontrer la possibilité d'exploiter la régularité dans la rédaction des documents techniques dans le but d'en extraire les expressions linguistiques correspondantes aux termes d'indexation des graphiques, nous nous sommes limités à l'étude d'un unique manuel d'utilisation. Notre étude à permis d'aboutir à des critères spécifiques à notre corpus. Même si elle ne nous permet pas de généraliser les règles d'extraction d'index, elle est une preuve de la faisabilité de cette extraction, et dès lors une étude similaire et plus poussée pourra être faite. Les informations à extraire du texte afin d'enrichir la description du graphique sont celles représentées dans les deux vues symbolique et opératoire, à savoir :-quelles sont les composantes contenues dans le graphique, leurs propriétés et leurs fonctions ?-quelles actions doivent leur être appliquées, à quelles conditions, et quel est leur ordre d'exécution ?-quel est l'action décrite par le graphique, quelle est son étape et dans quel cas est-elle nécessaire ?Afin d'extraire les termes correspondant à ces informations, une étude du commentaire à été menée pour tenter de mettre en place des règles permettant leur repérage.Il en a résulté que, d'un point de vue « structure », le commentaire peut être un titre, un ou plusieurs items d'une liste ou un paragraphe classique. Et d'un point de vue « sens », le commentaire peut soit décrire un composant, soit une action à lui appliquer. Ce deuxième point de vue est détaillé dans ce qui suit :-Lorsqu'il s'agit d'une description d'un composant, on parlera du patron COMDESC (le composant COM et sa description) :COMDESC :

(ADJ)* COM (PREP GN)*(ADJ)* 1 Exemple : « Ecran d'affichage de 16 caractères » COMPOSANT :écran d'affichage DESCRIPTION: de 16 caractères COMPOSANT : COM DESCRIPTION: PREP GN/ADJ Où COM : (ADJ)*((PREP)* SUBC (SUBC)*)* (ADVB)* 2

-« Comment faire pour 'x' ?» : le document fournit alors des informations indiquant l'action générale à accomplir, le cas d'application de cette action, les actions intermédiaires à effectuer sur les composants de la machine et les conditions et l'ordre d'exécution de ces actions.Afin de diminuer l'effort de modélisation de l'utilisateur, les graphiques permettent de schématiser les informations citées ci-dessus et l'utilisateur peut alors facilement les localiser dans le graphique. On retrouve alors deux types de graphiques. Certains sont à visée descriptive et on y distingue une présentation des objets qu'ils contiennent. D'autres sont à visée opératoire et on y trouve la définition d'une liste d'actions à appliquer sur les objets qu'ils contiennent. (b) La main et la flèche sous entendent une action (a) Description de l' « Ecran d'affichage »

ADJ : Adjectif, PREP : Préposition, GN : Groupe nominal, * : facultatif

SUBC : Substantif commun, ADVB : Adverbe

ART : Article, PARE : Parenthèse, NB : Nombre, GP : Groupe nominal ou verbal

VRB : Verbe

Traduction exacte: les termes extraits du patron correspondent aux index adéquats.


Christophe Brouard
email: christophe.brouard@imag.fr

CLIPS at TREC-11: Experiments in Filtering

At the TREC9 conference, we presented a new adaptive filtering system called RELIEFS. This system which is based on the idea of resonance, combines for each term t, the relative frequency of relevance knowing t and the relative frequency of t kwowing relevance. On the basis of other experiments, several changes have been made. We improved our threshold adaption, we slightly changed our relevance evaluation function and we gave up the use of conjunctions and thesaurus. The system is now focusing more exclusively on the combination of both reverse frequencies that we believe to represent the fundamental aspects of relevance estimation. This year we used the system in its new version and we tested it on the Reuters corpus. Focusing on the combination of the two frequencies, we varied their relative importance. The results show globally a good effectiveness especially when both frequencies are balanced.

Introduction

In a logical approach, it has been found that the evaluation of relevance of a document D to a query Q can be based on the evaluation of the implication from document to query D->Q [START_REF] Van Rijsbergen | A non-classical logic for information retrieval[END_REF]. Some authors also emphasized the role of the reverse implication (Q->D) [START_REF] Nie | An outline of a general model for information retrieval[END_REF]. These two entailment relations can also be found in most probabilistic models, formulated as P(Q/D) (Probability of Q knowing D) and P(D/Q) (see Crestani, Lalmas, van Rijsbergen & Campbell, 1998, for an overview of Probabilistic models).

If one considers a document as a set of terms, and a query as a specification of what we are looking for, the entailment D->Q may be decomposed to the judgment of "if the term is present then the document is relevant" for each term of the document. So, if we use a set of documents with the relevant judgments associated, the entailment D->Q can be decomposed in a set of relative frequencies of relevance knowing term for each term of the document. Similarly, the reverse entailment relation can be decomposed in a set of relative frequencies of term knowing relevance. From a pragmatic point of view, the use of the first frequency is easily understood since it allows to favour the terms which predict relevance (when the term is present then the document in which it occurs is relevant). The consideration of the reverse frequencies may be justified by the fact that it allows to favour terms which have been met many times in relevant documents. Since they appear relatively frequently, these terms are likely to be usefull for the next evaluations, and we can think that their presence in relevant documents is not a coincidence (comparing to rare terms which occured once or twice). We believe that both entailment relations capture the essence of relevance. As we noted before they are found in the most IR models but not always in a obvious way. With the system RELIEFS we try to isolate them and to use them in a simple way. So, for each term t i , we propose to compute the frequency of relevance knowing term F(R / t i ) and the reverse frequency 1).

F(t i / R) (Figure

System description

The RELIEFS document processing can be decomposed in three steps:

1. Selection of N terms from the document, 2. Estimation of the document's relevance, 3. Revision of term's relative frequencies.

Step 1 : Selection of N document terms

All the document terms are compared with the terms which have been extracted from the query, from the document examples given for learning and from the documents which have been previously selected. They are sorted by the value the product F(R / t i )* F(t i / R). If less than N terms can be selected in this way (in our experiments we choose N=30), this selection is completed by the document terms in their lecture order.

Step 2 : Relevance estimation

Considering the terms which appear in the document, the score of the document is computed as follows :

F(R / t i )* F(t i / R) i =1 N ∑ F(R/ t j )* F(t j / R) j =1 N ∑ relevance term relevance knowing term term knowing relevance F(R / t i ) F(t i / R)
where i are the indices of the N best terms (according to the product

F(R / t) * F(t / R) ))
which are present in the document and where j are the indices of the N best terms (present or not present in the document). In RELIEFS, the relevance of a document can be interpreted as a kind of resonance in a network (Figure 2) in which each relative frequency corresponds to a weighted connection and each term corresponds to a node [START_REF] Brouard | Relevance as Resonance : A new Theoretical Perspective and a Practical Utilisation in Information Filtering[END_REF]. A relevance node is built for each query.

Step 3 : Relative frequencies updating

If the evaluation of step2 is larger than a defined threshold the document is selected and the relevance feedback takes place. Given the relevant judgment, the N terms selected in the first step are submitted to an updating process on their relative frequencies.

Threshold adaption

The queries are very different from each other. Therefore, a different threshold is determined for each query. The value of the threshold is determined empirically. The initial threshold is computed on the basis of the score of the three first relevant documents. We used the following strategy to adjust the value:

-If a selected document is irrelevant, the system is considered to be too tolerant. The threshold is increased.

-If a document (that we do not know if it is relevant or not) is not selected, the system is considered to be too strict. Then the threshold is decreased The increase scale is set to be higher than the decrease scale because there are much more unselected documents than the selected ones. The decrease of threshold in the second case is due to the fact that we do not want the system to remain silent for a too long period. This allows to gradually correct an initial threshold that is fixed too high. In both cases, we considered different criteria for the modification of the threshold, including:

-The number of irrelevant documents that are selected consecutively: The higher this number, the larger the increase scale and the smaller the decrease scale.

-The number of consecutive relevant document: The higher this number, the larger the decrease scale. This change only concerns the decrease case.

-The number of documents considered: The larger this number, the lower the change scales. The intuition behind this criterion is that we would make larger changes at the beginning of the filtering. When a certain number of documents have been treated, the system should stabilize.

We also considered a more global criterion on the probability of relevance. Each score is associated with a frequency of relevance and we try to adjust the threshold on the score for which the probability is 0.33 (this selection criterion is optimal for the utility measure).

Experiments

Preprocessing

We used the Porter's stemmer to get the root form of every term and we removed the stopwords.

Details of processing

All parameters (which mainly concern the threshold tuning) were tuned on the Oshumed corpus (TREC9). For each document of the Reuters corpus, we only considered the title and the text fields. For updating frequencies, the unjudged documents were considered as irrelevant. A pseudo-relevance feedback has been applied when the scores were smaller than a defined threshold. In this case, the document is considered as irrelevant.

Varying the relative importance of the entailment relations

In our previous tests, both entailment relations are considered with the same importance: they are multiplied. Our question is, should they play equal role in the estimation or should one factor be more important than another? In order to answer this question, we vary the importance of one of the implication by replacing the weight F(R / t i ) by F(R / t i )

ρ . The factor ρ changes the relative importance of this relation. The relevance estimate is defined as follows:

F(R / t i )* F(t i / R) ρ i =1 N ∑ F(R/ t j )* F(t j / R) ρ j =1 N ∑

Results

Globally, it turns out that the best results are obtained when the two frequencies are balanced ( ρ in [1.0,1.4]) even if we can observe that good results for ρ =1.6 and ρ =1.7

(Table 1). This is consistent with the previous observations we obtained with the Oshumed corpus.

ρ We submitted the best run ( ρ =1.2) for comparison on utility criteria. The comparison is favourable since about 80% of the scores are above or equal to the median. Like the other systems we obtained better results for the first 50 queries than for the 50 last ones which are built differently.

In conclusion, results suggest that the two reverses frequencies are sufficient clues to estimate the relevance. Furthermore, the fact that the best results are obtained when the two aspects are balanced should indicate that they are both necessary and equally important.

Figure 1 -

 1 Figure 1 -Relationships between terms and relevance

Figure 2 -

 2 Figure 2 -Relevance evaluation in RELIEFS of a document in which term1 and term4 occur

Table 1 :

 1 The impact of ρ on the utility.

		Utility	ρ	Utility	ρ	Utility	ρ	Utility
	0.0	-0.26	0.5	10.35	1.0	16.68	1.5	14.01
	0.1	2.65	0.6	12.25	1.1	17.25	1.6	16.82
	0.2	4.92	0.7	12.42	1.2	17.84	1.7	17.27
	0.3	8.01	0.8	13.22	1.3	17.68	1.8	13.19
	0.4	9.41	0.9	15.44	1.4	16.95	1.9	12.03