Akademia Górniczo-Hutnicza

Im. Stanisława Staszica w Krakowie

Wydział Elektrotechniki, Automatyki,

Informatyki i Elektroniki

Katedra Automatyki

Praca dyplomowa

ROZPOZNAWANIE OBRAZÓW

PRZY UŻYCIU

SYMULATORA SIECI HOPFIELDA

Promotor	:	dr inż. Joanna Grabska - Chrząstowska
Autor	:	Mateusz Macnar
Kierunek	:	Informatyka

KRAKÓW, 2002 R.

SPIS TREŚCI

• Wstęp

Mózg ludzki jest bardzo wydajną i elastyczną „maszyną liczącą”. Obecnie, w dobie gwałtownego rozwoju sztucznej inteligencji, próbuje się odkrywać i naśladować jego budowę, właściwości i zasady działania. Powstają systemy wykorzystujące zjawiska, które zaobserwowano w trakcie wieloletnich badań medycznych, bliżej opisane w pracy [18]. Oczywiście nie ma sensu stosowanie tego typu sztucznych sieci neuronowych do rozwiązywania problemów, z którymi tradycyjne komputery radzą sobie doskonale, czyli rozwiązywanych przy zadanych ograniczeniach pamięciowych i czasowych - w czasie wielomianowo zależnym od rozmiaru problemu. Tam, gdzie potrzebna jest jedynie szybkość i dokładność obliczeń, komputery są i prawdopodobnie będą niezastąpione. Niestety, na co dzień spotykamy się z problemami, dla których nie istnieją wielomianowe algorytmy (zostało to przedstawione w pracy [11]). Można wręcz zaryzykować stwierdzenie, że takie właśnie zadania dominują w otoczeniu człowieka, a te o złożoności wielomianowej to jedynie ich uproszczenia. Już kilkuletnie dziecko z powodzeniem stawia czoła wyzwaniom, wobec których komputery są bezradne. Przede wszystkim brakuje im umiejętności uczenia się, gromadzenia wiedzy i doświadczenia, tak chętnie wykorzystywanej przez naturę. Nie potrafią one reagować na sytuacje, z którymi wcześniej się nie spotkały. Oznacza to, że jeżeli programista nie uwzględnił w kodzie programu ich wystąpienia, to program w ich obliczu zachowa się, w zależności od jego konstrukcji, w sposób nieprzewidywalny (błędne działanie, zawieszenie się) lub poinformuje o błędzie. Współczesny komputer nie może jeszcze analizować zaistniałych okoliczności i odwoływać się do wcześniejszych doświadczeń w celu podjęcia decyzji, czyli działać intuicyjnie. Rozważmy następujący przykład: człowiek bierze do ręki pewien przedmiot, podrzuca i ponownie chwyta. Program komputerowy musiałby znać dokładną masę przedmiotu, siłę, z którą został wyrzucony, obliczyć jego tor uwzględniając opór powietrza, bardzo szybko znaleźć położenie i dokładnie w momencie, kiedy wyrzucony przedmiot znalazłby się w odpowiednim punkcie toru, podjąć decyzję o jego przechwyceniu. Byłby to dosyć skomplikowany sposób na wykonanie tej czynności. Nadzieją na efektywne rozwiązywanie takich i o wiele poważniejszych zadań są sztuczne sieci neuronowe. Nie liczą one prędkości w ruchu jednostajnie opóźnionym według skomplikowanych wzorów, po prostu uczą się poprzez wieloetapowe dostosowywanie się do rozwiązywania danego problemu (proces ten opisano w pracach [9], [10]). Ponadto potrafią rozpoznawać i kojarzyć obiekty. Cechy te sprawiają, że sztuczne sieci neuronowe w bardzo szybkim tempie zdobywają nowe, szerokie obszary zastosowań we wszystkich dziedzinach nauki i techniki.

Celem niniejszej pracy było zbadanie działania sieci Hopfielda zastosowanych do rozpoznawania obrazów za pomocą programowego symulatora opartego na synchronicznym modelu dyskretnym Hopfielda. Zamodelowane sieci zostały użyte do rozpoznawania czarno-białych rastrowych obrazów liter i cyfr oraz ręcznie pisanych znaków. Większy nacisk położono na dobór parametrów i metod uczenia, a także graficzną prezentację wyników rozpoznawania możliwą do oceny wizualnej przez użytkownika, natomiast mniejszy na sposób wprowadzania obrazów uczących i testujących. Mogą one być tworzone automatycznie według specyfikacji tekstowej, np. „0-9A-Z” lub wprowadzane ręcznie przez użytkownika za pomocą urządzenia wskazującego.

W rozdziale drugim przedstawiono teorię sztucznych sieci neuronowych. Opisano historię badań nad sieciami neuronowymi, podstawowy podział na sieci liniowe i nieliniowe oraz dalszą klasyfikację sieci. Podano także podstawowe metody ich uczenia oraz obszary zastosowań. W rozdziale trzecim skupiono się na badanym w tej pracy rodzaju sieci, czyli sieciach Hopfielda. Opisano ich budowę, związane z nią wady i zalety oraz wynikające z tych cech główne zastosowania. Rozdział czwarty przedstawia symulator programowy Snhop sieci Hopfielda zbudowany na potrzeby tej pracy. Zawiera opis środowiska działania, funkcji programu, interfejsu użytkownika oraz sposobu realizacji typowych zadań. W rozdziale piątym przedstawiono badania sieci Hopfielda przeprowadzone za pomocą symulatora. Badania te objęły cztery metody uczenia sieci, dwie historycznie pierwsze związane z pracami Hebba oraz dwie dalsze będące nieco nowszym spojrzeniem na problem uczenia sieci neuronowych. Rozdział ten zawiera także spostrzeżenia i wnioski uzyskane w czasie przeprowadzania badań. Syntezę informacji zebranych podczas realizowania niniejszej pracy oraz propozycje rozwinięcia symulatora Snhop umieszczono w rozdziale szóstym.

• Sieci neuronowe

1. Rys historyczny

Badania nad sztucznymi sieciami neuronowymi datuje się od lat 40-tych XX wieku. Początkowo była to wąska dziedzina wiedzy, leżąca jedynie w zakresie zainteresowań biologów, której powstanie zostało zainicjowane poprzez badanie komórek ośrodkowego układu nerwowego zwierząt i człowieka, czyli neuronów. Pierwsze próby wyjaśnienia i matematycznego opisu działania błony komórkowej i całego neuronu podjął McCulloh w roku 1943, a pod koniec lat 50-tych i na początku lat 60-tych powstały pierwsze modele pojedynczych neuronów. Niewątpliwie olbrzymim krokiem naprzód był Perceptron Rosenblatta i Wightmana zbudowany w roku 1957 w Cornell Aeronautical Laboratory, który został zastosowany do rozpoznawania znaków alfanumerycznych. Później powstały pierwsze sieci neuronowe oferowane komercyjnie (neurokomputery, za pracą [18]), m.in. Madaline Widrowa w roku 1960. Niefortunnie dla tej nowej, szybko rozwijającej się dziedziny wiedzy, jaką jest technika sieci neuronowych, na przełomie lat 60-tych i 70-tych nastąpiło zahamowanie badań po publikacji książki Minsky'ego i Paperta (1969) wykazującej m.in. poważną ograniczoność pola zastosowań liniowych sieci neuronowych jako zdolnych jedynie do realizacji funkcji liniowych. Aż do początku lat 80-tych sieciami zajmowało się w świecie zaledwie kilka ośrodków (Grossberg, Hinton, Hopfield, PDP Research Group). Rozwój i większa dostępność komputerowych technik symulacji w latach 80-tych przyczyniły się do stopniowej intensyfikacji badań, a w drugiej połowie lat 80-tych nastąpił prawdziwy renesans badań nad sztucznymi sieciami neuronowymi. Powstała wtedy fala nowych koncepcji, architektur i algorytmów uczenia, wzrosło zainteresowanie ze strony specjalistów zajmujących się sztuczną inteligencją (Newell, Simon) wynikające z kryzysu nękającego tradycyjne, symboliczne techniki rozwijane w tej dziedzinie od lat 60-tych. Należy tutaj wspomnieć ważną pracę Rumelharta, McClellanda i PDP Research Group „Parallel Distributed Processing. Explorations in the Microstructure of Cognition" (1986). Nastąpiła wówczas popularyzacja algorytmu wstecznej propagacji błędów (ang. Backpropagation, przedstawionego w pracy [18]), który przełamał impas w konstrukcji sieci wielowarstwowych. Na lata 90-te datuje się dalszy wzrost popularności sieci neuronowych, nowe badania w tej dziedzinie przyniosły szybsze algorytmy uczenia, podejścia hybrydowe (zastosowania logiki rozmytej, algorytmów genetycznych itp.), rozwój sektora zastosowań w medycynie, przemyśle i innych dziedzinach oraz coraz większą ilość przystępnych cenowo realizacji sprzętowych. Ujawniły one zalety „prawdziwych” (równoległych) sieci neuronowych, w odróżnieniu od wszelkiego rodzaju symulatorów działania sieci neuronowych realizowanych na maszynach sekwencyjnych.

2. Modele neuronu

Pod pojęciem sieci neuronowej będziemy rozumieć sztuczną sieć neuronową do przetwarzania informacji, będącą bardzo uproszczonym modelem niektórych obszarów ludzkiego mózgu (według prac [18], [20]), składającą się z wielu komórek nerwowych zwanych neuronami. Stosowane w sztucznych sieciach neuronowych modele neuronów są w odniesieniu do swych pierwowzorów chemiczno-elektrycznych bardzo uproszczonymi odpowiednikami matematycznymi. Neurony są ze sobą powiązane za pomocą połączeń sparametryzowanych wagami modyfikowanymi w procesie uczenia sieci neuronowej. Na podstawie zasady działania rzeczywistego neuronu stworzono wiele modeli matematycznych, w których uwzględnione zostały w większym lub mniejszym stopniu własności rzeczywistej komórki nerwowej. Większość tych modeli bliska jest modelowi McCullocha-Pittsa, zawierającemu sumator dokonujący sumowania ważonego sygnałów wejściowych neuronu oraz blok wytwarzający sygnał wyjściowy, będący w ogólności dowolną funkcją sygnału uzyskiwanego z sumatora. Historycznie jako pierwsze zostały zbadane i zastosowane neurony liniowe, a późniejsze neurony nieliniowe są ich modyfikacjami i rozszerzeniami.

1. Neuron liniowy

Model liniowy neuronu o M wejściach posiada wiele wejść x₀,x₁,...,x_M odpowiadających dendrytom i jedno wyjście y odpowiadające aksonowi neuronu biologicznego (Rys.1), opisanego w pracach [4], [17]. Chemiczno-elektryczne synapsy są modelowane za pomocą współczynników wagowych w₀,w_1,...,w_M połączeń pomiędzy neuronami.




Rysunek 1: Model liniowy neuronu.

Zazwyczaj zakłada się, że zarówno sygnały wejściowe jak i sygnał wyjściowy mogą przyjmować wartości z pewnego ograniczonego przedziału, np.


,


.

Zależność pomiędzy sygnałami wejściowymi a sygnałem wyjściowym decyduje o istocie działania neuronu. W ogólnym przypadku ma ona postać


,

przy czym g to tzw. funkcja aktywacji neuronu (szerzej opisana w pracy [18]). Ważona suma sygnałów wejściowych nazywana jest potencjałem wewnętrznym neuronu p (szerzej opisany w pracy [17])


.

W przypadku neuronów liniowych funkcja aktywacji redukuje się do funkcji tożsamościowej


.

2. Perceptron

Perceptron jest modelem McCullocha-Pittsa o odpowiednio przyjętej strategii uczenia. Nieliniowa funkcja aktywacji perceptronu jest funkcją nieciągłą typu dyskryminującego, w związku z tym sygnał wyjściowy określony jest zależnością


.

Często wprowadza się dodatkowy sygnał wejściowy x₀ zawsze równy 1 i wtedy waga w₀ reprezentuje tzw. BIAS, czyli próg zadziałania neuronu, który może być różny od 0.

3. Neuron sigmoidalny

W przypadku neuronu sigmoidalnego, opisanego w pracy [14], mamy do czynienia z modelem podobnym do perceptronu, różniącym się jednak funkcją aktywacji, która jest ciągła i przyjmuje postać funkcji unipolarnej lub bipolarnej. Zazwyczaj stosuje się w wersji unipolarnej funkcję sigmodalną


,

oraz w wersji bipolarnej tangens hiperboliczny


.

4. Neuron stochastyczny

W odróżnieniu od wszystkich modeli deterministycznych, w modelu stochastycznym, przedstawionym w pracy [11], stan wyjściowy neuronu zależy nie tylko od sumy ważonej sygnałów wejściowych, ale także od pewnej zmiennej losowej R∈(0,1). W modelu stochastycznym neuronu sygnał wyjściowy y przyjmuje wartość 1 z prawdopodobieństwem


,

a wartość -1 z prawdopodobieństwem


,

gdzie: β - wartość stała, dodatnia, najczęściej równa 1,

e - podstawa logarytmu naturalnego.

Proces obliczania sygnału wyjściowego w neuronie stochastycznym przebiega w następujących etapach:

1. obliczenie sumy ważonej sygnałów wejściowych p jak w neuronie liniowym,

2. obliczenie prawdopodobieństwa P(g(p)=1), że y przyjmie wartość 1,

3. wygenerowanie zmiennej losowej R∈(0,1),

4. przyjęcie y=1, jeżeli R<P(g(p)=1) lub y=-1 w przeciwnym przypadku.

1. Klasyfikacja sieci neuronowych

Sieci neuronowe można sklasyfikować ze względu na kilka kryteriów (przedstawionych szczegółowo w pracach [11], [17]):

• model neuronu (sieci liniowe i nieliniowe),

• sposób uczenia (sieci nadzorowane i nie nadzorowane),

• topologię połączeń (sieci jednokierunkowe i rekurencyjne),

• sposób propagacji pobudzenia (sieci synchroniczne i asynchroniczne).

1. Sieci liniowe i nieliniowe

Sieci neuronowe ze względu na wykorzystany do ich budowy model neuronu dzielimy na:

• liniowe (ang. linear),

• nieliniowe (ang. nonlinear).

W przypadku sieci liniowych można przyjąć funkcję aktywacji neuronu jako funkcję tożsamościową g(p) = p. W takich sieciach każda struktura wielowarstwowa może być zastąpiona przez odpowiednią sieć jednowarstwową, dlatego też nie buduje się wielowarstwowych sieci liniowych.

W przypadku sieci nieliniowych jako funkcję aktywacji neuronu stosuje się wiele rodzajów funkcji, np. perceptronową, sigmoidalną, tangens hiperboliczny, sinus, różne rodzaje funkcji signum. W praktyce liczba warstw sieci nieliniowych nie przekracza trzech, która to wartość teoretycznie wystarcza do zamodelowania dowolnej funkcji za pomocą sieci nieliniowej (dowód znajduje się w pracy [18]). Poprzez zastosowanie funkcji aktywacji typu signum sieć przechodzi od modelu ciągłego do modelu dyskretnego.

1. Sieci nadzorowane i nie nadzorowane

Sieci neuronowe ze względu na strategię przyjętą podczas procesu uczenia sieci dzielimy na:

• nadzorowane (ang. supervised learning),

• nie nadzorowane (ang. unsupervised learning).

Sieci nadzorowane są nazywane także sieciami uczonymi z nauczycielem. W ich przypadku właściwa odpowiedź sieci (oczekiwane prawidłowe sygnały wyjściowe) jest znana i podana sieci podczas procesu uczenia. Sieć nadzorowana zmieniając poszczególne wagi połączeń pomiędzy neuronami stara się otrzymać wynik jak najbardziej zbliżony do zadanego. Po zakończeniu procesu uczenia sieć poddawana jest testom, podczas których nie posiada już dostępu do informacji o prawidłowych odpowiedziach, a samodzielnie wygenerowane przez nią rozwiązanie jest podstawą do oceny skuteczności procesu uczenia.

Sieci nie nadzorowane są nazywane także sieciami uczonymi bez nauczyciela. W przypadku tego rodzaju uczenia sieci nie jest podawane prawidłowe rozwiązanie. Nie nadzorowana sieć neuronowa tworzy wartości wag korzystając z zauważonych korelacji pomiędzy sygnałami wejściowymi lub z mechanizmu konkurencji neuronów.

1. Sieci jednokierunkowe i rekurencyjne

Sieci neuronowe ze względu na topologię połączeń pomiędzy neuronami (zawieranie bądź nie pętli) dzielimy na:

• jednokierunkowe (ang. feedforward),

• rekurencyjne (ang. feedback, bidirectional)

W sieciach jednokierunkowych połączenia pomiędzy poszczególnymi neuronami nie tworzą pętli, dzięki czemu sieci takie bardzo szybko reagują na impulsy wejściowe. Sygnał jest propagowany jedynie w kierunku od wejścia do wyjścia sieci. Uczenie takich sieci odbywa się zazwyczaj z wykorzystaniem algorytmu wstecznej propagacji błędów (backpropagation).

W sieciach rekurencyjnych istnieją pętle w połączeniach pomiędzy neuronami tworzące sprzężenia zwrotne. Sygnał podawany na wejście jest przetwarzany w sieci wielokrotnie, zanim ustalą się stabilne wartości wyjściowe. Sieci takie są trudniejsze do uczenia niż jednokierunkowe i działają wolniej, a w ich analizie nie można pominąć dynamicznych stanów przejściowych stanowiących w tym przypadku istotę działania.

1. Sieci synchroniczne i asynchroniczne

Sieci neuronowe ze względu na sposób propagacji pobudzenia neuronów (kolejność aktualizacji sygnałów wyjściowych) dzielimy na:

• synchroniczne (ang. synchronous),

• asynchroniczne (ang. asynchronous).

W modelowaniu sieci synchronicznych bieżący stan sieci jest „zamrażany" i na jego podstawie dla każdego neuronu oblicza się nową wartość sygnału wyjściowego; następnie wielkości te aktualizuje się dla całej sieci w jednym kroku, jednocześnie dla wszystkich neuronów sieci. W takich sieciach mamy do czynienia z sytuacją, w której wszystkie neurony obliczają swój stan w tych samych momentach czasowych wyznaczanych przez centralny zegar. Jest to rodzaj sieci wykorzystujący dyskretyzację zarówno stanów wyjściowych neuronów jak i czasu.

W sieciach asynchronicznych w każdym kolejnym kroku przetwarzania jeden wybrany neuron oblicza nową wartość swojej odpowiedzi. Stosuje się różne metody wyboru tego neuronu spośród wszystkich neuronów, którego stan poddawany jest aktualizacji.

1. Proces uczenia sieci neuronowych

Użycie sieci neuronowej wykazuje zasadniczą odmienność od algorytmicznego podejścia do rozwiązywania problemów. Sieć neuronowa podlega procesowi uczenia, podczas którego ustalane są wagi połączeń pomiędzy neuronami tak, aby w fazie testowania odpowiedź sieci na zadane sygnały wejściowe była właściwa. Proces uczenia może być przeprowadzany nawet przy nieznajomości dokładnych zależności pomiędzy sygnałami wejściowymi i wyjściowymi, przy wykorzystaniu jedynie próbek, przykładów takich powiązanych danych (wyczerpujący opis procesu uczenia sieci znajduje się w pracach [1], [9]). Często wykorzystywany jest sposób uczenia bez nauczyciela, który polega na prezentowaniu sieci próbek danych wejściowych bez potrzeby znajomości prawidłowych sygnałów wyjściowych. Tak uczona sieć może samodzielnie wyekstrahować klasy prezentowanych jej obiektów wejściowych. Cechy funkcji aktywacji neuronu, szczególnie jej ciągłość, mają decydujący wpływ na wybór techniki uczenia. Drugim bardzo istotnym czynnikiem jest wybór strategii uczenia spomiędzy uczenia z nauczycielem lub uczenia bez nauczyciela. Pierwsza z nich szybciej prowadzi do osiągnięcia zadowalających rezultatów i nie wymaga konstruowania nadmiarowej sieci neuronowej. Jeśli jednak nie można zapewnić warunków dla uczenia z nauczycielem, pozostaje wybór strategii uczenia bez nauczyciela. Stosuje się wtedy dwa różne podejścia do problemu. Jedno z nich polega na wykorzystaniu konkurencji neuronów między sobą - strategia WTA (ang. Winner Takes All) i poddawania uczeniu jedynie najbardziej aktywnych, „zwycięskich” neuronów, natomiast drugie na wykorzystaniu korelacji sygnałów uczących (Reguła Hebba) i wzmacnianiu połączeń pomiędzy jednocześnie pobudzanymi neuronami. Należy zwrócić uwagę na fakt, że w uczeniu bez nauczyciela na etapie adaptacji neuronu nie jesteśmy w stanie przewidzieć jego sygnału wyjściowego po zakończeniu procesu uczenia, w odróżnieniu od trybu z nauczycielem, kiedy wynik uczenia jest z góry przesądzony przez wybór próbek wejściowych i wyjściowych wartości uczących.

2. Zastosowania sieci neuronowych

Jakkolwiek dzisiaj już sieci neuronowe stanowią dziedzinę wiedzy całkowicie samodzielną, to w rozwiązaniach praktycznych istnieją zwykle jako część sterująca procesem lub część decyzyjna, przekazująca sygnał wykonawczy innym elementom systemu, niezwiązanym bezpośrednio z sieciami neuronowymi. Funkcje realizowane za pomocą sieci neuronowych można sklasyfikować w kilka podstawowych grup:

• rozpoznawanie i klasyfikacja wzorców,

• predykcja wartości funkcji,

• kompresja danych,

• identyfikacja i sterowanie,

• asocjacja.

W każdym z wyżej wymienionych zastosowań sieć neuronowa pełni funkcję uniwersalnego aproksymatora (według pracy [11]) funkcji wielu zmiennych, reprezentowanych przez sygnały wejściowe sieci. Fakt, że duża liczba zadań modelowania, identyfikacji i przetwarzania sygnałów da się sprowadzić do zagadnienia aproksymacyjnego ma decydujące znaczenie dla różnorodności zastosowań sieci neuronowych.

Przy rozpoznawaniu i klasyfikacji wzorców sieć uczy się podstawowych cech tych wzorców, np. takich jak odwzorowanie geometryczne, rozkład składników głównych, składników transformacji Fouriera lub innych właściwości. Podczas procesu uczenia wyodrębniane są różnice występujące pomiędzy poszczególnymi wzorcami, które stanowią podstawę podjęcia decyzji o przypisaniu wzorca do określonej klasy.

W dziedzinie predykcji wartości funkcji zadaniem sieci jest określenie spodziewanych odpowiedzi modelowanego systemu na podstawie znanego ciągu wartości, które już wystąpiły. Posiadając informacje o wartościach zmiennej x w chwilach poprzedzających predykcję


,

sieć podejmuje decyzję, jak będzie estymowana wartość badanego ciągu w chwili aktualnej t. W adaptacji wag sieci wykorzystuje się aktualny błąd predykcji oraz wartość tego błędu w chwilach poprzedzających.

W zagadnieniach identyfikacji i sterowania procesami dynamicznymi sieć neuronowa pełni zazwyczaj kilka funkcji. Przede wszystkim stanowi ona model nieliniowy procesu, pozwalający na wypracowanie odpowiedniego sygnału sterującego. Pełni również funkcję układu śledzącego i nadążnego, a więc systemu czasu rzeczywistego. Podczas podejmowania decyzji o dalszym przebiegu procesu sterowania ważną rolę odgrywa jej funkcja klasyfikująca wzorce.

W zadaniach asocjacji sieć neuronowa pełni rolę pamięci skojarzeniowej (ang. associative memory). Wyróżnia się tzw. pamięć autoasocjacyjną, w której działaniu skojarzenie dotyczy poszczególnych składowych tego samego wektora wejściowego oraz pamięć dwu- lub wielo- asocjacyjną, gdzie zadaniem sieci jest skojarzenie ze sobą dwu lub więcej wektorów informacji. Główną zaletą sieci neuronowych w tym zastosowaniu jest jej właściwość polegająca na tym, że jeżeli na wejście sieci podany będzie wektor odkształcony w dopuszczalnych granicach, np. zniekształcony szumem lub pozbawiony pewnych elementów informacji to sieć będzie w stanie odtworzyć wektor oryginalny w przypadku autoasocjacji lub właściwy wektor skojarzony z wejściowym w przypadku wielo- asocjacji.

Najważniejszymi cechami sieci neuronowych, decydującymi o zdobywaniu przez nie coraz to nowych obszarów zastosowań, są zdolność do pracy przy zniekształconych sygnałach wejściowych oraz bardzo szybkie, równoległe przetwarzanie informacji pozwalające na budowę systemów czasu rzeczywistego.

• Sieci Hopfielda

1. Geneza modelu

W roku 1982 J. J. Hopfield przedstawił model obliczeniowy sieci neuronowej nazwany później od jego nazwiska. Wywodził się on z modelu Insinga stosowanego w mechanice kwantowej, opisującego układy złożone z bardzo dużej liczby dwustanowych spinów, odpowiadających neuronom sieci Hopfielda. Energia układu spinów jest ściśle związana z energią sieci Hopfielda. Model wprowadzony przez Hopfielda zbudowany był z dużej liczby binarnych neuronów typu McCullocha-Pittsa i opierał się na koncepcji zbliżonej do modelu Littla zaproponowanego w roku 1974, który powstał na gruncie badań nad stabilną, długotrwałą pamięcią w układach biologicznych. Model Littla uwzględniał jedynie synchroniczny sposób zmiany stanu neuronów, natomiast model Hopfielda może funkcjonować zarówno w trybie synchronicznym jak i asynchronicznym. Hopfield nadał i rozwinął nową interpretację modelu Littla poprzez zaproponowanie efektywnego algorytmu konstruowania pamięci adresowanych zawartością, a nie lokalizacją fizyczną (autoasocjacja). Ponadto istotną nowością było zaproponowanie przez niego asynchronicznej i niezależnej aktualizacji stanu neuronów.

2. Budowa sieci Hopfielda

Sieci Hopfielda są sieciami rekurencyjnymi (ze sprzężeniem zwrotnym), co oznacza, że sygnały wyjściowe są podawane ponownie na wejście sieci aż do ustalenia się stanu stabilnego, jeśli to nastąpi. Neurony są połączone według zasady „każdy z każdym”, zatem nie ma sensu wyróżnianie warstw sieci. Stan stabilny oznacza zrównanie się potencjałów na wejściach i wyjściach wszystkich neuronów. W praktyce jako warunek zatrzymania przyjmuje się osiągnięcie przez sieć odpowiednio małej sumy modułów lub wartości maksymalnej, co do modułu, różnic pomiędzy odpowiednimi wejściami i wyjściami sieci neuronowej. Model dyskretny przedstawiony przez Hopfielda składa się z N neuronów n_i, i=1,2,...,N. Każdy z nich posiada potencjał wejściowy p_i (potencjał wewnętrzny), będący sumą sygnałów wejściowych pomnożonych przez odpowiednie wagi oraz potencjał wyjściowy y_i (potencjał zewnętrzny), będący nieliniową funkcją g potencjału wejściowego (Rys.2).





Rysunek 2: Model sieci Hopfielda.

W trybie synchronicznym w kroku czasowym t każdy neuron n_i, i=1,2,..,N oblicza swój potencjał p wewnętrzny zgodnie ze wzorem


,

oraz potencjał wyjściowy (sygnał wyjściowy neuronu) zgodnie ze wzorem


,

gdzie w_ij to waga połączenia wyjścia neuronu j z wejściem neuronu i. Aby zapewnić uzyskanie przez sieć stanu stabilnego, zakłada się symetrię połączeń pomiędzy neuronami (w_ij = w_ji, i,j=1,2,...,N) oraz brak sprzężeń w obrębie pojedynczego neuronu (w_ii=0, i=1,2,...,N). Wymuszenie zewnętrzne podane na wejście sieci x_i często przyjmuje się równe 0 we wszystkich poza pierwszym kolejnych krokach czasowych.

W trybie asynchronicznym aktualizacja stanów neuronów przebiega w sposób następujący: w chwili czasowej t wybierany jest neuron n_i, który oblicza swój nowy potencjał wejściowy, a następnie potencjał wyjściowy. Do często używanych metod wyboru aktywnego neuronu spośród N neuronów należą następujące dwa sposoby:

• w chwili t następuje losowanie indeksu neuronu i, i=1,2,...,N według rozkładu jednostajnego, niezależnie od wyników losowania w chwilach 1,...,t-1,

• w chwili t następuje wybór indeksu neuronu i według cyklicznie stosowanej permutacji zbioru indeksów I={1,2,...,N} wylosowanej na początku symulacji działania sieci.

W zależności od przyjętej funkcji aktywacji dla sieci możemy uzyskać model Hopfielda ściśle dyskretny (funkcja skoku jednostkowego) bądź dyskretno-ciągły (funkcja sigmoidalna).

1. Uczenie sieci Hopfielda

Istnieje wiele sposobów na ustalenie wartości wag wejść wszystkich neuronów sieci Hopfielda, czyli uczenie sieci. Można podzielić je ze względu na dwa kryteria:

• wykorzystanie bitów wektorów uczących (metody lokalne i nielokalne),

• kolejność prezentacji wektorów uczących (metody online i offline).

1. Metody lokalne i nielokalne

Metody uczenia sieci neuronowych Hopfielda ze względu na wykorzystanie bitów wektorów uczących dzielimy na:

• lokalne (ang. local),

• nielokalne (ang. nonlocal)

Lokalne metody uczenia sieci Hopfielda do ustalenia wagi w_ij potrzebują tylko bitów i oraz j z wektorów uczących. Należą do nich historycznie pierwsza Reguła Hebba, jej modyfikacja Metoda Wzajemnych Ograniczeń oraz Zmodyfikowana Reguła Perceptronu.

Nielokalne metody uczenia sieci Hopfielda do ustalenia wagi w_ij potrzebują dodatkowych informacji oprócz bitów i oraz j z wektorów uczących. Najczęściej zachodzi przypadek wykonywania przez metodę obliczeń na macierzy powstałej ze wszystkich bitów wszystkich wektorów uczących. Do metod tego rodzaju należą Reguła Rzutowania (Pseudoinwersji) oraz Reguła Rzutowania Delta.

1. Metody online i offline

Metody uczenia sieci neuronowych Hopfielda ze względu na kolejność prezentacji wektorów uczących dzielimy na:

• online (ang. online),

• offline (ang. offline).

Metody uczenia online posiadają możliwość konstruowania macierzy wag w trakcie jednokrotnego prezentowania kolejnych wektorów uczących bez potrzeby powracania do wektorów już użytych. Niektóre z metod uczenia sieci Hopfielda istnieją w wersjach zarówno online jak i offline (np. Reguła Hebba, Reguła Rzutowania).

Metody uczenia offline nie posiadają możliwości konstruowania macierzy wag w trakcie jednokrotnego prezentowania wektorów uczących. Podczas stosowania tych metod istnieje konieczność dostarczenia ponownie już raz użytych do obliczenia wag neuronów wektorów uczących. Są to zarówno metody, które potrzebują jednokrotnej informacji o wszystkich wektorach uczących jak i takie, które korzystają kolejno z pojedynczych wektorów, ale wymagają ich wielokrotnych prezentacji. Należą do nich nowsze metody uczenia, takie jak Reguła Wzajemnych Ograniczeń, Reguła Rzutowania Delta oraz Zmodyfikowana Reguła Perceptronu.

1. Wybrane metody uczenia

Do najczęściej używanych sposobów uczenia sieci Hopfielda możemy zaliczyć następujące metody (reguły obliczania wag):

1. Reguła Hebba (RH) - wersja offline

Dla neuronów bipolarnych wagi ustala się według wzoru


,

gdzie: w_ij - waga połączenia pomiędzy neuronami i oraz j,

x_i^m - i-ty bit m-tego wektora uczącego,

M - liczba wektorów uczących, m = 1,2,...,M,

N - liczba neuronów sieci, i,j = 1,2,...,N.

Dla neuronów unipolarnych wagi ustala się według wzoru


,

gdzie: w_ij - waga połączenia pomiędzy neuronami i oraz j,

x_i^m - i-ty bit m-tego wektora uczącego,

M - liczba wektorów uczących, m = 1,2,...,M,

N - liczba neuronów sieci, i,j = 1,2,...,N.

2. Reguła Hebba (RH) - wersja online

Ta wersja Reguły Hebba może „douczać” sieć już podczas działania poprzez jednokrotną prezentację nowego wektora na wejściu sieci.

Wagi ustala się według wzoru


,

gdzie: w_ij^t - waga połączenia pomiędzy neuronami i oraz j w kroku czasowym t,

x_i^m - i-ty bit m-tego wektora uczącego,

M - liczba wektorów uczących, m = 1,2,...,M,

N - liczba neuronów sieci, i,j = 1,2,...,N.

3. Reguła Rzutowania (Pseudoinwersji) (RR) - wersja offline

Metoda ta zakłada liniową niezależność wektorów uczących w celu zapewnienia poprawności procesu uczenia sieci.

Dla wektorów liniowo niezależnych wagi ustala się według wzoru


,

gdzie: W - macierz wag wszystkich neuronów sieci,

X = [X¹,X²,...,X^M] - macierz wektorów uczących zapisanych kolumnowo,

M - liczba wektorów uczących.

Dla wektorów ortogonalnych wagi ustala się według wzoru


,

gdzie: W - macierz wag wszystkich neuronów sieci,

X = [X¹,X²,...,X^M] - macierz wektorów uczących zapisanych kolumnowo,

M - liczba wektorów uczących,

N - liczba neuronów sieci.

4. Reguła Rzutowania (RR) - wersja online

Ta wersja Reguły Rzutowania może „douczać” sieć już podczas działania poprzez jednokrotną prezentację nowego wektora na wejściu sieci.

Wagi ustala się według wzoru




gdzie: W^t - macierz wag neuronów sieci w kroku czasowym t,

X^t - kolejny wektor uczący (dla kroku czasowego t)

M - liczba wektorów uczących, t = 1,2,...,M,

W⁰ = 0 - początkowa (startowa) macierz wag sieci.

5. Reguła Wzajemnych Ograniczeń (RWO)

Wagi ustala się według wzoru


,

gdzie: w_ij - waga połączenia pomiędzy neuronami i oraz j,

x_i^m - i-ty bit m-tego wektora uczącego,

M - liczba wektorów uczących, m = 1,2,...,M,

N - liczba neuronów sieci, i,j = 1,2,...,N,

λ > 0 - stała uczenia.

6. Reguła Rzutowania Delta (RRD)

Metoda ta wykorzystuje wielokrotną prezentację wektorów uczących, podzieloną na tzw. epoki uczenia. Każda epoka uczenia obejmuje jeden cykl jednorazowych prezentacji kolejno wszystkich wzorców uczących.

Wagi ustala się według wzoru


,

gdzie: W^t_m - macierz wag neuronów sieci w kroku czasowym m epoki uczenia t,

E - liczba epok uczenia, t = 1,2,...,E,

X_m - kolejny wektor uczący dla kroku czasowego m każdej epoki uczenia,

M - liczba wektorów uczących, m = 1,2,...,M,

N - liczba neuronów sieci,

W⁰ = 0 - początkowa (startowa) macierz wag sieci,

η ∈ <0,7;0,9〉 - stała uczenia.

Warunek końca iteracji


,

gdzie: W^t_m - macierz wag neuronów sieci w kroku czasowym m epoki uczenia t,

E - liczba epok uczenia, t = 1,2,...,E,

M - liczba wektorów uczących, m = 1,2,...,M,

ε - minimalna zmiana wag sieci według normy || . ||.

7. Zmodyfikowana Reguła Perceptronu (ZRP)

Metoda ta wykorzystuje wielokrotną prezentację wektorów uczących, podzieloną na tzw. epoki uczenia. Każda epoka uczenia obejmuje jeden cykl jednorazowych prezentacji kolejno wszystkich wzorców uczących.

Wagi ustala się według wzoru


,

gdzie: w_ij^t - waga połączenia pomiędzy neuronami i oraz j w kroku czasowym m epoki uczenia t,

E - liczba epok uczenia, t = 1,2,...,E,

M - liczba wektorów uczących, m = 1,2,...,M,

N - liczba neuronów sieci, i,j = 1,2,...,N,

η ∈ <0,7;0,9〉 - stała uczenia.

1. Zastosowania sieci Hopfielda

Sieci Hopfielda znalazły szerokie zastosowanie w rozwiązywaniu różnego rodzaju problemów optymalizacyjnych, opisanych w pracach [3], [5]. W przypadku wielu z nich kryterium skuteczności nie jest jedyną, a często nawet nie podstawową miarą jakości rozwiązania danego problemu. Krytycznymi parametrami przy rozwiązywaniu wielu skomplikowanych problemów optymalizacyjnych są często ograniczenia czasowe lub pamięciowe, przedstawione w [3]. Sieci neuronowe zastosowane do ich rozwiązania osiągają zwykle bardzo dobre rezultaty w krótkim czasie i przy ograniczonych wymaganiach sprzętowych. Dzięki swojej zdolności do uogólniania zdobytej wiedzy oraz ewolucyjnej poprawy efektywności działania bardzo dobrze nadają się do zastosowania w rozwiązywaniu problemów optymalizacyjnych. Po okresie treningu sieć neuronowa zwykle potrafi rozwiązać nie tylko problemy treningowe, ale także nieznane problemy pokrewne (problem ten przedstawiono w pracach [2], [4]). Analizując przykłady z życia codziennego można dojść do wniosku, że większość problemów mających praktyczne znaczenie czy zastosowanie, niezależnie od ich genezy i pierwotnego sformułowania, można sprowadzić przez odpowiednią transformację do problemu optymalizacyjnego. Najczęściej stosowanym miernikiem oceny efektywności metody rozwiązującej dany problem optymalizacyjny jest skuteczność minimalizacji bądź maksymalizacji funkcji celu. W wielu problemach jednak istotniejszym kryterium może być np. szybkość generowania odpowiedzi lub uniwersalność stosowanej metody. Następujące trzy problemy optymalizacyjne szczegółowo przedstawione poniżej za [11] posiadają bardzo ważne, inne niż skuteczność, kryteria oceny metod ich rozwiązywania:

1. problem komiwojażera,

2. problem rozpoznawania obiektów,

3. problem określenia strategii gry.

1. Problem komiwojażera

Problem komiwojażera (ang. TSP - Travelling Salesman Problem) dla N miast, z których każde dwa połączone są drogą o określonej długości, polega na znalezieniu trasy spełniającej następujące warunki:

• trasa zaczyna się i kończy w tym samym mieście,

• trasa przechodzi dokładnie raz przez każde miasto, za wyjątkiem miasta będącego jednocześnie początkiem i końcem trasy,

• trasa jest najkrótszą spośród tras spełniających poprzednie warunki.

Formalna definicja problemu komiwojażera brzmi następująco:

Dany jest niezorientowany graf pełny K_N oraz symetryczna macierz wag krawędzi tego grafu. Znaleźć w tym grafie cykl Hamiltona o minimalnym koszcie.

Istnieje wiele różnych wariantów problemu TSP, wśród najbardziej rozpowszechnionych wymienić należy:

• pytanie o istnienie drogi komiwojażera w grafie, który nie jest pełny,

• znalezienie najkrótszej drogi komiwojażera w grafie, który nie jest pełny,

• znalezienie suboptymalnej trasy, różniącej się od optymalnej o nie więcej niż zadaną z góry wielkość e,

• znalezienie optymalnej drogi przy niesymetrycznej macierzy kosztu,

• warianty problemu, w których odległości pomiędzy miastami są liczone przy pomocy geometrii nieeuklidesowych.

Problemowi komiwojażera z uwagi na jego istotne znaczenie praktyczne poświęcono bardzo wiele uwagi próbując rozwiązać go zarówno metodami klasycznymi jak i metodami sztucznej inteligencji (heurystyki, sieci neuronowe, algorytmy genetyczne, opisane w [7], [12] i [16]). Problem ten odpowiada zadaniu zdefiniowania optymalnej trasy rozwożenia towarów oraz wielu innym problemom logistycznym. Niezależnie od stosowanej metody rozwiązania, etykietując w sposób losowy zbiór miast X={X₁,X₂,...,X_N} oraz oznaczając przez d_ij = d_ji, i,j=1,2,...,N koszt drogi pomiędzy miastami i oraz j otrzymujemy, że dla dowolnej permutacji σ zbioru miast X sumaryczny koszt drogi zamkniętej przebytej przez komiwojażera F(σ) jest równy


.

Zatem rozwiązanie problemu to znalezienie permutacji σ_min takiej, że:


,

gdzie P_N to zbiór wszystkich permutacji zbioru N - elementowego.

Problem komiwojażera należy do klasy problemów NP-trudnych. Oznacza to, że zapewnienie uzyskania rozwiązania optymalnego wymaga nakładów czasowych, które wraz ze wzrostem wymiaru problemu N rosną szybciej niż wielomian dowolnego, skończonego stopnia względem N. W praktyce jedyną metodą dającą gwarancję uzyskania rozwiązania optymalnego jest wygenerowanie wszystkich permutacji zbioru miast, policzenie długości drogi odpowiadającej każdemu z układów i wybranie najkrótszej z nich. Przy odpowiednio dużym wymiarze problemu podejście polegające na przeglądaniu wszystkich możliwości jest nie do przyjęcia ze względu na zbyt długi czas osiągnięcia rozwiązania. Tutaj właśnie alternatywne podejście proponuje metodologia sieci neuronowych, a konkretnie modele dyskretne i ciągłe sieci Hopfielda. Stosując sieci Hopfielda rezygnuje się z zapewnienia optymalności rozwiązania na rzecz istotnego zmniejszenia wymagań czasowych w stosunku do metody wyczerpującego przeszukiwania. Dzięki temu możliwe jest wykorzystanie metody wielokrotnych startów, polegającej na wielokrotnym uruchomieniu sieci Hopfielda z różnymi warunkami początkowymi, aby wybrać rozwiązanie najlepsze spośród uzyskanych. Z powyższego wynika, że w problemie komiwojażera za zastosowaniem sieci Hopfielda przemawia kryterium czasowe.

1. Problem rozpoznawania obiektów

Problem rozpoznawania obiektów, podobnie jak problem komiwojażera, występuje w wielu różnych postaciach, w zależności od kontekstu, w którym jest rozpatrywany. Załóżmy, że jest zdefiniowana pewna liczba klas (kategorii) obiektów, a problem polega na określeniu, do której ze zdefiniowanych klas należą nieznane obiekty testowe. Jako wejście dla systemu rozpoznającego obiekty stosuje się zdjęcia bądź wzorce obiektów - w przypadku systemów implementowanych za pomocą programów komputerowych lub same obiekty - w przypadku zaawansowanych sprzętowo systemów, np. robotów. Zdefiniowana jest pewna liczba klas obiektów K₁,K₂,...,K_N oraz zbiór obiektów do rozpoznania. Zadanie optymalizacyjne (teorię optymalizacji i badań operacyjnych przybliżają [5] i [19]) polega na minimalizacji liczby niepoprawnych odpowiedzi na pytanie, do której spośród kategorii należy dany obiekt testowy, stawiane kolejno dla wszystkich obiektów testowych. Jeden z wariantów problemu rozpoznawania obiektów polega na wyróżnieniu pewnego, zadanego zbioru X z całej przestrzeni obiektów i odpowiedzi na pytanie, czy testowany obiekt należy do zbioru X. Tradycyjna metoda generowania odpowiedzi polega na zapamiętaniu wszystkich wzorców treningowych x_s, s = 1,2,...,M, a następnie dla danego wzorca testowego x_t znalezieniu jego najbliższego sąsiada x' oraz określeniu kategorii k ε {K₁,K₂,...,K_N} zawierającej x'. Najbliższym sąsiadem obiektu x_t jest wzorzec x' spełniający warunek


,

gdzie R(x_t, x_s) to miara odległości pomiędzy x_t a x_s.

Niestety proponowane rozwiązanie jest w przypadku dużej liczby obiektów M oraz dużych ich rozmiarów niepraktyczne ze względu na wymagania dotyczące wielkości pamięci niezbędnej do ich przechowania. Ponadto w przypadku obarczenia błędem obiektów uczących zdolność generalizacji powyższego algorytmu jest bardzo słaba. Istotnym czynnikiem przy rozwiązywaniu tego problemu jest także szybkość odpowiedzi. W wielu aplikacjach czas odpowiedzi jest krytycznym parametrem systemu. Także z tego powodu metoda polegająca na przeglądaniu całej bazy wzorców nie może być brana pod uwagę w przypadku przeglądania sekwencyjnego. Zatem w problemie rozpoznawania obiektów za zastosowaniem sieci Hopfielda przemawiają kryterium sprzętowe (pamięciowe) i kryterium czasowe.

2. Problem określenia strategii gry

Problem określenia strategii gry rozpatrzymy w kontekście dwuosobowej gry planszowej, jaką są np. warcaby lub szachy. Zadanie polega na opracowaniu takiej metody gry M, która zagwarantuje największą skuteczność w sensie liczby wygranych pojedynków. Przyjmijmy, że wygrana ma wartość 1, remis ½, a przegrana 0. Zatem zadanie optymalizacyjne polega na maksymalizacji wartości funkcji liczby wygranych W(M) ze względu na strategię M, określonej wzorem


,

gdzie: P_M - zbiór rozegranych partii testowych z zastosowaniem strategii M,

p_i - i-ta partia testowa w P_M,

G_M(p_i) - wynik i-tej partii testowej w P_M,

M - strategia należąca do zbioru możliwych strategii w danej grze.

W przypadku oceny efektywności systemu grającego w grę typu warcaby lub szachy warunkami równie istotnymi jak kryterium skuteczności będą kryterium sprzętowe i czasowe. Specyfika problemu wyklucza dominującą rolę któregokolwiek z tych kryteriów. Wszystkie strategie M powinny być porównywane na podstawie partii rozgrywanych z tymi samymi przeciwnikami przy odpowiednio dobranych liczbach partii i przeciwników. Dla oceny efektywności systemu olbrzymie znaczenie ma wybór metody uczenia. Ze względu na ograniczenia sprzętowe i możliwość zapamiętania skończonej liczby partii gry pożądaną cechą jest umiejętność uogólniania nabytej wiedzy oraz skutecznego jej stosowania w sytuacjach zbliżonych do problemów uczących. Dobrze byłoby zapewnić możliwość automatycznego poprawiania poziomu gry systemu poprzez umiejętne łączenie wiedzy predefiniowanej z tą zdobytą z doświadczenia podczas przeprowadzanych partii gry, a więc etap uczenia systemu nie zostałby gwałtownie i całkowicie zakończony. Taka koncepcja autonomicznego rozwoju systemu podczas pracy jest jedną z bardzo ważnych idei w dziedzinie sztucznej inteligencji. Sieć Hopfielda w odróżnieniu od podejścia tradycyjnego może zapewnić cechy uogólniania i samouczenia się systemu. Zatem za zastosowaniem sieci Hopfielda w problemie określenia strategii gry przemawiają kryterium zarządzania wiedzą (uogólniania, zdobywania doświadczenia) oraz kryterium sprzętowe (pamięciowe).

1. Sieć Hopfielda jako pamięć autoasocjacyjna

Zadaniem pamięci autoasocjacyjnej (ang. associative memory), opisanej w pracach [13], [14], [15]) jest zapamiętanie określonego zbioru wektorów binarnych w taki sposób, aby po otrzymaniu na wejściu nieznanego wektora binarnego x pamięć odtwarzała na wyjściu ten z zapamiętanych wektorów, który jest najbliższy x w sensie odległości Hamminga. Inaczej formułując problem, pamięć skojarzeniowa powinna spełniać dwa warunki:

• podanie na jej wejście dowolnego z zapamiętanych wektorów powoduje odtworzenie na wyjściu tego samego wektora,

• podanie na jej wejście zaburzonej w dopuszczalnych granicach wersji dowolnego z zapamiętanych wektorów powoduje odtworzenie na wyjściu poprawnej postaci tego wektora.

Oprócz modelu Hopfielda dyskretnego jako pamięci skojarzeniowe stosuje się także model dyskretno-ciągły Hopfielda, z dyskretnym czasem i ciągłą funkcją aktywacji neuronów w postaci sigmoidalnej. W niniejszej pracy zastosowano model dyskretny z funkcją aktywacji signum. Hopfield zaproponował zastosowanie do uczenia pamięci autoasocjacyjnej Reguły Hebba, która wywodzi się za spekulacji na temat sposobu, w jaki ludzki mózg reprezentuje koncepcje psychologiczne. Hebb postulował, że pewne rodzaje koncepcji psychologicznych mogą być reprezentowane poprzez jednoczesne pobudzanie pewnych grup neuronów. Podstawą idei Hebba jest teza, iż funkcjonalne grupy neuronów formują się w procesie uczenia poprzez wzmocnienie wzajemnych oddziaływań (wag) pomiędzy wszystkimi jednocześnie pobudzonymi neuronami. Proces wzmacniania wzajemnych połączeń spowodowany jednoczesnym pobudzeniem neuronów został zaakceptowany jako metoda uczenia sztucznych sieci neuronowych niekorzystająca z informacji o prawidłowych odpowiedziach sieci i nazwany Regułą Hebba. Rozpoznawanie wektorów przez pamięć autoasocjacyjną przebiega w następujący sposób: nieznany wektor jest podawany na wejście sieci Hopfielda, a następnie wszystkie neurony obliczają swoje potencjały wewnętrzne oraz zewnętrzne (odpowiedzi). W kolejnym kroku przetwarzania rekurencyjnego na wejście sieci jest podawany wektor sygnałów wyjściowych, znowu liczone są potencjały wewnętrzne oraz zewnętrzne itd.. Taki proces przetwarzania może zakończyć się na dwa sposoby: poprzez osiągnięcie stanu stabilnego, gdy w dwóch kolejnych przetwarzaniach sieć wygeneruje taki sam wektor wyjściowy, będący odpowiedzią pamięci skojarzeniowej na podany na wejście wektor wejściowy lub, gdy zostanie przekroczona maksymalna liczba rekurencji. Może się to stać w sytuacji, gdy sieć wpadnie w oscylacje pomiędzy dwoma stanami meta-stabilnymi, tzn. na zmianę będzie generowała na wyjściu dwa różne wektory Y₁ i Y₂ według schematu Y₁→Y₂→Y₁→Y₂→.... Dla dowolnego wektora wejściowego maksymalna liczba synchronicznych iteracji sieci Hopfielda, zanim osiągnięty zostanie stan stabilny bądź sieć rozpocznie oscylacje, jest ograniczona zgodnie z zależnością


,

gdzie: I_max - maksymalna liczba rekurencji przetwarzania,

M - liczba wektorów uczących zapamiętanych w pamięci skojarzeniowej.

Oscylacje nie powstają w sieciach Hopfielda w przypadku uaktualniania asynchronicznego stanu neuronów w kolejności zgodnej z dowolną, losowo wybrana permutacją neuronów. Wynika to z faktu, że w trybie asynchronicznym pracy sieci Hopfielda warunkiem wystarczającym zbieżności sieci do stanu stabilnego jest symetria macierzy wag W i wyzerowanie jej głównej przekątnej, czyli zabronienie sprzężeń zwrotnych w zakresie pojedynczych neuronów. Załóżmy, że w sieci Hopfielda pracującej jako pamięć autoasocjacyjna i złożonej z N neuronów unipolarnych n_i, i=1,2,..,N w macierzy wag W zachodzą warunki


.

Zdefiniujmy za [11] pomocniczą funkcję energii sieci jako


.

Dla kolejnego uaktualnianego asynchronicznie neuronu n_i następuje zmiana energii sieci o wartość


.

Zatem z unipolarnej funkcji aktywacji oraz zależności




wynika ΔE_i ≤ 0, przy czym równość zachodzi tylko w przypadku, gdy Δy_i = 0. Oznacza to, że przy stosowaniu asynchronicznego uaktualniania neuronów energia sieci E jest nierosnąca w czasie. Ponieważ zakres wartości E jest ograniczony zgodnie z nierównością


,

sieć po pewnym skończonym czasie musi osiągnąć stan stabilny charakteryzujący się minimum wartości energii i zatrzymać się. Pojemność, definiowana jako liczba wzorców uczących wygenerowanych według rozkładu jednostajnego, które sieć potrafi bezbłędnie odtworzyć w procesie rozpoznawania, dla bipolarnej synchronicznej lub asynchronicznej sieci Hopfielda uczonej Regułą Hebba wynosi asymptotycznie przy liczbie neuronów N→∞ (za pracą [11])


.

Jeśli założymy nieznaczne osłabienie warunku rygorystycznego rozpoznawania wszystkich wzorców uczących, asymptotyczna pojemność zwiększa się dwukrotnie


.

Często jest także stosowane oszacowanie pojemności pamięci autoasocjacyjnej podane przez Hopfielda


.

Proces przetwarzania rekurencyjnego przez sieć Hopfielda zakłóconego wektora wejściowego kończy się jednym ze stanów przedstawionych na rysunkach Rys. 3 - Rys. 6 (rysunki pochodzą z badań rozpoznawania obrazów za pomocą symulatora Snhop):

• odtworzenie nie zakłóconego wzorca lub jego negatywu (Rys.3),

• odtworzenie niewłaściwego wzorca lub jego negatywu (Rys.4),

• odtworzenie kompilacji kilku wzorców (Rys.5),

• wpadnięcie sieci w oscylacje i przekroczenie maksymalnej liczby rekurencji (Rys.6).




Rysunek 3: Poprawne odtworzenie wzorca.


Rysunek 4: Odtworzenie niewłaściwego wzorca.




Rysunek 5: Odtworzenie kompilacji kilku wzorców.


Rysunek 6: Wpadnięcie sieci w oscylacje.

Praktyczne znaczenie problemu zapamiętywania i poprawnego odtwarzania zakłóconej informacji powoduje dużą popularność i mnogość zastosowań sieci Hopfielda jako pamięci autoasocjacyjnych. Podstawowymi kryteriami stosowanymi do oceny takich systemów są:

• pojemność pamięci,

• skuteczność rozpoznawania,

• zdolność generalizacji,

• złożoność obliczeniowa,

• lokalność metody uczenia,

• sposób prezentacji wzorców (online/offline),

• wymagania czasowe i pamięciowe.

• Symulator sieci Hopfielda

1. Architektura systemu

Snhop (Sieci neuronowe hopfielda) - program symulatora dołączony do pracy dyplomowej „Rozpoznawanie obrazów przy użyciu symulatora sieci Hopfielda” jest aplikacją dla środowiska Sun Java 2, dzięki czemu istnieje możliwość uruchamiania go na wirtualnych maszynach Java na różnych platformach i systemach operacyjnych. Został on zaprojektowany i zaimplementowany według metodologii obiektowej, co ułatwia dalszą rozbudowę i modyfikację istniejących modułów programu.

1. Wymagania

Program Snhop do poprawnego działania potrzebuje składników systemowych o następujących (lub wyższych) parametrach:

• składniki sprzętowe:

• częstotliwość taktowania CPU: 200 MHz,

• pojemność RAM: 64 MB,

• składniki programowe:

• Sun J2RE 1.3.1,

• GUI.

1. Właściwości

Symulator Snhop pozwala na zamodelowanie i następnie przeprowadzenie symulacji działania dyskretnej, synchronicznej sieci Hopfielda oraz badanie skuteczności rozpoznawania obrazów przez sieć przy różnych parametrach modelu, dobieranych zarówno na etapie uczenia jak i testowania. Wyniki uzyskane podczas badań na symulatorze mogą zostać zachowane w sposób trwały w postaci zbiorów na dysku. Symulator Snhop umożliwia:

• ustalenie wymiaru poziomego i pionowego rozpoznawanego obrazu,

• ustalenie parametru BIAS neuronów,

• wybranie funkcji aktywacji neuronów spośród trzech odmian funkcji signum,

• wybranie metody uczenia sieci (Reguła Hebba, Reguła Wzajemnych Ograniczeń, Reguła Rzutowania Delta, Zmodyfikowana Reguła Perceptronu),

• ustalenie generowanego losowo zaszumienia obrazów wejściowych,

• ustalenie dopuszczalnego zaszumienia odpowiedzi sieci, traktowanego jeszcze jako odpowiedź poprawna,

• tworzenie zestawu obrazów uczących według specyfikacji tekstowej, np.

„0-9A-Z” lub ręcznie,

• wizualizację zbiorów uczącego, testującego, wynikowego i rekurencyjnego,

• generowanie raportu z przebiegu symulacji,

• zapis całej sieci lub oddzielnie zbiorów uczącego, testującego i wynikowego do pliku.

1. Budowa

Symulator sieci Hopfielda Snhop zbudowany jest z ośmiu klas i jednego interfejsu języka Java (Rys.7). Model symulatora wykonany według notacji języka UML w programie Rational Rose 98 firmy Rational Software Corporation oraz pliki źródłowe Java znajdują się na załączonym do niniejszej pracy nośniku CD.


Rysunek 7: Diagram klas symulatora Snhop.

Symulator składa się z następujących klas:

• Snhop,

• PatternContainer,

• AbstractPattern,

• LearnPattern,

• InputPattern,

• OutputPattern,

• RecurPattern,

• Hopfield,

• HopfieldObserver (interfejs Java).

Klasa Snhop jest podstawową klasą aplikacji symulatora, odpowiada za główne okno aplikacji i logikę działania. PatternContainer zajmuje się wizualizacją obrazów uczących, testujących, wynikowych oraz rekurencyjnych (powstających podczas rekurencji sieci). Klasa abstrakcyjna AbstractPattern modeluje podstawowe cechy obrazów liter i cyfr używanych w aplikacji symulatora. LearnPattern reprezentuje wzorce uczące sieci Hopfielda, InputPattern - obrazy testujące sieci, OutputPattern - obrazy wynikowe sieci, RecurPattern - obrazy rekurencyjne sieci. Klasa Hopfield modeluje właściwą sieć Hopfielda (macierz wag wszystkich neuronów sieci), zaś HopfieldObserver to interfejs obsługi sieci Hopfielda, realizowany przez klasę Snhop, oddzielony w celu stworzenia możliwości realizacji tej obsługi przez inne klasy przy rozbudowie symulatora.

1. Interfejs użytkownika

Program Snhop posiada graficzny (okienkowy) interfejs użytkownika. Dla ułatwienia obsługi programu wszystkie jego podstawowe funkcje, podzielone na cztery grupy, tzn. Instrukcja, Parametry, Symulacja oraz Wyniki, są zorganizowane w formie zakładek w głównym oknie, pomiędzy którymi można dokonywać szybkiego przełączania.

1. Główne okno

Zakładka Instrukcja głównego okna programu przedstawiona jest na Rys. 8.


Rysunek 8: Zakładka Instrukcja głównego okna programu.

Elementy zakładki Instrukcja oraz głównego okna programu:

• obszar wyświetlania pomocy programu,

• przycisk Spis treści przechodzący do spisu treści pomocy,

• przycisk Indeks przechodzący do alfabetycznego indeksu pomocy ,

• pasek menu pozwalający na dostęp do wszystkich funkcji,

• pasek narzędzi pozwalający na szybki dostęp do wybranych funkcji,

• zakładki widoku pozwalające na przełączanie grupy funkcji,

• obszar komunikatów dla użytkownika .

Zakładka Parametry głównego okna programu przedstawiona jest na Rys. 9.


Rysunek 9: Zakładka Parametry głównego okna programu.

Elementy zakładki Parametry głównego okna programu:

• przełącznik wyboru i pola wprowadzania parametrów metody uczenia,

• pola wprowadzania wymiarów poziomego i pionowego (mierzonych w

pikselach obrazu px)

• pole wprowadzania zaszumienia wejścia i wyjścia (mierzonych w %),

• pole wprowadzania maksimum rekurencji,

• pole wprowadzania BIAS,

• przełącznik wyboru funkcji aktywacji.

Zakładka Symulacja głównego okna programu przedstawiona jest na Rys. 10.


Rysunek 10: Zakładka Symulacja głównego okna programu.

Elementy zakładki Symulacja głównego okna programu:

• obszar wyświetlania odległości Hamminga i iloczynu skalarnego,

• obszar wizualizacji zbiorów uczącego, testującego, wynikowego i

rekurencyjnego,

• pole wprowadzania specyfikacji wstawianych automatycznie wzorców

uczących,

• przyciski Wstaw, Ręczny i Wyczyść operujące na wzorcach uczących,

• przyciski Uczenie i Rozpoznawanie uruchamiające symulację,

• przycisk Stop zatrzymujący symulację,

• przycisk Raport generujący raport z przebiegu symulacji.

Zakładka Wyniki głównego okna programu przedstawiona jest na Rys. 11.


Rysunek 11: Zakładka Wyniki głównego okna programu:

Elementy zakładki Wyniki głównego okna programu:

• obszar wyświetlania raportów w formie tabelek zawierających:

• ilość wzorców uczących,

• rodzaj i parametry metody uczenia,

