الإنتروبيا والمعلومات

يبدو سؤال «ما مقدار لايقيني؟» سؤالاً عن شعور. وليس كذلك. فله جواب عددي دقيق مقيس بالبتّات، ويتبيّن أن ذلك الجواب هو الكمية التي تحدّد كيف تنقسم شجرة القرار وعلى أي خسارة يُدرَّب المصنِّف. وكلاهما ينبع من تعريف واحد.

أ. قياس المفاجأة بالبتّات

لنبدأ بالحدس. العملة التي نعلم أنها تسقط على «صورة» دائماً لا تحمل لايقيناً: فرصدها لا يخبرك بشيء لم تكن تعرفه. والعملة المتوازنة أقصى ما تكون لايقيناً بين خيارين. أما العملة التي تسقط على صورة 99٪ من الوقت فأقرب كثيراً إلى الحالة الأولى منها إلى الثانية - خمّن «صورة» فلن تخطئ إلا 1٪ من الوقت.

نريد مقياساً يساوي $0$ للعملة اليقينية، ويبلغ أقصاه للمتوازنة، ويصغر لعملة الـ99٪. وباتّباع راسل ونورفيغ، تكون إنتروبيا متغيّر عشوائي $V$ يأخذ القيم $v_k$ بالاحتمالات $P(v_k)$ هي

$$H(V) = \sum_{k} P(v_k) \log_2 \frac{1}{P(v_k)} = -\sum_{k} P(v_k) \log_2 P(v_k) .$$

والصورة الأولى أدلّ. فالكمية $\log_2 \frac{1}{P(v_k)}$ هي مفاجأة النتيجة $k$: كبيرة حين تكون النتيجة غير مرجّحة، وصفر حين تكون يقينية. والإنتروبيا ببساطة المفاجأة المتوقَّعة - كل مفاجأة مرجّحة بمدى تكرارها الفعلي.

لماذا الأساس 2. الوحدة هي البت، والأساس 2 يجعل ذلك حرفياً: فالإنتروبيا هي متوسط عدد أسئلة نعم/لا اللازمة لتحديد النتيجة. ورمية عملة متوازنة تحتاج سؤالاً واحداً، فينبغي أن تقيس $1$ بت بالضبط. وهي كذلك:

$$H(\text{Fair}) = -\big(0.5 \log_2 0.5 + 0.5 \log_2 0.5\big) = 1 .$$

وللنرد الرباعي المتوازن أربع نتائج متساوية الترجيح، وهو ما يحتاج سؤالين: $H = 2$ بت. وتتصرّف العملة المغشوشة كما اقتضى الحدس:

$$H(\text{Loaded}) = -\big(0.99 \log_2 0.99 + 0.01 \log_2 0.01\big) \approx 0.08 \text{ bits}.$$

وللمتغيّر البولياني يريحنا أن نكتب $B(q)$ لإنتروبيا شيء صادق باحتمال $q$:

$$B(q) = -\big(q \log_2 q + (1-q) \log_2 (1-q)\big).$$

متناظرة حول $q = 0.5$، وأقصى ما تكون هناك، وصفر عند اليقين - وهو الشكل الذي طلبناه بالضبط. (واصطلاحاً $0 \log 0 = 0$، وهو أيضاً نهايتها.)

ب. مكسب المعلومات: كم يخبرك السؤال

تصير الإنتروبيا نافعة لحظة أن تسأل ماذا يشتري لك الاختبار. لنفترض أن مجموعة تدريب فيها $p$ مثالاً موجباً و$n$ مثالاً سالباً. فإنتروبيتها $B\!\left(\frac{p}{p+n}\right)$.

والآن اختبر سمةً $A$ لها $d$ قيمة، فتقسم المجموعة إلى مجموعات جزئية $E_1, \dots, E_d$، حيث تحوي $E_k$ عدد $p_k$ موجباً و$n_k$ سالباً. والنزول في الفرع $k$ يترك $B\!\left(\frac{p_k}{p_k+n_k}\right)$ بتّاً باقية للحسم، ويسلك مثال عشوائي ذلك الفرع باحتمال $\frac{p_k+n_k}{p+n}$. ومن ثم تكون الإنتروبيا المتوقّعة المتبقّية بعد الاختبار

$$\text{Remainder}(A) = \sum_{k=1}^{d} \frac{p_k + n_k}{p + n}\, B\!\left(\frac{p_k}{p_k + n_k}\right),$$

ومكسب المعلومات هو الانخفاض المتوقّع في الإنتروبيا:

$$\text{Gain}(A) = B\!\left(\frac{p}{p+n}\right) - \text{Remainder}(A).$$

مثال محلول. اثنا عشر مثالاً، ستة موجبة وستة سالبة، فالإنتروبيا الابتدائية $B(0.5) = 1$ بت بالضبط. وتقسمها سمةٌ إلى فرع من 5 (4 موجبة، 1 سالب) وفرع من 7 (2 موجبة، 5 سالبة).

إنتروبيتا الفرعين: $B(4/5) = B(0.8) = 0.7219$ و$B(2/7) = B(0.2857) = 0.8631$.

والأوزان: $5/12 = 0.4167$ و$7/12 = 0.5833$.

$$\text{Remainder} = 0.4167 \times 0.7219 + 0.5833 \times 0.8631 = 0.8043 ,$$ $$\text{Gain} = 1.0000 - 0.8043 = 0.1957 \text{ bits}.$$

فهذه السمة تحسم نحو خُمس بت من البت الواحد من اللايقين الذي بدأنا به - تحسّن حقيقي لكنه متواضع.

المكسب القريب من الصفر يشي بسمة غير ذات صلة. فإن قسم اختبارٌ البيانات إلى مجموعات جزئية تبدو نِسَب فئاتها كلها كنِسَب الأم، فهو لم يخبرك بشيء، ويعيد الحساب أعلاه صفراً تقريباً. وهذا يجعل مكسب المعلومات إشارة صالحة للتشذيب كما هو صالح للقسمة.

يطبّق الشكل أدناه الحساب نفسه على قسمة أخرى: بيانات المطعم عند Russell وNorvig، وهي أيضًا اثنا عشر مثالًا ستة منها موجبة وستة سالبة، مع صفتين من صفاتها. فالصفة Patrons تكسب $0.5409$ بتّ، والصفة Type تكسب $0$ بالضبط، وهي الصفة غير ذات الصلة التي ذكرتها الملاحظة أعلاه. وكل فرع مرسوم شريطًا وكل رقم محسوب من جديد لا منقولًا. وأداة التحكّم الثالثة تنقل أمثلة داخل فرع Patrons الوحيد الذي ما زال مختلطًا، وهو الموضع الوحيد الذي يمكن أن يتغيّر فيه المكسب دون تغيير السؤال، وتُظهر ما لا تُظهره قسمة واحدة محسوبة باليد: فالإنتروبيا المتوقّعة الباقية أكبر ما تكون حين يتوازن ذلك الفرع، بينما لا يكون المكسب أصغر ما يكون هناك، لأن نقل مثال يغيّر أيضًا الإنتروبيا التي بدأ منها القسم.

ج. مطبّ اصطلاحي يستحق التسمية

تعرض مقالة أشجار القرار والتجميعات معيار القسمة

$$D = -\sum_{k=1}^{K} \hat p_{mk} \log \hat p_{mk}$$

وتسمّيه إنتروبيا متقاطعة، اتّباعاً لاصطلاح التعلّم الإحصائي. وقراءةً على ضوء هذه المقالة، تلك هي صيغة الإنتروبيا - توزيع واحد يُقيَّم مقابل نفسه.

أما نظرية المعلومات فتحجز الإنتروبيا المتقاطعة لكمية تشمل توزيعين. والاسمان معياريان كلٌّ في أدبياته، ولا خطأ في أيّهما، لكنهما ليسا الشيء نفسه، ويسبّب التصادم التباساً حقيقياً. فحين تصادف «الإنتروبيا المتقاطعة» معياراً لقسمة الأشجار، اقرأها إنتروبيا عقدة؛ والقسم التالي عن الشيء الآخر.

د. الإنتروبيا المتقاطعة وتباعد كولباك-لايبلر

لنفترض أن الحقيقة $p$ لكنك تتصرّف باعتقاد $q$. تقيس الإنتروبيا المتقاطعة متوسط المفاجأة التي تتكبّدها فعلاً:

$$H(p, q) = -\sum_{i} p(x_i) \log_2 q(x_i) .$$

فالأوزان هي الاحتمالات الحقيقية $p$؛ والمفاجآت محسوبة من اعتقادك $q$. فإن كان $q = p$ انهارت إلى $H(p)$. وإلا فهي أكبر تماماً - أي أنك مفاجأ منهجياً أكثر مما يلزم.

وللفائض اسمه. فـتباعد KL بين $P$ و$Q$ هو

$$\text{KL}(P, Q) = \sum_{i} P(x_i) \log_2 \frac{P(x_i)}{Q(x_i)} ,$$

وترتبط الكميات الثلاث بـ

$$H(p, q) = H(p) + \text{KL}(p \,\|\, q).$$

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

تحقّق عددياً. لتكن الحقيقة عملة متوازنة، $p = (0.5, 0.5)$، بينما تعتقد أنت $q = (0.9, 0.1)$:

$$H(p) = 1.0000, \qquad H(p, q) = 1.7370, \qquad \text{KL}(p \,\|\, q) = 0.7370 .$$

و$1.0000 + 0.7370 = 1.7370$، كما ادُّعي.

