Ronald Rosenfeld: A Maximum Entropy Approach to Adaptive Statistical Language Modeling

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>
  • 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>
  • 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 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 <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(x_i|y_i))</latex>

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_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>

• 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).
• 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í.