Stasjoner, inntil 500 meter utenfor plattformender (N=31)

Tout d’abord, nous pr´esentons le mod`ele de base des graphes conceptuels. Nous rappelons donc que celui-ci est bien-fond´e d’un point de vue logique, le raisonnement y ´etant correct et complet au regard de la logique du premier ordre (FOL). La connaissance ontologique y est g´en´eralement cod´ee dans un support (´egalement appel´e vocabulaire) permettant de soutenir l’expression des graphes basiques (BG) ainsi que l’op´eration fondamentale de raisonnement, un homomorphisme de graphe appel´e projection.

D´efinition 81 (Support des graphes basiques). Le BG support est un tuple S = hTC, TR, I, σi tel que :

- TC et TR sont des ensembles finis disjoints de tpes.

- TC est un ensemble de types de concept partiellement ordonn´es par la relation ≤ dans lequel il existe un ´el´ement universel (qui est le superconcept de tous les ´el´ements), not´e >. - TR est un ensemble de types de relation partiellement ordonn´es par la relation ≤, et par- titionn´e en sous-ensembles T_R1, . . . , T_Rk de types de relation respectivement d’arit´e 1, . . . , k, et dans lesquels les ´eventuels ´el´ements universels sont not´es >1, . . . , >k. L’arit´e d’une relation r est not´ee arite(r). Deux relations avec deux arit´es diff´erentes ne sont pas com- parables par ≤.

6.1. Le formalisme des graphes conceptuels - I est un ensemble de marqueurs individuels qui est disjoint de TC et TR. De plus, on note * le marqueur g´en´erique. On note l’ensemble des marqueurs M = I ∪ {∗}. Cet ensemble est muni de l’ordre partiel ≤ suivant : les ´el´ements de I sont deux `a deux incomparables, et ∀ m ∈ I, m ≤ ∗. Chaque ´el´ement de I peut ˆetre assign´e `a plusieurs types ainsi qu’`a tous les supertypes de ceux-ci.

- σ associe `a chaque relation j-aire (r ∈ T<sub>R</sub>j) une signature c’est `a dire un j-uplet de types de concept (σ(r) ∈ (TC)j), o`u le i-`eme concept est le type maximal pour le i-`eme argument de la relation. Les signatures respectent les ordres sur TR et TC c’est-`a-dire : ∀ r1, r2 ∈ T_Rj, r1 ≤ r2 ⇒ σ(r1) ≤ σ(r2), i.e. pour tout 1 ≤ i ≤ j, le i-`eme argument de σ(r1) est plus sp´ecifique (au sens large) que le i-`eme argument de σ(r2).

Exemple 62. La Figure 6.1 d´ecrit une partie du BG vocabulaire utilis´e dans un syst`eme d’ar- gumentation `a la Dung. > Entit´e Ens Ext Arg AF (a) TC >2 output (AF,Ext) relation (Arg,Entit´e) R (Arg,Arg) contr.

(Arg,Arg) (Arg,Arg)refut. ∈ (Arg,Ens) >1 prop (AF) Eba (Ext) Ead (Ens) Epr (Ext) Esc (Ens) Ena (Ext) Est (Ext) bf

(AF)cyclique(AF)

(b) TR et σ

Figure 6.1 – Exemple graphique de vocabulaire

Un tel vocabulaire d´ecrit des connaissances ontologiques de nature taxonomique telles que : – “Une extension (Ext) est un ensemble (Ens)”.

– “L’extension pr´ef´er´ee (Epr) est une sorte d’extension admissible (Ead)” (ou plus pr´ecis´ement la propri´et´e d’ˆetre une extension pr´ef´er´ee est une sp´ecialisation de la propri´et´e d’ˆetre une extension admissible).

– “L’extension na¨ıve (Epr) est une sorte d’ensemble sans-conflit (Esc)”.

– “Le caract`ere bien fond´e (bf ) et cyclique sont des propri´et´es d’un syst`eme d’argumenta- tion”.

– “R est une relation (d’attaque) entre deux arguments, sa signature est (Arg, Arg)”. – “∈ est une relation (d’appartenance) entre un argument et un ensemble, sa signature est

(Arg, Ens)”.

– “Les relations de contrari´et´e (contr.) et de r´efutation (refut.) sont des sortes de relation d’attaque (R)”.

Les faits sont repr´esent´es par des graphes basiques, d´efinis ci-dessous. Un BG permet d’asserter l’existence d’entit´es et de relations entre ces entit´es. Une entit´e peut ˆetre vue comme une instance d’un ou plusieurs types de concepts de TC, qui est soit identifi´ee (on lui associe un ´el´ement de I), soit inconnue, on lui associe le marqueur g´en´erique. Ainsi, en relation avec le support, un graphe de base est d´efini comme suit :

D´efinition 82 (Graphes basiques). Etant donn´e un support S = hTC, TR, I, σi, un graphe basique G = hCG, RG, LG, etiqGi est un multigraphe biparti ´etiquet´e tel que :

• (CG, RG, LG) est un multigraphe biparti, fini et non orient´e. CG est l’ensemble des noeuds concepts de G, RGest l’ensemble des noeuds relations de G, LGest la famille des arˆetes11. • etiq_G est une fonction qui ´etiquette les noeuds et les arˆetes de (CG, RG, LG) et qui satis-

fait :

1. Un noeud concept c est ´etiquet´e par une paire (type(c), marqueur(c)) o`u type(c) est un ensemble de types12 de TC et marqueur(c) ∈ I ∪ {∗}.

2. Un noeud relation r est ´etiquet´e par type(r) ∈ TR.

3. Le degr´e d’un noeud relation r est ´egal `a l’arit´e de type(r).

4. Les arˆetes incidentes au noeud relation r sont totalement ordonn´ees et sont ´etiquet´ees de 1 `a arite(type(r)). On note (r, i, c), une arˆete entre r et c ´etiquet´ee i.

Un ordre sur les ´etiquettes peut ˆetre d´efini, il permettra de raisonner par la suite `a l’aide de ces graphes. Soient deux ´etiquettes de sommets concept (t, m) et (t0, m0), (t, m) ≤ (t0, m0) si m ≤ m0 (voir l’ordre sur les marqueurs dans la D´efinition 81) et t ≤ t0, i.e ∀ t0_i ∈ t0, ∃ tj ∈ t avec tj ≤ t0i (si t et t0 sont des types simples, la condition s’´ecrit simplement t ≤ t0).

Exemple 63. Les graphes F et T de la Figure 6.2 repr´esentent des syst`emes d’argumentation en tant que faits, le graphe F repr´esente le fait : “Il existe un argument qui attaque un argument qui attaque β”, le graphe T repr´esente le fait : “ il existe γ un argument contrarie les arguments α, β, δ, avec δ qui contrarie l’argument γ”, enfin le graphe G repr´esente le fait : “il existe un syst`eme d’argumentation qui est bien-fond´e.” Nous pouvons ´egalement repr´esenter les graphes

Arg : β 2 R 1 Arg : * 2 R 1 Arg : *

Arg : γ contr. contr. Arg : δ Arg : α Arg : β contr. contr. 1 2 2 1 1 2 1 2 AF : * bf 1 z}|{ z }| { z}|{ F T G

Figure 6.2 – Exemple de fait

basiques comportant des relations unaires ou binaires sur une ligne d’´edition, `a savoir pour G dans cet exemple : [AF : *]→(bf ). Il peut ˆetre choisi dans certains cas de repr´esenter les ´etiquettes des arˆetes li´ees aux relations unaires et binaires par des arcs pour simuler les num´eros d’arit´e 1 et 2, comme par exemple dans le cas d’un graphe d’attaque.

Un graphe basique est sous forme normale si chacun de ses marqueurs individuels apparaˆıt exactement une fois (autrement dit, on n’a pas deux sommets concepts qui repr´esentent la mˆeme entit´e identifi´ee).

11. Multigraphe signifie qu’il peut exister plusieurs arˆetes entre deux sommets. Biparti signifie que l’ensemble des sommets est partitionn´e en deux ensembles, ici CGet RG, tels qu’il n’existe pas d’arˆete entre des sommets

d’un mˆeme ensemble.

12. Les graphes de base d´efinis ici sont ´etendus `a des types de concepts conjonctifs. Pour plus de d´etails sur cette notion voir [CM08].

6.1. Le formalisme des graphes conceptuels Ce formalisme de base est muni d’une s´emantique en logique du premier ordre par le biais d’une transformation not´ee Φ. Les types de concept se traduisent en pr´edicats unaires, les re- lations en pr´edicats de mˆeme arit´e, et les marqueurs individuels en constantes. L’ensemble des formules Φ(S) associ´e `a un support S traduit naturellement les ordres partiels sur TC et TR (si t2 ≤ t1, on a la formule ∀ x1, . . . , xk (t2(x1, . . . , xk) ⇒ t1(x1, . . . , xk)), o`u k est l’arit´e des pr´edicats t1 et t2).

Un BG G se traduit par une formule Φ(G) construite comme suit. A tout sommet concept est associ´e un terme, qui est la constante associ´ee `a son marqueur individuel le cas ´ech´eant, sinon une nouvelle variable. A tout sommet concept ou relation est associ´e un atome form´e `a partir du pr´edicat associ´e `a son type, et du terme associ´e au sommet concept ou des termes associ´es aux entit´es voisines du sommet relation. Si le sommet a un type conjonctif, on obtient un tel atome par type “primitif”. Φ(G) est la conjonction de ces atomes ferm´ee existentiellement. Dans l’Exemple 63 : Φ(F ) = ∃x, ∃y(Arg(β) ∧ Arg(x) ∧ Arg(y) ∧ R(x, β) ∧ R(y, x)) et Φ(G) = ∃x(AF (x) ∧ bf (x)).

La notion fondamentale pour raisonner sur les BG est l’homomorphisme de graphes, couramment appel´ee “projection”. Elle t´emoigne de la pr´esence des connaissances encod´ees par un graphe dans un autre. En termes logiques, cette notion se traduit par la d´eduction.

D´efinition 83 (Projection). Soient F = hCF, RF, LF, etiqFi et T = hCT, RT, LT, etiqTi, deux graphes basiques d´efinis sur un mˆeme support. Une projection Π de F dans T est une application de CF dans CT et de RF dans RT, pr´eservant les arˆetes et pouvant sp´ecialiser les ´etiquettes des concepts et des relations, c’est-`a-dire :

– ∀ (r, i, c) ∈ LF, (Π(r), i, Π(c)) ∈ LT, – ∀ e ∈ CF ∪ RF, etiqT(Π(e)) ≤ etiqF(e).

On dit alors que le graphe F se projette dans le graphe T . On note Π(F ) l’image de F dans T . La notion de projection fournit naturellement un m´ecanisme d’interrogation : F peut ˆetre vue comme une requˆete, T comme un fait donn´e, et toute projection Π de F dans T fournit une r´eponse.

Exemple 64. Dans la Figure 6.3, F exprime la requˆete : “existe t-il un argument qui attaque un argument qui attaque l’argument β ? (autrement dit l’argument β est il d´efendu ?)”. On a un homomorphisme (projection) de F dans T . Donc l’argument β est bien d´efendu.

Un graphe basique est irredondant s’il ne se projette pas dans l’un de ses sous-graphes stricts. Autrement dit, il encode ses connaissances de fa¸con minimale. Tout graphe peut ˆetre mis sous une forme irredondante qui lui est ´equivalente.

Le th´eor`eme suivant exprime le fait que l’op´eration de projection est ad´equate et compl`ete par rapport `a la d´eduction.

Th´eor`eme 2 (Ad´equation et compl´etude de la projection). Soit F et T deux graphes basiques d´efini sur un support S avec T sous forme normale. Le graphe F se projette dans le graphe T ssi Φ(S), Φ(T ) |= Φ(F ).

Exemple 65. La Figure 6.4 repr´esente le graphe Q exprimant la requˆete suivante : “Existe t-il un syst`eme d’argumentation tel que les extensions de base, stable et pr´ef´er´ee co¨ıncident ?”. Lorsque cette requˆete est appliqu´ee au graphe G de la Figure 6.2, celle-ci n’a pas de r´eponse, alors qu’intuitivement elle devrait car tout syst`eme bien fond´e poss`ede une extension de base,

Arg : β 2 R 1 Arg : * 2 R 1 Arg : * Arg : γ contr. contr. Arg : δ Arg : α Arg : β contr. contr. 1 2 2 1 1 2 1 2 Π([ Ar g , β ]) Π(( R )) Π([ Ar g ,∗ ]) Π(( R )) Π([ Ar g ,∗ ]) F T Π z}|{ z }| {

Figure 6.3 – Exemple de requˆete

AF : * output Ext : * Epr Est Eba 1 2 1 1 1 z }| { Q

Figure 6.4 – Exemple de requˆete

qui est `a la fois stable et pr´ef´er´ee. Ceci est dˆu `a l’absence de certaines informations dans ce graphe.

Il est donc primordial pour satisfaire des requˆetes de rajouter des informations de nature ontolo- gique “en marge” du graphe. Ces informations manquantes peuvent ˆetre cod´ees de fa¸con g´en´erique sous forme de BG-r`egles.