CS 412: Spring’21 Introduction To Data Mining
Take-Home Final
(Due Saturday, May 8, 10:00 am)
General Instructions
• You will have to answer the questions yourself, you cannot consult with other students in
class. I
...
CS 412: Spring’21 Introduction To Data Mining
Take-Home Final
(Due Saturday, May 8, 10:00 am)
General Instructions
• You will have to answer the questions yourself, you cannot consult with other students in
class. It is an open book exam, so you can use the textbook and the material shared in class,
e.g., slides, lectures, etc.
• The take-home final will be due at 10 am, Saturday, May 8. We will be using gradescope for
the submissions. Please submit your answers via gradescope, and please contact the TAs if
you are having technical difficulties in submitting the assignment. We will NOT accept late
submissions.
• Your answers should be typeset and submitted as a pdf. You cannot submit a hand-written
and scanned version of your answers.
• You DO NOT have to submit code for any of the questions.
• For the questions, you will not get full credit if you only give out a final result. Please show
the necessary details, calculation steps, and explanations as appropriate.
• If you have clarification questions, you can use slack or campuswire. However, since the
midterm needs to be submitted within 24 hours, please try to do your best in answering the
questions based on your own understanding, in case responses are delayed.
1
1. (25 points) Consider the following dataset for 2-class classification (Figure 1), where the blue points belong to one class and the orange points belong to another class. Each data point has two features x = (x1; x2). We will consider learning support vector machine (SVM) classifiers on the dataset.
Figure 1: 2-class classification dataset.
(a) (7 points) Can we train a hard margin linear SVM on the dataset? Clearly explain your
answer.
(b) (8 points) Can we train a soft margin linear SVM on the dataset? If yes, briefly describe
how you will do it. If no, briefly explain why not.
(c) (10 points) Professor Quadratic Kernel claims that mapping each feature vector xi = (xi 1; xi 2) to a 6-dimensional space given by
φ(xi) = [1 xi 1 xi 2 xi 1xi 2 (xi 1)2 (xi 2)2]T
and training a linear SVM in that mapped space would give a highly accurate predictor. Do you agree with Professor Kernel’s claim? Clearly explain your answer.
2. (25 points) We consider comparing the performance of two classification algorithms A1 and B1
based on k-fold cross-validation. The comparison will be based on a t-test to assess statistical
significance with significance level α = 5%.1
(a) (5 points) We will assess the results for k = 10-fold cross-validation. What should be
the degrees of freedom for the test? Briefly explain your answer.
(b) (10 points) The accuracies for k = 10-fold cross-validation from algorithms A1 and B1
are given in Table 1.
Is the performance of one of the algorithms significantly different than the other based a t-test at significance level α = 5%? Clearly explain your answer by showing details of (a) the computation of the t-statistic, and (b) the computation of the p-value.
1The relevant material for testing statistical significance is discussed in Chapter 7 of the text book. We will assume that the conditions needed for the validity of the test are satisfied.
2
1 2 3 4 5 6 7 8 9 10
A1 B1 0.908 0.449 0.962 0.585 0.878 0.381 0.956 0.433 0.939 0.475 0.955 0.430 0.944 0.520 0.933 0.590 0.881 0.565 0.9490.443
Table 1: Accuracies on 10-folds for Algorithms A1 and B1.
Given the t-statistic t stat and degrees of freedom df, you should be able to compute the p-value using the following:2
from scipy.stats import t
p val = (1-t.cdf(abs(t stat), df)) * 2
(c) (10 points) Suppose we have a better version of algorithm B1 called B2. The accuracies
for k = 10-fold cross-validation from algorithms A1 and B2 are given in Table 2.
1 2 3 4 5 6 7 8 9 10
A1 B2 0.908 0.968 0.962 1.000 0.878 0.950 0.956 0.994 0.939 0.989 0.955 0.989 0.944 1.000 0.933 0.994 0.881 0.966 0.9490.966
Table 2: Accuracies on 10-folds for Algorithms A1 and B2.
Is one of the algorithms significantly better than the other based a t-test at significance level α = 5%? Clearly explain your answer by showing details of (a) computation of the t-statistic, and (b) computation of the p-value.
3. (25 points) Let Z = f(x1; y1); : : : ; (xn; yn)g; xi 2 Rd; yi 2 f0; 1g; i = 1; : : : ; n be a set of n
training samples. The input xi; i = 1; : : : ; n are d-dimensional features, and xi j denotes the
j-th feature of the i-th data point xi. The output yi 2 f0; 1g; i = 1; : : : ; n; are the class labels. We consider training a single layer perceptron where for any input xi, the output is given by
y^i = g(ai) = g(wT xi) = g 0 @Xj=1 d wjxi j1 A ;
where g(a) = max(a; 0), i.e., the ReLU transfer function, and ai = wT xi is the input activation. Note that the parameters w = [w1 · · · wd]T are the unknown parameters of the model. Consider a learning algorithm which focuses on minimizing squared loss between the true and predicted outputs:
L(wjZ) = 1
2
nX i =1
(yi - y^i)2 = 1
2
nX i =1
(yi - g(wT xi))2 :
2Alternatively, you can look a table for p-values for t-statistic, similar to how you had done it for the χ2-statistic earlier in the semester.
[Show More]
