Sztuczna inteligencja/SI Moduł 5 - Wnioskowanie jako metoda przeszukiwania

Wprowadzenie

Jak mieliśmy okazję przekonać się w lekcji trzeciej, PROLOG jest językiem deklaratywnym, opisującym sposób sterowania algorytmem wnioskowania. Sama zasada wnioskowania polega na zastępowaniu stwierdzeń, których prawdziwość jest poddawana weryfikacji, przez inne stwierdzenia, zgodnie z zapisanymi definicjami predykatów. Proces ten kończy się wtedy, gdy algorytm wnioskowania dojdzie do stwierdzenia prawdziwego (gdyż zapisanego jako prawdziwe), bądź wtedy, gdy nie da się dopasować żadnej reguły wnioskowania.

Spróbujmy sobie wyobrazić graficznie schemat zależności między stwierdzeniami, poddawanymi weryfikacji, regułami i faktami. Dla przykładu rozważmy najpierw predykaty kr_ko, m_ko, m_kr, m_s, opisujące relacje: 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(Berlin, Europa).
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_s(Warszawa, Polska).
m_s(Moskwa, Rosja).

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

Skonstruujmy graf skierowany w następujący sposób (patrz rysunek poniżej). Istnieją dwa wyróżnione węzły: „prawda” i „porażka”. Węzeł „prawda” jest połączony krawędziami z każdym z podanych faktów (ujętymi w pola prostokątne). Węzeł „porażka” jest połączony krawędziami z każdym stwierdzeniem, którego zmiennych nie da podstawić na wartości zgodne z żadnym faktem ani z konkluzją żadnej z reguł. Każda definicja predykatu, będąca regułą, jest połączona krawędziami ze stwierdzeniami (ujętymi w zaoblone prostokąty), które są wynikiem podstawień zmiennych z części przesłankowej reguły. W przypadku reguł, w których część przesłankowa jest koniunkcją warunków logicznych, wprowadzamy pomocniczy węzeł koniunkcyjny (ujęty w owal), w którym zapisujemy podstawienia wszystkich zmiennych pomocniczych (tj. nie występujących jako elementy konkluzji reguły). W naszym przykładzie dotyczy to definicji predykatu kr_ko, której argumentami są Kraj i Kont, zaś zmienną pomocniczą jest Miasto.

Śledzenie ścieżek prowadzących do węzłów „prawda” i „porażka” jest istotą wnioskowania. Jako prawdziwe uznaje się:

• Fakty (prostokąty), połączone bezpośrednio z węzłem prawda (jak np. w przypadku faktu m_kr(„Kraków”, „Polska”).
• Pomocnicze węzły koniunkcyjne (owale), połączone wyłącznie z prawdziwymi węzłami,
• Stwierdzenia (zaoblone prostokąty) połączone z co najmniej jednym węzłem prawdziwym.

Prześledźmy sposób wnioskowania związany z weryfikacją stwierdzenia:

kr_ko(Polska, Europa).

W tym celu naszkicujmy wszystkie połączenia wiążące się z weryfikowanym stwierdzeniem (patrz rysunek poniżej).

Tu ma być rysunek

Prawdziwość stwierdzenia kr_ko(Polska, Europa) wynika z tego, że węzeł, odpowiadający temu stwierdzeniu, łączy się z prawdziwymi węzłami, odpowiadającymi koniunkcjom:

m_kr(Warszawa, Polska), m_ko(Warszawa, Europa).
m_kr(Kraków, Polska), m_ko(Kraków, Europa).

Prawdziwość składników tych koniunkcji wynika albo znowu z wnioskowania, tak jak w przypadku stwierdzenia:

m_kr(Warszawa, Polska)

albo też z bezpośredniego połączenia ich z węzłem „prawda”; dotyczy to stwierdzeń:

m_kr(Kraków, Polska),
m_ko(Kraków, Europa),
m_ko(Warszawa, Europa)

Zauważmy, że w czasie wywodu będą sprawdzone również węzły, odpowiadające koniunkcjom:

m_kr(Irkuck, Polska), m_ko(Irkuck, Europa).
m_kr(Moskwa, Polska), m_ko(Moskwa, Europa).

przy czym co najmniej jeden z elementów każdej z powyższych koniunkcji jest bezpośrednio lub pośrednio połączony z węzłem „porażka”.

Podobne grafy połączeń można skonstruować dla każdego stwierdzenia:

m_kr(Miasto, Kraj)
m_st(Miasto, Kraj)
m_ko(Miasto, Kontynent)
kr_ko(Kraj, Kontynent)

Każdy z takich grafów jest podzbiorem grafu pełnego, który jest grafem całej przestrzeni przeszukiwań, w której prowadzone jest wnioskowanie. Tak więc wnioskowanie jest przeglądaniem przestrzeni przeszukiwań, ograniczonym do możliwie najmniejszej liczby węzłów pozwalających stwierdzić prawdziwość badanego stwierdzenia.