جرافيد

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
📷 يحتوي على 14 صور
الموسوعة الحرة

الرسم البياني المصغر هو مجموعة من العبارات على النحو التالي: " X غير ذي صلة بـ Y بشرط أن نعرف Z "، حيث X و Y و Z مجموعات من المتغيرات. قد يُفسَّر مفهوم "عدم الصلة" و"بشرط أن نعرف" تفسيرات مختلفة، بما في ذلك التفسيرات الاحتمالية والعلائقية والترابطية ، وذلك تبعًا للتطبيق. تشترك هذه التفسيرات في خصائص مشتركة يمكن تمثيلها بمسارات في الرسوم البيانية (ومن هنا جاء اسم "الرسم البياني المصغر"). تُحدد نظرية الرسوم البيانية المصغرة هذه الخصائص في مجموعة محدودة من البديهيات المشتركة بين عدم الصلة المعلوماتية وتمثيلاتها البيانية.

تاريخ

صاغ جوديا بيرل وأزاريا باز [ 1 ] مصطلح "الرسوم البيانية الجزئية" بعد اكتشافهما أن مجموعة من البديهيات التي تحكم الاستقلال الشرطي في نظرية الاحتمالات مشتركة بين الرسوم البيانية غير الموجهة . تُمثَّل المتغيرات كعُقد في الرسم البياني بحيث تكون مجموعتا المتغيرات X و Y مستقلتين بشرط Z في التوزيع عندما تفصل مجموعة العُقد Z بين X و Y في الرسم البياني. وقد اشتق أ. فيليب داويد [ 2 ] وولفغانغ سبون [ 3 ] بديهيات الاستقلال الشرطي في الاحتمالات سابقًا . ثم وُسِّع نطاق العلاقة بين التبعية والرسوم البيانية ليشمل الرسوم البيانية الموجهة غير الدورية (DAGs) [ 4 ] [ 5 ] [ 6 ] ونماذج أخرى للتبعية [ 1 ] [ 7 ] .

تعريف

نموذج التبعية M هو مجموعة جزئية من الثلاثيات ( X ، Z ، Y ) التي تكون فيها العبارة I ( X ، Z ، Y ): X مستقل عن Y بشرط Z ، صحيحة. يُعرَّف الرسم البياني الجزئي بأنه نموذج تبعية مغلق في ظل البديهيات الخمس التالية:

  1. التناظر: أنا(X،Z،Y)⇔أنا(Y،Z،X){\displaystyle I(X,Z,Y)\Leftrightarrow I(Y,Z,X)}
  2. التحلل:أنا(X،Z،Y∪دبليو)⇒أنا(X،Z،Y) و أنا(X،Z،دبليو){\displaystyle I(X,Z,Y\cup W)\Rightarrow I(X,Z,Y)~\&~I(X,Z,W)}
  3. اتحاد ضعيف:أنا(X،Z،Y∪دبليو)⇒أنا(X،Z∪دبليو،Y) و أنا(X،Z∪Y،دبليو){\displaystyle I(X,Z,Y\cup W)\Rightarrow I(X,Z\cup W,Y)~\&~I(X,Z\cup Y,W)}
  4. انقباض:أنا(X،Z،Y) و أنا(X،Z∪Y،دبليو)⇒أنا(X،Z،Y∪دبليو){\displaystyle I(X,Z,Y)~\&~I(X,Z\cup Y,W)\Rightarrow I(X,Z,Y\cup W)}
  5. تقاطع:أنا(X،Z∪دبليو،Y) و أنا(X،Z∪Y،دبليو)⇒أنا(X،Z،Y∪دبليو){\displaystyle I(X,Z\cup W,Y)~\&~I(X,Z\cup Y,W)\Rightarrow I(X,Z,Y\cup W)}

النموذج شبه البياني هو نموذج تبعية مغلق تحت البديهيات من 1 إلى 4. تُعرف هذه البديهيات الخمس مجتمعةً باسم بديهيات النموذج البياني. [ 8 ] وبشكل بديهي، تعني خصائص الاتحاد الضعيف والانكماش أن المعلومات غير ذات الصلة لا ينبغي أن تُغير حالة صلة القضايا الأخرى في النظام؛ فما كان ذا صلة يبقى ذا صلة، وما كان غير ذي صلة يبقى غير ذي صلة. [ 8 ]

أنواع الجرافويدات

الرسوم البيانية الاحتمالية

الاستقلال الشرطي، الذي يُعرَّف بأنه

أنا(X،Z،Y)⇔P(X|Y،Z)=P(X|Z){\displaystyle I(X,Z,Y)\Leftrightarrow P(X\mid Y,Z)=P(X\mid Z)}

هو شبه رسم بياني يصبح رسمًا بيانيًا كاملًا عندما تكون P موجبة تمامًا. [ 1 ] [ 7 ]

الرسوم البيانية الارتباطية

يُعتبر نموذج التبعية رسمًا بيانيًا ارتباطيًا إذا كان لدينا في دالة احتمالية ما،

أناج(X،Y،Z)⇔ρxy.z=0 لكل x∈X و y∈Y{\displaystyle I_{c}(X,Y,Z)\Leftrightarrow \rho _{xy.z}=0{\text{ لكل }}x\in X{\text{ و }}y\in Y}

أينρxy.z{\displaystyle \rho _{xy.z}}هو الارتباط الجزئي بين x و y بالنظر إلى المجموعة Z.

بمعنى آخر، لن يقل خطأ التقدير الخطي للمتغيرات في X باستخدام قياسات على Z بإضافة قياسات للمتغيرات في Y ، مما يجعل Y غير ذي صلة بتقدير X. تتطابق نماذج الارتباط والاعتماد الاحتمالي للتوزيعات الطبيعية. [ 1 ] [ 7 ]

الرسوم البيانية العلائقية

يُعتبر نموذج التبعية رسمًا بيانيًا علائقيًا إذا كان يحقق الشروط التالية:

P(X،Z)>0 و P(Y،Z)>0⟹P(X،Y،Z)>0.{\displaystyle P(X,Z)>0~\&~P(Y,Z)>0\يتضمن P(X,Y,Z)>0.}

بمعنى آخر، لا يتقيد نطاق القيم المسموح بها لـ X باختيار Y ، بمجرد تثبيت Z. وتتشابه عبارات الاستقلال التي تنتمي إلى هذا النموذج مع التبعيات متعددة القيم المضمنة (EMVDs) في قواعد البيانات. [ 1 ] [ 7 ]

الرسوم البيانية المستحثة

إذا وُجد رسم بياني غير موجه G بحيث،

أنا(X،Z،Y)⇔⟨X،Z،Y⟩جي،{\displaystyle I(X,Z,Y)\Leftrightarrow \langle X,Z,Y\rangle _{G},}

عندئذٍ يُطلق على الرسم البياني المُستحث اسم الرسم البياني المُستحث. بعبارة أخرى، يوجد رسم بياني غير مُوجَّه G بحيث تنعكس كل عبارة استقلال في M كفصل رأس في G والعكس صحيح. الشرط الضروري والكافي لكي يكون نموذج التبعية رسمًا بيانيًا مُستحثًا هو أن يُحقق البديهيات التالية: التناظر، والتفكيك، والتقاطع، والاتحاد القوي، والتعدي.

تنص قوانين الاتحاد القوي على أن

أنا(X،Z،Y)⟹أنا(X،Z∪دبليو،Y){\displaystyle I(X,Z,Y)\implies I(X,Z\cup W,Y)}

تنص خاصية التعدي على أن

أنا(X،Z،Y)⟹(∀ γ∉X∪Y∪Z،  أنا(X،Z،γ) أو أنا(γ،Z،Y)){\displaystyle I(X,Z,Y)\implies \left(\forall ~\gamma \notin X\cup Y\cup Z,~~I(X,Z,\gamma ){\text{ or }}I(\gamma ,Z,Y)\right)}

تشكل بديهيات التناظر، والتفكيك، والتقاطع، والاتحاد القوي، والتعدي، توصيفًا كاملاً للرسوم البيانية غير الموجهة. [ 9 ]

الجرافويدات المستحثة بواسطة DAG

يُطلق على الرسم البياني اسم الرسم البياني الموجه غير الدوري (DAG) إذا وُجد رسم بياني موجه غير دوري D بحيثأنا(X،Z،Y)⇔⟨X،Z،Y⟩د{\displaystyle I(X,Z,Y)\Leftrightarrow \langle X,Z,Y\rangle _{D}}أين⟨X،Z،Y⟩د{\displaystyle \langle X,Z,Y\rangle _{D}}يرمز إلى الفصل الاتجاهي في D. يوسع الفصل الاتجاهي ( حيث يشير الحرف d إلى "الاتجاهي") مفهوم فصل الرؤوس من الرسوم البيانية غير الموجهة إلى الرسوم البيانية الموجهة غير الدورية. يسمح هذا بقراءة الاستقلالات الشرطية من بنية الشبكات البايزية . مع ذلك، لا يمكن وصف الاستقلالات الشرطية في الرسم البياني الموجه غير الدوري وصفًا كاملًا بمجموعة محدودة من البديهيات. [ 10 ]

الإدماج والبناء

تُحتوى الرسوم البيانية الجزئية المُستحثة بواسطة الرسوم البيانية والرسوم البيانية الموجهة غير الدورية (DAGs) ضمن الرسوم البيانية الجزئية الاحتمالية. [ 11 ] وهذا يعني أنه لكل رسم بياني G، يوجد توزيع احتمالي P بحيث يكون كل استقلال شرطي في P ممثلاً في G ، والعكس صحيح. وينطبق الأمر نفسه على الرسوم البيانية الموجهة غير الدورية. مع ذلك، توجد توزيعات احتمالية ليست رسومًا بيانية جزئية، وعلاوة على ذلك، لا توجد مجموعة بديهيات محدودة للاعتمادات الشرطية الاحتمالية. [ 12 ]

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

  1. رتب المتغيرات بترتيب عشوائي 1، 2، ...، i، ...، N ، وابدأ بـ i  =  1،
  2. اختر لكل عقدة i مجموعة من العقد PA i بحيث تكون i مستقلة عن جميع العقد السابقة لها، 1، 2، ...، i − 1، بشرط PA i .  
  3. ارسم أسهمًا من PA i إلى i واستمر.

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

مراجع

  1. 1 2 3 4 5 بيرل، جوديا؛ باز، عزاريا (1985). "الرسوم البيانية: منطق قائم على الرسم البياني للاستدلال حول علاقات الصلة" (PDF) .
  2. ↑ داويد، أ. فيليب (1979). "الاستقلال الشرطي في النظرية الإحصائية". مجلة الجمعية الإحصائية الملكية، السلسلة ب : 1-31 .
  3. ↑ سبون، وولفغانغ (1980). "الاستقلال العشوائي، والاستقلال السببي، وقابلية الحماية" . مجلة المنطق الفلسفي . 9 : 73-99 . doi : 10.1007/bf00258078 .
  4. ↑ بيرل، جوديا (1986). "الاندماج والانتشار والهيكلة في شبكات المعتقدات". الذكاء الاصطناعي . 29 (3): 241-288 . doi : 10.1016/0004-3702(86)90072-x .
  5. ↑ فيرما، توماس؛ بيرل، جوديا (1988). "الشبكات السببية: الدلالات والتعبيرية". وقائع ورشة العمل الرابعة حول عدم اليقين في الذكاء الاصطناعي : 352-359 .
  6. ↑ لوريتزن، إس إل (1996). النماذج الرسومية . أكسفورد: مطبعة كلارندون.
  7. 1 2 3 4 جيجر، دان (1990). "الرسوم البيانية: إطار نوعي للاستدلال الاحتمالي" (أطروحة دكتوراه، تقرير فني R-142، قسم علوم الحاسوب، جامعة كاليفورنيا، لوس أنجلوس) .
  8. 1 2 بيرل، جوديا (1988). الاستدلال الاحتمالي في الأنظمة الذكية: شبكات الاستدلال المعقول . مورغان كوفمان.
  9. ↑ أ. باز، ج. بيرل، و س. أور، "توصيف جديد للرسوم البيانية بناءً على علاقات الاعتراض" مجلة نظرية الرسم البياني، المجلد 22، العدد 2، 125-136، 1996.
  10. ↑ جيجر، د. (1987). "عدم إمكانية وضع بديهيات للتبعيات في الرسوم البيانية الموجهة غير الدورية" (ملف PDF) . تقرير تقني لعلوم الحاسوب بجامعة كاليفورنيا في لوس أنجلوس R-83 .
  11. ↑ جيجر، د.؛ بيرل، ج. (1993). "الخصائص المنطقية والخوارزمية للاستقلال الشرطي والنماذج البيانية". حوليات الإحصاء . 21 (4): 2001-2021 . CiteSeerX 10.1.1.295.2043 . doi : 10.1214/aos/1176349407 . 
  12. ↑ ستوديني، م. (1992). كوبيك، س.؛ فيسك، ج. أ. (محرران). "علاقات الاستقلال الشرطي ليس لها توصيف كامل محدود". نظرية المعلومات، دوال القرار الإحصائية والعمليات العشوائية. وقائع المؤتمر الحادي عشر في براغ . ب . دوردريخت: كلوير: 377-396 .
  13. ↑ فيرما، ت.؛ بيرل، ج. (1990). شاختر، ر.؛ ليفيت، ت.س.؛ كانال، ل.ن. (محررون). "الشبكات السببية: الدلالات والتعبيرية". عدم اليقين في الذكاء الاصطناعي 4. دار نشر إلسيفير للعلوم: 69-76 .