• wymiary poziomy i pionowy obrazów,

• zaszumienia wejścia i wyjścia,

• maksimum rekurencji i dane o funkcji aktywacji (rodzaj, BIAS),

• ilość rozpoznań poprawnych i błędnych,

• skuteczność rozpoznawania obrazów przez sieć (mierzoną w %),

• przycisk Wyczyść kasujący wyświetlane raporty.

1. Okna dialogowe

W następujących sytuacjach program Snhop przekazuje użytkownikowi komunikaty za pomocą okien dialogowych:

• zamykanie programu przy nie zapisanym projekcie sieci (Rys.12),




Rysunek 12: Okno dialogowe zapisu sieci Hopfielda.

• wybranie funkcji usunięcia elementu zbioru uczącego (Rys.13),




Rysunek 13: Okno dialogowe usunięcia elementu zbioru uczącego.

• wybranie funkcji Stop podczas trwania symulacji (Rys.14),




Rysunek 14: Okno dialogowe przerwania symulacji.

• wprowadzenie niepoprawnej wartości jednego z parametrów (Rys.15),




Rysunek 15: Okno dialogowe błędnej wartości parametru.

• wybranie funkcji O programie (Rys.16),




Rysunek 16: Okno dialogowe O programie.

1. Komendy menu

Większość funkcji programu Snhop dostępna jest poprzez menu zorganizowane w sześć grup: Plik, Zbiór, Widok, Parametry, Symulacja oraz Pomoc. Zawierają one następujące komendy menu:

• Plik | Nowy - przygotowuje program do pracy z nową siecią,

• Plik | Otwórz - otwiera sieć z pliku,

• Plik | Zapisz - zapisuje sieć do pliku,

• Plik | Zakończ - kończy pracę programu,

• Zbiór | Uczący | Otwórz - otwiera z pliku zbiór uczący sieci,

• Zbiór | Uczący | Zapisz - zapisuje do pliku zbiór uczący sieci,

• Zbiór | Testujący | Otwórz - otwiera z pliku zbiór testujący sieci,

• Zbiór | Testujący | Zapisz - zapisuje do pliku zbiór testujący sieci,

• Zbiór | Wynikowy | Zapisz - zapisuje do pliku zbiór wynikowy sieci,

• Widok | Instrukcja - przełącza widok na zakładkę Instrukcja,

• Widok | Parametry - przełącza widok na zakładkę Parametry,

• Widok | Symulacja - przełącza widok na zakładkę Symulacja,

• Widok | Wyniki - przełącza widok na zakładkę Wyniki,

• Parametry | Ustaw - ustawia zmienione parametry pracy programu,

• Parametry | Anuluj - przywraca poprzednie parametry pracy programu,

• Parametry | Domyślne - ustawia domyślne parametry pracy programu,

• Symulacja | Wzorce | Wstaw - wstawia wzorce według specyfikacji,

• Symulacja | Wzorce | Ręczny - wstawia pusty wzorzec (do ręcznej modyfikacji),

• Symulacja | Wzorce | Wyczyść - usuwa wszystkie wzorce,

• Symulacja | Przebieg | Uczenie - uruchamia proces uczenia sieci,

• Symulacja | Przebieg | Rozpoznawanie - uruchamia proces rozpoznawania,

• Symulacja | Przebieg | Stop - zatrzymuje proces uczenia lub rozpoznawania,

• Symulacja | Przebieg | Raport - generuje raport z przebiegu symulacji,

• Pomoc | Spis treści - wyświetla spis treści pomocy programu,

• Pomoc | Indeks - wyświetla indeks alfabetyczny pomocy programu,

• Pomoc | O programie - wyświetla okno z informacją o programie.

1. Pasek narzędzi

Pasek narzędzi głównego okna programu przedstawiony jest na Rys. 17.




Rysunek 17: Pasek narzędzi głównego okna programu.

Pozwala on na szybkie uruchomienie często używanych poleceń. Większość przycisków na pasku narzędzi posiada odpowiadające im polecenia menu. Przycisk Uczenie i rozpoznawanie, który uruchamia uczenie i natychmiast po nim rozpoznawanie przez sieć obrazów testowych, odpowiada użyciu kolejno dwóch poleceń menu.

Elementy paska narzędzi głównego okna programu:

• przycisk Nowy (odpowiednik polecenia menu Plik | Nowy),

• przycisk Otwórz (odpowiednik polecenia menu Plik | Otwórz),

• przycisk Zapisz (odpowiednik polecenia menu Plik | Zapisz),

• przycisk Uczenie i rozpoznawanie (odpowiednik poleceń menu

Symulacja | Przebieg | Uczenie i Symulacja | Przebieg |

Rozpoznawanie użytych kolejno po sobie),

• przycisk Stop (odpowiednik polecenia menu Symulacja | Przebieg |

Stop),

• przycisk O programie (odpowiednik polecenia menu Pomoc |

O programie).

1. Typowe zadania

Zalecane etapy wykonywania czynności podczas pracy przy użyciu

symulatora Snhop są następujące:

1. utworzenie nowej sieci (stan domyślny po uruchomieniu programu),

2. ustalenie parametrów symulacji,

3. utworzenie wzorców uczących (według specyfikacji lub ręcznie),

4. przeprowadzenie uczenia sieci,

5. przeprowadzenie rozpoznawania obrazów przez sieć,

6. wygenerowanie raportu,

7. zapis sieci do pliku w celu zachowania wyników pracy.

1. Tworzenie nowej sieci Hopfielda

Aby utworzyć nową sieć Hopfielda, należy:

1. użyć polecenia menu Plik | Nowy,

2. jeżeli poprzedni projekt nie został wcześniej zapisany, program zaproponuje zapis sieci do pliku.

1. Odczyt i zapis sieci

Aby odczytać sieć z pliku typu „hop” (Rys. 18), należy:

1. użyć polecenia menu Plik | Otwórz,

2. w oknie dialogowym wskazać plik z siecią i nacisnąć przycisk OK,

3. jeżeli poprzedni projekt nie został wcześniej zapisany, program zaproponuje zapis sieci do pliku.




Rysunek 18: Okno otwierania pliku z siecią Hopfielda.

Aby zapisać sieć do pliku typu „hop” (Rys. 19), należy:

1. użyć polecenia menu Plik | Zapisz,

2. w oknie dialogowym wskazać plik lub wpisać nazwę nowego pliku i nacisnąć przycisk OK.




Rysunek 19: Okno zapisu sieci Hopfielda do pliku.

1. Odczyt i zapis zbioru uczącego

Aby odczytać zbiór uczący z pliku typu „set”, należy:

1. użyć polecenia menu Zbiór | Uczący | Otwórz,

2. w oknie dialogowym wskazać plik ze zbiorem uczącym i nacisnąć przycisk OK,

3. jeżeli poprzedni projekt nie został wcześniej zapisany, program zaproponuje zapis sieci do pliku.

Aby zapisać zbiór uczący do pliku typu „set”, należy:

1. użyć polecenia menu Zbiór | Uczący | Zapisz,

2. w oknie dialogowym wskazać plik lub wpisać nazwę nowego pliku i nacisnąć przycisk OK.

1. Odczyt i zapis zbioru testującego

Aby odczytać zbiór testujący z pliku typu „set”, należy:

1. użyć polecenia menu Zbiór | Testujący | Otwórz,

2. w oknie dialogowym wskazać plik ze zbiorem testującym i nacisnąć

przycisk OK,

3. jeżeli poprzedni projekt nie został wcześniej zapisany, program

zaproponuje zapis sieci do pliku.

Aby zapisać zbiór testujący do pliku typu „set”, należy:

1. użyć polecenia menu Zbiór | Testujący | Zapisz,

2. w oknie dialogowym wskazać plik lub wpisać nazwę nowego pliku i nacisnąć przycisk OK.

1. Zapis zbioru wynikowego

Aby zapisać zbiór wynikowy do pliku typu „set”, należy:

1. użyć polecenia menu Zbiór | Wynikowy | Zapisz,

2. w oknie dialogowym wskazać plik lub wpisać nazwę nowego pliku i

nacisnąć przycisk OK.

1. Ustalanie parametrów symulacji

Aby ustalić parametry symulacji, należy:

1. użyć polecenia menu Widok | Parametry,

2. wybrać metodę uczenia sieci,

3. wpisać żądane wartości parametrów metody uczenia w odpowiednie pola,

4. wybrać funkcję aktywacji neuronów,

5. użyć polecenia menu Parametry | Ustaw, aby zatwierdzić zmiany,

6. użyć polecenia menu Parametry | Anuluj, aby cofnąć zmiany,

7. użyć polecenia menu Parametry | Domyślne, aby przywrócić domyślne wartości parametrów.

1. Tworzenie obrazów uczących

Aby utworzyć wzorce uczące według specyfikacji, należy:

1. użyć polecenia menu Widok | Symulacja,

2. wpisać żądaną specyfikację wzorców, np. „0-9A-Z”,

3. użyć polecenia menu Symulacja | Wzorce | Wstaw, aby automatycznie wstawić wzorce.

Aby utworzyć wzorce uczące ręcznie, należy:

1. użyć polecenia menu Widok | Symulacja,

2. użyć polecenia menu Symulacja | Wzorce | Ręczny dla każdego wzorca,

3. po wstawieniu pustego wzorca istnieje możliwość jego ręcznej

modyfikacji (lewy przycisk urządzenia wskazującego stawia piksel,

prawy przycisk zeruje piksel).

Aby usunąć wzorce, należy:

1. użyć polecenia menu Symulacja | Wzorce | Wyczyść, aby usunąć

wszystkie wzorce,

2. nacisnąć dowolnym przyciskiem urządzenia wskazującego na

elemencie zbioru testującego, aby usunąć wzorzec (spowoduje to

usunięcie kolumny: wzorzec, element testujący, element wynikowy).

1. Kontrola przebiegu symulacji

Aby kontrolować przebieg symulacji, należy:

1. użyć polecenia menu Symulacja | Przebieg | Uczenie, aby uruchomić uczenie,

2. użyć polecenia menu Symulacja | Przebieg | Rozpoznawanie, aby uruchomić rozpoznawanie,

3. użyć polecenia menu Symulacja | Przebieg | Uczenie i Rozpoznawanie, aby uruchomić kolejno uczenie i rozpoznawanie,

4. użyć polecenia menu Symulacja | Przebieg | Stop, aby przerwać uczenie lub rozpoznawanie.

1. Pomiar odległości Hamminga i iloczynu skalarnego

Aby obliczyć odległości Hamminga i iloczyn skalarny dla elementu zbioru rekurencyjnego i wzorców uczących, należy:

1. użyć polecenia menu Widok | Symulacja,

2. nacisnąć dowolny przycisk urządzenia wskazującego na elemencie zbioru rekurencyjnego, aby obliczyć dla niego odległości od wzorców uczących (funkcja ta działa tylko do momentu modyfikacji zbioru uczącego w tej symulacji, odległości są podawane jako: H1 - odległość Hamminga od wzorca, H2 - odległość Hamminga od negatywu, S1 - iloczyn skalarny ze wzorcem, S2 - iloczyn skalarny z negatywem).

1. Wizualizowanie zbioru rekurencyjnego

Aby obejrzeć zbiór rekurencyjny po zakończeniu symulacji, należy:

1. użyć polecenia menu Widok | Symulacja,

2. nacisnąć dowolny przycisk urządzenia wskazującego na elemencie zbioru wynikowego, co spowoduje wyświetlenie dla niego wszystkich etapów przetwarzania rekurencyjnego przez sieć (funkcja ta działa tylko do momentu modyfikacji zbioru uczącego w tej symulacji),

3. nacisnąć dowolny przycisk urządzenia wskazującego na elemencie zbioru rekurencyjnego, aby obliczyć dla niego odległości od wzorców uczących (funkcja ta działa tylko do momentu modyfikacji zbioru uczącego w tej symulacji).

1. Generowanie raportu

Aby wygenerować raport po zakończeniu symulacji, należy:

1. użyć polecenia menu Symulacja | Przebieg | Raport (na zakładce Wyniki pojawi się raport z ostatnio przeprowadzonej symulacji rozpoznawania).

• Badania zrealizowane przy pomocy symulatora sieci Hopfielda

Badania sieci Hopfielda przeprowadzone za pomocą symulatora sieci Hopfielda Snhop (opisane również w pracy [8]) miały na celu porównanie wyników rozpoznawania obrazów testowych zakłóconych w sposób losowy w zadanym stopniu przez sieci Hopfielda uczone tym samym zbiorem obrazów wzorcowych (liter i cyfr) w zależności od:

• liczby neuronów sieci czyli wymiarów siatkówki,

• przyjętej metody uczenia sieci i jej parametrów charakterystycznych,

• stopnia zaszumienia danych wejściowych generowanego losowo,

• dopuszczalnego stopnia zaszumienia danych wyjściowych.

Sposób przedstawienia poprawności rozpoznania obrazu na rysunkach z wizualizacją przetwarzania obrazów przedstawia Rys.20. Wskaźnik poprawności umieszczony jest z lewej strony poniżej każdego elementu zbioru wynikowego.




Rysunek 20: Wskaźnik poprawności rozpoznania obrazu.

1. Rozpoznawanie liter i cyfr

Badania rozpoznawania liter i cyfr przeprowadzono dla zbioru uczącego 21-elementowego według specyfikacji „0-9A-K”. Porównano cztery zaimplementowane metody uczenia z następującymi parametrami:

• Reguła Hebba,

• Reguła Wzajemnych Ograniczeń: λ = 0,8,

• Reguła Rzutowania Delta: η = 0,8, E = 1000,

• Zmodyfikowana Reguła Perceptronu: η = 0,8, E = 1000,

gdzie: λ, η - stałe uczenia,

E - liczba epok uczenia sieci.

Pozostałe parametry symulacji:

• wymiary siatkówki: x = 10, y = 10,

• zaszumienie wejścia: θ_in = <0;100〉 % z krokiem k = 20 %,

• dopuszczalne zaszumienie wyjścia: θ_out = <5;15〉 % z krokiem k = 5 %,

• maximum rekurencji: R = 10,

• różne rodzaje funkcji aktywacji signum,

• próg przełączenia neuronu: BIAS = 0.

Zbiór obrazów użytych do uczenia sieci przedstawia Rys. 21.




Rysunek 21: Zestaw znaków dla rozpoznawania liter i cyfr.

Uzyskane wyniki rozpoznawania liter i cyfr przy małym dopuszczalnym zaszumieniu wyjścia θ_out=5 % przedstawiają Tab. 1 oraz Rys. 22.

θout=5 %	Skuteczność rozpoznawania [%]
θin [%]	Reg. Hebba	Reg. Wzaj. Ogr.	Reg. Rzut. Delta	Zmod. Reg. Perc.
0	24,0	0,0	100,0	100,0
20	24,0	0,0	67,0	33,0
40	24,0	0,0	0,0	5,0
60	24,0	0,0	0,0	0,0
80	24,0	0,0	29,0	33,0
100	24,0	0,0	100,0	100,0

Tabela 1: Skuteczność rozpoznawania liter i cyfr przy małym zaszumieniu wyjścia.


Rysunek 22: Skuteczność rozpoznawania liter i cyfr przy małym zaszumieniu wyjścia.

