خوارزمية أخذ العينات المتداخلة

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

يمكن استخدام نظرية بايز لاختيار النموذج ، حيث يكون لدى المرء زوج من النماذج المتنافسة${\displaystyle M_{1}}$و${\displaystyle M_{2}}$للحصول على البيانات${\displaystyle D}$قد يكون أحد هذين الاحتمالين صحيحًا (مع أن أيّهما غير معروف)، لكن لا يمكن أن يكون كلاهما صحيحًا في الوقت نفسه. يوفر اختيار النموذج البايزي طريقة لتقييم عامل بايز ، الذي يحدد الميزة النسبية لكل نموذج.

الاحتمال اللاحق لـ${\displaystyle M_{1}}$يمكن حسابها على النحو التالي:

${\displaystyle {\begin{aligned}P(M_{1}\mid D)&={\frac {P(D\mid M_{1})P(M_{1})}{P(D)}}\\&={\frac {P(D\mid M_{1})P(M_{1})}{P(D\mid M_{1})P(M_{1})+P(D\mid M_{2})P(M_{2})}}\\&={\frac {1}{1+{\frac {P(D\mid M_{2})}{P(D\mid M_{1})}}{\frac {P(M_{2})}{P(M_{1})}}}}\end{aligned}}}$

الاحتمالات المسبقة${\displaystyle M_{1}}$و${\displaystyle M_{2}}$هي معروفة مسبقًا، حيث يختارها الباحث مسبقًا. ومع ذلك، فإن عامل بايز المتبقي${\displaystyle P(D\mid M_{2})/P(D\mid M_{1})}$ليس من السهل تقييمه، لأنه يتطلب عموماً استبعاد المعلمات المزعجة. عموماً،${\displaystyle M_{1}}$يحتوي على مجموعة من المعلمات التي يمكن تجميعها معًا وتسميتها${\displaystyle \theta }$، و${\displaystyle M_{2}}$له متجه خاص به من المعاملات التي قد تكون ذات أبعاد مختلفة، ولكنه لا يزال يُطلق عليه اسم${\displaystyle \theta }$التهميش من أجل${\displaystyle M_{1}}$يكون

${\displaystyle P(D\mid M_{1})=\int d\theta \,P(D\mid \theta ,M_{1})P(\theta \mid M_{1})}$

وكذلك بالنسبة لـ${\displaystyle M_{2}}$غالبًا ما يكون هذا التكامل غير قابل للحل التحليلي، وفي هذه الحالات، من الضروري استخدام خوارزمية عددية لإيجاد قيمة تقريبية. وقد طوّر جون سكيلينج خوارزمية أخذ العينات المتداخلة خصيصًا لتقريب هذه التكاملات الهامشية، ولها ميزة إضافية تتمثل في توليد عينات من التوزيع الاحتمالي اللاحق.${\displaystyle P(\theta \mid D,M_{1})}$[ ^{2 ]} إنه بديل للأساليب الواردة في الأدبيات البايزية ^{[ 3 ]} مثل أخذ العينات الجسرية وأخذ العينات الدفاعية المهمة ^.

فيما يلي نسخة مبسطة من خوارزمية أخذ العينات المتداخلة، متبوعة بوصف لكيفية حساب كثافة الاحتمال الهامشي.${\displaystyle Z=P(D\mid M)}$أين${\displaystyle M}$يكون${\displaystyle M_{1}}$أو${\displaystyle M_{2}}$:

ابدأ بـ${\displaystyle N}$نقاط${\displaystyle \theta _{1},\ldots ,\theta _{N}}$تم أخذ العينات من البيانات السابقة. لـ${\displaystyle i=1}$ل${\displaystyle j}$يتم تحديد عدد التكرارات j عن طريق التخمين. ${\displaystyle L_{i}:=\min(}$القيم الحالية لاحتمالية النقاط${\displaystyle )}$؛ ${\displaystyle X_{i}:=\exp(-i/N);}$${\displaystyle w_{i}:=X_{i-1}-X_{i}}$${\displaystyle Z:=Z+L_{i}\cdot w_{i};}$ احفظ النقطة ذات الاحتمالية الأقل كنقطة عينة مع وزن.${\displaystyle w_{i}}$. قم بتحديث النقطة ذات الاحتمالية الأقل عن طريق أخذ عينة من التوزيع الاحتمالي المسبق المقيد بالاحتمالات المذكورة أعلاه.${\displaystyle L_{i}}$على سبيل المثال، مع سلسلة ماركوف مونت كارلو . نهاية الإرجاع${\displaystyle Z}$؛

