Metody automatycznego

uczenia się systemów

Metody automatycznego

uczenia się systemów

Definicja

Uczeniem się systemu jest każda
autonomicma zmiana w systemie
zachodząca na podstawie
doświadczeń, która prowadzi do
poprawy jakości jego działania.

Paweł Cichosz “Systemy uczące się WNT,
Warszawa 2000

Metody automatycznego

uczenia się systemów

Kryteria klasyfikacji systemów uczących się

▪

metoda reprezentacji wiedzy lub

umiejętności,

▸

Symboliczne

▸

Subsymboliczne

▪

sposób używania wiedzy lub umiejętności,

▸

Klasyfikacja

▸

Aproksymacja

▪

źródło i postać informacji trenującej,

▸

Uczenie się z nadzorem

▸

Uczenie się bez nadzoru

▪

mechanizm nabywania i doskonalenia

wiedzy lub umiejętności.

▸

Indukcyjne uczenie się na przykladach

▸

Nieindukcyjne - uczenie się ze wzmocnieniem,

wyjaśnianie

Metody automatycznego

uczenia się systemów

Nauka o uczeniu się - trzy nurty

▪

Nurt teoretyczny zajmuje się

rozwijaniem podstaw teoretycznych
algorytmów uczenia się.

▪

Nurt biologiczny stawia sobie za cel

konstruowanie obliczeniowych modeli
procesów uczenia się występujących w
naturalnych systemach biologicznych

▪

Nurt systemowy zajmuje się

opracowywaniem algorytmów uczenia się
oraz konstruowaniem, badaniem i
stosowaniem wykorzystujących je
systemów uczących się.

Metody automatycznego

uczenia się systemów

Nauka o uczeniu się - dziedziny pokrewne

▪

Teoria prawdopodobieństwa

▪

Teoria informacji

▪

Logika formalna

▪

Statystyka

▪

Teoria sterowania

▪

Psychologia

▪

Neurofizjologia

Metody automatycznego

uczenia się systemów

Uczenie się indukcyjne

Wnioskowania indukcyjnego polega na
przechodzenia od faktów i obserwacji
jednostkowych do ich uogólnień (fakty i
obserwacje są nazywane przykładami
trenującymi, a dostarczana uczniowi
informacja trenująca to zbiór przykładów
trenujacych.).

Metody automatycznego

uczenia się systemów

Rodzaje uczenia się indukcyjnego

▪

Uczenie sie sposobu klasyfikowania

obiektów

▪

Grupowanie obiektów

▪

Uczenie się aproksymacji

Metody automatycznego

uczenia się systemów

Metody

▪

Metoda Quinlana

▪

Algorytmy genetyczne

▪

Uczenie ze wzmocnieniem

▪

Sztuczne sieci neuronowe

Metody automatycznego

uczenia

Algorytmy genetyczne: definicja

Definicja: algorytmy genetyczne
polegają na generowaniu populacji
pewnych obiektów, które dopasowują się
do pewnych wymagań

Źródło: J.Mulawka “systemy ekspertowe”, WNT,
Warszawa 1996

Metody automatycznego

uczenia

Algorytmy genetyczne: literatura

●

Arabas J. Wykłady z algorytmów

ewolucyjnych, WNT, Warszawa 2001

●

Iwański C.,Szkatuła G.,”Wybrane

metody uczenia maszynowego dla
tworzenia reguł klsasyfikacji obiektów”,
prace IBS PAN Warszawa 1992.

●

Holland J. “Adaptation in Natural and

Artificial Systems”, Uniwersity of
Michigan Press, Ann Arbor, 1975

Metody automatycznego

uczenia

Algorytmy genetyczne: historia

Początek lat 70, prace Johna Hollanda na
Uniwesytecie Michigan

Procedure Prosty algorytm genetyczny
begin
t:=0
inicjacja P

0

ocena P

0

while (not warunek stopu) do

T

t

:=reprodukcja P

t

O

t

:= krzyżowanie i mutacja T

t

ocena O

t

P

t+1

:=O

t

t:=t+1

end
end

Metody automatycznego

uczenia

Algorytmy genetyczne: zasada działania

1

Dany jest ciąg symboli zwykle cyfr zwanych

łańcuchami (łańcuchy są zakodowanym opisem
obiektów lub rozwiązań pewnych zadań)

2

Należy znaleźć najlepszy łańcuch ze względu na

pewną funkcję wartościującą zwaną funkcją
użyteczności

3

Algorytm działa w powtarzających się cyklach.

4

Łańcuchy najmniej użyteczne są usuwane ze zbioru

zaś z pozostałych przy użyciu funkcji losowych buduje
się nowe łańcuchy

5

Trwa to tak długo aż nie nastąpi warunek końca

zwykle jest to moment gdy nowo powstające łańcuchy
nie zwiększają swojej użyteczności

Metody automatycznego

uczenia

Algorytmy genetyczne: operacje stosowane przez

algorytmy genetyczne

▪

Selekcja

▪

Krosowanie

▪

Mutacja

Metody automatycznego

uczenia

Algorytmy genetyczne: selekcja

Selekcja - wybór łańcuchów które wejdą
do następnej populacji.
Prawdopodobieństwo tego że łańcuch e

i

przejdzie pomyślnie selekcję wynosi:

p

f e

f e

i

i

j

j

n

=

=

å

( )

( )

1

Gdzie f(e

i

) - funkcja użyteczności

Metody automatycznego

uczenia

Algorytmy genetyczne: selekcja

Wartość oczekiwana E liczby kopii
łańcucha w następnej populacji
wynosi:

E = n * p

i

Gdzie
E - wartość oczekiwana
n - liczba elementów populacji
p

i

-prawdopodobieństwo tego że łańcuch

pomyślnie przejdze selekcję

Metody automatycznego

uczenia

Algorytmy genetyczne: krosowanie

1

Wybiera się losowo dwóch członków

populacji

2

Losuje się miejsce w którym ma nastąpić

rozcięcie chromosomów

3

Dokonuje się rozcięcia chromosomów w

wyznaczonym miejscu

4

Skleja się chromosomy w następujący

sposób: pierwsza część pierwszego
chromosomu z drugą częścią drugiego i
pierwsza część drugiego z drugą pierwszego.

5

Chromosomy powstałe ze sklejenia są

potomkami i zastępują rodziców

Metody automatycznego

uczenia

Algorytmy genetyczne: krosowanie

0 1 0 0 1 1 0 1 0
1 1 1

1 1 0 0 1 1 1 1 0
1 0 1

0 1 0 0 1 1 1 1 0
1 0 1

1 1 0 0 1 1 1 1 0
1 0 1

1 1 0 0 1 1 0 1 0
1 1 1

Metody automatycznego

uczenia

Algorytmy genetyczne: mutacja

Mutacja jest operacją określoną dla
jednego elementu składowego w
jednym chromosomie. Polega na
zamianie tego elementu na inny
dowolnie wybrany

1 1 0 0 1 1 0 1 0
1 1 1

1 1 0 0 1 1 0 1 1
1 1 1

Metody automatycznego

uczenia

Algorytmy genetyczne: kiedy zatrzymać algorytm

●

Nigdy ?

●

Kryterium maksymalnego kosztu - jeśli

koszt algorytmu przekroczy załozoną wartość
maksymalną K

max

to algorytm kończy

działanie

●

Kryterium zadowalającego - poziomu

funkcji użyteczności. Kryterum to jest
spełnione gdy algorytm znajdzie rozwiązanie
o wartości funkcji uzyteczności określonej
jako zadawalająca

●

Kryterium minimalnej szybkości naprawy.

Algorytm jest zatrzymywany jeśli w kolejnych
n generacjach nie uda się poprawić wyniku o
więcej niż założona wartość

Metody automatycznego

uczenia

Algorytmy genetyczne: metody oceny algorytmu

genetycznego

●

Wynik działania

●

Koszt symulacji

●

Zdolność opuszczania obszarów

przyciągania maksimum lokalnego

Metody automatycznego

uczenia

Algorytmy genetyczne: zastosowania

Zagadnienia optymalizacyje:

▪

Optymalizacja przepływu energii w

sieci elektrycznej

▪

Optymalizacja procesów

fermentacyjnych

▪

Wybór optymalnego kształtu

magnesu

Prognozowanie:

▪

Płynności finansowej

przedsiebiorstwa

▪

Cen akcji przedsiebiorstwa

Metody automatycznego

uczenia

Algorytmy genetyczne: przykład

Dana jest funkcja kwadratowa w
postaci:

f x

x

( )=

2

Należy znaleźć c z ptrzedziału
[0,31] dla którego funkcja
przyjmuje największą wartość

Metody automatycznego

uczenia

Algorytmy genetyczne: przykład

Każdy x z przedziału [0,31] ma
swój kod w systemie dwójkowym i
tak np:

19 1 2

0 2 1 2 1 2

4

3

1

0

=

+

+

+

*

*

*

*

Czyli odpowiada jej łańcuch
10011

Metody automatycznego

uczenia

Algorytmy genetyczne: przykład

W przypadku niniejszego przykładu
funkcja użyteczności ma postać:

y x

=

2

Czyli:

f

f

(

)

(8)

01000

8

64

2

=

= =

Metody automatycznego

uczenia

Algorytmy genetyczne: przykład

Nr

Popu-
lacja

Wartość
odkodowana

x

2

Użytec
z.

Użytec
z.
Część.

Wart.
Ocze
k.

Liczba
kopii

1

01101

13

169

0,14

0,58

1

2

11000

24

576

0,49

1,97

2

3

01000

8

64

0,06

0,22

0

4

10011

19

361

0,31

1,23

1

å

1170

Metody automatycznego

uczenia

Algorytmy genetyczne: przykład

0110

1100 0

1

01100

11001

11011

10000

1
1

1
0

000
011

Metody automatycznego

uczenia

Algorytmy genetyczne: przykład

Nr

Popu-
lacja

Wartość
odkodowana

x

2

Użytec
z.

Użytec
z.
Część.

Wart.
Ocze
k.

Liczba
kopii

1

01100

12

144

0,08

0,33

0

2

11001

25

625

0,36

1,42

1

3

11011

27

729

0,42

1,66

2

4

10000

16

256

0,14

0,58

1

å

1754

Metody automatycznego

uczenia

Algorytmy genetyczne: przykład

Dana jest funkcja kwadratowa w
postaci:

f x

x

( ) = - +

2

1

f x

( )

x

1

-1

1

Metody automatycznego

uczenia

Algorytmy genetyczne: przykład

●

Liczba genów - 11

●

Liczba osobników w populacji 29

●

Prawdopodobieństwo krzyżowania

0,6

●

Prawdopodobieństwo mutacji 0,001

Main.exe

Metody automatycznego

uczenia

Uczenie się ze wzmocnieniem: zasada działania

Jeśli wykonanie pewnej akcji w pewnym
stanie pociąga za sobą dobre
kosekwencje to tendencja do
wykonywania tej akcji powinna zostać
wzmocniona

Metody automatycznego

uczenia

Uczenie się ze wzmocnieniem: zasada działania

Uczenie ze wzmocnieniem - uczenie się
na podstawie prób i błędów

Zadaniem systemu uczacego jest
skonstruowanie strategii decyzyjnej
prowadzącej do maksymalizacji wartości
wzmocnienia otrzymywanych w długim
horyzoncie czasowym

Metody automatycznego

uczenia

Uczenie się ze wzmocnieniem: zasada działania

Formalizuje się to kryterium jako
wartość oczekiwaną całkowitej sumy
wzocnienia

E

r

t

t

t

[

]

g

=

¥

å

0

Gdzie : r

t

-wartość wzmocnienia w

kroku t

g Î [ , ]

01

Współczynnik
dyskontowania
określający względną
ważność wartości
wzmocnienia bliskich i
odległych w czasie

Metody automatycznego

uczenia

Uczenie się ze wzmocnieniem: zasada działania

▪

Kary

▪

Nagrody

▪

Algorytm czasowego przypisania

zasługi

Metody automatycznego

uczenia

Uczenie się ze wzmocnieniem - zasady

▪

Informacja trenująca ma charakter

wartościujący, uczeń nie otrzymuje
przy- kładów określających pożądany
sposób jego zachowania, lecz tylko
zwrotną ocenę, na ile jego obecne
zachowanie jest dobre.

▪

Informacja trenująca określa cel

zadania, a nie sposób jego realizacji.

▪

Uczenie się następuje na podstawie

prób i błędów.

▪

Uczenie się wykonywania zadania i

jego faktyczne wykonywanie odbywa
się łącznie

Metody automatycznego

uczenia

Algorytm Quinlana

Www.cse.unsw.edu.au./~quinlan/

Metody automatycznego

uczenia

Algorytm Quinlana

Quinlan zastosował podejście oparte na
teorii informacji. Drzewo decyzyjne może
być traktowane jako źródło informacji,
gdyż dla każdego obiektu generuje
wiadomość, do jakiej klasy należy ten
obiekt. Złożoność drzewa jest ściśle
związana ż ilością informacji jaką niesie
wygenerowana przez niego wiadomość

Metody automatycznego

uczenia

Algorytm Quinlana

Zgodnie teorią informacji, ilość informacji
zawarta w wiadomości generowanej
przez źródło, jest określona funkcją
entropii i wynosi

M S

p

p

i

i

n

i

( )

log

= -

=

å

1

2

Gdzie:
M(S) -wartość funkcji entropii dotycząca
informacji że obiekt należy do zbioru S
n - ilość informacji zawartej w wiadomości,
generowanej przez źródło
p - prawdopodobieństwo wygenerowania
informacji

Metody automatycznego

uczenia

Algorytm Quinlana

Wartość oczekiwana ilości informacji
generowanej po dokonaniu podziału ze
względu na cechę A

B S A

p v M S

i

i

n

i

( , )

( ) ( )

=

=

å

1

Gdzie:

A - oznacza cechę według której dzieli się zbiór S,

v

i

- wartości przyjmowane przez cechę A.

Metody automatycznego

uczenia

Algorytm Quinlana

Ilość informacji generowanej przez cały
fragment drzewa definiuje się jako:

M(S) -
B(S,A)

Gdzie:

B(S,A) - ilość informacji generowanej po podziele
drzewa ze wzgledu na cechę A
M(S) - ilość informacji w wiadomości że dany obiekt
należy do zbioru S

Szuka się cechy maksymalizujacej to
wyrażenie

Metody automatycznego

uczenia

Algorytm Quinlana

A

S

1

S

2

S

n

....

v

1

v

2

v

n

Metody automatycznego

uczenia

Algorytm Quinlana

Zbiór S zawiera następujące obiekty:

{ niski, blondyn, niebieskie: KŁASA 1
},
{ wysoki, blondyn, nlebieskie:
KLASA 1 },
{ wysoki, rudy, niebieskie: KLASA
1},
{ wysoki szatyn, niebieskie: KLASA 2
},
{ wysoki, blondyn, piwne: KLASA
2 },
{ wysoki, szatyn, piwne: KLASA 2 },
{ niski, szatyn, niebieskie: KLASA
2 },
{ niski, blondyn, piwne: KLASA 2 }.

M S

( )

log

log

,

= -

-

=

3

8

3

8

5

8

5

8

0954

2

2

Metody automatycznego

uczenia

Algorytm Quinlana

Rozbicie zbioru S ze względu na cechę S wzrost

Wzrost

{wysoki,blon,piwne: KLASA
2}
{wysoki,rudy,nieb.; KLASA
1}
{wysoki,szatyn,nieb.: KLASA
2} {wysoki,blon. ,nieb.:
KLASA 1}
{wysoki,szatyn,piwne.-
KLASA 2}

{niski,blon.nieb.: KLASA 1}
{niski,szatyn,nieb. : KLASA
2}
{niski,blon.,piwne; : KLASA
2}

Wysok
i

Niski

Metody automatycznego

uczenia

Algorytm Quinlana

Mwysoki

bitów

(

)

log

log

,

= -

-

=

2

5

2

5

3

5

3

5

0971

2

2

M niski

bitów

(

)

log

log

,

= -

-

=

1

3

1

3

2

3

2

3

0918

2

2

B Swzrost

( ,

)

,

,

,

=

+

=

5

8

0971

3

8

0918 0951

M S B Swzrost

( )

( ,

)

,

,

,

-

=

-

=

0954 0951 0003

Metody automatycznego

uczenia

Algorytm Quinlana

Rozbicie zbioru S ze względu na cechę S oczy

Włosy

{niski,szatyn,nieb.: KLASA 2}
{wysoki,szatyn,nieb.: KLASA
2} {wysokl,szatyn,piwne:
KLASA 2}

{niski,blon.,nieb.: KLASA
1}
{wysoki,blon.,piwne:
KLASA 2}
{wysoki, blon., nieb. ;
KLASA 1}
{niski,blon.,piwne: KLASA
2}

{wysoki,rudy,nieb.:
KLASA 1}

Szatyn

Rudy

Blondy
n

Metody automatycznego

uczenia

Algorytm Quinlana

Mszatyn

(

)=0

B Swlosy

( ,

)

,

=

+ + =

3

8

0

1

8

0

4
8

1 05

M S

B Swlosy

( )

( ,

)

,

,

,

-

=

-

=

0954 05 0454

Mrudy

(

)=0

M S B Soczy

( )

( ,

)

,

-

=0347

Metody automatycznego

uczenia

Algorytm Quinlana

Włosy

{niski,szatyn,nieb.: KLASA 2}
{wysoki,szatyn,nieb.: KLASA
2} {wysokl,szatyn,piwne:
KLASA 2}

{wysoki,rudy,nieb.:
KLASA 1}

Szatyn

Rudy

Blondy
n

Oczy

{niski, blon. ,nieb. : KLASA
1} {wysoki,blon.,nieb.:
KLASA 1}

{wysokl,blon.,piwne:
KLASA 2}
{niski,blon.piwne: KLASA
2}

Niebieski
e

Piwne

Metody automatycznego

uczenia

Algorytm Quinlana

Włosy

KLASA 2

KLASA 1

Szatyn

Rudy

Blondy
n

Oczy

KLASA 1

KLASA 2

Niebieski
e

Piwne