Информационное измерение - Information dimension

В теория информации, информационное измерение является информационной мерой для случайных векторов в Евклидово пространство, основанный на нормированном энтропия тонко квантованных версий случайных векторов. Эта концепция была впервые представлена Альфред Реньи в 1959 г.^[1]

Проще говоря, это мера фрактальная размерность из распределение вероятностей. Он характеризует скорость роста Энтропия Шеннона задаваемые последовательно более тонкой дискретизацией пространства.

В 2010 году Ву и Верду дали рабочую характеристику информационного измерения Реньи как фундаментального ограничения сжатия данных практически без потерь для аналоговых источников при различных ограничениях регулярности кодера / декодера.

Определение и свойства

Энтропия дискретной случайной величины ${\displaystyle Z}$ является

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

куда ${\displaystyle P_{Z}(z)}$ это вероятностная мера из ${\displaystyle Z}$ когда ${\displaystyle Z=z}$, а ${\displaystyle supp(P_{Z})}$ обозначает набор ${\displaystyle \{z|z\in {\mathcal {Z}},P_{Z}(z)>0\}}$.

Позволять ${\displaystyle X}$ - произвольная случайная величина с действительным знаком. Учитывая положительное целое число ${\displaystyle m}$, мы создаем новую дискретную случайную величину

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

где ${\displaystyle \lfloor \cdot \rfloor }$ - это оператор пола, который преобразует действительное число в наибольшее целое меньшее его. потом

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

и

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

называются нижним и верхним информационными измерениями ${\displaystyle X}$ соответственно. Когда ${\displaystyle {\underline {d}}(X)={\bar {d}}(X)}$, мы называем это ценностным информационным измерением ${\displaystyle X}$,

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

Некоторые важные свойства информационного измерения ${\displaystyle d(X)}$:

• Если легкое состояние ${\displaystyle \mathbb {H} (\lfloor X\rfloor )<\infty }$ выполнено, у нас есть ${\displaystyle 0\leq {\underline {d}}(X)\leq {\bar {d}}(X)\leq 1}$.
• Для ${\displaystyle n}$-мерный случайный вектор ${\displaystyle {\vec {X}}}$, первое свойство можно обобщить на ${\displaystyle 0\leq {\underline {d}}({\vec {X}})\leq {\bar {d}}({\vec {X}})\leq n}$.
• Достаточно вычислить верхнюю и нижнюю информационные размерности при ограничении экспоненциальной подпоследовательностью ${\displaystyle m=2^{l}}$.
• ${\displaystyle {\underline {d}}(X)}$ и ${\displaystyle {\bar {d}}(X)}$ остаются неизменными, если при квантовании используются функции округления или ограничения.

${\displaystyle d}$-Мерная энтропия

Если информационное измерение ${\displaystyle d}$ существует, можно определить ${\displaystyle d}$-мерная энтропия этого распределения на

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

при условии, что лимит существует. Если ${\displaystyle d=0}$, нульмерная энтропия равна стандартной Энтропия Шеннона ${\displaystyle \mathbb {H} _{0}(X)}$. Для целочисленного измерения ${\displaystyle d=n\geq 1}$, то ${\displaystyle n}$-мерная энтропия - это ${\displaystyle n}$-кратный интеграл, определяющий соответствующие дифференциальная энтропия.

Дискретно-непрерывное распределение смеси

В соответствии с Теорема разложения Лебега,^[2] распределение вероятностей может быть однозначно представлено смесью

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

куда ${\displaystyle p+q+r=1}$ и ${\displaystyle p,q,r\geq 0}$; ${\displaystyle P_{Xd}}$ является чисто атомарной вероятностной мерой (дискретной частью), ${\displaystyle P_{Xc}}$ - абсолютно непрерывная вероятностная мера, а ${\displaystyle P_{Xs}}$ - вероятностная мера, сингулярная относительно меры Лебега, но не содержащая атомов (сингулярная часть). ${\displaystyle X}$ - случайная величина такая, что ${\displaystyle \mathbb {H} (\lfloor X\rfloor )<\infty }$. Предположим, что распределение ${\displaystyle X}$ можно представить как

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

куда ${\displaystyle P_{Xd}}$ дискретная мера и ${\displaystyle P_{Xc}}$ - абсолютно непрерывная вероятностная мера с ${\displaystyle 0\leq \rho \leq 1}$. потом

${\displaystyle d(X)=\rho }$

Более того, учитывая ${\displaystyle \mathbb {H} _{0}(P_{Xd})}$ и дифференциальная энтропия ${\displaystyle h(P_{Xc})}$, то ${\displaystyle d}$-Мерная энтропия просто дается

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

куда ${\displaystyle \mathbb {H} _{0}(\rho )}$ энтропия Шеннона дискретной случайной величины ${\displaystyle Z}$ с ${\displaystyle P_{Z}(1)=\rho }$ и ${\displaystyle P_{Z}(0)=1-\rho }$ и дано

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

Пример

Рассмотрим сигнал, имеющий Гауссово распределение вероятностей.

Пропускаем сигнал через полуволну выпрямитель который преобразует все отрицательные значения в 0 и сохраняет все остальные значения. Однополупериодный выпрямитель можно охарактеризовать функцией

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

Тогда на выходе выпрямителя сигнал имеет выпрямленное гауссово распределение. Он характеризуется атомной массой 0,5 и имеет гауссову PDF для всех ${\displaystyle x>0}$.

С этим распределением смеси мы применяем приведенную выше формулу и получаем информационное измерение ${\displaystyle d}$ распределения и вычислить ${\displaystyle d}$-мерная энтропия.

${\displaystyle d(X)=\rho =0.5}$

Нормализованная правая часть гауссова распределения с нулевым средним имеет энтропию ${\displaystyle h(P_{Xc})={\frac {1}{2}}\log _{2}(2\pi e\sigma ^{2})-1}$, следовательно

${\displaystyle {\begin{aligned}\mathbb {H} _{0.5}(X)&=(1-0.5)(1\log _{2}1)+0.5h(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(s)}}\end{aligned}}}$

Связь с дифференциальной энтропией

Показано ^[3] это информационное измерение и дифференциальная энтропия тесно связаны.

Позволять ${\displaystyle X}$ - положительная случайная величина с плотностью ${\displaystyle f(x)}$.

Предположим, мы разделим диапазон ${\displaystyle X}$ в ячейки длины ${\displaystyle \Delta }$. По теореме о среднем значении существует значение ${\displaystyle x_{i}}$ в каждом бункере так, чтобы

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

Рассмотрим дискретизированную случайную величину ${\displaystyle X^{\Delta }=x_{i}}$ если ${\displaystyle i\Delta \leq X<(i+1)\Delta }$.

Вероятность каждой точки поддержки ${\displaystyle X^{\Delta }=x_{i}}$ является

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

Энтропия этой переменной равна

${\displaystyle {\begin{aligned}\mathbb {H} _{0}(X^{\Delta })&=-\sum _{x_{i}\in supp(P_{X^{\Delta }})}P_{X^{\Delta }}\log _{2}P_{X^{\Delta }}\\&=-\sum _{x_{i}\in supp(P_{X^{\Delta }})}f(x_{i})\Delta \log _{2}(f(x_{i})\Delta )\\&=\sum _{x_{i}\in supp(P_{X^{\Delta }})}\Delta f(x_{i})\log _{2}f(x_{i})-\sum _{x_{i}\in 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{aligned}}}$

Если мы установим ${\displaystyle \Delta =1/m}$ и ${\displaystyle x_{i}=i/m}$ затем мы делаем то же самое квантование, что и определение информационного измерения. Поскольку перемаркировка событий дискретной случайной величины не меняет ее энтропию, мы имеем

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

Это дает

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

и когда ${\displaystyle m}$ достаточно большой,

${\displaystyle -\sum \Delta f(x_{i})\log _{2}f(x_{i})\approx \int f(x)\log _{2}{\frac {1}{f(x)}}\mathrm {d} x}$

которая является дифференциальной энтропией ${\displaystyle h(x)}$ непрерывной случайной величины. В частности, если ${\displaystyle f(x)}$ интегрируем по Риману, то

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

Сравнивая это с ${\displaystyle d}$-мерная энтропия показывает, что дифференциальная энтропия - это в точности одномерная энтропия

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

Фактически, это можно обобщить на более высокие измерения. Реньи показывает, что если ${\displaystyle {\vec {X}}}$ случайный вектор в ${\displaystyle n}$-мерное евклидово пространство ${\displaystyle \Re ^{n}}$ с абсолютно непрерывным распределением с функцией плотности вероятности ${\displaystyle f_{\vec {X}}({\vec {x}})}$ и конечная энтропия целой части (${\displaystyle H_{0}(\langle {\vec {X}}\rangle _{m})<\infty }$), у нас есть${\displaystyle d({\vec {X}})=n}$

и

${\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}},}$

если интеграл существует.

Сжатие данных без потерь

Информационное измерение распределения дает теоретическую верхнюю границу степени сжатия, если кто-то хочет сжать переменную, полученную из этого распределения. В контексте сжатия данных без потерь мы пытаемся сжать действительное число с меньшим количеством действительного числа, которое имеет бесконечную точность.

Основная цель сжатия данных без потерь - найти эффективные представления для исходных реализаций. ${\displaystyle x^{n}\in {\mathcal {X}}^{n}}$ к ${\displaystyle y^{n}\in {\mathcal {Y}}^{n}}$. А ${\displaystyle (n,k)-}$код для ${\displaystyle \{X_{i}:i\in {\mathcal {N}}\}}$ это пара отображений:

• кодировщик: ${\displaystyle f_{n}:{\mathcal {X}}^{n}\rightarrow {\mathcal {Y}}^{k}}$ который преобразует информацию из источника в символы для передачи или хранения;
• декодер: ${\displaystyle g_{n}:{\mathcal {Y}}^{k}\rightarrow {\mathcal {X}}^{n}}$ - это обратный процесс, преобразовывающий кодовые символы обратно в форму, понятную получателю.

Вероятность ошибки блока равна ${\displaystyle {\mathcal {P}}\{g_{n}(f_{n}(X^{n}))\neq X^{n}\}}$.

Определять ${\displaystyle r(\epsilon )}$ быть пределом ${\displaystyle r\geq 0}$ такая, что существует последовательность ${\displaystyle (n,\lfloor rn\rfloor )-}$коды такие, что ${\displaystyle {\mathcal {P}}\{g_{n}(f_{n}(X^{n}))\neq X^{n}\}\leq \epsilon }$ для всех достаточно больших ${\displaystyle n}$.

Так ${\displaystyle r(\epsilon )}$ в основном дает соотношение между длиной кода и длиной источника, это показывает, насколько хороша конкретная пара кодеров-декодеров. Основные ограничения в кодировании источников без потерь следующие.^[4]

Рассмотрим функцию непрерывного энкодера ${\displaystyle f(x):\Re ^{n}\rightarrow \Re ^{\lfloor Rn\rfloor }}$ с функцией непрерывного декодирования ${\displaystyle g(x):\Re ^{\lfloor Rn\rfloor }\rightarrow \Re ^{n}}$. Если мы не налагаем регулярности на ${\displaystyle f(x)}$ и ${\displaystyle g(x)}$, благодаря богатой структуре ${\displaystyle \Re }$, у нас есть минимум ${\displaystyle \epsilon }$-достижимая ставка ${\displaystyle R_{0}(\epsilon )=0}$ для всех ${\displaystyle 0<\epsilon \leq 1}$. Это означает, что можно построить пару кодер-декодер с бесконечной степенью сжатия.

Чтобы сделать несколько нетривиальных и содержательных выводов, позвольте ${\displaystyle R^{*}(\epsilon )}$ минимум ${\displaystyle \epsilon -}$достижимая скорость для линейного кодировщика и декодера Бореля. Если случайная величина ${\displaystyle X}$ имеет распределение, которое представляет собой смесь дискретной и непрерывной частей. потом ${\displaystyle R^{*}(\epsilon )=d(X)}$ для всех ${\displaystyle 0<\epsilon \leq 1}$ Предположим, мы ограничиваем декодер непрерывной липшицевой функцией и ${\displaystyle {\bar {d}}(X)<\infty }$ выполняется, то минимум ${\displaystyle \epsilon -}$достижимая ставка ${\displaystyle R(\epsilon )\geq {\bar {d}}(X)}$ для всех ${\displaystyle 0<\epsilon \leq 1}$.

Смотрите также

• Фрактальное измерение
• Измерение корреляции
• Энтропия (теория информации)

Примечания

1. Видеть Реньи 1959.
2. Видеть Inlar 2011.
3. Видеть Обложка и Томас 2012.
4. Видеть Wu & Verdu 2010.

Рекомендации

• Чинлар, Эрхан (2011). Вероятность и стохастика. Тексты для выпускников по математике. 261. Springer. Дои:10.1007/978-0-387-87859-1. ISBN  978-0-387-87858-4.

• Обложка, Томас М .; Томас, Джой А. (2012). Элементы теории информации (2-е изд.). Вайли. ISBN  9781118585771.

• Реньи, А. (март 1959 г.). «О размерности и энтропии вероятностных распределений». Acta Mathematica Academiae Scientiarum Hungaricae. 10 (1–2): 193–215. Дои:10.1007 / BF02063299. ISSN  0001-5954.

• Ву, Ихонг; Верду, С. (август 2010 г.). «Информационное измерение Реньи: фундаментальные пределы аналогового сжатия почти без потерь». IEEE Transactions по теории информации. 56 (8): 3721–3748. Дои:10.1109 / TIT.2010.2050803. ISSN  0018-9448.