AeriesGuard Le Refuge des Créateurs Minecraftiens !

À la recherche de l'homomorphisme induit

Maintenant que je tiens une structure suffisamment expressive il me suffit de construire l' homomorphisme induit pour finaliser la construction de ma catégorie . 

C'est exactement la même démarche que pour ERic 0.2 où :

ma structure était le digraphe étiqueté

mon homomorphisme était l' homomorphisme de graphes

ma catégorie était la catégorie où les objets étaient des graphes et où les flèches étaient des homomorphismes de graphes

C'est encore tout pareil cette fois-ci. En plus compliqué.

Liens trans-hyper-nœuds

Cela fait 3 jours que, à part jouer à l'excellent Scrambled Nations je me pose la question suivante :

Dans mes 3 schémas d'exemple les liens qui traversent le cadre d'un hyper-nœud le font tous dans le sens du nœud courant vers le nœud parent.

Je me creuse la tête pour trouver un contre-exemple. Un graphe qui nécessiterait un lien qui traverse le cadre d'un hyper-nœud dans le sens du nœud courant vers un nœud fils.

Comme je ne trouve pas ce contre-exemple je ne sais pas si mon modèle est complet (tous les liens utiles qui traversent le font toujours dans le même sens) ou extensible (des liens qui traverseraient  dans le même sens contraire seraient également utiles).

D'où blocage. Un linguiste (avec une spécialisation en graphes conceptuels) pourrait me débloquer mais je n'en connais pas.

En l'absence de réponse définitive je vais devoir prendre un risque :

Parier que les liens sont uni-sens (quitte à me tromper).

Autoriser les liens dans les deux sens (quitte à compliquer encore plus la notion d'homomorphisme de structure).

Ne pas trancher prématurément (quitte à perdre du temps).

Résumons-nous

Lors de nos précédents arbitrages parmi la grande famille des graphes nous nous étions arrêtés au multi-digraphe-étiqueté-à-hyper-nœuds . C'est le point de départ de cet article où nous achevons notre spécification d'ERic 0.3.

Droit au but

Cette fois je fais fi de la démarche (trop tortueuse) pour vous présenter directement le résultat.

Les hyper-nœuds sont des conteneurs

C'était le credo de l'article précédent. Un hyper-nœud est une boîte fermée hermétiquement. Intérieur et extérieur sont isolés. Chaque boîte contient une donnée. Il suffit de désigner une boîte pour accéder à la donnée qu'elle contient. Éventuellement il y a encore une boîte dans la boîte. Comme des poupées russes. C'est du grand classique de l'algorithmique.

 

Les hyper-nœuds sont des membranes

Maintenant on change de point de vue. Les hyper-nœuds ne sont plus des boîtes hermétiques. Ce sont des membranes biologiques. Cela fait deux différences fondamentales :

Les hyper-nœuds sont des cadres-contextes. À l'extérieur de l'hyper-nœud on est dans le contexte de l'hyper-nœud parent. À l'intérieur de l'hyper-nœud on est dans un nouveau contexte plus spécifique qui enrichi le contexte parent (celui de l'hyper-nœud parent). C'est plus organique, il y a des systèmes et des sous-systèmes.

Il y a toujours un intérieur et un extérieur mais les échanges sont possibles entre les deux mondes. Le conteneur était un sarcophage. La membrane est une interface. C'est plus organique, il y a des flux qui traversent les parois.

Comme toujours des schémas valent mieux qu'un long discours.

Tom croit toujours qu'Éva veut épouser un marin.

Sauf que maintenant il y a 3 variantes possibles selon l'hyper-nœud dans lequel se trouve le marin.

C'est beaucoup plus précis, n'est-ce pas ?

Les graphes conceptuels

