W czasach gdy badacze sztucznej inteligencji zaczynali próby realizacji inteligentnych systemów, dużą popularność zyskał język programowania w logice Prolog. Z czasem okazało się, że głównym problemem jest przetwarzanie dużej ilości danych, a do tego lepiej są przystosowane inne języki programowania.

Jednak sam mechanizm wnioskowania zawarty w Prologu jest nadal atrakcyjnym rozwiązaniem. Stąd pomysły, aby zintegrować go z językami bardziej uniwersalnymi. Można wykorzystać interpreter Prologu w innym języku, albo tworzyć rozszerzenia samego Prologu w innych językach. Takie podejście komplikuje jednak tworzenie oprogramowania. W niniejszym artykule przedstawiono odmienne podejście: potraktowanie mechanizmów wnioskowania Prologu jako wzorców programowania.

Mechanizm wnioskowania

Predykaty

Predykaty to najprościej mówiąc zdania logiczne (formuły), które mogą zawierać zmienne. Na przykład: 'X ma duży nos'. Predykaty możemy też utożsamiać z komendami lub funkcjami języków programowania, które zwracają wartość logiczną (PRAWDA lub FAŁSZ). Dlatego często spotyka się zapis typowy dla funkcji: ma_duży_nos(X).

Klauzule Horna

Klauzulą nazywamy zbiór formuł logicznych, którego wartość logiczna jest równa alternatywie tych formuł. Na przykład dla klauzuli (~(n<0), ~(n>12), najwyzej_tuzin(n)) mamy alternatywę: ~(n<0) lub ~(n>12) lub najwyzej_tuzin(n), która jest prawdziwa dla liczb od 1 do 12.

Klauzula Horna zawiera najwyżej jeden element bez negacji. Nietrudno zauważyć, że taka klauzula jest równoważna implikacji z jednym następnikiem: (F0,~F1,~F2...~Fn) jest równoważne F1 ^ F2 ...^ Fn -> F0

W powyższym przykładzie mamy:

(n>0) i (n<=12) -> najwyzej_tuzin(n)

Czyli mamy regułę wnioskowania:

jeśli liczba jest większa od 0 i nie większa niż 12 to mamy spełnioną formułę mniej_niż_tuzin(n).

Warto zwrócić uwagę, że nie jest to twierdzenie matematyczne, ale właśnie reguła wnioskowania, która może zawierać jakąś wiedzę (lub być pozbawiona sensu).

Programowanie w logice

Klauzle Horna można wykorzystać zapisu reguł wnioskowaniaⁱ. Następnik implikacji można traktować jako wniosek z pozostałych formuł klauzuli. Czyli następnik implikacji odpowiada na pytanie czego szukamy, a pozostałe formuły definiują reguły poszukiwań. Można więc traktować to jako definicję klauzuli – procedury sprawdzania:

jeśli chcesz sprawdzić, czy najwyzej_tuzin(n) to sprawdź: (n>0) i (n<=12).

Taka reguła wnioskowania nazywa się regułą rezolucjiⁱⁱ:

wniosek(X) lub ~reguły(X),reguły(X)
___________________________________
               
             wniosek(X)

Czyli chcąc wykazać wniosek (najwyzej_tuzin(n)) przy założeniu, że albo wniosek jest prawdziwy, albo reguły fałszywe (nieprawda, że (n>0) i (n<=12)), wystarczy zbadać reguły. Pomimo, że ten przykład został odpowiednio dobrany, istnieją dowody, że każdy zbiór reguł logiki klasycznej da się zapisać w postaci koniunkcji klauzul Horna.

Następnik implikacji (wniosek) odpowiada nagłówkowi procedury. Dlatego nazywa się go nagłówkiem klauzuli, a zbiór pozostałych formuł klauzuli (tworzących koniunkcję) nazywamy ciałem klauzuliⁱⁱⁱ. Możemy to zapisać na przykład tak:

nagłówek(parametr) { ciało }
dla naszego przykładu:
najwyzej_tuzin(n) { (n>0), (n<=12) }

Mamy więc podstawy tworzenia języka odpowiedniego do gromadzenia wiedzy. Definiując nowe reguły, możemy używać w prosty sposób wcześniej zdefiniowanych. Jeśli na przykład chcemy zdefiniować pojemność kobiałki jabłek, możemy zapisać:

można_zmieścić(ilość, waga) { najwyzej_tuzin(ilość), (waga<=1kg) }

Fakty i baza wiedzy

Klauzulę z pustym ciałem nazywa się faktem^iv. Jest to intuicyjnie zrozumiałe, gdyż fakt nie wymaga uzasadnienia. Na przykład faktem jest: tuzin(12) {}

Baza wiedzy składa się z klauzul i faktów.

Odpowiedzi na pytania: unifikacja i nawroty

Zapytania do bazy wiedzy formułuje się w postaci reguł zawierających zmienne. Załóżmy że mamy bazę osób z zawierającą klauzulę:

dziadek(zmienna_dziadek,zmienna_wnuk)

Aby odszukać dziadka Jana Kowalskiego, możemy sformułować zapytanie:

dziadek(X, ‘Jan Kowalski’) 

Odpowiedź na takie zapytanie wiąże się z odszukaniem wszystkich możliwych wartości zmiennej X. Algorytm poszukiwań składa się z unifikacji i nawrotów.

Unifikacją nazywa się poszukiwanie takich wartości zmiennych, dla których zadany warunek (ciało klauzuli) jest spełniony. Możemy to przeanalizować przykładzie bazy wiedzy zawierającej następujące klauzule i fakty (małe pojedyncze litery oznaczają zmienną):

dziadek(x,y) { ojciec(x,z),ojciec(z,y) }
ojciec(Jan,Robert)
ojciec(Jan,Ewa)
ojciec(Robert,Zenon)
ojciec(Zenon,Tadeusz)
ojciec(Robert,Andrzej)

Jeśli zadamy zapytanie dziadek(Jan,y), to unifikacja będzie polegać na podstawieniu pod y takich wartości, aby zbiór klauzul bazy wiedzy wraz zapytaniem był spełniony^v.

Otrzymamy więc po kolei:

 
1. dziadek(Jan,y) 
2. ojciec(Jan,z),ojciec(z,y) 
3. ojciec(Jan,Robert),ojciec(Robert,y) 
4. ojciec(Jan,Robert),ojciec(Robert,Zenon) - pierwszy wynik, uzgodnienie zmiennej y = Zenon 
5. ojciec(Jan,Robert),ojciec(Robert,y) - nawrót 
6. ojciec(Jan,Robert),ojciec(Robert,Andrzej) – drugi wynik: y=Andrzej 
7. ojciec(Jan,Robert),ojciec(Robert,y) - nawrót 
8. ojciec(Jan,z),ojciec(z,y) - nawrót 
9. ojciec(Jan,Ewa),ojciec(Ewa,y) – brak możliwości pełnego uzgodnienia 
10. ojciec(Jan,z),ojciec(z,y) - nawrót 

Po uzgodnieniu wszystkich zmiennych, gdy ciało klauzuli jest spełnione – wypisujemy wynik i następuje powrót w drzewie wyszukiwań. Wykonanie programu w logice polega na sprawdzeniu całego drzewa.

Obiektowa baza wiedzy

Główną przyczyną, dla której Prolog nie zdobył popularności był dynamiczny rozwój metod obiektowych. Próby stworzenia obiektowego Prologu^vi nie zyskały powszechnego uznania.

Poniżej opisano odmienne podejście^vii: zastąpienie klauzul obiektami, które są używane do poszukiwania rozwiązań. Nawroty zaimplementowano w nim poprzez wykorzystanie generatorów (słowo kluczowe yield w Pythonie). Natomiast unifikację zmiennych umożliwia zastosowanie odpowiednich obiektów. Takie rozwiązanie może być bardzo użyteczne w systemach pozyskiwania danych z rozproszonych źródeł.

Przykład generatora w języku Python:

#!/usr/bin/env python

potomstwo = [('Jan','Robert'),('Jan','Ewa'),('Robert','Zenon'),
('Zenon','Tadeusz'),('Robert','Andrzej')]

def dziadek(dziadek):
  for o in synowie(dziadek):
    for w in synowie(o):
      yield w

def synowie(ojciec):
  for (o,s) in potomstwo:
    if (o==ojciec):
      yield s

def main():
    for d in dziadek('Jan'):
        print d

if __name__ == '__main__':
    main()

Powyższy program można uznać za implementację w Pythonie wcześniejszego przykładu z potomkami. Zapewnia on przeszukanie całego drzewa rozwiązań.

W wersji obiektowej ten przykład może wyglądać następująco:

#!/usr/bin/env python

potomstwo = [('Jan','Robert'),('Jan','Ewa'),('Robert','Zenon'),
('Zenon','Tadeusz'),('Robert','Andrzej')]

class UnifyingVariable:
  def __init__(self,value=None):
    self.value = value

  def unify(self, arg):
    if self.value <> None:
      if self.value == arg:
        return
      else:
        del self.value
    self.value = arg
    return

class Ojciec:
  def __call__(self, ojciec, syn):
    for (o,s) in potomstwo:
      if (o==ojciec.value):
        syn.unify(s)
        yield True

class Dziadek:
  def __call__(self, dziadek, wnuk):
    osoba1=UnifyingVariable()
    ojciec=Ojciec()
    for result1 in ojciec(dziadek,osoba1):
        for result2 in ojciec(osoba1,wnuk):
          yield True

def main():
    osoba=UnifyingVariable('Jan')
    wnuk=UnifyingVariable()
    dziadek=Dziadek()
    for r in dziadek(osoba,wnuk):
        print wnuk.value

if __name__ == '__main__':
    main()

Różnica polega na tym, że uzyskujemy całą moc programowania obiektowego.

Widać na tym przykładzie, że uwzględnienie wnioskowania w programach przeszukiwania danych w języku Python nie sprawia żadnych problemów, a nawet – nie wymaga pełnego zrozumienia teorii jaka się za tym kryje.

Przypisy: