MM algoritmi - MM algorithm

The MM algoritmi iterativdir optimallashtirish dan foydalanadigan usul qavariqlik uning maksimal yoki minimalarini topish uchun funktsiya. MM kerakli optimallashtirish maksimallashtirish yoki minimallashtirish bo'lishiga qarab "Majorize-Minimization" yoki "Minorize-Maximization" degan ma'noni anglatadi. MM ning o'zi algoritm emas, balki an ni qanday tuzishni tavsiflaydi optimallashtirish algoritmi.

The kutish - maksimallashtirish algoritmi MM algoritmining alohida holati sifatida qarash mumkin.^[1]^[2]Biroq, EM algoritmida shartli kutishlar odatda ishtirok etadilar, MM algoritmida esa konveksiya va tengsizliklar asosiy diqqat markazida bo'lib, ko'p hollarda tushunish va qo'llash osonroq.^{[tushuntirish kerak ]}

Tarix

MM algoritmining tarixiy asosini kamida 1970 yilda, Ortega va Reynboldt bilan bog'liq tadqiqotlarni olib borishda boshlash mumkin. chiziqlarni qidirish usullari.^[3] Xuddi shu kontseptsiya turli sohalarda turli shakllarda qayta paydo bo'lishni davom ettirdi. 2000 yilda Hunter va Lange umumiy asos sifatida "MM" ni taklif qilishdi.^[4] So'nggi tadqiqotlar^{[JSSV? ]} kabi mavzuni keng doirada qo'lladilar matematika, statistika, mashinada o'rganish va muhandislik.^{[iqtibos kerak ]}

Algoritm

MM algoritmi maqsad funktsiyasini kichraytiradigan yoki kattalashtiradigan surrogat funktsiyasini topish orqali ishlaydi. Surroqat funktsiyasini optimallashtirish maqsad vazifasining qiymatini yaxshilaydi yoki uni o'zgarishsiz qoldiradi.

Minorallashtirish-maksimallashtirish versiyasini olaylik ${ displaystyle f ( theta)}$ maksimallashtiriladigan ob'ektiv konkav funktsiyasi bo'ling. Da $m$ algoritm bosqichi, ${ displaystyle m = 0,1 ...}$ , tuzilgan funktsiya ${ displaystyle g ( theta | theta _ {m})}$ da ob'ektiv funktsiyaning kichiklashtirilgan versiyasi (o'rnini bosuvchi funktsiya) deb nomlanadi ${ displaystyle theta _ {m}}$ agar

{ displaystyle g ( theta | theta _ {m}) leq f ( theta) { text {for all}} theta}

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

Keyin, maksimal darajaga ko'taring ${ displaystyle g ( theta | theta _ {m})}$ o'rniga ${ displaystyle f ( theta)}$ va ruxsat bering

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

Yuqoridagi takroriy usul bunga kafolat beradi ${ displaystyle f ( theta _ {m})}$ sifatida mahalliy tegmaslik yoki egar joyiga yaqinlashadi $m$ cheksizlikka boradi.^[5] Yuqoridagi qurilish bo'yicha

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

Yurish ${ displaystyle theta _ {m}}$ va maqsad vazifasiga nisbatan surrogat funktsiyalari rasmda ko'rsatilgan.

MM algoritmi

Majorize-Minimallashtirish xuddi shunday protsedura, ammo konveks maqsadi minimallashtiriladi.

Surrogat funktsiyasini qurish

Maqsad funktsiyasining kerakli kattalashtirilgan / kichraytirilgan versiyasini qurish uchun har qanday tengsizlikdan foydalanish mumkin. Odatda tanlovga quyidagilar kiradi

Jensen tengsizligi
Qavariq tengsizlik
Koshi-Shvarts tengsizligi
Arifmetik va geometrik vositalarning tengsizligi
Ikkinchi tartib bo'yicha kvadratik kattalashtirish / minalashtirish Teylorning kengayishi egri chiziqli ikki marta farqlanadigan funktsiyalar.

Adabiyotlar

^ Lange, Kennet. "MM algoritmi" (PDF).
^ Kennet Lange: "MM optimallashtirish algoritmlari", SIAM, ISBN 978-1-611974-39-3 (2016).
^ Ortega, JM.; Reynboldt, Vashington (1970). Bir nechta o'zgaruvchilardagi chiziqli tenglamalarning takroriy echimlari. Nyu-York: akademik. pp.253 –255. ISBN 9780898719468.
^ Hunter, D.R .; Lange, K. (2000). "MM algoritmi orqali kvantil regressiya". Hisoblash va grafik statistika jurnali. 9 (1): 60–77. CiteSeerX 10.1.1.206.1351. doi:10.2307/1390613. JSTOR 1390613.
^ Vu, C. F. Jeff (1983). "EM algoritmining konvergentsiya xususiyatlari to'g'risida". Statistika yilnomalari. 11 (1): 95–103. doi:10.1214 / aos / 1176346060. JSTOR 2240463.

[1] Lange, Kennet. "MM algoritmi" (PDF).

[2] Kennet Lange: "MM optimallashtirish algoritmlari", SIAM, ISBN 978-1-611974-39-3 (2016).

[3] Ortega, JM.; Reynboldt, Vashington (1970). Bir nechta o'zgaruvchilardagi chiziqli tenglamalarning takroriy echimlari. Nyu-York: akademik. pp.253 –255. ISBN 9780898719468.

[4] Hunter, D.R .; Lange, K. (2000). "MM algoritmi orqali kvantil regressiya". Hisoblash va grafik statistika jurnali. 9 (1): 60–77. CiteSeerX 10.1.1.206.1351. doi:10.2307/1390613. JSTOR 1390613.

[5] Vu, C. F. Jeff (1983). "EM algoritmining konvergentsiya xususiyatlari to'g'risida". Statistika yilnomalari. 11 (1): 95–103. doi:10.1214 / aos / 1176346060. JSTOR 2240463.

[1]

[2]

[3]

[4]

[5]