حقل ماركوف العشوائي

في مجال الفيزياء والاحتمالات ، يُعرف حقل ماركوف العشوائي ( MRF )، أو شبكة ماركوف ، أو النموذج البياني غير الموجه ، بأنه مجموعة من المتغيرات العشوائية التي تتمتع بخاصية ماركوف، ويتم وصفها بواسطة رسم بياني غير موجه . بعبارة أخرى، يُقال إن الحقل العشوائي هو حقل ماركوف عشوائي إذا استوفى خصائص ماركوف. ينبع هذا المفهوم من نموذج شيرينغتون-كيركباتريك . ^{[ 1 ]}

تُشبه شبكة ماركوف، أو حقل ماركوف العشوائي (MRF)، شبكة بايز في تمثيلها للعلاقات؛ ويكمن الاختلاف في أن شبكات بايز موجهة وغير دورية ، بينما شبكات ماركوف غير موجهة وقد تكون دورية. وبالتالي، تستطيع شبكة ماركوف تمثيل بعض العلاقات التي لا تستطيع شبكة بايز تمثيلها (مثل العلاقات الدورية )؛ في المقابل، لا تستطيع تمثيل بعض العلاقات التي تستطيع شبكة بايز تمثيلها (مثل العلاقات المستحثة ). قد يكون الرسم البياني الأساسي لحقل ماركوف العشوائي محدودًا أو غير محدود.

عندما تكون دالة الكثافة الاحتمالية المشتركة للمتغيرات العشوائية موجبة تمامًا، يُشار إليها أيضًا باسم حقل جيبس ​​العشوائي ، لأنه، وفقًا لنظرية هامرسلي-كليفورد ، يمكن تمثيلها بمقياس جيبس ​​لدالة طاقة مناسبة (معرفة محليًا). يُعد نموذج إيزينغ النموذج الأولي لحقل ماركوف العشوائي ؛ في الواقع، تم تقديم حقل ماركوف العشوائي كإطار عام لنموذج إيزينغ. ^{[ 2 ]} في مجال الذكاء الاصطناعي ، يُستخدم حقل ماركوف العشوائي لنمذجة مهام متنوعة منخفضة إلى متوسطة المستوى في معالجة الصور ورؤية الحاسوب . ^{[ 3 ]}

بالنظر إلى رسم بياني غير موجه${\displaystyle G=(V,E)}$، مجموعة من المتغيرات العشوائية${\displaystyle X=(X_{v})_{v\in V}}$مفهرسة بواسطة${\displaystyle V}$تشكيل حقل ماركوف عشوائي بالنسبة إلى${\displaystyle G}$إذا كانت تحقق خصائص ماركوف المحلية:

خاصية ماركوف الثنائية: أي متغيرين غير متجاورين مستقلان شرطياً بالنظر إلى جميع المتغيرات الأخرى:

${\displaystyle X_{u}\perp \!\!\!\perp X_{v}\mid X_{V\smallsetminus \{u,v\}}}$

خاصية ماركوف المحلية: يكون المتغير مستقلاً شرطياً عن جميع المتغيرات الأخرى بالنظر إلى جيرانه:

${\displaystyle X_{v}\perp \!\!\!\perp X_{V\smallsetminus \operatorname {N} [v]}\mid X_{\operatorname {N} (v)}}$

أين${\textstyle \operatorname {N} (v)}$هي مجموعة جيران${\displaystyle v}$، و${\displaystyle \operatorname {N} [v]=v\cup \operatorname {N} (v)}$هو الحي المغلق لـ${\displaystyle v}$.

خاصية ماركوف العالمية: أي مجموعتين جزئيتين من المتغيرات مستقلتان شرطياً بالنظر إلى مجموعة جزئية فاصلة:

${\displaystyle X_{A}\perp \!\!\!\perp X_{B}\mid X_{S}}$

حيث كل مسار من عقدة في${\displaystyle A}$إلى عقدة في${\displaystyle B}$يمر عبر${\displaystyle S}$.

تُعد خاصية ماركوف العالمية أقوى من خاصية ماركوف المحلية، والتي بدورها أقوى من خاصية ماركوف الثنائية. ^{[ 4 ]} ومع ذلك، فإن خصائص ماركوف الثلاث المذكورة أعلاه متكافئة بالنسبة للتوزيعات الموجبة ^{[ 5 ]} (أي تلك التي تُسند احتمالات غير صفرية فقط للمتغيرات المرتبطة بها).

