Rozdział 6
Wprowadzenie do genetycznych systemów uczących się
Pięć rozdziałów wcześniej rozpoczęliśmy wędrówkę w świat algorytmów genetycznych z myślą o ostatecznym celu, jakim jest zrozumienie odporności - uniwersalności i skuteczności zarazem - metod genetycznych w zastosowaniu do samouczenia i samosterowa-nia. Z pewnego punktu widzenia nasze zainteresowanie zastosowaniem algorytmów genetycznych w zagadnieniach poszukiwania i optymalizacji było odejściem od zasadniczego celu, gdyż, jak dobrze wiemy, metodyka optymalizacji jest zbyt sztywna, byśmy mogli proces optymalizacji powierzyć samemu sobie nawet w zupełnie prostych przypadkach. Z innego punktu widzenia, zbadanie zachowania się algorytmów genetycznych w zagadnieniach poszukiwania i optymalizacji służyło bardziej ambitnemu celowi, który wytyczyliśmy, z dwóch powodów. Po pierwsze te przedszkolne zabawy w poszukiwanie dały nam możliwość precyzyjnej kontroli "środowiska", w którym działa algorytm genetyczny, jak i samych operacji genetycznych, dzięki czemu mogliśmy przeprowadzić dokładną "sekcję" algorytmu genetycznego i jego sposobu działania. Po drugie, rozważając rozmaitość zastosowań algorytmów genetycznych w zagadnieniach poszukiwania, mieliśmy możność zaobserwować ich naturalną zdolność szybkiego przeszukiwania dowolnych przestrzeni ciągów kodowych.
O co więc chodzi? Dlaczego nie możemy po prostu wypróbować tej umiejętności w bardziej skomplikowanych, mniej wyraźnie określonych środowiskach? Problem leży nie w samych algorytmach genetycznych, ale w strukturach, które chcemy poddać adaptacji. W tym rozdziale pokażemy, jak można przezwyciężyć tę trudność, zmieniając adaptowaną strukturę. Opisujemy systemy uczące się, w których podstawowy mechanizm heurystyczny jest oparty na poszukiwaniu genetycznym. Dajemy też krótki przegląd początków genetycznych systemów uczących się [genetic-based machinę learning systems] (systemów GBML) i omawiamy najczęściej stosowaną architekturę GBML, tak zwane systemy klasyfikujące [classifier systems\. Działaniu systemu klasyfikującego poświęcimy nieco więcej uwagi; podamy także implementację elementarnego systemu kla-
6.1. Skąd wzięty się systemy GBML .
233
syfikującego w Pascalu. Na koniec przetestujemy działanie tego systemu na prostym przykładzie uczenia się funkcji boolowskiej.
6.1. Skąd wzięty się systemy GBML
Teoretyczne podstawy systemów GBML zostały wypracowane przez Hollanda (1962c). Przedstawiając zarys teorii systemów adaptacyjnych, poświęcił on szczególną uwagę sprawie replikacji programów. Chociaż późniejsze zastosowania algorytmów genetycznych w latach sześćdziesiątych dotyczyły głównie zagadnień poszukiwania i optymalizacji, zamysł teoretyczny nie był tak ograniczony.
Na tym fundamencie teoretycznym, i przy uwzględnieniu podstawowej roli rekombinacji (Holland, 1965), wyłoniły się bardziej konkretne sugestie serii projektów coraz bardziej zlożonychprocesorów schematów (Holland, 1971). Konferencja, na której przedstawiono tę pracę (1968), wyprzedziła pierwsze zastosowanie systemu klasyfikującego (Holland i Reitman, 1978) o całe dziesięciolecie. Nic więc dziwnego, że współczesne systemy klasyfikujące przypominająprocesory schematów zarówno w ogólnym zarysie,jak i w szczegółach. Pierwotny projekt Hollanda obejmował cztery prototypowe systemy. Prototyp I był to procesor typu bodziec-reakcja, który przyporządkowywał schematom środowiskowym (będziemy je wkrótce nazywać warunkami) określone działania efektorów. Prototyp II stanowił rozszerzenie prototypu I o stany wewnętrzne, natomiast prototyp IJJ był wyposażony dodatkowo w model świata zewnętrznego (służący do przewidywania stanów środowiska) oraz wewnętrzny mechanizm oceny. Wreszcie prototyp IV górował nad swymi poprzednikami zdolnością do modyfikacji swych własnych receptorów i efektorów, zapewniając w ten sposób większy (lub może mniejszy) zakres rozpoznawania danych oraz bogatszy repertuar zachowań. Nie powinno dziwić, że prace nad tym projektem zbiegły się z rozwinięciem teorii schematów (Holland, 1968, 1971); nigdy jednak nie pojawiły się doniesienia o eksperymentach lub próbach implementacji któregokolwiek z prototypów.
Te pierwsze pomysły przerodziły się w koncepcję ogólnego (ijak dotąd nie zreali-zowanego)j'ezyfca przekazu [broadcast language] (Holland, 1975). Język przekazu umożliwia tworzenie jednostek przekazu (reguł przepisywania) zapisanych w alfabecie złożonym z dziesięciu symboli. Alfabet składa się z cyfr dwójkowych, kilku metasymboli oraz znaków specjalnych: symbolu trwałości tyersistence\ (powodującego stałą transmisję komunikatu) i cudzysłowu (powodującego literalną interpretację następującego po nim symbolu). Język ten jest dostatecznie mocny, aby zapewnić dogodny sposób reprezentacji i uniwersalność obliczeniową [computational completeness]. Projektjęzyka przekazu przyczynił się do zunifikowania wcześniejszych pomysłów dotyczących procesorów schematów, dostarczając teoretycznie jednolitej reprezentacji wszystkich operatorów, danych i reguł lub instrukcji; jednakże ogólność osiągnięta w teorii nie została nigdy zrealizowana w praktyce.
Pierwsza praktyczna implementacja systemu GBML ujrzała światło dzienne w trzy lata po przedstawieniu projektu języka przekazu (Holland i Reitman, 1978). System ten, nazwany systemem kognitywnym poziomu pierwszego (CS-1), był trenowany w rozwią-
.lL,
234
6. Wprowadzenie do genetycznych systemów uczących się
zywaniu dwóch zadań pokonywania labiryntu. Zastosowano w nim układ wykonawczy złożony z listy komunikatów, prostych reguł przepisywania zwanych klasyfikatorami [classifiers], algorytmu genetycznego opartego na reprodukcji, krzyżowaniu, mutacji i metodzie ścisku oraz mechanizmu uczenia z nagradzaniem, w którym nagroda zostaje rozdzielona między wszystkie klasyfikatory aktywne w okresie między dwiema kolejnymi wypłatami. Ten ostatni mechanizm był w późniejszych systemach zastępowany przeważnie przez inny, zwany algorytmem bucket brigade.
Po skonstruowaniu pierwszego systemu klasyfikującego idea ta została rozwinięta w różnych kierunkach i zastosowana do rozmaitych celów przez innych badaczy. W tablicy 6.1 podajemy wykaz zastosowań genetycznych systemów uczących się. Począwszy od eksperymentów ze "sztucznym życiem", a skończywszy na zagadnieniu odmiany czasowników w języku norweskim, systemy GBML cieszą się rosnącym zainteresowaniem na różnorodnych polach badawczych. Bardziej szczegółowego przeglądu wyników badań prowadzonych przy użyciu systemu CS-1 i innych systemów GBML, mających znaczenie historyczne lub aktualne, dokonamy w następnym rozdziale. Reszta niniejszego rozdziału jest poświęcona aspektom teoretycznym i implementacyjnym oraz przykładowemu zastosowaniu prostego systemu klasyfikującego.
Tablica6.1.Zastosowaniagenetycznychsystemowuczacychsie
Rok
Badacz(e)
Opis
Biologia i medycyna
1984 Rada, Rhine i Smailwood
1987 1987b
Biznes
1986
1987
Bickel i Bickel Wilson
Thompson i Thompson Greene i Smith
Informatyka
1980 Smith
1981 Forsyth-
1985 Cramer
1985b, c Forrest
1986a Riolo
1986b Riolo
1986 Zhou
Próba zastosowania systemu GBML do diagnostyki medycznej
Opracowanie systemu GBML do diagnostyki medycznej Projekt użycia systemu klasyfikującego do symulacji mor-fogenezy
Zastosowanie AG do tworzenia zestawów reguł służących do przewidywania rentowności przedsiębiorstw System GBML uczący się reguł opisujących preferencje konsumentów
Program pokerowy LS-1
System Beagle służący do rozpoznawania wzorców na drodze ewolucji
Generowanie algorytmu mnożenia liczb w języku niskiego poziomu przy użyciu algorytmu genetycznego Kompilator języka opisu sieci semantycznych KL-ONE na klasyfikatory
Pakiet ogólnego przeznaczenia w języku C do badań systemów klasyfikujących
Zastosowanie systemu klasyfikującego do przewidywania sekwencji liter
Konstrukcja automatów skończonych na podstawie przykładów przy użyciu AG
6.1. Skąd wzięty się systemy GBML . Tablica 6.1. (cd.)
235
Rok
Badacz(e)
Opis
1986 Robertson
1989 Stackhouse i Zeigler
Technika i badania operacyjne
1983 Goldberg
1984 1985 1986 1987 1987 Techniki Schaffer Kuchinski Wilson Antonisse Hilliard et hybrydowe i Keller al.
Maszynowe uczenie się
1971 Holland
1980a Holland
1985 Zhou
1986
1987c
1987a, b Riolo
Holland, Holyoak, Nesbitt i Thagard Grefenstette
1987 Westerdale
1987c, d Wilson
Implementacje współbieżne
1987a, b Robertson
Nauki społeczne
1978 Holland i Reitman
1982
1983
Booker
Wilson
Implementacja w Lispie systemu klasyfikującego na Maszynę Konekcyjną
Zastosowanie AG do poszukiwania reguł dla systemu przetwarzania symbolicznego opartego na regułach
Zastosowanie systemu klasyfikującego w zadaniach sterowania układem inercyjnym i pracą gazociągu System LS-2 (potomek LS-1) w zastosowaniu do problemów parzystości i przekazu sygnałów Zastosowanie AG do poszukiwania reguł dowodzenia na polu walki
Emulacja multipleksera za pomocą systemu klasyfikującego
Opracowanie systemu klasyfikującego na potrzeby zastosowań militarnych System klasyfikujący uczący się reguł szeregowania
Hybrydowy system uczący się, łączący metody konekcyj-ne, indukcję na grafach i algorytmy genetyczne
Projekt czterech prototypów procesorów schematów
Zarys algorytmu bucket brigade
Projekt wyposażenia systemów klasyfikujących w pamięć
długoterminową
Publikacja Indukcji
Zastosowanie algorytmu przyznawania ocen i heurystycz-nej inwersji w systemie uczącym się typu LS Analiza i symulacja efektywności algorytmu bucket brigade
Analiza altruizmu w metodzie bucket brigade Projekt jawnie hierarchicznego przyznawania ocen
Implementacja systemu klasyfikującego na Maszynie Ko-nekcyjnej
Pierwszy system klasyfikujący w zadaniach pokonywania labiryntu
"Sztuczne zwierzę" z mózgiem w postaci systemu klasyfikującego uczy się poruszać w dwuwymiarowym środowisku Systemu klasyfikujący sterujący wideokamerą
236
6. Wprowadzenie do genetycznych systemów uczących się
Tablica6.1. (cd.;
Rok
Badacz(e)
Opis
1985b Axelrod
1985b,c Wilson
1986a,b Schrodt
1986 Hasley (Skanland)
1987 Fujiko i Dickinson
Poszukiwanie strategii dla iterowanego dylematu więźnia przy użyciu AG
System klasyfikujący ANIMAT uczy się poruszać po dwuwymiarowych lasach
Zastosowanie systemu klasyfikującego do przewidywania wydarzeń międzynarodowych
System klasyfikujący uczy się form czasu przeszłego w języku norweskim
Generowanie przy użyciu systemu klasyfikującego programów w Lispie do znajdowania rozwiązań iterowanego dylematu więźnia
6.2. Czym jest system klasyfikujący?
System klasyfikujący jest to system, który uczy się prostych syntaktycznie reguł (zwanych klasyfikatorami), w celu koordynacji swoich działań w dowolnym środowisku. System klasyfikujący zawiera trzy główne składowe:
1) układprzetwarzaniakomunikatów;
2) układ oceniający; .;
3) algorytm genetyczny.
Układ przetwarzania komunikatów [rule and message system] w systemie klasyfikującym stanowi szczególny przypadek systemu produkcji. System produkcji (Davis i King, 1976) jest to pewien system formalny, służący do opisu algorytmów przy użyciu reguł syntaktycznych. Choć rozmaite warianty systemów produkcji różnią sie szczegółami składniowymi, ogólnie biorąc produkcje (reguły przepisywania) mają w nich następującą postać:
jeśli
to
Interpretacja (znaczenie) reguły przepisywaniajest następująca: jeżeli "warunek" jest spełniony, to może zostać podjęta "akcja" (mówimy wówczas, że reguła "odpala").
Na pierwszy rzut oka ograniczenie się do tak prostego mechanizmu reprezentacji wiedzy wydaje się zbyt restrykcyjne. Jednakże dowiedziono, że systemy produkcji są systemami uniwersalnymi obliczeniowo'* [computationally complete] (Minsky, 1967, Post, 1943). Co więcej, są one dogodne w aspekcie algorytmicznym. Pojedyncza produkcja lub mały zbiór produkcji mogą reprezentować w zwartej postaci złożony zasób wiedzy. "Eksplozja" systemów doradczych opartych na regułach w ostatnim dziesięcioleciu jest silnym dowodem empirycznym na rzecz tej tezy.
1 To znaczy, że są równoważne maszynom Turinga fynypis tlum.}
6.2. Czym jest system klasyfikujący?
237
Mimo takiego rozwoju systemów doradczych, tradycyjne systemy oparte na regułach nie cieszyły się podobnym powodzeniem w zastosowaniach wymagających umiejętności uczenia się. Jedną z głównych przeszkód stanowiły tu skomplikowane reguły syn-taktyczne. Systemy produkcji mogą posługiwać się zawiłymi konstrukcjami gramatycznymi w celu definiowania warunków i akcji. Systemy klasyfikujące odbiegają od głównego nurtu, dopuszczając jedynie reguły mające reprezentacje o stałej długości. Takie ograniczenie ma dwie zalety. Po pierwsze wszystkie ciągi symboli określonego alfabetu są poprawnymi syntaktycznie regułami. Po drugie, reprezentacja w postaci słów o ustalonej długości umożliwia zastosowanie operacji typu genetycznego. Dzięki temu powstaje możliwość wykorzystania algorytmu genetycznego do poszukiwań w przestrzeni dopuszczalnych reguł.
W systemach klasyfikujących stosuje się równoległe uaktywnianie reguł, w przeciwieństwie do tradycyjnych systemów doradczych, które opierają się na uaktywnianiu sekwencyjnym. W każdym cyklu uzgadniania [matching cycle] tradycyjny system doradczy uaktywniajedną regułę. Procedura ta stanowi "wąskie gardło", uniemożliwiające wzrost produktywności; stąd główne różnice w architekturze konkurujących ze sobą systemów doradczych dotyczą wyboru "lepszej" strategii wyboru uaktywnianej reguły dla tego czy innego typu problemów. Systemy klasyfikujące radzą sobie z tym wąskim gardłem przez równoległe uaktywnianie wielu reguł w jednym cyklu uzgadniania, zapewniając w ten sposób koordynację wielu równoczesnych działań. Kiedy zajdzie konieczność wyboru jednej z wzajemnie wykluczających się akcji w zewnętrznym środowisku albo gdy trzeba zredukować zbiór uzgodnionych reguł (aby nie przekroczyć dopuszczalnego rozmiaru listy komunikatów), decyzje w tych sprawach zostają odłożone do ostatniej możliwej chwili, a wówczas stosuje się kryterium konkurencyjności. Na temat zasad konkurencji między regułami powiemy więcej nieco później; na razie ograniczymy się do stwierdzenia, że architektura systemów klasyfikujących sprzyja równoległości, co wskazuje na możliwość skonstruowania bardzo szybkich implementacji sprzętowych systemów klasyfikujących, a jednocześnie daje podstawę do racjonalnego podejmowania decyzji bez konieczności wprowadzania dowolnych strategii arbitrażu.
W tradycyjnych systemach doradczych wartość określonej reguły w stosunku do innych reguł zostaje ustalona przez programistę na podstawie ocen eksperta lub grupy ekspertów, których dany system ma emulować. W systemie uczącym się reguł nie ma miejsca na taki luksus. Względna wartość różnych reguł jest właśnie jedną z podstawowych rzeczy, których trzeba się wyuczyć. W celu wspomagania tego typu uczenia się systemy klasyfikujące zmuszają klasyfikatory do koegzystencji w ramach "rynku usług informacyjnych". Klasyfikatory konkurują ze sobą o prawo do reakcji na komunikaty, przyznawane tym spośród nich, które składają najkorzystniejsze oferty, przy czym opłaty ponoszone z tego tytułu służąjako źródło przychodu dla nadawców, których komunikaty zostały pomyślnie odebrane. W ten sposób tworzy się łańcuch pośredników między producentem (detektory) a konsumentem (akcje i wypłaty w środowisku zewnętrznym). Konkurencyjna natura rynku gwarantuje, że dobre (tj. przynoszące zysk) reguły utrzymują się, a złe (nie przynoszące zysku) upadają.
Niebawem zajmiemy się szczegółami algorytmu przyznawania ocen [apportion-ment of credit algorithm\, w tym miejscu musimy jednak zdecydować się na krok
238
6. Wprowadzenie do genetycznych systemów uczących się
o zasadniczym znaczeniu, mianowicie rta wprowadzenie wewnętrznego pieniądza. Cyrkulacja i akumulacja pieniądza zapewnia naturalne kryterium oceny, dające się zastosować w algorytmie genetycznym. Jeśli użyć salda bankowego klasyfikatora jako wskaźnika przystosowania, to można reprodukować, krzyżować i dokonywać mutacji klasyfikatorów w sposób omówiony w pięciu pierwszych rozdziałach tej książki. Dzięki temu system nabywa zdolności uczenia się nie tylko przez ocenianie wartości istniejących reguł; może on również odkrywać nowe, potencjalnie lepsze reguły, będące nowatorskimi kombinacjami wcześniej używanych. Musimy być przy tym mniej nonszalanccy, jeśli chodzi o tworzenie całkowicie nowych populacji i zwrócić baczniejszą uwagę na to, które elementy będą ulegać wymianie; poza tym jednak zastosowany tu algorytm genetyczny nie różni od tych, których używaliśmy w zadaniach poszukiwania i optymalizacji.
Metoda przyznawania ocen w drodze konkurencji łącznie z mechanizmem odkrywania nowych reguł przy użyciu algorytmu genetycznego tworzą racjonalną podstawę konstrukcji systemu uczącego się w ramach uniwersalnego i dogodnego algorytmicznie systemu formalnego opartego na klasyfikatorach. Aby lepiej zrozumieć działanie systemu klasyfikującego, przeanalizujemy teraz dokładniej każdy z jego składników.
6.3. Układ przetwarzania komunikatów
Na rysunku 6.1 widzimy schematyczne przedstawienie układu przetwarzania komunikatów, układu oceniającego i algorytmu genetycznego. Układ przetwarzania komunikatów stanowi kościec algorytmiczny naszego krzemowego zwierza. Bodźce ze środowiska oddziałują na system klasyfikujący za pośrednictwem detektorów - jego oczu i uszu - w kfórych następuje ich transformacja na jeden lub więcej komunikatów [messages] o ustalonej długości. Te komunikaty zewnętrzne [environmental messages] zostają następnie umieszczone na liście komunikatów [message list] o ograniczonej pojemności, gdzie mogą powodować uaktywnienie reguł przepisywania (klasyfikatorów). Po uaktywnieniu klasyfikator umieszcza pewien komunikat na liście komunikatów. Komunikaty te mogą powodować uaktywnienie kolejnych klasyfikatorów lub doprowadzić do uruchomienia efektorów, zdolnych do wykonywania działań w środowisku. W ten sposób klasyfikatory łączą sygnały płynące ze środowiska z wewnętrznym modelem zachowania, decydując, co należy zrobić i nad czym się "zastanawiać" w następnej chwili. Można na to patrzeć jak na koordynację przepływu informacji - od miejsca, w którym jest odbierana (detektory), przez układ przetwarzania (lista komunikatów i zespół klasyfikatorów) do miejsca, w którym zostaje użyta do kierowania działaniami (efektory). Aby lepiej zrozumieć funkcjonowanie systemu przetwarzania komunikatów, przyjrzyjmy się dwóm jego składnikom - komunikatom i klasyfikatorom - oraz sposobowi, w jaki ze sobą współdziałają.
W systemie klasyfikującym komunikat ma postać słowa o ustalonej długości, zbudowanego z symboli określonego alfabetu. Jeżeli ograniczymy się do alfabetu dwójkowego, to otrzymamy następującą definicję:
6.3. Układ przetwarzania komunikatów .
239
Środowisko
Przyznawanie ocen
Algorytm genetyczny
Rys. 6.1. Uczący się system klasyfikujący oddziałuje ze środowiskiem
::={0, l}1 .- .
Symbol "::=" oznacza tu "równy z definicji", natomiast operacja potęgowania zbioru wyraża fakt, że bierzemy produkt (konkatenację) / zer lub jedynek. Komunikaty są podstawowymi jednostkami wymiany informacji w systemie klasyfikującym. Komunikaty znajdujące się na liście komunikatów mogą pasować do jednego lub więcej klasyfikatorów. Klasyfikator jest to produkcja (regula przepisywania) o niezwykle prostej składni:
: :=:
Warunek ma postać wzorca tekstowego, z metasymbolem "#" jako symbolem uniwersalnym:
::={0, 1, #}1
Tak więc warunek pasuje do komunikatu'', jeżeli na każdej określonej pozycji w obu tych ciągach zero w pierwszym odpowiada zeru w drugim, jedynka jedynce, a symbol uniwersalny - zeru lub jedynce. Na przykład czteropozycyjny warunek #01# pasuje do komunikatu0010,aniepasujedokomunikatu00002).
" Albo komunikat pasuje do warunku tyrzyp. tlum.)
2) Sprawdzanie dopasowania (zgodności) wzorców nazywamy uzgadnianiem Q)rzyp. tlum.)
l\A, k , T iWhi* , S
240
6. Wprowadzenie do genetycznych systemów uczących się
Jeżeli zdarzy się, że pewien komunikat pasuje do warunku klasyfikatora, to klasyfikator ten staje się kandydatem ubiegającym się o umieszczenie swego własnego komunikatu na liście komunikatów w następnym kroku. O tym, czy do tego dojdzie, decyduje "przetarg" na uaktywnianie, podczas którego bierze się pod uwagę "wartość" lub "wagę" klasyfikatorów.
W celu ugruntowania wiedzy na temat funkcjonowania układu przetwarzania komunikatów przeprowadźmy odręczną symulację tego procesu. Przypuśćmy, że zespół klasyfikatorów składa się z klasyfikatorów zamieszczonych w tabl. 6.2. W pierwszym kroku na liście komunikatów pojawia się komunikat zewnętrzny 0111. Komunikat ten pasuje do klasyfikatora nr 1, który następnie wysyła swój komunikat, 0000. Ten z kolei komunikat pasuje do klasyfikatorów nr 2 i nr 4, które następnie wysyłają swoje komunikaty (1100 i 0001). Komunikat 1100 pasuje do klasyfikatorów nr 3 i nr 4. W końcu stwierdza się, że komunikat 1000 wysłany przez klasyfikator nr 3 pasuje do klasyfikatora nr 4 i na tym proces przetwarzania urywa się.
Tablica 6.2. Cztery klasyfikatory
Numer
Klasyfikator
1) 2) 3) 4)
0l##:0000 00#0:llOO 11##:1000 ##00:0001
Mechanizm tego prostego układu przetwarzania komunikatów jest więc zupełnie przejrzysty Niektórzy badacze rozszerzyli składnię klasyfikatorów, wprowadzając wielość warunków (Goldberg, 1983) oraz symbole przenoszące ^pass-through} (Forrest, 1985b,c; Riolo, 1986a). Niektóre z tych innowacji omówimy w następnym rozdziale. Postąpimy przy tym zgodnie z wypróbowaną metodyką wojskową: najpierw całuj, a potem składaj dokładniejsze wyjaśnienia". Nawet prosty system jest w stanie nauczyć się niebanalnych zachowań; stają też przed nami istotne pytania o podstawowym znaczeniu. Jedno z nich nasuwa się niemal natychmiast: jeśli lista komunikatów okaże się nie dość obszerna, by pomieścić wszystkie komunikaty od możliwych do uaktywnienia klasyfikatorów, to w jaki sposób decydujemy, które z nich uaktywnić? Odpowiedź na to pytanie jest ściśle związana z działaniem układu oceniającego.
6.4. Układ oceniający: Algorytm bucket brigade__________
W wielu systemach klasyfikujących ocena wartości poszczególnych klasyfikatorów zależy od roli, jaką odegrały one w zdobyciu przez system "nagrody" od środowiska. Cho-
" Nieprzetłumaczalna gra słów: słowo KISS (całować) jest jednocześnie akronimem sformułowania keep it simple, stupid - czyIi: prosto, łopatologicznie ^>rzyp. tlum.).
6.4. Układ oceniający: Algorytm bucket brigade
241
ciaż można to robić na wiele sposobów, dominująca metoda opiera się na algorytmie, któremu Holland nadał miano bucket brigade[>. Algorytm ten najprościej rozpatrywać (ryzykując pewne pomieszanie metafor) jako swego rodzaju rynek usług informacyjnych, gdzie prawo do obrotu informacją jest nabywane i sprzedawane przez klasyfikatory. Klasyfikatory tworzą łańcuch pośredników biegnący od producenta informacji (środowisko) do jej konsumenta (efektory).
Rynek usług informacyjnych opiera się na dwóch podstawowych elementach: instytucjach przetargu [auction] oraz izby rozrachunkowej [clearinghouse]. Klasyfikatory nadające się do uaktywnienia nie mogą wysyłać bezpośrednio swoich komunikatów, nabywają natomiast prawo do uczestnictwa w przetargu na uaktywnienie. Aby wziąć udział w przetargu, każdy klasyfikator prowadzi ewidencję swojego "stanu posiadania", zwanego jego silą [strength] S. Każdy uprawniony klasyfikator składa ofertę [bid] B, proporcjonalną do swojej siły. Dzięki temu reguły dobrze przystosowane (które zgromadziły znaczne zasoby) zyskują przewagę nad innymi regułami. Proponowano również inne mechanizmy składania ofert - niektóre z nich jeszcze zdążymy omówić; jednak obecnie będziemy się kierować przede wszystkim prostotą rozwiązań.
Dzięki przetargowi mogą zostać wyłonione odpowiednie klasyfikatory, którym wolno będzie wysłać swoje komunikaty. Jednak historia bucket brigade na tym się nie kończy. Gdy klasyfikator wygra przetarg na uaktywnienie, musi następnie wpłacić należność do izby rozrachunkowej, aby uregulować zobowiązania wobec innych klasyfikatorów, które dostarczyły pasujących do niego komunikatów. Wartość złożonej oferty B zostaje wypłacona na rzecz klasyfikatorów odpowiedzialnych za wysłanie komunikatów, które pasowały do warunku należącego do uaktywnionego klasyfikatora. Wspomniana kwota zostaje w pewien sposób podzielona pomiędzy wszystkie te klasyfikatory. Podział należności między "dostawców" przyczynia się do wytworzenia podpopulacji reguł o odpowiednich liczebnościach (Booker, 1982). Dzięki temu możliwa jest koegzystencja różnych "gatunków" reguł określających różnorodne wzorce zachowania, jakich wymaga środowisko. Rozumowanie to opiera się na argumentacji przedstawionej w rozdziale piątym, dotyczącej znaczenia podziału zasobów dla formowania się gatunków zajmujących odmienne nisze ekologiczne. W jakimkolwiek konsekwentnym systemie uczącym się reguł nie ma sensu poszukiwać jednej uniwersalnej reguły. Należy natomiast szukać podzbioru reguł wytworzonego w wyniku ko-adaptacji, pokrywających łącznie taki zakres wzorców zachowania, który gwarantuje wystarczające wypłaty dla systemu uczącego się.
W celu ilustracji działania algorytmu bucket brigade rozważmy jeszcze raz cztery klasyfikatory z tabl. 6.2, uwzględniając jednak tym razem również ich płatności. Zakładając, że początkowo siła wszystkich czterech klasyfikatorów wynosi 200, wysyłamy, jak poprzednio, inicjalny komunikat zewnętrzny 0111 (por. tabl. 6.3). Załóżmy, że "współczynnik inwestycyjny" Chid wynosi 0,1, a wysokość ofertyjest równa iloczynowi tego współczynnika i siły klasyfikatora. W pierwszym kroku (t-0) zostaje stwierdzone
0 Termin powstał w odniesieniu do dawnej metody gaszenia pożarów przez "łańcuszek'' ludzi podają-cychjeden drugiemu kubeł z wodą, dosłownie więc: "drużyna kubełkowa" (przyp. tłum.)
242
6. Wprowadzenie do genetycznych systemów uczących się
dopasowanie klasyfikatora nr 1, który składa ofertę w wysokości 20 jednostek i w następnym kroku wysyła komunikat. Klasyfikator nr 1 wpłaca oferowaną kwotę dostawcy komunikatu, dzięki któremu został uaktywniony; w tym przypadku siła środowiska zwiększa się o 20 jednostek, gdyż właśnie komunikat wysłany przez środowisko spowodował uaktywnienie klasyfikatora nr 1. W kolejnych krokach uaktywnione klasyfikatory regulują zobowiązania wobec poprzednio aktywnych klasyfikatorów. Ostatecznie w kroku piątym system otrzymuje nagrodę i przekazuje ją ostatniemu aktywnemu klasyfikatorowi (nr 4).
Tablica 6.3. Odręczna symulacja systemu klasyfikującego - uzgadnianie i rozliczanie
( = 0 t=\ t=2
w u L* 'S i- 'S " S- 'E
S ca cd L Ź ^0 3 0
-H c o co co
i s- 3 <3 ra a a, S E ca ^ 3 ca O. S cd C D, cd
z 5 S t2 Q o t/5 o o ~ o o W Q O 55 W Q 0
i) 01##:0000 200 E 20 180 0000 220
2) 00#0:1100 200 200 1 20 180 1100
3) 11##:1000 200 200 200 2 20
4) ##00:0001 200 200 1 20 180 0001 2 18
Środowisko 0 0111 20 20
Koniec
t= 3 (=4 ;=5 Wypłata
o
ż ^ c cd L 1
3 ^ 5
3 iH c fc 03
R M" cd B CL. P cd -g
a 5 S &0 ^ a Ś *- O O 1) 01##:0000 220 220 220
2) 00#0:1100 218 208 208
3) 11##:1000 180 1000 196 196
4) ##00:0001 162 0001 3 16 156 0001 206 50
Środowisko 20 20 20
Uwagi: 1. C,,,=0,1 2. C=0,0
Chcąc poprawnie zrealizować tę procedurę, musimy zdobyć się na większą ścisłość w opisie szczegółów przetargu i rozliczeń. Jak już wspomnieliśmy, podczas przetargu klasyfikatory składają oferty (fi,). Zwycięskie klasyfikatory przekazują oferowane kwoty do izby rozrachunkowej jako wypłaty fy>ayments] Pt. Klasyfikator może również otrzy-
6.4. Układ oceniający: Algorytm bucket brigade
243
mywać przychód [receipf\ Rl za wcześniejszą dostawę komunikatów lub z tytułu nagród od środowiska. Oprócz tego klasyfikator może być zmuszony do płacenia podatku [tax\ Tj. Ostatecznie równanie określające zależność między siłą klasyfikatora nr i w dwóch kolejnych krokach (chwilach) można zapisać następująco:
St(t + 1) = 5,.(0 - P,.(0 - r,(r) +
Aby uzyskać szczegółowy obraz procesu "bogacenia się" klasyfikatora, musimyjeszcze scharakteryzować ilościowo wysokości ofert, wypłat i podatków. Klasyfikator składa oferty proporcjonalne do swej siły:
gdzie Chld jest współczynnikiem inwestycyjnym a S - siłą klasyfikatora nr i.
Moglibyśmy właściwie na tym zakończyć i poprzestać na deterministycznej metodzie wyboru k najlepszych klasyfikatorów (gdzie &jest pojemnością listy komunikatów); jednak takie rozwiązanie sprzyjałoby nadmiernie tendencji do utrwalania status quo (De Groot, 1970). Wprowadzimy zatem do przetargu element zaburzenia losowego. Dla każdego uprawnionego klasyfikatora obliczmy efektywną wysokość oferty (EB) jako sumę wysokości deklarowanej i szumu losowego:
gdzie szum N jest funkcją zadanego odchylenia standardowego oferty Ghid.
Po zakończeniu cokolwiek hałaśliwego przetargu i wyłonieniu zwycięskich klasyfikatorów trzeba zapłacić klasyfikatorom, które dostarczyły komunikatów umożliwiających uaktywnienie zwycięzców. Ci ostatni dokonują wypłat w deklarowanej wysokości (tj. Bj, a nie EB,), które przekazują do izby rozrachunkowej, gdzie następuje podział wpłaconych kwot pomiędzy wszystkich dostawców pasującego (i zwycięskiego) komunikatu.
Aby zapobiec pasożytnictwu, każdy klasyfikator podlega opodatkowaniu; w ten sposób w populacji faworyzowane są reguły produktywne. Można tu stosować rozmaite podejścia; w przyjętym przez nas rozwiązaniu podatekjest proporcjonalny do siły klasyfikatora:
Powyższe zależności łącznie określają algorytm przyznawania ocen stosowany w wielu systemach klasyfikujących. Aby przeprowadzić pobieżną analizę stabilności i długofalowego zachowania tego mechanizmu, przepiszmy równanie stanu posiadania klasyfikatora w postaci, w której wypłaty i podatki wyrażają się poprzez jego siłę. Dla aktywnego klasyfikatora wygląda to następująco:
S(t + 1) = 5(?) - CM5(0 - CtaxS(t) + R(t)
244
6. Wprowadzenie do genetycznych systemów uczących się
W powyższym równaniu opuściliśmy wskaźnik i określający numer klasyfikatora, do którego odnoszą się poszczególne człony równania. Po przegrupowaniu składników otrzymujemy zależność:
S(t+ 1) = (1 -K)S(t) + R(t)
W celu określenia warunków stabilności rozwiązań, możemy posłużyć się transformatą Z (Takahashi, Rabins i Auslander, 1970) dla równań jednorodnych. Na bardziej intuicyjnym poziomie możemy zauważyć, że stabilność systemujest możliwa tylko przy ograniczonym wejściu (w tym przypadku przy ograniczonym R), kiedy wartości S nie rosną w czasie w sposób niekontrolowany. Pomijając na razie przyrosty R(t), otrzymujemy następujące równania jednorodne, opisujące samoistny spadek siły klasyfikatora:
s(t+ i) = (i -K)S(t) *" vv.; - ' ;..:
Rozwiązując ten układ dla t=n, otrzymujemy związek S(n) = (l -K}"S(Q). Rozwiązanie to jest stabilne (nie eksploduje) przy dowolnym 5(0), pod warunkiem, że 0 < K < 2; w praktyce jednak trzeba postulować, żeby K< 1, aby siła przybierała wartości nieujem-ne. Wynik ten jest słuszny dla klasyfikatorów, które są stale aktywne; jednak system pozostanie stabilny także w przypadku realnych klasyfikatorów, zmieniających od czasu do czasu swój stan - jeśli tylko zmienna wartość K spełnia kryterium stabilności.
Stabilność jest sprawą istotną, ale jeśli interesują nas efekty działania tego mechanizmu, musimy zbadać zachowanie się algorytmu w czasie. Mówiąc wprost, co robi nasz system z nagrodami, które otrzymuje od środowiska? Przy zadanej sile początkowej 5(0) możemy wyznaczyć siłę w ra-tym kroku czasowym zgodnie z następującą równością:
n-l
S(n} = (1 - K)"S(0) +
Ponownie zignorowaliśmy tu zmienność będącą skutkiem "przełączania się" klasyfikatorów, choć w zasadzie można ją uwzględnić, wprowadzając zmienny współczynnik KQ). Długofalowe zachowanie się tego mechanizmu można zanalizować, rozważając stan równowagi dynamicznej. Jeśli proces przebiega nieustannie przy stałych wartościach przychodu R(t) = R^, to warunkiem stacjonarności siłyjest, żeby S(t+ l) = 5(?) = 5". Zależność ta daje następujący związek:
sa=Ra/K -; .' ; - =-. v . ; . .
Okazuje się zatem, że siła jest równa przychodowi pomnożonemu przez czynnik l/K. Stacjonarną wysokość oferty można natomiast wyznaczyć następująco:
R _ B -
^bid
R,.
6.5. Algorytm genetyczny
245
Ponieważ wielkość Clax jest zazwyczaj mała w stosunku do współczynnika inwestycyjnego, stacjonarna wysokość oferty jest na ogół bliska stacjonarnej wysokości przychodu, BSS = RSS. Inaczej mówiąc, w warunkach stacjonarnego przychodu wysokość oferty zbliża się do wielkości przychodu. Natomiast w przypadku zmiennych w czasie przychodów, wysokość oferty jest, jak widzimy, średnią ważoną przychodów o wagach malejących geometrycznie. Działa to jak filtr wobec potencjalnie nieregularnych i zaburzonych przychodów. , ' ,- %
6.5. Algorytm genetyczny
Algorytm bucket brigade daje nam do ręki narzędzie oceny i wyboru spośród konkurujących reguł. Brakuje nam jeszcze sposobu zasilania systemu nowymi, potencjalnie lepszymi regułami. W tym właśnie miejscu wkracza na arenę algorytm genetyczny. Nowe reguły zostają wytworzone w znajomym procesie opartym na trzech operacjach genetycznych (reprodukcja, krzyżowanie, mutacja), podobnym do elementarnego algorytmu genetycznego z rozdziału trzeciego. Reguły te są następnie umieszczane w populacji i biorą udział w przetargach i rozliczeniach, podczas których ujawnia się ich rzeczywista wartość dla systemu. Nie możemy sobie przy tym pozwolić na całkowitą wymianę populacji i musimy zwracać baczniejszą uwagę na sposób zastępowania elementów. Mimo tych odmienności algorytmy genetyczne stosowane w systemach klasyfikujących zachowują znaczne podobieństwo do tych, których używaliśmy w zadaniach poszukiwania i optymalizacji. W tym punkcie skoncentrujemy się na omówieniu najważniejszych różnic między obu wariantami.
Elementarny algorytm genetyczny z rozdziału trzeciego opierał się na modelu rozłącznych populacji, w ramach którego w każdym pokoleniu dokonywało się wyboru całkowicie nowej populacji, zastępującej poprzednią. Niejest to na ogół pożądane w systemach uczących się. W tym przypadku zależy nam często na utrzymaniu wysokiego poziomu efektywności bieżącej w czasie, gdy system uczy się sprawniejszych wzorców zachowania; natomiast w przypadku poszukiwania lub optymalizacji sprawą większej wagi wydaje się osiągnięty stopień zbieżności. Omawiając eksperymenty De Jonga (1975), zwróciliśmy uwagę na parametr zwany współczynnikiem wymiany G, który został użyty do implementacji i testowania algorytmów genetycznych stosujących mieszanie pokoleń. Tutaj zdefiniujemy analogiczną wielkość, określającą ułamek populacji podlegający wymianie w wyniku jednego wywołania algorytmu genetycznego. Wprowadzimy także parametr Tga, określający liczbę kroków (cykli układu przetwarzania komunikatów) między kolejnymi wywołaniami AG. Okres ten można traktować w sposób deterministyczny (wywołując AG dokładnie co Tga kroków) albo stochastyczny (wywołując AG w momentach losowych średnio co Tga kroków). Ponadto wywołania algorytmu genetycznego mogą być uwarunkowane zajściem określonych zdarzeń, jak brak dopasowania lub mała efektywność.
W procesie selekcji używa się najczęściej reguły ruletki, przy czym siła klasyfikatora S odgrywa rolę wskaźnika przystosowania. Ponieważ nie wymieniamy już populacji w całości, musimy zachowywać ostrożność przy wyborze kandydatów do zastąpienia.
246
6. Wprowadzenie do genetycznych systemów uczących się
Można tu zastosować opisany w rozdziale czwartym model ze ściskiem De Jonga (1975), w którym preferuje się zastępowanie elementów podobnych. ' !ii
Trzeba także zmodyfikować nieco sposób mutacji, ponieważ klasyfikatory posługują się alfabetem trójelementowym. Definicja prawdopodobieństwa mutacji pm nie ulega przy tym zmianie; natomiast sama operacja zastępuje mutowany znak jednym z dwóch pozostałych, z jednakowym prawdopodobieństwem (0 -^ {1, #}, 1 ^> {0, #}, #^{0, 1}).
Po wprowadzeniu tych zmian do istniejącgo programu można już włączyć algorytm genetyczny do systemu klasyfikującego i posługiwać się nim prawie tak samo, jak w zadaniach poszukiwania i optymalizacji.
6.6. System klasyfikujący w Pascalu
Systemy klasyfikujące wyróżniają się prostotą. Jednak, gdy przyjdzie co do czego, początkujący adepci systemów klasyfikujących - podobnie jak nowi użytkownicy algorytmów genetycznych - często bezradnie rozkładają ręce. W tym punkcie postaramy się nieco wykończyć surową konstrukcję systemu klasyfikującego, projektując prostą implementację takiego systemu w Pascalu. Konkretnie skonstruujemy system, którego zadaniem jest wyuczenie się funkcji boolowskiej (multiplekser). Z uwagą dokonamy rozbioru systemu na podstawowe elementy. Listę komunikatów zredukujemy tu do pojedynczego komunikatu zewnętrznego, co - wywołując natychmiastowe sprzężenie zwrotne ze środowiskiem - umożliwia istotne uproszczenie mechanizmu rozliczeń. Dzięki tym ułatwieniom możemy stworzyć funkcjonalny system z minimum maszynerii.
6.6.1. Strukturydanych
Jak już wskazywaliśmy, układ przetwarzania komunikatów - zwany niekiedy ukladem wykonawczym fc>erformance system] - stanowi kościec systemu klasyfikującego. Omówimy teraz struktury danych i procedury niezbędne do implementacji prostej wersji układu wykonawczego w systemie klasyfikującym. Skupimy się przy tym na najważniejszych fragmentach programu, pomijając mniej istotne szczegóły; kompletny wydruk programu SCS został zamieszczony w dodatku C wraz z przykładowymi zestawami danych wejściowych. W wydruku 6.1 pokazano deklaracje struktur danych implementujących populację klasyfikatorów oraz komunikat zewnętrzny. Typ danych reprezentujący klasyfikatory, classtype, jest zdefiniowany jako rekord złożony z warunku c, akcji a oraz kilku innych zmiennych prostych. Typ condition stanowi tablicę o elementach typu trit (ternary digit, cyfra trójkowa) - przyjmujących wartości -1, 0 i 1, przy czym -1 interpretuje się jako symbol uniwersalny, a pozostałe dwie cyfry zachowują zwykłe znaczenie. Typ action w programie SCS jest zdefiniowany jako bit, gdyż w zadaniu emulacji multipleksera system klasyfikujący ma na celu wyuczenie się pewnej funkcji boolowskiej i najego wyjściu muszą pojawiać się cyfry 1 lub 0. W definicji klasyfikatora
6.6. System klasyfikujący w Pascalu .
247
występują również pola typu reai. strength, bid i ebid. Reprezentują one odpowiednio siłę, deklarowaną wysokość oferty i efektywną wysokość oferty (którą wcześniej oznaczaliśmy jako EB) klasyfikatora. Przypomnijmy, że efektywna wysokość oferty różni się od deklarowanej pewnym składnikiem losowym (szumem) o zerowej wartości oczekiwanej. W definicji klasyfikatora pojawia się też dodatkowe pole matchflag typu boolean. Otrzymuje ono wartość true wtedy, kiedy aktualny komunikat zewnętrzny pasuje do warunkuklasyfikatora. ;,.-,
{ declare.scs: declarations for scs )
const
type
maxposition - 50; .: .
maxclass 100; wildcard - -1;
btt - 0..1; ( a blnary dlgit ) trit - -1..1; ( a ternary digit; 0-0; 1-1; -action - bit; { a binaray decision ) condltlon - array[l. .maxposit<.on] of trit; message - array[l..maxposition] ofbit; classtype - record
c:condition;
a:action; ' '
strength, bid, ebld:real;
matchflag:boolean;
specificity:integer; end;
classarray - array[l..maxclass] of classtype; classlist - record
clist:array[l..maxclass] of integer;
nactive:integer end; poptype record
classifier:classarray; '
nclassifier, nposition:integer; .,:--
pgeneral, cbid, bidsigma, bidtax, lifetax,
bidl, bid2, ebidl, ebid2,
sumstrength, maxstrength, avgstrength, minstrength:real end;
population:poptype; matchlist:classlist; envmessage:message; rep:text;
{ population of classifiers } ( who matched ) ( environmental oessage } ( report device/file }
Wyd. 6.1. Definicje i deklaracje podstawowych struktur danych w uproszczonym systemie klasyfikujacym(SCS).Opispopulacjiklasyfikatorow
Typ classarray stanowi tablice klasyfikatorów (tj. elementów typu classtype). Pole tego typu ( classifier) występuje w definicji typu rekordowegopoptype, reprezentującego populację. Dodatkowo wprowadzamy pola nclassifier i nposition typu integer, opisujące odpowiednio liczbę klasyfikatorów i liczbę pozycji w warunku. Jest tam także kilka pól typu real reprezentujących parametry populacji; wrócimy do nich, gdy zajdzie potrzeba ich użycia.
Mając zdefiniowaną strukturę populacji, deklarujemy pojedynczy obiekt tego typu o (raczej stosownej) nazwie population. Deklarujemy także zmienną envmessage repre-
248
6. Wprowadzenie do genetycznych systemów uczących się
zentującą komunikat zewnętrzny. Jej typ (message) został zdefiniowany jako tablica elementów typ bit, przy czym ten ostatni jest okrojonym typem integer o zakresie O..1. W bardziej zaawansowanych systemach klasyfikujących moglibyśmy zadeklarować tablicę takich komunikatów (odpowiadającą liście komunikatów). Tutaj ograniczamy się do jednej zmiennej, która odpowiada komunikatowi zewnętrznemu.
Prócz tablicy klasyfikatorów i komunikatu zewnętrznego tworzymy także pomocniczą strukturę danych matchlist służącą do rejestrowania klasyfikatorów, które pasują aktualnie do komunikatu zewnętrznego. Jest to obiekt typu classlist (rekord zawierający pole clist będące tablicą elementów typu integer oraz pole nactive typu integer, opisujące liczbę elementów aktywnych). Podczas działania układu wykonawczego rekord ten zawiera listę numerów oraz liczbę tych klasyfikatorów, które pasują do aktualnego komunikatu. Tę samą informację można uzyskać (z pewnym wysiłkiem) badając wartości pól matchflag wszystkich klasyfikatorów; jednak korzystnie jest prowadzić oddzielny rejestr w celu osiągnięcia efektywnej implementacji przetargu.
W końcu, musimy zadeklarować plik (czy też urządzenie) przeznaczone do zapisywania wszystkich raportów wynikowych (wstępnych i bieżących) prócz interakcyjnych dialogów na ekranie. Jest to plik tekstowy o nazwie rep. W programie SCS używamy łącznie siedmiu plików:
przeznaczone dIa raportów nieekranowych
z danymi opisującymi klasyfikatory
z danymi opisującymi detektory i środowisko
z danymi opisującymi wzmocnienie
z danymi opisującymi zależności czasowe
z danymi opisującymi algorytm genetyczny
przeznaczone na tabele danych
Szczegółowy opis tych plików znajduje się w dodatku C. Struktury danych, tworzone na podstawie tych plików omawiamy bardziej szczegółowo w ramach dalszej analizy struktury SCS.
rep Wyjście
cfile Wejście
efile Wejście
rfile Wejście
tfile Wejście
Sfile Wejście
pfile Wyjście
6.6.2. Układ wykonawczy
Podobnie jak sercem systemu SCS jest układ wykonawczy, tak też jądro układu wykonawczego stanowią procedury uzgadniające. Na wydruku 6.2 widzimy dwie takie procedury o nazwach match \ matchclassifiers. Funkcja paskalowa match dokonuje porównania warunku i komunikatu, przyjmując wartość true, jeśli oba ciągi pasują do siebie. Proces uzgadniania przebiega krokami, pozycja za pozycją, przy czym w każdym kroku daje on wynik pozytywny (wartość true), jeśli jednym z porównywanych symboli jest symbol uniwersalny (#, czyli -1) lub też jeśli oba są identyczne. Całość tego procesu jest koordynowana przez konstrukcję while-do. Warto zapewne poświęcić nieco wysiłku na opracowanie bardziej efektywnej metody, gdyż większość czasu zużywanego przez system klasyfikujący idzie na wykonywanie procedury match. Można pomyśleć o wstawce wję-
6.6. System klasyfikujący w Pascalu .
249
function match(var c:condition; var m:message; npositlon:integer):boolean; { match a single condition to a single message } var matchtemp:boolean; begin
matchtemp : true;
while (matchtemp - true) and (nposition > 0) do begin
matchtemp :- (c[nposition) -wildcard) or (c[nposition] -m[nposition]); nposition :- nposition - 1
end: ..-.-. ; ,-, , -.,'-f.-..-;.v;v!-; ,- ........ .- M -w
match :- matchtemp
end; ' ' '- : ' ." ' '' '*'' " ' ':- '
procedurę matchclassifiers(var population:poptype; var emess:message;
var matchlist:classlist);
( match all classifiers against environmental message and create match list } var j:integer; begin with population do with matchlist do begin
nactive : 0; \' ;
for j :- 1 to nclassifier do with classifier[J] do begin ,,.^
matchflag :- match(c, emess, nposition); if matchflag then begin
nactive : nactive + 1; < clist[nactive] :-j . .
end . . . -- , - . : / ^
end; end end;
Wyd. 6.2. Funkcja paskalowa match \ procedura mafcftc/asstf/ersstanowiąserce układu orzetwarzania komunikatów w systemie SCS
zyku asemblera, używającej niskopoziomowych operacji porównywania słów maszynowych, są to jednak rozwiązania zależne od sprzętu i wykraczają poza zakres naszych rozważań.
Procedura matchclassifiers sprawdza zgodność wszystkich klasyfikatorów z komunikatem zewnętrznym i konstruuje rekord matchlist. Jądro podprogramu mieści się wewnątrz pet\ifor-do. Na początku każdego cyklu zmienna boolowska matchflag otrzymuje wartość nadaną jej w wyniku wywołania funkcji match. Następnie wartość zmiennej nactive, określającej liczbę aktywnych klasyfikatorów, zostaje w razie potrzeby zwiększona o 1, a lista klasyfikatorów clist powiększa się o numer pasującego klasyfikatora. Przy wyjściu z procedury matchclassifiers wszystkie pasujące klasyfikatory mają ustawione znaczniki matchflag, a rekord matchlist zawiera ich liczbę oraz listę ich numerów. Zakończywszy w ten sposób proces porównywania, jesteśmy już gotowi do wyłonienia zwycięzców i rozdziału wypłaty między klasyfikatory, zgodnie z algorytmem przyznawania ocen.
6.6.3. Algorytm przyznawania ocen
Poprzednio wymieniliśmy dwie główne składowe algorytmu przyznawania ocen: instytucję przetargu i izby rozrachunkowej. Oba te elementy występują w podprogramie realizującym układ oceniający w SCS (wyd. 6.3). Widzimy tam procedurę aoc, zawierającą wywołania trzech innych procedur: auction, clearinghouse i taxcollector. Jest tam również definicja typu crecord (wpis do rejestru izby rozrachunkowej) i deklaracja zmiennej
250
6. Wprowadzenie do genetycznych systemów uczących się
clearingrec tego typu. Wpis do rejestru składa się z dwóch pól typu integer. winner (aktualny zwycięzca) oraz oldwinner (poprzedni zwycięzca) oraz znacznika buck-etbrigadeflag typu boolean. Ten ostatni otrzymuje wartość true podczas inicjalizacji, jeżeli użytkownik decyduje się na ukrytą formę realizacji algorytmu bucket brigade. W zadaniu emulacji multipleksera znacznik bucketbrigadeflag zostaje zazwyczaj ustawiony nafalse, gdyż w każdym kroku czasowym system otrzymuje nagrodę, a kolejne sygnały wejściowe nie są ze sobą związane (są generowane w sposób losowy). W innego typu zadaniach, w których w celu nagrodzenia działań poprzedzających trzeba łańcuszka rozliczeń, znacznik bucketbrigadeflag powinien być ustawiony na true, co powoduje realizację wypłaty ze strony aktualnego zwycięzcy na rzecz poprzedniego. Niezależnie od tego czy stosujemy ukrytą formę bucket brigade czy nie, bardziej skomplikowane systemy klasyfikujące wymagają oczywiście dokładniej prowadzonego rejestru wszystkich zwycięzców i ich prekursorów; uciążliwość tej procedury jest jedną z przyczyn, dla których zajmujemy się teraz uproszczonym systemem klasyfikującym.
( aoc data declaratlons - aoc uses cflle for lnput ) type crecord - record ^
wlnner, oldwlnner:integer; bucketbrigadeflag:boolean; end;
var clearlngrec:crecord;
procedurę aoc(var population:poptype; var matchlist:classlist; '' var clearingrec:crecord);
( apportionment of credit coordinator ) begin
wlth clearingrec do winner :- auction(population, matchllst, oldwinner);
taxcollector(populacion);
clearinghouse(population, clearingrec); end;
Wyd. 6.3. Procedura aoc koordynuje pracę układu oceniającego w SCS poprzez strukturę danych clearingrec
Szczegóły funkcjonowania układu oceniającego można prześledzić na wyd. 6.4. Funkcja paskalowa auction przeprowadza przetarg (w obecności szumu losowego) w celu wyłonienia zwycięzców spośród grona oferentów pasujących do komunikatu. Wewnątrz konstrukcji/or-Jo, w kolejnych cyklach oblicza się, korzystając z rekordu rnatch-list, deklarowaną (bid) i efektywną (ebid} wysokość oferty poszczególnych pasujących klasyfikatorów. Wartość bid jest obliczana jako iloczyn trzech czynników: pola cbid, funkcji liniowej szczegółowości" (specificity) oraz siły klasyfikatora. Wspomniana funkcja ma w tym przypadku postać
bid] + bid2 *specificity
gdzie bid] i bid2 są parametrami wejściowymi. Dobierając różne wartości bidl \ bid2 można badać różne struktury ofert. Efektywna wysokość oferty jest również iloczynem
Tj. liczby zer i jedynek w warunku klasyfikatora (przyp. tlum.)
6.6. System klasyfikujący w Pascalu.
251
cbid, funkcji liniowej specificity (o współczynnikach ebidl i ebid2) \ siły, powiększonym o składnik losowy o rozkładzie normalnym ze średnią zero i odchyleniem standardowym bidsigma. Użycie odrębnych współczynników dodatkowo zwiększa swobodę przy określaniu struktury ofert. Do generowania szumu losowego o rozkładzie normalnym została użyta metoda Boxa-Mullera (Pike, 1980), zaimplementowana w postaci kilku procedur wchodzących w skład pliku utility.scs (dodatek C). Na koniec funkcja auction przybiera jako wartość numer klasyfikatora o najwyższej efektywnej wysokości oferty i oddaje sterowanie procedurze aoc.
Jako następna zostaje wywołana procedura clearinghouse, której zadaniem jest dokonanie rozrachunków. Siła (strength) aktualnego zwycięzcy zostaje pomniejszona
function auction(var populatlon:poptype; var matchllst:classlist;
oldwinner:integer):integer;
{ auction among currently matched classifiers - return winner ) var j, k, winner:integer; bidmaximum:real;
begin wlth population do with matchlijt do begin . , , ,,;
bldmaxImum :- 0.0;
winner :- oldwlnner; { tf no match, oldwlnner wlns again ) lf nactive > 0 then for J :- 1 to nactive do begln k :- cllst[j]; with classifter[k] do begin
bid :- cbid * (bidl + bid2 * specificity) * strength; ebid :- cbid * (ebidl + ebid2 * specificity) * strength
+ noise(0.0, bidsigma); if (ebid > bIdmaximum) then begin
winner : k; !
bidmaximum : ebid end
end end; :
auction : winner end end;
procedurę clearinghouse(var population:poptype; var clearingrec:crecord); ( distribute payment from recent winner to oldwinner ) var payment:real;
begin with population do with clearingrec do begin with classifier[winner] do begin ( payment ) payment : bid;
strength : strength - payment end;
if bucketbrigadeflag then ( pay oldwinner receipt if bb is on } with classifier[oldwlnner] do strength :- strength + payment end end;
procedurę taxcollector(var population:poptype); { collect existence and bidding taxes from population members ) var j:integer; bidtaxswitch:real; begin with population do begin ( life tax from everyone & bidtax from actives )
.if (lifetax O 0.0) or (bidtax O 0.0) then for J :- 1 to nclassifier do with classifier[j] do begin
if matchflag then bidtaxswitch :- 1.0 else bidtaxswitch :- 0.0; strength :- strength - lifetax*strength - bidtax*bidtaxswitch*strength; end; end end;
Wyd. 6.4. Przyznawanie ocen w SCS jest realizowane za pomocą funkcji auction oraz procedur clearinghouse i taxcollector
252
6. Wprowadzenie do genetycznych systemów uczących się
o deklarowaną (a nie efektywną) wartość oferty bid, i - jeśli znacznik bucketbrigadeflag ma wartość true - pole strength poprzedniego zwycięzcy (oldwinner} ulega zwiększeniu o taką samą wypłatę Q?ayment). Opisana procedura izby rozrachunkowej została w znacznym stopniu uproszczona w stosunku do ogólnego systemu klasyfikującego. Zauważmy również inną różnicę między tą implementacją a opisanym wcześniej ogólnym mechanizmem przyznawania ocen. Wcześniej stwierdziliśmy mianowicie, że zwycięskie klasyfikatory płacą poprzednio aktywnym klasyfikatorom za dostarczenie komunikatów, które umożliwiły uaktywnienie tych pierwszych. W uproszczonej wersji, którą tu omawiamy, aktualnie aktywny klasyfikator dokonuje wypłaty na rzecz swego poprzednika ^esli bucketbrigadeflag ma wartość true), chociaż nie ma między nimi bezpośredniego powiązania poprzez listę komunikatów. W ten sposób zakładamy istnienie sprzężenia między klasyfikatorami aktywnymi w sąsiednich chwilach - przypuszczenie uzasadnione porządkiem czasowym nakładanym przez środowisko. Taka ukryta postać mechanizmu bucket brigade została po raz pierwszy wypracowana przez Wilsona (1985b). Bywa ona skuteczna w prostych systemach klasyfikujących, którym do efektywnego funkcjonowania wystarcza pojedynczy łańcuch derywacji. W złożonych systemach potrzeba bardziej efektywnego sposobu dystrybucji wypłat klasyfikatorom, które przyczyniają się do zdobycia nagrody, co osiąga się za pomocą ogólniejszej postaci tego mechanizmu z rozgałęzionymi łańcuchami powiązań klasyfikator-komunikat.
Ostatnią procedurą wywoływaną w aoc jest taxcollector. W celu odsiania nieproduktywnych reguł, od klasyfikatorów pobiera się dwa rodzaje podatku: podatek pogłów-ny i podatek obrotowy. Podatek pogłówny, którego stopa jest określona przez parametr populacji lifeta\ (typu real), płacą wszystkie klasyfikatory, natomiast podatek obrotowy płacą te klasyfikatory, które składały oferty podczas ostatniego przetargu; jego stopajest określona przez parametr bidtax (również typu real). Jeżeli którakolwiek z tych stóp jest różna od zera, to pet\afor-do wewnątrz procedury taxcollector stanowi narzędzie wystarczające do ściągnięcia odpowiedniej kwoty podatku od każdego klasyfikatora.
Łącznie trzy procedury auction, dearinghouse i taxcollector rozdzielają i pobierają należności oraz podatki, aby doprowadzić do tego, że dobre reguły rosną w siłę, a złe - słabną. Siła reguły może być następnie użyta jako miara przystosowania w genetycznym procesie poszukiwania nowych, potencjalnie lepszych reguł.
6.6.4. Poszukiwanie genetyczne w systemie klasyfikującym
Algorytm genetyczny stosowany do odkrywania nowych reguł w systemie SCS uderzająco przypomina program SGA z rozdziału trzeciego. Wobec tego zatrzymamy się tylko przy znaczących różnicach. Wydruk 6.5 zawiera opis struktur danych oraz głównej procedury sterującej (ga) algorytmu genetycznego wchodzącego w skład SCS. Parametr garec procedury ga jest rekordem typu grecord. Rekord ten zawiera następujące pola typu reai. proportionselect, pmutation i pcrossover. Pole proportionselect określa ułamek populacji podlegający reprodukcji podczas jednego wywołania procedury. Pola pmutation i pcrossover określają odpowiednio prawdopodobieństwa zajścia mutacji (dla jednej pozycji ciągu) i krzyżowania (dla kojarzenia). Rekord zawiera też pola typu in-
6.6. System klasyfikujący w Pascalu .
253
teger. Pole crowdingfactor określa czynnik ścisku, tj. liczbę osobników będących kandydatami do zastąpienia przy zastosowaniu metody ścisku. Pola nmutation i ncrossover pełnią funkcję liczników wykonanych mutacji i krzyżowań odpowiednio. Prócz tego rekord typu grecord zawiera też pole mating będące tablicą typu marray. Jest to tablica złożona z rekordów opisujących osobniki wybrane do reprodukcji i do zastąpienia. Każdy taki rekord składa się z indeksów dwóch kojarzonych osobników (matel i mate2), punktu krzyżowania koniugującej pary (sitecross) oraz indeksów dwóch klasyfikatorów (mortl i mort2) ustępujących miejsca "nowo narodzonym" regułom. Z tych ostatnich rekordów korzysta się jedynie w celu przygotowania raportu o działaniu algorytmu genetycznego. Przeglądając treść procedury ga (wyd. 6.5) możemy zauważyć, że jest ona bardzo zbliżona do analogicznej procedury elementarnego algorytmu genetycznego (SGA): sta-
( ga.scs: genetic algorithm code for SCS }
{ data declarations )
const maxmating 10; *
type mrecord - record
matel, mate2, mortl, raort2, sitecross:integer end;
marray - array[l..maxmating] of mrecord;
grecord - record , , ; :
proportionselect, pmutatlon, pcrossover:real; ncrossover, nmutation, crowdingfactor, crowdingsubpop,
nselect:integer;
mating:marray; ( mating records for ga report) end;
var garec: grecord; gflle:text;
procedurę ga(var garec:grecord; var population:poptype);
( coordinate selection, mating, crossover, mutation, & replacement )
var j:integer; childl, child2:classtype;
begin with garec do with population do begin
statistics(population); { get average, max, min, sumstrength )
for j :- 1 to nselect do with mating[j] do begin
matel :- select(population); { pick mates }
mate2 : select(population);
crossover(classifier[matel], classifier(mate2], childl, child2, pcrossover, pmutation, sitecross, nposition,
ncrossover, nmutation); ( cross & mutate }
mortl :- crowding(childl, population, crowdingfactor, crowdingsubpop); sumstrength :- sumstrength - classifler[mortl].strength
+ childl.strength; { update sumstrength )
classifier[mortl] : childl; ( insert child łn mortl's place ) mort2 :- crowding(child2, population, crowdingfactor, crowdingsubpop); sumstrength :- sumstrength - classifier[mort2].strength
+ child2.strength; { update sumstrength )
classifier[mort2] :- child2; end; end end;
Wyd. 6.5. Algorytm genetyczny w SCS wykazuje znaczne podobieństwo do elementarnego algorytmu genetycznego (SGA) z rozdziału trzeciego, o czym świadczą procedura ga \ struktura danych garec
254
6. Wprowadzenie do genetycznych systemów uczących się
tystyki dotyczące populacji są obliczane w procedurze statistics, funkcja select dobiera pary partnerów (matel \ mate2), stosując metodę ruletki, a krzyżowanie zachodzi w procedurze crossover. Na tym jednak podobieństwa się kończą. Ponieważ naszym celem jest teraz znalezienie dobrze dostosowanego zespołu reguł, a nie jednej, najlepszej reguły, stosujemy metodę ścisku, aby wybrać klasyfikatory, które mają być zastąpione przez nowo powstałe potomstwo. Jak pamiętamy z rozdziału czwartego, w najprostszym modelu ze ściskiem wybiera się tylu kandydatów do (ewentualnego) zastąpienia przez danego
function worstofn(var population:poptype; n:lnteger):integer; ( select worst individual from random subpopulation of slze n } var j, worst, candidate:integer; worststrength:real; begln wlth populatlon do begin ( initialize with random selectlon } worst :- rnd(l, nclassIfier);
worststrength :- classifier[worst].strength; , ; { select and compare frora remaining subpopulation } if (n > 1) then for j :- 2 to n do begin candidate :-rnd(l, nclassifier); if worststrength > classifier[candidate].strength then begin
worst :- candidate; <
worststrength :- classifier[worst].strength; end;
'" ' end; '. .- ,-/ ',.- \ .. .r - - . ..
( return worst ) worstofn :- worst; '<>; end end;
functionmatchcount(var classifierl, classifier2:classtype;
nposition:integer):integer; ! count number of positions of similarlty ) var tempcount, j:integer; begin
if (classifierl.a - classifier2.a) then tempcount :- 1
else tempcount : 0; for j : 1 to nposition do
if (classifierl.c[j] - classifier2.c[j]) then tempcount :- tempcount + 1; matchcount :- tempcount; end;
function crowding(var child:classtype; var population:poptype;
crowdingfactor, crowdingsubpop:integer):integer; ( replacement using modified De Jong crowding ) var popmember, j, match, matchmax, mostsimilar:integer; begin with population do begin matchmax :- -1; mostsimilar : 0; if (crowdingfactor < 1) then crowdingfactor :- 1; for j : 1 to crowdingfactor do begin
popmember :- worstofn(population, crowdingsubpop); ( pick worst of n } match : matchcount(child, classifier[popmember], nposition); if match > matchmax then begin matchmax :- match; mostsimilar :- popmember; end; end;
crowding : mostsimilar; end end;
Wyd. 6.6. Metodę ścisku stosuje się w celu utrzymania różnorodności w populacji reguł. Funkcja paskalowa crowding wywołuje dwie inne funkcje matchcount \ worstofn
6.6. System klasyfikujący w Pascalu .
255
potomka, ile wynosi czynnik ścisku crowdingfactor. W zastosowanym tu wariancie wymaga się ponadto, aby kandydaci do usunięcia byli wybrani z podpopulacji o niskim przystosowaniu. Za każdym razem, gdy wybieramy ewentualnego kandydata do zastąpienia na podstawie podobieństwa, losujemy najpierw crowdingsubpop osobników z pełnej populacji, zachowując najsłabszego z nich. Następnie postępujemy zgodnie z metodą ścisku, takjak zostało to opisane w rozdziale czwartym. Dzięki tej modyfikacji wymiana dotyka osobników o niskiej wydajności, podobnych do nowo utworzonych członków populacji, którzy ich zastępują.
Metoda ścisku została zrealizowana w systemie SCS za pomocą funkcji paska-lowych worstofn, matchcount \ crowding, zamieszczonych na wyd. 6.6. Funkcja worstofn wylosowuje podpopulację o liczebności n (w naszym przypadku - o liczebności crowdingsubpop) z pełnej populacji, przyjmując jako wartość indeks najsłabszego spośród wybranych osobników. Funkcja matchcount porównuje dwa klasyfikatory pod względem podobieństwa, rejestrując liczbę zgodnych pozycji. Każdy przypadek zgodności na pozycjach zajmowanych przez warunki zwiększa licznik ojeden. To samo dotyczy pozycji zajmowanej przez akcję. Funkcja crowding korzysta z dwóch poprzednich funkcji w celu umieszczenia klasyfikatora potomnego (child) w populacji na miejscu okupowanym dotychczas przez blisko spokrewionego z nim, mało wydajnego klasyfikatora. Pętla for-do zostaje powtórzona łącznie crowdingfactor razy. Wewnątrz pętli dokonuje się wyboru klasyfikatora z populacji classifier przy użyciu funkcji worstofn, po czym wyznacza się liczbę zgodnych pozycji matchl) za pomocą funkcji matchcount. Jeśli liczba ta przekracza największą dotychczas znalezioną wartość matchmax, to nowy rekord wymazuje poprzedni. Na koniec funkcja crowding otrzymuje wartość równą numerowi klasyfikatora o największej zgodności.
Funkcja crowding dopełnia treści procedury ga (wyd. 6.5). Dwa osobniki zostają zatem zmuszone do przedwczesnego ustąpienia (zmienne indeksowe mortl i mort2}. Ponadto, przy zastępowaniu ich nowym potomstwem, wartość zmiennej sumstrength zostaje zaktualizowana, aby poprawnie określać całkowitą siłę zmienionej populacji.
6.6.5. A więc gdzie problem?
Opisując nasz uproszczony system klasyfikujący, przedstawiliśmy go tak, jakby zupełnie nie dbał o otaczający go świat. W gruncie rzeczy tak do tej pory było. Nie postawiliśmy mu żadnego zadania (reprezentowanego przez środowisko) ani nie określiliśmy sposobu interakcji ze środowiskiem. Obecnie naprawimy to zaniedbanie, formułując proste zadanie wyuczenia się funkcji boolowskiej reprezentującej logikę multipleksera z sześcioma liniami wejściowymi.
Wspomniana wyżej funkcja została przedstawiona schematycznie na rys. 6.2. Problem ten był rozpatrywany już wcześniej, tak z pozycji modelu konekcyjnego (Barto, Anandan i Anderson, 1985),jak i systemu klasyfikującego (Wilson, 1987a). Sześć linii
0 W stosunku do klasyfikatora child fyrzyp. tłum.).
256
6. Wprowadzenie do genetycznych systemów uczących się
Adres AO Al
Dane DO Dl DE D3
Rys. 6.2. Schemat ideowy sześciobitowego multipleksera
sygnałowych wchodzi do multipleksera. Sygnały odebrane z dwóch pierwszych linii (linii adresowych lub A-linii) zostają zdekodowane do postaci liczby dwójkowej. Adres ten określa, który z pozostałych czterech sygnałów (na liniach danych lub D-liniach) ma zostać przesłany na wyjście multipleksera. Na przykład na rysunku sygnał adresowy 11 określa adres 3, a zatem sygnał na linii danych 3 (równy 1) zostaje przesłany na wyjście.
i { envlronment declarations } type erecord-record
laddress, ldata, lsignal, address, output,
classlfieroutput:integer; signal:message; end;
var environrec:erecord;
eflle:text; .
procedurę generateslgnal(var environrec:erecord); ( generate random slgnal ) var j:integer; begin with envlronrec do for j :- 1 to lsignal do
tf flip(0.5) then signal[j] :- 1
else signal[j] :- 0 , i
' ' end; ' "' ' ' ' '" '
function decode(var mess:message; start, length:integer):integer; ( decode substring as unsigned binary integer ) var j, accum, powerof2:integer; begin
accum : 0; powerof2 : 1; for j :- start to start+length-1 do begin accum : accum + powerof2*mess[j]; powerof2 : powerof2 * 2; end; -;
decode : accum end;
Wyd. 6.7. Procedura environment wraz ze strukturą danych environrec implementują symulowane środowiskosystemuSCS
6.6. System klasyfikujący w Pascalu .
257
procedurę multiplexeroutput(var environrec:erecord);
{ calculate correct multiplexer output )
var j:integer;
begin with environrec do begin
( decode the address ) <,; :
address :- decode(signal,l,laddress); ( set the output }
output : signal[laddress + address + 1] end end;
procedurę environment(var environrec:erecord); ( coordinate multiplexer calculations ) begin
generatesignal(environrec);
multiplexeroutput(environrec); end;
Wyd. 6.7. (Cd.)
Działanie multipleksera objaśnić nietrudno, ale wciąż nie wiemy,jakie zadanie stoi przed systemem klasyfikującym. W programie SCS systemowi klasyfikującemu prezentuje się wygenerowany losowo ciąg przykładowych sygnałów. Na tej podstawie system ma za zadanie nauczyć się emulować działanie multipleksera. W tym celu system klasyfikujący raz po raz odpowiada na kolejne sygnały, otrzymując - lub nie - nagrodę w zależności od tego, czy udzielił poprawnej odpowiedzi. W ten sposób układ oceniający nagradza istniejące reguły stosownie do ich efektywności. Następnie algorytm genetyczny dorzuca nowe reguły w nadziei zwiększenia skuteczności systemu.
Środowisko multipleksera zostało zaprogramowane w Pascalu w sposób pokazany na wyd. 6.7. Rekord environrec typu erecord reprezentujący środowisko składa się z pól typu integer: laddress (długość adresu), ldata (długość danych), lsignal (długość sygnału), address (zdekodowany adres), output (poprawny sygnał na wyjściu) i classifierout-put (sygnał wyjściowy klasyfikatora). Ponadto typ erecord zawiera pole signal zawierające kopię wygenerowanego losowo komunikatu zewnętrznego.
( detector.scs: convert envlronmental states to env. raessage ) ( detector data declaratlons )
type drecord record
end; ( For thls problem, no detector record ls
requlred. Normally, the detector record i contains information for raapping envlronmental
state variables to the environmental blt-string. )
var detectrec:drecord; ( dummy detector record )
procedurę detectors(var environrec:erecord; var detectrec:drecord;
var envmessage:message);
( convert envlronmental state to env. message ) begln with environrec do { place signal message in env. message )
envmessage : signal end; ' '' / ; ' ' . . i . .
Wyd. 6.8. Procedura detectors tworzy komunikat zewnętrzny na podstawie stanu środowiska, posługując się w tym celu strukturą danych detectrec. W zadaniu o emulacji multipleksera jest to bardzo łatwe; w innych przypadkach może być potrzebne przekształcenie parametrów
258
6. Wprowadzenie do genetycznych systemów uczących się
Środowisko multipleksera wykonuje dwie zasadnicze czynności: generowanie losowego komunikatu oraz określenie poprawnej odpowiedzi (co jest potrzebne do późniejszego nagradzania). Jak widać z wyd. 6.8, procedura envlronment (środowisko) koordynuje te dwa działania za pomocą wywołań procedur generatesignal \ multiplexerout-put. Procedura generatesignal wytwarza nowy komunikat posługując się funkcją flip generującą losowe wartości boolowskie (dodatek B). Procedura multiplexeroutput deko-duje adres właściwej linii danych za pomocą funkcji decode (podobnej do funkcji o tej samej nazwie z rozdziału trzeciego) i zapisuje poprawny sygnał wyjściowy w polu output rekordu environrec. Wielkość ta zostaje później użyta przez podprogram decydujący o wypłacie nagrody danemu klasyfikatorowi.
6.6.6. Odczytaj komunikat, podejmij działanie
I tak oto wypełniliśmy wnętrznościami korpus naszego uproszczonego systemu klasyfikującego. Mamy również zasadniczy zrąb implementacji jego środowiska. Jak zatem skłonićje teraz do współdziałania? Cofając się pamięcią do schematu z rys. 6.1, przypomnijmy sobie, że system klasyfikujący otrzymuje informacje ze środowiska za pośrednictwem swoich detektorów i oddziałuje na nie za pomocą efektorów. Zajmiemy się teraz implementacją detektorów i efektorów w systemie SCS.
Na wydruku 6.8 widzimy opis struktur danych i procedur realizujących układ detekcyjny w systemie SCS. W rozważanym zadaniu działanie detektorów jest oczywiste. Procedura detectors kopiuje po prostu komunikat signal do zmiennej envmessage (komunikat zewnętrzny). W innego rodzaju zadaniach koniecznejest zakodowaniejednego lub więcej parametrów rzeczywistych w postaci ciągu dwójkowego. W tym celu są potrzebne struktury danych określające zakres i długość każdego parametru środowiska uwzględnionego w komunikacie. Potrzebne są także procedury kodujące i odwzorowujące w celu tworzenia i łączenia podciągów tworzących komunikat.
procedurę effector(var populatIon:poptype; var clearingrec:crecord;
var environrec:erecord);
( set action in obJect as dlctated by auction winner } begin with populatlon do wlth clearingrec do with envlronrec do classifleroutput :- classifler[wlnner).a end;
Wyd. 6.9. Procedura effecforodwzorowuje akcję zwycięskiego klasyfikatora w środowisku
Procedury układu detekcyjnego troszczą się o przekazanie informacji płynącej ze środowiska do systemu SCS, ale co z oddziaływaniem systemu na środowisko? Zajmuje się tym krótka procedura effector zamieszczona w wyd. 6.9. W naszym szczególnym przypadku działanie efektorajest oczywiste: po prostu podajemyjako sygnał wyjściowy multipleksera akcję klasyfikatora, który zwyciężył w przetargu. W innego typu zadaniach może to wymagać bardziej złożonych odzworowań i w takich przypadkach procedura effector będzie potrzebować bardziej rozbudowanych struktur danych i algorytmów. ,.
6.6. System klasyfikujący w Pascalu.
259
( reinforcement data declaratlons )
type rrecord record ( reinforcement record type)
reward, rewardcount, totalcount, count50, rewardcount50, proportionreward, i proportlonreward50:real;
lastwinner:integer; ....
end;
var reinforcementrec:rrecord;
rfile:text; ( reinforcement file - rfile )
function criterion(var rrec:rrecord; var environrec:erecord):boolean; ( return true if crifcerion is achieved ) var tempflag:boolean;
begin with rrec do with environrec do begin tempflag :- (output - classifieroutput); totalcount :- totalcount + 1; count50 : count50 + 1;
( increment reward counters }
if tempflag then begin < Tl "--;
rewardcount :- rewardcount + 1; rewardcount50 : rewardcount50 + 1; end;
( calculate reward proportions: running & last 50 ) proportionreward : rewardcount/totalcount; if ( round(count50 - 50.0) - 0) then begin proportionreward50 :- rewardcount50/50.0; rewardcount50 :- 0.0; count50 :- 0.0 ( reset ) end;
criterion :- tempflag; end end;
procedurę payreward(var population:poptype; var rrec:rrecord;
var clearingrec:crecord); ( pay reward to appropriate individual } begin with population do with rrec do with clearingrec do
with classifier[winner] do begin strength :- strength + reward; lastwinner : winner end end;
procedurę reinforcement(var reinforcementrec:rrecord; var population;poptyp'e;
var clearingrec:crecord; var environrec:erecord); ( make payment if criterion satisfied } begin
if criterlon(reinforcementrec, environrec) then
payreward(population, reinforcementrec, clearingrec); end; , , ... . , , . .- Ł. . v ..
Wyd. 6.10. Procedura reinforcement monitoruje wyniki i wypłaca nagrody za poprawne odpowiedzi
260
6. Wprowadzenie do genetycznych systemów uczących się
6.6.7. Zwycięzca bierze wszystko
Jestjeszczejeden istotny rodzaj informacji, która musi przepływać między środowiskiem a systemem klasyfikującym. Kiedy system klasyfikujący podejmuje poprawne działanie (tj. gdy na jego wyjściu pojawia się właściwy sygnał), musi wówczas otrzymać odpowiednią nagrodę od środowiska - rodzaj elektronicznej marchewki - która podtrzyma jego zachowanie. Funkcję tę moglibyśmy powierzyć człowiekowi - "trenerowi" czy "instruktorowi" systemu; jednak dla wygody i zachowaniajednolitości wprowadzimy automatyczne nadzorowanie jego funkcjonowania, rozpoznawanie poprawnego zachowania i wypłacanie stosownych nagród. Wszystkie te czynności realizuje procedura
program scs;
( SCS - A Simple Classifier System ) ( (C) David E. Goldberg, 1987 ) ( All Rights Reserved )
($1 declare.scs )
($1 random.apb )
($1 io.scs )
($1 utility.scs )
($1 environ.scs }
($1 detector.scs }
($1 perform.scs )
($1 aoc.scs )
($1 effector.scs }
($1 reInforc.scs ) ;
{$1 timekeep.scs )
($1 advance.scs }
($1 ga.scs )
($1 report.scs }
($1 initial.scs )
begin ( main ) ;"
initiallzation;
detectors(environrec, detectrec, envmessage); report(rep);
with timekeeprec do repeat timekeeper(timekeeprec); enviro'nment(environrec) ;
detectors(envlronrec, detectrec, envmessage); matchclassifiers(population, envmessage, matchllst); aoc(population, matchlist, clearłngrec); effector(population, clearlngrec, environrec);
reinforcement(reinforcementrec, populatlon, clearingrec, environrec); if reportflag then report(rep);
if consolereportflag then consolereport(reinforcementrec); if plotreportflag then plotreport(pfile, reinforcementrec); advance(clearingrec); if gaflag then begin ga(garec, population);
if reportflag then reportga(rep, garec, population); end;
until halt;
report(rep); ( flnal report } close(pfile); { close plot file } end.
Wyd.6.11. ProgramgłównykoordynujewszystkiedziałaniasystemuSCS v
6.6. System klasyfikujący w Pascalu .
261
reinforcement (wzmocnienie) w powiązaniu ze strukturą danych reinforcementrec (wyd. 6.10). Algorytmjest oczywisty: jeśli akcjajest poprawna, wypłaca się nagrodę. Oprócz wypłacania nagród dla zwycięzców, procedury wzmacniające śledzą ułamek poprawnych odpowiedzi od chwili rozpoczęcia pracy przez system i przez ostatnie 50 kroków czasowych. Odpowiednie statystyki są potem drukowane w różnych raportach.
6.6.8. Program główny
A teraz fanfary! Dysponując procedurą wzmacniającą, jesteśmy już w stanie poskładać-wszystko wjedną całość, czyli program główny (wyd. 6.11). Tekst programu rozpoczyna się od długiej listy dyrektyw dołączania plików, przypominających komentarze. Dyrektywy te, podobnie jak komentarze, umieszcza się wewnątrz nawiasów klamrowych ("{" i "}"); jednak znaki $1 następujące po lewym nawiasie oznaczają, że zawartość pliku o podanym dalej identyfikatorze (np. declare.scs) ma być podczas kompilacji dołączona w tym miejscu do programu. Wszystkie komponenty naszego systemu klasyfikującego zostają dołączone w ten sposób w trakcie kompilacji, właściwy zaś program główny zaczyna się dopiero od słowa kluczowego begin gdzieś pośrodku wydruku.
Dalej następuje inicjalizacja programu, zrealizowana za pomocą wywołania procedury initialization. W naszej skrótowej prezentacji działania systemu SCS pominęliśmy wiele prozaicznych aspektów programu, takich jak inicjalizacja, wejście i wyjście. Zainteresowany Czytelnik może znaleźć brakujące szczegóły przeglądając pełny tekst programu, zamieszczony w dodatku C. Po zakończeniu inicjalizacji przechodzimy do odebrania pierwszego komunikatu zewnętrznego (wywołanie procedury detectors). Pierwsza faza działań kończy się wywołaniem procedury report.
Główna petla czasowa jest zrealizowana za pomocą konstrukcji repeat-until, obejmującej resztę programu. Proces iteracji rozpoczyna się od wywołania procedury time-keeper, która zlicza iteracje i ustawia znaczniki sygnalizujące konieczność wykonania różnych powtarzających się cyklicznie czynności, jak drukowanie raportu lub wywołanie algorytmu genetycznego. Następnie program wywołuje kolejno procedury environment, detectors \ matchclassifiers, aby wygenerować komunikat, przekazać go do układu przetwarzania oraz sprawdzić dopasowanie klasyfikatorów. Kolejne wywołania procedur aoc, effector i reinforcement realizują przeprowadzenie przetargu i przyznanie ocen, podjęcie akcji oraz nagrodzenie dobrych wyników. !
Jeżeli nadszedł czas drukowania raportu (warunek reportflag ma wartość true), to zostaje wywołana procedura report. Analogicznie raporty przeznaczone do wyprowadzenia na konsoli oraz urządzeniu graficznym są drukowane w przypadku, gdy zostały ustawione ich znaczniki (za co odpowiada procedura timekeeper). Następnie procedura advance aktualizuje dane izby rozrachunkowej. W końcu, jeżeli nadszedł czas wywołania algorytmu genetycznego (warunek gaflag ma wartość true), to procedura ga wykonuje algorytm, a procedura reportga drukuje raport o wynikach. Proces może wtedy zatrzymać się ze zgrzytem, jeżeli użytkownik naciśnie klawisz na klawiaturze komputera (w takim przypadku funkcja paskalowa halt przerywa normalne wykonanie programu i upewnia się, czy użytkownik myśli serio o zakończeniu działań).
<*!'SSf"
262
6. Wprowadzenie do genetycznych systemów uczących się
6.7. Wyniki eksperymentów z systemem SCS___
Dysponując implementacją uproszczonego systemu klasyfikującego, możemy teraz przetestować jego zachowanie na przykładzie uczenia się funkcji multipleksera. Podamy teraz wartości parametrów środowiska i systemu klasyfikującego, które zostały wybrane do tych eksperymentów, a następnie omówimy wyniki trzech wariantów doświadczeń. Są to: eksperymenty z regułami idealnymi, eksperymenty z hierarchią domniemań oraz eksperymenty ze startem od zera.
. . .. , -, : \ : ; . . >.': . . . ., , , ' ; ^ , . . . ,
6.7.1. Parametry środowiska i systemu _______________________________________________
Parametry charakteryzujące środowisko i system zostały dobrane następująco:
nposition nclassifier
= 6
= 100 (wartość zmienna w przypadku dwóch pierwszych
wariantów)
pgeneral = 0,5
cbid = 0,1
bidsigma = 0,075
bidtax = 0,01
lifetax = 0,0
proportionselect = 0,2 *-'-
pmutation = 0,02 " ' " * ' s-
pcrossover = 1,0
gaperiod = 5000
crowdingfactor = 3 crowdingsubpop = 3 reward = 1
Dobór parametrów systemu klasyfikującego pozostaje wciąż swego rodzaju sztuką; można jednak otrzymać użyteczne wskazówki, obliczając oczekiwane stacjonarne mierniki zachowania oraz półokresy trwania przy różnych stopach podatkowych.
6.7.2. Reguty idealne i "dywersanci"
W celu przetestowania poprawności programu SCS wykonamy eksperyment z użyciem idealnego zestawu reguł, które zostały zamieszczone w tabl. 6.4. Zestaw ten składa się z ośmiu rozłącznych reguł, przy czym dla każdej wartości adresu potrzeba dwóch reguł. Na przykład reguły0
" Reguły są tu zakodowane w porządku D3D2...AtA0:output Qirzyp. tlum.).
6.7. Wyniki eksperymentów z systemem SCS______________________________________ 263
###ooo:0 :
###100:1
odpowiadają dwóm możliwym wartościom sygnału na linii danych DO. Aby przetestować działanie algorytmu przyznawania ocen, wprowadzimy zakłócenie do tego idealnego zestawu reguł w postaci paru dodatkowych złych reguł (które nazwiemy "dywer-santami"). Chcemy się przekonać, czy system klasyfikujący będzie potrafił podnosić siłę dobrych reguł i jednocześnie obniżać siłę złych.
Tablica6.4.Regutyidealnewzadaniuemulacjimultipleksera(6linii) '
Reguła
Cel
###0 00:0 0 Adres/0 Sygnał
##0#01:0 1 Adres/0 Sygnał
#0## 10:0 2 Adres/0 Sygnał
0### 1 1 :0 3 Adres/0 Sygnał
###1 00:1 0 Adres/ 1 Sygnał
##!#01:1 1 Adres/1 Sygnał
#1## 10:1 2 Adres/ 1 Sygnał
1### 11:1 3 Adres/ 1 Sygnał
Uruchamiając program SCS należy najpierw odpowiedzieć na serię zapytań, które stawia w trybie interakcyjnym (wyd. 6.12). Rezultatem tego dialogu jest inicjalizacja systemu klasyfikującego i wypisanie raportu początkowego (wyd. 6.13) wraz z pierwszym raportem migawkowym (wyd. 6.14). System klasyfikujący wykonuje 2000 iteracji, wypisując na zakończenie raport migawkowy (wyd. 6.15). Widzimy z wydruku,jaka siłę osiągnęły poprawne reguły. Istotnie, siła wszystkich dobrych klasyfikatorów doszła (lub prawie doszła) do swej stacjonarnej wartości
S,., =
1
C 4-
'~'tax ^
0,01+0,1
= 9,09
********************************************
A Simple Classlfier System - SCS (C) David E. Goldberg, 1987
All Rights Reserved ********************************************
Enter seed random number (O.0..1.0) > 0.3333
perfect.dta envlron.dta reinf.dta tlme.dta-ga.dta lst: plot.prn
Wyd. 6.12. Przed przystąpieniem do właściwych działań system odbywa wstępny dialog z użytkownikiem
Enter classifier Enter environment Enter relnforcement Enter timekeeper Enter gen. algorlthm Enter report Enter plot fłle f llename : fllename: f llename: filename: fllename: fllename: fllename:
264
6. Wprowadzenie do genetycznych systemów uczących się
********************************************
A Simple Classifier System - SCS (C) David E. Goldberg, 1987
All Rtghts Reserved ********************************************
Population Parameters
Number of classiflers - 10
Number of posltions 6
Bid coefficient - 0.1000
Bid spread - 0.0750
Bidding tax - 0.0100
Existence tax - 0.0000
Generality probability - 0.5000
Bid specificity base - 1.0000
Bid specificity mult. - 0.0000
Ebid specificity base - 1.0000
Ebid specificity mult. - 0.0000
Environmental Parameters (Multiplexer)
Number of address lines 2 Number of data lines 4 Total nunfber of lines - 6
Apportionment of Credlt Parameters Bucket brigade flag - false
Reinforcement Parameters Reinforcement reward
1.0
Timekeeper Parameters
Initial iteration - -0
Initial block - 0
Report period - 2000
Console report period 50
Plot report period - 50
Genetic algorithm period -1
Genetic Algorithm Parameters
Proportion to select/gen - 0.2000
Number to select - 1
Mutation probability - 0.0200
Crossover probability - 1.0000
Crowding factor - 3
Crowding subpopulation - 3
Wyd. 6.13. Raport początkowy zawiera zestawienie wszystkich parametrów systemowych
6.7. Wyniki eksperymentów z systemem SCS
265
a wysokości składanych przez nie ofert są bliskie swej wartości stacjonarnej
Natomiast obydwaj dywersanci osiągnęli siłę i wysokości ofert bliskie zeru.
1,00 -0,99 -0,98 -0,97 -O,96 -0,95 -0,94 -0,93 -0,92 -O,91 -0,90
0,2 0,4
O,6 0.8 1 1,2 1,4 1,6 1,8
Numer iteracji (x1000) Średnia ogólna + z 50 iteracji
Rys. 6.3. W eksperymencie z regułami idealnymi system SCS szybko zmniejsza siłę błędnych reguł, zwiększając jednocześnie siłę poprawnych reguł. W efekcie system osiąga niemal idealną skuteczność wyrażonąw terminach średniej w czasie
Na rysunku 6.3 pokazano wykresy ułamków poprawnych odpowiedzi w zależności od numeru iteracji. Przedstawiono ruchome średnie obejmujące ostatnie 50 iteracji oraz średnią za cały okres (do danej chwili). System klasyfikujący szybko eliminuje błędne reguły, osiągając w ten sposób niemal idealną sprawność. -. i,, r-,,
6.7.3. Hierarchia domniemań
Fakt, że system klasyfikujący potrafi odsiać kilka błędnych reguł z zestawu zawierającego idealne reguły jest wprawdzie pokrzepiający, ale musimy zadać sobie pytanie, co będzie się działo w mniej szczęśliwych okolicznościach, kiedy dysponujemy populacją niezupełnie idealnych reguł? Chcielibyśmy, aby w takiej sytuacji klasyfikatory same organizowały się w strukturę, którą Holland nazwał hierarchią domniemań [default hierarchy]. W hierarchii takiej reguły ogólne (zawierające wiele symboli #) dotyczą przypadków powszechnych, a reguły szczegółowe - przypadków wyjątkowych.
Jako przykład hierarchii domniemań rozważmy następujący zestaw reguł dla zada-niaemulacji multipleksera: <, ' ,',
266
6. Wprowadzenie do genetycznych systemów uczących się
Snapshot Report
[ Block:Iteration ] - [ 0:0 ] Current Multiplexer Status ; .
Signal
Decoded address Multlplexer output Classifler output
000000 0
Environmental message: No. Strength bid
0
000000
ebid M Classifier
1 10, .00 0 .00 0 .00 ###000: [0]
2 10. .00 0 .00 0 .00 ###100: [1]
3 10. ,00 0.00 0 .00 ##0#01 : [0]
4 10, ,00 0 .00 0 .00 ##!#01 : [1]
5 10 .00 0 .00 0 .00 #0##10 : [0]
6 10, ,00 0 .00 0 .00 #1##10: m
7 10 .00 0 .00 0 .00 0###11: : [0]
8 10 .00 0 .00 0 .00 1###11: ; [1]
9 10 .00 0 .00 0 .00 ######: [0]
10 10.00 0 .00 0 .00 ######: : [1]
New winner [1] : 01d winner [1] Reinforcement Report
0.0000
0.0000
0
Proportion Correct (from start) -Proportion Correct (last fifty) -Last winning classifler number
Wyd. 6.14. Pierwszy raport migawkowy ukazuje początkowy skład populacji reguł. W eksperymencie z idealnym zestawem reguł pierwszych osiem reguł to regufy idealne, a dwie ostatnie to dywersanci (błędne reguty) *
###000:0
##0#01:0
#0##10:0 ",
O###ll:0
######:1......................
Jeśli założymy, że każda nagrodzona reguła otrzymuje jednakową wypłatę oraz dodatkowo, że w przypadku, gdy dwie nie wykluczające się reguły składają oferty odpowiedzi na określony komunikat, to bardziej szczegółowa reguła wygrywa - będziemy mieIi właśnie do czynienia z zestawem reguł tworzących efektywną hierarchię domniemań. Jest to widoczne, gdyż cztery pierwsze reguły obsługują idealnie wszystkie wyjścia zerowe, a reguła uniwersalna obsługuje wyjścia jedynkowe. Zauważmy, że reguła uniwersalna jako taka jest poprawna tylko w połowie przypadków. Przy dobrze dobranym zestawie reguł (i przy zapewnieniu pierwszeństwa reguł szczegółowych przed ogólnymi) "pomyłki" reguly ogólnej są blokowane przez reguły szczegółowe, dzięki czemu reguła
6.7. Wyniki eksperymentów z systemem SCS
267
Snapshot Report
[ Block:Iteratlon ] - [ 0:2000 ] Current Multiplexer StaCus
Signal
Decoded address Multiplexer output Classifier output
Environmental message: No. Strength bid
100011 3 1 1
100011
ebid M Classifier
1 9 .09 0 .91 0. .94 ###000 : (0]
2 9 .09 0 .91 0. 97 ###100 : 11]
3 9 .09 0 .91 0. ,82 ##0#01 : [0]
4 9 .09 0 .91 0. ,85 ##!#01 : [1]
5 9 .09 0 .91 0, ,94 #0##10 : [0]
6 9 .09 0.91 0. ,82 #1##10 : [1]
7 9 .09 0 .91 1, ,06 0###11: [0]
8 9 .09 0 .91 0, .97 X 1###11: [1]
9 0 .00 0 .00 -0.06 X ###### : [0]
10 0 .00 0 .00 0 .10 X ######: [1]
New winner [8] : 01d winner [4] Reinforcement Report
Proportion Correct (from start) Proportion Correct (last fifty) Last winning classifier number
0.9990
1.0000
8
Wyd. 6.15. Ostatni raport migawkowy w eksperymencie z idealnym zestawem reguł (T=2000) demonstruje dużąsiłę reguł idealnych i niemal zerową siłę dywersantów
ogólna może otrzymać nagrodę za każdym razem, gdy zostanie użyta. W istocie powyższy zestaw pięciu reguł, współpracujących w ramach hierarchii domniemań, funkcjonuje równie dobrze, jak ośmioelementowy zestaw reguł idealnych, omawianych w poprzednim punkcie.
Niebawem dowiemy się, jak doprowadzić do formowania się hierarchii domniemań za pomocą odpowiedniego doboru parametrów wpływających na wysokość oferty. Przedtemjednak powinniśmy sobie wyjaśnić, dlaczego właściwie chcielibyśmy to osiągnąć. Hierarchie domniemań dają następujące korzyści w stosunku do zestawów reguł rozłącznych:
1) oszczędność;
2) powiększenie zbioru rozwiązań.
) ' ' '' : ' ^ ~'' ;'
Oszczędność hierarchii domniemań polega na tym, że zawierają one mniej reguł niż równoważne zestawy reguł rozłącznych. W naszym przykładzie zestaw reguł idealnych składa się z ośmiu reguł Qest to najmniejszy zbiór reguł rozłącznych), a przykładowa
268
6. Wprowadzenie do genetycznych systemów uczących się
hierarchia domniemań zawiera pięć reguł (i jest to najmniejsza taka hierarchia). Zasada oszczędności została szczegółowo przedyskutowana przez innych autorów (Holland, Ho-lyoak, Nisbett i Thagard, 1986), ale jej implikacje dla systemu odkrywającego reguły są widoczne. Jeżeli potrzebujemy mniej reguł, aby osiągnąć wysoką skuteczność, to czas oczekiwania na skompletowanie dobrego zestawu reguł skraca się i mamy większe szansę szybko dojść do dobrych wyników.
Hierarchie domniemań powiększają także zbiór możliwych rozwiązań. Aby się
0 tym przekonać, zwróćmy uwagę na to, że hierarchie domniemań nie wpływają ujemnie na skuteczność systemu w obecności zbioru idealnych, rozłącznych reguł. Istnienie innych podzbiorów reguł, które działają równie sprawnie może co najwyżej rozszerzyć zbiór rozwiązań. A ponieważ hierarchia domniemań stanowi strukturę niejawną czy też wirtualną (nie zaś fizyczną - reguły pozostają takie same), jej wprowadzenie do systemu nie odbywa się kosztem rozszerzenia reprezentacji. W ten sposób rozszerzenie zbioru możliwych rozwiązań bez zwiększenia rozmiarów reprezentacji przyczynia się do szybszego odkrycia zestawów reguł o wysokiej skuteczności.
Prócz skłonności do oszczędności oraz rozszerzenia zbioru rozwiązań, hierarchie domniemań sprzyjają nabywaniu i poszerzaniu wiedzy w sposób bardziej naturalny, niż jest to możliwe w przypadku wzajemnie wykluczających się struktur wiedzy (Holland
1 inni, 1986). Nie będziemy się rozwodzić na ten temat, ale nawet proste przykłady rzeczy powszechnie wiadomych ilustrują teze, że ludzie starają się organizować swoją wiedzę w postaci hierarchii domniemań. Na przykład znana każdemu uczniowi zasada mówiąca, że końcówkę -ówka, piszemy przez ó z wyjątkiem wyrazów skuwka i zasuwka, stanowi prostą hierarchię domniemań, a można podać wiele podobnych przykładów.
Hierarchie domniemań sprzyjają efektywniejszemu procesowi uczenia się systemów klasyfikujących, jak jednak możemy doprowadzić do ich utworzenia? Istnieje więcej niż jedno rozwiązanie tego problemu; najprostsze polega na tym, aby wysokość oferty uczynić proporcjonalną do iloczynu siły oraz pewnej funkcji liniowej szczegółowości reguły:
B, = C,M-f(Sp)-S, -- >'- ;
gdzief(Sp)-bidI +bid2 Sp. W tym przypadku stacjonarna wartość siły reguły wyniesie
R..,. !
S.. =
Chidf(Sp) + C,u
a stacjonarna wysokość oferty Cudf(Sp)Ra
B.. =
CMdf(Sp) + Ct
Zakładając, że CM - 0,1 i Ctm = 0,01, i przyjmując, że reguła uniwersalna oferuje 25% Cbkl, a najbardziej szczegółowa reguła - 100% Chid, możemy obliczyć względne siły (w stosunku do wysokości nagrody) i wysokości ofert dla naszych reguł. Wyniki zostały zamieszczone w tabl. 6.5. Jeżeli założymy istnienie idealnej hierarchii domniemań, to
~
V '
6.7. Wyniki eksperymentów z systemem SCS
269
każdy wyjątek spowoduje ukrycie błędu reguły ogólnej; wszystkie reguły wchodzące w skład hierarchii domniemań powinny być nagradzane w każdym przypadku, kiedy wygrały przetarg. Teoretycznie możemy się spodziewać, że ten prosty mechanizm, przy którym wysokość oferty jest funkcją rosnącą szczegółowości, prowadzi do wytworzenia się stabilnej hierarchii domniemań.
Tablica 6.5. Znormalizowane wartości stacjonarne siły i wysokości oferty dla eksperymentu z hierar-chiądomniemań
Szczegółowość (Sp) f(Sp) Sss/ Rss Bvs//?vs.
0 0,250 28,57 0,714
1 ". 0,375 21,05 0,789
2 ; 0,500 16,67 0,833
3 0,625 13,79 0,862
4 0,750 11,76 0,882
5 0,875 10,25 0,897
6 1,000 9,09 0,909
Aby sprawdzić to w praktyce, wykonajmy prosty eksperyment polegający na porównaniu mechanizmu uwzględniającego szczegółowość z mechanizmem, w którym wysokość oferty jest proporcjonalna do samej siły. Nie musimy w tym celu zmieniać tekstu programu, gdyż mamy do dyspozycji cztery parametry bid], bld2, ebidl \ ebid2, dzięki którym możemy kontrolować rodzaj mechanizmu składania ofert. Aby uzyskać hierarchię domniemań opisaną wyżej (tabl. 6.5), wybieramy następujące wartości parametrów:
1,00 -0,99 -
0,98 -
0,97 -
1 .s 1 0,96 -0,95 -0,94 - K/W^XA>*~*-jl^
V VX^"Y^^TuiluBdug 0,93 - f*^ /W V V
0,92 - ef \ / Y V 4 Y
t 0,91 - i y "
c 0,90 - * ,"
1 0,89 - i
g. 0,88 ->
- 0,87 -
m 0,86 - 1
S 0,85 -
5 0,84 -
0,83 -
0,82 -
0,81 -i
0 0,2 0,4 0,6 0,8 1 1.2 1,4 1,6 1,8 2
Numer iteracji (x1000) D Średnia ogólna + z 50 iteracji
Rys. 6.4. Bez mechanizmu regulującego wysokość ofert zależnie od szczegółowości reguł, system klasyfikujący nie jest w stanie posługiwać się należycie hierarchią domniemań
270
6. Wprowadzenie do genetycznych systemów uczących się
bidI = ebidJ=0,250 ; .,-
bid2 = ebid2=0,l25
Natomiast aby zapobiec utworzeniu się takiej hierarchii przyjmujemy .
bidl = ebidl = },0
bid2 = ebid2 = 0,0 .- -.*, - ,-. ;..-
Wykonano dwa przebiegi programu SCS z zestawem pięciu reguł opisanych wcześniej (z dodatkiem kilku dywersantów). Wyniki obu eksperymentow,jednego bez, a drugiego z hierarchią domniemań zostały przedstawione na rys. 6.4 i 6.5 odpowiednio. Jak należało się spodziewać, w pierwszym przypadku nie udało się osiągnąć rezultatów tak dobrych jak w drugim. Bez odpowiedniego mechanizmu regulującego wysokość ofert, reguła domniemana (###### : 1) wygrywa z regułami szczegółowymi (idealnymi) wtedy, gdy nie powinna. Te pomyłki obniżają siłę reguły domniemanej, dzięki czemu właściwe reguły szczegółowe zaczynają znowu wygrywać. W tej sytuacji reguła domniemana nie popełniajuż tylu błędów ijej siła zaczyna wzrastać, i znowu zaczyna wygrywać wtedy, gdy nie powinna. Bez właściwego mechanizmu ofert, który sprzyjałby tworzeniu się stabilnej hierarchii domniemań, ten cykl zdarzeń będzie się ciągle powtarzać, obniżając w sposób nieunikniony skuteczność systemu. Natomiast w eksperymencie uwzględniającym zależność wysokości ofert od szczegółowości wystąpiła dostatecznie duża różnica między regułami szczegółowymi a regułą ogólną (w reżimie stacjonarnym), by umożliwić konsekwentną przewagę reguł szczegółowych w przypadkach, gdy mają one zastosowanie. Dzięki temu możliwejest wytworzenie się prawidłowej hierarchii domniemań, ojaką nam chodzi.
1,00
'R
O,2 O,4
1,6
0.6 0,8 1 1,2 1.4
Numeriteracji(x1000) o Średnia ogólna + z 50 iteracji
1.8
Rys. 6.5. Mając mechanizm regulujący wysokość ofert zależnie od szczegółowości reguł, system klasyfikujący z hierarchią domniemań osiąga niemal idealną skuteczność
6.7. Wyniki eksperymentów z systemem SCS .
271
6.7.4. Start od zera: Model Tabula rasa
W tym punkcie zajmiemy się zbadaniem zachowania uproszczonego systemu klasyfikującego dla zadania emulacji multipleksera, startując od wygenerowanego losowo zestawu 100 reguł. Wykonujemy dwa eksperymenty z systemem SCS -jeden bez, a drugi z użyciem algorytmu genetycznego. Możemy dzięki temu rozróżnić efekty uczenia się będące skutkiem oddziaływania algorytmu przyznawania ocen na pierwotny zestaw reguł od podobnych efektów, wynikających z wprowadzania do systemu nowych reguł przez algorytm genetyczny.
W obu przypadkach rozpoczynamy od jednakowych losowych zestawów 100 reguł, używając tej samej stałej początkowej generatora losowego i prawdopodobieństwa "ogólności" pgeneml=Q,5. Wartości pozostałych parametrów dobrano tak jak w poprzednim punkcie. W eksperymencie z zastosowaniem algorytmu genetycznego był on wywoływany co 5000 iteracji i za każdym razem 20 procent bieżącej populacji podlegało reprodukcji, krzyżowaniu, mutacji i zastępowaniu metodą ścisku.
Wyniki eksperymentu bez użycia algorytmu genetycznego są pokazane na rys. 6.6. Możemy zaobserwować, jak algorytm przyznawania ocen reguluje siłę reguł, osiągając stacjonarną skuteczność 88% poprawnych odpowiedzi. Chociaż średnie ruchome z 50 iteracji skaczą w obie strony wokół tego poziomu, to na dłuższą metę system klasyfikujący jest w stanie utrzymać ten względnie wysoki poziom skuteczności nawet bez pomocy algorytmu genetycznego. Fakt, że system klasyfikujący bez algorytmu genetycznego uzyskuje o tyle lepsze wyniki niż to, co można by osiągnąć przy losowych rzutach monetą, nie powinien zaskakiwać. Losowy zestaw 100 regułjest dostatecznie bogatym zestawem dla tego dość skromnego zadania, a mechanizm przetargu umożliwiający tworzenie się hierarchii domniemań umożliwia skuteczne współdziałanie dobrych reguł.
0,3
40
.20 30
Numeriteracji(x1000) n Średnia ogólna ----- z 50 iteracji
Rys. 6.6. Nawet bez użycia algorytmu genetycznego system SCS jest w stanie osiągnąć wyższą skuteczność niż algorytm losowy, organizując istniejące reguty w hierarchię domniemań
272
6. Wprowadzenie do genetycznych systemów uczących się
Moglibyśmy mieć wątpliwości, czy przy tak wysokiej skuteczności działania bez udziału algorytmu genetycznego jego zastosowanie przyniesie jakąś poprawę wyników, ale bylibyśmy w błędzie. Wyniki osiągnięte z udziałem algorytmu genetycznego, pokazane na rys. 6.7, są lepsze od poprzednich, dochodząc aż do 95-96% poprawnych odpowiedzi. Jest to fakt szczególnie godny uwagi ze względu na stosunkowo rzadkie interwencje algorytmu genetycznego; populacja została bowiem wymieniona w całości tylko dwukrotnie w ciągu 50000 iteracji (0,2- 100-50000/5000 = 200 osobników potomnych wytworzonych przez AG).
0,3
10 2O 30
Numer iteracji (x1000) Średnia ogólna ------ z 50 iteracji
40
Rys. 6.7. Po włączeniu algorytmu genetycznego nowe reguty są wprowadzane do pamięci systemu w regularnych odstępach czasu, dzięki czemu skuteczność systemu przewyższa nawet tę z rys. 6.6.
Z jednej strony wyniki te wyglądają zachęcająco. System klasyfikujący z algorytmem genetycznym działał lepiej niż bez niego, w dodatku osiągnięty poziom skuteczności mógłby rywalizować z ludzką dokładnością. Z drugiej jednak strony mamy tu do czynienia z dość banalnym zadaniem, w którym liczba wszystkich możliwych sytuacji wynosi tylko 26 = 64. Pamiętajmy wszakże, że naszym celem było zbudowanie możliwie najprostszego działającego systemu klasyfikującego. Nie wyposażyliśmy go w rozmaite dość oczywiste udoskonalenia (w następnym rozdziale opowiemy o systemie klasyfikującym, który z równym powodzeniem dawał sobie radę ze znacznie poważniejszymi zadaniami tego samego typu, gdzie liczba różnych komunikatów przekraczała milion). Ponadto sami (celowo) związaliśmy tu sobie ręce, używając algorytmu genetycznego jako jedynej heurystycznej metody odkrywania nowych reguł. Istnieją też inne sposoby generowania dobrych reguł. Moglibyśmy powiązać komunikaty zewnętrzne z poprawnymi odpowiedziami (dostępnymi w fazie nagradzania) i włączać te idealne - choć może zbyt szczegółowe - reguły do populacji albo moglibyśmy uogólniać takie idealne reguły, umieszczając symbole # na pewnej liczbie pozycji. Chociaż można - i pewnie należałoby
6.8. Podsumowanie
273
- próbować zwiększyć skuteczność, stosując takie lub podobne techniki, naszym celem tutaj było wyodrębnienie wkładu, jaki wnosi algorytm genetyczny jako mechanizm odkrywania reguł. Uczyniwszy to, mamy teraz większą swobodę w poszukiwaniu innych sposobów doskonalenia mechanizmów uczenia się w systemach klasyfikujących i innych genetycznych systemach uczących się.
6.8. Podsumowanie
Rozdział ten był poświęcony podstawom, zasadom działania, implementacji oraz zachowaniu systemu klasyfikującego. Systemy klasyfikujące są odmianą genetycznych systemów uczących się (systemów GBML), które łączą w sobie prosty system produkcji oparty na regułach kodowanych binarnie, algorytm przyznawania ocen będący modelem "rynku usług informacyjnych" i algorytm genetyczny. Systemy klasyfikujące i pochodne systemy znajdują coraz szersze zastosowania w nauce, technice i ekonomice.
Kośćcem systemu klasyfikującego jest jego układ przetwarzania komunikatów, stanowiący rodzaj systemu produkcji (czyli systemu opartego na regułach przepisywania). Eksplozja systemów doradczych opartych na regułach dodaje wiarygodności przekonaniu, że reguły są adekwatnym sposobem wyrażania ludzkiej wiedzy i sposobu rozumienia. Podobnie jak w innych systemach produkcji, reguły przepisywania w systemach klasyfikujących mają postać "jeśli to "; jednak w tych ostatnich warunki i akcje są kodowane w postaci ciągów dwójkowych o ustalonej długości; zawierają przy tym jawny mechanizm rozpoznawania wzorców, z symbolem uniwersalnym "#". Ponadto systemy klasyfikujące odbiegają od głównego nurtu systemów doradczych pod tym względem, że opierają się na równoległym uaktywnianiu reguł. Pozwala to uniknąć wąskiego gardła, jakie powstaje w systemach stosujących uaktywnianie sekwencyjne ^edna reguła na raz), dzięki czemu możliwe jest jednoczesne wykonywanie wielu działań fizycznych i konceptualnych. Również pod względem mechanizmu decydowania o wyborze jednej spośród konkurujących, wzajemnie wykluczających się możliwości, systemy klasyfikujące odbiegają od głównego nurtu, stosując kryterium konkurencyjności zamiast kolejności lub innej arbitralnej procedury.
W większości systemów klasyfikujących, klasyfikatory nadają komunikaty, które zostają umieszczone na liście komunikatów, co z kolei powoduje uaktywnienie innych klasyfikatorów lub uruchomienia efektorów zdolnych do wykonywania akcji. Obecność centralnej listy komunikatów zapewnia istnienie scentralizowanego kanału wymiany informacji. Ponieważ pojemność listy komunikatów jest ograniczona, trzeba zapewnić jakiś mechanizm preferencji dla konkurujących ze sobą komunikatów. W większości systemów klasyfikujących stosuje się w tym celu algorytm przyznawania ocen, będący modelem rynku usług, który zapewnia właściwą ocenę i wybór reguł. Reguły składają oferty na prawo do nadania komunikatu (lub uruchomienia efektorów); kwoty proponowane w zwycięskich ofertach zostają wypłacone klasyfikatorom, które uprzednio dostarczyły uaktywniających komunikatów. W ten sposób tworzy się łańcuch pośredników między środowiskiem a końcową akcją. Współzawodnictwo zapewnia uczciwość tego
274
6. Wprowadzenie do genetycznych systemów uczących się
mechanizmu; użyteczne klasyfikatory żyją i prosperują, podczas gdy ich mniej udani konkurenci kończą bankructwem.
Kwoty otrzymywane i wypłacane przez reguły zwiększają lub zmniejszają ich stan posiadania, zwany siłą. Siła determinuje wysokość oferty składanej przez regułę, a prócz tego stanowi miarę jej przystosowania podczas działania algorytmu genetycznego. Algorytm genetyczny używany w systemach klasyfikujących jest bardzo zbliżony do algorytmów stosowanych w zadaniach poszukiwania; jednak reprodukcji jest poddawana za każdym razem tylko część populacji i więcej uwagi zwraca się na wybór osobników podlegających wymianie.
Opisano implementację w Pascalu uproszczonej wersji systemu klasyfikującego (SCS). W celu przetestowania systemu na konkretnym zadaniu zaprogramowano środowisko systemu klasyfikującego w postaci funkcji boolowskiej reprezentującej sześcio-bitowy multiplekser. W pierwszych eksperymentach system uczy się pomijać błędne reguły, a jednocześnie wzmacniać osiem idealnych reguł. W następnych eksperymentach, dzięki wprowadzeniu mechanizmu uzależniającego wysokość ofert od stopnia szczegółowości reguł, system uczy się korzystać ze zbioru reguł tworzących hierarchię domniemań. Istnienie hierarchii domniemań umożliwia systemom klasyfikującym wykonywać więcej tańszym kosztem, dzięki oszczędnym zestawom reguł i powiększeniu zbioru rozwiązań. Hierarchie domniemań odpowiadają również ludzkim intuicjom dotyczącym hierarchii pojęciowych i wyjątków. W bardziej swobodnych eksperymentach typu tabula rasa, startując od 100 wygenerowanych losowo reguł, system klasyfikujący bez pomocy algorytmu genetycznego osiąga wyniki lepsze niż przy losowym zgadywaniu, a przy zastosowaniu algorytmu genetycznego uzyskuje dalszą poprawę. Stanowi to zachętę do bliższego zapoznania się z innymi zastosowaniami genetycznych systemów uczących się, czym zajmiemy się w następnym rozdziale.
6.9. Zadania
6.1. Pewien klasyfikator jest stale aktywny i przy tym obciążony łącznym podatkiem ostopieC(M = 0,01,natomiastjegowspółczynnikinwestycyjnywynosiCWrf= 0,1. Zakładając, że klasyfikator otrzymuje 10 punktów nagrody na każde uaktywnienie, oblicz jego siłę w warunkach stacjonarnych. Wykonaj podobne obliczenia dla stopy podatkowej równej 0,0 oraz 0,02.
6.2. Siła początkowa pewnego klasyfikatora wynosi 100 punktów. Klasyfikator nie zostaje ani razu uaktywniony, ale jest obciążony podatkiem o stopie 0,01. Wyznacz liczby iteracji, po których siła klasyfikatora spada do 90, 80, 70, 60 i 50 punktów. Wykonaj analogiczne obliczenia dla stóp podatkowych 0,1 i 0,001.
6.3. Czas, po którym klasyfikator traci połowę swej początkowej siły wskutek opodatkowania, nazywa się pótokresem życia. Wyprowadź wzór ogólny na półokres ży-ciajako funkcję stopy podatkowej Ctax. Naszkicuj wykres tej funkcji.
6.9. Zadania
275
6.4. Pewien klasyfikator jest stale aktywny, jego współczynnik inwestycyjny wynosi CWd = 0,05, a stopa podatkowa - C/ai = 0,01. Przy każdym uaktywnieniu otrzymuje on 1 punkt. Oblicz stacjonarną wysokość oferty tego klasyfikatora. Wykonaj analogiczne obliczenia dla CWrf = 0,01 i 0,1.
6.5. Klasyfikator jest uaktywniany w każdej iteracji, jego współczynnik inwestycyjny wynosi CW(/ = 0,1, a stopa podatkowa - zero. Klasyfikator otrzymuje 10 punktów co drugą iterację. Po dostatecznie długim okresie, siła tego klasyfikatora oscyluje między dwiema wartościami. Wyznacz te stacjonarne wartości siły i odpowiadające im wysokości ofert.
6.6. Klasyfikator jest uaktywniany w każdej iteracji, ale otrzymuje wypłatę R co każdych k iteracji. Wyprowadź równania opisujące wartości stacjonarne siły tego klasyfikatora, zakładając, że jego współczynnik inwestycyjny wynosi Cbid i że nie płaci on podatku.
6.7. W systemie klasyfikującym przeznaczonym do emulacji multipleksera o sześciu liniach wejściowych zastosowano sześciopozycyjny kod trójkowy dla warunku i jednopozycyjny kod dwójkowy dla akcji. Wyznacz liczbę wszystkich możliwych reguł w tym zadaniu. Wyznacz liczbę schematów, które można określić dla tego zadania.
6.8. W pewnym systemie klasyfikującym zastosowano dwupozycyjny kod trójkowy dla warunku i jednopozycyjny kod dwójkowy dla akcji. Inaczej mówiąc, reguły w tym systemie mają postać ogólną
CC:A
gdzie Ce {0, 1, #} i Ae {0, 1}. W wybranej losowo populacji liczącej =12 reguł (każdy symbol trójkowy jednakowo prawdopodobny i każdy symbol dwój-kowyjednakowo prawdopodobny) znalazły się po trzy egzemplarze następujących reguł:
00:0 '. "' .
11:1 "' ' "'"' ' "" ' '' ' ' ' '' '" '' "
##:0
##:1
Oblicz prawdopodobieństwo a priori wylosowania identycznej populacji.
6.9. Załóżmy, że w poprzednim zadaniu prawdopodobieństwo wylosowania symbolu uniwersalnego (#) jest równe pg(Wra, = 0,8, a pozostałe dwa symbole są wybierane z jednakowym prawdopodobieństwem. Oblicz przy tych założeniach prawdopodobieństwo a priori wylosowania populacji takiej, jak w zadaniu 6.8.
6.10. Klasyfikator Cl zostaje uaktywniony i wysyła komunikat do klasyfikatora C2. Następnie zostaje uaktywniony klasyfikator C2 i zapoczątkowuje akcję, za którą otrzymuje nagrodę 10 punktów. Zakładając, że oba klasyfikatory mają współczynnik inwestycyjny równy 0,1 i płacą podatek o łącznej stopie 0,02, oblicz stacjonarne wartości siły i wysokości ofert obydwu klasyfikatorów, jeżeli opisany proces współdziałania klasyfikatorów powtarza się w nieskończoność. Wykonaj analogiczne obliczenia przy podwojonej stopie podatkowej.
276
6. Wprowadzenie do genetycznych systemów uczących się
6.10. Ćwiczenia komputerowe
A. Zbadaj efekty ścisku w systemie SCS. Startując od tej samej populacji reguł (użyj w tym celu tej samej wartości początkowej dla generatora liczb losowych, jeśli generujesz losową populacje początkową), prześledź przebieg procesu uczenia się systemu dla wartości crowdingfactormwnei 1 (bez ścisku) i 3 ("normalny" współczynnik ścisku). Porównaj i omów skuteczność i skład zestawów reguł otrzymanych po 50000 iteracji. ^-
B. Wybierz jakiekolwiek proste zadanie uczenia się reguł i zaprogramuj odpowiedni interfejs z systemem SCS. Które podprogramy należy w tym celu zmienić? Pamiętaj, aby wprowadzać zmiany etapami, testując każdy moduł osobno. Jest rzeczą bardzo trudną skutecznie przetestować system klasyfikujący jako niepodzielną całość, ze względu na jego wielkość oraz elementy losowości (zazwyczaj nie znamy poprawnych odpowiedzi, które można porównać z wynikami testów).
C. Zaimplementuj procedurę wzmacniającą, która nagradza klasyfikatory w SCS, przydzielając ptscorrect punktów za poprawną odpowiedź i ptswrong punktów za błędną odpowiedź. Wykonaj eksperyment z emulacją multipleksera (6 linii) dla ptscor-rect=\, ptswrong=0,5. Porównaj skuteczność tego systemu z wynikami przedstawionymi w tym rozdziale.
D. Zaimplementuj i przetestuj układ wykonawczy dla mniej okrojonej wersji systemu klasyfikującego, z listą komunikatów, wewnętrznym przetwarzaniem komunikatów i efektorami zależnymi od komunikatów. Jakie procedury i struktury danych trzeba zmodyfikować, aby zaimplementować ten układ? Spróbuj zachować przy tym modularną strukturę systemu SCS.
E. Obmyśl metodę podziału wypłat ułatwiającą formowanie się gatunków (i nisz) w zbiorze klasyfikatorów w systemie SCS. Zaimplementuj ten mechanizm i porównaj z metodą "wszystko dla zwycięzcy" zastosowaną w SCS. Przedyskutuj zalety i wady obu metod ze względu na skuteczność i efektywność obliczeniową.
Wyszukiwarka
Podobne podstrony:
07 Zastosowania genetycznych systemów uczących się
Ćwiczenie 2 2 Wprowadzenie do systemu Windows 2000;XP;2003
Lab Wprowadzenie do systemu UNIX
wprowadzenie do systemu linux
Wprowadzenie Do Systemu Linuks Linuks pl
Lab Wprowadzenie do systemu UNIX
Wprowadzenie do systemów baz danych
WYKŁAD 1 Wprowadzenie do biotechnologii farmaceutycznej
Medycyna manualna Wprowadzenie do teorii, rozpoznawanie i leczenie
01 Wprowadzenie do programowania w jezyku C
wprowadzenie do buddyzmu z islamskiego punktu widzenia
1 wprowadzenie do statystyki statystyka opisowa
2006 06 Wstęp do Scrum [Inzynieria Oprogramowania]
Informatyka Wprowadzenie Do Informatyki Ver 0 95
więcej podobnych podstron