Home Coding Entrance Exam

Image Classification with Multiclass Perceptrons

    1. Preprocessing the CIFAR-10 Dataset

For this exam, we will use CIFAR-10, a very popular dataset for benchmarking image classification models. CIFAR-10 consists of RGB color images, each represented as a 3

    • 32 × 32 (i.e., [num RGB channels] × [image height] × [image length]) tensor.

Every image is labeled as one of ten classes: airplane, automobile, bird, cat, deer, dog, frog, horse, ship, truck. CIFAR-10 contains 60000 total images, with 6000 images per class. There are 50000 training images and 10000 test images.

To preprocess the data, please complete the following steps:

    • Download the data. Using the following link, download only the Python version of CIFAR-10: https://www.cs.toronto.edu/~kriz/cifar.html.

        ◦ Load the data. The CIFAR-10 data files are pickled, so you can use thepickle library to read these files. You might find the function pickle.load helpful to unpickle the file.

        ◦ Preprocess the data. Each image consists of 8-bit pixel values ranging from 0 to 255. Normalize all pixel values so that they range from 0 to 1. This will help your classification model converge faster. Feel free to experiment with other data preprocessing techniques.

    2. Training a Multiclass Perceptron

The multiclass perceptron is an algorithm for online multiclass classification. Let D = {(⃗xi, yi)}Ni=1 be a classification dataset, where ⃗xi ∈ Rd is the i-th data point, yi ∈ {ℓj}Mj=0−1 is ⃗xi’s class label, and N is the number of data points in D. The objective of the multiclass perceptron is to learn weight vectors W = {w⃗ℓj }Mj=0−1 and bias scalars b = {bℓj }Mj=0−1, such that arg maxℓj (w⃗ℓj ⃗xi + bℓj ) = yi for all (⃗xi, yi) ∈ D. Together, W and b constitute our classification model.

Define the training and test sets as Dtrain and Dtest, respectively, where D = Dtrain +Dtest. Then, we have N = Ntrain + Ntest, where Ntrain = |Dtrain| and Ntest = |Dtest|. For CIFAR-10, we have N = 60000, Ntrain = 50000, Ntest = 10000, and M = 10. For time and memory limitations of using physical computers, we will separate Dtrain into B distinct batches, with Nbatch = ⌈|DtrainB|⌉. Performing updates with these smaller batches may also help the model avoid some local minima in practice.

In this problem, you need to implement and train a multiclass perceptron to perform image classification on the CIFAR-10 dataset. Here, we obtain ⃗xi by flattening the i-th image into a d-dimensional feature vector, where d = 3 × 32 × 32 = 3072.

The multiclass perceptron algorithm is explained in the pseudocode on the following page.

ake-Home Coding Entrance Exam

Algorithm 1 Multiclass Perceptron


Require: training set Dtrain = {(⃗xi, yi)}Ni=1train , test set Dtest classes M, number of batches B, learning rate η

Initialize weights W = {w⃗ℓj = 0}Mj=0−1 and biases b = {bℓj = 0}Mj=0−1 for batch = 1, ..., B do
create the batch Dbatch from Dtrain
for each example (⃗xi, yi) ∈ Dbatch do

Compute the predicted class probabilities as p⃗i = softmax(w⃗ℓj ⃗xi + bℓj ). end for
Compute the loss (prediction error) as L =
1
Nbatch
cross

entropy(⃗yi, p⃗i).

Nbatch
i=1









Compute the gradients of the loss w.r.t. the weights and biases: ∂W∂L ; ∂∂bL.


Minimize the prediction error by updating the weights and biases via gradient descent:
    • = W − η ∗ ∂W∂L ; b = b − η ∗ ∂∂bL.

end for
for each example (⃗xi′ , yi′ ) ∈ Dtest do
Compute the predicted label as yˆi′  = arg maxℓj (softmax(w⃗ℓj ⃗xi′  + bℓj )).
end for
Compute the test accuracy: Atest =
1
Ntest
accuracy(yi′ , yˆi′ )

Ntest
i′ =1


As outlined in the pseudocode, you should train your model using only the training data, then evaluate your model’s accuracy on the testing data. Your script should print the model’s test accuracy at the end.

Note: In this problem, your multiclass perceptron is expected to yield a test accuracy of around 30%. Meanwhile, recent advances in deep learning have pushed the state-of-the-art CIFAR-10 test accuracy to 99.5%! Hopefully, this serves as compelling motivation for taking this deep learning course.


