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

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

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

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

${\displaystyle 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}})}$

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

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

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

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

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

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

احتمال X هو:

${\displaystyle 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}}}$

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

${\displaystyle \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})}$

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

${\displaystyle {\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}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

${\displaystyle \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 تثبت انه ${\displaystyle H({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})\geq H({\boldsymbol {\theta }}^{(t)}|{\boldsymbol {\theta }}^{(t)})}$, و بذلك نستطيع ان نستنتج انه

${\displaystyle \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)})\,.}$

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

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

[1] [2] [3] [4] [5] [6] [7] [8] [9]

• بوابة إحصاء
• بوابة علم الحاسوب

1. Expectation-Maximization (EM) algorithm Yuzhen Ye School of Informatics and Computing Indiana University, Bloomington Spring 2013
2. Expectation-Maximization Algorithm for Bernoulli Mixture Models a Tutorial: http://blog.zabarauskas.com/expectation-maximization-tutorial/ نسخة محفوظة 2020-01-20 على موقع واي باك مشين.
3. [Dempster et al, 1977] A. P. Dempster, N. M. Laird, D. B. Rubin. "Maximum Likelihood from Incomplete Data via the EM Algorithm". Journal of the Royal Statistical Society. Series B (Methodological) 39 (1): 1–38.
4. [Bishop, 2006] C. M. Bishop. "Pattern Recognition and Machine Learning". Springer, 2006. ISBN 9780387310732.
5. Sean Borman. The Exp ectation Maximization algorithm : A short tu torial. www.isi.edu/natural-language/teaching/cs562/.../B06.pdf, Juillet 2004.
6. Mich ael Collin s. The EM algorithm. www.cse.unr.edu/ b ebis/CS679/Readings/EM_Algorithm_Review.p df, Septemb re 1997.
7. Stephan Morgenthaler. Génétique statistique. Collection « Statistique et probabilités appliquées ». Springer, 2008.
8. Matsuyama, Yasuo (2003). "The α-EM algorithm: Surrogate likelihood maximization using α-logarithmic information measures". IEEE Transactions on Information Theory 49 (3): 692–706. doi:10.1109/TIT.2002.808105
9. Machine Learning A Probabilistic Perspective http://mitpress.mit.edu/books/machine-learning-2 نسخة محفوظة 2020-07-12 على موقع واي باك مشين.