Sztuczna inteligencja/SI Moduł 3 - Wnioskowanie w PROLOG-u

Wprowadzenie

Jak mogliśmy się przekonać na podstawie poprzedniego rozdziału, logika predykatów jest takim sposobem opisywania świata, w którym zapis stwierdzeń prawdziwych (faktów) i reguł wynikania pozwala na wnioskowanie – wyprowadzanie nowych prawdziwych stwierdzeń. Język PROLOG (akronim od PROgramming in LOGic) pozwala na zapis faktów i reguł w formalny sposób, a także na przeprowadzenie wnioskowania za pomocą wbudowanej „maszyny wnioskującej”. W praktyce odbywa się to w taki sposób, że użytkownik, po „oprogramowaniu wiedzy” (wprowadzeniu faktów i reguł) może zadawać pytania o prawdziwość stwierdzeń. Każde zapytanie uruchamia maszynę wnioskującą, która stara się wyznaczyć wszystkie sposoby udowodnienia prawdziwości badanego stwierdzenia, wychodzące od faktów poprzez reguły.

Język PROLOG jest językiem deklaratywnym – użytkownik nie musi programować metody wnioskowania, gdyż jest ona wbudowana, lecz musi jedynie wprowadzić fakty i reguły. Czytelnicy znający tematykę relacyjnych baz danych mogą tu dostrzec analogię do języka SQL, w którym również deklaruje się jedynie strukturę bazy danych i wprowadza się dane. Po utworzeniu bazy danych można następnie zadawać zapytania (kwerendy – fraza SELECT), prowadzące do wybrania z bazy danych tych rekordów, które spełniają kryteria selekcji. Chociaż PROLOG jest językiem deklaratywnym, sposób zapisu faktów i reguł ma wpływ na szybkość wykonania wnioskowania. Język został ponadto wbudowany w elementy sterowania wnioskowaniem, którym przyjrzymy się bliżej w trakcie tej lekcji. Również i pod tym względem można dostrzec analogię do języka SQL, w którym różny zapis fraz SELECT (np. różna kolejność rozważania kryteriów selekcji) skutkuje bardzo zróżnicowanymi czasami wykonania (a programowanie fraz SELECT stanowi umiejętność samą w sobie).

Po tej krótkiej charakterystyce przejdźmy teraz do omówienia elementów składni języka, a następnie rozważymy kilka przykładowych programów w języku PROLOG.

Programy w języku PROLOG można kompilować i wykonywać korzystając z narzędzia SWI-PROLOG: http://www.swi-proglog.org

Składnia języka PROLOG

PROLOG opisuje związki zachodzące między zbiorami danych. Reprezentantem zbioru danych jest zmienna – element języka, mający nazwę, mogący przyjmować wartość z pewnego zbioru, zwanego dziedziną. Z kolei stałą jest wartość, będąca ustalonym elementem dziedziny.

Zmienne i dziedziny

Przykładami dziedziny mogą być:

• zbiór liczb rzeczywistych,
• zbiór liczb całkowitych,
• zbiór napisów {„czerwony”, „zielony”, „niebieski”}.

Stałymi są (w nawiasach określono dziedziny):

• liczba 4,35 (liczba rzeczywista),
• liczba -13 (liczba całkowita),
• napis „czerwony” (wymieniony wyżej zbiór napisów).

W języku PROLOG zmienne będziemy oznaczać napisami rozpoczynającymi się od wielkiej litery. Definicja zmiennej polega na określeniu jej nazwy i dziedziny. Robimy to, wykorzystując frazę domain:

domain(<Zmienna>, <Zbiór>).

Predykaty

Związki pomiędzy wartościami pochodzącymi z różnych dziedzin są predykatami. A zatem predykat jest zbiorem, będącym podzbiorem iloczynu kartezjańskiego zbiorów związanych tym predykatem.

Przykładowo, jeżeli rozważymy następujące dziedziny:

A={"mały", "duży"}
B={"czerwony", "zielony", "niebieski"}
C={"trójkąt", "kwadrat"}

to predykatem jest każdy podzbiór iloczynu kartezjańskiego $AxBxC$, a zatem podzbiór zbioru następujących trójek:

{(mały czerwony trójkąt),
 (mały zielony trójkąt),
 (mały niebieski trójkąt),
 (duży czerwony trójkąt),
 (duży zielony trójkąt),
 (duży niebieski trójkąt),
 (mały czerwony kwadrat),
 (mały zielony kwadrat),
 (mały niebieski kwadrat),
 (duży czerwony kwadrat),
 (duży zielony kwadrat),
 (duży niebieski kwadrat)}

Przykładowym predykatem może być

P={(mały czerwony trójkąt),
   (duży czerwony trójkąt),
   (mały czerwony kwadrat),
   (mały zielony kwadrat),
   (mały niebieski kwadrat),
   (mały niebieski trójkąt)}

Definiowanie predykatu poprzez wyliczanie wszystkich jego elementów jest bardzo niewygodne, a niekiedy wręcz niemożliwe (np. zbiór dodatnich liczb rzeczywistych). Z tego powodu predykaty definiuje się jako zbiór tych elementów z iloczynu kartezjańskiego dziedzin, dla którego da się udowodnić prawdziwość pewnej funkcji logicznej. Przykładowo, predykat P mógłby być zdefiniowany jako zbiór tych trójek X,Y,Z, dla których: Y=czerwony i Z=trójkąt lub X=mały i Z=kwadrat lub X=mały i Y=niebieski i Z=trójkąt.

Predykaty wbudowane

W PROLOGu istnieją predykaty wbudowane oraz predykaty definiowane przez użytkownika. Predykaty wbudowane to między innymi takie, które określają relacje między wartościami tej samej dziedziny.

Niektóre dziedziny są „bogatsze” w możliwe operacje w porównaniu z innymi dziedzinami. Przykładowo, dla wszystkich dziedzin można zdefiniować operację równości, oznaczaną znakiem „=”. Jednak nie dla wszystkich dziedzin da się określić relację porządkującą, a zatem operację porównania „<”. W podanych wyżej przykładowych dziedzinach, operacja porównania jest dobrze określona jedynie dla zbiorów liczb rzeczywistych i całkowitych. Przykładowo, operacja przyrównania jest predykatem postaci:

=(X,Y)

gdzie X, Y są zmiennymi tej samej dziedziny. Dla wygody zapisu przyjęto w wielu dialektach PROLOGu notację beznawiasową dla predykatów wbudowanych, tak więc predykatu związanego z operacją przyrównania można używać pisząc:

X=Y

Nazwy predykatów wbudowanych są zastrzeżone i nie można ich przedefiniować.

Predykaty użytkownika

Definicja predykatu użytkownika może mieć dwojaką formę. Pierwsza, prostsza forma jest zwana faktem. Podaje się w ten sposób zbiory wartości dziedzin argumentów predykatu, których iloczyn kartezjański należy do predykatu.

Druga, bardziej złożona forma definicji predykatu to reguła (czyli implikacja). Składa się ona z dwóch części – konkluzji (mającej formę predykatu) oraz części przesłankowej – mającej formę warunku logicznego lub koniunkcji warunków, rozdzielonych przecinkami. Aby część przesłankowa była prawdziwa, warunek logiczny musi być spełniony dla choć jednego zestawu zmiennych, występujących w tym warunku. Konkluzję od części przesłankowej rozdziela napis :- (dwukropek, minus).

Każda definicja predykatu jest kończona kropką.

Predykat jest zbiorem tych elementów iloczynu kartezjańskiego dziedzin argumentów, dla których prawdziwa jest choć jedna definicja predykatu (tzn. choć jeden fakt lub reguła). O pozostałych elementach tego iloczynu kartezjańskiego nie sposób wywnioskować, że są prawdziwe. Pamiętajmy jednak, że nie musi to wcale automatycznie oznaczać, że są fałszywe.

Przykładowo, predykat pred1 może zostać zdefiniowany jako:

domain(X, ["maly", "duzy"]).
domain(Y, ["czerwony", "zielony" , "niebieski"]).
domain(Z, ["kwadrat", "trojkat"]).

pred1(X, "czerwony", "trojkat").
pred1("maly", Y, "kwadrat").
pred1("maly", "niebieski", "trojkat").

Zmienne X, Y, Z muszą zostać wpierw zdefiniowane, a zatem podawane są ich nazwy i zbiory wartości.

Są trzy alternatywne definicje predykatu pred1, wszystkie będące faktami. Pierwsza z nich to „czerwone trójkąty”, druga – „małe kwadraty”, zaś trzecia – „mały niebieski trójkąt”. Zwróćmy uwagę, że można by dopisać jeszcze co najmniej kilka alternatywnych definicji, np.:

pred1(X,Y,Z):-
  X="maly", Z="czerwony".

Tak więc alternatywne definicje mogą być nadmiarowe. Z punktu widzenia logiki jest jednak to, aby alternatywne definicje nie były wzajemnie sprzeczne, a także, aby zbiór elementów iloczynu kartezjańskiego dziedziny, spełniających choć jedną z alternatywnych definicji, był tożsamy z predykatem.

Rozważmy teraz przykład, w którym definicja predykatu zawiera regułę wnioskowania. Za pomocą predykatów kr_ko, m_ko, m_kr, m_st, opiszemy następujące relacje świata rzeczywistego: kraj położony na kontynencie, miasto położone na kontynencie, miasto położone w kraju oraz miasto będące stolicą kraju:

m_ko("Warszawa", "Europa").
m_ko("Kraków", "Europa").
m_ko("Irkuck", "Azja").
m_ko("Moskwa", "Europa").
m_kr("Kraków", "Polska").
m_kr("Irkuck", "Rosja").
m_st("Warszawa", "Polska").
m_st("Moskwa", "Rosja").

m_kr(Miasto, Kraj):-
  m_st(Miasto, Kraj).

kr_ko(Kraj, Kont):-
  m_kr(Miasto, Kraj),
  m_ko(Miasto, Kont).

Oprócz faktów, mamy tutaj dwie reguły. W regule:

kr_ko(Kraj, Kont):-
  m_kr(Miasto, Kraj),
  m_ko(Miasto, Kont).

konkluzją jest:

kr_ko(Kraj, Kont)

natomiast część przesłankowa zawiera postulat istnienia takiej wartości zmiennej pomocniczej Miasto, dla której prawdziwa jest koniunkcja dwóch warunków logicznych:

m_kr(Miasto, Kraj),
m_ko(Miasto, Kont).

Zwróćmy uwagę na konwencję zapisu zbiorów elementów: wyliczone wartości są rozdzielone przecinkami i ujęte w nawiasy kwadratowe. Tak naprawdę, PROLOG przechowuje zbiory wartości nie jako nieuporządkowane kolekcje, lecz jako listy (co za tym idzie, przyjmuje kolejność przeglądania takiej listy).

Listy

Można powiedzieć, że lista jest podstawową strukturą danych PROLOGu. Listę można definiować wyliczając jej kolejne elementy, np.:

["a","b","c","b"]

lub też podając jej dwa fragmenty, pierwszy element (zwany głową) i listę pozostałych elementów (zwaną ogonem):

["a"|["b","c","b"]]

W tym przykładzie, ogonem jest lista ["b","c","b"], a głowę od ogona oddziela operator |. Możliwa jest też konwencja mieszana, w której pierwsze elementy listy są wyliczane i doklejana jest do nich lista-ogon:

["a","b"|["c","b"]

Są dwa szczególne przypadki list:

• lista jednoelementowa, np. ["a"]
• lista pusta: []

Elementami listy mogą być dowolne wartości, w szczególności mogą być to listy, np.:

[["a","b"],["c"],"d", []]

W powyższym przykładzie, mamy do czynienia z listą zawierającą cztery elementy – pierwszym jest dwuelementowa lista ["a","b"], drugim – jednoelementowa lista ["c"], trzecim – wartość "d", zaś czwartym – lista pusta [].

Przykładowe predykaty

Predykat member

Spróbujmy teraz zdefiniować predykat, który jest prawdziwy wówczas, gdy pierwszy argument predykatu jest elementem listy, będącej drugim argumentem. Składania predykatu jest następująca:

member(X,L) gdzie X jest wartością, a L – listą.

Przykładowo, prawdziwe są stwierdzenia:

member("c", ["a","b","c","d"]).
member("a", ["a","b","c","d"]).

Definicję predykatu spróbujemy poprzedzić analizą problemu.

1. Warunek logiczny predykatu jest spełniony, jeśli głową listy L jest wartość X.
2. Warunek logiczny predykatu jest spełniony, jeśli głową listy L jest wartość różna od X, lecz predykat jest spełniony dla X i ogona listy L.

Z powyższej analizy wynika natychmiast definicja predykatu:

member(X,[X|T]).
member(X,L):-
  L=[H|T],
  member(X,T).

Łatwo zauważyć że w powyższej definicji niektóre zdefiniowane zmienne nie są wykorzystywane (np. T w pierwszej definicji predykatu). W związku z tym możliwa jest bardziej zwarta definicja predykatu, którą uzyskuje się zastępując niepotrzebne zmienne symbolem podkreślenia:

member(X,[X|_]).
member(X,[_,T]):-
  member(X,T).

Predykat append

Kolejny predykat będzie miał charakter nieco bardziej proceduralny. Chcemy napisać predykat, który będzie „łączyć” dwie listy w trzecią, doklejając zawartość jednej listy za ostatnim elementem drugiej listy. Składania predykatu jest następująca

append(L1, L2, L3)

gdzie L2 jest listą doklejaną na koniec listy L1 w celu uzyskania listy L3.

Mamy w pamięci, że PROLOG jest językiem deklaratywnym, jak więc można uzyskać taki efekt „doklejenia”? Odpowiedź na to pytanie przyniesie kolejny punkt, my zaś tymczasem przeformułujmy zadanie tak, że predykat append sprawdza, czy lista L3 powstała w wyniku odpowiedniego doklejenia. Tak więc przykładowe stwierdzenia są prawdziwe:

append([],[],[]).
append(["a","b"],[],["a","b"]).
append([], ["a","b"], ["a","b"]).
append(["a","b"],["c","d"],["a","b","c","d"]).

Ponownie zanalizujmy problem:

1. Jeśli lista L1 jest pusta, to L3 jest tożsama z L2.
2. Jeśli lista L2 jest pusta, to L3 jest tożsama z L1.
3. Jeśli obie listy są niepuste, to głowa listy L1 powinna być równa głowie listy L3, a ogon listy L3 powinien być wynikiem sklejenia ogona listy L1 z listą L2.

Definicja predykatu będzie więc następująca:

append([],L,L).
append(L,[],L).
append(L1,L2,L3):-
  L1=[H|T1],
  L3=[H|T3],
  append(T1,L2,T3).

Rezolucja i unifikacja w PROLOGu

Spróbujmy teraz wykonać wnioskowanie, posługując się przykładowymi predykatami opisanymi w poprzednim punkcie. Wnioskowanie przebiega według zasad rezolucji i unifikacji przedstawionych w lekcji drugiej.

Weryfikacja stwierdzenia, prowadzona przez maszynę wnioskującą języka PROLOG, jest procesem o charakterze rekurencyjnym (proszę sobie przypomnieć metodę ruchem skoczka szachowego przejścia przez wszystkie pola szachownicy, tak że każde jej pole zostanie odwiedzone dokładnie jeden raz). Oznacza to, że kolejne etapy procesu wnioskowania można sobie wyobrazić w postaci drzewa, którego węzły odpowiadają kolejnym stanom procesu wnioskowania (charakteryzowanym przez rozważanie kolejnych podstawień zmiennych). Korzeniem drzewa jest stwierdzenie podlegające weryfikacji, zaś węzłami terminalnymi (liśćmi) są stany, w których unifikacja ani podstawienie są niemożliwa (porażka) bądź też wszystkie warunki prawdziwości predykatu są spełnione bez konieczności rozwinięć rekurencyjnych (sukces). Stwierdzenie poddawane weryfikacji (korzeń) jest uznawane za prawdziwe wówczas, gdy choć jeden liść jest sukcesem.

Drzewo wnioskowania jest przeglądane sekwencyjnie, po kolejnych ścieżkach prowadzących od korzenia do liścia. Kolejność przeglądania tych ścieżek jest narzucona przez program w PROLOGu poprzez określenie kolejności definicji predykatów. Poniżej prześledzimy proces weryfikacji prawdziwości stwierdzeń. Będziemy używać symboli „/” i „~” na oznaczenie podstawienia i unifikacji.

Rozważmy na początek predykat member. Ponumerujmy linie jego definicji:

def1 member(X,[X|_]).
def2 member(X,[_|T]):-
  member(X,T).

Załóżmy, że był on wywołany w następujący sposób:

member("c", ["a","b","c"]).

Wnioskowanie przebiegnie następująco:

def1 X/"c", ["a","b","c"]=[X|_], X/"a" porażka
def2 X/"c", ["a","b","c"]=[_|T], T/["b","c"]
  def1 X/"c", ["b","c"]=[X|_], X/"b" porażka
  def2 X/"c", ["b","c"]=[_|T], T/["c"]
    def1 X/"c", ["c"]=[X|_], X/"c" sukces
    def2 X/"c", ["c"]=[_|T], T/[]
      def1 X/"c", []=[X|_] porażka
      def2 X/"c", []=[_|T] porażka

Tak więc wynikiem wnioskowania będzie prawda (stwierdzenie jest prawdziwe, bo w toku wnioskowania udało się znaleźć co najmniej jedną definicję predykatu, którego podstawienie wartości zmiennych zakończyło się sukcesem). Zbiór podstawień wartości zmiennych, dla których stwierdzenie jest prawdziwe, jest równy

{ ("c", ["a","b","c"]) }

Przyjmijmy teraz, że wywołanie predykatu member jest nieco odmienne (pierwszy argument jest zmienną)

member(N, ["a","b","c"]).

Wnioskowanie przebiegnie następująco:

def1 X~N, ["a","b","c"]=[X|_], X/"a" sukces
def2 X~N, ["a","b","c"]=[_|T], T/["b","c"]
  def1 X~N, ["b","c"]=[X|_], X/"b" sukces
  def2 X~N, ["b","c"]=[_|T], T/["c"]
    def1 X~N, ["c"]=[X|_], X/"c" sukces
    def2 X~N, ["c"]=[_|T], T/[]
      def1 X~N, []=[X|_] porażka
      def2 X~N, []=[_|T] porażka

Tak więc wynikiem wnioskowania będzie prawda, a zbiór podstawień wartości argumentów, dla których stwierdzenie jest prawdziwe, jest równy:

{ ("a", ["a","b","c"]), ("b", ["a","b","c"]), ("c", ["a","b","c"]) }

Zauważmy, że w ten sposób inaczej użyliśmy predykatu member, tworzonego z zamysłem weryfikacji, czy wartość X jest elementem listy L. Predykat ten można mianowicie wykorzystać do wyprowadzenia wszystkich elementów zawartych w liście L.

Zwróćmy uwagę, że „rozwiązanie robocze”, czyli unifikacje argumentów pierwszego wywołania, są tworzone na bieżąco poprzez kolejne unifikacje w kolejnych zagnieżdżeniach procesu wnioskowania. Tak więc argument N poprzez unifikacje z argumentami X w kolejnych zagnieżdżeniach, przyjmuje kolejno wartości „a”, „b”, „c”. Reguła unifikacji na bieżąco nabiera znaczenia wówczas, gdy wynikiem unifikacji jest obiekt o strukturze złożonej, czyli lista.

def1 append(L1,L2,L3):-
  L1=[],
  L3=L2.
def2 append(L1,L2,L3):-
  L2=[],
  L3=L1.
def3 append(L1,L2,L3):-
  L1=[H|T1],
  L3=[H|T3],
  append(T1,L2,T3).

Ilustracją tego procesu niech będzie sposób wnioskowania w weryfikacji stwierdzenia:

append(["a","b"],["c","d"],L).
def1 ["a","b"]/[] porażka
def2 ["c","d"]/[] porażka
def3 ["a","b"]/[H|T1], H/"a", T1/["b"], L3~["a"|T3]

a zatem L3~["a"|T3], co oznacza, że cała lista L nie jest wprawdzie znana, ale jej głowa jest już znana na tym etapie!

def1 ["b"]/[] porażka
def2 ["c","d"]/[] porażka
def3 ["b"]/[H|T1], H/"b", T1/[], L3~["b"|T3]

tutaj L3 jest zmienną zunifikowaną z T3 z wywołania powyżej, zatem lista L ma na tym etapie postać ["a","b"|T3]

def1 []/[], L3=["c","d"] sukces

w tym momencie lista L przyjmuje postać ["a","b","c","d"]

def2 ["c","d"]/[] porażka
def3 []/[H|T1] porażka

Zatem badane stwierdzenie jest prawdziwe dla następującego zbioru trójek argumentów:

{(["a","b"],["c","d"], ["a","b","c","d"])}

W ramach ćwiczenia proszę zastanowić się nad sposobem wnioskowania i zbiorem wartości zmiennych dla których poniższe stwierdzenie jest prawdziwe:

append(L1,L2,["a","b","c","d"])

Mechanizm odcięcia

W czasie weryfikacji stwierdzenia - korzenia, w pamięci komputera rozwijane są kolejne ścieżki drzewa wnioskowania, w wyniku czego wszystkie liście drzewa zostaną przejrzane. Takie podejście może powodować, że wnioskowanie teoretycznie nigdy się nie skończy (a w praktyce zaowocuje wyczerpaniem zasobów komputera). Przykładem takiej sytuacji może być weryfikacja stwierdzenia:

member("a", L).

używając najprostszej definicji predykatu member:

def1 member(X,[X|_]).
def2 member(X,[_|T]):-
       member(X,T).

Łatwo sprawdzić, że w wyniku wywołań rekurencyjnych, z powodu wielokrotnie wywoływanej definicji def2, lista L będzie unifikowana z coraz to dłuższą listą. Nie trzeba dodawać, że przyczyną tej sytuacji jest nieskończona liczba list spełniających warunek prawdziwości definicji predykatu member; listy takie można utworzyć chociażby z samych elementów „a”. W takich przypadkach wystarcza często zadowolić się dokładnie jednym liściem, który pozytywnie weryfikuje prawdziwość stwierdzenia, i zaniechać dalszego przeglądu drzewa wnioskowania. Efekt ten można osiągnąć, stosując operację odcięcia.

Operacja odcięcia jest zaznaczana symbolem wykrzyknika „!”. Znaczenie odcięcia jest następujące. Jest to predykat bezargumentowy, zawsze prawdziwy, który w czasie swojej weryfikacji powoduje zaniechanie badania innych, pozostałych jeszcze do weryfikacji definicji predykatów na bieżącym poziomie drzewa wnioskowania.

Dla przykładu wzbogacimy definicję predykatu member o operację odcięcia:

def1 member(X,L):-
       L=[X|T],!.
def2 member(X,L):-
       L=[H|T],
       member(X,T).

W czasie weryfikacji stwierdzenia:

member("a", ["a","b","c"]).

następują podstawienia:

def1 X/"a", ["a","b","c"]/["a"|T], T/["b","c"], ! sukces

i wnioskowanie się kończy, gdyż definicja def2 została odcięta.

Odcięcie zastosowane powyżej miało miejsce po spełnieniu wszystkich warunków logicznych warunkujących prawdziwość predykatu. Tak nie musi być, operacja ta może być również wykorzystana „w środku” definicji predykatu. Przykładem niech będzie predykat app2 (L1,L2,L3), prawdziwy, jeśli lista L3 jest posortowaną listą, będącą wynikiem złączenia posortowanych list L1, L2; w kolejności rosnącej. Zakładamy istnienie predykatu X<Y.

app2(L,[],L):-!.
app2([],L,L):-!.
app2([H1|T1],[H2|T2],[H3|T3]):-
  H1<H2,!,
  H3=H1,
  app2(T1,[H2|T2],T3).
app2([H1|T1],[H2|T2],[H3|T3]):-
  H1>H2,!,
  H3=H2,
  app2([H1|T1],T2,T3).
app2([H1|T1],[H2|T2],[H3|T3]):-
  H1=H2,!,
  H3=H2,
  app2(T1,T2,T3).

W powyższym przykładzie, jeśli żadna z list będących argumentami predykatu app2 nie jest pusta, próby zastosowania pierwszych dwóch definicji predykatu kończą się porażką. W warunku logicznym trzeciej, czwartej i piątej definicji wykonywany jest test relacji elementów H1 i H2. Zauważmy, że niespełnienie testu powoduje porażkę i przejście do kolejnej definicji. Natomiast spełnienie testu powoduje przejście do wykonania operacji odcięcia, a zatem kolejne definicje predykatu na danym poziomie wnioskowania nie będą już rozważane.