خوارزمية التوقع والتعظيم

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

في الإحصاء ، تُعدّ خوارزمية التوقع والتعظيم ( EM ) طريقةً تكراريةً لإيجاد تقديرات الاحتمال الأقصى (المحلي) أو تقديرات الاحتمال اللاحق الأقصى (MAP) للمعلمات في النماذج الإحصائية ، حيث يعتمد النموذج على متغيرات كامنة غير مُلاحظة . [ 1 ] يتناوب تكرار خوارزمية EM بين تنفيذ خطوة التوقع (E)، التي تُنشئ دالة لتوقع لوغاريتم الاحتمال المُقيّم باستخدام التقدير الحالي للمعلمات، وخطوة التعظيم (M)، التي تحسب المعلمات التي تُعظّم لوغاريتم الاحتمال المتوقع الذي تم إيجاده في خطوة التوقع . تُستخدم تقديرات المعلمات هذه بعد ذلك لتحديد توزيع المتغيرات الكامنة في خطوة التوقع التالية. يمكن استخدامها، على سبيل المثال، لتقدير خليط من التوزيعات الغاوسية ، أو لحل مشكلة الانحدار الخطي المتعدد. [ 2 ]

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

تاريخ

تم شرح خوارزمية EM وتسميتها بهذا الاسم في ورقة بحثية كلاسيكية نُشرت عام 1977 بقلم آرثر ديمبستر ، ونان ليرد ، ودونالد روبين . [ 3 ] وأشاروا إلى أن هذه الطريقة "اقتُرحت مرات عديدة في ظروف خاصة" من قِبل باحثين سابقين. ومن أوائل هذه الطرق طريقة عدّ الجينات لتقدير ترددات الأليلات التي وضعها سيدريك سميث . [ 4 ] واقترح إتش أو هارتلي طريقة أخرى عام 1958، ثم هارتلي وهوكينج عام 1977، والتي استُمدت منها العديد من الأفكار الواردة في ورقة ديمبستر-ليرد-روبين. [ 5 ] وهناك طريقة أخرى من قِبل إس كيه نج، وثريامباكام كريشنان، وجي جيه ماكلاكلان عام 1977. [ 6 ] ويمكن توسيع نطاق أفكار هارتلي لتشمل أي توزيع منفصل مُجمّع. نُشرت دراسةٌ مُفصّلةٌ للغاية لطريقة EM للعائلات الأسية بواسطة رولف سوندبيرغ في أطروحته وعدة أوراق بحثية، [ 7 ] [ 8 ] [ 9 ] وذلك بعد تعاونه مع بير مارتن-لوف وأندرس مارتن-لوف . [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] عمّمت ورقة ديمبستر-ليرد-روبين البحثية عام 1977 هذه الطريقة، وقدّمت تحليلًا للتقارب لفئةٍ أوسع من المسائل. رسّخت ورقة ديمبستر-ليرد-روبين مكانة طريقة EM كأداةٍ مهمةٍ في التحليل الإحصائي. انظر أيضًا مينغ وفان دايك (1997).

كان تحليل تقارب خوارزمية دمبستر-ليرد-روبين معيبًا، وقد نشر سي إف جيف وو تحليلًا صحيحًا للتقارب في عام 1983. [ 15 ] أثبت برهان وو تقارب طريقة EM حتى خارج العائلة الأسية ، كما ادعى دمبستر-ليرد-روبين. [ 15 ]

مقدمة

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

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

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

وصف

الرموز

بالنظر إلى النموذج الإحصائي الذي يُولّد مجموعةX{\displaystyle \mathbf {X} }من البيانات المرصودة، أو مجموعة من البيانات الكامنة غير المرصودة أو القيم المفقودةZ{\displaystyle \mathbf {Z} }، ومتجه من المعاملات المجهولةθ{\displaystyle {\boldsymbol {\theta }}}بالإضافة إلى دالة الاحتماليةل(θ؛X،Z)=ص(X،Z|θ){\displaystyle L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )=p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})}يتم تحديد تقدير الاحتمال الأقصى ( MLE) للمعلمات المجهولة عن طريق تعظيم الاحتمال الهامشي للبيانات المرصودة.

ل(θ؛X)=ص(X|θ)=∫ص(X،Z|θ)دZ=∫ص(X|Z،θ)ص(Z|θ)دZ{\displaystyle {\begin{aligned}L({\boldsymbol {\theta }};\mathbf {X} )=p(\mathbf {X} \mid {\boldsymbol {\theta }})&=\int p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})\,d\mathbf {Z} \\&=\int p(\mathbf {X} \mid \mathbf {Z} ,{\boldsymbol {\theta }})p(\mathbf {Z} \mid {\boldsymbol {\theta }})\,d\mathbf {Z} \end{aligned}}}

ومع ذلك، فإن هذه الكمية غالباً ما تكون غير قابلة للحل لأنZ{\displaystyle \mathbf {Z} }غير قابلة للملاحظة وتوزيعZ{\displaystyle \mathbf {Z} }غير معروف قبل الوصولθ{\displaystyle {\boldsymbol {\theta }}}.

خوارزمية EM

تسعى خوارزمية EM إلى إيجاد تقدير الاحتمال الأقصى للاحتمال الهامشي من خلال تطبيق هاتين الخطوتين بشكل متكرر:

خطوة التوقع (الخطوة E) : تحديدسؤال(θ|θ(ت)){\displaystyle Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})}باعتبارها القيمة المتوقعة لدالة الاحتمالية اللوغاريتمية لـθ{\displaystyle {\boldsymbol {\theta }}}، فيما يتعلق بالتوزيع الشرطي الحالي لـZ{\displaystyle \mathbf {Z} }منحX{\displaystyle \mathbf {X} }والتقديرات الحالية للمعلماتθ(ت){\displaystyle {\boldsymbol {\theta }}^{(t)}}⁠ :

سؤال(θ|θ(ت))=هـZ∼ص(⋅|X،θ(ت))⁡[سجل⁡ص(X،Z|θ)]:=∫سجل⁡ص(X،Z|θ)ص(Z|X،θ(ت))دZ{\displaystyle Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})=\operatorname {E} _{\mathbf {Z} \sim p(\cdot |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)})}\left[\log p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})\right]:=\int \log p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})\,p(\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)})\,d\mathbf {Z} \,}

خطوة التعظيم (خطوة M) : إيجاد المعاملات التي تعظم هذه الكمية:θ(ت+1)=arg⁡الأعلىθ⁡سؤال(θ|θ(ت)){\displaystyle {\boldsymbol {\theta }}^{(t+1)}=\mathop {\arg \max } _{\boldsymbol {\theta }}Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})\,}

وباختصار أكثر، يمكننا كتابتها كمعادلة واحدة:θ(ت+1)=arg⁡الأعلىθ⁡هـZ∼ص(⋅|X،θ(ت))⁡[سجل⁡ص(X،Z|θ)]{\displaystyle {\boldsymbol {\theta }}^{(t+1)}=\mathop {\arg \max } _{\boldsymbol {\theta }}\operatorname {E} _{\mathbf {Z} \sim p(\cdot |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)})}\left[\log p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})\right]\,}

تفسير المتغيرات

