User Tools

Site Tools


notatki:ci:douczanie

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
notatki:ci:douczanie [2010/03/18 15:47]
127.0.0.1 edycja zewnętrzna
notatki:ci:douczanie [2019/03/21 13:06] (current)
Line 1: Line 1:
-====== ​Douczanie ​====== +====== ​Online learning ​======
-===== Wstęp ​=====+
  
-Klasyczne metody uczenia metod inteligencji obliczeniowej (ang. computational intelligence,​ CI) głównie koncentrują się na problemie zbudowania pewnego modelu wiedzy w przypadku gdy dostępny jest skończony zbiór przypadków. Innymi słowy zakłada się, iż budowany model matematyczny (np. neuronowy lub rozmyty) powstanie na bazie pewnej skończonej liczby danych empirycznych,​ pochodzących z badanego zjawiska wszystkich dostępnych jednocześnie. Z matematycznego punktu widzenia na podstawie zbioru danych X składającego się z n – przypadków o postaci {{eq0001SP.gif|}} , gdzie m – to liczba zmiennych, stawia się hipotezę H bez hipotez pośrednich jako funkcję [2],[5]:  +===== References ​=====
- +
-{{eq0002SP.gif|}} (1) +
- +
-Założenie o dostępności całości zbioru danych podczas uczenia nie zawsze jednak może być spełnione. Typowym tego przykładem jest uczenie robota lub innych systemów autonomicznych,​ które w trakcie swojego działania stopniowo pozyskują odpowiednią wiedzę i gromadzą dane na których muszą uczyć się w sposób ciągły. Wówczas, ze względu na brak całości zbioru danych uczenie się takiego systemu polega na ciągłym douczaniu, co powoduje że po prezentacji i –tego wektora danych xi  system tworzy nową hipotezę Hi, na podstawie hipotezy Hi-1 oraz owego nowego przypadku xi. +
- +
-{{eq0003SP.gif|}}  ​ (2) +
- +
-Dodatkowo w zależności od sposobu realizacji douczania możliwa jest jeszcze inna opcja, w której hipoteza Hi tworzona jest z wykorzystaniem całego dostępnego zbioru przypadków,​ co można zapisać jako: +
- +
-{{eq0005SP.gif|}} (3)  +
- +
-Należy zauważyć, iż w przypadku metod douczania nie definiuje się wartości n. +
-W literaturze zależność (2) związana jest z tak zwanymi systemami uczenia typu on-line natomiast zależność (3)  z uczeniem inkrementacyjnym [1]. +
-Innym zagadnieniem gdzie również wykorzystuje się metody douczania jest uczenie dużych zbiorów danych, w których liczba wektorów oraz zmiennych nie pozwala na dokonanie uczenia na całym zbiorze danych ze względów na moce obliczeniowe stosowanych komputerów. Przykładem takiego problemu może być opisane [4] zagadnienie przewidzenia poszycia lasu (repozytorium UCI KDD), gdzie zbiór danych liczył 581012 przypadków,​ opisanych przez 54 zmienne. ​ Do rozwiązania zadania wykorzystano inkrementacyjną wersję algorytmu CN2 zwaną ICN. Równie poważne zadanie łączy się również z problemem uczenia w rozproszonych bazach danych. Zostało to między innymi opisane jako jedno z głównych wyzwań stojących przed systemami CI [3].   +
-Trzecim obszarem w którym zastosowanie metod douczania może przynieść istotne zyski są wszelkiego rodzaju zadania związane z gospodarką i przemysłem. Wiąże się to z takzwanym dryftem koncepcji czyli ciągle zmieniającymi się warunkami w których system pracuje. Przykładem tego może być zmieniająca się charakterystyka urządzeń (w tym np. pieców hutniczych) związana z ich zużyciem i amortyzacją. Ciągle zmieniające się środowisko wymaga więc automatycznej ​ adaptacji systemów do nowych sytuacji w których model pracuje. Zagadnienie to było szeroko analizowane przez społeczność związaną z tzw. wnioskowaniem w oparciu o przypadki (ang. Case Based Reasoning, CBR)  gdzie definiuje się odpowiedni model przepływu danych, który służy następnie douczaniu i adaptacji systemu do nowych warunków. +
- +
-===== Wnioskowanie w oparciu o przypadki ===== +
- +
-CBR powszechnie stosowany jest do rozwiązywania różnych problemów analizy przypadków,​ gdzie pojedyncze sytuacje odpowiadają wystąpieniu określonych zjawisk. Idea ich działania opiera się na zasadzie, iż podobne zadania powinny być rozwiązywane w podobny sposób, dlatego też systemy te działają gromadząc w bazie wiedzy charakterystyczne przypadki. Innymi słowy CBR bazuje na rozwiązywaniu nowych problemów na podstawie podobieństwa do już rozwiązanych zagadnień zgromadzonych w bazie wiedzy. CBR między innymi używany jest w analizie przepisów prawa precedensowego,​ wiele wdrożeń można również zaobserwować w medycynie np. [16] oraz przemyśle. W systemach CBR główny nacisk położony jest również na maksymalizację dokładności predykcji, jednakże poszczególne przypadki traktowane są jako pojedyncze reguły postępowania,​ gdzie baza wiedzy jest inkrementacyjnie rozbudowywana. Związane jest to z procesem eksploracji danych online, gdzie każdorazowy sukces lub porażka predykcji zakończony jest umieszczeniem tego przypadku w bazie wiedzy z odpowiednio zmodyfikowaną etykietą. ​ Innymi słowy douczenie polega na zapisaniu nowego przypadku (wektora) w bazie wiedzy, jest więc to najszybszy sposób douczania modeli. +
-Do metod uczenia poprzez analizę przypadków można zaliczyć: wnioskowanie pamięciowe zaproponowane przez Stanfilla i Waltza (ang. memory based reasoning, MBR) [17], uczenie w oparciu o instancje autorstwa Aha i innych (ang. instance based learning, IBL) [18]. Wszystkie one bazują na modyfikacjach algorytmu k najbliższych sąsiadów (kNN). +
-Algorytm ten można zdefiniować jako: +
- +
-{{nauka:​notatki:​douczanie:​eq0006SP.gif|}} (4) +
- +
-Gdzie z oznacza badany przypadek, xj j-ty element bazy wiedzy, k to liczba najbliższych sąsiadów, n – liczbę przypadków zgromadzonych w bazie wiedzy, natomiast ​ {{eq0007SP.gif|}} jest miarą odległości dobieraną odpowiednio do stosowanych atrybutów (jakościowych,​ ilościowych). Powyższą zależność należy interpretować jako znalezienie w bazie wiedzy k najbardziej podobnych przypadków do badanego wektora z oraz wyznaczenie odpowiedzi poprzez średnią wartość spośród k- sąsiadów. W praktyce systemów CBR często stosuje się ważenie odpowiednich decyzji, tak iż najbardziej podobne przypadki zgromadzone w bazie wiedzy posiadają najwyższy współczynnik istotności przy podejmowaniu decyzji. W takich przypadkach zamiast średniej stosuje się operator średniej ważonej. +
-W systemach z rodziny CBR jednym z istotnych problemów jest szybkość podejmowania decyzji przez system, co związane jest z dużą liczbą przypadków zgromadzonych w bazie wiedzy. Tym bardziej, że z upływem czasy rozmiar bazy wiedzy stopniowo powiększa się. Problem ten powodując zmniejszenie szybkości działania oraz duże zapotrzebowanie na zasoby systemu komputerowego. Dlatego konieczne jest używanie metod mających na celu przyspieszenie procesu znajdywania najbliższych sąsiadów. Do typowych rozwiązań należą tutaj algorytm Kd-tree [19] lub inne metody drzew decyzji jak C4.5, które wykorzystywane są do wstępnej indeksacji i selekcji przypadków [20], ograniczając tym samym obszar przeszukiwania. +
-Najistotniejszym jednak elementem systemów CBR, który ma szczególne zastosowanie w przypadku aplikacji przemysłowych i powinien być zawsze stosowany jest schemat przepływu danych. Definiuje się tutaj zamknięty obieg dany w postaci:  +
- +
-{{nauka:​notatki:​douczanie:​image006.gif|}} +
- +
-Który w przypadku języka angielskiego definiuje się jako 4xR: +
-  * RETRIEVE – pozyskaj najbardziej podobny przypadek lub przypadki +
-  * REUSE – wykorzystaj wiedzę uzyskaną przez ten przypadek (przypadki) do rozwiązania problemu +
-  * REVISE – zweryfikuj zaproponowane rozwiązanie +
-  * RETAIN – zachowaj najbardziej użyteczne części rozwiązania by w przyszłości rozwiązać podobne problemy +
-Tak zdefiniowany obieg informacji można opisać słownie jako – rozwiązując dane zadanie szukamy w bazie wiedzy najbardziej podobnego przypadku (przypadków),​ który został już rozwiązany;​ na podstawie wiedzy o dotychczasowych rozwiązaniach udziel odpowiedzi na nowe zadanie; zweryfikuj uzyskaną odpowiedź i sprawdź jej poprawność;​ popraw uzyskane rozwiązanie pochodzące z modelu i dokonaj aktualizacji bazy wiedzy o nowo udzieloną odpowiedź.  +
-Na szczególną uwagę zasługują tutaj ostatnie dwa kroki gdzie weryfikuje się czy system wymaga douczenia i jeśli tak następuje jego douczenie w taki sposób by w przyszłości przewidywał z większą dokładności. Dodatkowo podczas realizacji tych dwóch kroków następuje sprawdzenie czym była spowodowana błędna odpowiedź systemu (jeśli była błędna). Ma to istotne znaczenie w warunkach przemysłowych gdzie niepoprawne rozwiązanie uzyskane z fizycznego systemu mogło być spowodowane bardzo nietypowymi warunkami pracy, sytuacją ekstremalną,​ wówczas douczenie systemu – umieszczenie w bazie takiego przypadku może być niebezpieczne i prowadzić do utraty stabilności jego działania. +
- +
-===== Douczanie modeli SVM ===== +
- +
-!!!! To jest wersja z brakami wzorów - trzeba tutaj uzupełnić !!!! +
- +
-Algorytm SVM opiera się na funkcji decyzyjnej postaci: +
- +
-{{eq0008SP.gif|}} (5) +
- +
-W której αi są poszukiwanymi w procesie optymalizacji kwadratowej współczynnikami (wagami neuronu liniowego), {{eq0009SP.gif|}} ​ jest pozytywnie dodatnio określoną macierzą funkcji jądrowych. Proces optymalizacji opiera się na funkcji celu zdefiniowanej jako +
- +
-{{eq0010SP.gif|}} (6) +
- +
-Gdzie wektor w określa szerokość marginesu zaufania. +
-Pierwszą metodą douczania SVM zaproponował Syed i inni w [10]. Jedną z motywacji powstania tej metody był problem uczenia dużych zbiorów danych. Ze względu na złożoność obliczeniową algorytmu SVM zbiór danych losowo dzielony jest na mniejsze podzbiory na których następnie uczony jest model SVM w sposób inkrementacyjny.  +
-W pierwszym kroku algorytm uczy się na pierwszym podzbiorze. Uczenie drugiego podzbioru odbywa się z dodatkowym wykorzystaniem wektorów wsparcia wyznaczonych w pierwszym podzbiorze. Podejście to bazuje na dwóch właściwościach algorytmu SVM, po pierwsze zerowanie się wielu współczynników α podczas uczenia pierwszego modelu SVM, powoduje że uzyskane rozwiązanie ze zbioru danych wybiera jedynie małą - rzadką reprezentację wektorów wsparcia oraz druga właściwość związana jest ze stabilnością algorytmu SVM, gdzie w miarę douczania, kształt granicy decyzji przestaje się zmienić i stabilizuje się, tym samym powoduje to że często wybierane są te same wektory wsparcia, warunkiem jest jednak założenie iż dane pochodzą z identycznych i niezależnych rozkładów prawdopodobieństwa (ang. identically independent distributed). Ogólnie więc algorytm ten można przedstawić jako: +
- +
-  - dokonaj podziału zbioru danych na podzbiory ​  +
-  - naucz SVM na pierwszym podzbiorze ​  +
-  - oznacz iteracją jako i=1 +
-  - wykorzystaj wektory wsparcia SVi nauczonego już SVMi i dołącz je do podzbioru Xi+1 :   +
-  - naucz SVMi+1 na zbiorze ​  +
-  - i=i+1, przejdź do kroku 4 aż nie zostanie nauczony cały zbiór danych +
- +
-Innym rozwiązaniem douczania modelu SVM jest metoda zaproponowana przez d’Alche-Buc oraz L. Ralaivola [11], która stanowi rozwinięcie powyżej opisanego pomysłu. W metodzie tej autorzy analizują wpływ pojawienia się nowego wektora danych na aktualizację wag poszczególnych neuronów. Opisany przez nich model ma zastosowanie w przypadku wszystkich modeli o lokalnym charakterze jak sieci typu RBF oraz SVM o Gaussowskich funkcjach jądrowych. W przypadku algorytmu SVM określa się wpływ parametrów αi na podjętą przez system decyzję podczas wyznaczania wartości wyjściowej dla wektora xn: +
- +
-{{eq0011SP.gif|}} (7) +
- +
-Z powyższej zależności wynika, że w przestrzeni danych wejściowych wpływ na podjętą decyzję zmienia się w funkcji odległości Euklidesa (dla funkcji jądrowych typu Gaussowskiego) od badanego wektora xn . Tym samym douczanie modelu można sprowadzić do rozwiązania problemu optymalizacji kwadratowej i doboru odpowiednich wartości αi w bezpośredniego otoczenia k- najbliższych wektorów do wektora xn . Opis zaproponowanego algorytmu przedstawia poniższa tabela: +
- +
-  - jeżeli ​  nie douczaj systemu, gdyż hipoteza klasyfikująca xn spełniona jest w dostatecznym stopniu +
-  - j = 1 +
-  - powtarzaj +
-    - j = j + 1 +
-    - dodaj do zbioru roboczego k-najbliższych sąsiadów wokół wektora xn +
-    - doucz kandydującą hipotezę ​  ​poprzez optymalizację problemu kwadratowego na zbiorze roboczym +
-  - do spełnienia kryterium stopu   +
- +
-Autorzy w swojej pracy rozważali również wpływ doboru wartości liczby sąsiadów k na jakość predykcji modelu, zaowocowało to powstaniem trzech różnych metod określania sąsiedztwa:​ pierwsza bazująca na manualnym doborze parametru k; druga to tzw. metoda wczesnego zatrzymania,​ oraz trzecia wykorzystująca granice zaufania zdefiniowaną przez Cristianini oraz Shaw-Taylora [12]. +
-Rozszerzenie metod douczania o uwzględnienie dryftem koncepcji (ang. concept drift) ​  w przypadku modelu SVM zaproponował S. Rusing [13]. Wyszedł on z założenia,​ iż zbiór wektorów wsparcia uzyskanych po nauczeniu modelu SVM reprezentuje nie zbiór danych lecz funkcję decyzyjną definiującą kształt granicy pomiędzy różnymi klasami. Powoduje to iż prezentacja nowego przypadku uczącego powinna uwzględniać ​ inny sposób ważenia błędu – inną wagę popełnianej pomyłki niż w przypadku pozostałych wektorów. Jak wspomniano wyżej związane jest to z tak zwanym dryftem koncepcji, czyli zmianą kształtu funkcji decyzyjnej związaną z upływem czasu i zmianą parametrów badanego obiektu fizycznego, którego właściwości system się uczy. W tym celu Tubing zaproponował modyfikację funkcji kosztu klasyfikatora SVM do postaci: +
- +
-{{eq0012SP.gif|}} (8) +
- +
-Gdzie S stanowi zbiór dotychczasowych wektorów wsparcia, natomiast ​ I to nowy wektor prezentowany podczas uczenia. Wartość L przyjmowana jest jako: +
- +
-{{eq0013SP.gif|}} (9) +
- +
-Niezależna od pozostałych koncepcja douczania modelu SVM została zaproponowana przez Cauwenberghs’a oraz T. Poggio. W odróżnieniu od pozostałych metod autorzy skoncentrowali się na zapewnieniu spełnienia warunków Kuhn-Tucker’a (KT) które są wymagane podczas realizacji procesu optymalizacji. ​ Oznaczając g(.) jako warunek KT, S jak zbiór wektorów tworzących margines, dokładnie leżących na marginesie ({{eq0014SP.gif|}}),​ zbiór E – wskazujący błędne wektory wsparcia rozszerzające margines oraz R jako zbiór zignorowanych wektorów wewnątrz marginesu, zaproponowany algorytm można przedstawić jako: +
- +
-  - inicjalizuj αn jako 0 (współczynnik α nowo prezentowanego wektora) +
-  - jeżeli ​  ​przerwij +
-  - jeżeli ​ zastosuj możliwie największy przyrost αn  aż do spełnienia jednego z warunków:​ +
-    -  +
-    - αn = 0 +
-    - dokonaj migracji elementów zbioru treningowego ​  ​pomiędzy S, R, E +
-  - powtarzaj jeśli konieczne +
- +
- +
-Zaproponowana przez autorów metoda pozwala również na oduczanie klasyfikatora co przykładowo może zostać wykorzystane przy estymacji jego dokładności w postaci testu jeden pozostaw (ang. leave one out), lub do oduczania systemu w przypadku zaprezentowania mu w procesie uczenie wektorów odstających. +
-===== Spis literatury ​=====+
  
 [1] T.M. Kwok, D.Y. Yeung, Objective Functions for Training New Hidden Units In Constructive Neural Networks. IEEE Trans. On Neural Networks, vol. 8(5),  1999, pp.1131-1148 \\ [1] T.M. Kwok, D.Y. Yeung, Objective Functions for Training New Hidden Units In Constructive Neural Networks. IEEE Trans. On Neural Networks, vol. 8(5),  1999, pp.1131-1148 \\
notatki/ci/douczanie.txt · Last modified: 2019/03/21 13:06 (external edit)