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 ...
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 ...
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?
26
votes
1answer
7k views

Relation between variational Bayes and EM

I read somewhere that Variational Bayes method is a generalization of the EM algorithm. Indeed, the iterative parts of the algorithms are very similar. In order to test whether the EM algorithm is a ...
25
votes
2answers
6k views

Why is the Expectation Maximization algorithm guaranteed to converge to a local optimum?

I have read a couple of explanations of EM algorithm (e.g. from Bishop's Pattern Recognition and Machine Learning and from Roger and Gerolami First Course on Machine Learning). The derivation of EM is ...
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^{...
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 ...
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 ...
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 ...
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 ...
16
votes
1answer
620 views

E-M, is there an intuitive explanation?

The E-M procedure appears, to the uninitiated, as more or less black magic. Estimate parameters of an HMM (for example) using supervised data. Then decode untagged data, using forward-backward to '...
16
votes
1answer
990 views

Training a basic Markov Random Field for classifying pixels in an image

I am attempting to learn how to use Markov Random Fields to segment regions in an image. I do not understand some of the parameters in the MRF or why the expectation maximisation I perform fails to ...
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 ...
14
votes
2answers
4k views

Why isn't k-means optimized using gradient descent?

I know k-means is usually optimized using Expectation Maximization. However we could optimize its loss function the same way we optimize any other! I found some papers that actually use stochastic ...
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 ...
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 ...
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.
12
votes
2answers
377 views

Does MLE always mean we know the underlying PDF of our data, and does EM mean we don't?

I have some simple conceptual questions that I would like clarified regarding MLE (Maximum Likelihood Estimation), and what link it has, if any, to EM (Expectation Maximization). As I understand it, ...
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 ...
11
votes
2answers
450 views

Significance of initial transition probabilites in a hidden markov model

What are the benefits of giving certain initial values to transition probabilities in a Hidden Markov Model? Eventually system will learn them, so what is the point of giving values other than random ...
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 ...
10
votes
3answers
7k views

Hidden Markov models and expectation maximization algorithm

Can somebody clarify how hidden Markov models are related to expectation maximization? I have gone through many links but couldn't come up with a clear view. Thanks!
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 ...
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-...
9
votes
1answer
4k views

MCMC/EM limitations? MCMC over EM?

I am currently learning hierarchical Bayesian models using JAGS from R, and also pymc using Python ("Bayesian Methods for Hackers"). I can get some intuition from this post: "you will end up with a ...
9
votes
2answers
1k views

EM algorithm Practice Problem

This is a practice problem for a midterm exam. The problem is an EM algorithm example. I am having trouble with part (f). I list parts (a)-(e) for completion and in case I made a mistake earlier. Let ...
9
votes
1answer
7k views

Convergence from the EM Algorithm with bivariate mixture distribution

I have a mixture model which I want to find the maximum likelihood estimator of given a set of data $x$ and a set of partially observed data $z$. I have implemented both the E-step (calculating the ...
9
votes
1answer
492 views

Why does the EM algorithm have to be iterative?

Suppose that you have a population with $N$ units, each with a random variable $X_i \sim \text{Poisson}(\lambda)$. You observe $n = N-n_0$ values for any unit for which $X_i > 0$. We want an ...
9
votes
2answers
662 views

Help in Expectation Maximization from paper :how to include prior distribution?

The Question is based on the paper titled : Image reconstruction in diffuse optical tomography using the coupled radiative transport–diffusion model Download link The Authors apply EM algorithm with ...
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 ...
9
votes
3answers
816 views

Difference between MLE and Baum Welch on HMM fitting

In this popular question, high upvoted answer makes MLE and Baum Welch separate in HMM fitting. For training problem we can use the following 3 algorithms: MLE (maximum likelihood estimation), ...
9
votes
1answer
694 views

Does EM algorithm consistently estimate the parameters in Gaussian Mixture model?

I am studying the Gaussian Mixture model and come up with this question myself. Suppose the underlying data is generated from a mixture of $K$ Gaussian distribution and each of them has a mean vector ...
9
votes
1answer
367 views

Determine an unknown number of real world locations from GPS-based reports

I'm working on some software which should determine real world locations (f.e. speed cams) from several GPS-based reports. An user will be driving when reporting a location, thus the reports a very ...
8
votes
2answers
612 views

Why is there a E in the name EM algorithm?

I understand where the E step happens in the algorithm (as explicated in the math section below). In my mind, the key ingenuity of the algorithm is the use of the Jensen's inequality to create a lower ...
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: $$ \...
8
votes
1answer
667 views

MCMC in a frequentist setting

I have been trying to get a sense of the different problems in frequentist settings where MCMC is used. I am familiar that MCMC (or Monte Carlo) is used in fitting GLMMs and in maybe Monte Carlo EM ...
8
votes
1answer
1k views

Question on how to use EM to estimate parameters of this model

I am trying to understand EM and trying to infer parameters of this model using this technique but am having trouble understanding how to begin: So, I have a weighted linear regression model as ...
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}$. ...
8
votes
1answer
1k views

Relative advantages of multiple imputation and expectation maximization (EM)

I've got a problem where $$y = a + b $$ I observe y, but neither $a$ nor $b$. I want to estimate $$b = f(x) + \epsilon$$ I can estimate $a$, using some sort of regression model. This gives me $\...
7
votes
2answers
2k views

Self-study: Finding the maximum likelihood estimates of the parameters of a density function - UPDATED

UPDATED I am trying to find maximum likelihood estimation of a probability distribution function given below \begin{equation} g(x)=\frac{1}{\Gamma \left( \alpha \right)\gamma^{2\alpha}2^{\alpha-1}}x^...
7
votes
2answers
974 views

Combination of variational methods and empirical Bayes

Suppose I have a posterior $p(z, \theta | y, \eta)$ with $y$ observed data, $z$ are hidden variables and $\theta$ are parameters, and $\eta$ is a vector of hyperparameters. I construct a mean field ...
7
votes
3answers
2k views

Variance of EM mean estimates in a simple mixture of two normals

Consider a mixture of two normal distributions: $ f(x) = p N(x|u_1, S_1) + (1-p) N(x|u_2, S_2) $ where N() is the normal pdf. $p$, $S_2$, and $S_2$ are known. The means are not. You can get the MLE ...
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 (...
6
votes
2answers
4k views

Maximum likelihood estimation in a Poisson model for football (soccer) scores

I've got a set of football results and I want to make a probabilty model of football scores as described in Dixon, Coles (1997, http://www.math.ku.dk/~rolf/teaching/thesis/DixonColes.pdf). They ...
6
votes
2answers
3k views

Expectation maximization on Bayesian networks with latent variables

I am trying to determine parameters in a bayesian network with two latent variables (in blue). Every variable is discrete with 2-4 categories. The latent variables have 3 categories each. I am ...
6
votes
1answer
545 views

Learning parameters of a mixture of Gaussian using MLE

It seems that MLE (via EM) is widely used in machine learning / statistics to learn the parameters of a mixture of Gaussians. I'm assuming we're given random samples from the mixture. My question is:...
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 ...
6
votes
1answer
591 views

Fitting Gaussian mixture models with dirac delta functions

I was told that using gradient methods for Gaussian mixture models may end up with Dirac delta function(s). I hadn't thought of this problem before, but when I verify this, it does seem to be a ...
6
votes
1answer
554 views

Rate of convergence of EM algorithm?

What can be said in general about the rate of convergence of EM algorithm? For example, if I let the parameters to be $\theta$, starting point to be $\theta^0$, and the optimal solution is $\theta^*$...
6
votes
1answer
334 views

How to calculate likelihood for a mixture model with missing data?

Toy explanation: I have set of different cars of different colours. There can be green, blue, red, etc. cars. I have a set of classes i.e.: "The set contains blue, red and pink cars" or "The set ...

1 2 3 4 5 10