|
Next revision
|
Previous revision
|
courses:rg:maxent-lm [2010/05/11 19:11]
popel vytvořeno |
courses:rg:maxent-lm [2013/04/27 22:52] (current)
popel typo |
| * Mějme diskrétní prostor jevů X a dvě pravděpodobností rozdělení <latex>P, Q : X \rightarrow [0,1]</latex>. Pak | * Mějme diskrétní prostor jevů X a dvě pravděpodobností rozdělení <latex>P, Q : X \rightarrow [0,1]</latex>. Pak |
| * Entropy <latex>H(P) = - \sum_{x \in X} P(x)\cdot \log_2 P(x)</latex> | * Entropy <latex>H(P) = - \sum_{x \in X} P(x)\cdot \log_2 P(x)</latex> |
| | * Perplexity <latex>PPL(P) = 2^{H(P)}</latex> |
| * Cross-entropy <latex>H(P, Q) = - \sum_{x \in X} P(x) \cdot \log_2 Q(x)</latex> | * Cross-entropy <latex>H(P, Q) = - \sum_{x \in X} P(x) \cdot \log_2 Q(x)</latex> |
| * Kullback-Leibler divergence <latex>D_{KL}(P || Q) = \sum_{x \in X} P(x)\cdot\log_2(\frac{P(x)}{Q(x)})</latex> | * Kullback-Leibler divergence <latex>D_{KL}(P || Q) = \sum_{x \in X} P(x)\cdot\log_2(\frac{P(x)}{Q(x)})</latex> |
| 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. | 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 cross-entropii lze zavést definice (s trochu jiným značením): | 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 | * 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 |
| V praxi se entropie textu počítá jinak: | V praxi se entropie textu počítá jinak: |
| * Nechť text T je posloupnost slov <latex>T = w_1,\ldots w_{|T|}</latex>, jev <latex>x \in X</latex> představuje "aktuální slovo" <latex>w_i</latex> a jev <latex>y \in Y</latex> představuje "historii" <latex>y = w_1, \ldots w_{i-1}</latex>. Pak | * Nechť text T je posloupnost slov <latex>T = w_1,\ldots w_{|T|}</latex>, jev <latex>x \in X</latex> představuje "aktuální slovo" <latex>w_i</latex> a jev <latex>y \in Y</latex> představuje "historii" <latex>y = w_1, \ldots w_{i-1}</latex>. Pak |
| * <latex>H_{X|Y}(T) =-\frac{1}{|T|}\cdot\sum_{i=1\ldots |T|}\log_2(P(y_i|x_i))</latex> | * <latex>H_{X|Y}(T) =-\frac{1}{|T|}\cdot\sum_{i=1\ldots |T|}\log_2(P(x_i|y_i))</latex> |
| |
| === Definice mutual information === | 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. |
| |
| * pointwise mutual information <latex>pMI(x,y) = log \frac{P(x,y)}{P(x)P(y)}</latex> | === Definice variant mutual information === |
| * mutual information <latex>MI(X,Y) = E_{x \in X, y \in Y} pMI(x,y)</latex> | |
| * average (pointwise) mutual information <latex>apMI(x,y) = P(x,y) log \frac{P(x,y)}{P(x)P(y)} + P(x,\bar{y}) log \frac{P(x,\bar{y})}{P(x)P(\bar{y})} + P(\bar{x},y) log \frac{P(\bar{x},y)}{P(\bar{x})P(y)} + P(\bar{x},\bar{y}) log \frac{P(\bar{x},\bar{y})}{P(\bar{x})P(\bar{y})}</latex> | * pointwise mutual information <latex>pMI(x,y) = log_2 \frac{P(x,y)}{P(x)P(y)}</latex> |
| | * mutual information <latex>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)}</latex> |
| | * average (pointwise) mutual information <latex>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)}</latex> |
| | |
| | Platí, že |
| | * <latex>MI(X,Y) = H(X) - H(X|Y) = H(Y) - H(Y|X)</latex> |
| | * <latex>MI(X,Y) = D_{KL}(P(X,Y) || P(X|Y))</latex> |
| | |
| | === 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 <latex>Pr_{PRIOR}</latex>, 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 <s>, 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 <latex>I(A_0:B)</latex>)? 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 <latex>P(\bar{B}) > P(B)</latex>, tedy že pokud chápeme apMI jako vážený průměr pMI pro <latex>(A_0,B),(A_0,\bar{B}),(\bar{A_0},B),(\bar{A_0},\bar{B})</latex>, tak největší váhu nemá <latex>(A_0,B)</latex>, ale <latex>(A_0,\bar{B})</latex> a <latex>(\bar{A_0},\bar{B})</latex>. |
| | * 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í. |
