Logika i systemy z bazą wiedzy: wnioskowanie w przód i wstecz, rezolucja i systemy ekspertowe

Baza wiedzy, wynikanie i sprawdzanie modeli, klauzule Horna, wnioskowanie w przód i wstecz, rezolucja, Prolog i systemy ekspertowe od MYCIN-a po grafy wiedzy — na małym systemie, który rozpoznaje zwierzę.

15 minut Matěj Žalmánek 2026-10-15

Seria Podstawy AI Część 24 z 52

1. Mapa sztucznej inteligencji: co jest czym i jak to do siebie pasuje
2. Krótka historia sztucznej inteligencji: od Turinga do modeli językowych
3. Dane, model, trening, inferencja: podstawowe pojęcia na jednym przykładzie
4. Jak czytać zapis matematyczny: symbole, indeksy, sumy i kwantyfikatory
5. Zbiory i relacje: klocki, z których składają się definicje w AI
6. Funkcje i odwzorowania: dlaczego każdy model AI jest funkcją
7. Logika i dowody: reguły, według których rozumuje AI
8. Grafy i drzewa: struktura, na której opierają się przeszukiwanie i sieci neuronowe
9. Algebra liniowa dla uczenia maszynowego: wektory, macierze i dlaczego AI głównie mnoży
10. Pochodne, gradient i reguła łańcuchowa: jak model ustala, w którą stronę się uczyć
11. Spadek gradientu: jak uczy się model
12. Czym jest prawdopodobieństwo: od rzutu kostką do aksjomatów Kołmogorowa
13. Prawdopodobieństwo warunkowe i twierdzenie Bayesa: jak zmienić ocenę, gdy dowiesz się czegoś nowego
14. Zmienna losowa i dystrybuanta: jedna funkcja, która mówi o rozkładzie wszystko
15. Funkcja gęstości i funkcja prawdopodobieństwa: dlaczego zmienna ciągła ma w punkcie prawdopodobieństwo zero
16. Wartość oczekiwana, wariancja i kowariancja: gdzie leży rozkład, jak jest szeroki i co z czym się wiąże
17. Przegląd rozkładów prawdopodobieństwa: Bernoulliego, dwumianowy, Poissona, jednostajny, normalny i wykładniczy
18. Prawo wielkich liczb i centralne twierdzenie graniczne: dlaczego średnie zachowują się tak przewidywalnie
19. Statystyka i estymacja parametrów: największa wiarygodność, MAP i przedziały ufności
20. Teoria informacji: entropia, entropia krzyżowa i dywergencja KL — skąd się biorą funkcje straty
21. Przeszukiwanie przestrzeni stanów: BFS, DFS, UCS i A* z animacjami
22. Gry i przeciwnik: minimax, przycinanie alfa-beta i Monte Carlo tree search
23. Spełnianie ograniczeń: backtracking, propagacja ograniczeń i AC-3 na sudoku i mapie czeskich krajów
24. Logika i systemy z bazą wiedzy: wnioskowanie w przód i wstecz, rezolucja i systemy ekspertowe
25. Planowanie: STRIPS, świat klocków, heurystyki z relaksacji i planowanie w agentach AI
26. Przeszukiwanie lokalne i symulowane wyżarzanie: komiwojażer przez czeskie miasta wojewódzkie
27. Algorytmy genetyczne: populacja, krzyżowanie, mutacja i selekcja na plecaku na wycieczkę
28. Strategie ewolucyjne i programowanie genetyczne: od reguły jednej piątej do prawa Keplera
29. Optymalizacja kolonią mrówek: jak ślad feromonowy znajduje krótką drogę
30. Optymalizacja rojem cząstek: bezwładność, własne doświadczenie i doświadczenie roju
31. Neuroewolucja: ewolucja wag i kształtu sieci neuronowych oraz algorytm NEAT
32. Zbiory rozmyte i funkcje przynależności: jak zapisać „trochę ciepło”
33. Logika rozmyta a prawdopodobieństwo: dlaczego „trochę ciepło” nie znaczy „prawdopodobnie ciepło”
34. Logika rozmyta: t-normy, implikacje i reguły JEŻELI–TO
35. Sterowanie rozmyte: Mamdani i Sugeno od wentylatora po wahadło na wózku
36. Klasteryzacja rozmyta: algorytm fuzzy c-means i punkty między skupieniami
37. Systemy neuro-rozmyte (ANFIS): reguły rozmyte, które uczą się z danych
38. Łańcuchy Markowa: macierz przejścia, rozkład stacjonarny i PageRank
39. Ukryte modele Markowa: algorytm Viterbiego i nieuczciwe kasyno
40. Sieci bayesowskie: dlaczego trawa jest mokra i co z tego wynika dla zraszacza
41. Filtr Kalmana: jak z niedokładnych pomiarów oszacować, gdzie jest samochód i jak szybko jedzie
42. Rodzaje uczenia maszynowego: nadzorowane, nienadzorowane, półnadzorowane i inne
43. Prompty, kontekst i RAG: jak dać modelowi właściwe informacje
44. Wariacyjne autoenkodery (VAE): nowe obrazki z ciągłej przestrzeni latentnej
45. Generatywne sieci przeciwstawne (GAN): fałszerz kontra detektyw
46. Modele dyfuzyjne: jak z czystego szumu powstaje obraz
47. Procesy decyzyjne Markowa: stany, akcje, nagrody i równania Bellmana
48. Q-learning i DQN: uczenie się wartości akcji od tabeli po sieć neuronową
49. Policy gradient i PPO: uczenie się bezpośrednio polityki
50. Jak działa agent AI: model językowy w pętli z narzędziami
51. Programowanie z agentami AI: zadanie, testy i kontrola
52. Ocena i bezpieczeństwo systemów AI: jak mierzyć i jak pilnować

