MMアルゴリズム
Iterative optimization method

MMアルゴリズムは、関数の凸性を利用して最大値または最小値を求める反復最適化手法です。MMは「Majorize-Minimization（最大化-最小化）」または「Minorize-Maximization（最小化-最大化）」の略称で、目的とする最適化が最小化か最大化かによって異なります。MMという名称にもかかわらず、MM自体はアルゴリズムではなく、最適化アルゴリズムの構築方法を記述したものです。

期待最大化アルゴリズムは、 MMアルゴリズムの特殊なケースとして扱うことができます。[1] [2] しかし、EMアルゴリズムでは通常条件付き期待値が関係しますが、MMアルゴリズムでは凸性と不等式が主な焦点であり、ほとんどの場合、理解しやすく適用しやすいです。[3]

歴史

MMアルゴリズムの歴史的基盤は、少なくとも1970年、オルテガとラインボルトが直線探索法に関する研究を行っていた頃に遡ります。[4]同じ概念は、その後も様々な分野で様々な形で再登場しました。2000年には、ハンターとランゲが一般的な枠組みとして「MM」を提唱しました。[5]近年の研究（誰が？）では、この手法が数学、統計学、機械学習、工学など、幅広い分野に適用されています。[要出典]

アルゴリズム

MMアルゴリズム

MMアルゴリズムは、目的関数をマイナー化またはメジャー化する代理関数を見つけることで機能します。代理関数を最適化すると、目的関数の値が向上するか、変化しないかのいずれかになります。

マイナー化最大化版では、最大化される目的関数を とする。アルゴリズムのm番目のステップにおいて、構築された関数は、における目的関数のマイナー化版（代理関数）と呼ばれる。 f ( θ ) {\displaystyle f(\theta )} m = 0 , 1... {\displaystyle m=0,1...} g ( θ | θ m ) {\displaystyle g(\theta |\theta _{m})} θ m {\displaystyle \theta _{m}}

g ( θ | θ m ) ≤ f ( θ )  for all  θ {\displaystyle g(\theta |\theta _{m})\leq f(\theta ){\text{ for all }}\theta }
g ( θ m | θ m ) = f ( θ m ) {\displaystyle g(\theta _{m}|\theta _{m})=f(\theta _{m})}

次に、の代わりにを最大化し、 g ( θ | θ m ) {\displaystyle g(\theta |\theta _{m})} f ( θ ) {\displaystyle f(\theta )}

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

上記の反復法は、 mが無限大に近づくにつれて、局所最適値または鞍点に収束することを保証する。[6]上記の構成により、 f ( θ m ) {\displaystyle f(\theta _{m})}

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

目的関数に対する代替関数の進行が図に示されています。 θ m {\displaystyle \theta _{m}}

Majorize-Minimization は同じ手順ですが、最小化されるのは凸目的です。

代理関数の構築

任意の不等式を用いて、目的関数の望ましいメジャー化/マイナー化バージョンを構築することができます。典型的な選択肢としては、

参考文献

  1. ^ ランゲ、ケネス. 「MMアルゴリズム」(PDF) .
  2. ^ ランゲ、ケネス (2016). MM最適化アルゴリズム. SIAM. doi :10.1137/1.9781611974409. ISBN 978-1-61197-439-3。
  3. ^ Lange, K.; Zhou, H. (2022). 「EMアルゴリズムの遺産」. International Statistical Review . 90 (Suppl 1): S52 – S66 . doi :10.1111/insr.12526. PMC 10191373. PMID 37204987  .  
  4. ^ Ortega, JM; Rheinboldt, WC (1970).多変数非線形方程式の反復解法. ニューヨーク: Academic. pp. 253–255. ISBN 9780898719468。
  5. ^ Hunter, DR; Lange, K. (2000). 「MMアルゴリズムによる分位点回帰」. Journal of Computational and Graphical Statistics . 9 (1): 60– 77. CiteSeerX 10.1.1.206.1351 . doi :10.2307/1390613. JSTOR  1390613. 
  6. ^ Wu, CF Jeff (1983). 「EMアルゴリズムの収束特性について」Annals of Statistics . 11 (1): 95–103 . doi : 10.1214/aos/1176346060 . JSTOR  2240463.
Retrieved from "https://en.wikipedia.org/w/index.php?title=MM_algorithm&oldid=1317118451"