KL ليست مسافة. فهي ليست متناظرة - إذ $\text{KL}(P, Q) \neq \text{KL}(Q, P)$ عموماً - ولا تحقّق متباينة المثلث. وتسميتها «تباعداً» لا مسافة تسمية مقصودة. ولاحظ أيضاً أنها تنفجر إذا كان $q(x) = 0$ حيث $p(x) > 0$: فإسناد احتمال صفري لشيء ثم وقوعه مفاجأة لا نهائية.

في ما يلي، المصدر ثابت والنموذج بين يديك. راقب أيّ القراءتين يأبى أن يتزحزح: فالإنتروبيا خاصّية للمصدر، ولا يمسّها أي ضبط للمؤشّرات. وكل ما يعلو تلك الأرضية هو التباعد، وهو وحده ما يستطيع التدريب أن يقلّصه. أما اللوحة الثانية فتفصّل الكلفة رمزًا رمزًا، وعندها يكفّ الحساب عن كونه متوسّطًا ليصير تشخيصًا: فالبتّات قلّما تُهدر حيث تتوقّع.

هـ. لماذا تُدرَّب المصنِّفات على الإنتروبيا المتقاطعة

هنا تستحق النظرية مكانها. يُخرج المصنِّف توزيعاً احتمالياً على التسميات؛ والحقيقة الأرضية أيضاً توزيع - عادةً بكل الكتلة على تسمية واحدة. وتدريب النموذج يعني جعل توزيعه يطابق التوزيع الحقيقي، والإنتروبيا المتقاطعة هي بالضبط الكمية التي تقيس الفجوة. ويقولها شولّيه مباشرة: الإنتروبيا المتقاطعة كمية من نظرية المعلومات تقيس المسافة بين التوزيعات الاحتمالية، وهنا بين توزيع الحقيقة الأرضية وتنبّؤات النموذج، وهي عادةً الاختيار الصحيح حين يُخرج النموذج احتمالات.

ومع حقيقة أحادية على الفئة $c$، تتلاشى كل الحدود إلا واحداً وتصير خسارة ذلك المثال مجرّد

$$-\log q(c),$$

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

وهذا هو الاستدلال نفسه الذي يبرّر هدف خسارة اللوغاريتم في الانحدار اللوجستي والتصنيف: فالخسارة ليست دالة مريحة اعتباطية، بل هي المفاجأة المتوقّعة لاعتقادات النموذج تحت التوزيع الحقيقي.

والإنتروبيا نفسها تقيس أيضًا ما تستطيع قناة ذات ضجيج أن تحمله، وهنا يذهب الشكل أدناه خطوة أبعد من هذه المقالة. إنه قناة ثنائية تقلب كل بتّ باحتمال $f$، وسعتها $1 - B(f)$ بتّ لكل استعمال. اضبط احتمال القلب على 0.1 لتقرأ 0.5310، وعلى 0.5 لتقرأ صفرًا تمامًا، ثم تجاوزه وانظر السعة تعود صاعدة، لأن قناة تكذب دائمًا يمكن عكسها. أما اللوحة الثانية فمثال مستقلّ: بتّان متوازنان وهدف هو «أو» الحصري لهما، حيث يحمل كل مدخل وحده 0 بتّ بالضبط عن الهدف ويحمل الزوج بتًّا واحدًا. ومزلاج المعالجة يمرّر المخرج عبر قناة ثانية على التوالي: قلبها المركّب $f(1-g) + g(1-f)$، وهو لا يكون أقرب إلى اليقين من $f$ أبدًا، فلا يمكن للمعلومة أن ترتفع.

الخلاصات الأساسية

• الإنتروبيا $H(V) = -\sum_k P(v_k)\log_2 P(v_k)$ هي المفاجأة المتوقّعة، مقيسةً بـالبتّات؛ والأساس 2 يجعلها متوسط عدد أسئلة نعم/لا.
• العملة المتوازنة $1$ بت بالضبط، والنرد الرباعي المتوازن $2$ بت، وعملة الـ99٪ نحو $0.08$ بت، والنتيجة اليقينية $0$.
• مكسب المعلومات هو انخفاض الإنتروبيا المتوقّع من اختبار؛ وقسمتنا نقلت $1$ بت إلى $0.8043$، بمكسب 0.1957 بت.
• يسمّي التعلّم الإحصائي معيار الشجرة $-\sum \hat p \log \hat p$ «إنتروبيا متقاطعة»؛ وتسمّيه نظرية المعلومات إنتروبيا. الصيغة نفسها، والاسمان مختلفان، والالتباس حقيقي.
• الإنتروبيا المتقاطعة $H(p,q) = -\sum p \log q$ تقيّم اعتقاداً $q$ مقابل حقيقة $p$، وتتفكّك إلى $H(p) + \text{KL}(p \| q)$ - لايقين غير قابل للتقليص زائد عقوبة الخطأ.
• تباعد KL غير متناظر وغير محدود؛ وهو ليس مسافة.
• تصغير الإنتروبيا المتقاطعة هو تصغير KL عن الحقيقة، ولهذا كانت خسارة التصنيف المعيارية.

ما التالي

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