فهم التوقع–التعظيم
تعلّم نموذج احتمالي من بيانات كاملة أمر مباشر: إذ تتفكك لوغاريتم الإمكان إلى حدّ واحد لكل معلمة، ويمكن تصفير كل مشتقة جزئية على حدة، ويتبين أن كل تقدير نسبةُ تكرارات. وتنشأ الصعوبة حين تكون بعض المتغيرات الداخلة في تلك التكرارات غير مرصودة قط - من أي عنقود جاءت النقطة، وأي موضوع ولّد الوثيقة، وفي أي حالة كانت العملية.
وتحوّل EM التكرارات المفقودة إلى تكرارات متوقَّعة. ففي خطوة التوقع تُستعمل المعالم الحالية لحساب التوزيع البعدي للمتغيرات الخفية عند كل مثال؛ وتسمّى العضوية الكسرية الناتجة مسؤولية. وفي خطوة التعظيم تُطبَّق صيغ الإمكان الأعظم الخاصة بالبيانات الكاملة كما هي، مع إحلال مجموع المسؤوليات محل كل تكرار. وتتناوب الخطوتان حتى تتوقف لوغاريتم الإمكان عن التحرك.
والضمان الذي يجعل هذا يعمل هو أن كل تكرارة تعظّم حدًّا أدنى للوغاريتم الإمكان يلامسها عند المعالم الحالية. ولذلك لا يمكن لتحسين الحد الأدنى أن يسوّئ الإمكان. وهذا ثابت نافع حقًا عند التنفيذ: فإن هبطت لوغاريتم الإمكان يومًا فالبرنامج خاطئ لا سيّئ الحظ.
وما لا يُضمن هو الأمثلية العظمى الشاملة. فالتهيئات المختلفة تتقارب إلى نقاط ثابتة مختلفة، بعضها أسوأ من بعض بكثير؛ والعلاج المعتاد حفنة من الإعادات العشوائية يُحتفظ منها بالملاءمة الأعلى إمكانًا. والحلول المنحلّة ممكنة أيضًا - إذ قد تنطبق مركّبة من المزيج على نقطة واحدة فيؤول تباينها إلى الصفر ويُرسل الإمكان إلى ما لا نهاية - ولذلك تفرض التطبيقات حدًّا أدنى للتباين.
والخوارزمية أعمّ بكثير من التجميع. فتعلّم معالم شبكة بايزية ذات عقد خفية، وتعلّم نموذجي الانتقال والاستشعار لنموذج ماركوف الخفي من الرصدات وحدها (حيث خطوة التوقع هي بالضبط التنعيم الأمامي–الخلفي)، وملاءمة نماذج المتغيرات الكامنة في الإحصاء كله، كلها أمثلة على الخطوتين نفسيهما.
كيفية الحساب
θ⁽ⁱ⁺¹⁾ = argmax_θ Σ_z P(Z = z | x, θ⁽ⁱ⁾) · L(x, Z = z | θ)
حيث
- x
- كل القيم المرصودة عبر جميع الأمثلة
- Z
- كل المتغيرات الخفية عبر جميع الأمثلة
- θ⁽ⁱ⁾
- تقديرات المعالم بعد i تكرارة
- P(Z = z | x, θ⁽ⁱ⁾)
- خطوة التوقع: التوزيع البعدي للمتغيرات الخفية في ظل الملاءمة الحالية
- L(x, Z = z | θ)
- لوغاريتم إمكان البيانات المكمَّلة، وهي التي تُعظَّم في خطوة التعظيم
مثال على التوقع–التعظيم
خذ عشرين نقطة على مستقيم، ثمانٍ منها من مجموعة ضيقة قرب الصفر واثنتا عشرة من مجموعة عريضة قرب الخمسة، مع حجب التسميات. وانطلاقًا من التخمين الفج بأن المتوسطين 0 و5 وأن الانحرافين المعياريين كليهما 1، تتقارب EM في 82 تكرارة، رافعةً لوغاريتم الإمكان رفعًا رتيبًا من −56.616239 إلى −46.633131، ومستقرةً على وزنين 0.347288 و0.652712، ومتوسطين 0.128189 و4.581627، وانحرافين معياريين 0.731077 و2.367312.
وتستعيد تلك المعالم التسميات المحجوبة استعادة تامة. أما القسمة المثلى للمتوسطات k على البيانات نفسها فلا تفعل: إذ تضع x = 1.7 في العنقود الضيق، لأن 1.7 يبعد 1.571811 عن المتوسط الضيق و2.881627 عن العريض. وتقارن EM كثافات لا مسافات، والمركّبة العريضة أوسع بمقدار 3.24 مرة وتحمل الوزن الأكبر، فتنال مسؤولية 0.736211 عن تلك النقطة.
والإعادة مهمة. فمن بين 400 تهيئة عشوائية على هذه البيانات بلغت 385 القيمة −46.633131 وتوقفت الخمس عشرة الباقية عند −48.277387 - وهي ملاءمة أسوأ فعلًا لا يخرج منها أي قدر إضافي من التكرار.
الأسئلة الشائعة
بم تختلف EM عن المتوسطات k؟
تسنِد المتوسطات k كل نقطة بتمامها إلى عنقود واحد وتقارن مسافات إقليدية؛ أما EM فتسنِد مسؤوليات كسرية وتقارن كثافات موزونة، فتستطيع بذلك مراعاة مركّبات مختلفة العرض والحجم. والمتوسطات k هي تقريبًا الحالة الحدية لـ EM على مزيج ذي تباينات كروية متساوية متقلصة.
كيف يُبتّ في التقارب؟
عادةً بمراقبة لوغاريتم الإمكان والتوقف حين يهبط التغير بين التكرارتين دون عتبة. ولأن المتتالية غير متناقصة ومحدودة من أعلى في المسائل حسنة الوضع، فإن هذا الاختبار حسن السلوك؛ ويُستعمل تغير المعالم أحيانًا معيارًا إضافيًا.
هل تجد EM العدد الصحيح للمركّبات؟
لا. فعدد مركّبات المزيج يُثبَّت قبل الملاءمة، تمامًا كما يُثبَّت k في المتوسطات k. ويتطلب اختياره معيارًا لانتقاء النماذج مثل BIC أو الإمكان المتحقَّق منه تقاطعيًا، لأن لوغاريتم الإمكان وحدها تتحسن دائمًا كلما أُضيفت مركّبات.
الخلاصة
خوارزمية EM هي ما يصير إليه الإمكان الأعظم حين يتعذر عدّ التكرارات: خمّنها من النموذج الحالي، ثم أعد الملاءمة، ثم كرّر. ولا ينخفض الإمكان أبدًا، مما يجعل الخوارزمية سهلة الائتمان سهلة التنقيح، لكنها لا تجد قط سوى أمثلية محلية، فأعدها من بدايات متعددة واحتفظ بأفضل ملاءمة.