الشبكات البايزية والتوزيع المشترك

يجيب التوزيع المشترك الكامل عن كل سؤال احتمالي، وهو مع ذلك عديم الجدوى عمليًا: فعلى $n$ متغيّرًا بوليانيًا له $2^n$ مدخلة، لا أحد يستطيع تزويدها ولا أحد يستطيع تخزينها. أما الشبكة البايزية فتحتفظ بقوّة التوزيع المشترك ولا تدفع إلا ثمن التبعيّات الموجودة فعلًا.

ما الشبكة

الشبكة البايزية مخطّط موجَّه لا دوري فيه

• كل عقدة متغيّر عشوائي،
• والسهم من $X$ إلى $Y$ يقول إن $X$ أبٌ لـ$Y$، أي إن لـ$X$ تأثيرًا مباشرًا في $Y$،
• وكل عقدة $X_i$ تحمل جدول احتمالات شرطية (CPT) يعطي $P(X_i \mid \mathrm{Parents}(X_i))$، بصفّ لكل تركيبة من قيم الآباء.

ويجب أن يكون مجموع كل صفّ من الجدول واحدًا، فلا يُكتب للمتغيّر البولياني إلا احتمال الصواب ويلزم منه الآخر. ولذلك تحتاج العقدة البوليانية ذات $k$ أبًا بوليانيًا إلى $2^k$ عددًا، وتحتاج عقدة الجذر إلى عدد واحد بالضبط.

شبكة السطو

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

$$\begin{array}{ll} P(b) = 0.001 & P(e) = 0.002 \\[4pt] P(a \mid b, e) = 0.95 & P(a \mid b, \lnot e) = 0.94 \\ P(a \mid \lnot b, e) = 0.29 & P(a \mid \lnot b, \lnot e) = 0.001 \\[4pt] P(j \mid a) = 0.90 & P(j \mid \lnot a) = 0.05 \\ P(m \mid a) = 0.70 & P(m \mid \lnot a) = 0.01 \end{array}$$

في المخطّط الأسهم $B \to A$ و$E \to A$ و$A \to J$ و$A \to M$، ولا شيء غيرها. وهذه مجموعة من الدعاوى: فجون وماري لا يدركان السطو مباشرةً، ولا يلاحظان الزلازل الطفيفة، ولا يتشاوران قبل الاتّصال. وكل ما قد يُعطّل الإنذار - بطّارية فارغة أو سلك مقطوع - أو يمنع جارًا من الإبلاغ عنه مطويٌّ في الأعداد لا منمذجٌ. وليس ذلك تهاونًا؛ بل هكذا يتدبّر عميل صغير أمره في عالم كبير.

ماذا تعني الشبكة

الدلالة معادلة واحدة. فلأي إسناد كامل $x_1, \dots, x_n$ لكل المتغيّرات،

$$P(x_1, \dots, x_n) \;=\; \prod_{i=1}^{n} P\big(x_i \mid \mathrm{parents}(X_i)\big),$$

حيث يرمز $\mathrm{parents}(X_i)$ إلى قيم آباء $X_i$ داخل الإسناد. فالشبكة هي التوزيع المشترك، مكتوبًا جداءً لمدخلات جداولها.

مثال محلول: حدث كامل واحد

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

$$\begin{aligned} P(j, m, a, \lnot b, \lnot e) &= P(j \mid a)\,P(m \mid a)\,P(a \mid \lnot b, \lnot e)\,P(\lnot b)\,P(\lnot e) \\ &= 0.90 \times 0.70 \times 0.001 \times 0.999 \times 0.998 \\ &= 0.000628 . \end{aligned}$$

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

لماذا الشبكة أصغر بكثير

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

$$1 + 1 + 4 + 2 + 2 = 10$$

في مقابل $2^5 - 1 = 31$ مدخلة مستقلّة في جدول التوزيع المشترك الكامل. وتتّسع الهوّة اتّساعًا انفجاريًا: فمع 30 متغيّرًا بوليانيًا لكلٍّ منها خمسة آباء على الأكثر، تحتاج الشبكة إلى $30 \times 2^5 = 960$ عددًا على الأكثر حيث يحتاج التوزيع المشترك إلى أكثر من مليار. والوفر مردّه إلى المحلّية: فكل متغيّر لا يتأثّر مباشرةً إلا بقلّة من المتغيّرات الأخرى.

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

الاستقلالات التي يقرّرها المخطّط

طبّق قاعدة السلسلة على أي ترتيب للمتغيّرات:

$$P(x_1, \dots, x_n) = \prod_{i=1}^{n} P(x_i \mid x_{i-1}, \dots, x_1).$$

وبالمقارنة مع الدلالة أعلاه، تكون الشبكة تمثيلًا صحيحًا بالضبط حين يتحقّق، لكل متغيّر،

$$P(X_i \mid X_{i-1}, \dots, X_1) = P\big(X_i \mid \mathrm{Parents}(X_i)\big)$$

لترتيب ما تأتي فيه كل عقدة بعد آبائها. وبالكلمات: كل متغيّر مستقلّ شرطيًا عن سوابقه الأخرى بمعلومية آبائه. وتلزم من المخطّط وحده نتيجتان أخريان.

• العقدة مستقلّة شرطيًا عن غير أحفادها بمعلومية آبائها. ففي شبكة السطو، $J$ مستقلّ عن $B$ و$E$ و$M$ متى عُلم $A$.
• والعقدة مستقلّة شرطيًا عن كل عقدة أخرى بمعلومية غطاء ماركوف الخاصّ بها: آبائها وأبنائها والآباء الآخرين لأبنائها. فغطاء $B$ هو $\{A, E\}$، ومن ثمّ فمتى عُلمت حالة الإنذار وحالة الزلزال، لم تُخبرك المكالمتان بشيء زائد عن السطو.

الترتيب مهمّ حين تبني شبكة. أضف العقد بالترتيب $M, J, A, B, E$ فتُضطرّ إلى رسم $M \to J$، ثم المكالمتين كلتيهما إلى $A$، ثم $A \to B$، ثم $A \to E$ و$B \to E$: وصلتان زائدتان وثلاثة أعداد زائدة على الشبكة السببية، وبعضها يصف علاقات يصعب تقديرها حقًا. فوضع الأسباب قبل النتائج هو ما يُبقي الشبكة صغيرة.

قبل الاختبار

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