الشبكات البايزية والاستدلال الاحتمالي

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

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

الشبكة البايزية مخطّط موجَّه لا دوري. كل عقدة فيه متغيّر عشوائي؛ والسهم من $X$ إلى $Y$ يجعل $X$ أبًا لـ$Y$؛ وكل عقدة تحمل جدول احتمالات شرطية يعطي $P(X_i \mid \mathrm{Parents}(X_i))$، بصفّ لكل تركيبة من قيم الآباء. والعقدة البوليانية ذات $k$ أبًا بوليانيًا تحتاج إلى $2^k$ عددًا.

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

$$\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}$$

ومعنى الصورة معادلة واحدة. فلأي إسناد كامل،

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

فاحتمال أن ينطلق الإنذار بلا سطو ولا زلزال، ويتّصل الجاران كلاهما، هو

$$P(j, m, a, \lnot b, \lnot e) = 0.90 \times 0.70 \times 0.001 \times 0.999 \times 0.998 = 0.000628 .$$

وكل واحد من المدخلات الـ32 للتوزيع المشترك متاح على هذا النحو، من عشرة أعداد بدل 31. وليس الوفر حيلة: بل هو الدعوى، التي تقرّرها الأسهم الغائبة، بأن كل متغيّر مستقلّ شرطيًا عن غير أحفاده بمعلومية آبائه. بل أقوى من ذلك: كل عقدة مستقلّة عن كل العقد الأخرى بمعلومية غطاء ماركوف الخاصّ بها - آبائها وأبنائها والآباء الآخرين لأبنائها. فبمعلومية الإنذار والزلزال، لا تقول المكالمتان شيئًا زائدًا عن السطو.

ب. الاستدلال الدقيق

يسأل الاستعلام عن $\mathbf{P}(X \mid \mathbf{e})$. ولمّا كانت كل مدخلة من التوزيع المشترك جداءً لمدخلات من الجداول، فالاستعلام مجموع مُعيَّر لجداءات على المتغيّرات المخفية. اتّصل الجاران كلاهما؛ أهو سطو؟

$$P(b \mid j, m) = \alpha\, P(b) \sum_{e} P(e) \sum_{a} P(a \mid b, e)\,P(j \mid a)\,P(m \mid a).$$

أربعة حدود لأجل $b$، وأربعة لأجل $\lnot b$، كلٌّ منها جداء خمسة أعداد:

$$\mathbf{P}(B \mid j, m) = \alpha\, \langle 0.00059224,\ 0.00149186 \rangle = \langle 0.284,\ 0.716 \rangle .$$

فبلاغان مستقلّان يرفعان احتمالًا قبليًا قدره واحد في الألف إلى 28 بالمئة، ولا أبعد من ذلك، لأن كتلة اللاسطو تأتي من ثلاث طرق متقاربة: إنذار بلا سبب ثم المكالمتان، ‎$0.000628$‎؛ ولا إنذار مع اتصال الجارين مع ذلك، ‎$0.000498$‎؛ وإنذار بسبب زلزال ثم المكالمتان، ‎$0.000365$‎. ومعًا تزن هذه الطرق 2.5 ضعف طريق السطو، ‎$0.000592$‎.

والتعداد يحسب هذا شجرةً بالعمق أوّلًا، والشجرة تكرّر نفسها: فالجداء $P(j \mid a)\,P(m \mid a)$ يُحسب مرّة تحت $e$ ومرّة أخرى تحت $\lnot e$. وعلى $n$ متغيّرًا بوليانيًا تكون الكلفة $O(2^n)$، وهي أفضل من $O(n\,2^n)$ لبناء كل مدخلة من التوزيع المشترك على حدة، لكن جلّها إعادة حساب. أما إزالة المتغيّرات فتخزّن كل جزء عاملًا - جدولًا على المتغيّرات التي ما زال يتوقّف عليها - وتركّب العوامل بالجداء النقطي وبالجمع على متغيّر. فالجمع على $A$ يعطي عاملًا على $(B, E)$:

$$f_6(B, E) = \begin{array}{c|cc} & e & \lnot e \\ \hline b & 0.598525 & 0.592230 \\ \lnot b & 0.183055 & 0.001130 \end{array}$$

والجمع على $E$ في مقابل $P(E)$ يترك $f_7(B) = \langle 0.592243,\ 0.001493 \rangle$، والضرب في $P(B)$ ثم التعيير يعيد $\langle 0.284, 0.716 \rangle$ وقد حُسب كل جداء من جداءات الأوراق مرّة واحدة.

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

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

ج. أخذ العيّنات حين يستحيل الدقيق

لشبكة الرشّاش أربعة متغيّرات بوليانية ومساران من $\mathit{Cloudy}$ إلى $\mathit{WetGrass}$، أحدهما عبر الرشّاش والآخر عبر المطر:

$$\begin{array}{ll} P(c) = 0.5 & \\[4pt] P(s \mid c) = 0.10 & P(s \mid \lnot c) = 0.50 \\ P(r \mid c) = 0.80 & P(r \mid \lnot c) = 0.20 \\[4pt] P(w \mid s, r) = 0.99 & P(w \mid s, \lnot r) = 0.90 \\ P(w \mid \lnot s, r) = 0.90 & P(w \mid \lnot s, \lnot r) = 0.00 \end{array}$$

أخذ العيّنات القبلي يسحب كل متغيّر من جدوله بترتيب الآباء أوّلًا. واحتمال إنتاج حدث ما هو جداء المدخلات التي رُجع إليها، وهو التوزيع المشترك نفسه: فـ$[c, \lnot s, r, w]$ يخرج باحتمال $0.5 \times 0.9 \times 0.8 \times 0.9 = 0.324$. فتتقارب التردّدات إذن إلى الاحتمالات، ويكون التقدير متّسقًا.

وأخذ العيّنات بالرفض يجيب عن استعلام شرطي برفض كل عيّنة تخالف الشواهد. فلأجل $P(\mathit{Rain} \mid \mathit{Sprinkler} = \text{true})$، وقيمته الدقيقة $0.3$، رفضت تشغيلة ذات بذرة ثابتة من 1,000 عيّنة قبلية 703 منها وأبقت 79 فيها مطر في مقابل 218 بلا مطر، بتقدير قدره $0.266$. فسبعون بالمئة من الجهد ذهب سدًى، وتلك هي الحالة الرحيمة: فمعدّل البقاء هو $P(\mathbf{e})$، وهو يهبط أسّيًا مع عدد متغيّرات الشواهد. فاسأل شبكة السطو عن $\mathbf{P}(B \mid j, m)$ فلا يبقى إلا نحو 21 عيّنة من كل 10,000.

والترجيح بالإمكان يثبّت متغيّرات الشواهد بدل سحبها، فيصير كل حدث متّسقًا، ويرجّح كل حدث باحتمال الشواهد بمعلومية الآباء الذين اختارهم الساحب. فلأجل $\mathbf{P}(\mathit{Rain} \mid c, w)$ بالترتيب $C, S, R, W$: يبدأ الوزن من $1$، و$C$ من الشواهد فـ$w \leftarrow 0.5$؛ و$S$ يُسحب من $\langle 0.1, 0.9 \rangle$، ولنقل خطأً؛ و$R$ من $\langle 0.8, 0.2 \rangle$، ولنقل صوابًا؛ و$W$ من الشواهد فـ$w \leftarrow 0.5 \times P(w \mid \lnot s, r) = 0.45$. فيُعدّ الحدث تحت المطر بوزن $0.45$. ولا شيء يُرفض، ولمّا كان احتمال السحب مضروبًا في الوزن يساوي التوزيع المشترك، فالعدّ المرجَّح متّسق: ألف عيّنة على البذرة نفسها تعطي $0.9758$ في مقابل قيمة دقيقة $0.9758$. وتتدهور الطريقة حين تكون الشواهد غير مرجّحة تحت القيم المسحوبة، لأن بضعة أوزان ثقيلة تهيمن عندئذٍ على كل شيء.

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

$$P(x_i' \mid \mathrm{mb}(X_i)) = \alpha\, P\big(x_i' \mid \mathrm{parents}(X_i)\big) \prod_{Y_j \in \mathrm{Children}(X_i)} P\big(y_j \mid \mathrm{parents}(Y_j)\big).$$

فلأجل $\mathbf{P}(\mathit{Rain} \mid s, w)$ من الحالة $[c, s, \lnot r, w]$، تستعمل إعادة سحب $C$ الجداءَ $P(C)\,P(s \mid C)\,P(\lnot r \mid C)$، فيعطي $P(c \mid s, \lnot r) = 0.048$؛ ولنقل إنه خرج خطأً. ثم تستعمل إعادة سحب $R$ الجداءَ $P(R \mid \lnot c)\,P(w \mid s, R)$، فيعطي $P(r \mid \lnot c, s, w) = 0.216$. وكل حالة تُزار عيّنة. وألف خطوة على بذرة ثابتة تقدّر $0.315$ في مقابل القيمة الدقيقة $0.320$.

وسبب نجاح هذا أن للسلسلة توزيعًا مستقرًّا، وأن خطوة غيبس تحقّق التوازن التفصيلي بالنسبة إلى التوزيع البعدي، ما يُلزم الاثنين بالتطابق: فنسبة الزمن المقضيّ في كل حالة على المدى الطويل هي $P(\mathbf{x} \mid \mathbf{e})$. فلا عيّنة تُرفض ولا وزن ينهار. والكلفة ترابط بين الحالات المتعاقبة، فتحتاج السلسلة إلى وقت لتنسى من أين بدأت.

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

أين يتركك هذا

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