تستخدم النماذج النموذجية التي يتم تطبيق EM عليهاZ{\displaystyle \mathbf {Z} }كمتغير كامن يشير إلى الانتماء إلى إحدى مجموعات معينة:

  1. نقاط البيانات المرصودةX{\displaystyle \mathbf {X} }قد تكون البيانات منفصلة (تأخذ قيمًا في مجموعة منتهية أو مجموعة لا نهائية قابلة للعد) أو متصلة (تأخذ قيمًا في مجموعة لا نهائية غير قابلة للعد). ويرتبط بكل نقطة بيانات متجه من الملاحظات.
  2. القيم المفقودة (المعروفة أيضًا بالمتغيرات الكامنة )Z{\displaystyle \mathbf {Z} }منفصلة ، ​​مستمدة من عدد ثابت من القيم، وبوجود متغير كامن واحد لكل وحدة مُلاحظة.
  3. المعلمات متصلة، وهي من نوعين: المعلمات المرتبطة بجميع نقاط البيانات، وتلك المرتبطة بقيمة محددة لمتغير كامن (أي المرتبطة بجميع نقاط البيانات التي يكون لمتغيرها الكامن المقابل تلك القيمة).

ومع ذلك، من الممكن تطبيق خوارزمية EM على أنواع أخرى من النماذج.

الدافع هو كما يلي. إذا كانت قيمة المعلماتθ{\displaystyle {\boldsymbol {\theta }}}عادةً ما تكون قيمة المتغيرات الكامنة معروفةZ{\displaystyle \mathbf {Z} }يمكن إيجادها عن طريق تعظيم دالة الاحتمال اللوغاريتمي على جميع القيم الممكنة لـZ{\displaystyle \mathbf {Z} }إما ببساطة عن طريق التكرار علىZ{\displaystyle \mathbf {Z} }أو من خلال خوارزمية مثل خوارزمية فيتربي لنماذج ماركوف المخفية . وعلى العكس من ذلك، إذا كنا نعرف قيمة المتغيرات الكامنةZ{\displaystyle \mathbf {Z} }، يمكننا إيجاد تقدير للمعاملاتθ{\displaystyle {\boldsymbol {\theta }}}يمكن تحقيق ذلك بسهولة نسبية، عادةً عن طريق تجميع نقاط البيانات المرصودة وفقًا لقيمة المتغير الكامن المرتبط بها، ثم حساب متوسط ​​القيم، أو دالة ما للقيم، للنقاط في كل مجموعة. وهذا يشير إلى خوارزمية تكرارية، في حالة كون كليهماθ{\displaystyle {\boldsymbol {\theta }}}وZ{\displaystyle \mathbf {Z} }غير معروف:

  1. أولاً، قم بتهيئة المعلماتθ{\displaystyle {\boldsymbol {\theta }}}إلى بعض القيم العشوائية.
  2. احسب احتمال كل قيمة ممكنة لـZ{\displaystyle \mathbf {Z} }، معطى​θ{\displaystyle {\boldsymbol {\theta }}}⁠ .
  3. ثم استخدم القيم المحسوبة للتو لـZ{\displaystyle \mathbf {Z} }لحساب تقدير أفضل للمعلماتθ{\displaystyle {\boldsymbol {\theta }}}⁠ .
  4. كرر الخطوتين 2 و 3 حتى الوصول إلى التقارب.

تقترب الخوارزمية كما تم وصفها للتو بشكل رتيب من الحد الأدنى المحلي لدالة التكلفة.

ملكيات

على الرغم من أن تكرار خوارزمية EM يزيد من دالة احتمالية البيانات المرصودة (أي الهامشية)، إلا أنه لا يوجد ضمان بأن التسلسل يتقارب إلى مُقدِّر الاحتمالية القصوى . بالنسبة للتوزيعات متعددة الأنماط ، هذا يعني أن خوارزمية EM قد تتقارب إلى قيمة عظمى محلية لدالة احتمالية البيانات المرصودة، اعتمادًا على القيم الأولية. توجد مجموعة متنوعة من الأساليب الاستدلالية أو ما وراء الاستدلالية لتجنب القيمة العظمى المحلية، مثل تسلق التل ذي إعادة التشغيل العشوائي (بدءًا من عدة تقديرات أولية عشوائية مختلفة ).θ(ت){\displaystyle {\boldsymbol {\theta }}^{(t)}}) ، أو تطبيق أساليب التلدين المحاكي .

تُعدّ خوارزمية EM مفيدةً بشكلٍ خاص عندما يكون الاحتمال من عائلة التوزيعات الأسية ، انظر سوندبيرغ (2019، الفصل 8) للحصول على شرحٍ مُفصّل: [ 16 ] حيث تُصبح خطوة E مجموع توقعات الإحصاءات الكافية ، وتتضمن خطوة M تعظيم دالة خطية. في مثل هذه الحالة، يُمكن عادةً اشتقاق تحديثات تعبيرية مُغلقة لكل خطوة، باستخدام صيغة سوندبيرغ [ 17 ] (التي أثبتها ونشرها رولف سوندبيرغ، استنادًا إلى نتائج غير منشورة لبير مارتن-لوف وأندرس مارتن-لوف ). [ 8 ] [ 9 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ]

تم تعديل طريقة EM لحساب تقديرات الاحتمال الأقصى اللاحق (MAP) للاستدلال البايزي في الورقة الأصلية التي كتبها ديمبستر وليرد وروبين.

توجد طرق أخرى لإيجاد تقديرات الاحتمال الأقصى، مثل انحدار التدرج ، والتدرج المترافق ، أو متغيرات خوارزمية جاوس-نيوتن . وعلى عكس خوارزمية EM، تتطلب هذه الطرق عادةً حساب المشتقة الأولى و/أو الثانية لدالة الاحتمال.

إثبات صحة النتائج

تعمل خوارزمية التوقع والتعظيم على التحسينسؤال(θ|θ(ت)){\displaystyle Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})}بدلاً من التحسين المباشرسجل⁡ص(X|θ){\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})}يُبين هنا أن التحسينات التي تطرأ على الأول تستلزم تحسينات على الثاني. [ 18 ]

لأيZ{\displaystyle \mathbf {Z} }باحتمالية غير صفريةص(Z|X،θ){\displaystyle p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }})}يمكننا أن نكتب سجل⁡ص(X|θ)=سجل⁡ص(X،Z|θ)-سجل⁡ص(Z|X،θ).{\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})=\log p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})-\log p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}).} نأخذ القيمة المتوقعة على القيم المحتملة للبيانات المجهولةZ{\displaystyle \mathbf {Z} }في ظل تقدير المعلمة الحاليθ(ت){\displaystyle \theta ^{(t)}}بضرب كلا الطرفين فيص(Z|X،θ(ت)){\displaystyle p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)})}والجمع (أو التكامل) علىZ{\displaystyle \mathbf {Z} }يمثل الطرف الأيسر القيمة المتوقعة لثابت، لذا نحصل على: سجل⁡ص(X|θ)=∑Zص(Z|X،θ(ت))سجل⁡ص(X،Z|θ)-∑Zص(Z|X،θ(ت))سجل⁡ص(Z|X،θ)=سؤال(θ|θ(ت))+ح(θ|θ(ت))،{\displaystyle {\begin{aligned}\log p(\mathbf {X} \mid {\boldsymbol {\theta }})&=\sum _{\mathbf {Z} }p{\left(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)}\right)}\log p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})-\sum _{\mathbf {Z} }p{\left(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)}\right)}\log p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }})\\&=Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)}),\end{aligned}}} أينح(θ|θ(ت)){\displaystyle H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})}يُعرَّف بواسطة المجموع المنفي الذي يحل محله. هذه المعادلة الأخيرة صحيحة لكل قيمة من قيمθ{\displaystyle {\boldsymbol {\theta }}}مشتملθ=θ(ت){\displaystyle {\boldsymbol {\theta }}={\boldsymbol {\theta }}^{(t)}}، سجل⁡ص(X|θ(ت))=سؤال(θ(ت)|θ(ت))+ح(θ(ت)|θ(ت))،{\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }}^{(t)})=Q({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)}),} وبطرح هذه المعادلة الأخيرة من المعادلة السابقة نحصل على سجل⁡ص(X|θ)-سجل⁡ص(X|θ(ت))=سؤال(θ|θ(ت))-سؤال(θ(ت)|θ(ت))+ح(θ|θ(ت))-ح(θ(ت)|θ(ت)).{\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})-\log p(\mathbf {X} \mid {\boldsymbol {\theta }}^{(t)})=Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})-Q({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})-H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)}).} لكن متباينة جيبس ​​تخبرنا أنح(θ|θ(ت))≥ح(θ(ت)|θ(ت)){\displaystyle H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})\geq H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})}لذا يمكننا أن نستنتج أن سجل⁡ص(X|θ)-سجل⁡ص(X|θ(ت))≥سؤال(θ|θ(ت))-سؤال(θ(ت)|θ(ت)).{\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})-\log p(\mathbf {X} \mid {\boldsymbol {\theta }}^{(t)})\geq Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})-Q({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)}).} بالكلمات، اختيارθ{\displaystyle {\boldsymbol {\theta }}}لتحسينسؤال(θ|θ(ت)){\displaystyle Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})}الأسبابسجل⁡ص(X|θ){\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})}لتحسين الوضع على الأقل بنفس القدر.

