MSI 2006 w4

background image

Metody sztucznej inteligencji

wykªad 4

(dla studentów Wydziaªu MT Politechniki ‘laskiej

- na prawach rekopisu)

06 kwietnia 2006

background image

Obliczanie prawdopodobie«stw zdarze«

Prawdopodobie«stwo, »e oboje John i Mary zadzwonia, je±li sªy-
cha¢ alarm pomimo »e nie bedzie ani wªamania, ani trzesienia
ziemi:

P(J ∧ M ∧ A ∧ ¬B ∧ ¬E)

= P(J |A)P(M |A)P(A|¬B ∧ ¬E)P(¬B)P(¬E)

= 0.90 × 0.70 × 0.001 × 0.999 × 0.998 = 0.00062

1

background image

Budowanie sieci przekona«

Sie¢ przekona« jest zbudowana poprawnie, je±li ka»dy wezeª
jest warunkowo niezale»ny od swoich poprzedników w upo-
rzadkowaniu wezªów

Rodzicami wezªa X

i

powinny by¢ wszystkie takie wezªy, które

bezpo±rednio wpªywaja na ten wezeª:

P(X

i

|X

i−1

, . . . , X

1

) = P(X

i

|P arents(X

i

))

(1)

przy zaªo»eniu, »e P arents(X

i

)

⊆ {X

i−1

, . . . , X

1

}

2

background image

Ogólna procedura

Wybierz zbiór relewantnych zmiennych {X

i

}

opisujacych dziedzine

Wybierz uporzadkowanie zmiennych {X

i

}

Dopóki pozostaja jeszcze zmienne w {X

i

}

:

wybierz zmienna X

i

i dodaj dla niej wezeª do sieci

ustal minimalny zbiór zmiennych P arents(X

i

)

warunkowo

niezale»nych

okre±l tablice prawdopodobie«stw warunkowych dla tego

wezªa

3

background image

Wnioskowanie w sieciach przekona«

Zadaniem systemu wnioskowania probabilistycznego jest oblicze-
nie rozkªadu prawdopodobie«stwa a posteriori dla zbioru zmien-
nych zapytania (query variables), gdy dane sa dokªadne warto±ci
zmiennych-dowodów (evidence variables)

4

background image

Rodzaje wnioskowania w sieciach przekona«

(1)

Wnioskowanie diagnostyczne (od efektów do przyczyn)

Wiemy »e JohnCalls

wnioskujemy P(Burglary|JohnCalls) = 0.016

Wnioskowanie przyczynowe (od przyczyn do efektów)

Wiemy, »e Burglary

wnioskujemy P(JohnCalls|Burglary) = 0.86,

P(M aryCalls|Burglary) = 0.67

5

background image

Rodzaje wnioskowania w sieciach przekona«

(2)

Wnioskowanie miedzyprzyczynowe (pomiedzy przyczynami
wspólnego skutku)

je±li wiemy, »e Alarm, to P(Burglary|Alarm) = 0.376

gdy wiemy dodatkowo, »e Earthquake, to

P(Burglary|Alarm ∧ Earthquake) = 0.003

6

background image

Rodzaje wnioskowania w sieciach przekona«

(3)

Wnioskowanie mieszane (ªaczy dwa lub wiecej powy»szych
rodzajów wnioskowa«):

JohnCalls = T rue (efekt) oraz Eartquake = F alse (przy-

czyna) daje:
P(Alarm|J ohnCalls ∧ ¬Eartquake) = 0.03

[jednoczesne zastosowanie wnioskowania diagnostycznego
i przyczynowego]

P(Burglary|J ohnCalls ∧ ¬Eartquake) = 0.0017

[jednoczesne zastosowanie wnioskowania diagnostycznego
i miedzyprzyczynowego]

7

background image

Zastosowanie sieci przekona«

Podstawowe: Obliczanie warto±ci miary przekonania (ang. be-

lief ) dotyczacego zmiennych zapytania, gdy sa okre±lone warto±ci
dowodów

Inne: • Podejmowanie decyzji opartych na prawdopodobie«st-

wach reprezentowanych w sieci i warto±ciach u»yteczno±ci
dla agenta

Decydowanie jakie dodatkowe dowody zgromadzi¢, by pozyska¢
u»yteczna informacje

Analiza wra»liwo±ci w celu okre±lenia które atrybuty maja
najwiekszy wpªyw na prawdopodobie«stwo wyniku

8

background image

Wnioskowanie w wielokrotnie poªaczonych

sieciach przekona«

Metody grupowania

transformacje sieci w probabilistycznie równowa»ne polidrzewo

Metody warunkowania

transformacja poprzez konkretyzacje zmiennych poprzez pod-
stawienia, a nastepnie poprzez analize polidrzew dla ka»dego
mo»liwego podstawienia

Symulacja stochastyczna

9

background image

Przykªad sie¢ wielokrotnie poªaczona (1)

Cloudy

Sprinkler

Rain

Wet grass

Cloudy

Cloudy

Sprinkler

Sprinkler

Rain

Rain

Wet grass

Wet grass

P(C)=0.5

P(C)=0.5

C
T
F

P(S)
0.10
0.50

C
T
F

P(S)
0.10
0.50

C
T
F

P(S)
0.10
0.50

C
T
F

P(R)
0.80
0.20

C
T
F

P(R)
0.80
0.20

C
T
F

P(R)
0.80
0.20

S
T
T
F
F

R
T
F
T
F

P(W)
0.99
0.90
0.90
0.00

S
T
T
F
F

R
T
F
T
F

P(W)
0.99
0.90
0.90
0.00

S
T
T
F
F

R
T
F
T
F

S
T
T
F
F

R
T
F
T
F

P(W)
0.99
0.90
0.90
0.00

10

background image

Przykªad sie¢ wielokrotnie poªaczona (2)

Cloudy

Cloudy

Spr+Rain

Spr+Rain

Wet grass

Wet grass

P(C)=0.5

P(C)=0.5

S +
T
T
F
F

R
T
F
T
F

P(W)
0.99
0.90
0.90
0.00

S +
T
T
F
F

R
T
F
T
F

P(W)
0.99
0.90
0.90
0.00

S +
T
T
F
F

R
T
F
T
F

S +
T
T
F
F

R
T
F
T
F

P(W)
0.99
0.90
0.90
0.00

C
T
F

P(S+R=x)

TT
.08
.40

TF
.02
.10

FT
.72
.40

FF
.18
.10

C
T
F

P(S+R=x)

TT
.08
.40

TF
.02
.10

FT
.72
.40

FF
.18
.10

C
T
F

P(S+R=x)

TT
.08
.40

TF
.02
.10

FT
.72
.40

FF
.18
.10

11

background image

Przykªad sie¢ wielokrotnie poªaczona (2)

Sprinkler

Rain

Wet grass

+Cloudy

+Cloudy

Sprinkler

Sprinkler

Rain

Rain

Wet grass

Wet grass

+Cloudy

+Cloudy

+Cloudy

+Cloudy

Sprinkler

Rain

Wet grass

-Cloudy

-Cloudy

Sprinkler

Sprinkler

Rain

Rain

Wet grass

Wet grass

-Cloudy

-Cloudy

-Cloudy

-Cloudy

Transformacja polidrzewa na kilka prostszych polidrzew.

P(X|E)

jest obliczane jako ±rednia wa»ona warto±ci obliczonych

dla ka»dego polidrzewa

12

background image

Metoda symulacji stochastycznej

Ka»da runde symulacji rozpoczyna losowy wybór warto±ci
dla ka»dego wezªa poczatkowego sieci (z uwzglednieniem
prawdopodobie«stw a priori)

Warto±ci w wezªach po±rednich przyjmuje sie losowo z uwzgled-
nieniem prawdopodobie«stw warunkowych

Po wystarczajacej liczbie iteracji estymuje sie

P(X|E) ≈ N(X ∧ E)/N(E)

gdzie N liczby uzyskanych wyników

13

background image

Inne podej±cia do rozumowania niepewnego

Rozumowanie domy±lne (default reasoning)

Podej±cie bazujace na reguªach

Teoria Dempstera-Schafera

Zbiory rozmyte i logika rozmyta

14

background image

Rozumowanie domy±lne (przykªad)

Widze samochód parkujacy na ulicy. Chocia» widze jedynie
jego trzy koªa, przyjmuje do wiadomo±ci, »e ma cztery koªa.

Ten wniosek przyjmuje domy±lnie, ze wzgledu na brak in-
nych dowodów wskazujacych na to, »e ten samochód ma
inna liczbe kóª ni» cztery.

Takie rozumowanie nie jest monotoniczne.

15

background image

Metody bazujace na reguªach

Systemy bazujace na reguªach sa monotoniczne.

Przykªad: system MYCIN, w którym zastosowano stopie«
pewno±ci (certainty factor).

16

background image

Reprezentowanie ignorancji

Stopie« przekonania to prawdopodobie«stwo zdarzenia, »e
dowody wspieraja stwierdzenie

Miara jest funkcja przekonania (belief ) Bel(X)

Dla poszczególnych zdarze« deniowane sa przedziaªy mini-
malnego i maksymalnego przekonania o sªuszno±ci danego
stwierdzenia