Implementation

Setup

You can set up a virtual environment by using virtualenv.

    • sudo pip install virtualenv # If you didn’t install it

    • virtualenv -p python3 .env

    • source .env/bin/activate

# [Work on your coding exam...]

    • deactivate

You can install required Python libraries by running the following command:

    • pip install pickle numpy

Code

• We provide you with a skeleton code file called exam.py, which contains a model

class and various functions. Please do NOT modify the main() function to accept arguments or any function definitions. You should implement your solution only by filling in the TODO sections of the skeleton code. We describe some key parts of the skeleton code below, but more detailed instructions for TODO are included in the skeleton code. Please make sure you fill out all theTODO sections in the skeleton code.

    • The forward() function returns the softmax probabilities for each image in the batch. The softmax of a M-dimensional vector ⃗q = [qj]Mj=0−1 is defined as:
softmax(⃗q)j =
eqj

M−1 eqj



j=0

This transforms ⃗q into a distribution p⃗, where the elements of p⃗ sum to 1.

    • The loss() function implements the cross-entropy loss, which is defined as:



entropy(⃗y, p⃗) = −
M−1
cross


⃗yj log(p⃗j)







j=0

Here, ⃗y is the true label distribution and p⃗ is the model’s predicted label distribution. For classification with CIFAR-10, we often represent ⃗y as a one-hot vector, which is a binary vector containing all zeros except for a one at the index of the true class label. For example, if an image in the CIFAR-10 dataset has class label y = 3 (bird), then the one-hot encoding of y would be ⃗y = [0, 0, 0, 1, 0, 0, 0, 0, 0, 0]T .

    • The compute gradients() function returns the gradients. The gradient descent() function uses the gradients and learning rate to update the model. Do not negate the weights and biases or update the model in the compute gradients() function. For each batch, you should compute the average gradient across the batch, then update your model parameters using this batch-average gradient.

    • The accuracy() function uses the accuracy metric to evaluate the model’s predicted labels with respect to the true labels.



Training Details

    • As a starting point, we recommend using a learning rate of η = 0.005 and a batch size of 100.

    • The model contains a total of 30730 trainable parameters: 30720 weight terms and 10 bias terms. All parameter values should be initialized as 0.
    • 
Hyperparameter Tuning

    • You can try to improve your model’s accuracy by tuning the model’s hyperparameters (e.g., learning rate, batch size). However, it is not appropriate to access the test set until the final model evaluation. Instead, the common practice is to hold out part of the training set to use as a validation set for hyperparameter tuning. By tuning only on the validation set, we can estimate the model’s generalization ability to the testing set (w.r.t. different hyperparameter configurations) without accessing the test data. The pseudocode below shows one possible high-level procedure for tuning the hyperparameters:



Algorithm 2 Hyperparameter Tuning


Require: training set Dtrain = {(⃗xi, yi)}Ni=1train , number of classes M, for several iterations do
Partition Dtrain into distinct sets Dtrain’ + Dval
Initialize hyperparameters: batch size (B) and learning rate (η).

Perform Algorithm 1 (Dtrain’, Dval, M, B, η) to find validation set accuracy for (B, η). end for

return hyperparameters B, η that provided the highest validation set accuracy.



    • You may update your models to use the hyperparameters that you found in your hy-perparameter search. Remember that your submission should use the original training and testing sets in its main() function. Therefore, you are encouraged to make a separate function to perform a hyperparameter search.


Output

    • After training for one epoch (i.e., pass over all training examples)

    • Please output the test accuracy as a percentage (i.e., between 0 and 1), in the .4f format (e.g., .3032). If the accuracy value is stored in a variable called acc, then you can print the accuracy by doing print(f"{acc:.4f}").

    • Before you submit your script, remember to change your filename from exam.py to YourUSCID.py.

    • Make sure your script does not download the dataset during execution.


Evaluation

We will grade your coding exam using automated tests, based on the following criteria:

    • Your script’s functionality (e.g., whether the script is runnable, functions working as expected).
CSCI 566: Deep Learning and its Applications - Spring 2022

Take-Home Coding Entrance Exam    Page 6 of 7


    • Your script’s adherence to the exam instructions (e.g., correctly formatted out-puts, correct filename).

    • Your script’s runtime. If your script your takes more than five minutes to iterate over the training set, then it will not be graded.

    • Your model’s test accuracy. We recommend that you monitor how the accuracy changes across batches, since it should increase over time.