System klasyfikatorów uczących się - Learning classifier system

Wizualizacja 2D reguł LCS ucząca się przybliżania funkcji 3D. Każda niebieska elipsa reprezentuje indywidualną regułę obejmującą część przestrzeni rozwiązania. (Na podstawie zdjęć zrobionych z XCSF za zgodą Martina Butza)

Uczenia systemów klasyfikatora lub ACC są paradygmatem uczących reguł opartych na sposobach, które łączą element wykrywania (np zazwyczaj algorytm genetyczny ) ze składnikiem uczenia (wykonując jedną nadzorowane uczenia , uczenia wzmacniającą lub bez nadzoru uczenia się ). Systemy klasyfikatorów uczących się starają się zidentyfikować zestaw reguł zależnych od kontekstu, które zbiorczo przechowują i stosują wiedzę w sposób fragmentaryczny w celu prognozowania (np. Modelowanie zachowania , klasyfikacja , eksploracja danych , regresja , przybliżanie funkcji lub strategia gry ). Takie podejście umożliwia podzielenie złożonych przestrzeni rozwiązań na mniejsze, prostsze części.

Podstawowe koncepcje leżące u podstaw uczenia się systemów klasyfikatorów pochodzą z prób modelowania złożonych systemów adaptacyjnych przy użyciu agentów opartych na regułach w celu stworzenia sztucznego systemu poznawczego (tj. Sztucznej inteligencji ).

Metodologia

Architektura i komponenty danego systemu klasyfikatorów uczących się mogą być dość zróżnicowane. Warto pomyśleć o LCS jako o maszynie składającej się z kilku współdziałających ze sobą komponentów. Komponenty mogą być dodawane lub usuwane, a istniejące komponenty mogą być modyfikowane / wymieniane w celu dostosowania do wymagań danej dziedziny problemowej (np. Algorytmiczne bloki konstrukcyjne) lub w celu uczynienia algorytmu wystarczająco elastycznym, aby mógł działać w wielu różnych dziedzinach problemowych. W rezultacie paradygmat LCS można elastycznie zastosować do wielu dziedzin problemowych, które wymagają uczenia maszynowego . Główne podziały wśród wdrożeń LCS są następujące: (1) architektura w stylu Michigan kontra architektura w stylu Pittsburgha, (2) uczenie ze wzmocnieniem vs. uczenie nadzorowane , (3) uczenie przyrostowe vs. uczenie wsadowe, (4) uczenie online vs. . uczenie się w trybie offline , (5) sprawność oparta na sile kontra kondycja oparta na dokładności oraz (6) kompletne mapowanie działań a mapowanie najlepszych działań. Te podziały niekoniecznie wykluczają się wzajemnie. Na przykład XCS, najbardziej znany i najlepiej zbadany algorytm LCS, jest w stylu Michigan, został zaprojektowany do uczenia się ze wzmocnieniem, ale może również przeprowadzać uczenie nadzorowane, stosuje uczenie przyrostowe, które może odbywać się w trybie online lub offline, stosuje kondycję opartą na dokładności i poszukuje aby wygenerować pełne mapowanie działań.

Elementy ogólnego algorytmu LCS

Schemat krokowy ilustrujący cykl uczenia się generycznego systemu klasyfikatorów uczących się w stylu Michigan, który przeprowadza uczenie nadzorowane.

Mając na uwadze, że LCS jest paradygmatem opartego na genetyce uczenia maszynowego, a nie konkretną metodą, poniżej przedstawiono kluczowe elementy ogólnego, nowoczesnego (tj. Post-XCS) algorytmu LCS. Dla uproszczenia skupmy się na architekturze w stylu Michigan z uczeniem nadzorowanym. Zobacz ilustracje po prawej stronie przedstawiające kolejne etapy tego typu ogólnego LCS.

Środowisko

Środowisko jest źródłem danych, na podstawie których LCS się uczy. Może to być offline, skończony zbiór danych szkoleniowych (charakterystyczny dla problemu eksploracji danych , klasyfikacji lub regresji) lub sekwencyjny strumień online instancji szkoleniowych na żywo. Zakłada się, że każda instancja szkoleniowa zawiera pewną liczbę cech (nazywanych również atrybutami lub zmiennymi niezależnymi ) i pojedynczy interesujący punkt końcowy (nazywany również klasą , działaniem , fenotypem , prognozą lub zmienną zależną ). Część uczenia się LCS może obejmować wybór funkcji , dlatego nie wszystkie funkcje w danych szkoleniowych muszą mieć charakter informacyjny. Zbiór wartości cech instancji jest powszechnie nazywany stanem . Dla uproszczenia załóżmy domenę przykład problem z Boolean / binarnych cech i Boolean / binarnego klasy. W przypadku systemów w stylu Michigan, jedna instancja ze środowiska jest szkolona w każdym cyklu uczenia się (tj. Uczenie przyrostowe). Systemy w stylu Pittsburgha przeprowadzają uczenie wsadowe, w którym zestawy reguł są oceniane w każdej iteracji na podstawie większości lub wszystkich danych szkoleniowych.

