Krótki przewodnik po języku Common Lisp stanowi oddzielny tekst, który zawiera informacje nie tylko ułatwiające posługiwanie się dostarczonym oprogramowaniem, lecz także umożliwiające dokonywanie w nim prostych modyfikacji, nawet bez uprzedniej znajomości tego języka. Jednak używanie programów w podstawowym zakresie, jaki jest omawiany w niniejszej dyskusji, nie wymaga nawet powierzchownej wiedzy o języku Lisp. Niezbędna jest natomiast podstawowa orientacja w specyfice środowiska tego języka pozwalająca na ładowanie kodu programu i jego uruchamianie oraz śledzenie jego działania.
Język Lisp jest językiem interpretowanym. Dowolny program -- w postaci źródłowej lub przetłumaczonej do binarnej reprezentacji wewnętrznej -- jest interpretowany przez specjalny program, który zapewnia to, co nazywamy środowiskiem języka Lisp. Jedną z jego podstawowych cech jest interaktywność: użytkownik wydaje mu polecenia ładowania plików zawierających kod programu i uruchamiania funkcji, lecz może także sprawdzać i zmieniać wartości zmiennych, modyfikować i definiować nowe funkcje oraz obliczać dowolne wyrażenia języka. Ma to duży walor zwłaszcza w przypadku oprogramowania o charakterze raczej badawczym lub dydaktycznym niż użytkowym, kiedy łatwość wprowadzania niewielkich zmian jest cenna.
Środowisko zgłasza gotowość przyjęcia poleceń użytkownika przez wypisanie tekstu zachęty, który często ma postać znaku > -- tak będziemy przyjmować w poniższych przykładach. Wówczas użytkownik może wpisać dowolne poprawne wyrażenie w języku Lisp, czy też -- jak przyjmuje się je nazywać -- formę. Najbardziej podstawowe rodzaje form, którymi można się łatwo posługiwać bez znajomości języka, to zmienne oraz wywołania funkcji. Wartością formy będącej zmienną jest aktualna wartość tej zmiennej. Wartością formy będącej wywołaniem funkcji jest wartośc zwrócona przez tę funkcję wywołaną dla podanych argumentów. W każdym przypadku wpisanie formy po znaku zachęty i wciśnięcie klawisza Enter powoduje wyznaczanie jej wartości (czyli wartościowanie), która następnie jest wypisywana, po czym środowisko oczekuje na podanie kolejnej formy.
Forma wyznaczająca wartość zmiennej zapisywana jest po prostu jako nazwa tej zmiennej. Forma wywołania funkcji zapisywana jest w postaci (fun arg1 arg2 ... argn), gdzie fun oznacza nazwę funkcji, a arg1, arg2,..., argn są jej argumentami. Poniższy przykład demonstruje sprawdzanie wartości zmiennych pogoda-atrybuty i pogoda-kategorie, przy założeniu, że zostały one wcześniej zdefiniowane:
> pogoda-atrybuty ((AURA (SLONECZNA POCHMURNA DESZCZOWA)) (TEMPERATURA (ZIMNA UMIARKOWANA CIEPLA)) (WILGOTNOSC (NORMALNA WYSOKA)) (WIATR (SLABY SILNY)) ) > pogoda-kategorie (1 0)Z kolei następujący przykład pokazuje, jak wywołać funkcję o nazwie learn z jednym argumentem pogoda-przyklady, przy założeniu, że funkcja learn i zmienna pogoda-przyklady zostały wcześniej zdefiniowane:
> (learn pogoda-przyklady)
< AURA >
=SLONECZNA
< WILGOTNOSC >
=NORMALNA
[TAK]
=WYSOKA
[NIE]
=POCHMURNA
[TAK]
=DESZCZOWA
< WIATR >
=SLABY
[TAK]
=SILNY
[NIE]
Do ładowania plików do środowiska służy funkcja load, której argumentem jest ujęta w cudzysłowy nazwa pliku. W niektórych środowiskach można podając nazwę pominąć domyślny przyrostek .lsp lub .lisp. Ładowany plik musi zawierać poprawne formy języka Lisp. W trakcie ładowania są one interpretowane i wartościowane. W przypadku, gdy plik zawiera kod programu, są to przede wszystkim definicje funkcji i definicje zmiennych. W trakcie ładowania pliku mogą pojawiac się komunikaty towarzyszące wartościowaniu znajdującym się w nim form. Może też nastąpić ładowanie innych plików, jeśli ładowany plik tego wymaga. Poniższy przykład demonstruje ładowanie jednego z plików źródłowych dostarczonego oprogramowania:
> (load "tdidt") ;; Loading file /home/pawel/src/lisp/tdidt.lsp ... ;; Loading file /home/pawel/src/lisp/concept.lsp ... ;; Loading file /home/pawel/src/lisp/util.lsp ... ;; Loading of file /home/pawel/src/lisp/util.lsp is finished. ;; Loading of file /home/pawel/src/lisp/concept.lsp is finished. ;; Loading file /home/pawel/src/lisp/info.lsp ... ;; Loading of file /home/pawel/src/lisp/info.lsp is finished. ;; Loading of file /home/pawel/src/lisp/tdidt.lsp is finished. T
W przypadku przeprowadzania czasochłonnych obliczeń warto ładować pliki źródłowe w postaci skompilowanej do specjalnej wewnętrznej postaci binarnej (specyficznej dla konkretnych środowisk), co może przyspieszyć wykonanie o kilka lub nawet kilkanaście razy. Do przeprowadzania kompilacji służy funkcja compile-file, której argumentem jest nazwa pliku w cudzysłowach. Następnie wywołując funkcję load należy jej podać nazwę pliku, który powstanie w wyniku kompilacji. Jest ona tworzona przez dodanie do nazwy oryginalnej przyrostka zależnego od konkretnego środowiska.
Można również spowodować kompilowanie plików źródłowych na bieżąco w trakcie ładowania dostarczając funkcji load dodatkowy specjalny argument kluczowy :compiling z wartością t (logiczna prawda), tak jak w poniższym przykładzie:
> (load "cover" :compiling t) ;; Loading file /home/pawel/src/lisp/cover.lsp ... ;; Loading of file /home/pawel/src/lisp/cover.lsp is finished. T
Jeśli nazwa pliku nie zawiera ścieżki dostępu, jest on poszukiwany w katalogu bieżącym lub zależnym od parametrów danego środowiska katalogu domyślnym. Zazwyczaj środowiska pozwalają na zmianę katalogu bieżącego, lecz służąca do tego funkcja nie jest objęta standardem języka. W przypadku środowiska CLISP jest to funkcja cd, która jako argument przyjmuje nazwę katalogu ujętą w cudzysłowy.
Kod źródłowy dostarczonego oprogramowania znajduje się w plikach odpowiadających pakietom języka Lisp. Każdy pakiet stanowi pewien zbiór zdefiniowanych symboli, przede wszystkim funkcji i zmiennych, które dzielą się na publiczne (dostępne dla innych pakietów) i prywatne. Podział na logicznie odrębne pakiety służy bardziej przejrzystej organizacji kodu źródłowego i czytelnego wyrażenia występujących w nim zależności. Jest to możliwe dzięki jawnemu deklarowaniu, które funkcje każdego pakietu są dostępne na zewnątrz oraz jakie inne pakiety są w nim wykorzystywane.
Pliki źródłowe składające się na udostępnione oprogramowanie są szczegółowo omówione dalej. Obecnie musimy wiedzieć, że aby było możliwe korzystanie z funkcji zdefiniowanych w którymkolwiek z tych plików, musi on zostać najpierw załadowany. W przypadku, gdy w ładowanym pliku korzysta się z funkcji zdefiniowanych w innych plikach, zostaną one także załadowane automatycznie. Również dane dla algorytmów indukcyjnego uczenia się umieszczono w plikach mających postać plików źródłowych języka Lisp. Pliki te zawierają definicje zmiennych przechowujących opisy atrybutów, kategorii oraz przykładów. Postać tych opisów będzie przedstawiona dalej. Obecnie wystyarczy zaznaczyć, że korzystanie z któregokolwiek z dostarczoncyh zbiorów danych możliwe jest po uprzednim załadowaniu zawierającego go pliku źródłowego.
Używanie programów w języku Lisp sprowadza się zazwyczaj do uruchamiania wybranych funkcji, które składają się na te programy. W dalszym opisie znajdują się szczegółowe informacje na temat tego, które funkcje i w jaki sposób należy wywołać w celu eksperymentowania z zaimplementowanymi algorytmami uczenia się. W każdym przypadku wywołanie ma podaną wyżej postać ujętej w nawiasy nazwy funkcji i jej argumentów oddzielonych dowolnymi białymi znakami (odstępu, tabulacji lub nowegi wiersza). Należy przy tym zapewnić, że definicja wywoływanej funkcji jest dostępna, a więc odpowiedni plik źródłowy został załadowany, a związany z nim pakiet jest aktualnie używany lub jego nazwa występuje w przedrostku kwalifikującym nazwę funkcji. Przedrostek kwalifikacyjny składa się z nazwy pakietu i znaku :, np. kwalifikowaną nazwą funkcji learn z pakietu "TDIDT" jest tdidt:learn. Aby jego podawanie nie było konieczne, należy zadeklarować używanie pakietu korzystając z funkcji use-package, której argumentem jest nazwa pakietu zapisana w cudzysłowiu wielkimi literami, tak jak w poniższym przykładzie:
> (use-package "TDIDT") T
Zadeklarowanie używania pakietu lub poprzedzenie nazwy przedrostkiem kwalifiuacyjnym o podanej postaci pozwala na dostęp tylko do publicznych funkcji pakietu (i w ogólnym przypadku dowolnych symboli), czyli tych, które pakiet eksportuje. Używanie innych, niepublicznych funkcji i symboli pakietów, nie powinno być na ogół konieczne w celach innych niż diagnostyczne. W każdym jednak razie jest to możliwe przez użycie przedrostka kwalifikującego z dwoma znakami : zamiast jednego.
Zagadnienia dostępności poszczególnych symboli pakietów będą wyjaśnione na konkretnych przykładach w trakcie omawiania sposobu używania najważniejszych funkcji.
Dzięki interaktywności środowiska języka Lisp możliwe jest łatwe śledzenie procesu wykonywania programów. Dzięki temu dostarczone implementacje algorytmów uczenia się pozwalają nie tylko na przeprowadzanie z nimi eksperymentów, lecz również na obserwowanie "od środka" ich działania i przez to ich lepsze zrozumienie. Śledzenie polega na drukowaniu przez środowisko komunikatów diagnostycznych podających wszystkie wywołania wybranych do śledzenia funkcji wraz z ich argumentami oraz wartościami zwracanymi. Żądanie śledzenia funkcji zgłaszane jest za pomocą funkcji trace, której jako argumenty przekazuje się nazwę jednej lub nazwy większej liczby funkcji do śledzenia, tak jak w poniższym przykładzie:
(trace cover::complex-generate-aq cover::star-generate-aq) ;; Tracing function COVER::COMPLEX-GENERATE-AQ. ;; Tracing function COVER::STAR-GENERATE-AQ. (COVER::COMPLEX-GENERATE-AQ COVER::STAR-GENERATE-AQ)Śledzone funkcje są prywatnymi funkcjami pakietu "COVER", stąd przy ich nazwach występuje odpowiedni przedrostek kwalifikujący.
Każde wywołanie funkcji, które nastapi po zgłoszeniu żądania jej śledzenia, spowoduje wypisanie odpowiedniego komunikatu diagnostycznego, o postaci zależnej od konkretnego środowiska. W celu zaprzestania śledzenia funkcji należy wywołać funkcję untrace, przekazując jej jako argumenty nazwy funkcji, których śledzenie ma zostać zakończone. Wywołanie tej funkcji bez argumentów powoduje zaprzestanie śledzenia wszystkich dotąd śledzonych funkcji.
Przebieg sesji ze środowiskiem języka Lisp, a więc wszystkie wpisywane przez użytkownika formy i drukowane przez środowisko wyniki, można zachować w pliku w celu późniejszej analizy. Służy do tego funkcja dribble, której jako argument dostarcza się nazwę pliku (jak zwykle w cudzysłowach), w którym ma być zapisany przebnieg sesji. Zapisywanmie kontynuowane jest do zakończenia działania środowiska lub następnego wywołania tej funkcji bez argumentu.
Jak widać, zdecydowana większość dostarczanego kodu implementuje podstawowe algorytmy uczenia się pojęć wraz z różnymi operacjami pomocniczymi. Nie dotyczy to tylko pliku automata.lsp.
Dla wygody i przejrzystości każdy z wymienionych plików źródłowych jednoznacznie związany jest z pakietem języka Lisp o takiej samej nazwie (bez przyrostka .lsp). Pakiety mają określony zestaw publicznych (dostępnych w innych pakietach) definicji funkcji i w niektórych przypadkach zmiennych. Te publiczne interfejsy pakietów zostaną omówione w końcowej części tego opisu. Po informacje o niepublicznych definicjach znajdujących się w poszczególnych pakietach można sięgnąć bezpośrednio do odpowiednich plików źródłowych.
Używanie funkcji któregokolwiek z omawianych pakietów możliwe jest tylko pod warunkiem ustalenia informacji o atrybutach, za pomocą których opisywane są przykłady, i kategoriach pojęcia docelowego. Opis pojedynczego atrybutu ma postać listy, którego pierwszym elementem jest nazwa tego atrybutu, a drugim lista złożona z jego wartości. W przypadku atrybutu aura dla dziedziny stanów pogody opis ma postać listy:
(aura (sloneczna pochmurna deszczowa))
Wszystkie określona na dziedzinie atrybuty opisuje sekwencja złożona z opisów każdego z tych atrybutów. W implementacji żadnego pakietu nie zakładano, czy jest to lista, czy wektor, aby umożliwić wybór reprezentacji bardziej efektywnej dla konkretnego interpretera. Poniższa forma języka Lisp definiuje zmienną pogoda-atrybuty jako listę opisów wszystkich atrybutów dla tej dziedziny:
(defparameter pogoda-atrybuty
'((aura (sloneczna pochmurna deszczowa))
(temperatura (zimna umiarkowana ciepla))
(wilgotnosc (normalna wysoka))
(wiatr (slaby silny))))
Analogiczna konstrukcja wykorzystująca wektor ma postać:
(defparameter pogoda-atrybuty
'#((aura (sloneczna pochmurna deszczowa))
(temperatura (zimna umiarkowana ciepla))
(wilgotnosc (normalna wysoka))
(wiatr (slaby silny))))
W dostarczonych wraz z oprogramowaniem plikach z danymi oraz dalszych przykładach będziemy konskwentnie używać sekwencji atrybutów będących listami. To samo dotyczy innych przypadków, w których może być wykorzystana sekwencja dowolnego typu: będziemy wówczas wyraźnie stwierdzać, że chodzi o sekwencję, lecz w przykładach wykorzystywać listę.
Użycie konstrukcji defparameter powoduje, że przy każdorazowym jej wartościowaniu (np. podczas wielokrotnego wczytywania pliku z danymi) wartość definiowanmej zmiennej wyznaczana jest na nowo. Dzięki temu, jeśli opisy atrybutów umieszczone są w pliku, wprowadzenie do tego pliku zmian i ponowne wczytanie go osiąga oczekiwany efekt. Alternatywna konstrukcja defvar powoduje, że podana wartość nadawana jest zmiennej tylko wtedy, gdy dotychczas jej wartość nie była określona.
Nazwy atrybutów mogą być dowolnymi poprawnymi symbolami języka Lisp. Wartości atrybutów mogą być dowolnymi poprawnymi symbolami lub liczbami. Niezależnie od ich postaci wymienione w opisie atrybutu wartości są zawsze traktowane jako wartości atrybutu nominalnego. Możliwe jest także wykorzystywanie atrybutów ciągłych. Aby atrybut był traktowany jako ciągły, w jego opisie należy pominąć listę wartości. Wówczas opis atrybutu jest jednoelementową listą zawierającą tylko jego nazwę. Aby atrybut temperatura dla dziedziny stanów pogody był traktowany jako ciągły, powyższą definicję atrybutów należałoby zmodyfikować w następujący sposób:
(defparameter pogoda-atrybuty
'((aura (sloneczna pochmurna deszczowa))
(temperatura)
(wilgotnosc (normalna wysoka))
(wiatr (slaby silny))))
Opis kategorii pojęcia docelowego ma postać sekwencji (listy lub wektora) etykiet tych kategorii, które mogą być dowolnymi symbolami lub liczbami języka Lisp. Poniższa konstrukcja definiuje zmienną pogoda-kategorie określającą, że dla dziedziny stanów pogody pojęcie docelowe ma dwie kategorie 1 i 0:
(defparameter pogoda-kategorie '(1 0))
Aby wprowadzić opisy atrybutów i kategorii, co jest niezbędne do korzystania z większości funkcji rozważanych pakietów, można wykorzystać funkcję concept-setyp z pakietu "CONCEPT", której argumentami są sekwencja opisów atrybutów i sekwencja opisów kategorii. Zakładając dostępność zmiennych pogoda-atrybuty i pogoda-kategorie zdefiniowanych w podany wyżej sposób, można przykładowe wywołanie tej funkcji zapisać następująco:
(concept:concept-setup pogoda-atrybuty pogoda-kategorie)
Później zobaczymy, że używając funkcji pakietu "TESTER" można informacje o atrybutach i kategoriach przekazać jako ichumenty.
Poprzedzenie nazwy funkcji przedrostkiem kwalifikującym złożonym z nazwy pakietu i znaku : jest niezbędne, jeśli wywołanie następuje z innego pakietu (domyślnym pakietem jest w większości środowisk języka Lisp pakiet "USER"). Można tego uniknąć zapewniając przed wywołaniem, że publiczne funkcje pakietu "CONCEPT" są dostępne za pomocą formy:
(use-package "CONCEPT")
Ta sama uwaga dotyczy używania innych publicznych funkcji dowolnego pakietu innym pakiecie. W dalszych przykładach zakładać będziemy na ogół, że zostały wykonane odpowiednie formy use-package i wykorzystywane funkcje są dostępne bez potrzeby poprzedzania ich nazw przedrostkiem kwalifikującym.
Pojedynczy przykład reprezentowany jest za pomocą listy, której pierwszy element jest sekwencją wartości atrybutów dla tego przykładu, a drugim elementem jest jego etykieta kategorii. Wartości atrybutów muszą występować w kolejności zgodnej z kolejnością atrybutów, jaka została określona. Pierwszy przykład trenujący dla dziedziny stanów pogody ma więc następujący opis:
((sloneczna ciepla wysoka slaby) 0)
Każda wartość atrybutu musi pochodzić listy wartości podanej przy określaniu atrybutów. W przypadku atrybutów ciągłych jako wartość może wystąpić dowolna liczba. Gdyby atrybut temperatura był ciągły, powyższy opis przykładu mógłby mieć postać:
((sloneczna 27 wysoka slaby) 0)
Nieznane (brakujące) wartości atrybutów dla przykładów reprezentowane są przez nil. Dla przykładu o następującym opisie wartość atrybutu aura jest nieznana:
((nil ciepla normalna silny) 1)
W opisie przykładu można pominąć etykietę kategorii, jeśli nie jest znana. Wówczas mamy do czynienia z przykładem nieetykietowanym. Pomijając kategorię pierwszego przykładu trenującego dla dziedziny stanów pogody dostajemy:
((sloneczna ciepla wysoka slaby))
Jako przykłady trenujące dla uczenia się pojęć mogą być oczywiście używane wyłącznie przykłady etykietowane. Przykłady nieetykietowane mogą być klasyfikowane za pomocą uzyskanych hipotez i używane jako dane trenujące dla grupowania.
Zbiór przykładów jest reprezentowany przez listę przykładów, opisanych w określony wyżej sposób. Wprawdzie niektóre z funkcji operujących na zbiorach przykładów może posługiwać się dowolną sekwencją (czyli także wektorem), lecz w implementacji części funkcji założenie o reprezentacji listowej ma istotne znaczenie. Zbiór trenujący dla dziedziny stanów pogody można przedstawić następująco:
(defparameter pogoda-przyklady
'(((sloneczna ciepla wysoka slaby) 0)
((sloneczna ciepla wysoka silny) 0)
((pochmurna ciepla wysoka slaby) 1)
((deszczowa umiarkowana wysoka slaby) 1)
((deszczowa zimna normalna slaby) 1)
((deszczowa zimna normalna silny) 0)
((pochmurna zimna normalna silny) 1)
((sloneczna umiarkowana wysoka slaby) 0)
((sloneczna zimna normalna slaby) 1)
((deszczowa umiarkowana normalna slaby) 1)
((sloneczna umiarkowana normalna silny) 1)
((pochmurna umiarkowana wysoka silny) 1)
((pochmurna ciepla normalna slaby) 1)
((deszczowa umiarkowana wysoka silny) 0)))
Powyższa konstrukcja definiuje zmienną pogoda-przyklady przechowującą listę przykładów trenujących.
(learn pogoda-przyklady)
Oczywiście aby używać funkcji learn z wybranego pakietu należy albo porzedzić ją przedrostkiem kwalifikującym, albo wcześniej zadeklarować używanie tego pakietu za pomocą konstrukcji use-package. W tym drugim przypadku należy pamiętać, że próba używania więcej niż jednego pakietu zawierającego definicję tego samego symbolu (w tym przypadku funkcji learn) powoduje konflikt, który powoduje błąd lub wymaga rozstrzygnięcia przez użytkownika. Można tego uniknąć rezygnując z używania poprzedniego pakietu przed użyciem następnego za pomocą konstrukcji unuse-package.
Aby wygenerować hipotezę na podstawie zbioru trenującego dla dziedziny stanów pogody najpierw korzystając z pakietu "TDIDT", a następnie korzystając z pakietu "COVER", można wykonać następujący ciąg form:
(concept:concept-setup pogoda-atrybuty pogoda-kategorie) (tdidt:learn pogoda-przyklady) (cover:learn pogoda-przyklady)albo równoważnie:
(use-package "CONCEPT") (concept-setup pogoda-atrybuty pogoda-kategorie) (use-package "TDIDT") (learn pogoda-przyklady) (unuse-package "TDIDT") (use-package "COVER") (learn pogoda-przyklady)
Oczywiście powyższe wywołania funkcji są poprawne pod warunkiem, że zmienne pogoda-atrybuty, pogoda-kategorie i pogoda-przyklady zostały odpowiednio zdefiniowane, na przykład tak jak było to podane wyżej.
W przypadku pakietu "COVER" funkcja learn może poza listą przykładów otrzymywać dodatkowe argumenty kluczowe:
Poniższe formy powodują wygenerowanie zbiorów reguł na podstawie przykładów trenujących dla dziedziny stanów pogody za pomocą algorytmu AQ i algorytmu CN2:
(cover:learn pogoda-przyklady :target 1 :algorithm :aq) (cover:learn pogoda-przyklady :algorithm :cn2)
W pierwszym przypadku została dodatkowo przekazana kategoria docelowa 1, co spowoduje wygenerowanie reguł tylko dla tej kategorii.
Pewne parametry wpływające na działanie algorytmów AQ i CN2 implementowanych przez pakiet "COVER" są zdefiniowane jako publiczne zmienne tego pakietu. Ich domyślne wartości mogą być zmieniane przez użytkownika. Są to następujące zmienne:
Poniższy przykład demonstruje zmianę tych parametrów przez użytkownika:
(setq *maxstar* 3) (setq *cn2-theta* 1.0) (setq *cn2-disjuncts* 2)
Funkcja learn każdego z omawianych pakietów jako swój wynik zwraca uzyskaną hipotezę. Jej reprezentacja jest oczywiście inna dla każdego pakietu i można ją poznać przeglądając kod źródłowy, nie ma ona jednak dużego znaczenia dla użytkownika, który hipotezy obserwuje zapisywane w bardziej czytelnej postaci. Poniżej przedstawione jest w takim zapisie drzewo decyzyjne oraz zbiór reguł wygenerowany przez algorytm AQ dla dziedziny stanów pogody:
< AURA >
=SLONECZNA
< WILGOTNOSC >
=NORMALNA
[1]
=WYSOKA
[0]
=POCHMURNA
[1]
=DESZCZOWA
< WIATR >
=SLABY
[1]
=SILNY
[0]
Rules: 1. IF < AURA=( SLONECZNA DESZCZOWA ) TEMPERATURA=( ZIMNA CIEPLA ) WILGOTNOSC=( WYSOKA ) > THEN 0 2. IF < AURA=( POCHMURNA DESZCZOWA ) WIATR=( SLABY ) > THEN 1 3. IF < AURA=( DESZCZOWA ) TEMPERATURA=( ZIMNA UMIARKOWANA ) WIATR=( SILNY ) > THEN 0 4. IF < AURA=( SLONECZNA POCHMURNA ) TEMPERATURA=( ZIMNA UMIARKOWANA ) WIATR=( SILNY ) > THEN 1 5. IF < AURA=( SLONECZNA POCHMURNA ) TEMPERATURA=( ZIMNA UMIARKOWANA ) WILGOTNOSC=( WYSOKA ) WIATR=( SLABY ) > THEN 0 6. IF < WILGOTNOSC=( NORMALNA ) WIATR=( SLABY ) > THEN 1 Default category: 1
Hipoteza generowana przez funkcję learn z pakietu "TDIDT" jest drzewem decyzyjnym, którego struktura w zapisie tekstowym jest ukazywana za pomocą odpowiednich wcięć. W nawiasach trójkątnych znajdują się nazwy atrybutów odpowiadające węzłom, w nawiasach kwadratowych nazwy kategorii odpowiadające liściom, a wartości atrybutów odpowiadające gałęziom poprzedzone są znakiem równości. Zbiór reguł generowany w przypadku pakietu "COVER" zapisywany jest w postaci ponumerowanej listy (choć zbiór ten traktować należy jako uporządkowany tylko wtedy, jeśli do jego tworzenia użyto algorytmu CN2), po której następuje dodatkowo wskazanie kategorii domyślnej, do której klasyfikowane będą przykłady niepokryte przez żadną z tych reguł. Zapisując reguły uwzględnia się tylko selektory nieuniwersalne ich kompleksów, poprzedzając listę wartości dozwolonych każdego takiego selektora nazwą odpowiedniego atrybutu i znakiem równości. Dla naiwnego klasyfikatora bayesowskiego, który implementuje pakiet "BAYES" hipoteza ma postać zbioru oszacowań prawdopodobieństw kategorii oraz warunkowych prawdopodobieństw wartości atrybutów. Przy ich zapisie jawnie podaje się, których kategorii, atrybutów i ich wartości dotyczą. Najtrudniejsza do interpretacji jest postać hipotez tworzonych za pomocą algorytmu COBWEB w pakiecie "CLUSTER". W jego węzłach nie są fizycznie przechowywane przykłady, a tylko liczniki wystąpień wartości atrybutów, jednak podawanie ich wszystkich dla każdego węzła prowadziłoby do zapisu bardzo nieczytelnego. W obecnej implementacji przyjęto, że przechowuje się także liczniki wystąpienia poszczególnych etykiet kategorii, o ile przykłady trenujące są etykietowane, co umożliwia użycie drzewa grupowania jako hipotezy dla uczenia się pojęć. Właśnie te liczniki są wypisywane dla każdego węzła (w kolejności zgodnej z kolejnością w sekwencji kategorii), przy czym do tekstowej reprezentacji struktury drzewiastej wykorzystane są wcięcia.
Zwróconą przez funkcję learn hipotezę można oczywiście nie tylko obejrzeć, ale również zachować w pewnej zmiennej i następnie używać do klasyfikowania przykładów. Służy do tego również udostępniana przez każdy z pakietów "TDIDT", "COVER", "BAYES" i "CLUSTER" funkcja classify, której pierwszym argumentem jest hipoteza, a drugim przykład do klasyfikacji. Wartością zwracaną jest wyznaczona za pomocą hipotezy kategoria przykładu. Ilustrację dla dziedziny stanów pogody stanowią dwie poniższe formy, przy założeniu, że wcześniej została wykonana forma use-package dla wybranego pakietu:
(setq h (learn pogoda-przyklady)) (classify h '((sloneczna zimna wysoka silny)))
Oczywiście funkcji classify można przekazać tylko hipotezę wygenerowaną przez funkcję learn z tego samego pakietu.
Funkcje zajmujące się wstępnym przetwarzaniem zbiorów przykładów używanych do uczenia się udostępniają pakiety "MISSING" i "DISCRETIZE", poświęcone odpowiednio eliminacji lub wypełnianiu brakujących wartości atrybutów oraz dyskretyzacji atrybutów ciągłych. Zgodnie z tym, co napisano wcześniej, brakujące wartości atrybutów są reprezentowane przez nil w opisie przykładu, a atrybuty ciągłe określa się przez pominięcie w ich opisie listy wartości. Pakiet "CONCEPT" udostępnia funkcję value-unknown-p, która jest predykatem sprawdzającym, czy wartość atrybutu przekazana jako jej argument jest wartością nieznaną (brakującą), oraz funkcję attribute-continuous-p, która jest predykatem sprawdzającym, czy przekazany jako jej argument atrybut (dokładniej, opis atrybutu w podanym wyżej sensie) jest atrybutem ciągłym.
Funkcja missing-eliminate z pakietu "MISSING" zwraca kopię przekazanej jako argument listy przykładów z pominięciem tych z nich, dla których występują brakujące wartości atrybutów. Lista wynikowa zawiera więc tylko te przykłady z listy oryginalnej, dla których wartości wszystkich atrybutów są znane. Gdyby zbiór trenujący dla dziedziny stanów pogody został zdefiniowany w sposób następujący:
(defparameter pogoda-nieznane-instances
'(((sloneczna ciepla wysoka slaby) 0)
((sloneczna ciepla wysoka silny) 0)
((pochmurna ciepla wysoka slaby) 1)
((deszczowa umiarkowana wysoka slaby) 1)
((deszczowa zimna normalna slaby) 1)
((deszczowa zimna normalna silny) 0)
((pochmurna zimna normalna silny) 1)
((sloneczna umiarkowana wysoka slaby) 0)
((sloneczna zimna normalna slaby) 1)
((deszczowa umiarkowana normalna slaby) 1)
((sloneczna umiarkowana normalna silny) 1)
((pochmurna umiarkowana wysoka silny) 1)
((pochmurna ciepla normalna slaby) 1)
((deszczowa umiarkowana wysoka silny) 0)
((nil ciepla normalna silny) 1)))
to wykonanie formy:
(setq pogoda-znane-instances (missing-eliminate pogoda-nieznane-instances))powoduje umieszczenie w zmiennej pogoda-znane-instances kopii listy pogoda-nieznane-instances bez ostatniego przykładu. Lista pogoda-nieznane-instances nie jest przy tym w żaden sposób modyfikowana.
Zamiast pomijania przykładów z brakującymi wartościami atrybutów można te wartości wypełnić za pomocą funkcji missing-fill z pakietu "MISSING". Wypełnianie może być przeprowadzone zgodnie z dwoma prostymi strategiami: albo najczęściej występującą wartością w całym zbiorze przykładów, albo wartością najczęściej występującą w ramach kategorii, którego dotyczy wypełnianie (jeśli więcej niż jedna wartość ma taką samą maksymalną liczbę wystąpień, może zostać użyta dowolna z nich, zależnie od implementacji). Do wyboru jednej z dwóch możliwości służy argument kluczowy :algorithm tej funkcji, który jako wartości może przyjmować symbole odpowiednio :most-common i :category-most-common. Pierwszym argumentem jest lista przykładów. W wyniku działania funkcji jest ona modyfikowana i następnie zwracana. Do podanego wyżej zbioru przykładów dla dziedziny stanów pogody można ją zastosować następująco:
(missing-eliminate pogoda-nieznane-instances :algorithm :category-most-common)Forma ta spowoduje wypełnienie brakującej wartości atrybutu aura dla ostatniego przykładu wartością najczęściej występującą dla przykładów kategorii 1.
Po wyeliminowaniu lub wypełnieniu brakujących wartości atrybutów w zbiorze przykładów można wykorzystywać go jako dane trenujące lub testujące dla dowolnego algorytmu uczenia się zaimplementowanego w pakietach "TDIDT", "COVER", "BAYES" i "CLUSTER".
Pakiet "DISCRETIZE" udostępnia dwie funkcje służące do dwukrokowego przeprowadzania dyskretyzacji atrybutów ciągłych. Pierwsza z nich, attributes-discretize na podstawie dostarczonego zbioru przykładów wyznacza przedziały dyskretyzacji (zgodnie z wybranym algorytmem) i odpowiednio modyfikuje opisy atrybutów ciągłych, wprowadzając do nich listy odpowiadających tym przedziałom wartości dyskretnych. Każdemu wyznaczonemu przedziałowi o końcach v1 i v2 przyporządkowywana jest jednoznacznie dyskretna wartość atrybutu mająca postać nowo tworzonego symbolu, któreho nazwa w zapisie tekstowym ma postać "v1:v2". Zmieniona sekwnencja opisów atrybutów jest zwracana, a lista przykładów nie ulega zmianie. Lista ta jest pierwszym argumentem funkcji, której mogą być także przekazane następujące argumenty kluczowe:
Jeśli dla dziedziny stanów pogody atrybuty temperatura i wilgotjność zostały określone jako ciągłe:
(defparameter pogoda-ciagle-atrybuty
'((aura (sloneczna pochmurna deszczowa))
(temperatura)
(wilgotnosc)
(wiatr (slaby silny))))
(defparameter pogoda-kategorie
'(1 0))
(concept-setup pogoda-ciagle-atrybuty pogoda-kategorie)
(defparameter pogoda-ciagle-przyklady
'(((sloneczna 37.0 80.0 slaby) 0)
((sloneczna 35.0 85.0 silny) 0)
((pochmurna 32.0 90.0 slaby) 1)
((deszczowa 25.0 83.0 slaby) 1)
((deszczowa 18.0 70.0 slaby) 1)
((deszczowa 17.0 65.0 silny) 1)
((pochmurna 19.0 72.0 silny) 1)
((sloneczna 24.0 95.0 slaby) 0)
((sloneczna 20.0 55.0 slaby) 1)
((deszczowa 26.0 60.0 slaby) 1)
((sloneczna 23.0 67.0 slaby) 1)
((pochmurna 22.0 87.0 silny) 1)
((pochmurna 30.0 59.0 slaby) 1)
((deszczeowa 27.0 93.0 silny) 0)))
Przykładowe wywołanie funkcji attributes-discretize może mieć
postać:
(discretize:attributes-discretize pogoda-ciagle-przyklady
:intervals 3 :extend t
:algorithm :chi-merge)
Druga funkcja, instances-discretize, dokonuje faktyczne rzutowania zbioru przykładów do przestrzeni atrybutów otrzymanej po dyskretyzacji. Przekształca ona dostarczony jej zbiór przykładów zastępując występujące w nim wartości atrybutów poprzednio ciągłych odpowiednimi wartościami dyskretnymi, pobranymi z (uprzednio zmodyfikowanych przez funkcję attributes-discretize) opisów tych atrybutów. Lista przykładów jest jedynym argumentem tej funkcji, który po dokonaniu modyfikacji jest zwracany. Kontynuując powyższy przykład możemy wywołanie tej funkcji zapisać następująco:
(discretize:instances-discretize pogoda-ciagle-przyklady)
Po przeprowadzeniu dyskretyzacji atrybutów i następnie odpowiedniego rzutowania zbioru przykładów można go używać jako danych trenujących lub testujących dla wszystkich algorytmów uczenia się zaimplementowanych w pakietach "TDIDT", "COVER", "BAYES" i "CLUSTER".
Omówione dotychczas funkcje pakietów "TDIDT", "COVER", "BAYES" i "CLUSTER" oraz "MISSING" i "DISCRETIZE" pozwalają używanie ich do generowania hipotez i klasyfikowania przykładów, a także wstępne przetwarzanie -- w razie potrzeby -- zbiorów trenujących i testujących. Wykorzystując te funkcje można w łatwy sposób przeprowadzać eksperymenty mające na celu określenie jakości hipotez uzyskiwanych przez różne algorytmy uczenia się dla różnych zbiorów danych. Usprawnieniu tego typu procedur eksperymentalnych służy pakiet "TESTER". Oferowane przez niego usprawnienia mają dwojaki charakter:
Każdy z czterech pakietów implementujących algorytmy uczenia się i tworzenia pojęć udostępnia funkcję learn, służącą do wygenerowania hipotezy na podstawie dostarczonego jako argument zbioru trenującego. Jednolity dostęp do wersji tej funkcji pochodzących z różnych pakietów zapewnia funkcja train z pakietu "TESTER", która również otrzymuje zbiór przykładów jako argument i zwraca uzyskaną na jego podstawie hipotezę. Funkcja ta otrzymuje dodatkowo następujące argumenty kluczowe:
(train pogoda-przyklady
:attributes pogoda-atrybuty
:categories pogoda-kategorie
:package "TDIDT")
Jej skutki są równoważne skutkom wykonania poniższych form, dla
których stanowi ona w istocie alternatywny zapis:
(concept:concept-setup pogoda-atrybuty pogoda-kategorie) (tdidt:learn pogoda-przyklady)
Wprawdzie zapis używający funkcji train nie jest krótszy niż bezpośrednio odwołujący się do funkcji concept-setup i learn, ale jego istotną przewagą jesto, że nazwa pakietu występuje tam jako argument wywołania, przez co może być zmienną. W ten sposób można wygenerować hipotezę za pomocą funkcji learn z pakietu, którego nazwa jest znana dopiero w czasie wykonywania formy (np. odczytana z pliku, podana przez użytkownika) lub w zautomatyzowany sposób wykorzystać różne pakiety. Następująca forma daje w wyniku listę hipotez dla dziedziny stanów pogody uzyskanych za pomocą wszystkich czterech pakietów udostępniających funkcję learn:
(mapcar #'(lambda (p)
(train pogoda-przyklady
:attributes pogoda-atrybuty
:categories pogoda-kategorie
:package p))
'("TDIDT" "COVER" "BAYES" "CLUSTER"))
Ten prosty przykład ilustruje, jak za pomocą pakietu "TESTER" można
automatyzować przeprowadzanie eksperymentów. Dalej zobaczymy kolejne
przykłady tego typu.
Funkcja train z pakietu "COVER" oprócz zbioru przykładów może przyjmować argumenty kluczowe określające docelową i domyślną kategorię oraz wykorzystywany algorytm uczenia się. W związku z tym funkcja train z pakietu "TESTER" umożliwia przekazanie do wywoływanej funkcji learn dowolnych dodatkowych argumentów kluczowych różnych od tych, które one sama wykorzystuje. Jest to mechanizm uniwersalny, który działa nie tylko dla pakietu "COVER", ale może być też użyty dla ewentualnych nowych pakietów lub w przypadku wprowadzenia do funkcji learn z pozostałych obecnie istniejących pakietów dodatkowych argumentów. Dla ilustracji, aby do generowania hipotezy dla dziedziny stanów pogody użyć algorytmu CN@, napiszemy:
(train pogoda-przyklady
:attributes pogoda-atrybuty
:categories pogoda-kategorie
:package "COVER"
:algorithm :aq)
Dostęp do funkcji classify z różnych pakietów umożliwia funkcja o tej samej nazwie z pakietu "TESTER" na takich samych zasadach, jak omówione wyżej dla funkcji train. Tym razem pierwsze dwa argumenty to hipoteza i przykład do klasyfikacji, kluczowe argumenty :attributes i :categories służą do podania informacji o atrybutach i kategoriach, a kluczowy argument :package określa pakiet, z którego ma pochodzić funkcja classify użyta do klasyfikacji tego przykładu za pomocą tej hipotezy. Oczywiście musi być to ten sam pakiet, który był użyty do generowania hipotezy. Tak jak poprzednio, ewentualne dodatkowe argumenty kluczowe są przekazywane do wywoływanej funkcji, lecz obecnie żadna z dostępnych wersji funkcji classify takich argumentów nie używa.
Poniższe dwie formy powodują zapamiętanie hipotezy wygenerowanej dla dziedziny stanów pogody za pomocą pakietu "TDIDT", a następnie wykorzystanie jej do klasyfikacji nowego przykładu:
(setq h (train pogoda-przyklady
:attributes pogoda-atrybuty
:categories pogoda-kategorie
:package "TDIDT"))
(classify h '((sloneczna zimna wysoka silny))
:package "TDIDT")
W wywołaniu funkcji classify pominięto argumenty
:attributes i categories, aby użyć informacji o
atryhutach i kategoriach ustalonych przez wcześniejsze wywołanie
funkcji train.
Wynikiem wykonania poniższej formy jest lista kategorii przypisanych temu samemu nowemu przykładowi przez każdą z hipotez uzyskanych dla dziedziny stanów pogody za pomocą wszystkich czterech pakietów udostępniających funkcje learn i classify:
(mapcar #'(lambda (p)
(let ((h (train pogoda-przyklady
:attributes pogoda-atrybuty
:categories pogoda-kategorie
:package p)))
(classify h '((sloneczna zimna wysoka silny))
:package p)))
'("TDIDT" "COVER" "BAYES" "CLUSTER"))
Często jakość uzyskanej hipotezy oceniamy obliczając jej błąd próbki na pewnym zbiorze przykładów używanych do testowania. Aby uniknąć konieczności jawnego wielokrotnego wywoływania funkcji classify i obliczania liczby pomyłek, w pakiecie "TESTER" zaimplementowano funkcję test, która dla hipotezy i zbioru przykładów podanych jako odpowiednio pierwszy i drugi argument wyznacza błąd próbki. Działanie tej funkcji polega oczywiście na wielokrotnym wywoływaniu funkcji classify, więc należy jej przekazać argumenty kluczowe niezbędne do poprawnego wykonania takiego wywołanie -- w razie potrzeby argumenty :attributes i :categories (jeśli informacje o atrybutach i kategoriach nie zostały wcześniej właściwie określone) oraz w każdym przypadku argument :package w celu podania, z którego pakietu funkcja classify ma być użyta. Poniżej pokazano sposób testowania za pomocą funkcji test drzewa decyzyjnego dla dziedziny stanów pogody, zakładając, że wartością zmiennej pogoda-test-instances jest pewna lista przykładów testujących:
(setq h (train pogoda-przyklady
:attributes pogoda-atrybuty
:categories pogoda-kategorie
:package "TDIDT"))
(test h pogoda-test-instances
:package "TDIDT")
Dwie podstawowe metody eksperymentalnej oceny skuteczności algorytmu uczenia się dla ustalonego zbioru danych to walidacja krzyżowa i k-krotna walidacja krzyżowa. Ze względu na ich częste stosowanie pakiet "TESTER" pozwala przeprowadzić je w sposób w pełni zautomatyzowany, bez potrzeby jawnego manipulowania na zbiorze przykładów oraz odpowiedniego wywoływania funkcji train i test. Pierwszym argumentem funkcji cross-validate i k-fold-cross-validate jest zbiór przykładów etykietowanych, który ma być we właściwy sposób dzielony na zbioru trenujący i testujący. Dla pierwszej z tych funkcji zbiór trenujący jest losowym podzbiorem całego zbioru przykładów o rozmiarze równym iloczynowi jego rozmiaru i ułamkowego współczynnika przekazanego jako jej drugi argument. Pozostałe przykłady wchodzą w skład zbioru testującego. Błąd próbki uzyskanej hipotezy na tym zbiorze stanowi pierwszą wartość zwracaną przez funkcję. Zwraca ona także drugą wartość, którą jest błąd tej hipotezy na zbiorze trenującym, oraz trzecią, będąca rozmiarem hipotezy (ściślej, listą wartości zwróconych dla niej przez funkcję hypothesis-size, której tu nie omawiamy, lecz której opis znajduje się w ramach prezentacji publicznych interfejsów wszystkich pakietów). Z kolei dla funkcji k-fold-cross-validate drugim argumentem jest liczba w przybliżeniu równolicznych losowych podzbiorów, na które dzielony jest zbiór przykładów. Każdy z tych podzbiorów pełni rolę zbioru testującego dla hipotezy wygenerowanej na podstawie zbioru trenującego powstałego przez połączenie pozostałych podzbiorów. Jako pierwszą wartość funkcja zwraca średni uzyskany błąd próbki na zbiorze testującym. Drugą wartość zwracaną stanowi lista złożona z list zawierających wszystkie uzyskane błędy testowania i odpowiadające im rozmiary hipotez (a ściślej, listy wartości zwróconych przez funkcję hypothesis-size). Ponieważ obie funkcje realizują swoje zadanie przez odpowiednie wywoływanie funkcji train i test, należy im przekazać niezbędne dla takich wywołań argumenty kluczowe.
Poniższa forma wykonuje walidację krzyżową dla algorytmu ID3 na podstawie zbioru przykładów dla dziedziny stanów pogody, używając jako zbioru trenującego zbioru przykładów złożonego z połowy dostępnych dla tej dziedziny danych:
(cross-validate pogoda-przyklady 0.5
:attributes pogoda-atrybuty
:categories pogoda-kategorie
:package "TDIDT")
Z kolei następna forma demonstruje 7-krotną walidację krzyżową dla
algorytmu CN2 na podstawie tych samych danych:
(k-fold-cross-validate pogoda-przyklady 7
:attributes pogoda-atrybuty
:categories pogoda-kategorie
:package "COVER"
:algorithm :cn2)
Ostatnią ważną cechę funkcjonalną pakietu "TESTER" stanowi możliwość zautomatyzowanego wykonywania tych samych eksperymentów dla różnych algorytmów uczenia się. Dzięki niej można powtórzyć uczenie się, walidację krzyżową lub k-krotną walidację krzyżową na podstawie tych samych danych dla dowolnego dostępnego algorytmu. Operacją wykonywaną w ramach takiego eksperymentu może być dowolna funkcja, która niezależnie od używanego algorytmu uczenia się przyjmuje takie same argumenty. Spośród omawianych wyżej funkcji pakietu "TESTER" wyklucza to funkcje classify i test, które jako argument otrzymują hipotezę o postaci specyficznej dla każdego algorytmu, ale pozwala na używanie funkcji train, cross-validate i k-fold-cross-validate. Jedna z tych funkcji może być pierwszym argumentem służącej do automatyzacji eksperymentów funkcji experiment (nazwę funkcji poprzedza się wówczas przedrostkiem '#). Oczywiście można użyć także pewnej funkcji zdefiniowanej uprzednio przez użytkownika, o ile spełnia podany warunek. Drugi argument to z kolei lista stałych, wspólnych dla wszystkich algorytmów uczenia się argumentów (niekluczowych), jakie mają być do tej wybranej funkcji przekazywane przy jej wywoływaniu. Trzeci argument jest listą określającą, dla jakich algorytmów eksperyment ma być przeprowadzony. Każdy element tej listy może być albo nazwą pakietu, albo listą złożoną z nazwy pakietu i dodatkowych, specyficznych dla tego pakietu argumentów. Jak wiemy, obecnie takie argumenty mają znaczenie tylko dla pakietu "COVER". Ewentualne dodatkowe argumenty kluczowe funkcji experiment przekazywane są do wywoływanej przez nią dla każdego algorytmu funkcji, co w szczególności pozwala podać informacje o atrybutach i kategoriach. Wynikiem funkcji jest lista asocjacyjna, w której każdy używany algorytm związany jest z uzyskanym dla niego wynikiem eksperymentu.
Przedstawiona niżej forma powoduje przeprowadzenie 7-krotnej walidacji krzyżowej na podstawie dostępnych danych dla dziedziny stanów pogody dla każdego dostępnego algorytmu uczenia się:
(experiment #'k-fold-cross-validate
`(,pogoda-przyklady 7)
'("TDIDT"
("COVER" :algorithm :aq)
("COVER" :algorithm :cn2)
"BAYES"
"CLUSTER")
:attributes pogoda-atrybuty
:categories pogoda-kategorie)
Warto zauważyć, że drugim argumentem powyższego wywołania musi być
lista argumentów przekazywanych przy każdym wywołaniu funkcji
k-fold-cross-validate. Jej pierwszym argumentem ma być zbiór
przykładów, a drugim liczba 7, aby przeprowadzona została 7-krotna
walidacja krzyżowa. Listę taką uzyskuje się za pomocą konstrukcji:
`(,pogoda-przyklady 7)Poprzedzenie listy wstecznym apostrofem ` zamiast zwykłego ' powoduje, że można jako jej element umieścić wartość zmiennej (w tym przypadku pogoda-przyklady), jeśli poprzedzi się nazwę tej zmiennej przecinkiem. "Naiwny" zapis:
'(pogoda-przyklady 7)tworzy tymczasem listę, której pierwszym elementem jest symbol pogoda-przyklady, a nie wartość zmiennej o takiej nazwie.
Zamiast nazw pakietów wywołując funkcję experiment można też z identycznym skutkiem użyć odpwiednich symboli, czyli powyższy przykład może być równie dobrze zapisany następująco:
(experiment #'k-fold-cross-validate
`(,pogoda-przyklady 7)
'(tdidt
(cover :algorithm :aq)
(cover :algorithm :cn2)
bates
cluster)
:attributes pogoda-atrybuty
:categories pogoda-kategorie)
Aby przy korzystaniu z algorytmów indukcyjnego uczenia się i tworzenia pojęć całkowicie wyeliminować potrzebę bezpośredniego odwoływania się do funkcji pakietów innych niż "TESTER", zawarto w nim także funkcje missing-eliminate i missing-fill oraz discretize-attributes, discretize-instances i discretize-all. Ich działanie sprowadza się do odpowiedniego wywoływania funkcji z pakietów "MISSING" i "DISCRETIZE". Nie będziemy ich w tym miejscu dokładniej omawiać, uznając za wystarczający ich opis przedstawiony niżej przy prezentacji publicznych interfejsów pakietów.
Pakiet "AUTOMATA" jako jedyny z dostarczonych pakietów nie dotyczy uczenia się lub tworzenia pojęć, lecz uczenia się automatów skończonych. Zawiera on implementację podstawowego algorytmu L* uczącego się na podstawie zapytań o przynależność i równoważność. Zdefiniowane w nim struktury danych do reprezentacji automatów i obsługujące je funkcje moga być oczywiście wykorzystane do implementacji innych algorytmów. Dla większej ogólności przyjęto, że poszukiwana hipoteza ma postać automatu z wyjściami typu Moore'a -- automat skończony bez wyjśc (ze stanami końcowymi) może być traktowany jako jego szczególny przypadek.
Symbolami wejściowymi i wyjściowymi automatu mogą być dowolne symbole języka Lisp. Alfabet wejściowy i wyjściowy przechowują odpowiednio zmienne *inalpha* i *outalpha zdefiniowane w pakiecie "AUTOMATA", których wartościami mogą być dowolne listy symboli. Domyślnie obie zmienne mają wartość (0 1), czyli alfabet wejściowy i wyjściowy składa się z symboli 0 i 1.
Napis, czyli ciąg symboli wejściowych, reprezentowany jest przez listę złożoną z symboli alfabetu wejściowego. Zatem napis 0010 ma reprezentację (0 0 1 0).
Informacja trenująca dla algorytmu L* ma postać odpowiedzi na zapytania o przynależność i równoważność. Aby umożliwić wykorzystywanie implementacji tego algorytmu, jaką dostarcza pakiet "AUTOMATA", w maksymalnie elastyczny sposób, przyjęto, że zadanie zapytania każdego z tych rodzajów i pozyskanie na nie odpowiedzi realizują specjalne funkcje, które mogą być zdefiniowane przez użytkownika. Pozwala to w szczególności generować odpowiedzi na te zapytania przez wykorzystanie zaimplementowanego odrębnie symulatora automatu docelowego, co ułatwia automatyzację testowania algorytmu L*. Jednocześnie udostępnione zostały domyślne definicje tych funkcji, które zadają zapytania interaktywnie użytkownikowi.
Funkcja odpowiedzialna za zadawanie zapytań o przynależność otrzymuje jako argument pewien napis (czyli listę złożoną z symboli wejściowych). Odpowiedzią na to zapytanie powinien być symbol wyjściowy, jaki automat docelowy wygeneruje po przetworzeniu tego napisu (zaczynając w stanie początkowym). Domyślna wersja tej funkcji, zdefiniowana w pakiecie "AUTOMATA" pod nazwą default-mq, przedstawia zapytanie użytkownikowi i czyta jego odpowiedź z wejścia. Użytkownik powinien podać wówczas pewien symbol wyjściowy automatu (bez znaku cytowania ').
Argumentem funkcji zadającej zapytanie o równoważność jest automat, reprezentowany przez zdefiniowaną w pakiecie "AUTOMATA" strukturę służącą do tego celu. Szczegóły tej reprezentacji można poznać zaglądając do kodu źródłowego. Oczekiwany wynik tej funkcji jest listą, której pierwszy element stanowi pozytywna (czyli t) lub negatywna (czyli nil) odpowiedź na zapytanie, a drugi element -- który jest konieczny tylko w przypadku odpowiedzi negatywnej -- jest kontrprzykładem, mającym tak jak każdy napis postać listy symboli wejściowych. Domyślna wersja funkcji zadającej zapytania o równoważność, zdefiniowana w pakiecie "AUTOMATA" pod nazwą default-eq, kieruje je do użytkownika i czyta z wejścia jego odpowiedź. Użytkownik powinien wprowadzić listę podanej postaci, z pominięciem znaku cytowania '.
Do inicjalizacji procesu uczenia się automatu za pomocą algorytmu L* służy funkcja learn. Można jej przekazać następujące argumenty kluczowe:
W wyniku wywołania funkcji learn wykonywane są kolejne iteracje algorytmu L*, przy czym zadawane są niezbędne do tego zapytania. Po uzyskaniu pozytywnej odpowiedzi na zapytanie o równoważność funkcja kończy działanie i zwraca uzyskany automat.
Jako ilustrację sposobu korzystania z pakietu L* przedstawimy przebieg jego działania podczas uczenia się języka docelowego, którego napisy są złożone z parzystej liczby symboli 0 i 1. Dla większej czytelności tekst wprowadzany przez użytkownika w odpowiedzi na zapytania podany jest z wcięciem.
> (learn)
Membership query for NIL
1
Membership query for (0)
0
Membership query for (1)
0
Membership query for (0 0)
1
Membership query for (0 1)
0
Equivalence query for
A=(0 1)
Y=(0 1)
0: #(1 1) | 1
1: #(0 1) | 0
(nil (1 1))
Membership query for (1 1)
1
Membership query for (1 1 0)
0
Membership query for (1 1 1)
0
Membership query for (1 0)
0
Membership query for (1 0 0)
0
Membership query for (1 1 1 0)
0
Membership query for (1 1 0 0)
1
Membership query for (0 1 0)
0
Membership query for (0 0 0)
0
Equivalence query for
A=(0 1)
Y=(0 1)
0: #(2 1) | 1
1: #(1 0) | 0
2: #(0 1) | 0
(nil (0 1 1))
Membership query for (0 1 1 0)
1
Membership query for (0 1 1)
0
Membership query for (0 1 1 0 0)
0
Membership query for (0 1 1 1 0)
0
Membership query for (0 1 1 1)
0
Membership query for (0 1 0 0)
0
Membership query for (0 1 0 1)
1
Membership query for (0 1 1 1 1)
0
Membership query for (0 1 1 0 1)
0
Membership query for (1 0 1)
0
Membership query for (1 1 1 1)
1
Membership query for (1 1 0 1)
0
Membership query for (0 0 1)
0
Equivalence query for
A=(0 1)
Y=(0 1)
0: #(2 3) | 1
1: #(3 2) | 0
2: #(0 1) | 0
3: #(1 0) | 0
(t)
A=(0 1)
Y=(0 1)
0: #(2 3) | 1
1: #(3 2) | 0
2: #(0 1) | 0
3: #(1 0) | 0
Zgodnie z przyjętą w języku Lisp konwencją nazwy pakietów zapisywane są wielkimi literami i ujmowane w cydzysłowy. Dla każdego pakietu podamy listę zdefiniowanych w nim publicznych zmiennych (jeśli występują) i funkcji, wraz z krótką charakterystyką. Sposób posługiwania się najważniejszymi z nich będzie dokładniej omówiony oddzielnie.
Funkcje udostępniane przez ten pakiet wykorzystywane są w większości pozostałych pakietów. Nie wiążą się one w ścisły sposób z algorytmami uczenia się, lecz mają charakter pewnych pomocniczych operacji ogólnego przeznaczenia.
W tym pakiecie zdefiniowane są funkcje obliczające wartości teorioinformacyjnych heurystyk używanych przy indukcji drzew decyzyjnych oraz indukcji reguł za pomocą algorytmu CN2. Obliczane wartości informacji i entropii odnoszą się do rozkładu kategorii przykładów.
Funkcje udostępniane przez ten pakiet wykorzystywane są przez wszystkie pakiety implementujące algorytmy uczenia się pojęć, a także pakiet "INFO", poświęcony implementacji grupowania pojęciowego pakiet "CLUSTER", pakiety "MISSING" i "DISCRETIZE" zajmujące się przetwarzaniem zbiorów trenujących i pakiet "TESTER", który ułatwia testowanie algorytmów indukcji.
Pakiet ten zawiera implementację indukcji drzew decyzyjnych za pomocą algorytmu ID3. Pozwala on na generowanie drzewa na podstawie zbioru przykładów oraz używanie go do klasyfikacji nowych przykładów.
Pakiet ten zawiera implementację indukcji reguł za pomocą algorytmów AQ i CN2. Pozwala on na generowanie zbioru reguł (nieuporządkowanego dla algorytmu AQ oraz uporządkowanego dla algorytmu CN2) na podstawie zbioru przykładów oraz używanie go do klasyfikacji nowych przykładów. Oba algorytmy są zaimplementowane zgodnie z ich opisem w książce. Szczegóły techniczne można poznać przeglądając kod źródłowy pakietu.
Funkcje tego pakietu zajmują się szacowaniem na podstawie dostarczonych przykładów prawdopodobieństw używanych przez naiwny klasyfikator bayesowski oraz wykorzystywaniem ich do klasyfikowania nowych przykładów.
Pakiet ten implementuje grupowanie pojęciowe za pomocą algorytmu COBWEB. Pozwala na zbudowanie drzewa grupowania na podstawie zbioru przykładów, a także na traktowanie go (jeśli było generowane na podstawie przykładów etykietowanych) jako hipotezy dla uczenia się pojęć, pozwalającej na klasyfikowanie nowych przykładów.
Jest to pakiet udostępniający funkcje do eliminowania przykładów z brakującymi wartościami atrybutów oraz do wypełniania tych brakujących wartości zgodnie z prostymi algorytmami.
W pakiecie tym zdefiniowano funkcje realizujące dyskretyzację atrybutów ciągłych i odpowiednie przekształcanie zbioru przykładów. Zaimplementowane są prymitywne metody dyskretyzacji według równej szerokości i równej częstości oraz algorytm ChiMerge.
Głównym celem tego pakietu jest udostępnienie wspólnego interfejsu dla pakietów "TDIDT", "COVER", "BAYES", "CLUSTER". Eliminuje on potrzebę bezpośredniego odwoływania się do ich funkcji, gdyż są one wszystkie dostępne za pośrednictwem funkcji pakietu "TESTER", którym wystarczy wskazać, którego z tych pakietów należy użyć do generowania hipotezy lub klasyfikowania przykładów. Oprócz tych dwóch operacji, dostępnych w każdym z tych pakietów, pakiet "TESTER" dodatkowo umożliwia testowanie hipotez (wyznaczanie błędu próbki) oraz testowanie algorytmów metodą walidacji krzyżowej i k-krotnej walidacji krzyżowej. Dzięki funkcjom tego pakietu przeprowadzanie takich testów może zostać w znacznym stopniu zautomatyzowane.
W tym pakiecie zaimplementowane zostało uczenie się automatów skończonych za pomocą algorytmu L*. Domyślne wersje funkcji zadających zapytania o przynależność i równoważność, które kierują je do użytkownika i czytają jego odpowiedź z wejścia, mogą zostać zastąpione innymi wersjami tych funkcji.