Logika a znalostné systémy: dopredné a spätné reťazenie, rezolúcia a expertné systémy

Znalostná báza, vyplývanie a kontrola modelov, Hornove klauzuly, dopredné a spätné reťazenie, rezolúcia, Prolog a expertné systémy od MYCINu po znalostné grafy — na malom systéme, ktorý spozná zviera.

15 minút Matěj Žalmánek 2026-10-15

Séria Základy AI Diel 24 z 52

1. Mapa umelej inteligencie: čo je čo a ako to do seba zapadá
2. Stručná história umelej inteligencie: od Turinga po jazykové modely
3. Dáta, model, tréning, inferencia: základné pojmy na jednom príklade
4. Ako čítať matematický zápis: symboly, indexy, sumy a kvantifikátory
5. Množiny a relácie: stavebnica, z ktorej sa skladajú definície v AI
6. Funkcie a zobrazenia: prečo je každý model v AI funkcia
7. Logika a dôkazy: pravidlá, podľa ktorých sa v AI uvažuje
8. Grafy a stromy: štruktúra, na ktorej stojí hľadanie aj neurónové siete
9. Lineárna algebra pre strojové učenie: vektory, matice a prečo AI hlavne násobí
10. Derivácie, gradient a reťazové pravidlo: ako model zistí, ktorým smerom sa učiť
11. Gradientný zostup: ako sa model učí
12. Čo je pravdepodobnosť: od hodu kockou ku Kolmogorovovým axiómam
13. Podmienená pravdepodobnosť a Bayesova veta: ako zmeniť odhad, keď sa dozviete niečo nové
14. Náhodná premenná a distribučná funkcia: jedna funkcia, ktorá o rozdelení povie všetko
15. Funkcia hustoty a pravdepodobnostná funkcia: prečo má spojitá premenná v bode pravdepodobnosť nula
16. Stredná hodnota, rozptyl a kovariancia: kde rozdelenie leží, aké je široké a čo s čím súvisí
17. Prehľad pravdepodobnostných rozdelení: Bernoulliho, binomické, Poissonovo, rovnomerné, normálne a exponenciálne
18. Zákon veľkých čísel a centrálna limitná veta: prečo sa priemery správajú tak predvídateľne
19. Štatistika a odhady parametrov: maximálna vierohodnosť, MAP a intervaly spoľahlivosti
20. Teória informácie: entropia, krížová entropia a KL divergencia — odkiaľ sa berú stratové funkcie
21. Prehľadávanie stavového priestoru: BFS, DFS, UCS a A* s animáciami
22. Hry a protivník: minimax, alfa-beta orezávanie a Monte Carlo tree search
23. Splňovanie obmedzujúcich podmienok: backtracking, propagácia obmedzení a AC-3 na sudoku a mape krajov
24. Logika a znalostné systémy: dopredné a spätné reťazenie, rezolúcia a expertné systémy
25. Plánovanie: STRIPS, svet kociek, heuristiky z relaxácie a plánovanie v AI agentoch
26. Lokálne hľadanie a simulované žíhanie: obchodný cestujúci cez krajské mestá
27. Genetické algoritmy: populácia, kríženie, mutácia a výber na batohu na výlet
28. Evolučné stratégie a genetické programovanie: od pravidla jednej pätiny po Keplerov zákon
29. Optimalizácia mravčou kolóniou: ako feromónová stopa nájde krátku cestu
30. Optimalizácia rojom častíc: zotrvačnosť, vlastná skúsenosť a skúsenosť roja
31. Neuroevolúcia: evolúcia váh aj tvaru neurónových sietí a algoritmus NEAT
32. Fuzzy množiny a funkcie príslušnosti: ako zapísať „trochu teplo“
33. Fuzzy logika a pravdepodobnosť: prečo „trochu teplo“ neznamená „pravdepodobne teplo“
34. Fuzzy logika: t-normy, implikácie a pravidlá AK–TAK
35. Fuzzy riadenie: Mamdani a Sugeno od ventilátora po kyvadlo na vozíku
36. Fuzzy zhlukovanie: algoritmus fuzzy c-means a body medzi zhlukmi
37. Neuro-fuzzy systémy (ANFIS): fuzzy pravidlá, ktoré sa učia z dát
38. Markovove reťazce: prechodová matica, stacionárne rozdelenie a PageRank
39. Skryté Markovove modely: Viterbiho algoritmus a nepoctivé kasíno
40. Bayesovské siete: prečo je tráva mokrá a čo z toho vyplýva pre postrekovač
41. Kalmanov filter: ako z nepresných meraní odhadnúť, kde auto je a ako rýchlo ide
42. Druhy strojového učenia: s učiteľom, bez učiteľa, s čiastočným učiteľom a ďalšie
43. Prompty, kontext a RAG: ako modelu dať správne informácie
44. Variačné autoenkodéry (VAE): nové obrázky zo spojitého latentného priestoru
45. Generatívne adversariálne siete (GAN): falšovateľ proti detektívovi
46. Difúzne modely: ako sa z čistého šumu stane obrázok
47. Markovove rozhodovacie procesy: stavy, akcie, odmeny a Bellmanove rovnice
48. Q-learning a DQN: učenie hodnoty akcií od tabuľky po neurónovú sieť
49. Policy gradient a PPO: učenie priamo stratégie
50. Ako funguje AI agent: jazykový model v slučke s nástrojmi
51. Programovanie s AI agentmi: zadanie, testy a kontrola
52. Vyhodnocovanie a bezpečnosť AI systémov: ako merať a ako strážiť