كإجراء تعظيم-تعظيم

يمكن اعتبار خوارزمية EM بمثابة خطوتين متناوبتين لتحقيق أقصى قيمة، أي كمثال على خوارزمية التدرج الإحداثي . [ 19 ] [ 20 ] لنفترض الدالة التالية: F(q،θ):=هـq⁡[سجل⁡ل(θ؛x،Z)]+ح(q)،{\displaystyle F(q,\theta ):=\operatorname {E} _{q}[\log L(\theta ;x,Z)]+H(q),} حيث q هو توزيع احتمالي عشوائي على البيانات غير المرصودة z، و H ( q ) هي إنتروبيا التوزيع q . يمكن كتابة هذه الدالة على النحو التالي: F(q،θ)=-دكل(q∥صZ|X(⋅|x؛θ))+سجل⁡ل(θ؛x)،{\displaystyle F(q,\theta )=-D_{\mathrm {KL} }{\big (}q\parallel p_{Z\mid X}(\cdot \mid x;\theta ){\big )}+\log L(\theta ;x),} أين صZ|X(⋅|x؛θ){\displaystyle p_{Z\mid X}(\cdot \mid x;\theta )}يمثل التوزيع الشرطي للبيانات غير المرصودة بالنظر إلى البيانات المرصودةx{\displaystyle x}ودكل{\displaystyle D_{KL}}هو تباعد كولباك-لايبير .

ويمكن النظر إلى خطوات خوارزمية EM على النحو التالي:

  • خطوة التوقع : اخترq{\displaystyle q}لتحقيق أقصى قدر منF{\displaystyle F}⁠ :q(ت)=arg⁡الأعلىq⁡F(q،θ(ت)){\displaystyle q^{(t)}=\mathop {\arg \max } _{q}F{\left(q,\theta ^{(t)}\right)}}
  • خطوة التعظيم : اخترθ{\displaystyle \theta }لتحقيق أقصى قدر منF{\displaystyle F}⁠ :θ(ت+1)=arg⁡الأعلىθ⁡F(q(ت)،θ){\displaystyle \theta ^{(t+1)}=\mathop {\arg \max } _{\theta }F{\left(q^{(t)},\theta \right)}}

التطبيقات

خوارزميات التصفية والتنعيم EM

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

تنشأ خوارزميات التصفية والتنعيم EM من خلال تكرار هذا الإجراء المكون من خطوتين:

الخطوة الإلكترونية
قم بتشغيل مرشح كالمان أو مُنعِّم التباين الأدنى المصمم بتقديرات المعلمات الحالية للحصول على تقديرات الحالة المحدثة.
خطوة إم
استخدم تقديرات الحالة المفلترة أو المُنعّمة ضمن حسابات الاحتمال الأقصى للحصول على تقديرات محدثة للمعلمات.

لنفترض أن مرشح كالمان أو مُنعِّم التباين الأدنى يعمل على قياسات نظام ذي مدخل واحد ومخرج واحد يحتوي على ضوضاء بيضاء مضافة. يمكن الحصول على تقدير مُحدَّث لتباين ضوضاء القياس من حساب الاحتمال الأقصى.σ^v2=1شمال∑ك=1شمال(zك-x^ك)2،{\displaystyle {\widehat {\sigma }}_{v}^{2}={\frac {1}{N}}\sum _{k=1}^{N}{(z_{k}-{\widehat {x}}_{k})}^{2},}

أينx^ك{\displaystyle {\widehat {x}}_{k}}هل يتم حساب تقديرات المخرجات العددية بواسطة مرشح أو مُنعِّم من N قياسات عددية؟zك{\displaystyle z_{k}}يمكن تطبيق التحديث المذكور أعلاه أيضًا على تحديث شدة ضوضاء قياس بواسون. وبالمثل، بالنسبة لعملية الانحدار الذاتي من الدرجة الأولى، يمكن حساب تقدير محدّث لتباين ضوضاء العملية بواسطة σ^w2=1شمال∑ك=1شمال(x^ك+1-F^x^ك)2،{\displaystyle {\widehat {\sigma }}_{w}^{2}={\frac {1}{N}}\sum _{k=1}^{N}{({\widehat {x}}_{k+1}-{\widehat {F}}{\widehat {x}}_{k})}^{2},}

أينx^ك{\displaystyle {\widehat {x}}_{k}}وx^ك+1{\displaystyle {\widehat {x}}_{k+1}}هي تقديرات الحالة العددية المحسوبة بواسطة مرشح أو مُنعِّم. يتم الحصول على تقدير معامل النموذج المُحدَّث عبر F^=∑ك=1شمال(x^ك+1-F^x^ك)2∑ك=1شمالx^ك2.{\displaystyle {\widehat {F}}={\frac {\sum \limits _{k=1}^{N}{\left({\widehat {x}}_{k+1}-{\widehat {F}}{\widehat {x}}_{k}\right)}^{2}}{\sum \limits _{k=1}^{N}{\widehat {x}}_{k}^{2}}}.}

لقد دُرست مسألة تقارب تقديرات المعلمات، مثل تلك المذكورة أعلاه، دراسةً وافية. [ 26 ] [ 27 ] [ 28 ] [ 29 ]

المتغيرات

تم اقتراح عدد من الطرق لتسريع تقارب خوارزمية EM البطيء أحيانًا، مثل تلك التي تستخدم التدرج المترافق وطرق نيوتن المعدلة (نيوتن-رافسون). [ 30 ] كما يمكن استخدام خوارزمية EM مع طرق التقدير المقيدة.

غالباً ما توفر خوارزمية تعظيم التوقع الموسعة للمعاملات (PX-EM) تسريعاً من خلال "استخدام "تعديل التغاير" لتصحيح تحليل خطوة M، والاستفادة من المعلومات الإضافية الملتقطة في البيانات الكاملة المحسوبة". [ 31 ]

تستبدل خوارزمية التوقع والتعظيم الشرطي (ECM) كل خطوة M بسلسلة من خطوات التعظيم الشرطي (CM) حيث يتم تعظيم كل معلمة θ i بشكل فردي، بشرط ثبات المعلمات الأخرى. [ 32 ] ويمكن توسيعها لتصبح خوارزمية التوقع والتعظيم الشرطي (ECME) . [ 33 ]

تم توسيع هذه الفكرة في خوارزمية التوقع والتعظيم المعممة (GEM) ، حيث يُسعى فقط إلى زيادة دالة الهدف F لكل من خطوتي E وM كما هو موضح في قسم "إجراءات التعظيم" . [ 19 ] وقد طُوّرت خوارزمية GEM في بيئة موزعة وأظهرت نتائج واعدة. [ 34 ]

من الممكن أيضًا اعتبار خوارزمية EM كفئة فرعية من خوارزمية MM (Majorize/Minimize أو Minorize/Maximize، اعتمادًا على السياق)، [ 35 ] وبالتالي استخدام أي آلية تم تطويرها في الحالة الأكثر عمومية.

خوارزمية ألفا-إي إم

تعتمد دالة Q المستخدمة في خوارزمية EM على دالة الاحتمال اللوغاريتمي، ولذلك تُعرف باسم خوارزمية log-EM. يمكن تعميم استخدام دالة الاحتمال اللوغاريتمي ليشمل نسبة الاحتمال اللوغاريتمي α. بعد ذلك، يمكن التعبير بدقة عن نسبة الاحتمال اللوغاريتمي α للبيانات المرصودة على أنها تساوي باستخدام دالة Q لنسبة الاحتمال اللوغاريتمي α والتباعد α. يُعد الحصول على دالة Q هذه خطوة E معممة، بينما تعظيمها خطوة M معممة. يُطلق على هذا الزوج اسم خوارزمية α-EM [ 36 ] ، والتي تتضمن خوارزمية log-EM كفئة فرعية منها. بالتالي، تُعد خوارزمية α-EM التي طورها ياسوو ماتسوياما تعميمًا دقيقًا لخوارزمية log-EM، ولا تتطلب حساب التدرج أو مصفوفة هيسيان. تُظهر خوارزمية α-EM تقاربًا أسرع من خوارزمية log-EM عند اختيار قيمة α مناسبة. تؤدي خوارزمية α-EM إلى نسخة أسرع من خوارزمية تقدير نموذج ماركوف المخفي α-HMM. [ 37 ]

العلاقة بطرق بايز التباينية

خوارزمية EM هي طريقة احتمالية قصوى غير بايزية جزئيًا. تُعطي نتيجتها النهائية توزيعًا احتماليًا على المتغيرات الكامنة (على الطريقة البايزية) بالإضافة إلى تقدير نقطي لـ θ (إما تقدير احتمالية قصوى أو نمط لاحق). قد يُراد نسخة بايزية كاملة من هذه الخوارزمية، تُعطي توزيعًا احتماليًا على θ والمتغيرات الكامنة. ببساطة، تُعامل θ كمتغير كامن آخر في النهج البايزي للاستدلال. في هذا النموذج، يختفي التمييز بين خطوتي E و M. عند استخدام تقريب Q المُحلل كما هو موضح أعلاه ( بايز التبايني )، يمكن تكرار الحل على كل متغير كامن (بما في ذلك θ ) وتحسينه واحدًا تلو الآخر. الآن، يلزم k خطوة لكل تكرار، حيث k هو عدد المتغيرات الكامنة. بالنسبة للنماذج البيانية، يسهل القيام بذلك لأن قيمة Q الجديدة لكل متغير تعتمد فقط على غطاء ماركوف الخاص به، لذا يمكن استخدام تمرير الرسائل المحلي للاستدلال الفعال.

التفسير الهندسي

في هندسة المعلومات ، يتم تفسير الخطوة E والخطوة M على أنهما إسقاطات تحت اتصالات أفينية مزدوجة ، تسمى الاتصال e والاتصال m؛ ويمكن أيضًا فهم تباعد Kullback-Leibler بهذه المصطلحات.

أمثلة

خليط غاوسي

مقارنة بين خوارزميتي k-means و EM على بيانات اصطناعية مُصوَّرة باستخدام ELKI . باستخدام التباينات، تستطيع خوارزمية EM وصف التوزيعات الطبيعية بدقة، بينما تقسم خوارزمية k-means البيانات إلى خلايا فورونوي . يُشار إلى مركز المجموعة بالرمز الأكبر والأفتح.
عرض متحرك يوضح كيفية قيام خوارزمية EM بملاءمة نموذج خليط غاوسي ثنائي المكونات لمجموعة بيانات Old Faithful . وتنتقل الخوارزمية من مرحلة التهيئة العشوائية إلى مرحلة التقارب.

يتركx=(x1،x2،...،xن){\displaystyle \mathbf {x} =(\mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{n})}كن نموذجًا لـن{\displaystyle n}ملاحظات مستقلة من مزيج من توزيعين طبيعيين متعدد المتغيرات ذي بُعدد{\displaystyle d}ودعz=(z1،z2،...،zن){\displaystyle \mathbf {z} =(z_{1},z_{2},\ldots ,z_{n})}[ 20 ] هي المتغيرات الكامنة التي تحدد المكون الذي تنشأ منه الملاحظة.Xأنا|(Zأنا=1)∼شمالد(μ1،Σ1)،Xأنا|(Zأنا=2)∼شمالد(μ2،Σ2)،{\displaystyle {\begin{aligned}X_{i}\mid (Z_{i}=1)&\sim {\mathcal {N}}_{d}({\boldsymbol {\mu }}_{1},\Sigma _{1}),\\X_{i}\mid (Z_{i}=2)&\sim {\mathcal {N}}_{d}({\boldsymbol {\mu }}_{2},\Sigma _{2}),\end{aligned}}} أين P⁡(Zأنا=1)=τ1وP⁡(Zأنا=2)=τ2=1-τ1.{\displaystyle \operatorname {P} (Z_{i}=1)=\tau _{1}\,\quad {\text{and}}\quad \operatorname {P} (Z_{i}=2)=\tau _{2}=1-\tau _{1}.}

الهدف هو تقدير المعلمات المجهولة التي تمثل قيمة المزج بين التوزيعات الغاوسية ومتوسطات وتغايرات كل منها: θ=(τ،μ1،μ2،Σ1،Σ2)،{\displaystyle \theta ={\big (}{\boldsymbol {\tau }},{\boldsymbol {\mu }}_{1},{\boldsymbol {\mu }}_{2},\Sigma _{1},\Sigma _{2}{\big )},} حيث تكون دالة الاحتمالية للبيانات غير المكتملة ل(θ؛x)=∏أنا=1ن∑ج=12τج و(xأنا؛μج،Σج)،{\displaystyle L(\theta ;\mathbf {x} )=\prod _{i=1}^{n}\sum _{j=1}^{2}\tau _{j}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j},\Sigma _{j}),}

ودالة الاحتمالية للبيانات الكاملة هي ل(θ؛x،z)=ص(x،z|θ)=∏أنا=1ن∏ج=12[و(xأنا؛μج،Σج)τج]أنا(zأنا=ج)،{\displaystyle {\begin{aligned}L(\theta ;\mathbf {x} ,\mathbf {z} )&=p(\mathbf {x} ,\mathbf {z} \mid \theta )\\&=\prod _{i=1}^{n}\prod _{j=1}^{2}\left[f(\mathbf {x} _{i};{\boldsymbol {\mu) }} _ {j}،\Sigma _{j})\tau _{j}\right]^{\mathbb {I} (z_{i}=j)}،\end{محاذاة}}}