في كل تكرار،${\displaystyle X_{i}}$يمثل هذا تقديرًا لكمية الكتلة السابقة التي يغطيها الحجم الفائق في فضاء المعلمات لجميع النقاط ذات الاحتمالية الأكبر من${\displaystyle \theta _{i}}$عامل الوزن${\displaystyle w_{i}}$هو تقدير لكمية الكتلة السابقة التي تقع بين سطحين متداخلين${\displaystyle \{\theta \mid P(D\mid \theta ,M)=P(D\mid \theta _{i-1},M)\}}$و${\displaystyle \{\theta \mid P(D\mid \theta ,M)=P(D\mid \theta _{i},M)\}}$خطوة التحديث${\displaystyle Z:=Z+L_{i}w_{i}}$يحسب المجموع على${\displaystyle i}$ل${\displaystyle L_{i}w_{i}}$لتقريب التكامل عدديًا

${\displaystyle {\begin{aligned}P(D\mid M)&=\int P(D\mid \theta ,M)P(\theta \mid M)\,d\theta \\&=\int P(D\mid \theta ,M)\,dP(\theta \mid M)\end{aligned}}}$

في الحد${\displaystyle j\to \infty }$، هذا المُقدِّر لديه انحياز إيجابي من الرتبة${\displaystyle 1/N}$^{[ 4 ]} والتي يمكن إزالتها باستخدام${\displaystyle (1-1/N)}$بدلاً من${\displaystyle \exp(-1/N)}$في الخوارزمية المذكورة أعلاه.

الفكرة هي تقسيم نطاق${\displaystyle f(\theta )=P(D\mid \theta ,M)}$وقم بالتقدير، لكل فترة${\displaystyle [f(\theta _{i-1}),f(\theta _{i})]}$ما مدى احتمالية أن يتم اختيار عشوائيًا مسبقًا${\displaystyle \theta }$سيتم ربطها بهذه الفترة. يمكن اعتبار هذا بمثابة طريقة بايزية لتنفيذ تكامل لوبيغ عدديًا . ^{[ 5 ] [ 6 ]}

يمكن تحديث النقطة ذات الاحتمالية الأقل باستخدام بعض خطوات سلسلة ماركوف مونت كارلو وفقًا للتوزيع الاحتمالي المسبق، مع قبول الخطوات التي تحافظ على الاحتمالية أعلى من ذلك.${\displaystyle L_{i}}$لا يحدد الإجراء الأصلي الذي وضعه سكيلينج (المذكور أعلاه في الشفرة الزائفة ) الخوارزمية المحددة التي ينبغي استخدامها لاختيار نقاط جديدة ذات احتمالية أفضل، ولكن تم تطوير العديد من الخوارزميات. ^{[ 7 ]}

تختار أمثلة برمجية خاصة بسكيلينغ (مثل المثال الوارد في سيفيا وسكيلينغ (2006)، ^{[ 8 ]} والمتاح على موقع سكيلينغ الإلكتروني ) نقطة موجودة عشوائيًا، ثم تختار نقطة قريبة منها بناءً على مسافة عشوائية من تلك النقطة؛ فإذا كان الاحتمال أفضل، تُقبل النقطة، وإلا تُرفض وتُكرر العملية. لاحقًا، طُوّرت مجموعة متنوعة من خوارزميات ماركوف مونت كارلو (MCMC) المصممة خصيصًا لأخذ العينات المتداخلة، بما في ذلك أخذ العينات بالشرائح، ^{[ 5 ]} التي اشتهرت بفضل برنامج PolyChord، وخوارزمية مونت كارلو الهاميلتونية المقيدة . ^{[ 9 ]}