تتضح العلاقة بين خصائص ماركوف الثلاث بشكل خاص في الصيغة التالية:

• ثنائيًا: لأي${\displaystyle i,j\in V}$غير متساوٍ أو متجاور،${\displaystyle X_{i}\perp \!\!\!\perp X_{j}|X_{V\smallsetminus \{i,j\}}}$.
• محلي: لأي${\displaystyle i\in V}$و${\displaystyle J\subset V}$لا يحتوي على أو مجاور لـ${\displaystyle i}$،${\displaystyle X_{i}\perp \!\!\!\perp X_{J}|X_{V\smallsetminus (\{i\}\cup J)}}$.
• عالمي: لأي${\displaystyle I,J\subset V}$غير متقاطعة أو متجاورة،${\displaystyle X_{I}\perp \!\!\!\perp X_{J}|X_{V\smallsetminus (I\cup J)}}$.

بما أن خاصية ماركوف لتوزيع احتمالي عشوائي قد يكون من الصعب إثباتها، فإن فئة شائعة الاستخدام من حقول ماركوف العشوائية هي تلك التي يمكن تحليلها وفقًا لمجموعات الرسم البياني.

بافتراض مجموعة من المتغيرات العشوائية${\displaystyle X=(X_{v})_{v\in V}}$، يترك${\displaystyle P(X=x)}$ليكن احتمال تكوين حقل معين${\displaystyle x}$في${\displaystyle X}$-إنه،${\displaystyle P(X=x)}$هي احتمالية العثور على المتغيرات العشوائية${\displaystyle X}$تتخذ قيمة محددة${\displaystyle x}$. لأن${\displaystyle X}$هي مجموعة، احتمال${\displaystyle x}$ينبغي فهم ذلك على أنه يتعلق بالتوزيع المشترك لـ${\displaystyle X_{v}}$.

إذا أمكن تحليل هذه الكثافة المشتركة على مجموعات من${\displaystyle G}$مثل

${\displaystyle P(X=x)=\prod _{C\in \operatorname {cl} (G)}\varphi _{C}(x_{C})}$

ثم${\displaystyle X}$يشكل حقل ماركوف عشوائيًا بالنسبة إلى${\displaystyle G}$. هنا،${\displaystyle \operatorname {cl} (G)}$هي مجموعة الزمر من${\displaystyle G}$يكون التعريف مكافئًا إذا تم استخدام الزمر القصوى فقط. الدوال${\displaystyle \varphi _{C}}$يُشار إليها أحيانًا باسم كمونات العامل أو كمونات الزمرة . مع ذلك، تجدر الإشارة إلى وجود مصطلحات متضاربة مستخدمة: فكلمة " كمون" تُستخدم غالبًا للإشارة إلى لوغاريتم${\displaystyle \varphi _{C}}$وذلك لأنه في الميكانيكا الإحصائية ،${\displaystyle \log(\varphi _{C})}$لها تفسير مباشر على أنها طاقة الوضع لتكوين ما${\displaystyle x_{C}}$.

بعض نماذج ماركوف العشوائية لا تتحلل إلى عوامل: يمكن إنشاء مثال بسيط على دورة من 4 عقد ذات طاقات لانهائية، أي تكوينات ذات احتمالات صفرية، ^{[ 6 ]} حتى لو سمح المرء، بشكل أكثر ملاءمة، للطاقات اللانهائية بالتأثير على الرسم البياني الكامل على${\displaystyle V}$[ ^{7 ]​}

يمكن تحليل نماذج ماركوف العشوائية (MRF) إذا تحقق شرط واحد على الأقل من الشروط التالية:

• الكثافة موجبة تمامًا (بحسب نظرية هامرسلي-كليفورد )
• الرسم البياني هو رسم وتري (بموجب التكافؤ مع الشبكة البايزية )

عندما يكون هذا التحليل موجودًا، فمن الممكن إنشاء رسم بياني للعوامل للشبكة.

يمكن كتابة أي حقل ماركوف عشوائي موجب كعائلة أسية في شكل قانوني مع دوال مميزة${\displaystyle f_{k}}$بحيث يمكن كتابة التوزيع المشترك الكامل على النحو التالي

${\displaystyle P(X=x)={\frac {1}{Z}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})\right)}$

حيث الترميز

