5/5 - (1 vote)

Problem 2 Classification

For this assignment you are asked to implement both binary and multiclass classification using gradient descent to update weight and bias in each iteration. PLEASE EDIT bm_classify.py ONLY. Any other changes that cause system issues may lead to 0 point in this part.

Q2.1 Binary Classification Perceptron vs. Logistic

In our lecture we have been discussing how to do binary classification using different loss. Now it is your time to implement perceptron loss and logistic loss for binary classification. In this problem you are given training set $D = {{(x_{n}, y_{n})}_{N}^{n = 1}}, y_{i} \in {0, 1} \forall i = 1… N .$ Please note that the labels are not +1 or -1 as we discussed in lectures, so think carefully before you apply formula to this question. Your task is to learn a model $w^{T} x + b$ that minimize the given loss. Please find the gradients of the two loss functions by yourself and apply average gradient descent to update $w, b$ in each iteration. For perceptron loss we define $Z = y_{n} (w^{T} x_{n} + b) > 0$ as correctly classified data.

(8 points) TODO 1 For perceptron loss that is find the minimizer of
(8 points) TODO 2 For logistic loss that is find the minimizer of
(4 points) TODO 3 Also you will find out it is convenient to use sigmoid fuction $σ (z) = (1 + e^{- z})^{- 1}$ for logistic loss, so please complete it. You can use this function in TODO 2.
(4 points for each)TODO 4 TODO 5 After you learn the models, how do you know it is good enough? The intuitive way is to make some predictions to see if those predicted results are correct or not. Here we want you complete the prediction functions. It will be like something greater than 0 and something put into sigmoid function greater than 0.5. You may find out an interesting fact here.

After you finish the 5 TODOs above in bm_classify.py, you can run binary.sh to test it. If your code is programmed correctly, you should see binary.out as an output file keeping taining and testing accurancies of two loss functions for three datasets. You will see how similar between perceptron loss and logistic loss. Quite interesting isnt it? Can you figure out why this happends? We will leave this open question to you.

Two of the datasets you are going to do binary classification:

Synthetic data:
Two Moon data:

Q2.2 Multiclass classification SGD vs. GD

Well done! Ready to take our next challenge? Lets get into multiclass classification. In this question you are going to build a model to classify data into more than just two classes. Also you are going to implement both $S G D$ and $G D$ for multiclass classification and compare performances of the two approaches. Training dataset are similar to question Q2.1, but $y_{i} \in {0, 1, . . ., C - 1} \forall i = 1… N .$ Your task is to learn models for multiclass classification based on minimizing logistic loss.

Here is a short review of $S G D$ .

From the lecture we know multiclass logistic loss is

Here, $w_{k}$ is the weight vector for class $k$ and $w_{y_{n}}$ is the weight vector for class $y_{n}$ . $k$ is in range [0, C-1]. Now we try to apply $S G D$ . First we randomly pick a data $x_{n}$ and minimize logistic loss

And then find the derivative $▽_{w} g (W)$ , where $▽_{w} g (W)$ is a $C$ x $D$ matrix.

Lets look at each row k.

If $k \neq y_{n}$ :

else:

where $P$ is softmax function.

In the end, our update for $W$ is

That is the whole idea of $S G D$ of logistic loss for multiclass classification.

(8 points) TODO 6 Complete the $S G D$ part in def multiclass_train, and dont forget the bias $b$ . To randomly pick a data from dataset, you can use np.random.choice one time in each iteration.
(16 points) TODO 7 Complete the $G D$ part in def multiclass_train. Compare to $S G D$ , $G D$ does not randomly pick a data $x_{n}$ . Instead, $G D$ considers all training data points to compute derivative. Please think about how to compute $G D$ , and again we want average gradient descent. Also there is a tricky point. When dataset is large, $G D$ will takes a large amount of time. How to reduce the time? Make sure you use numpy programming instead of nested for loops, otherwise you will not finish your test on Vocareum within the time limit.

Hint 1: If you need to run a for loop for $N$ times to accumulate $C$ x $D$ matrices, why not design an equivalent computation as a $C$ x $N$ matrix dot another $N x D$ matrix.

