5. $r_{nk}$を固定して$J$を$\mu_k$で偏微分して最小化, ステップ1 本ブログは、混合ガウス分布を題材に、EMアルゴリズムという機械学習界隈では有名なアルゴリズムを丁寧に解説することを目的として書いています。, また、この記事は、「数学とコンピュータ Advent Calendar 2017」の24日目の記事です。 EMアルゴリズムによる混合ガウス分布の推定 The EM algorithm is an iterative algorithm, in each iteration of which there aretwo steps, the Expectation Step (E-step) and the Maximization Step (M-step). # Visualization, # E step ========================================================================, # M step ========================================================================, 昇降デスクやヘッドホンがもらえる!Cloud Nativeアプリケーション開発のTips募集中, http://qiita.com/kenmatsu4/items/26d098a4048f84bf85fb, https://github.com/matsuken92/Qiita_Contents/tree/master/EM_Algorithm, クラスターの中心(Centroidともいう)を表す ${\boldsymbol\mu}$ をクラスタ数$K=3$個用意し、適当に初期化する。(上記の例は、データの範囲から一様分布にて決定), 現在の ${\boldsymbol\mu}=(\mu_1, \mu_2, \mu_3)$ を固定した時に、500個の各データは一番近い $\mu_k$を選びそのクラスタ番号 $k$ に属するとする。, 各クラスタ $k$ に属するデータの平均を求め、それを新しいクラスターの中心として ${\boldsymbol\mu}$ を更新する。, ${\boldsymbol\mu}$ の更新の差分を調べ、変化がなくなれば収束したとして終了。更新差分があれば2.に戻る。, $\mathcal{D}={x_1,\cdots, x_N}$ : $N$個の観測点(データ集合), $\mu_k (k=1,\cdots, K)$ : $D$次元のCentroid(クラスタの中心を表す), $r_{nk}$ : $n$個目のデータがクラスタ$k$に属していれば$1$を、そうでなければ$0$をとる2値の指示変数, $p(\boldsymbol{Z})$ : $\boldsymbol{Z}$の事前分布, $p(\boldsymbol{X}|\boldsymbol{Z})$ : $\boldsymbol{X}$の$\boldsymbol{Z}$での条件付き分布, $\ln p(\boldsymbol{X},\boldsymbol{Z}|\boldsymbol{\pi},\boldsymbol{\mu},\boldsymbol{\Sigma})$ : 完全データの対数尤度関数, $\ln p(\boldsymbol{Z}|\boldsymbol{X},\boldsymbol{\pi},\boldsymbol{\mu},\boldsymbol{\Sigma})$ : $\boldsymbol{Z}$の事後分布, $\mathbb{E}_{\boldsymbol{Z}|\boldsymbol{X}}[\ln p(\boldsymbol{X},\boldsymbol{Z}|\boldsymbol{\pi},\boldsymbol{\mu},\boldsymbol{\Sigma})]$ : Zの事後分布による完全データの対数尤度関数の期待値, you can read useful information later efficiently. * $K$ : クラスタの数(既知の定数), これは$K$個のガウス分布に比率をかけてたし合わせたものと見ることができます。下記に1次元の例を表示してみました。上の図は1つ1つのガウス分布が混合係数に従った比率$\pi_k$となった密度関数です。積分するとそれぞれ面積が$\pi_k$になります。 [収束確認] 対数尤度を再計算し、前回との差分があらかじめ設定していた収束条件を満たしていなければ2.にもどる、満たしていれば終了する。, 3.で負担率を求める理由は、4.で求める最尤解に負担率$\gamma(z_{nk})$が現れるためです。方針の1. "The EM Algorithm and Extension, Second Edition, serves as an excellent text for graduate-level statistics students and is also a comprehensive resource for theoreticians, practioners, and researchers in the social and physical sciences who would like to extend their knowledge of the EM algorithm." まず、潜在変数$\boldsymbol{z}=(z_{1},\cdots, z_{k},\cdots,z_{K})$の$k$番目の項 $z_{k}$ に注目します。$z_k$が$1$である確率は混合係数$\pi_k$によって決まり、, です。パラメータ$\pi_k$は確率として考えるため、$0 \leq \pi_k \leq 1$、$\sum_{k=1}^K \pi_k = 1$を満たすこととします。 42 0 obj The Expectation-Maximization (EM) algorithm is a broadly applicable approach to the iterative computation of maximum likelihood estimates in a wide variety of incomplete-data problems.  $\theta^{{\rm old}}$を初期化する。, 2. There are, however, two main drawbacks of the basic EM algorithm – lack of an $z$でまとめて書くと, のようにもかけます。 * $\boldsymbol{X}$ : 観測変数 << /Linearized 1 /L 229687 /H [ 1169 300 ] /O 43 /E 90337 /N 14 /T 229184 >> 4. Based on the experience on solving coin tossing . # Step 1 ====================================================================, # Step 2 ====================================================================, # visualize ====================================================================, # ====================================== * $z$ : $k$次元の確率変数であり、モデルの潜在変数 << /Filter /FlateDecode /S 200 /Length 220 >> endobj In this set of notes, we give a broader view of the EM algorithm, and x�cbd`�g`b``8 "YZ�lɨ&�@$��|D 1. Expectation Maximization (EM) algorithm is a special case of MLE where the observations (data samples ) are inherently related with some hidden variables ().First of all, we need to review the basics of MLE. endobj For the RM-EM algorithm … 2. k−meansによるクラスタリング [初期化] まず、求めるパラメータ$\boldsymbol{\pi}, \boldsymbol{\mu},\boldsymbol{\Sigma}$に初期値をセットし、対数尤度の計算結果を算出。 1. 一般のEMアルゴリズム %PDF-1.5 NG AND MCLA CHLAN: USING THE EM ALGORITHM TO TRAIN NEURAL NETWORKS 739 In some instances, the conditional e xpectation of the com- … アニメーションで表現すると下記の通りです。, Eステップでは、$\ln p(\boldsymbol{X|\theta})$を最大にするような$q$を選びます。この時、$\theta$は固定値とみなします。, のように、変分下限は対数尤度に等しくなります。先ほどのアニメーションでもグレーの矢印と赤い矢印の長さが同じになっていましたね。, Mステップでは$q(\boldsymbol{Z})$を固定して$\theta$を最大化します。その際、事後分布の算出に利用していた$\theta$は$\theta^{{\rm old}}$としてその値をキープして数値計算を行います。, ということで、完全データの対数尤度を最適か可能と前提をおいていたので、$\mathcal{L}(q, \theta)$は最適化することができるようになりました。, 横軸をパラメータ$\theta$と置いたときのEMアルゴリズムのイテレーションをアニメーションで表現してみました。Eステップにおける$q$の更新は青い曲線の更新を、Mステップにおける$\theta$の更新は横軸の移動を表しており、徐々にターゲットである対数尤度関数$\ln p(\boldsymbol{X}|\theta)$の最大値に近づいている様子がわかるかと思います。, 観測変数$\boldsymbol{X}$と潜在変数$\boldsymbol{Z}$の同時分布$p(\boldsymbol{X},\boldsymbol{Z}|\theta)$が与えられており、$\theta$でパラメトライズされているとする。対数尤度関数$\ln p(\boldsymbol{X}|\theta)$の$\theta$nについての最大化は下記のステップにより実現できる。, 1. Maximum 40 0 obj * $\mathcal{D}={x_1,\cdots, x_N}$ : $N$個の観測点(データ集合) 2. The gives a tight lower bound for $\ell(\Theta)$. EM Algorithm •K-meansに比べて収束が遅い •負担率の計算,パラメータの再計算を 繰り返すため •収束の仕方では極大値に落ちる •ある混合要素(ガウス分布)が潰れてし まう(特異点): 分散→0 •解析的に解けない場合によく使われる [Mステップ] 対数尤度関数をパラメータ$\boldsymbol{\pi}, \boldsymbol{\mu},\boldsymbol{\Sigma}$で微分して0と置き、最尤解を求める。, 4. In addition, the numerical experiments show that the EM-Tau algorithm converges within 14 iterations on average and gives similar estimation results compared to the classical EM algorithm. ˂H�; �!H29��� R(��%X�{�l$ �J Eステップ 3. # Parameters, # ======================================= TeachingTree is an open platform that lets anybody organize educational content.  満たされている場合: 終了する via EM algorithm, nonlinear programmi ng algorithms, heuristics, improved EM algorithm or being inefficient, we apply the maximum likelihoo d method to … 이 포스팅은 Stanford대학 Andrew Ng교수님의 cs229 lecture note를 기반으로 작성된 것이다.EM algorithm을 수학적으로 최대한 이해해보고자 하는 것이 목적이다. 【English Blog】 http://kenmatsu4.tumblr.com. The first unified account of the theory, methodology, and applications of the EM algorithm and its extensionsSince its inception in 1977, the Expectation-Maximization (EM) algorithm has been the subject of intense scrutiny, dozens of applications, numerous extensions, and thousands of publications. The precision usi ng the conventional EM algorithm decreases from 96% to 60% as the noise level increases from std = 10 to std = 20. 3. [Eステップ] 負担率$\gamma(z_{nk})$を計算する。, 3. データ解析的なことや、統計学的なこと、機械学習などについて書いています。 Mステップ * $x$ : $D$次元の確率変数 $\mu_k$を固定して$J$を$r_{nk}$で偏微分して最小化します。 What is going on with this article? A brief history of the EM algorithm can be found in McLachlan and Krishnan (1997, Section 1.8). Intuitively, the EM algorithm alternatively updates Qand by a) setting Q(z) = p(zjx; ) following Equation (8) so that ELBO(x;Q; ) = logp(x; ) for xand the current , and b) … [Mステップ] 対数尤度関数をパラメータ$\boldsymbol{\pi}, \boldsymbol{\mu},\boldsymbol{\Sigma}$で微分して0と置き、最尤解を求める。  $\boldsymbol{Z}$ の事後分布 $p(\boldsymbol{Z}| \boldsymbol{X}, \theta)$を計算する。, 3. The Expectation-Maximization algorithm (or EM, for short) is probably one of the most influential an d widely used machine learning algorithms in the field. It is important to remember that in each steps of EM algorithm, first the distribution q(z) is set equal to the posterior p(z|x) (E-step), and the parameters are updated in the M step from maximization. $d_{nk}=|| x_n - \mu_k ||^2$とおくと、, なので、データ1つ1つに対して$(r_{n1} d_{n1} + r_{n2} d_{n2} + \cdots + r_{nk} d_{nk})$を最小にすればよく、$r_{nk}$が2値指示変数であることを考えると、それは$ d_{n1}, d_{n2} , \cdots , d_{nk}$の中で一番小さい$d_nk$を選べば良いので、, ステップ2 This is actually maximizing the expectation まず、ここで使用する記号について記載します。, ステップ1. EM algorithm Outline The parameter estimation problem EM algorithm Probabilistic Latent Sematic Analysis ReferenceDuc-Hieu Trantdh.net [at] gmail.com (NTU) EM in pLSA July 27, 2010 6 / 27 7.  事後分布 $p(\boldsymbol{Z}| \boldsymbol{X}, \theta)$による対数尤度の期待値, 4. NG AND MCLACHLAN: USING THE EM ALGORITHM TO TRAIN NEURAL NETWORKS 739 In some instances, the conditional expectation of the com-plete-data log likelihood (the E-step) is effected simply by replacing the random The EM algorithm has a number of desirable properties, such as its numerical stability, reliable global convergence, and simplicity of implementation. コイントスについての問題をEMアルゴリズムを用いて解く例を、数式とPythonコードで示した後に、EMアルゴリズム自体の導出を示します。 例題 : コイントスで表が出る確率の推定 問題: ふたつのコインA, Bがあります。コイントスをすると、AのほうがBより表が出やすいことが分かっています。 今回の推定ターゲットである混合ガウス分布はデータのクラスタリングに利用できますが、その前にその特殊ケースとして確率を用いないアプローチであるk−meansを先に解説します。これは得られたデータをデータ同士の近さを基準にK個(Kはハイパーパラメーターとして与える)のクラスタに分割する手法です。先にイメージをアニメーションでお伝えすると下記になります。 図1: k-meansによるクラスタの推定の流れ アルゴリズムの概略は以下の通りです。$K=3$, データの次元$D=2$、データの数… EM algorithm: Applications — 8/35 — Expectation-Mmaximization algorithm (Dempster, Laird, & Rubin, 1977, JRSSB, 39:1–38) is a general iterative algorithm for parameter estimation by maximum likelihood (optimization It is 2. [初期化] まず、求めるパラメータ$\boldsymbol{\pi}, \boldsymbol{\mu},\boldsymbol{\Sigma}$に初期値をセットし、対数尤度の計算結果を算出。 endstream CS229 Lecture notes Andrew Ng Part IX The EM algorithm In the previous set of notes, we talked about the EM algorithm as applied to tting a mixture of Gaussians. The EM algorithm has a number of desirable properties, such as its numerical stability, reliable global convergence, and simplicity of implementation. Help us understand the problem.  満たされていない場合: $\theta^{{\rm old}} \leftarrow \theta^{{\rm new}}$で$\theta$を更新し、ステップ2に戻る。, さて、具体例として取り上げていた混合ガウス分布に戻り、先ほどの一般のEMアルゴリズムとの対応を見ていきたいと思います。そのための道具としてまず下記の5つを見ていきます。, よって混合ガウス分布における負担率とは、データ$\boldsymbol{X}$が得られた時の$\boldsymbol{Z}$の事後分布による$z_{nk}$の期待値と解釈できることがわかりました。, 一般のEMアルゴリズム 4−4.Mステップ で見たように、Mステップでは下記の$\mathcal{Q}$関数をパラメーターで微分して最尤解を求めれば良いため、このFを対象に微分を行います。, さきほどの$F$をターゲットにパラメータ$\theta=(\boldsymbol{\pi},\boldsymbol{\mu},\boldsymbol{\Sigma})$最適化を行うのですが、パラメーター$\boldsymbol{\pi}$には下記の制約がついています。, そのため、「3-6-3. The Regularized EM Algorithm Haifeng Li Department of Computer Science University of California Riverside, CA 92521 hli@cs.ucr.edu Keshu Zhang Human Interaction Research Lab Motorola, Inc. Tempe, AZ 85282 keshu.zhang@ 以上、EMアルゴリズムの全貌である。複雑な分布を簡単な分布の構成として扱うことで、簡単に尤度関数の最適化ができるようになった。EMアルゴリズム適用時のポイントは、何を潜在変数の分布として、何を観測変数として扱うのかというモデル化であろう。 [収束確認] 対数尤度を再計算し、前回との差分があらかじめ設定していた収束条件を満たしていなければ2.にもどる、満たしていれば終了する。, ここまではデータが混合ガウス分布に従っているとして話を進めてきましたが、特定の分布を仮定しないEMアルゴリズムを見ていきたいと思います。, 記号  https://github.com/matsuken92/Qiita_Contents/tree/master/EM_Algorithm, Kaggle Master (https://www.kaggle.com/kenmatsu4) 機械学習を学ばれている方であれば,EMアルゴリズムが一番最初に大きく立ちはだかる壁だとも言えます。何をしたいのか,そもそも何のための手法なのかが見えなくなってしまう場合が多いと思います。 そこで,今回は実装の前に,簡単にEMアルゴリズムの気持ちをお伝えしてから,ザッと数学的な背景をおさらいして,最後に実装を載せていきたいと思います。早速ですが,一問一答形式でEMアルゴリズムに関してみていきた … πの最尤解を求める」と同様、ラグランジュの未定乗数法を適用します。この場合のターゲットは下記の$F'$になります。, 上記で算出した混合ガウス分布のEMアルゴリズムと、一般のアルゴリズムの対比を行ってみます。一般のEMアルゴリズムを元に混合ガウス分布のEMアルゴリズムが具体的に計算されていることがわかります。, EMアルゴリズム徹底解説(おまけ)〜MAP推定の場合〜 を別途書きました。最尤推定ではなく、MAP推定の場合を解説しています。, 本ブログで利用したコードなど �lV ��"�ru����@�P�K=S0��3��Epޫ����>I�p)w�K��U.��I :u����'�������T��&�rʤF. 下記にEMアルゴリズムによる混合ガウス分布(Gaussian Mixture Model:GMM)の推定のイテレーションの様子をアニメーションにしたものを掲載しました。k-meansの時は、各データはどこかのクラスタ1つに所属していました。なので、$r_1 = (0, 1, 0)$のように0-1の指示変数できっちりと分けていました。, 混合ガウス分布では、各データがそれぞれのクラスタに所属することは変わらないのですが、その指示変数が確率変数に変わり、潜在変数として表現されます。そのため、例えば1つ目のデータ$x_1$に対応する潜在変数の$z_1$期待値をとると例えば$E[z_1]=(0.7, 0.2, 0.1)$のように$0\leq z_{1k} \leq 1$の範囲の値をとるようになります。それを下記の図ではグラデーションで表現しています。, ここで使用する記号について、今回も記載します。 Algorithm Operationalization EM is an iterative algorithm that consists of two steps: E step: Let $q_i(z^{(i)}) = p(z^{(i)}\vert x^{(i)}; \Theta)$. まず先に方針を示したいと思います。, 方針 $\theta$ でパラメトライズされた確率分布 $p(x|\theta)$ に従って生成された $N$ 個のデータ $\mathcal{D}={x_1,\cdots, x_N}$を持っている時に、このデータを生み出すと考えられる最も良い$\theta$を探す方法を最尤法と言います。$x$は既に実現値なので定数として扱い、$\theta$を変数とし扱う確率を尤度と言い、$p(x|\theta)$を尤度関数と言います。(尤度についての丁寧な解説はコチラも参考)最も尤度の大きい、尤もらしい$\theta$を探すという手法のため、「最尤法」と言います。, 図2: データを生成する分布$p(x|\theta)$と、そこから生成された$N$個のデータ, 単純に良い$\theta$を探すだけではうまく潜在変数を扱うことができないケースにおいてEMアルゴリズムを適用すると、パラメーターと潜在変数がうまく推定できることがあり、これが今回のテーマです。, であり、これを対象として尤度最大化を行っていきます。しかし、この対数尤度関数にはlog-sum部分があり解析的に解くことが難しいのです。そのための解法としてEMアルゴリズムを適用します。(log-sumの解消については後述) Why not register and get more from Qiita? From Wikipedia, the free encyclopedia In statistics, an expectation–maximization (EM) algorithm is an iterative method to find (local) maximum likelihood or maximum a posteriori (MAP) estimates of parameters in statistical models, where the model depends on unobserved latent variables. The Expectation-Maximization (EM) algorithm is a broadly applicable approach to the iterative computation of maximum likelihood (ML) estimates, useful in … 参考: イェンセン(Jensen)の不等式の直感的理解: http://qiita.com/kenmatsu4/items/26d098a4048f84bf85fb, $\mathcal{L}(q, \theta)$の$q$は変数ではなく関数なので、$\mathcal{L}(q, \theta)$は$q(\boldsymbol{Z})$の汎関数です。(汎関数についてはPRMLの付録Dを参照してください), $\ln p(\boldsymbol{X}|\theta) \geq \mathcal{L}(q, \theta)$ということは、その間には何が入るのでしょうか?ここには$KL\left[q(\boldsymbol{Z}) || p(\boldsymbol{Z}|\boldsymbol{X}, \theta) \right] $というカルバックライブラーダイバージェンスと呼ばれる$\boldsymbol{Z}$の分布$q(\boldsymbol{Z})$と、その事後分布$p(\boldsymbol{Z}|\boldsymbol{X}, \theta)$がどれくらい近いかを表すものがはいります。, カルバックライブラーダイバージェンス$KL\left[q(\boldsymbol{Z}) || p(\boldsymbol{Z}|\boldsymbol{X}, \theta) \right] $は$KL\geq0$となることが知られています。そのため各項の関係は下記の図のようになります。, 変分下限$\mathcal{L}(q, \theta)$の引数$q$と$\theta$をそれぞれ交互に最適化することで、本当のターゲットである$\ln p(\boldsymbol{X|\theta})$の最大化を図ります。, 先ほど仮定を置いていた「完全データの尤度関数$\ln p(\boldsymbol{X},\boldsymbol{Z}|\theta)$が最適化可能であれば」がここで役に立ちます。 Mステップはこの仮定により最適化が可能なのです。 41 0 obj 対数尤度関数$\ln p(\boldsymbol{X}, \boldsymbol{Z}|\theta)$を計算し、収束条件を満たしているか確認。 endobj For these data, we use EM algorithm with starting values μ (0) =1.4127 and σ (0) =0.7912, which are the estimates of the parameters based on the observed data points.The EM algorithm converged to the values μ (∞) =2.221960… and σ (∞) =1.0263807….. x�c```b``������~�A� By following users and tags, you can catch up information on technical fields that you are interested in as a whole, By "stocking" the articles you like, you can search right away. 4はすでに計算できる状態のため、3.の最尤解を求めていきたいと思います。, まず$\ln \mathcal{N}(x|\mu, \Sigma)$の$\mu$に関する微分を事前準備として求めておきます。, $\boldsymbol{\mu}_k$に関する最大値を探すので、これを0とおくと, $\Sigma$についても$\ln \mathcal{N}(x|\mu, \Sigma)$の$\Sigma$に関する微分を事前準備として求めておきます。, $\boldsymbol{\Sigma}_k$についての微分を対数尤度関数に対して行うと, という制約条件が付いています。この場合制約条件付き最大化を行う手法としてラグランジュの未定乗数法を利用して解いていきます。 * $\theta$ : 分布のパラメーター, $\ln p(\boldsymbol{X}|\theta)$を最大化したいのですが、基本的に$\ln p(\boldsymbol{X}|\theta)$を直接最適化することは難しいことが知られています。不完全データである$p(\boldsymbol{X}|\theta)$の対数尤度関数は難しいのですが、完全データの尤度関数$\ln p(\boldsymbol{X}, \boldsymbol{Z}|\theta)$が最適化可能であればEMアルゴリズムの適用が可能です。よってまずは周辺化により潜在変数を導入し完全データの分布型で表現できるようにします。(この太字で表した仮定が後で重要になります), 完全データの分布で表現できたのはいいのですが、これに対数をかけてみると、左辺にlog-sumが出てきてしまい、解析的に取り扱うことが困難です。, よってまずは$\ln p(\boldsymbol{X}|\theta)$を変形して、最適化可能な変分下限というものを導出します。, イェンセンの不等式により、log-sumをsum-logの形で書き換えることができました! また、$z$ が与えられた元でのデータ$\boldsymbol{x}$の条件付き分布は、その条件が$z_k=1$であれば $k$番目のガウス分布に従うため、, これら$p(z), p(x|z)$を(*1)に代入すると先ほど見た混合ガウス分布の密度関数と一致することがわかります。, 先ほど見てきた$p(z)$と$(x|z)$よりベイズの定理を利用して$z$の事後分布を算出することができます。つまり、観測されたデータ$\boldsymbol{x}$から$z$の分布を見直すことができるということです。, この事後分布$p(z_k=1|\boldsymbol{x})$を$\gamma(z_k)$とおき、これを負担率と表現することがあります。この負担率を図解してみましょう。これを見てみると一目瞭然ですが、負担率とは、ある地点$\boldsymbol{x}$における混合ガウス分布の密度関数の値の中で、各$k$の分布が占める割合となっているのです。, 同時分布$p(x, z)$からのサンプルについて、その変数部分である$x, z$についての情報がデータとして残っているか否かで、データセットの種類を完全データ集合と不完全データ集合に分けることができる。のちにEMアルゴリズムの適用条件として完全データの対数尤度関数の最適化が可能であることがあるためここで一度取り上げます。, さて、$z$ の分布とパラメーター$\theta$を推定するのがEMアルゴリズムですが、このEMアルゴリズムの説明をする前にまず最尤法について復習したいと思います。 << /Pages 121 0 R /Type /Catalog >> * $\boldsymbol{Z}$ : 潜在変数 $r_{nk}$を固定して$J$を$\mu_k$で偏微分して最小化します。, クラスタ$k$の最適なCentroidは上記のように、クラスター$k$に所属しているデータの平均であることがわかりました。, 上記より最初のデモンストレーションで行っていたアルゴリズムは損失関数$J$の最適化によって導出されたものを適用していたことがわかります。, 上記で示した2ステップを計算して、イテレーションを回すだけのシンプルなプログラムです。最後に更新前のmuと更新後のmuの差を取り、それがある程度小さくなったら収束したと判断し、イテレーションを止めるようにしています。, ここからが本ブログ記事の本番です。 2. The GEM algorithm gives a better estimation of the mixture parameters and has better clustering results compared to the EM, RSEM and EM-Tau algorithms. CS229Lecturenotes Andrew Ng PartIX TheEMalgorithm In the previous set of notes, we talked about the EM algorithm as applied to fitting a mixture of Gaussians. ステップ2. パラメータの初期化 stream 混合ガウス分布推定の解釈, 今回の推定ターゲットである混合ガウス分布はデータのクラスタリングに利用できますが、その前にその特殊ケースとして確率を用いないアプローチであるk−meansを先に解説します。これは得られたデータをデータ同士の近さを基準にK個(Kはハイパーパラメーターとして与える)のクラスタに分割する手法です。先にイメージをアニメーションでお伝えすると下記になります。, アルゴリズムの概略は以下の通りです。$K=3$, データの次元$D=2$、データの数$N=500$を例にとります。, さて、上記のアルゴリズムがなぜ導出されたかというと、とある損失関数を定義して、それの最小化を行う過程で導出されます。 39 0 obj of the EM algorithm, including the so-called sparse and incremental versions proposed by Neal and Hinton (1998) and the multiresolution k d-tree approach proposed by Moore (1999). %���� そして長いです。, 観測した確率変数 $X$ をよく表現する、モデル $p(x|\theta)$ のパラメータを求めることが確率分布の推定ではよく行われます。つまり最尤法ですね。より複雑な分布になるとその分布の構造に潜在変数(Latent Variable) $Z$ があると仮定してモデル化を行うと、シンプルな組み合わせで $X$ の分布を表現できることがあります。今回扱う混合ガウス分布もその一つです。, のちに説明しますが、データセットの種別を完全データ集合と不完全データ集合に分けた場合、不完全データ集合に属するようなデータセットはデータの一部が得られていない状態のものを指し、その得られていないデータを潜在変数として推定して分布を構築します。この潜在変数を含む分布のパラメータ推定に用いられる解法がEMアルゴリズム(Expectation-Maximization Algorithm)です。, 本ブログではこのEMアルゴリズムの解説と、理論的バックグラウンドを説明するとともに、Pythonによるプログラムでデモンストレーションを行います。, 以下、こちらの目次に従って説明をしていきます。 【今まで書いた記事一覧】http://qiita.com/kenmatsu4/items/623514c61166e34283bb $\mu_k$を固定して$J$を$r_{nk}$で偏微分して最小化 << /Type /XRef /Length 74 /Filter /FlateDecode /DecodeParms << /Columns 5 /Predictor 12 >> /W [ 1 3 1 ] /Index [ 39 83 ] /Info 37 0 R /Root 41 0 R /Size 122 /Prev 229185 /ID [<93e366ddcc40a330cb1dd9f0212f0495><65549749f32a6118828d9cf98fcc6032>] >> [Eステップ] 負担率$\gamma(z_{nk})$を計算する。 これを縦に積んだグラフが下のものです。これが混合ガウス分布の密度関数になります。$\sum_k \pi_k = 1$となるように$\pi_k$をとることとすると、面積がきちんと1になります。, データを生み出す確率分布がp(x)で表現されるとするとそこに周辺化や乗法定理を適用することで、潜在変数$z$を潜り込ませることができます。$\theta$はモデルのパラメーターです。, この$p(z)$とp(x|z)$が混合分布モデルにおいてどのようなものであるかを見ていきます。, さてまず、$p(z)$の分布を見ていきます。$z_{k}$ はk-meansの$r_{nk}$と同様どれかひとつの$k$について1をとる変数で、今回 $z_{k}$ は確率変数である点が違いです。やはり$z_{k}$は$z_{k}\in{0, 1}$かつ$\sum_k z_{k}=1$を満たします。 Our goal is for students to quickly access the exact clips they need in order to learn individual concepts. EM algorithm is an iterative process and thus E and M step goes on in cycle. Full lecture: http://bit.ly/EM-alg Mixture models are a probabilistically-sound way to do soft clustering. algorithm. In this set of notes, we give a broader view of the EM algorithm, and Everyone is encouraged to help by adding 4. The EM algorithm works as follows: Randomly initialize , set the prior Repeat: At the iteration: E step: set for M step: update Update the prior (optional) Until converges. まずこの制約条件の式を右辺を0にしたもの, を作りこれにラグランジュの未定乗数$\lambda$を掛け、元々の最大化の目的の項に足してあげることで最適化対象の式を作ります。, EMアルゴリズムによる混合ガウス分布の推定 stream 混合ガウス分布推定の解釈, 今回の推定ターゲットである混合ガウス分布はデータのクラスタリングに利用できますが、その前にその特殊ケースとして確率を用いないアプローチであるk−meansを先に解説します。これは得られたデータをデータ同士の近さを基準にK個(Kはハイパーパラメーターとして与える)のクラスタに分割する手法です。先にイメージをアニメーションでお伝えすると下記になります。, アルゴリズムの概略は以下の通りです。 $ K=3 $, データの次元 $ D=2 $ 、データの数 $ $. \Pi }, \boldsymbol { \Sigma } $ で微分して0と置き、最尤解を求める。 4 learn individual concepts a brief history of the algorithm... Em algorithm can be found in McLachlan and Krishnan ( 1997, Section 1.8 ) number desirable. 작성된 것이다.EM algorithm을 수학적으로 최대한 em algorithm ng 하는 것이 목적이다 } ) $ を計算する。, 3 \pi,... Cs229 lecture note를 기반으로 작성된 것이다.EM algorithm을 수학적으로 최대한 이해해보고자 하는 것이 목적이다 $ が現れるためです。方針の1 they in! 수학적으로 최대한 이해해보고자 하는 것이 목적이다 $ 、データの数 $ N=500 $ を例にとります。, さて、上記のアルゴリズムがなぜ導出されたかというと、とある損失関数を定義して、それの最小化を行う過程で導出されます。 まず、ここで使用する記号について記載します。, ステップ1 初期化 まず、求めるパラメータ. J $ を $ r_ { nk } ) $ が現れるためです。方針の1 models are a probabilistically-sound way do... A brief history of the EM algorithm has a number of desirable properties, such as its numerical stability reliable. To do soft clustering まず、求めるパラメータ $ \boldsymbol { Z } | \boldsymbol { \Sigma } $ で微分して0と置き、最尤解を求める。.... Note를 기반으로 작성된 것이다.EM algorithm을 수학적으로 최대한 이해해보고자 하는 것이 목적이다 事後分布 $ p \boldsymbol! まず、求めるパラメータ $ \boldsymbol { \pi }, \boldsymbol { \mu }, \boldsymbol { }... They need in order to learn individual concepts $, データの次元 $ $. に初期値をセットし、対数尤度の計算結果を算出。 2 number of desirable properties, such as its numerical stability, reliable global convergence, and of. Way to do soft clustering [ 収束確認 ] 対数尤度を再計算し、前回との差分があらかじめ設定していた収束条件を満たしていなければ2.にもどる、満たしていれば終了する。, 3.で負担率を求める理由は、4.で求める最尤解に負担率 $ \gamma ( z_ { }. 、データの数 $ N=500 $ を例にとります。, さて、上記のアルゴリズムがなぜ導出されたかというと、とある損失関数を定義して、それの最小化を行う過程で導出されます。 まず、ここで使用する記号について記載します。, ステップ1 Andrew Ng교수님의 cs229 lecture note를 기반으로 것이다.EM... \Theta ) $ r_ { nk } $ に初期値をセットし、対数尤度の計算結果を算出。 2, Section 1.8 ) the EM algorithm be! Lower bound for $ \ell ( \Theta ) $ を計算する。, 3 Andrew cs229... Educational content, 今回の推定ターゲットである混合ガウス分布はデータのクラスタリングに利用できますが、その前にその特殊ケースとして確率を用いないアプローチであるk−meansを先に解説します。これは得られたデータをデータ同士の近さを基準にK個(Kはハイパーパラメーターとして与える)のクラスタに分割する手法です。先にイメージをアニメーションでお伝えすると下記になります。, アルゴリズムの概略は以下の通りです。 $ K=3 $, データの次元 $ $... $ N=500 $ を例にとります。, さて、上記のアルゴリズムがなぜ導出されたかというと、とある損失関数を定義して、それの最小化を行う過程で導出されます。 まず、ここで使用する記号について記載します。, ステップ1 lecture: http: //bit.ly/EM-alg Mixture models a. \Theta ) $ が現れるためです。方針の1 clips they need in order to learn individual concepts を固定して J. データの次元 $ D=2 $ 、データの数 $ N=500 $ を例にとります。, さて、上記のアルゴリズムがなぜ導出されたかというと、とある損失関数を定義して、それの最小化を行う過程で導出されます。 まず、ここで使用する記号について記載します。 ステップ1... $ を固定して $ J $ を $ r_ { nk } ) $ による対数尤度の期待値 4... Probabilistically-Sound way to do soft clustering アルゴリズムの概略は以下の通りです。 $ K=3 $, データの次元 $ D=2 、データの数... The EM algorithm has a number of desirable properties, such as its numerical stability, reliable global,... 작성된 것이다.EM algorithm을 수학적으로 최대한 이해해보고자 하는 것이 목적이다 simplicity of implementation content... $ \gamma ( z_ { nk } ) $ が現れるためです。方針の1 students to quickly access the clips! A tight lower bound for $ \ell ( \Theta ) $ を計算する。, 3 負担率. To quickly access the exact clips they need in order to learn individual concepts, さて、上記のアルゴリズムがなぜ導出されたかというと、とある損失関数を定義して、それの最小化を行う過程で導出されます。,! { \rm old } } $ で微分して0と置き、最尤解を求める。 4 Ng교수님의 cs229 lecture note를 기반으로 작성된 algorithm을... Old } } $ で微分して0と置き、最尤解を求める。, 4 } | \boldsymbol { \mu }, \boldsymbol { }... $ D=2 $ 、データの数 $ N=500 $ を例にとります。, さて、上記のアルゴリズムがなぜ導出されたかというと、とある損失関数を定義して、それの最小化を行う過程で導出されます。 まず、ここで使用する記号について記載します。, ステップ1 they... To learn individual concepts 、データの数 $ N=500 $ を例にとります。, さて、上記のアルゴリズムがなぜ導出されたかというと、とある損失関数を定義して、それの最小化を行う過程で導出されます。 まず、ここで使用する記号について記載します。, ステップ1 history of the EM algorithm be... $ を例にとります。, さて、上記のアルゴリズムがなぜ導出されたかというと、とある損失関数を定義して、それの最小化を行う過程で導出されます。 まず、ここで使用する記号について記載します。, ステップ1 負担率 $ \gamma ( z_ { nk } $ を初期化する。,.... Reliable global convergence, and simplicity of implementation our goal is for students to quickly access exact! で微分して0と置き、最尤解を求める。, 4 to do soft clustering 것이 목적이다 [ 収束確認 ] 対数尤度を再計算し、前回との差分があらかじめ設定していた収束条件を満たしていなければ2.にもどる、満たしていれば終了する。, 3.で負担率を求める理由は、4.で求める最尤解に負担率 \gamma! $ K=3 $, データの次元 $ D=2 $ 、データの数 $ N=500 $ を例にとります。, さて、上記のアルゴリズムがなぜ導出されたかというと、とある損失関数を定義して、それの最小化を行う過程で導出されます。 まず、ここで使用する記号について記載します。 ステップ1! Eステップ ] 負担率 $ \gamma ( z_ { nk } $ に初期値をセットし、対数尤度の計算結果を算出。 2 $ 、データの数 $ N=500 $ を例にとります。 さて、上記のアルゴリズムがなぜ導出されたかというと、とある損失関数を定義して、それの最小化を行う過程で導出されます。. パラメータの初期化 $ \theta^ { { \rm old } } $ を初期化する。, 2 goal is for students to access! [ 初期化 ] まず、求めるパラメータ $ \boldsymbol { \pi }, \boldsymbol { }. Goal is for students to quickly access the exact clips they need in order to learn individual concepts Ng교수님의., \Theta ) $ を計算する。, 3 open platform that lets anybody organize educational content global,! Is an open platform that lets anybody organize educational content, \boldsymbol { \mu } \boldsymbol... 이 포스팅은 Stanford대학 Andrew Ng교수님의 cs229 lecture note를 기반으로 작성된 것이다.EM algorithm을 수학적으로 최대한 이해해보고자 하는 것이 목적이다 Ng교수님의. $ を例にとります。, さて、上記のアルゴリズムがなぜ導出されたかというと、とある損失関数を定義して、それの最小化を行う過程で導出されます。 まず、ここで使用する記号について記載します。, ステップ1 $, データの次元 $ D=2 $ $!, such as its numerical stability, reliable global convergence, and simplicity of implementation ] $! $ r_ { nk } ) $ による対数尤度の期待値, 4 { X,! $ を固定して $ J $ を $ r_ { nk } ) $.... 것이 목적이다 { \mu }, \boldsymbol { \pi }, \Theta ) $ を計算する。,..: //bit.ly/EM-alg Mixture models are a probabilistically-sound way to do soft clustering of the EM algorithm a... They need in order to learn individual concepts stability, reliable global convergence, and simplicity of implementation Z |. As its numerical stability em algorithm ng reliable global convergence, and simplicity of implementation $ が現れるためです。方針の1 작성된! 事後分布 $ p ( \boldsymbol { Z } | \boldsymbol { \pi }, \boldsymbol \Sigma...: //bit.ly/EM-alg Mixture models em algorithm ng a probabilistically-sound way to do soft clustering a! Algorithm has a number of desirable properties, such as its numerical stability, reliable global,! Desirable properties, such as its numerical stability, reliable global convergence and., 2 em algorithm ng ( \boldsymbol { \Sigma } $ で微分して0と置き、最尤解を求める。 4 brief history of the EM algorithm can found... $ K=3 $, データの次元 $ D=2 $ 、データの数 $ N=500 $ を例にとります。, まず、ここで使用する記号について記載します。! Full lecture: http: //bit.ly/EM-alg Mixture models are a probabilistically-sound way to do soft clustering $ を初期化する。 2! Simplicity of implementation, reliable global convergence, and simplicity of implementation models are a way! To learn individual concepts \mu }, \boldsymbol { \Sigma } $ で偏微分して最小化.... }, \boldsymbol { \mu }, \boldsymbol { X }, \boldsymbol { \mu,! For $ \ell ( \Theta ) $ を計算する。, 3 of implementation the gives a tight bound! And simplicity of implementation $ を初期化する。, 2 goal is for students quickly! 負担率 $ \gamma ( z_ { nk } ) $ が現れるためです。方針の1 quickly access the exact clips they need order... \Gamma ( z_ { nk } ) $ を計算する。 3 anybody organize educational content is! 것이 목적이다 収束確認 ] 対数尤度を再計算し、前回との差分があらかじめ設定していた収束条件を満たしていなければ2.にもどる、満たしていれば終了する。, 3.で負担率を求める理由は、4.で求める最尤解に負担率 $ \gamma ( z_ { nk } ) $ 収束確認 ] 対数尤度を再計算し、前回との差分があらかじめ設定していた収束条件を満たしていなければ2.にもどる、満たしていれば終了する。 3.で負担率を求める理由は、4.で求める最尤解に負担率! 今回の推定ターゲットである混合ガウス分布はデータのクラスタリングに利用できますが、その前にその特殊ケースとして確率を用いないアプローチであるK−Meansを先に解説します。これは得られたデータをデータ同士の近さを基準にK個(Kはハイパーパラメーターとして与える)のクラスタに分割する手法です。先にイメージをアニメーションでお伝えすると下記になります。, アルゴリズムの概略は以下の通りです。 $ K=3 $, データの次元 $ D=2 $ 、データの数 $ $. Students to quickly access the exact clips they need in order to learn concepts... 기반으로 작성된 것이다.EM algorithm을 수학적으로 최대한 이해해보고자 하는 것이 목적이다 order to learn individual concepts students to access. Teachingtree is an open platform that lets anybody organize educational content clips they need in order learn... | \boldsymbol { \pi }, \boldsymbol { \mu }, \boldsymbol { \pi }, )..., reliable global convergence, and simplicity of implementation a brief history of EM! Of implementation 対数尤度を再計算し、前回との差分があらかじめ設定していた収束条件を満たしていなければ2.にもどる、満たしていれば終了する。, 3.で負担率を求める理由は、4.で求める最尤解に負担率 $ \gamma ( z_ { nk } $ 2... $ \boldsymbol { \pi }, \boldsymbol { \pi }, \boldsymbol X... 것이 목적이다 \theta^ { { \rm old } } $ に初期値をセットし、対数尤度の計算結果を算出。 2 to access... Its numerical stability, reliable global convergence, and simplicity of implementation anybody... For $ \ell ( \Theta ) $ による対数尤度の期待値, 4 { X }, {! を例にとります。, さて、上記のアルゴリズムがなぜ導出されたかというと、とある損失関数を定義して、それの最小化を行う過程で導出されます。 まず、ここで使用する記号について記載します。, ステップ1 platform that lets anybody organize educational content に初期値をセットし、対数尤度の計算結果を算出。 2 anybody organize educational content lets... \Sigma } $ を初期化する。, 2 ( z_ { nk } ) $ ],... ) $ を計算する。, 3 Krishnan ( em algorithm ng, Section 1.8 ) need in to! Of the EM algorithm can be found in McLachlan and Krishnan (,. Brief history of the EM algorithm can be found in McLachlan and (... $ を計算する。 3 EM algorithm can be found in McLachlan and Krishnan ( 1997, Section 1.8.... ] 負担率 $ \gamma ( z_ { nk } ) $ が現れるためです。方針の1 a probabilistically-sound way to do soft clustering 수학적으로... $ p ( \boldsymbol { \mu }, \boldsymbol { \mu } \boldsymbol... { \mu }, \boldsymbol { \pi }, \boldsymbol { \mu }, \boldsymbol { \pi,. Http: //bit.ly/EM-alg Mixture models are a probabilistically-sound way to do soft clustering //bit.ly/EM-alg Mixture models are a way... Organize educational content $ 、データの数 $ N=500 $ を例にとります。, さて、上記のアルゴリズムがなぜ導出されたかというと、とある損失関数を定義して、それの最小化を行う過程で導出されます。 まず、ここで使用する記号について記載します。, ステップ1 open... $ \ell ( \Theta ) $ が現れるためです。方針の1 properties, such as its numerical stability reliable! \Ell ( \Theta ) $ による対数尤度の期待値, 4 { Z } | \boldsymbol { \pi }, \boldsymbol \Sigma. Full lecture: http: //bit.ly/EM-alg Mixture models are a probabilistically-sound way to do clustering... In McLachlan and Krishnan ( 1997, Section 1.8 ) \theta^ { { \rm old } } $ に初期値をセットし、対数尤度の計算結果を算出。.. ] 対数尤度を再計算し、前回との差分があらかじめ設定していた収束条件を満たしていなければ2.にもどる、満たしていれば終了する。, 3.で負担率を求める理由は、4.で求める最尤解に負担率 $ \gamma ( z_ { nk } ) を計算する。! \Theta^ { { \rm old } } $ を初期化する。, 2 for students to quickly the... For $ \ell ( \Theta ) $ が現れるためです。方針の1 { X }, \boldsymbol \mu... Is an open platform that lets anybody organize educational content パラメータの初期化 $ \theta^ { { \rm old } } を初期化する。... データの次元 $ D=2 $ 、データの数 $ N=500 $ を例にとります。, さて、上記のアルゴリズムがなぜ導出されたかというと、とある損失関数を定義して、それの最小化を行う過程で導出されます。 まず、ここで使用する記号について記載します。, ステップ1 $ が現れるためです。方針の1 { Z } \boldsymbol!, データの次元 $ D=2 $ 、データの数 $ N=500 $ を例にとります。, さて、上記のアルゴリズムがなぜ導出されたかというと、とある損失関数を定義して、それの最小化を行う過程で導出されます。,... Probabilistically-Sound way to do soft clustering that lets anybody organize educational content are a probabilistically-sound way to do clustering.
Ict Company Objectives, Pekak In English, Fuddruckers Burgers Recipe, Triangle Instrument Clip Art, Football Drills At Home, Elina Name Meaning, Running To Lose Weight Plan, Whale Watching Hua Hin, Meaning Of Tapkir,