أو

سجل⁡ل(θ؛x،z)=∑أنا=1ن∑ج=12أنا(zأنا=ج)[سجل⁡τج-12سجل⁡|Σج|-12(xأنا-μج)⊤Σج-1(xأنا-μج)-د2سجل⁡(2π)]،{\displaystyle \log L(\theta ;\mathbf {x} ,\mathbf {z} )=\sum _{i=1}^{n}\sum _{j=1}^{2}\mathbb {I} (z_{i}=j)\left[\log \tau _{j}-{\tfrac {1}{2}}\log |\Sigma _{j}|-{\tfrac {1}{2}}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})^{\top }\Sigma _{j}^{-1}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})-{\tfrac {d}{2}}\log(2\pi )\right],}

أينأنا{\displaystyle \mathbb {I} }هي دالة مؤشر وو{\displaystyle f}هي دالة كثافة الاحتمال للتوزيع الطبيعي متعدد المتغيرات.

في المساواة الأخيرة، لكل i ، مؤشر واحدأنا(zأنا=ج){\displaystyle \mathbb {I} (z_{i}=j)}يساوي الصفر، ومؤشر واحد يساوي واحدًا. وبالتالي، يختزل المجموع الداخلي إلى حد واحد.

خطوة

بالنظر إلى تقديرنا الحالي للمعاملات θ ( t ) ، يتم تحديد التوزيع الشرطي لـ Z i بواسطة نظرية بايز ليكون الارتفاع النسبي للكثافة الطبيعية المرجحة بـ τ : تيج،أنا(ت):=P⁡(Zأنا=ج|Xأنا=xأنا؛θ(ت))=τج(ت)و(xأنا؛μج(ت)،Σج(ت))τ1(ت)و(xأنا؛μ1(ت)،Σ1(ت))+τ2(ت)و(xأنا؛μ2(ت)،Σ2(ت)).{\displaystyle {\begin{aligned}T_{j,i}^{(t)}:={}&\operatorname {P} (Z_{i}=j\mid X_{i}=\mathbf {x} _{i};\theta ^{(t)})\\={}&{\frac {\tau _{j}^{(t)}\,f{\left(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j}^{(t)},\Sigma _{j}^{(t)}\right)}}{\tau _{1}^{(t)}\,f{\left(\mathbf {x} _{i};{\boldsymbol {\mu }}_{1}^{(t)},\Sigma _{1}^{(t)}\right)}+\tau _{2}^{(t)}\,f{\left(\mathbf {x} _{i};{\boldsymbol {\mu }}_{2}^{(t)},\Sigma _{2}^{(t)}\right)}}}.\end{aligned}}}

وتسمى هذه "احتمالات العضوية"، والتي تعتبر عادةً ناتج خطوة E (على الرغم من أن هذه ليست دالة Q أدناه).

تتوافق هذه الخطوة E مع إعداد هذه الوظيفة لـ Q : سؤال(θ|θ(ت))=هـZ|X=x؛θ(ت)⁡[سجل⁡ل(θ؛x،Z)]=هـZ|X=x؛θ(ت)⁡[سجل⁡∏أنا=1نل(θ؛xأنا،Zأنا)]=هـZ|X=x؛θ(ت)⁡[∑أنا=1نسجل⁡ل(θ؛xأنا،Zأنا)]=∑أنا=1نهـZأنا|Xأنا=xأنا؛θ(ت)⁡[سجل⁡ل(θ؛xأنا،Zأنا)]=∑أنا=1ن∑ج=12P(Zأنا=ج|Xأنا=xأنا؛θ(ت))سجل⁡ل(θ؛xأنا،ج)=∑أنا=1ن∑ج=12تيج،أنا(ت)[سجل⁡τج-12سجل⁡|Σج|-12(xأنا-μج)⊤Σج-1(xأنا-μج)-د2سجل⁡(2π)].{\displaystyle {\begin{aligned}Q(\theta \mid \theta ^{(t)})&=\operatorname {E} _{\mathbf {Z} \mid \mathbf {X} =\mathbf {x} ;\mathbf {\theta} ^{(t)}}\left[\log L(\theta  ;\mathbf {x} ,\mathbf {Z} )\right]\\&=\operatorname {E} _{\mathbf {Z} \mid \mathbf {X} =\mathbf {x}  ;\mathbf {\theta } ^ {(t)}}\left[\log \prod _{i=1}^{n}L(\theta  ;\mathbf {x} _{i},Z_{i})\right]\\&=\operatorname {E} _{\mathbf {Z} \mid \mathbf {X} =\mathbf {x}  ;\mathbf {\theta } ^ {(ر)}}\left[\sum _{i=1}^{n}\log L(\theta  ;\mathbf {x} _{i},Z_{i})\right]\\&=\sum _{i=1}^{n}\operatorname {E} _{Z_{i}\mid X_{i}=x_{i};\mathbf {\theta } ^{(t)}}\left[\log L(\theta  ;\mathbf {x} _{i},Z_{i})\right]\\&=\sum _{i=1}^{n}\sum _{j=1}^{2}P(Z_{i}=j\mid X_{i}=\mathbf {x} _{i};\theta ^{(t)})\log L(\theta  ;\mathbf {x} _{i},j)\\&=\sum _{i=1}^{n}\sum _{j=1}^{2}T_{j,i}^{(t)}\left[\log \tau _{j}-{\tfrac {1}{2}}\log |\Sigma _{j}|-{\tfrac {1}{2}}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})^{\top }\Sigma _{j}^{-1}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})-{\tfrac {d}{2}}\log(2\pi )\right].\end{aligned}}} التوقع لـسجل⁡ل(θ؛xأنا،Zأنا){\displaystyle \log L(\theta يتم حساب ;\mathbf {x} _{i},Z_{i})} داخل المجموع بالنسبة لدالة كثافة الاحتمالP(Zأنا|Xأنا=xأنا؛θ(ت)){\displaystyle P(Z_{i}\mid X_{i}=\mathbf {x} _{i};\theta ^{(t)})}، وهو ما قد يختلف من شخص لآخر xأنا{\displaystyle \mathbf {x} _{i}}من مجموعة التدريب. كل شيء في الخطوة E معروف قبل اتخاذ الخطوة باستثناءتيج،أنا{\displaystyle T_{j,i}}، والتي يتم حسابها وفقًا للمعادلة في بداية قسم خطوة E.

لا يلزم حساب هذا التوقع الشرطي الكامل في خطوة واحدة، لأن τ و μ / Σ يظهران في حدود خطية منفصلة وبالتالي يمكن تعظيمهما بشكل مستقل.

الخطوة M

سؤال(θ|θ(ت)){\displaystyle Q(\theta \mid \theta ^{(t)})}كونها دالة تربيعية الشكل يعني أن تحديد القيم القصوى لـθ{\displaystyle \theta }الأمر بسيط نسبياً. أيضاً،τ{\displaystyle \tau }،(μ1،Σ1){\displaystyle ({\boldsymbol {\mu }}_{1},\Sigma _{1})}و(μ2،Σ2){\displaystyle ({\boldsymbol {\mu }}_{2},\Sigma _{2})}قد يتم تعظيمها جميعًا بشكل مستقل لأنها جميعًا تظهر في حدود خطية منفصلة.

للبدء، فكر فيτ{\displaystyle \tau }، والذي يتضمن القيدτ1+τ2=1{\displaystyle \tau _{1}+\tau _{2}=1}: τ(ت+1)=arg⁡الأعلىτ⁡سؤال(θ|θ(ت))=arg⁡الأعلىτ⁡{[∑أنا=1نتي1،أنا(ت)]سجل⁡τ1+[∑أنا=1نتي2،أنا(ت)]سجل⁡τ2}.{\displaystyle {\begin{aligned}{\boldsymbol {\tau }}^{(t+1)}&=\mathop {\arg \max } _{\boldsymbol {\tau }}Q{\left(\theta \mid \theta ^{(t)}\right)}\\&=\mathop {\arg \max } _{\boldsymbol {\tau }}\left\{\left[\sum _{i=1}^{n}T_{1,i}^{(t)}\right]\log \tau _{1}+\left[\sum _{i=1}^{n}T_{2,i}^{(t)}\right]\log \tau _{2}\right\}.\end{aligned}}} وهذا له نفس شكل تقدير الاحتمال الأقصى للتوزيع ذي الحدين ، لذلك τج(ت+1)=∑أنا=1نتيج،أنا(ت)∑أنا=1ن(تي1،أنا(ت)+تي2،أنا(ت))=1ن∑أنا=1نتيج،أنا(ت).{\displaystyle \tau _{j}^{(t+1)}={\frac {\sum \limits _{i=1}^{n}T_{j,i}^{(t)}}{\sum \limits _{i=1}^{n}\left(T_{1,i}^{(t)}+T_{2,i}^{(t)}\right)}}={\frac {1}{n}}\sum _{i=1}^{n}T_{j,i}^{(t)}.}

للحصول على التقديرات التالية لـ(μ1،Σ1){\displaystyle ({\boldsymbol {\mu }}_{1},\Sigma _{1})}: (μ1(ت+1)،Σ1(ت+1))=arg⁡الأعلىμ1،Σ1⁡سؤال(θ|θ(ت))=arg⁡الأعلىμ1،Σ1⁡∑أنا=1نتي1،أنا(ت){-12سجل⁡|Σ1|-12(xأنا-μ1)⊤Σ1-1(xأنا-μ1)}.{\displaystyle {\begin{aligned}\left({\boldsymbol {\mu }}_{1}^{(t+1)},\Sigma _{1}^{(t+1)}\right)&=\mathop {\arg \max } _{{\boldsymbol {\mu }}_{1},\Sigma _{1}}Q{\left(\theta \mid \theta ^{(t)}\right)}\\&=\mathop {\arg \max } _{{\boldsymbol {\mu }}_{1},\Sigma _{1}}\sum _{i=1}^{n}T_{1,i}^{(t)}\left\{-{\tfrac {1}{2}}\log \left|\Sigma _{1}\right|-{\tfrac {1}{2}}\left(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1}\right)^{\top }\Sigma _{1}^{-1}\left(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1}\right)\right\}.\end{aligned}}} وهذا له نفس شكل تقدير الاحتمال الأقصى المرجح للتوزيع الطبيعي، لذلك μ1(ت+1)=∑أنا=1نتي1،أنا(ت)xأنا∑أنا=1نتي1،أنا(ت)،Σ1(ت+1)=∑أنا=1نتي1،أنا(ت)(xأنا-μ1(ت+1))(xأنا-μ1(ت+1))⊤∑أنا=1نتي1،أنا(ت){\displaystyle {\begin{aligned}{\boldsymbol {\mu }}_{1}^{(t+1)}&={\frac {\sum \limits _{i=1}^{n}T_{1,i}^{(t)}\mathbf {x} _{i}}{\sum \limits _{i=1}^{n}T_{1,i}^{(t)}}},\\[1ex]\Sigma _{1}^{(t+1)}&={\frac {\sum \limits _{i=1}^{n}T_{1,i}^{(t)}\left(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1}^{(t+1)}\right)\left(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1}^{(t+1)}\right)^{\top }}{\sum \limits _{i=1}^{n}T_{1,i}^{(t)}}}\end{aligned}}} وبالتناظر، μ2(ت+1)=∑أنا=1نتي2،أنا(ت)xأنا∑أنا=1نتي2،أنا(ت)،Σ2(ت+1)=∑أنا=1نتي2،أنا(ت)(xأنا-μ2(ت+1))(xأنا-μ2(ت+1))⊤∑أنا=1نتي2،أنا(ت).{\displaystyle {\begin{aligned}{\boldsymbol {\mu }}_{2}^{(t+1)}&={\frac {\sum \limits _{i=1}^{n}T_{2,i}^{(t)}\mathbf {x} _{i}}{\sum \limits _{i=1}^{n}T_{2,i}^{(t)}}},\\[1ex]\Sigma _{2}^{(t+1)}&={\frac {\sum \limits _{i=1}^{n}T_{2,i}^{(t)}\left(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{2}^{(t+1)}\right)\left(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{2}^{(t+1)}\right)^{\top }}{\sum \limits _{i=1}^{n}T_{2,i}^{(t)}}}.\end{aligned}}}

إنهاء الخدمة

اختتم العملية التكرارية إذا كان تحديث التوقع صغيرًا بما فيه الكفاية. أي، إذا|هـZ|θ(ت)،x⁡[سجل⁡ل(θ(ت)؛x،Z)]-هـZ|θ(ت-1)،x⁡[سجل⁡ل(θ(ت-1)؛x،Z)]|≤ε{\displaystyle \left|\operatorname {E} _{Z\mid \theta ^{(t)},\mathbf {x} }[\log L(\theta ^{(t)};\mathbf {x} ,\mathbf {Z} )]-\operatorname {E} _{Z\mid \theta ^{(t-1)},\mathbf {x} }[\log L(\theta ^{(t-1)};\mathbf {x} ,\mathbf {Z} )]\right|\leq \varepsilon }لε{\displaystyle \varepsilon }أقل من عتبة محددة مسبقاً.

تعميم

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

الانحدار المقتطع والمُراقب

تم تطبيق خوارزمية EM في حالة وجود نموذج انحدار خطي أساسي يفسر تباين كمية معينة، ولكن القيم المرصودة فعليًا هي نسخ منقحة أو مبتورة من تلك الممثلة في النموذج. [ 38 ] تشمل الحالات الخاصة لهذا النموذج الملاحظات المنقحة أو المبتورة من توزيع طبيعي واحد . [ 38 ]

البدائل

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

انظر أيضاً