${\displaystyle w_{k}^{\top }f_{k}(x_{\{k\}})=\sum _{i=1}^{N_{k}}w_{k,i}\cdot f_{k,i}(x_{\{k\}})}$

هو ببساطة حاصل ضرب نقطي على تكوينات الحقول، و Z هي دالة التقسيم :

${\displaystyle Z=\sum _{x\in {\mathcal {X}}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})\right).}$

هنا،${\displaystyle {\mathcal {X}}}$يشير إلى مجموعة جميع القيم الممكنة لجميع المتغيرات العشوائية في الشبكة. عادةً ما تكون دوال الميزات${\displaystyle f_{k,i}}$يتم تعريفها بحيث تكون مؤشرات على تكوين الزمرة، أي${\displaystyle f_{k,i}(x_{\{k\}})=1}$لو${\displaystyle x_{\{k\}}}$يتوافق هذا النموذج مع التكوين الممكن رقم i للزمرة رقم k، و0 فيما عدا ذلك. هذا النموذج مكافئ لنموذج تحليل الزمر المذكور أعلاه، إذا${\displaystyle N_{k}=|\اسم المشغل {dom} (C_{k})|}$هي عدد عناصر المجموعة، ووزن السمة${\displaystyle f_{k,i}}$يتوافق مع لوغاريتم عامل الزمرة المقابل، أي${\displaystyle w_{k,i}=\log \varphi (c_{k,i})}$، أين${\displaystyle c_{k,i}}$يمثل التكوين المحتمل رقم i للزمرة رقم k ، أي القيمة رقم i في نطاق الزمرة${\displaystyle C_{k}}$.

يُطلق على الاحتمال P غالبًا اسم مقياس جيبس. ولا يكون هذا التعبير عن حقل ماركوف كنموذج لوجستي ممكنًا إلا إذا كانت جميع عوامل الزمرة غير صفرية، أي إذا لم يكن أي من عناصر${\displaystyle {\mathcal {X}}}$يتم تعيين احتمال 0. وهذا يسمح بتطبيق تقنيات من جبر المصفوفات، على سبيل المثال أن أثر المصفوفة هو لوغاريتم المحدد ، مع تمثيل المصفوفة للرسم البياني الناتج عن مصفوفة وقوع الرسم البياني .

تكمن أهمية دالة التقسيم Z في إمكانية تعميم العديد من مفاهيم الميكانيكا الإحصائية ، مثل الإنتروبيا ، مباشرةً على حالة شبكات ماركوف، مما يُتيح فهمًا بديهيًا لها. إضافةً إلى ذلك، تسمح دالة التقسيم بتطبيق الطرق التباينية لحل المسألة: إذ يُمكن ربط قوة دافعة بواحد أو أكثر من المتغيرات العشوائية، واستكشاف استجابة الشبكة لهذا الاضطراب . على سبيل المثال، يُمكن إضافة حد دافع J_{_v} ، لكل رأس v في الرسم البياني، إلى دالة التقسيم للحصول على:

${\displaystyle Z[J]=\sum _{x\in {\mathcal {X}}}\exp \left(\sum _{k}w_{k}^{\top }f_{k}(x_{\{k\}})+\sum _{v}J_{v}x_{v}\right)}$

إن التفاضل الرسمي بالنسبة إلى J _v يعطي القيمة المتوقعة للمتغير العشوائي X _v المرتبط بالرأس v :

${\displaystyle E[X_{v}]={\frac {1}{Z}}\left.{\frac {\partial Z[J]}{\partial J_{v}}}\right|_{J_{v}=0}.}$

يتم حساب دوال الارتباط بنفس الطريقة؛ الارتباط بين نقطتين هو:

${\displaystyle C[X_{u},X_{v}]={\frac {1}{Z}}\left.{\frac {\partial ^{2}Z[J]}{\partial J_{u}\,\partial J_{v}}}\right|_{J_{u}=0,J_{v}=0}.}$

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

