Metody automatycznego
uczenia się systemów
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