شبكة بايزية

تعد الشبكة البايزية Bayesian network (تُعرف أيضًا باسم شبكة بايز Bayes network أو شبكة الاعتقاد belief network أو شبكة اتخاذ القرار decision network) فهي نموذج رسومي احتمالي الذي يمثل مجموعة من المتغيرات و التبعيات الشرطية عبر رسم بياني لا دوري موجه (DAG). تعتبر الشبكات البايزية مثالية لأخذ حدث واقع والتنبؤ باحتمالية أن يكون أحد الأسباب المحتملة العديدة هو العامل المساهم. على سبيل المثال، يمكن للشبكة البايزية أن تمثل العلاقات الاحتمالية بين الإضطراب والأعراض. بالنظر إلى الأعراض، يمكن استخدام الشبكة لحساب احتمالات وجود اضطرابات مختلفة.

يمكن أن تؤدي وتنفذ الخوارزميات الفعالة الاستدلال و التعلم في الشبكات البايزية. فالشبكات البايزية التي تضع نموذجاً لتسلسل المتغيرات (على سبيل المثال إشارات الكلام أو تسلسل الپروتين) والتي تسمى الشبكة البايزية الديناميكية. تسمى تعميمات الشبكات البايزية التي يمكن أن تمثل وتحل مشاكل القرار في ظل عدم اليقين مخططات التأثير.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

النموذج الرسومي

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


مثال

شبكة بايزية بسيطة ذات جداول احتمالية مشروطة

يمكن أن يتسبب حدثان في تبلل العشب: رشاش نشط أو مطر. المطر له تأثير مباشر على استخدام الرش (أي أنه عندما تمطر، فإن الرش عادة ما يكون غير نشط). يمكن تصميم هذا الموقف باستخدام شبكة بايزية (تظهر على اليمين). كل متغير له قيمتان محتملتان، T (للصحيح) و F (للخطأ).

تكون دالة الاحتمال المشترك:

حيث G = "العشب رطب (صح/خطأ)"، S = "تم تشغيل الرشاش (صح/خطأ)"، و R = "مطر (صح/خطأ)".

يمكن للنموذج أن يجيب على أسئلة حول وجود سبب بالنظر إلى وجود تأثير (ما يسمى بالاحتمال العكسي) مثل "ما هو احتمال أن تمطر، بالنظر إلى أن العشب رطب؟" باستخدام صيغة الاحتمال الشرطي وجمع كل المتغيرات العشوائية:

باستخدام النشر لدالة الاحتمال المشترك والاحتمالات الشرطية من جداول الاحتمال الشرطي (CPTs) المذكورة في الرسم التخطيطي، يمكن للمرء تقييم كل حد في المجاميع في البسط والمقام. فمثلا،

فتكون النتائج العددية (مكتوبة بقيم المتغيرات المرتبطة) هي

للإجابة على سؤال تداخلي، مثل "ما هو احتمال هطول المطر، إذا كنا نبلل العشب؟" تخضع الإجابة لوظيفة التوزيع المشترك بعد التدخل

تم الحصول عليها عن طريق إزالة العامل من توزيع ما قبل التدخل. يفرض عامل do أن تكون قيمة G صحيحة. لا يتأثر احتمال هطول الأمطار بالإجراء:

للتنبؤ بتأثير تشغيل الرشاش:

بإزالة المصطلح ، تبين أن الإجراء يؤثر على العشب وليس المطر.

قد لا تكون هذه التنبؤات ممكنة في ضوء المتغيرات المخفية، كما هو الحال في معظم مشاكل تقييم الخطط. ومع ذلك، لا يزال من الممكن التنبؤ بتأثير الإجراء كلما تم استيفاء معيار الباب الخلفي.[1][2] تنص على أنه إذا كان من الممكن ملاحظة مجموعة Z من العقد أنه d-يفصل[3] (أو يمنع) كل مسارات المدخل الراجع من X إلى Y إذن