C'est encore un graphe (ou pas ) ? C'est encore une structure de données (ou pas ) ? On trouve ça dans les livres d'algorithmique (ou pas ) ? Et sinon c'est grave docteur ? Non, ça n'est pas grave. Tout ce dont on a besoin c'est d'une base de données et d'un mécanisme de requête. Et le mécanisme de requête c'est la recherche de tous les homomorphismes existant entre un motif et une collection de données. D'ailleurs c'était déjà le cas avec Eric 0.2. Wikipédia était bien capable de définir les homomorphismes de graphe tout en étant incapable de donner un algorithmique pour les trouver. Ça n'a pas empêché d'implanter ERic 0.2. Ce sera pareil avec ERic 0.3. Si on n'a plus le courage de faire de la recherche en algorithmique alors on changera de projet.

---

L'histoire continue

Ceux qui croient que la mise en parenthèse du projet ERic m'empêche d'alimenter ce blog se fourvoient. Un temps mort dans le développement c'est au contraire le moment idéal pour mieux fixer des idées parfois trop mouvantes. Et quoi de mieux pour fixer ses idées que de les mettre au propre pour les partager. De façon informelle, en français, bien avant de devoir rédiger la documentation officielle et définitive (qui serait cette fois en anglais).

---

Les pré-requis

Ce tutoriel n'est pas le plus facile de la série sur ERic.
Pour l'assimiler au mieux je ne peux que vous recommander :

la lecture de la documentation officielle d'ERic 0.2f (en français)

éventuellement, la lecture de l' introduction aux graphes-conceptuels par John F. Sowa (en anglais)

---

Les 4 visages d'ERic

Il y a 4 façons de comprendre et d'envisager ERic en tant qu'un système complet d'information :

comme une représentation graphique du langage naturel

comme une structure de données informatique

comme une modélisation des connaissances

comme une logique diagrammatique

Jusqu'ici on a surtout insisté sur les deux premiers aspects :

Quoique de manière incomplète ERic nous permet d'assez bien rendre compte de la sémantique du langage naturel.

La structure de données de prédilection est le multi-digraphe-étiqueté . On a justifié ce choix par le fait que cette structure de données est familière au lecteur et au programmeur.

On a également donné un méta-modèle d'ERic. C'est dire qu'au moins implicitement on assume une certaine capacité de modélisation.

On n'a pas donné de sémantique logique formellement dérivable d'un graphe entités/relations. Pour ne pas embarrasser le non-logicien mais surtout parce que le programmeur principal est plus à l'aise avec la vision "structure de données". Cependant aux détours de certaines explications on a laissé entrevoir qu'une telle logique était à l'œuvre. De plus on a identifié l' homomorphisme comme la méthode de requête et la subsomption comme la méthode de classification. Il n'y aucune raison de remettre en cause ces choix de mathématique/logique.

---

Comment améliorer ERic ? 

Quelque soit la modification opérée sur ERic elle impactera simultanément les 4 interprétations de façon cohérente.

Avoir 4 interprétations étroitement liées est-il un avantage ou bien une complexité supplémentaire ?

A-t-on l'obligation d'anticiper 4 fois plus et de tourner 4 fois sa langue dans sa bouche avant de changer une ligne de code ?

Heureusement non. Dans le cas contraire ERic serait de fait condamné à la stagnation.
En fait on peut carrément choisir une interprétation, améliorer ERic dans cette interprétation, et l'amélioration se répercutera sur les 3 autres interprétations sans même qu'on ait à y penser.

Mieux: on peut identifier une limitation dans une interprétation et la corriger à l'aide d'une extension dans une autre interprétation. Chaque amélioration se répercute sur les 4 interprétations.
C'est d'ailleurs exactement comme ça que l'on va procéder.
L'homme est supérieur en capacités linguistiques, c'est donc sur ce point qu'on va chercher des problèmes.
ERic est supérieur en capacités de modélisation, c'est dans ce domaine qu'on va chercher les solutions.

---

ERic 0.2f possède des limitations linguistiques 

Dans les deux premier cas on a un complément d'objet direct (un Dieu, une crème-glacée).
Le dernier cas est plus composite. Tom croit à une Proposition qui affirme ( Statement ) quelque chose. Éva veut une Situation qui décrit ( Description ) un certain état.

ERic 0.2 ne gère pas cette configuration de façon optimale :

Il n'est pas possible d'exprimer que le marin n'existe pas ailleurs que dans la tête de Tom.

Pire encore: si on demande "une personne veut-t-elle se marier" on aura pour réponse "oui, Éva veut se marier". Sans rien préciser des pensées de Tom. Le problème ici est que le graphe n'est pas assez structuré. Le fait que Tom croit quelque chose n'est qu'une extension du fait qu'Éva veut épouser un marin. Et vice-versa. Il y a des propositions mais il n'y a pas de propositions subordonnées . 

Évidemment on voudrait bien remédier à ces déficiences.

On a dit également qu'ERic ne supportait pas la négation. La version ERic 0.2d supporte la négation atomique qui n'a de négation à peu près que le nom. En fait il s'agit juste d'interdire un certain type de lien entre deux entités. On n'a pas de négation générale. Et pour des raisons de logique qui dépassent le cadre de ce tutoriel on n'ambitionne pas d'en avoir.

---

Modéliser ERic pour améliorer ERic 

Comme n'importe quel concepteur de logiciel on va utiliser un langage de conception pour faciliter la re-factorisation d'ERic.

Remarque cruciale n°1: dans ce méta-modèle tous les référents (Name, Integer, String, Reference, Float) sont des types atomiques, il n'y a aucun type structuré.

Remarque cruciale n°2: ce méta-modèle définit le type EntityRelationGraph qui lui est un type très structuré.

Idée: On va simplement ajouter le type EntityRelationGraph dans la liste des référents possibles. De cette façon on pourra avoir des nœuds dont le référent est un graphe entités/relations. Un graphe dont les nœuds peuvent contenir des graphes s'appelle un graphe à hyper-nœuds. 

---

Conséquences linguistiques 

Comme on va le voir cette modification résout le problème des propositions subordonnées .
Par contre cela ne résout pas le problème de l'existence (in)certaine du marin.

On voit que les arêtes Statement et Description ont disparu.
Chaque proposition subordonnée est désormais délimitée par un nœud-cadre.

Désormais le code contient une indentation pour marquer le niveau d'imbrication des nœuds :

join
   [Believe *b] Experiencer [Person:Tom] b Theme
   [Proposition
      [Want *w] Experiencer [Person:Eva] w Theme
      [Situation
         [Marry *m] Agent [Person:Eva]
         m Theme [Sailor]
      ]
  ].

---

Conséquences logiques 

Les notions d' homomorphisme et de subsomption deviennent récursives. En particulier les requêtes deviennent récursives. Elles se propagent à l'intérieur des hyper-nœuds tout en mémorisant le contexte externe.

Concrètement lorsque l'on demande "une personne veut-t-elle se marier" on aura pour réponse "oui, Tom croit qu'Éva veut se marier" au lieu de simplement "oui, Éva veut se marier".

---

Conséquences sur les structures de données 

Comme on l'a dit on passe du multi-digraphe-étiqueté au multi-digraphe-étiqueté-à-hyper-nœuds .

Le challenge n'est pas tant dans la représentation de ce type de graphe que dans la façon d'en stocker une très grande quantité tout en ralentissant le moins possible la recherche récursive d'homomorphismes.

---

Conclusion

On a présenté une solution au problème des propositions subordonnées et ce que cette solution implique sur les 4 interprétations d'un graphe entités/relations.

Le prochain article présentera une solution au problème de l'existence (in)certaine du marin ainsi que ses implications profondes sur la nature algorithmique des graphes-conceptuels.

(In)conscience artificielle

Quelque part sur un site d'informatique un membre enthousiaste d'AG a émis cette idée qu'une conscience artificielle pourrait se résumer dans la formule "je sais que je sais".

Je n'ai pas d'opinion philosophique sur la question. Par contre je pense être suffisamment avancé sur le plan technique pour exprimer artificiellement "je sais que je sais" beaucoup plus aisément que notre gentil membre ne pourra le faire malgré sa bonne volonté évidente.

D'ailleurs je vais le faire pas plus tard que tout de suite.

