Action ESCRIRE

Méthodologie de comparaison

jeudi 9 mars 2000

 

Introduction

Afin de manipuler efficacement une base de documents (par exemple un site web), on cherche à indexer les documents par leur contenu (ou leur sens). Cela permet de rechercher les documents pertinents en utilisant des requêtes structurées tirant parti des formalismes de représentation de connaissance actuels (hiérarchies de classes, mécanismes de classification...). Pour cela, une représentation du contenu dans un formalisme de représentation de connaissance par objets devra être intégrée dans le document. Mais laquelle ? Afin d’avoir une idée plus précise de l’adéquation des formalismes de représentation de connaissance à cette tâche, l’action ESCRIRE a pour but de comparer trois formalismes : graphes conceptuels, représentation par objets et logiques de descriptions. Le présent document fixe la méthodologie de comparaison mise en œuvre.

Méthodologie

Données

Il est prévu d’utiliser deux jeux de données (très similaires) dont l’un sert à l’entraînement des logiciels et l’autre à leur évaluation (il serait encore plus utile de disposer de trois jeux : entraînement, premier test, évaluation).

Par jeu de données on entendra :

  1. un ensemble de documents ET leurs représentations pivot (échantillonnées comme ci-dessous) ;
  2. un ensemble de requêtes ET leurs représentations pivot (échantillonnées comme ci-dessous) ;
  3. les réponses (ordonnées) à ces requêtes.

Les documents et requêtes concerneront un même domaine qui sera modélisée dans la représentation pivot par l’ensemble des participants (modèle commun aux deux jeux de test).

Les données seront des " méta-données " introduites dans un document. Elles se composeront donc de trois parties :

  1. le document ;
  2. les méta-données classiques (ex. dublin-core) ;
  3. le champ de méta-donnée content qui contiendra une description du contenu du document en langage pivot (auquel on pourra adjoindre sa traduction dans l’un ou les trois langages).

Pour des raisons de simplicité du processus, le champ contenu ne contiendra pas de référence aux autres documents mais pourra faire référence à l’" ontologie ".

Processus

Le processus mis en œuvre est présenté dans la deux figure suivante :

Il nécessite l’encodage du contenu des documents à partir d’une représentation pivot (qui pourrait être celle engendrée à partir d’un mécanisme de traitement automatique de la langue naturelle, mais qui dans notre cadre sera engendré manuellement). De même, les requêtes devront être traduites à partir d’une représentation pivot. Ainsi, les formalismes comparés sont placés sur un réel pied d’égalité (les mêmes représentations et requêtes entrent en jeu au lieu d’être exprimées dans des langages différents).

Logiciels comparés

Le but de l’expérimentation est de comparer trois logiciels utilisant des systèmes de représentation de connaissance différents (GC=graphes conceptuels, RCO=représentation de connaissance par objets, LD=logique de description). Afin d’avoir un témoin extérieur aux performances de ces systèmes, on les comparera avec les performances d’un logiciel de recherche texte intégral (TI).

Pour que les mesures soient objectives, il est nécessaire que les entrées/sorties des logiciels soient les mêmes, d’où l’utilisation d’une structure pivot. Cependant, afin de prendre en compte le biais introduit par cette structure vis-à-vis des logiciels, il sera permis aux équipes qui le désirent de procéder à une seconde vague de test avec un encodage manuel des données d’entrée (respectivement mGC, mRCO et mLD).

Mesures objectives et subjectives

Il est souhaitable que la plupart des tests puissent se faire de manière automatique.

Il n’est pas interdit, cependant d’introduire des tests manuels avec un critère d’évaluation subjectif (voir plus bas). On aura alors deux types de test qualifiés dans le document Concerto de " test externes " et de " qualité à l’usage (quality in use) ". En tout état de cause, le développement d’évaluation subjective nécessite de décrire l’ensemble du contexte d’évaluation (caractéristiques de l’utilisateur, de la tâche, de l’environnement).

