الانتقال إلى المحتوى
العودة إلى نتائج البحث

خوارزمية التوقع-تعظيم (EM)

قدّمه
Dempster, Laird & Rubin
السنة
1977
النوع
Iterative optimization algorithm
العائلة
Estimation

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

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

الفكرة الحدسية وراء الطريقة

تخيل محاولة تعلم قواعد لعبة من خلال مشاهدة لاعبين لا يمكنك رؤية أوراقهم. في كل جولة، تخمن الأوراق التي من المحتمل أن يحملوها بناءً على ما تلاحظه، ثم تحدث نموذجك للقواعد بافتراض أن هذه التخمينات صحيحة. تقوم خوارزمية EM بذلك بالضبط: خطوة E تملأ المعلومات المفقودة احتماليًا باستخدام تقديرات المعلمات الحالية، وخطوة M تعيد ضبط النموذج كما لو كانت هذه القيم المملوءة ملاحظات حقيقية.

التاريخ

تم توحيد الخوارزمية وتسميتها رسميًا بواسطة آرثر ديمبستر ونان لايرد ودونالد روبن في ورقتهم البحثية المنشورة في JRSS-B عام 1977، والتي لا تزال واحدة من أكثر المقالات الإحصائية استشهادًا على الإطلاق. عممت الورقة إجراءات خاصة سابقة تم تطويرها بشكل مستقل لمشاكل البيانات المفقودة المحددة. أنتجت العقود اللاحقة العديد من التوسعات بما في ذلك خوارزميات ECM و ECME و AECM و SEM، مما وسع نطاق التطبيق وسرع التقارب في العديد من الإعدادات العملية.

متى تُستخدم

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

الحدود والاعتبارات

  • التقارب إلى حد أقصى محلي بدلاً من الحد الأقصى العالمي عندما تكون سطح الاحتمالية متعدد الأنماط
  • يمكن أن تظهر تقاربًا بطيئًا جدًا (خطيًا) عندما تكون نسبة المعلومات المفقودة كبيرة
  • تتطلب من المحلل تحديد نموذج البيانات الكامل وتوزيع المتغيرات الكامنة
  • خوارزمية EM القياسية لا توفر مباشرة مصفوفة التباين للبيانات المرصودة للتقديرات؛ هناك حاجة إلى خطوة تكميلية (مثل طريقة لويس أو خوارزمية SEM) لحساب الأخطاء المعيارية

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

نقاط القوة

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

التطبيقات

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

كيف يعمل

كيف يعمل

1

قبل بدء التكرار، يختار المحلل قيمًا ابتدائية للمعلمات غير المعروفة، والتي يُشار إليها بالرمز ثيتا-0 (θ₀). يمكن اختيار هذه القيم عشوائيًا، أو من خلال ملاءمة مبسطة، أو بناءً على معرفة بالمجال. يمكن أن تؤثر جودة التهيئة على الحد الأقصى المحلي الذي تتقارب إليه الخوارزمية، مما يجعل عمليات إعادة التشغيل العشوائية المتعددة ممارسة شائعة.

الصيغة
\text{Choose initial parameter estimates } \theta^{(0)}
2

بالنظر إلى تقدير المعلمة الحالي ثيتا-t (θᵗ)، تحسب خطوة E الدالة Q، وهي القيمة المتوقعة للوغاريتم الاحتمالية للبيانات الكاملة فوق توزيع المتغيرات الكامنة غير المرصودة Z، بشرط البيانات المرصودة X. هذه القيمة المتوقعة تستبدل الكميات غير المعروفة فعليًا بتقديراتها الاحتمالية دون الالتزام بقيمة واحدة مُستنبطة.

الصيغة
Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{Z \mid X, \theta^{(t)}}[\log p(X, Z \mid \theta)]
3

تقوم خطوة M بتعظيم الدالة Q من خطوة E بالنسبة لـ ثيتا (θ)، مما ينتج تقديرًا محدثًا ثيتا-(t+1) (θᵗ⁺¹). نظرًا لأن لوغاريتم الاحتمالية للبيانات الكاملة غالبًا ما يكون أبسط في التعظيم من لوغاريتم الاحتمالية الهامشية للبيانات المرصودة، فإن هذه الخطوة غالبًا ما تكون قابلة للحل حتى عندما لا تكون الاحتمالية القصوى المباشرة كذلك.

الصيغة
\theta^{(t+1)} = \arg\max_{\theta} \, Q(\theta \mid \theta^{(t)})
4

تُكرر خطوتا E و M بالتناوب. بعد كل دورة كاملة، يتم تقييم لوغاريتم الاحتمالية للبيانات المرصودة. يتوقف التكرار عندما ينخفض التغيير في لوغاريتم الاحتمالية (أو في متجه المعلمات) عن قيمة تحمل محددة من قبل المستخدم إبسيلون (ε). أثبت ديمبستر وآخرون أن كل دورة لا يمكن أن تقلل من احتمالية البيانات المرصودة، مما يضمن التقارب المستقر.

الصيغة
\text{Repeat E- and M-steps until } |\ell(\theta^{(t+1)}) - \ell(\theta^{(t)})| < \epsilon

الأخطاء الشائعة

  • استخدام تهيئة عشوائية واحدة يخاطر بالانتهاء عند حد أقصى محلي ضعيف؛ قم دائمًا بتشغيل عمليات إعادة تشغيل متعددة واختر الحل الذي يحقق أعلى احتمالية نهائية
  • الإعلان عن التقارب مبكرًا جدًا عن طريق مراقبة تغيير المعلمات فقط بدلاً من احتمالية البيانات المرصودة يمكن أن يؤدي إلى تقديرات غير دقيقة
  • تطبيق خوارزمية EM عندما تكون البيانات مفقودة بشكل غير عشوائي (MNAR) دون تعديل النموذج يمكن أن يؤدي إلى تحيز منهجي في التقديرات
  • تجاهل مشكلة تبديل التسميات في نماذج الخليط يؤدي إلى تعيينات مكونات غير قابلة للتفسير حتى بعد التقارب الصحيح

الأسئلة الشائعة

هل تتقارب خوارزمية EM دائمًا إلى الحد الأقصى العالمي؟

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

كيف تختلف خوارزمية EM عن تحسين الاحتمالية المباشر؟

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

متى يجب أن أفضل استنباط MICE على خوارزمية EM؟

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

طرق ذات صلة

المصادر

  1. Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B, 39(1), 1–38.

    افتح مرجع DOI
    تم النسخ.