Информационное измерение

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

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

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

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

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

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

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

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

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

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

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

и

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

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

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

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

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

d -мерная энтропия

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

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

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

Эквивалентное определение информационного измерения

В 1994 году Кавабата и Дембо в работе Kawabata & Dembo 1994 предложили новый способ измерения информации, основанный на значении скорости искажения случайной величины. Мера определяется как

$d_{R}(X)=-2{\frac {R(X,D)}{\log D}},$

где $R(X,D)$ — это функция искажения скорости, которая определяется как

$R(X,D)=\min _{\|X-{\hat {X}}\|_{2}\leq D}I(X,{\hat {X}}),$

или, что то же самое, минимальная информация, которая может привести к $D$-близкое приближение $X$.

Далее они доказали, что такое определение эквивалентно определению информационного измерения. Формально,

$d_{R}(X)=d(X).$

Смещение размерной скорости

Используя приведенное выше определение информационного измерения Реньи, мера, аналогичная d -мерной энтропии, определена в Charusaie, Amini & Rini 2022 . Это значение $b(X)$ то, что называется смещением размерной скорости, определяется таким образом, чтобы уловить конечный член функции скорости-искажения. Формально,

$R(X,D)=-{\frac {d(X)}{2}}\log {\frac {2\pi eD}{d(X)}}+b(X).$

Смещение размерной скорости равно d -мерной скорости для непрерывного , дискретного и дискретно-непрерывного смешанного распределения. Более того, она вычислима для набора сингулярных случайных величин , тогда как d -мерная энтропия там не обязательно существует.

Наконец, смещение размерности обобщает энтропию Шеннона и дифференциальную энтропию , поскольку можно найти взаимную информацию. $I(X;Y)$ используя следующую формулу:

$I(X;Y)=b(X)+b(Y)-b(X,Y).$

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

По теореме Лебега о разложении распределение вероятностей может быть однозначно представлено смесью

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

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

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

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

$d(X)=\rho$

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

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

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

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

Пример

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

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

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

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

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

$d(X)=\rho =0.5$

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

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

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

Это показано что информационное измерение и дифференциальная энтропия тесно связаны.

Позволять $X$ быть случайной величиной с непрерывной плотностью $f(x)$.

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

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

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

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

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

Позволять $S=\operatorname {supp} (P_{X^{\Delta }})$.Энтропия $X^{\Delta }$ является

${\begin{aligned}\mathbb {H} _{0}(X^{\Delta })&=-\sum _{x_{i}\in S}P_{X^{\Delta }}\log _{2}P_{X^{\Delta }}\\&=-\sum _{x_{i}\in S}f(x_{i})\Delta \log _{2}(f(x_{i})\Delta )\\&=-\sum _{x_{i}\in S}\Delta f(x_{i})\log _{2}f(x_{i})-\sum _{x_{i}\in S}f(x_{i})\Delta \log _{2}\Delta \\&=-\sum _{x_{i}\in S}\Delta f(x_{i})\log _{2}f(x_{i})-\log _{2}\Delta \\\end{aligned}}$

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

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

Это дает

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

и когда $m$ достаточно велик,

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

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

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

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

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

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

и

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

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

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

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

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

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

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

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

Так $r(\epsilon )$ в основном дает соотношение между длиной кода и длиной источника, оно показывает, насколько хороша конкретная пара кодера-декодера. Фундаментальные ограничения исходного кодирования без потерь заключаются в следующем.

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

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

Фундаментальная роль информационного измерения в сжатии данных без потерь выходит за рамки данных iid. Показано, что для заданных процессов (например, процессов скользящего среднего) коэффициент сжатия без потерь также равен размерности информации. Этот результат позволяет обеспечить дальнейшее сжатие, которое было невозможно при рассмотрении только предельного распределения процесса.

См. также

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

Ссылки

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

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

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

• Ву, Ихонг; Верду, С. (август 2010 г.). «Информационное измерение Реньи: фундаментальные ограничения аналогового сжатия почти без потерь». Транзакции IEEE по теории информации . 56 (8): 3721–3748. дои : 10.1109/TIT.2010.2050803 . ISSN   0018-9448 . S2CID   206737933 .
• Чарусайе, М.; Амини, А.; Рини, С. (май 2022 г.). «Меры сжимаемости аффинно сингулярных случайных векторов» . Транзакции IEEE по теории информации . 68 (9): 6245–6275. arXiv : 2001.03884 . дои : 10.1109/TIT.2022.3174623 .

• Кавабата, Т.; Дембо, А. (сентябрь 1994 г.). «Измерение скорости-искажения множеств и мер» . Транзакции IEEE по теории информации . 40 (5): 1564–1572. дои : 10.1109/18.333868 .