Questions tagged [expectation-maximization]

An optimization algorithm often used for maximum-likelihood estimation in the presence of missing data.

Filter by
Sorted by
Tagged with
119
votes
9answers
86k views

Numerical example to understand Expectation-Maximization

I am trying to get a good grasp on the EM algorithm, to be able to implement and use it. I spent a full day reading the theory and a paper where EM is used to track an aircraft using the position ...
20
votes
2answers
32k views

EM algorithm manually implemented

I want to implement the EM algorithm manually and then compare it to the results of the normalmixEM of mixtools package. Of ...
28
votes
2answers
10k views

What is the difference between EM and Gradient Ascent?

What is the difference between the algorithms EM (Expectation Maximization) and Gradient Ascent (or descent)? Is there any condition under which they are equivalent?
10
votes
1answer
3k views

Why should one use EM vs. say, Gradient Descent with MLE?

Mathematically, it's often seen that expressions and algorithms for Expectation Maximization (EM) are often simpler for mixed models, yet it seems that almost everything (if not everything) that can ...
13
votes
4answers
3k views

Separating two populations from the sample

I'm trying to separate two groups of values from a single data set. I can assume that one of the populations is normally distributed and is at least half the size of the sample. The values of the ...
10
votes
1answer
5k views

How do you use the EM algorithm to calculate MLEs for a latent variable formulation of a zero inflated Poisson model?

The zero inflated Poisson regression model is defined for a sample $(y_1,\ldots,y_n)$ by $$ Y_i = \begin{cases} 0 & \text{with probability} \ p_i+(1-p_i)e^{-\lambda_i}\\ k & \text{with ...
13
votes
4answers
2k views

Fast alternatives to the EM algorithm

Are there any speedy alternatives to the EM algorithm for learning models with latent variables (especially pLSA)? I'm okay with sacrificing precision in favor of speed.
51
votes
3answers
48k views

Clustering with K-Means and EM: how are they related?

I have studied algorithms for clustering data (unsupervised learning): EM, and k-means. I keep reading the following : k-means is a variant of EM, with the assumptions that clusters are ...
13
votes
3answers
605 views

Estimate the size of a population being sampled by the number of repeat observations

Say I have a population of 50 million unique things, and I take 10 million samples (with replacement)... The first graph is I've attached shows how many times I sample the same "thing", which is ...
21
votes
5answers
2k views

Motivation of Expectation Maximization algorithm

In the EM algorithm approach we use Jensen's inequality to arrive at $$\log p(x|\theta) \geq \int \log p(z,x|\theta) p(z|x,\theta^{(k)}) dz - \int \log p(z|x,\theta) p(z|x,\theta^{(k)})dz$$ and ...
24
votes
4answers
17k views

EM maximum likelihood estimation for Weibull distribution

Note: I am posting a question from a former student of mine unable to post on his own for technical reasons. Given an iid sample $x_1,\ldots,x_n$ from a Weibull distribution with pdf $$ f_k(x) = k x^{...
18
votes
2answers
4k views

Why is optimizing a mixture of Gaussian directly computationally hard?

Consider the log likelihood of a mixture of Gaussians: $$l(S_n; \theta) = \sum^n_{t=1}\log f(x^{(t)}|\theta) = \sum^n_{t=1}\log\left\{\sum^k_{i=1}p_i f(x^{(t)}|\mu^{(i)}, \sigma^2_i)\right\}$$ I was ...
8
votes
1answer
3k views

K-means as a limit case of EM algorithm for Gaussian mixtures with covariances $\epsilon^2 I$ going to $0$

My goal is to see that K-means algorithm is in fact Expectation-Maximization algorithm for Gaussian mixtures in which all components have covariance $\sigma^2 I$ in the limit as $\lim_{\sigma \to 0}$. ...
3
votes
1answer
421 views

EM with Binomial

$X_1, X_2 \dots X_n$ represent independently observed Bernoulli random variables. $Z_1, Z_2, \dots Z_n$ are unobserved. $Z_i | \theta_i \sim N(\theta_i,1)$ $\theta_i \sim N(\epsilon, \sigma^2)$ $...
6
votes
2answers
2k views

Hidden Markov Models with multiple emissions per state

I want to use Hidden Markov Models for an unsupervised sequence tagging problem. Due to the peculiarities of my application domain (recognition of dialogue acts in conversations), I would like to use ...
3
votes
1answer
939 views

Derivation of E step in EM algorithm

While im going through the derivation of E step in EM algorithm for pLSA, i came across the following derivation at this page. Could anyone explain me how the following step is derived. $\sum_z q(z) ...
2
votes
1answer
435 views

Why is the expectation step in the EM algorithm called this way?

In the E-step of the EM algorithm we maximize $$\max_\theta \sum_Z p(Z\mid X,\theta_\text{old})\log p(X,Z\mid\theta).$$ This expression is called the expectation of the complete data log-likelihood $\...
4
votes
1answer
484 views

Why Baum-Welch algorithm is an instantiation of EM algorithm?

$\newcommand{\E}{\mathrm{E}}$ I don't understand why Baum-Welch algorithm is an instantiation of EM algorithm. Indeed, why computing $\alpha_t(i)$ and $\beta_t(i)$ corresponds to Expectation step. ...
4
votes
2answers
4k views

How to initialize EM-algorithm when trying to fit data to a separable mixture model?

As a part of my studies, I’m trying to cluster co-occurrences of URLs and tags in data from Delicious. I found a promising method for this in a paper called “Emergent Semantics from Folksonomies: A ...
10
votes
1answer
4k views

How to make a matrix positive definite?

I'm trying to implement an EM algorithm for the following factor analysis model; $$W_j = \mu+B a_j+e_j \quad\text{for}\quad j=1,\ldots,n$$ where $W_j$ is p-dimensional random vector, $a_j$ is a q-...
1
vote
1answer
514 views

EM Algorithm seems to work, but Q is not monotonic. Possible reasons?

I have implemented Expectation maximization to fit some of the parameters of a linear Gaussian state space model using Kalman filtering / smoothing. The model is: $x(t) = Ax(t - 1) + w(t); w(t) \sim ...
22
votes
3answers
8k views

Why is the expectation maximization algorithm used?

From what little I know the EM algorithm can be used to find the maximum likelihood when setting to zero the partial derivatives with respect to the parameters of the likelihood gives a set of ...
15
votes
2answers
2k views

Why Expectation Maximization is important for mixture models?

There are many literature emphasize Expectation Maximization method on mixture models (Mixture of Gaussian, Hidden Markov Model, etc.). Why EM is important? EM is just a way to do optimization and is ...
8
votes
1answer
2k views

Deriving K-means algorithm as a limit of Expectation Maximization for Gaussian Mixtures

Christopher Bishop defines the expected value of the complete-data log likelihood function (i.e. assuming that we are given both the observable data X as well as the latent data Z) as follows: $$ \...
6
votes
1answer
3k views

Relation between MAP, EM, and MLE

I am a beginner in machine learning. I can do programming fine but the theory confuses me a lot of the times. What is the relation between Maximum Likelihood Estimation (MLE), Maximum A posteriori (...
9
votes
2answers
2k views

Using EM algorithm for record linking

I am interested in linking records across 2 datasets by first name, last name, and birth year. Might this be doable with the EM algorithm, and if so, how? Consider the following record in the 1st as ...
4
votes
2answers
272 views

Expectation maxmisation algorithm increases true likelihood at each iteration

I've heard that the EM algorithm ensures that the true likelihood is non-decreasing at each iteration of the algorithm, but I'm not sure why this is the case. I've provided a basic plot which I ...
4
votes
2answers
660 views

Question about the latent variable in EM algorithm

In mixture models, Expectation maximization algorithm (EM) is a commonly used method to estimate the model parameters. Suppose that I have bivariate mixture model with two mixture components, with ...
3
votes
0answers
264 views

Question about E step in Em algorithm, a challenge part, any help please?

I am new to EM algorithm and copula. I was reading a paper in mixture pair-copula. The authors use $u=(u_r, u_s) = (u_r^t,u_s^t), (t= 1,...,T)$ to indictae to the vector of copula data. Then, they ...
2
votes
1answer
2k views

Convergence of EM for Mixture of Gaussians

Is the Mixture of Gaussians model (an example of latent class analysis) gauranteed to converge on a viable solution even on Unimodal data using the Expectation Maximization algorithm to estimate the ...
2
votes
0answers
352 views

Baum-Welch algorithm variation for Hidden Markov model with reward

Following my previous question on the subject I would like to get your feedback on the following alternative solution. (The original solution to this question is the usage of the POMDP model proposed ...
1
vote
1answer
3k views

EM algorithm for a binomial distribution [duplicate]

I have been reading the following link about an example of the EM algorithm applied to the tossing of a coin. The link is: http://ai.stanford.edu/~chuongdo/papers/em_tutorial.pdf In the example ...
3
votes
2answers
157 views

EM and (Gaussian) Mixture Models

I have some trouble understanding the definition of the EM-algorithm. On Wikipedia they write the following mathematical expression: $$ E_{Z|X,\Theta^{(t)}}[\log L(\Theta^{(t)}; X, Z)|X=x] $$ Now, ...
3
votes
1answer
2k views

t-distribution parameter estimation

I know there are already several threads on this, but none seem to explicitly cover what I want. I have a set of financial data (pulled straight from Bloomberg) and am trying to fit a t-distribution (...
2
votes
2answers
1k views

Finding most informative feature subsets given dataset, clustering algorithm and gold standard partition

I have an $n \times m$ matrix of data $\mathbf{D}$ as well as a $k$-partition $P$ of $n$ indices each representing a row in $\mathbf{D}$. Assuming an arbitrary clustering algorithm $A$, I would like ...
2
votes
1answer
422 views

Derivation of expectation-maximization in General - PRML

My question is: Why the incomplete-data likelihood equal to formula 1? Why it should not equal to formula 2? I apologize for not being word-perfect in English. I'm reading the book ...
11
votes
2answers
599 views

Finding number of gaussians in a finite mixture with Wilks' theorem?

Assume I have a set of independent, identically distributed univariate observations $x$ and two hypotheses about how $x$ was generated: $H_0$: $x$ is drawn from a single Gaussian distribution with ...
6
votes
1answer
623 views

Issues with using Expectation Maximization algorithm

I was using the EM algorithm to maximize a partially observed likelihood. However, I have certain doubts. Normally, the algorithm works fine. I could print the value of the log likelihood of the ...
5
votes
1answer
228 views

Help with Variational Bayes on a weighted linear regression model

I am trying to setup VB to do a weighted linear regression for vector observations. My setup is that I have $N$ numbers of $d$-dimensional vector observations. I would like to model the noise as being ...
4
votes
0answers
1k views

Expectation-Maximization with a MLE package in R

As a follow up to one answer of the topic Expectation-Maximization with a coin toss: One of the user posted an R-code with MLE example almost a year ago (and his last online time here was 3 months ago,...
3
votes
1answer
5k views

Advantages and disadvantages of EM algorithm vs trust region methods for nonlinear optimization

I have a set of observations X that I believe were generated by a mixture of several probability distributions (specifically, two von mises and one uniform). I'd like to find the maximum likelihood ...
2
votes
1answer
798 views

Can log-likelihood function calculated value (M-step) be smaller after 1 EM-iteration?

I am applying a MAP log-likelihood approach in order to fit a Markov mixture model, where objective function to be maximized is given by the formula: $$ L(X|\Theta _K)=\sum_{i=1}^{n}f(X_i|\Theta_K)+\...
1
vote
2answers
2k views

Comparing K-Means and Expectation Maximization on the dataset generated - When does K-Means perform better?

I was experimenting with K-Means and Gaussian Mixture Models (Expectation-Maximization) on the data set that I generated. Here is how the plot for two distributions looks like: Since this was ...
1
vote
1answer
73 views

Estimation of time for a specific value of a variable

I have a data set: ...
1
vote
1answer
850 views

How can I find mean and covariance after EM iteration on GMM algorithmm?

I have a dataset divided in 2 class(lets call x1,x2) but I don't know their mean and covariance. For each class I looked their graph and made a guess about their sub-classes, then run an EM(...
1
vote
2answers
826 views

Variational inference: how to rewrite ELBO?

I am reading this paper on variational inference and this website. One thing I am confused about is how they get to decompose ELBO, where $ELBO(q) = E_q[log~p(z,x)] - E_q[log~q(z)]$, when focusing ...
0
votes
1answer
2k views

r: normalmixEM not consistent?

I have the following data: http://s000.tinyupload.com/?file_id=00083355432555420222 I want to fit a mixture density of two normal distributions. I have the formula: \begin{align} f(l)=\pi \phi(l;\...
0
votes
1answer
416 views

Can the distribution of emission probabilities of an HMM be swapped out for the re-estimated ones only after all training sequences have been covered?

Regarding the re-estimation procedure of the Baum-Welch algorithm, the sources I looked into so far all describe the process in an abstract manner. Therefore I am wondering the following about ...