Pinskersova nerovnost - Pinskers inequality - Wikipedia

v teorie informace, Pinskerova nerovnost, pojmenovaný po svém vynálezci Mark Semenovich Pinsker, je nerovnost který ohraničuje celková variační vzdálenost (nebo statistická vzdálenost) z hlediska Kullback – Leiblerova divergence Nerovnost je omezena stálými faktory.^[1]

Formální prohlášení

Pinskerova nerovnost uvádí, že pokud ${ displaystyle P}$ a ${ displaystyle Q}$ jsou dva rozdělení pravděpodobnosti na měřitelný prostor ${ displaystyle (X, Sigma)}$, pak

${ displaystyle delta (P, Q) leq { sqrt {{ frac {1} {2}} D _ { mathrm {KL}} (P | Q)}}}}$

kde

${ displaystyle delta (P, Q) = sup { bigl {} | P (A) -Q (A) | { big |} A in Sigma { text {je měřitelná událost}} { bigr }}}$

je celková variační vzdálenost (nebo statistická vzdálenost) mezi ${ displaystyle P}$ a ${ displaystyle Q}$ a

${ displaystyle D _ { mathrm {KL}} (P | Q) = operatorname {E} _ {P} left ( log { frac { mathrm {d} P} { mathrm {d} Q }} right) = int _ {X} left ( log { frac { mathrm {d} P} { mathrm {d} Q}} right) , mathrm {d} P}$

je Kullback – Leiblerova divergence v nats. Když ukázkový prostor ${ displaystyle X}$ je konečná množina, Kullback – Leiblerova divergence je dána vztahem

${ displaystyle D _ { mathrm {KL}} (P | Q) = součet _ {i v X} vlevo ( log { frac {P (i)} {Q (i)}}} vpravo ) P (i) !}$

Všimněte si, že pokud jde o celková variační norma ${ displaystyle | P-Q |}$ z podepsané opatření ${ displaystyle P-Q}$, Pinskerova nerovnost se liší od výše uvedené dvěma faktorem:

${ displaystyle | P-Q | leq { sqrt {2D _ { mathrm {KL}} (P | Q)}}}}$

Důkaz Pinskerovy nerovnosti používá nerovnost oddílů pro F-rozdíly.

Dějiny

Pinsker nejprve dokázal nerovnost horší konstantou. Nerovnost ve výše uvedené formě byla nezávisle prokázána Kullback, Csiszár, a Kemperman.^[2]

Inverzní problém

Přesná inverze nerovnosti nemůže platit: pro každého ${ displaystyle varepsilon> 0}$existují distribuce ${ displaystyle P _ { varepsilon}, Q}$ s ${ displaystyle delta (P _ { varepsilon}, Q) leq varepsilon}$ ale ${ displaystyle D _ { mathrm {KL}} (P _ { varepsilon} | Q) = infty}$. Snadný příklad je dán dvoubodovým prostorem ${ displaystyle {0,1 }}$ s ${ displaystyle Q (0) = 0, Q (1) = 1}$ a ${ displaystyle P _ { varepsilon} (0) = varepsilon, P _ { varepsilon} (1) = 1- varepsilon}$. ^[3]

Na konečných prostorech však platí inverzní nerovnost ${ displaystyle X}$ s konstantou v závislosti na ${ displaystyle Q}$.^[4] Přesněji lze ukázat, že s definicí ${ displaystyle alpha _ {Q}: = min _ {x v X: Q (x)> 0} Q (x)}$ máme pro každé opatření ${ displaystyle P}$ což je naprosto kontinuální ${ displaystyle Q}$

${ displaystyle { frac {1} {2}} D _ { mathrm {KL}} (P | Q) leq { frac {1} { alpha _ {Q}}} delta (P, Q ) ^ {2}.}$

V důsledku toho, pokud ${ displaystyle Q}$ má plný Podpěra, podpora (tj. ${ displaystyle Q (x)> 0}$ pro všechny ${ displaystyle x v X}$), pak

${ displaystyle delta (P, Q) ^ {2} leq { frac {1} {2}} D (P | Q) leq { frac {1} { alpha _ {Q}}} delta (P, Q) ^ {2}.}$

Reference

Další čtení

• Thomas M. Cover a Joy A. Thomas: Základy teorie informace, 2. vydání, Willey-Interscience, 2006
• Nicolo Cesa-Bianchi a Gábor Lugosi: Predikce, učení a hry, Cambridge University Press, 2006