1

MSI-w5/1

Metody sztucznej inteligencji

Politechnika Śląska

Katedra Podstaw Konstrukcji Maszyn

Rok akademicki 2002/2003

Wykład 5

Materiały dydaktyczne (na prawach rękopisu)

dla studentów Wydziału Mechanicznego Technologicznego

MSI-w5/2

Uczenie (się) na podstawie

obserwacji

MSI-w5/3

Główna idea

• Percepcje są wykorzystywane nie tylko do

wyboru odpowiedniej akcji, lecz także do

powiększania zdolności systemu wnioskowania
(agenta) do działania w przyszłości (uczenia się)

• Uczenie się zachodzi jako

wynik interakcji

pomiędzy systemem wnioskowania (agentem)
i otoczeniem

• Jest wiele form uczenia, od

zapamiętywania

do

tworzenia złożonych teorii

MSI-w5/4

Ogólny model systemu wnioskowania

(agenta) uczącego się (1)

Ś

r

o
d
o

w

i

s

k
o

Krytyka

Element

uczący się

Element

działający

Generator

problemów

Sensory

Efektory

Agent

Sprzęż.

zwrotne

Cele

uczenia

Zmiany

Wiedza

MSI-w5/5

Ogólny model (systemu wnioskowania)

agenta uczącego się (2)

• Element uczący się

- odpowiada za dokonywanie

ulepszeń

• Element działający

- odpowiada za wybór

zewnętrznych działań

• Krytyka

- dostarcza elementowi uczącemu się

informacji o tym, jak dobrze działa agent

• Generator problemów

- sugeruje akcje, które będą

prowadzić do nowych i informatywnych doświadczeń

MSI-w5/6

Ogólny model (systemu wnioskowania)

agenta uczącego się (3)

• Dostępne sprzężenia zwrotne:

– uczenie nadzorowane

(agent zna zarówno

percepcje, jak i wynik ich klasyfikacji)

– uczenie ze wzmocnieniem

(agent jest nagradzany

lub karany, w zależności od wyniku akcji;

klasyfikacja nie jest agentowi znana)

– uczenie nienadzorowane

(klasyfikacja nieznana)

• Rola wiedzy podstawowej -

uczenie zwiększa

nieznacznie wiedzę posiadaną przez agenta

2

MSI-w5/7

Indukcja drzew decyzyjnych

• Jeden z najprostszych algorytmów uczenia

maszynowego

• Łatwe do wdrożenia

MSI-w5/8

Cechy drzewa decyzyjnego

• Obiekty są opisane przez zbiory ich cech
• Drzewo zwraca klasyfikację (decyzję)

TAK/NIE (mogą być przypadki
wieloklasowe - bardziej ogólne)

• Drzewo reprezentuje funkcję Boolowską

MSI-w5/9

Budowa drzewa decyzyjnego

• Każdy wewnętrzny węzeł odpowiada testowi

dotyczącemu wartości jakiegoś atrybutu

• Każdej krawędzi wychodzącej z danego węzła

przyporządkowana jest jedna wartość atrybutu
„węzłowego”

• Liściom przyporządkowane są wartości

Boolowskie, zwracane jeśli osiągnięto dany
liść

MSI-w5/10

Przykład - czy czekać na stolik?

• Alternate: w pobliżu

jest inna restauracja?

• Bar: czy w restauracji

jest bar gdzie można
poczekać?

• Fri/Sat: Piątek/Sobota
• Hungry: jesteś głodny?
• Patrons: ile jest ludzi w

restauracji?

• Price: zakres cen
• Raining: czy pada?
• Reservation: czy zarezer-

wowaliśmy wcześniej?

• Type: rodzaj restauracji -

chińska, włoska, Burger.

• WaitEstimate: szacowa-

ny czas oczekiwania w
min.

MSI-w5/11

Czy czekać na stolik?

Yes

Patrons?

No

Reservation?

Bar?

Yes

No

WaitEstimate?

Alternate?

Hungry?

Yes

Fri/Sat?

Yes

Alternate?

Yes

No

Yes

Yes

Raining?

No

Yes

No

None

Some

Full

0-10

10-30

30-60

>60

No

Yes

No

Yes

No

Yes

No

Yes

No

Yes

No

Yes

No

Yes

W tym drzewie nie
wykorzystano wszyst-
kich atrybutów!!

MSI-w5/12

Indukcja drzew decyzyjnych

