User:Timothee Flutre/Notebook/Postdoc/2011/12/14
From OpenWetWare
(Difference between revisions)
(→Entry title: add motivation, examples, aim, model) 
(→Learn about mixture models and the EM algorithm: add latent variables + algebra for mu_k and sigma_k) 

Line 16:  Line 16:  
* '''Model''': technically, we say that the observations were generated by a family of density functions. The density of all the observations is thus a mixture of densities, one per cluster. In our case, we will assume that each cluster <math>k</math> corresponds to a Normal distribution of mean <math>\mu_k</math> and standard deviation <math>\sigma_k</math>. Moreover, as we don't know for sure from which cluster a given observation comes from, we define the mixture probability <math>w_k</math> to be the probability that any given observation comes from cluster <math>k</math>. As a result, we have the following list of parameters: <math>\theta=(w_1,...,w_K,\mu_1,...\mu_K,\sigma_1,...,\sigma_K</math>. Finally, for a given observation <math>x_i</math>, we can write the model <math>f(x_i/\theta) = \sum_{k=1}^{K} w_k g(x_i/\mu_k,\sigma_k)</math> , wth <math>g</math> being the Normal distribution <math>g(x_i/\mu_k,\sigma_k) = \frac{1}{\sqrt{2\pi} \sigma_k} \exp^{\frac{1}{2}(\frac{x_i  \mu_k}{\sigma_k})^2}</math>  * '''Model''': technically, we say that the observations were generated by a family of density functions. The density of all the observations is thus a mixture of densities, one per cluster. In our case, we will assume that each cluster <math>k</math> corresponds to a Normal distribution of mean <math>\mu_k</math> and standard deviation <math>\sigma_k</math>. Moreover, as we don't know for sure from which cluster a given observation comes from, we define the mixture probability <math>w_k</math> to be the probability that any given observation comes from cluster <math>k</math>. As a result, we have the following list of parameters: <math>\theta=(w_1,...,w_K,\mu_1,...\mu_K,\sigma_1,...,\sigma_K</math>. Finally, for a given observation <math>x_i</math>, we can write the model <math>f(x_i/\theta) = \sum_{k=1}^{K} w_k g(x_i/\mu_k,\sigma_k)</math> , wth <math>g</math> being the Normal distribution <math>g(x_i/\mu_k,\sigma_k) = \frac{1}{\sqrt{2\pi} \sigma_k} \exp^{\frac{1}{2}(\frac{x_i  \mu_k}{\sigma_k})^2}</math>  
+  * '''Likelihood''': this corresponds to the probability of obtaining the data given the parameters: <math>L(\theta) = P(X/\theta)</math>. We assume that the observations are independent, ie. they were generated independently, whether they are from the same cluster or not. Therefore we can write: <math>L(\theta) = \prod_{i=1}^N f(x_i/\theta)</math>.  
+  
+  * '''Estimation''': now we want to find the values of the parameters that maximize the likelihood. This reduces to (i) differentiating the likelihood with respect to each parameter, and then (ii) finding the value at which each partial derivative is zero. Instead of maximizing the likelihood, we maximize its logarithm, noted <math>l(\theta)</math>. It gives the same solution because the log is monotonically increasing, but it's easier to derive the loglikelihood than the likelihood. Here is the whole formula:  
+  <math>l(\theta) = \sum_{i=1}^N log(f(x_i/\theta)) = \sum_{i=1}^N log( \sum_{k=1}^{K} w_k \frac{1}{\sqrt{2\pi} \sigma_k} \exp^{\frac{1}{2}(\frac{x_i  \mu_k}{\sigma_k})^2})</math>  
+  
+  * '''Latent variables''': here it's worth noting that, although everything seems fine, a big information is lacking, we aim at finding the parameters defining the mixture but we don't know from which cluster each observation is coming... That's why we need to introduce the following N latent variables <math>Z_1,...,Z_i,...,Z_N</math>, one for each observation, such that <math>Z_i=k</math> means that <math>x_i</math> belongs to cluster <math>k</math>. Thanks to this, we can reinterpret the mixing probabilities: <math>w_k = P(Z_i=k/\theta)</math>. Moreover, we can now define the membership probabilities, one for each observation: <math>P(Z_i=k/x_i,\theta) = \frac{w_k g(x_i/\mu_k,\sigma_k)}{\sum_{l=1}^K w_l g(x_i/\mu_l,\sigma_l)}</math>. We will note these membership probabilities <math>p(k/i)</math> as they will have a big role in the EM algorithm below. Indeed, we don't know the values taken by the latent variables, so we will have to infer their probabilities from the data.  
+  
+  * '''Technical details''': a few important rules are required, but only from a highschool level in maths (see [http://en.wikipedia.org/wiki/Differentiation_%28mathematics%29#Rules_for_finding_the_derivative here]). Let's start by finding the maximumlikelihood estimates of the mean of each cluster:  
+  
+  <math>\frac{\partial l(\theta)}{\partial \mu_k} = \sum_{i=1}^N \frac{1}{f(x_i/\theta)} \frac{\partial f(x_i/\theta)}{\partial \mu_k}</math>  
+  
+  As we derive with respect to <math>\mu_k</math>, all the others means <math>\mu_l</math> with <math>l \ne k</math> are constant, and thus disappear:  
+  
+  <math>\frac{\partial f(x_i/\theta)}{\partial \mu_k} = w_k \frac{\partial g(x_i/\mu_k,\sigma_k)}{\partial \mu_k}</math>  
+  
+  And finally:  
+  
+  <math>\frac{\partial g(x_i/\mu_k,\sigma_k)}{\partial \mu_k} = \frac{\mu_k  x_i}{\sigma_k^2} g(x_i/\mu_k,\sigma_k)</math>  
+  
+  Once we put all together, we end up with:  
+  
+  <math>\frac{\partial l(\theta)}{\partial \mu_k} = \sum_{i=1}^N \frac{1}{\sigma^2} \frac{w_k g(x_i/\mu_k,\sigma_k)}{\sum_{l=1}^K w_l g(x_i/\mu_l,\sigma_l)} (\mu_k  x_i)</math>  
+  
+  By convention, we note <math>\hat{\mu_k}</math> the maximumlikelihood estimate of <math>\mu_k</math>:  
+  
+  <math>\frac{\partial l(\theta)}{\partial \mu_k}_{\mu_k=\hat{\mu_k}} = 0</math>  
+  
+  Therefore, we finally obtain:  
+  
+  <math>\hat{\mu_k} = \frac{\sum_{i=1}^N p(k/i) x_i}{\sum_{i=1}^N p(k/i)}</math>  
+  
+  By doing the same kind of algebra, we also obtain the ML estimates for the standard deviation of each cluster:  
+  
+  <math>\hat{\sigma_k} = \sqrt{\frac{\sum_{i=1}^N p(k/i) (x_i  \mu_k)^2}{\sum_{i=1}^N p(k/i)}}</math>  
<! ##### DO NOT edit below this line unless you know what you are doing. ##### >  <! ##### DO NOT edit below this line unless you know what you are doing. ##### > 
Revision as of 17:34, 14 December 2011
Project name  Main project page Previous entry Next entry 
Learn about mixture models and the EM algorithm
As we derive with respect to μ_{k}, all the others means μ_{l} with are constant, and thus disappear:
And finally:
Once we put all together, we end up with:
By convention, we note the maximumlikelihood estimate of μ_{k}:
Therefore, we finally obtain:
By doing the same kind of algebra, we also obtain the ML estimates for the standard deviation of each cluster:
