Information dimension

In information theory, information dimension is an information measure for random vectors in Euclidean space, based on the normalized entropy of finely quantized versions of the random vectors. This concept was first introduced by Alfréd Rényi in 1959.^[1]

Simply speaking, it is a measure of the fractal dimension of a probability distribution. It characterizes the growth rate of the Shannon entropy given by successively finer discretizations of the space.

In 2010, Wu and Verdú gave an operational characterization of Rényi information dimension as the fundamental limit of almost lossless data compression for analog sources under various regularity constraints of the encoder/decoder.

The entropy of a discrete random variable${\displaystyle Z}$ is

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

where ${\displaystyle P_{Z}(z)}$ is the probability measure of ${\displaystyle Z}$ when ${\displaystyle Z=z}$, and the ${\displaystyle supp(P_{Z})}$ denotes a set ${\displaystyle \{z|z\in {\mathcal {Z}},P_{Z}(z)>0\}}$.

Let ${\displaystyle X}$ be an arbitrary real-valued random variable. Given a positive integer${\displaystyle m}$, we create a new discrete random variable

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

where the ${\displaystyle \lfloor \cdot \rfloor }$ is the floor operator which converts a real number to the greatest integer less than it. Then

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

and

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

are called lower and upper information dimensions of ${\displaystyle X}$ respectively. When ${\displaystyle {\underline {d}}(X)={\bar {d}}(X)}$, we call this value information dimension of ${\displaystyle X}$,

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

Some important properties of information dimension ${\displaystyle d(X)}$:

• If the mild condition ${\displaystyle \mathbb {H} (\lfloor X\rfloor )<\infty }$ is fulfilled, we have ${\displaystyle 0\leq {\underline {d}}(X)\leq {\bar {d}}(X)\leq 1}$.
• For an ${\displaystyle n}$-dimensional random vector ${\displaystyle {\vec {X}}}$, the first property can be generalized to ${\displaystyle 0\leq {\underline {d}}({\vec {X}})\leq {\bar {d}}({\vec {X}})\leq n}$.
• It is sufficient to calculate the upper and lower information dimensions when restricting to the exponential subsequence ${\displaystyle m=2^{l}}$.
• ${\displaystyle {\underline {d}}(X)}$ and ${\displaystyle {\bar {d}}(X)}$ are kept unchanged if rounding or ceiling functions are used in quantization.

If the information dimension ${\displaystyle d}$ exists, one can define the ${\displaystyle d}$-dimensional entropy of this distribution by

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

provided the limit exists. If ${\displaystyle d=0}$, the zero-dimensional entropy equals the standard Shannon entropy${\displaystyle \mathbb {H} _{0}(X)}$. For integer dimension ${\displaystyle d=n\geq 1}$, the ${\displaystyle n}$-dimensional entropy is the ${\displaystyle n}$-fold integral defining the respective differential entropy.

In 1994, Kawabata and Dembo in Kawabata & Dembo 1994 proposed a new way of measuring information based on rate distortion value of a random variable. The measure is defined as

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

where ${\displaystyle R(X,D)}$ is the rate-distortion function that is defined as

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

or equivalently, minimum information that could lead to a ${\displaystyle D}$-close approximation of ${\displaystyle X}$.

كما أثبتوا أن هذا التعريف يعادل تعريف بُعد المعلومات. رسميًا،

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

باستخدام التعريف المذكور أعلاه لبُعد معلومات ريني، تم تعريف مقياس مشابه للإنتروبيا ذات الأبعاد d في دراسة شاروساي، أميني ، وريني 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 }}}$

مثال

لنفترض وجود إشارة لها توزيع احتمالي غاوسي .

نمرر الإشارة عبر مقوم نصف موجة يحول جميع القيم السالبة إلى صفر، ويحافظ على جميع القيم الأخرى. يمكن وصف مقوم نصف الموجة بالدالة التالية:

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

ثم، عند مخرج المقوم، يكون للإشارة توزيع غاوسي مقوم . وتتميز بكتلة ذرية وزنها 0.5 ولها دالة كثافة احتمالية غاوسية لجميع${\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}$يُظهر مفهوم الإنتروبيا ذات الأبعاد n أن الإنتروبيا التفاضلية هي بالضبط الإنتروبيا أحادية البعد.

${\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):{\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}$ Suppose we restrict the decoder to be a Lipschitz continuous function and ${\displaystyle {\bar {d}}(X)<\infty }$ holds, then the minimum ${\displaystyle \epsilon -}$achievable rate ${\displaystyle R(\epsilon )\geq {\bar {d}}(X)}$ for all ${\displaystyle 0<\epsilon \leq 1}$.

The fundamental role of information dimension in lossless data compression further extends beyond the i.i.d. data. It is shown that for specified processes (e.g., moving-average processes) the ratio of lossless compression is also equal to the information dimension rate.^[5] This result allows for further compression that was not possible by considering only marginal distribution of the process.

• Fractal dimension
• Correlation dimension
• Entropy (information theory)

• Çınlar, Erhan (2011). Probability and Stochastics. Graduate Texts in Mathematics. Vol. 261. Springer. doi:10.1007/978-0-387-87859-1. ISBN 978-0-387-87858-4.

• Cover, Thomas M.; Thomas, Joy A. (2012). Elements of Information Theory (2nd ed.). Wiley. pp. 247–248. ISBN 9781118585771.

• Rényi, A. (March 1959). "On the dimension and entropy of probability distributions". Acta Mathematica Academiae Scientiarum Hungaricae. 10 (1–2): 193–215. doi:10.1007/BF02063299. ISSN 0001-5954. S2CID 121006720.

• Wu, Yihong; Verdu, S. (August 2010). "Rényi Information Dimension: Fundamental Limits of Almost Lossless Analog Compression". 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. (May 2022). "Compressibility Measures for Affinely Singular Random Vectors". IEEE Transactions on Information Theory. 68 (9): 6245–6275. arXiv:2001.03884. doi:10.1109/TIT.2022.3174623.

• Kawabata, T.; Dembo, A. (September 1994). "The Rate-Distortion Dimension of Sets and Measures". IEEE Transactions on Information Theory. 40 (5): 1564–1572. doi:10.1109/18.333868.