EM-Algorithmus manuell implementiert

Ich möchte den EM-Algorithmus manuell implementieren und ihn dann mit den Ergebnissen des normalmixEMof- mixtoolsPakets vergleichen. Natürlich würde ich mich freuen, wenn beide zu den gleichen Ergebnissen führen würden. Die Hauptreferenz ist Geoffrey McLachlan (2000), Finite Mixture Models .

Ich habe eine Mischungsdichte von zwei Gaußschen, in allgemeiner Form ist die log-Wahrscheinlichkeit gegeben durch (McLachlan Seite 48):

\log L_{c} (Ψ) = \sum_{i = 1}^{g} \sum_{j = 1}^{n} z_{i j} {\log π_{i} + \log f_{i} (y_{i}; θ_{i})} .

$\log L_c(\Psi) = \sum_{i=1}^g \sum_{j=1}^n z_{ij}\{\log \pi_i + \log f_i(y_i;\theta_i)\}.$ Die

z_{i j}

$z_{ij}$ sind

1

$1$ , wenn die Beobachtung aus der

i

$i$ ^tenKomponentendichtestammte, sonst

0

$0$ . Das

f_{i}

$f_i$ ist die Dichte der Normalverteilung. Das

π

$\pi$ ist das Mischungsverhältnis, also ist

π_{1}

$\pi_1$ die Wahrscheinlichkeit, dass eine Beobachtung aus der ersten Gaußschen Verteilung stammt, und

π_{2}

$\pi_2$ ist die Wahrscheinlichkeit, dass eine Beobachtung aus der zweiten Gaußschen Verteilung stammt.

Der E- Schritt ist nun die Berechnung der bedingten Erwartung:

Q (Ψ; Ψ^{(0)}) = E_{Ψ (0)} {\log L_{c} (| Ψ) | y} .

$Q(\Psi;\Psi^{(0)}) = E_{\Psi(0)}\{\log L_c(|\Psi)|y\}.$ was nach ein paar Ableitungen zum Ergebnis führt (Seite 49):

\begin{aligned} τ_{i} (y_{j}; Ψ^{(k)}) & = \frac{π_{i}^{(k)} f_{i} (y_{j}; θ_{i}^{(k)}}{f (y_{j}; Ψ^{(k)}} \\ = \frac{π_{i}^{(k)} f_{i} (y_{j}; θ_{i}^{(k)}}{\sum_{h = 1}^{g} π_{h}^{(k)} f_{h} (y_{j}; θ_{h}^{(k)})} \end{aligned}

$\begin{align} \tau_i(y_j;\Psi^{(k)}) &= \frac{\pi_i^{(k)}f_i(y_j;\theta_i^{(k)}}{f(y_j;\Psi^{(k)}} \\[8pt] &= \frac{\pi_i^{(k)}f_i(y_j;\theta_i^{(k)}}{\sum_{h=1}^g \pi_h^{(k)}f_h(y_j;\theta_h^{(k)})} \end{align}$ im Fall von zwei Gaußschen (Seite 82):

τ_{i} (y_{j}; Ψ) = \frac{π_{i} ϕ (y_{j}; μ_{i}, Σ_{i})}{\sum_{h = 1}^{g} π_{h} ϕ (y_{j}; μ_{h}, Σ_{h})}

$\tau_i(y_j;\Psi) = \frac{\pi_i \phi(y_j;\mu_i,\Sigma_i)}{\sum_{h=1}^g \pi_h\phi(y_j; \mu_h,\Sigma_h)}$ DerM-Schritt ist jetzt die Maximierung von Q (Seite 49):

Q (Ψ; Ψ^{(k)}) = \sum_{i = 1}^{g} \sum_{j = 1}^{n} τ_{i} (y_{j}; Ψ^{(k)}) {\log π_{i} + \log f_{i} (y_{j}; θ_{i})} .

$Q(\Psi;\Psi^{(k)}) = \sum_{i=1}^g\sum_{j=1}^n\tau_i(y_j;\Psi^{(k)})\{\log \pi_i + \log f_i(y_j;\theta_i)\}.$ Dies führt zu (im Fall von zwei Gaußschen) (Seite 82):

\begin{aligned} μ_{ich}^{(k + 1)} & = \frac{\sum_{j = 1}^{n} τ_{ich j}^{(k)} y_{j}}{\sum_{j = 1}^{n} τ_{ich j}^{(k)}} \\ Σ_{ich}^{(k + 1)} & = \frac{\sum_{j = 1}^{n} τ_{ich j}^{(k)} (y_{j} - μ_{ich}^{(k + 1)}) (y_{j} - μ_{ich}^{(k + 1)})^{T}}{\sum_{j = 1}^{n} τ_{ich j}^{(k)}} \end{aligned}

$\begin{align} \mu_i^{(k+1)} &= \frac{\sum_{j=1}^n \tau_{ij}^{(k)}y_j}{\sum_{j=1}^n \tau_{ij}^{(k)}} \\[8pt] \Sigma_i^{(k+1)} &= \frac{\sum_{j=1}^n \tau_{ij}^{(k)}(y_j - \mu_i^{(k+1)})(y_j - \mu_i^{(k+1)})^T}{\sum_{j=1}^n \tau_{ij}^{(k)}} \end{align}$ and we know that (p. 50)

π_{ich}^{(k + 1)} = \frac{\sum_{j = 1}^{n} τ_{ich} (y_{j}; Ψ^{(k)})}{n} (ich = 1, \dots, G) .

$\pi_i^{(k+1)} = \frac{\sum_{j=1}^n \tau_i(y_j;\Psi^{(k)})}{n}\qquad (i = 1, \ldots, g).$ We repeat the E, M steps until

L (Ψ^{(k + 1)}) - L (Ψ^{(k)})

$L(\Psi^{(k+1)})-L(\Psi^{(k)})$ is small.

I tried to write a R code (data can be found here).

# EM algorithm manually
# dat is the data

# initial values
pi1       <-  0.5
pi2       <-  0.5
mu1       <- -0.01
mu2       <-  0.01
sigma1    <-  0.01
sigma2    <-  0.02
loglik[1] <-  0
loglik[2] <- sum(pi1*(log(pi1) + log(dnorm(dat,mu1,sigma1)))) + 
             sum(pi2*(log(pi2) + log(dnorm(dat,mu2,sigma2))))

tau1 <- 0
tau2 <- 0
k    <- 1

# loop
while(abs(loglik[k+1]-loglik[k]) >= 0.00001) {

  # E step
  tau1 <- pi1*dnorm(dat,mean=mu1,sd=sigma1)/(pi1*dnorm(x,mean=mu1,sd=sigma1) + 
          pi2*dnorm(dat,mean=mu2,sd=sigma2))
  tau2 <- pi2*dnorm(dat,mean=mu2,sd=sigma2)/(pi1*dnorm(x,mean=mu1,sd=sigma1) + 
          pi2*dnorm(dat,mean=mu2,sd=sigma2))

  # M step
  pi1 <- sum(tau1)/length(dat)
  pi2 <- sum(tau2)/length(dat)

  mu1 <- sum(tau1*x)/sum(tau1)
  mu2 <- sum(tau2*x)/sum(tau2)

  sigma1 <- sum(tau1*(x-mu1)^2)/sum(tau1)
  sigma2 <- sum(tau2*(x-mu2)^2)/sum(tau2)

  loglik[k] <- sum(tau1*(log(pi1) + log(dnorm(x,mu1,sigma1)))) + 
               sum(tau2*(log(pi2) + log(dnorm(x,mu2,sigma2))))
  k         <- k+1
}


# compare
library(mixtools)
gm <- normalmixEM(x, k=2, lambda=c(0.5,0.5), mu=c(-0.01,0.01), sigma=c(0.01,0.02))
gm$lambda
gm$mu
gm$sigma

gm$loglik

The algorithm is not working, since some observations have the likelihood of zero and the log of this is -Inf. Where is my mistake?

r expectation-maximization gaussian-mixture Stat Tistician
quelle

The problem is not a statistical one, but rather a numerical one. You should add contingencies for likelihoods smaller than machine precision in your code.

JohnRos

why dont you try veryfying the mixtools function with a very simple example that can be verified by hand , say just five or ten values and two timeseries,first. then, if you find it works there, generalize your code and verify at each step.

Antworten:

You have several problems in the source code:

As @Pat pointed out, you should not use log(dnorm()) as this value can easily go to infinity. You should use logmvdnorm
When you use sum, be aware to remove infinite or missing values
You looping variable k is wrong, you should update loglik[k+1] but you update loglik[k]
The initial values for your method and mixtools are different. You are using $\Sigma$ in your method, but using $\sigma$ for mixtools(i.e. standard deviation, from mixtools manual).
Your data do not look like a mixture of normal (check histogram I plotted at the end). And one component of the mixture has very small s.d., so I arbitrarily added a line to set $\tau_1$ and $\tau_2$ to be equal for some extreme samples. I add them just to make sure the code can work.

Ich schlage auch vor, dass Sie vollständige Codes (z. B. wie Sie loglik [] initialisieren) in Ihren Quellcode einfügen und den Code einrücken, um das Lesen zu vereinfachen.

Immerhin vielen Dank, dass Sie das mixtools- Paket eingeführt haben und ich plane, es für meine zukünftige Forschung zu verwenden.

Ich habe auch meinen Arbeitscode als Referenz angegeben:

# EM algorithm manually
# dat is the data
setwd("~/Downloads/")
load("datem.Rdata")
x <- dat

# initial values
pi1<-0.5
pi2<-0.5
mu1<--0.01
mu2<-0.01
sigma1<-sqrt(0.01)
sigma2<-sqrt(0.02)
loglik<- rep(NA, 1000)
loglik[1]<-0
loglik[2]<-mysum(pi1*(log(pi1)+log(dnorm(dat,mu1,sigma1))))+mysum(pi2*(log(pi2)+log(dnorm(dat,mu2,sigma2))))

mysum <- function(x) {
  sum(x[is.finite(x)])
}
logdnorm <- function(x, mu, sigma) {
  mysum(sapply(x, function(x) {logdmvnorm(x, mu, sigma)}))  
}
tau1<-0
tau2<-0
#k<-1
k<-2

# loop
while(abs(loglik[k]-loglik[k-1]) >= 0.00001) {
  # E step
  tau1<-pi1*dnorm(dat,mean=mu1,sd=sigma1)/(pi1*dnorm(x,mean=mu1,sd=sigma1)+pi2*dnorm(dat,mean=mu2,sd=sigma2))
  tau2<-pi2*dnorm(dat,mean=mu2,sd=sigma2)/(pi1*dnorm(x,mean=mu1,sd=sigma1)+pi2*dnorm(dat,mean=mu2,sd=sigma2))
  tau1[is.na(tau1)] <- 0.5
  tau2[is.na(tau2)] <- 0.5

  # M step
  pi1<-mysum(tau1)/length(dat)
  pi2<-mysum(tau2)/length(dat)

  mu1<-mysum(tau1*x)/mysum(tau1)
  mu2<-mysum(tau2*x)/mysum(tau2)

  sigma1<-mysum(tau1*(x-mu1)^2)/mysum(tau1)
  sigma2<-mysum(tau2*(x-mu2)^2)/mysum(tau2)

  #  loglik[k]<-sum(tau1*(log(pi1)+log(dnorm(x,mu1,sigma1))))+sum(tau2*(log(pi2)+log(dnorm(x,mu2,sigma2))))
  loglik[k+1]<-mysum(tau1*(log(pi1)+logdnorm(x,mu1,sigma1)))+mysum(tau2*(log(pi2)+logdnorm(x,mu2,sigma2)))
  k<-k+1
}

# compare
library(mixtools)
gm<-normalmixEM(x,k=2,lambda=c(0.5,0.5),mu=c(-0.01,0.01),sigma=c(0.01,0.02))
gm$lambda
	gm$mu
gm$sigma

gm$loglik

Historgramm Histogram

zhanxw
quelle

@zahnxw danke für deine antwort, heißt das also, dass mein code falsch ist? Die Grundidee funktioniert also nicht?

Statistiker

"Ich schlage auch vor, dass Sie vollständige Codes (z. B. wie Sie loglik [] initialisieren) in Ihren Quellcode einfügen und den Code einrücken, um das Lesen zu vereinfachen." Na das ist mein Code? Das Loglik [] ist so definiert, wie ich es in dem von mir geposteten Code deklariert habe.

Statistiker

@StatTistician die Idee ist richtig, aber die Umsetzung hat Mängel. Beispielsweise haben Sie einen Unterlauf nicht berücksichtigt. Außerdem ist die Schleifenvariable k verwirrend. Sie setzen zuerst loglik [1] und loglik [2], nachdem Sie die while-Schleife eingegeben haben, setzen Sie loglik [1] erneut. Dies ist nicht der natürliche Weg. Mein Vorschlag zum Initialisieren von loglik [] bedeutet code loklik <- rep(NA, 100):, der loglik [1], loglik [2] ... loglik [100] vorbelegt. Ich stelle diese Frage, weil ich in Ihrem ursprünglichen Code die Delkaration von loglik nicht gefunden habe. Vielleicht wird der Code beim Einfügen abgeschnitten.

Zhanxw

Wie ich unten gepostet habe: Danke für Ihre Hilfe, aber ich lösche dieses Thema, da es für mich zu fortgeschritten ist.

Statistiker

Gibt es jetzt eine Möglichkeit zu bestimmen, welcher Teil der Daten zu welcher Mischung gehört?

Kardinal

Beim Versuch, Ihre .rar-Datei zu öffnen, wird immer wieder eine Fehlermeldung angezeigt, aber möglicherweise tue ich nur etwas Dummes.

Ich kann keine offensichtlichen Fehler in Ihrem Code sehen. Ein möglicher Grund, warum Sie Nullen erhalten, liegt in der Gleitkommapräzision. Denken Sie daran, wenn Sie rechnen $f(y;\theta)$ , Sie bewerten $\exp(-0.5(y-\mu)^2/\sigma^2)$ . Es macht keinen großen Unterschied zwischen $\mu$ und $y$ Wenn Sie dies auf einem Computer tun, wird dies auf 0 abgerundet. Dies macht sich in Mischungsmodellen doppelt bemerkbar, da einige Ihrer Daten nicht jeder Mischungskomponente "zugeordnet" werden und daher sehr weit davon entfernt sein können. Theoretisch sollten diese Punkte auch einen niedrigen Wert von haben $\tau$ Wenn Sie die Log-Wahrscheinlichkeit auswerten, um dem Problem entgegenzuwirken, wurde die Menge dank des Gleitkomma-Fehlers zu diesem Zeitpunkt bereits als -Inf ausgewertet, sodass alles kaputt geht :).

Wenn dies das Problem ist, gibt es einige mögliche Lösungen:

Eine ist, deine zu bewegen $\tau$ innerhalb des Logarithmus. Also anstatt zu bewerten

$\tau \log(f(y|\theta))$

bewerten

$\log \left( f(y|\theta)^\tau \right)$ .

Mathematisch dasselbe, aber denken Sie darüber nach, was wann passiert $f(y|\theta)$ und $\tau$ sind $\approx 0$ . Derzeit erhalten Sie:

$0 \log (0) = 0 (-Inf) = NaN$

but with tau moved you get

$\log \left( 0^0\right) = \log(1) = 0$

assuming R evaluates $0^0 = 1$ (I don't know if it does or not as I tend to use matlab)

Another solution is to expand out the stuff inside the logarithm. Assuming you're using natural logarithms:

$\tau \log(f(y|\theta))$

$= \tau \log(\exp(-0.5(y-\mu)^2/\sigma^2)/\sqrt{2\pi\sigma^2})$

$= -0.5\tau \log(2 \pi\sigma^2) - 0.5 \tau \frac{(y-\mu)^2}{\sigma^2}$ .

Mathematisch dasselbe, sollte aber gegenüber Gleitkommafehlern widerstandsfähiger sein, da Sie die Berechnung einer großen negativen Potenz vermieden haben. Dies bedeutet, dass Sie die eingebaute Normauswertungsfunktion nicht mehr verwenden können. Wenn dies jedoch kein Problem darstellt, ist dies wahrscheinlich die bessere Antwort. Nehmen wir zum Beispiel an, wir haben die Situation, in der

$-0.5\frac{(y-\mu)^2}{\sigma^2} = -0.5*40^2 = -800$ .

Bewerten Sie das, wie ich es vorgeschlagen habe, und Sie erhalten -800. In Matlab erhalten wir jedoch, wenn wir das Protokoll herausnehmen $\log(\exp(-800)) = \log(0) = -Inf$ .

Klopfen
quelle

mh, um ehrlich zu sein: Ich bin nicht gut genug, um dieses Ding zum Laufen zu bringen. Was mich interessiert hat, ist: Kann ich mit meinem Algorithmus das gleiche Ergebnis erzielen wie mit der implementierten Version des mixtools-Pakets? Aber aus meiner Sicht scheint dies nach dem Mond zu fragen. Aber ich denke, Sie geben sich Mühe, und ich werde es akzeptieren! Vielen Dank!

Statistiker