Procedures for a cooperative building of knowledge bases by multiple users
Philippe A. MARTIN
This work has been published as part of
my
Ph.D thesis:
"Exploitation de graphes conceptuels et de documents structurés et hypertextes
pour l'acquisition de connaissances et la recherche d'informations"
(University of Nice - Sophia Antipolis, France, October 14, 1996).
Abstract.
This paper describes procedures allowing various users to incrementally
build a knowledge base (KB) composed of an ontology (i.e. a type hierarchy and
definitions or constraints associated to the types) and assertions of facts
represented using these types.
Conceptual Graphs [CGs] are the knowledge
representation language used for illustrating our procedures.
As opposed to other knowledge integration approaches, our procedures do not
try to merge knowledge built separately, but to allow and ease a maximal
integration of knowledge at its insertion in the KB. Thus, the issue
of merging different ontologies is not handled here. There is only one
ontology and the whole formalised knowledge must always be consistent.
The underlying philosophy is that, the real word being considered
unique and consistent, inconsistencies between pieces of knowledge (i.e.
various abstractions of the real world) do not reveal contradictions between
what is described but that at least one of these pieces is not enough
precisely represented, or in other words, is under-constrained.
Hence, a piece of knowledge cannot be added to the KB if that leads to
an inconsistency. In that way, the existing knowledge really acts as a guide
for the knowledge authors: they may precise their knowledge or knowledge of
other users; no such result can be achieved by a knowledge engineer having to
merge knowledge bases developped separatelly.
However, an important issue is that this approach does not imply that
users have to reach a consensus on type names, their intended meanings,
or the facts which are represented. To allow this, apart from the use of
aliases and display filters, the main ideas of our procedures are
the following ones.
1. A user may add or specialise any type or assertion in the KB provided
this doesn't violate constraints, e.g. exclusion links between types;
2. If a user (U0) does not agree with the specialisations (T1 and T2)
which have been created by other users (U1 and U2) from one of his/her
type or assertion (T0), U0 must add constraints to T0
so that the system can detect an inconsistency and repair it
by replacing in the ancestors of T1 and T2 the now overconstrained T0
by a "clone" (T0') equivalent to T0 before it was overconstrained.
U0 may choose or not to have clones of his/her types displayed
when s/he browse the hierarchy.
Thus, our approach is a way to support a maximal cooperation between
users without having to agree with each other.
Such cooperation is asynchronous: it does not need the users to discuss
together or even to know each other. Thus, we hope that the approach is
scalable.
On our experimental site, in order to ease the construction of
the KB, we will initialise it with the natural language ontology
WordNet [WordNet]
plus a top-level ontology merging various other ones and insuring sufficient
constraints to avoid some of the most common problems of reusing a large
ontology for knowledge representation.
Applications of our approach are discussed in the
WebKB documentation [WebKB].
Keywords.
Knowledge representation, knowledge integration,
ontology, corporate memories, asynchronous cooperation, CSCW.
Table of contents
- Goal: the reuse and integration of knowledge from multiple users
- Approach: integration of knowledge at its insertion
- Visualisation
- Notification of updates
- Creation or modification
- Destruction
- References
As opposed to other knowledge integration approaches, our procedures do not
try to merge knowledge built separately, but to allow and ease a maximal
integration of knowledge at its insertion in the KB.
Thus, the issue of merging different ontologies is not handled here.
There is only one
ontology and the whole formalised knowledge must always be consistent.
The underlying philosophy is that, the real word being considered
unique and consistent, inconsistencies between pieces of knowledge (i.e.
various abstractions of the real world) do not reveal contradictions between
what is described but that at least one of these pieces is not enough
precisely represented, or in other words, is under-constrained.
Hence, a piece of knowledge cannot be added to the KB if that leads to
an inconsistency. In that way, the existing knowledge really acts as a guide
for the knowledge authors: they may precise their knowledge or knowledge of
other users; no such result can be achieved by a knowledge engineer having to
merge knowledge bases developped separatelly.
Il semble plus rapide pour des cogniticiens travaillant a`
representer une meme expertise, de construire de maniere
cooperative et incrementale une meme hierarchie de types
plutot que de travailler chacun de leur cote, "en aveugle"
puis de fondre leurs hierarchies en une seule. En effet, dans le
premier cas, chaque cogniticien peut reutiliser les types d'autres
utilisateurs et positionner chacun de ses types, des leur
creation et de maniere directe ou indirecte, par rapport aux
types d'autres utilisateurs. Il complete donc ces types des autres
utilisateurs, ou les specialise ou encore les
generalise. L'introduction d'une incoherence dans la
hierarchie des types peut ainsi etre detectee et
corrigee au plus tot, par le systeme (e.g. la creation
d'un cycle ou d'un sous-type commun a` des types exclusifs) ou par
un cogniticien (e.g. un cogniticien averti des specialisations ou
generalisations effectuees par d'autres cogniticiens sur des
types qu'il a crees, peut remarquer une mauvaise
interpretation du sens qu'il accordait a` ces types, et modifier
la hierarchie pour corriger ces erreurs). Un type represente
des objets ayant certaines caracteristiques. Si deux cogniticiens
se rendent compte qu'ils n'accordent pas exactement les memes
cararacteristiques aux objets representes par un type, ces
cogniticiens font en realite reference a` deux notions
distinctes et deux types differents doivent etre crees
pour representer ces notions (ces deux types peuvent alors avoir
des noms utilisateurs identiques, i.e. des alias identiques, mais
auront des noms systeme differents). Il est interessant que
ces deux types soit interclasses avec differents liens, e.g. un
lien de specialisation ou un lien d'exclusion.
However, an important issue is that this approach does not imply that
users have to reach a consensus on type names, their intended meanings,
or the facts which are represented. To allow this, apart from the use of
aliases and display filters, the main ideas of our procedures are
the following ones.
1. A user may add or specialise any type or assertion in the KB provided
this doesn't violate constraints, e.g. exclusion links between types;
2. If a user (U0) does not agree with the specialisations (T1 and T2)
which have been created by other users (U1 and U2) from one of his/her
type or assertion (T0), U0 must add constraints to T0
so that the system can detect an inconsistency and repair it
by replacing in the ancestors of T1 and T2 the now overconstrained T0
by a "clone" (T0') equivalent to T0 before it was overconstrained.
U0 may choose or not to have clones of his/her types displayed
when s/he browse the hierarchy.
Thus, our approach is a way to support a maximal cooperation between
users without having to agree with each other.
Such cooperation is asynchronous: it does not need the users to discuss
together or even to know each other. Thus, we hope that the approach is
scalable.
Pour faciliter la construction cooperative et incrementale
d'une hierarchie de types par plusieurs utilisateurs, en minimisant
les conflits et la necessite pour les utilisateurs de se
rencontrer frequemment afin de negocier le choix des types, de
leurs noms, de leurs definitions et de leur organisation, nous
proposons le protocole suivant.
Un utilisateur peut mettre des alias sur les noms des types
crees par d'autres utilisateurs et visualiser et manipuler ces
types sous ces alias (ce qui permet un certain confort dans la
reutilisation des types et evite ou reduit les conflits de
noms de type entre utilisateurs). Par defaut, pour un utilisateur,
un type cree par un autre utilisateurs doit pouvoir etre
visualise et manipule avec le nom donne par son createur
concatene avec le nom identificateur de ce createur.
Un utilisateur peut ne visualiser que certains types de la hierarchie, e.g. les types crees par certains utilisateurs, les sous-types de certains types. Nous utilisons ici le terme "certains" a` chaque fois qu'un sous-ensemble de choses est specifie par un utilisateur, manuellement ou via une requete. Le systeme de filtrage peut etre similaire a` celui que nous avons implemente dans les menus de gestion de taxinomies de CGKAT (cf. section 5.2.2.1). Les types pourraient egalement etre colores de maniere differente suivant les utilisateurs qui les ont crees.
Un utilisateur peut poser des commentaires prives (i.e. visibles de lui-seul) sur des types crees par d'autres utilisateurs.
Un utilisateur peut demander au systeme a` etre averti de certains types de modifications, effectuees par d'autres utilisateurs sur certains types. Par modification de type, nous designons tout ajout/destruction de lien sur un type et tout ajout/destruction/modification de definition d'un type. Il semble interessant que le createur d'un type modifie soit par defaut averti par le systeme de cette modification a` moins qu'il n'ait exprime le desir contraire. De meme, le createur d'un sous-type (direct ou indirect) d'un type modifie peut par defaut etre averti si ce createur n'est pas l'auteur de la modification et s'il ne s'est pas oppose a` de tels avertissements.
Un utilisateur peut ajouter des liens entre des types ou des definitions a` des types (si le systeme ne detecte pas d'incoherence ou s'il peut la reparer par le systeme comme nous le verrons plus loin). Cet ajout est possible meme si ces types ont ete crees par d'autres utilisateurs.
Un utilisateur peut detruire des liens entre types ou modifier des definitions a` condition qu'il en soit le createur. Les points suivants sont destines a` permettre/faciliter la gestion de ces ajouts, modifications et destructions lorsque la hierarchie est construite/partagee par de multiples utilisateurs).
Ainsi, un utilisateur peut ajouter des informations sur un type qu'il n'a pas cree, a` condition que le systeme ne detecte pas d'incoherence entre ces nouvelles informations et celles deja` existantes sur ce type (quels que soient les utilisateurs les ayant creees). Mais il ne peut detruire ou modifier des informations sur ce type s'il ne les a pas creees.
Lorsqu'un lien redondant est ajoute, e.g. un lien de specialisation entre un type et un de ses sous-types, ce lien n'est pas enregistre (meme si les types relies ont ete crees par differents utilisateurs). Si l'ajout d'un lien entraîne la redondance d'un autre lien, ce dernier est supprime (meme si les types relies ont ete crees par differents utilisateurs) ;
Un utilisateur peut demander a` etre enregistre comme co-createur de certains liens et de certains types et de leurs supertypes, afin d'exprimer son accord et son interet pour ces types, leurs definitions et leur organisation au moment de cet enregistrement (il exprime ainsi qu'il aurait pu creer lui-meme cette partie de la hierarchie). Il semble interessant que le co-createur d'un type modifie soit par defaut averti de cette modification a` moins qu'il n'ait exprime le desir contraire. Un utilisateur doit pouvoir selectionner un sous-ensemble de types sur le fait qu'ils ont ete co-crees par certains utilisateurs, par exemple pour signaler qu'il desire ou non visualiser ces types.
Un utilisateur qui met un alias sur un type d'un autre utilisateur, ou l'utilise dans un GC, devient automatiquement co-createur de ce type. De meme, un utilisateur qui ajoute un lien entre des types devient co-createur de ces types, ainsi que de leurs supertypes au moment de cet ajout, a` condition qu'il ne soit pas deja` createur de ces types et de ces supertypes ;
Un utilisateur ne peut ajouter un lien entre des types, ni ajouter ou modifier une definition d'un type si cela entraîne une incoherence detectee par le systeme (e.g. un cycle de liens de specialisation ou un sous-type commun a` des types exclusifs) sauf lorsqu'il a cree ces types et que l'incoherence peut etre levee par le systeme. Les deux cas suivants illustre des levees d'incoherence possibles par le systeme.
Une levee d'incoherence doit permettre a` un utilisateur Ux d'ajouter de modifier des types qu'il a crees sans etre gene par les specialisations qui ont ete faites de ses types par d'autres utilisateurs (ce sont ces specialisations qui creent l'incoherence) : le systeme doit modifier (le moins possible) les liens ou les types des autres utilisateurs de maniere a` lever l'incoherence. En effet, il n'est pas envisageable que Ux attende que les autres utilisateurs corrige la maniere dont ils ont specialises ses types. Par ailleurs, la correction effectuee par le systeme peut etre partiellement ou entierement ou partiellement acceptee par les autres utilisateurs, i.e. peu ou pas modifiee par ces utilisateurs.
Soit A, B, X et Y des types ayant ete crees par un utilisateur Ux (X peut etre confondu avec A). Soit Z un type non co-cree par Ux et sous-type de X et de Y. Si
a) A et B sont exclusifs et que Ux ajoute un lien de specialisation entre X et Y qui rend Z sous-type de A et B (Z est alors sous-type de Y, X, A et B), ou bien
b) Z est sous-type de Y, X, A et B, et que Ux ajoute un lien d'exclusion entre A et B,
l'incoherence engendree peut etre corrigee par le systeme de la maniere indiquee ci-dessous. Le principe retenu est tout d'abord de "cloner" un des supertypes de Z cree par Ux, c'est a` dire de le remplacer par un type "clone" ayant les memes supertypes que le type clone sauf ceux qui entraînent l'incoherence. La figure ci-dessous illustre la methode (decrite apres la figure).
![]()
Soit SAB_Z l'ensemble des types A, B, Z et des types a` la fois supertypes de Z et sous-types de A ou de B. Soit Uz le createur de Z, soit Z' le plus grand supertype qui appartient a` SAB_Z et qui est sous-type direct d'un type Y1 appartenant a` SAB_Z et cree par Ux (si plusieurs types peuvent jouer le role de Y1, choisir n'importe lequel ou eventuellement demander a` Ux). Soit SZ' l'ensemble des supertypes de Z' et n'appartenant pas a` SAB_Z.
Le systeme cree un type atomique Y1' en specialisant les types de SZ' , i.e. en creant un sous-type commun aux types les plus specialises de SZ'. Cela ne devrait pas creer d'incoherence detectable par le systeme puisqu'il n'y en avait pas avant l'ajout du lien entre X et Y.
Le systeme detruit le lien de specialisation entre Y1 et Z' (ce qui supprime l'incoherence) et pose un lien de specialisation entre Y1' et Z'. Si la specialisation de Y1 avait ete effectuee via une definition pour le type Z', Y1 est remplace par Y1' dans le concept porteur du parametre formel de la definition. Le type Y1', son lien avec Z' et ses liens avec ses supertypes directs, sont crees par le systeme tout comme si Uz les avait crees lui-meme. Uz n'est plus co-createur de Y1. Les co-createurs de Z deviennent co-createurs de Y1' et ne le sont plus de Y1. Pour le createur et pour chaque co-createur, le nom sous lequel Y1' lui est visible peut par defaut etre construit avec celui sous lequel Y1 lui etait visible mais avec en plus un prefixe tel que "clone_de_".
Le systeme envoie un message a` Uz pour l'avertir de cette destruction et ces creations de remplacement.
Ainsi, Z herite des memes proprietes qu'avant la destruction du lien entre Y1 et Z' sauf de celles qui entraînaient l'incoherence detectee. L'operation effectuee par le systeme est donc une relaxation de contraintes pour lever l'incoherence. Grâce a` cela, un utilisateur peut s'il le desire poser des liens entre des types qu'il a crees sans se soucier de la façon dont d'autres utilisateurs ont specialise ces types (ces specialisations peuvent d'ailleurs etre invisibles aux yeux de cet utilisateur : la detection d'incoherence prend tous les types en compte, visibles ou non).
Si la hierarchie de types avait une structure de treillis, apres une telle operation, elle peut avoir perdue cette structure. Notons cependant que les types et les liens engendres par de telles relaxations de contraintes peuvent etre temporaires dans le sens où leurs "createurs" (ceux au nom de qui le systeme a cree ces types), une fois avertis de ces creations, vont probablement les remplacer par des types ou des liens plus adequats.
Lorsque l'ajout ou la modification d'une definition a` un type X par un utilisateur Ux ayant cree ce type, entraîne une incoherence et que celle-ci est due (entre autres) a` l'existence de sous-types de X crees par d'autres utilisateurs que Ux (soit Ez l'ensemble de ces sous-types), cette incoherence peut etre corrigee par le systeme de la maniere indiquee ci-dessous.
Le principe retenu est comme precedemment une relaxation de contrainte via le clonage d'un type : ici les types clones sont le type X et eventuellement certains de ses sous-types (le clonage est different de precedemment).
La figure ci-dessous illustre la methode (decrite a` la page suivante).
![]()
Le systeme insere entre X et ses supertypes directs, le type X' qui a les memes definitions que X avait avant l'ajout ou la modification de la definition. Il transfere a` X' les sous-types directs de X appartenant a` Ez (s'il y en a).
Appelons "cloner un type Y sous le type C" l'operation consistant tout d'abord a` inserer entre Y et ses supertypes directs qui ne sont pas sous-types de X, le type Y' (si Y est atomique, Y' est atomique, sinon Y' a les memes definitions que Y en remplaçant dans ces definitions le type du concept porteur de la variable par C) puis a` sous-typer C par Y'.
Appelons "clone de Y" le resultat du clonage d'un sous-type de X sous un sous-type de X'.
Le systeme effectue les operations suivantes :
pour chaque sous-type Y de X et
appartenant a` Ez ou ayant un sous-type appartenant a` Ez,
si Y n'appartient pas a` Ez,
si Y est un sous-type direct de X, cloner Y sous X',
sinon cloner Y sous le clone de son supertype direct sous-type de X
sinon (Y appartient a` Ez),
si Y est un sous-type direct de X
remplacer le lien de specialisation entre X et Y
par un lien de specialisation entre X' et Y
sinon
soit G le supertype direct de Y qui est sous-type de X, soit G' le clone de G,
remplacer le lien de specialisation entre G et Y
par un lien de specialisation entre G' et Y.
Si la specialisation de G avait ete effectuee via une definition pour le type Y,
Y1 est remplace par Y1' dans le concept porteur du parametre formel de
cette definition.
Les operations de clonage et de remplacement de liens ci-dessus sont, tout comme dans le cas precedent, des operations de relaxation de contraintes destinees a` supprimer des incoherences. Les "createurs" des types et les liens ainsi crees sont les createurs des types de Ez. Si un clone est necessaire pour lever les incoherences creees par plusieurs types de Ez, l'un seulement des createurs de ces types devient createur des clones, les autres createurs deviennent co-createurs de ces clones. Les createurs des types de Ez ne sont plus co-createurs du type X et des types clones. Les noms sous lesquels ces createurs voient le type X' et les clones peuvent par defaut etre construits en utilisant respectivement les noms sous lesquels il voyaient X et les types qui ont ete clones mais avec en plus un prefixe tel que "clone_de_"..
Le systeme envoie un message aux createurs de chacun des types de Ez afin de les avertir des liens detruits et des types et liens crees en leurs noms.
Ainsi, un utilisateur peut ajouter des definitions a` des types qu'il a crees sans se soucier de la façon dont d'autres utilisateurs ont specialise ces types. Ceci peut cependant entraîner la creation de nombreux types artificiels. Il est donc preferable qu'un utilisateur prenne en compte la façon dont ses types ont ete specialises par d'autres utilisateurs avant de les modifier. Ainsi par exemple, plutot que d'ajouter des definitions a` ses types, il peut etre preferable d'ajouter des sous-types definis a` ces types.
Un utilisateur Ux qui, etant donne une modification d'un de ses types par un autre utilisateur Uy, comprend que Uy a mal interprete le sens qu'il accordait a` ce type, peut aider Uy (et la construction cooperative de la hierarchie de types) en ajoutant a` son tour plus d'informations a` ses types de maniere a` expliciter l'incoherence et la rendre detectable par le systeme. Le systeme va alors modifier certains liens crees par cet autre utilisateur de maniere a` reparer cette incoherence puis va avertir cet utilisateur afin qu'il re-etudie l'organisation de ses types. Ainsi,
1) l'utilisateur Ux ne modifie pas directement les types de Uy mais precise ses types,
2) des modifications minimales pour lever l'incoherence sont effectuees et automatiquement,
3) Uy peut re-etudier quand il le souhaite la maniere dont ses types peuvent reutiliser les types de Ux (ce dernier n'est pas bloque en attendant les corrections de Uy).
Notons que pour expliciter l'incoherence et ainsi engendrer des corrections, Uy peut poser un lien d'exclusion entre un de ses types et l'un de ceux de Uy. S'il utilise cette facilite, il doit prealablement etudier les types de Uy et leur organisation, de maniere a` s'assurer que Uy a reellement mal interprete le sens de certains de ses types (il peut en effet s'agir d'un simple probleme de nommage de type ; dans ce cas, Ux peut mettre des alias sur des types de Uy de maniere a` les visualiser sous des noms qu'il juge plus adequats).
Idem.
Lorsqu'un utilisateur Ux detruit un lien qu'il a cree entre deux types X et Y et que ce lien a des co-createurs, ce lien continue a` exister mais ne soit plus visible par Ux.
Si par contre, ce lien n'a pas de co-createur, il est detruit ; dans ce cas, si ce lien etait un lien de specialisation et que Y n'avait pas d'autre supertype, Y est detruit ainsi que ses eventuels sous-types (ceux-ci ont forcement ete crees pas Ux et n'ont pas de co-createur). Toutefois, si Y a des sous-types, le systeme doit demander a` Ux une confirmation de la destruction de Y et de ses sous-types.
P. Martin.
Exploitation de graphes conceptuels et de documents structures et hypertextes
pour l'acquisition de connaissances et la recherche d'informations.
Ph.D thesis, University of Nice - Sophia Antipolis, France, October 14, 1996.
URL: http://www.webkb.org/doc/PhD.html