Il n’est cependant pas souhaitable que puissent intervenir une manipulation des structures de représentation par l’utilisateur dans ces tests subjectifs. Dans un second temps, il peut être intéressant de définir un second ensemble de test subjectif avec manipulation directe (création de requête dans le langage de représentation par exemple). Cependant, hors d’un protocole extrêmement contrôlé, ces tests ne pourront pas être considérés comme significatifs.

Critères

Définition des critères objectifs

Rappel : % de réponses à une requête par rapport aux réponses attendues ;

Précision : % de réponses attendues par rapport aux réponses données ;

Performance : temps utilisé pour répondre à une requête. Afin d’avoir une idée expérimentale intéressante de cette grandeur (et sachant que les logiciels utilisés sont des prototypes de recherche non optimisés), il est nécessaire de l’évaluer dans le contexte de bases avec des ordres de grandeurs différents (pour la même requête) et de requêtes avec des complexités différentes (pour la même base).

Pertinence de l’ordre : Il est nécessaire de définir un degré d’accord de l’ordre des réponses retournées avec l’ordre escompté (pas facile) ;

Couverture des types de requêtes

Agrégation

Il sera sans doute nécessaire de définir des agrégations des mesures brutes données plus haut.

On peut déjà retenir le fameux : accuracy=(precision+recall)/2.

Critères subjectifs

Le principal critère subjectif est sans doute celui permettant l’agrégation, c’est-à-dire de demander à des spécialistes du domaine d’évaluer qualitativement et des classer les logiciels à comparer.

Ce problème est certainement plus simple à traiter dans notre cas, car les expérimentateurs peuvent simplement dire quel système ils pensent être le meilleur. Mais ils peuvent aussi décomposer les parties (simplement en leur proposant l’ensemble de notre grille d’analyse) ou plus simplement signaler ce qu’ils pensent nécessaire d’améliorer. Il faut par contre soumettre les évaluateurs aux mêmes règles.

Échantillonnage

Les tests devront être échantillonnés principalement en fonction de deux critères :

Cela devrait permettre de mieux cerner, en fonction des types de requêtes et d’information, les qualités de chacun des formalismes.

On aura donc une structure de tests bidimensionnelles (indépendamment des évaluations de performances développées ci-dessus). Chacune de ces dimensions (structure/requête) est détaillée ci-dessous.

Structures

Les structures de représentation manipulées et leur représentation seront à définir.

Je propose de prendre comme base les structures engendrables par les systèmes d’analyse de langage naturel au minimum (YT). Le langage pivot peut être d’autant plus riche que comme il n’est pas question pour les systèmes d’en engendrer, le non-traitement de certaines constructions ne sera visible que dans ses performances.

Principes

L’un des premiers principes proposés était de séparer l’" ontologie " des individus (le pendant de support/graphes, classes/instances, tbox/abox). Mais il y plusieurs arguments contre cela:

La DTD admet donc des éléments individuels dans l'élément ontology. En ce qui concerne les éléments conceptuels dans l'élément contenu, on attendra.

Le langage de description rencontré dans les documents décrira des objets, leur appartenance à des classes et les valeurs de leurs attributs (une Abox typique de logique de description, sans contraintes de cardinalité) ainsi que des relations (avec classes, arguments et attributs). Le langage de description des " ontologies " comprendra la description des classes (et des classes de relations) dans une taxonomie avec la description des attributs (par leur type et restriction sur les types). En ce qui concerne les restrictions sur les types, on peut envisager de coller au plus près de l’application considérée et de ne pas forcer à tout prix des restrictions particulières. Les restrictions minimales seront (a) la spécification des classes auxquelles la valeur doit appartenir, (b) la spécification d’un ensemble de valeurs.

Format

Le format est spécifié dans la DTD escrire.

Voici le format du langage de document :

<<ICI METTRE UN EXEMPLE AVANT LA PROCHAINE RELEASE>>

Requêtes

Une hiérarchie de types de requêtes est proposée ici en fonction de ce qui peut être trouvé dans les langages de requêtes OntoBroker (JE), Search 97 (RD), ODMG (AN), Trek (YT) , XMLQL (OC). Les formalismes seront comparés en fonction de (1) leur couverture de l’ensemble de requêtes et (2) leur performance en fonction des critères sur chacun des types de requête.

Interprétation des requêtes

Un premier principe est que les requêtes, même si elles portent sur des entités quelconques, sont destinées à retourner des documents : ceux qui parlent de ces entités.

La force des systèmes à base de connaissance consiste à faire des inférences pour coller à la sémantique des langages ce qui n’est pas le cas par exemple de XQL car XML est structurel. Il est possible d’imaginer répondre aux requêtes en faisant des inférences uniquement en fonction du contenu d’un document ou en fonction du contenu de tous les documents connus. Dans cette éventualité, on retourne les groupes de documents permettant de répondre par l’affirmative à une requête. Dans l’ordre d’inclusion:

C doc0 A -> C, B-> C

D doc1, doc2, doc3 X -> Y / A -> X / B -> X

| doc2, doc7 X -> Y / A -> X / B -> X

| doc4, doc8, doc3 Z -> Y / A -> Z / B -> X

Mais, indexer les documents par le contenu n’est pas la même chose que construire une base de connaissance, par ailleurs dans le cas général la base obtenue ne sera ni consensuelle, ni consistante.

On prend donc la décision (éventuellement révisable après expérience) que les inférences ne sont que locales.

Langage de requêtes (textuel)

On peut reprendre le schéma classique introduit par SQL :

Par exemple :

SELECT K.name

FROM K:gene, Z:interaction, W:interaction

WHERE Z.target = K, W.target = K, Z.promoter = A, W.promoter = B

ORDER BY K.name

Retournera des réponses de la forme:

nom1 url1.1

url1.2

url1.3

nom2 url2.1

url2.2

où les nom1,... sont les objets définis dans le SELECT et les url1,… ceux des documents permettant de répondre à la question (à noter que l’on pourrait imaginer SELECT FROM K:gene, R:interaction WHERE R.target=K). Les formats de requête et de retour seront communiquées au format XML (DTD qesc et resc) et manipulés suivant la procédure de la figure XX.

Figure XX. Acquisition et réponse à la requête.

On se penche donc plus longuement sur le champ WHERE.

where := cont (op cont)* // sélection

op := AND | OR // connecteurs

cont := NOT cont // contrainte

| quant comp / sur attribut

| in class / d’appartenance

| alike document /de proximité

CERTAINEMENT D’AUTRES ICI /…

quant := ALL | EXIST // quantificateur

comp := term pred term // comparaison

term := path | const // terme

path := attname (.atname)* // chemin

const := integer | string | regexp | set | list // valeur

pred := = | | | < | Œ | … // prédicat

Chacun de ces aspects est examiné ci-dessous, les éléments entre [ et ] ne sont pas pris en compte actuellement dans la plate-forme, ceux entre [[ et ]] sont résolument éliminés.

Sélection sur les valeurs d'attributs

L’ensemble des documents ayant &i {val-i à caractéristique att-i}.

Comparateurs (prédicats)

La sélection des valeurs peut être raffiné par le mode de comparaison des valeurs. Il existe une hiérarchie de façon de définir val-i :

  1. Égalité (la valeur doit être égale à une valeur particulière) ;
  2. Énumération (elle doit être dans un ensemble de valeurs particulière) ;
  3. Intervalle (elle doit être dans un intervalle de valeur particulier) ;
  4. Classe (elle doit être dans une classe d’objets particulière) ;
  5. [[Contrainte (elle doit satisfaire des contraintes – au sens CSP – particulières).]]
  6. Chemins

    La sélection des attributs peut être raffinée sur le mode d’Xpath/ODMG. Il existe une hiérarchie de façon de définir att-i :

  7. Nom d’attribut (père);
  8. Chemin d’attribut (père.père);
  9. [Clôture transitive d’attribut (père*);]
  10. [Expressions régulières sur les chemins d’attributs (père[1-3].frère+);]
  11. [Expressions régulières sur les noms d’attributs (?ère.fil*).]

Interprétation des requêtes (quantificateurs)

Soit une contrainte REQ telle que définie plus haut, elle peut s’interpréter avec diverses quantifications :

  1. le champ est le sujet de la requête et il doit la satisfaire ;
  2. il doit exister un objet dans le champ satisfaisant la requête ;
  3. tous les objets dans le champ doivent la satisfaire ;
  4. Il semble clair que

  5. avantage les RCO ;
  6. avantage les GC ;
  7. n’arrange personne mais offre peut d’intérêt.
  8. Cependant on a décidé de retenir les deux dernières interprétations marquées par un quantificateur explicite ALL ou EXIST.

    ALL d.content IN class1

    AND EXIST (x.length 2)

    OR ALL d.authors.nationalité = "french")

    Sélection sur les classes d'appartenance

    L’ensemble des documents classés sous &i {classe-i} (on pourrait varier par " exactement attaché à ").

    Proximité

    L’ensemble des documents proches du document i

    Sélection combinée

    Elle peut aisément être réalisé en adjoignant au AND implicite des requêtes SQL, le OR et le NOT. Ces opérateurs seront disponibles dans la plate-forme.

    Jointure

    Stricto Sensu : l’ensemble des couples de documents joints par un sous ensemble de leurs caractéristiques (d1.a = d2.a).

    Plus simple : une sélection avec des contraintes sur les caractéristiques d’un document en attribut (?).

    Classement

    Trouver la (les) classes d’un document.

    Conclusions

    Références

     

    XML Query Requirements

    W3C Working Draft 03 November 1999

    http://www.w3.org/XML/Group/1999/11/xmlquery-req19991103

    Concerto esprit project

    Conceptual indexing, querying and retrieval of digital document

    http://concerto.ccl.umist.ac.uk (surtout la partie evaluation), 1999

     

     

    Annexe 1 : synthèse sur les langages de requêtes

    On compare ici différents langages de requêtes afin d’élaborer les types de requêtes auxquelles le système devrait savoir répondre. Il faut cependant garder à l’esprit que des langages de type XQL/SQL sont des langages principalement structurels : si quelque chose peut être inféré (sur des bases sémantiques) d’un document XML, ces langages ne devraient pas pouvoir en tenir compte. Sans doute cela évoluera-t-il mais de manière détachée d’XML.

    XML-QL et XQL WG

    Il s’agit de deux langages de requêtes pour XML (le second en étant au stade des spécifications).

    Des requêtes avec des chemins arbitrairement complexes dans la structure du document

    Du pattern matching,

    Des parties fixes et des parties variables

    Des expressions régulières dans les balises

    La construction de fragments de documents à partir des résultats de la requête.

    À noter aussi un langage de requête, décrit dans le rapport http://www.ics.forth.gr/proj/isst/RDF/rdfquerying.pdf qui permet d'interroger du RDF ainsi que le schéma.

    Les spécifications pour XQL WG sont :

  9. Sélection: retenir un document ou un élément en fonction de son contenu, sa structure ou ses attributs ;
  10. Extraction: en extraire une sous partie ;
  11. Réduction: supprimer les éléments retenus d’un élément (retenu) ;
  12. Restructuration: construire un nouvel ensemble d’éléments satisfaisant la requête ;
  13. Transformation structurelle ;
  14. Combinaison: fusionner plusieurs éléments en un seul.
  15. On peut retenir pour ESCRIRE:

    Tout d’abord, ces langages sont très liés à XML. Il n’est pas souhaitable de reproduire leur comportement là où ils seront bon. Il n’est par exemple pas très utile de reproduire les capacités de transformation visées en Extraction/Réduction/Retructuration/Transformation et Combinaison. Cependant, on introduira sans doute dans la partie générique au projet des possibilités d’assemblage de documents destinées.

    On peut retenir :

    Trouver les documents annotés par un objet O de classe C (ou une sous-classe de C) O:C

    Exprimer des requêtes avec des chemins dans les objets (uniquement les chemins disponibles et non tout Xpath):

    O1.s1.s2 = "XXX"

    O2.s3.s4 = O3.s5.s6

    Trouver la valeur d’une propriété d’un objet :

    O1.s1 = ?X

    ?X est une variable, le fait d’utiliser une variable indique qu’on souhaite avoir la valeur en réponse à la requête, en plus de l’URL du document. Par exemple, je connais le titre je veux l’auteur.

    La question d’utiliser des expressions régulières se pose (en faut-il où fais-t-on l’impasse sachant que ce n’est pas là qu’est la force des représentations de connaissance).

    Une question plus importante est sans doute la possibilité d’ouvrir les résultats des requêtes à des requêtes XML quelconques (lorsque les résultats XQL seront disponibles). Il y a deux types d’ouverture :

  16. ouverture externe (requête sur le contenu ET|OU|… requête sur le document) : elle serait facile à implémenter et peut être traitée de l’extérieur des formalismes (du coup elle n’est plus très intéressante dans la comparaison) ;
  17. ouverture interne (requête sur le contenu DONT certaines variables proviennent d’une requête sur le document et vice versa) : elle serait plus délicate à implémenter, devrait être liée à chaque représentation et .
  18. On peut laisser le premier cas ouvert et voir si l’on est capable de le faire dans les temps du projet. Le second cas devra faire l’objet d’exemples plus détaillés et peut servir à définir un type de requête.

    Ontobroker – Flogic

    Select <var1>…<varn> such that <vari> :<typei>( featurei,j => vali,j ).

    Il s’agit du Select de SQL dont les expressions sont plus que du relationnel puisqu’il s’agit de Prolog avec Feature-terms. [[Message pour Raphaël : regarder SQL, cela peut apporter ici]].

    où vi,j est une variable où une constante.

    On peut retenir pour ESCRIRE:

    Sans doute le même type de schéma.

    Dans notre cas, une constante pourra être un objet ou un nœud d’un graphe ou un graphe ; un type pourra être remplacé par une classe (ou une conjonction de classes).Le langage de contraintes sur les traits devra aussi être exprimé plus complètement (en F-logic il est défini par un prédicat).

    ODMG

     

    OQL est fortement basé sur SQL :

    – select/from/where ;

  19. distinct (ensemble), average ;
  20. sous-requête ;
  21. path.
  22. select distinct struct ( name : x.name, pbp : (select y from x.parent where y.salaire > 10) )

    from Person x

    where x.age > 12

    select p from Persons p, Flowers f where f.name = p.name

    On peut retenir pour ESCRIRE:

     

    Search 97 (Verity)

    Search 97 permet au niveau des comparateurs de base:

  23. comparaisons sur les types de données numériques (et date),
  24. joker (troncature droite, gauche ou milieu),
  25. recherche de proximité phonétique,
  26. recherche sur la racine des termes après lemmatisation (grâce à l'opérateur STEM),
  27. recherche par concepts (topics), s'appuyant sur un arbre de concepts regroupant les termes ou expressions sous la forme d'une structure hiérarchique en affectant des poids aux différentes branches et en reliant les branches entre elles. La recherche par concepts consiste, après sélection des concepts, à générer une requête avec pondération des critères et à exploiter la structure de l'arbre pour calculer la pertinence des réponses.
  28. Ces opérateurs de base sont assemblés à l’aide d’opérateurs booléens et de recherche de proximité textuelle avec recherche sur expression (adjacence), dans une phrase ou dans un paragraphe, distance paramétrable avec ordre imposé ou non,

    Il permet aussi de la recherche par similarités (i.e. Query by Example),

    On peut jouer sur l'analyse de la pertinence en indiquant au moteur les choix préférentiels pour la pondération des résultats (grâce à l'opérateur de cumul (ACCRUE)).

    Pour calculer la pertinence, on utilise 4 paramètres :

  29. les poids affectés,
  30. la densité des termes (nombre d'occurrences et proximité,
  31. la localisation des termes, au début du texte trouvé et dans le titre,
  32. Le résultat de la recherche est présenté trié par ordre décroissant de pertinence, paramétrable par l'utilisateur.

    On peut retenir pour ESCRIRE:

    La recherche par concepts (bien que les concepts utilisés seront définis bien différemment que dans Search 97 où ils se ramènent en fait aux résultats de requêtes prédéfinies). Les autres opérateurs étant plus spécifiquement textuels ou linguistiques, ils ne sont pas du domaine de compétence de l’ARC. Cependant, certains ont tout de même été retenus (joker, ordre).

    L’opportunité d’introduire des opérateurs booléens et lesquels est à discuter mais semble intéressant. Les autres constructions d’assemblage étant typiquement textuels ne sont pas pertinents.

    L’analyse de la pertinence est à étudier de plus près.

    Trec – Text retrieval conference (YT)

     

    Trec est une compétition de moteurs de recherche plein texte. Sa particularité est que les requêtes sont aussi exprimées de manière plein texte (balisé). Trek utilise les balises suivantes (qui contiennent du texte libre) :

    Num : numéro

    Title : titre

    Desc : description de la réponse recherchée en lange naturelle

    Narr : précision de la description (en général décrit un ensemble d’exemples pertinents et un ensemble d’exemples non pertinents).

    http://trec.nist.gov/data/topics_eng/index.html

    On peut retenir pour ESCRIRE:

    Tout cela est vraiment trop textuel.

     

    Annexe 2 : caractéristiques qualité (vues par Concerto/ISO 9126)

    Voici les caractéristiques décrites dans le document Concerto cité plus haut. Il s’agit les deux premiers niveaux d’un arbre à développer en cas de besoin. En regard sont notés les critères plus adaptés à Escrire.

    In more detail, the quality characteristics, and first level sub-characteristics, defined by ISO are as follows. Definitions may be found in ISO 9126-1nd, from which quotations in the following are taken. These characteristics are expected to be treated as normative, although it is recognised that there may be particular differences for particular evaluations. However, most variation is intended to occur at lower levels of sub-characteristics.

    Functionality

    "The capability of the software to provide functions which meet stated and implied needs when the software is used under specified conditions."

    Suitability

  33. Accuracy
  34. Interoperability
  35. Security
  36. Compliance

Reliability

"The capability of the software to maintain its level of performance when used under specified conditions."

Usability

"The capability of the software to be understood, learned, used and liked by the user, when used under specified conditions."

  1. Understandability
  2. Learnability
  3. Operability
  4. Attractiveness
  5. Compliance

Efficiency

"The capability of the software to provide the required performance, relative to the amount of resources used, under stated conditions."

Maintainability => inutile dans Escrire

"The capability of the software to be modified. Modifications may include corrections, improvements or adaptation of the software to changes in environment, and in requirements and functional specifications."

Portability => inutile dans Escrire

"The capability of the software to be transferred from one environment to another."

  1. Adaptability
  2. Installability
  3. Co-existence
  4. Replaceability
  5. Compliance

It is to be noted that, in terms of quality in use, characteristics are interdependent. That is, the assessment of quality in use may, for example, depend on an inter-relation of functionality, reliability and efficiency; or operability may depend on suitability, changeability, adaptability and installability.

 

Annexe 3 : canevas de fiche d’évaluation

L’idée est de se représenter comment les données des évaluations brutes pourront être visualisées mais aussi comment répartir les tests dans chaque jeu de test. Une table telle que celle-ci est à produire pour les évaluations objectives et une autre pour les évaluations subjectives.

Critère

Requête

Couverture

(booléen)

Rappel

(%)

Précision

(%)

Performance

(complexité)

Ordre

(accord ?)

Agrégation

(?)

Sélection

           

- égalité

           

- énum.

           

- reg. exp.

           

- interv.

           

- class.

           

- contr.

           

Appart.

           

Combin.

           

Jointure

           

Proximité

           

Classif.

           

Ordonnan.

           

La performance devra s’apprécier en faisant varier par 10, 100, 1000 la taille des données (requête+base) et en évaluant la variation résultante.

Peut-être, l’ordre est-il à juger en fonction des critères d’ordonnancement (et il peut l’être sur plusieurs critères : rappel/précision des 5 premiers, critère d’accord à définir – p.ex. distance d’édition). Si cette évaluation est indépendante des types de requêtes (ce qui est vrai si les stratégies d’ordonancement ne sont pas définies de manière inductive sur les requêtes), on peut évaluer l’ordonancement dans un autre tableau :

Critère

Ordre

Rappel

(%)

Précision

(%)

Accord

(e-distance)

Agrégation

(?)

Satisfaction

       

Spécificité