MSI-w5/1

Metody sztucznej inteligencji

Politechnika Śląska

Katedra Podstaw Konstrukcji Maszyn

Rok akademicki 2009/10

Wykład 5

MSI-w5/2

Uczenie maszynowe

Uczenie maszynowe polega na zastosowaniu
mechanizmów adaptacyjnych, które pozwalają na
uczenie się systemów komputerowe na podstawie
doświadczeń, przykładów lub analogii. Zdolności
uczenia mogą również ulegać polepszeniu.
Najbardziej popularnym podejściem do uczenia
maszynowego są

sieci neuronowe

i

algorytmy

ewolucyjne

.

MSI-w5/3

Architektura typowej sieci neuronowej

Input Layer

Output Layer

Middle Layer

I n p u t

S i

g n a l

s

O

u t

p u t

S i

g n a l

s

Nengnevintsky M.: Artificial Intelligence

MSI-w5/4

Struktury sieci neuronowych

• Sieci feed-forward (nierekurencyjne)

– Skierowany graf acykliczny
– Neurony zwykle organizowane w warstwy
– Poza wartościami wag brak wewnętrznego stanu (bez

pamięci)

– Działają szybko, łatwo je zaprogramować

• Sieci rekurencyjne (mózg ludzki!!)

– Mają stan wewnętrzny
– Zaawansowany aparat matematyczny
– niekiedy długo trzeba czekać na stabilizację wyjścia

MSI-w5/5

Jednostka sieci (neuron)

wagi

wyjście

Ważona suma wejść

funkcja aktywacji

∑

⋅

=

⋅

=

j

i

i

j

i

j

i

a

W

in

a

W

,

Russel S., Norvig P.: Artificial Intelligence. A modern approach

MSI-w5/6

Jednostka (neuron)

• Posiada zbiór

połączeń wejściowych

• Posiada zbiór

połączeń wyjściowych

• Ma

poziom aktywacji

• Główna idea:

każda jednostka przeprowadza samodzielnie

(lokalnie) obliczenia, bazując na wejściach

od swoich sąsiadów, lecz bez potrzeby

globalnego sterowania zespołem

neuronów jako całością

MSI-w5/7

Threshold

Inputs

x

1

x

2

Output

Y

∑

Hard

Limiter

w

2

w

1

Linear

Combiner

θ

Jednowarstwowy dwuwejściowy

perceptron

Nengnevintsky M.: Artificial Intelligence

MSI-w5/8

Sieć neuronowa wielowarstwowa

„

Wielowarstwowy perceptron jest siecią neuronową
typu feed forward z jedną lub kilkoma warstwami
ukrytymi.

„

Sieć składa się z warstwy wejściowej, zawierającej
neurony z wejściami źródłowymi, co najmniej
jednej warstwy środkowej, nazywanej warstwą
ukrytą, i warstwy wyjściowej, która zwiera
obliczone wyjścia z sieci.

„

Sygnał wejściowy jest propagowany do przodu
(forward) z warstwy do warstwy.

MSI-w5/9

Wielowarstwowa sieć neuronowa z dwoma

warstwami ukrytymi

Input

layer

First

hidden

layer

Second

hidden

layer

Output

layer

O

u t

p u t

S i

g n a l

s

I n p u t

S i

g n a l

s

Nengnevintsky M.: Artificial Intelligence

MSI-w5/10

Warstwa ukryta

„

Warstwa ukryta ukrywa swoje oczekiwane wyjścia
(nie wiemy jakie mają być). Neurony z tej warstwy
nie mogą być bezpośrednio obserwowane poprzez
wejścia i wyjścia z sieci.
Stąd sieci neuronowe nazywane są czarnymi
skrzynkami.

„

Komercyjne sieci neuronowe zawierają trzy lub cztery
warstwy (włączając warstwy ukryte). Każda warstwa
zawiera od 10 do 1000 neuronów.

„

