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

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

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

Пусть . Энтропия IS${\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):\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}$

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

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

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

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

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