Informační dimenze - Information dimension - Wikipedia

v teorie informace, informační dimenze je informační měřítko pro náhodné vektory v Euklidovský prostor, na základě normalizované entropie jemně kvantovaných verzí náhodných vektorů. Tento koncept poprvé představil Alfréd Rényi v roce 1959.^[1]

Jednoduše řečeno, je to míra fraktální dimenze a rozdělení pravděpodobnosti. Charakterizuje rychlost růstu Shannonova entropie dáno postupně jemnější diskretizací prostoru.

V roce 2010 Wu a Verdú dali operativní charakterizaci Rényiho informační dimenze jako základní hranice téměř bezztrátové komprese dat pro analogové zdroje pod různými omezeními pravidelnosti kodéru / dekodéru.

Definice a vlastnosti

Entropie diskrétní náhodné proměnné ${ displaystyle Z}$ je

${ displaystyle mathbb {H} _ {0} (Z) = součet _ {z in supp (P_ {Z})} P_ {Z} (z) log _ {2} { frac {1} {P_ {Z} (z)}}}$

kde ${ displaystyle P_ {Z} (z)}$ je míra pravděpodobnosti z ${ displaystyle Z}$ když ${ displaystyle Z = z}$a ${ displaystyle supp (P_ {Z})}$ označuje množinu ${ displaystyle {z | z v { mathcal {Z}}, P_ {Z} (z)> 0 }}$.

Nechat ${ displaystyle X}$ být libovolná náhodná proměnná se skutečnou hodnotou. Dáno kladné celé číslo ${ displaystyle m}$, vytvoříme novou diskrétní náhodnou proměnnou

${ displaystyle langle X rangle _ {m} = { frac { lfloor mX rfloor} {m}}}$

Kde ${ displaystyle lfloor cdot rfloor}$ je operátor podlahy, který převádí reálné číslo na největší celé číslo menší než to. Pak

${ displaystyle { underline {d}} (X) = liminf _ {m rightarrow infty} { frac { mathbb {H} _ {0} ( langle X rangle _ {m})} { log _ {2} m}}}$

a

${ displaystyle { bar {d}} (X) = limsup _ {m rightarrow infty} { frac { mathbb {H} _ {0} ( langle X rangle _ {m})} { log _ {2} m}}}$

se nazývají spodní a horní informační dimenze ${ displaystyle X}$ resp. Když ${ displaystyle { underline {d}} (X) = { bar {d}} (X)}$, nazýváme tuto hodnotovou informační dimenzi ${ displaystyle X}$,

${ displaystyle d (X) = lim _ {m rightarrow infty} { frac { mathbb {H} _ {0} ( langle X rangle _ {m})} { log _ {2} m}}}$

Některé důležité vlastnosti informační dimenze ${ displaystyle d (X)}$:

• Pokud je mírný stav ${ displaystyle mathbb {H} ( lfloor X rfloor) < infty}$ je splněno, máme ${ displaystyle 0 leq { podtržení {d}} (X) leq { bar {d}} (X) leq 1}$.
• Pro ${ displaystyle n}$-dimenzionální náhodný vektor ${ displaystyle { vec {X}}}$, lze první vlastnost zobecnit na ${ displaystyle 0 leq { podtržení {d}} ({ vec {X}}) leq { bar {d}} ({ vec {X}}) leq n}$.
• Při omezení na exponenciální posloupnost stačí vypočítat horní a dolní informační rozměr ${ displaystyle m = 2 ^ {l}}$.
• ${ displaystyle { underline {d}} (X)}$ a ${ displaystyle { bar {d}} (X)}$ zůstanou nezměněny, pokud jsou při kvantování použity funkce zaokrouhlování nebo stropu.

${ displaystyle d}$-Dimenzionální entropie

Pokud je to informační rozměr ${ displaystyle d}$ existuje, lze definovat ${ displaystyle d}$-rozměrná entropie této distribuce pomocí

${ displaystyle mathbb {H} _ {d (X)} (X) = lim _ {n rightarrow + infty} ( mathbb {H} _ {0} ( langle X rangle _ {n} ) -d (X) log _ {2} n)}$

za předpokladu, že limit existuje. Li ${ displaystyle d = 0}$, nula-dimenzionální entropie se rovná standardu Shannonova entropie ${ displaystyle mathbb {H} _ {0} (X)}$. Pro celočíselnou dimenzi ${ displaystyle d = n geq 1}$, ${ displaystyle n}$-dimenzionální entropie je ${ displaystyle n}$-násobný integrál definující příslušné diferenciální entropie.

