Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit


CSCC11 Introduction to Machine Learning, Winter 2021

Assignment 2

This assignment makes use of material from week 3 to week 5 (specificallyChapter 9.6). To begin the program- ming component, download a2.zip from the course website and untar it. A directory A2 will be created; please don’t change its structure, nor the headers of the python methods therein. Please read the assignment handout carefully. Submission instructions are at the end.

We prefer you ask questions on Piazza. Otherwise, for your first   point of contact, please reach out to your TA, Mohammadreza (Reza) Moravej, through email: [email protected].

 

Written Component

1) Understanding Binary Class Logistic Regression

In this question, we investigate the assumptions and limitations of the binary class logistic regression model. Suppose we have two classes with labels c1 and c2, we can express the posterior probability of class c1 given input x as

 

P(c1 |x) =                   = g(wTx),                                                     (1)

 

where w is the weight vector with bias included and g is the Sigmoid function.

Written Problems.

1. First, let’s investigate the decision boundary of a binary class logistic regression model.  Recall that the decision boundary is the set of points where P(c1 |x) = 0.5 (i.e. when the decision function α(x) = 0). Show that when P(c1 |x) = 0.5, the decision boundary α(x) = 0 is a linear function.

2. Knowing that logistic regression has a linear decision boundary, what datasets would this model perform poorly on?  In this case, performing poorly means the model is unable to classify all the training data correct. Let’s look at a toy example – the XOR (Exclusive OR) dataset. XOR is a binary input Boolean function that outputs TRUE when both inputs are the same and outputs FALSE otherwise. The dataset is represented as the table below.  Our goal is to predict the output y  ∈ {0, 1} given the input vector x = [x1,x2]T, where x1,x2 ∈ {0, 1}.

x

1

2

y

0

0

0

0

1

1

0

1

1

1

1

0

(a) Assume we are using binary class logistic regression on the XOR dataset.  What is the maximum

classification accuracy we can obtain? Explain.

(b) As in basis function regression, we can apply basis functions to create a more sophisticated model.

Consider the following feature map (basis functions) on the inputs:

ψ(x) =          x1  

Then, we can express the posterior probability of class c1 given input x as P(c1 |x) = g(wTψ(x)), where w = [w1,w2,w3]T is the weight vector of the model. Note that we exclude the bias term in this question. Specify the conditions and provide an example for the weight vector w such that this model perfectly classifies the XOR dataset.

2) Multiclass Logistic Regression

In this question we will consider multi-class logistic regression. We will begin by extending the formulation of 2-class logistic regression to the multi-class case. For background, seeChapter 9.6 of the online lecture notes.

We will denote input feature vectors by x, and let’s assume the first element of x is 1 to allow for a bias term; i.e., x = (1,x1,...,xd)T. For now, suppose there are 2 classes, with class labels 1 and 2. And let c denote the class variable. In these terms, the conditional probability of class 1, given the data, is simply

 

p(c = 1 |x)  =                                                                                                      (3)

 

For the purposes of logistic regression, we define a mapping from an input feature vector to what we might call unnormalized probabilities as follows:

ewk(T)x   =  α p(c = k) p(x|c = k) .

for some unknown constant α, where k is either 1 or 2 in our 2-class case.  Such unnormalized probabilities are just an exponentiated linear functions of the inputs (with the addition of the bias term which is the first element of the weight vector). We call them unnormalized because we don’t know the value of α, and hence the exponentiated inner products ewk(T)x don’t sum to one like a probability distribution should.

For two classes the model is specified by two weight vectors, w1 and w2. And according to the model, Eqn. (3) can be rewritten as follows

ewx                                   1           

ewx  + ewx          1 + e(w2 −w1)Tx  .

This is immediately recognizable as the sigmoidal function g(·) from Eqn. (39) in Chapter 9.6 of the online lecture notes, but here it is applied to (w1  − w2)Tx instead of wTx.  In other words, in the online notes on 2-class logistic regression, the weights we learned were equal to the difference of the weights used here, i.e., w1 − w2, which defines the normal vector to the decision boundary (w1 − w2)Tx = 0.

Now we’re ready to look at the more general case with K classes.  Assume again that inputs are x  = (1,x1,...,xd)T. And for each of K classes, let there be a weight vector, wk = (bk,wk,1,...,wk,d)T. Assuming c denotes the class variable, we can write the probability for class c = k, where 1 ≤ k ≤ K, as

p(c = k |x)  =                                                                                         (4)

 

As above, the logistic regression model defines a parametric mapping from inputs to unnormalized probabilities. Given the model parameters, w1:K, the model specifies that

p(c = k |xw1:K)   =

 

=

 

ewk(T)x

P ewx

1

1 +P∈{1,...K}\k e(w wk)Tx  .


(5)

 

(6)


The sum in the denominator in Eqn. (6), ℓ takes on all values between 1 and K, except k. Note that while Eqn. (6) more closely resembles the sigmoidal function in 2-class logistic regression, it will be more convenient to use


