Skip to main content

Expectation maximizaton


Expectation maximization algorithm

Expectation maximization(EM) is an algorithm that applied in many applications. EM can be used in Hidden Markov Model (HMM) or in Bayes model. This algorithm basically has 2 steps: Expectation step and Maximization step. The main advantage of EM is resolve problem with incomplete data or with latent variable. In simple, E step gives an assumption and M step will maximize the assumption and find out the next attribute for next E step. The algorithm is finished when we got convergence. We will talk about the main idea of algorithm and the math behind it. 

The most popular example of EM is flip two coins A, B. Assume, we have two biased coins A and B. We flip coin in $m$ times, each time for $n$ flips. The question is: what is probability of head of coin A and coin B respectively: $\theta_{A}$ and $\theta_{B}$ in experiment. 

If all information is provided: which coin (A or B) is used in each time, we can calculate the probabilities easily. 
$$ \theta_{A} = \frac{\sum headA}{\sum(headA + tailA)}  (1) $$    
$$ \theta_{B} = \frac{\sum headB}{\sum(headB + tailB)}   (2) $$.  

But how can we estimate the $ \theta_{A}$ and $\theta_{B}$ if we don't know which one is used in each time ?

A simple usecase
We model the problem with parameters. Assume, $x= \{x_1, ..., x_m\}$ with $x_{i}$ is number of head in the $i_{th}$ sample, $z = \{ z_1, ..., z_m\} $ with $z_{i}$  in ${A, B}$ is type of coin. The problem will become joint probability of $x$ and $z$. In the previous (1) and (2) we already knew both of parameters and we can easily calculate.  
We define log likelihood of distribution of joint probability is: $logp(x, z; \theta)$  and it is a concave function with optimal point $\theta = (theta_A, theta_B)$ is calculated in (1) and (2). 


In the case of latent $z$ we will use EM algorithm to estimate the $\theta$ parameter as bellowing: 


1. Assume that, we got a random initial values of  $\theta_A = 0.6 $ and $ \theta_B = 0.5$.
2. E-step:  The input is 5 times choose the coin, each time we flip this coin 10. We estimate the chance of coin A and B: 
The pdf: $$ pdf = (_{k}^{n})p^{k}(1-p)^{n-k} $$ We omit the coefficient with both A and B coin
For the first sample:
$$ pdf_A = \theta_{A}^{5}*(1-\theta_{A})^{(10 - 5)} = 0.6^{5}*0.4^{5} = 0.0007962624 $$
$$ pdf_B = \theta_{B}^{5}*(1-\theta_{B})^{(10 - 5)} = 0.5^{5}*0.5^{5} = 0.0009765625$$
The probability of A and B for this sample:
$$ p_A = 0.0007962624/(0.0007962624 + 0.0009765625) = ~ 0.45 $$
And 
$$p_B = ~ 0.55 $$
Now we got the distribution head and tail:
Coin A: ~2.2H 2.2T  Coin B: ~2.8H 2.8T
Similarity, we got a table of distribution of head and tail for each A and B. 
3. M-step:
We re-calculate the $\theta_A and \theta_B $ based on the formula (1) and (2). 
4. After several step E-step & M-step the algorithm converges.

 Behind the algorithm
Mixture of Gaussian model:  $x = \{x^{(1)},...,x^{(m)}\},  z = \{z^{(1)},...,z^{(m)}\}$
$$p(x^{(i)}, z^{(i)}) = p(x^{(i)}|z^{(i)}) | p(z^{(i)})$$

Jensen inequality:
$$E[f(x)] \ge f(E[x]) $$ 
if f(x) is convex  and we flip the inequality in case f(x) is concave 

Log likelihood: $ p(x^{(i)};\theta)$  can be referred as pdf
$$ l(\theta) =\sum_{i=1}^{m} logp(x^{(i)};\theta) $$ 
$$= \sum_{i=1}^{m} log\sum_{z}p(x^{(i)}, z^{(i)};\theta)  $$

E-step: construct a problem posterior of $z^i$: $Q_i = p(z^i  = j;x, \theta)$

$$ l(\theta) = \sum_{i=1}^{m}log\sum_{z}Q_i\frac{p(x^{(i)}, z^{(i)};\theta)  }{Q_i}$$
$$ \ge \sum_{i=1}^m E[log( \frac{p(x^{(i)}, z^{(i)};\theta) }{Q_i} )] = \sum_{i=1}^m \sum_{z}Q_ilog(\frac{p(x^{(i)}, z^{(i)};\theta) }{Q_i}) $$

For the choice of $Q_i$ give lower-bound on the loglikelihood of $l(\theta)$ that we are trying to maximize.

M-step: optimize the problem $argmax_{\theta}\sum_{i=1}^m\sum_{z}Q_ilog(\frac{p(x, z;\theta)}{Q_i})$


EM is a powerful algorithm. It is appropriate for problems with clustering,  latent variable or joint distribution. 










Labels:

Comments

Post a Comment

Popular posts from this blog

Generative Adversarial Networks

Generative Adversarial Networks (GAN) is one a Neural Network architecture which simulates zero-sum game. There are 2 parts of this Neural Network. The first is called Generator and other is called Discriminator. Generator tries to mimic data and make the fake data likes the real data in distribution. Meanwhile, the Discriminator tries to maximize the difference between real data and fake data. It is reason we call zero-sum game. Two parts are coaction with each other. This structure makes the GAN to be a interesting Neural Network architecture and it has many application in both academic and industry. In modeling, the GAN is an approach of equilibrium Networks such as Boltzmann Machine did. It is an optimization problem with objectives of: minimize Generator and maximum Discriminator simultaneously.  $max_{D}min_{G} V(D,G)$  $max_{D}min_{G} V(D,G) = E_{x\sim p_{data}(x)}[log(D(x))] + E_{z\sim p_{z}(z)}[log(1 - D(G(z)))]$ $V(D,G)$ is optimization problem subject to G ...
Post a Comment
Read more

Mutual information and feature selection

   Feature selection is one of the most important step to make your model works well. In data mining, feature selection is the first step and it effects to all of process. Feature selection help model on some points: - The model will be trained faster - Reduce overfitting - Simplifying model - Reduce the dimension of data Hence, feature selection is kick-off step and it effects overall, especially in model. There are 3 type of feature selection: Filter methods, wrapper methods and embedded methods. Filter methods: this methods "filter" data based on correlation score. Normally, our data have many features, and a label. We calculate the correlations between features and label. After that, we only retrain the features that have a good (relevant) correlated score and remove others. In this type of method we have some ways to calculate the correlation. - Pearson correlation: this one is based on covariance between 2 continuous variables. $$ p_{X,Y} = \frac {Cov(X, Y)...
Post a Comment
Read more

The basic concepts of deep neural networks

We will explore 3 basic concepts of deep neural networks. The first part will explain how back-propagation algorithm works. The second talks about softmax function. And the last one is cost function. Inside Backpropagation algorithm The main idea of Backpropagation algorithm is aims to minimize the overall neural network error. To do that, we find out the partial derivative of error and weight vector. Take a look in a simple Neural Network: From Sigmoid function to Softmax function and Cross-entropy cost function In the classification problem with multinomial distribution, how do we know which label is choosen? Softmax function is used to do that. In practice, some people might also use one2All mechanism to detect label by traning many logistic regression models. However, it is not effective solution. Softmax function helps us to determine the label also we can calculate the cost from this easily by using Cross-entropy cost function. Sigmoid function Sigmoid function co...
Post a Comment
Read more