Pełny program serii Gotowe: 52 z 83 tematów

Zanim maszyny zaczęły uczyć się z danych, ludzie próbowali sztuczną inteligencję nauczyć ręcznie: spisać, co wie ekspert, w postaci reguł „jeśli–to” i pozwolić komputerowi wyciągać z nich wnioski. Tak powstały systemy ekspertowe lat siedemdziesiątych i osiemdziesiątych, które diagnozowały infekcje albo konfigurowały komputery na zamówienie. Potem natrafiły na swoje granice i nadeszła zima sztucznej inteligencji. Ich idee jednak nie zniknęły — żyją w Prologu, w bazach wiedzy za wyszukiwarkami i w sprawdzaniu tego, co twierdzą modele językowe.

Ta część nawiązuje do części Logika i dowody, gdzie znajdziesz spójniki, implikację i modus ponens.

1. Baza wiedzy i maszyna wnioskująca

Definicja — baza wiedzy

Baza wiedzy KB to zbiór zdań języka formalnego (tutaj logiki zdań), które system uważa za prawdziwe. System potrafi wykonać na niej dwie operacje: powiedz — dodaj do KB nowe zdanie — i zapytaj — sprawdź, czy z KB wynika zdanie α.

Takie podejście nazywa się deklaratywnym. Nie programujesz sposobu dojścia do odpowiedzi — zapisujesz tylko, co jest prawdą, a sposób to zawsze ta sama maszyna wnioskująca. Chcesz nauczyć system czegoś nowego? Dopisujesz zdanie, niczego nie przepisujesz.

Przez całą część będzie nam towarzyszył mały system ekspertowy wzorowany na podręcznikowym ZOOKEEPERZE Patricka Winstona: dwanaście reguł, z których na podstawie zaobserwowanych cech rozpoznaje się zwierzę. Zaobserwowaliśmy zwierzę, które ma sierść, ostre zęby, pazury, jest płowe i ma czarne pasy. Co to jest?

2. Wynikanie i modele

Definicja — model i wynikanie

Model zdania to wartościowanie symboli zdaniowych, przy którym zdanie jest prawdziwe. Zbiór modeli zdania α oznaczamy M(α).

Z KB wynika α, piszemy KB ⊨ α, wtedy i tylko wtedy, gdy M(KB) ⊆ M(α) — w każdym modelu bazy wiedzy prawdziwe jest też α.

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

KB ⊨ α

