عدم المساواة في نظرية المعلومات

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
📷 يحتوي على 42 صور
الموسوعة الحرة

تُعدّ المتباينات ذات أهمية بالغة في دراسة نظرية المعلومات . وتظهر هذه المتباينات في عدد من السياقات المختلفة.

عدم المساواة الإنتروبية

لنفترض وجود مجموعة من العناصرX1،X2،...،Xن{\displaystyle X_{1},X_{2},\dots ,X_{n}}لن{\displaystyle n}المتغيرات العشوائية ذات الدعم المحدود (أو على الأكثر القابل للعد) على نفس فضاء الاحتمال . يوجد 2^ n مجموعة جزئية، يمكن حساب الإنتروبيا ( المشتركة ) لها . على سبيل المثال، عندما n  =  2، يمكننا النظر في الإنتروبياح(X1)،{\displaystyle H(X_{1}),}ح(X2)،{\displaystyle H(X_{2}),}وح(X1،X2){\displaystyle H(X_{1},X_{2})}. وهي تحقق المتباينات التالية (التي تحدد مجتمعة نطاق الإنتروبيا الهامشية والمشتركة لمتغيرين عشوائيين):

  • ح(X1)≥0{\displaystyle H(X_{1})\geq 0}
  • ح(X2)≥0{\displaystyle H(X_{2})\geq 0}
  • ح(X1)≤ح(X1،X2){\displaystyle H(X_{1})\leq H(X_{1},X_{2})}
  • ح(X2)≤ح(X1،X2){\displaystyle H(X_{2})\leq H(X_{1},X_{2})}
  • ح(X1،X2)≤ح(X1)+ح(X2).{\displaystyle H(X_{1},X_{2})\leq H(X_{1})+H(X_{2}).}

في الواقع، يمكن التعبير عن كل هذه الحالات كحالات خاصة من متباينة واحدة تتضمن المعلومات المتبادلة الشرطية ، وهي:

أنا(أ؛ب|ج)≥0،{\displaystyle I(A;B|C)\geq 0,}

أينأ{\displaystyle A}،ب{\displaystyle B}، وج{\displaystyle C}يمثل كل منها التوزيع المشترك لمجموعة فرعية عشوائية (قد تكون فارغة) من مجموعتنا من المتغيرات العشوائية. تُعرف المتباينات التي يمكن اشتقاقها كتركيبات خطية من هذا التوزيع باسم متباينات شانون .

للأكبر حجمان{\displaystyle n}توجد قيود إضافية على القيم الممكنة للإنتروبيا. ولتوضيح ذلك بدقة، يُستخدم متجهح{\displaystyle h}فيR2ن{\displaystyle \mathbb {R} ^{2^{n}}}مفهرسة بواسطة مجموعات فرعية من{1،...،ن}{\displaystyle \{1,\dots ,n\}}يُقال إن النظام إنتروبي إذا كان هناك توزيع مشترك ومنفصل لـ n من المتغيرات العشوائيةX1،...،Xن{\displaystyle X_{1},\dots ,X_{n}}بحيثحأنا=ح(Xأنا:أنا∈أنا){\displaystyle h_{I}=H(X_{i}\colon i\in I)}يمثل الإنتروبيا المشتركة لكل مجموعة جزئيةأنا{\displaystyle I}يُرمز إلى مجموعة المتجهات الانتروبية بـΓن*{\displaystyle \Gamma _{n}^{*}}، وفقًا لترميز يونغ. [ 1 ] إنها ليست مغلقة ولا محدبة لـن≥3{\displaystyle n\geq 3}، لكن إغلاقها الطوبولوجيΓن*¯{\displaystyle {\overline {\Gamma _{n}^{*}}}}من المعروف أنها محدبة، وبالتالي يمكن وصفها بالمتباينات الخطية (التي لا حصر لها) التي تحققها جميع المتجهات الانتروبية، والتي تسمى المتباينات الانتروبية .

تحتوي مجموعة جميع المتجهات التي تحقق متباينات من نوع شانون (ولكن ليس بالضرورة متباينات إنتروبية أخرى)Γن*¯{\displaystyle {\overline {\Gamma _{n}^{*}}}}هذا الاحتواء صارم لـن≥4{\displaystyle n\geq 4}وتُعرف المزيد من المتباينات باسم متباينات غير شانون . وقد أبلغ تشانغ ويونغ عن أول متباينة غير شانون، [ 2 ] والتي يُشار إليها غالبًا باسم متباينة تشانغ-يونغ. أثبت ماتوس [ 3 ] أنه لا توجد مجموعة منتهية من المتباينات يمكنها أن تُحدد (بالتركيبات الخطية) جميع المتباينات الإنتروبية. بعبارة أخرى، المنطقةΓن*¯{\displaystyle {\overline {\Gamma _{n}^{*}}}}ليس متعدد الأوجه .

الحدود الدنيا لتباعد كولباك-لايبير

العديد من المتباينات المهمة في نظرية المعلومات هي في الواقع حدود دنيا لتباعد كولباك-لايبير . حتى متباينات شانون يمكن اعتبارها جزءًا من هذه الفئة، حيث يمكن التعبير عن معلومات التفاعل على أنها تباعد كولباك-لايبير للتوزيع المشترك بالنسبة لحاصل ضرب التوزيعات الهامشية، وبالتالي يمكن اعتبار هذه المتباينات حالة خاصة من متباينة جيبس .

من جهة أخرى، يبدو من الصعب للغاية استنباط حدود عليا مفيدة لتباعد كولباك-لايبير. ويعود ذلك إلى أن تباعد كولباك-لايبير D KL ( P || Q ) يعتمد بشكل كبير على الأحداث النادرة جدًا في التوزيع المرجعي Q. يزداد D KL ( P || Q ) بلا حدود عندما يصبح حدث ذو احتمال غير صفري محدود في التوزيع P نادرًا للغاية في التوزيع المرجعي Q ، بل إن D KL ( P || Q ) غير مُعرَّف أصلًا إذا كان احتمال حدث ذي احتمال غير صفري في P يساوي صفرًا في Q. (ومن هنا يأتي شرط أن يكون P متصلًا اتصالًا مطلقًا بالنسبة إلى Q ).

عدم المساواة عند جيبس

تنص هذه المتباينة الأساسية على أن تباعد كولباك-لايبير غير سالب.

عدم المساواة لكولباك

تُعرف متباينة أخرى تتعلق بتباعد كولباك-لايبير باسم متباينة كولباك . [ 4 ] إذا كان P و Q توزيعين احتماليين على خط الأعداد الحقيقية، حيث P متصلة اتصالاً مطلقاً بالنسبة إلى Q، ولحظاتهما الأولى موجودة، فإن

دكل(P∥سؤال)≥Ψسؤال*(μ1′(P))،{\displaystyle D_{KL}(P\parallel Q)\geq \Psi _{Q}^{*}(\mu '_{1}(P)),}

أينΨسؤال*{\displaystyle \Psi _{Q}^{*}}هي دالة معدل الانحرافات الكبيرة ، أي المرافق المحدب لدالة توليد العزوم التراكمية ، لـ Q ، وμ1′(P){\displaystyle \mu '_{1}(P)}هي اللحظة الأولى لـ P.

يُعد حد كرامر -راو نتيجة طبيعية لهذه النتيجة.

عدم المساواة عند بينسكر

تربط متباينة بينسكر بين تباعد كولباك-لايبير ومسافة التباين الكلي . وتنص على أنه إذا كان P و Q توزيعين احتماليين ، فإن

12دكل(هـ)(P∥سؤال)≥رشفة{|P(أ)-سؤال(أ)|:أ هو حدث يتم تخصيص احتمالات له.}.{\displaystyle {\sqrt {{\frac {1}{2}}D_{KL}^{(e)}(P\parallel Q)}}\geq \sup\{|P(A)-Q(A)|:A{\text{ هو حدث تُسند إليه احتمالات.}}\}.}

أين

دكل(هـ)(P∥سؤال){\displaystyle D_{KL}^{(e)}(P\parallel Q)}

هل تباين كولباك - لايبير في النتائج الطبيعية هو

رشفةأ|P(أ)-سؤال(أ)|{\displaystyle \sup _{A}|P(A)-Q(A)|}

هي مسافة التباين الكلية.

أوجه عدم المساواة الأخرى

عدم اليقين لدى هيرشمان

في عام 1957، [ 5 ] أثبت هيرشمان أنه بالنسبة لدالة (ذات سلوك جيد إلى حد معقول)و:R→ج{\displaystyle f:\mathbb {R} \rightarrow \mathbb {C} }بحيث∫-∞∞|و(x)|2دx=1،{\displaystyle \int _{-\infty }^{\infty }|f(x)|^{2}\,dx=1,}وتحويل فورييه الخاص بهز(y)=∫-∞∞و(x)هـ-2πأناxyدx،{\displaystyle g(y)=\int _{-\infty }^{\infty }f(x)e^{-2\pi ixy}\,dx,}مجموع الإنتروبيا التفاضلية لـ|و|2{\displaystyle |f|^{2}}و|ز|2{\displaystyle |g|^{2}}غير سالب، أي

-∫-∞∞|و(x)|2سجل⁡|و(x)|2دx-∫-∞∞|ز(y)|2سجل⁡|ز(y)|2دy≥0.{\displaystyle -\int _{-\infty }^{\infty }|f(x)|^{2}\log |f(x)|^{2}\,dx-\int _{-\infty }^{\infty }|g(y)|^{2}\log |g(y)|^{2}\,dy\geq 0.}

افترض هيرشمان، وثبت لاحقًا، [ 6 ] أن حدًا أكثر دقة لـسجل⁡(هـ/2)،{\displaystyle \log(e/2),}يمكن استبدال الطرف الأيمن من هذه المتباينة بالقيمة التي يتم الحصول عليها في حالة التوزيع الغاوسي . وهذا أمر بالغ الأهمية لأنه يستلزم صياغة فايل لمبدأ هايزنبرغ للشك ، وهو أقوى منها .

عدم المساواة عند تاو

بالنظر إلى المتغيرات العشوائية المنفصلةX{\displaystyle X}،Y{\displaystyle Y}، وY′{\displaystyle Y'}بحيثX{\displaystyle X}تأخذ قيمًا فقط في الفترة [ -1 ،  1] و Y′{\displaystyle Y'}يتم تحديده بواسطةY{\displaystyle Y}(بحيثح(Y′|Y)=0{\displaystyle H(Y'|Y)=0}لدينا [ 7 ] [ 8 ]

هـ⁡(|هـ⁡(X|Y′)-هـ⁡(X|Y)|)≤أنا(X؛Y|Y′)2سجل⁡2،{\displaystyle \operatorname {E} {\big (}{\big |}\operatorname {E} (X|Y')-\operatorname {E} (X\mid Y){\big |}{\big )}\leq {\sqrt {I(X;Y\mid Y')\,2\log 2}},}

يربط هذا بين التوقع الشرطي والمعلومات المتبادلة الشرطية . وهذه نتيجة مباشرة لمتباينة بينسكر . (ملاحظة: يظهر عامل التصحيح log  2 داخل الجذر لأننا نقيس المعلومات المتبادلة الشرطية بالبتات وليس بالنات ).

مدقق آلي لإثبات المتباينات النظرية للمعلومات

تتوفر الآن العديد من خوارزميات التحقق الآلي من صحة البراهين. تتحقق هذه الخوارزميات عادةً من صحة أو خطأ المتباينات. ويمكن لخوارزميات التحقق الأكثر تطورًا إنتاج براهين أو أمثلة مضادة. [ 9 ] ويمكن التحقق من صحة المتباينات المتعلقة بنظرية المعلومات الكمومية باستخدام طريقة إثبات خريطة الانكماش. [ 10 ]

انظر أيضاً

مراجع

  1. ↑ يونغ، ر. و. (1997). "إطار عمل لمتباينات المعلومات الخطية". معاملات IEEE في نظرية المعلومات . 43 (6): 1924-1934 . doi : 10.1109/18.641556 .)
  2. ↑ تشانغ، ز.؛ يونغ، ر. و. (1998). "حول توصيف دالة الإنتروبيا عبر متباينات المعلومات". معاملات IEEE في نظرية المعلومات . 44 (4): 1440-1452 . doi : 10.1109/18.681320 .
  3. ↑ ماتوس، ف. (2007). عدد لا نهائي من متباينات المعلومات . ندوة IEEE الدولية لنظرية المعلومات لعام 2007.
  4. ^ فوكس، إيمي؛ ليتا، جورجيو (1970). "L'Inégalité de KULLBACK. تطبيق على نظرية التقدير". ندوة الاحتمالات الرابعة جامعة ستراسبورغ . ملاحظات محاضرة في الرياضيات. المجلد. 124. ستراسبورغ. ص 108 – 131. دوى : 10.1007 / bfb0059338 . رقم ISBN   978-3-540-04913-5MR 0267669 .​ {{cite book}}: CS1 maint: موقع الناشر مفقود ( رابط )
  5. ↑ هيرشمان، الثاني (1957). "ملاحظة حول الإنتروبيا". المجلة الأمريكية للرياضيات . 79 (1): 152-156 . doi : 10.2307/2372390 . JSTOR 2372390 . 
  6. ↑ بيكنر، و. (1975). "المتباينات في تحليل فورييه". حوليات الرياضيات . 102 (6): 159-182 . doi : 10.2307/1970980 . JSTOR 1970980 . 
  7. ↑ تاو، ت. (2006). "إعادة النظر في مبرهنة سيميريدي للانتظام". مساهمات في الرياضيات المتقطعة . 1 : 8-28 . arXiv : math/0504472 . Bibcode : 2005math......4472T .
  8. ↑ أهلسويد، رودولف (2007). "الصيغة النهائية لمتباينة تاو التي تربط بين التوقع الشرطي والمعلومات المتبادلة الشرطية" . التقدم في رياضيات الاتصالات . 1 (2): 239-242 . doi : 10.3934/amc.2007.1.239 .
  9. ↑ هو، إس دبليو؛ لينغ، إل؛ تان، سي دبليو؛ يونغ، آر دبليو (2020). "إثبات ودحض متباينات المعلومات: النظرية والخوارزميات القابلة للتطوير". معاملات IEEE في نظرية المعلومات . 66 (9): 5525-5536 . doi : 10.1109/TIT.2020.2982642 . S2CID 216530139 . 
  10. ↑ باو، ن؛ ناسكار، ج؛، "خصائص خريطة الانكماش لمتباينات إنتروبيا التشابك الهولوغرافي"، مجلة فيزياء الطاقة العالية 06(2024)، 3، DOI: https://doi.org/10.1007/JHEP06(2024)039 ، 07 يونيو 2024.
  • توماس إم. كوفر، جوي أ. توماس. عناصر نظرية المعلومات ، الفصل 16، "المتباينات في نظرية المعلومات". جون وايلي وأولاده، 1991. رقم ISBN المطبوع. 0-471-06259-6رقم ISBN الإلكتروني 0-471-20061-1
  • أمير ديمبو، توماس إم. كوفر، جوي أ. توماس. متباينات نظرية المعلومات. معاملات IEEE في نظرية المعلومات، المجلد 37، العدد 6، نوفمبر 1991. pdf
  • موقع ITIP: http://user-www.ie.cuhk.edu.hk/~ITIP/ مؤرشف بتاريخ 7 أغسطس 2008 على موقع Wayback Machine
  • XITIP: http://xitip.epfl.ch
  • إن آر باي، سوهاس ديغافي، تي غلاسلي، إي بيرون، آر. بوليكوناتو، آر دبليو يونغ، واي يان، أوكسيتيب: إثبات عدم المساواة النظرية للمعلومات عبر الإنترنت http://www.oxitip.com
  • سيو واي هو، ولين لينغ، وتشي وي تان، وريموند دبليو يونغ، AITIP (إثبات عدم المساواة النظرية في المعلومات): https://aitip.org
  • نيفيديتا ريثناكار، سوهاس ديغافي، ريموند دبليو يونغ، InformationInequalities.jl: استكشاف المتباينات النظرية للمعلومات، حزمة جوليا، 2021