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

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

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

В 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 = п \ geq 1}$${\ displaystyle n}$${\ displaystyle n}$

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

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

${\ 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 {case} 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 {align} \ 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}} \, {\ текст {бит (ы)}} \ конец {выровнено}}}$

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

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

Позвольте быть случайной величиной с непрерывной плотностью .${\ 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 я \ Дельта \ Leq Икс <(я + 1) \ Дельта}$

Вероятность каждой точки поддержки равна ${\ 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 {align} \ 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 \\\ конец {выровнено}}}$

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

${\ 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}) \ приблизительно \ int f (x) \ log _ {2} {\ frac {1} {f (х)}} \ mathrm {d} x}$

которая является дифференциальной энтропией непрерывной случайной величины. В частности, если она интегрируема по Риману, то ${\ Displaystyle ч (х)}$${\ 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 ^ {п}}$${\ displaystyle f _ {\ vec {X}} ({\ vec {x}})}$${\ displaystyle H_ {0} (\ langle {\ vec {X}} \ rangle _ {m}) <\ infty}$${\ Displaystyle д ({\ vec {X}}) = п}$

а также

${\ 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 (п, к) -}$${\ displaystyle \ {X_ {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 г (\ эпсилон)}$${\ displaystyle r \ geq 0}$${\ Displaystyle (п, \ lfloor rn \ rfloor) -}$${\ displaystyle {\ mathcal {P}} \ {g_ {n} (f_ {n} (X ^ {n})) \ neq X ^ {n} \} \ leq \ epsilon}$${\ displaystyle n}$

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

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

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

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

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