Opis

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.

Projekt

WSTĘP

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.

SOFTWARE VISUALIZATION

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 (Prolog Program Visualization Laboratory)
  • TPM (Transparent Prolog Machine)
  • Tools for Software Visualization – SVT (Semantic Visualization Tools) and Vmax
  • VPP (Visual Programming in Prolog)

PPVL (Prolog Program Visualization Laboratory)

PPVL jest projektem który służy do wizualizacji wiedzy Prolog-u. Łączy w sobie kilka programów do wizualizacji - SV. Są to:

  • Spy (Byrd, 1980)
  • PTP (Prolog Trace Package)
  • TPM (Transparent Prolog Machine)
  • TTT (Textual Tree Tracer)

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 (Byrd, 1980)

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:

  • call
  • exit
  • fail
  • redo

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 (Prolog Trace Package)

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 (Transparent Prolog Machine)

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 (Textual Tree Tracer)

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 (The Internet Software Visualization Laboratory)

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:

http://www-jime.open.ac.uk/97/1/java/isvl-09.html

TPM (Transparent Prolog Machine)

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:

:pl:miw:miw08_rbs_back:tpm_model.jpg

Akcja:

:pl:miw:miw08_rbs_back:tpm_action.jpg

Granulacja danych:

:pl:miw:miw08_rbs_back:tpm_gran.jpg

Podgląd ogólny widoku uruchamiania programu Prologu.

:pl:miw:miw08_rbs_back:tpm_1.jpg

Ten sam widok z bliska

:pl:miw:miw08_rbs_back:tpm_2.jpg

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.

Tools for Software Visualization – SVT (Semantic Visualization Tools) and Vmax

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:

:pl:miw:miw08_rbs_back:vmax1.jpg

Przykładowy ekran widoku klauzuli:

:pl:miw:miw08_rbs_back:vmax2.jpg

Struktura klauzuli może być vizualizowana na różne sposoby. Przedstawia to rysunek poniżej:

:pl:miw:miw08_rbs_back:vmax3.jpg

Vmax umożliwia również wizualizacji klauzul bardzo podobnie do TPM, co można zobaczyć na rysunku:

:pl:miw:miw08_rbs_back:vmax4.jpg

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.

VPP (Visual Programming in Prolog) i VPE (Visual Program Execution)

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:

  1. Visual Programming (VPP)
  2. wizualizacja uruchamiania (VPE)

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:

:pl:miw:miw08_rbs_back:vpp1.jpg

Relacja w VPP jest przedstawiana następująco:

:pl:miw:miw08_rbs_back:vpp2.jpg

Klauzula w następujący sposób:

:pl:miw:miw08_rbs_back:vpp3.jpg

Reguła następująco:

:pl:miw:miw08_rbs_back:vpp4.jpg

Natomiast rysunek poniżej przedstawia kompletny ślad uruchamiania prostego programu w VPE:

:pl:miw:miw08_rbs_back:vpp5.jpg

Poniższy rysunek pokazuje jeden ze sposobów reprezentowania list relacji w VPP i VPE:

:pl:miw:miw08_rbs_back:vpp6.jpg

Aktualnie są dwie prototypowe implementacje VPP:

  • Philip
  • Treglow

Podsumowanie

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.

Sprawozdanie

Materiały

pl/miw/miw08_rbs_back.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0