to, o co pytamy: czy α wynika z bazy? Symbol ⊨ mówi o prawdzie w światach, a nie o tym, czy potrafimy coś wyprowadzić

M(KB)

światy, które baza dopuszcza — wartościowania, przy których prawdziwe są wszystkie jej zdania naraz (baza to ich koniunkcja); inne światy nas nie interesują, o nich baza twierdzi, że nie zaszły

⊆

zawieranie: w żadnym dopuszczonym świecie nie może zabraknąć α; jeden kontrprzykład wystarczyłby, by α nie wynikało

M(α)

światy, w których prawdziwe jest α; może ich być znacznie więcej — α może być prawdziwe także tam, gdzie baza nie jest

Najprostszym sposobem sprawdzenia wynikania jest sprawdzanie modeli (model checking): przejrzeć wszystkie wartościowania, wybrać te, przy których prawdziwa jest cała baza, i zobaczyć, czy prawdziwe jest w nich także pytanie. Nasza baza ma 24 symbole zdaniowe („ma sierść”, „ssak”, „tygrys”…), więc wartościowań jest 2²⁴ = 16 777 216. Spośród nich 13 440 to modele bazy — i we wszystkich prawdziwe jest „tygrys”. Odpowiedź brzmi tak, ale kosztem szesnastu milionów wierszy tabeli prawdy. Z każdym kolejnym symbolem liczba się podwaja; dla bazy z setkami symboli nie skończyłoby się to nigdy.

Przykład — sprawdzanie modeli dla trzech symboli

Baza KB = {pada ⇒ mokro, mokro ⇒ ślisko, pada}, pytanie α = ślisko. Trzy symbole dają 2³ = 8 wartościowań (1 = prawda, 0 = fałsz); implikacja p ⇒ q jest fałszywa tylko dla p = 1, q = 0.

pada	mokro	ślisko	pada ⇒ mokro	mokro ⇒ ślisko	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

Cała baza jest prawdziwa tylko w ostatnim wierszu, więc |M(KB)| = 1. W tym wierszu prawdziwe jest też „ślisko” — M(KB) ⊆ M(ślisko), a zatem KB ⊨ ślisko. Algorytm przeszedł 8 wierszy i w każdym obliczył 3 zdania bazy; ogólnie sprawdzanie modeli kosztuje O(2ⁿ · |KB|).

Przykład — skąd się wzięło 13 440 modeli

W każdym modelu bazy prawdziwych jest pięć zaobserwowanych faktów, a reguły R1, R6 i R9 wymuszają wtedy „ssak”, „drapieżnik” i „tygrys”. Tych 8 symboli jest na stałe prawdziwych. Pozostałe 16 rozpada się na grupy, które nie są ze sobą powiązane przez reguły, a liczby ich wartościowań się mnożą:

• „daje mleko” (R2 jest spełniona, ssak jest prawdą) i „je mięso” (R5 jest spełniona, drapieżnik jest prawdą): dowolnie, 2 · 2 = 4;
• „ma ciemne plamy”, „gepard” z regułą R8: trzy wartościowania — nie mogą być plamy bez geparda;
• „ma kopyta”, „kopytny”, „ma długą szyję”, „żyrafa”, „zebra” z R7, R10, R11: jeśli kopytny jest fałszem, fałszem muszą być też kopyta, a pozostałe trzy symbole są wolne (8 możliwości); jeśli jest prawdą, musi być prawdą zebra, kopyta są wolne, a szyja z żyrafą mają 3 możliwości (2 · 3 = 6); razem 14;
• grupa ptasia „ma pióra”, „lata”, „znosi jaja”, „ptak”, „nie lata”, „pływa”, „pingwin” z R3, R4, R12: bez ptaka nie mogą być prawdą pióra ani jednocześnie lata i jaja (3 możliwości), a ostatnie trzy symbole są wolne (8): 24; z ptakiem pióra są wolne (2), lata i jaja wolne (4), a z ośmiu wartościowań „nie lata, pływa, pingwin” zakazane jest tylko 1, 1, 0 (7): 56; razem 80.

Łącznie 4 · 3 · 14 · 80 = 13 440 — dokładnie tyle, ile naliczyło sprawdzanie modeli. I w każdym z nich prawdziwy jest tygrys, bo należy do symboli na stałe prawdziwych.

3. Wnioskowanie: poprawne i pełne

Zamiast przechodzić przez światy, można zdaniami manipulować: z posiadanych zdań tworzyć nowe według reguł wnioskowania, takich jak modus ponens. Tak robi to także człowiek.

Definicja — wyprowadzanie, poprawność, pełność

Piszemy KB ⊢ α, gdy α można otrzymać z KB skończenie wieloma zastosowaniami reguł wnioskowania.

Procedura wnioskowania jest poprawna, gdy z KB ⊢ α wynika KB ⊨ α — wyprowadza tylko to, co naprawdę wynika.

Jest pełna, gdy z KB ⊨ α wynika KB ⊢ α — wyprowadza wszystko, co wynika.

Definicja — klauzula Horna

Klauzula Horna to alternatywa literałów, z których co najwyżej jeden jest pozytywny. Klauzula z dokładnie jednym literałem pozytywnym jest określona i da się zapisać jako reguła

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

gdzie p₁, …, p_k to przesłanki, a q to wniosek. Dla k = 0 jest to fakt q.

Dlaczego „alternatywa z co najwyżej jednym literałem pozytywnym” to to samo co reguła? Implikacja A ⇒ q jest równoważna ¬A ∨ q, a z prawa De Morgana ¬(p₁ ∧ … ∧ p_k) to to samo co ¬p₁ ∨ … ∨ ¬p_k:

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

¬p₁ ∨ … ∨ ¬p_k

negatywne literały klauzuli; razem mówią „któraś przesłanka nie zachodzi” — a to jest dokładnie negacja koniunkcji przesłanek

(p₁ ∧ … ∧ p_k)

przesłanki reguły — z alternatywy literałów negatywnych stały się warunkiem dzięki De Morganowi; żadna z nich nie może być negatywna, inaczej w regule stałoby „jeśli nie zachodzi …”

q

jedyny literał pozytywny, wniosek; gdyby pozytywne były dwa, dostalibyśmy „to q lub r” i maszyna wnioskująca nie wiedziałaby, który z nich dodać

⇒

klauzula jest prawdziwa, gdy któraś przesłanka nie zachodzi lub zachodzi wniosek — to definicja implikacji; postać reguły tylko inaczej odczytuje tę samą alternatywę

4. Wnioskowanie w przód

Algorytm — wnioskowanie w przód

1. Każda reguła pamięta, ile jej przesłanek nie jest jeszcze znanych. Do agendy włóż wszystkie fakty.
2. Wybierz symbol z agendy. Jeśli był już przetworzony, przejdź do następnego.
3. Każdej regule, która ma go wśród przesłanek, zmniejsz licznik o 1. Jeśli spadnie do 0, reguła odpala: dodaj jej wniosek do agendy.
4. Powtarzaj, dopóki agenda nie jest pusta.

Twierdzenie. Dla bazy z określonych klauzul Horna wnioskowanie w przód jest poprawne i pełne dla symboli zdaniowych: wyprowadza dokładnie te, które wynikają z KB. Działa w czasie liniowym względem rozmiaru bazy.

Już pierwsza obserwacja „ma sierść” odblokowuje regułę R1, która dodaje „ssak” na koniec agendy. Pozostałe cztery obserwacje na razie niczego nie uruchamiają, ale zmniejszają liczniki. Gdy przychodzi kolej na ssaka, odblokowuje on R6 (ostre zęby i pazury już znamy) — powstaje „drapieżnik”. Drapieżnik odblokowuje R9 i mamy tygrysa. W ośmiu krokach, bez milionów wierszy. Reguła R5 („ssak, który je mięso, jest drapieżnikiem”) nie odpaliła nigdy: że zwierzę je mięso, nie wiemy — i nie musimy tego wiedzieć.

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:          # znamy wszystkie przesłanki
                    agenda.append(r.pak)
    return zname

Sercem algorytmu jest licznik przy każdej regule r z przesłankami P(r):

brakuje(r) = |P(r)| − |P(r) ∩ Znane|

brakuje(r)

ilu przesłanek jeszcze nie znamy; przy brakuje(r) = 0 reguła odpala — dzięki liczbie maszyna rozpozna to bez przeglądania listy przesłanek

|P(r)|

wartość początkowa: na początku nie wiemy nic, brakuje wszystkich przesłanek

|P(r) ∩ Znane|

przesłanki, które są już przetworzone; każdy przetworzony symbol zmniejsza licznik o 1 przy każdej regule, w której występuje — i jest przetwarzany tylko raz, dlatego nic nie zostanie policzone dwa razy

Jak liczniki spadają w trakcie naszego przebiegu (po przetworzeniu symbolu w danym wierszu; pogrubione zero oznacza odpalenie):

R5 zatrzymuje się na jedynce (brakuje „je mięso”), a R8 dla geparda również (brakuje „ma ciemne plamy”). Pozostałych reguł nie ma w tabeli; ich przesłanki w przebiegu albo w ogóle się nie pojawiły, albo tylko częściowo.

Twierdzenie — wnioskowanie w przód jest poprawne i pełne (dowód)

Poprawność. Każdy wyprowadzony symbol powstał z odpalenia reguły, której wszystkie przesłanki były już znane. W każdym modelu bazy prawdziwe są fakty i (indukcyjnie według kolejności wyprowadzania) także wcześniej wyprowadzone symbole, więc zgodnie z regułą prawdziwy jest też nowy wniosek — to modus ponens.

Pełność. Po zakończeniu weźmy wartościowanie m: prawda dla wyprowadzonych symboli (i faktów), fałsz dla wszystkich pozostałych. To jest model bazy: gdyby jakaś reguła p₁ ∧ … ∧ p_k ⇒ q nie była prawdziwa w m, wszystkie p_i byłyby wyprowadzone, a q nie — ale wtedy licznik reguły spadłby do zera i q zostałoby wyprowadzone. Jeśli więc q wynika z bazy, jest prawdziwe w modelu m, a zatem zostało wyprowadzone. ∎

Model m jest tym „najskromniejszym”: wierzy tylko w to, w co musi. Dla naszej bazy to wartościowanie, przy którym prawdziwe są dokładnie 5 obserwacji, ssak, drapieżnik i tygrys.

5. Wnioskowanie wstecz

Algorytm — wnioskowanie wstecz

Dowodzi celu q:

• jeśli q jest znanym faktem, jest udowodniony;
• w przeciwnym razie dla każdej reguły p₁ ∧ … ∧ p_k ⇒ q spróbuj po kolei udowodnić wszystkie p_i; jeśli przy którejś regule się to uda, q jest udowodniony;
• jeśli żadna reguła nie odniesie sukcesu, dowód się nie powiódł.

Dla określonych klauzul Horna wnioskowanie wstecz jest poprawne i pełne i bada tylko symbole związane z celem.

def zpetne(cil, fakta, pravidla, cesta=()):
    if cil in fakta:
        return True                           # wiemy to bezpośrednio
    if cil in cesta:
        return False                          # cykl: cel dowodzi sam siebie
    for r in pravidla:
        if r.pak == cil:                      # LUB: wystarczy jedna reguła
            if all(zpetne(p, fakta, pravidla, cesta + (cil,))
                   for p in r.kdyz):          # I: muszą wyjść wszystkie przesłanki
                return True
    return False                              # nie wiemy, jak to udowodnić

Funkcja all zatrzymuje się na pierwszej przesłance, która nie wychodzi — dlatego przy R5 po porażce z „je mięso” nic więcej nie jest badane. Lista cesta (ścieżka) pilnuje, żeby reguły takie jak „a ⇒ b, b ⇒ a” się nie zapętliły.

Algorytm zbadał 11 celów. Drapieżnika próbował najpierw udowodnić regułą R5 — ssaka udowodnił, ale natrafił na „je mięso”: tego nie wiemy, więc zrezygnował z R5 i spróbował R6, która się udała. Tu wnioskowanie wstecz jest mocne: wie, czego mu brakuje. System ekspertowy w takiej chwili pyta użytkownika: „Czy to zwierzę je mięso?” Cała rozmowa z systemem ekspertowym to więc właściwie wnioskowanie wstecz na głos.