Eqn. (5) in what follows. The function in Eqn. (5), which maps K score values (i.e., the inner products wk(T)x) to probabilities, is used often in deep learning; in neural network jargon it is called a softmaxfunction.

Now let’s consider the objective for learning. As with 2-class logistic regression we are going to use a log loss. Given training data {(xi,yi)}, assumed to be IID, we form the loss under the model as

N

E(w1:K)  =  − log Yp(yi|xi , w1:K) .

i=1

In the lectures and notes on the 2-class case we manipulated the form of the log probability of the model in terms of the sigmoid function with the class labels being either 0 or 1. We can do the same thing here but it’s just a little trickier. Rather than assume that yi takes on a value from 1 to K, instead we let yi be a so-called one-hot binary vector. That is, we define yi to be a vector of length K whose elements are 0 or 1. When the correct class

for the ith data point is k, then all elements of yi are 0 except for the kth; i.e.,

yi,k     =   

With this one-hot label encoding we can express the negative log likelihood of the training data as follows:

N    K

E(w1:K)   =   − log Y Y p(yi,k|xi , w1:K)yi,k

i=1 k=1

N    K

=   − XX yi,k  log p(yi,k|xi , w1:K)

i=1 k=1

Next we need to derive the form of the gradients of E so we can figure out the necessary conditions for the optimal values of the parameters w1:K. To this end, just as we defined the sigmoid function for 2-class logistic regression, here we use a similar notation to define the softmax function: i.e.,

 

σ(z1:K , k)  =                                                                              (7)

 

With this notation, and defining zi,k = wk(T)xi, for k = 1...K, we can express the loss as

N    K

E(w1:K)  =  − XX yi,klog σ(zi,1:K , k) .                                              (8)

i=1 k=1

We will solve the learning problem by minimizing E using gradient descent to find the weight vectors. But we still need to find the gradient first.

 


Written Problems.

1. Find the gradient of σ(z1:K ,k) in Eqn. (7) with respect to zj:

∂σ(z1:K , k)

∂zj         .

 

(9)


Hint: Consider the cases when k = j and k  j. You may find it helpful to look at the structure of the

gradient in the 2-class case in Eqn. (46) inChapter 9.6 of the online lecture notes.

2. Find the gradient of the log likelihood for a single point (x,y) with respect to wj:

    X yklog σ(z1:K , k)                                                     (10)

k=1


 


3. Find the gradient of the loss with respect to wj:

∂E(w1:K)

wj       .


(11)


Hint: Use the results above. And the gradient should have a form similar to Eqn. (48) in Chapter 9.6 of the online lecture notes.

4. Now, suppose we have D dimensional inputs and K classes. For each of K classes, let there be a weight vector, wk   =  (bk,wk,1,...,wk,d)T.  If we include regularization, with a (diagonal) Gaussian prior, the negative log-posterior becomes, up to an additive constant,

Eˆ(w1:K)  =  − log "p(w1:K) p(y = yi|xi , w1:K)# ,                               (12)

where p(w1:K) is the joint distribution over K indepdendent Gaussian densities with the same diagonal covariance. That is,

p(w1:K)  =   K       exp   −   .                         (13)

where the covariance matrix is given by C = diag(β,α,α,...,α) ∈ R(D+1)×(D+1). Here, α denotes the variance of the prior on each of the weights, and β is the prior variance on the bias term. Usually we don’t want a strong prior on the bias term so β ≫ α. Derive  for this regularized objective function.            Hint: Your negative log-posterior should have form Eˆ(w1:K) = E(w1:K) + E2(w1:K), where E2(w1:K) is the regularization term.

Programming Component

You are asked to implement a logistic regression classification algorithm (we provide gradient descent code). The starter code is in directory A2. You will then apply this algorithm on four datasets, each comprises a training set and a test set. You should train your algorithm on the training data, then evaluate performance on the test set. The test performance should be measured as the average 0-1 test loss; i.e., once you’ve fit a model to the training data, evaluate it by counting the number of correctly labelled test points and dividing the count by the size of the test set.

Datasets: In the starter file there is a datasets directory. In that directory there are several pickle files for the different datasets, as described below.

• Generic datasets: There are three generic datasets, generic_<i>.pkl where <i>  =  {1,  2,  3}, all of which have the same format. Given 2D, real-valued measurements (features), we want to classify whether a test point is class 0 or class 1 for the first two datasets, and class 0, class 1, or class 2 for the third dataset. Each pickle file contains four arrays, train_X, train_y, test_X, and test_y. The arrays train_X ∈ R100×2 and train_y ∈ R100×1 form 100 input/output pairs of the training set. The arrays test_X ∈ R50×2 and test_y ∈ R50×1 form 50 input/output pairs of the test set.

