1. Dany jest automat komórkowy o funkcji przejścia przedstawionej na rysunku, gdzie liczby przy węzłach oznaczają liczbę
sąsiednich komórek w stanie 1, zaś sąsiedztwem komórki są wszystkie komórki przylegające do niej bokami i
wierzchołkami. Należy wyznaczyć (narysować) stany następne od stanu przedstawionego na rysunku w trzech kolejnych
taktach zegarowych. Graf do zadania wygląda następująco:
Z grafu wynika, że kratka oznaczona jako pusta ma stan  0 , natomiast pełne mają stan  1 . Przejście z kratki pustej na pełną
następuje, gdy kratka otoczona jest 3 kratkami pełnymi.
Mamy konfigurację stabilną.
2. W pewnym momencie działania algorytmu symulowanego wyżarzania poszukującego minimum, przy temperaturze T,
będąc w punkcie w wylosowano nowy punkt w . Wartościami kryterium w tych punktach były odpowiednio E(w) i E(w ).
Obliczono różnicę między tymi wartościami jako "E = E(w )  E(w). Należy w przybliżeniu określić prawdopodobieństwo
akceptacji punktu w w zależności od wartości "E i T poprzez wpisanie w wolnych miejscach podanej tablicy przymiotników
spośród: H"0, małe, średnie, duże, H"1.
"E temperatura T prawd. akceptacji
1 1
<< 0 niska H" 1 (0,966) k "E,T = H"
( )
"E "E
<< 0 średnia duże (0,881)
1+ exp�ł �ł 1+ exp�ł �ł
�ł �ł �ł �ł
CT T
�ł łł �ł łł
<< 0 wysoka duże (0,731)
< 0 niska średnie (0,542)
< 0 średnia średnie (0,525)
< 0 wysoka średnie (0,512)
> 0 niska średnie (0,458)
> 0 średnia średnie (0,475)
> 0 wysoka średnie (0,488)
>> 0 niska H" 0 (0,034)
>> 0 średnia małe (0,119)
>> 0 wysoka małe (0,269)
3. Wyznacz wartości wag sieci neuronowej klasyfikującej kółka i trójkąty (rysunek).
Prowadzimy proste rozdzielające oba typy figur. Proste te muszą być równoległe i
zawierać się możliwie  centralnie pomiędzy typami figur.
Następnie wagi sieci wyznaczamy z równań prostych:
x2 = -2x1 + 4 2x1 + x2 - 4 = 0
ńł ńł

�ł �ł
= -2x1 + 6 + x2 - 6 = 0
ółx2 ół2x1
Stąd wagi sieci neuronowej są równe:
w11 = 2 w12 = 1 w13 = -4
w21 = 2 w22 = 1 w23 = -6
4. Zaznacz zbiór punktów na płaszczyz
nie xy, którym sieć neuronowa o progowej unipolarnej funkcji aktywacji przypisze
wartość 1.
Na podstawie schematu piszemy równania prostych:
0x + y -1 = 0 y =1 y d" 1
ńł ńł ńł
�!
�ł1x - y -1 = 0 �! �ł �ły
y = x -1 e" x -1
ół ół ół
Rysujemy wykres i zaznaczamy zbiór punktów:
5. Na rysunku pokazano stan początkowy problemu poszukiwania centrów klastrów, gdzie krzyżyki oznaczają zadane
punkty, a kółeczka oznaczają aktualne (prowizoryczne) położenia centrów klastrów. Należy dorysować trajektorie położenia
centrów klastrów przebyte w trakcie jednego cyklu metody  zwycięzca bierze wszystko . Kolejność pobudzania oznaczona
jest liczbami, a współczynnik korekcji wynosi 0,33.
Kółka będą przyciągane przez kolejne  x , ale przyciągnięta w danym takcie
będzie tylko to kółko, które jest najbliżej danego klastru. Współczynnik korekcji
oznacza procent drogi jaką przemierzy kółko w kierunku danego  x zanim się
zatrzyma.
6. Na podstawie danych z tablicy utwórz drzewo decyzyjne za pomocą algorytmu wykorzystującego entropię (algorytm ID3).
Różnice wielkości entropii są na tyle duże, że nie trzeba wyliczać dokładnie wartości logarytmów.
a1 a2 a3 klasa
1 1 0 0
1 1 1 0
1 0 1 0
0 0 1 1
0 1 1 1
1 0 0 1
0 1 0 1
7. Pokaż graficznie, na kilku kluczowych przykładach, że wymiar VC (VC dimension) maszyny sgn (w1x12+w2x1+w3-x2) jest
większy lub równy 4.
+1 x e" 0
ńł
sgn = w1x12 + w2x1 + w3 - x2 = 0 x2 = w1x12 + w2x1 + w3
- parabola
�ł
ół-1 x < 0
Trzeba pokazać, że parabola z uzyskanego równania rozdziela 4 punkty (jest 16 takich przypadków).
8. Na rysunku przedstawiona jest sieć neuronowa o dwóch wejściach x1 i x2 zbudowana z neuronów o bipolarnych
skokowych funkcjach aktywacji:
+1 net e" 0
ńł
f (net) =
�ł-1 net < 0
ół
Należy wyznaczyć odpowiedz
na sygnały wejściowe:
x1, x2 = [1,5 1,2], [1,5 3], [-1 3], [2 -3]  ocena za prawidłową odpowiedz
 50%
