Konceptuální graf

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Konceptuální grafy (angl. Conceptual graphs (CGs), pův. z lat. conceptio – „početí, pojetí, shrnutí“ či conceptus - „sebrání, početí“, významově „prvotní náhled, abstrakt“ a z řeč.γράφω - „psát, popsat“, termín „graf“ je v matematice používán jako orientovaný popisný objekt, jímž se vyjadřuje vztah, propojení mezi objekty). Jedná se o informatický model sloužící k formální reprezentaci znalostí. V prvním publikovaném článku věnovanému konceptuálním grafům, je John F. Sowa použil k reprezentaci konceptuálních schémat používaných v databázových systémech. Jde jde o druh formálního jazyka, který mapuje přirozenou řeč do schématu relační databáze, je již strojově zpracovatelný, ale přitom stále ještě relativně dobře čitelný. V první publikované práci Sowa tyto grafy aplikuje na širokou škálu témat z oborů umělé inteligence, počítačových věd a kognitivních věd.

Popis modelu[editovat | editovat zdroj]

Konceptuální graf je orientovaným grafem a má uzly dvou typů označované jako koncept a relace. Jde o bipartitní graf, tj. jeho vrcholy lze rozdělit na dvě skupiny tak, že tak, že hrany vedou pouze z jedné skupiny do druhé, přičemž jedna tato skupina přesně odpovídá konceptům a druhá relacím. Graficky jsou uzly typu koncept znázorněny jako obdélníky, uzly typu relace jako kruhy či elipsy.

Obecný tvar zápisu uzlu typu koncept je typ-konceptu : referent. Typem konceptu může být například „Člověk“ (odpovídá tedy informatickému pojetí pojmu „entita“).

Relace představuje uspořádaný vztah mezi 1 až n koncepty. Příkladem může být například ternární relace „rodiče“ mezi koncepty „Člověk : Adam“, „Člověk : Eva“ a „Člověk : Kain“.

Příklad: Konceptuální graf

Referent v uzlu typu koncept může být (v rozšířeném pojetí konceptuálních grafů) tvořen kvantifikátorem, designátorem a deskriptorem. Pokud není uveden žádný referent („Člověk“), poté je slovní interpretací takového uzlu „nějaký člověk“ (odpovídá existenciálnímu [[Kvantifikátor|kvantifikátoru)) ∃). Použitím univerzálního kvantifikátoru („Člověk : ∀“) se odkazují všechny výskyty daného konceptu. Designátorem se rozumí odkaz konkrétní instance konceptu („Člověk : Adam“) nebo množiny konceptů („Člověk : {Adam, Eva}”). Konkrétní hodnotu designátoru lze parametrizovat využitím tzv. „lambda výrazů“ a dosáhnout tak zobecnění.

Příklad: Konceptuální graf - lambda výrazy

Deskriptorem je jiný konceptuální graf, který popisuje příslušný koncept. Je-li deskriptor součástí konceptu, pak o tomto uzlu hovoříme jako o kontextu.

Příklad: Konceptuální graf - kontext

Simple graphs[editovat | editovat zdroj]

Výše popsaný rozšířený model konceptuálních grafů umožňuje na rozdíl od predikátové logiky prvního řádu vytvářet nerozhodnutelná schémata. Problém je v příliš expresivním množinovém designátoru a v deskriptorech. John Sowa tento problém řešil pomocí tzv. simple conceptual graphs, které použití těchto dvou prvků zapovídají (Sowa 1984). Myšlenku simple graphs dále rozpracovali Michel Chein a Marie-Laure Mugnier v roce 1992[1].

Rozšíření Konceptuálních grafů[editovat | editovat zdroj]

Za účelem lepší reprezentace libovolného jazyka či logiky se postupně vyvíjely rozšiřující modely. Tato rozšíření lze klasifikovat do několika stupňů[2]:

  • Core CGs: Beztypová logika pokrývající "Comon Logic" standardizovanou prostřednictvím ISO/IEC 24707
  • Extended CGs: Některé prvky navíc (univerzální kvantifikátor, typová návěstí a boolean kontexty), nicméně existuje formální překlad mezi "Extended" a "Core", takže vyjadřovací síla obou je stejná
  • CGs with contexts: Umožňuje podporu meta-jazyků (jazyků popisujících jiné jazyky). Kontexty realizují chybějicí potřebu odvozovat tvrzení o objektech z tvrzení o meta-objektech.
  • Research CGs: Různé variace, které slouží k testování různých nových možností. Úspěšná rozšíření tohoto typu mohou být později začleněna do standardu.

Inference[editovat | editovat zdroj]

Inference je proces odvozování logických závěrů ze známých předpokladů. Příkladem inferenční metody pro konceptuální grafy může být například vyhledávání pomocí tzv. projekce, kdy se vzor konceptuálního grafu promítá do konkrétní znalostní báze s využitím hierarchie konceptů a relací.

Pravidla tvorby a odvozování konceptuálních grafů[editovat | editovat zdroj]

Ne všechny možné kombinace kontextů a relací mají význam v přirozeném jazyce, který mají reprezentovat. Základní pravidla tvorby pomáhají udržet přehled o tom, které konceptuální grafy jsou v pořádku[3]:

  • Kopie - přesná kopie správně zformátovaného konceptuálního grafu je správně zformátovaná
  • Odpojení - souvislý graf odpojený od správně zformátovaného konceptuálního grafu je správně zformátovaný
  • Restrikce - ve správně zformátovaném konceptuálním grafu lze koncept nahradit obecnějším typem a graf zůstane správně zformátovaný
  • Spojení - pokud jsou dva koncepty ve dvou správně zformátovaných grafech stejného typu, lze oba grafy přes tyto koncepty spojit a výsledný graf je správně zformátovaný

Lze odvodit i další, složitější pravidla, která mají více složitějších kroků (například projekce - výběr podgrafu a poté 0-n restrikcí)

Historie[editovat | editovat zdroj]

Myšlenka konceptuálních grafů se poprvé objevuje v Sowově článku "Conceptual Graphs for a Data Base Interface" z července 1976. Od roku 1984 byl koncept modelu rozvíjen do třech hlavních směrů.

Grafické rozhraní pro predikátovou logiku prvního řádu[editovat | editovat zdroj]

V takovém přístupu, je vzorec v predikátové logice (prvního řádu) vyjádřen pojmenovaným grafem.

Lineární notace, formát pro výměnu konceptuálních grafů (Conceptual Graph Interchange Format (CGIF), byl standardizován normou ISO/IEC 24707:2007 pod ISO jako jeden ze tří dialektů „Obecné logiky“ Common Logic, která tvoří rámec skupiny jazyků založených na logice.

Kočka Elsie sedí na rohožce

Uvedený diagram je příkladem způsobu zobrazení konceptuálního grafu. Obdélníky tvoří pojmové (konceptuální) uzly a ovály zobrazují „vztahové“ uzly. Ve výše zmíněném zápisu (CGIG) by byl tento konceptuální graf zapsán následovně:

   [Cat Elsie] [Sitting *x] [Mat *y] (agent ?x Elsie) (location ?x ?y)

V hranatých závorkách jsou uzavřeny informace z pojmových uzlů a do kulatých závorek se zapisují vztahové uzly. Písmena x a y se nazývají „koreferenční štítky,“ které značí, jakým způsobem jsou konceptuální a vztahový uzel vzájemně propojeny.

Ve formátu Common Logic Interchange Format (CLIF), jsou tato písmena namapována na proměnné, viz následující příklad:

   (exists ((x Sitting) (y Mat)) (and (Cat Elsie) (agent x Elsie) (location x y)))

Srovnáme-li oba zápisy, tak jak ukazuje první příklad (ve zápis ve formátu CGIF), hvězdičky u koreferenčních štítků *x a *y odpovídají (v zápise formátu CLIF) existenčním kvantifikátorům proměnných. A dále otazníkům z prvního zápisu odpovídají vázaným proměnným druhého zápisu. Univerzální kvantifikátor by se v CGIF zapsal @every*z a v CLIF forall (z).

Prověření syntaxe může být provedeno tak, že přepíšeme graf do logického zápisu a takový zápis necháme přeložit robotem.

Diagramické zobrazení početní logiky[editovat | editovat zdroj]

Druhá vývojová větev je vystavěna na základech existenčních grafů navržených Charlesem Sandersem Peircem, které spadají do původních grafů navržených Johnem Florianem Sowou. V tomto přístupu, který vyvíjel převážně Frithjof Dau, jsou konceptuální grafy spíše (podle definice teorie grafů) konceptuálními diagramy, než grafy. Prověřovací operace jsou prováděné v těchto diagramech.

Reprezentace znalostí grafově a ověřovací modely[editovat | editovat zdroj]

Třetí větví vývoje konceptuálních grafů tvoří reprezentace znalostí pomocí grafů a logický ověřovací aparát (GBKR). Tento přístup vyvinuli Michel Chein a Marie-Laure Mugnier. Hlavními znaky jsou:

  • všechny druhy znalostí (ontologie, pravidla, omezení a fakta) jsou označené grafy, které poskytují intuitivní a snadné pochopení významu reprezentovaných znalostí
  • ověřovací mechanismy jsou založené na zápisu grafu, především na klasickém zápisu grafového homomorfismu (mapování dvou grafů na sebe s respektováním jejich struktury), což umožní především napojit základní ověřované problémy na jiné fundamentální problémy v počítačové vědě
  • forma je vystavěná na logice, tzn. má sémantiku logiky prvního řádu a vyvozovací mechanismus je jednoznačný a úplný s ohledem na dedukci v logice prvního řádu
  • z hlediska výpočetního, byl homomorfismus grafů přijat v 90. letech jako hlavní používaný zápis a výpočet komplexity a algoritmická účinnost našly uplatnění v několika málo oblastech

Softwarové nástroje[editovat | editovat zdroj]

  • CharGer - grafický editor konceptuálních grafů
  • Prolog+CG - inferenční stroj v jazyce Prolog
  • Anime Platform - rozsáhlejší Java platforma pro vývoj inteligentních a multiagentních systémů, jejíž součástí je mimo jiné Prolog+CG
  • CoGui - Java grafický editor na tvorbu konceptuálních grafů
  • WebKB - nástroj na reprezentaci znalostí a získávání informací
  • Cogitant - C++ knihovny s podpůrnou funkcionalitou pro konceputální grafy

Odkazy[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Conceptual graph na anglické Wikipedii.

  1. https://www.jair.org/media/918/live-918-2019-jair.pdf
  2. http://www.jfsowa.com/cg/cgif.htm
  3. http://www2.fiit.stuba.sk/~kapustik/ZS/Clanky0607/komara/index.html

Literatura[editovat | editovat zdroj]

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]