يعتمد خط بديل من الخوارزميات على أخذ العينات بالرفض . وقد وجد موخيرجي وآخرون (2006) ^{[ 10 ]} معدلات قبول أعلى عن طريق اختيار نقاط عشوائيًا داخل شكل بيضاوي مرسوم حول النقاط الموجودة؛ وقد تم تحسين هذه الفكرة بواسطة خوارزمية MultiNest ^{[ 11 ]} التي تتعامل مع التوزيعات الاحتمالية الخلفية متعددة الأنماط بشكل أفضل باستخدام أشكال بيضاوية متعددة مبنية من تجميع النقاط النشطة. يمكن أن تكون طرق الرفض فعالة حتى 20-30 بُعدًا. ^{[ 7 ]}

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

• توجد أمثلة بسيطة بلغات C أو R أو Python على موقع جون سكيلينج الإلكتروني .
• يوجد على موقع Hackage نسخة مكتوبة بلغة Haskell من الأكواد البسيطة المذكورة أعلاه .
• تم وصف مثال مكتوب بلغة R مصمم أصلاً لمطابقة الأطياف على موقع Bojan Nikolic الإلكتروني وهو متاح على GitHub .
• تُعدّ أداة NestedSampler جزءًا من مجموعة أدوات بايثون BayesicFitting ^{[ 12 ]} لتركيب النماذج العامة وحساب الأدلة. وهي متاحة على GitHub .
• يوجد تطبيق مكتوب بلغة C++ ، باسم DIAMONDS، على موقع GitHub .
• يوجد على GitHub مثال متوازي عالي الوحدات في لغة بايثون لاستخدامات الفيزياء الإحصائية وفيزياء المادة المكثفة .
• pymatnest هي حزمة برمجية مصممة لاستكشاف منحنى الطاقة لمواد مختلفة، وحساب المتغيرات الديناميكية الحرارية عند درجات حرارة عشوائية، وتحديد مواقع التحولات الطورية، وهي متاحة على GitHub.
• تتيح حزمة برامج MultiNest إمكانية إجراء أخذ عينات متداخلة على التوزيعات الاحتمالية الخلفية متعددة الأنماط. ^{[ 11 ] [ 13 ]} وهي مزودة بواجهات برمجة تطبيقات للغات C++ و Fortran وPython، ومتاحة على GitHub .
• PolyChord هي حزمة برمجية أخرى لأخذ العينات المتداخلة، متاحة على GitHub . تتميز PolyChord بكفاءة حسابية أعلى مع زيادة عدد المعاملات مقارنةً بـ MultiNest، مما يعني أنها أكثر كفاءة في حل المشكلات عالية الأبعاد. ^{[ 14 ]} تتضمن واجهات برمجة تطبيقات لوظائف الاحتمالية المكتوبة بلغات Python وFortran وC وC++. يمكن استخدام PolyChord بالتزامن مع Cobaya، ^{[ 15 ]} وهي مكتبة برمجية مبنية على Python لتحليل بايزي للنماذج الفيزيائية الهرمية. تُسهّل Cobaya استكشاف التوزيعات الاحتمالية اللاحقة باستخدام خوارزميات مونت كارلو المختلفة، وتتيح تعظيم العينات وإعادة ترجيحها حسب الأهمية، كما تتضمن واجهات برمجة تطبيقات لبرامج نظرية علم الكونيات ووظائف الاحتمالية.
• NestedSamplers.jl، وهي حزمة Julia لتنفيذ خوارزميات أخذ العينات المتداخلة أحادية ومتعددة الأشكال الإهليلجية موجودة على GitHub .
• Korali هو إطار عمل عالي الأداء لتحديد كمية عدم اليقين والتحسين والتعلم العميق المعزز، والذي يقوم أيضًا بتنفيذ أخذ العينات المتداخلة.
• تُقدّم حزمة برامج UltraNest خوارزمية أخذ عينات ديناميكية متداخلة متعددة الأشكال الإهليلجية، سريعة ومتوافقة مع MPI . كما يُمكن للمستخدم اختيار خوارزميات أخذ عينات الشرائح. البرنامج مكتوب بلغة بايثون، وله واجهات برمجة تطبيقات للغات بايثون، وسي، وفورتران، وآر، وجوليا، وهو متاح على منصة GitHub .