Diskrétní kontinuální distribuce směsi

Podle Lebesgueova věta o rozkladu,^[2] rozdělení pravděpodobnosti může být jednoznačně reprezentováno směsí

${ displaystyle v = pP_ {Xd} + qP_ {Xc} + rP_ {Xs}}$

kde ${ displaystyle p + q + r = 1}$ a ${ displaystyle p, q, r geq 0}$; ${ displaystyle P_ {Xd}}$ je čistě atomová míra pravděpodobnosti (diskrétní část), ${ displaystyle P_ {Xc}}$ je absolutně kontinuální míra pravděpodobnosti a ${ displaystyle P_ {Xs}}$ je míra pravděpodobnosti singulární vzhledem k Lebesgueově míře, ale bez atomů (singulární část) ${ displaystyle X}$ být náhodná proměnná taková ${ displaystyle mathbb {H} ( lfloor X rfloor) < infty}$. Předpokládejme distribuci ${ displaystyle X}$ lze reprezentovat jako

${ displaystyle v = (1- rho) P_ {Xd} + rho P_ {Xc}}$

kde ${ displaystyle P_ {Xd}}$ je diskrétní míra a ${ displaystyle P_ {Xc}}$ je absolutně kontinuální míra pravděpodobnosti s ${ displaystyle 0 leq rho leq 1}$. Pak

${ displaystyle d (X) = rho}$

Navíc vzhledem k tomu ${ displaystyle mathbb {H} _ {0} (P_ {Xd})}$ a diferenciální entropie ${ displaystyle h (P_ {Xc})}$, ${ displaystyle d}$-Dimenzionální entropie je jednoduše dána

${ displaystyle mathbb {H} _ { rho} (X) = (1- rho) mathbb {H} _ {0} (P_ {Xd}) + rho h (P_ {Xc}) + mathbb {H} _ {0} ( rho)}$

kde ${ displaystyle mathbb {H} _ {0} ( rho)}$ je Shannonova entropie diskrétní náhodné proměnné ${ displaystyle Z}$ s ${ displaystyle P_ {Z} (1) = rho}$ a ${ displaystyle P_ {Z} (0) = 1- rho}$ a dané

${ displaystyle mathbb {H} _ {0} ( rho) = rho log _ {2} { frac {1} { rho}} + (1- rho) log _ {2} { frac {1} {1- rho}}}$

Příklad

Zvažte signál, který má a Gaussovo rozdělení pravděpodobnosti.

Signál projdeme půlvlnou usměrňovač který převede všechny záporné hodnoty na 0 a udržuje všechny ostatní hodnoty. Poloviční vlnový usměrňovač lze charakterizovat funkcí

${ displaystyle f (x) = { begin {cases} x, & { text {if}} x geq 0 0, & x <0 end {cases}}}$

Poté má signál na výstupu usměrňovače a usměrněné Gaussovo rozdělení. Vyznačuje se atomovou hmotností 0,5 a má Gaussian PDF pro všechny ${ displaystyle x> 0}$.

S touto distribucí směsi použijeme výše uvedený vzorec a získáme informační dimenzi ${ displaystyle d}$ rozdělení a vypočítat ${ displaystyle d}$-rozměrná entropie.

${ displaystyle d (X) = rho = 0,5}$

Normalizovaná pravá část nulové střední Gaussovy distribuce má entropii ${ displaystyle h (P_ {Xc}) = { frac {1} {2}} log _ {2} (2 pi e sigma ^ {2}) - 1}$, proto

${ displaystyle { begin {zarovnáno} mathbb {H} _ {0,5} (X) & = (1-0,5) (1 log _ {2} 1) + 0,5 h (P_ {Xc}) + mathbb {H} _ {0} (0,5) & = 0 + { frac {1} {2}} ({ frac {1} {2}} log _ {2} (2 pi e sigma ^ {2}) - 1) +1 & = { frac {1} {4}} log _ {2} (2 pi e sigma ^ {2}) + { frac {1} { 2}} , { text {bit (y)}} end {zarovnáno}}}$

Připojení k diferenciální entropii

Je to zobrazeno ^[3] že informační dimenze a diferenciální entropie jsou úzce propojeny.

Nechat ${ displaystyle X}$ být pozitivní náhodná proměnná s hustotou ${ displaystyle f (x)}$.

Předpokládejme, že rozdělíme rozsah ${ displaystyle X}$ do košů délky ${ displaystyle Delta}$. Věta o střední hodnotě existuje hodnota ${ displaystyle x_ {i}}$ uvnitř každého koše tak, že

