Street1931
Falk1975
Falk1975
Inferencia ADOTTAK: ! •
generatív modell:
például: DAG + prior(ok) + likelihood(ok) → P(X1,X2,…,Xn)
•
megfigyelések: D = {Xi = xi, Xj = xj, …}
! KISZÁMOLANDÓK:! •
normalizáció a poszteriorhoz: P(D)
•
marginálisok: P(Xk|D)
•
legvalószínűbb magyarázat: arg maxx P(x|D)!
•
poszterior szerinti várható érték számítás: ∫ f(x)p(x|D)dx
! IDŐ ESETÉN: ciklikus modell, Markov-lánc, stb.! KISZÁMOLANDÓ PÉLDÁUL: P(Xt+1|D[0,t]) prediktív valószínűség
P(F=true |N=true) = ?
∝ P(F=true,N=true)
P(F,A,S,H,N) = P(F)P(A)P(S|F,A)P(H|S)P(N|S)
Változók számában exponenciálisan sok tag (23) Általános esetben az egzakt bayesiánus inferencia
NP-nehéz probléma!
Az agy képes NP-nehéz problémákat megoldani?! Néhány fantazmagórikus elmélettől eltekintve (Penrose: az agy, mint kvantumszámítógép) nincs okunk feltételezni, hogy az agy komputációsan
többre lenne képes, mint egy hatalmas számítógép. Vagyis P ≠ NP esetén az NP-nehéz problémák az agy számára is éppúgy számításigényesek.
Ha egy NP-nehéz problémát meg tudunk oldani, mint például az utazó ügynök problémát látszólag, az csak két dolog miatt lehet: vagy közelítő a megoldásunk, vagy csak kicsi a probléma mérete (?)
Szokásos érv, hogy a bayesiánus inferencia NP-nehéz probléma, ezért közelítő módszerekre van szükség. Valójában a közelítő módszerek is lehetnek NPnehezek, a gyakorlatban való megoldhatóság általában abban rejlik, hogy az input nem tetszőleges, hanem egy szűk részhalmaza a lehetséges összesnek. Ettől függetlenül a gyors közelítő módszereknek van relevanciája.
! Közelítő módszerek:! •
Laplace módszer: integrál közelítő formula, lényegében Gauss közelítések
•
Variációs módszerek: egzakt módszer elhanyagolás/egyszerűsítés után
•
Mintavételezés (Monte Carlo módszerek):
integrálok átlaggal való helyettesítése, tetszőlegesen finomítható (konzisztens)
Mintavételezés
Néha így, néha úgy döntünk
Néha ez, néha az a benyomásunk
Egy 60 éves ember várhatóan mennyi ideig fog még élni?
Egy 100 milliós bevétellel induló film mennyit fog összesen keresni?
Feltételezés: p(t|ttotal) = 1/ttotal Az életkor priorja jó közelítéssel Gauss, a filmek bevétele nem. A bayesiánus becslés függ a priortól, Gauss esetén például az átlag körül nyilvánvalóan törés van, filmek esetében nem.
Griffiths2006
Feltételezések:! •
optimális bayesiánus inferencia
•
prior reprezentáció a teljes értelmezési tartományon
•
likelihood: feltételezés arról, hogy a kísérletvezető hogyan generál
•
jóslat: medián képzés
!
MIN2 heurisztikus modell:
→ csupán két minta, irreleváns minták dobva → maradék minták minimuma (legközelebbi érték) → ha nincs releváns minta, akkor arányossá (g) !
G&T-Bayesian modell:! ugyanannyi minta alapján prior pontbecslés (σ) és bayesiánus számítás
Mozer2008
Mozer2008
Kérdés, hogy a minták mennyire függetlenek? Ha az első minta a legjobb, akkor a második csak ront a becslésen? Kísérlet kvízkérdésekkel, internetes felmérés (428 alany). Megkérdezték ugyanazt másodszor is (azonnal és 3 hét múlva). A második becslés variábilisabb. A második becslést is figyelembe véve jobbak vagyunk, de 3 hetet várva nagyobb a hatás: megkérdezni saját magunkat még egyszer harmadannyit ér, mint megkérdezni valaki más véleményét. Mindez azt sugallja, hogy az ember mintát vesz egy eloszlásból, és nem determinisztikusan választ a meglévő tudásbázis alapján. Vul2008
Mennyire rossz néhány minta alapján meghozni a döntés?
2AFC: melyik akciónak (A1 vagy A2) nagyobb a várható hasznossága? Teljes poszterior alapján optimális mindig a nagyobb valószínűségűt választani. P(A* = A1) := p ∈ [0.5,1]. Ekkor p valószínűséggel lesz helyes a döntés. k=1 minta esetén probability matching stratégia van, több minta esetén viszont a gyakoribbat fogjuk választani: q = 1 - ΘCDF(k/2,p,k) valószínűséggel, ahol Θ a binomiális eloszlás kumulatív eloszlásfüggvénye. A döntés qp+(1-q)(1-p) valószínűséggel lesz jó.
p-re egyenletesen kiátlagolva
1:1000 "morális" döntéshez 25000 minta kell, de kevés minta is közel van az optimumhoz! Vul2014
Moreno-Bote2011
Normalizálás után:
Individulas
Buffon-féle tűprobléma (L
Monte Carlo módszerek Stanislaw Ulam & Neumann János nevéhez köthetők (Los Alamos, II. világháború). 1947-ben Neumann a világ első számítógépén (ENIAC) futtat termonukleáris és hasadásos problémákat. MCMC cikk szerzői: A. Rosenbluth, M. Rosenbluth, A. Teller, E. Teller (1953). Később Hastings és tanítványa Peskun általánosították sok dimenzióra. Ezután lényegében 40 évnyi csend a számítási erőforrások hiánya miatt (ma MCMC-vel megoldott problémák kezelhetetlenek voltak az akkori számítástechnikai kapacitással). 90-es évek elején többnapos MCMC konferencia és új lendület! Paradigmaváltás: zárt képletű megoldások helyett algoritmusokra és valós problémákra terelődött a hangsúly. Ma a top 10 algoritmusból az elsőként tartják számon!
1. probléma: mintavételezés P eloszlásból 2. probléma: valamely mennyiség P szerinti várható értéke (1-es megoldja) !
MC módszerek: ! •
cdf módszer!
•
rejection sampling!
•
importance sampling!
•
particle!
•
stb.
!
MCMC módszerek:! •
Gibbs!
•
Metropolis!
•
Hamiltoni!
•
stb.
Sztochaszticitás forrása •
vagy inherensen sztochasztikus fizikai folyamat
•
vagy valamilyen nem-lineáris kaoutikus leképezés
!
Példa: Lehmer vagy Park–Miller
egyenletes eloszlású pszeudo-random generátor: leképezés: x → 16807·x
nemlinearitás: 32-biten túli számokat hagyjuk kicsorogni (azért működik jól, mert 231-1 egy Mersenne-prím)
Inverz transzformáció:! cdf (cumulative distribution function) használata! Legyen p(x) a mintavételezni kívánt eloszlás, legyen F(x) ennek a kumulatív eloszlás függvénye, legyen F-1 ez utóbbi inverz függvénye. Ha u ∈ [0,1] egyenletes eloszlású, akkor x = F-1(u) egy mintát generál.
ahol meredek, ott p nagy, fix dx-hez du szélesebb
Házi feladat: u∈[0,1] egyenletes eloszlású valószínűségi változó segítségével hogyan tudunk mintavételezni a p(x) = λe-λx exponenciális eloszlásból?
Hogyan mintavételezzünk egyenletesen
egy körlapot?
Megjegyzés: ha van egyenletes mintánk egy körlapon, akkor abbó lehet generálni normál eloszlást is (Box-Muller módszer): yi = xi (-2(ln(r2))/r2)1/2
Rejection sampling
"céllövölde"
Adaptív rejection sampling: amikor nem fogadunk el egy mintát, akkor a burkoló eloszlást adaptív módon csökkentjük. Ha a mintavételezni kívánt eloszlás logaritmusa konkáv, akkor működik az alábbi módszer: a sűrűségfüggvény logaritmusát szakaszonként lináris függvénnyel közelítjük felülről, és az exponenciálisok lecsengését adaptív módon változtatjuk. Exponenciálishoz mintát generálni ráadásul könnyű.
Rejection sampling hátránya sok dimenzió esetén
Példa: Legyen egy sokdimenziós normál eloszlásunk, a burkoló pedig legyen egy kicsit szélesebb normálatlan normál eloszlás azonos centrummal. Legyen csak 1% a különbség a szórásban. Tekinthetjük úgy, mintha a burkoló az eredeti minden irányban megnyújtott változata volna, vagyis a térfogata az eredetinek (1.01)D -szerese, ahol D a dimenzió. D = 1000 esetén például csak minden húszezredik mintát fogunk elfogadni!
Kondicionálisok mintavételezése (Likelihood weighting) Ha mintát tudunk venni a teljes eloszlásból (grafikus modellben például előre haladva a fán), akkor kidobva azokat, ahol nem teljesül a feltétel, mintát kapunk a kondicionálisból. Ez sok fölösleges mintát jelenthet. Mi lenne, ha eleve forszíroznánk a szükséges változók rögzítését? Ezzel sajnos torzítunk. A helyes megoldás, ha súlyozzuk a mintánkat a likelihood-ok szerint. Vagyis amely változókat rögzítünk, azoknak a likelihood-jait (az adott mintában már legenerált szülőkre kondicionálva) összeszorozzuk, és ez lesz a minta súlya!
Mielőtt tovább lépnénk nézzünk egy bonyolultabb példát: Mixture of Gaussians
F1 és F2 a hangokra jellemző frekvencia maximumok
Ismeretlenek: •
Gauss centrumok: η1,η2,…,ηK
•
Gauss szórások: σ1,σ2,…,σK
•
keverési súlyok: π1,π2,…,πK
•
adatpontok hovatartozása: c1,c2,…,cN ,ahol ci ∈ {1,2,…,K}
Adat: D = {x1,x2,…,xN} Modell: normál eloszlások szuperpozíciója •
p(xi|Θ,c) likelihood Gauss ηm és σm paraméterekkel, ahol m=ci
•
p(ci|Θ) = πi , Σ πi = 1
Feladat: p(Θ,c|D) poszterior számítása Bayes-tétel: •
számláló számítható: Πi∈{1,2,…,N} p(xi|Θ,c)p(c|Θ)p(Θ)
•
nevező reménytelen: P(D) = Σc ∫dη ∫dσ ∫dπ …
Normalizációhoz minden hipotézisre integrálni kéne!
Legtöbb érdekes kérdés megfogalmazható
várható érték számítással, csak jól kell megválasztani
a kívánt átlagolandó mennyiséget, azaz f függvényt:
Monte Carlo közelítő integrál:
Gaussian mixture példa: ha annak a valószínűsége érdekel minket,
hogy az i. és j. adat egy klaszterhez tartozik-e, akkor f := δKronecker(ci,cj)
Importance sampling
Milyen q(x) eloszlást válasszunk? Legyen minimális a becslés varianciája!
Házi feladat: Jensen-egyenlőtlenséget kihasználva
Az a fontos régió, ahol p(x) és |f(x)| is nagy! Variációk: adaptív; normalizálatlan eloszlások kezelése, …
Gibbs Korrelált minták:
a következő minta függ az előzőtől.
Mindig csak egy változót mintavételezünk,
a többit fixen tartjuk.
Az egyváltozós poszterior normalizációja 1D-integrálást igényel: tehát az n-dimenziós integrált lecseréljü n darab 1-dimenziósra.
Megjegyzés: a kondicionálisok 1-dimenziósak, ezért általában effektív a Gibbs mintavételezés a rejection sampling segítségével !
Grafikus modell: elegendő a Markov-takaróra kondicionálni! → térben elosztott, de időben szekvenciális algoritmus (nem paralellizálható) !
További hátrány: nagyon lassú tud lenni, mert egyszerre csak egy változó mentén lépünk, így erőss korrelációk esetén nehezen távolodunk el az aktuális állapottól.
MCMC: Metropolis-algoritmus •
elegendő P*(x) kiértékelése normalizáció nélkül
•
függő minták: Q(xkövetkező|xelőző) = Q(xelőző|xkövetkező)
például lehet a perturbáció Gauss: N(xkövetkező ; xelőző,σ2)
1. új pont generálása xt+1 ~ Q(xt+1;xt) 2. elfogadási arány a = min(1,P*(xt+1)/P*(xt)) 3. egyébként xkövetkező = xelőző
Állítás: xt aszimptotikus eloszlása P(x) lesz!
Metropolis-Hastings Általánosítás: Q nem kell szimmetrikus legyen
elfogadási arány: a = min(1,P*(xt+1)Q(xt;xt+1)/P*(xt)Q(xt+1;xt)) !
Megjegyzés: Gibbs egy speciális fajtája Q(x’;x) = p(x’i|x-i )δKronecker(x’-i,x-i) Megmutatható, hogy az elfogadási ráta 100% (házi feladat)! Gibbs-ben nincsen szabad paraméter, míg általánosságban az MCMCben Q-nak vannak szabad paraméterei, amiket tuningolni szükséges.
Emlékeztető: Markov lánc részletes egyesúlya Ha az állapottérben való véletlen bolyongás átmeneti p(s→s’) valószínűsége valamely π(s) valószínűségi mértékre eleget tesz az alábbi egyenletnek minden s és s’ állapotra: π(s) p(s→s’) = π(s’) p(s’→s) Állítás: ekkor π(s) stacionárius, azaz π(s) = Σs’ π(s’) p(s’→s) Bizonyítás: Σs’ [π(s) p(s→s’)] = Σs’ [π(s’) p(s’→s)] Σs’ [π(s) p(s→s’)] = π(s) Σs’ [p(s→s’)] = π(s)
Megjegyzések: •
Véletlen bolyongás nagyon lassúvá teszi
független mintához szükséges lépésszám ≈ (Lmax/∆)2
•
Ha Q szűk eloszlás, akkor kicsit lépünk (∆), ha nagy, akkor viszont könnyen elutasítunk (főleg sok dimenzióban)
optimum ≈ eloszlás legkisebb karakterisztikus távolsága
•
Nem tudjuk, hogy mikor áll be az aszimptotikus egyensúly
!
Mindegyikre van megoldás: → Hamiltonian sampling (diffúzió csökkentése) → slice sampling (inszenzitív a lépés nagyságára) → exact sampling (hol álljunk meg?)!
HMC P(x) érdekel minket, írjuk fel P(x) = exp(-Epot(x)/T)/Z alakban, T := 1. Vezessünk be új független konjugált p változókat, közös eloszlás függvény:
P(x,p) = exp(-H(x,p))/Z, ahol H(x,p) = Epot(x) + Ekin(p), ahol Ekin(p) := p2/(2m)
kvadratikus → Gauss Lépések:! 1. új p momentum választása x-től függetlenül P(p) normál eloszlásból 2. (x,p)-ből Hamilton dinamika szerinti fejlesztés (dx/dt=p, dp/dt = -∂Epot/∂x)
(lehet térfogattartó közelítő módszer, paraméterek lépésköz és lépésszám) 3. elfogadási arány: min(1,exp(-H(x’,p’)+H(x,p))) Szemléletesen: p ter modinamikai hőfürdő mintájára segít a sztochaszticitásban,
míg a Hamilton-dinamika segít grádiens mentén mozogni. Megjegyzések: P(x) nem kell normalizálva legyen,
viszont a nem zérus helyeken egyszer deriválható kell legyen!
Érdekeség: MCMC emberekkel, mint szimulátorokkal
Legyen x a jelenlegi állapot és x* a lehetséges új állapot. Ha a p(x → x*) = p(x* → x), akkor lehet használni az ún. Baker-féle elfogadási függvényt, ahol π a céleloszlás.
Sanborn2014
Feladat: két objektumot mutatnak (x1 és x2), és el kell dönteni, hogy a kettő közül melyik tartozik/származik egy c kategóriából. Bayesiánus: két hipotézis között kell dönteni, x1 származik p(x|c) eloszlásból és x2 valamilyen alternatív g(x)-ből (h1), vagy fordítva (h2).
Feltételezések:
p(h1) = p(h2) és g(x1) ≈ g(x2), például g egyenletes
Sanborn2014
Legyen x1 egy MCMC lehetséges új x* állapota x2 pedig az aktuális állapot. Ha az emberek probability matching szerint választanak a hipotézisek közül, akkor x* elfogadási valószínűsége az alábbi, ahol a céleloszlás p(x|c).
A probability matching-től eltérő stratégia paraméterezhető:
Sanborn2014
Óceáni halak egyenletes, tenyésztett halak Gauss eloszlással. Betanítás azonos arányban egyesével mutatott képekkel és visszajelzéssel. MCMC kísérletben két halat mutatnak, és a tenyészett a kérdés, de valójában az MCMC aktuális és lehetséges következő állapotát mutatják, mely utóbbit az aktuális állapot körüli Gauss eloszlásból választanak. Megcsinálták ugyanezt tanítás nélkül már létező kategóriákkal →
Összefoglalás: mintavételezés előnyei Algoritmikusan:! •
gépi tanulásban a legsikeresebb módszer
•
általános módszer
•
finomítható és konzisztens
Kevés számú minta:! •
gyorsabb döntés (idő)
•
könnyebb a döntés a lehetőségek közül
(Rakow2008: rövidtávú memóri kapacitás korrelál a használt minták számával)
•
tapasztalat és elmélet szerint is elegendő
(nagy dimenzióredukció esetén kevés is elég)
•
ökológiai környezetben flexibilisebb stratégia
Neurálisan implementálható: ezzel foglalkozunk még később
