الرسم البياني للعوامل

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

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

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

تعريف

الرسم البياني للعوامل هو رسم بياني ثنائي الأجزاء يمثل تحليل دالة إلى عواملها. بفرض تحليل دالة إلى عواملهاز(X1،X2،...،Xن){\displaystyle g(X_{1},X_{2},\dots ,X_{n})}،

ز(X1،X2،...،Xن)=∏ج=1موج(Sج)،{\displaystyle g(X_{1},X_{2},\dots ,X_{n})=\prod _{j=1}^{m}f_{j}(S_{j}),}

أينSج⊆{X1،X2،...،Xن}{\displaystyle S_{j}\subseteq \{X_{1},X_{2},\dots ,X_{n}\}}، الرسم البياني المقابل للعواملجي=(X،F،هـ){\displaystyle G=(X,F,E)}يتكون من رؤوس متغيرة X={X1،X2،...،Xن}{\displaystyle X=\{X_{1},X_{2},\dots ,X_{n}\}}، رؤوس العاملF={و1،و2،...،وم}{\displaystyle F=\{f_{1},f_{2},\dots ,f_{m}\}}والحوافهـ{\displaystyle E}تعتمد الحواف على التحليل كما يلي: توجد حافة غير موجهة بين رأس العاملوج{\displaystyle f_{j}}ورأس متغيرXك{\displaystyle X_{k}}لوXك∈Sج{\displaystyle X_{k}\in S_{j}}يُفترض ضمنيًا أن الدالة ذات قيم حقيقية :ز(X1،X2،...،Xن)∈R{\displaystyle g(X_{1},X_{2},\dots ,X_{n})\in \mathbb {R} }.

يمكن دمج مخططات العوامل مع خوارزميات تمرير الرسائل لحساب خصائص معينة للدالة بكفاءةز(X1،X2،...،Xن){\displaystyle g(X_{1},X_{2},\dots ,X_{n})}، مثل التوزيعات الهامشية .

أمثلة

مثال على رسم بياني للعوامل

لنفترض دالة يمكن تحليلها إلى عوامل كما يلي:

ز(X1،X2،X3)=و1(X1)و2(X1،X2)و3(X1،X2)و4(X2،X3){\displaystyle g(X_{1},X_{2},X_{3})=f_{1}(X_{1})f_{2}(X_{1},X_{2})f_{3}(X_{1},X_{2})f_{4}(X_{2},X_{3})}،

مع وجود رسم بياني للعوامل المقابل موضح على اليمين. لاحظ أن الرسم البياني للعوامل يحتوي على دورة . إذا قمنا بدمجو2(X1،X2)و3(X1،X2){\displaystyle f_{2}(X_{1},X_{2})f_{3}(X_{1},X_{2})}إذا تم تحويل عامل واحد إلى رسم بياني للعوامل، فسيكون الرسم البياني الناتج عبارة عن شجرة . وهذا تمييز مهم، لأن خوارزميات تمرير الرسائل عادة ما تكون دقيقة للأشجار، ولكنها تقريبية فقط للرسوم البيانية التي تحتوي على دورات.

تمرير الرسائل على مخططات العوامل

تُعد خوارزمية المجموع والضرب من خوارزميات تمرير الرسائل الشائعة على الرسوم البيانية العاملية، وهي تحسب بكفاءة جميع التوزيعات الهامشية للمتغيرات الفردية للدالة. وعلى وجه الخصوص، التوزيع الهامشي للمتغيرXك{\displaystyle X_{k}}يُعرَّف بأنه

زك(Xك)=∑Xك¯ز(X1،X2،...،Xن){\displaystyle g_{k}(X_{k})=\sum _{X_{\bar {k}}}g(X_{1},X_{2},\dots ,X_{n})}

حيث الترميزXك¯{\displaystyle X_{\bar {k}}}يعني ذلك أن عملية الجمع تشمل جميع المتغيرات، باستثناءXك{\displaystyle X_{k}}تُحسب رسائل خوارزمية الجمع والضرب نظريًا في الرؤوس وتُمرر عبر الحواف. الرسالة من أو إلى رأس متغير هي دائمًا دالة لهذا المتغير. على سبيل المثال، عندما يكون المتغير ثنائيًا، يمكن تمثيل الرسائل على الحواف المتصلة بالرأس المقابل كمتجهات طولها 2: العنصر الأول هو الرسالة عند تقييمها بـ 0، والعنصر الثاني هو الرسالة عند تقييمها بـ 1. عندما ينتمي المتغير إلى حقل الأعداد الحقيقية ، يمكن أن تكون الرسائل دوالًا عشوائية، ويجب توخي الحذر الشديد في تمثيلها.

عمليًا، تُستخدم خوارزمية الجمع والضرب للاستدلال الإحصائي ، حيثز(X1،X2،...،Xن){\displaystyle g(X_{1},X_{2},\dots ,X_{n})}هو توزيع مشترك أو دالة احتمالية مشتركة ، ويعتمد التحليل على الاستقلال الشرطي بين المتغيرات.

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

انظر أيضاً

مراجع

للمزيد من القراءة