Expertní systémy Znalosti Jan Górecki Název prezentace Název projektu Rozvoj vzdělávání na Slezské univerzitě v Opavě Registrační číslo projektu CZ.02.2.69/0.0./0.0/16_015/0002400 Logolink_OP_VVV_hor_barva_cz –. znalosti umožňují odvodit nové informace –. znalosti ukazují zákonitosti, vztahy, pravidla –. prakticky používané při řešení problémů –. zobecnění empirických zkušeností –. heuristická, intuitivní povaha (tacitní znalosti) –. neúplné, měnící se –. nepřesné, neurčité, nejisté, vágní –. spojené se způsobem usuzování –. úzce specializované • •Pojetí znalostí v rámci logiky usuzování a inferenčního •mechanismu, který ji prakticky realizuje: •Nová znalost je taková, která není daným inferenčním •mechanismem odvoditelná z již dostupných znalostí. Charakteristické rysy znalostí csvukrs •Rozhodovací proces – expert vybavený znalostmi zvažuje data relevantní pro daný problém a činí rozhodnutí •Znalosti expert získal vzděláním a zkušeností •Vybraná data představují informace •Zdroj znalostí (expert) a zdroj informací (sebraná data) se liší •Jestliže se můžeme spolehnout při sběru na automatický proces nebo úředníka, hovoříme o datech, resp. informacích. Správnost dat může být objektivně verifikována. •Jestliže hledáme experta, potom hovoříme o znalostech obsahujících abstrakce a generalizace. – Informace a znalosti csvukrs •. moudrost •. znalost •. informace •. data •. šum – Hierarchie znalostí csvukrs •. Predikátová logika, speciálně deskripční logika Formy reprezentace znalostí (1) csvukrs •. Rámce –-datové struktury reprezentující stereotypní situace –-postupné vyplňování stránek, předdefinované hodnoty –-dědičnost v hierarchii rámců (generalizace – specifikace) –-teorii vytvořil M. Minsky –-na jejím základě vzniklo objektově orientované programování – Formy reprezentace znalostí (2) csvukrs •. Sémantické sítě –– grafová reprezentace objektů a relací mezi nimi formou –orientovaných spojení – Formy reprezentace znalostí (3) csvukrs •. Konceptuální grafy -zobecnění rámců a sémantických sítí –-J.F.Sowa: Knowledge Representation: Logical, Philosophical, –and Computational Foundations. 2000, 594 str. •. Reprezentace znalostí pravidly – Formy reprezentace znalostí (4) csvukrs •Egypt: 17. století př.n.l. – tzv. Smythův papyrus (1882) se objevilo 48 pravidel ve stejném tvaru o poraněních hlavy • •KDYŽ má pacient tento symptom, •PAK se jedná o následující poranění • •60. a 70. léta – odklon od algoritmů k systémům využívajícím znalosti – DENDRAL – analýza molekul – první komerčně úspěšný ES Historie csvukrs •Pravidla (rules) mohou mít například takovéto tvary: •IF předpoklad THEN závěr •IF situace THEN akce •IF podmínka THEN závěr AND akce •IF podmínka THEN důsledek1 ELSE důsledek2 •V předpokladové části (antecedentu) se mohou vyskytnout spojky AND a OR, v důsledkové části (konsekventu) se může vyskytnout spojka AND. Součástí pravidla může být také tzv. kontext, ve kterém má být pravidlo uvažováno. Tvary pravidel (1) csvukrs •Jiný způsob zápisu pravidla if E then H: E ® H • (E – evidence, H – hypothesis). •Pravidlo E ® H neznamená totéž, co implikace E Þ H. Tvary pravidel (2) csvukrs •Většina znalostních systémů je založena na pravidlech, nebo kombinuje pravidla s jiným způsobem reprezentace. •Pravidlové systémy se od klasických logických systémů odlišují nemonotonním uvažováním a možností zpracování neurčitosti. •Neurčitost se může vyskytnout jednak v předpokladech pravidla, jednak se může týkat pravidla jako celku. • Pravidlové systémy csvukrs •Inference je založena na pravidle modus ponens: • • •To znamená, že jestliže platí předpoklad E a pravidlo E®H, pak platí závěr H. Modus ponens představuje přímé usuzování. Nepřímé usuzování je dáno pravidlem modus tollens: • • •Řešení problému spočívá v nalezení řady inferencí (inference chain), které tvoří cestu od definice problému k jeho řešení • Inference v pravidlových systémech csvukrs •Usuzování řízené daty (dopředné řetězení, forward chaining): • Začíná se všemi známými daty a postupuje k závěru. Je vhodné pro problémy zahrnující syntézu (navrhování, konfigurace, plánování, rozvrhování, … ). •Usuzování řízené cíli (zpětné řetězení, backward chaining): • Vybírá možný závěr a pokouší se dokázat jeho platnost hledáním dat, které jej podporují. Je vhodné pro diagnostické problémy, které mají malý počet cílových hypotéz. • Základní strategie procesu usuzování csvukrs •Inferenční síť (inference network): • Závěry pravidel jsou fakta, která korespondují s předpoklady jiných pravidel. Znalostní bázi můžeme vizualizovat jako síť propojených pravidel a faktů. •Systém porovnávání se vzorem (pattern-matching system): • Závěry pravidel jsou obecnější a můžeme je chápat jako kolekce faktů, které mohou nebo nemusí korespondovat se vzory popsanými v předpokladech jiných pravidel. • Základní struktury v pravidlových systémech csvukrs •Inferenční síť může být reprezentována jako graf, jehož uzly jsou fakta a orientované hrany odpovídají pravidlům. •Inferenční sítě jsou užitečné pro domény, kde počet možných řešení je limitován, jako jsou např. klasifikační nebo diagnostické problémy. Tyto systémy jsou však méně flexibilní. •Inferenční sítě se snadněji implementují a snadněji se v nich zajišťuje vysvětlování. Inferenční síť csvukrs Inferenční síť - příklad •A ∧ B → P B ∧ D → Q P → X Q ∧ R → Y •C → P C ∧ E → R Q → X csvukrs •Vztahy mezi fakty a pravidly se ustavují až při běhu na základě úspěšného porovnání faktů se vzory, které se nacházejí v levých částech pravidel. V případě shody všech vzorů v levé části pravidla s fakty v bázi faktů se mohou provést akce v pravé části pravidla (např. to může být zápis faktu do báze faktů nebo zrušení faktu v bázi faktů). •Systémy založené na porovnání se vzorem se vyznačují vysokou flexibilitou a schopností řešit problémy. Jsou spíše aplikovatelné v doménách, kde počet možných řešení je vysoký nebo neomezený, jako je navrhování, plánování a syntéza.V těchto doménách nejsou předdefinovány vztahy mezi fakty a pravidly. •V těchto systémech se hůře zajišťuje podpora rozhodování za neurčitosti. V rozsáhlých aplikacích hrozí snížení efektivnosti při vyhledávání aplikovatelných pravidel. Systém porovnávání se vzorem csvukrs •1. Porovnání (matching): • Pravidla ze znalostní báze jsou porovnávána se známými fakty, aby se zjistilo, u kterých pravidel jsou splněné předpoklady. •2. Řešení konfliktu (conflict resolution): • Z množiny pravidel se splněnými předpoklady se vybírá pravidlo podle priority a v případě více pravidel se stejnou prioritou podle nějaké strategie . •3. Provedení (execution): • Provede se pravidlo vybrané v předchozím kroku. Důsledkem provedení pravidla může být přidání nového faktu do báze faktů, odstranění faktu z báze faktů, přidání pravidla do báze znalostí apod. •Obvykle je přitom uplatňována podmínka, že pravidlo může být aktivováno pouze jednou se stejnou množinou faktů. Základní kroky dopředného řetězení csvukrs •Strategie hledání do hloubky (depth strategy): preferována jsou pravidla používající aktuálnější data (data, která se v bázi faktů vyskytují kratší dobu). •Strategie hledání do šířky (breath strategy): preferována jsou pravidla používající starší data. •Strategie složitosti resp. specifičnosti (complexity strategy): preferována jsou speciálnější pravidla (pravidla mající více podmínek). •Strategie jednoduchosti (simplicity strategy): preferována jsou jednodušší pravidla • Příklady strategií řešení konfliktu csvukrs •1. Monitorování a diagnostika řídicích systémů pro řízení procesů v reálném čase, kde data jsou kontinuálně získávána a měněna a kde existuje málo předem určených vztahů mezi vstupními daty a závěry. V těchto aplikacích se z důvodu potřeby rychlé odezvy používá inferenční síť. Vhodné aplikace pro dopředné řetězení (1) csvukrs •2. Problémy zahrnující syntézu (navrhování, konfigurace, plánování, rozvrhování, … ). V těchto aplikacích existuje mnoho potenciálních řešení a pravidla proto musejí vyjadřovat znalosti jako obecné vzory. Přesné vztahy (inferenční řetězce) tudíž nemohou být předem určeny a musejí být použity systémy porovnávání se vzorem. Vhodné aplikace pro dopředné řetězení (2) csvukrs •1. Utvoř zásobník a naplň jej všemi koncovými cíli. Algoritmus zpětného řetězení (1) csvukrs •2. Shromáždi všechna pravidla schopná splnit cíl na vrcholu zásobníku. Je-li zásobník prázdný, pak konec. Algoritmus zpětného řetězení (2) csvukrs •3. Zkoumej postupně všechna pravidla z předchozího kroku. –a) Jsou-li všechny předpoklady splněny, pak odvoď závěr (proveď pravidlo). Jestliže zkoumaný cíl byl koncový, pak jej odstraň ze zásobníku a vrať se na krok 2. Jestliže to byl podcíl (dílčí cíl), odstraň jej ze zásobníku a vrať se ke zpracování předchozího pravidla, které bylo dočasně odloženo. –b) Jestliže fakty nalezené v bázi faktů nesplňují předpoklady pravidla, je zkoumání pravidla ukončeno. Algoritmus zpětného řetězení (3) csvukrs –c) Jestliže pro některý parametr předpokladu chybí hodnota v bázi faktů, zjišťuje se, zda existuje pravidlo, z něhož by mohla být tato hodnota odvozena. Pokud ano, parametr se vloží do zásobníku jako podcíl, zkoumané pravidlo se dočasně odloží a přejde se na krok 2. V opačném případě se tato hodnota zjistí od uživatele a pokračuje se v kroku 3.a) zkoumáním dalšího předpokladu. Algoritmus zpětného řetězení (4) csvukrs •4. Jestliže pomocí žádného ze zkoumaných pravidel nebylo možné odvodit hodnotu důsledku, pak daný cíl zůstává neurčen. Odstraní se ze zásobníku a pokračuje se krokem 2. Algoritmus zpětného řetězení (5) csvukrs •Zpětné řetězení je vhodnější pro aplikace, mající mnohem více vstupů než možných závěrů. •Dobrou aplikací pro zpětné řetězení je diagnostika, kde člověk komunikuje se znalostním systémem a zadává data pomocí klávesnice. Většina diagnostických systémů byla implementována pomocí inferenční sítě, protože vztahy mezi fakty jsou obvykle dobře známy. •Ideální pro zpětné řetězení jsou rovněž klasifikační problémy. Tento typ aplikace může být implementován buď pomocí inferenční sítě nebo pomocí vzorů v závislosti na složitosti dat. Vhodné aplikace pro zpětné řetězení csvukrs Příklady pravidlových systémů ART CLIPS EXSYS M.4 ILOG-RULES OPS5 prázdný ES založený na Lispu, dopředné řetězení, algoritmus Rete programové prostředí, dopředné řetězení, algoritmus Rete prázdný expertní systém, dopředné a zpětné řetězení programové prostředí, dopředné a zpětné řetězení, porovnávání se vzorem programové prostředí, dopředné řetězení, algoritmus Xrete programové prostředí, dopředné řetězení, algoritmus Rete csvukrs •Výhody: –modularita, –uniformita, –přirozenost. Výhody a nevýhody pravidlových systémů csvukrs •Možné nevýhody a problémy: –nebezpečí nekonečného řetězení, –přidání nové rozporné znalosti, –modifikace existujících pravidel, –neefektivnost, –neprůhlednost, –pokrytí domény (existují domény vyžadující příliš mnoho pravidel). Výhody a nevýhody pravidlových systémů csvukrs Děkuji za pozornost Některé snímky převzaty od: RNDr. Jiří Dvořák, CSc. dvorak@fme.vutbr.cz