Homework 4

Overview

K-means and a from-scratch EM fit of a Gaussian mixture on a three-cluster dataset, then a short exercise writing and reading an HDF5 file.

Getting Started

Download the starter code: hw4-starter.zip

unzip hw4-starter.zip
cd hw4-starter
python generate_datasets.py --seed 541

This creates data/ with a placeholder cluster.txt in the same layout as the real file but with different points. Download the real file from the Data link into data/ to replace it.

q1/ contains clustering.py, with a docstring stating how it is run and what it prints or writes. q2/ contains the random_binary_collection.py template from Problem 2. Each directory also contains a test_interfaces.py that runs the script and checks its output. Run it from inside the problem directory:

python -m pytest test_interfaces.py

Problem 1: Clustering Algorithms

Unsupervised clustering algorithms are an efficient means to identify groups of related objects within large populations. Implement the following two clustering algorithms and apply them to the data in cluster.txt. The file contains data as: x, y, class. If necessary, use a regular expression to remove lines that are empty or that are invalid data. You may safely ignore any line that fails the regular expression.

Part A: K-Means Clustering

Use K-Means clustering with 3-clusters to label each \((x,y)\) pair as Head, Ear_right, or Ear_left.

Produce a scatter plot marking each \((x,y)\) pair as either BLUE (class = Head), RED (class = Ear_left) or GREEN (class = Ear_right). Compare the K-means predicted labels to the true label and generate a confusion matrix showing the respective accuracies.

Part B: Gaussian Mixture Models with EM

Gaussian Mixture Models (GMM) are a common method to cluster data from multi-modal probability densities. Expectation maximization (EM) is an iterative procedure to compute (locally) optimal GMM parameters – GMM cluster means \(\mu_k\), covariances \(\Sigma_k\), and mixing weights \(w_k\). EM consists of two steps. The E[xpectation]-step uses the mixture parameters to update estimates of hidden variables. The true but unknown class is an example of a hidden variable. The M[aximization]-step then uses the new hidden variable estimates to update the mixture parameter estimates. This back-and forth update provably increases the likelihood function and the estimate eventually converges to a local likelihood maximum.

The GMM update equations follow:

E-Step: Use current mixture parameters estimates to calculate membership probabilities (a.k.a. the hidden variables) for each sample, \(\gamma_k(x_n)\):

M-Step: Use new \(\gamma_{k}(x_n)\) to update mixture parameter estimates:

for \(k \in \{1, \ldots, K\}\) where \(K \in \mathbb{Z}^+\) is the (predefined) number of mixture components, \(x_n\) for \(n \in \{1, \ldots, N\}\) are the data samples, and \(f(x; \mu_k, \Sigma_k)\) is the \(d\)-dimensional jointly Gaussian pdf:

1. Implement Expectation Maximization and use it to estimate mixture parameters for a 3-component GMM for the cluster dataset.

2. Initialize \(\gamma_k(x_n)\) for each sample using the K-means labels from Part A as “one-hot” membership probabilities (i.e., initialize one of the probabilities as “1” and all others are “0”). Then compute initial \(\mu_k\) and \(\Sigma_k\) for each mixture component.

3. Run EM until it has sufficiently converged. Use either the negative log-likelihood

   \[ \ell = \sum_{n=1}^{N} \log \left( \sum_{k=1}^{K} w_k f(x_n; \mu_k, \Sigma_k) \right) \]

   as a convergence metric or monitor the class assignments until there are only small changes. Be aware that some points may “flip-flop” even when fully converged. Assign each datapoint to the mixture component with the largest membership probability. Produce a Blue-Red-Green scatter plot as in Part A and generate a confusion matrix showing the respective classification accuracies.

4. Generate figures showing the class assignments during the first four iterations.

5. Comment on the difference between the clustering result in Part A and Part B. Describe any obvious difference between the plots and indicate which performs better.

Deliverables

See Submission. clustering.py is your implementation of both parts. q1.pdf contains the K-means scatter plot and confusion matrix, the EM scatter plot and confusion matrix, the first-four-iteration figures, and your comparison.

Problem 2: HDF5 Binary Sequences

The HDF5 format can store multiple data objects in a single file each keyed by object name – e.g., you can store a numpy float array called regressor and a numpy integer array called labels in the same file. HDF5 also allows fast non-sequential access to objects without scanning the entire file. This means you can efficiently access objects and data such as x[idxs] with non-consecutive indexes e.g., idxs = [2, 234, 512]. This random-access property is useful when extracting a random subset from a larger training database.

In this problem you will create an HDF5 file containing a numpy array of binary random sequences that you generate yourself. Follow these steps:

1. Run the provided template python file – random_binary_collection.py (included in starter code). The script is set to DEBUG mode by default.

2. Experiment with the assert statements to trap errors and understand what they are doing by using the shape method on numpy arrays, etc.

3. Set the DEBUG flag to False. Manually create 10 binary sequences each with length 50. It is important that you do this by hand, i.e., do not use a coin, computer, or random number generator.

4. Verify that your HDF5 file was written properly by checking that it can be read back.

Deliverables

See Submission. random_binary_collection.py is your completed script and hw4_binary_sequences.hdf5 is the file it writes.

README.md
.gitignore
requirements.txt
generate_datasets.py
q1/
├── clustering.py
├── test_interfaces.py
└── q1.pdf
q2/
├── random_binary_collection.py
├── test_interfaces.py
└── hw4_binary_sequences.hdf5