Na płaszczyz
nie x1, x2 zaznaczyć obszar dla którego odpowiedz
sieci wynosi +1  ocena za prawidłową odpowiedz
 100%
1) Sposób (50%)  liczenie ręczne
n
nat = xi = w1x1 + w2x2 + ...+ wnxn
"w
i
i=1
y = f (net)
Odpowiedz
ręczna -
Obliczenia dla pierwszego przypadku czyli x1, x2 = [1,5 1,2]
f (net1) =1
net1 = (1,5�"-1) + (1, 2�"0) + (1�"2) = 0,5
f (net2) = 1
net2 = (1,5�"0) + (1, 2�"1) + (1�" -1) = 0, 2
net3 = (1,5�"1) + (1,2�" -1) + (1�"0) = 0,3 f (net3) = 1
net4 = (1�"1) + (1�"1) + (1�"1) + (1�" -2,5) = 0,5 f (net4) = 1
*
Itd. dla pozostałych danych x1, x2. Odpowiedz
dla x1,x2 = [1,5 1,2] to 1.
2) Sposób (100%)  obszar na płaszczyz
nie
Równanie (wszystkie wagi wchodzące do danego neuronu):
ńł-1�" x1 + 0�" x2 + 2 = 0 x1 = 2
ńł
�ł0�" x1 +1�" x2 -1 = 0 �! �łx = 1 Wiemy, że 4 neuron zwraca jedynkę tylko wtedy, gdy na jego wejściach są trzy
�ł �ł
2
 1 z neuronów 1,2,3, patrz (*). W innych przypadkach na wyjściu będzie  -1
�ł1�" x1 -1�" x2 + 0 = 0 �łx = x1 zatem równania będą mieć postać:
ół ół 2
ńł-x1 + x2 + 2 e" 0 x1 d" 2
ńł
�łx -1 e" 0 �łx
�! e" 1
�ł �ł
2 2
�łx - x2 e" 0 �łx d" x 1
ół 1 ół 2
9. Na podanym rysunku zaznaczono kilka kolejnych kroków pewnej metody szukania minimum funkcji. Jaka to mogłaby być
metoda (metody) ? Napisz 4 zdania zaczynające się następująco:
(Nie) może to być metoda gradientowa bo linie łączące kolejne kroki nie są
prostopadłe do poziomic.
(Nie) Może to być metoda ewolucyjna bo każdy kolejny krok jest lepszy od
poprzedniego.
(Nie) Może to być metoda szukania przypadkowego bo algorytm w kolejnych
krokach jest malejący.
(Nie) Może to być metoda symulowanego wyżarzania bo algorytm w tej metodzie
może zarówno rosnąć jak i maleć.
10. Jak zasada  brzytwy Ockhama przekłada się na algorytm konstrukcji drzewa decyzyjnego?
Zasada brzytwy Ockhama mówi, że bytów nie należy mnożyć więcej niż jest potrzeba. W odniesieniu do drzew decyzyjnych
zasada ta mówi:
* określ korzeń drzewa jako zmienną, która ma największy wpływ na podejmowaną decyzję (ma małą entropię ważoną)
* kolejne fragmenty drzewa to zmienne, które mają największy wpływ na decyzję zaraz po decyzji najważniejszej (korzeniu)
Przy wyznaczaniu wpływu kolejnych zmiennych bierzemy pod uwagę tylko te obszary, które spełniają warunki dostania się do
określonego węzła drzewa.
11. Jakie parametry zmienione są przy uczeniu sieci neuronowych, a jakie przy uczeniu systemów rozmytych (ANFIS) i czym
się różnią standardowe metody uczenia tych systemów.
* uczenie sieci neuronowych  zmieniane parametry to wartości wag neuronów
* uczenie systemów rozmytych  zmieniane parametry to zbiór parametrów konsekwencji oraz parametrów przesłanek
Uczenie się sieci neuronowych polega na doborze wag neuronów tak aby w efekcie końcowy błąd popełniony przez
sieć był mniejszy od zadanego.
Uczenie się ANFIS polega na znajdowaniu odpowiedniej funkcji na podstawie parametrów konsekwencji i przesłanek w
procesie uczenia z nauczycielem. Każdy cykl nauki podzielony jest na dwa etapy. W etapie 1) parametry konsekwencji są
wyznaczane metodą najmniejszych kwadratów, a w etapie 2) parametry przesłanek wyznaczane są metodą gradientową
(propagacji wstecznej).
Sieci neuronowe stosują metody algebraiczne (statyczne), a systemy rozmyte metody analityczne (całki).
12. Omów krótko dwie modyfikacje metody najszybszego spadku (metoda gradientowa) zwiększające jej szybkość
zbieżności do ekstremum.
1) Metoda parametru �:
* jeżeli błąd uczenia maleje to należy zwiększyć współczynnik � o małą wartość
* jeżeli błąd uczenia rośnie to należy pomnożyć współczynnik � o liczbę mniejszą od 1
2) Metoda momentu:
"�(k) = -� �""E(k) +ą"�(k -1)
13. Dlaczego stosuje się iteracyjne algorytmy uczenia, a nie przyrównywanie pochodnej do zera ?
Metody analityczne (przyrównywanie pochodnej do zera) często nie mają praktycznego zastosowania ze względu na
nieliniowość funkcji i występowanie licznych ekstremów lokalnych. Ciężko jest uzyskać równania w postaci jawnej albo liczba
uzyskanych rozwiązań jest bardzo duża. Dlatego do szukania ekstremów lepiej stosować algorytmy iteracyjne (symulowane
wyżarzanie, algorytm genetyczny, itd.)
Nieco samej teorii
1. Metody uczenia.
Uczenie to znalezienie maszyny realizującej odwzorowanie x d. Zadanie uczenia polega na znalezieniu funkcji y = f (x, w):
x  jakiś wektor, d  stwierdzenie czy wektor x coś przedstawia, w  wektor parametrów.
p (x, d)  wektor prawdopodobieństwa wektora x i sygnału d
E(w) = � (y - d)2 = - d)2 p(x, d)dxdd = f (x, w) - d]2 p(x, d)dxdd - błąd systemu
+"(y +"[
* Uczenie z nauczycielem:
Znaną pary uczące, czyli sygnał wejściowy xi i poprawna odpowiedz
di
* Uczenie z krytykiem:
Nie dysponujemy parami uczącymi natomiast dla każdej pary: sygnału wejściowego xi i odpowiedzi yi = f(xi, w), otrzymujemy
ocenę odpowiedzi. Ocena pochodzi od środowiska w którym działa system uczący się i na ogół nie jest znana jej analityczna
zależność od sygnałów x i y. Uczenie z krytykiem ma miejsce w tzw. wieloetapowych procesach decyzyjnych gdzie po ciągu
decyzji otrzymujemy ocenę tego ciągu bez wskazania jaki powinien być.
* Uczenie bez nadzoru:
W czasie uczenia bez nadzoru dysponujemy tylko sygnałami wejściowymi xi, nie znamy związanych z nimi poprawnych
odpowiedzi, ani nie znamy błędu podejmując jakąś decyzję. Uczenie to nazywa się czasami samoorganizacją i zazwyczaj polega
na znajdywaniu centrów skupisk (klastrów) sygnałów wejściowych.
2. Generalizacja.
Generalizacja jest to zdolność systemu uczącego do poprawnego działania gdy wejściowe sygnały różne są od sygnałów
stosowanych w procesie uczenia.
3. Metody iteracyjne szukania ekstremum.
"E
�ł łł
* Metoda gradientowa (metoda najszybszego spadku): (2)
�ł"w śł
1
1) Losowy wybór punktu startowego w.
�ł śł
2) Obliczenie gradientu funkcji E(w) w punkcie w.
"E(w) = �ł�" śł
2
w = w -�"E(w)
3) Wyznaczenie nowego punktu według wzoru (�  współczynnik korekcji): �ł śł
"E
�ł śł
4) Sprawdzenie warunku zatrzymania (numer kroku lub wartość funkcji E(w)).
�ł śł
Jeżeli warunek nie jest spełniony to skok do kroku 2.
n
�ł"w �ł
5) Zakończenie algorytmu.
�0
Aproksymacja stochastyczna
�k =
Aproksymacja stochastyczna jest metodą gradientową ze współczynnikiem korekcji zmienianym według wzoru:
k
gdzie k jest numerem kroku. Malejący w ten sposób współczynnik korekcji zapewnia wytłumienie błędów, a jednocześnie
umożliwia przesunięcie się punktu w od dowolnej wartości początkowej do ekstremum. Przyspieszanie zbieżności:
1. Metoda parametru �:
- jeżeli błąd uczenia monotonicznie maleje to należy zwiększyć współczynnik � o małą wartość
- jeżeli błąd uczenia rośnie to należy pomnożyć współczynnik � o liczbę mniejszą od 1
2. Metoda momentu:
"�(k) = -� �""E(k) +ą"�(k -1)
3. Metoda Levenberga-Marquarda
* Szukanie przypadkowe:
1) Losowy wybór punktu startowego w, przyjęcie licznika iteracji k = 1.
2) Wyznaczenie wartości funkcji E(w).
3) Wyznaczenie punktu w = w + "w, gdzie "w jest realizacją zmiennej losowej o rozkładzie normalnym (�  wariancja (stała))
�ł-
łł
g("w,� ) = (2Ą� )-n / 2 exp | "w |2 /(2� )�ł
�ł
4. Wyznaczenie wartości funkcji E(w ) i "E = E(w ) - E(w).
5. Gdy "E < 0, to podstawienie w �! w
6. k �! k+1. Jeżeli k osiągnęło przyjętą wartość lub E(w) jest mniejsze od założonej wartości, to zakończenie obliczeń; w
przeciwnym przypadku skok do 3.
Symulowane wyżarzanie
Symulowane wyżarzanie jest odmianą metody szukania przypadkowego.
1) Losowy wybór punktu startowego w; przyjęcie współczynnika T = Tmax nazywanego temperaturą;
przyjęcie licznika iteracji k = 1.
2) Wyznaczenie wartości funkcji E(w).
3) Wyznaczenie punktu w = w + "w, gdzie "w jest realizacją zmiennej losowej o rozkładzie normalnym
�ł-
łł
g("w,T ) = (2ĄT )-n / 2 exp | "w |2 /(2T )�ł
�ł
4) Wyznaczenie wartości funkcji E(w ).
5) Podstawienie w �! w z prawdopodobieństwem danym rozkładem Boltzmanna (gdzie "E = E(w ) - E(w), a c  jest stałą)
1
h("E,T ) =
1+ exp("E /(cT ))
6) Zmniejszenie temperatury T; zwykle T �! �T (gdzie � jest stałą z przedziału 0,1).
7) k �! k + 1. Jeżeli k osiągnęło przyjętą wartość, to zakończenie obliczeń; w przeciwnym przypadku skok do 3.
4. Metody ewolucyjne szukania ekstremum (algorytmy genetyczne).
Algorytmy ewolucyjne są ważnymi metodami poszukiwania minimum funkcji. Zasada działania algorytmu genetycznego polega
na początkowym wyborze pewnej liczby punktów początkowych, a następnie na przeprowadzeniu wielu cykli uczenia.
W czasie cyklu oceniana jest jakość punktów, wybierane są punkty najlepsze (selekcja) i tworzone są z nich pary, na podstawie
których tworzone są punkty nowe (krzyżowanie) oraz dokonywane są losowe zmiany punktów (mutacja). Dzięki tym
operacjom w kolejnych cyklach otrzymuje się punkty coraz bliższe minimum, dotyczy to zarówno całej populacji jak i punktu w
danej chwili najlepszego. Po przeprowadzeniu pewnej liczby cykli proces uczenia się kończy i z populacji punktów wybiera
się punkt najlepszy.
* Klasyczny algorytm genetyczny:
1) Wybór początkowej populacji łańcuchów.
2) Ocena jakości łańcuchów.
3) Sprawdzenie czy jakość całej populacji łańcuchów lub jakość łańcucha najlepszego osiągnęła wymaganą wartość. Jeżeli tak
to zakończenie algorytmu, jeżeli nie to przejście do etapu następnego.
4) Selekcja łańcuchów.
5) Krzyżowanie łańcuchów.
6) Mutacja.
Modyfikacje klasycznego algorytmu genetycznego:
1. Przyjęcie reprezentacji punktów innych niż łańcuchy binarne  np. reprezentacja za pomocą liczb rzeczywistych (zmiana
sposobu krzyżowania punktów).
2. Kumulacja oceny jakości punktu. Ma to miejsce wtedy, gdy nie potrafimy dokładnie ocenić jakości punktu. Np. nie możemy
ocenić dokładnie jakości predyktora przebiegu czasowego na podstawie jednego lub kilku predykcji.
* Właściwości algorytmów genetycznych:
Przyjmijmy oznaczenia: ch  łańcuch, P  populacja łańcuchów, k  długość łańcucha, l(P)  liczba łańcuchów w populacji P
F(chi)  kryterium jakości łańcucha chi, t  numer cyklu działania algorytmu genetycznego
I(P, S, t)  liczba łańcuchów w populacji P reprezentowana przez schemat S w cyklu t, pm  prawdopodobieństwo mutacji
Definicja 1) Licznością schematu S jest liczba L(S) równa liczbie pozycji określonych w schemacie. Np. S = (*1*0*11), L(S) = 4.
Definicja 2) Długością schematu S jest liczba D(S) równa odległości pomiędzy pierwszą i ostatnią określoną pozycją w tym
schemacie. Np. S = (*1*0**), D(S) = 4 - 2 = 2.
3)Przystosowaniem schematu S w cyklu t nazywamy liczbę: 4) Przystosowaniem populacji P w cyklu t nazywamy liczbę
l(P)
F(chi )
"
"F(ch )
i
chi"S
i=1
F(S,t) =
F(P,t) =
I(P, S,t) l(P)
5. Algorytm roju.
W algorytmach tych podobnie jak w algorytmach ewolucyjnych ekstremum funkcji jest poszukiwane przez populację punktów.
W metodzie roju populacja punktów (cząstek) przemieszcza się w przestrzeni. W każdym kroku iteracyjnym cząstka
przemieszcza się w kierunku określonym przez trzy wektory: wektor wskazujący najlepsze dotychczasowe położenie cząstki
(najmniejsza wartość funkcji), wektor wskazujący najlepsze dotychczasowe położenie cząstek sąsiednich i chwilowy wektor
swojej prędkości. W zależności od definicji sąsiedztwa cząstek wyróżnia się dwa podstawowe warianty metod:
1. Metoda najlepszy globalnie:
Położenie cząstki w kroku iteracyjnym t + 1 zmienia się według wzoru:
wi (t +1) = wi (t) + vi (t +1)
gdzie wi(t) - pozycja cząstki i w kroku t, vi(t+1) prędkość cząstki obliczaną według wzoru
vi (t +1) = vi (t) + c1r1(t)[ yi (t) - wi (t)] + c2r2(t)[ w
(t) - wi (t)]
gdzie c1 i c2 są dodatnimi stałymi, r1(t) i r2(t) są macierzami diagonalnymi o losowych elementach wybranych z rozkładu
równomiernego w przedziale [0,1], yi(t) jest najlepszą dotychczasową pozycją cząstki (najlepszą osobistą) spośród wszystkich
pozycji osiąganych od pierwszego kroku, a Ćy(t) jest najlepszą pozycją spośród najlepszych osobistych pozycji wszystkich
cząstek.
Najlepsza pozycja osobista wyznaczana jest ze wzoru: Najlepsza pozycja globalna wyznaczana jest ze wzoru:
yi (t) E(wi (t +1)) e" E( yi (t))
ńł
yi (t +1) = w
(t) = arg minn {E(yi (t))}
�ł
yi ,i=1...
(t +1) s
ółwi
gdzie E jest minimalizowaną funkcją, a ns jest całkowitą liczbą cząstek.
2. Metoda najlepszy lokalnie
W wariancie najlepszy lokalnie każdej cząstce przypisuje się pewne inne cząstki, które nazywane są sąsiednimi. Teraz, zamiast
pozycji najlepszej globalnie Ćy(t), bierze się pozycję najlepszą lokalnie Ćyi(t), tzn. najlepszą pozycję osobistą spośród cząstek
sąsiednich. Czyli mamy:
vi (t +1) = vi (t) + c1r1(t)[yi (t) - wi (t)]+ c2r2(t)[w
i (t) - wi (t)]
zaś pozycja najlepsza lokalnie jest obliczana ze wzoru:
w
i (t) = arg min { f ( w
j (t))}
w
, j"
j i
6. Sztuczne sieci neuronowe.
Struktury łączenia neuronów można podzielić na dwie grupy:
1. Sieci warstwowe bez sprzężeń zwrotnych - uważa się za układy statyczne, realizujące odwzorowanie nieliniowe, którego
kształt zależy od przyjętej funkcji aktywacji, stałej  i wektorów wag w wszystkich neuronów sieci. Reaguje z opóz
nieniem
wynikającym z opóz
nień wnoszonych przez czas reakcji poszczególnych neuronów.
2. Sieci ze sprzężeniami zwrotnymi - są nieliniowymi układami dynamicznymi. Wprowadzone w stan początkowy dzięki
sprzężeniom zwrotnym zmieniają swój stan aż do osiągnięcia stanu równowagi. Specyficzne zastosowanie tych sieci to
asocjacyjne pamięci rekurencyjne które po pobudzeniu dążą do jednego ze swoich stanów równowagi.
7. Metoda propagacji wstecznej błędu
Służy do nauki sieci neuronowej. Pierwsza warstwa neuronów to warstwa ukryta, druga wyjściowa. Idea metody polega na
przesuwaniu wektora wag, po każdorazowym podaniu sygnału wejściowego, w kierunku powodującym zmniejszanie błędu
El=�ŁkK(dlk  zlk)2. Do wyznaczenia przyrostu wag stosuje się metodę gradientową szukania ekstremum. Wzory na korekcję wag
Ł
Ł
Ł
zawierają w współczynnik �
�, który mocno wpływa na szybkość uczenia. Jeżeli nie znamy poprawnych odpowiedzi na każdy
�
�
obraz wejściowy to nie można stosować tej metody, wtedy skorzystamy np. z algorytmów genetycznych.
8. Drzewa decyzyjne.
Uczenie należy do metod w których uzyskiwana jest wiedza jawna, są jednorazowe (nie iteracyjne). Korzystamy z zasady
brzytwy Ockhama. Zgodnie z nią szukamy zmiennej która ma największy wpływ na podejmowaną decyzję. Jednak we
wczesnych etapach tworzenia drzewa nie ma zmiennej której wartość pozwala na jednoznaczną decyzję. Jako miarę wpływu
zmiennej przyjmuje się entropię rozkładu prawdopodobieństwa decyzji wynikających z przyjęcia tej zmiennej jako węzła.
Entropia pi wynosi E = - Łinpi�"log2(pi). W przypadku nieznajomości pi można zastępować je liczebnością zdarzeń.
Ł �"
Ł �"
Ł �"