Systemy Wspomagania

Decyzji (SWD)

Wykład 2 cz 2. Metody sztucznej

inteligencji we wspomaganiu decyzji

–metody automatycznego uczenia i

reprezentacja niepewności.

dr Jarosław Olejniczak
[e-mail]
u.pl

Automatyczne uczenie się

definicje

Uczeniem się systemu jest każda
autonomiczna 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

Uczenie się - modyfikacja
zachowania się jednostki w wyniku
jej dotychczasowych doświadczeń

Encyklopedia multimedialna PWN, 2004.

Automatyczne uczenie się

Klasyfikacja

Lp.

Nazwa kryterium

Rodzaje systemów

1.

Metoda reprezentacji

wiedzy lub
umiejętności

» Symboliczne
» Subsymboliczne

2.

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

» Klasyfikacja
» Aproksymacja

3.

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

» Uczenie się z
nadzorem

» Uczenie się bez
nadzoru

4.

Mechanizm nabywania
i doskonalenia wiedzy
lub umiejętności

» Indukcyjne
» Nieindukcyjne

Automatyczne uczenie się

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ę.

Automatyczne uczenie się

Nauka o uczeniu się – dziedziny

pokrewne

• Teoria prawdopodobieństwa
• Teoria informacji
• Logika formalna
• Statystyka
• Teoria sterowania
• Psychologia
• Neurofizjologia

Automatyczne uczenie się

Uczenie się indukcyjne

Wnioskowanie indukcyjne polega na
przechodzeniu 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
trenujących).

Automatyczne uczenie się

Rodzaje uczenia się indukcyjnego

• Uczenie się sposobu klasyfikowania

obiektów

• Grupowanie obiektów
• Uczenie się aproksymacji

Automatyczne uczenie się

Metody maszynowego uczenia się

•drzewa klasyfikacyjne,
•algorytmy genetyczne,
•metoda uczenia się ze
wzmocnieniem,
•sztuczne sieci neuronowe.

Automatyczne uczenie się

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

Automatyczne uczenie się

Algorytmy genetyczne - historia

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

Procedure Prosty algorytm
genetyczny
begin
t:=0
inicjacja P0
ocena P0
while (not warunek stopu) do
Tt :=reprodukcja Pt
Ot := krzyżowanie i mutacja Tt
ocena Ot
Pt+1:=Ot
t:=t+1
end
end

Automatyczne uczenie się

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

Automatyczne uczenie się

Algorytmy genetyczne – funkcje

•Selekcja
•Krosowanie
•Mutacja

Automatyczne uczenie się

Algorytmy genetyczne – selekcja

Selekcja - wybór łańcuchów które
wejdą do następnej populacji.
Prawdopodobieństwo tego że
łańcuch nie przejdzie pomyślnie
selekcję wynosi:

Gdzie f(e

i

) - funkcja użyteczności

Automatyczne uczenie się

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ę

Automatyczne uczenie się

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

Automatyczne uczenie się

Algorytmy genetyczne – krosowanie

Automatyczne uczenie się

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

Automatyczne uczenie się

Algorytmy genetyczne – kiedy zatrzymać

algorytm

• Nigdy ?
• Kryterium maksymalnego kosztu - jeśli

koszt algorytmu przekroczy założoną
wartość maksymalną K

max

to algorytm

kończy działanie

• Kryterium zadowalającego - poziomu

funkcji użyteczności. Kryterium to jest
spełnione gdy algorytm znajdzie
rozwiązanie o wartości funkcji
użytecznoś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ść

Automatyczne uczenie się

Algorytmy genetyczne – metody oceny

•Wynik działania
•Koszt symulacji
•Zdolność opuszczania obszarów

przyciągania maksimum lokalnego

Automatyczne uczenie się

Algorytmy genetyczne – zastosowania

Zagadnienia optymalizacyjne:

•Problem komiwojażera
•Optymalizacja przepływu energii w sieci

elektrycznej

•Wybór optymalnego kształtu magnesu

Prognozowanie:

•Płynności finansowej
przedsiębiorstwa
•Cen akcji przedsiębiorstwa

Automatyczne uczenie się

Algorytmy genetyczne – przykład

Dana jest funkcja kwadratowa w postaci:

2

)

(

x

x

f



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

Automatyczne uczenie się

Algorytmy genetyczne – przykład

2

)

(

x

x

f



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

Automatyczne uczenie się

Algorytmy genetyczne – przykład

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

Czyli odpowiada jej łańcuch 10011

19 = 1*2

4

+ 0*2

3

+ 0*2

2

+ 1*2

1

+

1*2

0

Automatyczne uczenie się

Algorytmy genetyczne – przykład

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

y = x

2

Czyli

f(01000) = f(8) = 8

2

= 64

Automatyczne uczenie się

Algorytmy genetyczne – przykład

Automatyczne uczenie się

Algorytmy genetyczne – przykład

Automatyczne uczenie się

Algorytmy genetyczne – przykład

Automatyczne uczenie się

Uczenie ze wzmocnieniem

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

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

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

Automatyczne uczenie się

Uczenie ze wzmocnieniem

•Informacja trenująca ma charakter

wartościujący, uczeń nie otrzymuje
przykł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

Automatyczne uczenie się

Drzewa klasyfikacyjne – 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ść

Automatyczne uczenie się

Drzewa klasyfikacyjne – algorytm Quinlana

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

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

Automatyczne uczenie się

Drzewa klasyfikacyjne – algorytm Quinlana

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

Gdzie:

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

v

i

- wartości przyjmowane przez cechę A.

Automatyczne uczenie się

Drzewa klasyfikacyjne – algorytm Quinlana

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

M(S) - B(S,A)

Szuka się cechy maksymalizującej to
wyrażenie

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

Automatyczne uczenie się

Drzewa klasyfikacyjne – algorytm Quinlana

Automatyczne uczenie się

Drzewa klasyfikacyjne – algorytm Quinlana

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

{ niski, blondyn, niebieskie: KŁASA 1 },
{ wysoki, blondyn, niebieskie: 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 }.

Automatyczne uczenie się

Algorytm Quinlana - przykład

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

Automatyczne uczenie się

Algorytm Quinlana - przykład

Automatyczne uczenie się

Algorytm Quinlana - przykład

Rozbicie zbioru S ze względu na cechę S włosy

Automatyczne uczenie się

Algorytm Quinlana - przykład

Automatyczne uczenie się

Algorytm Quinlana - przykład

Automatyczne uczenie się

Algorytm Quinlana - przykład