(Solved): Estimates of Parameters of GMM: The Expectation Maximization (EM) Algorithm We observe n data poin ...

Estimates of Parameters of GMM: The Expectation Maximization (EM) Algorithm We observe $n$ data points ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_n$ in ${\mathbb{R}}^d$. We wish to maximize the GMM likelihood with respect to the parameter set $?=\left\{p_1,\dots ,p_K,{?}^{(1)},\dots ,{?}^{(K)},{?}_1^2,\dots ,{?}_K^2\right\}$ Maximizing the log-likelihood $\log \left({?}_{i=1}^{n}p\left({\mathbf{x}}^{(i)}??\right)\right)$ is not tractable in the setting of GMMs. There is no closed-form solution to finding the parameter set $?$ that maximizes the likelihood. The EM algorithm is an iterative algorithm that finds a locally optimal solution $\widehat{?}$ to the GMM likelihood maximization problem. E Step The $\mathbf{E}$ Step of the algorithm involves finding the posterior probability that point ${\mathbf{x}}^{(i)}$ was generated by cluster $j$, for every $i=1,\dots ,n$ and $j=1,\dots ,K$. This step assumes the knowledge of the parameter set $?$. We find the posterior using the following equation: $p($ point ${\mathbf{x}}^{(i)}$ was generated by cluster $j?{\mathbf{x}}^{(i)},?)?p(j?i)=\frac{p_j\mathcal{N}\left({\mathbf{x}}^{(i)};{?}^{(j)},{?}_j^{2}I\right)}{p\left({\mathbf{x}}^{(i)}??\right)}$ M Step The $\mathbf{M}$ Step of the algorithm maximizes a proxy function $\widehat{?}\left({\mathbf{x}}^{(1)},\dots ,{\mathbf{x}}^{(n)}??\right)$ of the log-likelihood over $?$, where $\widehat{?}\left({\mathbf{x}}^{(1)},\dots ,{\mathbf{x}}^{(n)}??\right)?{?}_{i=1}^n{?}_{j=1}^{K}p(j?i)\log \left(\frac{p\left({\mathbf{x}}^{(i)}\text{ and }{\mathbf{x}}^{(i)}\text{ generated by cluster }j??\right)}{p(j?i)}\right)$ This is done instead of maximizing over $?$ the actual log-likelihood $?\left({\mathbf{x}}^{(1)},\dots ,{\mathbf{x}}^{(n)}??\right)={?}_{i=1}^n\log \left[{?}_{j=1}^{K}p\left({\mathbf{x}}^{(i)}\text{ generated by cluster }j??\right)\right]$ Maximizing the proxy function over the parameter set $?$, one can verify by taking derivatives and setting them equal to zero that $\begin{array}{rl}\widehat{{?}^{(j)}}& =\frac{{?}_{i=1}^{n}p(j?i){\mathbf{x}}^{(i)}}{{?}_{i=1}^{n}p(j?i)}\\ \widehat{p_j}& =\frac{1}{n}\underset{i=1}{\overset{n}{?}}p(j?i),\\ \widehat{{?}_j^2}& =\frac{{?}_{i=1}^{n}p(j?i){?{\mathbf{x}}^{(i)}?\widehat{{?}^{(j)}}?}^2}{d{?}_{i=1}^{n}p(j?i)}.\end{array}$ The $\mathrm{E}$ and $\mathrm{M}$ steps are repeated iteratively until there is no noticeable change in the actual likelihood computed after M step using the newly estimated parameters or if the parameters do not vary by much. Initialization As for the initialization before the first time E step is carried out, we can either do a random initialization of the parameter set $?$ or we can employ k-means to find the initial cluster centers of the $K$ clusters and use the global variance of the dataset as the initial variance of all the $K$ clusters. In the latter case, the mixture weights can be initialized to the proportion of data points in the clusters as found by the k-means algorithm. Gaussian Mixture Model: An Example Update - E-Step Assume that the initial means and variances of two clusters in a GMM are as follows: ${?}^{(1)}=?3,{?}^{(2)}=2,{?}_1^2={?}_2^2=4$. Let $p_1=p_2=0.5$. Let $x^{(1)}=0.2,x^{(2)}=?0.9,x^{(3)}=?1,x^{(4)}=1.2,x^{(5)}=1.8$ be five points that we wish to cluster. In this problem and in the next, we compute the updated parameters corresponding to cluster 1 . You may use any computational tool at your disposal. Compute the following posterior probabilities (provide at least five decimal digits): $p(1?1)=$ $p(1?2)=$ $p(1?3)=$ $p(1?4)=$ $p(1?5)=$ Gaussian Mixture Model: An Example Update - M-Step Compute the updated parameters corresponding to cluster 1 (provide at lea ${\hat{p}}_1=$ ${\widehat{?}}_1=$ ${\widehat{?}}_1^2=$