نظرية المعلومات

صنف فرعي من	نظرية رياضية
جزء من	علوم استعرافية — علم الحاسوب — رياضيات

نظرية المعلومات^[1] (بالإنجليزية: Information theory)‏ هي أحد تخصصات وفروع الرياضيات التطبيقية الذي يتضمن كمية Quantification (التحويل إلى كميات) البيانات بهدف تمكين نقل أو تخزين البيانات ضمن وسط ما أو نقلها عبر قناة اتصال ما بأكبر قدر ممكن. قياس المعلومات يعرف عادة بإنتروبية المعلومات وهو عبارة عن العدد الوسطي من البتات (متوسط عدد النبضات الثنائية) اللازم للتخزين أو الاتصال. مثلا، إذا كان وصف الطقس اليومي له إنتروبية بمقدار 3، فهذا يعني انه على مدى عدد كاف من الأيام يمكننا وصف الطقس اليومي بمعدل 3 بتات (نبضات ثنائية) لليوم الواحد.

تطبيقات نظرية المعلومات الأساسية تتضمن: ضغط البيانات غير المنقوص lossless data compression : مثلا زيب (صيغة ملفات) ZIP، ضغط البيانات المنقوص Lossy compression مثل إم.بي.ثري MP3، تشفير قنوات نقل البيانات وسعاتها channel capacity مثل خطوط دي.إس.إل DSL. يقع هذا الفرع عند حدود الرياضيات والإحصاء، وعلوم الحاسب والفيزياء والنيوروبيولوجيا والهندسة الكهربائية. تطبيقاتها كانت أساسية في نجاح مهمات فوياجير الفضائية، واختراع سي.دي CD، وتطبيقات الهاتف المحمول، وتطور الإنترنت. وحتى دراسة اللسانيات والاستشعار الإنساني، وأيضا فهم ظاهرة الثقوب السوداء وغيرها من الحقول والتطبيقات العلمية.

وحدات قياس المعلومات عدل

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

يحدد اختيار قاعدة اللوغاريتم في المعادلة التالية unit اعتلاج (معلومات) المستخدمة. أكثر وحدات القياس شيوعًا هي النبضة الثنائية (البِت) بت، وهي التي تبنى على اللوغاريتم الثنائي لوغاريتم ثنائي. وتتضمن وحدات القياس الأخرى nat, وهي وحدة قائمة على اللوغاريتم الطبيعي لوغارتم طبيعي، و هارتلي, وهي الوحدة القائمة على اللوغاريتم الشائع common logarithm]].

فيما يلي، سوف تُعْتَبَرُ أي صيغة رياضية على الصورة $p\log p\,$ اتفاقًا على أنها تساوي صفرًا $p=0.$ وهذا له ما يبرره نظرًا لأن $\lim _{p\rightarrow 0+}p\log p=0$ لأي قاعدة لوغاريتمية.

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

الإنتروبية الخاصة بمحاولات بيرنولي Bernoulli trial كدالة في احتمال النجاح، وعادة ما يطلق عليها binary entropy function,

H_{\mbox{b}}(p)

. تصل الأنتروبية إلى قيمتها القصوى والتي تبلغ 1 نبضة ثنائية (بت) لكل محاولة حين يكون لكل قيمة من قيمتي الخرج المحتملتين نفس القيمة، كما هو الحال عند إلقاء عملة غير منحازة.

وتعتبر انتروبي، $H$ , الخاصة بمتغير عشوائي غير متصل $X$ مقياسًا لكمية الشك المرتبطة بقيمة $X$ .

لنفرض أن أحد الأشخاص قام بإرسال 1000 نبضة ثنائية (صفر وواحد). إذا كانت هذه النبضات الثنائية معروفة قبل الإرسال (أي معروفة قيمتها بتحديد مطلق)، فإن المنطق يحتِّم أن نقول أنه لم تُرْسَل أية معلومات في هذه الحالة. ولكن، إذا كانت كل نبضة ثنائية مستقلة عن الأخرى وذات احتمال متساوٍ في أن تكون صفر أو واحد، فإننا نقول أنه أُرْسِلَت 1000 نبضة ثنائية (من وجهة نظر نظرية المعلومات). وبين هاتين الحالتين المتباينتين، يمكن تحديد كم المعلومات كما يلي.

إذا كان $\mathbb {X}$ يعبر عن المجموعة التي تضم كل القيم الممكنة التي يمكن أن تأخذها $\{x_{1},...,x_{n}\}$ that $X$ could be, وكان $p(x)$ هو احتمال قيمة ما تسمى $x\in \mathbb {X}$ , فإن الإنتروبية ويرمز لها بالرمز، $H$ , of $X$ تعرّف على أنها:^[2]

H(X)=\mathbb {E} _{X}[I(x)]=-\sum _{x\in \mathbb {X} }p(x)\log p(x).

وهنا، يرمز الرمز $I(x)$ إلى المضمون المعلومي، وهي مدى إسهام كل رسالة منفصلة في الإنتروبية، ويرمز الرمز $\mathbb {E} _{X}$ إلى القيمة المتوقعة قيمة متوقعة.) أحد الخصائص الهامة للإنتروبية هي أنها تبلغ الحد الأقصى حين تكون كل الرسائل المتاحة في مجال الرسائل متساوية الاحتمال $p(x)=1/n$ ,—أي أنها يصعب التنبؤ بها إلى أقصى درجة — وفي هذه الحالة يكون $H(X)=\log n$ .

الحالة الخاصة لإنتروبية المعلومات التي تمثل متغير عشوائي ثنائي هي binary entropy function, وهي عادة ما تكون محسوبة بالنسبة لأساس اللوغاريتم 2:

H_{\mathrm {b} }(p)=-p\log _{2}p-(1-p)\log _{2}(1-p).\,

ومن المهم أن نلاحظ هنا أن قيمة الإنتروبية (كما هو موضح في الشكل، تكون صفرًا عندما تكون قيمة المتغير العشوائي معروفة بدون أدنى شك. وهو ما يناظر الحالة التي تكون فيها $p=1$ أو $p=0$ إذ أن المتغير لا يحمل أي معلومات في هذه الحالة. ولكي نفهم ذلك، فكِّر في كم المعلومات التي تحصل عليها عندما يخبرك أحد الأشخاص بحقيقة كونية ثابتة، مثل: «الشمس تشرق من الشرق». إذ أن احتمال حدوث ذلك هو احتمال مؤكد وبالتالي لا تحصل على أي معلومة. وسوف يأتي الحديث إلى مسألة «ضغط البيانات» والتي نحاول فيها الوصول إلى أقل حجم لتمثيل بيانات عشوائية. وسوف نعرف حينئذ أن قيمة الإنتروبية هي أقل قيمة يمكن تمثيل المتغير العشوائي بها. في المثال الموجود أعلاه، والذي يفترض إرسال 1000 نبضة ثنائية من متغير عشوائي، وبفرض أن يأخذ المتغير العشوائي قيمة "1" هي 0.1 فإن الشكل يبين أن قيمة الإنتروبية حوالي 0.5 نبضة ثنائية (بِت). وبالتالي فإن نظرية المعلومات تخبرنا أن 1000 نبضة ثنائية مولّدة من هذا المتغير يمكن التعبير عنها بـ 500 نبضة فقط. وهذا العلم هو الذي يعرف باسم "ترميز المصدر" (Source Coding) أي اختيار أنسب مجموعة من الرموز يمكنها تمثيل مخرجات المتغير العشوائي/المصدر بأقل قدر من النبضات الثنائية.

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

تعبِّر الإنتروبية المشتركة لمتغيرين عشوائيين متقطعين $X$ و $Y$ عن الإنتروبية الخاصة بهما معًا عندما يكونان زوجًا: $(X,Y)$ . ويعني هذا ضمنيًا أنه إذا كان المتغيران $X$ و $Y$ مستقلان إحصائيًا أي استقلال (نظرية الاحتمال), فإن الإنتروبية المشتركة لهما لن تعدو أن تكون مجموع إنتروبية كل منهما. ولكن القيمة الحقيقية للإنتروبية المشتركة تظهر في حالة المتغيرات العشوائية المترابطة. فعلى سبيل المثال، إذا كان المتغيران $X$ و $Y$ يعبران عن درجة الحرارة في مكانٍ ما ومعدل الإصابة بضربات الشمس في نفس المكان، فإننا نتوقع أن يكون المتغيران مرتبطان، وبالتالي فإن مقياس كم المعلومات الموجود فيهما معًا (الإنتروبية المشتركة) يكون أقل من مجموعهما، نظرًا لأن هناك جزء من المعلومات التي نتعلمها من المتغير العشوائي الأول يمكن أن تفيدنا في معرفة شيء ما عن المتغير العشوائي الثاني والعكس بالعكس.

مثال آخر، إذا كان $(X,Y)$ يمثلان موقع قطعة شطرنج — حيث يمثل $X$ الصف ويمثل $Y$ العمود، فإن الإنتروبية المشتركة للإثنين معًا هي الإنتروبية التي تعبر عن مكان القطعة على لوحة الشطرنج. وبتطبيق نفس تعريف الإنتروبية على احتمالات المتغيرين العشوائيين معًا فإن الإنتروبية المشتركة يمكن حسابها من العلاقة:

H(X,Y)=\mathbb {E} _{X,Y}[-\log p(x,y)]=-\sum _{x,y}p(x,y)\log p(x,y)\,

وعلى الرغم من تشابه الرمز المعبر عن الإنتروبية المشتركة مع الرمز المعبِّر عن، الإنتروبية المتقاطعة cross entropy إلا أنه ينبغي ألا نخلط بينهما.

وقبل أن نستكمل الحديث عن كميات قياس المعلومات، لابد من التنويه عن أن الترابط بين متغيرين عشوائيين يجعل الإنتروبية المشتركة لهما أقل من مجموع الإنتروبية الخاصة بكلٍ منهما على حدة. إذ كلما زاد الترابط بين المتغيرين كانت معرفة أحدهما تُغنى عن معرفة الآخر.

ولفهم هذا المبدأ دعونا ننظر إلى الحالتين المتناقضتين: الأولى إذا كان المتغيران العشوائيان متطابقين، كأن يكون كلٌ من $X$ و $Y$ متساويين، من البديهى في هذه الحالة أن المعلومات (الإنتروبية) المشتركة (المتضمنة في المتغيرين معًا) لا تزيد عن المعلومات المتضمنة في واحدٍ فقط منهما. وعلى النقيض في الحالة الثانية، إذا كان المتغيران لا توجد بينهما أية علاقة، فإن المعلومات التي يحملانها معًا (الإنتروبية المشتركة لهما) تساوى مجموع المعلومات في $X$ والمعلومات في $Y$ وهي الإنتروبية الخاصة بكل منهما.

المعلومات المتبادلة (المعلومات المنقولة) عدل

تقيس المعلومات المتبادلة (Mutual Information) كم المعلومات التي يمكن الحصول عليها من متغير عشوائي (مصدر معلومات) من خلال ملاحظة متغير عشوائي (مصدر معلومات) آخر. وهي من الكميات الهامة في أنظمة الاتصالات حيث يساعد فهم مقدار المعلومات المتبادلة في زيادة كم المعلومات المتبادل بين الإشارات المرسلة والإشارات المستقبلة (كما سيأتي تفصيله فيما بعد). وتقاس كمية المعلومات المتبادلة بين متغير عشوائي $X$ ومتغير عشوائي آخر $Y$ طبقًا للمعادلة:

I(X;Y)=\sum _{x,y}p(x,y)\log {\frac {p(x,y)}{p(x)\,p(y)}}

وقبل أن نبدأ في سرد خواص المعلومات المتبادلة، يجب التنويه إلى معنى هذه القيمة وعلاقتها بالإنتروبية المشتركة التي سبق الحديث عنها: حيث أن حاصل طرح: مجموع المعلومات في كلٍ $X$ و $Y$ (وهو المجموع الذي يعبر عن $H(X)$ زائد $H(Y)$ أي قدر المعلومات التي يحويها كلاهما إذا افترضنا عدم وجود ارتباط بينهما)، ناقص الإنتروبية المشتركة (وهي تعبر عن إجمالي المعلومات التي يعبر عنها $X$ و $Y$ معًا) يعطينا المعلومات المعلومات المتبادلة (وهي المعلومات التي يعطيها أحدهما- وليكن $X$ - عن الآخر وليكن $Y$ ). ونعبر عن هذا بالمعادلة الرياضية

$I(X;Y)=H(X)+H(Y)-H(X,Y)$ ، والتي تكافئ تعريف الإنتروبية المشتركة $H(X;Y)=H(X)+H(Y)-I(X,Y)$ ،

ولمزيد من التوضيح إذا طرحنا المعلومات المتبادلة $I(X;Y)$ من المعلومات التي يحتويها المتغير العشوائي $Y$ فإن هذا يعطينا كم المعلومات المتبقي (أي الغير معروف بعد) في $X$ بعد معرفة $Y$ بالكامل. وهي كمية أخرى سيأتي الحديث عنها باسم الإنتروبية المشروطة (Conditional Entropy) ويرمز لها بالرمز $H(X|Y)$ .

ومن الخصائص الأساسية للمعلومات المتبادلة أن: $I(X;Y)=H(X)-H(X|Y)$ ، وتفسير هذه المعادلة، أنه بمعرفة، Y, يمكننا توفير كم من النبضات الثنائية (بِت) يساوي في المتوسط $I(X;Y)$ عند ترميز المتغير العشوائي $X$ بالمقارنة بما يحتاجه هذا الترميز إذا لم يكن المتغير $Y$ معروفًا.

وهو ما يعني ببساطة أن المعلومات التي أعطاها لنا $Y$ عن $X$ تمثل الفرق بين ما كنّا نجهله عن $X$ قبل وبعد معرفة $Y$ .

المعلومات المتبادلة symmetric:

I(X;Y)=I(Y;X)=H(X)+H(Y)-H(X,Y).\,

أي أن المعلومات التي يحملها كل من المتغيرين العشوائيين عن الآخر متساوية.

ولمزيد من التوضيح لأهمية هذه الكمية وتطبيقاتها: دعونا نتخيل أن $X$ يعبر عن البيانات المرسلة عبر قناة اتصال، بينما يعبر $Y$ عن البيانات الخارجة (المستقبلة) منها. في هذه الحالة، فإن الاختلاف بين $X$ و $Y$ يعود إلى ما تتعرض له الإشارات من تداخل وشوشرة عبر قنوات الاتصال. وتعبر المعلومات المتبادلة عن كم المعلومات التي يحتويها $X$ والتي أمكن تمريرها عبر القناة. ومن هنا، يكون من الطبيعي وجود علاقة بين سعة قناة الاتصال وبين المعلومات المتبادلة بين طرفيها. وهو ما يعرف باسم سعة القناة. وببساطة شديدة، ونظرًا لاعتماد المعلومات المتبادلة على إنتروبية المتغير العشوائي $X$ ، تكون سعة القناة هي أقصى قيمة يمكن أن تأخذها المعلومات المتبادلة مع جميع المتغيرات العشوائية الممكنة. ولعل معرفة سعة القناة هو أحد أكبر إنجازات نظرية المعلومات في مجال الاتصالات، حيث تمثل هذه السعة الحد الأقصى لما يمكن أن تحققه أنظمة الاتصالات بغض النظر عن أسلوب عملها، وقد أمكن الربط بين هذه السعة وبين خصائص كود تصحيح الخطأ.