# [Memo] Auto-encoding Variational Bayes

## Adatok
- Cím: Auto-Encoding Variational Bayes
- Szerzők: Diederik P Kingma, Max Welling
- Link: https://arxiv.org/abs/1312.6114

## Motiváció

### Mi a cél?
A probléma, amire a VAE megoldást próbál adni, az az unsupervised learning. Feltételezzük, hogy megfigyeléseink $x_1, \ldots, x_N$ valamilyen nem ismert eloszlásból, $p_\mathcal{D}(x)$, származnak, és egymástól függetlenül keletkeztek. (i.i.d. independent and identically distributed). A célunk az, hogy az adatok eloszlását a megfigyelések alapján megközelítsük, vagy leírjuk egy modellel, $p_\theta(x)$. A $p_\theta(x)$ egy valószínűségi eloszlás a megfigyelések terében, amit valamilyen paraméterek $\theta$ írnak le.

Ennek egyik módja hogy a modell likelihood-ját maximalizáljuk, azaz olyan paramétereket keresünk, amiknél az adott megfigyelések valószínűsége maximális:

$$
\theta^{ML} = \operatorname{argmax}_\theta \sum_{n=1}^N \log p_\theta(x_n)
$$

Ezt azonban általában nehéz kiszámolni, mivel $p_\theta(x_n)$ kiértékelése csak nagyon egyszerű eloszlások esetén lehetséges, bonyolultabb terekben bonyolultabb modellekre a maximum likelihood becslés nehéz.

Egy Maximum Likelihood Estimation-nel (MLE) megoldható példa az [Iris dataset](https://archive.ics.uci.edu/ml/datasets/iris)-en végzett klasszifikációs probléma, ahol a megfigyelt változók a szirom illetve virágkehely hossza/szélessége. Viszont ha a virágok képét vennénk bemenetként (ami már egy sokkal bonyolultabb változótér az előző bemenetünkhöz képest), azt már egy másik megközelítéssel lenne érdemesebb megoldani.

### Mi az a látens változós modell
A látens változós modell egy olyan modellje $p_\theta()$ a megfigyelhetõ változóknak ($x$), amit egy magasabb dimenziós eloszlás margináklisaként definiálunk:

$$
p_\theta(x) = \int p_\theta(x, z) dz,
$$

ahol $z$ az úgy nevezett látens vagy rejtett változó, vagy azokból alkotott vektor. Mint a neve is sejteti, $z$-t közvetlenül nem figyeljük meg. Például, ha a megfigyelt változók $x_n$ képek macskákról, a hozzájuk tartozó rejtett változók $z_n$ leírhatják a macska fajtáját, színét, korát, stb. Az Iris-es példánkoz visszatérve pedig a látens változók között ismét előfordulhat a szirmok hossza/szélessége, de az is elképzelhető hogy akár újak is születhetnek - például az hogy mennyire lekerekített egy szirom.

Összefoglalva: a látens változós modellek segítenek nekünk komplex megfigyelésekhez olyan látens változókat megtalálni, amik jól leírják az adott modellt.

### Miért jó egy látens változós modell

1. **generative modeling:** mert intuitív látens változókkal leírni a világot. Ha mondjuk egy videójátékot játszunk, nagy valószínűséggel van a világnak egy kompakt leírása a szamitógép memóriájában: hány ellenség van, hol vannak, merre mennek, stb. A játékos szempontjából a döntéshozáshoz ezeknek a meg nem figyelhető változóknak az értékei relevánsak. Helyette amit megfigyelünk az egy a látens változók alapján renderelt kép. Célszerű ezért ezt a képet úgy leírni egy modellel, hogy megpróbáljuk az alacsony dimenziós látens változókat kitalálni belőle.
2. **representation/transfer learning:** mert egy látens változós modellben utána aztán használhatjuk a nyers adatok helyett az egyes megfigyelésekhez társított látens változókat, azaz $x_n$ helyett $z_n$-t, egy későbbi tanulási feladatban (representation learning/transfer learning). Itt azt reméljük hogy a megtanult látens reprezentacio valamilyen szempontból hasznos leírása az adatodnak.
3. **manifold learning/dimensionality reduction:** mert azt feltételezzük, hogy az adataink, bár magas dimenzióban figyeljük meg őket, valójában egy alacsonyabb dimenziós manifoldon élnek, és effektíve sokkal kisebb dimenziójú vektorral is jól leírhatók. Ilyen szempontból gondolhatunk úgy egy látens változós modellre, mint egy nemlineáris koordináta-transzformációra.
4. **flexible models:** mert ilyen módon könnyű egyszerű modellekből komplex modellt kombinálni. Egy rejtett változós modellben lehet mind $p_\theta(z)$ es $p_\theta(x\vert z)$ nagyon egyszerű, pl. normál eloszlás, ami analitikailag könnyen kezelhető. Viszont amikor kombináljuk őket, $p_\theta(x,z) = p_\theta(x\vert z)p_\theta(z)$, akkor a megfigyelhető változókon szinte tetszőlegesen komplex $p_\theta(x)$ eloszlást tudunk definialni. Ez tortenik a VAE modellben is.
5. **variational learning:**: mert használhatunk ELBO-t arra hogy egy ilyen modelt tanítsunk.

## Hasznos háttér

### Jensen-egyenlőtlenség:

Konvex függvény ($f$) esetben a függvényértékek súlyozott összege a súlyozott függvényargumentumok helyén vett függvény értékénél mindig nagyobb, azaz $\forall t\in [0,1]$:

$$
tf(x_1) + (1-t)f(x_2) \geq f\left(tx_1+(1-t)x_2\right) .
$$

Továbbá ez igaz tetszőleges súlyozásra - ha a súlyok összege 1 -, vagyis kiterjeszthető valószínűségi eloszlásokra is. Mivel a várható érték esetében a súlyok pont egyre összegződnek a valószínűségi sűrűségfüggvény normált tulajdonsága miatt, vagyis (példaként a $\log$ függvényt használva, mivel arra van szükségünk a cikkhez):

$$
\log\mathbb{E}[X] \geq \mathbb{E}[\log X]
$$

Több infó itt: https://en.wikipedia.org/wiki/Jensen%27s_inequality

### Kullback-Leibler divergencia

A Kullback-Leibler divergencia egy nemnegatív mennyiség, amely valoszinusegi eloszlások között definiált.

A definíció:
$$ D_{KL}(p(x) || q(x)) = -\sum_x p(x)\log\dfrac{q(x)}{p(x)} \\
=\sum_x p(x)\log\dfrac{1}{q(x)} -H_p(x) \\ = H_{p,q}(x) -H_p(x), $$
vagyis a KL-divergencia kifejezhető a két eloszlás együttes várható információtartalmának és az első argumentumként megadott eloszlás várható információtartalmának különbségeként. A várható információtartalom a [Shannon-féle entrópia](https://en.wikipedia.org/wiki/Entropy_(information_theory)).
Intuitív magyarázat: a KL-divergencia azért nemnegatív, mert ha egy adott $p$ eloszláshoz hozzáveszünk még egy eloszlást, akkor a rendelkezésre álló infomráció nem csökkenhet, hiszen eggyel több információforrásunk van. A minimumot akkor érjük el, ha az új eloszlás $(q)$ nem tartalmaz új információt, ebben az esetben $H_{p,q}(x) = H_p(x),$ a különbség pedig 0.

### Evidence Lower Bound (ELBO)
Az ELBO egy alsó korlátot ad meg a $log-evidence$-nek nevezett mennyiségre, ami az adatpontok eloszlásának logaritmusa (adott $\theta$ paraméterek tere fölött):
$$ \log p_\theta(x^i) - D_{KL}\left(q_\phi(z|x^i)|| p_\theta(z|x^i)\right) = \mathcal{L}(\theta, \phi; x^i).$$
A KL-divergenciát (ami nemnegatív) elhagyva adódik, hogy $\mathcal{L}(\theta, \phi; x^i)$ alsó korlát.

Itt van két levezetés: [egy Jensen, meg egy KL-divergencia.](http://legacydirs.umiacs.umd.edu/~xyang35/files/understanding-variational-lower.pdf)

### "Amortized VI"
Hogy miért hívják így $\mathbb{E}_{q_\phi}(z|x^{(i)})$-t?
Azért, mert ha nem egy pontra végezzük el a becslést, akkor nem fogunk tudni minden pontra tökéletesen illeszkedő modelt kapni. Cserébe viszont a modellünk általánosítóképessége nem 0 lesz. Analóg módon bele lehet gondolni, hogy például az LS-becslésnek ugyanúgy van egyfajta általánosítóképessége - négyztes hiba tekintetében -, hiszen azt az alapesetben egyenest keresi, ami minden mintapontra a legjobban illeszkedik.

### REINFORCE
A REINFORCE vagy score function gradient estimator ilyen jellegű függvények gradiensének becslésére használható:

$$
F(\theta) =
$$

Tehát ezt szeretnénk megbecsülni:

\begin{align}
\nabla_\theta F(\theta) &= \nabla_\theta \mathbb{E}_{x \sim p(x;\theta)} f(x)\\
&= \nabla_\theta \int p(x;\theta) f(x) dx
\end{align}

Mivel a differencialas es x szeriti integralas linearis operaciok, ezert a sorrendjuk megcserelheto, ezert:

\begin{align}
\nabla_\theta F(\theta) &= \nabla_\theta \int p(x;\theta) f(x) dx \\
&= \int \nabla_\theta p(x;\theta) f(x) dx \\
\end{align}

Egy ilyen integralt altalaban nehez kiszamolni, viszont egy parcialis integralas trukkel kifejezheto ugy, mint egy varhato ertek. Barmilyen pozitiv $p(x; \theta)$ fuggvenyre igaz az, hogy:

$$
\nabla_\theta \log p(x; \theta) = \frac{\nabla_\theta p(x; \theta)}{p(x; \theta)}
$$

Ez egyszeruen a differencialas lanc-szabalyanak alkalmazasaval belathato. Ezert, behelyettesitve $$\nabla_\theta p(x; \theta) = \nabla_\theta \log p(x; \theta) p(x; \theta)$$-t a kovetkezot kapjuk:

\begin{align}
\nabla_\theta F(\theta) &= \int \nabla_\theta p(x;\theta) f(x) dx \\
&= \int \nabla_\theta \log p(x; \theta) p(x; \theta) f(x) dx \\
&= \mathbb{E}_{x\sim p(x; \theta)} \nabla_\theta \log p(x; \theta) f(x).
\end{align}

Es ez maga a REINFORCE gradien estimator. Ezt a varhato erteket Monte Carlo kozelitessel tudjuk becsulni ugy, hogy $p(x; \theta)$-bol mintavetetlelezunk mondjuk $K$-szor, $x_1, \ldots, x_K$ ertekeket, es ezeken empirikus atlagot szamolunk:

\begin{align}
\nabla_\theta F(\theta) &= \mathbb{E}_{x\sim p(x; \theta)} \log p(x; \theta) f(x) \\
&\approx \sum_{k=1}^K \nabla_\theta \log p(x_k; \theta) f(x_k)
\end{align}

Ahhoz, hogy ezt a modszert hasznaljuk a gradiens megbecslesere, tudnunk kell az eloszlas ugynevezett score-function -jat, azaz $$\nabla_\theta \log p(x; \theta)$$.

Egy sima, egy dimenzios normalis eloszlas eseteben pl, a score function egy linearis fuggveny:

$$
\nabla_\mu \log \mathcal{N}(x; \mu, \sigma=1) = \mu - x
$$

Ezt behelyettesitve pl. azt kapjuk, hogy:

$$
\nabla_\mu \mathbb{E}_{x\sim\mathcal{N}_{\mu,1}}f(x) \approx \sum_{1=k}^K (\mu - x_k) f(x_k)
$$

Ennek a becslésnek a problémája az, hogy nagyon nagy a varianciája. (Opcionális: valaki számolja ki, hogy mennyi a szórása a fenti Monte Carlo becslésnek Normális eloszlás esetén, feltételezve, hogy f(x_k) mondjuk lineáris függvény).

- Több infó: Ronald J. Williams, _Simple statistical gradient-following algorithms for connectionist
reinforcement learning_

### Reparametrization trick
Az $\mathcal{L}(\theta, \phi)=\mathbb{E}_{z \sim q_\phi(z)} f(z)$ alakú alsó korlát optimalizálásához meg kell határoznunk a kifejezés gradiensét $\theta$ és $\phi$ szerint. Az előbbit könnyen ki tudjuk számolni,

$$
\nabla_{\theta} \mathcal{L}(\theta, \phi) = \nabla_{\theta}\mathbf{E}_{z\sim q_\phi(z)}f(z) =
\mathbf{E}_{z\sim q_\phi(z)}[\nabla_{\theta} f(z)] \approx
\frac{1}{N} \sum_{n=1}^N \nabla_{\theta} f(z^{(n)})
$$

viszont az utóbbi ($\nabla_{\phi}\mathbf{E}_{z\sim q_\phi(z)}f(z)$) nehézségeket okoz, mert a sűrűségfüggvény $\phi$ paraméterezésű, így a hagyományos módszerek nem használhatóak, vagy nem elég hatékonyak, például túl nagy a variancia (ld. reinforce).

A probléma megoldásának érdekében a $z\sim q_\phi(z)$ valószínűségi változót írjuk fel $\phi$ és egy olyan $\epsilon \sim p(\epsilon)$ valószínűségi változó függvényeként, ahol a $p(\epsilon)$ nem függ $\phi$-től.

$$
z=g_{\phi}(\epsilon)
$$

Például, ha $z \sim \mathcal{N}(\mu, \sigma)$ normális eloszlású, akkor $z$ átírható úgy, hogy $z = \mu + \sigma * \epsilon$, ahol $\epsilon\sim \mathcal N(0,1)$ standard normális eloszlású.

Ekkor a $\nabla_{\phi} \mathcal{L}(\theta, \phi)$ gradiens átírható:

$$
\nabla_{\phi} \mathcal{L}(\theta, \phi)
= \nabla_{\phi}\mathbf{E}_{z\sim q_\phi(z)}f(z)
= \nabla_{\phi}\mathbf{E}_{\epsilon\sim p(\epsilon)}f(g_{\phi}(\epsilon))
$$

Mivel a sűrűségfüggvény már nem függ $\phi$-től, illetve a várható érték egy $\epsilon$ szerinti integrálás, így a differenciálás és a várható érték sorrendje már felcserélhető (Leibniz integral rule):

$$
\nabla_{\phi}\mathbf{E}_{\epsilon\sim p(\epsilon)}f(g_{\phi}(\epsilon))= \mathbf{E}_{\epsilon\sim p(\epsilon)}[\nabla_{\phi} f(g_{\phi}(\epsilon)]
$$

A Monte Carlo közelítésből és a differenciálás láncszabályából következik:

$$
\approx
\frac{1}{N} \sum_{n=1}^N \nabla_{\phi} f(g_{\phi}(\epsilon^{(n)})=\frac{1}{N} \sum_{n=1}^N f'(g_{\phi}(\epsilon^{(n)}))\nabla_{\phi}g_{\phi}(\epsilon^{(n)})
$$

A fentiekből látszik, hogy a módszer akkor alkalamzható, ha $f(z)$ és $g_{\phi}( \epsilon)$ differenciálható (a reinforce módszernél az előbbit nem követeltük meg).