Celá osnova série Hotovo: 52 z 83 tém

Skôr než sa stroje začali učiť z dát, skúšali ľudia umelú inteligenciu naučiť ručne: spísať, čo vie odborník, ako pravidlá „keď–potom“, a nechať počítač, aby z nich vyvodzoval závery. Tak vznikli expertné systémy sedemdesiatych a osemdesiatych rokov, ktoré diagnostikovali infekcie alebo zostavovali počítače na zákazku. Potom narazili na svoje hranice a prišla zima umelej inteligencie. Myšlienky z nich však nezmizli — žijú v Prologu, v databázach znalostí za vyhľadávačmi aj v kontrole toho, čo tvrdia jazykové modely.

Nadväzuje na diel Logika a dôkazy, kde nájdete spojky, implikáciu a modus ponens.

1. Znalostná báza a odvodzovací stroj

Definícia — znalostná báza

Nech 𝒫 je konečná množina výrokových symbolov a 𝓛(𝒫) množina všetkých viet (formúl) výrokovej logiky nad 𝒫, t. j. výrazov zložených zo symbolov 𝒫 spojkami ¬, ∧, ∨, ⇒, ⇔ (pozri Logika a dôkazy). Znalostná báza je konečná množina viet

KB ⊆ 𝓛(𝒫),

ktoré systém považuje za pravdivé. Systém s ňou vie dve operácie:

1. oznámiť vetu β ∈ 𝓛(𝒫): KB ← KB ∪ {β};
2. opýtať sa na vetu α ∈ 𝓛(𝒫): odpoveď je „áno“ práve vtedy, keď z KB vyplýva α (KB ⊨ α, definícia v ďalšej kapitole), inak „nie“.

Odvodzovací stroj je algoritmus, ktorý na operáciu „opýtať sa“ odpovedá.

Tento prístup sa nazýva deklaratívny. Neprogramujete postup, ako sa k odpovedi dostať — zapíšete len, čo platí, a postup je stále ten istý odvodzovací stroj. Chcete systém naučiť niečo nové? Pripíšete vetu, nič neprepisujete.

Celým dielom nás bude sprevádzať malý expertný systém podľa vzoru učebnicového ZOOKEEPERa Patricka Winstona: dvanásť pravidiel, z ktorých sa podľa pozorovaných vlastností spozná zviera. Pozorovali sme zviera, ktoré má srsť, ostré zuby, pazúry, je žltohnedé a má čierne pruhy. Čo je to?

2. Vyplývanie a modely

Definícia — model a vyplývanie

Nech 𝒫 je konečná množina výrokových symbolov. Ohodnotenie je funkcia m : 𝒫 → {0, 1} (1 = pravda, 0 = nepravda); pravdivostnú hodnotu m(α) ∈ {0, 1} rozšírime na každú vetu α ∈ 𝓛(𝒫) obvyklými pravdivostnými tabuľkami spojok. Ohodnotenie m je model vety α práve vtedy, keď m(α) = 1. Množina modelov vety α a znalostnej bázy KB ⊆ 𝓛(𝒫) je

M(α) = {m : 𝒫 → {0, 1} : m(α) = 1},   M(KB) = ⋂_{β ∈ KB} M(β)

(pre KB = ∅ je M(KB) množina všetkých 2^|𝒫| ohodnotení). Z KB vyplýva α, píšeme KB ⊨ α, práve vtedy, keď

M(KB) ⊆ M(α).

Slovami: α platí v každom ohodnotení, v ktorom platia všetky vety bázy.

KB ⊨ α ⇔ M(KB) ⊆ M(α)

KB ⊨ α

to, na čo sa pýtame: vyplýva α z bázy? Symbol ⊨ hovorí o pravde vo svetoch, nie o tom, či vieme niečo odvodiť

M(KB)

svety, ktoré báza pripúšťa — ohodnotenia, v ktorých platia všetky jej vety naraz (báza je ich konjunkcia); iné svety nás nezaujímajú, o tých báza tvrdí, že nenastali

⊆

inklúzia: v žiadnom pripustenom svete nesmie α chýbať; jediný protipríklad by stačil, aby α nevyplývala

M(α)

svety, v ktorých platí α; môže ich byť oveľa viac — α smie platiť aj tam, kde báza neplatí

Najpriamočiarejší spôsob, ako vyplývanie overiť, je kontrola modelov: prejsť všetky ohodnotenia, vybrať tie, v ktorých platí celá báza, a pozrieť sa, či v nich platí aj otázka. Naša báza má 24 výrokových symbolov („má srsť“, „cicavec“, „tiger“…), takže ohodnotení je 2²⁴ = 16 777 216. Z nich je 13 440 modelov bázy — a vo všetkých platí „tiger“. Odpoveď znie áno, lenže za cenu šestnástich miliónov riadkov pravdivostnej tabuľky. S každým ďalším symbolom sa počet zdvojnásobí; pri báze so stovkami symbolov by to nedobehlo nikdy.