Reguła / klasyfikator / populacja

Reguła jest zależną od kontekstu zależnością między wartościami stanu a pewnymi przewidywaniami. Reguły zwykle przyjmują postać wyrażenia {JEŚLI: WTEDY} (np. { JEŻELI 'warunek' TO 'akcja'} lub jako bardziej szczegółowy przykład {JEŻELI 'czerwony' AND 'ośmiokąt' TO 'znak stopu'} ). Krytyczną koncepcją zarówno w LCS, jak iw uczeniu maszynowym opartym na regułach jest to, że pojedyncza reguła sama w sobie nie jest modelem, ponieważ reguła ma zastosowanie tylko wtedy, gdy jej warunek jest spełniony. Pomyśl o regule jako o „modelu lokalnym” przestrzeni rozwiązań.

Reguły można przedstawić na wiele różnych sposobów, aby obsługiwać różne typy danych (np. Binarne, o wartościach dyskretnych, porządkowych, ciągłych). Biorąc pod uwagę dane binarne, LCS tradycyjnie stosuje trójskładnikową reprezentację reguł (tj. Reguły mogą zawierać 0, 1 lub „#” dla każdej funkcji w danych). Symbol „nie obchodzi mnie” (tj. „#”) Służy jako symbol wieloznaczny w ramach warunku reguły, umożliwiając regułom i systemowi jako całemu uogólnienie relacji między cechami a docelowym punktem końcowym, który ma być przewidywany. Rozważ następującą regułę (# 1 ### 0 ~ 1) (tj. Warunek ~ czynność). Regułę tę można zinterpretować jako: JEŻELI druga cecha = 1 ORAZ szósta cecha = 0 WTEDY klasa predykcyjna = 1. Powiedzielibyśmy, że druga i szósta cecha została określona w tej regule, podczas gdy pozostałe zostały uogólnione. Ta reguła i odpowiadająca jej prognoza mają zastosowanie tylko do instancji, gdy warunek reguły jest spełniony przez instancję. Jest to częściej określane jako dopasowywanie. W LCS w stylu Michigan każda reguła ma swoją poprawność, a także szereg innych powiązanych z nią parametrów reguł, które mogą opisywać liczbę kopii tej reguły, które istnieją (tj. Liczebność ), wiek reguły, jego dokładność lub dokładność przewidywań dotyczących nagrody oraz inne statystyki opisowe lub empiryczne. Reguła wraz z jej parametrami jest często nazywana klasyfikatorem . W systemach typu Michigan klasyfikatory są zawarte w populacji [P], która ma zdefiniowaną przez użytkownika maksymalną liczbę klasyfikatorów. W przeciwieństwie do większości algorytmów wyszukiwania stochastycznego (np. Algorytmów ewolucyjnych ), populacje LCS są początkowo puste (tj. Nie ma potrzeby losowego inicjowania populacji reguł). Zamiast tego klasyfikatory zostaną początkowo wprowadzone do populacji z mechanizmem pokrywającym.

W każdym LCS wytrenowany model jest zestawem reguł / klasyfikatorów, a nie pojedynczą regułą / klasyfikatorem. W LCS w stylu Michigan cała wyuczona (i opcjonalnie skompaktowana) populacja klasyfikatorów tworzy model predykcyjny.

Pasujący

Jednym z najbardziej krytycznych i często czasochłonnych elementów LCS jest proces dopasowywania. Pierwszy krok w cyklu uczenia LCS pobiera pojedynczą instancję szkoleniową ze środowiska i przekazuje ją do [P], gdzie ma miejsce dopasowywanie. W kroku drugim każda reguła w [P] jest teraz porównywana z instancją uczącą, aby zobaczyć, które reguły pasują (tj. Są kontekstowo istotne dla bieżącej instancji). W kroku trzecim wszystkie pasujące reguły są przenoszone do zestawu dopasowań [M]. Reguła pasuje do instancji uczącej, jeśli wszystkie wartości funkcji określone w warunku reguły są równoważne odpowiedniej wartości funkcji w instancji uczącej. Na przykład, zakładając, że instancja szkoleniowa to (001001 ~ 0), te reguły będą pasować: (### 0 ## ~ 0), (00 ### 1 ~ 0), (# 01001 ~ 1), ale te reguły nie (1 ##### ~ 0), (000 ## 1 ~ 0), (# 0 # 1 # 0 ~ 1). Zauważ, że przy dopasowywaniu punkt końcowy / akcja określona przez regułę nie jest brana pod uwagę. W rezultacie zestaw dopasowań może zawierać klasyfikatory, które proponują sprzeczne działania. W czwartym kroku, ponieważ przeprowadzamy uczenie nadzorowane, [M] jest dzielone na prawidłowy zbiór [C] i nieprawidłowy zestaw [I]. Reguła dopasowywania trafia do właściwego zestawu, jeśli proponuje prawidłowe działanie (na podstawie znanego działania instancji szkoleniowej), w przeciwnym razie przechodzi do [I]. W uczeniu się ze wzmocnieniem LCS zamiast tego zostałby utworzony zestaw akcji [A], ponieważ prawidłowe działanie nie jest znane.

Pokrycie

W tym momencie cyklu uczenia się, jeśli żaden klasyfikator nie przeszedł do [M] lub [C] (jak miałoby to miejsce w przypadku, gdy populacja zaczyna pusta), stosowany jest mechanizm pokrycia (piąty krok). Pokrycie jest formą inicjalizacji inteligentnej populacji online . Pokrycie losowo generuje regułę pasującą do bieżącej instancji szkoleniowej (aw przypadku uczenia nadzorowanego ta reguła jest również generowana z odpowiednim działaniem. Zakładając, że instancja szkoleniowa to (001001 ~ 0)), pokrycie może wygenerować dowolną z następujących reguł: (# 0 # 0 ## ~ 0), (001001 ~ 0), (# 010 ## ~ 0). Pokrycie nie tylko gwarantuje, że w każdym cyklu uczenia się istnieje co najmniej jedna poprawna reguła dopasowania w [C], ale że każda reguła zainicjowana w populacji będzie pasować do co najmniej jednej instancji szkoleniowej. Zapobiega to badaniu przez LCS przestrzeni wyszukiwania reguł, które nie pasują do żadnych instancji szkoleniowych.

Aktualizacje parametrów / przypisanie punktów / nauka

W szóstym kroku parametry reguły dowolnej reguły w [M] są aktualizowane, aby odzwierciedlić nowe doświadczenie zdobyte w bieżącej instancji szkoleniowej. W zależności od algorytmu LCS na tym etapie można przeprowadzić szereg aktualizacji. W przypadku uczenia nadzorowanego możemy po prostu zaktualizować dokładność / błąd reguły. Dokładność / błąd reguły różni się od dokładności / błędu modelu, ponieważ nie jest obliczana na podstawie całych danych uczących, ale tylko na podstawie wszystkich dopasowanych wystąpień. Dokładność reguły jest obliczana poprzez podzielenie liczby przypadków, w których reguła była w prawidłowym zestawie [C], przez liczbę razy, gdy była w zestawie dopasowanym [M]. Dokładność reguł można traktować jako „dokładność lokalną”. Poprawność reguł jest również aktualizowana w tym miejscu i jest zwykle obliczana jako funkcja dokładności reguł. Pojęcie sprawności zaczerpnięto bezpośrednio z klasycznych algorytmów genetycznych . Należy pamiętać, że istnieje wiele odmian sposobu, w jaki LCS aktualizuje parametry w celu przypisania punktów i uczenia się.

Subsumowanie

Na siódmym etapie zazwyczaj stosuje się mechanizm subsumpcji . Podsumowanie jest jawnym mechanizmem uogólniania, który łączy klasyfikatory pokrywające nadmiarowe części obszaru problemu. Klasyfikator podliczający efektywnie absorbuje klasyfikator podliczany (i zwiększa jego liczebność). Może się to zdarzyć tylko wtedy, gdy klasyfikator podrzędny jest bardziej ogólny, równie dokładny i obejmuje całą przestrzeń problemową klasyfikatora, który obejmuje.

Wykrywanie reguł / algorytm genetyczny

W ósmym kroku LCS przyjmuje wysoce elitarny algorytm genetyczny (GA), który wybierze dwa klasyfikatory rodzicielskie na podstawie sprawności (przeżycie najlepiej przystosowanych). Rodzice są wybierani z [C], zazwyczaj za pomocą selekcji turniejowej . Niektóre systemy stosowały selekcję na kole ruletki lub selekcję deterministyczną i mają inaczej wybrane reguły rodzicielskie z [P] - selekcja panmiktyczna lub z [M]). Operatory krzyżowania i mutacji są teraz stosowane do generowania dwóch nowych reguł dotyczących potomstwa. W tym momencie zarówno zasady dotyczące rodzica, jak i potomstwa są zwracane do [P]. Algorytm genetyczny LCS jest wysoce elitarny, ponieważ każda iteracja uczenia się zachowuje ogromną większość populacji. Wykrywanie reguł można alternatywnie przeprowadzić inną metodą, taką jak estymacja algorytmu dystrybucji , ale zdecydowanie najpowszechniejszym podejściem jest GA. Algorytmy ewolucyjne, takie jak GA, wykorzystują przeszukiwanie stochastyczne, co sprawia, że ​​LCS jest algorytmem stochastycznym. LCS stara się sprytnie eksplorować przestrzeń wyszukiwania, ale nie przeprowadza wyczerpującego wyszukiwania kombinacji reguł i nie gwarantuje zbieżności w optymalnym rozwiązaniu.

Usunięcie

Ostatnim krokiem w ogólnym cyklu uczenia LCS jest utrzymanie maksymalnej wielkości populacji. Mechanizm usuwania wybierze klasyfikatory do usunięcia (zwykle przy użyciu wyboru koła ruletki). Prawdopodobieństwo, że klasyfikator zostanie wybrany do usunięcia, jest odwrotnie proporcjonalne do jego przydatności. Gdy klasyfikator zostanie wybrany do usunięcia, jego parametr liczbowy jest zmniejszany o jeden. Zmniejszenie liczebności klasyfikatora do zera powoduje całkowite usunięcie go z populacji.

Trening

LCS będzie cyklicznie przechodzić przez te kroki dla pewnej liczby iteracji szkoleniowych zdefiniowanych przez użytkownika lub do momentu spełnienia określonych przez użytkownika kryteriów zakończenia. W przypadku nauki online LCS otrzyma w każdej iteracji całkowicie nową instancję szkoleniową ze środowiska. W przypadku uczenia się w trybie offline LCS przeprowadzi iterację przez ograniczony zestaw danych szkoleniowych. Gdy osiągnie ostatnią instancję w zbiorze danych, wróci do pierwszej instancji i ponownie przejdzie przez zbiór danych.

Reguła zagęszczania

Po zakończeniu szkolenia populacja reguł nieuchronnie będzie zawierała słabe, zbędne i niedoświadczone zasady. Powszechne jest stosowanie zagęszczania reguł lub heurystyki kondensacji jako kroku przetwarzania końcowego. Ta wynikająca z tego zbiorcza populacja reguł jest gotowa do zastosowania jako model predykcyjny (np. Do prognozowania instancji testowych) i / lub do interpretacji w celu odkrywania wiedzy .

Prognoza

Niezależnie od tego, czy zastosowano zagęszczanie reguł, wynik algorytmu LCS jest populacją klasyfikatorów, które można zastosować do prognozowania wcześniej niewidocznych wystąpień. Mechanizm przewidywania nie jest częścią samego nadzorowanego cyklu uczenia LCS, jednak odgrywałby ważną rolę w cyklu uczenia się LCS ze wzmocnieniem. Na razie zastanawiamy się, jak można zastosować mechanizm przewidywania do tworzenia prognoz do testowania danych. Podczas prognozowania składniki uczenia LCS są dezaktywowane, aby populacja nie mogła dalej uczyć się na podstawie napływających danych testowych. Instancja testowa jest przekazywana do [P], gdzie zestaw dopasowań [M] jest tworzony jak zwykle. W tym momencie zestaw dopasowań jest w inny sposób przekazywany do tablicy predykcji. Reguły w zestawie dopasowań mogą przewidywać różne działania, dlatego stosowany jest schemat głosowania. W prostym schemacie głosowania wygrywa akcja z najsilniejszym popierającym „głosem” z pasujących reguł i staje się wybraną prognozą. Nie wszystkie zasady dają równy głos. Siła głosu za jedną regułą jest raczej proporcjonalna do jej liczebności i przydatności. Ten schemat głosowania i natura wiedzy LCS o sklepie sugeruje, że algorytmy LCS są niejawnie uczniami zespołowymi .

Interpretacja

Poszczególne reguły LCS są zazwyczaj czytelne dla człowieka wyrażenia IF: THEN. Reguły tworzące model predykcyjny LCS można uszeregować według różnych parametrów reguł i sprawdzić ręcznie. Zaproponowano również globalne strategie kierowania odkrywaniem wiedzy za pomocą statystyki i grafiki. W odniesieniu do innych zaawansowanych podejść do uczenia maszynowego, takich jak sztuczne sieci neuronowe , losowe lasy lub programowanie genetyczne , systemy klasyfikatorów uczących się są szczególnie dobrze dostosowane do problemów wymagających interpretowalnych rozwiązań.

Historia

Wczesne lata

John Henry Holland był najbardziej znany ze swojej pracy popularyzującej algorytmy genetyczne (GA), dzięki swojej przełomowej książce „Adaptation in Natural and Artificial Systems” w 1975 roku oraz sformalizowaniu twierdzenia Hollanda o schemacie . W 1976 roku Holland opracował konceptualizację rozszerzenia koncepcji AH do tego, co nazwał „systemem poznawczym”, i przedstawił pierwszy szczegółowy opis tego, co stanie się znane jako pierwszy system klasyfikujący uczenie się w artykule „Cognitive Systems based on Adaptive Algorithms” (Systemy poznawcze oparte na algorytmach adaptacyjnych). Ten pierwszy system, nazwany Cognitive System One (CS-1), został pomyślany jako narzędzie do modelowania, zaprojektowane do modelowania rzeczywistego systemu (tj. Środowiska ) z nieznaną podstawową dynamiką przy użyciu populacji czytelnych dla człowieka reguł. Celem było stworzenie zestawu reguł przeprowadzania uczenia maszynowego online w celu dostosowania się do środowiska w oparciu o rzadkie wypłaty / nagrody (tj. Uczenie się ze wzmocnieniem) i zastosowanie tych reguł w celu wygenerowania zachowania pasującego do rzeczywistego systemu. Ta wczesna, ambitna realizacja została później uznana za zbyt złożoną, dającą niespójne rezultaty.

Od 1980 roku Kenneth de Jong i jego uczeń Stephen Smith przyjęli inne podejście do uczenia maszynowego opartego na regułach w (LS-1) , gdzie uczenie się było postrzegane jako proces optymalizacji offline, a nie proces adaptacji online. To nowe podejście było bardziej podobne do standardowego algorytmu genetycznego, ale wyewoluowało niezależne zestawy reguł. Od tego czasu metody LCS inspirowane platformą nauczania online wprowadzoną przez Holandię na University of Michigan były określane jako LCS w stylu Michigan , a te zainspirowane przez Smitha i De Jonga na University of Pittsburgh zostały określone jako w stylu Pittsburgh LCS . W 1986 roku Holandia opracowała coś, co można by uznać za standardowy LCS w stylu Michigan na następną dekadę.

Inne ważne pojęcia, które pojawiły się w pierwszych dniach LCS Badaniami objęto (1) sformalizowanie z algorytmem wiadro brygady (BBA) dla przypisania kredytowej / uczenia się, (2) wybór zasad nadrzędnych ze wspólnego „niszy ekologicznej” (czyli mecz zbiór [M]), a nie z całej populacji [P], (3) obejmujący , najpierw wprowadzony jako operator tworzenia , (4) formalizacja zbioru działań [A], (5) uproszczona architektura algorytmu, (6 ) sprawność oparta na sile , (7) rozważenie jednoetapowych lub nadzorowanych problemów w uczeniu się i wprowadzenie prawidłowego zestawu [C], (8) dopasowanie oparte na dokładności (9) połączenie logiki rozmytej z LCS (które później zrodziła linię rozmytych algorytmów LCS ), (10) zachęcanie do długich łańcuchów działań i domyślnych hierarchii w celu poprawy wydajności w przypadku problemów wieloetapowych, (11) badanie utajonego uczenia się (które później zainspirowało nową gałąź przewidujących systemów klasyfikatorów (ACS)), oraz (12) wprowadzenie pierwszego przypisania punktów w stylu Q-learning technika. Chociaż nie wszystkie te koncepcje są stosowane we współczesnych algorytmach LCS, każdy z nich był przełomem w rozwoju paradygmatu LCS.

Rewolucja

Zainteresowanie systemami klasyfikatorów uczenia się wzrosło w połowie lat dziewięćdziesiątych, głównie z powodu dwóch wydarzeń; opracowanie algorytmu Q-Learning do uczenia ze wzmocnieniem oraz wprowadzenie znacznie uproszczonej architektury LCS w stylu Michigan przez Stewarta Wilsona. Wilson's Zeroth-level Classifier System (ZCS) skupił się na zwiększeniu zrozumiałości algorytmów w oparciu o standardową implementację LCS firmy Hollands. Osiągnięto to częściowo poprzez usunięcie licytowania według reguł i wewnętrznej listy wiadomości, niezbędnych do pierwotnego przypisania punktów BBA, i zastąpienie go hybrydową strategią BBA / Q-Learning . ZCS wykazał, że znacznie prostsza architektura LCS może działać równie dobrze, jak oryginalne, bardziej złożone implementacje. Jednak ZCS nadal cierpiał z powodu wad wydajności, w tym mnożenia się zbyt ogólnych klasyfikatorów.

W 1995 roku Wilson opublikował swój przełomowy artykuł „Klasyfikator sprawności oparty na dokładności”, w którym przedstawił system klasyfikatorów XCS . XCS wykorzystał uproszczoną architekturę ZCS i dodał dopasowanie oparte na dokładności, niszowe GA (działające w zestawie działań [A]), wyraźny mechanizm uogólnienia zwany subsumpcją oraz adaptację przypisania punktów Q-Learning . XCS został spopularyzowany przez jego zdolność do osiągania optymalnych wyników przy jednoczesnym rozwijaniu dokładnych i maksymalnie ogólnych klasyfikatorów, a także dzięki imponującej elastyczności w problemach (zdolnej do wykonywania zarówno uczenia ze wzmocnieniem, jak i uczenia się nadzorowanego ). XCS stał się później najbardziej znanym i najlepiej zbadanym algorytmem LCS i zdefiniował nową rodzinę opartego na dokładności LCS . ZCS alternatywnie stał się synonimem LCS opartego na sile . XCS jest również ważny, ponieważ z powodzeniem wypełnia lukę między LCS a dziedziną uczenia się przez wzmacnianie . Po sukcesie XCS, LCS zostały później opisane jako systemy uczenia się ze wzmocnieniem wyposażone w możliwość generalizacji. Uczenie się ze wzmocnieniem zazwyczaj ma na celu nauczenie się funkcji wartości, która odwzorowuje pełną reprezentację przestrzeni stanu / działania. Podobnie, projekt XCS napędza go do tworzenia kompleksowej i dokładnej reprezentacji obszaru problemu (tj. Kompletnej mapy ), zamiast skupiać się na niszach o wysokich dochodach w środowisku (jak miało to miejsce w przypadku LCS opartego na sile). Koncepcyjnie kompletne mapy nie tylko pokazują, co należy zrobić lub co jest poprawne, ale także to, czego nie należy robić lub co jest nieprawidłowe. Z drugiej strony, większość LCS opartych na sile lub wyłącznie nadzorowanych uczących się LCS poszukuje zestawu reguł skutecznych uogólnień w postaci mapy najlepszego działania (lub mapy częściowej ). Porównania między siłą a kondycją opartą na dokładności oraz kompletnymi i najlepszymi mapami akcji zostały od tego czasu zbadane bardziej szczegółowo.

W ślad za XCS

XCS zainspirowało rozwój zupełnie nowej generacji algorytmów i aplikacji LCS. W 1995 roku Congdon jako pierwszy zastosował LCS w rzeczywistych badaniach epidemiologicznych chorób, a następnie Holmes, który opracował BOOLE ++ , EpiCS , a później EpiXCS do klasyfikacji epidemiologicznej . Te wczesne prace zainspirowały późniejsze zainteresowanie zastosowaniem algorytmów LCS do złożonych i zakrojonych na dużą skalę zadań eksploracji danych, których przykładem są aplikacje bioinformatyczne . W 1998 roku Stolzmann wprowadził systemy klasyfikatorów antycypacyjnych (ACS), które obejmowały reguły w postaci „warunku-działania-skutku” zamiast klasycznej reprezentacji „warunek-działanie”. ACS został zaprojektowany do przewidywania percepcyjnych konsekwencji działania we wszystkich możliwych sytuacjach w środowisku. Innymi słowy, system ewoluuje model, który nie tylko precyzuje, co należy zrobić w danej sytuacji, ale także dostarcza informacji o tym, co się stanie po wykonaniu określonej akcji. Ta rodzina algorytmów LCS najlepiej nadaje się do wieloetapowych problemów, planowania, przyspieszania uczenia się lub ujednoznaczniania percepcyjnego aliasingu (tj. Gdy ta sama obserwacja jest uzyskiwana w różnych stanach, ale wymaga różnych działań). Butz później kontynuował tę przewidywalną rodzinę LCS, opracowując szereg ulepszeń w stosunku do oryginalnej metody. W 2002 roku Wilson wprowadził XCSF , dodając obliczoną akcję w celu wykonania przybliżenia funkcji. W 2003 roku Bernado-Mansilla wprowadził system wspomaganego klasyfikatora (UCS) , który wyspecjalizował algorytm XCS do nadzorowanego uczenia się , rozwiązywania problemów jednoetapowych i tworzenia najlepszego zestawu działań. UCS usunęło strategię uczenia się ze wzmocnieniem na rzecz prostej, opartej na dokładności reguły dopasowania, a także faz uczenia się eksploracji / wykorzystywania, charakterystycznych dla wielu uczniów uczących się wzmacniania. Bull wprowadził prosty system LCS oparty na dokładności (YCS) i prosty system klasyfikatora minimalnego LCS (MCS) oparty na wytrzymałości w celu lepszego zrozumienia teoretycznego struktury LCS. Bacardit wprowadził GAssist i BioHEL , LCS w stylu Pittsburgha przeznaczone do eksploracji danych i skalowalności do dużych zbiorów danych w zastosowaniach bioinformatycznych . W 2008 roku Drugowitsch opublikował książkę zatytułowaną „Design and Analysis of Learning Classifier Systems” zawierającą teoretyczne badanie algorytmów LCS. Butz wprowadził pierwszą zasadę wizualizacji uczenia się online w GUI dla XCSF (patrz ilustracja na górze tej strony). Urbanowicz rozszerzył ramy UCS i wprowadził ExSTraCS, specjalnie zaprojektowany do nadzorowanego uczenia się w hałaśliwych domenach problemowych (np. Epidemiologia i bioinformatyka). ExSTraCS zintegrowała (1) wiedzę ekspercką w celu kierowania algorytmem pokrycia i algorytmu genetycznego w kierunku ważnych cech danych, (2) forma pamięci długotrwałej zwana śledzeniem atrybutów, umożliwiająca bardziej efektywne uczenie się i charakteryzację heterogenicznych wzorców danych oraz (3) elastyczna reprezentacja reguły podobna do mieszanej reprezentacji listy atrybutów dyskretnych i ciągłych Bacardita. Zarówno Bacardit, jak i Urbanowicz badali strategie statystyczne i wizualizacyjne w celu interpretacji reguł LCS i przeprowadzania odkrywania wiedzy na potrzeby eksploracji danych. Browne i Iqbal zbadali koncepcję ponownego wykorzystania bloków konstrukcyjnych w postaci fragmentów kodu i jako pierwsi rozwiązali problem testu porównawczego multipleksera 135-bitowego, najpierw ucząc się przydatnych bloków konstrukcyjnych na podstawie prostszych problemów dotyczących multiplekserów. ExSTraCS 2.0 został później wprowadzony w celu poprawy skalowalności LCS w stylu Michigan, z powodzeniem rozwiązując problem testu porównawczego 135-bitowego multipleksera po raz pierwszy bezpośrednio. Problem multipleksera n-bitowego jest wysoce epistatyczny i niejednorodny , co czyni go bardzo trudnym zadaniem uczenia maszynowego .

Warianty

System klasyfikatorów uczenia się w stylu Michigan

LCS w stylu Michigan charakteryzują się populacją reguł, w których algorytm genetyczny działa na poziomie poszczególnych reguł, a rozwiązanie jest reprezentowane przez całą populację reguł. Systemy w stylu Michigan uczą się również stopniowo, co umożliwia im zarówno uczenie się ze wzmocnieniem, jak i uczenie nadzorowane, a także uczenie się online i offline. Systemy w stylu Michigan mają tę zaletę, że można je zastosować w większej liczbie dziedzin problemowych i mają wyjątkowe zalety uczenia się przyrostowego.

System klasyfikatorów uczenia się w stylu Pittsburgha

LCS w stylu Pittsburgha charakteryzują się populacją zestawów reguł o zmiennej długości, z których każdy jest potencjalnym rozwiązaniem. Algorytm genetyczny zazwyczaj działa na poziomie całego zestawu reguł. Systemy w stylu Pittsburgha mogą również w unikalny sposób rozwijać uporządkowane listy reguł, a także stosować regułę domyślną. Systemy te mają naturalną zaletę polegającą na identyfikowaniu mniejszych zestawów reguł, co sprawia, że ​​systemy te są bardziej czytelne w kontekście ręcznej kontroli reguł.

Systemy hybrydowe

Zaproponowano również systemy, które starają się połączyć kluczowe mocne strony obu systemów.

Zalety

  • Adaptacyjne: potrafią zaaklimatyzować się w zmieniającym się środowisku w przypadku nauki online.
  • Bez modelu: przyjmują ograniczone założenia dotyczące środowiska lub wzorców powiązań w ramach danych.
    • Mogą modelować złożone, epistatyczne, heterogeniczne lub rozproszone podstawowe wzorce bez polegania na wcześniejszej wiedzy.
    • Nie przyjmują żadnych założeń dotyczących liczby cech predykcyjnych i nieprzewidywalnych w danych.
  • Uczący się w zespole: do danej instancji nie jest stosowany żaden pojedynczy model, który ogólnie dostarcza prognozy. Zamiast tego odpowiedni i często sprzeczny zestaw reguł przyczynia się do „głosowania”, które można zinterpretować jako rozmytą prognozę.
  • Uczący się stochastycznie: Niedeterministyczne uczenie się jest korzystne w przypadku problemów na dużą skalę lub o dużej złożoności, w których deterministyczne lub wyczerpujące uczenie się staje się trudne do rozwiązania.
  • W sposób dorozumiany wielocelowy: zasady ewoluują w kierunku dokładności z ukrytymi i jawnymi naciskami zachęcającymi do maksymalnej ogólności / prostoty. Ta niejawna presja na generalizację jest unikalna dla LCS. W efekcie bardziej ogólne zasady będą pojawiać się częściej w zestawach meczowych. Z kolei mają częstszą okazję do bycia wybranymi na rodziców i przekazania swoich bardziej ogólnych (genomów) reguł potomstwu.
  • Interpretowalne: w interesie eksploracji danych i odkrywania wiedzy poszczególne reguły LCS są logiczne i można je uczynić tak, aby były interpretowalne przez człowieka, JEŻELI: TO stwierdzenia. Wprowadzono również skuteczne strategie umożliwiające globalne odkrywanie wiedzy identyfikującej istotne cechy i wzorce skojarzeń z populacji reguł jako całości.
  • Elastyczna aplikacja
    • Problemy jedno- lub wieloetapowe
    • Uczenie się nadzorowane, wzmacniające lub nienadzorowane
    • Klasyfikacja binarna i wieloklasowa
    • Regresja
    • Funkcje dyskretne lub ciągłe (lub mieszanka obu typów)
    • Czyste lub hałaśliwe domeny problematyczne
    • Zrównoważone lub niezrównoważone zbiory danych.
    • Uwzględnia brakujące dane (tj. Brakujące wartości funkcji w instancjach szkoleniowych)

Niedogodności

  • Ograniczona dostępność oprogramowania: istnieje ograniczona liczba dostępnych wdrożeń LCS typu open source, a jeszcze mniej, które są zaprojektowane tak, aby były przyjazne dla użytkownika lub dostępne dla praktyków uczenia maszynowego.
  • Interpretacja: Chociaż algorytmy LCS są z pewnością bardziej interpretowalne niż niektórzy zaawansowani uczniowie maszyn, użytkownicy muszą interpretować zestaw reguł (czasami duże zestawy reguł, aby zrozumieć model LCS). Metody zagęszczania reguł i strategie interpretacji pozostają obszarem aktywnych badań.
  • Dowody teorii / zbieżności: za algorytmami LCS kryje się stosunkowo niewielka ilość prac teoretycznych. Wynika to prawdopodobnie z ich względnej złożoności algorytmicznej (zastosowanie szeregu oddziałujących ze sobą komponentów), a także z ich stochastycznej natury.
  • Overfitting: Jak każdy uczący się maszyn, LCS może cierpieć z powodu nadmiernego dopasowania pomimo ukrytych i jawnych nacisków na generalizację.
  • Parametry uruchamiania: LCS często mają wiele parametrów uruchamiania do rozważenia / optymalizacji. Zazwyczaj większość parametrów można pozostawić domyślnym parametrom określonym przez społeczność, z wyjątkiem dwóch parametrów krytycznych: maksymalnego rozmiaru populacji reguł i maksymalnej liczby iteracji uczenia się. Optymalizacja tych parametrów może być bardzo zależna od problemu.
  • Rozgłos: pomimo swojego wieku algorytmy LCS nadal nie są szeroko znane nawet w społecznościach zajmujących się uczeniem maszynowym. W rezultacie algorytmy LCS są rzadko brane pod uwagę w porównaniu z innymi uznanymi metodami uczenia maszynowego. Jest to prawdopodobnie spowodowane następującymi czynnikami: (1) LCS to stosunkowo skomplikowane podejście algorytmiczne, (2) LCS, modelowanie oparte na regułach to inny paradygmat modelowania niż prawie wszystkie inne podejścia do uczenia maszynowego. (3) Implementacje oprogramowania LCS nie są tak powszechne.
  • Kosztowne obliczeniowo: algorytmy LCS są z pewnością bardziej wykonalne niż niektóre wyczerpujące metody, ale mogą być kosztowne obliczeniowo. W przypadku prostych, liniowych problemów związanych z uczeniem się nie ma potrzeby stosowania LCS. Algorytmy LCS najlepiej nadają się do złożonych przestrzeni problemowych lub przestrzeni problemowych, w których istnieje niewielka wcześniejsza wiedza.

Domeny problemowe

  • Sterowanie adaptacyjne
  • Eksploracja danych
  • Projektowanie inżynieryjne
  • Wybór funkcji
  • Aproksymacja funkcji
  • Rozgrywka
  • Klasyfikacja obrazu
  • Obsługa wiedzy
  • Diagnoza medyczna
  • Modelowanie
  • Nawigacja
  • Optymalizacja
  • Prognoza
  • Zapytanie
  • Robotyka
  • Wytyczanie
  • Indukcja reguł
  • Planowanie
  • Strategia

Terminologia

Nazwa „Learning Classifier System (LCS)” jest nieco myląca, ponieważ istnieje wiele algorytmów uczenia maszynowego , które „uczą się klasyfikować” (np. Drzewa decyzyjne , sztuczne sieci neuronowe ), ale nie są LCS. Termin „uczenie maszynowe oparte na regułach ( RBML )” jest przydatny, ponieważ lepiej oddaje istotny element „oparty na regułach” tych systemów, ale także uogólnia metody, które nie są uważane za LCS (np. Uczenie się reguł asocjacji lub sztuczne układy odpornościowe ). Bardziej ogólne terminy, takie jak „uczenie maszynowe w oparciu o genetykę”, a nawet „algorytm genetyczny”, zostały również zastosowane w odniesieniu do czegoś, co byłoby bardziej charakterystycznie zdefiniowane jako system klasyfikujący uczenie się. Ze względu na podobieństwo do algorytmów genetycznych systemy klasyfikatorów uczenia się w stylu Pittsburgha są czasami ogólnie określane jako „algorytmy genetyczne”. Poza tym niektóre algorytmy LCS lub blisko spokrewnione metody były określane jako „systemy poznawcze”, „czynniki adaptacyjne”, „ systemy produkcyjne ” lub ogólnie jako „system klasyfikujący”. Ta zmienność terminologii powoduje pewne zamieszanie w tej dziedzinie.

Aż do 2000 roku prawie wszystkie metody klasyfikatorów uczenia się były opracowywane z myślą o problemach uczenia się przez wzmacnianie. W rezultacie termin „uczący się system klasyfikujący” był powszechnie definiowany jako połączenie uczenia się metodą prób i błędów ze wzmocnieniem z globalnym wyszukiwaniem algorytmu genetycznego. Zainteresowanie aplikacjami do nauki nadzorowanej, a nawet uczeniem się nienadzorowanym, poszerzyło zastosowanie i definicję tego terminu.

Zobacz też

Bibliografia

Linki zewnętrzne

Wideo poradnik

Strony internetowe