Algoritmus MM - MM algorithm

The Algoritmus MM je iterativní optimalizace metoda, která využívá konvexnost funkce za účelem nalezení jejích maxim nebo minim. MM znamená „Majorize-Minimization“ nebo „Minorize-Maximization“, podle toho, zda je požadovaná optimalizace maximalizací nebo minimalizací. MM sám o sobě není algoritmus, ale popis toho, jak postavit optimalizační algoritmus.

The algoritmus očekávání – maximalizace lze považovat za speciální případ MM algoritmu.^[1][2]V algoritmu EM podmíněná očekávání jsou obvykle zahrnuty, zatímco v algoritmu MM jsou hlavním zaměřením konvexita a nerovnosti a ve většině případů je snazší pochopit a aplikovat je.^{[je zapotřebí objasnění ]}

Dějiny

Historický základ algoritmu MM lze datovat přinejmenším do roku 1970, kdy Ortega a Rheinboldt prováděli studie týkající se vyhledávání linek metody.^[3] Stejný koncept se nadále objevoval v různých oblastech v různých formách. V roce 2000 navrhli Hunter a Lange „MM“ jako obecný rámec.^[4] Nedávné studie^{[SZO? ]} aplikovali metodu v široké škále tematických oblastí, jako např matematika, statistika, strojové učení a inženýrství.^{[Citace je zapotřebí ]}

Algoritmus

Algoritmus MM funguje tak, že najde náhradní funkci, která zmenší nebo zvětší objektivní funkci. Optimalizace náhradní funkce buď zlepší hodnotu objektivní funkce, nebo ji ponechá beze změny.

Vezmeme-li verzi minorize-maximization, dovolte ${ displaystyle f ( theta)}$ být cílem konkávní funkce, která má být maximalizována. Na m krok algoritmu, ${ displaystyle m = 0,1 ...}$, vytvořená funkce ${ displaystyle g ( theta | theta _ {m})}$ bude nazývána minorizovanou verzí objektivní funkce (náhradní funkce) v ${ displaystyle theta _ {m}}$ -li

${ displaystyle g ( theta | theta _ {m}) leq f ( theta) { text {pro všechny}} theta}$

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

Pak maximalizujte ${ displaystyle g ( theta | theta _ {m})}$ namísto ${ displaystyle f ( theta)}$a nechte

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

Výše uvedená iterační metoda to zaručí ${ displaystyle f ( theta _ {m})}$ bude konvergovat k místnímu optimálnímu nebo sedlovému bodu jako m jde do nekonečna.^[5] Podle výše uvedené konstrukce

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

Pochodující z ${ displaystyle theta _ {m}}$ a náhradní funkce vzhledem k objektivní funkci jsou znázorněny na obrázku.

Algoritmus MM

Majorize-Minimization je stejný postup, ale s konvexním cílem je minimalizován.

Sestavení náhradní funkce

Lze použít libovolnou nerovnost ke konstrukci požadované majorizované / minorizované verze objektivní funkce. Mezi typické možnosti patří

• Jensenova nerovnost
• Konvexita nerovnost
• Cauchy – Schwarzova nerovnost
• Nerovnost aritmetických a geometrických prostředků
• Kvadratická majorizace / mininorizace prostřednictvím druhého řádu Taylorova expanze dvakrát rozlišitelných funkcí s omezeným zakřivením.

Reference