مسار المدخل الراجع هو الذي ينتهي بسهم في X. المجموعات التي تفي بمعيار المدخل الراجع تسمى "كافية" أو "مقبولة". فمثلا، المجموعة Z = R مقبول للتنبؤ بتأثير S = T على G، لأن R d- يفصل مسار المدخل الراجع (فقط) S ← R → G.ومع ذلك، إذا لم يتم ملاحظة S، فلا توجد مجموعة أخرى d - تفصل هذا المسار وتأثير تشغيل الرشاش (S = T) على العشب (G) لا يمكن التنبؤ بها من الملاحظات السلبية. في تلك الحالة P(G | do(S = T)) غير "محدد". هذا يعكس حقيقة أنه، في ظل نقص البيانات التداخلية، فإن الاعتماد المرصود بين S و G يرجع إلى علاقة سببية أو زائفة (الاعتماد الواضح الناشئ عن سبب مشترك، R). (انظر مفارقة سيمپسون) لتحديد ما إذا كانت العلاقة السببية قد تم تحديدها من شبكة بايزية عشوائية ذات متغيرات غير ملحوظة، يمكن للمرء استخدام القواعد الثلاثة لـ "do-حساب التفاضل و التكامل"[1][4]واختبار ما إذا كان يمكن إزالة جميع مصطلحات do من التعبير عن تلك العلاقة، وبالتالي التأكد من أن الكمية المرغوبة يمكن تقديرها من بيانات التردد.[5]

يمكن أن يؤدي استخدام الشبكة البايزية إلى توفير قدر كبير من الذاكرة على جداول الاحتمالات الشاملة، إذا كانت التبعيات في التوزيع المشترك قليلة. على سبيل المثال، تتطلب طريقة بسيطة لتخزين الاحتمالات الشرطية لـ 10 متغيرات ثنائية القيمة كجدول مساحة تخزين لقيم .إذا لم يعتمد التوزيع المحلي للمتغير على أكثر من ثلاثة متغيرات رئيسية ، فإن تمثيل الشبكة البايزية يخزن على الأكثر قيم .

تتمثل إحدى ميزات الشبكات البايزية في أنه من الأسهل بشكل حدسي على الإنسان فهم (مجموعة متفرقة من) التبعيات المباشرة والتوزيعات المحلية أكثر من التوزيعات المشتركة الكاملة.

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

تؤدي الشبكات البايزية ثلاث مهام استدلال رئيسية:

استنتاج المتغيرات المخفية

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

أكثر طرق الاستدلال الدقيق شيوعاً هي: الحذف المتغير، والذي يزيل (بالتكامل أو التجميع) المتغيرات غير الملحوظة التي لم تتم ملاحظتها واحداً تلو الآخر عن طريق توزيع المجموع على المنتج؛ انتشار شجرة الزمرة، والتي تخزن الحساب مؤقتاً بحيث يمكن الاستعلام عن العديد من المتغيرات في وقت واحد ويمكن نشر أدلة جديدة بسرعة؛ والتكييف التكراري وبحث AND / OR، مما يسمح تعويض الزمكان ويتناسب مع كفاءة الاستبعاد المتغير عند استخدام مساحة كافية. كل هذه الأساليب لها تعقيد أسي في عرض ثلاثي للشبكة. فخوارزميات الاستدلال التقريبي الأكثر شيوعًا هي أخذ العينات المهمة، MCMC العشوائية، حذف المقدار الصغير ، انتشار الاعتقاد كثير الحلقات ، انتشار الاعتقاد المعمم و طرق التنويع.

تعلم الپارامتر

من أجل تحديد الشبكة البايزية بشكل كامل وبالتالي تمثيل التوزيع الاحتمالي المشترك بشكل كامل، من الضروري تحديد التوزيع الاحتمالي لكل عقدة X مشروطاً بأصول X. قد يكون لتوزيع X المشروط بأصوله أي شكل. من الشائع العمل مع توزيعات گاوس المتقطعة لأن ذلك يبسط الحسابات. في بعض الأحيان ، لا يُعرف سوى القيود المفروضة على التوزيع؛ يمكن للمرء بعد ذلك استخدام مبدأ الإنتروپيا القصوى لتحديد توزيع واحد، وهو التوزيع الذي يحتوي على أكبر الإنتروپيا نظرًا للقيود. (بشكل مشابه، في السياق المحدد لـ الشبكة البايزية الديناميكية، يتم تحديد التوزيع الشرطي للتطور الزمني للحالة المخفية بشكل شائع لتعظيم معدل الإنتروپيا للعملية العشوائية الضمنية.)

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

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

تعلم البنية

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

يعد التعلم التلقائي لبنية الرسم البياني للشبكة البايزية (BN) تحدياً يتم متابعته في التعلم الآلي. تعود الفكرة الأساسية إلى خوارزمية الاسترداد التي طورها ريباين و پيرل[6] ويستند إلى التمييز بين الأنماط الثلاثة الممكنة المسموح بها في DAG ثلاثية العقد:

أنماط التوصيل
الأنماط النموذج
سلسلة
تفرع
تعارض

أول 2 يمثلان نفس التبعيات ( و مستقلان نظراً ل) وبالتالي، لا يمكن تمييزها. ومع ذلك، يمكن تحديد المعارض بشكل فريد عندما تكون و مستقلة بشكل هامشي وجميع الأزواج الأخرى تابعة. وهكذا، في حين أن الهياكل (الرسوم البيانية المجردة من الأسهم) لهذه الثلاثة توائم متطابقة، يمكن تحديد اتجاه الأسهم جزئيًا. ينطبق نفس التمييز عندما يكون ل و أصول مشتركة، باستثناء أنه يجب أولاً أن يشترط هذه الأصول تم تطوير خوارزميات لتحديد الهيكل للرسم البياني الأساسي بشكل منهجي، ثم توجيه جميع الأسهم التي تم تحديد اتجاهها بواسطة الاستقلالية الشرطية التي تمت ملاحظتها.[1][7][8][9]

تستخدم طريقة بديلة للتعلم الهيكلي البحث القائم على التحسين. والتي تتطلب دالة التسجيل وإستراتيجية البحث. يكون تابع التسجيل الشائع هو الاحتمالية اللاحقة للهيكل المعطى لبيانات التدريب، مثل BIC أو BDeu. المتطلب الزمني لإرجاع بحث شامل لبنية تزيد النتيجة إلى الحد الأقصى هو أسي فائق في عدد المتغيرات. تُجري استراتيجية البحث المحلية تغييرات تدريجية تهدف إلى تحسين درجة الهيكل. يمكن لخوارزمية بحث عالمية مثل سلسلة ماركوڤ مونت كارلو تجنب الوقوع في شرك الحدود الدنيا المحلية. فريدمان وآخرون.[10][11] تمت مناقشة استخدام المعلومات المتبادلة بين المتغيرات وإيجاد بنية تعظم ذلك. تم تنفيذ ذلك عن طريق تقييد تعيين المرشح الرئيسي على عقد "k" والبحث الشامل فيها.

إحدى الطرق السريعة بشكل خاص لتعلم BN الدقيق هي طرح المشكلة على أنها مشكلة تحسين، وحلها باستخدام البرمجة التامة. تتم إضافة قيود الحدية إلى البرنامج التام (IP) أثناء الحل في شكل مستويات القطع.[12] يمكن أن تتعامل هذه الطريقة مع مشاكل تصل إلى 100 متغير.

من أجل التعامل مع مشاكل آلاف المتغيرات، من الضروري اتباع نهج مختلف. الأول هو أخذ عينة من طلب واحد، ثم إيجاد بنية BN الأمثل فيما يتعلق بهذا الترتيب. وهذا يعني العمل على مساحة البحث الخاصة بالطلبات المحتملة، وهو أمر مناسب لأنه أصغر من مساحة هياكل الشبكة. ثم يتم أخذ عينات من الطلبات المتعددة وتقييمها. لقد ثبت أن هذه الطريقة هي الأفضل في الأعمال عندما يكون عدد المتغيرات ضخمًا.[13]