${ displaystyle f (x_ {i}) Delta = int _ {i Delta} ^ {(i + 1) Delta} f (x) ; mathrm {d} x}$

Zvažte diskretizovanou náhodnou proměnnou ${ displaystyle X ^ { Delta} = x_ {i}}$ -li ${ Displaystyle i Delta leq X <(i + 1) Delta}$.

Pravděpodobnost každého bodu podpory ${ displaystyle X ^ { Delta} = x_ {i}}$ je

${ displaystyle P_ {X ^ { Delta}} (x_ {i}) = int _ {i Delta} ^ {(i + 1) Delta} f (x) ; mathrm {d} x = f (x_ {i}) Delta}$

Entropie této proměnné je

${ displaystyle { begin {aligned} mathbb {H} _ {0} (X ^ { Delta}) & = - sum _ {x_ {i} v supp (P_ {X ^ { Delta}} )} P_ {X ^ { Delta}} log _ {2} P_ {X ^ { Delta}} & = - sum _ {x_ {i} v supp (P_ {X ^ { Delta }})} f (x_ {i}) Delta log _ {2} (f (x_ {i}) Delta) & = sum _ {x_ {i} v supp (P_ {X ^ { Delta}})} Delta f (x_ {i}) log _ {2} f (x_ {i}) - sum _ {x_ {i} v supp (P_ {X ^ { Delta} })} f (x_ {i}) Delta log _ {2} Delta & = sum _ {x_ {i} in supp (P_ {X ^ { Delta}})} Delta f (x_ {i}) log _ {2} f (x_ {i}) - log _ {2} Delta end {zarovnáno}}}$

Pokud jsme nastavili ${ displaystyle Delta = 1 / m}$ a ${ displaystyle x_ {i} = i / m}$ pak děláme přesně stejnou kvantizaci jako definice informační dimenze. Protože opětovné značení událostí diskrétní náhodné proměnné nemění její entropii, máme

${ displaystyle mathbb {H} _ {0} (X ^ {1 / m}) = mathbb {H} _ {0} ( langle X rangle _ {m}).}$

To přináší

${ displaystyle mathbb {H} _ {0} ( langle X rangle _ {m}) = - sum { frac {1} {m}} f (x_ {i}) log _ {2} f (x_ {i}) + log _ {2} m}$

a kdy ${ displaystyle m}$ je dostatečně velký,

${ displaystyle - součet Delta f (x_ {i}) log _ {2} f (x_ {i}) přibližně int f (x) log _ {2} { frac {1} {f (x)}} mathrm {d} x}$

což je diferenciální entropie ${ displaystyle h (x)}$ spojité náhodné proměnné. Zejména pokud ${ displaystyle f (x)}$ je tedy Riemann integrovatelný

${ displaystyle h (X) = lim _ {m rightarrow infty} mathbb {H} _ {0} ( langle X rangle _ {m}) - log _ {2} (m).}$

Srovnání s ${ displaystyle d}$-dimenzionální entropie ukazuje, že diferenciální entropie je přesně jednorozměrná entropie

${ displaystyle h (X) = mathbb {H} _ {1} (X).}$

Ve skutečnosti to lze zobecnit na vyšší dimenze. Rényi ukazuje, že pokud ${ displaystyle { vec {X}}}$ je náhodný vektor v a ${ displaystyle n}$-rozměrný euklidovský prostor ${ displaystyle Re ^ {n}}$ s absolutně spojitým rozdělením s funkcí hustoty pravděpodobnosti ${ displaystyle f _ { vec {X}} ({ vec {x}})}$ a konečná entropie celočíselné části (${ displaystyle H_ {0} ( langle { vec {X}} rangle _ {m}) < infty}$), my máme${ displaystyle d ({ vec {X}}) = n}$

a

${ displaystyle mathbb {H} _ {n} ({ vec {X}}) = int cdots int f _ { vec {X}} ({ vec {x}}) log _ {2 } { frac {1} {f _ { vec {X}} ({ vec {x}})}} mathrm {d} { vec {x}},}$

pokud integrál existuje.

Bezztrátová komprese dat

Informační dimenze distribuce poskytuje teoretickou horní hranici rychlosti komprese, pokud chceme komprimovat proměnnou pocházející z této distribuce. V kontextu bezztrátové komprese dat se snažíme komprimovat reálné číslo s méně reálným číslem, které má nekonečnou přesnost.

Hlavním cílem bezztrátové komprese dat je najít efektivní reprezentace pro zdrojové realizace ${ displaystyle x ^ {n} v { mathcal {X}} ^ {n}}$ podle ${ displaystyle y ^ {n} in { mathcal {Y}} ^ {n}}$. A ${ displaystyle (n, k) -}$kód pro ${ displaystyle {X_ {i}: i in { mathcal {N}} }}$ je pár mapování:

• kodér: ${ displaystyle f_ {n}: { mathcal {X}} ^ {n} rightarrow { mathcal {Y}} ^ {k}}$ který převádí informace ze zdroje na symboly pro komunikaci nebo ukládání;
• dekodér: ${ displaystyle g_ {n}: { mathcal {Y}} ^ {k} rightarrow { mathcal {X}} ^ {n}}$ je obrácený proces, převod kódových symbolů zpět do formy, které příjemce rozumí.

Pravděpodobnost chyby bloku je ${ displaystyle { mathcal {P}} {g_ {n} (f_ {n} (X ^ {n})) neq X ^ {n} }}$.

Definovat ${ displaystyle r ( epsilon)}$ být infimum z ${ displaystyle r geq 0}$ taková, že existuje posloupnost ${ displaystyle (n, lfloor rn rfloor) -}$kódy takové, že ${ displaystyle { mathcal {P}} {g_ {n} (f_ {n} (X ^ {n})) neq X ^ {n} } leq epsilon}$ pro všechny dostatečně velké ${ displaystyle n}$.

Tak ${ displaystyle r ( epsilon)}$ v zásadě udává poměr mezi délkou kódu a délkou zdroje, ukazuje, jak dobrý je konkrétní pár dekodéru dekodéru. Základní limity v bezztrátovém kódování zdroje jsou následující.^[4]

Zvažte funkci kontinuálního kodéru ${ displaystyle f (x): Re ^ {n} rightarrow Re ^ { lfloor Rn rfloor}}$ s funkcí nepřetržitého dekodéru ${ displaystyle g (x): Re ^ { lfloor Rn rfloor} rightarrow Re ^ {n}}$. Pokud nebudeme ukládat žádnou pravidelnost ${ displaystyle f (x)}$ a ${ displaystyle g (x)}$, vzhledem k bohaté struktuře ${ displaystyle Re}$, máme minimum ${ displaystyle epsilon}$- dosažitelná rychlost ${ displaystyle R_ {0} ( epsilon) = 0}$ pro všechny ${ displaystyle 0 < epsilon leq 1}$. To znamená, že lze vytvořit pár kodér-dekodér s rychlostí komprese nekonečna.

Abychom získali nějaké netriviální a smysluplné závěry, dovolme ${ displaystyle R ^ {*} ( epsilon)}$ minimum ${ displaystyle epsilon -}$dosažitelná rychlost pro lineární kodér a dekodér Borel. Je-li náhodná proměnná ${ displaystyle X}$ má distribuci, která je směsicí diskrétní a spojité části. Pak ${ displaystyle R ^ {*} ( epsilon) = d (X)}$ pro všechny ${ displaystyle 0 < epsilon leq 1}$ Předpokládejme, že omezíme dekodér na Lipschitzovu spojitou funkci a ${ displaystyle { bar {d}} (X) < infty}$ drží, pak minimum ${ displaystyle epsilon -}$dosažitelná míra ${ displaystyle R ( epsilon) geq { bar {d}} (X)}$ pro všechny ${ displaystyle 0 < epsilon leq 1}$.

Viz také

• Fraktální rozměr
• Korelační dimenze
• Entropie (teorie informace)

Poznámky

Reference

• Çınlar, Erhan (2011). Pravděpodobnost a Stochastics. Postgraduální texty z matematiky. 261. Springer. doi:10.1007/978-0-387-87859-1. ISBN  978-0-387-87858-4.CS1 maint: ref = harv (odkaz)

• Cover, Thomas M .; Thomas, Joy A. (2012). Základy teorie informace (2. vyd.). Wiley. ISBN  9781118585771.CS1 maint: ref = harv (odkaz)

• Rényi, A. (březen 1959). "O dimenzi a entropii rozdělení pravděpodobnosti". Acta Mathematica Academiae Scientiarum Hungaricae. 10 (1–2): 193–215. doi:10.1007 / BF02063299. ISSN  0001-5954.CS1 maint: ref = harv (odkaz)

• Wu, Yihong; Verdu, S. (srpen 2010). „Rényi Information Dimension: Fundamental Limits of Almost Lossless Analog Compression“. Transakce IEEE na teorii informací. 56 (8): 3721–3748. doi:10.1109 / TIT.2010.2050803. ISSN  0018-9448.CS1 maint: ref = harv (odkaz)