Szeroko±¢ przedziaªu odpowiada naszej niewiedzy; gdy jest
zbyt szeroki, nale»y zebra¢ dalsze dowody

17

background image

Zbiory rozmyte i logika rozmyta (1)

Rodzaj rozumowania niepewnego

Dla elementu deniuje sie dodatkowo funkcje przynale»no±ci

do danego zbioru

Mo»liwa jest przynale»no±¢ cze±ciowa

0

1

m(A)

100

140

180

220

260

18

background image

Zbiory rozmyte i logika rozmyta (2)

W logice rozmytej rozwa»a sie rozmyty stopie« prawdzi-
wo±ci
T(A) =

stopie« prawdziwo±ci zdarzenia A

Reguªy obliczania T ( ) dla zda« zªo»onych:

T(A ∧ B) = min{T(A), T(B)}

T(A ∨ B) = max{T(A), T(B)}

T(

¬A) = 1 − T(A)

Uwaga!! T(A ∨ ¬A) 6= T(T rue)!!

19

background image

Probabilistyczne systemy rozumowania

podsumowanie (1)

Warunkowa niezale»no±¢ umo»liwia strukturalizacje informa-
cji o niepewnej dziedzinie

Sieci przekona« sa naturalnym ±rodkiem reprezentacji infor-
macji o warunkowej niezale»no±ci

Sie¢ przekona« reprezentuje ªaczny rozkªad prawdopodobie«-
stwa dla danej dziedziny

20

background image

Probabilistyczne systemy rozumowania

podsumowanie (2)

Rozumowanie w sieci przekona« polega na obliczeniu rozkªadu
prawdopodobie«stwa dla zbioru zmiennych zapytania, gdy
dany jest zbiór dowodów

Sieci przekona« sa najbardziej uniwersalne ze wzgl. na mo»li-
wo±¢ stosowania ró»nych typów wnioskowania (diagnosty-
czne, przyczynowe, miedzyprzyczynowe, mieszane)

21

background image

Probabilistyczne systemy rozumowania

podsumowanie (3)

Stopie« zªo»ono±ci rozumowania w sieci przekona« zale»y od

struktury sieci (najªatwiej dla polidrzew)

Dla bardziej zªo»onych sieci istnieje wiele ró»nych metod

rozumowania

Do wnioskowania mo»na stosowa¢ stochastyczna symulacje

(wymaga mniej oblicze«)

Znanych jest wiele innych metod wnioskowania z uwzglednie-

niem niepewno±ci

22

background image

Uczenie (si¦) na podstawie ob-

serwacji

23

background image

Gªówna idea

Percepcje s¡ wykorzystywane nie tylko do wyboru odpowied-
niej akcji, lecz tak»e do powi¦kszania zdolno±ci systemu
wnioskowania (agenta) do dziaªania w przyszªo±ci (ucze-
nia si¦)

Uczenie si¦ zachodzi jako wynik interakcji pomi¦dzy sys-
temem wnioskowania (agentem) i otoczeniem

Jest wiele form uczenia, od zapami¦tywania do tworzenia
zªo»onych teorii

24

background image

Ogólny model systemu wnioskowania

(agenta) ucz¡cego si¦ (1)

25

background image

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«

26

background image

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 klasykacji)

uczenie ze wzmocnieniem (agent jest nagradzany lub

karany, w zale»no±ci od wyniku akcji; klasykacja nie jest

agentowi znana)

uczenie nienadzorowane (klasykacja nieznana)

Rola wiedzy podstawowej - uczenie zwi¦ksza nieznacznie

wiedz¦ posiadan¡ przez agenta

27

background image

Indukcja drzew decyzyjnych

Jeden z najprostszych algorytmów uczenia maszynowego

Šatwa do wdro»enia

28

background image

Cechy drzew decyzyjnych

Obiekty s¡ opisane przez zbiory ich cech

Drzewo zwraca klasykacj¦ (decyzj¦) TAK/NIE (mog¡ by¢
przypadki wieloklasowe - bardziej ogólne)

Drzewo reprezentuje funkcj¦ Boolowsk¡

29

background image

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¡d-
kowana jest jedna warto±¢ atrybutu w¦zªowego

Li±ciom przyporz¡dkowane s¡ warto±ci Boolowskie, zwracane
je±li osi¡gni¦to dany li±¢

30

background image

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: szacowany
czas oczekiwania w min.

31

background image

Czy czeka¢ na stolik?

32

background image

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:
Najbardziej prawdopodobna jest najprostsza spo±ród hipotez
zgodnych ze wszystkimi obserwacjami

33

background image

Algorytm indukcji drzew decyzyjnych

34

background image

Algorytm indukcji drzew decyzyjnych

35

background image

Uwagi dotycz¡ce indukcji drzew

Podstawowy problem - wybór

Indukcja niezupeªna (nie mamy wszystkich mo»liwych przy-
kªadów)

Programy realizuj¡ce uczenie maszynowe dziaªaj¡ bardzo szy-
bko i efektywnie

Drzewa decyzyjne mog¡ by¢ bardzo rozbudowane - cz¦sto si¦
je przycina kosztem nieco gorszej sprawno±ci klasykacji

36

background image

Ocena sprawno±ci algorytmu uczenia (1)

Zgromad¹ dostatecznie liczny zbiór przykªadów

Podziel go na rozª¡czne zbiory: trenuj¡cy i 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 po-

prawnie klasykowana przez H

Powtarzaj te kroki dla zbiorów trenuj¡cych ró»nych wiel-

ko±ci, losowo wybieranych

37

background image

Ocena sprawno±ci algorytmu uczenia (2)

Ilo±¢ informacji [bity] zawartej w poprawnej odpowiedzi, gdy zbiór trenu-

j¡cy zawiera p przykªadów pozytywnych i n negatywnych:

I(

p

p + n

,

n

p + n

) =

p

p + n

log

2

p

p + n

n

p + n

log

2

n

p + n

(2)

Ilo±¢ informacji dost¦pna po testowaniu atrybutu A:

P ozostalo(A) =

ν

X

i=1

p

i

+ n

i

p + n

I(

p

i

p

i

+ n

i

,

n

i

p

i

+ n

i

)

(3)

Atrybut A dzieli zbiór E na podzbiory E

1

, . . . , E

ν

; p

i

, n

i

to liczby przykªadów

pozytywnych i negatywnych w tym podzbiorze

Przyrost ilo±ci informacji:

Gain(A) = I(

p

p + n

,

n

p + n

)

− P ozostalo(A)

(4)

38

background image

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) - wyma-
gana dyskretyzacja

39

background image

Niektóre problemy

Bª¦dne dane (np. sprzeczne przykªady - takie same warto±¢
atrybutów warunku, ró»ne warto±ci atrybutu decyzyjnego)
drzewo klasykuje bª¦dnie

Nadmierne dopasowanie zbyt szczegóªowy klasykator, du»o
bª¦dów dla nowych przykªadów

Rada - PRZYCINANIE DRZEWA

40

background image

Podstawowe pytanie

Sk¡d wiadomo, »e algorytm uczenia pozwoliª utworzy¢ teori¦,
która b¦dzie poprawna?

41

background image

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 wystar-
czaj¡co licznym zbiorem trenuj¡cym, byªa powa»nie bª¦d-
na

Uczenie PAC (Probably Approximately Correct)

42

background image

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

43

background image

Ile potrzeba przykªadów (2)?

Bª¡d (h ∈ H ró»ne od aproksymowanej funkcji f):

error(h) = P{h(x) 6= f (x) | x wylosowane z D}

(5)

Hipoteza jest w przybli»eniu poprawna, je±li dla maªej liczby
ε

:

error(h) ≤ ε

(6)

Gdy δ dopuszczalne prawdopodobie«stwo bª¦dnej hipotezy:

m ≥

1

ε

ln

1

δ

+ ln

|H|

(7)

44

background image

Podsumowanie (1)

Zdolno±¢ uczenia si¦ systemu wnioskowania (agenta) jest is-
totna 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 modykowanie

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¦

45

background image

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¦ zde-
terminowanych funkcji Boole'a

46

background image

Podsumowanie (3)

Brzytwa Ockhama sugeruje wybór najprostszej hipotezy pa-
suj¡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 klasykacji

47


Wyszukiwarka

Podobne podstrony:
MSI 2006 w4
MSI 2006 w3
MSI 2006 w2
MSI 2006 w1
MSI 2006 w7
MSI AiR w4 2004
MSI 2006 w3
MSI 2006 w3
MSI 2006 w2
MSI w6 2006 cz1
mikroskopia w4 2006 w1
systemy podatkowe w4 4 04 2006 Y34OFF636N43SNAFYBXLSOPQZBMYP4IZL4455UI
MSI w4 konspekt 2010 id 309792 Nieznany
finanse międzynarodowe w4 (14 03 2006) XEHYIKNNQ5XZWBJV4ZLKZZL6PEB2B6F7F62IH7I
rachunkowo 9c e6+mi eadzynarodowa+ w4 + 2805 04 2006 29 NJJDTAD2KPGRX2VLHWHIYVRLNIDPEWVKE63QOOQ
W4 Proces wytwórczy oprogramowania

więcej podobnych podstron