Príklad — kontrola modelov na troch symboloch

Báza KB = {prší ⇒ mokro, mokro ⇒ šmýka sa, prší}, otázka α = šmýka sa. Tri symboly dávajú 2³ = 8 ohodnotení (1 = pravda, 0 = nepravda); implikácia p ⇒ q je nepravdivá len pre p = 1, q = 0.

prší	mokro	šmýka sa	prší ⇒ mokro	mokro ⇒ šmýka sa	KB
0	0	0	1	1	0
0	0	1	1	1	0
0	1	0	1	0	0
0	1	1	1	1	0
1	0	0	0	1	0
1	0	1	0	1	0
1	1	0	1	0	0
1	1	1	1	1	1

Celá báza platí len v poslednom riadku, takže |M(KB)| = 1. V tom riadku platí aj „šmýka sa“ — M(KB) ⊆ M(šmýka sa), a preto KB ⊨ šmýka sa. Algoritmus prešiel 8 riadkov a v každom vyhodnotil 3 vety bázy; všeobecne stojí kontrola modelov O(2ⁿ · |KB|).

Príklad — odkiaľ sa vzalo 13 440 modelov

V každom modeli bázy platí päť pozorovaných faktov a pravidlá R1, R6 a R9 potom vynútia „cicavec“, „šelma“ a „tiger“. Týchto 8 symbolov je pevne pravdivých. Zvyšných 16 sa rozpadne na skupiny, ktoré spolu cez pravidlá nesúvisia, a počty ich ohodnotení sa násobia:

• „dáva mlieko“ (R2 je splnené, cicavec platí) a „žerie mäso“ (R5 je splnené, šelma platí): ľubovoľne, 2 · 2 = 4;
• „má tmavé škvrny“, „gepard“ s pravidlom R8: tri ohodnotenia — nesmú platiť škvrny bez geparda;
• „má kopytá“, „kopytník“, „má dlhý krk“, „žirafa“, „zebra“ s R7, R10, R11: ak je kopytník nepravda, musia byť nepravda aj kopytá a zvyšné tri symboly sú voľné (8 možností); ak je pravda, musí platiť zebra, kopytá sú voľné a krk so žirafou majú 3 možnosti (2 · 3 = 6); spolu 14;
• vtáčia skupina „má perie“, „lieta“, „znáša vajcia“, „vták“, „nelieta“, „pláva“, „tučniak“ s R3, R4, R12: bez vtáka nesmie platiť perie ani zároveň lieta a vajcia (3 možnosti) a posledné tri symboly sú voľné (8): 24; s vtákom je perie voľné (2), lieta a vajcia voľné (4) a z ôsmich ohodnotení „nelieta, pláva, tučniak“ je zakázané len 1, 1, 0 (7): 56; spolu 80.

Dohromady 4 · 3 · 14 · 80 = 13 440 — presne toľko, koľko ich kontrola modelov napočítala. A v každom z nich platí tiger, pretože patrí medzi pevne pravdivé symboly.

3. Odvodzovanie: korektné a úplné

Namiesto prechádzania svetov sa dá s vetami manipulovať: z viet, ktoré máme, vyrábať nové podľa odvodzovacích pravidiel, ako je modus ponens. Tak to robí aj človek.

Definícia — odvodzovanie, korektnosť, úplnosť

Nech 𝓛 = 𝓛(𝒫) je množina viet a 𝓡 množina odvodzovacích pravidiel; každé pravidlo určuje, ktorú vetu smieme odvodiť z ktorých už odvodených viet (napríklad modus ponens: z β a β ⇒ γ odvoď γ). Nech KB ⊆ 𝓛 a α ∈ 𝓛. Odvodenie vety α z KB je konečná postupnosť viet β₁, …, β_k taká, že β_k = α a pre každé i = 1, …, k je β_i ∈ KB, alebo β_i vznikne niektorým pravidlom z 𝓡 z viet β₁, …, β_i−1. Píšeme

KB ⊢ α ⇔ existuje odvodenie α z KB.

Odvodzovací postup (množina pravidiel 𝓡, prípadne algoritmus, ktorý ich používa) je

1. korektný práve vtedy, keď pre všetky KB ⊆ 𝓛 a α ∈ 𝓛 platí KB ⊢ α ⇒ KB ⊨ α — odvodí len to, čo naozaj vyplýva;
2. úplný práve vtedy, keď pre všetky KB ⊆ 𝓛 a α ∈ 𝓛 platí KB ⊨ α ⇒ KB ⊢ α — odvodí všetko, čo vyplýva.

Korektnosť a úplnosť sa často tvrdí len pre užšiu triedu báz a otázok (napríklad bázy z Hornových klauzúl a otázky v tvare jediného symbolu); potom sa kvantifikátory „pre všetky“ berú len cez túto triedu.

Definícia — Hornova klauzula