• Iris dataset: The iris dataset, iris.pkl, has four attributes: sepal length, sepal width, petal length, and petal width, measured in cm (i.e. 4D measurements/features). Given the 4D measurements, we want to classify whether the iris class is iris setosa, iris versicolour, or iris virginica (i.e.  3 classes).  The file contains four arrays, train_X, train_y, test_X, and test_y. The arrays train_X ∈ R120×4 and train_y ∈ R120×1 form 120 input/output pairs of the training set. The arrays test_X ∈ R30×4 and test_y ∈ R30×1 form 30 input/output pairs of the test set.

 

Visualizing the Generic Datasets:   You need to modify visualize_generic.py to visualize the three generic datasets. Once you have visualized the datasets (NOTE: You do not need to submit the generated plots), answer the following questions under Visualization in Questions.txt.

1. Do you expect logistic regression to perform well on generic_1? Why? What if we apply the feature map defined in Eqn. 2?

2. Do you expect logistic regression to perform well on generic_2? Why? What if we apply the feature map defined in Eqn. 2?

3. Do you expect logistic regression to perform well on generic_3? Why?

4. Why can’t we directly visualize the iris dataset? What are some ways to visualize it?

Implementing Logistic Regression: You should implement the multi-class logistic regression with regularization explained in the written component and Chapter 9.6 of the online lecture notes. The gradient for the model is derived in the written component above. You only need to modify the file logistic_regression.py. You might find utils.py to be helpful for your implementation. The relevant methods are

• _compute_loss_and_gradient computes the negative log likelihood and its gradient given the in- puts and outputs. It is essential for learning the logistic regression model parameters. When the hyper- parameters α − 1  and β − 1  are non-zero, we compute the negative log posterior instead.  IMPORTANT NOTE: For numerical stability, divide the negative log likelihood by the number of data points, drop all log constants, and drop all constant factors. Your loss should be in the form Eˆ avg(w) =  + E2(w), where N is the number of data points. Then, compute the gradient based on Eˆavg .

•  learn is a template for a gradient descent method, with line search, for minimizing the negative log like- lihood of the data. It uses _compute_loss_and_gradient extensively, and it provides a facility to check your gradients numerically. Specifically, by setting the check_grad flag, it computes the numer- ical gradient using finite difference. It uses your implementation of negative log likelihood and negative log posterior for the computation.

• predict evaluates the logistic regression model given an array of exemplars and the weight parameters. It computes the posterior class probability given the data and model parameters.  This function is used mainly for classification.

Training Logistic Regression and Evaluating Performance:  To train and evaluate the classifier, you will learn models with different parameter settings, and compute the test errors for them on different datasets. The Python file train_logistic_regression.py allows you to train and evaluate a model given a dataset, random seed, hyperparameters, and initial parameters for training. You will need to implement the train function and the feature_map in train_logistic_regression.py. Specifically, you will need to implement the code to initialize logistic regression model, initialize its parameters, train the model, and evaluate the training and test performance with and without the feature map defined in Eqn. 2. Note that only the generic datasets can be used with the feature map since it is meant for 2D inputs.  To apply feature map on the inputs, set

apply_data_preprocessing  =  True.

Finally, run logistic regression using train_logistic_regression.py and answer the following questions under Analysis in Questions.txt:

1. First, we have an experiment on generic_1 dataset. Run logistic regression without regularization and without feature map. Did you run into any numerical errors? If so, why do you think this is the case? Now, run logistic regression with regularization. What happens? What are the train and test accuracies?


2. Now, let’s look at generic_2 dataset. Run logistic regression without regularization and without feature map. What are the train and test accuracies? Run it with feature map now, did the performance get better? Why do you think that is the case?

3.  generic_3 is a multi-class classification problem.  Run logistic regression without regularization and without feature map. What are the train and test accuracies? What if we run it with feature map?

4. Iris dataset: Does logistic regression without regularization and without feature map perform well on this dataset? If not, does regularization help?

5. How accurate are the predictions made by the model on training and test data for the iris problem, and do they appear reasonable? Explain your answer.

 

Submission

You will need to submit two files, one for each component.  The specifications of the file format and naming convention are specified below.

1. Written Component

You may hand write or type up (e.g. Word, LateX, etc.) the solutions. We strongly recommend typing it up     for legibility. Compile the document as a PDF named A2sol studentUTORID.pdf (e.g. A2sol student1.pdf). Then you should submit the PDF file onto Quercus.

2. Programming Component

Compress the A2 directory into a tar file named A2sol UTORID.tgz (e.g., A2sol student1.tgz).

Please don’t modify the method/function headers or the structure of the A2 directory tree since the automarker will fail to run. Failing to follow the instructions will result in a 25% penalty.

To tar and zip the contents, use the command:  tar  -cvzf  name of tar.tgz  A2.  Make sure to decompress the tar file to ensure the entire A2 directory is there. Then you should submit the tar file onto Quercus.