Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /var/www/galicea/logic/plugins/system/t3/includes/menu/megamenu.php on line 141

Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /var/www/galicea/logic/libraries/f0f/dispatcher/dispatcher.php on line 524

Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /var/www/galicea/logic/libraries/f0f/dispatcher/dispatcher.php on line 529

Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /var/www/galicea/logic/libraries/f0f/dispatcher/dispatcher.php on line 534

Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /var/www/galicea/logic/libraries/f0f/dispatcher/dispatcher.php on line 539

Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /var/www/galicea/logic/libraries/f0f/dispatcher/dispatcher.php on line 552

Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /var/www/galicea/logic/libraries/f0f/dispatcher/dispatcher.php on line 561

Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /var/www/galicea/logic/libraries/f0f/dispatcher/dispatcher.php on line 566

Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /var/www/galicea/logic/libraries/f0f/dispatcher/dispatcher.php on line 580

Warning: "continue" targeting switch is equivalent to "break". Did you mean to use "continue 2"? in /var/www/galicea/logic/libraries/f0f/dispatcher/dispatcher.php on line 609
Mechanizm wnioskowania w systemach przetwarzania danych

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ł wnioskowaniai. 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łą rezolucjiii:

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 klauzuliiii. 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ę faktemiv. 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łnionyv.

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 Prologuvi nie zyskały powszechnego uznania.

Poniżej opisano odmienne podejścievii: 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:

iv) j.w.

v) Nie każdy zbiór klauzul jest umożliwia unifikację. Zobacz przykłady w: http://sequoia.ict.pwr.wroc.pl/~witold/ai/ai_logic_s.pdf

vi) Na przykład Prolog++ czy SCOOP (Structured Concurrent Object-Oriented Prolog). Zobacz http://www.academia.edu/4148314/SCOOP_Structured_Concurrent_Object-Oriented_Prolog

vii) Podobne rozwiązania zastosowano w projekcie Yield Prolog, który pozwala na integrację z Pythonem, JavaScript lub C#