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

From Studia Informatyczne

Spis treści

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_st, 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_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).

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).

Grafika:SI M5 01.png

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.

Sposoby wnioskowania

Graf wnioskowania jest grafem skierowanym, gdyż reguły wnioskowania mają wyróżnioną część przesłankową i konkluzję. Przeszukiwanie grafu, jako realizacja procesu wnioskowania, może być prowadzone na dwa sposoby – zgodnie lub przeciwnie do kierunku wskazywanego przez strzałki.

Wnioskowanie wstecz

Przyjęcie kierunku przeciwnego do strzałek oznacza, że wnioskowaniem kieruje stwierdzenie do weryfikacji. To stwierdzenie jest zastępowane przez wiele innych, tak, aby w końcu dojść do jednego z dwóch węzłów terminalnych – „prawda” albo „porażka”. Taki sposób postępowania jest wykorzystywany w maszynie wnioskującej PROLOGu i jest nazywany wnioskowaniem regresywnym (inaczej: wnioskowaniem sterowanym celem, albo wnioskowaniem wstecz).

Algorytm weryfikacji wstecz

Argument: stwierdzenie S\,
Dla każdej definicji D\, predykatu unifikującej się ze stwierdzeniem
Jeśli D\, jest faktem
zwróć wartość „prawda”
Jeśli D\, jest regułą
powtarzaj
Wybierz stwierdzenie S_i\, będące składnikiem części przesłankowej
Wykonaj unifikacje zmiennych pomocniczych
Wykonaj weryfikację wstecz (S_i\,)
dopóki są niezweryfikowane stwierdzenia S_i\,
Jeśli wszystkie S_i\, są prawdziwe
zwróć wartość „prawda”
w przeciwnym przypadku
zwróć wartość „porażka”

Wnioskowanie w przód

Jednak można sobie wyobrazić inną metodę postępowania: posuwać się od węzła „prawda” w kierunku strzałek, generując nowe prawdziwe stwierdzenia, w nadziei wygenerowania tego stwierdzenia, które podlega weryfikacji. Ten sposób postępowania nosi nazwę wnioskowania progresywnego (inaczej: wnioskowania sterowanego danymi albo wnioskowania w przód).

Algorytm weryfikacji w przód

Argument: stwierdzenie S\,
Lista faktów F = \emptyset
Dopóki S\, nie unifikuje się z żadnym faktem z F\, powtarzaj
Zbiór definicji predykatu D = \emptyset
Dla każdej definicji D_i\,
Jeśli D_i\, jest faktem lub
D_i\, jest regułą i część przesłankowa unifikuje się z faktami z F\,
D = D \cup \{D_i\}
Wybierz definicję D_i\, ze zbioru D\,
Jeśli D_i\, jest faktem
F = F \cup \{D_i\}
Jeśli D_i\, jest regułą
F_d\, = zbiór podstawień konkluzji reguły D_i\,
F = F + F_d\,

Sterowanie wnioskowaniem

Przegląd grafu wnioskowania musi się z konieczności odbywać w sposób sekwencyjny, a zatem algorytm wnioskujący będzie wykonywać weryfikację stwierdzeń w ustalonym porządku. Stąd konieczność dokonywania pewnych wyborów w każdym z wymienionych wyżej algorytmów - konieczność sterowania wnioskowaniem. Sterowanie wnioskowaniem ma kluczowe znaczenie z punktu widzenia efektywności procesu przeszukiwania - nie trzeba chyba przekonywać, że im mniejsza liczba odwiedzanych węzłów grafu wnioskowania, tym szybszy proces wnioskowania.

Sterowanie wnioskowaniem wstecz

W przypadku wnioskowania wstecz, wybór dotyczy kolejności rozważania alternatywnych definicji predykatu, a także kolejności analizowania składników przesłanki reguły. Ta pierwsza decyzja ma wpływ na szybkość poruszania się w głąb grafu wnioskowania, co może przyspieszyć moment pierwszego dojścia do węzła „prawda” (a niekiedy zależy nam nie na wszystkich, lecz na jakimkolwiek sposobie udowodnienia prawdziwości stwierdzenia). Druga decyzja z kolei rzutuje na kolejność unifikacji zmiennych pomocniczych, a zatem na „szerokość” zbioru węzłów będących alternatywnymi unifikacjami. Przykładowo, w definicji predykatu kr_ko(Kraj, Kont) przyjęliśmy następującą kolejność rozważania składników części przesłankowej:

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

Powoduje to, że w trakcie wnioskowania wykonana będzie najpierw próba unifikacji predykatu m_kr, a później m_ko. W efekcie, będzie 5 prób unifikacji m_kr i tylko dwie (Warszawa, Kraków) próby unifikacji m_ko (zresztą udane). Przy odwrotnej definicji predykatu:

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

mielibyśmy 5 prób unifikacji m_ko (w tym cztery udane) i cztery próby unifikacji m_kr. Tak więc umiejętnie sterując wnioskowaniem można ograniczyć pracochłonność tego procesu.

W PROLOGu, decyzje dotyczące kolejności rozważania definicji i kolejności rozważania składników koniunkcji przypadają w udziale programiście, gdyż maszyna wnioskująca dokonuje analizy w kolejności zapisanej w programie: od lewej do prawej, od góry do dołu. Można sobie jednak wyobrazić nieco bardziej zaawansowaną maszynę wnioskującą, która dokonywałaby tego wyboru w sposób automatyczny. Przykładowo, można w procesie oceny stwierdzeń części przesłankowej jako pierwsze wybierać te, których zmienne pomocnicze mają najmniej pomyślnych unifikacji.

Sterowanie wnioskowaniem w przód

W przypadku wnioskowania w przód, kluczową decyzją z punktu widzenia efektywności algorytmu jest wybór definicji predykatu do zastosowania. Ze względu na fakt, że przed pomyślnym zakończeniem wnioskowania nie jesteśmy w stanie określić, która definicja jest na którym etapie najlepsza, stosować można rozmaite zdroworozsądkowe zasady postępowania, takie jak stosowanie definicji najrzadziej dotychczas wykorzystywanej, definicji najbardziej ogólnej (o możliwie największej liczbie podstawień zmiennych), najbardziej szczegółowej itp. Podobnymi kryteriami można się kierować również przy wyborze definicji we wnioskowaniu wstecz.

Sterowanie wyborem reguł musi być wykonywane z duża ostrożnością, gdyż przy niefortunnych zasadach sterowania, łatwo o wejście w nieskończoną ścieżkę wnioskowania. Wbrew pozorom nie jest to sytuacja trudno wyobrażalna – wystarczy rozważyć predykat member zdefiniowany następująco:

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

Weryfikacja prawdziwości stwierdzenia w PROLOGu:

member("a",L).

spowoduje generację w nieskończoność coraz to dłuższej listy.

Wybór metody wnioskowania

Jeśli mamy do wyboru dwa schematy wnioskowania - wstecz i w przód - który z nich powinien być wybrany? Odpowiedź na to pytanie powinna być oparta na przewidywaniu co do wielkości stopnia rozgałęziania grafu wnioskowania w kierunku, w którym następuje wnioskowanie. Przez stopień rozgałęziania będziemy rozumieć średnią liczbę krawędzi, wychodzących z węzła w kierunku wykorzystywanym w schemacie wnioskowania (tj. zgodnie z kierunkiem wynikania reguł w przypadku wnioskowania w przód, a przeciwnie do tego kierunku w schemacie wnioskowania wstecz). Jeśli odległość (rozumiana jako najkrótsza liczba strzałek do przejścia) między prawdziwym stwierdzeniem a węzłem „prawda” wynosi n\,, zaś stopień rozgałęzienia wynosi a\,, wówczas przy odpowiednim sposobie sterowania wnioskowaniem zostanie wykonana weryfikacja a^n\, stwierdzeń. Mogąc zatem wybierać kierunek wnioskowania, wybierzemy ten o mniejszym stopniu rozgałęziania, co poskutkuje krótszym czasem wnioskowania.

Rozwiązywanie problemów przez przeszukiwanie przestrzeni

Wnioskowanie nie jest jedynym i na pewno nie najprostszym przykładem zastosowania przeszukiwania do rozwiązywania problemów. Obecnie zajmiemy się zagadnieniem przeszukiwania przestrzeni odrywając się od specyfiki tej przestrzeni, podyktowanej przez specyfikę rozwiązywanego zadania. Zadanie to sprowadza się w swej ogólnej postaci do pełnego przeglądu przestrzeni – odwiedzenia wszystkich węzłów.

Schemat przeszukiwania przestrzeni zapiszemy w postaci podstawowego algorytmu przeszukiwania, którego warianty, związane z pewnymi właściwości przestrzeni przeszukiwań, będziemy rozważać w tym i kolejnym rozdziale.

Algorytm przeszukiwania przestrzeni przetwarza zbiór węzłów do odwiedzenia A_t\,, zbiór węzłów odwiedzonych V_t\, i bieżący węzeł s_t\,. Zasada działania jest prosta. Algorytm rozpoczyna pracę od wyróżnionego węzła s_0\,. Węzeł ten staje się węzłem odwiedzonym, zaś wszystkie węzły z jego sąsiedztwa są dodawane do zbioru V_t\,. Rozpoczyna się dalej pętla główna, w której wykonywane są następujące czynności. Ze zbioru A_t\, jest wybierany kolejny węzeł i jest od dodawany do zbioru odwiedzonych V_t\,. Wszystkie węzły z jego sąsiedztwa, które nie były jeszcze odwiedzone, są dodawane do zbioru A_t\,. Pętla jest wykonywana do osiągnięcia kryterium zatrzymania, którym może być np. opróżnienie zbioru A_t\, bądź też znalezienie węzła s_t\, o szczególnych, interesujących nas właściwościach.

Algorytm przeszukiwania przestrzeni

t = 0\,
V_0 = \{s_0\}\,
A_t = N(s_0)\,
Powtarzaj
Wybierz s_{t+1}\, z A_t\,
V_{t+1} = V_t \cup \{s_{t+1}\}\,
A_{t+1} = A_t \cup N(s_{t+1}) - V_t\,
t = t + 1\,
Dopóki niespełniony warunek zatrzymania

W praktycznych realizacjach algorytmu przeszukiwania zbiór A_t\, jest realizowany jako kolejka. Wybór węzła z kolejki A_t\, może być dokonywany na podstawie kolejności dodawania – wówczas uzyskuje się ślepe strategie przeszukiwania – bądź też wybór ten jest wykonywany na podstawie dodatkowych właściwości węzła – prowadzi to do tzw. poinformowanych strategii przeszukiwania (tzw. strategie „najpierw najlepszy” – best first). W ramach ślepych strategii przeszukiwania, wybór węzła s_t\, z kolejki A_t\, oraz dodawanie nowych węzłów może być wykonywane według reguły rządzącej kolejką LIFO albo FIFO. Uzyskuje się odmienny sposób sterowania przeszukiwaniem, prowadzący do dwóch różnych realizacji algorytmu: przeszukiwania w głąb i wszerz.

Ślepe strategie przeszukiwania

Ślepymi strategiami przeszukiwania nazywane są takie sposoby sterowania przeszukiwaniem, w których zbiór A_t jest uporządkowany w kolejności określonej sekwencją dodawania do niego kolejnych elementów.

Strategia w głąb

W strategii „w głąb”, zbiór A_t\, jest reprezentowany jako kolejka LIFO. Oznacza to, że po wyborze węzła s_t\, i usunięciu go z kolejki A_t\,, elementy z sąsiedztwa N(s_t)\, wchodzą niejako „na miejsce” s_t\, (patrz rysunek). W konsekwencji, węzeł ostatnio dodany do listy będzie pierwszym z niej wybranym.

Grafika:SI M5 02.png

Strategia wszerz

Z kolei w strategii „wszerz”, zbiór A_t\, jest kolejką FIFO. Po wybraniu węzła s_t\, i usunięciu go z kolejki A_t\,, elementy z sąsiedztwa N(s_t)\, są wstawiane na koniec kolejki. Powoduje to, że kolejnym rozważanym węzłem będzie ten, który był najdawniej dodany (a zatem był dodany bezpośrednio po s_t\,).

Grafika:SI M5 03.png

Dyskusja

Jeśli celem przeszukiwania jest odnalezienie docelowego węzła o pożądanych cechach, wówczas strategia w głąb ma szanse znaleźć ten węzeł szybciej niż metoda wszerz. Jeśli w przestrzeni przeszukiwań istnieją ścieżki nieskończonej długości, nie można zagwarantować, że strategia w głąb nie „pójdzie” taką właśnie ścieżką.

Natomiast jeśli celem przeszukiwania jest znalezienie najkrótszej ścieżki, łączącej węzeł początkowy z docelowym, wówczas stosując strategię wszerz mamy gwarancję jej wyznaczenia. Unikamy w ten sposób ryzyka ścieżki nieskończonej.

Przykład

Jako ilustrację sposobu działania strategii wszerz i w głąb, rozważmy następujący prosty przykład. Załóżmy, że zamierzamy odnaleźć drogę w labiryncie, prowadzącą z kratki A do kratki B. Każda kratka ma co najwyżej czterech sąsiadów (brak sąsiada jest zaznaczony grubą linią – „ścianą” labiryntu).

Grafika:SI M5 04.png

Tak więc kratki labiryntu będą węzłami przestrzeni przeszukiwań.

Poszukiwanie wyjścia polega na tym, że wpisujemy do kratek numery iteracji, w których były one węzłem rozwijanym przez algorytm przeszukiwania. Po odnalezieniu rozwiązania drogę będziemy odtwarzać, idąc od węzła B do węzła A w kierunku sąsiedniej kratki o najmniejszym numerze.

Załóżmy, że obie metody przeszukiwania rozważają kratki sąsiadujące w kolejności: góra, lewo, dół, prawo. Dostajemy wówczas dla obu metod kolejność odwiedzania kratek labiryntu jak na poniższych rysunkach.

Metoda w głąb

Grafika:r5x05.png

Metoda wszerz

Grafika:r5x06.png

Zauważmy skutki efektu odwrócenia kolejności rozważania węzłów sąsiedztwa wynikającego z działania kolejki LIFO. Widać także, że pierwsza ścieżka, znaleziona przez algorytm przeszukiwania w głąb, nie jest ścieżką najkrótszą. Z drugiej jednak strony, w tym akurat zadaniu metoda wszerz wymaga odwiedzenia wszystkich pól labiryntu, aby znaleźć pierwsze (i zarazem najlepsze) rozwiązanie.