Nech 𝒫 je množina výrokových symbolov. Literál je symbol p ∈ 𝒫 (kladný literál) alebo jeho negácia ¬p (záporný literál). Klauzula je disjunkcia konečne mnohých literálov ℓ₁ ∨ … ∨ ℓ_m, m ≥ 0 (pre m = 0 prázdna klauzula □, ktorá je vždy nepravdivá). Klauzula je

1. Hornova práve vtedy, keď z jej literálov je najviac jeden kladný;
2. určitá práve vtedy, keď z jej literálov je práve jeden kladný.

Určitú klauzulu ¬p₁ ∨ … ∨ ¬p_k ∨ q (k ≥ 0, p₁, …, p_k, q ∈ 𝒫) zapisujeme ako pravidlo

p₁ ∧ p₂ ∧ … ∧ p_k ⇒ q,

kde p₁, …, p_k sú predpoklady a q záver. Pre k = 0 je to fakt q. (Že ide o tú istú vetu, ukazuje rozbor nižšie.)

Prečo je „disjunkcia s najviac jedným kladným literálom“ to isté čo pravidlo? Implikácia A ⇒ q je ekvivalentná ¬A ∨ q a podľa De Morganovho zákona je ¬(p₁ ∧ … ∧ p_k) to isté čo ¬p₁ ∨ … ∨ ¬p_k:

¬p₁ ∨ … ∨ ¬p_k ∨ q ≡ (p₁ ∧ … ∧ p_k) ⇒ q

¬p₁ ∨ … ∨ ¬p_k

záporné literály klauzuly; dohromady hovoria „niektorý predpoklad neplatí“ — a to je presne negácia konjunkcie predpokladov

(p₁ ∧ … ∧ p_k)

predpoklady pravidla — z disjunkcie záporných literálov sa stali podmienkou vďaka De Morganovi; žiadny z nich nesmie byť záporný, inak by v pravidle stálo „keď neplatí …“

q

jediný kladný literál, záver; keby boli kladné dva, dostali by sme „potom q alebo r“ a odvodzovací stroj by nevedel, ktorý z nich pridať

⇒

klauzula je pravdivá, keď neplatí niektorý predpoklad alebo platí záver — to je definícia implikácie; tvar pravidla len inak číta tú istú disjunkciu

4. Dopredné reťazenie

Algoritmus — dopredné reťazenie

Vstup: konečná množina KB určitých Hornových klauzúl nad 𝒫 — fakty F ⊆ 𝒫 a pravidlá r s množinou predpokladov P(r) ⊆ 𝒫, |P(r)| ≥ 1, a záverom z(r) ∈ 𝒫.
Výstup: množina Známe ⊆ 𝒫 všetkých odvodených symbolov.

1. Pre každé pravidlo r nastav počítadlo chýba(r) ← |P(r)| (koľko jeho predpokladov ešte nie je známych). Nastav Známe ← ∅ a do agendy (frontu) vlož všetky fakty z F.
2. Ak je agenda prázdna, skonči a vráť Známe.
3. Vyber z agendy symbol p. Ak je p ∈ Známe, pokračuj krokom 2; inak Známe ← Známe ∪ {p}.
4. Každému pravidlu r s p ∈ P(r) zníž chýba(r) o 1. Ak klesne na 0, pravidlo vystrelí: vlož z(r) do agendy. Pokračuj krokom 2.

Zastavenie: krok 4 prebehne pre každý symbol najviac raz a každé pravidlo vystrelí najviac raz, takže do agendy pribudne len konečne veľa symbolov.

Veta. Nech KB je konečná množina určitých Hornových klauzúl nad 𝒫 a q ∈ 𝒫. Potom dopredné reťazenie odvodí q (t. j. q ∈ Známe) práve vtedy, keď KB ⊨ q; je teda pre výrokové symboly korektné aj úplné. Počet jeho krokov je lineárny v súčte dĺžok klauzúl bázy.

Hneď prvé pozorovanie „má srsť“ odomkne pravidlo R1, ktoré pridá „cicavec“ na koniec agendy. Zvyšné štyri pozorovania zatiaľ nič nespustia, ale znižujú počítadlá. Keď na rad príde cicavec, odomkne R6 (ostré zuby a pazúry už poznáme) — vznikne „šelma“. Šelma odomkne R9 a máme tigra. Za osem krokov, žiadne milióny riadkov. Pravidlo R5 („cicavec, ktorý žerie mäso, je šelma“) nevystrelilo nikdy: že zviera žerie mäso, nevieme — a nepotrebujeme to vedieť.

def dopredne(fakta, pravidla):
    chybi = {r.id: len(r.kdyz) for r in pravidla}
    zname, agenda = set(), list(fakta)
    while agenda:
        p = agenda.pop(0)
        if p in zname:
            continue
        zname.add(p)
        for r in pravidla:
            if p in r.kdyz:
                chybi[r.id] -= 1
                if chybi[r.id] == 0:          # všetky predpoklady poznáme
                    agenda.append(r.pak)
    return zname

Srdcom algoritmu je počítadlo pri každom pravidle r s predpokladmi P(r):

chýba(r) = |P(r)| − |P(r) ∩ Známe|

chýba(r)

koľko predpokladov ešte nevieme; pri chýba(r) = 0 pravidlo vystrelí — vďaka číslu to stroj spozná bez prechádzania zoznamu predpokladov

|P(r)|

počiatočná hodnota: na začiatku nevieme nič, chýbajú všetky predpoklady

|P(r) ∩ Známe|

predpoklady, ktoré už sú spracované; každý spracovaný symbol zníži počítadlo o 1 pri každom pravidle, kde sa vyskytuje — a spracuje sa len raz, preto sa nič nezapočíta dvakrát

Ako počítadlá chýba(r) počas nášho behu klesajú (po spracovaní symbolu v danom riadku; tučne nula, teda výstrel). V riadku 0 je ešte chýba(r) = |P(r)| (farby podľa vzorca vyššie):

R5 sa zastaví na jednotke (chýba „žerie mäso“) a R8 pre geparda tiež (chýba „má tmavé škvrny“). Ostatné pravidlá v tabuľke nie sú; ich predpoklady sa v behu buď vôbec neobjavili, alebo len sčasti.

Veta — dopredné reťazenie je korektné a úplné (dôkaz)

Nech KB je konečná množina určitých Hornových klauzúl nad 𝒫 a Známe výstup dopredného reťazenia. Potom pre každé q ∈ 𝒫 platí q ∈ Známe ⇔ KB ⊨ q.

Korektnosť (⇒). Každý odvodený symbol vznikol výstrelom pravidla, ktorého všetky predpoklady už boli známe. V každom modeli bázy platia fakty a (indukciou podľa poradia odvodenia) aj skôr odvodené symboly, takže podľa pravidla platí aj nový záver — je to modus ponens.

Úplnosť (⇐). Po skončení vezmime ohodnotenie m: pravda pre odvodené symboly (a fakty), nepravda pre všetky ostatné. To je model bázy: keby nejaké pravidlo p₁ ∧ … ∧ p_k ⇒ q v m neplatilo, boli by všetky p_i odvodené a q nie — lenže potom by počítadlo pravidla kleslo na nulu a q by sa odvodilo. Ak teda q z bázy vyplýva, platí v modeli m, a teda bolo odvodené. ∎

Model m je ten „najskromnejší“: verí len tomu, čomu musí. Na našej báze je to ohodnotenie, kde platí práve 5 pozorovaní, cicavec, šelma a tiger.

5. Spätné reťazenie

Algoritmus — spätné reťazenie

Vstup: konečná množina KB určitých Hornových klauzúl nad 𝒫 (fakty F ⊆ 𝒫 a pravidlá), cieľ q ∈ 𝒫 a množina C ⊆ 𝒫 cieľov, ktoré sa práve dokazujú vyššie v strome (na začiatku C = ∅).
Výstup: „dokázané“, alebo „nedokázané“.

Procedúra SPÄŤ(q, C):

1. Ak je q ∈ F, vráť „dokázané“.
2. Ak je q ∈ C, vráť „nedokázané“ (cieľ by dokazoval sám seba — cyklus).
3. Pre každé pravidlo p₁ ∧ … ∧ p_k ⇒ q z KB: zavolaj postupne SPÄŤ(p_i, C ∪ {q}) pre i = 1, …, k; ak všetky volania vrátia „dokázané“, vráť „dokázané“ (pri prvom neúspechu toto pravidlo opusti).
4. Ak neuspelo žiadne pravidlo, vráť „nedokázané“.

Zastavenie: každé vnorené volanie má C väčšiu o jeden symbol a 𝒫 je konečná, takže hĺbka rekurzie je najviac |𝒫|.

Veta. Nech KB je konečná množina určitých Hornových klauzúl nad 𝒫 a q ∈ 𝒫. Potom SPÄŤ(q, ∅) vráti „dokázané“ práve vtedy, keď KB ⊨ q. Spätné reťazenie je teda korektné a úplné a skúma len symboly, ktoré s cieľom súvisia cez pravidlá.

def zpetne(cil, fakta, pravidla, cesta=()):
    if cil in fakta:
        return True                           # vieme to priamo
    if cil in cesta:
        return False                          # cyklus: cieľ dokazuje sám seba
    for r in pravidla:
        if r.pak == cil:                      # ALEBO: stačí jedno pravidlo
            if all(zpetne(p, fakta, pravidla, cesta + (cil,))
                   for p in r.kdyz):          # A: musia vyjsť všetky predpoklady
                return True
    return False                              # nevieme, ako to dokázať

Funkcia all sa zastaví pri prvom predpoklade, ktorý nevyjde — preto sa pri R5 po neúspechu s „žerie mäso“ už nič ďalšie neskúma. Zoznam cesta stráži, aby sa pravidlá ako „a ⇒ b, b ⇒ a“ nezacyklili.

Algoritmus preskúmal 11 cieľov. Šelmu skúsil najprv dokázať pravidlom R5 — cicavca dokázal, ale na „žerie mäso“ narazil: to nevieme, a tak sa R5 vzdal a skúsil R6, ktoré vyšlo. Tu je spätné reťazenie silné: vie, čo mu chýba. Expertný systém sa v takej chvíli opýta používateľa: „Žerie to zviera mäso?“ Celý rozhovor s expertným systémom je tak vlastne spätné reťazenie nahlas.

Kedy čo použiť? Dopredné reťazenie sa hodí, keď prichádzajú dáta a chcete vedieť, čo z nich vyplýva — napríklad monitorovanie výroby. Spätné, keď máte konkrétnu otázku — diagnóza, dotaz do databázy. Keby sme sa opýtali „je to zebra?“, spätné reťazenie by to vyvrátilo po preskúmaní iba 5 cieľov: zebra je kopytník a kopytá naše zviera nemá.

6. Rezolúcia: odvodzovanie pre celú logiku

Hornove klauzuly nestačia na všetko. Veta „zviera je cicavec alebo vták“ má v závere „alebo“ a pravidlom ju nezapíšete. Pre ľubovoľné výroky existuje jediné pravidlo, ktoré stačí na všetko.

Definícia — rezolúcia

Nech 𝒫 je množina výrokových symbolov. Veta je v konjunktívnej normálnej forme (KNF) práve vtedy, keď je konjunkciou konečne mnohých klauzúl K₁ ∧ … ∧ K_s (klauzula pozri definíciu Hornovej klauzuly); klauzulu pritom chápeme ako množinu jej literálov, takže opakovaný literál sa počíta raz.

Rezolučné pravidlo. Nech p ∈ 𝒫, ℓ ∈ {p, ¬p} je literál, ¬ℓ literál k nemu opačný (¬¬p chápeme ako p) a A, B klauzuly (aj prázdne). Z klauzúl (A ∨ ℓ) a (B ∨ ¬ℓ) smieme odvodiť ich rezolventu

(A ∨ ℓ), (B ∨ ¬ℓ) ⊢ (A ∨ B).

Veta γ je nesplniteľná práve vtedy, keď nemá žiadny model (M(γ) = ∅); to isté pre množinu viet.

Veta (dôkaz sporom). Nech KB ⊆ 𝓛(𝒫) a α ∈ 𝓛(𝒫). Potom KB ⊨ α práve vtedy, keď je KB ∪ {¬α} nesplniteľná.

Veta (Robinson, 1965). Nech S je konečná množina klauzúl. Potom S je nesplniteľná práve vtedy, keď sa z S dá opakovaným použitím rezolučného pravidla odvodiť prázdna klauzula □.

Rezolučný dôkaz KB ⊨ α preto prevedie KB ∪ {¬α} do KNF a odvodzuje rezolventy, kým nevznikne □ (spor nájdený, α vyplýva), alebo kým nepribúdajú nové klauzuly (α nevyplýva; nad konečnou 𝒫 je klauzúl konečne veľa, takže to nastane). Postup je korektný a pre vyvracanie úplný.

( A ∨ ℓ ), ( B ∨ ¬ℓ ) ⊢ ( A ∨ B )

ℓ, ¬ℓ

doplnkové literály — v každom svete je pravdivý práve jeden z nich, takže jednu z klauzúl nesplní; tá musí byť splnená svojím zvyškom. Preto ℓ vo výsledku chýba

A

zvyšok prvej klauzuly: platí, kedykoľvek je ℓ nepravda (vtedy prvú klauzulu drží len A)

B

zvyšok druhej klauzuly: platí, kedykoľvek je ℓ pravda (vtedy ¬ℓ neplatí a druhú klauzulu drží B)

Algoritmus — prevod do konjunktívnej normálnej formy

Vstup: veta φ ∈ 𝓛(𝒫). Výstup: veta v KNF, ktorá má rovnaké modely ako φ. Každý krok sa opakuje, kým sa dá použiť; každý zachováva modely a skončí, pretože odstráni či posunie konečne veľa spojok.

1. Odstráň ekvivalencie: α ⇔ β nahraď (α ⇒ β) ∧ (β ⇒ α).
2. Odstráň implikácie: α ⇒ β nahraď ¬α ∨ β.
3. Posuň negácie až k symbolom: ¬¬α ≡ α, ¬(α ∧ β) ≡ ¬α ∨ ¬β, ¬(α ∨ β) ≡ ¬α ∧ ¬β (De Morgan).
4. Roznásob ∨ cez ∧: α ∨ (β ∧ γ) ≡ (α ∨ β) ∧ (α ∨ γ).

Príklad: (prší ∨ sneží) ⇒ mokro

krok 2: ¬(prší ∨ sneží) ∨ mokro

krok 3: (¬prší ∧ ¬sneží) ∨ mokro

krok 4: (¬prší ∨ mokro) ∧ (¬sneží ∨ mokro) — dve klauzuly, obe dokonca Hornove.

Roznásobovanie v 4. kroku môže formulu exponenciálne predĺžiť; riešiče preto v praxi používajú Tseitinovu transformáciu s pomocnými symbolmi, ktorá dáva len lineárne dlhší výsledok (splniteľný práve vtedy, keď pôvodná formula).

Rezolúcia je univerzálna, ale všeobecne drahá: pre výrokovú logiku je problém splniteľnosti (SAT) NP-úplný. Moderné SAT riešiče aj tak zvládajú milióny premenných — o nich bola reč v diele o obmedzujúcich podmienkach.

7. Pravidlá s premennými a Prolog

