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 (MAP) estimate, and Expectation-Maximization (EM) algorithm?
I see them used as the methods that actually do the optimization.
Imagine that you have some data $X$ and probabilistic model parametrized by $\theta$, you are interested in learning about $\theta$ given your data. The relation between data, parameter and model is described using likelihood function
$$ \mathcal{L}(\theta \mid X) = p(X \mid \theta) $$
To find the best fitting $\theta$ you have to look for such value that maximizes the conditional probability of $\theta$ given $X$. Here things start to get complicated, because you can have different views on what $\theta$ is. You may consider it as a fixed parameter, or as a random variable. If you consider it as fixed, then to find it's value you need to find such value of $\theta$ that maximizes the likelihood function (maximum likelihood method [ML]). On another hand, if you consider it as a random variable, then this means that it also has some distribution, so you need to make one more assumption about prior distribution of $\theta$, i.e. $p(\theta)$, and you will be using Bayes theorem for estimation
$$ p(\theta \mid X) \propto p(X \mid \theta) \, p(\theta) $$
If you are not interested in estimating the posterior distribution of $\theta$ but only about point estimate that maximizes the posterior probability, then you will be using maximum a posteriori (MAP) method for estimating it.
As about expectation-maximalization (EM), it is an algorithm that can be used in maximum likelihood approach for estimating certain kind of models (e.g. involving latent variables, or in missing data scenarios).
Check the following threads to learn more:
Maximum Likelihood Estimation (MLE) in layman terms
What is the difference between Maximum Likelihood Estimation & Gradient Descent?
Bayesian and frequentist reasoning in plain English
Who Are The Bayesians?
Is there a difference between the "maximum probability" and the "mode" of a parameter?
What is the difference between "likelihood" and "probability"?
Wikipedia entry on likelihood seems ambiguous
Numerical example to understand Expectation-Maximization
I stumbled across this post, when I tried to give a more comprehensive answer of that topic to a friend of mine. Since the answer written by @Tim♦ is already a bit older and this topic just really complex, I will try to give an easy introduction into the EM "algorithm" and its relationship to Maximum A Posteriori (MAP) and Maximum Likelihood Estimation (MLE). To do so, I will split my explanation into four parts. A Preface, where I will give a short insight into the general idea of the expectation maximization "algorithm" and into bayesian thinking. The second Main part will be split into MLE, MAP and EM. In the Conclusion I will point out the relationship between these optimization methods. Throughout the course of that explanation I will use a variety of sources, which helped me put this answer together. You can review my bibliography in the last chapter called Sources. I will always include the link to the source as well as a note, why that is a useful resource to look at. Moreover, I am going to cite throughout my answer (where necessary), so that you can always go and checkout where I got the information from.
As you might have wondered in the text so far I put a quote around "algorithm". The reason is, that Dempster et al. [1] themselves point out, that this term can be critized since it does not point out clear programing steps (p. 6).
In order to better understand the idea of the Expectation Maximization "algorithm", we need some pretext. When we look at statistic more broadly, one can identify (probably under a wide range of ideas) two paradigms, viz. the Frequentist-approach and the Bayesian-approach. Imagine you are going to the store and buy 100 bags of M&Ms. You open a bag and whenever you eat a M&M you note down the color. After finishing all 100 bags of M&Ms you conclude that 30% of your M&Ms were red, 20% were green, 25% were blue and 35% were yellow. From a frequentist's perspective, this is the prior; the knowledge was obtained by the frequent and repeated sample of measuring. Hence you expect a similar color distribution the next time that you buy M&Ms. This connects "probabilites deeply to the frequency of events" [2].
In a Bayesian world that is different. For example, say you are about to eat M&Ms for the first time in your life and you are asked what you expect the colour distribution to be. Following a Bayesian perspective you might assert, "well, I walked through the park today and saw a lot of green trees, so 40% green, each tree had some (red) apples, so 25% red, the sun was shining, so 15% yellow and when I came home it started pouring down on me, hence 20% of the M&Ms will be blue." That analogy shows that "probabilites are fundamentally related to our own knowlegde about an event" [2].
This prior estimation of $\theta$ (here the distribution of the colors within a M&M package) is a huge topic of debate. (Subjective) Bayesians say it is subjective, what would result in always different outcomes since everybody has their own experience/knowledge. Others say, we must first check it and then base it on frequency (that goes into the frequentist direction). Or maybe everything is subjective and so all models are different, just that some of them are actually useful [3]. Just think of the data you chose, the model you want to use etc. Those decisions are all based on subjectivity. The pragmatic solution which was found was, that if the sample size is just big enough the selected starting value for $\theta$ does not matter anymore, since all $\theta$s will converge all to the same value (this is also called the law of big numbers).
This idea is also called Bayes' rule, which is the core of Bayesian statistics. Here's how it looks:
\begin{equation} \color{orange}{P(A|B)} = \frac{\color{red}{P(B|A)}\color{green}{P(A)}}{\color{magenta}{P(B)}} \end{equation}
In order to better explain the various parts of that equation, I will stick to the M&Ms analogy.
Now we could read our Bayes' rule like so:
\begin{equation} Posterior\ =\ \frac{Likelihood\ *\ Prior/Believe}{Evidence} \end{equation}
The main idea is that we can update our beliefs with that model. In statistics we can call this sequentialism. Continuing with the M&Ms analogy, that means that with every M&M you eat, your probability of a chosen color is updated. This is an iterative process and can be repeated continuously; everytime the posterior (the belief) of what color the next M&M you pick from a package will be, is updated (updated here can either mean that the probability of a certain color either increases or decreases). So lets imagine you pick/eat three different M&Ms from your package. Now you could just update your belief once, using each of these three M&Ms; Bayes' rule sequentially incorporates these three M&Ms. Meaning we pick/eat one M&M and update our probability (our posterior) accordingly. Next, we will pick/eat the second M&M, and what happens now is that our posterior which we just calculated based on the color of the first M&M, becomes our new prior, and so on.
Lets do this again step by step. We have a new bought package of M&Ms, and we already assume that the colors are distributed by a distribution $\color{green}{P(A)}$.
\begin{equation} \color{orange}{P(A|B)} = \frac{P(B|A)\color{green}{P(A)}}{P(B)} \end{equation}
Now you open the package and pick/eat the first M&M $P(A)$, and we update our belief accordingly. Because we actually now know what color this M&M had.
\begin{equation} \color{red}{P(A|B)} = \frac{P(B|A)\color{orange}{P(A)}}{P(B)} \end{equation}
And with the second M&M picked, we will update our beliefs again.
\begin{equation} \color{blue}{P(A|B)} = \frac{P(B|A)\color{red}{P(A)}}{P(B)} \end{equation}
This is going on and on with every M&M you eat. As the lecturer indicates in [1], our posterior tonight is our prior tomorrow. In a more statistical version, this function can be written as:
\begin{equation} \color{orange}{P(\theta|y)} = \frac{P(y|\theta)\color{green}{P(\theta)}}{\color{magenta}{P(y)}} \end{equation}
This is nothing different then the above. Our data (here $y$) and our unknowns (here $\theta$). Essentially, we want to get our unknowns ($\theta$s) given our knowns (our data $y$). In order to calculate that, we can first get rid of $\color{magenta}{P(y)}$. Since we already have the data, we can treat it as fixed (since what should change on already gathered data?). So we can get rid of the denominator. However, $\theta$ is what we do not know. How can we derive something we do not know? The idea is to give it some kind of distribution, hence, our unknowns can be quantified using probabilites.1 With that in mind we can transform our original equation to:
\begin{equation} P(\theta|y) \propto L(y|\theta)P(\theta) \end{equation}
First I want to point out a property of the Bayes' rule. It states that "the posterior density is proprotional (denoted as $\propto$) to the likelihood function times the prior density" [3]. In statistical terms the likelihood function just means a function of $\theta$ given data $y$. A good example is statistical inference. We have some data (lets say about speeding) and we want to know, what are certain parameters ($\theta$s) that can form a prediction as to the likelihood regarding whether or not a person is speeding?
So, why is all of that relevant to the relationship between MAP, MLE and EM? The EM is a method which is closely related to Bayesian inference and also to MAP [1, p. 11]. So it is good to know, what kind of mindset a Baysian has.
1A really good quote here is: "[...] probability is our best language to quantify uncertainty", from [3], lecture 16.
In the pretext I highlighted the differences between Frequentist and Bayesian thinking and I also gave a short insight into Bayesian thinking. Moving on, I will now delve a bit more deeper into the explanation of MLE, MAP and EM.
The general gist of the Maximum Likelihood Estimation is to estimate the probability of an event given some data. In the M&M analogy, what is the probability of a red M&M given a package of M&Ms. Mathmatically put, this would look like
\begin{equation} P(red\ M\&M|package\ of\ M\&Ms) \propto L(package\ of\ M\&Ms|red\ M\&M) \end{equation}
Lets get a bit more hands-on. A good idea could be, to just buy 100 packages of M&Ms and just count the number of occurances of red M&Ms in each of the packages. So, we come to the conclusion that the amount of red M&Ms in the packages are somewhat uniformly distributed.
We can see that of 100 packages we tested, around 19 had 26 red M&Ms. So, we can say, that 26 red M&Ms is the most probable value. So the next time, that we are going to buy a package of M&Ms this is what we expect. We expect that is has 26 red M&Ms [4].
So what does the MLE do in mathmatical terms? Well, it is called the maximum likelihood estimator, hence, it tries to maximize the likehood of an event to occur. Therefore, the MLE returns a point estimate, which maximizes the likelihood. When we look at any uniform distribution, we can see, that the most probable value is always the mean, which in a uniform distribution, is always the estimator which maximizes the likelihood. When we put that down in a formula it would look like this2:
\begin{equation} \theta_{MLE} = argmax_{\theta}\ P(x|\theta) \end{equation}
Spoken that would sound like: "Return me those values, which maximizes the probability of my data given parameters." One could argue that the MLE idea is mostly a frequentist idea. We just measure often enough, then we take the mean (which is the value which maximizes the likelihood) and we already have our MLE. This is a bit different when we are talking about MAP.
2Normally this function also takes the log-likelihood. The reason for this is, that is it computationally easier to maximize. Since I have not explained that, I will leave the log out in this formula.
Now assume you read some news in the paper that the company which produces the M&Ms runs low on red color. So the next time you buy a package M&Ms and you ask yourself "how many red M&Ms are inside that package?", you cannot just take the mean, as established in the MLE section. With that low-color information you already can guess, that the red colored M&Ms within a package cannot be uniformly distributed anymore. You rather assume such a distribution:
If we would try to use MLE to predict, what would maximize our likelihood, then we would be terribly off. But thanks to the established Bayesian thinking in the Preface, we can account for that fact. We can tell our function, that it has to adjust for that distribution.
\begin{equation} \theta_{MAP} = argmax_{\theta}\ P(x|\theta)g(\theta) \end{equation}
The $g(\theta)$ is our prior. More specifically, it is our belief that we are dealing with a specific probability distribution function. Since it is also a maximization function, MAP also returns a point estimate, in fact those points which maximize the posterior distribution.3 The MAP idea is, hence we giving it some prior information, rather an idea which Bayesians like.
3@Tim♦ already gave the link to the fitting question, which gives an answer to the difference between "likelihood" and "probability".
The Expectation Maximization "algorithm" is the idea to approximate the parameters, so that we could create a function, which would best fit the data we have. So what the EM tries, is to estimate those parameters ($\theta$s) which maximize the posterior distribution. This is helpful, if we are just dealing with a subset of data.4 [5] has a quite nice representation of the EM using a coin toss example, which I want to display here.
This picture is taken from the paper What is the expectation maximization algorithm? by the authors Do & Batzoglou (2008, p. 898).
Let me first describe that picture, and then dive a bit deeper into the math behind this approach. We can see here, that we initially select two random variables for $\hat{\theta}_A^{(0)}$ and $\hat{\theta}_B^{(0)}$. Those are the respective probabilites that this coin displays head, when thrown. Next, we have some data, but we do not know which coin created that data.5 However, we can caluclate the expectation for each coin. So lets first calculate the expectation that the first dataset [HTTTHHTHTH] belongs to coin a, if coin a has the probability of $0.6$ to return head after thrown:
\begin{equation} \frac{0.6^{5}*(1-0.6)^{10-5}}{0.6^{5}*(1-0.6)^{10-5}+0.5^{5}*0.5^{10-5}} = 0.45 \end{equation}
The "algorithm" uses this function to calculate all the expectations for coin a. The expectation for coin b are easily computed, since we can just do 1 - probability of coin a. Once we have all data, we can multiply our expectation with the number of events we want to measure. Meaning, we calculate:
\begin{equation} 0.45 * 5 = 2.2 \end{equation}
Now we know, that if the first data set would belong to coin a, we would expect $2.2$ times heads and $2.2$ times tails6. Once we have that full table, all what we do, is to do MLE. We sum up the values for the occurances of heads and tails for each coin, and calculate the probability of heads for each coin. This is also called the M(aximization)-step. These two probabilities we just calculated are now our new values, with which we re-run our expectation calculation. We can repeat this as many times as we want. The nice idea of this is, that in the end we can approximate the real $\theta$s, viz. after ten iterations we have a posterior maximization value of $0.8$ for coin a.
4On the first page of their paper Dempster et al. [1] define a subset of data, as two sample spaces, whereas the second one is displayed through a transformation $y$.
5It should be noted that the EM algorithm is also seen as a clustering method, since we can now maximize the expectation that the data is either belongs to coin a or coin b.
6$0.45 * (10-5) = 2.2$
After explaining MLE, MAP and EM, lets now discuss their relationship and why it was important to first review how a Bayesian thinks. The MAP function essentially derives from Bayes' rule, like shown in the Preface. When we again think about the function of the MAP, we can see that it just multiplies a likelihood with a prior. However, when use as prior the uniform distribution then MAP = MLE. Hence, the MLE is just a special version of the MAP, using a uniform distribution. EM also assumes that the given data is uniformly distributed, thus it uses the MLE. Having written that, Dempster et al. [1] point out multiple times, that the EM "algorithm" can easily be altered to use MAP, meaning a different probability distribution of the data.
If you have read until this point, then you are really in love with either Data Science or theory! If you want to see this in action now, or you want to read more, it might be worth (additional to checking out the Sources section) to visit this link.
Note: This is the paper, where most of the references point to. It is really math heavy and explains the Expectation Maximization "algorithm" probably in its most mathmathical way.
[2] https://jakevdp.github.io/blog/2014/03/11/frequentism-and-bayesianism-a-practical-intro/
Note: This is a really good introduction into Bayesian vs. Frequentists. It delves a lot more deeper into that topic that what was outlined here. Moreover, it was written by Jake Vanderplas who is a well known author and developer of the scipy Python package.
[3] https://cs109.github.io/2015/
Note: This source is an amazing source for introductry to advanced topics in machine learning. They give really good advices on which books to read (which are mostly free available on the web) and they explain a lot of topics, so that they are understandable. This is a recommended source to read/listen to!
[4] http://www.bdhammel.com/mle-map/
Note: In this source the distinction between MLE and MAP is also quite good explained.
[5] https://datajobs.com/data-science-repo/Expectation-Maximization-Primer-[Do-and-Batzoglou].pdf
Note: This paper is quite short, but visualizes and explains quite nice, what the EM algorithm is.
