論文の概要: Fair Marriage Principle and Initialization Map for the EM Algorithm
- arxiv url: http://arxiv.org/abs/2007.12845v1
- Date: Sat, 25 Jul 2020 03:23:49 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-07 00:44:31.566112
- Title: Fair Marriage Principle and Initialization Map for the EM Algorithm
- Title(参考訳): emアルゴリズムにおける公正結婚原理と初期化写像
- Authors: Chenguang Lu
- Abstract要約: 論文は、EMアルゴリズムの一般的な収束理論は間違っていると主張している。
局所極大Qは収束速度に影響を与えるが、大域収束をブロックすることはできない。
改良されたEMアルゴリズムはChannel Matching (CM) EMアルゴリズムと呼ばれ、世界収束を加速することができる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The popular convergence theory of the EM algorithm explains that the observed
incomplete data log-likelihood L and the complete data log-likelihood Q are
positively correlated, and we can maximize L by maximizing Q. The Deterministic
Annealing EM (DAEM) algorithm was hence proposed for avoiding locally maximal
Q. This paper provides different conclusions: 1) The popular convergence theory
is wrong; 2) The locally maximal Q can affect the convergent speed, but cannot
block the global convergence; 3) Like marriage competition, unfair competition
between two components may vastly decrease the globally convergent speed; 4)
Local convergence exists because the sample is too small, and unfair
competition exists; 5) An improved EM algorithm, called the Channel Matching
(CM) EM algorithm, can accelerate the global convergence. This paper provides
an initialization map with two means as two axes for the example of a binary
Gaussian mixture studied by the authors of DAEM algorithm. This map can tell
how fast the convergent speeds are for different initial means and why points
in some areas are not suitable as initial points. A two-dimensional example
indicates that the big sample or the fair initialization can avoid global
convergence. For more complicated mixture models, we need further study to
convert the fair marriage principle to specific methods for the
initializations.
- Abstract(参考訳): EMアルゴリズムの一般的な収束理論は、観測された不完全データ対数対数対数対数対数対数と完全データ対数対数Qが正の相関関係にあり、Qを最大化することでLを最大化することができることを説明している。
1) 一般的な収束理論は間違っている。
2) 局所極大Qは収束速度に影響を与えるが、大域収束をブロックすることはできない。
3) 結婚競争と同様に,二成分間の不公平競争は,世界的な収束速度を大幅に減少させる可能性がある。
4) サンプルが小さすぎて不公平な競争が存在するため,局所収束が存在する。
5)Channel Matching (CM) EMアルゴリズムと呼ばれる改良されたEMアルゴリズムは,グローバル収束を加速することができる。
本稿では,DAEMアルゴリズムの著者らによって研究された二元ガウス混合の例として,二つの手段を2つの軸とする初期化写像を提案する。
このマップは、収束速度がどれくらい速く、なぜいくつかの領域の点が初期点として適さないかを示すことができる。
2次元の例は、大きなサンプルや公正な初期化が大域収束を避けることができることを示している。
より複雑な混合モデルでは、フェア結婚の原則を初期化の特定の方法に変換するためにさらなる研究が必要である。
関連論文リスト
- Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳(メタデータ) (2023-01-10T12:18:47Z) - Rank-1 Matrix Completion with Gradient Descent and Small Random
Initialization [15.127728811011245]
我々は,GDの暗黙的正規化が分析において重要な役割を担っていることを示す。
我々は、手頃な分析において暗黙の正規化GDが重要な役割を担っていることを観察する。
論文 参考訳(メタデータ) (2022-12-19T12:05:37Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Bregman divergence based em algorithm and its application to classical
and quantum rate distortion theory [61.12008553173672]
本稿では,Bregman分散系における指数サブファミリーと混合サブファミリー間のBregman分散の最小化問題に対処する。
このアルゴリズムを量子設定を含む歪みとその変種の評価に適用する。
論文 参考訳(メタデータ) (2022-01-07T13:33:28Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - Understanding and Accelerating EM Algorithm's Convergence by Fair
Competition Principle and Rate-Verisimilitude Function [0.40611352512781856]
本稿では,異なる収束困難を説明するために婚姻競争を利用し,フェアコンペティション原則(FCP)を提案する。
この収束証明はシャノンらによる変分的および反復的手法を採用する。
速度歪み関数の分析に使用される。
論文 参考訳(メタデータ) (2021-04-21T20:27:25Z) - Constrained Ensemble Langevin Monte Carlo [7.000381889390774]
我々は、「アンサンブル」という概念を使い、多数の粒子が一緒に進化し、隣の粒子が互いに勾配情報を提供するようにしている。
適切なチューニングを行うことで、サロゲーションは合理的な数値的な節約をもたらすのに十分な頻度で行われることを示す。
適切なチューニングを行うことで、サロゲーションは合理的な数値的な節約をもたらすのに十分な頻度で行われることを示す。
論文 参考訳(メタデータ) (2021-02-08T15:30:37Z) - A Unified Analysis of First-Order Methods for Smooth Games via Integral
Quadratic Constraints [10.578409461429626]
本研究では、滑らかで強可変なゲームやイテレーションのための一階法に積分二次的制約理論を適用する。
我々は、負の運動量法(NM)に対して、既知の下界と一致する複雑性$mathcalO(kappa1.5)$で、初めて大域収束率を与える。
一段階のメモリを持つアルゴリズムでは,バッチ毎に1回だけ勾配を問合せすれば,高速化は不可能であることを示す。
論文 参考訳(メタデータ) (2020-09-23T20:02:00Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳(メタデータ) (2020-05-09T02:48:23Z) - Replica Exchange for Non-Convex Optimization [4.421561004829125]
勾配降下(GD)は凸目的関数に対して急速に収束することが知られているが、局所的なミニマに閉じ込められることがある。
ランゲヴィン力学(LD)は状態空間を探索し、大域的な最小値を見つけることができるが、正確な推定を得るためには、LDは小さな離散化ステップサイズで実行し、弱い力を検証する必要がある。
本稿では,これら2つのアルゴリズムとその非スワッピング変種が,単純な交換機構によって協調可能であることを示す。
論文 参考訳(メタデータ) (2020-01-23T03:13:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。