ze zbioru przykładów

• Przykład opisywany jest przez

wartości

atrybutów

(warunku) oraz przez

wartość

atrybutu decyzyjnego

• Przykłady tworzą

zbiór trenujący

• Brzytwa Ockhama (XIV w.):

Pluralitas non est ponenda sine neccesitate

Najbardziej prawdopodobna jest
najprostsza spośród hipotez zgodnych ze
wszystkimi obserwacjami

3

MSI-w5/13

Algorytm indukcji drzew decyz.

function DECISION-TREE-LEARNING(examples,attributes,default) returns a decision tree

inputs: examples, zbiór przykładów

attributes, zbiór atrybutów
default, wartość domyślna dla atrybutu decyzyjnego

if examples is empty then return default
else if all examples have the same classification then return the classification
else if attributes is empty then return MAJORITY-VALUE(examples)
else

best

← CHOOSE-ATTRIBUTE(attributes,examples)

tree

← a new decision tree with root test best

for each value v

i

of best do

examples

i

← {elements of examples with best = v

i

}

subtree

← DECISION-TREE-LEARNING(examples

i

,attributes-best,

MAJORITY-VALUE(examples))

add a branch to tree with label v

i

and subtree subtree

end
return tree

Oznacza to, że
dane mają te same
opisy, lecz należą
do różnych klas;
rozstrzyga głoso-
wanie

MSI-w5/14

Uwagi dotyczące indukcji drzew

• Podstawowy problem - wybór
• Indukcja niezupełna (

nie mamy wszystkich

możliwych przykładów

)

• Programy realizujące uczenie maszynowe

działają bardzo szybko i efektywnie

• Drzewa decyzyjne mogą być bardzo

rozbudowane - często się je

przycina

kosztem

nieco gorszej sprawności klasyfikacji

MSI-w5/15

Ocena sprawności algorytmu uczenia (1)

• Zgromadź

liczny zbiór przykładów

• Podziel go na rozłączne zbiory:

zbiór trenujący

i

zbiór testowy

• Stosując zbiór trenujący jako przykłady,

uzyskaj indukcyjnie hipotezę H

• Stosując przykłady testowe,

określ jaka ich

część jest poprawnie klasyfikowana przez H

• Powtarzaj te kroki dla zbiorów trenujących

różnych wielkości, losowo wybieranych

MSI-w5/16

Ocena sprawności algorytmu uczenia (2)

• Ilość informacji

[bity] zawartej w poprawnej

odpowiedzi, gdy zbiór trenujący zawiera p
przykładów pozytywnych i n negatywnych:

• Ilość informacji dostępna po testowaniu atrybutu

A:

• Przyrost ilości informacji:

n

p

n

n

p

n

n

p

p

n

p

p

n

p

n

n

p

p

I

+

+

−

+

+

−

=

+

+

2

2

log

log

)

,

(

∑

=

+

+

+

+

=

v

i

i

i

i

i

i

i

i

i

n

p

n

n

p

p

I

n

p

n

p

A

Pozostało

1

)

,

(

)

(

)

(

)

,

(

)

(

Pr

A

Pozostało

n

p

n

n

p

p

I

A

zyrost

−

+

+

=

Atrybut A dzieli zbiór E na
podzbiory E

1

,..., E

v

; p

i

, n

i

to liczby przykładów pozyty-
wnych i negatywnych w tym
podzbiorze

MSI-w5/17

Zwiększenie możliwości

zastosowania drzew decyzyjnych

• Brakujące dane

(nie zapisane; zbyt

kosztowne ich uzyskanie)

• Atrybuty wielowartościowe
• Atrybuty o wartościach ciągłych

(rzeczywistych) - wymagana dyskretyzacja

MSI-w5/18

Niektóre problemy

• Błędne dane (np. sprzeczne przykłady -

takie same wartość atrybutów warunku,
różne wartości atrybutu decyzyjnego)

– drzewo klasyfikuje błędnie

• Nadmierne dopasowanie

– zbyt szczegółowy klasyfikator, dużo błędów dla

„unseen examples”

• Rada - PRZYCINANIE DRZEWA

4

MSI-w5/19

Podstawowe pytanie

Skąd wiadomo, że algorytm uczenia
pozwolił utworzyć teorię, która
będzie

poprawna

?

MSI-w5/20

Odpowiedź intuicyjna

• Każda hipoteza, która jest poważnie błędna,

zostanie na pewno znaleziona z wysokim

prawdopodobieństwem jedynie dla małej liczby

przykładów, ponieważ to prowadziłoby do

błędnych przewidywań

• Wniosek:

Jest nieprawdopodobne, żeby hipoteza zgodna z

wystarczająco licznym zbiorem trenującym, była

poważnie błędna

• Uczenie

PAC

(Probably Approximately Correct)

MSI-w5/21

Ile potrzeba przykładów (1)?

• X - zbiór wszystkich możliwych

przykładów

• D – rozkład prawdopodobieństwa, z którego

losuje się przykłady

• H - zbiór możliwych hipotez
• f

∈

H – prawdziwa funkcja, którą staramy

się przybliżyć za pomocą hipotezy h

∈

H

• m - liczba przykładów w zbiorze

trenującym

MSI-w5/22

Ile potrzeba przykładów (2)?

• Błąd (h różne od aproksymowanej funkcji f):

• Hipoteza jest w przybliżeniu poprawna, jeśli:

• Gdy

δ-dopuszczalne prawdop. błędnej hipotezy:

}

z

wylosowane

|

)

(

)

(

{

)

(

D

x

x

f

x

h

P

h

error

h

≠

=

∈ H

liczba

mała

,

)

(

−

≤

ε

ε

h

error













+

≥

H

ln

1

ln

1

δ

ε

m

MSI-w5/23

Podsumowanie (1)

• Zdolność uczenia się systemu wnioskowania (agenta)

jest istotna

ze względu na działanie w nieznanym

środowisku

• W systemie wnioskowania (agencie) uczącym się

można wyróżnić:

– element działający

, odpowiedzialny za wybór akcji

– element uczący (się)

, odpowiedzialny za modyfikowanie

elementu działającego

• Możliwe są

różne formy uczenia

, ze względu na:

element działający, sprzężenia zwrotne oraz dostępną

wiedzę

MSI-w5/24

Podsumowanie (2)

• Uczenie się jakiegokolwiek składnika elementu

działającego może być interpretowane jako

uczenie się aproksymacji funkcji

• Uczenie się aproksymacji funkcji na podstawie

przykładów nazywa się

uczeniem indukcyjnym

• Drzewa decyzyjne są skutecznym środkiem

uczenia się

zdeterminowanych funkcji Boola

5

MSI-w5/25

Podsumowanie (3)

• Brzytwa Ockhama

sugeruje wybór

najprostszej hipotezy pasującej do

obserwowanych przykładów

• Określenie

największego przyrostu

informacji

umożliwia znalezienie

prostych

drzew decyzyjnych

• Osiągi algorytmu uczenia indukcyjnego

określa się za pomocą

łącznego błędu

klasyfikacji

MSI-w5/26

Uczenie w sieciach neuronowych

MSI-w5/27

Sieci neuronowe -geneza

• Reprezentuje złożone (np. nieliniowe) funkcje
• Sieci złożone z prostych elementów

wykonujących operacje arytmetyczne

• Szczególnie użyteczne w przypadku

skomplikowanych funkcji wielu zmiennych,

które:

– mają wyjścia o wartościach rzeczywistych
– mają wiele wejść obciążonych szumem

MSI-w5/28

Jak działa mózg?

• Składa się z neuronów (komórek nerwowych)
• Neurony połączone pomiędzy sobą poprzez

synapsy

• Sygnały pomiędzy neuronami:

– propagowane poprzez reakcje elektrochemiczne
– przekazywane, gdy potencjał elektryczny danego

neuronu przekroczy odpowiedni próg

– mogą być wzmacniane lub tłumione przez

synapsy

MSI-w5/29

Długość wypustek komórki nerwowej jest około

100 razy większa od średnicy komórki.

Budowa neuronu

wejścia

wyjście

wzmocnienie

MSI-w5/30

Mózg : komputer

10

14

10

5

Liczba neuronów
aktualizowanych/s

10

14

10

9

Pasmo [bity/s]

10

-3

10

-8

Czas trwania cyklu [s]

10

11

neuronów;

10

14

synaps

RAM 10

9

bitów;

Dysk 10

10

bitów

Pojemność pamięci

10

11

neuronów

1 CPU; 10

5

bramek

Liczba jednostek

Mózg ludzki

Komputer (1994r)

6

MSI-w5/31

Sieć neuronowa

• Wiele

węzłów

(jednostek)

• Połączenia

między nimi

• Połączeniom przyporządkowane

wagi

MSI-w5/32

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/33

Algorytm budowy sieci

• Określ:

– liczbę potrzebnych neuronów
– ich rodzaj
– sposób połączenia neuronów pomiędzy sobą

• Zainicjuj początkowe wartości wag
• Trenuj sieć (modyfikując wagi), używając

odpowiedniego algorytmu zastosowanego

do zbioru przykładów trenujących

MSI-w5/34

Jednostka sieci (neuron)

wagi

wyjście

Ważona suma wejść

funkcja aktywacji

∑

⋅

=

⋅

=

j

i

i

j

i

j

i

a

W

in

a

W

,

MSI-w5/35

Przykłady funkcji aktywacji







<

≥

=

t

x

t

x

x

t

if

,

0

if

,

1

)

(

step







<

−

≥

+

=

0

if

,

1

0

if

,

1

)

(

sign

x

x

x

x

e

x

−

+

=

1

1

)

(

sigmoid

1

,

gdzie

)

(

step

)

(

step

0

,

0

0

,

0

1

,

−

=

=

⋅

=

⋅

=

∑

∑

=

=

a

t

W

a

W

a

W

a

i

n

j

j

i

j

n

j

j

i

j

t

i

MSI-w5/36

Zastosowanie funkcji aktywacji step powoduje, że

neurony mogą działać jak logiczne bramki.

Reprezentowanie funkcji logicznych

7

MSI-w5/37

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/38

Dwa wejścia (I

1

i I

2

), dwa neurony (H

1

i H

2

) w warstwie

ukrytej i jeden neuron (O

5

) na wyjściu sieci.

Prosta sieć neuronowa

z propagacją w przód

(

)

(

)

(

)

(

)

2

4

,

2

1

4

,

1

5

,

4

2

3

,

2

1

3

,

1

5

,

3

4

5

,

4

3

5

,

3

5

a

W

a

W

g

W

a

W

a

W

g

W

g

a

W

a

W

g

a

⋅

+

⋅

⋅

+

⋅

+

⋅

⋅

=

⋅

+

⋅

=

MSI-w5/39

Perceptrony

• Mogą reprezentować

złożone funkcje

logiczne

• Zastępują złożone

binarne drzewa

decyzyjne (perceptron

o n wejściach można

zastąpić drzewem

decyzyjnym o 2

n

węzłach)

MSI-w5/40

Liniowa separowalność

• Np. XOR nie jest liniowo separowalny
• Istnieje algorytm, który

umożliwia nauczenie każdej

liniowo separowalnej funkcji

, gdy jest

dostatecznie dużo

przykładów trenujących

MSI-w5/41

Reprezentuje funkcję minimalizacji

Liniowa separacja w przestrzeni 3D

MSI-w5/42

Ogólny algorytm uczenia sieci

function NEURAL-NETWORK-LEARNING(examples) returns network

network

← sieć z losowo przyjętymi wagami

repeat

for each e in examples do

O

← NEURAL-NETWORK-OUTPUT(network, e)

T

← zaobserwowane wartości wyjściowe dla e

zaktualizuj wagi w network bazując na e, O, T

end

until wszystkie przykłady poprawnie sklasyfikowane

lub osiągnięte kryterium stop

return network

O - wartośc wyjściowa sieci, T - wartość poprawna

8

MSI-w5/43

Reguła uczenia perceptronu

• Uczenie polega na aktualizacji wag
• Określa się błąd predykcji:

Err = T - O

gdy > 0, zwiększyć O; gdy < 0, zmniejszyć O

• Udział j-tego neuronu wejściowego w

wyjściu = W

j

I

j

• Reguła uczenia (

α - prędkość uczenia):

W

j

← W

j

+

α × I

j

× Err

MSI-w5/44

Porównanie zastosowania perceptronów i drzew

decyzyjnych

(a) Perceptron lepszy w uczeniu funkcji majoryzującej

dla 11 wejść,

(b) Drzewa decyzyjne lepsze w uczeniu predykatów

WillWait (przykład oczekiwania na stolik
w restauracji)

MSI-w5/45

Dwuwarstwowa sieć neuronowa

nierekurencyjna dla zadania

„oczekiwanie na stolik w restauracji”

Neuron wyjściowy

Neurony ukryte

Neurony wejściowe

MSI-w5/46

Wsteczna propagacja błędu (1)

• Najbardziej popularna metoda uczenia NN
• Bazuje na algorytmie uczenia perceptronu
• Istota polega na odpowiednim rozdzielaniu

błędu proporcjonalnie do wag sieci

• W wyrażeniu na aktualizację wag

uwzględnia się

gradient funkcji aktywacji

MSI-w5/47

Wsteczna propagacja błędu (2)

Jeśli dla i-tego wyjścia Err

i

= T

i

- O

i

, to:

( )

( )

( )

.

:

wejsciowej

warstwy

Dla

.

:

gdzie

:

Wtedy

.

Niech

,

,

,

,

,

,

,

j

k

j

k

j

k

i

i

i

j

j

j

i

j

i

j

i

j

i

i

i

i

i

j

i

j

i

j

I

W

W

W

in

g

a

W

W

in

g

Err

in

g

Err

a

W

W

∆

⋅

⋅

+

←

∆

⋅

′

=

∆

∆

⋅

⋅

+

←

′

⋅

=

∆

′

⋅

⋅

⋅

+

←

∑

α

α

α

MSI-w5/48

Algorytm wstecznej propagacji błędu

• Oblicz wartości

∆ dla neuronów wyjściowych

stosując uzyskany błąd

• Zaczynając od warstwy wyjściowej, powtarzaj

dla każdej warstwy sieci, dopóki nie zostanie
osiągnięta pierwsza warstwa ukryta:

– Propaguj wartości

∆ do poprzedzającej warstwy

– Aktualizuj wagi połączeń pomiędzy obiema

warstwami

9

MSI-w5/49

Powierzchnia błędów dla gradientu spadku

w przestrzeni wag

Kiedy w

1

=a i w

2

=b błąd dla danego zbioru danych

trenujących jest minimalny

MSI-w5/50

Dyskusja (1)

• SN

są reprezentacją opartą na atrybutach

i nie

pozwalają na wyrażanie logicznych zależności

(w odróżnieniu od drzew decyzyjnych),

• Wydajność obliczeniowa

SN

zależy od czasu,

który jest potrzebny na trenowanie sieci

, w celu

jej dopasowania do danego zbioru przykładów,

• SN

pozwalają na generalizację problemów

, co

czyni je przydatnymi w rozwiązywaniu wielu

zadań świata rzeczywistego.

MSI-w5/51

Dyskusja (2)

• SN

nie są czułe na szum

na wejściu ponieważ

działają na zasadzie nieliniowej regresji,

• SN

są czarnymi skrzynkami

(są nieprzeźroczyste);

nie można uzyskać odpowiedzi na pytanie:

„dlaczego dane wyjście jest poprawne?”,

• SN

nie umożliwiają oceny jaka wiedza a priori

jest najlepsza do ich nauczenia

, co jest efektem

ich nieprzeźroczystości. (Problem może być

usunięty w sieciach przekonań)

MSI-w5/52

Przykłady zastosowań

• Wymowa pisanych angielskich tekstów

realizowana przez komputer (NETtalk 1987).

Litera „k” odpowiada dźwiękowi [k], ale litera „c”

odpowiada także [k] (cat) lub [s]

(cent).

• Rozpoznawanie pisma odręcznego.

stosowane do odczytywania adresów na

kopertach (VLSI, 1989).

• Sterowanie pojazdem

poruszającym się po

autostradzie (ALVINN, 1993)

MSI-w5/53

Podsumowanie (1)

• Sieć neuronowa to model obliczeniowy o niektórych

własnościach podobnych do mózgu

• Zachowanie się sieci określone jest przez jej

topologię

• Perceptron to rodzaj sieci jednowarstwowej, która

może reprezentować tylko funkcje liniowo

separowalne

• Dla danych separowalnych liniowo, reguła uczenia

perceptronu poprzez modyfikację wag sieci

umożliwia bezbłędne dopasowanie do danych

MSI-w5/54

Podsumowanie (2)

• Nierekurencyjne sieci wielowarstwowe o

odpowiednim stopniu złożoności mogą

reprezentować dowolną funkcję

• Algorytm uczenia ze wsteczną propagacją

błędu umożliwia uczenie nierekurencyjnych

sieci wielowarstwowych:

– Jest zbieżny do lokalnie optymalnego rozwiązania
– Użyty z powodzeniem w wielu zastosowaniach