منذ اقتراح أسلوب أخذ العينات المتداخلة عام ٢٠٠٤، استُخدم في العديد من المجالات العلمية، ^{[ ٦ ]} ولا سيما في علم الفلك . اقترحت إحدى الدراسات استخدام هذا الأسلوب لاختيار النماذج الكونية والكشف عن الأجرام السماوية، نظرًا لما يوفره من "مزيج فريد من الدقة والتطبيق العام والجدوى الحسابية". ^{[ ١٠ ]} كما اقتُرح تحسين الخوارزمية للتعامل مع التوزيعات الاحتمالية المتعددة الأنماط كوسيلة للكشف عن الأجرام السماوية في مجموعات البيانات المتاحة. ^{[ ١٣ ]} ومن التطبيقات الأخرى لأخذ العينات المتداخلة مجال تحديث العناصر المحدودة، حيث تُستخدم الخوارزمية لاختيار نموذج العناصر المحدودة الأمثل ، وقد طُبّق ذلك على ديناميكيات الهياكل . ^{[ ١٦ ]} كما استُخدمت هذه الطريقة في مجال نمذجة المواد، حيث يمكن استخدامها لتعلم دالة التوزيع من الميكانيكا الإحصائية واستنباط الخصائص الديناميكية الحرارية . ^{[ ١٧ ]}

طُوِّرت أدوات تشخيصية مُخصصة لأخذ العينات المتداخلة للتحقق من كفاءة عملية أخذ العينات. تشمل هذه الأدوات اختبار U للتأكد من توزيع رتبة احتمالية نقطة الاستبدال توزيعًا منتظمًا بين النقاط الحية، ^{[ 18 ] [ 7 ] ومسافة قفزة مونت كارلو لسلسلة ماركوف، [ 19 ]} ومقارنة اتساق عدة عمليات أخذ عينات متداخلة مستقلة، ^{[ 20 ] [ 21 ]} بما في ذلك عمليات إعادة التشغيل مع زيادة عدد خطوات مونت كارلو لسلسلة ماركوف . كما يُمكن التحقق من الحساب باستخدام تقنيات عامة قابلة للتطبيق، مثل المعايرة القائمة على المحاكاة. ^{[ 22 ]}

يُعدّ أخذ العينات المتداخلة الديناميكية تعميمًا لخوارزمية أخذ العينات المتداخلة، حيث يتم تعديل عدد العينات المأخوذة في مناطق مختلفة من فضاء المعلمات ديناميكيًا لزيادة دقة الحساب إلى أقصى حد. ^{[ 23 ]} وهذا من شأنه أن يُحسّن الدقة والكفاءة الحسابية مقارنةً بخوارزمية أخذ العينات المتداخلة الأصلية، التي لا يُمكن فيها تغيير توزيع العينات، وغالبًا ما تُؤخذ عينات كثيرة في مناطق ذات تأثير ضئيل على دقة الحساب.

تتضمن حزم برامج أخذ العينات المتداخلة الديناميكية المتاحة للجمهور ما يلي:

• dynesty – تطبيق بايثون لأخذ العينات المتداخلة الديناميكية والذي يمكن تنزيله من GitHub . ^{[ 24 ]}
• dyPolyChord: حزمة برمجية يمكن استخدامها مع لغات بايثون وسي++ وفورتران لحساب احتمالية التوزيعات الاحتمالية المسبقة. ^{[ 25 ]} dyPolyChord متوفرة على GitHub .
• UltraNest (انظر أعلاه).

تم تطبيق أسلوب أخذ العينات المتداخلة الديناميكية على مجموعة متنوعة من المشكلات العلمية، بما في ذلك تحليل موجات الجاذبية، ^{[ 26 ]} ورسم خرائط المسافات في الفضاء ^{[ 27 ]} واكتشاف الكواكب الخارجية. ^{[ 28 ]}

• مقارنة النماذج البايزية
• قائمة الخوارزميات