Kiedy czego używać? Wnioskowanie w przód pasuje, gdy napływają dane i chcesz wiedzieć, co z nich wynika — na przykład przy monitorowaniu produkcji. Wnioskowanie wstecz, gdy masz konkretne pytanie — diagnoza, zapytanie do bazy danych. Gdybyśmy zapytali „czy to zebra?”, wnioskowanie wstecz obaliłoby to po zbadaniu zaledwie 5 celów: zebra jest kopytna, a kopyt nasze zwierzę nie ma.

6. Rezolucja: wnioskowanie dla całej logiki

Klauzule Horna nie wystarczą do wszystkiego. Zdanie „zwierzę jest ssakiem lub ptakiem” ma we wniosku „lub” i regułą go nie zapiszesz. Dla dowolnych zdań istnieje jedna reguła, która wystarcza do wszystkiego.

Definicja — rezolucja

Zdania sprowadza się do koniunkcyjnej postaci normalnej — koniunkcji klauzul, z których każda jest alternatywą literałów. Reguła rezolucji: z klauzul (A ∨ ℓ) i (B ∨ ¬ℓ) wyprowadź (A ∨ B).

Dowód nie wprost: KB ⊨ α wtedy i tylko wtedy, gdy KB ∧ ¬α jest niespełnialna. Rezolucja wyprowadza z KB ∧ ¬α nowe klauzule; jeśli wyprowadzi klauzulę pustą, sprzeczność została znaleziona. Taka procedura jest poprawna i pełna (Robinson, 1965).

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

ℓ, ¬ℓ

literały komplementarne — w każdym świecie prawdziwy jest dokładnie jeden z nich, więc jednej z klauzul nie spełni; ta musi być spełniona przez swoją resztę. Dlatego w wyniku brakuje ℓ

A

reszta pierwszej klauzuli: zachodzi zawsze, gdy ℓ jest fałszem (wtedy pierwszą klauzulę utrzymuje tylko A)

B

reszta drugiej klauzuli: zachodzi zawsze, gdy ℓ jest prawdą (wtedy ¬ℓ nie zachodzi i drugą klauzulę utrzymuje B)

Algorytm — sprowadzenie do koniunkcyjnej postaci normalnej

1. Usuń równoważności: α ⇔ β zastąp przez (α ⇒ β) ∧ (β ⇒ α).
2. Usuń implikacje: α ⇒ β zastąp przez ¬α ∨ β.
3. Przesuń negacje aż do symboli: ¬¬α ≡ α, ¬(α ∧ β) ≡ ¬α ∨ ¬β, ¬(α ∨ β) ≡ ¬α ∧ ¬β (De Morgan).
4. Rozdziel ∨ względem ∧: α ∨ (β ∧ γ) ≡ (α ∨ β) ∧ (α ∨ γ).

Przykład: (pada ∨ śnieży) ⇒ mokro

krok 2: ¬(pada ∨ śnieży) ∨ mokro

krok 3: (¬pada ∧ ¬śnieży) ∨ mokro

krok 4: (¬pada ∨ mokro) ∧ (¬śnieży ∨ mokro) — dwie klauzule, obie nawet hornowskie.

Rozdzielanie w 4. kroku może wykładniczo wydłużyć formułę; solwery stosują więc w praktyce transformację Tseitina z symbolami pomocniczymi, która daje wynik dłuższy tylko liniowo (spełnialny wtedy i tylko wtedy, gdy formuła pierwotna).

Rezolucja jest uniwersalna, ale w ogólności droga: dla logiki zdań problem spełnialności (SAT) jest NP-zupełny. Współczesne solwery SAT mimo to radzą sobie z milionami zmiennych — była o nich mowa w części o spełnianiu ograniczeń.

7. Reguły ze zmiennymi i Prolog

Logika zdań ma wadę: „Rex jest ssakiem” i „Micka jest ssakiem” to dla niej dwa niezwiązane symbole. Regułę o wszystkich ssakach trzeba by przepisać dla każdego zwierzęcia osobno. Logika predykatów z części o logice i dowodach rozwiązuje to zmiennymi: ∀x : ma_sierść(x) ⇒ ssak(x).

Definicja — unifikacja

Unifikator dwóch wyrażeń to podstawienie za zmienne, po którym oba wyrażenia są identyczne. Na przykład rodič(jan, Y) i rodič(X, petr) (rodič = rodzic) unifikuje podstawienie {X / jan, Y / petr}. Algorytm unifikacji znajduje najogólniejszy unifikator, jeśli istnieje.

def unifikuj(a, b, s):                    # s: dotąd znalezione podstawienie (słownik)
    if s is None:
        return None                           # już wcześniej się nie powiodło
    a, b = dosad(a, s), dosad(b, s)           # zastosuj to, co już wiemy
    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 drugim
            s = unifikuj(x, y, s)
        return s
    return None                               # różne stałe lub predykaty

Na przykładzie rodič(jan, Y) i rodič(X, petr): predykaty się zgadzają, więc porównuje się argumenty. jan i X dają {X / jan}, Y i petr dodają Y / petr. Natomiast rodič(jan, Y) i rodič(petr, eva) się nie unifikują — jan i petr to różne stałe. Test vyskytuje_se (occurs check) zapobiega podstawieniu typu X / f(X), które prowadziłoby do nieskończonego wyrażenia. (Prolog ze względu na szybkość standardowo go pomija.)

Na wnioskowaniu wstecz z unifikacją opiera się Prolog (Alain Colmerauer, Marsylia, 1972) — język, w którym program jest bazą wiedzy, a uruchomienie programu to zapytanie (rodic = rodzic, prarodic = dziadek lub babcia, kdo = kto):

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

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

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

Prolog dochodzi do celu prarodic(jan, Kdo) dokładnie tak jak nasze drzewo dla tygrysa: znajduje regułę, unifikuje X = jan, dowodzi rodic(jan, Y), znajduje Y = petr, a potem rodic(petr, Z) z wynikiem eva.

8. Systemy ekspertowe

System ekspertowy to baza wiedzy spisana razem z ekspertem i maszyna wnioskująca, zwykle z wnioskowaniem wstecz i z możliwością wyjaśnienia, dlaczego doszedł do wniosku — wystarczy odczytać drzewo, które narysowaliśmy wyżej. Najbardziej znane były trzy:

• DENDRAL (Stanford, od 1965 roku) określał strukturę cząsteczek na podstawie danych ze spektrometru mas — pierwszy system, który wykonywał pracę naukowców według ich własnych reguł.
• MYCIN (Stanford, lata 70.) diagnozował bakteryjne zakażenia krwi i zalecał antybiotyki. Miał około sześciuset reguł, a w ocenie z 1979 roku jego zalecenia wypadły tak samo dobrze jak zalecenia specjalistów ze Stanfordu albo lepiej. Mimo to nigdy nie był używany w szpitalu.
• XCON (firma DEC, od 1980 roku) składał konfiguracje komputerów VAX według zamówienia. Miał tysiące reguł i według firmy oszczędzał dziesiątki milionów dolarów rocznie.

Medycyna jednak rzadko zna pewność. MYCIN dołączał więc do każdej reguły liczbę mówiącą, jak bardzo ekspert jej ufa:

Definicja — współczynnik pewności

Współczynnik pewności CF ∈ [−1, 1] wyraża stopień zaufania do wniosku: 1 na pewno zachodzi, −1 na pewno nie zachodzi, 0 nie wiemy. Jeśli ten sam wniosek wspierają dwie reguły z dodatnimi współczynnikami CF₁ i CF₂, wynikowy współczynnik wynosi

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

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

CF₁

zaufanie z pierwszej reguły; druga reguła nie może go obniżyć, tylko dodać

CF₂

jaką część pozostałej niepewności druga reguła usuwa; gdyby po prostu dodawać, dwie wskazówki po 0,6 dałyby bezsensowne 1,2

1 − CF₁

niepewność, która została po pierwszej regule; tylko z niej można jeszcze ująć, dlatego wynik nigdy nie przekroczy 1

Przykład — trzy wskazówki i reguła z niepewnymi przesłankami