> ERic
Entity-Relationship interactive calculator.
version 0.2e by Damien Guichard.
# load "ECO.bdd".
# super-type [Think] Know.
# join
  [Know*k] Agent [Person:I]
  k Theme [Proposition*p]
  p Statement k.

Voilà c'est fait. On a créé une conscience artificielle (ou pas).

Quelles différences entre ERic et une base de données orientée graphes ? 

 

Les bases de données orientées graphes classiques s'appuient toutes sur un langage à objets. La conséquence c'est que les entités sont des objets et les relations sont des références. Du coup il y a une hiérarchie sur les types d'entités (la hiérarchie des classes) mais il n'y a pas de hiérarchie sur les types de relations. Au contraire, ERic 0.2 possède deux hiérarchies distinctes, une pour les entités, une autre pour les relations.

Deuxième conséquence, plus importante: ERic 0.2 possède la subsomption. Les données sont des graphes. Les requêtes sont des graphes. Les réponses sont des graphes. Avec les autres bases de données, les données sont des objets, les requêtes sont des chemins+filtres, les réponses sont des objets. Il n'y a pas de notion de subsomption. En fait les bases de données orientées graphes classiques ne sont guère plus qu'un moyen de (dé-)sérialisation pour des amas d'objets à charger/sauver sur disque.

La documentation des bases de données orientées graphes affirme que le graphe est la structure de données la plus générale . La documentation d'ERic n'affirme rien de tel. Au contraire. ERic 0.3+ a pour objectif d'offrir une structure de données plus générale que les graphes, les multi-graphes, les graphes bipartites, les hyper-graphes et autres variations ou extensions de la définition d'un graphe.

La plupart des bases de données orientées graphes offrent certains algorithmes classiques comme le plus court chemin d'un objet à un autre, les plus proches voisins vérifiant une certaine propriété... ERic n'offre rien de tel, il ne fonctionne que par subsomption.

Mise à jour mineure vers la version 0.2f

Suite à une visite de nlegriel la relation Attribut a été renommée  Attribut e et une relation Value a été ajoutée.

Le couple Property / Value constitue une alternative à Attribute :

• Si la modélisation est orientée Graphe Conceptuel on préfèrera →(Attribute)→[Age 17]
• Si la modélisation est orientée RDF / OWL on préfèrera →(Property)→[Age]→(Value)→[Integer 17]

Interface source avec OCaml.

Pour vous faire patienter avant de dévoiler les nouvelles caractéristiques d'ERic 0.3a, voici un petit tutoriel sur mon algo de reachability en version 0.2

ERic 0.2 possède une double hiérarchie: une pour les concepts et aune autre pour les relations.

Dynamiquement ERic compare les types de milliers de paires de concepts et de paires de relations. La vitesse de comparaison de deux types est donc vitale pour la performance.

L'ordre dans une hiérarchie est un ordre partiel .

Voici comment on compare deux types A et B :

• ou bien le type A est un ancêtre du type B (on note A ≥ B)
• ou bien le type B est un ancêtre du type A (on note B ≥ A)
• ou bien les deux types A et B ne sont pas comparables

Voici une représentation d'une hiérarchie, une liaison vers la droite est un lien vers un nœud frère, une liaison vers le bas est un lien vers une liste de nœuds fils.

  A
  |
  B-----------------C-----D
  |                 |     |      
  E------F------G   H     I------J

Le nœud A est le nœud sommet. Les nœuds B,C,D sont ses fils directs.

Dans ce cas comparer deux nœuds quelconques est une opération complexe.

Il faut partir d'un nœud et parcourir le chemin qui mène jusqu'au sommet en espérant rencontrer l'autre nœud au passage. Et si ça échoue alors il faut partir de l'autre nœud et parcourir le chemin qui mène jusqu'au sommet en espérant rencontrer le premier nœud au passage. Et si ça échoue encore alors les deux nœuds n'étaient pas comparables !

Bref il faut parcourir l'arbre.

TROP LENT.

Voici la solution de SpiceGuid.

Au départ l'arbre ci-dessus est étiqueté avec des intervalles d'entiers. Comme ceci.

[0,10]
  |
[1,5]-------------[5,7]-[7,10]
  |                 |     |      
[2,3]-[3,4]-[4,5] [6,7] [8,9]-[9,10]

Les nœuds proches du commet ont un intervalle plutôt large.

Alors que les nœuds feuilles ont un intervalle plutôt étroit.

À présent la comparaison entre deux nœuds se fait en temps constant : un nœud A est l'ancêtre d'un nœud B si et seulement si l'intervalle A contient l'intervalle B.

Évidemment l'objectif de la version 0.3a est d'offrir un niveau similaire de performance dans la comparaison de deux nœuds tout en offrant la possibilité de l'héritage multiple. La hiérarchie n'est alors plus un arbre mais un DAG (Directed-Acyclic-Graph).

La solution s'inspirera probablement de la technique générale dite de structural-boostrapping . Cette technique consiste (pour simplifier) à se baser sur un TAD incomplet (ici mon arbre étiqueté avec des intervalles) pour construire le TAD recherché (ici un DAG qui résout le problème de reachability ). Cette solution devrait donner de bons résultats pratiques puisque plusieurs études chiffrent le nombre moyen de types parents à environ presque 2 pour les ontologies les plus foisonnantes et à peine plus de 1 pour les ontologies les plus arborescentes.

Il va y avoir une  longue pose pause de brainstorming avant la spécification de la version 0.3a

Explications :

• Je suis tout nouveau dans le monde des bases de données. Je n'avais pas compris que les données stockées ont un cycle de vie. Il ne suffit pas d'un langage de déclaration et d'un langage de requête, il faut en plus un langage de mise à jour. Et mettre à jour des graphes ça n'est pas évident. En tout cas c'est plus difficile que mettre à jour des enregistrements ou des objets. C'est une faiblesse de l'approche que je n'avais pas vue initialement. Une recherche rapide dans le domaine me confirme que le problème est peu étudié / non-résolu.  
• J'aimerais étendre les capacités des requêtes. En particulier dans le quantitatif (minimum, maximum, intervalle) et dans le temporel (durée minimale, durée maximale, date butoir).
• J'aimerais pouvoir créer des cadre-contextes qui rendraient l'information contextuelle. C'est-à-dire liée à une situation, un état, un point de vue,... C'est une extension bien étudiée, dont on connaît les propriétés. Toutefois ça complique considérablement l'implantation et ça n'arrange rien quant à la résolution des deux problèmes précédents.
• J'aimerais autoriser le sous-typage multiple (héritage multiple) dans la hiérarchie des concepts et dans la hiérarchie des relations.
• J'aimerais faciliter l'embarquement dans les applications utilisateurs, en particulier dans les langages C et OCaml (tant pis pour les autres, ils n'auront qu'à s'interfacer avec le C). Comparativement aux points précédents celui-ci est le plus facile. Pour OCaml c'est trivial et pour le C c'est (assez bien) documenté et il est facile de contacter nombre de personnes expérimentées en la matière.

Je ne crois pas que j'arriverai à tout faire, mon objectif pour la version 0.3a c'est de résoudre au moins 3 parmi ces 5 points afin d'avancer un peu plus vite.

En attendant vos questions / commentaires / critiques sur la version 0.2d sont toujours les bienvenues

Mon but à moyen/long terme c'est d'avoir une Graph-based DB à visée commerciale.

Pour ça, une fois les 5 points précédents résolus il en restera encore 2 autres :

• une interface graphique GTK+
• un mécanisme de requêtes asynchrones distribuées

Et tout ça peut se faire 100% en OCaml

La poupée qui dit "non"

La prochaine version ERic v0.2 d implémentera la négation atomique (et non, TSG , ça n'est ni toxique ni radioactif ).

Alors me direz-vous, quelle différence entre la négation logique et la négation atomique

Hé bien la réponse est simple : je vais être obligé de m'atomiser le cerveau dans le seul but de réussir à l'implanter

Et si je survis je pourrai continuer avec des super-pouvoirs algorithmiques renforcés.