EM Algorithm for Mixture of Lines

Assume that the training examples ${\bf x}_n \in \mathbb{R}^2$ with $n=1,...,N$ were generated from a mixture of $K$ lines

$$P(x_{n,2} \vert z_{n,k}=1) = \mathcal{N}( x_{n,2} \vert \theta_{k,1} x_{n,1} + \theta_{k,2},\sigma_k)$$ (1)

where

$$\mathcal{N}( x \vert \mu,\sigma) = \frac{1}{\sqrt{2\pi} \sigma} \exp \left( -\frac{(x-\mu)^2}{2 \sigma^2}\right)$$ (2)

and the hidden variable $z_{n,k}=1$ if ${\bf x}_n$ is generated from line $k$ and 0 otherwise.

1. [1* P]Derive the update equations for the M-step of the EM algorithm for the variables ${\bf\theta}_{k}$ and $\sigma_k$ .

2. [2* P]Implement the EM algorithm for Mixture of Lines using the update equations you derived in 1. Use the provided dataset⁸ to evaluate your implementation. Show some plots of intermediate steps and describe what is happening.

Present your results clearly, structured and legible. Document them in such a way that anybody can reproduce them effortless. Send the code of your solution to mailto:florian.hubner@igi.tugraz.atflorian.hubner@igi.tugraz.at