هناك طريقة أخرى تتمثل في التركيز على الفئة الفرعية للنماذج القابلة للتقسيم، والتي لها شكل مغلق MLE. من الممكن بعد ذلك اكتشاف بنية متسقة لمئات المتغيرات.[14]

يعد تعلم الشبكات البايزية ذات النطاق الثلاثي المحدود أمراً ضرورياً للسماح بالاستدلال الدقيق القابل للتتبع، نظراً لأن تعقيد الاستدلال الأسوأ يكون أسياً في عرض الثلاثي k (وفقًا لفرضية الزمن الأسي). ومع ذلك، باعتباره خاصية شاملة للرسم البياني، فإنه يزيد بشكل كبير من صعوبة عملية التعلم. في هذا السياق، من الممكن استخدام K-tree للتعلم الفعال.[15]

مقدمة إحصائية

البيانات المعطاة والپارامتر ، يبدأ التحليل البايزي بـ احتمال سابق (مسبق) و الاحتمالية لحساب الاحتمالية اللاحقة .

غالباً ما تعتمد السابقة بدورها على الپارامترات التي لم يرد ذكرها في الاحتمال. لذلك، يجب استبدال الأولية باحتمالية ، و والمطلوب التي تم إدخالها حديثاً

هذا هو أبسط مثال على النموذج البايزي الهرمي.[مطلوب توضيح]

يمكن تكرار العملية؛ على سبيل المثال، قد تعتمد الپارامترات بدورها على پارامترات إضافية ، والتي تتطلب سابق خاص بها. في النهاية يجب أن تنتهي العملية، مع مقدمات لا تعتمد على پارامترات غير مذكورة.


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

أمثلة تمهيدية

بالنظر إلى الكميات المقاسة لكل منها أخطاء توزيع طبيعي لانحراف معياري معروف ،

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

ومع ذلك، إذا كانت الكميات مرتبطة، بحيث تكون الفردية على سبيل المثال مستمدةً من التوزيع الأساسي، فإن هذه العلاقة تدمر الاستقلال وتقترح نموذجاً أكثر تعقيداً، على سبيل المثال،

فبواسطة السوابق الغير مناسبة , . عندما يكون، فهذا نموذج محدد (أي يوجد حل فريد لپارامترات النموذج)، والتوزيعات اللاحقة ل الفردية سوف تميل إلى الانتقال، أو يتضاءل بعيداً عن تقديرات الاحتمالية القصوى تجاه متوسطها المشترك. هذا التضاؤل هو سلوك نموذجي في النماذج بايزية الهرمية.

القيود على السابقات

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

التعاريف والمفاهيم

تم تقديم عدة تعريفات مكافئة للشبكة البايزية. لما يلي، لنفترض أن G = (V,E) يكون الرسم البياني غير الدوري الموجه (DAG) ولنجعل X = (Xv), vV تكون مجموعة من المتغيرات العشوائية مفهرسة بواسطة V.

تعريف تحليل العوامل

X عبارة عن شبكة بايزية بالنسبة إلى G إذا كان من الممكن كتابة دالة كثافة الاحتمال (فيما يتعلق قياس الخرج) كمنتج لتواابع الكثافة الفردية، مشروطة بمتغيراتها الأصلية:[16]

حيث pa (v) هي مجموعة أصول v (أي تلك الذرا التي تشير مباشرة إلى v عبر حافة واحدة).

لأي مجموعة من المتغيرات العشوائية، يمكن حساب احتمال أي عنصر في التوزيع المشترك من الاحتمالات الشرطية باستخدام قاعدة السلسلة (مع الأخذ في الاعتبار الترتيب الطوبولوجي X) على النحو التالي:[16]

باستخدام التعريف أعلاه، يمكن كتابة هذا على النحو التالي:

الفرق بين التعبيرين هو الاستقلال المشروط للمتغيرات من أي من غير المتحدرين منهم، مع مراعاة قيم المتغيرات الأصلية.

خاصة ماركوڤ المحلية

X هي شبكة بايزية فيما يتعلق بـ G إذا كانت تفي بـ خاصة ماركوڤ المحلية : كل متغير هو مستقل بشروط من غير المنحدرين منه نظرًا لمتغيراته الأصلية:[17]

حيث de(v) هي مجموعة السلائل و V \ de(v) هي مجموعة غير المتحدرين من v.

يمكن التعبير عن هذا بعبارات مشابهة للتعريف الأول ، مثل

مجموعة الأصول هي مجموعة فرعية من مجموعة غير المتحدرين لأن الرسم البياني لا دوري.

تطوير الشبكات البايزية

غالباً ما يبدأ تطوير الشبكة البايزية بإنشاء DAG G بحيث تحقق X خاصية ماركوڤ المحلية فيما يتعلق بـ G. في بعض الأحيان يكون هذا هو DAG السببي. يتم تقييم توزيعات الاحتمال الشرطي لكل متغير بالنظر إلى أصله في G. في كثير من الحالات، على وجه الخصوص في الحالة التي تكون فيها المتغيرات منفصلة، إذا كان التوزيع المشترك لـ X هو نتاج هذه التوزيعات الشرطية، فإن X هي شبكة بايزية فيما يتعلق بـG.[18]

غطاء ماركوڤ

غطاء ماركوڤ لعقدة ما هي مجموعة العقد التي تتكون من أصولها وسلائلها وأي أصول آخرى لسلائلها. يجعل غطاء ماركوڤ العقدة مستقلة عن بقية الشبكة؛ التوزيع المشترك للمتغيرات في غطاء ماركوڤ للعقدة هو معرفة كافية لحساب توزيع العقدة. X هي شبكة بايزية فيما يتعلق بـ G إذا كانت كل عقدة مستقلة بشكل مشروط عن جميع العقد الأخرى في الشبكة، نظراً لـ غطاء ماركوڤ.[17]

فصل d

يمكن جعل هذا التعريف أكثر عمومية من خلال تحديد فصل d بين عقدتين، حيث تشير d إلى الاتجاه.[1] نحدد أولاً فصل d للمسار ثم نحدد فصل d بين عقدتين بشروط ذلك.

لندع P يكون مساراً من العقدة u إلى v. المسار عبارة عن مسار خالٍ من الحلقات وغير موجه (أي يتم تجاهل جميع اتجاهات الحافة) بين عقدتين. ثم يُقال أن P هي d - مفصولة بمجموعة من العقد Z إذا كان أي من الشروط التالية صحيحاً:

  • تحتوي P على (ولكن لا يلزم أن يكون بالكامل) سلسلة موجهة، أو ، بحيث تكون العقدة الوسطى m في Z،
  • تحتوي P على تفرع، ، بحيث تكون العقدة الوسطى m في Z، أو
  • تحتوي P على تفرع مقلوب (أو معارض)، ، بحيث أن العقدة الوسطى m ليست في Z ولا يوجد سليل لـ m في Z.

العقدتان u و v هما d - مفصولتان بـ Z إذا كانت جميع المسارات بينهما d - مفصولة. إذا لم تكن u و v مفصولة عن d، فهما متصلان بـ d.

X هي شبكة بايزية فيما يتعلق بـ G إذا، لأي عقدتين u ، v:

حيث Z هي مجموعة تفصل d - عن u و v. (غطاء ماركوڤ هو الحد الأدنى من مجموعة العقد التي تفصل d - العقدة v عن جميع العقد الأخرى.)

الشبكات السببية

على الرغم من أن الشبكات البايزية غالباً ما تُستخدم لتمثيل علاقات السببية، لا يلزم أن يكون هذا هو الحال: الحافة الموجهة من u إلى v لا تتطلب أن Xv تعتمد سببياً على Xu. يتضح هذا من خلال حقيقة أن الشبكات البايزية على الرسوم البيانية:

متكافئة: أي أنها تفرض نفس متطلبات الاستقلال المشروط بالضبط.

الشبكة السببية هي شبكة بايزية تتطلب أن تكون العلاقات سببية. تحدد الدلالات الإضافية للشبكات السببية أنه إذا كانت العقدة X ناجمة عن أن تكون في حالة معينة من x (إجراء مكتوب كما ينفذ (X = x))، ثم تتغير دالة كثافة الاحتمال إلى تلك الخاصة بالشبكة التي تم الحصول عليها عن طريق قطع الروابط من X الأصول إلى X، وتعيين X على القيمة الناتجة x.[1] باستخدام هذه الدلالات، يمكن التنبؤ بتأثير التدخلات الخارجية من البيانات التي تم الحصول عليها قبل التدخل.

تعقيد الاستدلال وخوارزميات التقريب

في عام 1990، أثناء العمل في جامعة ستانفورد على تطبيقات المعلومات الحيوية الضخمة، أثبت كوپر أن الاستدلال الدقيق في الشبكات البايزية هو NP-الصارمة.[19] دفعت هذه النتيجة إلى إجراء بحث حول خوارزميات التقريب بهدف تطوير تقريب قابل للتتبع للاستدلال الاحتمالي. في عام 1993 ، أثبت داگن و لوبي نتيجتين مدهشتين بشأن تعقيد تقريب الاستدلال الاحتمالي في الشبكات البايزية.[20] أولاً، أثبتوا أنه لا توجد خوارزمية حتمية قابلة للتتبع يمكن أن تقرب الاستدلال الاحتمالي إلى داخل خطأ مطلق ɛ < 1/2 ثانياً، أثبتوا أنه لا يمكن تتبع الاستدلال الاحتمالي ضمن الخطأ المطلق ɛ < 1/2 مع احتمال ثقة أكبر من 1/2.

في نفس الوقت تقريباً، أثبت روث أن الاستدلال الدقيق في الشبكات البايزية هو في الواقع # P-كامل (وبالتالي يصعب حساب عدد المهام المرضية من نمط الصيغة العادية المرتبطة (CNF) وذلك الاستنتاج التقريبي ضمن عامل 2n1−ɛ لكل ɛ > 0، حتى بالنسبة للشبكات البايزية ذات البنية المقيدة، هي NP-hard.[21][22]

من الناحية العملية، أشارت نتائج التعقيد هذه إلى أنه في حين أن الشبكات البايزية كانت تمثيلات غنية لتطبيقات الذكاء الاصطناعي والتعلم الآلي، فإن استخدامها في تطبيقات العالم الحقيقي الكبيرة يجب أن يتم تعديله إما عن طريق القيود الهيكلية الطوبولوجية، مثل الشبكات البايزية البسيطة، أو القيود على الاحتمالات الشرطية. فخوارزمية التباين المحدود[23] كانت أول خوارزمية تقريب سريع يمكن إثباتها لتقريب الاستدلال الاحتمالي التقريبي بكفاءة في الشبكات البايزية مع ضمانات لتقريب الخطأ. تتطلب هذه الخوارزمية القوية تقييداً طفيفاً على الاحتمالات الشرطية لشبكة بايزية لتكون مقيدة بعيداً عن الصفر وواحد بنسبة 1/p(n) حيث p(n) كان أي متعدد الحدود على عدد العقد في الشبكة n


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

البرمجيات

