Instructions

1. Please submit your assignment on Gradescope. The instructions for this will be coming soon. There are two components to this assignment:  mathematical solutions/proofs with English explanations (Part I). For the programming assignment portion of the homework (Part II), you will be writing a report in a conference paper format for this assignment, reporting your findings. All parts of the assignments must be typeset, including figures. You must use NeurIPS format for your report (link below). We strongly recommend that you use some dialect of TEXor LATEX. You may also use Word if you so choose.  The link below has both LATEXand Word NeurIPS formats. Figures may be generated with Excel or Python, so long as they are computer generated. We will  not be accepting any  handwritten work - this  includes the “written part.”   NeurIPS templates in LATEXand Word are available from the 2015 NeurIPS format site.  The page limits mentioned there don’t apply.

2. For the group report, include an informative title  (informative  means it is not  "CSE  151b  PA1", but something that says what you did, like handwritten text recognition with logistic regression or some such), author list, and an abstract.  The abstract should summarize briefly what you did, and the best percent correct you got on each problem.  The report should be well-organized with an introduction, background (if you review previous work), methods, results, and discussion for each programming part.  Figures should be near where they are referenced, there should be informative captions on figures, clearly specified axes and figure keys, etc. A details of what to include in the the report along with rubric can be found at the end of the document.

3. You are expected to use Python (usually with NumPy). You also need to submit all of the source code files and a readme.md file that includes detailed instructions on how to run your code.

You should write clean code with consistent format, as well as explanatory comments, as this code may be reused in the future.

4. Using any off-the-shelf code is strictly prohibited.

5.  If you end up  dropping the  class  and your teammate  does not, you are  expected to help your teammate anyway!  Please don’t leave your teammate(s) without your assistance. Being on a team means just that: teamwork! When you join a team, you have made a commitment. Please honor it.

6. Any form of copying, plagiarizing, grabbing code from the web, having someone else write your code for you, etc., is cheating. We expect you all to do your own work, and when you are on a team, to pull your weight. Team members who do not contribute will not receive the same scores as those who do. Discussions of course

materials and homework solutions are encouraged, but you should write the final solutions alone.  Books, notes, and Internet resources can be consulted, but not copied from.  Working together on homework must follow the spirit of the Gilligan’s Island Rule (Dymond, 1986):  No notes can be made (or recording of any kind) during a discussion, and you must watch one hour of Gilligan’s Island or something equally insipid before writing anything down.  Suspected cheating has been and will be reported to the UCSD Academic Integrity office.

Part I

Problems to be solved and turned in individually

For this part we will not be accepting handwritten reports.  Please use latex or word for your report.  MathType is a handy tool for equations in Word.  The free version (MathType Lite) has everything you need.  [N.B.:  This advice may be out of date; I’ve had some trouble trying to download MathType for word...-gwc.]

1. Perceptrons (12 points)

Recall the perceptron activation rule:

y     (

if Pi(d)=0 wixi  ⩾ 0

else

Here, we have written it so that w0  is the bias (the opposite of the threshold), and so x0 = 1.

(a)  (2 pts) Assuming d = 2, derive the equation for the line that is the decision boundary (the solid black line in Figure 1).  Write it in slope-intercept form, i.e., y(x) = mx + b, where m and b are written in terms of the weights.

(b)  (3 pts) Prove that the distance from the decision boundary to the origin (as shown in Figure 1) is given by:

l =

∥w∥

Figure 1: In part (b), you need to prove the length of the dashed line is what is shown here.  You have to assume that the weight vector is in the first quadrant, as shown.

In class, we showed how to learn the “OR” function using the perceptron learning rule. Now we want to learn the “NAND” function using four patterns, as shown in Table 1.

Table 1: The “NAND” function

(c)  (1 pt) Write down the perceptron learning rule as an update equation.

(d)  (4pts) Draw the rest of this table, as we did in class, as the network learns NAND. Initialize w0 , w1 , and w2 to be 0 and fix the learning rate to 1. Add one row for each randomly selected pattern (training example) for the perceptron to learn.  Stop when the learning converges. Make sure you show the final learned weights and bias.  You may pick a “random” order to make the learning converge faster, if you can (you may not need all of these rows).

(e)  (2 pts) Is the solution unique? Why or why not? Justify your answer.

2. Logistic Regression (5 points)

Logistic regression is a binary classification method.  Intuitively, logistic regression can be conceptualized as a single neuron reading in a d-dimensional input vector x ∈ Rd  and producing an output y between 0 and 1 that is the system’s estimate of the conditional probability that the input is in the target category, given the input. The “neuron” is parameterized by a weight vector w ∈ Rd+1, where w0  represents the bias term (a weight from a unit that has a constant value of 1).

Consider the following model parameterized by the vector w:

y = P(C1 |x) = = g(w⊤x)                                                (1)

P(C0 |x) = 1 − P(C1 |x) = 1 − y,                                                         (2)

where we assume that x has been augmented by a leading 1 to represent the bias input. With the model so defined, we now define the Cross-Entropy cost function, equation 3, the quantity we want to minimize over

our training examples:

N

E(w) = − X {tn ln(yn) + (1 − tn)ln(1 − yn)} .                                           (3)

n=1

Here, tn  ∈ {0, 1} is the label or teaching signal for example n (tn  = 1 represents xn  ∈ C1). We minimize this cost function via gradient descent.

To do so, we need to derive the gradient of the cost function with respect to the parameters wj.  Assuming we use the logistic activation function g as in equation 1, prove that this gradient is:

− ∂E(w) = X(tn − yn)xj(n)                                                                                    (4)

Part II

Programming Assignment

Requirements: Write your own Logistic Regression and Softmax Regression classifiers using Python, following the instructions below. This assignment can be done using only two libraries: Numpy, and Matplotlib. Of course, you are allowed to use any other libraries on top of these (like os, random, other visualization libraries, etc.). However, you  are not allowed to use any SciPy implementations of logistic or softmax regression, or any other packages from machine learning libraries including, but not limited to: TensorFlow, PyTorch, Keras, Pandas, scikit-learn, etc. This list is not exhaustive but given as examples. For this assignment, we request you to solely rely on Numpy to manipulate data (after getting the dataset as instructed in the assignment).  This will give much better clarity of what you are doing in terms of vectors and matrices. For this assignment, a “team” is defined as two or three people.

1    Starter code

Starter code is hosted on GitHub, as well as provided as a zip file.  Both versions of the code are the same - feel free to pick whichever way is easiest for you.

1.1    GitHub Classroom

The link to our GitHub Classroom assignment is https://classroom.github.com/a/RNuJtP4n.  Following that link will lead to a button that says "Accept this assignment." Accepting this assignment will set up a Git repo with the starter code. You should have admin permissions on this repo, so you can share it with your teammates.  Only one person per team should accept the assignment and then share the repository with the whole team by adding them as collaborators. On GitHub, this can be done under Settings -> Manage Access -> Add people.

1.2    Zip file

If the GitHub Classroom assignment does not work for you, you can use the zip file provided on Piazza under resources. Unzip this file and set up a new Git repository in the created folder. Only one person per team should do this setup, and the new repository should be shared with the whole team.

2    Dataset

For the first assignment, we will use logistic regression/softmax classifier to detect different classes of Hiragana character set (Hirgana is a part of the Japanese writing system). The dataset we are using is called KMNIST. The detailed description of the dataset can be found here:

https://github.com/rois-codh/kmnist.

You can use the script get_data.sh to download the data. If your system does not support bash scripts, you’ll need to do the following.

1. Create directories data/train and data/test

2. Download the file located at http://codh.rois.ac.jp/kmnist/dataset/kmnist/kmnist-train-imgs.npz. Save it to data/train/images.npz.

3. Download the file located at http://codh.rois.ac.jp/kmnist/dataset/kmnist/kmnist-train-labels. npz. Save it to data/train/labels.npz.

4. Download the file located at http://codh.rois.ac.jp/kmnist/dataset/kmnist/kmnist-test-imgs.npz. Save it to data/test/images.npz.

5. Download the file located athttp://codh.rois.ac.jp/kmnist/dataset/kmnist/kmnist-test-labels.npz. Save it to data/test/labels.npz.

To load training and testing data, you can use the given function load_data in data.py.  You can use the train parameter to determine if you’re loading training or testing data.  We’ll use training data for training and validation, and testing data for testing.

You should not use testing data to tune your hyperparameters!

As a first step, we will have to normalize the dataset (both X_train and X_test), and then one hot encode the labels (both y_train and y_test).  It is also a good idea to shuffle the dataset before using.  This should be implemented in the data.py file - there are function stubs provided for you.  You are free to add any parameters you need to these functions. Implement both min-max normalization and z-score normalization.

3    Cross Validation Procedure

We will need a validation dataset to estimate a model’s performance on unseen data (without using test data), to tune its hyperparameters (e.g. learning rate, batch size, etc.)  and to prevent overfitting. We will use the method of k-fold cross-validation to separate a portion from training data as validation.

For each problem below, you should divide the train data (X_train) into k mutually exclusive sets.  Each set should contain a representative sample with respect to the problem.  Basically, you want to have roughly equal amounts of each category in each of the k sets (a trivial way to do is to shuffle the dataset before splitting). Don’t worry if they don’t divide up perfectly equally; but make sure they are mutually exclusive! For this assignment, we will fix k to 10.

Repeat the following k times:

• Choose a set to be holdout (or validation).   Then, train your model on the remaining k − 1 of the sets. Psuedocode for this is in the Training algorithm below.

• The loss (Equation3 for logistic and7for softmax) on the holdout set should go down as you train the model, even though the examples in the holdout set are not being used to change the weights.  However, at some point, the holdout loss should start to rise. This means the model is overfitting and you should stop training. This is called early stopping.

• It is also possible that the holdout set loss never goes up over the M epochs (one pass through all of the training data is called an epoch). So you should also have some limit on the number of training steps. In our case, we will set M to 100.

• After early stopping or M epochs, record the model’s performance (accuracy) on this holdout set.

After repeating step 1 to 4 for all remaining holdouts, calculate their average accuracy. We will use this average accuracy to determine a best set of hyperparameters. For example, say you get an average accuracy of x% in the 10 validation sets for learning rate of 0.01 and batch size of 512, using 10-fold cross validaiton.  Now, change the hyperparameters (e.g. 0.01 to 0.001 and 512 to 128) and observe if accuracy dropped or increased. If the accuracy increases, store the hyperparameter. In this fashion, try a different combination of hyperparameters and record the one which yields the best average validation accuracy. This process is known as ‘hyperparameter tuning.’

After getting the best model using hyperparameter tuning, we will run the trained model on unseen test set and record the performance. Notice that we have only used the test set once.

4    Logistic Regression

Here, we build and evaluate classifiers on the data. We will experiment with discerning between two classes of data, and with multi-class classification. Now, without using any high-level machine learning libraries, implement logistic regression.  Here, you’ll be using stochastic gradient descent, and will only need one logistic output unit.  (Think about why we only need one if we’re classifying two classes?)

Here we ask you to perform logistic regression on two different sets of classes. The first set contains the images where the output class is 0 or the output class is 6, and the second set will contain the images where the output class is 2 or the output class is 6.  Train a logistic regression model on these two datasets following the training procedure mentioned above. Here, your hyperparameters are learning rate, batch size, and type of normalization. After getting final model, you should have these: losses for all training folds, losses for all validation folds, and test

1:  procedure Training Procedure

2:

3:

4:

5:

6:

7:

8:

9:

10:

11:

12:

folds = k mutex split of training data;

for fold = 1 to k do

val_set ← folds[fold];

train_set ← remaining folds;

Project train_set and val_set onto top p train PC’s

for epoch = 1 to M do

train the model with train_set, and test the performance on val_set every epoch

record train_set, val_set loss for plotting and accuracy on val_set for hyperparameter tuning save the best model based on val_set performance

plot the training and validation loss curves

Project test onto top p train PC’s and use the best model to report accuracy on test