[ Skip to the content ]

Institute of Formal and Applied Linguistics Wiki


[ Back to the navigation ]

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

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
Line 10: Line 10:
   * 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>
Line 15: Line 16:
 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
Line 24: Line 25:
 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},ylog \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_{\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,blog_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í.

[ Back to the navigation ] [ Back to the content ]