مراجع

  1. ↑ مينغ، إكس.-إل.؛ فان دايك، د. (1997). "خوارزمية EM - أغنية شعبية قديمة تُغنى بلحن جديد سريع" . مجلة الجمعية الإحصائية الملكية، السلسلة ب ، 59 (3): 511-567 . doi : 10.1111/1467-9868.00082 . S2CID 17461647 . 
  2. ↑ جيونغ يول كوون، قسطنطين كارامانيس وقائع المؤتمر الدولي الثالث والعشرين حول الذكاء الاصطناعي والإحصاء ، PMLR 108:1727-1736، 2020.
  3. ↑ ديمبستر، أ.ب .؛ ليرد، ن.م .؛ روبين، د.ب. (1977). "الاحتمال الأقصى من البيانات غير المكتملة باستخدام خوارزمية EM". مجلة الجمعية الإحصائية الملكية، السلسلة ب . 39 (1): 1-38 . doi : 10.1111/j.2517-6161.1977.tb01600.x . JSTOR 2984875. MR 0501537 .  
  4. ↑ سيبيليني، ر.م. (1955). "تقدير ترددات الجينات في مجتمع يتزاوج عشوائيًا". حوليات علم الوراثة البشرية . 20 (2): 97-115 . doi : 10.1111/ j.1469-1809.1955.tb01360.x . PMID 13268982. S2CID 38625779 .  
  5. ↑ هارتلي، هيرمان أوتو (1958). "تقدير الاحتمال الأقصى من البيانات غير المكتملة". القياسات الحيوية . 14 (2): 174-194 . doi : 10.2307/2527783 . JSTOR 2527783 . 
  6. ↑ نغ، شو كاي؛ كريشنان، ثريامباكام؛ ماكلاكلان، جيفري جيه. (21-12-2011)، "خوارزمية EM"، دليل الإحصاءات الحاسوبية ، برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ، ص 139-172 ، doi : 10.1007/978-3-642-21551-3_6 ، ISBN  978-3-642-21550-6، S2CID 59942212 
  7. ↑ سوندبيرغ، رولف (1974). " نظرية الاحتمال الأقصى للبيانات غير المكتملة من عائلة أسية". المجلة الإسكندنافية للإحصاء . 1 (2): 49-58 . JSTOR 4615553. MR 0381110 .  
  8. 1 2 رولف سوندبيرغ. 1971. نظرية الاحتمال الأقصى وتطبيقاتها على التوزيعات الناتجة عن رصد دالة لمتغير من عائلة أسية . أطروحة دكتوراه، معهد الإحصاء الرياضي، جامعة ستوكهولم.
  9. 1 2 سوندبيرغ، رولف (1976). "طريقة تكرارية لحل معادلات الاحتمالية للبيانات غير المكتملة من العائلات الأسية". الاتصالات في الإحصاء - المحاكاة والحساب . 5 (1): 55-64 . doi : 10.1080/03610917608812007 . MR 0443190 . 
  10. ↑ انظر إلى شكر وتقدير ديمبستر وليرد وروبين في الصفحات 3 و5 و11.
  11. 1 2 بير مارتن-لوف . 1966. الإحصاء من وجهة نظر الميكانيكا الإحصائية . ملاحظات المحاضرات، المعهد الرياضي، جامعة آرهوس. ("صيغة سوندبيرج"، منسوبة إلى أندرس مارتن-لوف).
  12. 1 2 بير مارتن لوف . 1970. Statistiska Modeller (النماذج الإحصائية): Anteckningar från Seminarier läsåret 1969–1970 (مذكرات المحاضرة 1969-1970)، بمساعدة رولف سوندبيرج. جامعة ستوكهولم.
  13. 1 2 مارتن-لوف، ب. مفهوم التكرار واستخدامه كمقياس كمي للانحراف بين فرضية إحصائية ومجموعة من البيانات الرصدية. مع مناقشة من قِبل ف. أبيلدغارد، أ.ب. دمبستر ، د. باسو ، د.ر. كوكس ، أ.و.ف. إدواردز ، د.أ. سبورت، ج.أ. بارنارد ، أ. بارندورف-نيلسن، ج.د. كالفلايش، وج. راش، وردّ من المؤلف. وقائع مؤتمر الأسئلة التأسيسية في الاستدلال الإحصائي (آرهوس، 1973)، ص 1-42. مذكرات، رقم 1، قسم الإحصاء النظري، معهد الرياضيات، جامعة آرهوس، آرهوس، 1974.
  14. 1 2 مارتن-لوف، بير (1974). "مفهوم التكرار واستخدامه كمقياس كمي للتناقض بين الفرضية الإحصائية ومجموعة من البيانات الرصدية". مجلة الإحصاء الإسكندنافية 1 ( 1): 3-18 .
  15. وو ، سي إف جيف (مارس 1983). "حول خصائص تقارب خوارزمية EM" . حوليات الإحصاء . 11 (1): 95-103 . doi : 10.1214 / aos/1176346060 . JSTOR 2240463. MR 0684867 .  
  16. ↑ سوندبيرغ، رولف (2019). النمذجة الإحصائية باستخدام العائلات الأسية . مطبعة جامعة كامبريدج. ISBN 978-1-108-70111-2.
  17. ↑ ليرد، نان (2006). "صيغ سوندبيرغ" . موسوعة العلوم الإحصائية . وايلي. doi : 10.1002/0471667196.ess2643.pub2 . ISBN 0-471-66719-6.
  18. ↑ ليتل، رودريك جيه إيه؛ روبين، دونالد بي. (1987). التحليل الإحصائي مع البيانات المفقودة . سلسلة وايلي في الاحتمالات والإحصاء الرياضي. نيويورك: جون وايلي وأولاده. ص 134-136 . ISBN  978-0-471-80254-9.
  19. 1 2 نيل، رادفورد؛ هينتون، جيفري (1999). "نظرة على خوارزمية EM تبرر المتغيرات التزايدية والمتفرقة وغيرها". في مايكل آي. جوردان (محرر). التعلم في النماذج الرسومية (PDF) . كامبريدج، ماساتشوستس: مطبعة معهد ماساتشوستس للتكنولوجيا. ص 355-368 . ISBN  978-0-262-60032-3تم الاطلاع عليه بتاريخ 22-03-2009 .
  20. 1 2 هاستي، تريفور ؛ تيبشيراني، روبرت ؛ فريدمان، جيروم (2001). "8.5 خوارزمية EM". عناصر التعلم الإحصائي . نيويورك: سبرينغر. ص 236-243 . ISBN  978-0-387-95284-0.
  21. ↑ ليندستروم، ماري جيه؛ بيتس، دوغلاس إم (1988). "خوارزميات نيوتن-رافسون وخوارزمية EM لنماذج التأثيرات المختلطة الخطية لبيانات القياسات المتكررة". مجلة الجمعية الإحصائية الأمريكية . 83 (404): 1014. doi : 10.1080/01621459.1988.10478693 .
  22. ↑ فان دايك، ديفيد أ. (2000). "ملاءمة نماذج التأثيرات المختلطة باستخدام خوارزميات EM الفعالة". مجلة الإحصاءات الحاسوبية والرسومية . 9 (1): 78-98 . doi : 10.2307/1390614 . JSTOR 1390614 . 
  23. ↑ ديفي، إس. إم؛ سميث، إيه. بي؛ ويلش، إيه. إتش؛ كوليس، بي. آر (2017). "خوارزمية EM جديدة مُوسّعة المعلمات (REML) للنماذج الخطية المختلطة" . المجلة الأسترالية والنيوزيلندية للإحصاء . 59 (4): 433. doi : 10.1111/anzs.12208 . hdl : 1885/211365 .
  24. ↑ ماتارازو، تي جيه، وباكزاد، إس إن (2016). "STRIDE لتحديد الهياكل باستخدام خوارزمية التوقع والتعظيم: طريقة تكرارية تعتمد على المخرجات فقط لتحديد الأنماط الاهتزازية." مجلة الهندسة الميكانيكية. http://ascelibrary.org/doi/abs/10.1061/(ASCE)EM.1943-7889.0000951
  25. ↑ كريير، ماركوس؛ كيزيليرسو، عائشة؛ توماس، أنتوني و. (2022). "خوارزمية تعظيم التوقع الخاضعة للرقابة للخلائط: تطبيق على أوقات الانتظار بين الصفقات" . فيزيكا أ: الميكانيكا الإحصائية وتطبيقاتها . 587 (1) 126456. رمز Bibcode : 2022PhyA..58726456K . doi : 10.1016/j.physa.2021.126456 . ISSN 0378-4371 . S2CID 244198364 .  
  26. ↑ إينيك، جي إيه؛ مالوس، جيه تي؛ ريد، دي سي؛ هاينسورث، دي دبليو (يناير 2009). "تقارب معادلة ريكاتي وخوارزمية EM لمحاذاة الملاحة بالقصور الذاتي". معاملات IEEE لمعالجة الإشارات . 57 (1): 370-375 . رمز Bibcode : 2009ITSP...57..370E . doi : 10.1109/TSP.2008.2007090 . S2CID 1930004 . 
  27. ↑ إينيك، جي إيه؛ فالكو، جي؛ مالوس، جي تي (مايو 2010). "تقدير مصفوفة الحالة باستخدام خوارزمية EM للملاحة". رسائل معالجة الإشارات IEEE . 17 (5): 437-440 . Bibcode : 2010ISPL...17..437E . doi : 10.1109/LSP.2010.2043151 . S2CID 14114266 . 
  28. ↑ إينيك، جي إيه؛ فالكو، جي؛ دان، إم تي؛ ريد، دي سي (مايو 2012). "تقدير التباين القائم على المُنعِّم التكراري". رسائل معالجة الإشارات IEEE . 19 (5): 275-278 . Bibcode : 2012ISPL...19..275E . doi : 10.1109/LSP.2012.2190278 . S2CID 17476971 . 
  29. ↑ إينيك، جي إيه (سبتمبر 2015). "الترشيح التكراري وتنعيم القياسات التي تحتوي على ضوضاء بواسون". معاملات IEEE في أنظمة الفضاء والطيران والإلكترونيات . 51 (3): 2205-2211 . Bibcode : 2015ITAES..51.2205E . doi : 10.1109/TAES.2015.140843 . S2CID 32667132 . 
  30. ↑ جمشيديان، مرتضى. جينريش، روبرت آي. (1997). “تسريع خوارزمية EM باستخدام طرق شبه نيوتن”. مجلة الجمعية الإحصائية الملكية، السلسلة ب . 59 (2): 569-587 . دوى : 10.1111 / 1467-9868.00083 . السيد 1452026 . S2CID 121966443 .  
  31. ↑ ليو، سي (1998). "توسيع المعلمات لتسريع خوارزمية EM: خوارزمية PX-EM". Biometrika . 85 (4): 755–770 . CiteSeerX 10.1.1.134.9617 . doi : 10.1093/biomet/85.4.755 . 
  32. ↑ مينغ، شياو لي؛ روبين، دونالد ب. (1993). "تقدير الاحتمال الأقصى باستخدام خوارزمية ECM: إطار عام". Biometrika . 80 ( 2): 267–278 . doi : 10.1093/biomet/80.2.267 . MR 1243503. S2CID 40571416 .  
  33. ↑ ليو، تشوانهاي؛ روبين، دونالد ب (1994). "خوارزمية ECME: امتداد بسيط لخوارزميتي EM وECM مع تقارب رتيب أسرع". Biometrika . 81 (4): 633. doi : 10.1093/biomet/81.4.633 . JSTOR 2337067 . 
  34. ↑ جيانغتاو ين؛ يانفنغ تشانغ؛ ليكسين غاو (2012). "تسريع خوارزميات التوقع والتعظيم مع التحديثات المتكررة" (ملف PDF) . وقائع المؤتمر الدولي لهندسة الكهرباء والإلكترونيات حول الحوسبة العنقودية .
  35. ↑ هانتر دي آر ولانج كيه (2004)، دليل تعليمي حول خوارزميات MM ، الإحصائي الأمريكي، 58: 30-37
  36. ↑ ماتسوياما، ياسوو (2003). "خوارزمية α-EM: تعظيم الاحتمالية البديلة باستخدام مقاييس المعلومات اللوغاريتمية α". معاملات IEEE في نظرية المعلومات . 49 (3): 692-706 . doi : 10.1109/TIT.2002.808105 .
  37. ↑ ماتسوياما، ياسوو (2011). "تقدير نموذج ماركوف المخفي القائم على خوارزمية ألفا-إي إم: نماذج ماركوف المخفية المنفصلة والمتصلة". المؤتمر الدولي المشترك حول الشبكات العصبية : 808-816 .
  38. 1 2 وولينتز، م.س. (1979). "تقدير الاحتمال الأقصى في نموذج خطي من بيانات طبيعية مقيدة ومُراقبة". مجلة الجمعية الإحصائية الملكية، السلسلة ج . 28 (2): 195-206 . doi : 10.2307/2346749 . JSTOR 2346749 . 
  39. ↑ بيرسون، كارل (1894). "مساهمات في النظرية الرياضية للتطور" . المعاملات الفلسفية للجمعية الملكية في لندن، السلسلة أ . 185 : 71-110 . رمز Bibcode : 1894RSPTA.185...71P . doi : 10.1098/rsta.1894.0003 . ISSN 0264-3820 . JSTOR 90667 .  
  40. ↑ شعبان، أمير رضا؛ مهرداد، فرجتبار؛ بو، شي؛ لي، سونغ؛ بايرون، بوتس (2015). "تعلم نماذج المتغيرات الكامنة من خلال تحسين الحلول الطيفية باستخدام طريقة النقطة الخارجية" (ملف PDF) . UAI : 792-801 . مؤرشف من الأصل (ملف PDF) بتاريخ 24-12-2016 . تم الاطلاع عليه بتاريخ 12-06-2019 .
  41. ^ بالي، بورخا كواتوني، أريادنا كاريراس، كزافييه (27/06/2012). تحسين الخسارة المحلية في نماذج المشغلين: نظرة جديدة إلى التعلم الطيفي . او سي ال سي 815865081 . {{cite book}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  42. ↑ لانج، كينيث. "خوارزمية MM" (PDF) .

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

  • هوغ، روبرت؛ ماكين، جوزيف؛ كريغ، ألين (2005). مقدمة في الإحصاء الرياضي . أبر سادل ريفر، نيوجيرسي: بيرسون برنتيس هول. الصفحات 359-364 . 
  • ديلايرت، فرانك (فبراير 2002). خوارزمية تعظيم التوقع (ملف PDF) (التقرير الفني رقم GIT-GVU-02-20). كلية الحوسبة بمعهد جورجيا للتكنولوجيا.يقدم شرحاً أسهل لخوارزمية EM فيما يتعلق بتحقيق الحد الأدنى الأمثل.
  • بيشوب، كريستوفر م. (2006). التعرف على الأنماط والتعلم الآلي . سبرينغر. ISBN 978-0-387-31073-2.
  • غوبتا، إم آر؛ تشين، واي. (2010). "نظرية واستخدام خوارزمية EM". أسس واتجاهات في معالجة الإشارات . 4 (3): 223-296 . CiteSeerX 10.1.1.219.6830 . doi : 10.1561/2000000034 . كتاب قصير مكتوب بشكل جيد حول خوارزمية EM، بما في ذلك اشتقاق مفصل لخوارزمية EM لنماذج GMM وHMM وDirichlet.
  • بيلمز، جيف (1997). دليل مبسط لخوارزمية EM وتطبيقها على تقدير المعلمات لنماذج خليط غاوسي ونماذج ماركوف المخفية (تقرير فني TR-97-021). المعهد الدولي لعلوم الحاسوب.يتضمن اشتقاقًا مبسطًا لمعادلات EM للخلائط الغاوسية ونماذج ماركوف المخفية للخلائط الغاوسية.
  • ماكلاكلان، جيفري جيه؛ كريشنان، ثريامباكام (2008). خوارزمية EM وامتداداتها (الطبعة الثانية  ). هوبوكين: وايلي. ISBN 978-0-471-20170-0.