WSTĘP

Systemy uczące się zależą od trzech powiązanych ze sobą komponentów: topologii, funkcji koszt/wydajność oraz algorytmów uczenia się. Topologie określają ograniczenia dla mapowania, a algorytmy uczenia się oferują środki do znalezienia optymalnego rozwiązania; ale rozwiązanie jest optymalne względem czego? Optymalność jest charakteryzowana przez kryterium i w literaturze poświęconej sieciom neuronowym jest to najmniej uwzględniany komponent, a mimo to ma decydujący wpływ na wydajność generalizacji. Z pewnością założenia leżące u podstaw wyboru kryterium powinny być lepiej zrozumiane i zbadane.Tradycyjnie, najmniejsze kwadraty były kryterium odniesienia dla problemów regresji; rozważając klasyfikację jako problem regresji w kierunku szacowania prawdopodobieństw a posteriori klas, najmniejsze kwadraty były wykorzystywane do trenowania topologii sieci neuronowych i innych klasyfikatorów w celu aproksymacji poprawnych etykiet. Główną motywacją do wykorzystania metody najmniejszych kwadratów w regresji jest po prostu komfort intelektualny, jaki zapewnia to kryterium dzięki jego skuteczności w tradycyjnych zastosowaniach liniowej regresji najmniejszych kwadratów - co można sprowadzić do rozwiązania układu równań liniowych. W regresji nieliniowej założenie gaussowskości dla błędu pomiaru w połączeniu z zasadą największej wiarygodności może być wykorzystane do promowania tego kryterium. W regresji nieparametrycznej zasada najmniejszych kwadratów prowadzi do warunkowego rozwiązania oczekiwanego, co jest intuicyjnie atrakcyjne. Chociaż istnieją dobre powody, aby użyć średniego błędu kwadratowego jako kosztu, jest on z natury powiązany z założeniami i nawykami wymienionymi powyżej. W konsekwencji, w sygnale błędu znajdują się informacje, które nie są rejestrowane podczas uczenia nieliniowych układów adaptacyjnych w warunkach rozkładu innego niż gaussowski, gdy nalega się na kryteria statystyczne drugiego rzędu. Argument ten rozciąga się na inne techniki liniowe drugiego rzędu, takie jak analiza głównych składowych (PCA), liniowa analiza dyskryminacyjna (LDA) i analiza korelacji kanonicznej (CCA). Najnowsze prace próbują uogólnić te techniki na scenariusze nieliniowe, wykorzystując techniki jądra lub inne heurystyki. Nasuwa się pytanie: jakie inne alternatywne funkcje kosztów można by wykorzystać do trenowania systemów adaptacyjnych i jak moglibyśmy opracować rygorystyczne techniki rozszerzania użytecznych koncepcji z liniowych i statystycznych technik drugiego rzędu na nieliniowe i statystyczne metodologie uczenia się wyższego rzędu?

TŁO

To pozornie proste pytanie leży u podstaw najnowszych badań nad uczeniem się opartym na teorii informacji (ITL) prowadzonych przez autorów, a także badań innych naukowców nad alternatywnymi kryteriami optymalności odporności na obserwacje odstające i szybszą konwergencję, takimi jak różne miary błędu indukowanego przez normę L_p, miara błędu epsilon-in-sensitive , solidna teoria estymacji m Hubera lub modyfikacje Bregmana oparte na dywergencji . Entropia to miara niepewności, która uogólnia rolę wariancji w rozkładach Gaussa poprzez uwzględnienie informacji o statystykach wyższego rzędu funkcji gęstości prawdopodobieństwa (pdf) . W przypadku nauki online, wielkości teorii informacji muszą być szacowane nieparametrycznie na podstawie danych. Wyrażenie nieparametryczne, które jest różniczkowalne i łatwe do aproksymacji stochastycznej, umożliwi importowanie użytecznych koncepcji, takich jak stochastyczne uczenie gradientu i wsteczna propagacja błędów. Naturalnym wyborem jest estymacja gęstości jądra (KDE) , ze względu na jej gładkość i właściwości asymptotyczne. Metodologia estymacji wtykowej w połączeniu z definicjami Renyiego dostarcza zestaw narzędzi dobrze dostosowanych do zastosowań w uczeniu się - narzędzi odpowiednich do uczenia nadzorowanego i nienadzorowanego, offline i online. Definicja entropii dla zmiennej losowej X według Renyiego to:



Uogólnia to postulat liniowej addytywności Shannona na addytywność wykładniczą, co prowadzi do rodziny funkcji parametrycznych. Pominięcie logarytmu w celu optymalizacji upraszcza algorytmy. Szczególnie interesująca jest entropia kwadratowa (α=2), ponieważ jej estymator próbki wymaga tylko jednego przybliżenia (samego estymatora gęstości), a dla estymatorów gęstości jądra można uzyskać wyrażenie analityczne dla całki. W konsekwencji, estymator próbki dla entropii kwadratowej można wyprowadzić dla jąder Gaussa o odchyleniu standardowym σ na iid zbiorze próbek {x₁,….x_N} jako sumę oddziaływań parami próbek (cząstek) :



Interakcja par próbek poprzez jądro w intrygujący sposób nawiązuje do entropii cząstek w fizyce. Cząstki oddziałujące za pośrednictwem sił informacyjnych (jak w problemie N-ciał w fizyce) mogą wykorzystywać techniki obliczeniowe opracowane do symulacji tak dużych systemów. Wykorzystanie entropii w trenowaniu struktur wielowarstwowych można badać w ramach propagacji wstecznej sił informacyjnych . Estymator entropii kwadratowej został wykorzystany do pomiaru rozbieżności między gęstościami prawdopodobieństwa a ślepą separacją źródeł, ślepą dekonwolucją oraz klasteryzacją . Wyrażenia kwadratowe o właściwościach podobnych do informacji wzajemnej wprowadzono na podstawie odległości euklidesowej i Cauchy′ego-Schwartza (ED/CSD). Są one korzystne ze względu na prostotę obliczeniową i stabilność statystyczną w optymalizacji . Zgodnie z koncepcją potencjału informacyjnego, siły i zasad, estymator interakcji paramizostał uogólniony, aby wykorzystać dowolne jądra i dowolny rząd entropii ?. Opracowano stochastyczny gradient informacji (SIG) w celu trenowania systemów adaptacyjnych o złożoności porównywalnej z algorytmem LMS (najmniejszej średniej kwadratowej) - niezbędnym do trenowania złożonych systemów z dużymi zbiorami danych. Uczenie nadzorowane i nienadzorowane jest ujednolicone w oparciu o kryteria oparte na informacji. Możliwa jest minimalizacja entropii błędu w regresji nadzorowanej lub maksymalizacja entropii wyjściowej w uczeniu nienadzorowanym (analiza czynnikowa), minimalizacja wzajemnej informacji między wyjściami systemu w celu uzyskania niezależnych komponentów lub maksymalizacja wzajemnej informacji między wyjściami a pożądanymi odpowiedziami w celu uzyskania optymalnych projekcji podprzestrzeni w klasyfikacji. Systematyczne porównania ITL z konwencjonalną MSE w identyfikacji systemów potwierdziły zalety tej techniki w nieliniowej identyfikacji systemów i ślepej korekcji kanałów komunikacyjnych. Odkryto związki z technikami zmiennych instrumentalnych, co doprowadziło do opracowania kryterium wybielania błędów dla nieobciążonego systemu liniowego w warunkach zaszumionych danych wejściowych i wyjściowych .

KILKA POMYSŁÓW I ZASTOSOWAŃ W TECHNOLOGII ITL

Maszyny jądra i klasteryzacja widmowa: KDE zostało zainspirowane właściwościami gładkości inherentnymi dla reprodukcji przestrzeni Hilberta jądra (RKHS). Dlatego praktyczne połączenie między ITL opartym na KDE, maszynami jądra i technikami uczenia maszynowego opartego na widmie było nieuniknione. Połączenie to zostało zrealizowane i wykorzystane w niedawnej pracy, która demonstruje ramy teorii informacji dla klasteryzacji parami podobieństwa (spektralnej), w szczególności technik znormalizowanego cięcia . Wykazano, że znormalizowane klasteryzacja cięcia pozwala na określenie optymalnego rozwiązania, które maksymalizuje CSD między klastrami (Jenssen, 2004). To połączenie pozwala natychmiast podejść do maszyn jądra z perspektywy estymacji gęstości, zapewniając w ten sposób solidną metodę wyboru rozmiaru jądra, problem wciąż badany przez niektórych badaczy w literaturze poświęconej jądru i technikom spektralnym. Z naszego doświadczenia wynika, że wybór rozmiaru jądra w oparciu o odpowiednie kryteria mające na celu uzyskanie najlepszego dopasowania do danych treningowych - na przykład przy użyciu regularyzowanego dopasowania błędu kwadratowego Silvermana lub walidacji krzyżowej z pominięciem jednego elementu i maksymalną wiarygodnością - okazał się wygodnymi, solidnymi i dokładnymi technikami, które pozwalają uniknąć wielu problemów ze złożonością obliczeniową i obciążeniem. Modyfikacje oparte na lokalnym rozproszeniu danych, skutkujące zmienną szerokością KDE, są również obserwowane jako bardziej odporne na szum i wartości odstające. Ilustrację klastrowania ITL poprzez maksymalizację CSD między dwoma oszacowanymi klastrami przedstawiono na rysunku



Próbki oznaczono tak, aby maksymalizowały



gdzie p i q to KDE dla dwóch kandydujących klastrów, f to ogólne KDE danych, a ważony iloczyn skalarny do pomiaru odległości kątowej między klastrami to



Po oszacowaniu przy użyciu ważonej wersji KDE, to kryterium staje się równoważne



gdzie K_I/f jest równoważnym jądrem wygenerowanym z oryginalnego jądra K (tutaj Gaussa). Jedną z trudności związanych z maszynami jądra jest ich nieparametryczna natura, a mianowicie konieczność rozwiązania rozkładu własnego dużej macierzy dodatnio określonej o rozmiarze N×N dla N próbek treningowych. Rozwiązaniem jest ważona suma jąder ocenionych dla każdej próbki treningowej, zatem procedura testowa dla każdej nowej próbki obejmuje ocenę sumy N jąder:



Aby pokonać tę trudność, zastosowano szybką transformację Gaussa (FGT) , która wykorzystuje rozwinięcia wielomianowe dla jądra Gaussa (lub innego). FGT starannie wybiera kilka punktów środkowych, wokół których obcięte rozwinięcia wielomianów Hermite′a aproksymują maszynę jądra. FGT nadal wymaga dużego obciążenia obliczeniowego podczas treningu offline (minimum O(N,²), zazwyczaj O(N³)). Wybór centrów ekspansji odbywa się zazwyczaj poprzez klasteryzację .

Korenopia jako uogólniona metryka podobieństwa:

Główną cechą ITL jest to, że zachowuje ona uniwersum pojęć, którymi dysponujemy w dziedzinie obliczeń neuronowych, ale pozwala systemowi adaptacyjnemu na wydobycie większej ilości informacji z danych. Na przykład, ogólna zasada Hebba jest redukowana do metryki drugiego rzędu w tradycyjnej literaturze poświęconej sztucznym sieciom neuronowym (iloczyn wejścia-wyjścia), stając się tym samym synonimem statystyki drugiego rzędu. Reguła uczenia się, która maksymalizuje entropię wyjściową (zamiast wariancji wyjściowej f), przy użyciu SIG z jądrami Gaussa, to Δw(n) = η(x(n)-x(n-1)((y(n)-Y(n-1)), która nadal podlega zasadzie Hebba, ale wydobywa z danych więcej informacji (co prowadzi do kryterium wybielania błędów dla uczenia odpornego na szum wejściowy). ITL kwantyfikuje globalne właściwości danych, ale czy będzie możliwe zastosowanie jej do funkcji, szczególnie tych w RKHS? Konkretnym przykładem jest podobieństwo między zmiennymi losowymi, które jest zazwyczaj wyrażane jako korelacja drugiego rzędu. Korentropia uogólnia podobieństwo, aby uwzględnić informacje o momentach wyższego rzędu. Nazwa wskazuje na silny związek z korelacją, ale podkreśla również różnicę - średnią dla opóźnień (dla procesów losowych) lub dla wymiarów (dla wielowymiarowych Zmienne losowe) to potencjał informacyjny, czyli argument entropii Renyiego drugiego rzędu. Dla zmiennych losowych X i Y o łącznej gęstości p(x,y), korentropia jest definiowana jako



i mierzy gęstość dwóch zmiennych losowych wzdłuż linii x=y w przestrzeni wspólnej. Zauważ, że jest to podobne do korelacji, która również zadaje to samo pytanie w kontekście drugiego momentu. Jednak korentropia jest lokalna dla linii x=y, podczas gdy korelacja jest kwadratowo zależna od odległości próbek w przestrzeni wspólnej. Używając środowiska KDE z jądrami Gaussa



Korentropia jest funkcją dodatnio określoną, a zatem definiuje RKHS. W przeciwieństwie do korelacji, RKHS jest nieliniowo związana z danymi wejściowymi, ponieważ wszystkie momenty zmiennej losowej są uwzględniane w transformacji. Możliwe jest analityczne rozwiązanie regresji najmniejszych kwadratów i głównych składowych w tej przestrzeni, co daje nieliniowe dopasowania w przestrzeni wejściowej. Metryka indukowana korentropią (CIM) zachowuje się jak norma L₂ dla małych odległości i stopniowo zbliża się do normy L₁, a następnie zbiega do L₀ w nieskończoności. W ten sposób automatycznie osiągana jest odporność na obserwacje odstające, a równoważność z solidną estymacją Hubera może zostać udowodniona .W przeciwieństwie do konwencjonalnych metod jądra, rozwiązania korentropii pozostają w tej samej wymiarowości co wektor wejściowy. Może to wskazywać na wbudowane właściwości regularyzacji, które jeszcze nie zostały zbadane. Uczenie nieparametryczne w RKHS: Możliwe jest uzyskanie solidnych rozwiązań dla różnych problemów uczenia się, wykorzystując nieparametryczną i lokalną naturę KDE oraz jej związek z teorią RKHS. Niedawno badaliśmy możliwość zaprojektowania nieparametrycznych rozwiązań problemu identyfikacji nieliniowych schematów redukcji wymiarowości, które zachowują maksymalną informację różnicową w problemie rozpoznawania wzorców (całkiem trafnie mierzoną wzajemną informacją między danymi a etykietami klas, zgodnie z ustaleniami wielu badaczy). Wykorzystując formalizm RKHS i bazując na KDE, uzyskano wyniki, które konsekwentnie przewyższały alternatywne, raczej heurystyczne podejścia jądra, takie jak jądro PCA i jądro LDA . Pominięcie koncepcyjne w tych dwóch ostatnich metodach polega na tym, że zarówno procedury PCA, jak i LDA są najbardziej odpowiednie dla danych rozproszonych Gaussa (chociaż akceptowalne dla innych symetrycznych rozkładów unimodalnych i powszechnie, choć potencjalnie niewłaściwie, stosowane dla dowolnych rozkładów danych). Oczywiste jest, że rozkład danych w przestrzeni cech indukowanej przez jądro nie mógł być rozkładem Gaussa dla wszystkich typowo wykorzystywanych wyborów jądra (takich jak jądro Gaussa), ponieważ są one zazwyczaj niezmienne translacyjnie. W związku z tym dane są w zasadzie odwzorowywane na nieskończenie wymiarową hipersferę, na której dane nie mogłyby mieć rozkładu Gaussa (ani rozkładu symetrycznego w ogólności dla idealnego jądra dla danego problemu, ponieważ są to dodatnio określone funkcje). W konsekwencji, pochopne stosowanie rozszerzeń jądra technik drugiego rzędu nie jest koniecznie optymalne w sensownym sensie statystycznym. Niemniej jednak techniki te znalazły skuteczne zastosowania w różnych problemach; jednak ich suboptymalność jest oczywista w porównaniach z bardziej starannie zaprojektowanymi rozwiązaniami. Aby zilustrować, jak drastyczna może być różnica w wydajności, przedstawiamy porównanie nieliniowego podejścia projekcji nieparametrycznej opartego na informacji wzajemnej i jądra LDA w uproszczonym studium przypadku klasyfikacji cyfr pisanych ręcznie w dwóch klasach oraz studium przypadku wykrywania min sonarowych. Krzywe ROC obu algorytmów w zbiorze testowym po trenowaniu tymi samymi danymi przedstawiono na rysunku 2.



Zakłada się, że jądro jest kołowym rozkładem Gaussa o rozmiarze zgodnym z regułą Silvermana. W przypadku danych sonaru uwzględniamy również przybliżony klasyfikator Bayesa oparty na KDE oraz liniową analizę LDA. W tym przykładzie analiza KLDA wykonuje projekcje bliskie wzajemnej informacji, co jest sporadycznie obserwowane.

PRZYSZŁE TRENDY

Nieparametryczne węże, krzywe główne i powierzchnie: Ostatnio badaliśmy zastosowanie KDE i RKHS do nieparametrycznego klasteryzacji, krzywych głównych i powierzchni. Opracowano interesujące algorytmy punktów stałych, podobne do przesunięcia średniej; szczególnie interesująca jest koncepcja nieparametrycznych węży i lokalnych rozmaitości głównych , które niedawno opracowaliśmy. Podejście nieparametrycznego węża pokonuje główne trudności, z jakimi borykają się węże (aktywne kontury) w segmentacji obrazu, takie jak niski zasięg przechwytywania, niejednorodność krzywizny danych oraz zaszumione i brakujące informacje o krawędziach. Podobnie, lokalne warunki określania, czy punkt znajduje się w rozmaitości głównej, czy nie, dostarczają wskazówek do projektowania algorytmów punktów stałych i innych iteracyjnych algorytmów uczenia się w celu identyfikacji tak ważnych struktur. W przypadku nieparametrycznych węży traktujemy mapę krawędzi obrazu jako próbki, a wartości krawędzi jako wagi, aby skonstruować ważone KDE, na podstawie którego można opracować iteracyjny algorytm o stałym punkcie do wykrywania granic obiektu w tle. Zaprojektowany algorytm można łatwo uodpornić na krawędzie odstające, osiąga bardzo szybką zbieżność i może penetrować wklęsłości, nie wpadając jednocześnie w obiekt w miejscach brakujących krawędzi. Obraz gitary na rysunku 3 podkreśla te zalety, ponieważ obraz wykazuje zarówno brakujące krawędzie, jak i wklęsłości, a złożoność tła jest trywialnie niska, ponieważ nie to było głównym problemem w tym eksperymencie - KDE o zmiennej szerokości z łatwością omija przeszkody o teksturze.



Algorytm ten można wykorzystać do wykrywania granicy grzbietu struktury w dowolnym zbiorze danych wymiarowych w innych zastosowaniach. Definiując rozmaitości główne, pominęliśmy tradycyjne kryteria rekonstrukcji metodą najmniejszych kwadratów, takie jak samouzgodnione krzywe główne Hastiego , i zaproponowaliśmy definicję lokalnego maksimum podprzestrzeni dla rozmaitości głównych, inspirowaną geometrią różniczkową. Definicja ta nadaje się do jednoznacznie zdefiniowanej hierarchii rozmaitości głównych, dzięki czemu można użyć inflacji i deflacji do uzyskania d-wymiarowej rozmaitości głównej z (d+1)-wymiarowej rozmaitości głównej. Rygorystyczna i lokalna definicja umożliwia łatwe projektowanie algorytmów i wieloskalową analizę struktury głównej dla gęstości prawdopodobieństwa. Wierzymy, że w niedalekiej przyszłości społeczność będzie w stanie udowodnić maksymalne właściwości zachowania informacji przez rozmaitości główne uzyskane przy użyciu tej definicji w sposób podobny do klasteryzacji z przesunięciem średniej, rozwiązując problem minimalnego zniekształcenia informacji oraz modelowania metodą maksymalnej wiarygodności, osiągając asymptotycznie minimalną dywergencję Kullbacka-Leiblera .

WNIOSKI

Zastosowanie kryteriów uczenia się teorii informacji w sieciach neuronowych i innych rozwiązaniach systemów adaptacyjnych do tej pory wyraźnie wykazało szereg korzyści wynikających ze zwiększonej zawartości informacyjnej tych miar w porównaniu ze statystykami drugiego rzędu . Co więcej, zastosowanie estymacji gęstości jądra z gładkimi jądrami pozwala uzyskać ciągłe i różniczkowalne kryteria odpowiednie dla iteracyjnego uczenia się opartego na zstępowaniu/wznoszeniu, a nieparametryczna natura środowiska KDE i jego wariantów (takich jak jądra o zmiennej wielkości) pozwala na osiągnięcie jednocześnie solidności, globalnej optymalizacji poprzez wyżarzanie jądra oraz elastyczności modelowania danych w projektowaniu sieci neuronowych i algorytmów uczenia się dla różnorodnych problemów testowych. Ze względu na brak miejsca, szczegółowe opracowania matematyczne nie mogą być przedstawione w niniejszym artykule; czytelnika odsyła się do literatury w celu uzyskania szczegółowych informacji.

WSTĘP

Sieć Bayesowska (BN) wykorzystuje relację między grafami a rozkładami prawdopodobieństwa. W przeszłości BN była wykorzystywana głównie do reprezentacji wiedzy i wnioskowania. W ostatnich latach odnotowano wiele udanych zastosowań BN w klasyfikacji, wśród których klasyfikator Naiwnego Bayesa okazał się zaskakująco skuteczny, pomimo swojego prostego mechanizmu . Opiera się on na silnym założeniu, że różne atrybuty są od siebie niezależne. Pomimo wielu zalet, głównym ograniczeniem stosowania klasyfikatora Naiwnego Bayesa jest to, że dane rzeczywiste nie zawsze spełniają założenie niezależności atrybutów. To silne założenie może sprawić, że dokładność przewidywań klasyfikatora Naiwnego Bayesa będzie wysoce wrażliwa na skorelowane atrybuty. Aby pokonać to ograniczenie, opracowano wiele podejść mających na celu poprawę wydajności klasyfikatora Naiwnego Bayesa. Niniejszy artykuł stanowi krótkie wprowadzenie do podejść, które starają się złagodzić założenie o niezależności atrybutów lub wykorzystują określone procedury wstępnego przetwarzania, aby atrybuty były jak najbardziej niezależne od siebie. Wcześniejsze wyniki teoretyczne i empiryczne pokazały, że wydajność klasyfikatora Naïve Bayes może zostać znacząco poprawiona dzięki zastosowaniu tych podejść, przy jednoczesnym pewnym wzroście złożoności obliczeniowej.

TŁO

Naiwny klasyfikator Bayesa, zwany również prostym klasyfikatorem bayesowskim, jest zasadniczo prostym klasyfikatorem BN. Ponieważ nie jest wymagane uczenie się struktury, bardzo łatwo jest skonstruować i zaimplementować naiwny klasyfikator Bayesa. Pomimo swojej prostoty, naiwny klasyfikator Bayesa konkuruje z innymi, bardziej zaawansowanymi i wyrafinowanymi klasyfikatorami, takimi jak drzewa decyzyjne . Dzięki tym zaletom, naiwny klasyfikator Bayesa zyskał dużą popularność w rozwiązywaniu różnych problemów klasyfikacyjnych. Niemniej jednak, jego założenie o niezależności między atrybutami jest często naruszane w praktyce. Na szczęście opracowano wiele podejść mających na celu złagodzenie tego problemu. Ogólnie rzecz biorąc, podejścia te można podzielić na dwie grupy. Jedno z nich próbuje złagodzić założenie o niezależności naiwnego klasyfikatora Bayesa, np. Semi-Naïve Bayes (SNB) , Poszukiwanie zależności, Drzewo Rozszerzonego Naïve Bayesa (TAN) , Drzewo Superrodziców Rozszerzonego Naïve Bayesa (SP-TAN) , Reguła Lazy Bayesa (LBR) oraz Agregujące Estymatory Jednozależności (AODE) . Druga grupa próbuje wykorzystać pewne procedury wstępnego przetwarzania do selekcji lub transformacji atrybutów, które mogą być bardziej odpowiednie dla założenia klasyfikatora Naïve Bayesa. Selekcję cech można zrealizować za pomocą zachłannego przeszukiwania w przód oraz drzew decyzyjnych . Techniki transformacji obejmują analizę głównych składowych (PCA) , analizę niezależnych składowych (ICA) oraz CC-ICA .Następna sekcja opisuje w szerokim zakresie główne idee obu grup technik.

ULEPSZANIE NAIWNEGO KLASYFIKATORA BAYESA

W tej sekcji przedstawiono dwie grupy podejść, które zostały wykorzystane do ulepszenia naiwnego klasyfikatora Bayesa. W pierwszej grupie silne założenie o niezależności jest łagodzone przez ograniczone uczenie się struktury. Druga grupa pomaga wybrać niektóre główne (i w przybliżeniu niezależne) atrybuty z atrybutów oryginalnych lub przekształcić je w nowe atrybuty, które następnie mogą być wykorzystane przez naiwny klasyfikator Bayesa.

Rozluźnienie założenia niezależności

Rozluźnienie założenia niezależności oznacza, że zależność zostanie uwzględniona podczas konstruowania sieci. Aby uwzględnić zależności między atrybutami, Kononenko zaproponował klasyfikator Bayesa Semi-Naïve (SNB), który łączył atrybuty w oparciu o twierdzenie Czebyszewa. Dane diagnostyczne wykorzystano do porównania wydajności SNB i NB. Stwierdzono, że wyniki dwóch domen są identyczne, ale w pozostałych dwóch domenach SNB nieznacznie poprawia wydajność. Niemniej jednak metoda ta może powodować problemy z nadmiernym dopasowaniem. Innym ograniczeniem SNB jest to, że liczba parametrów rośnie wykładniczo wraz ze wzrostem liczby atrybutów, które należy połączyć. Ponadto wyczerpująca technika wyszukiwania łącząca atrybuty może wpływać na czas obliczeń. Pazzani (Pazzani, 1995)zastosował metodę Forward Sequential Selection and Joining (FSSJ) oraz Backward Sequential Elimination and Joining (BSEJ) do wyszukiwania zależności i łączenia atrybutów. Przetestowali obie metody na danych UCI i stwierdzili, że BSEJ zapewnia największą poprawę. Friedman i in. (Friedman, Geiger i Goldszmidt, 1997) stwierdzili, że metody Kononenko i Pazzaniego można przedstawić jako rozszerzoną sieć Naïve Bayesa, która zawiera pewne podgrafy. Ograniczyli sieć do sieci Tree Augmented Naïve Bayes (TAN), obejmującej wszystkie atrybuty i możliwej do uczenia się za pomocą algorytmów uczenia się struktury drzewa. Wyniki oparte na problemach z repozytorium UCI pokazały, że klasyfikator TAN przewyższa klasyfikator Naïve Bayesa. Jest on również konkurencyjny w stosunku do C4.5, zachowując jednocześnie prostotę obliczeniową. Jednak zastosowanie klasyfikatora TAN jest ograniczone jedynie do problemów z atrybutami dyskretnymi. W przypadku problemów z atrybutami ciągłymi, atrybuty te muszą być predyskretyzowane. Aby rozwiązać ten problem, Friedman i inni rozszerzyli TAN o obsługę atrybutów ciągłych za pomocą parametrycznych i półparametrycznych prawdopodobieństw warunkowych. Keogh i Pazzani zaproponowali wariant klasyfikatora TAN, tj. SP-TAN, który może zapewnić lepszą wydajność niż TAN. Wydajność metody SP-TAN jest również konkurencyjna w porównaniu z regułą Lazy Bayesa (LBR), w której techniki uczenia leniwego są wykorzystywane w klasyfikatorze Naïve Byes . Chociaż LBR i SP-TAN charakteryzują się znakomitą wydajnością w przypadku danych testowych, główną wadą obu metod jest ich wysoka złożoność obliczeniowa. Agregujące estymatory jednozależności (AODE), opracowane przez Webba, pozwalają uniknąć selekcji modelu, co może zmniejszyć złożoność obliczeniową i prowadzić do niższej wariancji. Zalety te zostały potwierdzone wynikami niektórych eksperymentów empirycznych. Stwierdzono również empirycznie, że średnia dokładność predykcji AODE jest porównywalna z LBR i SP-TAN, ale z niższą wariancją. Dlatego AODE może być bardziej odpowiednie dla małych zbiorów danych ze względu na niższą wariancję.

Korzystanie z procedur wstępnego przetwarzania

Ogólnie rzecz biorąc, procedury wstępnego przetwarzania dla klasyfikatora Naiwnego Bayesa obejmują selekcję cech i transformację oryginalnych atrybutów. Selektywny klasyfikator Bayesa (SBC) zajmuje się skorelowanymi cechami, wybierając tylko niektóre atrybuty do ostatecznego klasyfikatora. Zastosowano metodę zachłanną do przeszukiwania przestrzeni oraz selekcję w przód w celu wybrania atrybutów. W badaniu wykorzystano sześć zbiorów danych UCI do porównania wydajności klasyfikatora Naiwnego Bayesa, SBC i C4.5. Stwierdzono, że wybór atrybutów może poprawić wydajność klasyfikatora Naiwnego Bayesa w przypadku występowania atrybutów redundantnych. Ponadto stwierdzono, że SBC jest konkurencyjny wobec C4.5 pod względem zbiorów danych, w których C4.5 przewyższa klasyfikator Naiwnego Bayesa. W badaniu Ratanamahatana i Gunopulos zastosowano metodę C4.5 do wyboru atrybutów dla klasyfikatora Naïve Bayes. Co ciekawe, wyniki eksperymentów wykazały, że nowe atrybuty uzyskane za pomocą metody C4.5 mogą sprawić, że klasyfikator Naïve Bayes będzie skuteczniejszy niż C4.5 w odniesieniu do wielu zbiorów danych. Transformacja atrybutów to kolejna użyteczna procedura wstępnego przetwarzania dla klasyfikatora Naïve Bayes. Gupta stwierdził, że analiza głównych składowych (PCA) była pomocna w poprawie dokładności klasyfikacji i zmniejszeniu złożoności obliczeniowej. Prasad zastosował niezależną analizę składowych (ICA) do wszystkich danych treningowych i stwierdził, że wydajność klasyfikatora Naïve Bayes zintegrowanego z ICA była lepsza niż w przypadku metod C4.5 i IB1 zintegrowanych z ICA. Bressan i Vitria zaproponowali klasowo-warunkową klasyfikację ICA (CC-ICA) w celu wykonania procedury wstępnego przetwarzania dla klasyfikatora Naïve Bayes i odkryli, że klasyfikator Naïve Bayes oparty na CC-ICA przewyższył czysty klasyfikator Naïve Bayes. W oparciu o zbiory danych UCI, Fan i Poh przeprowadzili szczegółowe badanie porównawcze PCA, ICA i CC-ICA dla klasyfikatora Naïve Bayes. PCA próbuje przekształcić oryginalne dane w nowy, nieskorelowany zbiór danych, podczas gdy ICA próbuje przekształcić je w nowy zbiór danych z niezależnymi atrybutami. ICA warunkowa klasowo (CC-ICA), zaproponowana przez Bressana i Vitrię (2002), opiera się na założeniu, że ICA służy do uczynienia atrybutów jak najbardziej niezależnymi dla każdej klasy. W ten sposób nowe atrybuty są bardziej uzasadnione niż te z PCA i ICA, aby spełnić założenie niezależności klasyfikatora Naïve Bayes. Zbiory danych ograniczono do zbiorów ciągłych ze względu na wymagania trzech procedur wstępnego przetwarzania. Wyniki pokazały, że wszystkie trzy procedury wstępnego przetwarzania mogą poprawić wydajność klasyfikatora Naïve Bayes. Prawdopodobnie wynika to z faktu, że transformacja atrybutów mogłaby osłabić zależność między nimi. Ponadto rozbieżność między wydajnością ICA i PCA zintegrowanych z klasyfikatorem Naïve Bayes nie jest duża. Może to wskazywać, że PCA i ICA są konkurencyjne w poprawianiu wydajności klasyfikatora Naïve Bayes. Wraz ze wzrostem liczby atrybutów, trzy procedury wstępnego przetwarzania również poprawiły wydajność klasyfikatora Naïve Bayes o więcej. Z metodologicznego punktu widzenia procedura wstępnego przetwarzania CC-ICA wydaje się być bardziej prawdopodobna niż PCA i ICA dla klasyfikatora Naïve Bayes . Wyniki eksperymentów Fana i Poha wykazały również, że CC-ICA zintegrowana z klasyfikatorem Naïve Bayes przewyższa PCA i ICA zintegrowane z klasyfikatorem Naïve Bayes pod względem dokładności klasyfikacji. CC-ICA wymaga jednak większej ilości danych treningowych, aby zapewnić wystarczającą ilość danych treningowych dla każdej klasy. Dlatego sugeruje się, aby wybór odpowiedniej procedury wstępnego przetwarzania zależał od charakterystyki zbiorów danych, np. liczebności próby dla każdej klasy.

PRZYSZŁE TRENDY

Wraz z rozwojem algorytmów uczenia się klasyfikatorów Bayesa (BN), rozluźnienie założenia niezależności jest obiecujące dla poprawy wydajności klasyfikatora Naiwnego Bayesa. Jednak rozluźnienie założenia niezależności dla nieograniczonego klasyfikatora Bayesa nie jest właściwe. Friedman i inni porównali klasyfikator Naiwnego Bayesa i sieć bayesowską i stwierdzili, że użycie nieograniczonego klasyfikatora Bayesa nie poprawiło dokładności. Wręcz przeciwnie, wręcz zmniejszyło dokładność w niektórych domenach. Dlatego można zastosować inne ograniczone klasyfikatory Bayesa w celu poprawy wydajności, zachowując jednocześnie prostotę klasyfikatora Bayesa Naiwnego. Skuteczny i prosty algorytm uczenia się jest również istotny dla poprawy wydajności. Z drugiej strony, wraz z rozwojem algorytmów uczenia maszynowego, oczekuje się opracowania większej liczby procedur wstępnego przetwarzania do selekcji lub transformacji atrybutów. Jednym z możliwych sposobów na poprawę wydajności jest połączenie selekcji cech z technikami transformacji w celu wykonania procedur wstępnego przetwarzania. Spośród alternatywnych technik wykonywania procedur wstępnego przetwarzania, najbardziej obiecująca może być ICA. Powodem jest to, że celem procedur wstępnego przetwarzania jest wyprowadzenie atrybutów spełniających założenie niezależności dla klasyfikatora Naiwnego Bayesa, podczas gdy celem ICA jest znalezienie niezależnych komponentów. Istnieją jednak pewne ograniczenia w stosowaniu ICA, np. wymagania dotyczące ciągłych zbiorów danych i dużej liczby próbek uczących. Pokonanie tych ograniczeń stanowi zatem potencjalny obszar przyszłych badań.

WNIOSKI

W niniejszym artykule krótko omówiono techniki, które można wykorzystać do poprawy wydajności klasyfikatora Naiwnego Bayesa. Ogólnym założeniem jest pokonanie ograniczenia silnego założenia niezależności klasyfikatora Naiwnego Bayesa. Rozluźnienie silnego założenia jest naturalnym sposobem i zostało zbadane z różnych punktów widzenia. Wszystkie podejścia rozluźniające to założenie omówione w artykule są ograniczonymi sieciami bayesowskimi, które nadal są najbardziej praktycznymi technikami. Ponadto procedury wstępnego przetwarzania są również bardzo przydatne do dostosowania atrybutów do założenia niezależności. Jednak stosowanie tych podejść zwiększa w pewnym stopniu złożoność obliczeniową. Przydatne byłoby modelowanie korelacji między odpowiednimi atrybutami, które można uchwycić za pomocą prostej, ograniczonej struktury, ale z dobrą wydajnością.

WSTĘP

Postrzeganie sztucznych sieci neuronowych jako systemów adaptacyjnych doprowadziło do rozwoju doraźnych procedur generycznych, znanych jako reguły uczenia się. Pierwszą z nich jest reguła perceptronu (Rosenblatt, 1962), przydatna w przypadku jednowarstwowych sieci z jednokierunkowym sprzężeniem zwrotnym i problemów liniowo separowalnych. Jej prostota i piękno, a także istnienie twierdzenia o zbieżności uczyniły ją podstawowym punktem wyjścia w algorytmach uczenia się neuronowego. Algorytm ten jest szczególnym przypadkiem reguły Widrowa-Hoffa lub reguły delty , mającej zastosowanie do sieci ciągłych bez warstw ukrytych z funkcją błędu o parametrach kwadratowych.

TŁO

Pierwszym prawdziwie użytecznym algorytmem dla sieci wielowarstwowych ze sprzężeniem zwrotnym jest algorytm propagacji wstecznej , podobno zaproponowany po raz pierwszy przez Werbosa (1974) i Parkera (1982). Wiele wysiłków poświęcono jego ulepszeniu na wiele sposobów, zwłaszcza w zakresie szybkości i niezawodności zbieżności . Algorytm propagacji wstecznej służy generalnie do obliczania wektora gradientu we wszystkich metodach pierwszego rzędu, omówionych poniżej. Sieci neuronowe =są trenowane poprzez ustawienie wartości parametrów sieci celu zminimalizowania funkcji błędu . Jeśli funkcja ta jest kwadratowa względem to rozwiązanie można znaleźć, rozwiązując liniowy układ równań (np. za pomocą rozkładu na wartości osobliwe ) lub iteracyjnie za pomocą reguły delta. Minimalizacja jest realizowana za pomocą wariantu procedury gradientu prostego, której ostatecznym wynikiem jest minimum lokalne: , od którego każda nieskończenie mała zmiana powoduje wzrost , co może nie odpowiadać jednemu z minimów globalnych. Różne rozwiązania uzyskuje się rozpoczynając od różnych stanów początkowych. Proces jest również zaburzony przez błędy zaokrągleń. Biorąc pod uwagę minimalizację i stan początkowy , metody te wykonują dla każdej iteracji krok aktualizacji:



gdzie uⁱ to kierunek minimalizacji (kierunek ruchu), a α_i ∈ R to rozmiar kroku (o jaki dystans należy wykonać w uⁱ), znany również we wcześniejszych kontekstach jako tempo uczenia się. Dla wygody zdefiniuj . Typowe kryteria zatrzymania to:

1. Osiągnięto maksymalną liczbę prezentacji D (epok).
2. Przekroczono maksymalny czas obliczeń.
3. Ocena została zminimalizowana poniżej określonej tolerancji.
4. Norma gradientu spadła poniżej określonej tolerancji.

ALGORYTMY UCZENIA SIĘ

Algorytmy uczenia mogą wymagać informacji tylko z funkcji celu, wektora gradientu funkcji celu lub macierzy hesjańskiej funkcji celu:

o Algorytmy uczenia zerowego rzędu wykorzystują tylko funkcję celu. Najważniejszymi algorytmami są algorytmy ewolucyjne, które są metodami optymalizacji globalnej .

o Algorytmy uczenia pierwszego rzędu wykorzystują funkcję celu i jej wektor gradientu. Przykładami są metody gradientu zstępującego, gradientu sprzężonego lub quasi-Newtona, które są metodami optymalizacji lokalnej .

o Algorytmy uczenia drugiego rzędu wykorzystują funkcję celu, jej wektor gradientu i macierz hesjańską. Przykładami są metoda Newtona i algorytm Levenberga-Marquardta, które są metodami optymalizacji lokalnej.

Metody pierwszego rzędu. Gradient

funkcji s-wymiarowej jest polem wektorowym pierwszych pochodnych funkcji względem ,



Tutaj . Liniowa aproksymacja E(w) w nieskończenie małym otoczeniu dowolnego punktu




Zapisujemy dla gradientu obliczonego w . Są to pierwsze dwa wyrazy rozwinięcia Taylora wokół . W metodach najstromszego spadku lub gradientu prostego, ten lokalny gradient sam w sobie określa kierunek minimalizacji . Ponieważ w dowolnym punkcie , gradient wskazuje w kierunku najszybszego wzrostu , dostosowanie w kierunku ujemnym lokalnego gradientu prowadzi do jego maksymalnego spadku. W konsekwencji obierany jest kierunek W konwencjonalnym najstromszym spadku, rozmiar kroku α_i jest uzyskiwany przez przeszukiwanie linii w kierunku uⁱ: jak daleko należy zajść wzdłuż uⁱ, zanim zostanie wybrany nowy kierunek. W tym celu dokonuje się oceny i jego pochodnych w celu zlokalizowania pewnego pobliskiego lokalnego minimum. Przeszukiwanie linii to ruch w wybranym kierunku uⁱ w celu znalezienia minimum wzdłuż niego. W przypadku tego jednowymiarowego problemu najprostszym podejściem jest postępowanie wzdłuż uⁱ małymi krokami, oceniając w każdym punkcie próbkowania, aż zacznie ono rosnąć. Jedną z często stosowanych metod jest strategia "dziel i zwyciężaj", zwana również metodą Brenta :

1. Uwzględnij przeszukiwanie, ustawiając trzy punkty ai tak, aby E(auⁱ)>E(buⁱ)i). Ponieważ E jest ciągłe, istnieje minimum lokalne na linii łączącej a z c.

2. Dopasuj parabolę (wielomian kwadratowy) do a, b, c.

3. Oblicz minimum ľ paraboli na linii łączącej a z c. Wartość ta jest przybliżeniem minimum E w tym przedziale.

4. Ustaw trzy nowe punkty a, b, c spośród ľ oraz dwa punkty spośród starych a, b, c o najniższym E. Powtórz od 2.

Chociaż możliwe jest zlokalizowanie najbliższego minimum globalnego, koszt może być niemożliwie wysoki. Przeszukiwanie linii można zastąpić stałym krokiem α, który należy starannie dobrać. Wymagane jest wystarczająco małe α?, tak aby było efektywnie bardzo małe i można było zastosować rozwinięcie (3). Zbyt duża wartość może spowodować przekroczenie lub doprowadzić do oscylacji rozbieżnych i całkowitego załamania algorytmu. Z drugiej strony, bardzo małe wartości przekładają się na boleśnie powolną minimalizację. W praktyce przeprowadza się metodę prób i błędów. Popularną heurystyką jest historyczna średnia z poprzednich zmian w celu wykorzystania tendencji i dodania bezwładności do spadku, uzyskiwana poprzez dodanie tzw. członu pędu , gdzie to poprzednia aktualizacja wagi. Ten człon pomaga uniknąć lub wygładzić oscylacje w ruchu w kierunku minimum. W praktyce przyjmuje się stałą wartość β∈(0,5,1). W sumie dla najszybszego spadku równanie aktualizacji (1) wygląda następująco:



gdzie i . Metoda ta jest bardzo wrażliwa na wybrane wartości α_i i β do tego stopnia, że dla różnych problemów, a nawet dla różnych etapów procesu uczenia się, wymagane są różne wartości . Nieefektywność metody najszybszego spadku wynika z faktu, że zarówno uⁱ, jak i α_i są dość źle dobrane. O ile pierwszy krok nie zostanie wybrany w sposób prowadzący prosto do minimum, procedura iteracyjna najprawdopodobniej będzie błądzić z wieloma małymi krokami zygzakiem. Dlatego te metody są obecnie całkowicie nieużywane. Metodą, w której oba parametry są prawidłowo dobrane, jest gradient sprzężony.

Gradient sprzężony

Ta technika minimalizacji opiera się na założeniu, że nowy kierunek uⁱ⁺¹ nie powinien zepsuć poprzednich minimalizacji w kierunkach . Dzieje się tak, jeśli po prostu wybierzemy , gdzie , jak to zostało znalezione powyżej dla najszybszego spadku. W większości punktów na gradient nie jest skierowany bezpośrednio w kierunku minimum. Po minimalizacji linii, nowy gradient jest ortogonalny do kierunku przeszukiwania linii, tj. . Zatem kolejne kierunki przeszukiwania również będą ortogonalne, a minimalizacja funkcji błędu będzie przebiegać zygzakiem, niezwykle powoli, do minimum. Rozwiązanie tego problemu polega na określeniu kolejnych kierunków przeszukiwania uⁱ⁺¹ w taki sposób, aby składowa gradientu równoległa do uⁱ (która właśnie została zerowana, ponieważ minimalizowaliśmy w tym kierunku) pozostała zerowa, dzięki czemu kolejne kierunki przeszukiwania uzupełniają się, unikając możliwości zaprzepaszczenia postępu osiągniętego w poprzednich iteracjach. Załóżmy, że właśnie wykonano minimalizację linii wzdłuż uⁱ, zaczynając od bieżących wag ; znaleźliśmy zatem nowy punkt , dla którego



spełnia. Następny kierunek wyszukiwania uⁱ⁺¹ jest wybierany, aby zachować właściwość, że składowa gradientu równoległa do uⁱ pozostaje zerowa:



Rozwijając (6) do pierwszego rzędu w α_i i stosując (5), otrzymujemy warunek :

Jeśli powierzchnia błędu jest kwadratowa, równanie (7) zachodzi niezależnie od wartości α_i, ponieważ hesjan jest stały, a wyrazy wyższego rzędu w poprzednim rozwinięciu znikają. Kierunki poszukiwań uⁱ⁺¹,uⁱ spełniające warunek (7) nazywane są sprzężonymi. Można udowodnić, że w tych warunkach możliwe jest skonstruowanie ciągu takiego, że jest sprzężony ze wszystkimi poprzednimi kierunkami, tak aby minimum można było znaleźć w co najwyżej krokach. Technika gradientu sprzężonego odchodzi od (1), ale ustawia , ustawiając . Okazuje się, że βⁱ można znaleźć bez jawnej znajomości hesjanu, a różne wersje gradientu sprzężonego rozróżnia się na podstawie sposobu ustawienia parametru βⁱ. Dla aktualizacji Polaka-Ribière′a:



Jest to iloczyn skalarny poprzedniej zmiany gradientu z bieżącym gradientem, podzielony przez kwadrat normy poprzedniego gradientu. Dla aktualizacji Fletchera-Reevesa:



Jest to stosunek kwadratu normy bieżącego gradientu do kwadratu normy poprzedniego gradientu. α_i można znaleźć, wykonując przeszukiwanie liniowe (w każdym kroku iteracji), aby określić optymalną odległość do przemieszczenia się wzdłuż bieżącego kierunku pociągu; to znaczy minimalizację liniową względem α_i Prowadzi to do szczególnego przypadku najstromszego spadku z pędem, gdzie parametry α_i,β_i są określane w każdej iteracji. Dla kwadratowej powierzchni błędu metoda znajduje minimum po co najwyżej

krokach, bez obliczania hesjanu. W praktyce może być dalekie od kwadratu, więc technika musi być uruchamiana przez wiele iteracji i rozszerzona o kryterium resetowania wektora przeszukiwania do ujemnego kierunku gradientu po każdych s krokach . Wersja skalowana uwzględnia w pewnym stopniu niekwadratowy charakter funkcji błędu. Dzięki tym ulepszeniom metoda ta jest powszechnie uważana za szybką i niezawodną. W przeciwieństwie do metody najstromszego spadku, jest ona stosunkowo niewrażliwa na swoje parametry - poszukiwanie linii dla ?i i warianty obliczania β_i - jeśli są one ustawione w rozsądnym zakresie tolerancji. Istnieją pewne dowody na to, że wzór Polaka-Ribière′a umożliwia bardziej wydajne przejście do dalszych iteracji: gdy traci siłę, ma tendencję do resetowania kierunku pociągu uⁱ, aby zszedł z lokalnego gradientu, co jest równoważne z ponownym rozpoczęciem procedury gradientu sprzężonego.

Algorytm uczenia Newtona

Aproksymacje pierwszego rzędu ignorują krzywiznę . Można to naprawić, rozważając człon drugiego rzędu rozwinięcia Taylora wokół pewnego w przestrzeni wag:



gdzie jest macierzą hessowską s×s drugich pochodnych, ze składowymi



Ponownie, wskazuje na ocenę w . Hesjan śledzi krzywiznę funkcji błędu w przestrzeni wag, przedstawiając informacje o tym, jak zmienia się w różnych kierunkach. Biorąc pod uwagę kierunek uⁱ od , iloczyn i jest szybkością zmiany gradientu wzdłuż uⁱ od . Różniczkując (10) względem w, lokalne przybliżenie gradientu wokół wygląda następująco:

Dla punktów bliskich równania (10) i (11) dają rozsądne przybliżenia funkcji błędu i jej gradientu. Ustawiając równanie (11) na zero i rozwiązując równanie dla w, otrzymujemy:



Metoda Newtona wykorzystuje drugie pochodne cząstkowe funkcji celu, a zatem jest metodą drugiego rzędu, znajdującą minimum funkcji kwadratowej w zaledwie jednej iteracji. Wektor jest znany jako kierunek ciągu Newtona. Ponieważ pominięto wyrazy wyższego rzędu, wzór aktualizacji (12) jest używany iteracyjnie do znalezienia optymalnego rozwiązania. Dokładna ocena hesjanu jest wymagająca obliczeniowo, jeśli jest przeprowadzana na każdym etapie algorytmu iteracyjnego; macierz hesjanu musi być również odwrócona. Co więcej, kierunek ciągu Newtona może zmierzać w kierunku maksimum lub punktu siodłowego, a nie minimum (jeśli hesjan nie jest dodatnio określony), a redukcja błędu nie jest gwarantowana. To motywuje do opracowania alternatywnych metod aproksymacji.

Algorytm uczenia quasi-Newtona

Jak pokazano powyżej, wzór iteracyjny używany w metodzie Newtona to



Podstawową ideą metody quasi-Newtona jest aproksymacja inną macierzą G, przy użyciu jedynie pierwszych pochodnych cząstkowych funkcji błędu. Jeśli jest aproksymowane przez macierz G, równanie (13) można zapisać jako



gdzie α^*(i) można uznać za optymalną prędkość pociągu wzdłuż kierunku pociągu . Metodę kierunku gradientu zstępującego można uzyskać, ustawiając G=I. Aby zaimplementować równanie (14), potrzebna jest przybliżona odwrotność G macierzy hesjańskiej. Dwa powszechnie stosowane algorytmy to algorytm Davidona-Fletchera-Powella (DFP) i algorytm Broydena-Fletchera-Goldfarba-Shanno (BGFS). Algorytm DFP jest podany wzorem



gdzie ⊗ oznacza iloczyn zewnętrzny, który jest macierzą: składowa i,j funkcji u⊗v to u_iv_j. Algorytm BGFS jest dokładnie taki sam, ale z jednym dodatkowym członem:



gdzie wektor v jest podany przez



Powszechnie uznaje się, że schemat BFGS jest empirycznie lepszy od schematu DFP (Press, Teukolsky, Vetterling i Flannery, 1992). Metoda Levenberga-Marquardta, podobnie jak metody quasi-Newtona, została zaprojektowana w celu osiągnięcia szybkości uczenia drugiego rzędu bez obliczania hesjanu. Gdy funkcją celu jest suma kwadratów (bardzo częsty przypadek w sieciach neuronowych), macierz hesjanu można aproksymować wzorem H=J^TJ, a gradient obliczyć wzorem , gdzie J jest macierzą Jakobianu zawierającą pierwsze pochodne błędów sieci względem wag, a jest wektorem błędów sieci. Jakobian można obliczyć za pomocą standardowej propagacji wstecznej, procesu znacznie mniej złożonego niż obliczanie hesjanu. Algorytm Levenberga-Marquardta wykorzystuje to przybliżenie do hesjanu w następującej aktualizacji podobnej do Newtona:



Gdy skalar μ jest równy zeru, jest to metoda Newtona wykorzystująca przybliżoną macierz hesjańską. Gdy μ jest duże, staje się to metodą spadku gradientowego z małym krokiem. Metoda Newtona jest szybsza i dokładniejsza w pobliżu minimum błędu, dlatego celem jest jak najszybsze przejście w kierunku metody Newtona. Zatem μ jest zmniejszane po każdym udanym kroku (redukcji funkcji celu) i zwiększane tylko wtedy, gdy krok kuszący spowodowałby jego wzrost. Gdy obliczenia Jakobianu stają się niemożliwie wysokie dla dużych sieci na dużej liczbie przykładów treningowych, preferowana jest metoda quasi-Newtona.

ALGORYTM PROPAGACJI WSTECZNEJ

Ten algorytm stanowił przełom w uczeniu koneksjonistycznym ze względu na możliwość rekurencyjnego i wydajnego obliczenia gradientu funkcji błędu . Nazywa się tak, ponieważ składowe gradientu dotyczące wag należących do jednostek wyjściowych są obliczane jako pierwsze i propagowane wstecz (w kierunku wejść), aby obliczyć pozostałe, w kolejności określonej przez warstwy. Intuicyjnie, algorytm określa stopień, w jakim dostosowanie jednego połączenia zmniejszy błąd w przykładach treningowych (pochodna cząstkowa funkcji błędu względem połączenia) i dlatego algorytm oblicza pełny wektor gradientu . Aby wyprowadzić algorytm, wprowadzamy pewną notację.Dla funkcji f: Rⁿ -> R^m, która ma być aproksymowana, wychodzimy od skończonego zbioru treningowego D zawierającego p próbek f,



Dla uproszczenia przyjmujemy, że strata jest błędem kwadratowym i definiujemy:



gdzie μ (sieć ma c+1 warstw, z których c jest ukrytych). Dla danego wzorca wejściowego x_μ zdefiniuj:



aby

Obliczenie pojedynczej jednostki i w warstwie l, 1≤ l ≤ c+1 po przedstawieniu sieci wzorca x_μ można wyrazić wzorem

, gdzie g jest funkcją gładką - jak sigmoidalne - i



Pierwsze wyjścia są następnie definiowane jako ζ,sup>μ,0i = x_μi. Pojedyncza waga w_{ij,/sub>^l oznacza siłę połączenia z neuronu j w warstwie l-1 do neuronu i w warstwie l, 1≤ l ≤ c+1. Jeśli zastosowana zostanie reguła gradientu zstępującego (1) ze stałą ?, wówczas . Wraz z (2), przyrost Δwij w pojedynczej wadze w>sub>ij}^l równania w wynosi:



Mamy:



Kontynuując od prawej do lewej w (23):



Zakładając, że g jest funkcją logistyczną o nachyleniu β:



Pozostałe wyrażenie



jest bardziej delikatny i stanowi rdzeń algorytmu. Rozwijamy dwa oddzielne przypadki: l=c+1 i l


Przy okazji, zbierając wszystkie dotychczasowe wyniki i zakładając c=0 (brak warstw ukrytych), otrzymujemy regułę delty dla nieliniowych sieci jednowarstwowych:



gdzie pomijamy indeks górny l (ponieważ c=0), a

. Inną nazwą algorytmu propagacji wstecznej jest uogólniona reguła delty. W związku z tym, dla l ≥ 1, delty (błędy lokalne dla jednostki) są definiowane jako:



Dla warstwy wyjściowej l=c+1, δ^μ,l_i= (y_μ,i -ς^μ_i)g′(ξ^μ_i.W przypadku gdy g jest funkcją logistyczną, ostatecznie mamy:



W przypadku ogólnym l


Teraz l funkcjonalnie zależy od warstwy l+1 przed warstwą l, a pochodną można podzielić na dwie części. Sumowanie po k wynika z faktu, że zależy od każdego neuronu w warstwie l+1. Przepisując (31):



ponieważ



a zatem



Łącząc (24), (25), (27) i (32) w (23):



gdzie



delty dla jednostek ukrytych. Przedstawiamy metodę w formie algorytmicznej, dla epoki lub prezentacji zbioru treningowego.



WNIOSKI

Mocnymi stronami sieci neuronowych są zdolność uczenia się na przykładach, obliczenia rozproszone, odporność na częściowe awarie oraz możliwość wykorzystania ich jako modeli typu "czarna skrzynka". Procedura wykorzystywana do przeprowadzenia procesu uczenia w sieci neuronowej nazywana jest algorytmem uczenia lub uczenia. Ponieważ funkcja celu jest nieliniową funkcją swobodnych parametrów, nie jest możliwe znalezienie zamkniętych algorytmów uczenia dla minimów. Preferowanymi algorytmami dla perceptronu wielowarstwowego są metody quasi-Newtona i Levenberga-Marquardta, wraz z propagacją wsteczną, umożliwiającą efektywne obliczenie wektora gradientu.

WSTĘP

Nadzorowane sztuczne sieci neuronowe (ANN) to systemy przetwarzania informacji, które dostosowują swoją funkcjonalność w wyniku interakcji z przykładami wejścia-wyjścia. W tym celu istnieją ogólne procedury i techniki, znane jako reguły uczenia się. Najczęściej stosowane w kontekście sieci neuronowych opierają się na informacjach pochodnych i są zazwyczaj związane z perceptronem wielowarstwowym (MLP). Inne rodzaje nadzorowanych ANN opracowały własne techniki. Tak jest w przypadku sieci Radialnych Funkcji Bazowych (RBF) . Prowadzono również intensywne prace nad rozwojem ad-hoc metod uczenia się opartych na algorytmach ewolucyjnych.

TŁO

Problem uczenia się relacji wejście/wyjście na podstawie zbioru przykładów można postrzegać jako zadanie aproksymacji nieznanej funkcji na podstawie zbioru punktów danych, które mogą być rzadkie. Jeśli chodzi o aproksymację za pomocą klasycznych sieci neuronowych ze sprzężeniem w przód, sieci te implementują parametryczną funkcję aproksymującą iwykazano, że są w stanie reprezentować ogólne klasy funkcji (jako funkcje ciągłe lub całkowalne) z dowolnym stopniem dokładności. Ogólnie rzecz biorąc, podczas definiowania takiej sparametryzowanej rodziny funkcji pojawiają się trzy pytania:

1. Jaka jest najbardziej odpowiednia forma parametryczna dla danego problemu?
2. Jak znaleźć najlepsze parametry dla wybranej formy?
3. Jakie klasy funkcji można reprezentować i jak dobrze?

Do najczęstszych problemów w procesie uczenia nadzorowanego w sieciach neuronowych (SSN), oprócz samego określania parametrów uczenia, należą :

1. Możliwość utknięcia w lokalnych optimach funkcji kosztu, w których konwencjonalne nieliniowe techniki optymalizacji pozostaną na zawsze. Wprowadzenie globalnego schematu (takiego jak wielokrotne restarty lub harmonogram wyżarzania) z pewnością zwiększy szansę na znalezienie lepszego rozwiązania, choć koszt może stać się niemożliwie wysoki. Sieć sprzężenia zwrotnego ma wiele równoważnych rozwiązań, tworzonych przez permutacje wag i odwracanie znaku. Każde lokalne minimum w sieci z pojedynczą ukrytą warstwą jednostek h₁ ma s(h₁)=h₁!2^h₁ równoważnych rozwiązań, więc szanse na znalezienie w 1 basenu przyciągania jednego z nich są dość wysokie. Złożoność powierzchni błędu- szczególnie w bardzo wysokich wymiarach - sprawia, że możliwość wpadnięcia w pułapkę jest realna.

2. Długi czas uczenia, oscylacje i paraliż sieci. Są to cechy ściśle związane ze specyficznym algorytmem uczenia się i wiążą się z błędnym lub zbyt ogólnym wyborem parametrów techniki optymalizacji (takich jak szybkość uczenia). Obecność punktów siodłowych - obszarów, w których powierzchnia błędu jest bardzo płaska - również powodujeekstremalnie powolny postęp przez dłuższy czas. Zastosowanie bardziej zaawansowanych metod, które dynamicznie ustawiają te i inne parametry, może złagodzić ten problem.

3. Uczenie niekumulatywne. Trudno jest ponownie wytrenować już wytrenowaną sieć z wykorzystaniem dodatkowych danych bez utraty wcześniej nabytej wiedzy.

4. Klątwa wymiarowości, w skrócie wyrażona jako fakt, że liczba przykładów potrzebnych do przedstawienia danej funkcji rośnie wykładniczo wraz z liczbą wymiarów.

5. Trudności ze znalezieniem struktury w danych uczących, prawdopodobnie spowodowane bardzo dużą liczbą wymiarów lub zniekształcającym schematem wstępnego przetwarzania.

6. Błędna generalizacja, która może wynikać z kilku przyczyn: użycia słabych danych treningowych lub prób ekstrapolacji poza nie, nadmiernej liczby jednostek ukrytych, zbyt długich procesów treningowych lub źle dobranej regularyzacji. Wszystkie te czynniki mogą prowadzić do nadmiernego dopasowania danych treningowych, w którym sieć neuronowa dostosowuje zbiór treningowy jedynie w ramach zadania interpolacji.

7. Niemożność inspekcji. Interpretacja zdobytej wiedzy jest zazwyczaj trudna, szczególnie w dużych sieciach lub z dużą liczbą danych wejściowych modelu.

UCZENIE SIĘ W SIECIACH RBF

Sieć z radialną funkcją bazową to rodzaj sztucznej inteligencji (SSN), którą można postrzegać jako rozwiązanie problemu dopasowania krzywej wielowymiarowej. Uczenie się jest równoważne ze znalezieniem powierzchni zapewniającej najlepsze dopasowanie do danych. Sieć RBF to dwuwarstwowa sieć typu feed forward wykorzystująca liniową funkcję przejścia dla jednostek wyjściowych i radialnie symetryczną funkcję przejścia dla jednostek ukrytych. Obliczenie jednostki ukrytej jest wyrażone jako złożenie dwóch funkcji, jako:



z wyborem h(x,w_i)= ||x-w_i||/θ (lub innej miary odległości), zθ > 0, wyrazem wygładzającym, plus aktywacją g, która bardzo często jest monotonicznie malejącą odpowiedzią z początku układu współrzędnych. Jednostki te są zlokalizowane w tym sensie, że dają znaczącą odpowiedź tylko w otoczeniu swojego środka w_i. Dla funkcji aktywacji preferowanym wyborem jest gaussowskie g(z)=exp(-z²/2). Uczenie się w sieciach RBF charakteryzuje się rozdzieleniem procesu na dwa kolejne etapy :

1. Zoptymalizuj wolne parametry warstwy ukrytej (w tym wyraz wygładzający) używając tylko {x}_i w D. Jest to metoda nienadzorowana, która zależy od rozkładu próbki wejściowej.
2. Po znalezieniu i zamrożeniu tych parametrów zoptymalizuj {ci}i, czyli wagi ukryte do wyjściowej, używając pełnej informacji w D. Jest to metoda nadzorowana, która zależy od danego zadania.

Istnieje wiele sposobów optymalizacji parametrów warstwy ukrytej. Gdy liczba neuronów ukrytych jest równa liczbie wzorców, każdy wzorzec można uznać za środek danego neuronu. Celem jest jednak utworzenie reprezentacji funkcji gęstości prawdopodobieństwa danych poprzez umieszczenie środków tylko w tych obszarach przestrzeni wejściowej, w których obecne są istotne dane. Jedną z powszechnie stosowanych metod jest algorytm k-średnich , który z kolei jest przybliżoną wersją rozwiązania o największej wiarygodności (ML) do określania położenia średnich gęstości mieszaniny gęstości składników (tj. aksymalizacji wiarygodności parametrów względem danych). Algorytm maksymalizacji oczekiwań (EM) można wykorzystać do znalezienia dokładnego rozwiązania ML dla średnich i kowariancji gęstości. Wydaje się, że EM jest lepszy niż k-średnich . Zbiór centrów można również wybrać losowo ze zbioru punktów danych. Wartość składnika wygładzającego można uzyskać z samej metody klasteryzacji lub oszacować a posteriori. Jedną z popularnych heurystyk jest:



gdzie d to maksymalna odległość między wybranymi środkami, a M to liczba środków (jednostek ukrytych). Alternatywnie można zastosować metodę uśredniania odległości (DSO) , która jest globalną średnią wszystkich odległości euklidesowych między środkiem każdej jednostki a środkiem jej najbliższego sąsiada. Po wybraniu i utrzymaniu tych parametrów na stałym poziomie, przy założeniu, że jednostki wyjściowe są liniowe, funkcja błędu (kwadratowego) jest kwadratowa, a zatem wagi ukryte względem wyjściowych można szybko i niezawodnie znaleźć iteracyjnie, stosując prostą metodę spadku gradientu po powierzchni kwadratowej funkcji błędu lub bezpośrednio, rozwiązując rozwiązanie minimalnej normy dla problemu dopasowania danych metodą najmniejszych kwadratów . Cały zestaw parametrów sieci RBF można również zoptymalizować za pomocą procedury globalnego spadku gradientu dla wszystkich parametrów swobodnych jednocześnie . To powraca do omówionych już problemów minimów lokalnych, powolnego uczenia itp. Jednakże, w zasadzie można znaleźć lepsze rozwiązania, ponieważ rozwiązanie bez nadzoru koncentruje się na oszacowaniu funkcji gęstości prawdopodobieństwa wejściowego, ale wynikowa dyspozycja może nie minimalizować błędu kwadratowego.

EWOLUCYJNE ALGORYTMY UCZENIA SIĘ

Alternatywą dla algorytmów uczenia się opartych na pochodnych (DBLA) są algorytmy ewolucyjne (EA) . Chociaż liczbę udanych konkretnych zastosowań algorytmów ewolucyjnych szacuje się na setki , jedynie algorytmy genetyczne (GA) oraz, w mniejszym stopniu, programowanie ewolucyjne były szeroko stosowane do optymalizacji sieci neuronowych (SSN), od czasu wcześniejszych prac wykorzystujących algorytmy genetyczne . Algorytmy ewolucyjne działają na populacji osobników, stosując zasadę przetrwania najlepiej przystosowanych, aby uzyskać lepsze przybliżenia rozwiązania. W każdym pokoleniu tworzona jest nowa populacja poprzez selekcję osobników według ich poziomu dostosowania w domenie problemu i rekombinację ich za pomocą operatorów zapożyczonych z genetyki naturalnej. Potomstwo również ulega mutacji. Proces ten prowadzi do ewolucji populacji osobników lepiej dostosowanych do swojego środowiska niż osobniki, z których powstały, podobnie jak w przypadku adaptacji naturalnej. Istnieją obszerne artykuły przeglądowe i przewodniki po obszernej literaturze na ten temat. Jedną z ich głównych zalet w porównaniu z metodami opartymi na pochodnych jest globalny mechanizm wyszukiwania. Globalna metoda nie oznacza, że rozwiązanie nie jest lokalnym optimum; raczej eliminuje możliwość utknięcia w lokalnych optimach. Inną atrakcyjną kwestią jest możliwość wykonania tradycyjnie oddzielnych kroków określania najlepszej architektury i jej wag jednocześnie, w przeszukiwaniu wspólnej przestrzeni struktur i wag. Inną zaletą jest wykorzystanie potencjalnie dowolnej miary kosztów do oceny dopasowania lub uwzględnienia informacji strukturalnych. Jeszcze inną możliwością jest wcielenie algorytmu dynamicznego (DBL) w algorytm genetyczny (GA), wykorzystując ten ostatni do przeszukiwania przestrzeni struktur, a algorytm dynamiczny (DBL) do optymalizacji wag; taka hybrydyzacja prowadzi do ekstremalnie wysokich kosztów obliczeniowych. Wreszcie, istnieje możliwość wykorzystania algorytmu dynamicznego wyłącznie do numerycznego problemu optymalizacji. W kontekście neuronowym jest to prawdopodobnie zadanie, do którego ciągłe algorytmy dynamiczne (EA) są najbardziej naturalnie przystosowane.Trudno jednak znaleźć zastosowania, w których algorytmy dynamiczne (GA) (lub inne algorytmy dynamiczne) wyraźnie przewyższają algorytmy dynamiczne (BDLA) w nadzorowanym szkoleniu sieci neuronowych z jednokierunkowym sprzężeniem zwrotnym . Wskazano, że zadanie to jest z natury trudne dla algorytmów, które w dużym stopniu opierają się na rekombinacji potencjalnych rozwiązań . Ponadto czas szkolenia może stać się zbyt kosztowny, nawet gorszy niż w przypadku DBLA. Ogólnie rzecz biorąc, algorytmy ewolucyjne - a w szczególności algorytmy ciągłe - wymagają szczegółowych badań poświęconych ustaleniu ich ogólnej trafności jako alternatywy dla DBLA w optymalizacji sieci neuronowych. Prace teoretyczne i praktyczne, ukierunkowane na dostosowanie konkretnych parametrów algorytmu ewolucyjnego do tego zadania, wraz ze specjalistycznym projektowaniem operatorów, powinny utorować drogę do owocnej oceny trafności.

TRENDY PRZYSZŁOŚCI

Badania w dziedzinie sieci neuronowych (ANN) dotyczą obecnie rozwoju algorytmów uczenia się w celu adaptacji wag lub, częściej, udoskonalania istniejących. Od czasu do czasu wprowadzane są również nowe architektury (sposoby rozmieszczania jednostek w sieci). Klasyczne modele neuronowe, choć użyteczne i skuteczne, są redukowane do kilku ogólnych klas funkcji, z których tylko nieliczne przykłady są wykorzystywane w praktyce. Jednym z najatrakcyjniejszych ulepszeń jest rozszerzenie modeli neuronowych na współczesne sytuacje eksploracji danych, takie jak heterogeniczność danych. Chociaż sieć neuronowa typu feed-forward może w zasadzie aproksymować dowolną funkcję z dowolnym pożądanym stopniem dokładności, w praktyce do próbek danych często stosuje się schemat wstępnego przetwarzania, aby ułatwić to zadanie. W wielu ważnych dziedzinach świata rzeczywistego obiekty są opisywane za pomocą mieszanki zmiennych ciągłych i dyskretnych, zazwyczaj zawierających brakujące informacje i charakteryzujących się nieostrością, niepewnością lub niedokładnością. Na przykład w znanym repozytorium UCI ponad połowa problemów zawiera jawnie zadeklarowane atrybuty nominalne, nie mówiąc już o innych typach dyskretnych lub informacjach rozmytych, zazwyczaj niezgłaszanych. Tej heterogenicznej informacji nie należy generalnie traktować jako wartości rzeczywistych. Konwencjonalne sposoby kodowania niestandardowych informacji w sieciach neuronowych (ANN) obejmują:

Zmienne porządkowe. Zmienne te odpowiadają dyskretnym (skończonym) zbiorom wartości, dla których zdefiniowano uporządkowanie (być może tylko częściowe). Są one często traktowane jako wartości rzeczywiste i odwzorowywane równoodlegle na dowolnym przedziale wartości rzeczywistych. Drugą możliwością jest ich zakodowanie za pomocą termometru. W tym celu niech k będzie liczbą uporządkowanych wartości; wówczas tworzonych jest k nowych danych binarnych. Aby przedstawić wartość i, dla 1≤ i ≤ k, skrajne lewe jednostki 1,...,i będą włączone, a pozostałe i+1,...,k wyłączone. Zainteresowanie tymi zmiennymi wynika z faktu, że często pojawiają się one w domenach rzeczywistych, albo jako informacja symboliczna, albo w procesach o charakterze dyskretnym. Należy zauważyć, że zmienna porządkowa nie musi być numeryczna.

Zmienne nominalne Zmienne nominalne są jednomyślnie kodowane przy użyciu reprezentacji 1 z k, gdzie k jest liczbą wartości, które są następnie kodowane jako wiersze macierzy jednostkowej I_k×k. Brakujące wartości Brakujące informacje to stary problem w analizie statystycznej. Istnieje kilka przyczyn braku wartości. Są one bardzo powszechne w medycynie i inżynierii, gdzie wiele zmiennych pochodzi z czujników online lub pomiarów urządzeń. Brakujące informacje są trudne do obsłużenia, szczególnie gdy utracone części są znacznej wielkości. Można je usunąć (cały przypadek) lub "uzupełnić" średnią, medianą, najbliższym sąsiadem lub zakodować, dodając inny sygnał wejściowy równy jeden tylko wtedy, gdy wartość jest nieobecna i zero w przeciwnym razie. Podejścia statystyczne muszą przyjmować założenia dotyczące samego rozkładu wejściowego lub go modelować. Głównym problemem z brakującymi danymi jest to, że nigdy nie wiemy, czy wszystkie wysiłki poświęcone ich oszacowaniu nie zwrócą się w praktyce w postaci lepiej zachowujących się danych. To jest również powód, dla którego rozwijamy temat traktowania brakujących wartości w ramach ogólnej dyskusji na temat charakterystyki danych. Omawiane metody wstępnie przetwarzają dane, aby uczynić je akceptowalnymi przez modele, które w przeciwnym razie by ich nie zaakceptowały. W przypadku brakujących wartości dane są uzupełniane, ponieważ dostępne metody neuronowe dopuszczają jedynie kompletne zbiory danych.

Niepewność. Niejasność, nieprecyzyjność i inne źródła niepewności to zagadnienia zazwyczaj pomijane w paradygmacie ANN. Niemniej jednak wiele zmiennych w procesach uczenia się prawdopodobnie będzie obarczonych jakąś formą niepewności. Na przykład w inżynierii czujniki on-line z czasem i ciągłym użytkowaniem mogą się starzeć, co może mieć odzwierciedlenie w jakości ich pomiarów. W wielu przypadkach dostępne dane są nieprecyzyjne z wielu powodów: ograniczeń technicznych, rzeczywistego pochodzenia jakościowego, a nawet możemy być zainteresowani wprowadzeniem nieprecyzyjności w celu zwiększenia możliwości abstrakcji lub generalizacji, prawdopodobnie dlatego, że uważa się, że proces leżący u ich podstaw jest mniej precyzyjny niż dostępne miary. W teorii systemów rozmytych istnieją jawne formalizmy do reprezentowania i manipulowania niepewnością, a to właśnie system najlepiej modeluje i zarządza. Zaskakujące jest to, że dostarczając tego rodzaju dane wejściowe/wyjściowe, wymagamy od sieci bardzo precyzyjnego przybliżenia pożądanego wyniku. Czasami znana wartość przyjmuje postać przedziałową: "między 5,1 a 5,5", więc każda transformacja do wartości rzeczywistej spowoduje utratę informacji. Bardziej powszechną sytuacją jest brak wiedzy numerycznej. Rozważmy na przykład wartość "dość wysoka" dla zmiennej wysokość. Ponownie, systemy rozmyte są wygodne, ale dla sieci neuronowych stanowi to prawdziwy problem. Integracja informacji symbolicznej i ciągłej jest również ważna, ponieważ metody numeryczne zapewniają większą konkretność, podczas gdy metody symboliczne wyższą abstrakcję. Ich łączne zastosowanie prawdopodobnie zwiększy elastyczność systemów hybrydowych. W przypadku danych numerycznych dodatkową elastyczność uzyskuje się poprzez uwzględnienie niedokładności ich wartości, co prowadzi do liczb rozmytych.

WNIOSKI

Jak szczegółowo wyjaśniono w innych rozdziałach, algorytmy uczenia się oparte na pochodnych przyjmują szereg założeń dotyczących lokalnej powierzchni błędu i jej różniczkowalności. Ponadto istnienie minimów lokalnych jest często pomijane lub całkowicie pomijane. W rzeczywistości możliwość znalezienia się w tych minimach jest często omijana przez wielokrotne uruchomienia algorytmu (tj. wielokrotne restarty z różnych punktów początkowych w przestrzeni wag). Ta procedura "próbkowania" jest w rzeczywistości implementacją bardzo naiwnego procesu stochastycznego. Globalnym algorytmem szkoleniowym dla sieci neuronowych jest algorytm ewolucyjny, czyli algorytm uczenia się z przeszukiwaniem stochastycznym oparty na mechanice genetyki naturalnej i ewolucji biologicznej. Wymaga on informacji z funkcji celu, ale nie z wektora gradientu ani macierzy hesjańskiej, a zatem jest metodą zerowego rzędu. Z drugiej strony pojawia się coraz większa potrzeba opracowania modeli neuronów, które będą w stanie prawidłowo obsługiwać różne typy danych, tak jak ma to miejsce w przypadku maszyn wektorów nośnych , gdzie projektowanie jądra jest aktualnym tematem badań.

WSTĘP

W dziedzinie przetwarzania języka naturalnego, jednym z bardzo ważnych obszarów badawczych ekstrakcji informacji (IE) jest rozpoznawanie jednostek nazwanych (NER). NER to podzadanie IE, którego celem jest identyfikacja i klasyfikacja predefiniowanych kategorii jednostek nazwanych w dokumentach tekstowych. W ostatnich latach włożono wiele pracy w rozwój NER ze względu na rosnące zapotrzebowanie na teksty zautomatyzowane i powszechną dostępność korpusów elektronicznych. O ile dla czytelnika czytanie i zrozumienie kontekstu danego artykułu jest stosunkowo łatwe i naturalne, o tyle nauczenie maszyny rozumienia i rozróżniania słów stanowi duże wyzwanie. Na przykład słowo "brązowy" może odnosić się do osoby o imieniu Pan Brown lub do koloru przedmiotu, który jest brązowy. Czytelnicy mogą łatwo zrozumieć znaczenie słowa, patrząc na kontekst danego zdania, ale dla komputera jego interpretacja bez dodatkowych informacji byłaby prawie niemożliwa. Aby rozwiązać ten problem, badacze z dziedziny NER zaproponowali różne systemy oparte na regułach . Systemy te są w stanie osiągnąć wysoką dokładność rozpoznawania za pomocą list znanych, nazwanych jednostek, zwanych gazeterami. Problem z podejściem opartym na regułach polega na tym, że brakuje mu solidności i przenośności. Wiąże się ono ze znacznymi kosztami utrzymania, zwłaszcza gdy konieczne jest wprowadzenie nowych reguł dla nowych informacji lub nowych domen. Lepszym rozwiązaniem jest zatem zastosowanie uczenia maszynowego, które jest podatne na trenowanie i adaptację. Trzy dobrze znane podejścia uczenia maszynowego, które były szeroko stosowane w NER, to Ukryty Model Markowa (HMM), Model Maksymalnej Entropii (MEM) i Drzewo Decyzyjne. Wiele istniejących systemów NER opartych na uczeniu maszynowym jest w stanie osiągnąć wydajność zbliżoną do ludzkiej w zakresie tagowania nazwanych jednostek, mimo że ogólna wydajność jest nadal o około 2% niższa od wydajności systemów opartych na regułach. Podejmowano również wiele prób poprawy wydajności NER za pomocą podejścia hybrydowego, łączącego ręcznie tworzone reguły z modelami statystycznymi Systemy te mogą osiągnąć stosunkowo dobrą wydajność w docelowych domenach dzięki kompleksowym, ręcznie tworzonym regułom. Niemniej jednak problem przenośności nadal pozostaje nierozwiązany, jeśli chodzi o wykorzystanie NER w różnych domenach.W związku z tym niniejszy artykuł przedstawia hybrydowe podejście do uczenia maszynowego, wykorzystujące kolejno MEM i HMM. Powodem zastosowania dwóch modeli statystycznych jeden po drugim, a nie jednego, jest ich odmienna natura. HMM osiąga lepszą wydajność niż jakikolwiek inny model statystyczny i jest powszechnie uważany za najskuteczniejszy w podejściu do uczenia maszynowego. Jednakże, cierpi on na problem rzadkości, co oznacza, że do osiągnięcia akceptowalnej wydajności potrzebna jest znaczna ilość danych. Z drugiej strony, MEM jest w stanie utrzymać rozsądną wydajność nawet przy niewielkiej ilości danych dostępnych do celów treningowych. Idea polega zatem na przejściu korpusu testowego za pomocą MEM w celu wygenerowania tymczasowego wyniku tagowania, a jednocześnie na wykorzystaniu tej procedury jako procesu treningowego dla HMM. Podczas drugiego przejścia korpus wykorzystuje HMM do ostatecznego tagowania. W tym procesie tymczasowy wynik tagowania wygenerowany przez MEM będzie wykorzystywany jako punkt odniesienia do późniejszego sprawdzania i korygowania błędów. W przypadku gdy dostępnych jest niewiele danych szkoleniowych, wynik końcowy może być nadal wiarygodny w oparciu o wkład początkowego wyniku znakowania MEM.

KONTEKST

Konferencja "Message Understanding Conference". W 1987 roku Centrum Systemów Oceanicznych Marynarki Wojennej (NOSC), obecnie znane jako Centrum Dowództwa, Kontroli i Nadzoru Oceanicznego Marynarki Wojennej, zainicjowało pierwszą Konferencję "Message Understanding Conference" (MUC). W dalszej kolejności zorganizowano serię konferencji MUC, których celem było promowanie i ocena badań nad IE. Oceny uzyskane w ramach tych konferencji MUC doprowadziły program badawczy w dziedzinie IE do jego obecnego stanu. W 1995 roku określono cele i zadania dla MUC-6,aby uczynić system IE bardziej praktycznym i osiągnąć automatyczne działanie z wysoką dokładnością. Następnie opracowano "Named Entity", aby ułatwić identyfikację nazw osób, organizacji i lokalizacji geograficznych w tekście. Od tego czasu zadania NER stały się centralnym tematem konferencji MUC . Zgodnie ze specyfikacjami zdefiniowanymi przez MUC, zadania NER zazwyczaj działają na siedmiu typach nazwanych encji, wymienionych poniżej wraz z ich odpowiednimi znacznikami:

•  OSOBA (ENAMEX)
•  ORGANIZACJA (ENAMEX)
•  LOKALIZACJA (ENAMEX)
•  DATA (TIMEX)
• o CZAS (TIMEX)
•  PIENIĄDZE (NUMEX)
•  PROCENT (NUMEX)

Z powyższej listy, trzy podzadania są wyprowadzane z tych siedmiu typów nazwanych encji i przypisywane do trzech odpowiednich elementów tagu SGML, mianowicie ENAMEX, TIMEX i NUMEX. Ponieważ TIMEX i NUMEX są dość łatwe do przewidzenia za pomocą niektórych skutecznych metod skończonych stanów , większość obecnych badań dotyczy wyłącznie ENAMEX, które są wysoce zmienne i niejednoznaczne.



Od czasu MUC-6 i MUC-7 zaproponowano wiele systemów NER, które okazały się skuteczne w docelowych domenach. Ogólnie rzecz biorąc, systemy NER wykorzystujące ręcznie tworzone reguły nadal przodują, osiągając najwyższy wynik miary F, sięgający 96,4% w MUC-6, w porównaniu z podejściami statystycznymi, które osiągnęły 94,9% . W podejściu opartym na regułach, zestaw reguł lub wzorców jest definiowany w celu identyfikacji nazwanych bytów w tekście. Reguły te lub wzorce składają się z charakterystycznego formatu słów, takiego jak kapitalizacja lub konkretny przyimek przed nazwanym bytem. Na przykład, ciąg pisany wielką literą za tytułami, takimi jak "Pan", "Dr" itp., zostanie zidentyfikowany jako imię i nazwisko osoby, podczas gdy słowo pisane wielką literą po przyimku, takim jak "w", "w", "w pobliżu" itp., najprawdopodobniej będzie lokalizacją. Dzięki wdrożeniu skończonego zestawu starannie zdefiniowanych reguł dopasowywania wzorców, nazwane encje w tekście mogły być systematycznie wyszukiwane.Wykonano wiele prac z wykorzystaniem podejścia opartego na regułach. Jednym z dobrze udokumentowanych systemów, które podążały za tym podejściem, był system LaSIE, opisany przez Wakao (1996). Innym znanym przykładem systemu opartego na regułach jest system ekstrakcji tekstu NetOwl firmy IsoQuest, zaprezentowany przez Krupkę i Hausmana (1998). Tymczasem Diana Maynard i inni (2001) również zbudowali system NER oparty na ręcznie opracowanych regułach, który jest w stanie osiągnąć średnio 93% precyzji i 95% wykrywalności dla różnych typów tekstu. Podejście statystyczne, z drugiej strony, działa poprzez wykorzystanie modelu probabilistycznego zawierającego cechy danych podobne do podejścia opartego na regułach. Cechy danych, które można rozumieć jako zbiór reguł dla modelu probabilistycznego, powstają poprzez uczenie się powstałych korpusów z poprawnie oznaczonymi nazwanymi encjami. Model probabilistyczny wykorzystuje następnie te cechy do obliczenia i identyfikacji najbardziej prawdopodobnych nazwanych encji. W związku z tym, jeśli adnotowane cechy danych są rzeczywiście wiarygodne, model będzie miał wysokie prawdopodobieństwo znalezienia prawie wszystkich nazwanych encji w tekście. W ostatniej dekadzie wiele prac w NER zostało wykonanych z wykorzystaniem podejścia statystycznego opartego na bardzo dużych korpusach. MEM, jeden z najpopularniejszych modeli statystycznych, był często stosowany w różnych zadaniach NER. Jednym z istotnych opracowań na temat MEM jest system MENE opisany przez Borthwicka (1998). W ich systemie wykorzystali cztery główne cechy do identyfikacji nazwanych encji, które określili jako cechy binarne, cechy leksykalne, cechy sekcji i cechy słownikowe. Cechy binarne w systemie MENE zasadniczo dotyczą kapitalizacji w tekście. Tymczasem cechy leksykalne dotyczą terminów leksykalnych, takich jak lista słów i ich typy, które są używane z gramatyką. Cechy sekcji wskazują bieżącą sekcję tekstu, podczas gdy cechy słownika wykorzystują szeroką gamę słowników pojedynczych lub wielu terminów, takich jak imiona, nazwy organizacji, sufiksy korporacyjne itp. Cechy słownika są podobne do gazeterów używanych w systemach opartych na regułach, z tym wyjątkiem, że słowniki w systemie MENE nie wymagają dużego nakładu pracy w zakresie konserwacji. Niemniej jednak, użycie samego systemu MENE na danych testowych MUC-7, jak opisali Borthwick i inni (1998), pozwoliło uzyskać jedynie wskaźnik F na poziomie 84,22%. Aby system MENE działał lepiej, Borthwick i in. połączyli MENE z innymi podejściami opartymi na regułach, aby uzyskać lepsze rezultaty. Oprócz Borthwick i in., Bender i in. (2003) również opisali system NER, który osiągnął wskaźnik F na poziomie 89,58% dzięki zastosowaniu MEM. Dysponując korpusem adnotowanym i zestawem funkcji, zbudowali oni najpierw bazowy rozpoznawacz nazwanych encji, który następnie został użyty do wyodrębnienia nazwanych encji i ich informacji kontekstowych z danych nieadnotowanych. Dokładność ich systemu została dodatkowo poprawiona dzięki ostatecznemu rozpoznawaczowi, który wykorzystywał wytrenowane dane. Inny system oparty na MEM można znaleźć w pracach Chieu i Ng (2002). Zaprezentowali oni system o nazwie MEN-ERGI, który wykorzystywał informacje globalne z tylko jednym klasyfikatorem i wykazali, że ich system był w stanie osiągnąć wydajność porównywalną z najlepszymi systemami opartymi na uczeniu maszynowym w MUC-6 i MUC-7. Oprócz MEM, HMM to kolejny dobrze znany model statystyczny, który był często używany w różnych systemach NER. IdentiFinder zgłoszony przez Bikela (1999) wykorzystujący zmodyfikowany HMM był najlepszy w oficjalnych danych testowych MUC-6 i MUC-7 spośród wszystkich systemów opartych na uczeniu maszynowym. IdentiFinder wykorzystywał podobne funkcje jak system MENE i opierał się na statystykach, aby podejmować decyzje dotyczące identyfikacji nazwanych obiektów. Różni się tym, że posiada kompletny model probabilistyczny, który rządzi wszystkimi decyzjami dotyczącymi klasyfikacji nazwanych obiektów i modeluje kategorie interesujące i pozostałe dane wejściowe, które nie są interesujące.Zmodyfikowany model HMM używany przez IdentiFinder został następnie zaadaptowany przez Zhou i Su (2002). W swojej pracy byli oni w stanie znacząco zwiększyć wydajność swojego systemu NER, wprowadzając cztery podcechy z modelowaniem back-off. Wykorzystując dane testowe z MUC-6 i MUC-7, ich system osiągnął wyniki miary F wynoszące odpowiednio 96,6% i 94,1%. Wiele wcześniejszych prac przeprowadzono z wykorzystaniem modeli statystycznych innych niż MEM i HMM. Istnieje również wiele systemów NER, które wykorzystują podejście hybrydowe, łącząc modele statystyczne z niektórymi technikami uczenia się opartymi na regułach. Jeden bardzo udany przykład można znaleźć w pracy Mikheeva i in. (1999), w której wykorzystali oni znaczne, ręcznie opracowane reguły wraz z MEM do częściowego dopasowania. Obserwacja poprzednich podejść pokazuje jednak, że żaden system nigdy nie próbował używać MEM i HMM kolejno.

PODEJŚCIE HYBRYDOWE

Jak wspomniano wcześniej, system NER przedstawiony w tym artykule wykorzystuje kolejno dwa modele statystyczne - MEM i HMM. MEM opiera się na systemie MENE opisanym przez Borthwicka i (1998), natomiast HMM na systemie IdentiFinder opisanym przez Bikela (1999). System został zbudowany w Javie z wykorzystaniem istniejącej implementacji z repozytorium JavaNLP. Do celów szkoleniowych i eksperymentalnych jako korpus testowy wybrano Brytyjski Korpus Narodowy (BNC), który zawiera teksty zróżnicowane pod względem dziedziny, stylu i gatunku. Ma to na celu zapewnienie niezależności proponowanego systemu NER od dziedziny i możliwości odpowiedniego radzenia sobie z różnymi typami tekstów.

Maksymalna entropia

Zgodnie z wytycznymi MUC-6 i MUC-7 dotyczącymi definicji zadania NER, każde słowo z korpusu jest tokenizowane i przypisywane do pożądanej kategorii nazwanego bytu ze znacznikiem "osoba" (), "organizacja" () lub "lokalizacja" (). MEMjest najpierw używane do oszacowania prawdopodobieństwa, że dane słowo zostanie przypisane do jednej z trzech wymienionych kategorii, na podstawie zestawu cech i danych treningowych. Dwa specjalne warunki są brane pod uwagę, gdy słowo znajduje się na początku () i na końcu () zdania. W przypadku, gdy dane słowo nie należy do żadnej z pożądanych kategorii, zostanie umieszczony pusty znacznik (< >), aby wskazać, że słowo nie należy do żadnej z pożądanych kategorii. W celu znalezienia nazwanych encji, proces estymacji maksymalnej entropii wykorzystuje model opisany poniżej do obliczenia prawdopodobieństwa warunkowego P dla wszystkich tagów t na podstawie historii h, w której każda cecha fi jest powiązana z parametrem ważenia α_i:



Należy zauważyć, że historia h, o której mowa w modelu, odnosi się do wszystkich danych warunkowych, które umożliwiają systemowi podjęcie decyzji w procesie tagowania. Obejmuje ona wszystkie informacje możliwe do uzyskania z korpusu w odniesieniu do tokena, którego tag system próbuje określić, niezależnie od tego, czy jest to samo słowo, czy cechy. Następnie obliczany jest iloczyn wag dla wszystkich cech aktywnych na h, który ostatecznie dzielony jest przez funkcję normalizacyjną Z_α(h).

Ukryty model Markowa

Po przejściu przez MEM, wszystkie otagowane nazwane encje w korpusie testowym są wykorzystywane jako dane treningowe dla HMM w celu przeprowadzenia ostatecznego tagowania. Ponieważ po analizie korpusu za pomocą MEM trening będzie wystarczający, system nie musi korzystać z modeli back-off, takich jak te stosowane przez Bikela (1999) oraz Zhou i Su (2002). W tym systemie model HMM służy głównie do sprawdzania globalnego kontekstu, czyli do sprawdzania wystąpień tej samej nazwanej jednostki w różnych sekcjach tego samego dokumentu tekstowego. Sprawdzanie kontekstu całego dokumentu jest ważne, ponieważ zapewnia spójność oznaczonych nazwanych jednostek i rozwiązuje niektóre niejednoznaczne przypadki. Na przykład nazwa organizacji jest często skracana, zwłaszcza gdy została już gdzieś wspomniana w dokumencie. Sprawdzając informacje globalne, można zidentyfikować skrót jako organizację. Poza tym istnieją również pewne jednostki, które są wysoce niejednoznaczne, a ich kategorii nie można określić bez uwzględnienia kontekstu globalnego. Fraza "Honda City" w zdaniach takich jak "Honda City jest ładne" lub "Promocja dla Honda City" może łatwo zostać błędnie zinterpretowana jako lokalizacja na podstawie lokalnych danych kontekstowych,chyba że istnieje inne zdanie, które brzmi jak "Jadę Honda City". Podobnie jak wcześniej używany model MEM, model HMM służy do obliczania prawdopodobieństwa wystąpienia słów w danej kategorii nazwanych jednostek. Każde tokenizowane słowo jest teraz traktowane jako uporządkowane w pary. Za pomocą łańcucha Markowa prawdopodobieństwo słów jest obliczane po prostu na podstawie poprzedniego słowa. Aby sklasyfikować nazwane byty, system znajduje najbardziej prawdopodobny tag t dla danej sekwencji słów w, który maksymalizuje P(t|w). Wystąpienia danych zdarzeń są zliczane w całym tekście na podstawie poniższego obliczenia:



Na koniec klasyfikator koryguje błędy w wynikach uzyskanych z MEM, aby przeprowadzić końcowy proces tagowania za pomocą HMM.

Wyniki eksperymentalne.

Proponowany system został przetestowany z artykułami BNC opartymi na szerokim zakresie dziedzin z różnych dziedzin. Dzięki kolejnemu wykorzystaniu MEM i HMM jest on w stanie utrzymać pożądaną wydajność niezależnie od rozmiaru danych treningowych. Ogólnie rzecz biorąc, system konsekwentnie osiągał wyniki miary F powyżej 95% dla większości powszechnie używanych dziedzin.

PRZYSZŁE TRENDY

Chociaż wstępne wyniki podejścia hybrydowego są dość pozytywne, proponowany system jest wciąż dość niedojrzały. Konieczne jest włożenie wielu prac, aby poprawić wydajność System będzie bardziej niezawodny. Na przykład, interesujące będzie obserwowanie, jak można włączyć bardziej zaawansowane funkcje, aby poprawić wydajność systemu. Interesujące będzie również to, jak system można trenować na korpusach w językach obcych. Przewiduje się, że w przyszłości proponowane podejście może okazać się cenne w różnych aplikacjach języka naturalnego. Jednym z bezpośrednich wkładów będzie automatyzacja żmudnego zadania budowania ontologii. Jednocześnie, proponowane systemy automatycznego podsumowania tekstu mogą również zostać wzbogacone o proponowany system, ponieważ nazwane encje są w stanie dostarczyć wskazówek do identyfikacji odpowiednich segmentów w tekście. Wreszcie, oczekuje się, że proponowane podejście pomoże również w budowaniu dokładniejszych wyszukiwarek internetowych.

WNIOSKI

W niniejszym artykule przedstawiono hybrydowe podejście uczenia maszynowego, wykorzystujące kolejno MEM i HMM. Dzięki wstępnemu trenowaniu danych za pomocą MEM i odpowiedniemu klasyfikatorowi do korekcji błędów w końcowym procesie rozpoznawania za pomocą HMM, wydajność proponowanego systemu NER może zostać znacznie zwiększona w porównaniu z wykorzystaniem tylko jednego modelu statystycznego. Co więcej, system jest w stanie dostosować się do różnych domen bez ingerencji człowieka i utrzymuje pożądaną wydajność niezależnie od rozmiaru korpusu treningowego.