Reprezentace a vyvozování znalostí
Aleš Horák
E-mail: hales@fi.muni.cz
http://nlp.fi.muni.cz/uui/
Obsah:
▶ Statistické výsledky průběžné písemky
▶ Reprezentace a vyvozování znalostí
▶ Extralogické informace
▶ Pravidlové systémy
▶ Nejistota a pravděpodobnost
Úvod do umělé inteligence 9/12 1 / 32
Statistické výsledky průběžné písemky
Oznámení
23. listopadu přesun přednášky do D2
Úvod do umělé inteligence 9/12 2 / 32
Statistické výsledky průběžné písemky
Statistické výsledky průběžné písemky
průběžná písemka PB016
177 studentů
Body Počet studentů
20 56
18–17 22
16.5 46
14.5 3
14 6
13.5 8
13 10
11–10 14
9.5 3
7.5 2
7 3
6.5–4 4
Medián: 16.5 bodů
Úvod do umělé inteligence 9/12 3 / 32
Reprezentace a vyvozování znalostí
Reprezentace a vyvozování znalostí
otázka:
Jak zapíšeme znalosti o problému/doméně?
Když je zapíšeme, můžeme z nich mechanicky odvodit nová fakta?
▶ reprezentace znalostí (knowledge representation) – hledá způsob
vyjádření znalostí počítačově zpracovatelnou formou (za účelem
odvozování)
▶ vyvozování znalostí (reasoning) – zpracovává znalosti uložené v bázi
znalostí (knowledge base, KB) a provádí odvození (inference) nových
závěrů:
• odpovědi na dotazy
• zjištění faktů, které vyplývají z faktů a pravidel v KB
• odvodit akci, která vyplývá z dodaných znalostí, . . .
Úvod do umělé inteligence 9/12 4 / 32
Reprezentace a vyvozování znalostí Reprezentace znalostí
Reprezentace znalostí
proč je potřeba speciální reprezentace znalostí?
vnímání lidí × vnímání počítačů
▶ člověk
▶ když dostane novou věc (třeba pomeranč) – prozkoumá a
zapamatuje si ho (a třeba sní)
▶ během tohoto procesu člověk zjistí a uloží si všechny základní
vlastnosti předmětu
▶ později, když se zmíní daná věc, vyhledají se a připomenou uložené
informace
▶ počítač
▶ musí se spolehnout na informace od lidí
▶ jednodušší informace – přímé programování
▶ složité nebo rozsáhlé informace – zadané v symbolickém jazyce
Úvod do umělé inteligence 9/12 5 / 32
Reprezentace a vyvozování znalostí Reprezentace znalostí
Volba reprezentace znalostí
která reprezentace znalostí je nejlepší?
Pro řešení skutečně obtížných problémů musíme používat několik různých
reprezentací. Každý konkrétní typ datových struktur má totiž své
klady a zápory a žádný se sám o sobě nezdá adekvátní pro všechny
funkce zahrnuté v tom, čemu říkáme “selský rozum” (common sense).
– Marvin Minsky, spoluzakladatel MIT UI lab
Úvod do umělé inteligence 9/12 6 / 32
Reprezentace a vyvozování znalostí Reprezentace znalostí
Limity reprezentace znalostí
Všechny modely se mýlí, některé jsou ale užitečné.
(All models are wrong, but some are useful)
– George Box, významný britský statistik
Kompletní reprezentace
znalostí má řešit:
▶ kategorie
▶ míry a hodnoty
▶ složené objekty
▶ čas, prostor a změny
▶ události a procesy
▶ fyzické objekty
▶ látky/substance
▶ mentální objekty a postoje
▶ ...
Často je nutné se kvůli efektivitě modelu vzdát přesnosti nebo úplnosti.
Úvod do umělé inteligence 9/12 7 / 32
Reprezentace a vyvozování znalostí Reprezentace znalostí
Reifikace – abstrakce jako objekt
reifikace (zvěcnění ) – zjednodušení (logické) analýzy
abstrakci/objekt vyššího řádu modelujeme jako objekt
vlastnost objektu ≈ predikát pomeranč
“držím pomeranč” ≈ držet(Já, x) ∧ pomeranč(x)
“mám rád chuť pomeranče” ≈ mít_rád(Já, x) ∧ x = chuť(?pomeranč?)
... v PL1 nelze
s reifikací predikátu pomeranč (konstanta):
“mám rád chuť pomeranče” ≈ mít_rád(Já, x) ∧ x = chuť(pomeranč)
“držím pomeranč” ≈ držet(Já, x) ∧ is_instance(x, pomeranč)
Z čistě logického hlediska vznikají neexistující objekty (spory při tvrzení
o neexistenci)
ale při korektním zpracování – stačí jednodušší formalismus
Úvod do umělé inteligence 9/12 8 / 32
Extralogické informace
Extralogické informace – třídy, sémantické sítě, rámce
co jsme dosud ignorovali:
▶ objekty reálného světa mají mezi sebou vztahy
• třídy/kategorie, podtřídy × nadtřídy
• hierarchie vztahů části/celku
• dědění vlastností v hierarchiích
▶ stav světa se může měnit v čase
• explicitní reprezentace času
• nemonotónní uvažování (pravdivost se může měnit v čase)
▶ ne každá informace je “černobílá”
• nejistota
• statistika, fuzzy logika
Úvod do umělé inteligence 9/12 9 / 32
Extralogické informace Třídy objektů
Třídy objektů
▶ “Chci si koupit fotbalový míč.”
• Chci si koupit FM27341 – špatně
• Chci si koupit objekt, který je prvkem třídy fotbalových míčů – správně
▶ objekty jsou organizovány do hierarchie tříd
• FM27341 ∈ fotbalové_míče
• fotbalové_míče ⊂ míče
▶ fakta (objekty) × pravidla (třídy)
• Všechny míče jsou kulaté.
• Všechny fotbalové míče mají X cm v průměru.
• FM27341 je červenomodrobílý.
• FM27341 je fotbalový míč.
• (Proto: FM27341 je kulatý a má X cm v průměru.)
Úvod do umělé inteligence 9/12 10 / 32
Extralogické informace Ontologie
Ontologie
▶ ontologie ve filozofii – nauka o existenci a typech existencí
▶ ontologie v informatice – formální popis znalostí, pojmy a vztahy mezi
pojmy, hierarchie
▶ ontologie obecné (upper level) × doménové
▶ různé dostupné obecné, žádná standardem (zatím):
(Open)Cyc, SUMO/MILO, Dublin Core, DOLCE, ...
http://archivo.dbpedia.org, http://www.ontologyportal.org
(=>
(and
(instance ?KILL Killing)
(patient ?KILL ?OBJ))
(exists (?DEATH)
(and
(instance ?DEATH Death)
(experiencer ?DEATH ?OBJ)
(causes ?KILL ?DEATH))))
Pokud nějaký proces (?KILL) je instancí zabíjení
(Killing) a nějaký agent (?OBJ) je předmětem
toho procesu
=>
pak existuje jiný proces (?DEATH) takový, že
tento jiný proces je instancí smrti (Death) a
agent ?OBJ se účastní tohoto jiného procesu
?DEATH a původní proces ?KILL je příčinou
tohoto jiného procesu ?DEATH
Úvod do umělé inteligence 9/12 11 / 32
Extralogické informace Sémantické sítě
Sémantické sítě
sémantické sítě – reprezentace faktových znalostí (pojmy + vztahy)
▶ vznikly kolem roku 1960 pro reprezentaci významu anglických slov
▶ znalosti jsou uloženy ve formě grafu
pojmy (objekty, třídy)
vztahy
▶ nejdůležitější vztahy – taxonomie:
• podtřída (subclass) – vztah mezi třídami
• instance – vztah mezi konkrétním objektem a jeho rodičovskou třídou
jiné vztahy – část (has-part), barva, . . .
Úvod do umělé inteligence 9/12 12 / 32
Extralogické informace Sémantické sítě
Sémantické sítě – příklad
zvíře
plaz savec hlava
velký slon šedý
Clyde Nellie jablka
podtřída podtřída
část
podtřída
barvavelikost
instance instance
mít_rád
Úvod do umělé inteligence 9/12 13 / 32
Extralogické informace Sémantické sítě
Dědičnost v sémantických sítích
▶ pojem sémantické sítě předchází OOP
▶ dědičnost:
• jestliže určitá vlastnost platí pro třídu→ platí i pro všechny její podtřídy
• jestliže určitá vlastnost platí pro třídu→ platí i pro všechny prvky této třídy
▶ určení hodnoty vlastnosti – rekurzivní algoritmus
▶ potřeba specifikovat i výjimky – mechanizmus vzorů a výjimek (defaults
and exceptions)
• vzor – hodnota vlastnosti u třídy nebo podtřídy, platí ta, co je blíž objektu
• výjimka – u konkrétního objektu, odlišná od vzoru
Úvod do umělé inteligence 9/12 14 / 32
Extralogické informace Sémantické sítě
Dědičnost vztahů část/celek
▶ “Krávy mají 4 nohy.”
• každá noha je částí krávy
▶ “Na poli je (konkrétní) kráva.”
• všechny části krávy jsou taky na poli
▶ “Ta kráva (na poli) je hnědá (celá).”
• všechny části té krávy jsou hnědé
▶ “Ta kráva je šťastná.”
• všechny části té krávy jsou šťastné – neplatí
▶ lekce: některé vlastnosti jsou děděny částmi, některé nejsou
explicitně se to vyjadřuje pomocí pravidel jako
part-of(x, y) ∧ location(y, z) ⇒ location(x, z)
Úvod do umělé inteligence 9/12 15 / 32
Extralogické informace Sémantické sítě
Vzory a výjimky – příklad
pták umí létat
pták se
zlom.křídly
. . . tučňák neumí létat
kouzelný
tučňák
umí létat
▶ “Všichni ptáci mají křídla.”
▶ “Všichni ptáci umí létat.”
▶ “Ptáci se zlomenými křídly jsou ptáci, ale neumí létat.”
▶ “Tučňáci jsou ptáci, ale neumí létat.”
▶ “Kouzelní tučňáci jsou tučňáci, kteří umí létat.”
▶ kdo umí létat:
– “Penelope je pták.” ⇒ ”Penelope umí létat.”
– “Penelope je tučňák.” ⇒ ”Penelope neumí létat.”
– “Penelope je kouzelný tučňák.” ⇒ ”Penelope umí létat.”
▶ všimněte si, že znalost hodnoty vlastnosti objektu se může měnit
s příchodem nových informací o klasifikaci objektu
Úvod do umělé inteligence 9/12 16 / 32
Extralogické informace Sémantické sítě
Aplikace sémantických sítí
(Princeton) WordNet – http://wordnet.princeton.edu/
▶ sémantická síť 150.000 (anglických) pojmů, zachycuje:
• synonyma, antonyma (významově stejná/opačná)
• hyperonyma, hyponyma (podtřídy)
• odvozenost a další jazykové vztahy
▶ tvoří se národní wordnety (navázané na anglický WN)
český wordnet – cca 30.000 pojmů
▶ nástroj na tvorbu a editaci národních wordnetů – DEBVisDic/VisDic,
vyvinutý na FI MU – http://deb.fi.muni.cz/
▶ VisualBrowser –
http://nlp.fi.muni.cz/projekty/visualbrowser/
nástroj na vizualizaci (sémantických) sítí, vznikl jako DP na FI MU
Úvod do umělé inteligence 9/12 17 / 32
Extralogické informace Sémantické sítě
Úvod do umělé inteligence 9/12 18 / 32
Extralogické informace Sémantické sítě
Úvod do umělé inteligence 9/12 19 / 32
Extralogické informace Rámce
Rámce – příklad
Rámce (frames) – varianta sémantických sítí představená Marvinem Minskim
rámec obsahuje objekty, sloty a hodnoty slotů
příklady rámců:
savec:
podtřída: zvíře
část: hlava
*má_kožich: ano
slon:
podtřída: savec
*barva: šedá
*velikost: velký
Nellie:
instance: slon
mít_rád: jablka
’*’ označuje vzorové hodnoty, které mohou měnit hodnoty u podtříd a instancí
Úvod do umělé inteligence 9/12 20 / 32
Extralogické informace Rámce
Rámce
▶ rámec – univerzální struktura všech informací relevantních pro daný
pojem
▶ velice populární pro reprezentaci znalostí v expertních systémech
▶ stejně jako sémantické sítě, rámce podporují dědičnost
▶ OO programovací jazyky vycházejí z teorie rámců
Sémantické sítě × rámce:
sémantické sítě rámce
uzly objekty
spoje sloty
uzel na druhém konci spoje hodnota slotu
deskripční logika (description logic) – logický systém, který manipuluje
přímo s rámci
Úvod do umělé inteligence 9/12 21 / 32
Extralogické informace Rámce
Rámce – využití v praxi
příklad využití rámců – ontologie Friend of A Friend (FOAF)
▶ popisuje osoby, jejich činnosti a vztahy k jiným osobám a objektům
▶ decentralizovaný přístup, http://xmlns.com/foaf/spec/
▶ využívaný komunitami (blogovací platformy, MediaWiki, ...)
▶ základ standardu W3C WebID 1.0 (2014 draft)
Vincent van Gogh
Úvod do umělé inteligence 9/12 22 / 32
Pravidlové systémy Pravidlová báze znalostí
Pravidlová báze znalostí – příklad
pravidla pro oblékání:
pravidlo 1 IF X je seriózní
AND X bydlí ve městě
THEN X by měl nosit sako
pravidlo 2 IF X je akademik
AND X je společensky aktivní
AND X je seriózní
THEN X by měl nosit sako a
kravatu
pravidlo 3 IF X bydlí ve městě
AND X je akademik
THEN X by měl nosit kravatu
pravidlo 4 IF X je podnikatel
AND X je společensky aktivní
AND X je seriózní
THEN X by měl nosit sako, ale
ne kravatu
společenská pravidla:
pravidlo 5 IF X je podnikatel
AND X je ženatý
THEN X je společensky
aktivní
pravidlo 6 IF X je akademik
AND X je ženatý
THEN X je seriózní
profesní pravidla:
pravidlo 7 IF X učí na univerzitě
OR X učí na vysoké škole
THEN X je akademik
pravidlo 8 IF X vlastní firmu
OR X je OSVČ
THEN X je podnikatel
Úvod do umělé inteligence 9/12 23 / 32
Pravidlové systémy Pravidlová báze znalostí
Pravidlová báze znalostí
▶ snaha zachytit produkčními pravidly znalosti, které má expert
▶ obecná forma pravidel
IF podmínka
THEN akce
• podmínky – booleovské výrazy, dotazy na hodnoty proměnných
• akce – nastavení hodnot proměnných, příznaků, . . .
▶ důležitá vlastnost – strukturování znalostí do modulů
• systém může být snadno rozšířen přidáním nových pravidel beze změny
zbytku systému
Úvod do umělé inteligence 9/12 24 / 32
Pravidlové systémy Expertní systémy
Expertní systémy
Aplikace pravidlových systémů
▶ zaměřeny na specifické oblasti – medicínská diagnóza, návrh konfigurace
počítače, expertíza pro těžbu nafty, . . .
▶ snaha zachytit znalosti experta pomocí pravidel
ale znalosti experta zahrnují – postupy, strategie, odhady, . . .
▶ expertní systém musí pracovat s procedurami, nejistými znalostmi,
různými formami vstupu
▶ vhodné oblasti pro nasazení expertního systému:
• diagnóza – hledání řešení podle symptomů
• návrh konfigurace – složení prvků splňujících podmínky
• plánování – posloupnost akcí splňujících podmínky
• monitorování – porovnání chování s očekávaným chování, reakce na změny
• řízení – ovládání složitého komplexu
• předpovědi – projekce pravděpodobných závěrů z daných skutečností
• instruktáž – inteligentní vyučování a zkoušení studentů
Úvod do umělé inteligence 9/12 25 / 32
Pravidlové systémy Expertní systémy
Expertní systémy v praxi
CLIPS, pravidlový jazyk a prostředí pro expertní systémy
▶ původně NASA Johnson Space Center – řízení kontroly raket
(1985–1996)
▶ aktivně vyvíjený (v. 6.41 z 21.6.2023), tisíce projektů
▶ pracuje s objekty, fakty a IF-THEN pravidly
( deftemplate emergency ( s l o t type )) ; o b j e k t
( deftemplate response ( s l o t action )) ; o b j e k t
( d e f r u l e fire−emergency ( emergency ( type f i r e )) ; p r a v i d l o
=> ( a s s e r t ( response ( action a c t i v a t e − s p r i n k l e r ) ) ) )
( r e s e t )
( a s s e r t ( emergency ( type f i r e ) ) ) ; f a k t
( run )
( f a c t s )
f−0 ( i n i t i a l − f a c t )
f−1 ( emergency ( type f i r e ))
f−2 ( response ( action a c t i v a t e − s p r i n k l e r ))
For a t o t a l of 3 f a c t s .
Úvod do umělé inteligence 9/12 26 / 32
Nejistota a pravděpodobnost Nejistota
Nejistota
definujme akci At jako “Vyrazit na letiště t hodin před odletem letadla.”
jak najít odpověď na otázku “Dostanu se akcí At na letiště včas k odletu letadla?”
problémy:
1. částečná pozorovatelnost (stav vozovky, záměry ostatních řidičů, . . . )
2. nejistota výsledků akcí (píchnutí kola, . . . )
3. obrovská složitost modelování a předpovědi dopravní situace
čistě logický přístup tedy:
– riskuje chybu – “A5 mě na letiště dostane včas.”
– vede k závěrům, které jsou příliš slabé pro rozhodování: “A5 mě tam
dostane včas, pokud nebude na dálnici nehoda a pokud nebude pršet a
jestli nepíchnu kolo a jestli nebude fronta na odbavovacích přepážkách a
jestli nebudou problémy při kontrole zavazadel . . . ”
Úvod do umělé inteligence 9/12 27 / 32
Nejistota a pravděpodobnost Nejistota
Metody pro práci s nejistotou
▶ defaultní/nemonotónní logika
Předpokládejme, že nepíchnu cestou kolo.
Předpokládejme, že A5 bude OK, pokud se nenajde protipříklad.
▶ logická pravidla s faktory nejistoty (problém příčiny a následku)
A5 →0.3 dostat se na letiště včas.
zalévání →0.99 mokrý trávník
mokrý trávník →0.7 déšť
▶ pravděpodobnost (míra předpokladu, že hodnota bude true)
Vzhledem k dostupným informacím, A3 mě tam dostane včas
s pravděpodobností 0.05.
poznámka: fuzzy logika se zabývá mírou pravdivosti, NE pravděpodobností
Úvod do umělé inteligence 9/12 28 / 32
Nejistota a pravděpodobnost Pravděpodobnost
Pravděpodobnost
Pravděpodobnost sumarizuje nejistotu pocházející z
– lenosti – nepodařilo se vypočítat všechny výjimky, podmínky, . . .
– neznalosti – nedostatek relevantních údajů, počátečních podmínek, . . .
subjektivní × Bayesovská pravděpodobnost:
– pravděpodobnostní vztah mezi tvrzením a jeho pravdivosti vzhledem
k podmínkám:
P(A4|žádné hlášené nehody) = 0.5
nejedná se o vyjádření pravděpodobnostní tendence (ale může se získat ze
znalostí podobných případů v minulosti)
– pravděpodobnost tvrzení se může měnit s novými (vstupními) podmínkami:
P(A4|žádné hlášené nehody, je 4:00 ráno) = 0.63
pravidlo pro podmíněnou pravděpodobnost – P(a|b) = P(a∧b)
P(b) pokud P(b) ̸= 0
neboli pravidlo násobení (product rule) – P(a ∧ b) = P(a, b) = P(a|b)P(b)
P(a ∧ b ∧ c) = P(a, b, c) = P(a|b, c)P(b, c) = P(a|b, c)P(b|c)P(c)
Úvod do umělé inteligence 9/12 29 / 32
Nejistota a pravděpodobnost Vyvozování z nejistých znalostí
Vyvozování z nejistých znalostí
▶ náhodná proměnná (random variable) – funkce, která vzorkům
přirazuje hodnoty → vrací výsledky měření sledovaného jevu
distribuce pravděpodobností náhodné proměnné = (vektor)
pravděpodobností, že daná proměnná bude mít konkrétní hodnotu
např.:
náhodná proměnná Odd ≈ výsledek hodu kostkou bude lichý
náhodná proměnná Weather ≈ jaké bude počasí (slunce, déšť, mraky, sníh)
Odd(1) = true Weather(21.11.2005) = déšť
distribuce pravděpodobností proměnných Odd a Weather
P(Odd = true) = 1/6 + 1/6 + 1/6 = 1/2
P(Odd) = ⟨1/2, 1/2⟩
P(Weather) = ⟨0.72, 0.1, 0.08, 0.1⟩
▶ pravidla pro výpočet pravděpodobnosti logicky souvisejících událostí
P(a ∨ b) = P(a) + P(b) − P(a ∧ b)
Úvod do umělé inteligence 9/12 30 / 32
Nejistota a pravděpodobnost Vyvozování z nejistých znalostí
Bayesovské pravidlo pro vyvozování
z pravidla pro podmíněnou pravděpodobnost – P(a|b) = P(a∧b)/P(b)
lze odvodit Bayesovské pravidlo pro určení diagnostické
pravděpodobnosti ze znalosti příčinné pravděpodobnosti:
P(Příčina|Následek) =
P(Následek|Příčina)P(Příčina)
P(Následek)
např. ZMB zánět mozkových blan, ZK ztuhlý krk:
P(zmb|zk) =
P(zk|zmb)P(zmb)
P(zk)
=
0.8 × 0.0001
0.1
= 0.0008
vyvozování =1. rozdělení akce na atomické události
2. zjištění pravděpodobností atomických událostí
3. výpočet/odvození pravděpodobností pomocí složených distribucí
pravděpodobností (joint probability distribution)
P(Odd, Weather) =
0.36 0.05 0.04 0.05
0.36 0.05 0.04 0.05
Úvod do umělé inteligence 9/12 31 / 32
Nejistota a pravděpodobnost Vyvozování z nejistých znalostí
Bayesovské sítě
Bayesovská síť:
▶ acyklický orientovaný graf
▶ uzly obsahují tabulky podmíněných pravděpodobností rodičů
▶ síť reprezentuje složenou distribuci pravděpodobností všech proměnných
▶ umožňuje efektivní přesné nebo přibližné (Monte Carlo) vyvozování
▶ nejčastěji používaný aparát pro vyvozování z nejistých znalostí
Alarm
Vloupání Zemětřesení
Honza volá Marie volá
P(V )
0.001
P(Z)
0.002
V Z P(A)
t t 0.95
t f 0.94
f t 0.29
f f 0.001
A P(H)
t 0.90
f 0.05
A P(M)
t 0.70
f 0.1
P(v|h, m) = αP(v) z P(z) a P(a|v, z)P(h|a)P(m|a)
Úvod do umělé inteligence 9/12 32 / 32