Hint 2: You may find it useful to use a special (one-hot) representation of the labels, where each label $y_{i}$ is represented as a row of zeros with a single 1 in the column, that corresponds to the class $y_{i}$ . So this one-hot should be an $N$ x $C$ matrix.

Advice: To avoid numerical issues such as overflow and underflow caused by np.exp. Let $x$ be a input vector to the softmax function. Use $\tilde{x} = x - m a x (x)$ instead of using $x$ directly for the softmax function $x$ . That is, if you want to compute $f (x)_{i}$ , compute $f (\tilde{x})_{i} = \frac{e x p ({\tilde{x}}_{i})}{\sum_{j = 1}^{D} e x p ({\tilde{x}}_{j})}$ instead, which is clearly mathematically equivalent but numerically more stable.

(8 points) TODO 8 You need to complete the predict function in def multiclass_predict.

After you complete TODO 6 TODO 7 TODO 8, please run multiclass.sh to test your code. If your code is programmed correctly, you should see multiclass.out as a output file keeping processing time, taining and testing accurancies of $S G D$ and $G D$ for each given dataset. You shall see how fast $S G D$ process compared to $G D$ , but its accuracy is hard to catch up with the others. One more open question to leave you. Is there any chance that $S G D$ reach to the same accuracy as $G D$ does using less time?

That is all for this assignment.

Scatter plot of a sample toy dataset for multicalss classification:

5/5 – (1 vote)

$F (w, b) = \sum_{n = 1}^{N} L_{p e r c e p t r o n} (y_{n} (w^{T} x_{n} + b)) = \sum_{n = 1}^{N} M A X (0, - y_{n} (w^{T} x_{n} + b))$

$F (w, b) = \sum_{n = 1}^{N} L_{l o g i s t i c} (y_{n} (w^{T} x_{n} + b)) = \sum_{n = 1}^{N} l n (1 + e^{- y_{n} (w^{T} x_{n} + b)})$

$F (W) = \sum_{n = 1}^{N} l n (1 + \sum_{k \neq y_{n}} e^{{(w_{k} - w_{y_{n}})}^{T} x_{n}}) .$

$g (W) = l n (1 + \sum_{k \neq y_{n}} e^{{(w_{k} - w_{y_{n}})}^{T} x_{n}}) .$

$▽_{w_{k}} g (W) = \frac{e^{{(w_{k} - w_{y_{n}})}^{T} x_{n}}}{1 + \sum_{k^{'} \neq y_{n}} e^{{(w_{k^{'}} - w_{y_{n}})}^{T} x_{n}}} x_{n}^{T} = P (k | x_{n}; W) x_{n}^{T}$

$▽_{w_{k}} g (W) = \frac{- \sum_{k^{'} \neq y_{n}} e^{{(w_{k^{'}} - w_{y_{n}})}^{T} x_{n}}}{1 + \sum_{k^{'} \neq y_{n}} e^{{(w_{k^{'}} - w_{y_{n}})}^{T} x_{n}}} x_{n}^{T} = (P (y_{n} | x_{n}; W) - 1) x_{n}^{T}$

Reviews

There are no reviews yet.

Only logged in customers who have purchased this product may leave a review.

Whatsapp Us

[Solved] CSCI567 Homework2-Classification

Problem 2 Classification

Q2.1 Binary Classification Perceptron vs. Logistic

Q2.2 Multiclass classification SGD vs. GD

Reviews

Whatsapp Us

[Solved] CSCI567 Homework2-Classification

Problem 2 Classification

Q2.1 Binary Classification Perceptron vs. Logistic

Q2.2 Multiclass classification SGD vs. GD

Reviews

Related products

[Solved] CSCI567 Project 4 Part1-Hidden Markov Models

[Solved] CSCI567 Homework 5- Hidden Markov Models

[Solved] CSCI567 Homework2-Regression

[Solved] CSCI567 Homework3-Neural Networks

[Solved] CSCI567 Project 4 Part2- K-means

[Solved] CSCI567 Homework 2-Neural networks