تشمل البرامج البارزة للشبكات البايزية:

  • مجرد عينة أخرى من عينات جيبس Just another Gibbs sample (JAGS) - بديل مفتوح المصدر لـ WinBUGS. يستخدم أخذ عينات جيبس.
  • OpenBUGS - تطوير مفتوح المصدر لـ WinBUGS.
  • SPSS Modeler - برنامج تجاري يتضمن تطبيقاً للشبكات البايزية.
  • Stan (برمجيات) - ستان هي حزمة مفتوحة المصدر للحصول على الاستدلال البايزي باستخدام جهاز أخذ العينات No-U-Turn (NUTS ،[24] أحد أنواع هاملتونيان مونت كارلو.
  • PyMC3 - مكتبة پايثون التي تنفذ لغة خاصة بمجال مضمّن لتمثيل الشبكات البايزية ومجموعة متنوعة من أجهزة أخذ العينات (بما في ذلك NUTS)
  • WinBUGS - أحد التطبيقات الحسابية الأولى لأخذ عينات MCMC. لم تعد مدعومة.

تاريخ

تمت صياغة مصطلح الشبكة البايزية من قبل يودا پيرل في عام 1985 لتأكيد:[25]

  • الطبيعة الذاتية الغالبة لمعلومات الإدخال
  • الاعتماد على التكييف البايزي كأساس لتحديث المعلومات
  • التمييز بين طرق الاستدلال السببية والأدلة[26]

تم في أواخر الثمانينيات من القرن الماضي التفكير الاحتمالي في الأنظمة الذكية لپيرل[27] و ناپوليتان التفكير الاحتمالي في الأنظمة الخبيرة[28] تلخيص خصائصها وجعلها مجالاً للدراسة.

انظر أيضاً

ملاحظات

  1. ^ أ ب ت ث ج Pearl, Judea (2000). Causality: Models, Reasoning, and Inference. Cambridge University Press. ISBN 978-0-521-77362-1. OCLC 42291253.
  2. ^ "The Back-Door Criterion" (PDF). Retrieved 2014-09-18.
  3. ^ "d-Separation without Tears" (PDF). Retrieved 2014-09-18.
  4. ^ (1994) "A Probabilistic Calculus of Actions". UAI'94 Proceedings of the Tenth international conference on Uncertainty in artificial intelligence: 454–462, San Mateo CA: Morgan Kaufmann. 
  5. ^ Shpitser I, Pearl J (2006). "Identification of Conditional Interventional Distributions". In Dechter R, Richardson TS (eds.). Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence. Corvallis, OR: AUAI Press. pp. 437–444. arXiv:1206.6876.
  6. ^ Rebane G, Pearl J (1987). "The Recovery of Causal Poly-trees from Statistical Data". Proceedings, 3rd Workshop on Uncertainty in AI. Seattle, WA. pp. 222–228. arXiv:1304.2736.{{cite book}}: CS1 maint: location missing publisher (link)
  7. ^ Spirtes P, Glymour C (1991). "An algorithm for fast recovery of sparse causal graphs" (PDF). Social Science Computer Review. 9 (1): 62–72. doi:10.1177/089443939100900106. S2CID 38398322.
  8. ^ Spirtes, Peter; Glymour, Clark N.; Scheines, Richard (1993). Causation, Prediction, and Search (1st ed.). Springer-Verlag. ISBN 978-0-387-97979-3. {{cite book}}: Unknown parameter |name-list-format= ignored (|name-list-style= suggested) (help)
  9. ^ (1991) "Equivalence and synthesis of causal models". UAI '90 Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence: 255–270, Elsevier. 
  10. ^ Friedman, Nir; Geiger, Dan; Goldszmidt, Moises (November 1997). "Bayesian Network Classifiers". Machine Learning. 29 (2–3): 131–163. doi:10.1023/A:1007465528199. {{cite journal}}: Unknown parameter |name-list-format= ignored (|name-list-style= suggested) (help)
  11. ^ Friedman N, Linial M, Nachman I, Pe'er D (August 2000). "Using Bayesian networks to analyze expression data". Journal of Computational Biology. 7 (3–4): 601–20. CiteSeerX 10.1.1.191.139. doi:10.1089/106652700750050961. PMID 11108481.
  12. ^ Cussens, James (2011). "Bayesian network learning with cutting planes" (PDF). Proceedings of the 27th Conference Annual Conference on Uncertainty in Artificial Intelligence: 153–160. arXiv:1202.3713. Bibcode:2012arXiv1202.3713C. {{cite journal}}: Unknown parameter |name-list-format= ignored (|name-list-style= suggested) (help)
  13. ^ Scanagatta M, de Campos CP, Corani G, Zaffalon M (2015). "Learning Bayesian Networks with Thousands of Variables". NIPS-15: Advances in Neural Information Processing Systems. Vol. 28. Curran Associates. pp. 1855–1863.
  14. ^ (2013) "Scaling log-linear analysis to high-dimensional data" in International Conference on Data Mining., Dallas, TX, USA: IEEE. 
  15. ^ M. Scanagatta, G. Corani, C. P. de Campos, and M. Zaffalon. Learning Treewidth-Bounded Bayesian Networks with Thousands of Variables. In NIPS-16: Advances in Neural Information Processing Systems 29, 2016.
  16. ^ أ ب Russell & Norvig 2003, p. 496.
  17. ^ أ ب Russell & Norvig 2003, p. 499.
  18. ^ Neapolitan, Richard E. (2004). Learning Bayesian networks. Prentice Hall. ISBN 978-0-13-012534-7. {{cite book}}: Unknown parameter |name-list-format= ignored (|name-list-style= suggested) (help)
  19. ^ Cooper, Gregory F. (1990). "The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks" (PDF). Artificial Intelligence. 42 (2–3): 393–405. doi:10.1016/0004-3702(90)90060-d. {{cite journal}}: Unknown parameter |name-list-format= ignored (|name-list-style= suggested) (help)
  20. ^ Dagum P, Luby M (1993). "Approximating probabilistic inference in Bayesian belief networks is NP-hard". Artificial Intelligence. 60 (1): 141–153. CiteSeerX 10.1.1.333.1586. doi:10.1016/0004-3702(93)90036-b.
  21. ^ D. Roth, On the hardness of approximate reasoning, IJCAI (1993)
  22. ^ D. Roth, On the hardness of approximate reasoning, Artificial Intelligence (1996)
  23. ^ Dagum P, Luby M (1997). "An optimal approximation algorithm for Bayesian inference". Artificial Intelligence. 93 (1–2): 1–27. CiteSeerX 10.1.1.36.7946. doi:10.1016/s0004-3702(97)00013-1. Archived from the original on 2017-07-06. Retrieved 2015-12-19.
  24. ^ Hoffman, Matthew D.; Gelman, Andrew (2011). The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo. Bibcode2011arXiv1111.4246H. 
  25. ^ Pearl, J. (1985). "Bayesian Networks: A Model of Self-Activated Memory for Evidential Reasoning" (UCLA Technical Report CSD-850017) in Proceedings of the 7th Conference of the Cognitive Science Society, University of California, Irvine, CA.: 329–334. 
  26. ^ Bayes, T.; Price (1763). "An Essay towards solving a Problem in the Doctrine of Chances". Philosophical Transactions of the Royal Society. 53: 370–418. doi:10.1098/rstl.1763.0053. {{cite journal}}: Unknown parameter |name-list-format= ignored (|name-list-style= suggested) (help)
  27. ^ Pearl J (1988-09-15). Probabilistic Reasoning in Intelligent Systems. San Francisco CA: Morgan Kaufmann. p. 1988. ISBN 978-1558604797.
  28. ^ Neapolitan, Richard E. (1989). Probabilistic reasoning in expert systems: theory and algorithms. Wiley. ISBN 978-0-471-61840-9. {{cite book}}: Unknown parameter |name-list-format= ignored (|name-list-style= suggested) (help)

المراجع

Also appears as Heckerman, David (March 1997). "Bayesian Networks for Data Mining". Data Mining and Knowledge Discovery. 1 (1): 79–119. doi:10.1023/A:1009730122752. S2CID 6294315.
An earlier version appears as Technical Report MSR-TR-95-06, Microsoft Research, March 1, 1995. The paper is about both parameter and structure learning in Bayesian networks.

للاستزادة

وصلات خارجية

الكلمات الدالة: