Projekt zakończony
Dawid, Zwoźniak, david_z@poczta.fm
RBS_Back Przegląd metodologii reprezentacji reguł dla wnioskowania w tył (wstecz). Należy szczególnie uwzględnić reprezentacje graficzne oraz zwrócić uwagę na: przejrzystość reguł, gęstość reprezentowanej informacji.
Ekspertowy system regułowy składa się z bazy danych, zawierającej pewne ustalone fakty i reguły służące do wywnioskowywania nowych faktów oraz interpetera reguł, sterującego procesem wnioskowań.
W systemach ekspertowych wykorzystuje się 3 rodzaje wnioskowania: - w przód - wstecz - mieszane
Wnioskowanie wstecz przebiega w odwrotną stronę niż wnioskowanie w przód. Ogólnie polega ono na wykazaniu prawdziwości hipotezy głównej na postawie prawdziwości przesłanek. Jeśli nie wiemy, czy jakaś przesłanka jest prawdziwa, to traktujemy tę przesłankę jako nową hipotezę i próbujemy ją wykazać. Jeżeli w wyniku takiego postępowania zostanie wreszcie znaleziona reguła, której wszy¬stkie przesłanki są prawdziwe, to konkluzja tej reguły jest prawdziwa. Na pod¬stawie tej konkluzji dowodzi się następną regułę, której przesłanka nie była po¬przednio znana itd. Postawiona hipoteza jest prawdziwa, jeśli wszystkie rozważa¬ne przesłanki dadzą się wykazać.
Cel → reguły → fakty
Wnioskowanie wstecz różni się od wnioskowania w przód m.in. tym, że generuje mniejszą liczbę nowych faktów oraz uniemożliwia równoczesne dowodzenie kilku hipotez. Ogólnie w typowych zastosowaniach wnioskowanie wstecz jest efektywniejsze i bardziej rozpowszechnione. Istotne jest także to, że przy wnioskowaniu wstecz czas oczekiwania na osiągnięcie rozwiązania postawionej hipotezy jest w wielu przypadkach dużo krótszy niż przy wnioskowaniu w przód.
Wnioskowanie wstecz zostało zastosowane, między innymi, w interpreterach PROLOG-u.
Celem projektu było zbadanie metodologii reprezentacji wiedzy w systemach regułowych z wnioskowaniem wstecz, a konkretnie o sposób wizualizacji wiedzy.
W projekcie skupiono się na odszukaniu projektów wizualizaji reprezentacji wiedzy w PROLOG-u.
Znaleziono następujące programy:
PPVL jest projektem który służy do wizualizacji wiedzy Prolog-u. Łączy w sobie kilka programów do wizualizacji - SV. Są to:
W środowisku PPVL każdy wymieniony wyżej SV system ma podobny interfejs i nawigacje.
Środowisko zostało stworzone w Macprolog wersji 4.5 i uruchamiane na Macintosh system 7.1
Spy, PTP i TTT zostały w pełni zaimplementowane. Natomiast TPM zostało zaimportowane i później zmodyfikowane aby umożliwić integracje z PPVL (nawigacje i zapisywanie). PPVL posiada wiele zalet nad zaimplementowanymi systemami osobno, między innymi zapewnia identyczny interfejs dla wszystkich systemów.
Spy jest krokowym, liniowym i tekstowym systemem śledzenia wykonywania programu, który używa Byrd Box model do uruchamiania programu. Model używa proceduralnej interpretacji logiki.
Początek klauzuli jest klasyfikowany jako procedura, natomiast koniec klauzuli jedną lub więcej sub procedur. Każda procedura lub sub procedura może mieć jeden z czterech stanów:
Wywołanie procedury jest klasyfikowane jako call, jeśli jest zakończone sukcesem jest kończone exit, jeśli nie to fail. Procedura ponownego próbowania lub wstecznego śledzenia jest pokazywana jako redo.
Przykładowy program:
p(X) :- q(X), r(X).
q(a).
q(b).
r(b).
:- p(What).
Spy - śledzenie wykonywania przykładowego programu:
call p(_1)
UNIFY 1 []
call q(_1)
UNIFY 1
exit q(a)
call r(a)
fail r(a)
redo q(a)
UNIFY 2
exit q(b)
call r(b)
UNIFY 1
exit r(b)
exit p(b)
PTP został stworzony przez Eisenstadt (1984) w celu zapewnienia większej ilości detali i bardziej czytelnego przeglądanie uruchamiania programów Prologu, niż w Spy. PTP obsługuje 19 różnych stanów uruchamiania (Spy tylko 4). Również wyróżnia osiągnięcie celu i klauzuli w programie, które były wykorzystywane do osiągnięcia tego celu, poprzez używanie różnych symboli dla wchodzenia i wychodzenia z klauzuli i osiągniętego celu.
PTP - reprezentacja przykładowego programu:
1: ? p(_1)
2: > p(_1) [1]
3: ? q(_1)
4: +*q(a) [1]
5: ? r(a)
6: -~r(a)
7: ^ q(a)
8: < q(a) [1]
9: +*q(b) [2]
10: ? r(b)
11: +*r(b) [1]
12: + p(b) [1]
TPM wykorzystuje AND/OR model drzewa dla wykonywania programu Prologu. Został stworzony przez Eisenstadt and Brayshaw, 1988; Brayshaw and Eisenstadt, 1991. Opis TPM jest przedstawiony jako osobne narzędzie do wizualizacji.
TTT ma zasadniczo podobny model jak TPM, jednak używa tekstowej reprezentacji drzewa prez co dostarcza pojedynczego widoku uruchamiania programu. Został stworzony przez Taylor et al, 1991.
W przeciwieństwie do liniowych tekstowych programów śledzących wykonywanie programu takich jak Spy i PTP, bieżąca informacja określająca związek z poprzednio osiągniętym celem jest wyświetlana z lub nad poprzednią informacją. To utrzymuje wszystkie powiązane informacje poszczególnych celów w jednym miejscu.
Siedem symboli relacji klauzul jest zaimplementowanych. Zmienne powiązane z historią celu są wyświetlane bezpośrednio pod nim.
TTT- reprezentacja przykładowego programu:
»>1: p(What) 1S
|1 What = b
*2: q(What) 1SF/2S
|1 What ≠ a
|2 What = b
*3: r(a) Fm
***4: r(b) 1S
ISVL jest projektem, który miał na celu pomoc studentom w rozumieniu uruchamianych programów napisanych w Prolog-u, poprzez internet. Projekt ten wywiązał się jakby z PPVL, jednak zaimplementowano w nim jedynie TPM.
Demonstracje działania ISVL można zobaczyc na stronie:
TPM jest narzędziem do wizualizacji i animacji uruchamianych programów napisanych w Prologu. Stworzony zarówno dla początkujących jak i zaawansowanych programistów Prologu, zapewnia wierną reprezentację (w zwolnionym tempie) działania wewnętrznego interpretera Prologu, jak również umożliwia wysokiej prędkości wizualny podgląd uruchamianego programu.
Bieżące wersje umożliwiają używanie: textbook diagrams, animacji video oraz implementacji graficznych stacji roboczych.
System dodatkowo umożliwia tworzenie użytkownikowi widoków śledzonych programów .
Model:
Akcja:
Granulacja danych:
Podgląd ogólny widoku uruchamiania programu Prologu.
Ten sam widok z bliska
Projekt powstawal w latach 1983-1988 w Open University and Expert Systems Ltd. TPM jest dostepny jako komercyjny produkt (Expert Systems Ltd.) uruchamiany na graficznych stacjach roboczych systemu UNIX. Powstała również wersja uczelniana na platforme Mac.
System SVT dostarcza strukturę dla SV (Software Visualization) nazywana Vmax. Kod źródłowy i uruchamiane dane są analizowane w tym systemie poprzez język Prolog, co zapewnia dostęp do informacji o strukturze programu i uruchomionych w nim danych w szerokim zakresie połączonych widoków. Środowisko SVT oraz widok programu użytkownika został napisany w Javie.
SVT jest potężnym narzędziem który umożliwia wizualizację programów napisanych w różnych językach oraz wszelkiego typu diagramów.
Skupiono się jednak na możliwościach SVT do wizualizaji wiedzy i programów w Prolog-u.
Vmax może wyświetlać i edytować programy Prolog-u jako wizualne języki (visual languages). To pokazuje potencjalne możliwości SVT dla visual programming.
Klauzula Prologu w SVT wygląda następująco:
user_clause(ClauseId, Clause)
gdzie ClauseId jest niepowtarzalnym identyfikatorem klauzuli, a Clause jest struktura klauzuli.
Aktualnie nie ma zewnętrznej tekstowej reprezentacji Prologu.
Klauzule które zdefiniuje użytkownik mogą być przeglądane.
Przykładowy ekran widoku predykatów:
Przykładowy ekran widoku klauzuli:
Struktura klauzuli może być vizualizowana na różne sposoby. Przedstawia to rysunek poniżej:
Vmax umożliwia również wizualizacji klauzul bardzo podobnie do TPM, co można zobaczyć na rysunku:
Vmax daje możliwość edycji klauzul na różne sposoby zarówno tekstowo jak i graficznie. Jednak zmiany w trybie graficznym nie są zapisywane do kodu źródłowego, dlatego jest to mało użyteczne. Lepszym rozwiązaniem w tym przypadku jest edycja kodu źródła programu.
Komputerowe środowisko jakim jest VPP zostało stworzone aby wspomagać programowanie w Prolog-u przy wykorzystaniu graficznego interfejsu, który jest czytelniejszy dla początkujących programistów.
Visual Programming to dwie różne eksperymentalne implementacje:
W źródłach do jakich można dotrzeć VPE jest opisywane jeszcze w fazie konstrukcji. Działa na podobnej zasadzie jak TPM, jednak w przeciwieństwie do TPM ma dopełniający system VPP (który używa w zasadzie tych samych formalizmów) w celu zapewnienia pełną funkcjonalność dla visual programming. Zależności są bardziej wyeksponowane w VPE niż w TPM.
Wyidealizowany widok środowiska VPP dla visual programming przedstawia rysunek poniżej:
Relacja w VPP jest przedstawiana następująco:
Klauzula w następujący sposób:
Reguła następująco:
Natomiast rysunek poniżej przedstawia kompletny ślad uruchamiania prostego programu w VPE:
Poniższy rysunek pokazuje jeden ze sposobów reprezentowania list relacji w VPP i VPE:
Aktualnie są dwie prototypowe implementacje VPP:
Próby wizualizacji programów napisanych w Prologu były tworzone juz na początku lat 80-tych. Powstało kilka projektów/systemów, które dają możliwość wizualizacji i śledzenia wykonywania programów Prologu, jednak nie można żadnego z nich zdobyć. Są to albo wersje komercyjne (TPM na UNIX-a, SVT i Vmax) lub akademickie na system MAC (TPM, PPVL, ale tez nie udało się ich odnaleźć na sieci).
Większość z tych systemów podczas graficznej wizualizacji korzysta ciągle z tego samego, czyli TPM, a nie udało się odnaleźć bardziej szczegółowego opisu działania. Wydana została książka o TPM (koszt 150$ + przesyłka) a wszystkie inne informacje na sieci są bardzo pobieżne i piszą ciągle o tym samym (w skrócie jak to ladnie sobie można robić wizualizacje śledzenia programów w Prolog-u przy pomocy TPM).
Projekt niestety nie jest oparty na własnych próbach wykonywania programów z powodu braku dostępu do systemów SV dla Prologu. Zatem zostały opisane i przetłumaczone informacje jakie udało mi się odnaleźć w sieci.
Opisanie tych programów było bardzo trudne. Ciężko pisać o czymś czego nie można wypróbować opierając sie tylko na bardzo ogólnych opisach.
:pl:miw:miw08_rbs_back:005.pdf
:pl:miw:miw08_rbs_back:declarative-debugging-with-the.pdf
:pl:miw:miw08_rbs_back:domingue-97-1.pdf
:pl:miw:miw08_rbs_back:iee_20vis_20prolog_2091.pdf
:pl:miw:miw08_rbs_back:mulholland97incorporating.pdf
:pl:miw:miw08_rbs_back:ppigvisprologfixed.pdf
:pl:miw:miw08_rbs_back:tbpa91.pdf
:pl:miw:miw08_rbs_back:ucam-cl-tr-511.pdf
:pl:miw:miw08_rbs_back:visandor-iclp93.pdf
http://kmi.open.ac.uk/kmi-misc/tpm/tpm.html
http://www.amazon.com/Transparent-Prolog-Machine-Visualizing-Programs/dp/0792314476
http://www.cc.gatech.edu/classes/cs7390_98_winter/talks/logic/topic3.html