Výroková logika má chybu: „Rex je cicavec“ a „Micka je cicavec“ sú pre ňu dva nesúvisiace symboly. Pravidlo o všetkých cicavcoch by sa muselo odpísať pre každé zviera zvlášť. Predikátová logika z dielu o logike a dôkazoch to rieši premennými: ∀x : má_srsť(x) ⇒ cicavec(x).

Definícia — unifikácia

Nech sú dané množiny premenných (X, Y, …), konštánt (jan, petr, …) a funkčných a predikátových symbolov. Term je premenná, konštanta, alebo f(t₁, …, t_k) pre funkčný symbol f a termy t₁, …, t_k; atomická formula je P(t₁, …, t_k) pre predikátový symbol P. Oboje súhrnne nazývame výrazy.

Substitúcia (dosadenie) je konečná množina θ = {X₁ / t₁, …, X_n / t_n}, kde X₁, …, X_n sú navzájom rôzne premenné a t_i ≠ X_i termy; zápis X / t čítame „za X dosaď t“ (nie je to delenie). Pre výraz E je Eθ výraz, ktorý vznikne súčasným nahradením každého výskytu X_i termom t_i.

Nech E₁, E₂ sú výrazy. Substitúcia θ je ich unifikátor práve vtedy, keď

E₁θ = E₂θ.

Unifikátor θ je najvšeobecnejší práve vtedy, keď pre každý unifikátor σ výrazov E₁, E₂ existuje substitúcia λ taká, že Eσ = (Eθ)λ pre každý výraz E — každý iný unifikátor je len jeho ďalším spresnením. Napríklad rodič(jan, Y) a rodič(X, petr) unifikuje (a najvšeobecnejšie) substitúcia {X / jan, Y / petr}. Algoritmus unifikácie (nižšie) nájde najvšeobecnejší unifikátor, ak nejaký unifikátor existuje, a inak ohlási neúspech.

def unifikuj(a, b, s):                    # s: doteraz nájdené dosadenie (slovník)
    if s is None:
        return None                           # už skôr zlyhalo
    a, b = dosad(a, s), dosad(b, s)           # použi, čo už vieme
    if a == b:
        return s
    if je_promenna(a):
        return None if vyskytuje_se(a, b) else {**s, a: b}
    if je_promenna(b):
        return None if vyskytuje_se(b, a) else {**s, b: a}
    if slozeny(a) and slozeny(b) and a.jmeno == b.jmeno and len(a.args) == len(b.args):
        for x, y in zip(a.args, b.args):      # argumenty jeden po druhom
            s = unifikuj(x, y, s)
        return s
    return None                               # rôzne konštanty alebo predikáty

Na príklade rodič(jan, Y) a rodič(X, petr): predikáty sa zhodujú, takže sa porovnajú argumenty. jan a X dajú {X / jan}, Y a petr pridajú Y / petr. Naopak rodič(jan, Y) a rodič(petr, eva) neunifikujú — jan a petr sú rôzne konštanty. Kontrola vyskytuje_se bráni dosadeniu typu X / f(X), ktoré by viedlo k nekonečnému výrazu. (Prolog ju kvôli rýchlosti štandardne vynecháva.)

Na spätnom reťazení s unifikáciou stojí Prolog (Alain Colmerauer, Marseille, 1972) — jazyk, v ktorom program je znalostná báza a spustenie programu je dotaz:

rodic(jan, petr).
rodic(petr, eva).

prarodic(X, Z) :- rodic(X, Y), rodic(Y, Z).

?- prarodic(jan, Kdo).
Kdo = eva.

Prolog sa k cieľu prarodic(jan, Kdo) dopracuje presne ako náš strom pri tigrovi: nájde pravidlo, unifikuje X = jan, dokazuje rodic(jan, Y), nájde Y = petr a potom rodic(petr, Z) s výsledkom eva.

8. Expertné systémy

Expertný systém je znalostná báza spísaná s odborníkom a odvodzovací stroj, obvykle so spätným reťazením a s možnosťou vysvetliť, prečo k záveru dospel — stačí prečítať strom, ktorý sme nakreslili vyššie. Najznámejšie boli tri:

• DENDRAL (Stanford, od roku 1965) určoval štruktúru molekúl z údajov hmotnostného spektrometra — prvý systém, ktorý robil prácu vedcov podľa ich vlastných pravidiel.
• MYCIN (Stanford, 70. roky) diagnostikoval bakteriálne infekcie krvi a odporúčal antibiotiká. Mal okolo šiestich stoviek pravidiel a v hodnotení z roku 1979 obstáli jeho návrhy rovnako dobre ako návrhy stanfordských špecialistov alebo lepšie. V nemocnici sa napriek tomu nikdy nepoužíval.
• XCON (firma DEC, od roku 1980) zostavoval konfigurácie počítačov VAX podľa objednávky. Mal tisíce pravidiel a podľa firmy šetril desiatky miliónov dolárov ročne.

Medicína však málokedy pozná istotu. MYCIN preto ku každému pravidlu pripojil číslo, ako veľmi mu odborník verí:

Definícia — faktor istoty