Na rysunkach Rys. 23 - Rys. 30 przedstawiono wybrane wizualizacje działania sieci Hopfielda wykonane przy pomocy symulatora Snhop podczas rozpoznawania liter i cyfr dla małego dopuszczalnego zaszumienia wyjścia θ_out=5 % (RH - Reguła Hebba, RWO - Reguła Wzajemnych Ograniczeń, RRD - Reguła Rzutowania Delta, ZRP - Zmodyfikowana Reguła Perceptronu).




Rysunek 23: Rozpoznawanie przez sieć uczoną RH przy θ_in=0 %.




Rysunek 24: Rozpoznawanie przez sieć uczoną RH przy θ_in=20 %.




Rysunek 25: Rozpoznawanie przez sieć uczoną RWO przy θ_in=0 %.




Rysunek 26: Rozpoznawanie przez sieć uczoną RWO przy θ_in=20 %.




Rysunek 27: Rozpoznawanie przez sieć uczoną RRD przy θ_in=0 %.




Rysunek 28: Rozpoznawanie przez sieć uczoną RRD przy θ_in=20 %.




Rysunek 29: Rozpoznawanie przez sieć uczoną ZRP przy θ_in=0 %.




Rysunek 30: Rozpoznawanie przez sieć uczoną ZRP przy θ_in=20 %.

Uzyskane wyniki rozpoznawania liter i cyfr przy średnim dopuszczalnym zaszumieniu wyjścia θ_out=10 % przedstawiają Tab. 2 oraz Rys. 31.

θout=10 %	Skuteczność rozpoznawania [%]
θin [%]	Reg. Hebba	Reg. Wzaj. Ogr.	Reg. Rzut. Delta	Zmod. Reg. Perc.
0	48,0	0,0	100,0	100,0
20	48,0	0,0	86,0	29,0
40	48,0	0,0	5,0	10,0
60	48,0	0,0	0,0	29,0
80	48,0	0,0	100,0	33,0
100	48,0	0,0	100,0	100,0

Tabela 2: Skuteczność rozpoznawania liter i cyfr przy średnim zaszumieniu wyjścia.


Rysunek 31: Skuteczność rozpoznawania liter i cyfr przy średnim zaszumieniu wyjścia.

Na rysunkach Rys. 32 - Rys. 39 przedstawiono wybrane wizualizacje działania sieci Hopfielda wykonane przy pomocy symulatora Snhop podczas rozpoznawania liter i cyfr dla średniego dopuszczalnego zaszumienia wyjścia θ_out=10 % (RH - Reguła Hebba, RWO - Reguła Wzajemnych Ograniczeń, RRD - Reguła Rzutowania Delta, ZRP - Zmodyfikowana Reguła Perceptronu).




Rysunek 32: Rozpoznawanie przez sieć uczoną RH przy θ_in=0 %.




Rysunek 33: Rozpoznawanie przez sieć uczoną RH przy θ_in=20 %.




Rysunek 34: Rozpoznawanie przez sieć uczoną RWO przy θ_in=0 %.




Rysunek 35: Rozpoznawanie przez sieć uczoną RWO przy θ_in=20 %.




Rysunek 36: Rozpoznawanie przez sieć uczoną RRD przy θ_in=0 %.




Rysunek 37: Rozpoznawanie przez sieć uczoną RRD przy θ_in=20 %.




Rysunek 38: Rozpoznawanie przez sieć uczoną ZRP przy θ_in=0 %.




Rysunek 39: Rozpoznawanie przez sieć uczoną ZRP przy θ_in=20 %.

Uzyskane wyniki rozpoznawania liter i cyfr przy dużym dopuszczalnym zaszumieniu wyjścia θ_out=15 % przedstawiają Tab. 3 oraz Rys. 40.

θout=15 %	Skuteczność rozpoznawania [%]
θin [%]	Reg. Hebba	Reg. Wzaj. Ogr.	Reg. Rzut. Delta	Zmod. Reg. Perc.
0	57,0	29,0	100,0	100,0
20	57,0	29,0	100,0	81,0
40	57,0	0,0	43,0	33,0
60	57,0	0,0	19,0	52,0
80	57,0	0,0	100,0	71,0
100	57,0	0,0	100,0	100,0

Tabela 3: Skuteczność rozpoznawania liter i cyfr przy dużym zaszumieniu wyjścia.


Rysunek 40: Skuteczność rozpoznawania liter i cyfr przy dużym zaszumieniu wyjścia.

Na rysunkach Rys. 41 - Rys. 48 przedstawiono wybrane wizualizacje działania sieci Hopfielda wykonane przy pomocy symulatora Snhop podczas rozpoznawania liter i cyfr dla dużego dopuszczalnego zaszumienia wyjścia θ_out=15 % (RH - Reguła Hebba, RWO - Reguła Wzajemnych Ograniczeń, RRD - Reguła Rzutowania Delta, ZRP - Zmodyfikowana Reguła Perceptronu).




Rysunek 41: Rozpoznawanie przez sieć uczoną RH przy θ_in=0 %.




Rysunek 42: Rozpoznawanie przez sieć uczoną RH przy θ_in=20 %.




Rysunek 43: Rozpoznawanie przez sieć uczoną RWO przy θ_in=0 %.




Rysunek 44: Rozpoznawanie przez sieć uczoną RWO przy θ_in=20 %.




Rysunek 45: Rozpoznawanie przez sieć uczoną RRD przy θ_in=0 %.




Rysunek 46: Rozpoznawanie przez sieć uczoną RRD przy θ_in=20 %.




Rysunek 47: Rozpoznawanie przez sieć uczoną ZRP przy θ_in=0 %.




Rysunek 48: Rozpoznawanie przez sieć uczoną ZRP przy θ_in=20 %.

Na podstawie uzyskanych wyników można stwierdzić, że klasyczna Reguła Hebba oraz jej modyfikacja, czyli Reguła Wzajemnych Ograniczeń nie są odpowiednimi metodami uczenia dla sieci mających rozpoznawać dowolne wzorce (np. pisane przez człowieka), a szczególnie wzorce rzadkie i skorelowane, jakimi są litery i cyfry alfabetu. Z przeprowadzonych badań wynika, że rodzaj funkcji aktywacji ma niewielki wpływ na osiągane wyniki uczenia sieci. Skuteczność rozpoznawania zgodnie z oczekiwaniami układa się symetrycznie wokół wartości parametru zaszumienia wejścia θ_in=50 %.

1. Rozpoznawanie liter

Badania rozpoznawania liter przeprowadzono dla zbioru uczącego 37-elementowego według specyfikacji „A-Z”. Porównano cztery zaimplementowane metody uczenia z następującymi parametrami:

• Reguła Hebba,

• Reguła Wzajemnych Ograniczeń: λ = 0,8,

• Reguła Rzutowania Delta: η = 0,8, E = 1000,

• Zmodyfikowana Reguła Perceptronu: η = 0,8, E = 1000,

gdzie: λ, η - stałe uczenia,

E - liczba epok uczenia sieci.

Pozostałe parametry symulacji:

• wymiary siatkówki: x = 10, y = 10,

• zaszumienie wejścia: θ_in = <0;50〉 % z krokiem k = 10 %,

• dopuszczalne zaszumienie wyjścia: θ_out = 10 %,

• maximum rekurencji: R = 10,

• różne rodzaje funkcji aktywacji signum,

• próg przełączenia neuronu: BIAS = 0.

Zbiór obrazów użytych do uczenia sieci przedstawia Rys. 49.




Rysunek 49: Zestaw znaków dla rozpoznawania liter.

Uzyskane wyniki rozpoznawania liter przy dopuszczalnym zaszumieniu wyjścia θ_out=10 % przedstawiają Tab. 4 oraz Rys. 50.

θout=10 %	Skuteczność rozpoznawania [%]
θin [%]	Reg. Hebba	Reg. Wzaj. Ogr.	Reg. Rzut. Delta	Zmod. Reg. Perc.
0	0,0	0,0	100,0	100,0
10	0,0	0,0	100,0	53,1
20	0,0	0,0	74,6	29,2
30	0,0	0,0	6,2	15,4
40	0,0	0,0	0,0	3,1
50	0,0	0,0	0,0	0,0

Tabela 4: Skuteczność rozpoznawania liter.


Rysunek 50: Skuteczność rozpoznawania liter.

Na rysunkach Rys. 51 - Rys. 54 przedstawiono wybrane wizualizacje działania sieci Hopfielda wykonane przy pomocy symulatora Snhop podczas rozpoznawania liter dla dopuszczalnego zaszumienia wyjścia θ_out=10 % (RH - Reguła Hebba, RWO - Reguła Wzajemnych Ograniczeń, RRD - Reguła Rzutowania Delta, ZRP - Zmodyfikowana Reguła Perceptronu).




Rysunek 51: Rozpoznawanie przez sieć uczoną RH przy θ_in=20 %.




Rysunek 52: Rozpoznawanie przez sieć uczoną RWO przy θ_in=20 %.




Rysunek 53: Rozpoznawanie przez sieć uczoną RRD przy θ_in=20 %.




Rysunek 54: Rozpoznawanie przez sieć uczoną ZRP przy θ_in=20 %.

Na podstawie uzyskanych wyników można stwierdzić, że, podobnie jak poprzednio dla liter i cyfr, uczenie sieci za pomocą klasycznej Reguły Hebba i Reguły Wzajemnych Ograniczeń dało mierne rezultaty. Zbiór liter alfabetu bez cyfr nadal stanowi zbiór wzorców rzadkich i skorelowanych. Zdecydowanie najskuteczniejsza okazała się Reguła Rzutowania Delta. Nieco gorszą skuteczność uzyskała Zmodyfikowana Reguła Perceptronu. Aby uzyskać zadowalającą skuteczność rozpoznawania, było konieczne użycie złożonych obliczeniowo metod z wielokrotną prezentacją wektorów uczących.

1. Rozpoznawanie cyfr

Badania rozpoznawania cyfr przeprowadzono dla zbioru uczącego 10-elementowego według specyfikacji „0-9”. Porównano cztery zaimplementowane metody uczenia z następującymi parametrami:

• Reguła Hebba,

• Reguła Wzajemnych Ograniczeń: λ = 0,8,

• Reguła Rzutowania Delta: η = 0,8, E = 1000,

• Zmodyfikowana Reguła Perceptronu: η = 0,8, E = 1000,

gdzie: λ, η - stałe uczenia,

E - liczba epok uczenia sieci.

Pozostałe parametry symulacji:

• wymiary siatkówki: x = 10, y = 10,

• zaszumienie wejścia: θ_in = <0;50〉 % z krokiem k = 10 %,

• dopuszczalne zaszumienie wyjścia: θ_out = 10 %,

• maximum rekurencji: R = 10,

• różne rodzaje funkcji aktywacji signum,

• próg przełączenia neuronu: BIAS = 0.

Zbiór obrazów użytych do uczenia sieci przedstawia Rys. 55.




Rysunek 55: Zestaw znaków dla rozpoznawania cyfr.

Uzyskane wyniki rozpoznawania cyfr przy dopuszczalnym zaszumieniu wyjścia θ_out=10 % przedstawiają Tab. 5 oraz Rys. 56.

θout=10 %	Skuteczność rozpoznawania [%]
θin [%]	Reg. Hebba	Reg. Wzaj. Ogr.	Reg. Rzut. Delta	Zmod. Reg. Perc.
0	0,0	0,0	100,0	100,0
10	0,0	0,0	100,0	34,0
20	0,0	0,0	96,0	34,0
30	0,0	0,0	66,0	14,0
40	0,0	0,0	12,0	12,0
50	0,0	0,0	0,0	0,0

Tabela 5: Skuteczność rozpoznawania cyfr.


Rysunek 56: Skuteczność rozpoznawania cyfr.

Na rysunkach Rys. 57 - Rys. 60 przedstawiono wybrane wizualizacje działania sieci Hopfielda wykonane przy pomocy symulatora Snhop podczas rozpoznawania cyfr dla dopuszczalnego zaszumienia wyjścia θ_out=10 % (RH - Reguła Hebba, RWO - Reguła Wzajemnych Ograniczeń, RRD - Reguła Rzutowania Delta, ZRP - Zmodyfikowana Reguła Perceptronu).




Rysunek 57: Rozpoznawanie przez sieć uczoną RH przy θ_in=20 %.




Rysunek 58: Rozpoznawanie przez sieć uczoną RWO przy θ_in=20 %.




Rysunek 59: Rozpoznawanie przez sieć uczoną RRD przy θ_in=20 %.




Rysunek 60: Rozpoznawanie przez sieć uczoną ZRP przy θ_in=20 %.

Na podstawie uzyskanych wyników można stwierdzić, że, podobnie jak poprzednio dla liter i cyfr, uczenie sieci za pomocą klasycznej Reguły Hebba i Reguły Wzajemnych Ograniczeń nie dało zadowalających rezultatów. Zbiór cyfr bez liter nadal stanowi zbiór wzorców rzadkich i skorelowanych. Zdecydowanie najskuteczniejsza okazała się Reguła Rzutowania Delta przewyższając nieco Zmodyfikowaną Regułę Perceptronu. Aby uzyskać zadowalającą skuteczność rozpoznawania, było konieczne użycie złożonych obliczeniowo metod z wielokrotną prezentacją wektorów uczących.

1. Rozpoznawanie znaków gęstych

Badania rozpoznawania znaków gęstych przeprowadzono dla zbioru uczącego 8-elementowego według specyfikacji „0+\1LKPA”. Porównano cztery zaimplementowane metody uczenia z następującymi parametrami:

• Reguła Hebba,

• Reguła Wzajemnych Ograniczeń: λ = 0,8,

• Reguła Rzutowania Delta: η = 0,8, E = 1000,

• Zmodyfikowana Reguła Perceptronu: η = 0,8, E = 1000,

gdzie: λ, η - stałe uczenia,

E - liczba epok uczenia sieci.

Pozostałe parametry symulacji:

• wymiary siatkówki: x = 10, y = 10,

• zaszumienie wejścia: θ_in = <0;50〉 % z krokiem k = 10 %,

• dopuszczalne zaszumienie wyjścia: θ_out = 10 %,

• maximum rekurencji: R = 10,

• różne rodzaje funkcji aktywacji signum,

• próg przełączenia neuronu: BIAS = 0.

Zbiór obrazów użytych do uczenia sieci przedstawia Rys. 61.




Rysunek 61: Zestaw znaków dla rozpoznawania znaków gęstych.

Uzyskane wyniki rozpoznawania znaków gęstych przy dopuszczalnym zaszumieniu wyjścia θ_out=10 % przedstawiają Tab. 6 oraz Rys. 62.

θout=10 %	Skuteczność rozpoznawania [%]
θin [%]	Reg. Hebba	Reg. Wzaj. Ogr.	Reg. Rzut. Delta	Zmod. Reg. Perc.
0	100,0	100,0	100,0	100,0
10	100,0	97.5	100,0	70,0
20	100,0	92.5	100,0	42.5
30	87.5	62.5	100,0	12.5
40	40,0	25,0	52.5	0,0
50	0,0	0,0	0,0	0,0

Tabela 6: Skuteczność rozpoznawania znaków gęstych.


Rysunek 62: Skuteczność rozpoznawania znaków gęstych.

Na rysunkach Rys. 63 - Rys. 66 przedstawiono wybrane wizualizacje działania sieci Hopfielda wykonane przy pomocy symulatora Snhop podczas rozpoznawania znaków gęstych dla dopuszczalnego zaszumienia wyjścia θ_out=10 % (RH - Reguła Hebba, RWO - Reguła Wzajemnych Ograniczeń, RRD - Reguła Rzutowania Delta, ZRP - Zmodyfikowana Reguła Perceptronu).




