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

Термин в теории информации

В теории информации информационная размерность — это информационная мера для случайных векторов в евклидовом пространстве , основанная на нормализованной энтропии тонко квантованных версий случайных векторов . Эта концепция была впервые введена Альфредом Реньи в 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 \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}$

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

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

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

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

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

или, что эквивалентно, минимальная информация, которая может привести к близкому приближению к . ${\displaystyle D}$ ${\displaystyle X}$

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

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

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

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

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

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

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

${\displaystyle I(X;Y)=b(X)+b(Y)-b(X,Y).}$

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

Согласно теореме о разложении Лебега ^[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 S=\operatorname {supp} (P_{X^{\Delta }})}$ ${\displaystyle X^{\Delta }}$

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

Если мы устанавливаем и тогда мы делаем точно такое же квантование, как и определение информационного измерения. Поскольку перемаркировка событий дискретной случайной величины не меняет ее энтропию, мы имеем ${\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}$

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

Рассмотрим непрерывную функцию кодера с ее непрерывной функцией декодера . Если мы не накладываем регулярности на и , то из-за богатой структуры мы имеем минимально достижимую скорость для всех . Это означает, что можно построить пару кодер-декодер с бесконечной скоростью сжатия. ${\displaystyle f(x):{\mathbb {R} }^{n}\rightarrow {\mathbb {R} }^{\lfloor Rn\rfloor }}$ ${\displaystyle g(x):{\mathbb {R} }^{\lfloor Rn\rfloor }\rightarrow {\mathbb {R} }^{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}$

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

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

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

Примечания

1. См. Реньи 1959.
2. См. Чынлар 2011.
3. См. Кавер и Томас 2012.
4. См. Ву и Верду 2010.
5. См. Чарусайе, Амини и Рини, 2022 г.

Ссылки

• Чынлар, Эрхан (2011). Вероятность и стохастика . Graduate Texts in Mathematics. Vol. 261. Springer. doi :10.1007/978-0-387-87859-1. ISBN 978-0-387-87858-4.

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

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

• Wu, Yihong; Verdu, S. (август 2010 г.). «Информационное измерение Реньи: фундаментальные пределы почти без потерь аналогового сжатия». IEEE Transactions on Information Theory . 56 (8): 3721–3748. doi :10.1109/TIT.2010.2050803. ISSN  0018-9448. S2CID  206737933.
• Charusaie, M.; Amini, A.; Rini, S. (май 2022 г.). «Меры сжимаемости для аффинно-сингулярных случайных векторов». Труды IEEE по теории информации . 68 (9): 6245–6275. arXiv : 2001.03884 . doi : 10.1109/TIT.2022.3174623 .

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