Trzy wskazówki 0,6, 0,5 i 0,5: najpierw 0,6 + 0,5 · (1 − 0,6) = 0,8, potem 0,8 + 0,5 · (1 − 0,8) = 0,9. Sprawdzenie przez niepewności: 1 − 0,4 · 0,5 · 0,5 = 0,9.

Niepewne przesłanki. W MYCIN-ie (Shortliffe i Buchanan, 1975) koniunkcja przesłanek dostaje współczynnik swojego najsłabszego ogniwa, a wniosek reguły współczynnik reguły razy ten minimalny współczynnik (reguła jest przy tym stosowana tylko wtedy, gdy minimum przekracza 0,2): CF(wniosek) = CF(reguła) · min_i CF(p_i). Reguła ze współczynnikiem 0,7, której przesłanki mają współczynniki 0,9 i 0,6, wnosi więc do wniosku 0,7 · min(0,9; 0,6) = 0,42.

Pod koniec lat osiemdziesiątych pokazały się granice. Pozyskiwanie wiedzy było wąskim gardłem: ekspert często nie potrafi wyrazić swojego know-how w postaci reguł, a każda reguła kosztowała godziny rozmów. Systemy były kruche: krok poza swoją dziedziną nie wiedziały nic i nie wiedziały nawet, że nic nie wiedzą. A tysiące reguł trudno było utrzymać — nowa reguła mogła po cichu przeczyć starej. Rynek systemów ekspertowych się załamał i nadeszła druga zima sztucznej inteligencji. Odpowiedź, która przyszła potem, jest odwrotna: wiedzy nie spisywać, tylko nauczyć się jej z danych.

9. Wiedza w dzisiejszej sztucznej inteligencji

• Grafy wiedzy. Google od 2012 roku odpowiada na wiele zapytań z grafu wiedzy — sieci faktów typu (Praga, stolica, Czechy). Swobodnie dostępne Wikidane mają ponad sto milionów elementów. To baza wiedzy, tylko zamiast reguł przeważają fakty.
• Reguły tam, gdzie wszystko musi dać się sprawdzić. Obliczenia podatkowe, warunki ubezpieczenia, zatwierdzanie kredytów czy polityki bezpieczeństwa do dziś pisze się jako reguły: każdą decyzję da się wyjaśnić i obronić.
• Modele językowe i wiedza. Model językowy ma ogromną ilość wiedzy, ale rozproszoną w wagach sieci — nie da się jej odczytać ani poprawić po kawałku, a model czasem pewnie zmyśla. Dlatego podłącza się do niego wyszukiwanie w bazie wiedzy (RAG) albo narzędzia i maszyny wnioskujące, które sprawdzą wynik.
• Neurosymboliczna AI łączy jedno z drugim: sieć rozpoznaje, co widzi, a logika wyprowadza z tego, co wynika. Przykładem są systemy szukające dowodów matematycznych: model proponuje krok, a formalne narzędzie mechanicznie go sprawdza.

10. Podsumowanie

• Baza wiedzy to zbiór zdań; KB ⊨ α znaczy, że α jest prawdziwe we wszystkich modelach bazy. Sprawdzanie modeli to weryfikuje, ale kosztem 2ⁿ wartościowań.
• Wyprowadzanie (⊢) pracuje na zdaniach zamiast na światach. Chcemy, żeby było poprawne (nic nie wymyśla) i pełne (nic nie przeocza).
• Dla klauzul Horna wystarczy wnioskowanie w przód (od faktów, sterowane danymi) albo wstecz (od celu, sterowane pytaniem); wnioskowanie w przód działa w czasie liniowym, wstecz bada tylko to, co wiąże się z celem.
• Dla całej logiki zdań jest rezolucja i dowód nie wprost; dla reguł ze zmiennymi unifikacja i Prolog.
• Systemy ekspertowe pokazały siłę i granice ręcznie spisanej wiedzy — i przygotowały grunt pod uczenie się z danych.

Chcesz to wypróbować? Poproś agenta AI, żeby napisał system ekspertowy z wnioskowaniem wstecz, który pyta o brakujące fakty — i wymyśl własne reguły dla czegoś, na czym się znasz.

Masz inne zdanie? Napisz na support@coden-app.com.