CS440/ECE448 Spring 2020

Assignment 5: Classify

Due date: Wednesday November 4th, 11:59pm

Created 2018: Justin Lizama and Medhini Narasimhan
Updated 2020: Daniel Gonzales and Kuangxiao Gu
Updated Fall 2020: Ruicheng Xian and Weilin Zhang

In this assignment, we are going to see if we can teach a computer to distinguish living things from non-living things. More precisely, you will implement the perceptron and K-nearest neighbors algorithms to detect whether or not an image contains an animal or not.

Contents

General guidelines and submission

Basic instructions are the same as in MP 1. To summarize:

You should submit on Gradescope:

  • A copy of classify.py containing all your new code

Problem Statement

You are given a dataset consisting of images, that either contain pictures of animals or something else. Your task is to write two classification algorithms to classify which images have animals in them. Using the training set, you will train a perceptron classifier and K-nearest neighbor classifier that will predict the right class label for an unseen image. Use the development set to test the accuracy of your learned models. We will have a separate (unseen) test set that we will use to run your code after you turn it in. You may use NumPy in this MP to program your solution. Aside from that library, no other outside non-standard libraries can be used.

Dataset

This dataset consists of 10000 32x32 colored images total. We have split this data set for you into 2500 development examples and 7500 training examples. The images have their RGB values scaled to range 0-1. This is a subset of the CIFAR-10 dataset, provided by Alex Krizhevsky.

The data set can be downloaded here: data (gzip) or data (zip). When you uncompress this, you'll find a binary object that our reader code will unpack for you.

Perceptron Model

The perceptron model is a linear function that tries to separate data into two or more classes. It does this by learning a set of weight coefficients \(w_i\) and then adding a bias \(b\). Suppose you have features \(x_1,\dots,x_n\) then this can be expressed in the following fashion: \[ f_{w,b} (x) = \sum_{i=1}^n w_i x_i + b \] You will use the perceptron learning algorithm to find good weight parameters \(w_i\) and \(b\) such that \(\mathrm{sign}(f_{w,b}(x)) > 0\) when there is an animal in the image and \(\mathrm{sign}(f_{w,b}(x)) \leq 0\) when there is a no animal in the image. Note that in our case, each image is 32x32 and has thre (RGB) color channels, yielding 32*32*3 = 3072 features.

Training and Development

Please see the textbook and lecture notes for the perceptron algorithm. You will be using a single classical perceptron whose output is either positive or negative (i.e. sign/step activation function).

  • Training: To train the perceptron you are going to need to implement the perceptron learning algorithm on the training set. Each pixel of the image is a feature in this case. Be sure to initialize weights and biases to zero.
    Note: To get full points on the autograder, use a constant learning rate (no decay) and do not shuffle the training data.

  • Development: After you have trained your perceptron classifier, you will have your model decide whether or not images in the development set contain animals in them or not. In order to do this take the sign of the function \(f_{w,b}(x)\). If it is negative then classify as \(0\). If it is positive then classify as \(1\).

Use only the training set to learn the weights.

K-nearest neighbors Model

Perceptron is a simple linear model, and although this is sufficient in a lot of cases, this method has its limits. To see the performance of a different simple classifier, implement K-Nearest Neighbors using Euclidean distance. To break ties, use the negative label (no animal class). You must implement this algorithm on your own with only standard libraries and NumPy.

Note: To prevent memory errors due to the autograder's limitations, your algorithm should iterate through the list of test images rather than (say) creating a vector containing all the test images.

Our autograder tests will pass in various values for the parameter k. For your own understanding, you should try and see what's the highest accuracy you can get. Also try to understand how this algorithm compares to a perceptron, in accuracy but also efficiency.

Provided Code Skeleton

We have provided ( tar zip) all the code to get you started on your MP, which means you will only have to implement the logic behind perceptron.

  • reader.py - This file is responsible for reading in the data set. It makes a giant NumPy array of feature vectors corresponding with each image.

  • mp5.py - This is the main file that starts the program, and computes the accuracy, precision, recall, and F1-score using your implementation of the classifers.

  • classify.py This is the file where you will be doing all of your work.

To understand more about how to run the MP, run python3 mp5.py -h in your terminal.

Add your code to classify.py. Do not modify the code provided in the other files.

Inside the code ...

  • The function classifyPerceptron() takes as input the training data, training labels, development set, learning rate, and maximum number of iterations.
  • The function classifyKNN() takes as input the training data, training labels, development set, and the number of neighbors used (k).
  • By default, you need to put the training data in the mp5-code/ folder, and the training data provided is the output from reader.py.
  • The training labels is the list of labels corresponding to each image in the training data.
  • The development set is the NumPy array of images that you are going to test your implementation on.
  • You may change the default values for parameters such as the maximum number of iterations, the learning rate, k, etc. However, you may not reset these values inside your classifier functions, because some of our tests pass in specific values for these parameters.
  • You will have each classify() output the predicted labels for the development set from your models.