UNIWERSYTET WARSZAWSKI
Wydział Matematyki, Informatyki i Mechaniki
Autoreferat rozprawy doktorskiej
Marcin S. Szczuka
Promotor:
Prof. dr hab. Andrzej Skowron
W życiu codziennym co chwila dokonujemy oceny otoczenia i podejmujemy decyzje na podstawie klasyfikacji obserwowanej sytuacji. Czynimy to w oparciu o obserwację otoczenia, napływającą z różnych źródeł informację oraz posiadaną wiedzę i zdolności. Jest to dla nas czynność całkowicie naturalna. Jeżeli jednak zechcemy podobne zadania zlecić systemowi komputerowemu musimy wykonać wiele kroków, które pozwolą przynajmniej w części odwzorować przy pomocy oprogramowania ludzką zdolność do obserwacji, uczenia się, wyciągania wniosków w oparciu o posiadaną wiedzę i osiągania ostatecznej decyzji. Wzrastający rozmiar i poziom komplikacji informacji jaka otacza nas w codziennym życiu wywołał rosnące zapotrzebowanie na systemy przetwarzania danych zdolne do wyuczenia się klasyfikacji prezentowanych im obiektów. Wyzwania jakie stają przed konstruktorami systemów wspomagających klasyfikację stymulowały powstanie i rozwój wielu dziedzin badań. Można wśród nich wymienić sztuczne sieci neuronowe [4], sytemy maszynowego uczenia (ang. machine learning)[9], systemy ekspertowe (ang. expert systems) [5], drzewa decyzyjne [10], nowoczesne metody uczenia statystycznego (ang. statistical learning theory)[14], a także niektóre z metod stosowanych w odkrywaniu wiedzy i eksploracji danych (ang. knowledge discovery and data mining)[2].
Choć cele dla wielu dziedzin są zbieżne, metody ich osiągania często zasadniczo się różnią między sobą. Następstwem takiej dywersyfikacji są różnice występujące między wynikami uzyskiwanymi dla tych samych zbiorów danych (patrz [8]). Jednocześnie postępujące zrozumienie zjawisk występujących przy konstruowaniu różnego rodzaju klasyfikatorów pozwoliło badaczom wyróżnić wiele analogii i współzależności występujących pomiędzy różnymi metodami. Obserwacje te zapoczątkowały rozważania nad łączeniem elementów różnych podejść w systemy zwane hybrydowymi. Systemy takie wykorzystują elementy kilku metodologii do stworzenia klasyfikatora, który przejmie najlepsze cechy systemów wchodzących w jego skład przy jednoczesnym uwolnieniu się (przynajmniej częściowo) od ich ograniczeń (patrz [7]).
Jedną z dziedzin, która często pojawia się w kontekście systemów hybrydowych są sztuczne sieci neuronowe. Jednocześnie, wykorzystanie wraz z siecią neuronową innych metod takich jak systemy ekspertowe [7], drzewa decyzyjne [13], zbiory rozmyte [12] etc., pozwala uwolnić się od głównych niedostatków sieci neuronowych, którymi są: brak efektywnej i uniwersalnej metody wyboru struktury sieci dla zadanego problemu oraz niska przejrzystość (intuicyjna zrozumiałość) uzyskanego modelu klasyfikacji (patrz [6]).
Inny rodzaj systemów, pokrewny hybrydowym, to klasyfikatory zespołowe (złożone, wielostopniowe, ang. coupled classifiers [3]). W systemach tych wykorzystuje się zestawy klasyfikatorów w ten sposób, że informacja na wyjściu jednego z elementów trafia na wejście kolejnego. W ten sposób na każdym kolejnym etapie wejściem jest informacja o występowaniu (lub nie) w naszych pierwotnych danych pewnych własności wyższego rzędu, reprezentowanych przez wstępną klasyfikację dokonaną w poprzednich etapach.
Wyniki zawarte w pracy
Zasadnicze wyniki zamieszczone w rozprawie dotyczą dwu metod konstrukcji systemów klasyfikacyjnych (klasyfikatorów) wykorzystujących połączenie metod symbolicznych i sztucznych sieci neuronowych.W pierwszej z nich dokonywana jest synteza architektury sieci neuronowej w oparciu o drzewo decyzyjne zbudowane z wykorzystaniem algorytmu wyznaczającego podział przestrzeni za pomocą hiperpłaszczyzn (patrz [11], [10]). W algorytmie tym stosowane są metody ewolucyjne i wnioskowanie boolowskie. Jak to zostało wykazane w pracy, struktura otrzymana w wyniku działania takiego algorytmu może zostać zakodowana w postaci jednokierunkowej sieci neuronowej o dwu warstwach ukrytych. Ma to istotne znaczenie praktyczne, gdyż pomimo dużych potencjalnych możliwości aproksymacyjnych sieci, o czym można się przekonać na podstawie twierdzeń zamieszczonych w pierwszej części pracy, zagadnienie znajdowania architektury sieci neuronowej dobrze pasującej do konkretnego zadania nie znalazło dotąd ogólnego rozwiązania. Wykorzystanie klasyfikatora symbolicznego jako prototypu dla sieci neuronowej pozwala uniknąć, częstokroć skomplikowanego i kosztownego etapu poszukiwania metodą prób i błędów właściwej liczby neuronów i ich ułożenia. Ponadto, dzięki dobrym właściwościom metod znajdowania klasyfikatora symbolicznego sieć skonstruowana na jego podstawie charakteryzuje się umiarkowanym rozmiarem, co jest zaletą w stosunku do innych podejść (patrz np. [13]). Następnie przedyskutowane zostały metody modyfikacji tak uzyskanej sieci. Przedstawione zostały sposoby dostrajania funkcji aktywacji i wartości wag dla poszczególnych neuronów w zależności od ich roli w klasyfikatorze neuronowym. Omówione zostały możliwości uczenia takiej sieci neuronowej wraz ze wskazaniem sposobów dobierania właściwej postaci funkcjonału błędu, odpowiedniej wartości współczynnika uczenia i adekwatnej strategii nauki. Podane zostały kryteria pozwalające ocenić czy w wyniku uczenia nastąpiła poprawa jakości i elastyczności rozwiązania. Przedstawione zostały konsekwencje procesu uczenia z punktu widzenia zachowania możliwości interpretacji działania sieci w terminach hiperpłaszczyzn i reguł decyzyjnych (drzewa decyzyjnego), charakterystycznych dla wyjściowego kasyfikatora symbolicznego. Taka interpretacja pozwala na wyjaśnienie przyczyn które wpłynęły na podjęcie okreslonej decyzji w procesie klasyfikacji z wykorzystaniem sieci neuronowej w sposób intuicyjnie zrozumiały. Jest to znaczaco wygodniejsze i wymaga wykorzystania mniejszej liczby parametrów niż interpretowanie zasady działania dowolnej wyuczonej sieci neuronowej. Przedyskutowane także zostały sposoby nakładania ograniczeń w procesie uczenia zmodyfikowanej sieci neuronowej, prowadzące do zachowania jednoznacznego związku z pierwotną strukturą klasyfikatora opartego na hiperpłaszczyznach i drzewach decyzyjnych.
Druga matoda opiera się na wykorzystaniu prostych struktur sieci neuronowych w celu rozstrzygania konfliktów pojawiających się między regułami decyzyjnymi uzyskiwanymi przy wykorzystaniu metod zbiorów przybliżonych [1]. Problem ten jest istotnie związany z możliwościami wykorzystania w sposób efektywny reguł, które ze względu na przystępną i intuicyjną postać stanowią dobry sposób reprezentowania wiedzy zawartej w danych. Wykorzystanie w tym celu sieci neuronowej niesie ze sobą potencjalne korzyści w stosunku do wcześniej używanych metod. Dotychczasowe podejścia do rozstrzygania konfliktów opierały się na zastosowaniu jednego z modeli, ustalanego w chwili rozpoczęcia tworzenia klasyfikatora. W takim procesie tworzenia klasyfikatora parametry używanego modelu są ustalane na stałe. W przypadku wykorzystania w tym miejscu sieci neuronowej istnieje możliwość dostosowywania modelu do danych poprzez uczenie sieci. Ponadto można wykorzystać charakterystyczną dla sieci neuronowych elastyczność i odporność na zaszumienie danych. Zbadane zostały też możliwości wykorzystania adaptacyjnych własności sieci neuronowej w celu znajdowania możliwie najmniejszego zbioru reguł, wystarczającego do dokonania prawidłowej klasyfikacji. Pokazane zostały związki zaproponowanego podejścia z innymi metodami wykorzystywanymi przy rozstrzyganiu konfliktów, takimi jak głosowanie (ang. voting) dokonywane w oparciu o różnorodne miary wiarygodności dla zbiorów reguł (patrz [1],[9]). Wykorzystane metody konstruowania sieci pozwalają na bezpośrednią interpretację wartości wag dla poszczególnych neuronów w terminach wpływu, jaki mają konkretne reguły (czyli zależności między cechami obiektów) na podjęcie ostatecznej decyzji. Jest to wyjście na przeciw postulatom dotyczącym tworzenia klasyfikatorów zespołowych zawartym w [3], gdyż używając łącznie prostszych i mniejszych struktur charakterystycznych dla dwóch dziedzin jesteśmy w stanie uzyskać poziom jakości klasyfikacji właściwy znacznie bardziej skomplikowanym systemom w przypadku stosowania poszczególnych podejść osobno.
Wspomniane powyżej rezultaty zostały przedstawione na tle podstawowych wyników i metod pochodzących z dziedzin, których dokonania weszły w skład rozwiązań zaproponowanych w pracy. W szczególności zostały zaprezentowane:
- Podstawowe twierdzenia orzekające o możliwości
skonstruowania sieci neuronowej w ogólnym przypadku rozwiązywania
zadania aproksymacji funkcji decyzyjnej (klasyfikacyjnej).
Twierdzenia to dotyczą zarówno przypadku ogólnego jak i sieci
neuronowych wykorzystujących sigmoidalne funkcje aktywacji
często stosowane w praktyce ze względu na dobre własności
algorytmiczne. W części przypadków fakty zostały uzupełnione
dowodami (lub szkicami dowodów) w celu lepszego zobrazowania
występujących w nich mechanizmów.
- Wyniki dotyczące aspektów złożonościowych prezentowanych
metod. Przytoczony został rezultat orzekający o dużej złożoności
(NP-trudności) zadania konstrukcji sieci w przypadku rozpatrywania
problemu doboru wag w kategoriach klasycznej teorii złożoności
obliczeniowej. Podane zostało także nowe oszacowanie złożoności
zadania uczenia sieci pochodzące z teorii uczenia algorytmicznego
(ang. Computational Learning Theory - COLT) i
wykorzystujące pojęcie wymiaru Vapnika-Czerwonenkisa. jest
to rozszerzenie wyników z [14]. Wykazane zostało także
w oparciu o to oszacowanie, że dzięki wykorzystaniu klasyfikatora
opartego o hiperpłaszczyzny mamy potencjalnie, zgodnie z
COLT, ułatwione zadanie. Wyznaczone bowiem zostało w pracy
oszacowanie wymiaru Vapnika-Czerwonenkisa dla zbioru
hiperpłaszczyzn. Pokazuje ono wyższość tej metody nad
bezpośrednim podejściem do konstruowania sieci neuronowej w
ogólnej postaci.
- Omówienia standardowych technik stosowanych przy
rozstrzyganiu konfliktów występujących w rodzinach reguł
decyzyjnych. Przytoczone zostały w zarysie podejścia oparte o
miary wiarygodności dla pojedynczych reguł i ich zbiorów.
Zaprezentowane zostały także podstawowe podejścia do zagadnień
takich jak filtracja i skracanie w bazie reguł.
Bibliografia
- [1]
- Bazan J., Metody wnioskowań aproksymacyjnych dla syntezy
algorytmów decyzyjnych, praca doktorska, Wydział Matematyki, Informatyki i
Mechaniki Uniwersytetu Warszawskiego, Warszawa, 1998
- [2]
- Cios K., Pedrycz W., Świniarski R., Data mining methods for knowledge
discovery, Kluwer, Norwell MA, 1998
- [3]
- Dietterich T., Machine learning research - four current
directions,
AI Magazine, vol. 18 nr 4, 1997, str. 97-136
- [4]
- Fiesler E., Beale R.(ed.), Handbook of neural computation,
Oxford University Press, Oxford, 1997
- [5]
- Jackson P., Introduction to expert systems, Addison-Wesley,
Reading MA, 1999
- [6]
- De Jong G.(ed.), Investigating explanation-based learning,
Kluwer, Dordrecht, 1993
- [7]
- Medsker R. M., Hybrid neural networks and expert systems,
Kluwer, Dordrecht, 1994
- [8]
- Michie D., Spiegelhalter D.J., Taylor C.C.(eds.), Machine learning,
neural and statistical classification, Ellis Horwood, London, 1994
- [9]
- Mitchell T., Machine Learning, McGraw-Hill, New York,
1997
- [10]
- Murthy S.K., Kasif S., Salzberg S., A System for Induction of
Oblique Decision Trees, Journal of Artificial Intelligence
Research 2:1, 1994, str. 1-32
- [11]
- Nguyen Hung Son, Discretization of real value attributes:
Boolean Reasoning Approach, praca doktorska, Wydział Matematyki,
Informatyki i Mechaniki UW, Warszawa, 1997
- [12]
- Pal S.K., Mitra S., Neuro-fuzzy pattern recognition: methods
in soft computing, Wiley, Chichester, 1999
- [13]
- Shavlik J., Combining symbolic and neural learning,
Machine Learning, vol. 14 nr 2, 1994, str. 321-331
- [14]
- Vapnik V. N., Statistical learning theory, Wiley, New York, 1998