Eksperymentalne sieci neuronowe mogą mieć pięć lub
cześć warstw, w tym trzy lub cztery warstwy ukryte i
około miliona neuronów.

MSI-w5/11

Sieć ze wsteczną propagacją błędu

(back-propagation)

„

Uczenie w sieci wielowarstwowej przebiega w
taki sam sposób, jak w przypadku perceptronu.

„

Zbiór uczący (trenujący) jest podawany na wejście
sieci.

„

Sieć oblicza wzorcowe wyjścia i jeżeli między
aktualnymi wyjściami i wzorcowymi wyjściami
występuje błąd, wagi są dostosowywane
(obliczana jest poprawka), tak aby uzyskać zadany
minimalny błąd.

MSI-w5/12

Sieci neuronowe są projektowane poprzez analogię do
ludzkiego mózgu. Mózg i pamięć działają na zasadzie
skojarzeń (asocjacji).

Sieć wielowarstwowa ze wsteczną propagacją błędu nadaje
się do zdań rozpoznawania, jednak nie jest w stanie
symulować zdolności asocjacyjnych człowieka (ponieważ
nie ma pamięci). W tym celu należy zastosować sieć
neuronową rekurencyjną.

Sieć neuronowa rekurencyjna posiada pętle sprzężenia
zwrotnego od wyjść do wejść.

Sieć neuronowa rekurencyjna

MSI-w5/13

Badanie stabilności sieci neuronowych było przedmiotem
badań w latach 1960 - 1970.

Początkowo, nie można było określić jakie i kiedy sieci ze
sprzężeniem zwrotnym będą stabilne. Powodowało to, że
sieci te uważano za słabe i nieużyteczne algorytmu.

Problem stabilności sieci rekurencyjnych został rozwiązany
dopiero w 1982 przez Johna Hopfielda, który sformułował
podstawy przechowywania informacji w tych sieciach.

Sieć Hopfielda

Nengnevintsky M.: Artificial Intelligence

MSI-w5/14

Jednowarstwowa n-neuronowa sieć

Hopfielda

x

i

x

1

x

2

x

n

I n p u t

S i g

n a

l s

y

i

y

1

y

2

y

n

1

2

i

n

O u t

p u t

S i g

n a

l s

Nengnevintsky M.: Artificial Intelligence

MSI-w5/15

„

Sieć Hopfielda reprezentuje asocjacyjny typ pamięci, co
pozwala na odzyskiwanie (ratowanie) zniszczonej lub
niekompletnej pamięci, ale nie pozwala na kojarzenie
różnych źródeł pamięci. Pamięć ludzka ma taką własność.

„

Aby łączyć różne źródła pamięci wymagane jest
zastosowanie kilku, połączonych ze sobą sieci.

„

Dwukierunkowe pamięci asocjacyjne (BAM) zostały
opracowane przez Barta Kosko. Pamięć pozwala na
kojarzenie zbioru wzorcowego A, z innym zbiorem
wzorcowym B i odwrotnie. Podobnie jak sieć Hopfielda
sieć BAM pozwala na prowadzenie wnioskowania przy
niekompletnych danych.

Nengnevintsky M.: Artificial Intelligence

Dwukierunkowe pamięci asocjacyjne

(BAM)

MSI-w5/16

Działanie BAM

y

j

(p)

y

1

(p)

y

2

(p)

y

m

(p)

1

2

j

m

Output

layer

Input

layer

x

i

(p)

x

1

(p)

x

2

(p)

x

n

(p)

2

i

n

1

x

i

(p+1)

x

1

(p+1)

x

2

(p+1)

x

n

(p+1)

y

j

(p)

y

1

(p)

y

2

(p)

y

m

(p)

1

2

j

m

Output

layer

Input

layer

2

i

n

1

(a) Forward direction.

(b) Backward direction.

Nengnevintsky M.: Artificial Intelligence

MSI-w5/17

Główna cechą sieci neuronowych jest uczenie się na
podstawie danych pochodzących z obserwacji środowiska
oraz uczenie się
Wszystkie przedstawione sieci charakteryzują się uczeniem
się nadzorowanym (z nauczycielem; znany jest zbiór
wzorców).
Innym typem uczenia jest uczenie nienadzorowane (bez
nauczyciela); na wejścia sieci podawane są różne zbiory
danych i sieć sama decyduje (odkrywa), które wartości są
istotne i które wartości można traktować jako wzorce dla
danych wejść.
Algorytmu uczenia się nienadzorowanego działają bardzo
szybko w czasie rzeczywistym

Uczenie nienadzorowane

MSI-w5/18

W 1949 roku Donald Hebb sformułował jedno z
kluczowych praw uczenia biologicznego, znane
jako prawo Hebba.

Jeżeli neuron i jest wystarczająco blisko aby

pobudzić neuron j i ta sytuacja się powtarza,
połączenie między tymi dwoma neuronami jest
wzmacniane, neuron j staje się bardziej czuły na
sygnały pochodzące od neuronu i.
W odwrotnej sytuacji wprowadza się tzw.
współczynnik zapominania (osłabienie
połączenia).

Nengnevintsky M.: Artificial Intelligence

Uczenie Hebba

MSI-w5/19

Uczenie Hebba w sieci neuronowej

i

j

I n p

u t

S i g

n a l

s

O

u t

p u t

S i

g n

a l

s

Nengnevintsky M.: Artificial Intelligence

MSI-w5/20

„

Neurony współzawodniczą między sobą o to, aby
być aktywowanym.

„

Podczas uczenia Hebba jest aktywowanych kilka
neuronów wyjściowych jednocześnie; w uczeniu
przez współzawodnictwo w jednym czasie jest
aktywowany tylko jeden neuron.

„

Neuron wyjściowy, który wygrywa
współzawodnictwo jest nazywany neuronem
„zwycięzca bierze wszystko”.

Uczenie poprzez współzawodnictwo (1)

Nengnevintsky M.: Artificial Intelligence

MSI-w5/21

Kora mózgowa jest bardzo złożoną strukturą
składającą się z bilionów neuronów i wielokrotnie
większej liczby ich połączeń.
W mózgu wyróżnia się obszary odpowiedzialne za
różne działania i zachowania człowieka oraz
kojarzenie pamięci i bodźców odbieranych przez
zmysły.
Każdy ze zmysłów ma swój charakterystyczny
obszar w mózgu
Kora mózgowa jest samoorganizującą się mapą
w ludzkim mózgu.

Samoorganizująca się mapa Kohonena

Nengnevintsky M.: Artificial Intelligence

MSI-w5/22

Model mapy Kohonena

Input layer

Kohonen layer

(a)

Input layer

Kohonen layer

1

0

(b)

0

1

Nengnevintsky M.: Artificial Intelligence

MSI-w5/23

„

Inteligencja może być zdefiniowana jako zdolność
systemu (jednostki) do adoptowania swojego
zachowania w ciągle zmieniającym się środowisku.

„

Obliczenia ewolucyjne są symulacją ewolucji
przebiegającą w komputerze. Wynikiem takiej
ewolucji jest seria algorytmów optymalizacyjnych
opartych na bardzo prostych regułach działania.

„

Podejście ewolucyjne jest oparte na numerycznych
modelach naturalnej selekcji i genetyki. Nazywa się je
obliczeniami ewolucyjnymi. Wspólny termin łączący
algorytmy genetyczne i strategie ewolucyjne
nazywany jest programowaniem genetycznym.

Podstawy ewolucji

MSI-w5/24

Cykl algorytmu genetycznego

1

0

1

0

X1

i

Generation i

0

0

1

0

X2

i

0

0

0

1

X3

i

1

1

1

0

X4

i

0

1

1

1

X5

i

f = 56

1

0

0

1

X6

i

f = 54

f = 36

f = 44

f = 14

f = 14

1

0

0

0

X1

i+1

Generation (i + 1)

0

0

1

1

X2

i+1

1

1

0

1

X3

i+1

0

0

1

0

X4

i+1

0

1

1

0

X5

i+1

f = 54

0

1

1

1

X6

i+1

f = 56

f = 56

f = 50

f = 44

f = 44

Crossover

X6

i

1

0

0

0

0

1

0 X2

i

0

0

1

0

X2

i

0

1

1

1 X5

i

0

X1

i

0

1

1

1 X5

i

1

0

1

0

0 1

0 0

1

1

1

0

1

0

Mutation

0

1

1

1

X5'

i

0

1

0

X6'

i

1

0

0

0

0

1

0

X2'

i

0 1

0 0

0

1 1

11

X5

i

1

1 1 X1"

i

1 1

X2"

i

0 1

0

0

X1'

i

1

1 1

0 1

0

X2

i

Nengnevintsky M.: Artificial Intelligence

MSI-w5/25

„

Podejście zaproponowane w Niemczech w latach 60tych
jako narzędzie pozwalające na przeprowadzanie
optymalizacji złożonych problemów

„

W 1963 dwóch studentów Uniwersytetu Technicznego w
Berlinie, Ingo Rechenberg i Hans-Paul Schwefel,
pracowali na opracowaniem optymalnych kształtów ciał
latających. Na przykładzie naturalnej mutacji przeprowadzali
losowe zmiany parametrów określających kształt. Jako
wynik opracowali strategię ewolucyjną SE.

„

W odróżnieniu od GA, w SE używa się tylko operatorów
mutacji.

Strategie ewolucyjne

MSI-w5/26

„

Strategia ewolucyjna odzwierciedla naturę
chromosomów.

„

Pojedynczy gen może działać jednocześnie na
kilka cech charakterystycznych żyjących
organizmów.

„

Cecha charakterystyczna osobnika jest określana
poprzez jednoczesne interakcje kilku genów.

„

Selekcja naturalna działa na zbiory genów nie na
pojedyncze geny.

Charakterystyka strategii ewolucyjnej

MSI-w5/27

„

Programowanie genetyczne jest rozszerzeniem AG, ale celem
nie jest otrzymanie reprezentacji w postaci kodu binarnego, ale
kodu programu komputerowego.

„

Programowanie genetyczne zostało opracowane w latach 90tych
przez Johna Koza’iego.

„

PG polega na przeszukiwaniu przestrzeni możliwych
programów komputerowych w celu wyszukania programu, który
najbardziej pasuje do danego problemu.

„

Program komputerowy jest sekwencją operacji (funkcji)
zastosowanych dla wartości (argumentów), ale różne języki
programowania mogą zawierać różne typy operacji i definicji.

„

Jak język programowania został wybrany LISP

Programowanie genetyczne

MSI-w5/28

LISP ma strukturę symboliczną. Podstawowe
struktury danych to atomy i listy.

Przykłady atomów:
- 21,
- „To jest lancuch”.

LISP

MSI-w5/29

Lista
(

− (

*

A B) C)

wywołuje funkcję odejmowania (

−) dla dwóch

argumentów – lista (*A B) i atomu C.
funkcja mnożenia (*) jest wywoływana dla dwóch
atomów A a B.
Po tym jak dla listy (*A B) wykonana jest funkcja
mnożenia, stosowana jest funkcja (

−) dla całej listy

(

− (

*

A B) C).

Struktura LISPa

Nengnevintsky M.: Artificial Intelligence

MSI-w5/30

B

A

*

C

−

Graficzna reprezentacja listy (

− (*A B) C)

Nengnevintsky M.: Artificial Intelligence

MSI-w5/31

Kroki programowania genetycznego

1. Określ zbiór symboli (zmiennych).
2. Wybierz zbiór prostych funkcji.
3. Zdefiniuj funkcję przystosowania.
4. Określ parametry kontrolujące uruchomienie PG.
5. Wybierz rozwiązanie optymalne.

Nengnevintsky M.: Artificial Intelligence