AI_18_1

Trzeba si

uczy

Obserwuj

rodowisko agent nie tylko zdobywa

wiedz

wiecie, ale tak

e mo

e ulepszy

swoje

działania w przyszło

ci.

Uczenie ma mie

ró

ne formy – mo

e polega

po prostu na gromadzeniu do

wiadcze

, ale mo

tak

e prowadzi

do stworzenia ogólnych teorii,

na miar

teorii Einsteina.

F.A. Dul 2007

na miar

teorii Einsteina.

Rozpoczniemy od omówienia uczenia indukcyjnego
na podstawie obserwacji w oparciu o logik

zda

Odpowiemy te

na pytanie, dlaczego uczenie działa?

18.1. Formy uczenia

Agent ucz

cy si

posiada:

Standard jako

Agent musi si

uczy

, je

eli musi działa

w nieznanym

rodowisku.

Uczenie jest metod

konstruowania agenta polegaj

na skonfrontowaniu agenta z rzeczywisto

zamiast

budowania dokładnego modelu jego działania.
Uczenie modyfikuje mechanizm podejmowania decyzji
agenta w celu polepszenia jego osi

gów.

© F.A. Dul 2007

Agent ucz

cy si

posiada:

Agent

Czujniki

Mechanizmy

wykonawcze

Generator

problemów

Krytyka

Sprz

ęŜ

enie

zwrotne

Zmiany

Wiedza

Cel

uczenia

Moduł

ucz

cy si

Moduł

decyzyjny

• moduł decyzyjny

, który

dokonuje wyboru działa

podstawie obserwacji,

• moduł ucz

cy si

, który

modyfikuje moduł decyzyjny
tak, aby podejmował on lepsze
decyzje.

Moduły ucz

ce si

mog

mie

ró

ne postacie, zale

ne od typu

agenta który ma si

uczy

18.1. Formy uczenia

• Rodzaju elementów modułu decyzyjnego

które maj

uczone (odwzorowanie stan-działanie, reprezentacja cech

rodowiska, model

rodowiska i działa

, u

yteczno

ść

stanów,

yteczno

ść

działa

, cel),

• Reprezentacji

nauczanych elementów (refleksowa, logiczna,

probabilistyczna).

• Sprz

ęŜ

enia zwrotnego

które mo

e by

yte do uczenia tych

elementów.

• Zakresu

wiedzy pocz

tkowej

(apriorycznej) agenta.

Posta

modułu ucz

cego zale

y od:

© F.A. Dul 2007`

• Zakresu

wiedzy pocz

tkowej

(apriorycznej) agenta.

• Uczenie nadzorowane

(supervised learning): wyznaczenie

funkcji na podstawie przykładów ucz

cych (danych i

odpowiedzi),

• Uczenie nienadzorowane

(unsupervised learning): wyznaczenie

funkcji na podstawie danych bez znajomo

ci odpowiedzi.

• Uczenie ze wzmocnieniem

(reinforcement learning):

wyznaczenie funkcji na podstawie oceny wyników działania
agenta (najbardziej ogólne).

Sprz

ęŜ

enie zwrotne jest najwa

niejszym czynnikiem

okre

laj

cym rodzaj uczenia:

18.2. Uczenie indukcyjne

Uczenie indukcyjne jest najprostsz

form

uczenia si

Agent powinien nauczy

funkcji celu

f (target function).

Uczenie realizowane jest za pomoc

wzorców

cych

parami (x, f(x)), x

∈

Zbiór wzorców jest

zbiorem ucz

cym

Zadanie uczenia indukcyjnego:

Znale

źć

hipotez

h nale

Ŝą

do przestrzeni hipotez H

© F.A. Dul 2007

Znale

źć

hipotez

h nale

Ŝą

do przestrzeni hipotez H

tak

e h przybli

a f dla danego zbioru ucz

cego

wzorców.

Dobra hipoteza h umo

liwia

uogólnienie

- prawidłow

klasyfikacj

wzorca nie nale

Ŝą

cego do zbioru ucz

cego.

Uczenie indukcyjne jest bardzo uproszczonym sposobem
uczenia si

, gdy

• ignoruje wiedz

aprioryczn

posiadan

przez agenta,

• zakłada,

e dysponujemy zbiorem ucz

cym.

××××

f(x)

18.2. Uczenie indukcyjne

Metoda uczenia indukcyjnego

Hipoteza h jest

zgodna

(consistent) je

eli pokrywa si

z funkcj

f dla wszystkich wzorców.

Dopasowanie hipotezy h tak, aby zgadzała si

z funkcj

celu

f na zbiorze ucz

cym mo

na osi

ąć

np. poprzez

dopasowanie krzywej (curve fitting).

= a

+ a

= a

+ a

x + a

= a

+ a

x + a

+ a

××××

© F.A. Dul 2007

Któr

zgodn

hipotez

nale

y zatem wybra

Brzytwa Ockhama

(Ockham’s razor): nale

y wybra

najprostsz

hipotez

zgodn

z danymi.

= a

+ a

18.2. Uczenie indukcyjne

Identyfikacja jako uczenie indukcyjne

Identyfikacja parametryczna

polega na wyznaczeniu

parametrów p

danego

modelu M(x(t);p) tak, aby predykcja

stanu x(t) była zgodna z obserwacjami y(t

), np. w sensie

normy

Identyfikacja parametryczna jest wi

c rodzajem uczenia

∑

∈

−

)

;

(

)

(

min

arg

© F.A. Dul 2007

Identyfikacja parametryczna jest wi

c rodzajem uczenia

indukcyjnego, w którym funkcja celu dana jest niejawnie
poprzez model zale

ny od parametrów.

Identyfikacja strukturalna

polega na wyznaczeniu struktury

modelu, np. w postaci grafu przepływu informacji, systemu
modeli przyczynowych, itp.

18.3. Uczenie drzew decyzyjnych

Drzewo decyzyjne jest struktur

funkcyjn

na wej

ciu której

atrybuty

, za

na wyj

ciu –

decyzja

Atrybuty oraz decyzja mog

dyskretne lub ci

głe.

Drzewo decyzyjne stanowi jedn

z mo

liwych reprezentacji

hipotez.
Drzewo decyzyjne mo

e reprezentowa

moduł decyzyjny

agenta.
Uczenie drzew decyzyjnych jest jedn

z najbardziej

© F.A. Dul 2007

Uczenie drzew decyzyjnych jest jedn

z najbardziej

ytecznych form uczenia.

Uczenie drzew decyzyjnych dyskretnych nazywa si

klasyfikacj

, za

głych –

regresj

Klasyfikacja boolowska u

ywa warto

ci Fałsz i Prawda.

Drzewo decyzyjne wyznacza decyzj

na podstawie ci

testów.
Ka

dy test dotyczy pewnego atrybutu, za

cie drzewa

okre

laj

wypracowane decyzje.

18.3. Uczenie drzew decyzyjnych

Przykład
Nale

y zdecydowa

czy czeka

na stolik w restauracji

opieraj

c si

na nast

puj

cych atrybutach:

• Alternatywa

: czy w pobli

u jest inna restauracja?

• Bar

: czy jest wygodny bar przy którym mo

na poczeka

• Pi

tek/Sobota

: czy jest pi

tek lub sobota?

• Głodny

: czy jeste

my głodni?

• Klienci

: liczba osób w restauracji (Brak, Kilku, Pełno);

© F.A. Dul 2007

• Klienci

: liczba osób w restauracji (Brak, Kilku, Pełno);

• Cena

: rozpi

ść

cen ($, $$, $$$);

• Deszcz

: czy pada na zewn

trz?

• Rezerwacja

: czy dokonali

my rezerwacji?

• Rodzaj

: rodzaj restauracji (francuska, włoska, tajska, Burger);

• Czas

: szacowany czas oczekiwania: 0-10, 10-30, 30-60, >60 min.

Decyzj

okre

la predykat

CzyCzeka

cy funkcj

atrybutów.

18.3. Uczenie drzew decyzyjnych

Reprezentacje oparte na atrybutach
Wzorce opisane s

przez

warto

ci atrybutów

(boolowskie,

dyskretne, ci

głe).

Zbiór ucz

dla zadania oczekiwania na stolik w restauracji.

Atrybuty

Przykład

Altern.

Bar

Pt/Sob

Głodny

Klienci

Cena

Deszcz

Rezer.

Rodzaj

Czas

Cel
Czy

Czeka

Tak

Nie

Tak

Kilku

$$$

Nie

Tak

Francuska

0-10

Tak

Nie

Tak

Pełno

Nie

Tajska

30-60

Nie

Tak

Nie

Kilku

Nie

Burger

0-10

Tak

Nie

Tak

Pełno

Nie

Tajska

10-30

Tak

© F.A. Dul 2007

Klasyfikacja

wzorców jest

pozytywna

(Tak) lub

negatywna

(Nie).

Tak

Nie

Tak

Pełno

Nie

Tajska

10-30

Tak

Nie

Tak

Nie

Pełno

$$$

Nie

Tak

Francuska

> 60

Nie

Tak

Nie

Tak

Kilku

Tak

Włoska

0-10

Tak

Nie

Tak

Nie

Brak

Tak

Nie

Burger

0-10

Nie

Tak

Kilku

Tak

Tajska

0-10

Tak

Nie

Tak

Nie

Pełno

Tak

Nie

Burger

> 60

Nie

Tak

Pełno

$$$

Nie

Tak

Włoska

10-30

Nie

Brak

Nie

Tajska

0-10

Nie

Tak

Pełno

Nie

Burger

30-60

Tak

18.3. Uczenie drzew decyzyjnych

Drzewo decyzyjne

Drzewo decyzyjne dla zadania oczekiwania na stolik
w restauracji.

Klienci

CzasOczekiwania

Fałsz

Prawda

Brak

Kilku

Pełno

> 60

60-30

30-10

Alternatywa ?

Głodny?

Fałsz

0-10

Prawda

© F.A. Dul 2007

Rezerwacja ?

tek/Sobota ?

PadaDeszcz ?

Bar ?

Nie

Tak

Fałsz

Prawda

Fałsz

Prawda

Nie

Tak

Nie

Tak

Nie

Tak

Alternatywa ?

Prawda

Fałsz

Prawda

Nie

Tak

Nie

Tak

Nie

Tak

Posta

logiczna drzewa decyzyjnego

∀

s CzyCzeka

(s)

⇔

( P

(s)

∨

(s)

∨

...

∨

(s) )

18.3. Uczenie drzew decyzyjnych

Ekspresyjno

ść

drzewa decyzyjnego

Drzewo decyzyjne mo

e reprezentowa

funkcj

atrybutów.
Funkcjom boolowskim lub wierszom tablic prawdy
odpowiadaj

cie

ki do li

ci.

Przykład

Drzewo decyzyjne dla funkcji logicznej XOR (eXclusive OR)

Fałsz

Prawda

A xor B

Fałsz

Prawda

© F.A. Dul 2007

Dla ka

dego zbioru ucz

cego mo

na zbudowa

trywialne

zgodne drzewo decyzyjne z jedn

cie

do li

cia dla

dego wzorca.

Takie drzewo nie mo

e jednak by

uogólnione dla nowych

wzorców i mo

e by

bardzo wielkie.

na jednak zbudowa

bardziej zwarte drzewa decyzyjne.

Fałsz

Prawda

Fałsz

Prawda

Fałsz

Prawda

Fałsz

Prawda

Fałsz

Prawda

Fałsz

Prawda

Fałsz

Prawda

18.3. Uczenie drzew decyzyjnych

Drzewa decyzyjne s

efektywne dla pewnych zada

, a dla

innych nie.
Nie ma ogólnej efektywnej reprezentacji dowolnej funkcji.

Uzasadnienie

Liczba wszystkich funkcji boolowskich z n atrybutami jest
równa liczbie opisuj

cych je tablic prawdy.

da tablica prawdy ma 2

wierszy.

Warto

ść

funkcji opisuje 2

cyfr (kolumna tablicy prawdy).

© F.A. Dul 2007

Warto

ść

funkcji opisuje 2

cyfr (kolumna tablicy prawdy).

Liczba ró

nych funkcji jest zatem równa

dla n = 6 atrybutów boolowskich liczba funkcji jest

równa

18,446,744,073,709,551,616 ~ 10

na jednak efektywnie budowa

drzewa decyzyjne

dla wielu problemów o znaczeniu praktycznym.

18.3. Uczenie drzew decyzyjnych

Uczenie drzewa decyzyjnego

Cel: zbudowa

„małe” drzewo zgodne z wzorcami ucz

cymi.

Idea: wybra

rekursyjnie ”najwa

niejsze" atrybuty jako

korzenie poddrzew.

8 12

Dobre atrybuty dziel

zbiór wzorców na podzbiory które (w

przypadku idealnym) s

w cało

ci pozytywne lub negatywne.

Przykład

© F.A. Dul 2007

Włoska Tajska

9 10 11

Burger

Francuska

Rodzaj

Klienci

Brak

Kilku

Pełno

7 11

9 10

9 10 11

Nie

Tak

Głodny?

Rodzaj

jest złym atrybutem dziel

cym,

gdy

utworzone podzbiory s

mieszane.

Klienci

lepszym atrybutem jako korze

drzewa, gdy

dwa podzbiory s

jednorodne.

18.3. Uczenie drzew decyzyjnych

Wybór atrybutów na podstawie teorii informacji
Ocena zdolno

ci atrybutu do efektywnego podziału zbioru

ucz

cego mo

e by

przeprowadzona za pomoc

poj

cia

pojemno

ci informacyjnej

(entropii):

∑

−

)

(

log

)

(

))

(

),...,

(

Dla zbioru ucz

cego zawieraj

cego p wzorców pozytywnych

i n wzorców negatywnych entropia jest równa:

© F.A. Dul 2007

−

log

)

(

i n wzorców negatywnych entropia jest równa:

bit

log

)

(

−

Przykład Dla zadania restauracyjnego mamy p = 6, n = 6,
zatem entropia jest równa

18.3. Uczenie drzew decyzyjnych

Wzmocnienie informacyjne

eli atrybut A dzieli zbiór ucz

cy E na podzbiory E

, … , E

które zawieraj

oraz n

wzorców pozytywnych i negatywnych

to ilo

ść

informacji potrzebna do klasyfikacji wzorców jest równa

Wzmocnienie informacyjne

(Information Gain, IG) lub

zmniejszenie entropii atrybutu A wynosi

∑

)

(

)

(

© F.A. Dul 2007

zmniejszenie entropii atrybutu A wynosi

Wybór atrybutów przy budowie drzewa decyzyjnego nast

puje

w kolejno

ci okre

lonej warto

ciami ich wzmocnienia

informacyjnego.

)

(

)

(

)

(

−

18.3. Uczenie drzew decyzyjnych

Przykład
Warto

ci wzmocnienia informacyjnego dla atrybutów Klienci

i Rodzaj s

równe:

bitów

0541

)]

(

)

(

)

(

[

)

(

−

Klienci

bitów

)]

(

)

(

)

(

)

(

[

)

(

−

Rodzaj

© F.A. Dul 2007

Warto

ść

IG(Klienci) jest wi

ksza ni

IG(Rodzaj) i dlatego

atrybut Klienci zostanie wybrany przez algorytm Decision Tree
Learning jako korze

drzewa decyzyjnego.

18.3. Uczenie drzew decyzyjnych

Nauczone drzewo decyzyjne

Drzewo decyzyjne nauczone na podstawie 12 wzorców.

Klienci

Fałsz

Prawda

Brak

Kilku

Pełno

Głodny?

Fałsz

Nie

Tak

Rodzaj

Francuska

Włoska

Tajska

Burger

© F.A. Dul 2007

Nauczone drzewo jest du

o prostsze ni

drzewo wyj

ciowe.

Drzewo to ukazuje nieznan

wcze

niej własno

ść

- gotowo

ść

oczekiwania w weekendy na tajskie posiłki.
Drzewo odpowiadaj

ce hipotezie h bli

szej prawdziwej funkcji

f mo

na uzyska

na podstawie wi

kszej ilo

ci wzorców.

tek/Sobota ?

Fałsz

Prawda

Nie

Tak

Fałsz

Prawda

Francuska

Włoska

Tajska

Prawda

Burger

18.3. Uczenie drzew decyzyjnych

Miara jako

ci uczenia

Hipoteza h dobrze przybli

a funkcj

celu f je

eli poprawnie

klasyfikuje wzorce nieznane wcze

niej.

Metodologia oceny a posteriori jako

ci uczenia:

• Zebra

y zbiór wzorców.

• Podzieli

zbiór wzorców na

zbiór ucz

zbiór

testowy.

• Wyznaczy

hipotez

h za pomoc

algorytmu ucz

cego

• Wyznaczy

hipotez

h za pomoc

algorytmu ucz

cego

przy wykorzystaniu wzorców ze zbioru ucz

cego.

• Wyznaczy

udział poprawnie sklasyfikowanych

wzorców ze zbioru testowego przy u

yciu hipotezy h.

• Powtórzy

procedur

dla zbiorów testowych o ró

nych

wymiarach.

18.3. Uczenie drzew decyzyjnych

Krzywa ucz

obrazuje

udział poprawnych dopasowa

wzorców ze zbioru testowego
w funkcji wymiaru zbioru
ucz

cego.

Wraz ze wzrostem wymiaru
zbioru ucz

cego wzrasta

stopie

poprawno

klasyfikacji za pomoc

hipotezy h.

Zagl

danie

(peeking) jest bł

dem uczenia polegaj

cym

na „przeciekaniu” informacji ze zbioru testowego w trakcie
procesu nauczania.
Zagl

danie powoduje spadek jako

ci klasyfikacji za pomoc

tak otrzymanej hipotezy.
Zagl

daniu mo

na zaradzi

poprzez starann

separacj

zbiorów ucz

cych i testowych.

18.3. Uczenie drzew decyzyjnych

Przeuczenie (overfitting)

Gdy przestrze

hipotez jest zbyt obszerna mo

e wyst

zjawisko

przeuczenia

Przeuczenie wyst

puje najcz

ęś

ciej wtedy, gdy:

Pocz

tek

przeuczenia

• uczenie trwa zbyt długo,
• zbiór ucz

cy jest za mały.

• u

ywa si

parametrów

nie zwi

zanych przyczynowo

z funkcj

celu.

Przy przeuczeniu bł

d dopasowania

wzorców ze zbioru ucz

cego spada,

bł

d dopasowania wzorców

ze zbioru testowego ro

nie.

z funkcj

celu.

Przeuczenia mo

na unikn

ąć

przeprowadzaj

c testy, np. wali-

dacji skro

nej (cross-validation) czy wczesnego zako

czenia.

Pozwalaj

one stwierdzi

, czy dalsze uczenie prowadzi

do otrzymania lepszych uogólnie

Przeuczenie mo

e wyst

we wszystkich rodzajach uczenia.

18.4. Uczenie zespołowe

Uczenie zespołowe (ensemble learning) obejmuje zbiór hipotez.
Istota uczenia zespołowego polega na wyznaczeniu zbioru
hipotez a nast

pnie ł

czeniu wyników ich przewidywa

na zbudowa

kilka drzew decyzyjnych na podstawie tego

samego (du

ego) zbioru ucz

cego i u

ich do klasyfikacji

poprzez

głosowanie

Głosowanie wi

kszo

ciowe umo

liwia poprawienie jako

klasyfikacji, gdy

prawdopodobie

stwo bł

dnej klasyfikacji

klasyfikacji, gdy

prawdopodobie

stwo bł

dnej klasyfikacji

przez wi

kszo

ść

drzew jest małe.

–

ycie pi

ciu hipotez zamiast jednej

redukuje prawdopodobie

stwo bł

dnej

klasyfikacji z 1/10 do 1/100.
Uczenie zespołowe pozwala rozszerzy

przestrze

hipotez.

Trzy hipotezy pozwalaj

kwalifikowa

wzorce w obszarze, czego nie mo

łatwo osi

ąć

przy pomocy pojedy

czej hipotezy.

18.5. Obliczeniowa teoria uczenia

Dlaczego uczenie jest skuteczne?
Podstawowa zasada

obliczeniowej teorii uczenia:

Zła hipoteza zostanie prawie na pewno wykryta
na podstawie niewielkiej liczby przykładów ucz

cych,

gdy

jej przewidywania b

niewła

ciwe.

eli hipoteza jest potwierdzona przez du

Ŝą

liczb

przykładów

ucz

cych, to jest mało prawdopodobne aby była zła.

Taka hipoteza jest

prawdopodobnie w przybli

eniu poprawna

Taka hipoteza jest

prawdopodobnie w przybli

eniu poprawna

(probably approximately correct, PAC).

Algorytm PAC – algorytm ucz

cy oparty na hipotezie PAC.

Zało

enie podstawowe (o stacjonarno

ci): zbiory ucz

i testowe s

wybrane losowo i s

niezale

ne.

Zakłada si

e przykłady ucz

ce s

typowe dla zadania

– nie s

„dziwne” (np. trójkołowe samochody, itp.), gdy

wówczas uogólnienia mog

niemiarodajne (np. przy

rozpoznawaniu samochodów).

18.5. Obliczeniowa teoria uczenia

Liczba przykładów ucz

cych

Oznaczenia:

Bł

d hipotezy h wzgl

dem funkcji celu f

∈

H przy danym

zbiorze D jest to prawdopodobie

stwo tego,

e h ró

ni si

od f na pewnym przykładzie z D,

e(h) = P( h(x) ≠ f(x) | x

∈

D ).

• X – zbiór wszystkich mo

liwych przykładów,

• D –

ródło przykładów,

• H – zbiór mo

liwych hipotez,

• N – liczba przykładów w zbiorze ucz

cym.

e(h) = P( h(x) ≠ f(x) | x

∈

D ).

Hipoteza jest

poprawna w przybli

eniu

, je

eli

e(h) ≤

–

małe

Hipotezy zgodne le

Ŝą

w kole o

rodku w f i promieniu

złe

Liczba N przykładów ucz

cych dla

których wszystkie hipotezy zgodne b

w przybli

eniu poprawne jest równa

(ln

≥

– prawdopodobie

stwo,

e bł

hipotezy jest mniejszy ni

Uczenie agenta indukcyjnego

Uczenie indukcyjne to w istocie aproksymacja funkcji
na podstawie danych do

wiadczalnych.

Uczenie drzew decyzyjnych ma charakter
identyfikacji strukturalnej – buduje si

struktur

drzewa na podstawie danych.

Agent ucz

cy si

indukcyjnie jest „tabula rasa”

– nie wie niczego o

wiecie i niczego nie pami

ta.

F.A. Dul 2007

– nie wie niczego o

wiecie i niczego nie pami

ta.

e on znacznie podwy

szy

efektywno

ść

i jako

ść

uczenia poprzez wykorzystanie wiedzy wiedzy
posiadanej a priori.

Bardziej zaawansowany agent b

dzie zatem

wykorzystywał

uczenie z wiedz

Podsumowanie

• Uczenie jest niezb

dne przy niepewnym

rodowisku.

• Agent ucz

cy si

= moduł decyzyjny + moduł ucz

cy si

• Uczenie przybiera wiele form zale

nych od struktury agenta

i rodzaju ucz

cego sprz

ęŜ

enia zwrotnego.

• Uczenie indukcyjne wykorzystuje wzorce ucz

ce - zbiór par

wej

cie i wyj

cie.

• Uczenie funkcji dyskretnej to klasyfikacja, za

funkcji ci

głej

to regresja.

• Uczenie indukcyjne polega na znalezieniu hipotezy zgodnej

z danymi wzorcami.

• Brzytwa Ochkama sugeruje wybór hipotezy najprostszej.
• Identyfikacja modelu jest form

uczenia indukcyjnego.

• Drzewo decyzyjne uczy si

przy wykorzystaniu

wzmocnienia informacyjnego.

• Przeuczenie polega na nadmiernym dopasowaniu hipotezy

do wzorców i prowadzi do bł

dnych klasyfikacji.

• Jako

ść

uczenia wyra

a si

dokładno

wzorców mierzon

na zbiorze testowym (innym ni

zbiór ucz

cy).

F.A. Dul 2007