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