Paweł Cichosz
Wydział Elektroniki i Technik Informacyjnych
Politechniki Warszawskiej
Kwiecień 1998
Książka ma być podręcznikiem akademickim dotyczącym systemów uczących się. Jest to szczególnie intensywnie rozwijająca się dziedzina badań w ramach sztucznej inteligencji, która w ostatnich latach budzi w wielu krajach rosnące zainteresowanie na uczelniach i w instytutach naukowych oraz coraz częściej znajduje znaczące zastosowania praktyczne. Jej przedmiotem są metody konstruowania programów komputerowych charakteryzujących się zdolnością do uczenia się, czyli -- mówiąc najogólniej -- poprawy jakości wykonywania swoich zadań na podstawie doświadczeń z przeszłości.
Celem książki jest prezentacja najważniejszych rodzajów maszynowego uczenia się i odpowiadających im algorytmów uczenia się, opracowanych w większości w ciągu ostatnich 20 lat. W polskiej literaturze nie ma dotychczas pozycji, która prezentowałaby wyniki badań nad systemami uczącymi się w sposób wszechstronny, przystępny, systematyczny i nowoczesny. Nieliczne dostępne publikacje poruszające zagadnienia maszynowego uczenia się mają bardzo ograniczony zakres, uwzględniający tylko niektóre szczególne rodzaje i algorytmy uczenia się, a jedynym naprawdę dobrze reprezentowanym w nich typem systemów uczących się są sztuczne sieci neuronowe. Tę dotkliwą lukę ma wypełnić przygotowywana książka.
Próby konstruowania programów uczących się nie są motywowane chęcią eliminacji wysiłku projektantów oprogramowania i programistów. Nie są one w żadnej mierze alternatywą dla tradycyjnej inżynierii oprogramowania. Motywacja dla ich podejmowania nie wynika ze złożoności procesu tworzenia oprogramowania, której opanowaniu służą nowoczesne metody analizy i projektowania, lecz ze złożoności niektórych rodzajów stawianych programom komputerowym zadań, utrudniającej lub uniemożliwiającej sformułowanie poprawnych i pełnych algorytmów ich rozwiązywania. Program uczący się można sobie wyobrażać jako program wykorzystujący abstrakcyjny, w pewien sposób parametryzowany algorytm wykonywania zadania. Wówczas uczenie się polega na dobraniu na podstawie historycznych doświadczeń odpowiednich parametrów, które ten algorytm abstrakcyjny przekształcą w spełniający wymagania konstruktora algorytm konkretny. Owe uzyskiwane w wyniku uczenia się parametry nazywane są, zależnie od rodzaju zadań, wiedzą lub umiejętnością. Algorytmy pozyskiwania lub doskonalenia wiedzy bądź umiejętności nazywane są algorytmami uczenia się.
W literaturze systemów uczących się znanych jest bardzo wiele algorytmów uczenia się. Można je dzielić na grupy ze względu na różne kryteria, takie jak metoda reprezentacji wiedzy (umiejętności), rodzaj zadań, do wykonywania których ta wiedza (umiejętność) jest używana, sposób pozyskiwania doświadczeń stanowiących podstawę uczenia się (informacji trenującej). W książce będą omówione najbardziej reprezentatywne i skuteteczne w praktyce algorytmy poszczególnych grup. Świadomie będą przy tym niemal całkowicie pominięte sieci neuronowe, które oczywiście są systemami uczącymi się szczególnego typu, lecz doczekały się już wielu znakomitych książek wydanych w języku polskim.
Książka, jako podręcznik akademicki, przeznaczona będzie przede wszystkim dla studentów wyższych uczelni, studiujących na kierunkach informatycznych lub pokrewnych. Będzie ona również pomocna dla nauczycieli akademickich zainteresowanych prowadzeniem przedmiotów dotyczących systemów uczących się, którzy oprócz tekstu pozwalającego na opracowanie wykładu znajdą tam propozycje ćwiczeń i projektów. Można liczyć na to, że dzięki wszechstronnemu i nowoczesnemu potraktowaniu dziedziny maszynowego uczenia się książka będzie też pożytecznym źródłem informacji dla naukowców, porządkującym najważniejsze wyniki badań w tej dziedzinie i wskazującym podstawowe pozycje literatury. Dla doktorantów planujących własne badania dotyczące maszynowego uczenia się zapoznanie się z zawartością książki będzie dobrym punktem wyjścia. Powinna ona także zaspokoić po części potrzeby praktyków zainteresowanych zastosowaniami systemów uczących się, zwłaszcza do odkrywania zależności w bazach danych, pozyskiwania wiedzy dla systemów ekspertowych i automatycznego sterowania.
U czytelników książki zakładana będzie znajomość podstaw informatyki i elementarna umiejętność programowania w dowolnym języku programowania. W lekturze niektórych fragmentów książki pomocna będzie znajomość podstaw rachunku prawdopodobieństwa i logiki formalnej, gdziekolwiek wykorzystywany aparat matematyczny wykraczać będzie poza materiał szkoły średniej, zostanie on zwięźle opisany w dodatkach. Nieliczne trudniejsze fragmenty książki czytelnicy niezainteresowaniami teoretycznymi podstawami systemów uczących się będą mogli pominąć bez szkody dla zrozumienia istoty omawianych w niej algorytmów.
Książka podzielona będzie na kilkanaście rozdziałów i kilka dodatków. Większość rozdziałów poświęcona będzie omówieniu pewnego rodzaju uczenia się i przedstawieniu jednego lub kilku odpowiadających mu algorytmów uczenia się. Według wstępnych oszacowań książka osiągnie rozmiar odpowiadający ok. 25 arkuszom wydawniczym.
Każdy rozdział rozpoczynać się będzie od akapitu krótko zapowiadającego jego zawartość. Na końcu każdego rozdziału znajdzie się podsumowanie jego treści, nota historyczna i bibliograficzna oraz lista od kilku do kilkunastu ćwiczeń.
Każdy algorytm będzie przedstawiany w zrozumiałym dla czytelników o minimalnym doświadczeniu programistycznym pseudokodzie oraz szeroko komentowany w tekście. Podawane będzie intuicyjne lub teoretyczne uzasadnienie każdego algorytmu, a jego działanie ilustrowane przynajmniej jednym szczegółowo opisanym przykładem, polegającym na prześledzeniu sekwencji operacji wykonywanych dla przykładowych danych wejściowych. Niekiedy przedstawione zostaną w charakterze przykładów także wyniki eksperymentów obliczeniowych. Omówienie każdego algorytmu zamknie dyskusja związanych z nim zagadnień praktycznych i implementacyjnych. W pierwszym przypadku chodzi o przedstawienie czytelnikom problemów związanych z praktycznymi zastosowaniami algorytmu (np. pewnych ograniczeń, upraszczających założeń, które mogą nie być spełnione itp.) i możliwych sposobów ich rozwiązywania. W drugim przypadku chodzi o wskazanie możliwych decyzji implementacyjnych (np. dotyczących wyboru struktur danych) i ich konsekwencji dla efektywności.
Ćwiczenia zamieszczane na końcu każdego rozdziału będą miały za zadanie pomóc czytelnikowi w weryfikacji i ugruntowaniu zrozumienia omawianych w rozdziale zagadnień, zwrócić jego uwagę na niektóre szczegółowe problemy, które nie zostały dokładnie przedstawione w głównym tekście rozdziału, niekiedy zasugerować pewne możliwe rozszerzenia algorytmów. W książce będą ćwiczenia trzech następujących typów:
Wśród ćwiczeń tradycyjnych znajdą się m.in. pytania dotyczące pewnych elementów teorii lub właściwości algorytmów, polecenia prześledzenia działania algorytmów dla podanych danych wejściowych oraz ogólne sugestie pewnych modyfikacji algorytmów z prośbą o ich sprecyzowanie i przedyskutowanie. Rozwiązania wszystkich ćwiczeń tego typu podane będą w dodatku do książki.
Ćwiczenia laboratoryjne polegać będą na przeprowadzeniu eksperymentów wykorzystujących dostarczone wraz książką implementacje omawianych w niej algorytmów oraz na dokonaniu pewnych niewielkich zmian w tych programach. W dodatku do książki podane będą wskazówki do wszystkich ćwiczeń tego typu.
Ćwiczenia projektowe dotyczyć będą implementacji pewnych wariantów omawianych w książce algorytmów i wykorzystania ich w konkretnych prostych zastosowaniach.
Książce towarzyszyć będzie zbiór programów, implementujących większość omawianych w niej algorytmów uczenia się. Sposób implementacji będzie możliwie wiernie odzwierciedlał opis algorytmów zamieszczony w tekście. Programy będą dostępne w postaci źródłowej w języku Common Lisp, którego komercyjne i darmowe interpretery dostępne są dla wszystkich częściej spotykanych typów komputerów i systemów operacyjnych (w tym dla najbardziej popularnych komputerów PC z systemami DOS/Windows i Linux). Programy zostaną umieszczone na dołączonym do książki nośniku (dyskietka lub dysk optyczny CD ROM) oraz ewentualnie na poświęconej książce internetowej stronie WWW. W przypadku dołączenia do książki dysku optycznego możliwe będzie umieszczenie na nim także wybranego niekomercyjnego intepretera języka Common Lisp dla najbardziej popularnych platform (zgodnie z licencją zezwalającą na swobodne rozpowszechnianie). Wybór najszerzej używanego dialektu Lispa, normowanego standardem ANSI, jako języka programowania, w którym będą implementowane algorytmy z książki, jest uzasadniony
Chociaż znajomość języka Common Lisp (lub innego dialektu Lispa) stanowić będzie niewątpliwe ułatwienie w korzystaniu z programów, nie będzie ona w żadnej mierze konieczna. W dodatku do książki przedstawione będą szczegółowe instrukcje umożliwiające posługiwanie się nimi bez żadnej uprzedniej znajomości Lispa. W innym dodatku przedstawiony będzie krótki przewodnik po języku Common Lisp, pozwalający na rozumienie kodu źródłowego i wykonywanie w nim prostych modyfikacji.
Jak wspomniano wyżej, książka będzie mogła być wykorzystana do celów dydaktycznych -- jako podstawowy tekst do kursu systemów uczących się lub jako uzupełniający tekst do kursów na temat sztucznej inteligencji, systemów ekspertowych, metod reprezentacji wiedzy itp. Ocenia się, że zawartość książki może posłużyć do opracowania przynajmniej 30-45 godzin wykładu (zależnie od poziomu szczegółowości oraz przygotowania i zainteresowań słuchaczy). Zamieszczone w książce ćwiczenia tradycyjne mogą stanowić przykładowe zadania domowe lub egzaminacyjne. Towarzyszące książce oprogramowanie i zamieszczone w niej ćwiczenia laboratoryjne mogą posłużyć do zorganizowania 10-20 godzin zajęć przy komputerach w ramach laboratorium systemów uczących się. Ćwiczenia projektowe mogą stanowić tematy semestralnych projektów wykonywanych indywidualnie lub w niewielkich zespołach. Niektóre trudniejsze ćwiczenia projektowe, odpowiednio rozwinięte, mogą także posłużyć jako przykłady tematów prac dyplomowych na poziomie wyższych studiów zawodowych.
Poniżej przedstawione zostaną robocze tytuły oraz planowana zawartość wszystkich rozdziałów oraz dodatków książki. Podział rozdziałów na podrozdziały może oczywiście ulec zmianom w trakcie dalszych prac.
Pierwszy rozdział służyć będzie przybliżeniu czytelnikom algorytmicznego rozumienia procesu uczenia się.
Zostanie tu określone i zilustrowane przykładami, co rozumie się przez uczenie się sztucznych systemów (programów komputerowych) oraz ich wiedzę lub umiejętność. Przedstawiona zostanie także motywacja badawczego i praktycznego zainteresowania uczącymi się systemami oraz uwypuklona rola badań nad nimi w ramach sztucznej inteligencji.
Rodzaje maszynowego uczenia się zostaną sklasyfikowane za pomocą kilku podstawowych kryteriów (m.in. reprezentacja wiedzy/umiejętności, forma informacji trenującej, dziedzina zastosowania).
Powyższa klasyfikacja będzie punktem wyjścia do ogólnego zarysowania współczesnego obrazu dyscypliny naukowej zajmującej się badaniem systemów uczących się, z wyszczególnieniem jej trzech głównych gałęzi (rozwijanie teorii uczenia się, konstruowanie systemów uczących się, komputerowe modelowanie biologicznych procesów uczenia się) i zapowiedzią sposobu i stopnia, w jakim będą one reprezentowane w książce (problemy biologicznego uczenia się będą pominięte, a z wyników teoretycznych przytoczone i omówione tylko najbardziej podstawowe).
Ten podrozdział przedstawi w zarysie inferencyjną teorię uczenia się, traktującą proces uczenia się jako wynik stosowania różnych mechanizmów wnioskowania, która jest pierwszą próbą umieszczenia różnych form uczenia się w ramach jednolitej siatki pojęciowej i terminologicznej.
Wskazane tu zostaną najważniejsze obszary, w których systemy uczące się znajdowały dotychczas i mogą znaleźć w przyszłości zastosowania praktyczne.
Znajdzie się tu kilka uwag o charakterze filozoficznym, pobieżnie wskazujących te koncepcje znane z ostatnich 2500 lat dziejów zachodniej filozofii, które najściślej wiążą się z problemami uczenia się przez systemy naturalne oraz sztuczne.
Przedstawiona będzie skrótowo historia badań nad systemami uczącymi się od lat 50. do lat 90. oraz wskazane zostaną klasyczne publikacje z tej dziedziny, najlepsze artykuły przeglądowe i podręczniki.
Rodzajem uczenia się, któremu poświęcono najwięcej uwagi w badaniach teoretycznych, dla którego zaproponowano najwięcej algorytmów i który znalazł najliczniejsze praktyczne zastosowania, jest uczenie się indukcyjne. Obecny rozdział zdefiniuje problem indukcyjnego uczenia się (w kilku odmianach) i wprowadzi jego podstawy teoretyczne, a kilka kolejnych rozdziałów poświęconych będzie różnym konkretnym realizacjom tej formy uczenia się.
Przedstawiona tu zostanie indukcja jako mechanizm wnioskowania prowadzący do wskazywania hipotez najlepiej wyjaśniających i uogólniających obserwowane fakty, które w przypadku indukcyjnych metod uczenia się nazywane są przykładami. Następnie wskazane zostaną trzy najczęściej spotykane odmiany problemu uczenia się na podstawie przykładów: uczenie się pojęć, tworzenie pojęć i uczenie się aproksymacji funkcji.
W tym podrozdziale określone zostanie nieformalnie, co rozumie się przez pojęcie i jego uczenie się. Pojęcia służą do klasyfikowania obiektów pewnej dziedziny, czyli przykładów. W podstawowym przypadku pojęcie wyznacza podział dziedziny na zbiór przykładów pozytywnych (należących do pojęcia) i negatywnych (nienależących do pojęcia). Dopuszczalne są również pojęcia wielokrotne, które klasyfikują przykłady za pomocą większej liczby klas lub kategorii (podzbiorów dziedziny). Mówi się w tym sensie, że pojęcie przypisuje poszczególnym przykładom etykiety ich kategorii. Uczenie się pojęcia docelowego polega na konstruowaniu przez ucznia pewnej hipotezy na podstawie przykładów trenujących ze znanymi kategoriami (jest to uczenie się z nadzorem), która pozwalałaby na klasyfikowanie wszystkich przykładów z dziedziny tak samo lub prawie tak samo, jak nieznane pojęcie docelowe.
Nie zawsze zbiór klas, na jakie mogą być dzielone przykłady, jest zadany z góry. W podrozdziale tym będzie nieformalnie sformułowany problem indukcyjnego uczenia się bez nadzoru, w którym uczeń ma za zadanie zaproponowanie odpowiedniego zbioru klas i wygenerowanie reprezentującej je hipotezy, pozwalającej na klasyfikowanie za ich pomocą przykładów. Jest to problem znany jako grupowanie pojęciowe.
Zostanie tu wprowadzony nieformalnie problem indukcyjnego uczenia się z nadzorem, w którym zadaniem ucznia jest znalezienie hipotezy aproksymującej pewną nieznaną funkcję docelową, odwzorowującą dziedzinę przykładów na zbiór liczb rzeczywistych, której wartości znane są dla pewnego zbioru przykładów trenujących.
Wprowadzona będzie tu terminologia i notacja, która w dalszym ciągu rozdziału i w kilku rozdziałach następnych służyć będzie omawianiu indukcyjnego uczenia się. Terminy używane dotychczas nieformalnie (m.in. dziedzina, pojęcie, hipoteza, przykład itd.) zostaną bardziej ściśle zdefiniowane.
Pierwszym zastosowaniem wprowadzonych definicji i oznaczeń stanie się prezentacja najważniejszych wyników obliczeniowej teorii uczenia się, przede wszystkim dotyczących matematycznego modelu uczenia się pojęć na podstawie przykładów (model PAC). Wyniki te pozwalają na charakteryzowanie stopnia trudności uczenia się różnych klas pojęć oraz na szacowanie, przy pewnych założeniach, liczby przykładów i ilości obliczeń koniecznej/wystarczającej do ich nauczenia się z żądaną dokładnością. Przedstawione będą też statystyczne techniki szacowania błędów i wiarygodności hipotez oraz teoretyczne uzasadnienie tzw. zasady brzytwy Ockhama (preferencji dla prostych hipotez). Omawiane wyniki teoretyczne będą ilustrowane przykładami ich stosowania.
Do przedstawienia niektórych przykładów zostanie wykorzystany algorytm uczenia się tzw. przestrzeni wersji (możliwych hipotez zgodnych z dotychczas poznanymi przykładami trenującymi), wykorzystujący uporządkowanie hipotez ze względu na relację większej/mniejszej ogólności/szczegółowości. Algorytm ten ma raczej ograniczone znaczenie praktyczne, lecz stanowi dobrą ilustrację niektórych podstawowych zagadnień związanych z uczeniem się pojęć i jego omówienie na końcu tego rozdziału będzie wstępem do przedstawienia bardziej praktycznych algorytmów w następnych rozdziałach.
Przedstawione będą tu najważniejsze etapy rozwoju badań nad indukcyjnym uczeniem się (zwłaszcza nad rozwijaniem jego teorii) i zacytowane odpowiednie publikacje.
Ten rozdział poświęcony będzie jednemu z głównych podejść do indukcyjnego uczenia się pojęć na podstawie przykładów, w którym hipotezy reprezentowane są za pomocą drzew decyzyjnych.
Drzewo decyzyjne jest strukturą, której węzły reprezentują testy przeprowadzane na wartościach atrybutów klasyfikowanych przykładów, a liście przechowują etykiety kategorii. Gałęzie wychodzące z węzła odpowiadają różnym możliwym wynikom związanego z tym węzłem testu i prowadzą do poddrzew. Omówione zostanie i zilustrowane przykładami wykorzystanie struktur tego typu do reprezentowania hipotez, wskazane będą też zalety i wady takiej reprezentacji.
Przedstawiony tu zostanie schemat zstępującego konstruowania drzewa decyzyjnego na podstawie przykładów, którego konkretyzacjami są najczęściej stosowane algorytmy indukcji drzew decyzyjnych. Zgodnie z tym schematem konstrukcja drzewa rozpoczyna się od węzła-korzenia. Najpierw dokonuje się według pewnego kryterium wyboru testu dla tego węzła, a następnie dla każdego z możliwych wyników tego testu tworzona jest gałąź prowadzącą do poddrzewa, które konstruowane jest rekurencyjnie przez ten sam algorytm. Poszczególne konkretyzacje tego schematu różnić się mogą przede wszystkim kryteriami wyboru testów i zatrzymywania rekurencji. Przedstawione zostaną najczęściej stosowane kryteria dla obu tych decyzji, oparte na heurystykach wywodzących się ze statystyki i teorii informacji. Omówione będą możliwe rodzaje testów dla atrybutów o wartościach dyskretnych i ciągłych. Rozważane algorytmy będą ilustrowane przykładami.
W tym podrozdziale zostaną przedstawione techniki przycinania drzew decyzyjnych, mające na celu zapobieganie ich nadmiernemu dopasowaniu do danych trenujących, które mogą być obarczone pewnym błędem. Przycinanie drzew decyzyjnych jest oparte na ogólnej zasadzie brzytwy Ockhama i polega na zastąpieniu niektórych poddrzew drzewa decyzyjnego liśćmi z odpowiednio przypisanymi etykietami kategorii. Omówione będą najczęściej stosowane techniki przycinania, różniące się kryterium podejmowania decyzji o zastąpieniu poddrzewa liściem.
Wśród zagadnień związanych ze stosowaniem algorytmów indukcji drzew decyzyjnych w praktyce, które zostaną poruszone w tym podrozdziale, znajdą się m.in. sposób postępowania ze zbiorami trenującymi o dużych rozmiarach, sposób postępowania z niekompletnymi opisami przykładów (z brakującymi wartościami atrybutów) oraz modyfikacja standardowego schematu konstruowania drzewa pozwalająca na inkrementacyjne uwzględnianie nowych przykładów (przebudowę istniejącego drzewa).
Przedyskutowane tu zostaną zagadnienia związane z efektywną implementacją algorytmów indukcji drzew decyzyjnych, w tym zwłaszcza wyboru testu.
Znajdzie się tu przegląd najważniejszych prac opisujących różne algorytmy indukcji drzew decyzyjnych oraz ich udane zastosowania praktyczne.
Rozdział ten zostanie poświęcony drugiemu, obok indukcji drzew decyzyjnych, głównemu podejściu do uczenia się pojęć na podstawie przykładów -- indukcji zbiorów reguł decyzyjnych.
Reguła składa się z części warunkowej -- pewnej formuły, która może być przez opis przykładu (wartości atrybutów) spełniana lub nie -- oraz części decyzyjnej -- etykiety kategorii. Jeśli wartości atrybutów przykładu spełniają część warunkową reguły, mówi się, że reguła ta pokrywa przykład. Zbiór reguł może służyć do klasyfikowania (określania kategorii) przykładów, stanowi więc dopuszczalną reprezentację pewnej hipotezy. Będzie w tym miejscu dokładnie opisana i zilustrowana przykładami najczęściej spotykana postać części warunkowych reguł oraz możliwe sposoby wykorzystywania zbiorów reguł do klasyfikowania przykładów (m.in. klasyfikacja za pomocą uporządkowanych i nieuporządkowanych zbiorów reguł).
Jedno z najważniejszych podejść do indukcji reguł opiera się na metodzie sekwencyjnego pokrywania. Zostanie ona tu przedstawiona jako schemat, którego konkretyzacjami będą omówione dalej algorytmy. Polega on na generowaniu kolejno reguł pokrywających możliwie dużą część zbioru trenującego i charakteryzujących się możliwie dużą dokładnością (odpowiednio wiele spośród pokrytych przykładów trenujących ma kategorię zgodną z częścią decyzyjną reguły). Różne algorytmy wykorzystujące ten schemat różnią się przede wszystkim sposobem konstruowania części warunkowych generowanych reguł.
W tym podrozdziale będzie omówiona podstawowa wersja algorytmu AQ, należącego do najwcześniejszych i najbardziej znanych algorytmów opartych na schemacie sekwencyjnego pokrywania. W algorytmie tym przestrzeń możliwych warunków reguł jest przeszukiwana wiązkowo (tzn. zawsze przechowuje się określoną liczbę najlepszych dotąd kandydatów) w sposób kierowany pewnymi heurystycznymi funkcjami oceny ich jakości (na ogół uwzględniającymi liczbę pokrywanych przykładów i złożoność). Przeszukiwanie rozpoczyna się od wybrania pewnego przykładu trenującego jako tzw. ziarna i ma na celu znalezienie takich maksymalnie ogólnych warunków, które pokrywają ziarno, ale nie pokrywają żadnego przykładu o innej kategorii. Działanie algorytmu zostanie zilustrowane obszernym przykładem.
Inną konkretyzację abstrakcyjnego schematu sekwencyjnego pokrywania stanowi nieco nowszy algorytm CN2. On również stosuje wiązkowe przeszukiwanie przestrzeni warunków, lecz do kierowania tym procesem wykorzystuje pewne heurystyki teorioinformacyjne i statystyczne testy wiarygodności. Także ten algorytm będzie dokładnie opisany, a jego działanie zostanie zilustrowane przykładem.
Algorytmy oparte na sekwencyjnym pokrywaniu są przypuszczalnie najszerzej znanym, lecz nie jedynym podejściem do indukcji reguł. W tym podrozdziale znajdzie się przegląd podejść alternatywnych, w szczególności opartych na teorii zbiorów przybliżonych.
Dyskutowane tu zagadnienia będą dotyczyć m.in. przycinania reguł, postępowania z brakującymi wartościami atrybutów oraz złożoności obliczeniowej algorytmów AQ i CN2, która może niekiedy ograniczać ich stosowalność.
W tym podrozdziale rozważone będą przede wszystkim struktury danych do reprezentowania reguł pozwalające na efektywną implementację algorytmów indukcji.
Zostaną tu umieszczone i skomentowane odwołania do najważniejszych prac dotyczących algorytmów indukcji reguł i ich zastosowań.
W rozdziale tym omówione będą najważniejsze metody uczenia się oparte na wynikach teorii prawdopodobieństwa, a zwłaszcza na twierdzeniu Bayesa, odgrywającym wciąż rosnącą rolę w sztucznej inteligencji.
Będzie tu zawarta oparta na konkretnych przykładach dyskusja możliwych zastosowań wybranych elementów teorii prawdopodobieństwa do konstruowania systemów inteligentnych, w tym zwłaszcza do wnioskowania na podstawie niepewnych informacji. Czytelnicy potrzebujący przypomnienia podstaw teorii prawdopodobioństwa zostaną skierowani do jednego z dodatków.
Oddzielny podrozdział będzie poświęcony najważniejszemu dla sztucznej inteligencji i zwłaszcza maszynowego uczenia się wynikowi teorii prawdopodobieństwa, jakim jest twierdzenie Bayesa. Znajdzie się tu jego sformułowanie, dyskusja i ilustracja za pomocą przykładów. Twierdzenie to zostanie przedstawione jako podstawa mechanizmu wnioskowania o prawdopodobieństwie a posteriori hipotez na podstawie ich prawdopodobieństwa a priori oraz zaobserwowanych danych.
Wynikiem najbardziej bezpośredniego zastosowania twierdzenia Bayesa do konstruowania systemów uczących się są różnego rodzaju klasyfikatory bayesowskie: algorytmy reprezentujące swoje hipotezy za pomocą pewnych utworzonych na podstawie zbioru trenującego oszacowań rozkładów prawdopodobieństw dla wartości atrybutów i kategorii oraz klasyfikujące przykłady przez zaliczanie ich np. do najbardziej prawdopodobnych pod pewnymi warunkami kategorii. Dokładne realizacje tego ogólnego pomysłu mogą być różne i zostaną omówione przynajmniej trzy z nich, znane jako bezpośredni klasyfikator bayesowski, optymalny klasyfikator bayesowski i naiwny klasyfikator bayesowski.
Podrozdział ten poświęcony będzie innemu ważnemu sposobowi wykorzystania twierdzenia Bayesa do maszynowego uczenia się, jaki stanowią sieci bayesowskie. Węzły sieci bayesowskich odpowiadają atrybutom, a połączenia między węzłami reprezentują zależności przyczynowe między atrybutami. W każdym węźle przechowywany jest rozkład prawdopodobieństwa warunkowego dla wartości tego atrybutu przy danych wartościach atrybutów, od których on przyczynowo zależy. Sieć jako całość reprezentuje łączny rozkład prawdopodobieństwa dla wszystkich wartości wszystkich atrybutów. Dzięki temu możliwe jest przewidywanie najbardziej prawdopodobnych wartości niektórych atrybutów na podstawie znanych wartości innych atrybutów. W zależności od rodzaju dostępnej wiedzy o dziedzinie, uczeniu może podlegać bądź struktura sieci (między jakimi węzłami występują połączenia), bądź związane z poszczególnymi węzłami rozkłady prawdopodobieństwa, bądź jedno i drugie. Przedstawione zostaną algorytmy służące do realizacji tych rodzajów uczenia się i przykłady ilustrujące ich działanie.
Z twierdzeniem Bayesa wiąże się pewien coraz bardziej popularny mechanizm wnioskowania indukcyjnego, znany jako zasada minimalnej długości kodu, któremu będzie poświęcony ten podrozdział. Zasada minimalnej długości kodu, w dużym uproszczeniu, polega na interpretowaniu twierdzenia Bayesa w świetle wyników teorii informacji i kodowania. Oznacza to w szczególności zastąpienie prawdopodobieństw hipotez lub danych wyrażoną w bitach ilością informacji niezbędną do ich zakodowania, czyli właśnie długością kodu. Przyjmuje się, że zbiór trenujący ma zostać w ekonomiczny sposób zakodowany i przesłany do pewnego adresata w sposób umożliwiający jego odtworzenie. Jednym ze sposobów kodowania jest użycie komunikatów dwuczęściowych, których pierwsza część koduje pewną hipotezę, a druga część koduje przykłady przy założeniu znajomości tej hipotezy. Jeśli hipoteza jest dokładna, to zawiera ona stosunkowo kompletną informację na temat przykładów, a zatem ich zapis nie jest długi. Jeśli jednak hipoteza jest złożona, to długi jest z kolei jej zapis. Zasada minimalnej długości kodu mówi, że spośród rozważanych hipotez należy wybrać tę, która minimalizuje łączną długość dwuczęściowego komunikatu. Oprócz prezentacji tej zasady (w różnych odmianach) i ilustracji za pomocą przykładów w podrozdziale tym znajdzie się także dyskusja jej możliwych zastosowań do problemów uczenia się znanych ze wcześniejszych rozdziałów.
Zagadnienia tu omawiane dotyczyć będą m.in. możliwości stosowania przedstawionych w rozdziale algorytmów do zbiorów danych o realistycznie dużych rozmiarach, postępowania z atrybutami o wartościach ciągłych, metod ustalania prawdopodobieństw a priori dla hipotez, sposobu szacowania rozkładów prawdopodobieństw na podstawie niedostatecznie reprezentatywnych danych oraz niektórych technik kodowania.
Wśród omawianych zagadnień implementacyjnych znajdzie się m.in. unikanie błędów związanych ze skończoną precyzją liczb zmiennoprzecinkowych przy obliczaniu (małych) prawopodobieństw.
Omówiona tu będzie zmienna historia używania metod probabilistycznych w sztucznej inteligencji oraz cytowane najważniejsze prace z tego zakresu.
Rozdział ten dotyczyć będzie algorytmów tworzenia pojęć, czyli indukcyjnego uczenia się bez nadzoru.
Punktem wyjścia do omawiania metod grupowania pojęciowego będzie dyskusja znaczenia i użyteczności podziału na kategorie jako wiedzy służącej do pewnych rodzajów wnioskowania. Nieformalnie określone zostanie podstawowe kryterium oceny jakości grupowania, zgodnie z którym dobrym grupowaniem jest takie, dla którego na podstawie znajomości przynależności przykładu do kategorii można dużo wiarygodnie wywnioskować (na temat wartości atrybutów przykładu).
Pierwsza z omawianych w rozdziale metod grupowania pojęciowego stanowi pewną adaptację algorytmu AQ służącego do indukcji reguł (metoda ta wykorzystywana jest przez system CLUSTER/2). Reprezentuje ona kategorie w taki sam w zasadzie sposób, jak reprezentowane są warunki reguł. Tworzenie grupowania rozpoczyna się od wyboru pewnej liczby ziaren (przykładów ze zbioru trenującego), po czym następuje tworzenie dla każdego ziarna bardziej ogólnych opisów pokrywających ziarno i przykłady pod pewnymi względami do niego podobne. Przekształcenie tego pomysłu w poprawny algorytm wymaga rozwiązania szeregu szczegółowych problemów, które będą w tym podrozdziale dyskutowane.
W tym podrozdziale przedstawione zostanie alternatywne podejście do grupowania pojęciowego, w którym podział przykładów na kategorie reprezentowany jest za pomocą probabilistycznego drzewa klasyfikacji (metoda ta wykorzystywana jest przez system COBWEB). Każdy węzeł drzewa odpowiada pewnej kategorii, a kategorie związane z węzłami potomnymi są podkategoriami kategorii związanej z ich węzłem macierzystym (podział na kategorie jest hierarchiczny). Przechowywany w każdym węźle opis kategorii obejmuje liczbę zaliczonych do niej przykładów oraz rozkłady częstości poszczególnych wartości atrybutów wśród tych przykładów. Wartości te pozwalają na szacowanie odpowiednich rozkładów prawdopodobieństw. Drzewo takie budowane jest przez uwględnianie kolejno pojedynczych przykładów i stosowanie jednego z zestawu operatorów modyfikujących strukturę drzewa. Wybór najlepszego operatora dokonywany jest zgodnie z wartościami pewnej funkcji heurystycznej oceniającej jakość klasyfikacji.
Podrozdział ten będzie dotyczyć problemu grupowania przykładów opisywanych za pomocą atrybutów o wartościach ciągłych. Zostanie przedstawiona modyfikacja algorytmu z poprzedniego podrozdziału pozwalająca na używania atrybutów ciągłych oraz algorytm EM, służący do grupowania przykładów, których wszystkie atrybuty są ciągłe, i opisujący poszczególne kategorie za pomocą parametrów pewnego rozkładu prawdopodobieństwa (np. normalnego).
Znajdzie się tu dyskusja praktycznych zalet i ograniczeń poszczególnych algorytmów omawianych w rozdziale, w tym m.in. problemów modyfikowania istniejącego grupowania w celu uwzględnienia nowych przykładów. Przedstawione zostaną także najważniejsze zastosowania tych algorytmów jako komponentów systemów uczących się, w tym także sposób ich wykorzystania do uczenia się pojęć z nadzorem.
Podrozdział ten będzie poświęcony głównie doborowi struktur danych do efektywnej implementacji rozważanych algorytmów.
Przedstawione tu będą źródła, z których pochodzą oryginalne wersje omawianych algorytmów, oraz przegląd innych podejść do uczenia się bez nadzoru znanych z literatury.
W rozdziale tym omówione zostaną bardzo ważne w praktyce, a rzadko systematycznie prezentowane problemy przekształcania zbioru atrybutów opisujących przykłady w celu umożliwienia bądź ułatwienia stosowania algorytmów indukcyjnego uczenia się.
Przestrzeń hipotez rozpatrywanych przez system uczący się na podstawie przykładów opisanych za pomocą zestawu atrybutów zależy od używanego algorytmu uczenia się i właśnie od tego zostawu atrybutów. Celem tego podrozdziału będzie przedyskutowanie tej zależności i zilustrowanie jej za pomocą przykładów, demonstrujących wpływ zmiany zestawu atrybutów na hipotezy wybierane przez niektóre przedstawione we wcześniejszych rozdziałach algorytmy uczenia się.
Ten podrozdział poświęcony będzie najczęściej spotykanemu w praktyce przekształceniu zestawu atrybutów, dyskretyzacji atrybutów ciągłych. Niektóre algorytmy indukcyjnego uczenia się zakładają, że przykłady opisywane są wyłącznie za pomocą atrybutów dyskretnych. Niektóre inne algorytmy mogą uczyć się z użyciem również atrybutów ciągłych, lecz na ogół kosztem wyraźnego zwiększenia złożoności obliczeniowej procesu uczenia się i złożoności uzyskiwanych hipotez. To czyni metody dyskretyzacji atrybutów ciągłych ważnym, choć mało znanym działem maszynowego uczenia się. Przedstawiony będzie podział istniejących metod (m.in. na metody z nadzorem i bez nadzoru, wstępujące i zstępujące) oraz najbardziej skuteczne algorytmy. Ich działanie zostanie zilustrowane za pomocą przykładów.
Dyskretyzacja atrybutów ciągłych jest szczególnym przypadkiem przekształcania zestawu atrybutów, które w ogólnym przypadku nazywane jest konstruktywną indukcją. Konstruktywna indukcja polegać może na usuwaniu nieistotnych atrybutów lub dodawaniu nowych atrybutów, określonych na podstawie dotychczasowych. W tym podrozdziale zostaną zarysowane podstawowe podejścia do konstruktywnej indukcji, określane jako konstruktywna indukcja oparta na danych, konstruktywna indukcja oparta na hipotezach oraz konstruktywna indukcja oparta na wiedzy. Bardziej szczegółowo zostaną omówione wybrane metody konstruktywnej indukcji opartej na hipotezach, w której atrybuty do usunięcia lub dodania określa się na podstawie hipotez wygenerowanych przez wybrany algorytm uczenia się przy dotychczasowym zestawie atrybutów.
Będą tu przedyskutowane praktyczne aspekty stosowania dyskretyzacji atrybutów ciągłych (m.in. wybór metody, liczba podprzedziałów dyskretyzacji) i konstruktywnej indukcji (kiedy warto ją stosować).
Wśród omawianych zagadnień implementacyjnych znajdzie się dyskusja efektywnych technik implementacji omawianych w tym rozdziale algorytmów dyskretyzacji.
Będzie tu przedstawiony przegląd najważniejszych prac w ramach dyskretyzacji atrybutów ciągłych i konstruktywnej indukcji.
Rozdział poświęcony będzie wybranym algorytmom uczenia się aproksymacji funkcji -- odwzorowań ze zbioru przykładów na zbiór liczb rzeczywistych.
Problem aproksymacji funkcji, dotychczas wprowadzony nieformalnie, zostanie tu sformułowany bardziej ściśle.
Zostaną tu wyróżnione podstawowe rodzaje uczących się aproksymatorów, podzielone ze względu na sposób reprezentacji funkcji i tryb uczenia się. Najbardziej interesujące z nich będą następnie dokładniej omawiane w kolejnych podrozdziałach.
Ten podrozdział poświęcony będzie aproksymatorom opartym na reprezentacji parametrycznej. Zakłada się tu, że przykłady reprezentowane są za pomocą wektora rzeczywistoliczbowych atrybutów, w tym kontekście częściej nazywanych cechami, a aproksymowana funkcja za pomocą wektora parametrów nazywanych wagami, podlegających modyfikacji w trakcie uczenia się. Omówione zostaną najważniejsze aproksymatory tego typu, różniące się realizacją odwzorowania wektorów cech i wag na wartość funkcji oraz, co za tym idzie, sposobem modyfikacji wag na podstawie przykładów trenujących. Będzie mowa m.in. o prostych perceptronach, perceptronach wielowarstwowych i aproksymatorach opartych na tzw. rozszerzonej reprezentacji (m.in. RBF, CMAC).
Zostaną tu przedstawione metody aproksymacji funkcji oparte na zapamiętywaniu przykładów trenujących. Ta grupa aproksymatorów obejmuje w szczególności algorytmy najbliższych sąsiadów i lokalnej regresji.
Drzewa decyzyjme, które w podstawowej postaci służą do klasyfikowania przykładów, mogą w odpowiednio zmodyfikowanej wersji służyć także do aproksymacji funkcji. Nazywane są wówczas drzewami modelowania. Omówiony będzie sposób reprezentacji funkcji za pomocą takich drzew oraz algorytmy ich konstruowania.
Będzie tu m.in. dyskusja kryteriów doboru odpowiednich aproksymatorów dla różnych zastosowań.
W tym podrozdziale znajdą się sugestie dotyczące efektywnej implementacji niektórych spośród omawianych wcześniej algorytmów, w tym m.in. wykorzystania struktur danych znanych z geometrii obliczeniowej do przechowywania przykładów w metodach pamięciowych.
Przedstawione tu zostaną i skomentowane najważniejsze prace, z których pochodzą algorytmy przedstawione w rozdziale oraz najbardziej znane spośród innych algorytmów uczenia się aproksymacji funkcji.
Ten rozdział wprowadzi istotne rozszerzenie do paradygmatu indukcyjnego uczenia się omawianego w poprzednich rozdziałach, polegające na wykorzystaniu do reprezentowania pojęć predykatów, a do reprezentowania hipotez formuł rachunku predykatów pierwszego rzędu.
W tym podrozdziale znajdzie się omówienie sposobu wykorzystania formuł rachunku predykatów pierwszego rzędu do reprezentacji wiedzy. Zostaną podkreślone ograniczenia opisywania przykładów i wyrażania wiedzy o dziedzinie za pomocą atrybutów i zademonstrowany sposób pokonywania tych ograniczeń za pomocą rachunku predykatów. Czytelnicy nie znający podstaw tego formalizmu zostaną odesłani do jednego z dodatków, gdzie znajdą niezbędne informacje wprowadzające.
Będzie tu przedstawione rozszerzone rozumienie pojęcia jako nie tylko wiedzy o klasyfikowaniu obiektów, ale również o zachodzących pomiędzy nimi związkach. W tym nowym rozumieniu pojęcie nie jest więc już tylko jednoargumentową funkcją lub relacją klasyfikującą pojedyncze obiekty, lecz relacją o dowolnej liczbie argumentów, reprezentowaną przez n-argumentowy predykat. Odpowiednio zmodyfikowane będzie określenie przykładów, które obecnie będą n-tkami obiektów z dziedziny zamiast pojedynczymi obiektami. Zostanie wreszcie przedstawiona rozszerzona wersja reprezentacji hipotez za pomocą reguł, które przybiorą teraz postać klauzul Horna. Zbiór trenujący dla indukcyjnego programowania logicznego składa się z przykładów -- n-tek obiektów dziedziny, dla których zachodzą różne relacje. Jedna z tych relacji jest wyróżniona jako reprezentująca pojęcie docelowe. Zadaniem systemu uczącego się jest znalezienie hipotezy będącej zbiorem klauzul Horna, wyrażających definicję pojęcia docelowego za pomocą predykatów reprezentujących pozostałe relacje, których przykłady znalazły się w zbiorze trenującym. Ta forma indukcji polega zatem na wywnioskowaniu formuł logicznych opisujących relacje zachodzące w dziedzinie na podstawie przykładów tych relacji. Powstały w wyniku uczenia się zbiór klauzul może posłużyć jako baza wiedzy do wnioskowania dedukcyjnego (np. za pomocą zasady rezolucji), które jest podstawą tzw. programowania w logice -- wyjaśnia to pochodzenie nazwy rodzaju uczenia się opisywanego w tym rozdziale.
Ten podrozdział poświęcony będzie omówieniu sposobu adaptacji schematu sekwencyjnego pokrywania przedstawionego wcześniej dla indukcji reguł do problemu indukcyjnego programowania logicznego. Przedstawiony zostanie algorytm pochodzący z systemu FOIL oraz przykłady ilustrujące sposób jego działania.
Najważniejszym problemem rozważanym w tym podrozdziale będzie zapewnianie odporności indukcyjnego programowania logicznego na sprzeczności w zbiorze trenującym.
Zostaną tu przedyskutowane m.in. decyzje implementacyjne związane z maszynową reprezentacją formuł rachunku predykatów.
Znajdzie się tu przegląd najważniejszych dawnych i obecnych prac w ramach indukcyjnego programowania logicznego, które należy do najbardziej popularnych obszarów badań w ramach uczenia się maszyn w Europie.
Rozdział ten zamknie część książki poświęconą metodom indukcyjnego uczenia się omówieniem jego najważniejszego praktycznego zastosowania, jakim jest obecnie odkrywanie zależności w danych, na ogół przechowywanych w bazach danych. Będą tu przedyskutowane problemy związane z używaniem w tym celu niektórych algorytmów omawianych w poprzednich rozdziałach oraz przedstawione inne specyficzne metody odkrywania zależności.
Przedstawiony tu zostanie problem leżący u podstaw zainteresowania metodami odkrywania wiedzy w danych. Coraz liczniejsze firmy i instytucje funkcjonujące w różnych obszarach wykorzystują w swojej działalności i generują w jej wyniku coraz większe zbiory danych. Mówi się często, że w takiej powodzi danych ginie potencjalnie ukryta w nich wiedza -- jest ich zbyt dużo, aby jakakolwiek niemechaniczna metoda mogła być wystarczająca do zauważenia występujących w nich zależności i regularności. Takie zależności i regularności, na ogół zachodzące pomiędzy pewnymi atrybutami tabel (lub fragmentów tabel) w relacyjnych bazach danych, stanowią wiedzę, której odkrycie może mieć znaczenie przeliczalne na wymierne korzyści finansowe. Zajmująca się dokonywaniem takich odkryć dziedzina badań i zastosowań czerpie swoje metody z dwóch głównych źródeł: maszynowego uczenia się i statystyki.
W gruncie rzeczy wszystkie opisywane we wcześniejszych rozdziałach metody uczenia się na podstawie przykładów mogą być i bardzo często są traktowane jako metody odkrywania wiedzy w danych. W przeciwieństwie do tradycyjnych statystycznych metod analizy danych, które mogą być bardzo skutecznymi narzędziami do wykrywania korelacji między różnymi zjawiskami, odróżniania obserwacji znaczących od przypadkowych, wykrywania występujących trendów, metody uczenia się umożliwiają uzyskanie opisu odkrytych zależności w abstrakcyjnej, symbolicznej postaci, użytecznej do wyciągania wniosków -- również za pomocą automatycznych metod wnioskowania. Jednak odkrywanie wiedzy w występujących w rzeczywistości, na ogół dużych bazach danych, stanowi szczególnie wymagające zastosowanie dla algorytmów indukcyjnego uczenia się na podstawie przykładów. W tym podrozdziale zostaną omówione najważniejsze problemy, na jakie można przy próbie takich zastosowań napotkać, i możliwe podejścia do ich przezwyciężenia. Niektóre z tych problemów były już wcześniej dyskutowane dla poszczególnych algorytmów, a obecnie zostaną przedstawione w szerszej perspektywie. Mowa będzie m.in. o możliwościach redukcji dużych zbiorów danych, inkrementacyjnej aktualizacji wiedzy oraz postępowaniu z błędnymi i niekompletnymi danymi.
Nie zawsze ten rodzaj zależności, jaki może być odkryty za pomocą algorytmów uczenia się na podstawie przykładów, jest interesujący z punktu widzenia posiadacza danych. Nie zawsze też dane te charakteryzują się odpowiednio dużą regularnością, aby można było w nich odnaleźć znaczące zależności tego typu. W podrozdziale tym zostanie omówiony inny rodzaj możliwych do odkrycia zależności, które wprawdzie reprezentują wiedzę mniej dogodną do automatycznego wnioskowania, lecz mogą lepiej odpowiadać wymaganiom realnych baz danych. Zależności te dotyczą asocjacji (współwystępowania wartości atrybutów) zachodzących dla dwóch lub więcej atrybutów. Jedna z metod ich odkrywania, jakie zostaną tu przedstawione, opiera się na konstruowaniu tzw. tablic kontyngencji. Dla pary atrybutów tablica kontyngencji ma wiersze odpowiadające wszystkim wartościom (lub przedziałom wartości ciągłych) pierwszego atrybutu oraz odpowiednio kolumny dla wartości drugiego atrybutu. W polach tablicy na przecięciu każdego wiersza i kolumny wpisywana jest liczba przykładów (rekordów w bazie danych), dla których oba atrybuty mają wartości odpowiadające temu wierszowi i tej kolumnie. Do takich tablic można stosować statystyczne techniki mające na celu weryfikację, czy występują w nich znaczące wzorce, które mogą być podstawą do wyciągania wniosków. Ponieważ na ogół trudno się spodziewać, aby istotne wzorce występowały w tablicach kontyngencji tworzonych dla całej bazy danych, metody odkrywania zależności tego typu łączą analizę statystyczną tablic kontyngencji z heurystycznymi strategiami wybierania dekompozycji bazy danych na fragmenty, w których mogą występować istotne wzorce.
W przypadku atrybutów ciągłych można podjąć próbę opisania zależności między nimi za pomocą równania. Tego typu zależność, o ile uda się ją znaleźć, jest na ogół bardzo interesująca i przydatna. W podrozdziale tym zostaną przedstawione i zilustrowane za pomocą przykładów wybrane algorytmy odkrywania równań, z podziałem na służące do odkrywania równań dla dwóch atrybutów i dla więcej niż dwóch atrybutów oraz na metody odkrywania równań bez eksperymentowania i metody odkrywania równań z eksperymentowaniem. Stosowanie tych algorytmów wymaga w pierwszej kolejności przeprowadzenia statystycznego testu, który określa, czy zależność funkcyjna między atrybutami może zachodzić.
Cały rozdział ma mieć charakter dość praktyczny, w związku z tym ten podrozdział stanowić będzie jeszcze dalszy krok w stronę zastosowań. Będzie tu mowa m.in. o problemach związanych z komunikacją systemów odkrywania zależności z systemami zarządzania (przede wszystkim relacyjnymi) bazami danych.
Znajdzie się tu dyskusja zagadnień związanych z efektywną implementacją metod odkrywania zależności za pomoca tablic kontyngencji, w tym m.in. doboru struktur danych i technik ich aktualizacji podczas heurystycznego poszukiwania odpowiedniej dekompozycji zbioru przykładów.
Przedstawiony tu będzie przede wszystkim przegląd opublikowanych raportów z udanych praktycznych zastosowań metod odkrywania wiedzy w danych oraz źródła opisujące szerzej przedstawione w rozdziale algorytmy.
Ten rozdział odejdzie od paradygmatu indukcyjnego uczenia się i zwróci uwagę na pomijaną w poprzednich rozdziałach wiedzę wrodzoną ucznia -- wiedzę, w jaką system uczący się może być wyposażony przez jego konstruktora. Omawiane w tym rozdziale metody uczenia się mają na celu przekształcanie wiedzy wrodzonej i informacji trenującej w nową wiedzę, lepiej dostosowaną do potrzeb zadania, jakie wykonywać ma system.
W tym podrozdziale zostanie przydyskutowana rola wiedzy wrodzonej w procesie uczenia się. Będą zademonstrowane możliwe sposoby wykorzystania wiedzy wrodzonej dla metod indukcyjnego uczenia się.
Naszkicowana tu zostanie koncepcja nieindukcyjnego uczenia się, w którym wiedza wrodzona odgrywa kluczową rolę. W podejściu tym przyjmuje się założenie, że system uczący się może być wyposażony przez swojego projektanta w dostatecznie pełną i poprawną wiedzę na temat dziedziny jego działania. Jednak realistycznie zakłada się także, że wiedza ta wyrażona jest w postaci, w której nie może być bezpośrednio użyta przez ucznia do wykonania jego zadania -- można powiedzieć, że ma charakter "`teoretyczny'' a nie "`praktyczny''. Rolą przykładów trenujących jest wówczas pokazanie, jak ta teoria dziedziny odnosi się do niej w praktyce, co umożliwiłoby uczniowi przekształcenie jego wiedzy wrodzonej do nadającej się do bezpośredniego stosowania postaci. Mamy wówczas do czynienia z kompilacją wiedzy wrodzonej, przeprowadzaną na podstawie przykładów trenujących.
Tu przedstawiona będzie konkretna realizacja koncepcji wprowadzonej w poprzednim podrozdziale, znana jako metoda generalizacji na podstawie wyjaśnień. Uczeń wyposażony jest w wiedzę wrodzoną wyrażoną za pomocą formuł rachunku predykatów pierwszego rzędu (lub jego podzbioru). Do opisu dziedziny wykorzystywany jest pewien zestaw predykatów odpowiadających określonym na obiektach tej dziedziny relacjom, z których jedna reprezentuje pojęcie docelowe. Teoria dziedziny zawiera kompletną i poprawną definicję pojęcia docelowego, lecz definicja ta nie jest użyteczna praktycznie -- oznacza to na ogół, że wykorzystuje pewne trudne do wartościowania relacje lub wymaga wielu kroków wnioskowania. Przykładem trenującym jest n-tka obiektów dziedziny, dla których spełniona jest relacja reprezentująca pojęcie docelowe i które opisane są za pomocą łatwych do wartościowania innych relacji określonych na dziedzinie. Metoda generalizacji na podstawie wyjaśnień obejmuje dwa podstawowe kroki. W pierwszym przeprowadza się dowód poprawności przykładu, czyli tego, że z teorii dziedziny wynika na drodze dedukcji jego przynależność do pojęcia docelowego. Dowód taki może być przeprowadzony za pomocą znanych dedukcyjnych metod automatycznego wnioskowania w rachunku predykatów (np. zasady rezolucji). Drugi krok to uogólnienie dowodu, które polega na wybraniu tych i tylko tych elementów opisu przykładu, które są koniecznymi i wystarczającymi przesłankami tego dowodu, a następnie na uogólnieniu tych przesłanek przez usunięcie niepotrzebnych wiązań zmiennych. Dla obydwu kroków metody zostaną zapisane szczegółowe algorytmy, których działanie będzie zilustrowane za pomocą przykładów.
Jednym z godnych uwagi zastosowań ogólnej metody uczenia się na podstawie wyjaśnień jest użycie jej do uczenia się makrooperatorów w rozwiązywaniu problemów. Zostanie tu przedstawiony typowy paradygmat rozwiązywania problemów w sztucznej inteligencji, zgodnie z którym problem definiowany jest przez przestrzeń stanów z wyróżnionymi stanami docelowymi oraz przez zbiór operatorów, które prowadzą do zmiany stanów. Rozwiązanie problemu polega na znalezieniu sekwencji operatorów, której zastosowanie spowoduje przejście ze stanu początkowego do jednego ze stanów docelowych. Taka sekwencja operatorów może być nazwana makrooperatorem. Przedstawiony będzie sposób uczenia się makrooperatorów na podstawie wyjaśniania udanego zastosowania sekwencji operatorów za pomocą teorii dziedziny, definiującej działanie operatorów w języku predykatów, oraz przykład zastosowania tego podejścia do konkretnego problemu.
Najważniejsze zagadnienia praktyczne, jakie zostaną tu poruszone, to możliwy sposób postępowania z niepoprawnymi teoriami dziedziny oraz wykorzystywania przykładów negatywnych.
Zostanie tu m.in. przedyskutowana możliwość implementacji uczenia się na podstawie wyjaśnień z wykorzystaniem systemów wnioskowania dedukcyjnego i w szczególności języka Prolog.
Umieszczony tu będzie przegląd prac dotyczących algorytmów uczenia się na podstawie wyjaśnień i ich zastosowań do rozwiązywania problemów.
Będzie to rozdział poświęcony uczeniu się zupełnie innego rodzaju wiedzy, niż będąca przedmiotem zainteresowania w poprzednich rozdziałach wiedza o klasyfikacji przykładów, odwzorowaniu ich na liczby rzeczywiste lub o zachodzących pomiędzy nimi relacjach -- wiedzy reprezentowanej za pomocą maszyn abstrakcyjnych nazywanych automatami skończonymi.
Podrozdział ten służyć będzie przedstawieniu definicji automatu skończonego oraz możliwości wykorzystania go do reprezentowania języka formalnego (z klasy języków regularnych) oraz do modelowania środowiska. Podane zostaną przykłady ilustrujące te zastosowania automatów skończonych. Sformułowany zostanie także problem uczenia się automatów w wariantach zależnych od zakładanego rodzaju dostępnej informacji trenującej.
Będzie tu opisany klasyczny już algorytm L* służący do dokładnego uczenia się automatów skończonych na podstawie zapytań. Zakłada się, że uczeń ma do dyspozycji dwa rodzaje zapytań: o przynależność (czy dany napis należy do języka rozpoznawanego przez automat) i o równoważność (czy dany automat jest równoważny automatowi docelowemu). Działanie algorytmu L* zostanie zilustrowane szczegółowo komentowanym przykładem.
Założenia o dostępności zapytań o przynależność i równoważność są dla wielu interesujących zastosowań metod uczenia się automatów zbyt silne. W tym podrozdziale przedstawione będą algorytmy, które mogą służyć do uczenia się automatów wyłącznie na podstawie pewnej ograniczonej wersji zapytań o przynależność, które lepiej jest nazywać eksperymentami. Zostanie w szczególności omówiony algorytm znajdowania i wykorzystania tzw. sekwencji sprowadzających -- napisów, których odczytanie przez automat sprowadza go do określonego stanu.
Będzie tu szerzej omówiona możliwość wykorzystania algorytmów uczenia się automatów na podstawie eksperymentów do identyfikacji nieznanego środowiska. Przed takim problemem stoi na przykład robot, którego sensory dostarczają mu jedynie częściowej informacji o jego aktualnym położeniu i sytuacji.
Wśród dyskutowanych tu problemów znajdzie się problem uczenia się automatów niedeterministycznych oraz uczenia się automatów przy możliwości wystąpienia przekłamań obserwacji eksperymentalnych.
Znajdą się tu uwagi dotyczące przede wszystkim doboru struktur danych umożliwiających efektywną implementację algorytmów uczenia się automatów.
Przedstawiony tu będzie przegląd najważniejszych wyników teoretycznych dotyczących uczenia się automatów i algorytmów alternatywnych w stosunku do omówionych wcześniej w tym rozdziale.
Ten rozdział przyniesie kolejną znaczącą zmianę rozważanego paradygmatu uczenia się. O ile poprzednie rozdziały mają być poświęcone w większości uczeniu się z nadzorem i niekiedy uczeniu się bez nadzoru, obecny rozdział dotyczyć będzie rodzaju uczenia się nie dającego się zaklasyfikować do żadnej z tych grup. System uczący się ze wzmocnieniem otrzymuje wartościującą informację trenującą i na podstawie tej informacji oraz interakcji ze środowiskiem ma nauczyć się sekwencyjnego podejmowania decyzji, czyli pewnej umiejętności.
Sformułowany to zostanie nieformalnie problem uczenia się ze wzmocnieniem, w którym uczeń odbywa serię interakcji ze środowiskiem zgodnych ze stałym podstawowym scenariuszem. W każdym kroku czasu obserwuje on aktualny stan środowiska, wybiera i wykonuje pewną akcję, po czym obserwuje jej konsekwencje w postaci rzeczywistoliczbowej nagrody (wzmocnienia) i następnego stanu. Jego zadaniem jest nauczenie się strategii decyzyjnej, czyli odwzorowania stanów na akcje do wykonania w tych stanach, która prowadzi do długoterminowej maksymalizacji uzyskiwanych nagród.
W tym podrozdziale przedstawiony będzie matematyczny model problemu uczenia się ze wzmocnieniem, jakim jest proces decyzyjny Markowa. Jest on definiowany przez podanie zbioru stanów, zbioru akcji, funkcji nagród i funkcji przejść. Funkcja nagród każdej parze stan-akcja przyporządkowuje zmienną losową oznaczającą nagrodę generowaną po wykonaniu tej akcji w tym stanie. Funkcja przejść każdej parze stan-akcja przyporządkowuje zmienną losową oznaczającą następny stan po wykonaniu tej akcji w tym stanie. Podkreślone będzie znaczenie własności Makowa, zgodnie z którą wartości funkcji nagród i przejść zależą wyłącznie od aktualnego stanu i akcji (nie ma żadnej ukrytej zależności od historii poprzednich stanów, akcji i nagród). Przedstawione i zilustrowane przykładami będą definicje strategii, funkcji wartości (wartościującej stany przy ustalonej strategii) i funkcji wartości akcji (wartościującej pary stan-akcja przy ustalonej strategii).
W przypadku znajomości oczekiwanych wartości nagród i prawdopodobieństw przejść dla wszystkich stanów i akcji jest możliwe (chociaż nie zawsze opłacalne) znalezienie optymalnej strategii dla procesu decyzyjnego Markowa za pomocą metod programowania dynamicznego. Przedstawione tu zostaną podstawy teorii programowania dynamicznego, w tym różne wersje równania Bellmanna, oraz oparte na nich algorytmy, których działanie będzie zilustrowane przykładami.
Podrozdział ten stanowić będzie wstęp do przedstawienia podstawowych algorytmów uczenia się ze wzmocnieniem. Będzie tu mowa o uczeniu się funkcji wartości dla ustalonej strategii na podstawie interakcji ze środowiskiem. Omówione zostaną używane do tego celu metody różnic czasowych w najprostszej wersji TD(0).
Przedstawione tu będą możliwe sposoby wykorzystania metod różnic czasowych do uczenia się strategii, polegające na połączeniu uczenia się funkcji wartości lub funkcji wartości akcji dla aktualnej strategii z jednoczesnym modyfikowaniem tej strategii. Podane zostaną realizujące tę koncepcję konkretne algorytmy AHC, Q-learning i Sarsa oraz przykłady ilustrujące ich działanie.
Znajdzie się tu dyskusja różnych mechanizmów wyboru akcji podczas uczenia się ze wzmocnieniem, łączących eksploatację (działanie w celu pozyskania nagród) i eksplorację (działanie w celu pozyskania wiedzy). Omówione będą proste strategie probabilistyczne oraz bardziej zaawansowane podejścia wykorzystujące liczniki częstości odwiedzin poszczególnych stanów i wykonania poszczególnych akcji.
Przedstawiony tu zostanie problem reprezentacji funkcji (wartości, wartości akcji, strategii) w systemach uczących się ze wzmocnieniem oraz możliwość wykorzystania w tym celu uczących się aproksymatorów funkcji, opisanych w jednym z wcześniejszych rozdziałów.
Podrozdział ten poświecony będzie możliwości przyspieszenia uczenia
się ze wzmocnieniem za pomocą bardziej zaawansowanych wersji metod
różnic czasowych, TD
dla 
. Przedstawiony
zostanie standardowy algorytm TD oparty na śladach
aktywności stanów i sposób jego połączenia z podanymi wcześniej
algorytmami uczenia się ze wzmocnieniem (AHC, Q-learning, Sarsa), a
także proste rozważania teoretyczne i przykłady służące lepszemu
zrozumieniu omawianych technik.
Znajdzie się tu przegląd najbardziej obiecujących obszarów zastosowań algorytmów uczenia się ze wzmocnieniem, m.in. do optymalnego sterowania, programów grających w gry planszowe, konstruowania inteligentnych robotów i optymalizacji kombinatorycznej. Niektóre ze szczególnie udanych zastosowań będą opisane bardziej szczegółowo.
Wymienione tu będą i zwięźle przedyskutowane najważniejsze problemy badawcze występujące we wciąż bardzo młodej dziedzinie uczenia się ze wzmocnieniem. Mowa będzie m.in. o problemie ukrytego stanu (środowisk niemarkowowskich), aktywnej percepcji, efektywnej eksploracji, uwzględnianiu wiedzy wrodzonej i łączeniu uczenia się z planowaniem.
Treść tego podrozdziału stanowić będzie rodzaj krótkiego poradnika wyjaśniającego problemy pojawiające się przy praktycznych zastosowaniach algorytmów uczenia się ze wzmocnieniem.
Poruszone tu zostaną problemy związane z efektywną implementacją
algorytmów opartych na TD.
Będą tu wymienione najważniejsze publikacje, które wpłynęły na rozwój uczenia się ze wzmocnieniem i które wyznaczają kierunki przyszłych prac.
W tym rozdziale przedstawione zostaną możliwości zastosowania algorytmów ewolucyjnych -- technik optymalizacji i przeszukiwania inspirowanych mechanizmami doboru naturalnego i genetyki -- do wybranych problemów uczenia się spośród przedstawionych we wcześniejszych rozdziałach.
Podrozdział ten stanowić będzie niezwykle zwięzłe wprowadzenie do obliczeń ewolucyjnych. Zostanie przedstawiona koncepcja przeszukiwania przestrzeni rozwiązań przez przetwarzanie populacji osobników za pomocą operatorów genetycznych i ocenianie ich jakości za pomocą funkcji dopasowania. Podane będą przykłady operatorów dla różnych reprezentacji osobników oraz najważniejsze techniki stosowane do realizacji reprodukcji (następstwa pokoleń populacji) z selektywnym naciskiem (premiowaniem osobników lepiej dopasowanych).
Będzie tu opisane najwcześniejsze i wciąż najlepiej znane podejście do wykorzystania algorytmów ewolucyjnych do uczenia się. Polega ono na konstruowaniu systemów, nazywanych systemami klasyfikatorowymi, których genetycznie przetwarzana populacja składa się z prostych reguł decyzyjnych. System klasyfikatorowy jest w gruncie rzeczy systemem uczącym się ze wzmocnieniem: jego zadaniem jest reagowanie na obserwowane komunikaty wejściowe takimi akcjami, które prowadzą do długoterminowej maksymalizacji otrzymywanych nagród. Wybór akcji następuje na podstawie reguł pokrywających komunikat wejściowy. Z każdą regułą związana jest rzeczywistoliczbowa ocena jej jakości, nazywana siłą, aktualizowana na podstawie nagród za pomocą algorytmu brygady kubełkowej, i używana do wyznaczenia wartości funkcji dopasowania reguły. Podana będzie podstawowa wersja algorytmu brygady kubełkowej i przykład jej działania oraz przedyskutowane będą jej możliwe rozszerzenia. Zademonstrowane będzie także podobieństwo tego algorytmu do algorytmu TD(0) znanego z poprzedniego rozdziału.
Większość problemów uczenia się można potraktować jako problemy przeszukiwania przestrzeni hipotez. Z drugiej strony, algorytmy ewolucyjne są sprawdzonym w wielu zastosowaniach narzędziem przeszukiwania i optymalizacji. Na tej obserwacji opiera się koncepcja wykorzystania przeszukiwania genetycznego do różnych rodzajów indukcyjnego uczenia się, której poświęcony będzie ten podrozdział. Szczególnie obiecujące jest przy tym użycie zasady minimalnej długości kodu do wyznaczania wartości funkcji dopasowania dla hipotez. Ta ogólna koncepcja będzie skonkretyzowana m.in. dla problemu indukcji drzew decyzyjnych, indukcji reguł, grupowania pojęciowego i uczenia się automatów.
Przedyskutowane tu zostaną niektóre występujące w praktyce problemy związane z algorytmami ewolucyjnymi i ich zastosowaniami do uczenia się, takie jak przedwczesna zbieżność i właściwy dobór parametrów.
Będzie tu mowa o technikach stosowanych do implementacji algorytmów ewolucyjnych, w tym o odpowiednich strukturach danych oraz możliwości wykorzystania istniejących bibliotek.
Znajdą się tu odwołania do najważniejszych prac z dziedziny algorytmów ewolucyjnych i ewolucyjnych systemów uczących się.
Rozdział zamykający główną część książki będzie próbą podsumowania zawartych w niej treści oraz wskazania aktualnych problemów w dziedzinie systemów uczących się, którymi zajmują się naukowcy i praktycy.
Dyskutowane w poprzednich rozdziałach zagadnienia praktyczne związane z omawianymi tam algorytmami uczenia się zostaną tu uzupełnione ogólniejszym podsumowującym rozważaniem na temat drogi, jaką należy przejść od przedstawionych w książce algorytmów do systemów uczących się zdolnych do działania w realistycznych zastosowaniach. Zarysowana zostanie koncepcja systemów hybrydowych, integrujących różne rodzaje i algorytmy uczenia się.
Będą tu wymienione kierunki badań, z którymi wiąże się największe nadzieje na postęp w dziedzinie uczenia się maszyn.
Podrozdział ten stanowić będzie przegląd wdrożonych praktycznych zastosowań systemów uczących się.
Znajdzie się tu krótka dyskusja zamykająca książkę.
Część materiału o charakterze pomocniczym znajdzie się w kilku umieszczonych poza głównym tekstem dodatkach.
W tym dodatku zamieszczone zostaną rozwiązania do wszystkich ćwiczeń tradycyjnych oraz wskazówki do wszystkich ćwiczeń laboratoryjnych.
Będą tu streszczone podstawowe wiadomości z zakresu teorii prawdopodobieństwa, które mogą ułatwić lekturę kilka bardziej teoretycznych fragmentów książki.
Znajdzie się tu skrótowe wprowadzenie do rachunku predykatów pierwszego rzędu, zawierające wiadomości wykorzystywane przez niektóre rozdziały książki.
Znajdą się tu szczegółowe instrukcje posługiwania się wszystkimi dostarczanymi wraz z książką programami oraz wskazówki dotyczące dostępu do interpreterów języka Common Lisp i posługiwania się nimi.
W tym dodatku zamieszczone będzie skrótowe omówienie podstaw języka Common Lisp na poziomie niewystarczającym wprawdzie do samodzielnego pisania nietrywialnych programów, ale umożliwiającym rozumienie kodu źródłowego programów towarzyszących książce i wykonywanie w nich prostych modyfikacji.
Systemy uczące się
Konspekt książki
This document was generated using the LaTeX2HTML translator Version 96.1-h (September 30, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 -no_navigation -html_version 3.0 konspekt.
The translation was initiated by Pawel Cichosz on Sat Sep 12 00:19:26 CEST 1998