Homework 3: Available 10/08/2016, Due 10/22/2016.
NOTE: Only the software portion can be done in teams of up to three people, your report should be your own work.
Handing in assignment on compass:
  1. Report in pdf format. File name should be net_id_hw3_report (e.g. yeh17_hw3_report.pdf)
  2. Code for both code-from-scratch and TensorFlow in TGZ or ZIP format. File name should be net_id_hw3_code (e.g. yeh17_hw3_code.zip)
  3. Include your team members' name in the submission description and report.
  4. Make sure the uploaded file is correct. Missing or corrupted files will be considered late. (You can download the uploaded file to verify)

Data

For this assignment, the data contains only this image.

Software Requirements

  1. Do NOT use ipython notebook.
  2. Modularized your code, a single script code is difficult to read.
  3. Use a relative path when accessing data. Clearly write in the README file where to store the data relative to the base directory.

Pencil-and-Paper

In this part of the assignment, you will derive the update equations for Gaussian Mixture Models using the EM algorithm.
You are given a dataset, $D = \{x_1, ... x_n\}$. You have reason to believe that $p_{X|\Theta}(x_i|\theta)$ can be modeled as where $p_{V|H,\Theta}(x,h,\theta)$ has the form of a Gaussian distribution, and $\sum\limits_{k=1}^{m} w_k = 1$
We also define the posterior probability with the following notation,
  1. Read A gentle tutorial of the EM algorithm and its application to parameter estimation for Gaussian mixture and hidden Markov models, to review the EM algorithm and GMM.
  2. Write out the E-Step equations, following the notation above.
  3. Write out the M-Step equations, following the notation above.

Code-From-Scratch

In this portion of the assignment, you'll be clustering an image based on colors. Humans naturally group similar colors together; for example, we might describe a particular outfit as "a maroon sweater with navy blue shorts," ignoring the many subtle variations of color tone present in the sweater.

Given an image, we denote $\vec{x}[\vec{n}] = [r_{\vec{n}}, g_{\vec{n}}, b_{\vec{n}}]^{\intercal}$ as the RGB color vector at pixel $\vec{n} = [n1, n2]$ of an image. We treat each pixel as indepenent examples, meaning we have a training set of $\{\vec{x}_i\}$, where $i$ is the linear index mapped from $\vec{n}$.

Train a Gaussian Mixture model on $\{\vec{x}_i\}$, using the EM update equations derived in Pencil-and-Paper portion of the assignment. Here, we assume $m=3$, this model is a mixture of 3 Gaussian distributions. Randomlly initialize the $\mu$ and $\sigma$ for each of the Gaussian distriubtion.

With a trained GMM, you will have the following values $w_1, w_2, w_3$, $\vec{\mu}_1, \vec{\mu}_2, \vec{\mu}_3$, $\Sigma_1, \Sigma_2, \Sigma_3$, include these in your report.
Lastly, assign a cluster label for each of the pixels in the image. This can be done by computing likelihood that the example $x_{\vec{n}}$ comes from each of the Gaussian distribution in the mixture, and picking the maximum. Denote the cluster label as $l^*$. With the cluster label, now compute an image, where the pixel $x_{\vec{n}}$ is replaced with the corresponding cluster mean $\mu_{l^*}$.

You should expect to have similar effect (Illustrated on another image):



Repeat with different number of clusters, $m=5$ an $m=10$.

Note: For this assigment you are required to have the following modules
  1. Create a function gammaprob that accepts the parameters of a Gaussian mixture model (GMM), in any format that you find convenient (you'll have to use this format for the rest of this problem set), and the data samples as input, and outputs the posterior probability vectors
  2. A function estep that computes the E-step for training a Gaussian mixture model.
  3. A function mstep that computes the M-step for training a Gaussian mixture model.
What to turn in:

TensorFlow

In this section, you will use a higher-level API from the TensorFlow GMM, link, to repeat the code-from-scratch task described above.
Note: Make sure TensorFlow version is >= r.0.10.
You should include the following lines:
"from tensorflow.contrib.factorization.python.ops.gmm import GMM"
"from tensorflow.contrib.factorization.python.ops.kmeans import KMeansClustering as KMeans"

What to turn in: