KYBERNETIKA A UMELA INTELIGENCE

8-9. Pravdepodobnostnı rozhodovanı a predikce

laboratory

Gerstner

Gerstnerova laboratorkatedra kybernetiky

fakulta elektrotechnickaCVUT v Praze

Rozhodovanı za neurcitosti

� Dosud v UI prednaskach:

− vyhledavanı co nejlepsıho resenı problemu

− za deterministickych podmınek (bez neurcitosti).

� Dulezitou schopnostı inteligentnıch systemu je ale take schopnost

− vybrat co nejlepsı rozhodnutı

− za nejistych podmınek (s neurcitostı).

� Prıklad: Jet z A do B tramvajı, nebo metrem?

− Tramvaj: rychlejsı cesta dle jızdnıho radu, ale velmi nejiste dodrzenı.

− Metro: delsı cesta, ale temer jiste dodrzenı.

� Prıklad: kam smerovat dopis s tımto PSC?

− 15700? 15706? 15200? 15206?

� Jak se optimalne rozhodnout?

� Oba prıklady lze formalizovat stejnym ramcem.

Prıklad [Kotek, Vysoky, Zdrahal: Kybernetika 1990]

� Panı Novakova se vracı z prace. Co uvarı pan Novak k veceri?

� Napadly ho 3 moznosti rozhodnutı (d - decision):

− nic . . . neudelat nic ⇒ zadna prace, ale zhorsı naladu pı. Novakove.

− pizza . . . ohrat mrazenou pizzu ⇒ nenı pracne, ale neohromı.

− n.h. . . . nadıvana holoubata ⇒ udela jı radost, ale velmi pracne.

� P. Novak cıselne zhodnotı mıru neprıjemnosti zpusobenou jednotlivymi rozhodnutımi. Ta zavisı

na tom, s jakou naladou prijde pı. Novakova domu, coz je neznamy stav. Rozlisme tyto

moznosti:

− dobra . . . pı. Novakova ma dobrou naladu.

− prumerna . . . pı. Novakova ma prumernou naladu.

− spatna . . . pı. Novakova ma spatnou naladu.

� Pro kazdou z 9 moznych situacı (3 mozna rozhodnutı × 3 mozne stavy) je neprıjemnost dana

ztratovou funkcı l(d, s) (l - loss):

l(d, s) d = nic d = pizza d = n.h.

x = dobra 0 2 4

x = prumerna 5 3 5

x = spatna 10 9 6

Prıklad (pokracovanı)

� Neznamy stav - naladu pı. Novakove - zkusı p. Novak odhadnout experimentem: sdelı jı, ze

ztratil jejı oblıbeny casopis a sleduje jejı reakci.

� Predpoklada 4 mozne reakce:

− mırna . . . nic se nedeje, casopis najdeme.

− podrazdena . . . proc nedavas veci na sve mısto?

− nasupena . . . proc ja si toho Novaka brala?

− hroziva . . . rezignovane mlcenı

� Reakce je prımo pozorovatelny prıznak (zde nalady).

� Ze zkusenosti p. Novak vı, jak jsou jednotlive reakce pravdepodobne pri dane nalade: to

vystihuje podmınene rozlozenı P (x|s).

P (x|s) x = x = x = x =

mırna podrazdena nasupena hroziva

s = dobra 0.5 0.4 0.1 0

s = prumerna 0.2 0.5 0.2 0.1

s = spatna 0 0.2 0.5 0.3

Rozhodovacı strategie

� Rozhodovacı strategie: pravidlo pro vyber rozhodnutı na zaklade pozorovaneho prıznaku.

� Tj. funkce d = δ(x).

� Prıklady moznych strategiı p. Novaka:

δ(x) x = mırna x = podrazdena x = nasupena x = hroziva

δ1(x) = nic nic pizza n.h.

δ2(x) = nic pizza n.h. n.h.

δ3(x) = n.h. n.h. n.h. n.h.

δ4(x) = nic nic nic nic

� Celkem ma k dispozici 34 = 81 moznych strategiı (3 mozna rozhodnutı pro kazdou ze 4

moznych hodnot prıznaku).

� Jak urcit, ktera ze dvou strategiı je lepsı? Obecne: jak strategie usporadat dle kvality?

� Definujeme riziko strategie pri stavu s: strednı hodnota ztraty podmınena stavem s.

R(δ, s) =∑

x

l(δ(x), s)P (x|s)

Kriterium MiniMax

� Prıklad: riziko strategie δ1 pri stavu s = dobra je

R(δ1, dobra) = l(δ1(mırna), dobra)·P (mırna|dobra)+l(δ1(podrazdena), dobra)·P (podrazdena|dobra)

+l(δ1(nasupena), dobra) · P (nasupena|dobra) + l(δ1(hroziva), dobra) · P (hroziva|dobra)

= l(nic, dobra) · 0.5 + l(nic, dobra) · 0.4 + l(pizza, dobra) · 0.1 + l(n.h., dobra) · 0= 0 · 0.5 + 0 · 0.4 + 2 · 0.1 + 4 · 0 = 0.2

� Podobne: R(δ1, prumerna) = 4.4 a R(δ1, spatna) = 8.3

� Maximalnı riziko strategie δ1 (pres vsechny mozne stavy) je tedy 8.3.

� Podobne: maximalnı riziko strategie δ3 je 6.

� MiniMaxove kriterium: ze dvou strategiı je lepsı ta, jejız maximalnı riziko je nizsı.

� Tedy podle MiniMaxu je δ3 lepsı nez δ1.

� Nejlepsı strategie δ∗ je podle MiniMaxu ta, ktera minimalizuje maximalnı riziko:

δ∗ = arg minδ

maxs

R(δ, s)

� Pro jejı nalezenı bychom v aktualnım prıklade museli spocıtat max. rizika vsech 81 moznych

strategiı.

Bayesovske kriterium

� Co kdyz p. Novak vı, ze p. Novakova ma obvykle dobrou naladu? Obecneji: vı, jak jsou jejı

jednotlive nalady pravdepodobne, tj. zna rozlozenı P (s). Napr:

x = dobra s = prumerna s = spatna

P (s) = 0.7 0.2 0.1

� MiniMaxove kriterium tuto znalost nezohlednuje.

� Dıky znalosti P (s) lze spocıtat strednı riziko dane strategie pres vsechny mozne stavy:

r(δ) =∑

s

R(δ, s)P (s)

� Tedy napr.

r(δ1) = 0.2 · 0.7 + 4.4 · 0.2 + 8.3 · 0.1 = 1.85

r(δ3) = 4 · 0.7 + 5 · 0.2 + 6 · 0.1 = 4.4

� Bayesovske kriterium: ze dvou strategiı je lepsı ta s nizsım strednım rizikem. Z Baye-

sovskeho hlediska je tedy δ1 lepsı nez δ3.

� Opacne proti MiniMaxovemu kriteriu!

Bayesovsky optimalnı strategie

� Bayesovsky optimalnı strategie je ta, ktera minimalizuje strednı riziko. Tj.

δ∗ = arg minδ

r(δ)

� Protoze P (x|s)P (s) = P (s|x)P (x) (Bayesovo pravidlo), platı

r(δ) =∑

s

R(δ, s)P (s) =∑

s

∑x

l(δ(x), s)P (x|s)P (s)

=∑

s

∑x

l(δ(x), s)P (s|x)P (x) =∑

x

P (x)∑

s

l(δ(x), s)P (s|x)︸ ︷︷ ︸Podmınene riziko

� Optimalnı strategii tedy muzeme dostat minimalizacı podmıneneho rizika zvlast’ pro kazde x:

δ∗(x) = arg mind

∑s

l(d, s)P (s|x)

� Tedy narozdıl od MiniMaxove optimalnı strategie nemusıme pocıtat riziko pro vsechny mozne

strategie. Bayesovsky optimalnı strategii lze “sestrojit bod po bodu” nalezenım optimalnıho

rozhodnutı pro jednotliva pozorovanı x.

Statisticke rozhodovanı: shrnutı

� Zadany:

− Mnozina moznych stavu: S− Mnozina moznych rozhodnutı: D− Ztratova funkce: zobrazenı l : D × S → < (realna cısla)

− Mnozina moznych hodnot prıznaku X− Pravdepodobnostnı rozlozenı prıznaku za daneho stavu P (x|s), x ∈ X , s ∈ S.

� Definujeme:

− Strategie: zobrazenı δ : X → D− Riziko strategie δ pri stavu s ∈ S: R(δ, s) =

∑x l(δ(x), s)P (x|s)

� MiniMaxova uloha:

− Dale zadana: mnozina prıpustnych strategiı ∆.

− Uloha: nalezt optimalnı strategii δ∗ = arg minδ∈∆ maxs∈SR(δ, s)

� Bayesovska uloha:

− Dale zadano: pravdepodobnostnı rozlozenı stavu P (s), s ∈ S.

− Dale definujeme: strednı riziko strategie δ: r(δ) =∑

s R(δ, s)P (s)

− Uloha: nalezt optimalnı strategii δ∗ = arg minδ∈∆ r(δ)

− Resenı: δ∗(x) = arg mind

∑s l(d, s)P (s|x)

Prıznakove rozpoznavanı

� Systemy pro rozpoznavanı. Prıklad ulohy:

O jakou jde cıslici?

Lze prevest na ulohu

statistickeho

rozhodovanı

Prıznak = vektor hodnot pixelu.

� Prıznakove rozpoznavanı cıslic: klasifikace do jedne ze trıd 0 . . . 9 na zaklade vektoru

hodnot pixelu.

� Specialnı prıpad statistickeho rozhodovanı:

− Prıznakovy vektor ~x = (x1, x2, . . . ): hodnoty pixelu c. 1, 2, . . . .

− Mnozina stavu S = mnozina rozhodnutı D = {0, 1, . . . 9}.− Stav = skutecna trıda, Rozhodnutı = rozpoznana trıda.

− Ztratova funkce:

l(d, s) =

{0, d = s

1, d 6= s

� Strednı riziko = strednı chyba klasifikace.

Bayesovska klasifikace

� Obvykle kriterium: minimalizace strednı chyby Bayesovska klasifikacnı uloha.

� Optimalnı klasifikace pri prıznaku ~x:

δ∗(~x) = arg mind

∑s

l(d, s)︸ ︷︷ ︸0 pokud d=s

P (s|~x) = arg maxs

P (s|~x)

� Volıme tedy nejpravdepodobnejsı trıdu pro danou hodnotu prıznakoveho vektoru.

� Obvykle ale nenı znamo rozlozenı P (s|~x). Je treba odhadnout z trenovacıch dat (jiz kla-

sifikovanych prıkladu).

� Trenovacı data (prıklady): (~x1, s1), (~x2, s2), . . . (~xl, sl).

� Odhad:

P (s|~x) ≈ pocet prıkladu v nichz ~xi = ~x a si = s

pocet prıkladu v nichz ~xi = ~x

� Zasadnı problem prıznakove klasifikace:

− Pocet prıkladu l postacujıcı ke spolehlivemu odhadu P (s|~x) roste exponencialne s poctem

slozek vektoru ~x.

− tj. napr. s rozlisenım (poctem pixelu) v rozpoznavanych obrazcıch.

− “prokletı kombinatoricke exploze”. Realne ulohy: jmenovatel casto nulovy!

− Bayesovska klasifikace: hornı limit kvality klasifikace, v praxi obvykle nedosazitelny.

Bayesovska klasifikace

� Lze tez vyuzıt Bayesova vztahu:

P (s|~x) =P (~x|s)P (s)

P (~x)

� Odhad P (~x|s): analogicky jako odhad P (s|~x).

� Odhad P (s): jako relativnı cetnost jednotlivych trıd s v trenovacıch datech, tj.

P (s) ≈ pocet prıkladu trıdy s

l

� P (~x) nenı treba odhadovat. Proc?

� Tento prıstup sam o sobe neresı problem mnozstvı dat potrebnych k odhadu pravdepodobnostı.

� Ale umoznuje ho “resit” neprımo:

1. Hodnoty P (s) jsou casto explicitne znamy a nenı nutno je odhadovat.

Prıklad: pri rozpoznavanı 1. cıslice PSC je nejcastejsı cıslice 1, napr P (1) = 0.6.

Takto je do klasifikace zapojena apriornı znalost o pravdepodobnostech trıd.

P (s) . . . ‘apriornı pravdepodobnost’.

2. Prıstup umoznuje formulovat zjednodusenou, tzv. naivnı Bayesovskou klasifikaci, v nız ne-

musıme odhadovat P (~x|s), ale pouze P (x(1)|s), P (x(2)|s), . . ..

Naivnı Bayesovska klasifikace

� Ve vyjimecnem prıpade statisticke nezavislosti jednotlivych prıznakovych slozek x(i) v

ramci kazde trıdy s platı

P (~x|s) = P (x(1)|s) · P (x(2)|s) · . . .

� Stacı tedy odhadnout P (x(i)|s) zvlast’ pro kazde i (a kazde s).

− Napr: P (x(3)|8) ≈ podıl prıpadu cıslice 8 s rozsvıcenym 3. pixelem.

− Zadna kombinatoricka exploze (pouze jednoslozkove pravdepodobnosti).

� V praxi: nezavislost se casto predpoklada, i kdyz neplatı, prıp. platı priblizne.

− Potom jde o tzv. Naivnı Bayesovskou klasifikaci. Casto uspesna metoda.

� Nezavislost mezi prıznakovymi slozkami je jen jednım z moznych predpokladu, jehoz

splnenı vede k zabranenı kombinatoricke explozi.

� Alternativnı predpoklady jsou napr.:

− Podobne objekty patrı do stejne trıdy klasifikace dle nejblizsıch sousedu.

− Trıda je plne urcena linearnı kombinacı slozek prıznaku klasifikace dle linearnıhomodelu.

� Podobne jako u naivnı b.k. se metody zalozene na techto predpokladech s uspechem pouzıvajı,

i kdyz jsou predpoklady splnene jen priblizne.

Klasifikace dle nejblizsıch sousedu

� Podobnost chapeme jako malou vzdalenost v prostoru prıznakovych hodnot.

� Funkce merıcı vzdalenost dvou prıznakovych vektoru, tzv. metrika: ρ : X ×X → <+ ∪ {0}takova, ze ∀x, y, z: ρ(x, x) = 0, ρ(x, y) = ρ(y, x), ρ(x, z) ≤ ρ(x, y) + ρ(y, z). Prıklad:

− Euklidovska metrika pro vektory ~x1, ~x2 se realnymi slozkami x1(i) resp. x2(i):

ρE(~x1, ~x2) =√∑

i(x1(i)− x2(i))2

− Jsou-li slozky binarnı (z {0, 1}), tak ρE(~x1, ~x2)2 je pocet slozek, v nichz se ~x1 lisı od ~x2 -

tzv. Hammingova metrika.

� Klasifikace dle k nejblizsıch sousedu (k-nearest neighbor classification, k-NN).

� Zadano:

− k ∈ ℵ− trenovacı prıklady: (~x1, s1), (~x2, s2), . . . (~xl, sl)

− metrika ρ : X ×X → <− neklasifikovany objekt s prıznakem ~x.

� Uloha: klasifikovat ~x

� Postup: z trenovacıch prıkladu vyber k nejblizsıch k ~x vzhledem k metrice ρ. Trıda, ktere mezi

nimi prevlada, budiz trıdou ~x.

Flexibilita klasifikace

� Jak volit k? Obecna odpoved’ neexistuje, zalezı na konkretnıch datech.

� Obecny trend: Uvazujme trenovacı data se dvema trıdami (cervena/zelena) a sumem (nektere

si chybne). Znacky - trenovacı data, krivka - hranice klasifikace:

k = 1: Dobre prizpusobenı

trenovacım datum. Velka cit-

livost k sumu.

Bayesovska klasifikace: Mene

flexibilnı nez 1-nn, vıce nez

15-nn.

k = 15: Spatne prizpusobenı

trenovacım datum. Mala citli-

vost k sumu.

� Vzpomente: Bayesovska klasifikace δ∗ ma nejnizsı mozne strednı riziko r(δ∗). Pozn.: Znazornena

Bayesovska vychazı z presnych pravdepodobnostı P (s|~x), ktere jsou pro klasifikacnı algoritmus

nezname!

� Pozorovanı: prılis velka flexibilita (male k) i prılis mala flexibilita (velke k) vedou ke klasi-

fikatorum znacne odlisnym od Bayesovskeho, tedy ke zvysovanı strednıho rizika r(δ).

� Podobny trend i klasifikaci zalozene na modelech (napr. polynomialnı model flexibilnejsı nez

linearnı).

Trenovacı chyba a strednı riziko

� Strednı riziko r(δ) klasifikatoru δ odpovıda relativnı cetnosti jeho nespravnych klasifikacı.

� Definujme empiricke strednı riziko rE(δ) (tez: “trenovacı chyba”) jako relativnı cetnost

nespravne klasifikovanych prıkladu v trenovacıch datech.

� Je rE(δ) dobrym odhadem skutecneho strednıho rizika r(δ)?

� Prıklad: 1-nn nenı dobry klasifikator (viz minulou stranu), prestoze spravne klasifikuje vsechny

trenovacı prıklady, tj. ma trenovacı chybu 0.

� Trenovacı chyba tedy nenı dobrym odhadem strednıho rizika. Pro jeho odhad je treba

− mıt k dispozici trenovacı mnozinu (~x1, s1), . . . (~xl, sl) a nezavislou testovacı mnozinu(~xl+1, sl+1), . . . (~xl+m, sl+m)

− (muze vzniknout rozdelenım puvodnıch trenovacıch dat napr. v pomeru 75% a 25%).

− klasifikator sestrojit na zaklade trenovacı mnoziny

− empiricke strednı riziko tohoto klasifikatoru spocıtat na testovacı mnozine.

� Empiricke strednı riziko na testovacı mnozine je nevychylenym odhadem skutecneho strednı

rizika. (Pozor: nevychyleny neznamena presny!)

(Umele) neuronove sıte

� Inspirovany poznatky o neuronech a nervovych sıtıch zivych organizmu

� Schopnost ucit se = extrahovat a reprezentovat zavislosti v datech, ktere nejsou zrejme

� Schopnost resit silne nelinearnı ulohy – vyuzitı pro klasifikaci, regresi a predikci casovych rad

� Zakladnı vypocetnı jednotkou je neuron

� Resenı problemu:

− Volba typu sıte, metody ucenı

− Regularizace - navrh topologie, prizpusobenı sıte slozitosti ulohy

− Ucenı - automaticka optimalizace parametru (vah) na zaklade trenovacıch prıkladu.

Nervova sıt’.

Model neuronu.

ξ =∑n

i=1 wixi − θ

Sumacnı potencial

f (ξ) = 11+e−λξ

Aktivacnı funkce

Typy neuronovych sıtı

� Ruzne typy sıtı pro ruzne typ uloh:

− vıcevrstva perceptonova (MLP) - viz. dale,

− Hopfieldova - autoasociacnı,

− Kohonenovy mapy - samoorganizujıcı se, druh shlukove analyzy

− RBF (Radial Basis Function), . . .

Autoasociativnı pamet’.Samoorganizujıcı se mapy.

Perceptron vs. vıcevrstva sıt’

� Nejjednodussı dopredna neuronova sıt’ - pouze dve vrstvy

� Rosenblatt, 1957 – hlavnı prınos oproti neuronu je adaptacnı

pravidlo

− wnew = wold + α(outdesired − outactual)input,

− α - rychlost ucenı, konverguje pokud vahy existujı

� Linearnı (pro jeden vyst. neuron binarnı) klasifikator

� Vhodna demonstrace prechodu od linearnı k nelinearnı kla-

sifikaci Perceptron.

� Minsky, Papert: Perceptrons, 1969

− Zasadnı omezenı perceptronu, nelze implementovat mj. funkci XOR

� Resenı az v 80. letech - vıcevrstva sıt’ (navıc skryta vrstva)

� Ucenı algoritmem zpetneho sırenı (backpropagation)

− Prirozene rozsırenı metody nejmensıch ctvercu

− Gradientnı optimalizace, chyba je zpetne sırena od vystupu na vnitrnı neurony

− ∆w = −η ∂J∂w , η - rychlost ucenı, J chybova funkce

� Aktivacnı funkcı typicky sigmoida nebo tanh (derivovatelnost)

Perceptron vs. vıcevrstva sıt’

XOR jako vıcevrstva sıt’. [Duda, Hart, Stork: Pattern Classification].

Nelinearnı aproximace vıcevrstvou sıtı

Aproximace nelinearnı funkce MLP sıtı s architekturou 2-4-1. Je vyuzito ctyr protilehleumıstenych sigmoidalnıch fcı vnitrnıch neuronu. [Duda, Hart, Stork: Pattern Classification].

Nelinearnı aproximace vıcevrstvou sıtı

Slozitejsı architektury mohou implementovat libovolne rozhodovacı hranice (nekonvexnı,oddelene apod.) [Duda, Hart, Stork: Pattern Classification].