Rysunek 63: Rozpoznawanie przez sieć uczoną RH przy θ_in=20 %.




Rysunek 64: Rozpoznawanie przez sieć uczoną RWO przy θ_in=20 %.




Rysunek 65: Rozpoznawanie przez sieć uczoną RRD przy θ_in=20 %.




Rysunek 66: Rozpoznawanie przez sieć uczoną ZRP przy θ_in=20 %.

Na podstawie uzyskanych wyników można stwierdzić, że w przypadku mało licznej grupy różniących się od siebie znaków gęstych (znaków, w których prawdopodobieństwo wystąpienia piksela czarnego jest większe od 0,5) klasyczna Reguła Hebba wykazała się dużą zdolnością uczenia sieci, prowadzącą do wysokiej skuteczności rozpoznawania. Zaskakujące wyniki otrzymano dla modyfikacji Reguły Hebba czyli Reguły Wzajemnych Ograniczeń. Okazało się, że metoda ta jest bardzo wrażliwa na ustawienie współczynnika uczenia oraz że rezultaty rozpoznawania są zdecydowanie gorsze niż klasycznego prototypu. Z kolei dla jednej z metod wielokrotnego prezentowania wzorców, czyli Zmodyfikowanej Reguły Perceptronu, teoretycznie efektywniejszej od wyżej wymienionych metod, nieoczekiwanie uzyskano najgorsze rezultaty rozpoznawania. Najbardziej skuteczna okazała się Reguła Rzutowania Delta. Przy pomocy tej metody można odtwarzać rozpatrywaną grupę znaków przy 30% zaszumienia, a nawet z pewnymi błędami po zmianie 40% fragmentów obrazu. W przypadku znaków gęstych Reguła Hebba niewiele ustępuje Regule Rzutowania Delta.

1. Rozpoznawanie znaków rzadkich

Badania rozpoznawania znaków rzadkich przeprowadzono dla zbioru uczącego 7-elementowego według specyfikacji „1iIjJlL”. Porównano cztery zaimplementowane metody uczenia z następującymi parametrami:

• Reguła Hebba,

• Reguła Wzajemnych Ograniczeń: λ = 0,8,

• Reguła Rzutowania Delta: η = 0,8, E = 1000,

• Zmodyfikowana Reguła Perceptronu: η = 0,8, E = 1000,

gdzie: λ, η - stałe uczenia,

E - liczba epok uczenia sieci.

Pozostałe parametry symulacji:

• wymiary siatkówki: x = 10, y = 10,

• zaszumienie wejścia: θ_in = <0;50〉 % z krokiem k = 10 %,

• dopuszczalne zaszumienie wyjścia: θ_out = 10 %,

• maximum rekurencji: R = 10,

• różne rodzaje funkcji aktywacji signum,

• próg przełączenia neuronu: BIAS = 0.

Zbiór obrazów użytych do uczenia sieci przedstawia Rys. 67.


Rysunek 67: Zestaw znaków dla rozpoznawania znaków rzadkich.

Uzyskane wyniki rozpoznawania znaków rzadkich przy dopuszczalnym zaszumieniu wyjścia θ_out=10 % przedstawiają Tab. 7 oraz Rys. 68.

θout=10 %	Skuteczność rozpoznawania [%]
θin [%]	Reg. Hebla	Reg. Wzaj. Ogr.	Reg. Rzut. Delta	Zmod. Reg. Perc.
0	0,0	0,0	100,0	100,0
10	0,0	0,0	100,0	88.6
20	0,0	0,0	94.3	80,0
30	0,0	0,0	45.7	54.3
40	0,0	0,0	20,0	22.9
50	0,0	0,0	0,0	0,0

Tabela 7: Skuteczność rozpoznawania znaków rzadkich.


Rysunek 68: Skuteczność rozpoznawania znaków rzadkich.

Na rysunkach Rys. 69 - Rys. 72 przedstawiono wybrane wizualizacje działania sieci Hopfielda wykonane przy pomocy symulatora Snhop podczas rozpoznawania znaków rzadkich dla dopuszczalnego zaszumienia wyjścia θ_out=10 % (RH - Reguła Hebba, RWO - Reguła Wzajemnych Ograniczeń, RRD - Reguła Rzutowania Delta, ZRP - Zmodyfikowana Reguła Perceptronu).




Rysunek 69: Rozpoznawanie przez sieć uczoną RH przy θ_in=20 %.




Rysunek 70: Rozpoznawanie przez sieć uczoną RWO przy θ_in=20 %.




Rysunek 71: Rozpoznawanie przez sieć uczoną RRD przy θ_in=20 %.




Rysunek 72: Rozpoznawanie przez sieć uczoną ZRP przy θ_in=20 %.

Na podstawie uzyskanych wyników można stwierdzić, że w przypadku mało licznej grupy podobnych do siebie znaków rzadkich (znaków, w których prawdopodobieństwo wystąpienia piksela czarnego jest mniejsze od 0,5) Reguła Rzutowania Delta i Zmodyfikowana Reguła Perceptronu wykazały się dużą zdolnością uczenia sieci, prowadzącą do wysokiej skuteczności rozpoznawania, mimo dużego podobieństwa zaproponowanych wzorców. W przypadku testu dla znaków rzadkich wyniki zastosowania Zmodyfikowanej Reguły Perceptronu niewiele ustępują, a dla większego stopnia zakłóceń nawet nieco przewyższają rezultaty dotychczas najlepszej metody uczenia, czyli Reguły Rzutowania Delta.

1. Wnioski

Podczas badań za prawidłowe rozpoznanie obrazu przez sieć uznawano odległość odpowiedzi od wzorca nie większą niż ustalona wartość dopuszczalnego zaszumienia wyjścia. Z idealnym odtworzeniem obrazu uczącego mamy do czynienia przy zerowej odległości, odległość niezerowa może być jednak zaakceptowana w systemach filtrujących i zmniejszających zaszumienie danych wejściowych.

Zgodnie z oczekiwaniami najlepszą metodą pod względem skuteczności rozpoznawania okazała się Reguła Rzutowania Delta, a na drugim miejscu znalazła się Zmodyfikowana Reguła Perceptronu. Reguła Hebba i Reguła Wzajemnych Ograniczeń okazały się porównywalne ze sobą i możliwe do zastosowania tylko w bardzo ograniczonym zakresie - w przypadkach niezbyt rzadkich i ortogonalnych wzorców. Wyższa skuteczność nowszych metod offline okupiona jest koniecznością wielokrotnej prezentacji wzorców uczących, co zwiększa wymagania pamięciowe i czasowe procesu uczenia sieci Hopfielda.

Na podstawie dotychczasowych doświadczeń z testowanymi znakami można stwierdzić, że próby wykorzystywania sieci Hopfielda dla rozpoznawania wszystkich możliwych znaków alfabetu w danym zastosowaniu sieci nie rokują zbyt dużych sukcesów. Należy skupić się na małych grupach znaków i próbować uczyć sieć ich wzorcami w wielu wersjach, uwzględniając różne położenia na siatkówce. Takie podejście może być dobrym wstępem do bliskiego ideałowi rozpoznawania ręcznie pisanych znaków. Ponadto zbiór sieci rozpoznających różne grupy znaków, zwykle mylone przez standardowe algorytmy OCR, może funkcjonować w systemach hierarchicznych. Istnieje duża szansa uzyskania lepszego wyniku rozpoznawania po wprowadzeniu na wejście drugiej sieci takiego, już w mniejszym stopniu zaszumionego znaku. Na podstawie dotychczas przeprowadzonych testów można wnioskować, że taki system podwójnego poprawiania wzorca może być bardzo skutecznym systemem do rozpoznawania mało zróżnicowanych i zdeformowanych obrazów.

• Podsumowanie

Tematem niniejszej pracy było rozpoznawanie obrazów przy użyciu symulatora sieci Hopfielda. Wyznaczono w niej dwa zasadnicze cele:

• zbudowanie aplikacji do tworzenia i symulacji działania sieci neuronowych Hopfielda,

• zastosowanie symulatora do przeprowadzenia badań nad skutecznością rozpoznawania liter i cyfr przez sieci Hopfielda uczone różnymi metodami.

W związku z powyższymi założeniami pracę zrealizowano w dwóch etapach, tzn. przygotowano oprogramowanie symulacyjne Snhop, a następnie przeprowadzono testy sieci działających jako pamięci autoasocjacyjne. Program symulacyjny został zaimplementowany jako aplikacja dla środowiska Sun Java 2, dzięki czemu może on działać na komputerach bazujących na różnych platformach sprzętowych i systemach operacyjnych. Umożliwia on zaprojektowanie i przeprowadzenie symulacji działania sieci Hopfielda poprzez zbadanie skuteczności rozpoznawania obrazów przez sieć uzyskiwanej przy odpowiednio dobranych parametrach. Podczas tworzenia symulatora położono nacisk na zapewnienie prostoty obsługi i przyjaznego interfejsu użytkownika. Wyniki uzyskane podczas badań na symulatorze mogą zostać zachowane w sposób trwały i być wykorzystane do dalszych badań. Program symulacyjny daje możliwość definiowania rozmiaru rozpoznawanych obrazów, ustalenia parametru BIAS neuronów, wybrania funkcji aktywacji spośród trzech odmian funkcji signum, wybrania metody uczenia spośród czterech popularnych reguł i ustalenia generowanego losowo zaszumienia obrazów wejściowych oraz dopuszczalnego zaszumienia odpowiedzi sieci. Zestaw obrazów uczących dla programu tworzony jest na podstawie specyfikacji tekstowej podanej przez użytkownika lub ręcznie. Symulator przeprowadza na bieżąco wizualizację obrazów ze zbioru uczącego, testującego, wynikowego i rekurencyjnego sieci, a po zakończeniu symulacji generuje raport zawierający jej podsumowanie. Aplikacja Snhop może zostać w łatwy sposób rozbudowana, aby stać się uniwersalnym narzędziem pozwalającym na symulowanie sieci Hopfielda również dla innych, wymienionych w tej pracy, zastosowań takich jak rozwiązywanie problemu komiwojażera lub problemu określenia strategii gry. W tym celu należałoby dokonać następujących zmian i rozszerzeń:

• wprowadzenie możliwości wyboru innych funkcji aktywacji neuronu

(np. sigmoidalna, tangens hiperboliczny),

• wprowadzenie możliwości asynchronicznego uaktualniania stanu neuronów,

• zbudowanie modułu wizualizacji problemu komiwojażera na bazie wizualizatora rozpoznawania obrazów (klasa PatternContainer),

• zbudowanie modułu wizualizacji problemu określenia strategii gry na bazie wizualizatora rozpoznawania obrazów (klasa PatternContainer),

• wprowadzenie dalszych metod uczenia sieci Hopfielda, np. bazujących na wstępnej modyfikacji wzorców uczących (metody CEHAM).

Wyniki badań przeprowadzonych za pomocą symulatora Snhop pozwoliły na stwierdzenie, że sieć Hopfielda użyta do rozpoznawania nie ortogonalnego zbioru wzorców często uzyskiwała stan stabilny będący kompilacją wielu z nich. Efekt ten był szczególnie widoczny przy użyciu prostych metod uczenia sieci, bazujących na Regule Hebba. Jednakże pomimo tego zjawiska sieć Hopfielda może z powodzeniem spełniać zadania filtracji sygnału wejściowego i oczyszczania go z zakłóceń, gdy przy odpowiednio dobranych parametrach odległości odpowiedzi sieci od wzorców uczących są mniejsze niż od zakłóconych sygnałów wejściowych. Z czterech przebadanych metod najlepszą pod względem skuteczności rozpoznawania okazała się Reguła Rzutowania Delta, następnie Zmodyfikowana Reguła Perceptronu. Reguła Hebba i Reguła Wzajemnych Ograniczeń są porównywalne ze sobą i skuteczne jedynie w przypadku specyficznych zbiorów wzorców uczących (np. znaki gęste). Wyższa skuteczność nowszych metod offline okupiona jest koniecznością wielokrotnej prezentacji wzorców uczących, co zwiększa wymagania pamięciowe i czasowe procesu uczenia. Ostatecznie stwierdzono, że wykorzystywanie sieci Hopfielda do rozpoznawania obrazów w celu osiągnięcia zadowalających efektów powinno być realizowane poprzez użycie wielu podsieci uczonych na mało licznych grupach słabo skorelowanych i możliwie gęstych obrazów.

Badania wykonane przy pomocy symulatora zaowocowały referatem [8] przedstawionym na seminarium wyjazdowym Katedry Automatyki AGH i Katedry Informatyki Stosowanej Politechniki Łódzkiej pt. „Przetwarzanie i analiza sygnałów w systemach wizji i sterowania”.

Bibliografia

1. Aho A. V., Hopcroft J. E., Ullman J. D., Projektowanie i analiza algorytmów komputerowych, Państwowe Wydawnictwa Naukowe, 1993

2. Beale R., Jackson T., Neural Computing, An Introduction, A.Hilger IOP Publ. Co., Bristol, 1990

3. Cichocki A., Unbehauen R., Neural Networks for Optimization and Signal Pro­cessing, J.Wiley and Sons, 1993

4. Duch W., Korbacz J., Rutkowski L., Tadeusiewicz R., Sieci neuronowe w modelowaniu zaburzeń neuropsychologicznych i chorób psychicznych, Tom 6: Sieci neuronowe, Biocybernetyka 2000

5. Filipowicz B., Badania operacyjne. Wybrane metody obliczeniowe i algorytmy cz. 1, F. H. U. Poldex, Kraków, 1997

6. Freeman J.A., Skapura D.M., Neural Networks. Algorithms, Applications, and Programming Techniques, Addison-Wesley, 1991

7. Goldberg D. E., Algorytmy genetyczne i ich zastosowania, Wydawnictwa Naukowo-Techniczne, wyd. II, Warszawa, 1998

8. Grabska-Chrząstowska J., Macnar M., Odtwarzanie zniekształconych znaków przy pomocy sieci Hopfielda, Seminarium „Przetwarzanie i analiza sygnałów w systemach wizji i sterowania", Słok k/Bełchatowa, maj 2002

9. Hertz J., Krogh A., Palmer R.G., Wstęp do teorii obliczeń neuronowych, Wydawnictwa Naukowo-Techniczne, 1993

10. Korbicz J., Obuchowicz A., Uciński D., Sztuczne sieci neuronowe. Podstawy i zastosowania, Akademicka Oficyna Wydawnicza PLJ, Warszawa, 1994

11. Mańdziuk J., Sieci neuronowe typu Hopfielda, Akademicka Oficyna Wydawnicza EXIT, Warszawa, 2000

12. Michalewicz Z., Algorytmy genetyczne + struktury danych = programowanie ewolucyjne, Wydawnictwa Naukowo-Techniczne, Warszawa, 1996

13. Osowski S., Sieci neuronowe, Oficyna Wydawnicza Politechniki Warszawskiej, Warszawa, 1994

14. Osowski S., Sieci neuronowe do przetwarzania informacji, Oficyna Wydawnicza Politechniki Warszawskiej, Warszawa, 2000

15. Osowski S., Sieci neuronowe w ujęciu algorytmicznym, Wydawnictwa Naukowo-Techniczne, wyd. II, Warszawa, 1996

16. Rutkowska D., Piliński M., Rutkowski L., Sieci neuronowe, algorytmy genetyczne i systemy rozmyte, Państwowe Wydawnictwa Naukowe, Warszawa, 1997

17. Tadeusiewicz R., Elementarne wprowadzenie do techniki sieci neuronowych z przykładowymi programami, Akademicka Oficyna Wydawnicza PLJ, Warszawa, 1998

18. Tadeusiewicz R., Sieci neuronowe, Akademicka Oficyna Wydawnicza RM, Warszawa, 1993

19. Wierzbicki A., Findeisen W., Szymanowski J., Teoria i metody obliczeniowe optymalizacji, Wydawnictwa Naukowo-Techniczne, Warszawa, 1977

20. Żurada J., Barski M., Jędruch W., Sztuczne sieci neuronowe, Państwowe Wydawnictwa Naukowe, Warszawa, 1996

Dodatek A - Opis formatu plików typu „hop”

Symulator Snhop używa plików „hop” do przechowywania projektów sieci Hopfielda. Dyskretne wartości wyjściowe neuronów 1 i -1 są przechowywane jako 1 i 0 w celu uproszczenia zapisu. Pliki „hop” mają następującą strukturę blokową:

LP.	NAZWA	OPIS
1	Nagłówek	Wiersz zakończony znakiem nowej linii zawierający słowo Snhop.
2	Parametry	Wiersz zakończony znakiem nowej linii zawierający oddzielone znakiem „:”: słowo PAR, kod metody uczenia (0 - RH,1 - RWO,2 - RRD,3 - ZRP), stałe uczenia dla metod RWO,RRD,ZRP, liczby epok uczenia dla metod RRD, ZRP, wymiary poziomy i pionowy obrazów, zaszumienie wejścia i wyjścia, maksimum rekurencji, specyfikację wstawiania wzorców automatycznych, liczbę wzorców uczących, odmianę funkcji aktywacji (0 - dolna,1 - z pamięcią,2 - górna), BIAS.
3	Obrazy uczące, testujące i wynikowe	Blok wierszy zakończonych znakiem nowej linii zawierający w każdym wierszu oddzielone znakiem „:”: słowo PAT, znak generacji wzorca lub spację w przypadku wzorca ręcznego, ciąg zero-jedynkowy wszystkich pikseli obrazu uczącego (wierszami), ciąg zero-jedynkowy wszystkich pikseli obrazu testującego (wierszami), ciąg zero-jedynkowy wszystkich pikseli obrazu wynikowego (wierszami), kod RGB koloru wskaźnika poprawności rozpoznania obrazu wynikowego.
4	Obrazy rekurencyjne	Blok wierszy zakończonych znakiem nowej linii zawierający w każdym wierszu oddzielone znakiem „:”: słowo REC, ciąg zero-jedynkowy wszystkich pikseli obrazu rekurencyjnego (wierszami).
5	Macierz wag	Blok wierszy zakończonych znakiem nowej linii zawierający w każdym wierszu oddzielone znakiem „:” wagi z kolejnych wierszy symetrycznej macierzy wag sieci.
6	Separator	Wiersz zakończony znakiem nowej linii zawierający słowo RAPORT.
7	Raporty	Blok wierszy zawierający w formacie HTML tabele raportów wyświetlane na zakładce Wyniki symulatora.

Dodatek B - Opis formatu plików typu „set”

Symulator Snhop używa plików „set” do przechowywania zbiorów uczących, testujących i wynikowych sieci Hopfielda. Dyskretne wartości wyjściowe neuronów 1 i -1 są przechowywane jako 1 i 0 w celu uproszczenia zapisu. Pliki „set” mają następującą, powtarzalną dla każdego obrazu, strukturę blokową:

LP.	NAZWA	OPIS
1	Pojedynczy obraz zbioru uczącego, testującego lub wynikowego	Blok wierszy zakończonym znakiem nowej linii zawierający w każdym wierszu ciąg zero-jedynkowy kolejnego wiersza pikseli obrazu (od góry).
2	Separator	Wiersz pusty zakończony znakiem nowej linii.

Przykładowy zapis zbioru uczącego według specyfikacji „012” (¶ - znak nowej linii):

0000000000¶

0001111000¶

0011001100¶

0011001100¶

0011001100¶

0011001100¶

0011001100¶

0001111000¶

0000000000¶

0000000000¶

¶

0000000000¶

0000110000¶

0001110000¶

0000110000¶

0000110000¶

0000110000¶

0000110000¶

0001111000¶

0000000000¶

0000000000¶

¶

0000000000¶

0001111000¶

0010001100¶

0010001100¶

0000011000¶

0000110000¶

0001100000¶

0011111100¶

0000000000¶

0000000000¶

¶

Dodatek C - Zawartość dołączonego nośnika CD

Dołączony do niniejszej pracy nośnik CD zawiera zbiory elektroniczne związane z realizowaniem pracy, podzielone na następujące grupy:

• dokumenty (w katalogu /Doc/),

• programy instalacyjne (w katalogu /Install/),

• program symulacyjny Snhop (w katalogu /Program/),

• źródła programu symulacyjnego Snhop (w katalogu /Source/),

• badania (w katalogu /Lab/).

PLIK	ROZM. [B]	FORMAT	OPIS
/Doc/snhop.doc	5691392	MS Word 97-2002	Niniejsza praca w formie elektronicznej
/Doc/snhop.mdl	229776	Model Rational Rose	Model UML aplikacji symulatora Snhop
/Install/j2re-1_3_1_04-windows-i586.exe	9107504	Aplikacja Win32	Instalator środowiska Sun Java 2 RE 1.3.1
/Install/jcreator200LE.zip	1930268	Archiwum ZIP	Instalator edytora Java JCreator LE 2.00
/Lab/cyfry.hop	80253	Sieć Snhop	Rozpoznawanie cyfr, zbiór uczący
/Lab/cyfry.set	110	Zbiór Snhop
/Lab/geste.hop	78287	Sieć Snhop		Rozpoznawanie zn. gęstych, zbiór uczący
/Lab/geste.set	444	Zbiór Snhop
/Lab/litery.hop	96434	Sieć Snhop		Rozpoznawanie liter, zbiór uczący
/Lab/litery.set	4107	Zbiór Snhop
/Lab/rzadkie.hop	75740	Sieć Snhop		Rozpoznawanie zn. rzadkich, zbiór uczący
/Lab/rzadkie.set	777	Zbiór Snhop
/Lab/siec1.hop	96620	Sieć Snhop		Rozpoznawanie liter i cyfr, zbiory uczące, dla różnych wartości dopuszczalnego zaszumienia wyjścia
/Lab/siec1.set	2331	Zbiór Snhop
/Lab/siec2.hop	99147	Sieć Snhop
/Lab/siec2.set	2331	Zbiór Snhop
/Lab/siec3.hop	100246	Sieć Snhop
/Lab/siec3.set	2331	Zbiór Snhop
/Program/snhop.jar	175604	Archiwum Java	Aplikacja symulatora Snhop
/Source/res/close.gif	1154	Pliki graficzne GIF	Zasoby graficzne aplikacji symulatora Snhop
/Source/res/h.gif	866
/Source/res/help.gif	118
/Source/res/new.gif	915
/Source/res/open.gif	1132
/Source/res/start.gif	873
/Source/res/stop.gif	888
/Source/snhop/AbstractPattern.java	2630			Pliki źródłowe Java	Pliki źródłowe aplikacji symulatora Snhop
/Source/snhop/Hopfield.java	8231
/Source/snhop/HopfieldObserver.java	587
/Source/snhop/InputPattern.java	686
/Source/snhop/LearnPattern.java	2007
/Source/snhop/OutputPattern.java	1306
/Source/snhop/PatternContainer.java	10616
/Source/snhop/RecurPattern.java	733
/Source/snhop/Snhop.java	54250
/Source/help/about.gif	3069			Pliki graficzne GIF, pliki hipertekstowe HTM	Pomoc aplikacji symulatora Snhop
/Source/help/content.htm	1447
/Source/help/index.htm	4425
/Source/help/instrukcja.gif	24928
/Source/help/main.htm	15497
/Source/help/napewno.gif	1679
/Source/help/otworz.gif	6613
/Source/help/parametry.gif	23874
/Source/help/pasek.gif	4963
/Source/help/symulacja.gif	32301
/Source/help/usunac.gif	2536
/Source/help/wartosc.gif	1868
/Source/help/wyniki.gif	21030
/Source/help/zapisac.gif	1772
/Source/help/zapisz.gif	6623
/Source/make.bat	102	Plik wsadowy		Pliki projektu aplikacji symulatora Snhop dla edytora Java JCreator LE 2.00
/Source/manifest.mf	91	Manifest JAR
/Source/snhop.jcp	1432	Projekt JCreator
/Source/snhop.jcw	263	Środowisko projektu JCreator
/Source/snhop2.jcw	266
/Source/src_snhop.txt	586

Są to problemy należące do klasy P i NP. W celu sformalizowania i ujednolicenia badania złożoności problemów optymalizacyjnych wprowadza się pojęcia Deterministycznej Maszyny Turinga (ang. DTM - Deterministic Turing Machine) i Niedeterministycznej Maszyny Turinga (ang. NDTM - Nondeterministic Turing Machine). Pierwsza z nich odpowiada komputerowi sekwencyjnemu, natomiast druga dowolnie dużej, ale skończonej liczbie kopii DTM pracujących równolegle. W kontekście wymagań czasowych wyróżnia się dwie podstawowe klasy problemów: P (ang. Polynomial) - problemy, dla których istnieje algorytm rozwiązujący je za pomocą DTM w czasie wielomianowo zależnym od rozmiaru problemu oraz NP (ang. Nondeterministic Polynomial) - problemy, dla których istnieje algorytm rozwiązujący je za pomocą NDTM w czasie wielomianowo zależnym od rozmiaru problemu. Z definicji P⊂NP, natomiast nierówność P≠NP jest nierozstrzygnięta, zatem teoretycznie dla każdego problemu klasy NP (np. problem komiwojażera) istnieje możliwość znalezienia algorytmu klasy P.

Wśród czterech zaimplementowanych w symulatorze metod uczenia sieci Hopfielda dwie pierwsze to podstawowa Reguła Hebba (ang. Hebbian Rule) i jej modyfikacja - Reguła Wzajemnych Ograniczeń (ang. Mutual Inhibition Rule), natomiast dwie dalsze, historycznie późniejsze to metody wykorzystujące wielokrotną prezentację wzorców uczących, bardziej złożone obliczeniowo, ale prowadzące do uzyskania dużo lepszych efektów uczenia sieci - Reguła Rzutowania Delta (ang. Delta Pseudoinversion Rule) i Zmodyfikowana Reguła Perceptronu (ang. Modified Perceptron Rule).

Jedną z podstawowych zalet rzeczywistych (a nie symulowanych programowo) sieci neuronowych jest silnie równoległe przetwarzanie informacji (ang. Massive Parallel Processing), która to cecha zostaje utracona w momencie modelowania sieci neuronowej na komputerze sekwencyjnym. Jednak nic nie stoi na przeszkodzie, aby badać skuteczność algorytmów uczenia sieci neuronowych za pomocą takich symulatorów, pamiętając o odmiennych uwarunkowaniach czasowych modelu i rzeczywistej sieci.

Taka redukcja jest możliwa, gdyż dowolną liniową funkcję aktywacji można zamodelować za pomocą odpowiednich wag wejść neuronu liniowego. Nie istnieje potrzeba uwzględniania funkcji aktywacji g w działaniu neuronu liniowego, a jego odpowiedź można utożsamiać z potencjałem wewnętrznym p.

Jako metodę wyboru neuronu przyjmuje się najczęściej losowanie indeksu według rozkładu jednostajnego bądź wybór indeksu według cyklicznie stosowanej permutacji indeksów neuronów.

Tą cechę sieci neuronowych wykorzystuje się powszechnie stosując je do sterowania ramieniem robota. Są one wtedy alternatywą dla wykonywania bardzo złożonych tensorowych obliczeń, które uzyskiwane tradycyjnymi metodami często w momencie otrzymania wyniku są już nieaktualne i ze względu na to bezużyteczne.

W celu uproszczenia obliczeń zakłada się, że wymuszenie zewnętrzne działa jedynie w chwili początkowej i służy inicjalizacji sieci neuronowej, natomiast w każdym następnym kroku czasowym przyjmuje się je za równe 0.

Spotyka się definicję metod online jako wymagających spełnienia słabszego warunku, że wzorce uczące są prezentowane jeden po drugim. Według takiej definicji metody wymagające wielokrotnych kolejnych prezentacji wzorców będą metodami online.

Badania rozpoznawania obrazów przez sieć Hopfielda przeprowadzone na symulatorze sieci Hopfielda opisane są w rozdziale 5.

Opis symulatora Snhop znajduje się w rozdziale 4, a badania nad rozpoznawaniem obrazów i rekurencją w sieciach Hopfielda przeprowadzone za jego pomocą przedstawiono w rozdziale 5.

Centralny procesor komputera (ang. Central Processing Unit).

Pamięć operacyjna, o dostępie swobodnym (ang. Random Access Memory).

Środowisko uruchomieniowe Java 2 Runtime Environment firmy Sun.

Graficzny interfejs użytkownika (ang. Graphics User Interface).

Zunifikowany język modelowania obiektowego (ang. Unified Modelling Language).

Patrz Dodatek C - Zawartość dołączonego nośnika CD.

Liczba neuronów sieci to iloczyn wymiaru poziomego i pionowego.

Wartość dopuszczalna, do której zakłócona odpowiedź będzie traktowana jako prawidłowa.

Pozwala na wybranie wariantu funkcji aktywacji signum o zbiorze wartości {-1,1} różniące się ze względu na wartość funkcji od zera.

Wyjątek stanowi funkcja Uczenie i rozpoznawanie, uruchamiająca kolejno po sobie te dwa procesy, dostępna poprzez przycisk Uczenie i rozpoznawanie na pasku narzędzi.

Patrz Dodatek A - Opis formatu plików typu „hop”.

Patrz Dodatek B - Opis formatu plików typu „set”.

W momencie modyfikacji zbioru uczącego wszelkie wagi sieci neuronowej uzyskane uprzednio w procesie uczenia stają się nieaktualne, zatem nie ma sensu obserwowanie zbioru rekurencyjnego i jego odległości od zbioru uczącego przed ponownym nauczeniem sieci.

Zbiór rekurencyjny jest definiowany jako zbiór wszystkich kolejnych etapów przetwarzania danego wektora wejściowego aż do uzyskania stanu stabilnego sieci lub przekroczenia maksymalnej dopuszczalnej wartości rekurencji sieci.

Z teorii sieci Hopfielda wynika, że dążenie do atraktorów wzorców uczących jak i ich negatywów odpowiadających tej samej wartości energii sieci może być osiągane tak samo często przez gradientowy algorytm przetwarzania minimalizujący energię sieci.

Skrót OCR oznacza systemy rozpoznawania pisma (ang. Optical Character Recognition).

Poprawiająca sieć drugiego poziomu mogłaby być nauczona tym samym zestawem znaków, ale przy pomocy innej metody, nawet nieco gorszej, a więc wymagającej już mniejszych nakładów obliczeniowych podczas uczenia.

Mateusz Macnar

76

...

w₀

w₁

w_M

Wy

y

We

x₀

x₁

x_M

...

...

Neuron

...

y₁

y₂

y_N

n₁

n₂

n_N

x₂

x₁

x_N






















Rozpoznawanie obrazów przy użyciu symulatora sieci Hopfielda

---