==== Poznámky k článku o Maximum Entropy LM ====
[[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.61.1472&rep=rep1&type=pdf|Ronald Rosenfeld: A Maximum Entropy Approach to Adaptive Statistical Language Modeling]]
=== Definice entropie ===
Před čtením článku je dobré si připomenout základy ze [[http://wiki.matfyz.cz/wiki/Statistické_metody_zpracování_přirozených_jazyků_I|Statistických metod]]:
* Mějme diskrétní prostor jevů X a dvě pravděpodobností rozdělení P, Q : X \rightarrow [0,1]. Pak
* Entropy H(P) = - \sum_{x \in X} P(x)\cdot \log_2 P(x)
* Perplexity PPL(P) = 2^{H(P)}
* Cross-entropy H(P, Q) = - \sum_{x \in X} P(x) \cdot \log_2 Q(x)
* Kullback-Leibler divergence D_{KL}(P || Q) = \sum_{x \in X} P(x)\cdot\log_2(\frac{P(x)}{Q(x)})
Entropie je tedy definována primárně jako **vlastnost pravděpodobnostního rozdělení**. Pokud mluvíme o entropii jazyka, textu, korpusu apod., měli bychom vědět, jaké pravděpodobností rozdělení se pod takovouto entropií skrývá. Typicky se entropie korpusu/textu definuje jako entropie rozdělení P, které je odhadnuto z daného textu pomocí maximum likelihood odhadu. Typicky P předpovídá pravděpodobnost **slova** podmíněnou tzv. historií, tedy předchozími slovy.
Pro podmíněnou entropii a podmíněnou cross-entropii lze zavést definice:
* Nechť jsou X a Y dva diskrétní prostory jevů a P(X,Y) a Q(X,Y) pravděpodobnostní rozdělení jejich kartézského součinu. Marginální pravděpodobnost P(x|y) se klasicky odvodí z P(X,Y). Pak
* Conditional entropy H_{X|Y}(P) = - \sum_{x,y} P(x,y)\cdot\log_2(P(x|y))
* Conditional cross-entropy H_{X|Y}(P,Q) = - \sum_{x,y} P(x,y)\cdot\log_2(Q(x|y))
Značení se může lišit (H_{P,Q}(X|Y) místo H_{X|Y}(P,Q)), ale stále platí, že se jedná o veličinu charakterizující pravděpodobnostní rozdělení.
V praxi se entropie textu počítá jinak:
* Nechť text T je posloupnost slov T = w_1,\ldots w_{|T|}, jev x \in X představuje "aktuální slovo" w_i a jev y \in Y představuje "historii" y = w_1, \ldots w_{i-1}. Pak
* H_{X|Y}(T) =-\frac{1}{|T|}\cdot\sum_{i=1\ldots |T|}\log_2(P(x_i|y_i))
Celý tento úvod jsem psal, protože jsem se sám nejednou spletl, když jsem uvažoval o "entropii textu" (případně perplexitě), aniž bych si předem vyjasnil, o jakém pravděpodobnostním rozdělení vlastně uvažuju, jestli je to cross, či ne apod.
=== Definice variant mutual information ===
* pointwise mutual information pMI(x,y) = log_2 \frac{P(x,y)}{P(x)P(y)}
* mutual information MI(X,Y) = E_{x \in X, y \in Y} pMI(x,y) = \sum_{x \in X, y \in Y} P(x,y)log_2 \frac{P(x,y)}{P(x)P(y)}
* average (pointwise) mutual information apMI(x,y) = \sum_{a \in \{x,\bar{x}\}, b \in \{y,\bar{y}\}} P(a,b) log_2 \frac{P(a,b)}{P(a)P(b)}
Platí, že
* MI(X,Y) = H(X) - H(X|Y) = H(Y) - H(Y|X)
* MI(X,Y) = D_{KL}(P(X,Y) || P(X|Y))
=== Vlastní poznámky ===
* 1.2 "Using an ideal model, which capitalizes on every conceivable correlation in the language, L's cross entropy would equal its true entropy H." Zde se pod //true entropy// myslí podmíněná entropie (a to podmíněná vším možným), //ideal model// pak souvisí s pojmem [[http://en.wikipedia.org/wiki/Kolmogorov_complexity|Kolmogorov complexity]]. Nezaměňovat tedy s tím, když někdo pod pojmem //entropie// myslí nepodmíněnou entropii tak, jak se v 2.1 zavádí jako context-free estimation.
* O pár řádek níž se ve vzorečku cross-entropie používá dvakrát Pr_{PRIOR}, ovšem tato pravděpodobnost by měla být počítána pokaždé z jiných dat (train a heldout).
* V 2.4 se uvádí výsledek (dále použitý v 2.5.1), že i slovo ve vzdálenosti 10 je pořád o něco lepší informační zdroj pro předpověď aktuálního slova než slovo ve vzdálenosti 1000 (PPL = 139 vs. 141). Myslím si, že uvedený důkaz není korektní (byť s tvrzením v zásadě souhlasím). Uváděná PPL totiž není dvě na cross-entropii (jak bývá zvykem u perplexity), ale dvě na entropii (trénovacích dat, tedy se jakoby testuje na stejných datech, jako se trénovalo). Slovo, které se v datech vyskytuje jen jednou (tzv. singleton), pak predikuje stejně dobře slovo+10 i slovo+1000 (obě jsou předpovězena zcela jistě, s nulovou entropií). Problém je v tom, že při vzdálenosti 1000 chybí předchůdce pro 1/1000 slov (Brown corpus má 1MW), případně je předchůdcem je umělý token , což klidně mohlo způsobit rozdíl 139 vs. 141.
* Proč se v 2.5.2 používá k výběru trigger pairs právě míra apMI (v článku označovaná jako I(A_0:B))? Proč se nepoužívá jen ten první ze čtyř sčítanců? Jaké to má důsledky/výhody, když se na konci 2.5.3 stejně píše, že negative triggers moc nepomáhají? Uvědomme si, že P(\bar{B}) > P(B), tedy že pokud chápeme apMI jako vážený průměr pMI pro (A_0,B),(A_0,\bar{B}),(\bar{A_0},B),(\bar{A_0},\bar{B}), tak největší váhu nemá (A_0,B), ale (A_0,\bar{B}) a (\bar{A_0},\bar{B}).
* Figure 2 na straně 6 svádí k domněnce, že sloupec 4-10 je vyšší než sloupec 3 právě proto, že je v něm nasčítáno sedm hodnot místo jedné. Nikoli, nejedná se o sčítání, ale o (vážené) průměrování.
* 2.5.3, str. 6, bod 1 uvádí "expected return". Myslí se tím apMI?
* Při hodnocení užitečnosti různých trigger pairs je zajímavé si uvědomit hierarchii intrinsic/extrinsic hodnocení: apMI se používá k výběru trigger pairs, aby se dosáhlo nejlepších LM měřeno podle perplexity, což má vést k tomu, aby se dosáhlo nejlepších výsledků v ASR či MT měřeno podle WER či BLEU. Jaké jsou korelace mezi apMI a PPL či dokonce apMI a WER?
* začátek 4.2: Jaký je rozdíl mezi //subset// a //partition//? Zdá se, že //partition of the event space// je speciální případ //subset of the event space//.
* Kapitola 4 mi poodhalila další z tajemství fenoménu //Maximum Entropy//. Vřele doporučuji k přečtení.