كما هو الحال في الشبكة البايزية ، يمكن حساب التوزيع الشرطي لمجموعة من العقد${\displaystyle V'=\{v_{1},\ldots ,v_{i}\}}$إعطاء قيم لمجموعة أخرى من العقد${\displaystyle W'=\{w_{1},\ldots ,w_{j}\}}$في حقل ماركوف العشوائي عن طريق جمع جميع التعيينات الممكنة إلى${\displaystyle u\notin V',W'}$يُطلق على هذا الاستدلال الدقيق . مع ذلك، يُعدّ الاستدلال الدقيق مسألةً كاملةً من فئة #P ، وبالتالي يصعب حلّها حسابيًا في الحالة العامة. غالبًا ما تكون تقنيات التقريب، مثل سلسلة ماركوف مونت كارلو ونشر الاعتقاد الحلقي، أكثر جدوى من الناحية العملية. تمتلك بعض الفئات الفرعية المحددة من حقول ماركوف العشوائية، مثل الأشجار (انظر شجرة تشاو-ليو )، خوارزميات استدلال ذات زمن متعدد الحدود؛ ويُعدّ اكتشاف هذه الفئات الفرعية موضوعًا بحثيًا نشطًا. توجد أيضًا فئات فرعية من حقول ماركوف العشوائية تسمح باستدلال MAP الفعال ، أو التعيين الأكثر احتمالًا؛ ومن أمثلة هذه الفئات الشبكات الترابطية. ^{[ 9 ] [ 10 ]} فئة فرعية أخرى مثيرة للاهتمام هي فئة النماذج القابلة للتحليل (عندما يكون الرسم البياني وتريًا ): بوجود صيغة مغلقة لتقدير الاحتمال الأقصى ، يُمكن اكتشاف بنية متسقة لمئات المتغيرات. ^{[ 11 ]}

أحد أبرز أنواع حقول ماركوف العشوائية هو الحقل العشوائي الشرطي، حيث يمكن أن يكون كل متغير عشوائي مشروطًا أيضًا بمجموعة من الملاحظات العامة.${\displaystyle o}$في هذا النموذج، كل وظيفة${\displaystyle \varphi _{k}}$هي عبارة عن خريطة من جميع التعيينات إلى كل من المجموعة k والملاحظات${\displaystyle o}$إلى الأعداد الحقيقية غير السالبة. قد يكون هذا الشكل من شبكة ماركوف أكثر ملاءمة لإنتاج مصنفات تمييزية ، والتي لا تُنمذج التوزيع على المشاهدات. تم اقتراح نماذج الحقول العشوائية الشرطية (CRFs) من قِبل جون د. لافيرتي ، وأندرو ماكالوم ، وفرناندو سي إن بيريرا في عام 2001. ^{[ 12 ]}

تُستخدم حقول ماركوف العشوائية في مجالات متنوعة، بدءًا من رسومات الحاسوب ورؤية الحاسوب، ^{[ 13 ]} والتعلم الآلي وعلم الأحياء الحاسوبي ، ^{[ 2 ] [ 14 ]} واسترجاع المعلومات . ^{[ 15 ]} تُستخدم حقول ماركوف العشوائية في معالجة الصور لتوليد الأنسجة، نظرًا لقدرتها على إنشاء نماذج صور مرنة وعشوائية. في نمذجة الصور، تتمثل المهمة في إيجاد توزيع مناسب لشدة الصورة، حيث تعتمد الملاءمة على نوع المهمة، وتتميز حقول ماركوف العشوائية بمرونة كافية لاستخدامها في توليف الصور والأنسجة، وضغط الصور واستعادتها، وتجزئة الصور ، واستنتاج الصور ثلاثية الأبعاد من الصور ثنائية الأبعاد، وتسجيل الصور، وتوليف الأنسجة ، وتحسين الدقة ، والمطابقة المجسمة ، واسترجاع المعلومات . كما استُخدمت الأساليب الإحصائية الميكانيكية لتحليل نماذج حقول ماركوف العشوائية لاستعادة الصور باستخدام بايز؛ حيث درس كازويوكي تاناكا وتسويوشي هوريغوتشي نماذج حقول ماركوف العشوائية القابلة للحل لاستعادة الصور الملونة، والأساليب الحسابية التكرارية ذات الصلة لاستعادة الصور الرمادية. ^{[ 16 ] [ 17 ]} يمكن استخدامها لحل مشاكل رؤية الحاسوب المختلفة، والتي يمكن صياغتها كمشاكل تقليل الطاقة أو مشاكل تتطلب تمييز مناطق مختلفة باستخدام مجموعة من السمات المميزة، ضمن إطار حقل ماركوف العشوائي، للتنبؤ بفئة المنطقة. ^{[ 18 ]} كانت حقول ماركوف العشوائية تعميمًا لنموذج إيزينغ، ومنذ ذلك الحين، استُخدمت على نطاق واسع في عمليات التحسين التوافقي والشبكات.