Manipulations de contextes dans les Strates-IA

Nous présentons dans la première partie de ce chapitre la notion de contexte dans un système de représentation de documents audiovisuels en Strates Interconnectées par les Annotations. Un élément du graphe << dans le contexte >> d'un autre élément est une extrémité d'un chemin partant de ce dernier. Afin de contrôler et de manipuler les contextes, nous mettons en place la notion de graphe potentiel et un algorithme d'opérationalisation de la recherche de contextes. Dans la deuxième partie du chapitre, nous définissons les graphes potentiels caractérisés pour la manipulation de contextes, ainsi que quelques outils fondamentaux d'exploitation contextuelle des Strates-IA. Nous présentons alors quelques exemples d'utilisation de ces outils pour l'exploitation d'une base de documents audiovisuels annotés suivant les Strates-IA.

   
Contextes dans les Strates-IA

Un début de description

Nous présentons ici un exemple audiovisuel extrait du journal de France 2 du 13 juillet 1996¹. La figure 2.1 présente une vue globale du document : le journal est composé d'un indicatif, d'une ouverture², et de quelques reportages à chaque fois introduits par le présentateur. Le second de ces reportages a pour sujet la visite de Nelson Mandela à Paris à l'occasion du 14 juillet, et peut se décomposer (avec au moins une image par plan) en un lancement du sujet ; une introduction présentant la rencontre de Mandela et Chirac au château de Rambouillet ; une rappel de la rencontre de Mandela et Mitterrand quelques années plus tôt ; une rétrospective sur la vie de Mandela en Afrique du Sud avec sa condamnation, ses années de prison et sa libération ; et enfin une conclusion dans laquelle Mandela et Chirac marchent dans les allées du château de Rambouillet.

  

Figure 2.1: Vue d'ensemble du journal télévisé : la ligne de temps supérieure présente les grandes parties du journal (indicatif, ouverture, reportages), la ligne de temps inférieure détaille le contenu du reportage sur la visite de Nelson Mandela à Paris. Les suites d'imagettes se lisent de haut en bas et représentent les différents plans contenus dans le reportage

La figure 2.2 présente une vue d'un début d'annotation³ du journal télévisé de la figure 2.1. Les UAV sont représentées par des cadres, dans lesquels les bornes temporelles sont indiquées en bas à droite et font référence sauf indication contraire au même fichier. Les EA annotant les UAV sont représentés par leur nom et le cas échéant leurs attributs et les flèches représentent les relations élémentaires. Chaque UAV possède un numéro-identificateur unique pour le flux. On notera la double structuration du journal télévisé en ses composantes, et du document en séquences, plans, et autres documents, ainsi que la relation élémentaire mise en place entre l'EA < Extrait d'archive > et un EA < Plan > d'un autre document. Cette relation élémentaire permet donc une structuration inter-documentaire de l'annotation.

  

Figure 2.2: Une vue << emboîtée >> de l'annotation d'un journal télévisé

La figure 2.3 présente une base de connaissances correspondant à l'annotation décrite figure 2.2. On notera que pour des raisons de commodité de notation, nous avons << factorisé >> certains attributs dans certains EAA, tel que Nom:TTexte dans < Personnalité > ou SP:TSpectre (pour un spectre sonore) dans < Son > . Il est alors admis que les EAA qui en sont spécialisation possèdent ces attributs.

  

Figure 2.3: Un exemple de base de connaissances

La figure 2.4 présente un extrait du graphes des Strates-IA correspondant à une partie de l'annotation de la figure 2.2 et à une partie de la base de connaissances de la figure 2.3. Les bases temporelles correspondent à deux flux, on a également représentées les portées temporelles des UAV sur les flux et leurs EA primitifs.

  

Figure: Extrait de graphe Strates-IA d'annotation du journal télévisé correspondant à la figure 2.2. Une partie de la base de connaissances est représentée, ainsi que quelques unités audiovisuelles (UAV n^o 1, 4, 8, 10, 11, 13, 14, 15) et les éléments d'annotation qui les annotent. Les lignes de temps représentent les deux flux considérés et les unités audiovisuelles y sont décrites avec leurs éléments d'annotation primitifs

   
Une première approche du contexte

Notre démarche se base sur une approche d'annotation de parties de documents audiovisuels à l'aide d'éléments d'annotation, exprimant des objets d'intérêt audiovisuels. Les EA sont plus particulièrement caractérisés par leur nom, à savoir le terme d'annotation, le mot-clé utilisé pour décrire ce que l'annotateur tient à exprimer à propos de la partie du document, en lien avec les relations entre EA, qui permettent de structurer l'annotation, mais également de préciser les termes utilisés. Cette écriture sur le document va ensuite donner lieu à une lecture, c'est à dire à une interprétation de l'annotation. Nous nous intéressons successivement aux trois types d'objets des Strates-IA et aux différents facteurs selon lesquels on peut les interpréter, c'est à dire à leurs interprétants dans le graphe des Strates-IA.

Unités audiovisuelles.

Nous avons vu dans la partie 3 que deux contextes audiovisuels pouvaient être considérés, le contexte temporel et le contexte sémantique.

Intéressons-nous à une unité audiovisuelle mise en place au cours d'une activité d'annotation. Cette UAV est pour le système un représentant d'une partie de flux audiovisuel, puisqu'elle permet d'y accéder de façon non ambiguë. Unité bivalente, l'UAV est donc tout d'abord décrite du côté du document audiovisuel par la partie de flux qu'elle délimite, tandis que du côté du système, c'est cette partie de flux qui est décrite par les annotations liées à l'UAV⁴. Comme de plus l'UAV est insérée dans le graphe des Strates-IA, et peut être appréhendée et manipulée en tant que telle, nous la considérons comme ayant une existence propre, et pouvant être elle-même décrite par son annotation. La partie de flux est alors documentée par la description de l'UAV.

Une unité audiovisuelle est d'abord décrite par les annotations qui lui sont liées, donc les EA en relation d'annotation R_a avec elle. Cela correspond à un contexte << immédiat >>, qui est le contexte de l'UAV. Si nous considérons un contexte temporel immédiat, une UAV est également décrite par les EA annotant des UAV qui la contiennent temporellement. Par exemple l'UAV 7 de la figure 2.2 est contenue dans l'UAV 3, on peut donc dire suivant ce contexte (cette relation temporelle), qu'elle est également décrite par les EA de l'UAV 3 (par exemple par < Journal Télévisé > ). Inversement, l'UAV 3 peut, suivant la relation inverse être décrite par les EA annotant l'UAV 7, qu'elle contient temporellement (par exemple par < Bruno Masure > ). Nous nous trouvons donc en présence de deux contextes temporels immédiats, basés sur l'inclusion temporelle de parties de flux. Si nous considérons les autres relations temporelles entre UAV, il devient possible de définir tous les contextes temporels << non immédiats >> utiles, par exemple la superposition (overlap), la jonction, etc. Toutes les combinaisons de relations temporelles telles que celles définies par [12] peuvent donc participer à la recherche des contextes temporels d'une unité audiovisuelle.

Nous définissons l'annotation contextuelle d'une UAV comme les éléments d'annotation dont on peut, en définissant un contexte, considérer qu'ils annotent cette UAV⁵. Par exemple, en définissant le contexte d'inclusion temporelle, on peut considérer que toutes les annotations d'une UAV annotent également toute UAV qui la contient temporellement. Les UAV globales jouent donc un rôle dans la détermination des unités locales, inversement, les unités locales permettent de compléter la description des unités globales.

Si le contexte temporel est lié au flux et à sa temporalité (il est toujours possible de comparer temporellement deux UAV définies sur le même flux), le contexte sémantique prend quant à lui appui sur les relations entre annotations, c'est à dire sur la structure de l'annotation. Par exemple sur la figure 2.2, le contexte structurel suivant la relation nommée par l'EA < Struct Doc. > permet de définir que l'UAV 9 peut être annotée contextuellement par des EA annotant l'UAV 3. Si on suit un lien de structuration d'annotation basé sur < Focus Vidéo > , alors l'UAV 7se trouve dans le contexte de l'UAV 3. Enfin, si nous considérons un lien basé sur < Focus Vidéo > , une co-occurence temporelle d'EA et < Struct Doc. > , alors l'UAV 3 se trouve dans le contexte de l'UAV 7. Certes ce contexte est équivalent au contexte d'inclusion temporelle défini précédemment, mais sa signification est différente, puisqu'ici on peut décrire le contexte par le chemin suivi dans le graphe d'annotation.

La dernière possibilité d'annotation contextuelle d'une UAV dépend encore de ses annotations, mais surtout de leurs liens avec la base de connaissances. En effet, annotée par un élément d'annotation, l'unité audiovisuelle bénéficie encore des explications sur la signification de cet élément définies par le réseau de la base de connaissances. Ainsi par exemple une unité annotée par < Zoom Avant > pourra également être considérée comme l'étant par < Mouvement caméra > , du fait de la relation de spécialisation dans la base de connaissances entre < EAA:Mouvement caméra > et < EAA:Zoom Avant >. De la même manière, une UAV annotée par < Nelson Mandela > peut l'être également par < Afrique du Sud > du fait de la relation pays entre < EAA:Nelson Mandela > et < EAA:Afrique du Sud >. Ce type d'annotation contextuelle profite simplement des relations de la base de connaissances, à laquelle l'UAV est connectée dans le graphe par l'intermédiaire des EA qui l'annotent.

Eléments d'annotation.

Après nous être intéressés à l'annotation contextuelle des UAV, c'est à dire à leur contexte dans le graphe Strates-IA, nous pouvons appliquer un raisonnement similaire sur les éléments d'annotation. En effet, ceux-ci peuvent être également interprétés et manipulés et ici encore, plusieurs contexte peuvent être définis.

Un EA peut être considéré seul, auquel cas son interprétation sera contrainte, d'une part par l'UAV (et le flux) qu'il annote, c'est à dire par son contexte audiovisuel, mais aussi par les relations que l'EAA dont il est inscription dans le flux entretient dans la base de connaissances.

Par exemple, figure 2.2 l'EA < Pano Gauche-Droite > annotant l'UAV 8 s'explique d'abord par l'UAV 8elle-même, et par la partie de flux à laquelle elle correspond, mais aussi par l'EAA < EAA:Pano Gauche-Droite > et les relations de celui-ci avec < EAA:Mouvement caméra >, ses diverses abstractions et autre spécialisations (e.g. < Zoom avant > ). Si on considère les relations temporelles entre UAV, donc entre les EA qui les annotent, ceux-ci peuvent s'expliquer mutuellement (par exemple le fait qu'un EA < Meurtre > soit temporellement situé après un EA < Insulte > ).

Si l'EA est considéré dans ses relations avec d'autres EA, il peut s'interpréter du fait par exemple de la présence d'autres annotations dans l'UAV (< Pano Gauche-Droite > annote avec < Plan > l'UAV 8). Les relations élémentaires qu'il entretient avec d'autres EA permettent également de mettre en place un contexte d'interprétation. Par exemple dans l'UAV 8, < Pano Gauche-Droite > est en relation par l'intermédiaire de < FocusVidéo > avec deux EA < Groupes > , eux mêmes précisés par leurs relations avec leurs constituants ; si < Meurtre > est en relation élémentaire avec < Don Gomès > , alors son interprétation est plus contrainte.

Encore une fois, il nous apparaît que la lecture et l'interprétation des annotations peut se faire en prenant en compte leurs différents contextes dans le graphe des Strates-IA, lesquels se basent soit sur des relations temporelles par le biais des UAV, soit en tirant partie de la structure de l'annotation, soit de celle de la base de connaissances. Toute connaissance inscrite dans le flux comme élément d'annotation y est en effet contextualisée aussi bien temporellement que par les relations explicites que l'on met en place. De plus, ce sont les contextes hors du flux, dans la base de connaissances qui en prescrivent la signification de départ.

Eléments d'annotation abstraits.

Un élément d'annotation abstrait existe donc en premier lieu en l'absence d'annotation, et s'explique tout d'abord par le terme qui est choisi pour son nom, qui sera toujours interprétable et interprété, pas obligatoirement de façon unique⁶. C'est pourquoi, dans une base de connaissances comme dans un thésaurus, mais à des degrés de figement divers, les relations entre concepts (ou termes) permettent de spécifier la signification qu'il convient de mettre sous chaque terme, sous la forme de contraintes d'interprétation. La valeur sémantique d'un concept ou d'un terme dépend alors fortement du contexte dans lequel il se trouve au niveau des connaissances.

S'il est utilisé, un élément d'annotation abstrait est inscrit dans le flux sous la forme d'un élément d'annotation. La valeur en contexte (dans le flux) de l'EA peut alors naturellement varier (puisque des relations non prévues sont possibles) par rapport à la valeur hors-contexte (hors du flux) de l'EAA. En retour, sous la forme d'exemple d'utilisation, l'EA peut par sa signification contraindre l'interprétation de l'EAA, y compris du fait de sa position dans l'organisation de l'annotation. L'EAA est donc également décrit par le contexte de ses instances.

.

Nous l'avons vu en étudiant rapidement les possibilités d'interprétation contextuelle dans un graphe d'annotation Strates-IA, tous les objets utilisés dans ce graphe peuvent s'interpréter en fonction de la position qu'ils y occupent, c'est à dire en fonction des relations qu'ils peuvent entretenir avec d'autres objets. Le graphe des Strates-IA est un réseau de sens, avec des objets syntaxiques banalisées -- les UAV -- qui peuvent par conséquent bénéficier d'une sémantique associée à toute annotation contextuelle ; des termes d'annotation -- les EA -- qui forment un texte écrit sur le document, et à ce titre sont interprétables en fonction de relations implicites comme explicites dans l'annotation elle-même ; enfin, des termes abstraits d'annotation -- les EAA -- décrits hors du flux, et prenant éventuellement un sens nouveau dans celui-ci. Il apparaît qu'interpréter un objet de ce graphe n'est possible qu'en considérant son contexte, par exemple en extrayant un sous-graphe qui lui soit lié, lequel contexte servira d'interprétant local. Le contexte chez nous sera donc principalement lié à l'idée de chemins dans le graphe, lesquels seront fortement liés à la tâche courante des utilisateurs.

Ceci nous permet de justifier a posteriori notre volonté de considérer le système comme un graphe, car alors tous les liens de contextes entre sommets quelconques s'expriment de la même manière et de façon naturelle, ce qui ne serait pas forcément le cas avec d'autres formalisations.

Définition du contexte

Soit un système Strates-IA SIA = < O, R, G, C >tel que nous l'avons défini au chapitre précédent, avec G = < S, A,$\mu$,$\nu$ >.

Soit un objet o $\in$ O (O l'ensemble des objets) correspondant à un sommet de G s $\in$ S et $\mu$(s) = o (tel qu'il serve d'étiquette pour le sommet s). Un contexte de o est un objet o' de O tel qu'il existe un chemin du graphe G permettant de mettre en relation les sommets étiquetés par o et o'. On dira que o' est en contexte avec o.

Le contexte global de o est l'ensemble des objets o_ien contexte avec o.

Cette dernière définition est peu opératoire en l'état. En effet, G étant connexe, tout objet est en relation avec tout autre objet par l'intermédiaire d'un ou plusieurs chemins. Ceci exprime simplement le fait que le système est cohérent et unique, c'est à dire qu'on met en place un ensemble de connaissances de description (EAA) liées entre elles, qui s'expliquent mutuellement, ce qui est également le cas des connaissances utilisées par les descriptions (EA et UAV). Toutes les relations contextuelles entre objets leur permettent de s'expliquer (de se définir) mutuellement (cf. plus haut).

Afin cependant de contrôler les contextes pour qu'ils puissent exprimer des relations utiles entre éléments, il convient de mettre en place des outils permettant de les définir et de les manipuler. Les graphes potentiels nous permettront de définir formellement les contextes et de fournir le contrôle voulu. Avant de les présenter, il nous faut présenter ce qu'est la similarité entre objets des Strates-IA.

   
Sur la similarité entre objets

Nous définissons dans cette partie comment il est possible de comparer deux objets des Strates-IA.

.

Pour chacun des types d'attribut de E_a, on définit une ou plusieurs fonctions de similarité, c'est à dire qu'on associe à chaque type a $\in$ E_a un ensemble non vide de fonctions f_ai, i $\in$ [1..n] prenant en entrée deux valeurs d'attributs (v₁, v₂) $\in$ E_V(a) x E_V(a) et rendant en sortie une valeur booléenne 0 ou 1.

.

Par exemple, l'unique fonction de similarité associée aux attributs de type Type sera : f_Type1 : E_V(Type) x E_V(Type) $\longrightarrow$ {0, 1} avec f_Type1(t₁, t₂) = 1 si t₁ = t₂ et f_Type1(t₁, t₂) = 0 sinon.

Il y a lieu de définir plusieurs fonctions de similarité pour un type d'attribut donné afin prendre en compte les << vraies >> mesures de similarité liées aux primitives images et son (calculées). Par exemple, on pourra imaginer de comparer deux signatures de points d'intérêt suivant plusieurs méthodes ; ou bien on comparera deux textes soit de façon exacte, soit sur quelques-uns de leurs termes représentatifs (par exemple ils contiennent tous les deux les termes Chirac et Paysans).

Nous nous restreignons ici à des fonctions à valeurs booléennes afin de simplifier les calculs, c'est à dire que nous n'envisageons pas a priori d'ordonner des résultats : soit une primitive est jugée similaire à une autre, soit non.

.

Une fois définies les comparaisons entre attributs, nous pouvons mettre en place des comparaisons au niveau des objets. Une fonction de similarité entre objets est représentée par un ensemble de couples {(TypeAttribut,FonctionSimilarité)}, elle aura pour argument un couple d'objets (o₁, o₂) $\in$ O x O et rendra des valeurs booléennes.

Son principe est ici le suivant : pour chacun des types d'o₁, si il n'existe pas d'attribut de même type dans o₂ alors retourner 0sinon comparer les valeurs d'attributs avec la fonction de similarité ad-hoc. Si le résultat est 1 alors passer à l'attribut suivant, sinon retourner 0. Quand tous les attributs de o₁ sont passés en revue, retourner 1.

Cette fonction n'est donc pas symétrique, le résultat de la comparaison de o₁ avec o₂ ne sera pas forcément le même que celui de la comparaison de o₂ avec o₁.

.

Une fonction de comparaison simple est celle qui compare par exemple deux EA, en vérifiant que leurs types et noms sont les mêmes. Il est possible d'y ajouter une vérification que deux valeurs de primitives sont considérées comme similaires, ce qui nous permet alors de comparer des EA exprimant des primitives issues du traitement du signal.

Par exemple, on pourra comparer deux objets

o₁ = < (Type, EA),(Nom, Plan),(SignaturePointsInteret, sign₁) >

et

o₂ = < (Type, EA),(Nom, Plan), DateTournage : 18031998,(SignaturePointsInteret, sign₂) >

à l'aide de la fonction de comparaison définie par

{(Type, cmpType),(Nom, cmpNom),(SignaturePointsInteret, cmpSPI₂)}

si cmpType et cmpNom sont des fonctions de comparaison exactes, et cmpSPI₂ permet de comparer des signatures de points d'intérêt.

.

Remarquons que notre définition des similarités entre objets ne se prétend pas définitive, et qu'il est possible de définir autant de principes de similarité que l'on veut, pourvu que le résultat soit booléen.

Nous choisissons des similarités booléennes entre nuds (et non par exemple des similarités << floues >> à valeur dans [0, 1]) car nous chercherons à exprimer des comparaisons entre graphes en terme d'isomorphismes. Alors il faudra comparer des nuds de façon stricte.

Graphes potentiels pour exprimer des contextes

Si nous revenons à notre problème, celui-ci est donc le suivant : étant donné un objet o d'un système Strates-IA, comment contrôler l'ensemble des contextes qu'on pourra lui associer ? Pour répondre à cette question, il nous faut être capable de décrire dans le graphe un chemin de façon abstraite, c'est à dire hors du système, aussi bien de façon << syntaxique >> (les sommets et les arcs qui les lient) que << sémantique >> (les étiquettes associées aux sommets et aux arcs).

Il s'agit tout d'abord de décrire l'ossature du chemin, c'est à dire les sommets qui le composent, et les arcs entre ces sommets. La deuxième étape consiste en l'étiquetage de l'ossature du graphe (ou chemin virtuel), à l'aide d'objets << abstraits >> pour étiqueter les sommets, et d'un ensemble de relations étendues pour prendre en compte les relations temporelles.

Objets abstraits.

Un objet abstrait est un objet des Strates-IA (qui possède donc a minima un type), dont tous les autres attributs peuvent ne pas avoir de valeur, ou avoir des valeurs négligées dans les faits, ce qui revient d'une certaine façon à l'abstraire.

En effet, il s'agira de comparer les chemins, décrits de façon abstraite, aux chemins du graphe, donc de comparer les étiquettes, c'est à dire les objets abstraits aux objets concrets. Pour cela, une fonction de similarité entre objets sera utilisée, laquelle ne prendra en compte obligatoirement que le type de l'objet abstrait. On conçoit donc que si on ne considère que le type, il n'y ait pas lieu de définir d'autres attributs, ou que si ceux-ci sont définis, alors ils ne seront pris en compte que si la fonction de similarité le fait.

Par exemple, une UAV abstraite pourra être un objet u = < (Type, UAV) > et associée à une fonction de similarité f ne prenant en compte que l'attribut type, pourra être comparée aux objets de O, rendant vrai pour toutes les UAV de O, et fauxpour les EA et les EAA. Un EA e = < Type, EA) > pourra être considéré comme équivalent à tous les EA si la même fonction de similarité lui est associée. Par contre, un objet e' = < Type, EA),(Nom, Chirac) > associé à une fonction comparant exactement Type et Nom sera considéré équivalent à tous les EA inscriptions dans le flux de l'EAA < EAA:Chirac >.

Un objet abstrait associé à une fonction de similarité qui lui soit adaptée est appelé objet générique. Comme le plus souvent la généricité portera sur l'attribut Nom, nous valuerons celui-ci par *, * pouvant prendre l'ensemble des valeurs de E_V(Nom). Par exemple l'EA générique paradigmatique sera < * > , l'EAA sera < EAA:* >, et en étendant à l'UAV, on aura < UAV:* > .

Relations entre objets.

Les relations entre objets génériques sont les mêmes que les relations que nous avons déjà définies. Un EA générique sera par exemple en relation d'annotation R_a avec une UAV générique. Nous introduisons cependant un ensemble de relations supplémentaires possibles entre éléments d'annotation génériques, qui sont toutes les relations temporelles possibles entre parties de flux, typiquement les treize relations de Allen (before, after, touches, ovverlaps, etc.).

Les relations temporelles entre EA génériques permettent de définir des contextes temporels en étendant la notion de chemins virtuels. Soit R_T l'ensemble des relations temporelles.

.

La figure 2.5 présente un ensemble de chemins potentiels. Gp₁ par exemple décrit un chemin virtuel entre un EA générique < Document > et une UAV totalement générique, le chemin passant par un EA < StructDoc > et un EA totalement générique. Le graphe Gp₂ décrit un chemin suivant une relation de spécialisation entre un EAA < EAA:Homme politique français > et un EAA totalement générique. Le graphe Gp₃décrit un chemin contextuel potentiel sur le même schéma que Gp₁. Gp₄ décrit un chemin contextuel potentiel avec une composante temporelle signifiant que l'EA générique < Plan > doit être en relation d'inclusion temporelle avec un EA générique ayant un attribut Auteur avec << M. Laroche-joubert >> pour valeur. Cela signifie d'une part que l'UAV qu'annote < Plan > doit être incluse temporellement dans l'UAV qu'annote e, d'autre part que ce dernier EA générique est un EA associé à une fonction de similarité opérant sur les attributs Type et Auteur.

  

Figure 2.5: Quelques graphes potentiels

Associations de chemins

La description d'un chemin virtuel peut être précisée. Plus particulièrement, il est possible de spécifier pour chacun de ses éléments un contexte, c'est à dire un autre chemin contextuel, et ce de façon récursive. Ce principe est illustré par le graphe Gp₅ figure 2.5 où l'EA < Groupe > faisant partie du chemin entre une UAV et un EA totalement générique est spécifié par sa relation contextuelle avec un EA < Pano Gauche Droite > .

Il apparaît donc qu'un chemin virtuel est décrit par une ossature étiquetée de chemin, et que récursivement chacun des sommets du chemin peut être précisé par d'autres chemins, dont les sommets peuvent être à leur tour précisés, etc. Nous pouvons alors définir ce qu'est un graphe potentiel.

Graphe potentiel.

Un graphe potentiel est un graphe permettant de spécifier abstraitement des contextes, des relations contextuelles entre sommets d'un graphe Strates-IA.

Soit un système Strates-IA G_SIA = < O, R, G, C > avec G = < S, A,$\mu$,$\nu$ >. Alors soit O_p l'ensembles des objets du graphe potentiel, définis suivant les mêmes contraintes d'attributs et de valeurs que les objets de O. Soit f_Op l'application qui à tout objet o_p $\in$ O_p associe⁷ une fonction de similarité f_op permettant de le comparer aux objets de O. Le degré de généricité d'un sommet du graphe potentiel dépendra donc de la fonction de similarité qui lui est associée. On peut alors comparer tout objet de O_p (i.e. du graphe potentiel) à des objets de O (i.e. du graphe général des Strates-IA) : $\forall$o_p $\in$ O_p, $\forall$o $\in$ O, f_Op(o_p, o) = 1 si f_op(o_p, o) = 1 (si o_p est jugé similaire à o suivant la fonction de similarité qui lui est associée), = 0 sinon.

Un graphe potentiel est défini comme G_p = < O_p, f_Op, R_p, G_Gp, C_p > avec O_p ensemble des objets génériques du graphe potentiel, f_Op associant à tout objet générique une fonction de similarité, R_p = R $\cup$ R_T, G_Gp = < S_p, A_p,$\mu_{p}^{}$,$\nu_{p}^{}$ >avec S_p ensemble des sommet du graphe potentiel, A_p ensemble de ses arcs, $\mu_{p}^{}$ et $\nu_{p}^{}$ associant respectivement aux sommets et aux arcs des étiquettes issues de O_p et de R_p. C_p est l'ensemble des contraintes sur les relations du graphe potentiel, qui sont presque équivalentes à celles contenues dans C à la différence que les relations entre EA génériques peuvent être soit élémentaires, soit appartenir à R_T.

Instancier les graphes potentiels pour réaliser les contextes.

L'instanciation d'un graphe potentiel Gp dans un graphe Strates-IA G_SIA correspond à la recherche dans ce dernier des sous-graphes qui soient équivalents à Gp suivant les contraintes de structure (sommets et arcs) et les contraintes de similarité entre étiquettes de sommets et de relation. Une instance d'un graphe potentiel est un sous-graphe de SIA qui lui est équivalent suivant ces contraintes.

Plus formellement, si on a G_SIA = < O, R, G, C > avec G = < S, A,$\mu$,$\nu$ > et
G_p = < O_p, f_Op, R_p, G_Gp, C_p > avec G_Gp = < S_p, A_p,$\mu_{p}^{}$,$\nu_{p}^{}$ >. Alors les instances de G_p dans G_SIA sont les sous-graphes g_i = < S_i, A_i,$\mu_{i}^{}$,$\nu_{i}^{}$ > _{i $\in$ [1, n]} de G (avec $\mu_{i}^{}$ (resp. $\nu_{i}^{}$) la restriction de $\mu$ (resp. $\nu$) à S_i (resp. A_i)) tels que pour tout i $\in$ [1, n] il existe une fonction bi-univoque f_i : Sp $\longrightarrow$ S_i avec :

• a = (x, y) $\in$ A_p $\Leftrightarrow$ a' = (f_i(x), f_i(y)) $\in$ A_i et $\nu_{p}^{}$((x, y)) = $\nu_{p}^{}$( (f_i(x), f_i(y)) )
• $\forall$x $\in$ S_p  f_Op($\mu_{p}^{}$(x),$\mu_{i}^{}$(f_i(x))) = Vrai.

Par exemple les graphes potentiels de la figure 2.5 s'instancient dans le graphe défini par les figures 2.2 (pour les UAV et EA) et 2.3 (pour les EAA) de la manière suivante : Gp₁a quatre instances, Gp₂ et Gp4 en ont trois, Gp₃ une seule, et enfin Gp₅ permet de définir quatre instances.

On note I(G_p, G_SIA) l'ensemble des instances de G_p dans G_SIA.

Hypothèse de la correspondance initiale.

Le problème de la recherche des instances d'un graphe potentiel dans un graphe Strates-IA se ramène à la recherche des isomorphismes de sous-graphe partiels entre G_p et G_SIA. Ce problème est dans le cas général NP-complet, c'est pourquoi nous ajoutons comme contrainte supplémentaire sur tout graphe potentiel qu'un au moins de ses sommets sera associé de façon unique à un des sommets de G_SIA. Ainsi, $\exists$(x, y) $\in$ S_p x S tel que $\forall$f_i associée à une instance de I(G_p, G_SIA), f_i(x) = y.

Ce sommet initial du graphe potentiel correspondra par exemple à un objet générique EAA nommé, qui pourra alors être associé sans ambiguïté à l'EAA de la base de connaissances correspondant. Ce sommet pourra également correspondre à une UAV totalement déterminée, ou bien à un EA précis.

La contrainte que nous posons est naturelle : les graphes potentiels servent à exprimer des contextes virtuels entre sommets d'un graphe Strates-IA, tandis que les instances expriment des contextes réels. L'instanciation, la recherche de contextes doit alors se faire à partir de sommets connus dont on cherchera le contexte. Cette recherche sera locale dans le graphe, c'est à dire que son ou ses points de départs seront connus, à la différence d'une approche qui chercherait des motifs de façon globale.

Parmi les graphes potentiels de la figure  2.5, seuls Gp₂ et Gp₄ sont valides au sens de la restriction que nous venons de poser. Les autres graphes potentiels peuvent devenir valides, pour peu qu'on spécifie explicitement certains de leurs sommets comme correspondant à des sommets précis de G, ou bien qu'on les complète par exemple au niveau des EA nommés en les mettant en relation avec des EAA génériques nommés, qui eux peuvent être mis en correspondance non ambiguë avec les EAA de la base de connaissances, comme indiqué sur la figure 2.6. La mise en place de sommets génériques EAA nommés dans les graphes potentiels correspond à une recherche d'annotations dans leur contexte, donc qui partent de ceux-ci.

  

Figure 2.6: Rendre valide des graphes potentiels

Nous évoquerons plus en détail comment les graphes potentiels peuvent être manipulés et rendus valides. Retenons pour l'instant que pour tout graphe potentiel à instancier, on connaît sans calcul au moins une correspondance entre un sommet du graphe potentiel et un sommet du graphe Strates-IA.

   
Instanciation de graphes potentiels

Nous nous intéressons dans cette section à l'instanciation de graphes potentiels du point de vue algorithmique et de la théorie des graphes. Pour présenter la manière dont l'instanciation se réalise, nous allons simplifier notre problème en considérant des graphes étiquetés simplement (et non par des objets Strates-IA avec les contraintes associées). Par contre, les règles de vérification de cohérence utilisées seront décrites dans leur forme générale ; c'est à dire en se plaçant dans le cadre des graphes potentiels définis ci-dessus.

Isomorphismes de sous-graphes partiels

Un graphe G est défini par le couple G = (X, A_X), où X désigne l'ensemble des sommets de G et A_X $\subseteq$ X x X est l'ensemble des arcs de G. x_j est successeur de x_i si (x_i, x_j) $\in$ A_X ; l'ensemble des successeurs de x_i est noté Succ(x_i). x_i est prédécesseur de x_j si (x_i, x_j) $\in$ A_X; l'ensemble des prédécesseurs de x_i est noté Pred (x_i).

Etant donné un graphe G = (X, A_X), un sous-graphe de G est un graphe G' = (X', A_X') tel que X' $\subseteq$ X et X' $\neq$ $\emptyset$ et A_X' = A_X $\cap$ X' x X'. Un graphe partiel de G engendré par le sous-ensemble d'arcs B $\subset$ A_X est le graphe G' = (X, B). Le sous-graphe partiel engendré par X' $\subseteq$ X et B $\subseteq$ A_X' est le graphe partiel de G' = (X', A_X') engendré par B $\subseteq$ A_X'.

.

Le problème de l'isomorphisme est un problème fondamental en informatique. On peut le formuler de la façon suivante : soient deux graphes G_X = (X, A_X) et G_Y = (Y, A_Y). G_X et G_Y sont isomorphes s'il existe une bijection f : X $\longrightarrow$ Y telle que :

$$\forall$$x_i, x_j $$\in$$ X : (x_i, x_j) $$\in$$ A_X $$\Leftrightarrow$$ (f (x_i), f (x_j)) $$\in$$ A_Y

Une autre variante de ce problème appelée problème de l'isomorphisme de sous-graphes partiels connu aussi sous le nom d'inclusion de graphes consiste à rechercher une relation entre G_X et un sous-graphe partiel de G_Y. L'étude de ce problème répond à la question suivante : G_Y contient-il un sous graphe partiel isomorphe à G_X ? c'est à dire existe t-il un sous-ensemble Y' de sommets de Y et un sous-ensemble A_Y'd'arcs tels que | Y'| = | X|, | A_Y'| = | A_X| et il existe une bijection f : X $\longrightarrow$ Y' telle que :

$$\forall$$x_i, x_j $$\in$$ X : (x_i, x_j) $$\in$$ A_X $$\Leftrightarrow$$ (f (x_i), f (x_j)) $$\in$$ A_Y'

Méthodes de recherche d'isomorphismes de sous-graphes

Le problème de l'isomorphisme de sous-graphes se rencontre dans de nombreux domaines au nombre desquels :

• la chimie organique [197] pour la reconnaissance de molécules qui possèdent une sous-structure particulière ;
• le raisonnement à partir de cas pour la recherche de cas dans une base de cas [183,31] ;
• les réseaux sémantiques et les grammaires de graphes [88] ;
• l'apprentissage, où les informations symboliques sont représentées par des graphes de concepts et l'on désire par exemple savoir si un concept est plus général qu'un autre [98,66] ;
• la reconnaissance de formes et la vision par ordinateur, où l'étude de ce problème a été motivée par le désir de retrouver des objets dans des images [60,242,243].

.

Les méthodes développées pour résoudre le problème de l'isomorphisme de sous-graphes peuvent être classées dans l'une des deux approches suivantes.

L'approche basée sur la recherche de cliques⁸ maximales dans un graphe appelé graphe d'association décrivant toutes les correspondances possibles entre sommets de G_X et de G_Y⁹. Dans cette première approche, nous pouvons citer les travaux de [90,169,126] (cités dans [156]). Les algorithmes issus de cette approche sont très généraux, puisque le problème est considéré de façon globale mais peu efficaces dans la pratique de par leur complexité et ne s'appliquent qu'à des graphes de petite taille.

L'approche dite de relaxation, basée sur l'utilisation combinée de méthodes de filtrage et d'algorithmes d'énumération de l'espace des solutions. [136,134] décrivent des algorithmes illustrant cette seconde approche. Ces algorithmes présentent l'avantage de pouvoir s'implanter facilement sur des architectures parallèles et d'utiliser ainsi la puissance des machines multiprocesseurs. La proposition de [230] (que nous avons implanté) est similaire à cette approche : on construit un tableau de dimension N_X x N_Y, où N_X (resp. N_Y) désigne le nombre de sommet du graphe G_X (resp. _Y) en exécutant une procédure récursive ayant ce tableau -- modifié à chaque itération -- pour paramètre. La complexité est alors rédhibitoire pour les graphes de grande taille.  

.

Plus récemment, un algorithme de recherche d'isomorphismes également basé sur la deuxième approche a été proposé par [67], appliqué à des graphes générés aléatoirement et comparé aux algorithmes présentés par [230,156].

De manière informelle¹⁰, cet algorithme est basé sur le principe suivant : pour rechercher toutes les solutions, l'algorithme construit un arbre où chaque sommet représente un isomorphisme partiel et un arc correspond à l'ajout d'une paire de sommets conduisant à un autre isomorphisme partiel de cardinalité supérieure. La racine de cet arbre est l'ensemble vide et la profondeur de l'arbre en cours de construction est directement fonction du cardinal de l'isomorphisme partiel associé. Pendant la construction des solutions, si l'ajout d'une paire de sommets à un isomorphisme partiel (à un sommet de l'arbre) conduit à un état incohérent, alors l'algorithme abandonne toute exploration depuis cet état ; c'est à dire que le chemin s'interrompt sur cet état incohérent. L'algorithme présenté dans [67], s'avère en moyenne efficace grâce à cette technique d'élagage des chemins incohérents de l'arbre des solutions. Son inconvénient principal est cependant son exploration en largeur complète : tous les sommets de l'arbre sont développés en même temps, ce qui multiplie le nombre de sommets à chaque niveau de l'arbre de façon importante. De plus, la présence dans l'arbre de solutions partielles connexes (pouvant être fusionnées) n'est pas gérée, ce qui constitue un autre facteur de multiplication du nombre d'états et nécessite de tester les solutions doublonnées en fin de calcul.

.

Nous proposons une première amélioration de cet algorithme, qui consiste à explorer l'espace des états suivant des directions optimales d'un point de vue du nombre d'états générés.

A chaque étape, c'est à dire à chaque niveau de l'arbre, une direction est déterminée en étendant un seul état à la fois qui est choisi en fonction d'un critère réduisant le nombre d'états nouveaux.

Une deuxième amélioration importante vient de la fusion d'états connexes, réduisant ainsi le nombre d'états au total et évitant la redondance des solutions partielles portées par les sommets de l'arbre.

Ces deux améliorations apportées vont nous permettre de fournir des solutions finales dès qu'elles sont établies, sans attendre d'avoir terminé l'exploration de toutes les solutions possibles. Le reste de cette section est consacré à la présentation de notre algorithme dit de multi-propagation.

Notations et définitions

Nous allons dans cette partie introduire quelques définitions et préciser quelques notations nécessaires pour la description de notre algorithme. Chacune des définitions que nous donnons est illustrée sur la figure 2.7.

  

Figure 2.7: Il existe un isomorphisme de sous-graphe partiel entre G_X et G_Y

Correspondance :

Un couple de sommets [x, y] $\in$ X x Yen relation par f est appelé correspondance valide. Pour une correspondance c = [x, y], le sommet x est l'extrémité initiale ou origine (dans G_X) de c, y est l'extrémité finale ou extrémité (dans G_Y) de c.

Sur l'exemple de la figure 2.7, G_X est isomorphe au sous-graphe G_Y' de G_Y. Une bijection solution f : X $\longrightarrow$ Y' est totalement caractérisée par l'ensemble des correspondances

{[a, 2],[b, 7],[c, 8],[d, 9],[e, 6]}

Graine :

Une graine est une correspondance [x, y] valide donnée par l'utilisateur (correspondance de départ). Dans le modèle des Strates-IA, une graine associe un sommet du graphe potentiel à un sommet connu du graphe Strates-IA, et correspond à l'hypothèse de la correspondance initiale.

On suppose que les correspondances initiales de la recherche d'isomorphisme de sous-graphe partiel présenté figure 2.7 sont les couples [a, 2] et [d, 9] (indiqués en gras), il y a donc deux graines.

Etat :

Soient deux graphes G_X = (X, A_X) et G_Y = (Y, A_Y). Un état e du processus d'appariement des deux graphes est défini par un ensemble de correspondances valides V(e)

 

$$\in$$ (7.1)

et est appelé isomorphisme partiel associé à l'état e. On notera par V_X(e) (resp. V_Y(e)) la projection de V(e) sur X(resp. Y) :

• V_X(e) = {x $\in$ X | $\exists$y $\in$ Y | [x, y] $\in$ V(e)}
• V_Y(e) = {y $\in$ Y | $\exists$x $\in$ X | [x, y] $\in$ V(e)}

Un état composé uniquement d'une graine est appelé état initial. L'ensemble des graines présentes dans un état e est noté R(e) (gRaines) :

 

R(e) = {[x, y]/x soit en initiale avec y} (7.2)

  

Figure 2.8: Deux états e₁ et e₂ dans le processus de recherche d'isomorphisme partiel de G_X dans G_Y

Sur l'exemple de la figure 2.8, on peut considérer deux états e₁ et e₂. e₂, composé de la graine [d, 9] est un état initial. e₁ est composé de deux correspondances G_Y, V(e₁) = {[a, 2],[b, 7]} est l'isomorphisme partiel qui lui est associé. Les projections de e₁ sur X et Y sont respectivement V_X(e₁) = {a, b} et V_Y(e₁) = {2, 7}. On a R(e₁) = {[a, 2]} et R(e₂) = {[d, 9]}. Remarquons que pour un état e correspondant à l'isomorphisme final (5 correspondances), R(e) = {[a, 2],[d, 9]}.

Extension d'un état :

I_X(e) (resp. I_Y(e)) dénote l'ensemble des sommets incidents intérieurement aux sommets de V_X(e) (resp. V_Y(e)). E_X(e)(resp. E_Y(e)) dénote l'ensemble des sommets incidents extérieurement aux sommets de V_X(e) (resp. V_Y(e)). Plus formellement, on a :

• I_X(e) = {x $\in$ X - V_X(e) | $\exists$x' $\in$ V_X(e) | (x, x') $\in$ A_X}
• E_X(e) = {x $\in$ X - V_X(e) | $\exists$x' $\in$ V_X(e) | (x', x) $\in$ A_X}
• I_Y(e) et E_Y(e) peuvent être définis de façon similaire.

On désigne par I(e) (resp. E(e)) l'ensemble des paires de sommets incidents intérieurement (resp. extérieurement) aux sommets de V(e)et défini par :

E(e) = E_X(e) x E_Y(e)  (resp.I(e) = I_X(e) x I_Y(e)).

On note par C(e) l'ensemble des correspondances candidates à l'extension de l'isomorphisme partiel associé à l'état e. La définition de l'ensemble C(e) est réalisée par la séquence suivante (sachant qu'on aura toujours I(e) $\neq$ {}, puisque les graphes considérés dans le cas de notre étude sont connexes) :

 

$$\neq \leftarrow \leftarrow$$ (7.3)

Par exemple pour les états de la figure 2.8, on a C(e₁) = {[c, 8][e, 5][e, 6]} et C(e₂) = {[c, 8],[c, 3]}, si on prend en compte les critères de cohérence définis plus loin.

.

Soit C_X(e) = {x $\in$ X | $\exists$y $\in$ Y | [x, y] $\in$ C(e)} la projection de l'ensemble C(e) sur X. Pour tout sommet x $\in$ C_X(e) on appelle extension de C(e) suivant x la suite des correspondances de C(e) ayant le sommet x comme origine et notée par C(e $\rightarrow$ x). On note par | C(e $\rightarrow$ x)| la dimension (nombre d'éléments) de la suite C(e $\rightarrow$ x) et par $\delta$(e) la dimension de la plus petite extension associée à l'état e :

 

$$\delta \rightarrow \in$$ (7.4)

Pour les états de la figure 2.8, l'extension de e₁ suivant c est C(e₁ $\rightarrow$ c) = {[c, 8]}, et son extension suivant c est C(e₁ $\rightarrow$ e) = {[e, 5][e, 6]}. De la même manière, C(e₂ $\rightarrow$ c) = {[c, 8][c, 3]}¹¹. Les dimensions d'extension sont $\delta$(e₁) = 1 et $\delta$(e₂) = 2.

Critères de cohérence structurelle :

le contrôle de cohérence d'une correspondance [x, y] avec un isomorphisme partiel V(e) consiste à vérifier quelques propriétés structurelles telles que les propriétés de connectivité et d'incidence.

.

Propriété de connectivité : cette propriété exprime le fait que x peut être mis en correspondance avec y si chacun des voisins de x qui est dans V_X(e) est déjà mis en correspondance avec un voisin de y et inversement. D'où les règles qui vérifient le respect de ces contraintes d'adjacence :

• ($\forall$x' $\in$ V_X(e) $\cap$ pred_X(x) $\Rightarrow$ $\exists$y' $\in$ pred_Y(y) | (x', y') $\in$ V(e))
• ($\forall$y' $\in$ V_Y(e) $\cap$ pred_Y(y) $\Rightarrow$ $\exists$x' $\in$ pred_X(x) | (x', y') $\in$ V(e))
• ($\forall$x' $\in$ V_X(e) $\cap$ succ_X(x) $\Rightarrow$ $\exists$y' $\in$ succ_Y(y) | (x', y') $\in$ V(e))
• ($\forall$y' $\in$ V_Y(e) $\cap$ succ_Y(y) $\Rightarrow$ $\exists$x' $\in$ succ_X(x) | (x', y') $\in$ V(e))

.

Propriété d'incidence : les deux règles suivantes permettent de vérifier cette propriété. La première règle indique si le nombre de successeurs de x incidents intérieurement à V(e) est égal au nombre de successeurs de y incidents intérieurement à V(e). La deuxième règle traite les précédesseurs, la troisième et la quatrième sont consacrées au sommets incidents extérieurement.

• (|(succ_X(x) $\cap$ I_X(e)| = |(succ_Y(y) $\cap$ I_Y(e))|)
• (|(pred_X(x) $\cap$ I_X(e)| = |(pred_Y(y) $\cap$ I_Y(e))|)
• (|(pred_X(x) $\cap$ E_X(e)| = |(pred_Y(y) $\cap$ E_Y(e))|)
• (|(succ_X(x) $\cap$ E_X(e)| = |(succ_Y(y) $\cap$ E_Y(e))|)

Propriété d'incidence d'ordre 2 : Cette propriété indique si le nombre de successeurs (resp. prédécesseurs) de xhors de l'état e est bien égal au nombre de successeurs (resp. prédécesseurs) de y :

• (| pred_X(x) $\cap$ (X - E_X(e) - V_X(e))| $\leq$ | pred_Y(y) $\cap$ (Y - E_Y(e) - V_Y(e))|)
• (| succ_X(x) $\cap$ (X - E_X(e) - V_X(e))| $\leq$ | succ_Y(y) $\cap$ (Y - E_Y(e) - V_Y(e))|)

La vérification de la propriété d'incidence d'ordre 2 n'est pas nécessaire, elle permet simplement de couper l'espace de recherche en éliminant les mauvaises extensions d'état (cf. la note 11).

.

Critères de cohérence sémantique : la cohérence sémantique d'une correspondance [x, y] $\in$ C_X(e) x C_Y(e)s'exprime par le calcul d'une similarité entre étiquettes de sommets realisé par la fonction f_SymEtiqNoeud) et étiquettes d'arcs (suivant f_SymEtiqRel) :

• cohérence des sommets : f_SymEtiqNoeud(x, y) = Vrai ;
• cohérence des arcs :
  $$\forall$$(x', y') | x' $$\in$$ V_X(e) $$\cap$$ pred_X(x) $$\wedge$$ y' $$\in$$ V_Y(e) $$\cap$$ pred_Y(y) $$\Rightarrow$$ f_SymEtiqRel((x', x),(y', y)) = Vrai
  $$\forall$$(x', y') | x' $$\in$$ V_X(e) $$\cap$$ succ_X(x) $$\wedge$$ y' $$\in$$ V_Y(e) $$\cap$$ succ_Y(y) $$\Rightarrow$$ f_SymEtiqRel((x', x),(y', y)) = Vrai

.

Nous avons explicitement déjà pris en compte les critères de cohérence structurels et sémantiques en présentant les extensions des états e₁ et e₂. Par exemple [c, 3] ne fait pas partie de l'extension de e₁ puisque les étiquettes de sommets cet 3 sont différentes (critère de cohérence sémantique). Egalement, [c, 1] ne fait pas partie de l'extension de e₁ : bien que les étiquettes de e et de 1 soient similaires, le nombre des successeurs de 1 est nul, n'est pas au moins égal au nombre de successeurs e, donc la propriété d'incidence d'ordre 2 permet d'éliminer [c, 1].

Etape :

Une étape P_k est définie par l'ensemble des états {e_i(k);i $\in$ [1, N_k]} atteints à l'itération k du processus d'appariement. L'étape initiale notée P₀ est définie par l'ensemble des états initiaux {e_i(0);i $\in$ [1, N₀]} spécifiés par l'utilisateur.

Sur l'exemple de la figure 2.8, une étape peut être P₁ = {e₁, e₂}, tandis que l'étape initiale contenait les deux états initiaux correspondant aux deux graines.

Structure d'un état :

Chaque état e de P_k est décrit par les cinq éléments suivants :

• l'isomorphisme partiel V(e) (eq. 2.1),
• l'extension C(e) qui contient les extensions suivant les sommets de G_X extérieurs à l'état (eq. 2.3),
• le nombre $\delta$(e) (eq. 2.4),
• l'ensemble R(e) des graines présentes dans e (eq. 2.2),
• un indicateur d'extensibilité booléen : extensible(e), mis à la valeur Vrai à la création de l'état.

L'indicateur d'extensibilité d'un état permet de spécifier si celui-ci peut être étendu en un nouvel état au cours du processus d'appariement, ou s'il ne peut que fusionner avec d'autres états.

Fusion d'états :

à une étape donnée, pour savoir si l'extension d'un état e par une correspondance [x, y] crée un isomorphisme partiel connexe à un autre isomorphisme partiel, il faut savoir s'il existe déjà dans l'étape un état e'contenant la correspondance [x, y] et dont l'ensemble des graines est disjoint de l'ensemble des graines présentes dans e. Si c'est le cas, l'extension de e par [x, y] provoque la fusion des deux états (les deux états e et e' sont dits connexes). Le nouvel état résultant de la fusion de ces deux états connexes est obtenu en fusionnant leur ensemble de correspondances V(e'') $\leftarrow$ V(e') $\cup$ V(e) et leur ensemble de graines R(e'') $\leftarrow$ R(e') $\cup$ R(e). L'état e devient non extensible -- gelé¹² -- en positionnant son attribut d'extensibilité à False.

  

Figure 2.9: Etape après l'extension de e₁ suivant c

Par exemple, à supposer figure 2.9 que l'état e₁ de l'étape P₁ ait été étendu suivant cpour donner un nouvel état e₁' (dans une étape P₂), tandis que e₂' est la copie exacte de e₂. On a alors P₂ = {e₁', e₂'}, et l'état e₁' est caractérisé par l'isomorphisme partiel V(e₁') = {[a, 1],[b, 7],[c, 8]} ; son extension C(e₁') = {C(e₁' $\rightarrow$ e), C(e₁ $\rightarrow$ d )} avec C(e₁' $\rightarrow$ e) = {[e, 5],[e, 6]} ainsi que C(e₁' $\rightarrow$ d )= {[d, 9]} ; $\delta$(e₁') = 1 et R_e1' = {[a, 1]}.

  

Figure 2.10: Fusion des états e'₁ et e'₂ en e''₁

Comme [d, 9] est contenue dans V(e₂'), alors l'extension de e₁' suivant d mène à la fusion de e₁' et e₂', pour donner un nouvel état e₁'' qui est caractérisé par l'isomorphisme partiel V(e₁'') = {[a, 1],[b, 7],[c, 8],[d, 9]} ; son extension C(e₁'') = {C(e₁'' $\rightarrow$ e)} avec C(e₁'' $\rightarrow$ e) = {[e, 5],[e, 6]}, $\delta$(e₁'') = 2 et R_e1'' = {[a, 1],[d, 9]}.

Algorithme de multi-propagation

Les différentes notions que nous venons de définir nous permettent de présenter dans sa totalité l'algorithme de multi-propagation, dont les exemples déjà présentés ont sans doute permis de comprendre les grandes lignes.

.

L'étape 0 est initialisée avec les états liés aux graines de départ. Le déroulement général de l'algorithme consiste alors à passer d'une étape k à une étape k + 1 en étendant un certain nombre d'états de l'étape k suivant leurs relations d'extension, et en conservant les autres. Quand un état atteint la taille du graphe qu'on cherche à instancier, cet état représente un isomorphisme solution (son isomorphisme partiel est un isomorphisme solution).

On parle d'algorithme de propagation au sens où l'extension d'un état se fait par propagation le long des arcs des graphes. L'algorithme de [67] choisit un état quelconque de départ, une seule graine donc, et étend tous les états d'une étape de façon maximale, suivant toutes leurs possibilités d'extensions. Au bout d'autant d'étapes qu'il y a de sommets dans le graphe à instancier, cet algorithme de propagation aboutit à toutes les solutions, contenues dans la dernière étape.

Dès le moment où l'on dispose de plusieurs correspondances de départ (graines) à partir desquelles on peut propager les recherches de solutions, il y a lieu de parler de multi-propagation de la recherche d'isomorphisme. Dans le cas général, si on part d'une étape k, on retrouvera dans l'étape k + 1 :

• les états de l'étape k qui n'ont pas été touchés par l'extension ;
• les états de l'étape k qui ont servi à une fusion (donc ont simplement été marqués non extensibles) ;
• les nouveaux états résultant des extensions simples (l'isomorphisme partiel V(e) d'un état e $\in$ P_k est étendu d'une correspondance en V(e) $\cup$ {[x, y]}) ou bien des extensions avec fusion.

A la différence de l'approche présentée dans [67] qui étend à chaque étape tous les états suivant toutes les extensions possibles, dans notre approche on n'étend qu'un seul état à chaque passage d'une étape à l'autre, ce qui permet d'engendrer moins d'états dans l'arbre des solutions (au pire le même nombre). L'heuristique de choix de l'état à étendre à chaque étape est le critère principal de notre algorithme. A chaque itération, notre algorithme choisit un état e $\in$ P_k à étendre vérifiant le critère suivant :

$$\delta$$(e) = inf{$$\delta$$(a);a $$\in$$ P_k}

Ce choix de l'extension minimale revient à minimiser le nombre de nouveaux états générés dans le passage d'une étape k à une étape k + 1, donc à progresser de la façon la plus économique possible vers la solution.

  --------------------------------------------------------------
  IsoGP(G_X=(X,A_X),G_Y=(Y,A_Y),P_0)

  k <- 0
  REPEAT
    P_{k+1} <- { }
    Soit e dans P_k extensible tel que delta(e) = inf {delta(a)
    ; a dans P_k }
    P_{k+1} <- P_k - e
    Choisir un sommet x de G_X tel que |V(e -> x)| = delta(e)
    POUR_TOUT [x,y] correspondance de V(e -> x)
      P' = ExtensionFusion(P_{k+1},[x,y],e)
      POUR_TOUT e' de P'
         SI |e'| = |X|
           Retourner e' comme solution
         SINON 
           P_{k+1} <- P_{k+1} + e'
         FIN_SI
      FIN_POUR
    FIN_POUR 
    k <- k+1
  TANT_QUE pour tout e dans P_k, Extensible(e) = Faux)
  --------------------------------------------------------------

L'algorithme IsoGP présente la procédure principale de recherche de sous-graphes partiels, qui prend en entrée les graphes G_X et G_Y et l'étape initiale P_O comprenant les n états initiaux (n graines). A chaque étape k, le choix de l'état eà étendre fait, on reporte tous les états présents dans P_kdans P_{k + 1} à l'exception de l'état e. Pour chaque correspondance [x, y] de V(e $\rightarrow$ x), on appelle la fonction ExtensionFusion(P_{k + 1},[x, y], e) (cf. algorithme ExtensionFusion qui calcule l'extension de l'état e suivant [x, y].

La taille de chacun des états retournés par Extension_Fusion est ensuite testée. Si celle-ci correspond à la taille du graphe potentiel, alors l'état décrit un isomorphisme solution, et cette solution est rendue immédiatement, sinon on ajoute l'état à l'ensemble des états de P_{k + 1}.

L'algorithme s'achève lorsqu'il ne reste plus que des états gelés dans l'étape courante, c'est à dire lorsque tous les isomorphismes de sous-graphes partiels solutions ont été trouvés. La procédure ExtensionFusion permet de retourner :

• soit l'ensemble des états obtenus par fusion de e avec des états de P_{k + 1} connexes (ie. ayant [x, y] dans leurs correspondances et toutes leurs graines différentes de celles de e) ;
• soit un état résultant d'une simple extension de e par la correspondance [x, y] ;
• soit {} si les états nouveaux générés n'ont pas d'extension possible et ne peuvent donc mener à des solutions finales.

  --------------------------------------------------------------
  ExtensionFusion(P,[x,y], e)

  NouveauxEtats <- {} 
  POUR_TOUT t dans P | extensible(t) = Vrai
    SI R(t) Inter R(e) = {} et [x,y] dans t 
      e' <- t Union e ; R(e') <- R(t) Union R(e)
      extensible(t) <- Faux
      NouveauxEtats <- e'
    FIN_SI
  FIN_POUR

  SI NouveauxEtats = {}
    e' <- e + [x,y]
    NouveauxEtats <- NouveauxEtats + e'
  FIN_SI

  POUR_TOUT t dans NouveauxEtats
    SI |t| != |X| (t n'est pas solution)
      C(e') <- CalculExtension(e')
      SI C(e') =  {}
        Enlever t de NouveauxEtats
      FIN_SI
    FIN_SI
  FIN_POUR

  Retourner NouveauxEtats
  --------------------------------------------------------------

CalculExtension calcule l'ensemble des extensions possibles pour un état, ainsi que son extension minimale.

Un exemple complet

On considère les deux graphes orientés présentés figure 2.11 G_X = (X, A_X) avec X = {a, b, c, d, e} et G_Y = (Y, A_Y) avec Y = {1, 2, 3, 4, 5, 6, 7, 8, 9,}. Les arcs de G_X et G_Y ne sont pas étiquetés. On cherche les sous-graphes partiels de G_Y isomorphes au graphe d'entrée G_Xà partir des initiaux e₀₁ et e₀₂ avec V(e₀₁) = {[a, 3]}et V(e₀₂) = {[b, 4]}.

  

Figure 2.11: G_X a trois instances dans G_Y

L'exécution de l'algorithme sur notre exemple se fait suivant les étapes représentées dans le graphe états-transitions de la figure 2.12. Sur les arcs sont indiqués les sommets suivant lesquels des extensions sont réalisées. Un arc en pointillés indique une simple recopie d'un état d'une étape k dans l'étape k + 1. Un arc avec une croix schématise une extension non viable $\delta$ = 0. Un sommet entouré d'un rectangle en pointillé indique la non extensibilité de l'état associé. Les solutions finales trouvées sont les S_i.

Le passage de l'étape P₀ à l'étape P₁ se fait par une extension simple de l'état e₀₁ suivant c. Le passage de l'étape P₁ à l'étape P₂ voit l'extension de l'état e₁₂ suivant c et sa fusion subséquente avec e₁₁, de laquelle découle l'état e₂₂ tandis que e₁₁ (et ses diverses recopies) sont gelés. Le déroulement suivant ne pose pas de problème particulier¹³, et l'algorithme s'arrête car l'unique état présent dans l'étape P₅ n'est pas extensible. On remarquera également que l'ensemble de toutes les graines des états de cette étape ne couvre plus l'ensemble des graines de départ, c'est à dire que toutes les potentialités offertes par les différents états de départ on été exploitées au maximum. A l'issue de cette exécution, on obtient trois isomorphismes de sous graphes partiels de G_X dans G_Y :

• S₁ = {[a, 3],[c, 5],[b, 4],[d, 6],[e, 7]}
• S₂ = {[a, 3],[c, 5],[b, 4],[d, 7],[e, 8]}
• S₃ = {[a, 3],[c, 5],[b, 4],[d, 7],[e, 9]}

  

Figure 2.12: Graphe états-transition de déroulement de l'algorithme de multi-propagation

   
Expérimentation et discussion

Les notions d'étape, d'état et d'extension d'état ainsi que les critères de cohérence syntaxique et sémantique étaient déjà présentés dans [67]. Dans cet algorithme, on part d'une correspondance choisie au hasard, avant d'étendre maximalement dans toutes les directions, ce qui correspond à un arbre état-transition de profondeur | X| et de largeur maximale, dont les solutions sont les feuilles, éventuellement doublonnées. Cette approche correspond à une exploration en largeur des solutions par un algorithme de propagation simple. Nous avions également mis au point et implanté un tel algorithme sous sa forme récursive, où à chaque retour de récursion les isomorphismes partiels doublonnés étaient éliminés. La proposition de [67] nous a alors permis d'appréhender le problème sous une forme non récursive, que nous avons modifiée pour permettre une multi-propagation minimisant les états générés et éliminant naturellement les doublons, c'est à dire guidée par une heuristique déterminant à chaque étape la direction de propagation à privilégier. La notion de graine est à cet égard fondamentale, puisqu'il s'agit d'étendre plusieurs isomorphismes partiels en même temps, de telle sorte qu'ils se << rejoignent >> pour donner des solutions.

.

La phase d'expérimentation répond aux tests validant notre approche et permettant d'analyser les performances générales de l'algorithme mis en uvre. Pour cela, nous avons utilisé la bibliothèque LEDA [152,153] développée à l'Institut Max Planck à Saarbrücken, qui offre une gamme très complète de fonctionnalités relatives à la représentation et aux traitements de graphes. Un composant générique graphe est fourni avec les opérateurs permettant de réaliser les traitements de base les plus courants. Nous avons évalué notre algorithme et l'algorithme présenté dans [67] sur une série de graphes généraux aléatoires répondant aux contraintes des Strates-IA (UAV, EA, EAA, relations). Les graphes potentiels composés de 10 sommets en moyenne, sont construits par extraction de sous-graphes partiels des graphes généraux ainsi générés, et possèdent au moins un sommet UAV ou EAA ayant une correspondance unique).

.

Un test élémentaire sur un graphe général G_Y = (Y, A_Y) et un graphe potentiel G_X = (X, A_X) générés aléatoirement, consiste à prendre des mesures (temps d'exécution, nombre d'états générés, etc.) en exécutant :

• une fois notre algorithme avec n états initiaux (n graines) ;
• n fois l'algorithme [67] en fixant à chaque exécution un nouvel état initial. A partir de cette série d'exécutions, une moyenne des mesures visées est calculée.

Il est ainsi possible de comparer l'algorithme de multi-propagation prenant n graines en compte en même temps à une moyenne des nlancements de l'algorithme de propagation.

Le tableau 2.1 résume les résultats des séries de tests réalisées en donnant la taille en nombre de sommets du graphe général généré, le nombre de solutions trouvées, le numéro d'état correspondant à la première solution, le nombre total d'états générés par notre algorithme, et enfin le nombre total d'états générés par l'algorithme présenté dans [67].

 

Tableau 2.1: Comparaison, en fonction de la taille du graphe d'accueil du nombre d'états générés par les algorithmes de multi-propagation et de propagation

Taille GY	Nombre de solutions	Etat première solution	Nombre total d'état MP	Nombre total d'états Cordella et al. [67]
130	48	23	118	5803
250	17	17	68	2696
500	26	15	36	706
1500	14	19	40	2001
2000	20	14	28	615
8000	43	27	93	4875
15000	37	27	70	4527
30000	51	27	105	4597
80000	84	19	132	3837

 

.

Ces premiers résultats sont importants car ils confortent la stratégie choisie pour réduire l'espace des solutions explorés par notre algorithme. On montre ainsi qu'en pilotant le choix des états à l'extension par quelques paramètres simples, il est possible d'obtenir des solutions finales plus rapidement que l'algorithme présenté dans [67] et des espaces de solutions beaucoup plus réduits. Par exemple, en moyenne la première solution est fournie par notre algorithme avant d'atteindre le tiers de la taille totale de l'arbre d'états ; alors qu'avec l'algorithme de propagation, on est contraint d'attendre la construction totale de l'arbre d'états pour en extraire la première solution. De plus, on voit clairement que la réduction du nombre total d'états générés est très sensible.

Ces résultats doivent être nuancés dans le cas général de la recherche d'isomorphismes de sous-graphes partiels. Ils impliquent en effet qu'au moins une correspondance de départ soit connue, ce qui n'est pas le cas général. D'autre part, les tests ont été menés sur des graphes liés aux Strates-IA et non sur des graphes quelconques.

Remarques.

Il apparaît tout d'abord que nous avons fait le choix d'étendre un seul état par étape, suivant une unique direction, et l'heuristique de choix considère qu'une bonne direction est une direction qui générera le moins d'états possibles dans la nouvelle étape. Cette heuristique, qui donne de bons résultats peut être discutée. Par exemple, en gardant l'extension d'un unique état, il serait possible de considérer une heuristique variable qui, à partir d'un certaine étape du déroulement de l'algorithme stipulerait de favoriser les états considérés comme étant les plus près d'une solution (i.e. possédant un nombre de graines proche du nombre de graines total). Ensuite, l'algorithme que nous proposons s'intègre dans le domaine de la modélisation de documents audiovisuels, mais reste général. Ceci provient d'une volonté de considérer l'ensemble du système comme un unique graphe, et de s'attacher à décrire les opérations sur ce système comme étant liées à des manipulations de contextes exprimés par des graphes potentiels. Deux conséquences en découlent : en premier lieu, la généralité de l'algorithme permet d'envisager de l'appliquer à d'autres bases de données s'apparentant à des graphes. Ainsi on peut envisager d'en étudier l'application à des bases de données semi-structurées à partir non plus d'une unique graine (racine d'un arbre de données), mais à partir de plusieurs graines différentes. En deuxième lieu, les particularités des Strates-IA devraient permettre d'envisager de nouvelles heuristiques et améliorations de performance par rapport aux principes généraux présentés dans cette section. Celles-ci pourraient s'appuyer sur les types de sommets et de relations inter-sommets de l'application. Par exemple, la complexité liée aux fonctions de calcul des similarités entre sommets peut être prise en compte. Dans le cadre de notre application, il peut ainsi être utile d'étendre un état dans une direction impliquant un calcul de similarité basé sur des attributs issus de traitements d'image, s'il y a peu de candidats à la comparaison. Au contraire, si l'extension d'un état implique des calculs coûteux sur les attributs d'un grand nombre de sommets, il peut y avoir lieu de retarder ceux-ci, et d'explorer des branches nécessitant des calculs de similarité plus simples. De la même manière, si une relation liée à l'état est temporelle, l'extension de l'état peut être plus longue à calculer¹⁴. On peut donc imaginer de ne pas favoriser les extensions menant à des calculs de relations temporelles.

Il apparaît en conséquence que l'heuristique de choix de l'état à étendre est paramétrable et qu'adapter celle-ci à l'application permet d'améliorer encore les performances. Remarquons enfin que le fait que l'algorithme fournisse les solutions dès qu'elles sont arrivent, et non en fin de calcul, est un point important en recherche d'information : il est possible pour l'utilisateur de commencer à traiter les résultats sans que la recherche soit totalement terminée. L'algorithme est alors << anytime >> ce qui correspond à une caractéristique importante en aide à la décision.

   
Outils de manipulation fondés sur les graphes potentiels

Nous avons dans la section 2.1 introduit la notion de contexte dans les Strates-IA, ainsi que les graphes potentiels permettant d'instrumenter la manipulation et la recherche de contextes. L'instanciation d'un graphe potentiel se ramène à une recherche d'isomorphisme de sous-graphes partiels entre le graphe potentiel et le graphe des Strates-IA, et nous en avons proposé section 2.2 un algorithme.

Il convient maintenant de s'intéresser à la manière dont les graphes potentiels vont être utilisés et manipulés par l'utisateur comme par la machine, et quels outils sont disponibles pour les tâches de mise en place et d'exploitation d'un système Strates-IA. Ces outils devront être principalement adaptés à l'utilisateur. Notre approche d'annotation comme écriture sur le flux nécessite en effet de gérer la manière dont il va être possible de lire les annotations, c'est à dire d'envisager une tâche d'exploitation comme régissant une contextualisation.

Graphes potentiels caractérisés

Caractériser pour utiliser

Un graphe potentiel permet d'exprimer un contexte virtuel << brut >> en mettant en relation des objets génériques des Strates-IA. Par l'instanciation, il réalise le contexte abstraitement décrit en contextes concrets entre objets du graphe Strates-IA. Afin de pouvoir exploiter ces contextes concrets, il faut pouvoir les caractériser, c'est à dire spécifier opératoirement quels sommets du graphe potentiel (et donc des graphes-instances) seront utiles pour la tâche dans laquelle le graphe potentiel est utilisé.

Un graphe potentiel caractérisé est donc un graphe potentiel dont certains sommets d'intérêt, jugés utiles, sont nommés, et qui permettent de l'exploiter. Par exemple, un graphe potentiel exprimant un chemin contextuel devra posséder a minima une origine et une extrémité qui permettront de le désigner.

Soit G_P un graphe potentiel, alors le caractériser revient à nommer certains de ses sommets (chaque nom étant unique). On notera un graphe potentiel caractérisé par

G_PC = (G_P,{x_i})

où :

• G_P est un graphe potentiel ;
• x_i est un nom (une étiquette de sommet d'intérêt) associé à un sommet de G_P¹⁵.

Par exemple, le graphe potentiel caractérisé G_PC1 de la figure 2.13 est un graphe potentiel dont deux points sont caractérisés par des étiquettes de sommets d'intérêt origet extr correspondant aux sommets 1 et 4. L'étiquette de sommet d'intérêt PanoSurGroupe est associée au sommet 1 du graphe potentiel constituant G_PC2, ConstituantGroupe au sommet 6, orig au sommet 4 et extr au sommet 6.

  

Figure 2.13: Premiers exemples de graphes potentiels caractérisés

Manipulations de graphes potentiels caractérisés

Avant de donner des exemples plus précis de graphes potentiels caractérisés, nous en présentons rapidement quelques opérations de manipulation. Ces opérations seront directement adaptées de celles liées aux graphes potentiels.

Construction et instanciation de graphes potentiels.

On munit les graphes potentiels d'opérateurs de construction :

• création d'un graphe potentiel à un seul sommet et étiquettage par un objet générique ;
• mise en relation de graphes potentiels par une relation et étiquettage de celle-ci conformément aux contraintes de relation des Strates-IA ;
• étiquettage d'un sommet permettant de modifier un objet générique associé à un sommet ;
• jonction des deux graphes potentiels par identification de sous-graphes communs ;
• suppression de relation entre deux sommets.

Une dernière opération de construction de graphe potentiel est plus complexe, puisqu'il s'agit alors de potentialiser un sous-graphe du graphe général Strates-IA G_SIA. A partir d'un sous-graphe connexe g quelconque de G_SIA, on met alors en place un graphe isomorphe, dont les étiquettes sont des objets génériques obtenus par abstraction des objets étiquettes de g (i.e en supprimant ou en changeant des attributs, et en associant à chaque objet générique une fonction de similarité idoine). Cette opération se révèle d'intérêt pour prendre en compte des annotations qui on été mises en place afin de s'en inspirer pour construire ses propres requêtes.

Aux opérations de modification qu'on vient de présenter, on ajoute un opérateur d'instanciation qui permet de calculer les sous-graphes du graphe général G_SIA instances du graphe potentiel. Ce dernier doit être valide, c'est à dire posséder un moins une étiquette de sommet qui puisse être mise sans ambiguïté en correspondance avec un sommet du graphe général. Dans le cas contraire, l'instanciation ne pourra s'effectuer.

Construction et instanciation de graphe potentiels caractérisés.

Un graphe potentiel caractérisé étant principalement constitué d'un graphe potentiel (auquel on ajoute des étiquettes de sommets d'intérêt), il peut être construit uniquement avec les opérations présentées plus haut.

Cependant, l'accès au graphe potentiel dont est composé un graphe potentiel caractérisé peut également se faire à partir des sommets caractérisés, particulièrement les opérations d'étiquettage de sommets ou de mises en relation. Par exemple, si un graphe potentiel caractérisé possède un sommet caractérisé par ConstituantGroupe, alors cette étiquette de sommet d'intérêt permet d'accéder à l'objet générique correspondant directement, par exemple pour le préciser en < Nelson Mandela > . En d'autres termes, les sommets caractérisés et leurs noms sont des primitives de manipulation, des index de sommets de graphes potentiels qui se révèleront utiles au cours des tâches d'utilisation des graphes potentiels.

L'instanciation d'un graphe potentiel caractérisé G_PCconsiste simplement à instancier le graphe potentiel G_P qu'il contient.

De la même manière que précédemment, l'accès aux instances peut être contrôlé par les sommets caractérisés. Par exemple, si après l'instanciation du graphe G_PC2 de la figure 2.13, on obtient trois instances, alors l'accès aux sommets intéressants de celle-ci -- en l'occurrence ici les UAV annotées par un groupe qui soit l'objet d'un panoramique gauche-droite -- se fait en utilisant le sommet caractérisé par PanoSurGroupe.

Nous présentons dans la suite quelques exemples de graphes potentiels caractérisés, et illustrons les opérations que nous avons présentées. Les exemples que nous présentons ne sont que deux types très utiles de graphes potentiels caractérisés. On ne perdra pas de vue que ceux-ci peuvent être créés à volonté dès que le besoin s'en fait sentir.

Exemples de graphes potentiels caractérisés

Relations contextuelles potentielles.

Une relation contextuelle potentielle (RCP) est un graphe potentiel caractérisé par deux sommets. Le premier est nommé origine (orig), le second est nommé extrémité (extr) de la relation contextuelle potentielle.

Si rcp est une relation contextuelle potentielle, on a rcp = (gp,{orig, extr}).

Suivant les types des objets étiquetant les sommets origine et extrémité, les relations contextuelles potentielles peuvent être interprétées différemment. Par exemple, en se basant sur ce que nous avons présenté dans la partie 2.1.2. :

• si l'origine est UAV et l'extrémité EA ou EAA, alors on s'intéresse au contexte de l'UAV, particulièrement aux EA qui pourraient l'annoter contextuellement, soit en provenance du flux, soit de la base de connaissances. Un exemple de telle RCP est le graphe potentiel caractérisé G_PC1 de la figure 2.13.
• si l'origine est EA, alors on peut s'intéresser particulièrement aux RCP à extrémité EA ou EAA, qui fournissent des explications sur l'utilisation de l'EA, lesquelles sont en contexte (dans le flux) ou bien hors contexte (dans la base de connaissances). Par exemple, le graphe potentiel caractérisé G_PC2 de la figure 2.13 permet de s'intéresser au contexte dans le flux des EA < PanoGaucheDroite > (orig), contexte concernant le cas où c'est un groupe qui est filmé, auquel cas les EA correspondant à extr sont les constituants des groupes filmés ;
• si l'origine est EAA, et l'extrémité EA ou UAV, cela peut correspondre à un contexte d'explication d'utilisation ; tandis que si l'extrémité est un EAA, on s'intéresse à la place de l'EAA origine dans la base de connaissances (on en trouvera des exemples avec les filtres de désignation que nous présenterons plus bas).

Bien évidemment, l'interprétation des contextes et leurs mises en place dépendent de la tâche en cours. Par exemple, supposons que nous désirions annoter contextuellement une UAV u, c'est à dire définir un contexte désignant une autre UAV u', et plus particulièrement certains des éléments d'annotation annotant u', qu'on pourra alors considérer annoter contextuellement u.

  

Figure 2.14: Exemples de graphes potentiels caractérisés

Définissons alors une RCP à origine UAV et à extrémité UAV telle que rcp₁ figure 2.14, qui exprime que l'UAV faisant partie du contexte de l'UAV origine devra être en relation quelconque (non temporelle cependant) avec elle. Si nous appliquons cette RCP à une UAV connue, par exemple en créant une UAV rcp₁'(figure 2.15) équivalente à rcp₁ à la différence que l'objet générique correspondant à orig est objet UAV ayant un attribut identifiant l'UAV 8 du flux Fic232 de la figure¹⁶ 2.15, alors l'instanciation de rcp₁' donnera deux instances. Les extrémités de ces instances, c'est à dire les sommets du graphe Strates-IA G_SIA en correspondance avec le sommet extr de rcp₁' sont alors les UAV u₁ (UAV 1 du flux contenu dans le fichier fic342, voir figure 2.15) et u₂ (UAV 13 du flux principal représenté).

Supposons maintenant que nous désirions considérer comme annotations contextuelles les EA annotant ces deux UAV (et ne participant pas à la relation entre elles). Nous pouvons opérer une fusion de rcp₁ et rcp₂ telle que l'extrémité de rcp₁ et l'origine de rcp₂ soient identifiées, en créant une nouvelle RCP rcp₃ à origine l'origine de rcp₁ et extrémité l'extrémité de rcp₂. Alors, appliquer rcp₃ à l'UAV 7nous donnera une RCP rcp'₃. L'instanciation de rcp'₃ permet alors de récupérer les EA < Constituant > , < François Mitterrand > , < Danielle Mitterrand > et < Epouse > pour u₁ et < François Mitterrand > , < Poignée de main > et < Nelson Mandela > pour u₂ (voir figure 2.15).

  

Figure 2.15: Les trois relations contextuelles potentielles rcp₁', rcp₃' et rcp₄ s'instancient dans le graphe à partir de l'UAV 8. Les extrémités des instances correspondent aux sommets respectivement indiqués en rectangle gras pointillé, ovale gras, et double ovale gras

Supposons enfin que nous ne souhaitions ne récupérer comme annotations contextuelles que les EA inscriptions dans le flux d'un EAA spécialisation de l'EAA < EAA:Nom commun >. Alors il est possible de préciser l'extrémité de rcp₃ en la mettant en relation avec le sommet d'intérêt designation du graphe potentiel caractérisé fd₁ pour obtenir rcp₄. L'application de rcp₄à l'UAV 7 permet alors de récupérer comme extrémités les EA < Epouse > et < Poignée de main > ¹⁷ (voir figure 2.15).

   
Filtres de désignation.

Un filtre de désignation est un graphe potentiel caractérisé à sommets étiquetés par des objets de type EAA, caractérisé par un sommet d'intérêt appelé point de désignation (désignation). Par exemple figure 2.14, fd₁ est un filtre de désignation.

Si fd est un filtre de désignation, alors fd = (gp,{des}).

Instancier un filtre de désignation permet de récupérer un ensemble d'EAA, qui sont dans ses instances les sommets en correspondance avec le sommet nommé désignation. La figure 2.16 présente deux autres filtres de désignation : fd₂ permet de désigner uniquement l'EAA < EAA:Zoom avant > dans la base de connaissances de la figure 2.3, page , tandis que fd₃ désigne les EAA < EAA:Nelson Mandela > et < EAA:Winnie Mandela >.

  

Figure 2.16: Deux filtres de désignation

Dimensions d'analyse

Définition

Nous avons dans le chapitre 1 présenté une dimension d'analyse comme un regroupement des analyses qui permettent de repérer des objets d'intérêt de même type.

Dans le cadre des Strates-IA les objets d'intérêt sont réifiés en annotations représentées par des éléments d'annotation, eux mêmes abstraits en éléments d'annotation abstraits ; une dimension d'analyse permettra toujours de rassembler un certain nombre d'EAA. Nous définissons donc une dimension d'analyse comme l'association d'un nom et d'une méthode de désignation d'EAA.

.

Une méthode de désignation (MD) permet de désigner un ensemble d'EAA de la base de connaissances. Elle est donc d'abord un ensemble de filtres de désignation tels que nous les avons définis en 2.3.1.

Par exemple, la méthode de désignation md₁ = {fd₃, fd₄}permet de désigner les EAA < EAA:Nelson Mandela >, < EAA:Winnie Mandela > et < EAA:Jacques Chirac >.

On associe aux méthodes de désignation des opérations permettant d'ajouter, d'enlever des filtres de désignation, mais il est également possible de les manipuler à leur propre niveau. Ainsi on pourra définir une méthode de désignation comme l'association d'autres méthodes de désignation.

Une méthode de désignation md est alors un ensemble de méthodes de désignation et/ou d'ensembles de filtres de désignation :

md $$\leftarrow$$ {fd_i} | md + {fd_j} | {md_k}

On aura par exemple md₂ = {fd₂, md₁}.

Etendre une méthode de désignation consiste à remplacer récursivement les méthodes de désignation qui la composent par les méthodes de désignation ou filtres de désignation, et ainsi de suite jusqu'à ce que la MD ne soit plus composée que de filtres de désignation.

On aura alors Ext(md )= {fd_i}, par exemple md₂' = Ext(md₂) = {fd₂, fd₃, fd₄}.

Résoudre une méthode de désignation consiste à calculer l'ensemble des éléments d'annotation abstraits que celle-ci désigne.

On aura alors Res(md )= {eaa_i}, par exemple Res(md₂') = Res(md₂) = { < EAA:Nelson Mandela >, < EAA:Winnie Mandela >,< EAA:Jacques Chirac >,< EAA:Zoom Avant >}.

.

Remarquons que les opérations telles que ajout, retrait ou intersection de MD opérent sur les définitions de MD, et non sur leurs extensions, c'est à dire sur celles-ci telles qu'elles sont définies lorsqu'on les utilise. Ainsi par exemple, si m_a = {m₁, m₂, m₃}, m_b = {m₁, m₄} et m₁ = {m₂, m₄}alors on aura m_a $\cap$ m_b = {m₁}.

.

Nous définissons plus précisément une dimension d'analyse d est l'association d'un nom, d'un texte, et d'un méthode de description¹⁸.

d = < Nom, Description$$\_texte$$, md >

Une dimension d'analyse sera résolue en l'ensemble des EAA qu'elle permet de désigner. Ainsi, si d = < Nom, Description$\_texte$, md >, alors Res(d )= Res(md ).

Avec la dimension d'analyse da₁ = < Politiquesdivers, << sommets France/Afrique du Sud 1995-1999 >>, md₁ >, on aura Res(da₁) = {< EAA:Nelson Mandela >, < EAA:Winnie Mandela >, < EAA:Jacques Chirac >}.

Contraintes sur les valeurs d'attributs d'EAA contenus dans une dimension d'analyse

Une dimension d'analyse permet de décrire des EAA à utiliser pour l'annotation, c'est à dire que la seule prescription porte sur le nom de l'EA qui sera mis en place, toute l'information sur les autres attributs de celui-ci étant portée par l'EAA.

Il est possible de spécifier un peu plus les dimensions d'analyse de telle sorte qu'elles imposent des valeurs sur certains attributs des EA qu'elles permettront de générer. On peut ainsi leur associer des contraintes sur les attributs et les valeurs d'attributs des EA qu'elles permettront de mettre en place. Une condition nécessaire à la définition de ces contraintes est que les attributs soient présents en tant que définitions dans tous les EAA désignés par celle-ci.

Par exemple, daa = $\langle$DA : Emissions : {< EAA:Journal Télévisé >,< EAA:Jeu > } : Date = 05081999$\rangle$ est une dimension associée à des contraintes spécifiant que l'annotation pourra conduire à mettre en place des EA < Journal Télévisé > et/ou < EAA:Jeu > avec une valeur d'attribut Date fixée à 05081999.

Discussion

La notion de dimension d'analyse est fondamentale dans les Strates-IA. En effet, permettant de désigner un ensemble d'EAA, une dimension d'analyse représente une vue de la base de connaissances correspondant à une visée de description du flux audiovisuel. Elle est donc en quelque sorte un contexte dans lequel l'utilisateur se place afin d'appréhender le flux et d'y projeter ses attentes¹⁹. La dimension d'analyse peut alors être pensée comme technique, à la fois comme guide de repérage des objets d'intérêt et de caractérisation de ceux-ci. Une dimension d'analyse est donc liée à la tâche et à la volonté de description en cours, et en représente le pendant formel.

A ce titre une dimension d'analyse doit être fortement évolutive, c'est à dire qu'il doit être possible de la compléter, de la restreindre, de la fusionner avec une autre pour l'adapter à la visée de description. Les quelques opérations de manipulation que nous avons présentées correspondent à cette nécessaire évolutivité.

Certaines dimensions d'analyse sont construites manuellement par l'utilisateur qui sélectionne les EAA convenables, elles sont donc composées de filtres de désignation à portée réduite, ne désignant qu'un EAA pour chaque filtre (comme par exemple fd₂ ou fd₃ figure 2.16). D'autres dimensions d'analyse prennent avantage de l'organisation de la base de connaissances, c'est à dire des relations entre EAA par l'intermédiaire de filtres de désignation à portées plus larges (par exemple fd₁ ou fd₃). Ainsi une dimension d'analyse ayant pour méthode de désignation le filtre de désignation fd₁ permet de désigner tous les << Noms communs >> de la base de connaissances en utilisant l'organisation hiérarchique de cette dernière. Il va alors de soi que les choix d'organisation de la base de connaissances ont une influence sur les dimensions d'analyse qui seront utilisées pour l'exploitation de cette dernière. Par exemple, organiser hiérarchiquement la base de connaissances revient, au moins au niveau des feuilles, à définir implicitement des filtres de désignation efficaces et les dimensions d'analyse qu'ils permettent de construire. Regrouper les << hommes politiques >> utiles à l'annotation sous un même père hiérarchique revient à mettre en place implicitement une dimension d'analyse liée aux hommes politiques. Cependant, au delà de ces dimensions d'analyse << naturelles >> à la base de connaissances (puisqu'implicites), toute construction ou manipulation de DA est possible et nécessaire pour exploiter la base de connaissances d'une manière adaptée à la tâche.

Schémas de description

Nous avons jusqu'ici défini les graphes potentiels caractérisés comme des graphes potentiels manipulables, et les dimensions d'analyse comme des marques de la visée d'analyse d'un utilisateur annotant un flux. Les dimensions d'analyse permettent de guider un utilisateur selon une certaine description en ne lui proposant que des ensembles limités et nommés d'EAA²⁰ à inscrire dans le flux.

Si nous sommes donc pour l'instant capables de fournir un cadre précis pour l'annotation suivant certaines dimensions d'analyse, nous ne pouvons ni spécifier ni prescrire une description structurée d'un document ou d'une partie de document. Cela peut pourtant s'avérer nécessaire, par exemple lorsque l'annotation n'est pas personnelle, mais est réalisée dans une institution suivant les canons correspondant à la volonté de description de celle-ci. Il importe alors qu'au minimum certaines méthodes d'écriture comme de lecture sur le flux, donc de contextualisation soient définies.

Ces méthodes seront exprimées suivant des schémas de description.

Définition

Considérée du point de vue pratique de la description, une dimension d'analyse est un ensemble de termes utilisables pour l'annotation de façon quelconque. Pour exprimer une structuration de la pratique de description, il y a lieu de la considérer comme ensemble de termes jouant le même rôle par rapport à d'autres ensembles de termes, c'est à dire qu'il faut exprimer des relations entre les dimensions d'analyse dont les EA extraits seront mis en relation.

Par exemple, pour exprimer le fait que la description devra mettre en relation des EA issus de la dimension d'analyse da₁ =< DA:Homme politique > avec des termes issus de da₂ =< DA:Prise de parole publique:{< Discours > ,< Conférence de presse > ,< Interview > } > , on mettra da₁ et da₂ en relation dans un schéma de description.

.

Un schéma de description basique est un graphe orienté étiqueté dont les sommets sont doublement étiquetés par noms de dimensions d'analyse et des booléens.

.

On a alors SD = < S, A,$\mu_{1}^{}$,$\mu_{2}^{}$,$\nu$} avec S ensemble des sommets du graphe, A ensemble des arcs, $\mu_{1}^{}$ associant à chaque sommet une dimension d'analyse, $\mu_{2}^{}$ associant à chaque sommet un booléen, et $\nu$ associant à chaque arc une étiquette de relation.

.

Pour un sommet quelconque s $\in$ S, l'interprétation de $\mu_{2}^{}$(s)est la suivante :

• si $\mu_{2}^{}$(s) = Faux, alors la dimension d'analyse spécifie de mettre en place un EA de façon quelconque ;
• si $\mu_{2}^{}$(s) = Vrai, alors la mise en place de l'EA doit obligatoirement s'accompagner de la création d'une nouvelle unité audiovisuelle dont il sera EA primitif.

Soient s₁ et s₂ deux sommets de S tels que (s₁, s₂) $\in$ Aalors les étiquettes de relations possibles $\nu$((s₁, s₂)) et leurs interprétations sont les suivantes :

• $\nu$((s₁, s₂)) peut être une des relations élémentaires R_e[m, n], m $\leq$ n permettant de spécifier le nombre de relations élémentaires à mettre en place (R_e[0, 1], R_e[1, 1] et R_e[1, n] seront les plus utilisées). Par exemple, si ea₁ est issu de la dimension d'analyse $\mu_{1}^{}$(s₁), et que $\nu_{(}^{}$(s₁, s₂)) = R_e[1, n], alors il y a lieu de le mettre en relation élémentaire R_e avec un ou plusieurs ea_2i issus de $\mu_{1}^{}$(s₂).
• $\nu$((s₁, s₂)) peut appartenir à R_T l'ensemble des relations temporelles. Alors il faut que l'UAV annotée par ea₁ soit dans la même relation temporelle avec l'UAV qu'annote ea₂.
• Si $\nu$((s₁, s₂)) = R_a la relation d'annotation, alors ea₂ doit annoter la même unité audiovisuelle que ea₁.

  

Figure 2.17: Un schéma de description de base

.

La figure 2.17 présente un schéma de description sd₁ (indépendant des exemples que nous avons jusqu'ici présentés). Les sommets s_i du graphe entourés d'un rectangle signifient que $\mu_{2}^{}$(s_i) = Vrai donc que pour les EA extraits de leurs dimensions d'analyse étiquettes doivent être EA primitifs.

Les dimensions d'analyse utilisées dans le schéma de description sd₁ sont les suivantes :

• < DA:Document:{< Document > } >
• < DA:Plan:{< Plan > } >
• < DA:Cstruct:{< Cstruct > } >
• < DA:Agent:{< Agent > } >
• < DA:Sujet principal:{< Sujet principal > } >
• < DA:Personnage:{< Le Corbeau > , < Le Renard > , < Le Loup > , < L'agneau > , < Le Chêne > , < Le Roseau > } >
• < DA:Action:{< Posséder > , < Discourir > , < Flatter > , < Ecouter > , < Manger > , < Boire > } >

Nous présentons dans la suite trois étapes d'une utilisation de sd₁ pour la description d'un flux correspondant à un document (par exemple un dessin animé) illustrant une fable bien connue. A chaque étape, les parties utilisées du schéma de description sont soulignées en gras.

  

Figure 2.18: Utilisation de sd₁ : début d'annotation, mise en place de la structure et des << actions >>

La figure 2.18 correspond au début de l'annotation, c'est à dire à la mise en place de la structure (relations entre < Document > et < Plan > ) dans le flux, conduisant à la création de trois unités audiovisuelles, comme spécifié dans le schéma de description. De la même manière, à chaque UAV définie primitivement par < Plan > est associé un EA issue de la dimension d'analyse < DA:Action > .

  

Figure 2.19: Utilisation de sd₁ : relations entre < Document > et les << actions >> qui le composent

La figure 2.19 correspond simplement à l'utilisation de la mise en relation facultative permettant de lier < Document > à des sujets principaux, qui sont issus de < DA:Action > .

  

Figure 2.20: Utilisation de sd₁ : mise en place des << personnages >> et complétion libre de l'annotation

La figure 2.20 correspond à l'utilisation de la relation temporelle R_During dans le schéma de description entre les EA issus de < DA:Personnages > et ceux issus de < DA:Action > . On remarquera qu'une certaine latitude a été laissée pour l'annotation, ainsi par exemple la mise en place de l'EA < Le corbeau > extrait de < DA:Personnage > a pu conduire à la mise en place d'une nouvelle UAV, mais ce n'était pas obligatoire. Après la mise en place des relations médiatisées par < Agent > , l'annotateur a choisi d'ajouter l'EA < Fromage > à l'annotation de l'UAV1, et de le mettre en relation avec < Sujet principal > , ce qui est en dehors du schéma de description sd₁, ou plutôt est inclu dans le schéma de description le plus général imaginable, spécifiant que l'annotateur est libre d'utiliser les éléments d'annotation à sa guise.

L'annotation présentée correspondrait alors à l'utilisation du schéma spécifique sd₁ associé à un schéma libre.

Schémas de description généraux

Un schéma de description général (ou plan de description est un ensemble de schémas de description. Il spécifie quels sont les schémas de description à utiliser pour une annotation.

Par exemple, si sdg = {sd₁, sd₄} avec sd₄ réduit à une dimension d'analyse

da =< DA:Sentiments: {< Vanité > , < Orgueil > , < Joie > , < Ironie > } > .

Alors utiliser sdg pour annoter un flux revient à utiliser sd₁pour mettre en place une structure d'annotation, mais aussi à utiliser également les EAA extrait de da pour compléter l'annotation.

Manipulation

  

Figure 2.21: Quelques schémas de description à partir desquels a pû être construit sd₁

Parmi les opérateurs de construction de schémas d'annotation basiques, citons :

• la possibilité de joindre des schémas de description par certains sommets, par exemple pour préciser certains points d'annotation. Par exemple sd₁ a pu être construit à partir, entre autres, de sd₂ tel que présenté figure 2.21 ;
• la possibilité d'extraire des schémas de description d'autres schémas de description, par exemple sd₃ correspond à un schéma de description plus général que sd₁ et a pu en être extrait ;
• la possibilité d'extraire des schémas de description de l'annotation elle-même, en en repérant les régularités d'annotation. Par exemple, sd₁ a pu être mise en place en observant des annotations libres de dessins animés illustrant des contes et en en repérant les régularités.

Nous venons de le voir, schémas de description et (sous-)graphes d'annotation sont donc très proches, les uns pouvant être considérés comme abstractions des autres, qui en sont des spécialisations.

Discussion

Les schémas de description permettent de spécifier une structuration de l'annotation, de façon prescriptive. Cela répond donc à notre volonté d'avoir un moyen de contrôler l'annotation, i.e. l'écriture sur le flux dans le modèle des Strates-IA.

L'expressivité des schémas de description n'est pourtant pas totale : il est par exemple ardu d'exprimer dans un schéma de description que l'ensemble des UAV annotées par < Plan > dont est composé un document doit temporellement couvrir la totalité de l'UAV annotée par < Document > . Ce genre de problèmes pourrait être résolu en complexifiant la définition des schémas de description, par exemple en y définissant des relations supplémentaires, ou en attachant des vérifications procédurales aux dimensions d'analyse. Le schéma de description n'en restera pas moins un graphe de dimensions d'analyses correspondant à des sous-graphes d'annotation réels.

C'est cette dernière possibilité qui se révèle en effet la plus importante : connaissant un schéma de description ayant servi à annoter des flux, c'est à dire des schémas de mise en contexte, il est possible de construire des graphes potentiels caractérisés exprimant des schémas de contextualisation. Il nous reste donc à présenter quels sont les liens entre les graphes potentiels et les schémas de description.

Graphes requêtes

Un graphe requête (ou graphe potentiel généralisé) est un ensemble de graphes potentiels caractérisés défini en intension.

Informellement, la définition d'un graphe requête est similaire à celle des graphes potentiels caractérisés, à la différence près que les sommets étiquetés auparavant par des EAA peuvent l'être par des dimensions d'analyse.

La figure 2.22 présente un graphe requête gr₁défini à partir du schéma de description sd₁. Seule une partie de sd₁ a été utilisée, et la dimension d'analyse < DA:Action > a été spécialisée en < DA:Discourir > .

  

Figure 2.22: Un graphe requête et les quatre graphes potentiels caractérisés qu'il définit

Passer d'un graphe requête à un ensemble de graphes potentiels caractérisés revient à générer n graphes potentiels pour chaque sommet étiqueté par une dimension d'analyse décrite par n filtres de désignation. Les sommets précédemment étiquetés par des dimensions d'analyse sont alors identifiés avec les points de désignation des filtres de désignation dont elles sont composées.

Par exemple, le graphe requête gr₁ possède deux sommets étiquetés par des dimensions d'analyse < DA:Discourir > et < DA:Personnages > . La première DA est décrite par un unique filtre de désignation, tandis que la seconde est décrite par cinq filtres de désignation présentés figure 2.22. Le graphe requête permet de mettre en place 5 x 1 graphes potentiels caractérisés gpc_{i, i = 1..5}.

.  

Il apparaît donc que pour une dimension d'analyse << naturelle >> à la base de connaissances (i.e. fondée sur des propriétés d'organisation explicite de celle-ci, comme le serait une dimension d'analyse décrite par fd₅), le passage d'un graphe requête à un graphe potentiel caractérisé est immédiat et économique. Dans le cas contraire -- quand la dimension d'analyse est fortement personnelle ou liée à une tâche non prévue -- ce passage peut générer de nombreux graphes potentiels caractérisés, et donc entraîner un nombre important d'instanciations. Nous montrons dans la suite que l'algorithme de multi-propagation s'adapte aisément à la prise en compte de dimensions d'analyse << non-naturelles >>, pour peu que la base de connaissances soit virtuellement complétée par une super-organisation liée à la dimension d'analyse, c'est à dire à la tâche en cours.

.

L'instanciation d'un graphe requête peut en effet se faire de deux manières, pour des résultats équivalents.

La première méthode consiste en la mise en place des graphes potentiels caractérisés que le graphe requête décrit et de leurs instanciations, en identifiant les sommets étiquetés par les dimensions d'analyse avec les différents points de désignation des filtres de désignation qu'elles contiennent. Par exemple, on instanciera les gpc_i de la figure 2.22 et on récupérera les différentes sous-graphes instances comme résultats après cinq processus d'instanciation.

La deuxième méthode consiste à imposer pour chaque dimension d'analyse un certain nombre d'états de départ ayant la même graine, et signifiant les correspondances entre les EAA désignés par la dimension d'analyse avec les EAA de la base de connaissances. Par exemple l'étape P₁ dans le cas de l'utilisation de gr₁ aura sept états initiaux :

• un état e₁₁ désignant la correspondance de l'EAA < EAA:Discourir >, et ayant donc cette graine ;
• six états e_1i désignant les correspondances des EAA < EAA:Le Loup >, < EAA:Le Renard >, < EAA:L'agneau >, < EAA:Le Corbeau >, < EAA:Le Chêne >, < EAA:Le Roseau > ayant une même graine. Cette graine virtuelle désigne une correspondance virtuelle au niveau d'un EAA virtuel dont les six EAA seraient par exemple spécialisation. Cela revient en fait à générer virtuellement dans la base de connaissances un EAA dont les différents EAA de la dimension d'analyse seraient spécialisation, c'est à dire à mettre en place une organisation virtuelle de la base de connaissances dans laquelle la dimension d'analyse serait << naturelle >>. Dans cette base de connaissance modifiée, un graphe potentiel virtuel s'instancie de façon naturelle, comme illustré figure 2.23.

On aura alors P_O = {e₀₁, e₀₂} et P_O = {e₁₁, e₁₂, e₁₃, e₁₄, e₁₅, e₁₆} avec V(e₀₁ = {[f, 9]} et V(e₀₂) = {[a, 1']}, V(e₁₁) = {[a, 1'],[b, 11]}, etc.

  

Figure 2.23: Un graphe potentiel caractérisé virtuel s'instancie dans une base de connaissances virtuelle

.

Les graphes requêtes permettent donc, dans le cas où une dimension d'analyse possède plusieurs filtres de désignation, de ne pas générer autant de graphes potentiels qu'il y a de combinaisons possible de filtres de désignation, mais d'adapter virtuellement la base de connaissances à la tâche en cours, décrite par ses dimensions d'analyse. Ils s'inscrivent donc naturellement dans les outils d'exploitation de graphes Strates-IA.

Les graphes-requêtes peuvent être construits manuellement, ou bien générés à partir de graphes potentiels caractérisés (ce qui est immédiat), des descriptions elles-mêmes (par abstraction de description et réutilisation), ou bien encore à partir des schémas de description. Ce dernier processus revient alors à choisir une partie d'un schéma de description, et à l'utiliser pour annoter un flux imaginaire dont on mettra en place les UAV totalement génériques, certains EA étant précisés directement dans le flux, d'autres par leurs liens avec la base de connaissance, soit sous la forme d'EAA extraits des dimensions d'analyse du schéma de description, soit encore sous la forme de dimensions d'analyse²¹.

Un graphe requête n'étant qu'une façon de décrire un ensemble de graphes potentiels caractérisés, dans la suite on utilisera les termes << graphes potentiels caractérisés >> ou << graphe requête >> indifféremment, en précisant uniquement s'il y a lieu ce que nous entendons par là.

Valences

Une valence (notion que nous avons déjà évoquée dans la partie 1.2.2) est un attribut d'élément d'annotation abstrait exprimant une possibilité de mise en relation contextuelle pour les EA qui en sont extraits.

La mise en relation peut se faire soit en utilisant un EA pour en exprimer la sémantique, soit directement par une relation élémentaire.

.

Une valence est donc composée :

• d'une relation contextuelle potentielle dont l'origine est un EA et l'extrémité un autre EA (éventuellement sous la forme d'un graphe requête) ;
• d'une éventuelle indication sur le type de mise en relation, c'est à dire la présence ou non d'un filtre de désignation.

Une valence s'utilise éventuellement lorsque l'EAA dont elle est attribut est inscrit dans le flux. La relation contextuelle potentielle est alors appliquée au nouvel EA ea, et instanciée. S'il y a des instances, leurs extrémités ea_i' sont proposées à la mise en relation avec l'EA ea, soit directement si la valence n'a pas plus de précisions, soit par l'intermédiaire de l'EAA proposé.

La figure 2.24 propose un exemple de valence très simple, composée d'une relation contextuelle potentielle (ici présentée sous la forme d'un graphe-requête) et de l'EAA < EAA:Agent >. La relation contextuelle potentielle exprime qu'il y a lieu de chercher dans le contexte temporel d'inclusion un EA découlant de la dimension d'analyse < DA:Personnage > . < EAA:Agent > exprime le fait que si l'utilisateur décide d'utiliser la valence, alors cet EA sera mis en relation avec < Manger > par l'intermédiaire d'un EA < Agent > .

  

Figure 2.24: Utilisation de la valence de l'EAA < EAA:Manger > : le graphe potentiel de la valence, spécialisé en identifiant orig à l'EA < Manger > , est instancié, et son extrémité permet de proposer l'EA < Le Loup > à la mise en relation avec < Manger > par l'intermédiaire de < Agent >

.

Une autre utilisation des valences peut consister, si la relation potentielle ne s'instancie pas, à proposer à l'utilisateur de mettre en place un EA tel qu'il y ait une instance, puis de mettre en relation ce nouvel EA avec l'EA extrait de l'EAA dont est issue la valence.

Remarquons qu'on peut considérer les valences illustrant les possibilités de liaisons d'un EA en contexte comme des schémas de description locaux de voisinage des EAA (donc des EA), c'est à dire des indications sur les contextes potentiels de voisinage de tel ou tel EA. Ce schéma local n'a a priori pas obligatoirement d'existence en contexte, et peut de toute façon être supplanté par ce que l'annotateur décide finalement de faire. Inversement, il est possible d'utiliser les prescriptions fournies par un schéma de description avec les mêmes mécanismes que ceux des valences, en considérant les relations comme des valences locales des EAA utilisés dans les dimensions d'analyse du schéma de description.

.

Les valences permettent donc ;

• en précisant un entour de contextualisation indicatif dans le flux, d'expliquer dans la base de connaissances le sens et la signification d'un terme d'annotation, en plus des indications dues à l'organisation de la base de connaissances. On peut donc dire que les valences prescrivent un << signifié en puissance >> pour l'EAA. A l'inscription dans le flux, ce signifié en puissance peut être actualisé (révélé au jour).
• de fournir des indications d'annotation à l'annotateur, qui peut suivre ou non ces indications. Une aide à la description peut, entre autres, se baser sur ces indications.
• de fournir des indications de recherche utiles pour la construction de graphes potentiels de contextualisation : tel EA pourra sans doute se trouver en relations avec tel ou tel autre.
• enfin, il est possible de les utiliser pour << apprendre >> sur l'utilisation des éléments de la base de connaissances en contexte, et ainsi les compléter.

Exploitation d'une base Strates-IA

Après avoir décrit quelques outils de manipulation et d'exploitation des Strates-IA basés sur les graphes potentiels exprimant des contextes, nous allons maintenant montrer de quelles manières il est possible de les utiliser pour les différentes tâches d'un système d'information audiovisuel.

Plus particulièrement, nous allons successivement étudier les tâches d'indexation, de recherche, de navigation, d'analyse, de génération sous l'angle de la description et de la contextualisation.

Nous supposons qu'une base de connaissances a été mise en place et que des schémas de description existent, ainsi qu'au minimum les dimensions d'analyse qui sont utilisées par ces derniers.

Annoter -- indexer

A l'introduction d'un flux dans le système est créée une UAV le représentant, annotée par exemple par l'EA < Flux > . A partir de cette annotation primale, qui n'est pas réalisée par l'utilisateur, toute annotation devient sur-annotation d'une partie de flux désignée par une UAV. Quelle que soit la suite de l'annotation, on reste donc dans le cadre de manipulation du système, qui est le graphe des Strates-IA.

Toute annotation se fera dans le cadre d'un schéma de description, lequel sera plus ou moins prescriptif.

Par exemple, une annotation totalement libre suivra un schéma de description lâche ne contenant qu'une dimension d'analyse, laquelle spécifiera tous les éléments d'annotation abstraits, c'est à dire une vue totale de la base de connaissances. A l'opposé, un schéma totalement prescriptif donnera exactement le format de structuration du document à atteindre. Le rôle de l'annotateur se limitera à l'instanciation du schéma en un graphe d'annotation, donc au choix des limites temporelles des unités audiovisuelles, et à celui des EAA inscrits dans le flux parmi ceux proposés par les dimensions d'analyse.

Entre ces deux extrêmes, tout est imaginable : par exemple un schéma de description général sera composé d'un schéma de description minimal qui guidera le début de l'annotation, et d'un schéma très lâche autorisant l'utilisateur à compléter à volonté l'annotation. Lorsque l'annotation est libre, l'utilisateur peut définir ses propres dimensions d'analyse et ses propres schémas de description, y compris en cours d'annotation. Cela revient à spécifier ses propres visées de description pour annoter ensuite en les suivant.

L'utilisation de plusieurs schémas de description différents, par exemple pour réindexer un flux déjà indexé est possible : plusieurs descriptions différentes, éventuellement générées par des annotateurs différents sont donc naturellement gérées par le modèle. La relation élémentaire permet de plus, de façon libre de mettre en relation n'importe lesquels des éléments d'annotation en place dans le graphes Strates-IA, y compris ceux ayant été mis en place suivant deux schémas de description différents.

A l'inscription dans le flux d'un élément d'annotation, l'utilisateur doit donner une valeur à ses attributs obligatoires, ainsi qu'éventuellement aux autres. Il peut également le contextualiser en le mettant en relation élémentaire avec d'autres EA. Cette mise en relation peut consister :

• à continuer à suivre un schéma de description, si celui-ci est prescriptif, auquel cas c'est le système qui spécifie les éléments à mettre en relation, et la manière de le faire ;
• à utiliser une valence de l'élément d'annotation qui vient d'être mis en place, auquel cas le système propose une mise en relation, et éventuellement la création de l'EA cible de la relation si celui-ci n'existait pas déjà ;
• à créer ou à rechercher librement l'EA cible de la relation, en explorant le contexte de l'EA qui vient d'être inscrit dans le flux.

Des assistants d'annotation, particulièrement ceux spécialisés dans l'analyse vidéo peuvent venir en aide à l'annotateur quand celui-ci analyse le flux suivant une dimension d'analyse liée à des caractéristiques calculables. Par exemple, analyser le flux suivant une dimension d'analyse liée aux plans peut prendre appui sur un assistant réalisant le découpage automatique du flux. De la même manière, un assistant utilisant les flux image et son peut aider l'utilisateur à repérer dans le flux les occurrences d'un personnage par exemple.

   
Rechercher

Rechercher un élément des Strates-IA (plus particulièrement une séquences audiovisuelle, c'est à dire une UAV) consiste à le décrire tel qu'on aimerait le trouver, c'est à dire à le décrire contextuellement à partir d'éléments connus.

Les modes de recherche sont multiples, et se ramènent toujours, en dernière analyse, en un ensemble de graphes potentiels caractérisés qu'il s'agit d'instancier²².

.

Tout d'abord, la recherche peut consister à instancier des << schémas de recherche >> déjà mis en place, et qu'il convient de compléter, à charge pour un assistant automatique de mener la recherche en précisant les graphes potentiels caractérisés sous-entendus par les schémas. Par exemple, un schéma basique consiste à proposer à l'utilisateur de retrouver des documents annotés par un ensemble de termes (EA exprimant des caractéristiques de haut-niveau). Il s'agit alors de retrouver une UAV annotée directement par < Document > , et annotée, dans un contexte d'inclusion temporelle (R_it), par les termes cherchés. Alors le système -- ou plutôt un assistant de recherche spécialisé -- mettra en place un graphe potentiel tel que celui de la figure 2.25, l'instanciera, et retournera les UAV résultats.

 

  

Figure: Un graphe potentiel caractérisé de recherche mis en place automatiquement par un assistant : l'élément recherché est un document annoté par trois << mots-clé >> Terme1, Terme2 et Terme3. Par exemple, si on avait Terme1 = Le Renard, Terme2 = Le Corbeau et Terme3 = Fromage alors l'instanciation du graphe potentiel dans le graphe de description de la figure 2.20 permettrait de récupérer l'UAV UAV1 comme éléments Recherché.

Ensuite, la recherche avec des graphes requêtes peut se baser sur la construction par l'utilisateur de sa requête comme annotation d'un flux virtuel.

Cette annotation se fait en utilisant un schéma de description, libre ou contraint suivant que l'utilisateur n'a pas d'idée préconçue sur l'annotation qu'il cherche, ou au contraire sait quel schéma de description a été utilisé pendant la phase d'indexation. Dans tous les cas, il met en place les annotations qu'il recherche, ainsi que la manière dont il souhaite que celles-ci soient contextualisées, de façon plus ou moins lâche, en utilisant par exemple des dimensions d'analyse pour certains nuds du graphe requête.

Une recherche par l'exemple consiste à annoter un flux réel (l'exemple) en suivant un schéma de description, et à rendre génériques certains sommets avant d'instancier le graphe potentiel ainsi obtenu.

Une recherche à l'aide d'un exemple connu du graphe Strates-IA consiste à extraire un sous-graphe d'annotation de celui-ci afin de s'en inspirer pour mettre en place la requête²³

.

Dans tous les cas, rechercher des objets des Strates-IA consiste à décrire ceux-ci comme objets génériques dans leurs relations avec d'autres objets génériques, ceux-ci pouvant correspondre à des objets non connus, ou au contraire à des objets connus (auquel cas ils serviront de point de départ à la recherche d'instances). Bref, il s'agit de décrire les objets visés en les contextualisant :

• par rapport à d'autres objets génériques, par exemple figure 2.25 l'UAV totalement générique < * > , < Document > , < Terme1 > , < Terme2 > , < Terme3 > sont des objets virtuels en relations contextuelles ;
• par rapport à des objets connus, par exemple figure 2.25 < EAA:Document >, < EAA:Terme1 >, < EAA:Terme2 >, < EAA:Terme3 > sont des objets connus, des éléments d'annotation abstraits de la base de connaissances, qui peuvent être mis en correspondance de façon unique avec des objets du graphe Strates-IA.

Dans un espace d'information tel que le graphe Strates-IA, on peut donc considérer que l'on cherche toujours quelque-chose dont on connaît le contexte, c'est à dire que l'on vise un point de l'espace depuis plusieurs points connus à la fois, de telle sorte que les différentes visées y convergent.

Naviguer

La navigation résulte d'un principe similaire, à ceci près qu'un des points de visée est celui où l'on se trouve réellement, et que l'on souhaite naviguer vers le point cherché.

Naviguer dans le graphe consiste donc toujours à mettre en place une relation contextuelle potentielle dont le sommet origine correspondra à l'élément du graphe où l'on se trouve. Après l'instanciation, les sommets extrémité des sous-graphes instances seront proposés à la navigation.

Plusieurs conséquences en découlent.

.

Première conséquence, la navigation prend plusieurs formes suivant les types des éléments origine et extrémité des relations contextuelles potentielles.

Considérons pour commencer les formes de navigation les plus importantes, à savoir celles mettant en jeu des unités audiovisuelles, c'est à dire des morceaux de flux :

• aller des UAV vers les UAV correspond à une navigation dans le flux, dans le ou les documents, médiés par le substrat constitué par les EA ;
• aller des UAV vers les EAA correspond à un passage d'une vue du flux vers une vue abstraite issue de la base de connaissances. Par exemple, si une UAV est annotée par < Chirac > , elle l'est également par < Homme Politique > en utilisant entre autre un contexte lié à une relation de spécialisation dans la base de connaissances :
• passer d'un EA à une UAV ou d'une UAV à un EA correspond au passage de l'annotation au flux, c'est à dire de la documentation vers les documents (et inversement) ;

Si l'on considère maintenant, en étendant quelque peu la concept de navigation hors des documents visés par l'annotation mais dans le système de documentation lui-même :

• aller des EAA vers les EAA correspond à une navigation exploratoire dans la base de connaissances ;
• aller d'EA en EA correspond à une navigation dans l'annotation, par exemple en l'absence du flux lui-même comme fichier audiovisuel à visualiser ;
• aller des EAA vers les UAV ou les EA correspond à une recherche d'utilisation des EAA dans le flux, voire peut s'apparenter à une recherche telle que nous l'avons définie dans la section 2.4.2.

.

Deuxième conséquence, il apparaît que la navigation et la recherche par requêtes relèvent exactement du même principe, c'est à dire que ces deux modes de recherche sont unifiés dans le cadre des Strates-IA.

Si nous reprenons le principe des << fenêtres >> de [56], nous pouvons considérer un système dans une fenêtre ou vue dans laquelle se situe l'utilisateur, et à partir de laquelle il s'ouvre, aussi bien par requêtes que par navigation, d'autres vues qui vont lui permettre de continuer son exploration-recherche. L'extension ici réalisée consiste à intégrer dans le schéma de la base de document les index et les descripteurs abstraits permettant d'y accéder, c'est à dire à considérer un système d'exploitation documentaire dans son ensemble (figure 2.26).

  

Figure 2.26: Etendre le système pour considérer navigation et requêtes de la même manière

Les liens de navigation sont des éléments d'annotation d'unités audiovisuelles²⁴, et autant de types de navigation qu'il y a de manière de contextualiser sont alors imaginables. Médier le résultat d'une requête par l'endroit du graphe ou l'on se trouve (cf. [70]) est également trivial.

.

Troisième conséquence, la navigation ne consiste plus simplement à aller d'un nud à un nud incident, mais l'on peut considérer des chemins de navigation de longueurs quelconques correspondant à toutes les manières de contextualiser possibles. Le calcul s'appuie sur le graphe pour proposer les liens, les liens proposés dépendent de la tâche en cours et ne sont pas figés, puisqu'ils participent de la documentation des documents audiovisuels et sont exploités en tant que tels.

La navigation dans les Strates-IA s'appuie donc sur un calcul des liens à proposer à l'utilisateur en fonction des visées de contextualisation de celui-ci (i.e. en fonction du contexte vers lequel il entend naviguer).

Analyser

L'analyse d'un élément Strates-IA consiste en son éclairage suivant un ou plusieurs contextes particuliers. Suivant les types de contextes considérés, les objectifs de l'analyse ne sont pas les mêmes.

Annoter contextuellement une UAV consiste à chercher dans son contexte quels éléments pourraient l'annoter. Il ne s'agit pas comme ci-dessus de naviguer jusqu'à ceux-ci, mais bien de les considérer comme annotant l'UAV considérée.

Cela peut par exemple se faire en appliquant à l'UAV des relations contextuelles potentielles, spécifiées explicitement ou implicitement. Dans le dernier cas, on peut par exemple déterminer un contexte en utilisant une relation contextuelle potentielle UAV-UAV, et spécifier les types d'éléments intéressants par une dimension d'analyse, c'est à dire un ensemble de filtres de description. Alors l'assistant de construction de vue contextuelle étend les relations contextuelles en les joignant aux filtres de désignation²⁵.

.

Analyser une UAV suivant une dimension d'analyse consiste à lui appliquer une grille de lecture, et revient fondamentalement au même que l'annotation contextuelle que nous venons de présenter. C'est au niveau des modes de présentation de l'analyse que la différence principale se fera sentir, ainsi que sur les UAV auxquelles elle s'appliquera : on étudiera plutôt une UAV précise et de durée faible (en regard de celle du flux) afin d'y apporter des précisions ; on étudiera une UAV représentant un flux entier selon une dimension d'analyse.

Typiquement, l'analyse d'un flux suivant une ou plusieurs dimensions d'analyse consiste à en extraire les EA appartenant aux dimensions et à les présenter sur une ligne de temps de telle sorte que l'utilisateur puisse se faire une idée des co-occurrences -- temporelles ou non -- des annotations. On peut envisager ce genre d'analyse comme une << linéarisation >> de l'annotation suivant un certain nombre d'axes, une projection des visées d'analyse sur le flux.

Dans le cadre de l'annotation textuelle, [218] remarque que << l'application d'un même mot-clé à deux passages différents, où le mot n'est pas nécessairement présent dans les textes commentés eux-mêmes, est la création d'un lien conceptuel, d'une corrélation, l'élaboration d'une << grille de lecture >> >>. L'écriture sur le document est en effet déjà analyse, ainsi que le choix d'un terme plutôt qu'un autre. La co-occurence d'un terme dans plusieurs document est une relation contextuelle entre deux UAV passant par la base de connaissances. L'analyse inter-documentaire peut se baser sur ce genre de contextes pour étudier par exemple comment deux documents audiovisuels << résonnent >> entre eux.

Editer des documents, construire des documents pour la présentation

L'édition d'un document audiovisuel se base sur la recherche de parties de documents en vue de leur montage dans un nouveau document. Cela ne peut donc se concevoir que si des connaissances suffisantes existent dans la base.

Ces connaissances de montage se basant a minima sur des relations temporelles entre les UAV, le modèle des Strates-IA est à même de les prendre en compte dans des graphes de description. Il s'agirait alors de créer un graphe G_V annotant le document virtuel tel qu'on le souhaite, des relations temporelles étant mises en place entre les UAV virtuelles. Alors un ou plusieurs assistants adéquats se chargeraient de chercher dans le graphe général Strates-IA des instances de sous-parties du graphe G_V qui correspondraient à la description. Le reste du graphe G_V, c'est à dire les sous-parties non utilisées, pourrait alors correspondre à une annotation a priori du nouveau document.

Dans le même ordre d'idée, mais pour des applications plus simple, l'édition ou la génération automatique de présentations se basent sur la construction de documents réponses aux requêtes de l'utilisateur. Les graphes de description des nouveaux documents de présentation peuvent alors être créés automatiquement en fonction de la présentation désirée, avec des sous-parties correspondant aux diverses requêtes de l'utilisateur.

.

Les Strates-IA permettent donc d'une certaine manière de décrire en contexte des parties du nouveau document à mettre en place, le système cherchant dans le graphe des UAV correspondant le plus possible à celles cherchées.

Extraire une documentation

Les Strates-IA peuvent être utilisées comme indexation de base, descriptions de documents en vue d'une utilisation dans d'autres systèmes et suivant d'autres formats. On peut alors envisager d'extraire pour un graphe Strates-IA une hiérarchie documentaire qui correspondra à une vue du document liée à un besoin particulier, et lui sera attachée comme documentation dans un autre format (par exemple du HTML).

Dans ce cas de figure, une description en Strates-IA ne sert que de base à une description, dans un format qui peut être autre, dans laquelle une contextualisation est réalisée et présentée à l'utilisateur. Cela se rapproche d'ailleurs d'une vue d'un graphe Strates-IA présentée à l'utilisateur dans le cadre de son interaction avec le système d'information audiovisuelle. Les différentes informations utiles présentées à l'utilisateur subissent une médiation graphique, et expriment d'une manière ou d'une autre la présentation d'un élément des Strates-IA mis en contexte avec (contextualisé par) d'autres éléments. C'est cette approche systématique de présentation d'éléments des Strates-IA comme vues contextuelles que nous adoptons dans notre prototype.

Conclusion

Nous avons présenté dans ce chapitre comment il était possible d'exploiter contextuellement les modèles de représentation de documents audiovisuel en Strates Interconnectées par les Annotations. L'exploitation se base sur un outil fondamental, le graphe potentiel, qui permet d'exprimer des contextes ; ainsi que sur d'autres outils tels que les dimensions d'analyse et les schémas de description. La dernière section du chapitre est destinée à la présentation des différentes utilisations qu'il est possible de faire d'un système fondé sur les Strates-IA.

La suite de ce document sera consacrée à la présentation des prototypes réalisés et des fonctionnalités qu'ils implantent (chapitre 3) ; à l'étude d'un cadre original de modélisation d'un système d'information dans l'objectif d'en stocker l'expérience d'utilisation de telle sorte que celle-ci soit expliquée (chapitre 4) ; ainsi qu'à une discussion plus générale sur les documents et les connaissances nous permettant d'y situer l'approche des Strates-IA (chapitre 5).