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

NLG pipeline

NLG ¶ NLG stands for Natural Languate Generation. NLG is one field of AI aims to generate the understandable and appropriate texts from raw data. We should differientiate the concepts of NLG with NLP and NLU. NLP is natural languate processing. This is a field in AI working on text generally. NLP contains Speed recornigion, Speed synthesis, NLG and NLU. NLU and NLG is subsets of NLP. While NLG generate the text, NLU uses text as input and generate some pattern such as Sentiment Analysis, Summary. The pipeline of NLG NLG can be divided into 3 phases: Document planning, Microplanning and Realisation. The purpose of Document planning is to chose what to say and the purpos of Microplanning and Realisation is to find how to say. There are some components in each phase. In traditional NLG system, we have 5 components: Content Determination, Text Structure, Aggregation, Lexicalisation, Reffering expression, Realisation. Content Determination Content Determination is sets of enti...
Post a Comment
Read more

Introduction to recurrent neural networks

Recurrent neural networks (RNN) is one of the most popular neural networks. If you hear about LSTM ( Long-short term memory), it is one of types of RNN. Specially, the RECURSIVE neural networks is a general of Recurrent neural networks. The different between them is shared weights. In Recursive neural network, shared weights are put in every node, however in recurrent neural networks, shared weights are put through sequences. Problem : Could you know what word will be filled in the sentence: “I like French … ” ?. Let represent the sentence in numberic of words, based on dictionary, we are facing with a sequences problem: predicting the next word given by previous words. RNN does not only dare with sequence problem, It also build a neural network that can remmember. It is exactly what the brain does regularily. Normally, a feedforward neural networks only process information through layers and forget information in t...
Post a Comment
Read more

Where do variance and bias come from ?

What are variance and bias ? Variance and bias are assertions to evaluate our model based on different datasets. Both of them happen together and we have to find the methodology to trade-off them. A good model is a small variance and bias model.  In wikipedia, we have definitions of variance and bias, formally: The  bias  is an error from erroneous assumptions in the learning  algorithm . The  variance  is an error from sensitivity to small fluctuations in the training set.  (source:  https://en.wikipedia.org/wiki/Bias–variance_tradeoff ) However, I want to make them more normal and practical, so we could understand them as bellowing definitions: Variance asserts fluctuation of precision of model against training data, test data with real data(new data). One model has a hight precision in training and test phase but has low precision with real data, It means this model has hight variance. Hight variance also is called as overfitting: Too...
Post a Comment
Read more