Faktor istoty tvrdenia je číslo CF ∈ [−1, 1], ktoré vyjadruje mieru dôvery v tvrdenie: CF = 1 isto platí, CF = −1 isto neplatí, CF = 0 nevieme. Nie je to pravdepodobnosť — priraďuje ho odborník.

Nech dve rôzne pravidlá podporujú ten istý záver s faktormi CF₁, CF₂ ∈ (0, 1]. Výsledný faktor záveru je

CF = CF₁ + CF₂ · (1 − CF₁).

Pre záporné a zmiešané faktory má MYCIN iné kombinačné vzorce, ktoré v tomto diele nepotrebujeme.

CF = CF₁ + CF₂ · (1 − CF₁)

CF₁

dôvera z prvého pravidla; druhé pravidlo ju nemôže znížiť, len pridať

CF₂

akú časť zvyšnej neistoty druhé pravidlo odstráni; keby sa jednoducho sčítavalo, dve vodidlá po 0,6 by dali nezmyselných 1,2

1 − CF₁

neistota, ktorá po prvom pravidle zostala; len z nej sa ešte dá uberať, a preto výsledok nikdy neprekročí 1

Príklad — tri vodidlá a pravidlo s neistými predpokladmi

Tri vodidlá 0,6, 0,5 a 0,5: najprv 0,6 + 0,5 · (1 − 0,6) = 0,8, potom 0,8 + 0,5 · (1 − 0,8) = 0,9 (farby podľa vzorca vyššie). Kontrola cez neistoty: 1 − 0,4 · 0,5 · 0,5 = 0,9.

Neisté predpoklady. V MYCINe (Shortliffe a Buchanan, 1975) dostane konjunkcia predpokladov faktor svojho najslabšieho článku a záver pravidla faktor pravidla krát tento minimálny faktor (pravidlo sa pritom použije, len keď minimum prekročí 0,2): CF(záver) = CF(pravidlo) · min_i CF(p_i). Pravidlo s faktorom 0,7, ktorého predpoklady majú faktory 0,9 a 0,6, tak prispeje záveru 0,7 · min(0,9; 0,6) = 0,42.

Koncom osemdesiatych rokov sa ukázali hranice. Získavanie znalostí bolo úzke hrdlo: odborník svoje know-how často nevie vysloviť ako pravidlá a každé pravidlo stálo hodiny rozhovorov. Systémy boli krehké: o krok mimo svojej oblasti nevedeli nič a nevedeli ani, že nič nevedia. A tisíce pravidiel sa zle udržiavali — nové pravidlo mohlo potichu odporovať starému. Trh s expertnými systémami sa zrútil a prišla druhá zima umelej inteligencie. Odpoveď, ktorá prišla potom, je opačná: znalosti nespisovať, ale naučiť sa ich z dát.

9. Znalosti v dnešnej umelej inteligencii

• Znalostné grafy. Google od roku 2012 odpovedá na mnohé dotazy zo znalostného grafu — siete faktov typu (Praha, hlavné mesto, Česko). Voľne dostupné Wikidata majú cez sto miliónov položiek. Je to znalostná báza, len namiesto pravidiel prevažujú fakty.
• Pravidlá tam, kde sa musí dať skontrolovať. Daňové výpočty, poistné podmienky, schvaľovanie úverov alebo bezpečnostné politiky sa dodnes píšu ako pravidlá: každé rozhodnutie sa dá vysvetliť a obhájiť.
• Jazykové modely a znalosti. Jazykový model má obrovské množstvo znalostí, ale rozprestretých vo váhach siete — nedajú sa prečítať ani opraviť po jednej a model si občas sebaisto vymýšľa. Preto sa k nemu pripájajú vyhľadávanie v znalostnej báze (RAG) alebo nástroje a odvodzovacie stroje, ktoré výsledok overia.
• Neurosymbolická AI spája oboje: sieť rozpozná, čo vidí, a logika z toho odvodí, čo vyplýva. Príkladom sú systémy, ktoré hľadajú matematické dôkazy: model navrhne krok a formálny nástroj ho mechanicky skontroluje.

10. Zhrnutie

• Znalostná báza je množina viet; KB ⊨ α znamená, že α platí vo všetkých modeloch bázy. Kontrola modelov to overí, ale za cenu 2ⁿ ohodnotení.
• Odvodzovanie (⊢) pracuje s vetami namiesto svetov. Chceme, aby bolo korektné (nič nevymyslí) a úplné (nič neprehliadne).
• Pre Hornove klauzuly stačí dopredné reťazenie (od faktov, riadené dátami) alebo spätné (od cieľa, riadené otázkou); dopredné beží v lineárnom čase, spätné skúma len to, čo s cieľom súvisí.
• Pre celú výrokovú logiku je tu rezolúcia a dôkaz sporom; pre pravidlá s premennými unifikácia a Prolog.
• Expertné systémy ukázali silu aj hranice ručne písaných znalostí — a pripravili pôdu pre učenie z dát.

Chcete si to vyskúšať? Nechajte AI agenta napísať expertný systém so spätným reťazením, ktorý sa pýta na chýbajúce fakty — a vymyslite si vlastné pravidlá pre niečo, čomu rozumiete.

Máte na to iný názor? Napíšte na support@coden-app.com.