تحقيق أقصى قدر للتوقع (EM)

تحقيق أقصى قدر للتوقع

معلومات عامة

الطبيعة	data clustering algorithm (en)
المخترع	دونالد روبين
تاريخ الاختراع	1977

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

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

المبدأ

نضع n ملاحظات، يعتبر كانه انجاز n متغير عشوائي مستقل، مطابق و موزع $(\mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{n})$. في إطار نموذج إحصائي محدود $,\mathbf {P} _{\boldsymbol {\theta }})$ ξ $(\mathbf {E} _{x},$ . كل $\mathbf {x} _{i},\,i=(\mathbf {} _{1},\mathbf {} _{2},\ldots ,\mathbf {} _{n})$ يتبع نظرية متعلقة بالمعامل $\theta$ . مثلا $\mathbf {x} _{i}$ تستطيع ان تكون دالة غاوسية :(N(µ, σ2 و بالتالي (µ, σ2) ${\boldsymbol {\theta }}=$. نعني بـ: $L(x_{i}),L(x_{i};\theta )$ أو $L(x_{i}|\theta )$ كثافة $\mathbf {X} _{i}$. نسمي احتمالية العينة، الكثافة المرتبطة لـ: $\mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{n}$:

$L(x_{1}),\ldots ,x_{n};\theta )=\prod _{i=1}^{n}L(x_{1};\theta )$

في الحالة الخاصة، في حالة $\mathbf {x} _{i}$ أعداد متقطعة، هذا يعطينا:

$L(x_{1},\ldots ,x_{n};\theta )=\mathbf {P_{\theta }} ({X_{1}=x_{1},\ldots ,X_{n}=x_{n}})=\prod _{i=1}^{n}\mathbf {P_{\theta }} ({X_{i}=x_{i}})$

تعريف : التقدير بالمعنى الاقصى لـ $\theta$ هو:

${\hat {\boldsymbol {\theta }}}=\arg \max _{\boldsymbol {\theta }}L_{n}(x_{1},\ldots ,x_{n};\theta )$

هي إذا، من العينة الثابتة، قيمة المعامل $\theta$ التي تجعل كل ما أمكن الملاحظات المتحصل عليها متماثلة. و لأسباب تحليلية ملائمة، نفضل غالبا حساب اللوغاريتم $\log(L_{n})$ بدلا عن حساب $(L_{n})$، لأن الدالة اللوغاريتمية هي دائما متزايدة، وهذا يضمن الحصول على نفس قيمة $\theta$ التي تعظم الاحتمال:

${\hat {\boldsymbol {\theta }}}=\arg \max _{\boldsymbol {\theta }}\log L_{n}(x_{1},\ldots ,x_{n};\theta )$

وهذا يسهل كثيرا الحسابات، ببساطة للعمل بالجمع عوضا عن الضرب.

مثال

تقدير المعامل لقانون الاحتمال ذو خاصية برنولي (توزيع ثنائي الحدين)، نرمي قطعة نقدية التي يحتمل أن تكون مزورة لـ 30 رمية، نعتبر أنتا حصلنا على 22 مرة خلف و 8 مرات وجه. نعتبر 30 رمية $(x_{1},\ldots ,x_{30})$ انها إنجازات غير مرتبطة ببعضها و تتبع قانون الاحتمال ذو خاصية برنولي (β(p ذو المعامل المجهول p, الذي يإخذ القيمة 1 إذا حصلنا على خلف و 0 إذا حصلنا على وجه. أيضا $X=\sum X_{i}$ عدد المرات التي حصلنا فيها على خلف بإتباع القانون (β(p,30 . وبديهيا ناخد قيمة p بحساب تردد عدد المرات خلف، بالتالي ${\hat {p}}=22/30$ . وهذا يمثل أعلى تقدير لـ p . للتأكد من هذه الفرضية حسابيا، نتبع الخطوات التالية:

احتمال X هو:

$L_{30}(x_{1},\ldots ,x_{30};p)=\prod _{i=1}^{30}\mathbf {P_{p}} (X_{i}=x_{i})=p\sum X_{i}(1-p)^{30-\sum X_{i}}$

و هذا يعني أن احتماله اللوغاريتمي هو:

$\log(L_{30}(x_{1},\ldots ,x_{30};p))=\log(p)\sum _{i=1}^{30}X_{i}+(1-p)(30-\sum _{i=1}^{30}X_{i})$

نبحث لتحقيق أكبر قدر للاحتمال اللوغاريتمي: أقصاه يجب ان يلغي مشتقته و نحلها بـ:

${\frac {d}{dp}}\log(L_{30}(x_{1},\ldots ,x_{30};{\hat {p}}))=0,{\frac {\sum X_{i}}{\hat {p}}}-{\frac {(30-\sum X_{i})}{(1-{\hat {p}})}}=0$

و أخيرا كما هو متوقع

${\hat {p}}={\frac {\sum X_{i}}{30}}$

القارئ بإمكانه التحقق أنه يمثل أقصى نتيجة بفحصه أن المشتقة الثانية تكون سالبة.

ملاحظة هامة: في هذا المثال لحساب المعامل $\theta$ (p في هذا المثال) قمنا بإتباع طريقة تقدير الاحتمال Maximum likelihood و هذا لتوفر كل المعطيات، القطعة النقدية المستعملة في التجربة معلومة (في هذه التجربة استعملنا قطعة نقدية واحدة فلا داعي لتطبيق الخوارزمية EM). ولكن إذا استعملنا قطعتين نقديين لإجراء التجربة، يصبح تقدير المعاملات $p_{i}$ مستحيلا باعتبار أن القطعة النقدية المستعملة في كل رمية غير معلومة (قد تم اختيار قطعة نقدية في كل رمية عشوائيا). هنا تتدخل الخوارزمية EM لتقدير هذه المعاملات.

فلسفة الخوارزمية EM

الخوارزمية EM, هي خوارزمية تكرارية بالنسبة إلى (Dempster, Laird et Rubin (1977. أنها أسلوب لتقدير المعامل المسجل في إطار عام لأعلى احتمال.

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

الخوارزمية تستنبط اسمها نتيجة أنها في كل تكرار تمر بمرحلتين متميزين:

• مرحلة التوقع: غالبا مسماة بالمرحلة E, تعمل كاسمها افتراضا لتقدير المعطيات الغير معلومة أو المخفية، باعتبار أن المعطيات الملحوظة و المعاملات من المرحلة السابقة معلومة.

ملاحظة: في التكرار الأول نقوم باختيار المعاملات عشوائيا. مثلا في المثال أعلاه، المعامل p يختار عشوائيا. ثم نقدر الاحتمال أن تكون المعطيات الملحوظة (عدد مرات الحصول على خلف) هي نتيجة رمي القطعة النقدية رقم "1" أو "2" (هذا هو تقدير المعطيات المخفية).

• مرحلة التعظيم: أوالمرحلة M ,تعمل على تعظيم وتكبير الاحتمال، تجعله متصاعدا. وهذا ممكن باستعمال التقدير للمعطيات الغير معلومة المحسوبة في المرحلة السابقة، و تحديث المعامل أو المعاملات لتستخدم في التكرار القادم (بالتحديد في المرحلة E القادمة).

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

التقارب

(الغير) الخصائص الدقيقة لتقارب الخوارزمية متعلقة بمستوى جد عالي و بالتالي لن نناقشها هنا. لكن ببساطة يجب أن نذكر أن في بعض الحالات، الخوارزمية يمكن أن تتقارب إلى نقطة واحدة أو إلى أقصى قيمة محلية للاحتمال (في حالة ما كانت هذه النقطة موجودة). و هذا راجع إلى الاعتماد القوي على الشرط الأولي $\theta _{0}$ المختار عشوائيا لانطلاق الخوارزمية.

لبعض القيم الأولية السيئة لـ $\theta _{0}$, الخوارزمية يمكن أن تبقى ثابتة في نقطة واحدة. بينما تتقارب إلى أقصى قيمة عامة لبعض القيم الملائمة للشرط الأولي. الخوارزمية إذا تتطلب أحيانا تغيير قيم الشرط الأولي عدة مرات.

تطبيقات

كثيرا ما يستخدم EM لتقسيم البيانات في تعلم الآلة و رؤية الكمبيوتر .حيث نجد في معالجة اللغة الطبيعية، نوعين من الخوارزمية هما: خوارزمية باوم-ولش (Baum-Welch algorithm) و خوارزمية الداخل-الخارج (inside-outside algorithm) من اجل التحريض الغير خاضع للرقابة في قواعد النحو الاحتمالية الخالية من السياق.
في القياس النفسي، لا غنى عن EM لتقدير مميزات الشيء والخصائص الكامنة في نماذج استجابة الاشياء النظرية . مع القدرة على التعامل مع البيانات المفقودة ومراقبة المتغيرات المجهولة الهوية، EM أصبح أداة مفيدة لقياس وإدارة المخاطر.

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

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

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

خطوة تقدير E

تعمل مصفاة كالمان (Kalman) أو المنعم ذو التباين الاصغر المصممان باستعمال مميزات التقديرات الحالية للحصول على تقديرات الوضعية المعدلة.

خطوة تعظيم M

قم باستخدام تقديرات الوضعية المنعمة أو المصفاة داخل حسابات الاحتمال الأكبر للحصول على تقديرات المميزات المعدلة. لنفترض أن مصفاة كالمان ( Kalman) أو المنعم ذو التباين الاصغر يعملان على قياسات مشوشة من نظام وحيد الإدخال و الاخراج. فيمكن الحصول على قياس تقدير تباين التشويش من خلال حساب الاحتمال الأكبر كمايلي:

${\hat {\sigma }}_{v}^{2}={\frac {1}{N}}\sum _{k=1}^{N}{(z_{k}-{\hat {x}}_{k})}^{2}$

حيث ${\hat {x}}_{k}$ تمثل تقديرات البيانات الناتجة التي تم حسابها باستخدام المصفاة أو المنعم
بالمثل يمكن قياس تقدير تباين التشويش كما يلي:

${\hat {\sigma }}_{w}^{2}={\frac {1}{N}}\sum _{k=1}^{N}{({\hat {x}}_{k+1}-{\hat {F}}{\hat {x}}_{k})}^{2}$

حيث ${\hat {x}}_{k}$ و ${\hat {x}}_{k+1}$ تمثل تقديرات الوضعية التي تم حسابها باستخدام المصفاة أو المنعم.
كمانستطيع قياس تقدير معامل النموذج المعدل كما يلي:

${\hat {F}}={\frac {\sum _{k=1}^{N}({\hat {x}}_{k+1}-{\hat {F}}{\hat {x}}_{k})}{\sum _{k=1}^{N}{\hat {x}}_{k}^{2}}}$.

بالإضافة إلى هذا فان تقارب تقديرات المميزات تم دراسته و اثباته.

برهان على صحة EM

EM يعمل على تحسين $Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})$ بدلا من التحسين المباشر لـ: $\log p(\mathbf {X} |{\boldsymbol {\theta }})$. هنا نقوم باظهار ان تحسين هاته الاخيرة يؤدي إلى تحسين الأولى.

من اجل أي $\mathbf {Z}$ باحتمال مختلف عن الصفر $p(\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }})$, نستطيع ان نكتب

$\log p(\mathbf {X} |{\boldsymbol {\theta }})=\log p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})-\log p(\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }})\,.$

ناخذ التقدير على القيم $\mathbf {Z}$ بضرب جميع الاطراف بـ $p(\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)})$ و الجمع حول $\mathbf {Z}$. الطرف الايسر هو تقدير لثابت و بالتالي نحصل على:

${\begin{aligned}\log p(\mathbf {X} |{\boldsymbol {\theta }})&=\sum _{\mathbf {Z} }p(\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)})\log p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})-\sum _{\mathbf {Z} }p(\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)})\log p(\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }})\\&=Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})\,,\end{aligned}}$

اين $H({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})$ معرفة بالمجموع السلبي الذي تعوضه. هذه المعادلة الاخيرة صحيحة لاي قيمة لـ ${\boldsymbol {\theta }}$ إضافة إلى ${\boldsymbol {\theta }}={\boldsymbol {\theta }}^{(t)}$,

$\log p(\mathbf {X} |{\boldsymbol {\theta }}^{(t)})=Q({\boldsymbol {\theta }}^{(t)}|{\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}^{(t)}|{\boldsymbol {\theta }}^{(t)})\,,$

وطرح هذه المعادلة الاخيرة من المعادلة السابقة يعطينا

$\log p(\mathbf {X} |{\boldsymbol {\theta }})-\log p(\mathbf {X} |{\boldsymbol {\theta }}^{(t)})=Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})-Q({\boldsymbol {\theta }}^{(t)}|{\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})-H({\boldsymbol {\theta }}^{(t)}|{\boldsymbol {\theta }}^{(t)})\,,$

بالرغم من ذلك, Gibbs' inequality تثبت انه $H({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})\geq H({\boldsymbol {\theta }}^{(t)}|{\boldsymbol {\theta }}^{(t)})$, و بذلك نستطيع ان نستنتج انه

$\log p(\mathbf {X} |{\boldsymbol {\theta }})-\log p(\mathbf {X} |{\boldsymbol {\theta }}^{(t)})\geq Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})-Q({\boldsymbol {\theta }}^{(t)}|{\boldsymbol {\theta }}^{(t)})\,.$

في الحقيقة اختيار ${\boldsymbol {\theta }}$ لتحسين $Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})$ باستعمال$Q({\boldsymbol {\theta }}^{(t)}|{\boldsymbol {\theta }}^{(t)})$ سيحسن $\log p(\mathbf {X} |{\boldsymbol {\theta }})$ باستعمال $\log p(\mathbf {X} |{\boldsymbol {\theta }}^{(t)})$ .

بدائل لخوارزمية EM

خوارزمية α-EM

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

العلاقة مع أساليب بايز التغييرية

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