This is an old revision of the document!
Poznámky k článku o Maximum Entropy LM
Definice entropie
Před čtením článku je dobré si připomenout základy ze Statistických metod:
- 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>
- 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>
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):
- 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 <latex>H_{X|Y}(P) = - \sum_{x,y} P(x,y)\cdot\log_2(P(x|y))</latex>
- Conditional cross-entropy <latex>H_{X|Y}(P,Q) = - \sum_{x,y} P(x,y)\cdot\log_2(Q(x|y))</latex>
Značení se může lišit (<latex>H_{P,Q}(X|Y)</latex> místo <latex>H_{X|Y}(P,Q)</latex>), 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 <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>
Definice variant mutual information
- 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>
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 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).
- 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í.
- 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-PPL či dokonce apMI-WER?