خوارزمية MM

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

يمكن اعتبار خوارزمية التوقع والتعظيم حالة خاصة من خوارزمية MM. ^{[ 1 ] [ 2 ]} ومع ذلك، تتضمن خوارزمية EM عادةً توقعات مشروطة ، بينما تركز خوارزمية MM بشكل أساسي على التحدب والمتباينات، وهي أسهل في الفهم والتطبيق في معظم الحالات. ^{[ 3 ]}

يمكن إرجاع الأساس التاريخي لخوارزمية MM إلى عام 1970 على الأقل، عندما كان أورتيغا وراينبولدت يجريان دراساتٍ متعلقة بطرق البحث الخطي . ^{[ 4 ]} واستمر المفهوم نفسه في الظهور في مجالاتٍ مختلفة بأشكالٍ متنوعة. وفي عام 2000، طرح هنتر ولانج خوارزمية "MM" كإطارٍ عام. ^{[ 5 ] وقد طبّقت دراساتٌ حديثة هذه الطريقة في نطاقٍ واسع من} المجالات، مثل الرياضيات والإحصاء والتعلم الآلي والهندسة . [ ⁶ ]

تعمل خوارزمية MM عن طريق إيجاد دالة بديلة تُقلل أو تزيد من قيمة دالة الهدف. سيؤدي تحسين الدالة البديلة إما إلى تحسين قيمة دالة الهدف أو إبقائها دون تغيير.

بأخذ صيغة التصغير والتعظيم، لنفترض${\displaystyle f(\theta )}$لتكن دالة الهدف المقعرة المراد تعظيمها. في الخطوة m من الخوارزمية،${\displaystyle m=0,1...}$الدالة المُنشأة${\displaystyle g(\theta |\theta _{m})}$سيُطلق عليها اسم النسخة المصغرة من دالة الهدف (الدالة البديلة) في${\displaystyle \theta _{m}}$لو

${\displaystyle g(\theta |\theta _{m})\leq f(\theta ){\text{ لجميع }}\theta }$

${\displaystyle g(\theta _{m}|\theta _{m})=f(\theta _{m})}$

ثم، قم بتحقيق أقصى استفادة${\displaystyle g(\theta |\theta _{m})}$بدلاً من${\displaystyle f(\theta )}$ودع

${\displaystyle \theta _{m+1}=\arg \max _{\theta }g(\theta |\theta _{m})}$

تضمن الطريقة التكرارية المذكورة أعلاه ما يلي:${\displaystyle f(\theta _{m})}$ستتقارب الدالة إلى قيمة مثلى محلية أو نقطة سرجية عندما تؤول قيمة m إلى اللانهاية. ^{[ 7 ]} وفقًا للبناء المذكور أعلاه

${\displaystyle f(\theta _{m+1})\geq g(\theta _{m+1}|\theta _{m})\geq g(\theta _{m}|\theta _{m})=f(\theta _{m})}$

مسيرة${\displaystyle \theta _{m}}$وتظهر الدوال البديلة بالنسبة للدالة الهدف في الشكل.

تُعدّ عملية التكبير والتصغير هي نفس الإجراء ولكن مع هدف محدب يتم تقليله.

يمكن استخدام أي متباينة لبناء النسخة المطلوبة من دالة الهدف، سواء كانت ذات حد أعلى أو أدنى. تشمل الخيارات النموذجية ما يلي:

• عدم المساواة عند جنسن
• متباينة التحدب
• متباينة كوشي-شفارتز
• عدم تساوي المتوسطات الحسابية والهندسية
• التكبير/التصغير التربيعي عبر توسيع تايلور من الدرجة الثانية للدوال القابلة للتفاضل مرتين ذات الانحناء المحدود.