Ground rules

For this assignment, you may use any of our EE 660 course materials, and you may use your computer for coding and accessing the assignment, EE 660 materials, piazza, and D2L.  You may also use the internet for information about Python, Python coding, and Python libraries that you are allowed to use for the problem you are working on (e.g., looking up information for sklearn functions that you might want to use in a problem that allows the sklearn library).

You are not allowed to use the internet to look up answers or partial answers to any of this assignment’s problems, or communicate with other people (e.g., other students, people on discussion forums, etc.) on topics related to this assignment.

For all coding in this assignment, unless stated otherwise in the problem, you are allowed to use built-in Python functions, NumPy, and matplotlib; you can use pandas only for reading/writing csv files.  For Problems 1 and 3 you can also use sklearn.  For Problem 2, you can use pandas more generally.

For questions on this assignment, when posting on piazza, please consider whether this is a question that is appropriate for all students (e.g., clarifying the problem statement, what is  allowed,  suspected typos  or  omissions  in the problem  statement),  or  only  for the instructors (e.g., something that includes your approach or solution) which should be posted as a “private” post that is only visible to the professor, TAs and you.

Please respect your classmates and follow all of these guidelines, so that everyone can be graded fairly.  Any violations that are detected will result in substantial penalties.

Uploading your solutions. Please upload the following files before the final due date and time:

1.    A single pdf file of all your solutions/answers.

2.    Three  computer-readable pdf files  that  include  all  your  code  for  each problem: pr1_code.pdf,  pr2_code.pdf,   and pr3_code.pdf.

Updates:  Any updates or corrections to this assignment will be announced by instructor post on piazza.

Problems and points. This Midterm Assignment has 3 problems, worth a total of 100 points possible, distributed approximately equally among the 3 problems.  There will be partial credit on most problem parts.  Be sure to work all problems parts, up to “End of Midterm Assignment” statement on p. 13.

1. Linear regression, RANSAC, and regression error bounds

[created by Yao Zhu and Keith Jenkins]

In this problem, you are asked to compare Linear regression, Ridge, Lasso and RANSAC. RANSAC (RANdom SAmple Consensus) is a common approach for robust regression. You can refer to [1] and [2] as resources to learn RANSAC.

Please read [1] and [2] carefully to understand what RANSAC is and answer the written problem below:

(a)   [To be solved by hand. Your answers may be handwritten or typed.]

Suppose we set the following parameters for RANSAC.

•    S : number of samples per draw

•    e : probability of a point being an outlier

•    p : desired probability that we get a good draw

• N : number of draws needed to reach the above probability.

i.          What is the probability that all the samples in the draw are inliers?

ii.         What is the probability for a draw to be a bad one? i.e. the draw contains at least one outlier.

iii.        What is the probability that we can get at least one good draw? Report your result in terms of e, S and N . (Hint: this equals to p)

iv.        If S = 8, e = 0.5, what is minimum number of draws we need to have p = 0.99?

Problem  parts  (b)-(f)  are  based  on  the “Bike”  datasets  provided  with  the  Midterm Assignment. They are from a Bike Sharing Dataset [3] in UCI machine learning repository. You can take a look at the website and understand the background and features first. For this assignment, please use the given data files provided with the midterm assignment, in which the training, validation and test set are already split, and the feature set has been reduced.   Training   set   (Bike_train.csv)   contains    10427   samples,   validation   set (Bike_val.csv) contains 4172 samples and test set (Bike_test.csv) contains 2780 samples. There are 7 features ("holiday", "weekday", "workingday", "weathersit", "temp", "hum", "windspeed") and 1 target ("cnt"). All of them are numerical. The 7 features are already

standardized. You don’t need to standardize them.

Please answer the following parts below:

(b)  [By hand; computer use is OK but optional] In this regression problem, it is recommended that you center the y data for all 3 datasets, based on statistics of the training-set data; and for l1 and l2 regression using sklearn.linear_model.Ridge and Lasso, set fit_intercept = ‘false’ .

– Why centery and set fit_intercept parameter as stated?

– Why use statistics of only training-set data to calculate parameters?

Tip: if you’re not sure why, you can proceed to solve the rest of this problem as described above, and then return to answer this “why” question later.

(c)  [Computer] Try linear regression with no regularization, l1  regularization and l2

regularization. You can choose the best regularization coefficient 入 within range

lOg2入 = − 10 to lOg2入 = 10, step size ΔlOg2入 = 1 based on validation set. Report

(d) [Computer] Try RANSAC. You can use sklearn.linear_model.RANSACRegressor. Please try multiple parameters in RANSAC and select the best model with smallest val_MSE. Report the val_MSE of your best model. Compare with results from best models from (c) and discuss the possible reasons behind it.

(e) [By hand] (i)  For each of the 3 best models of (c), give an algebraic expression of its generalization-error bound based on the model’s val_MSE.  Evaluate each

generalization-error bound numerically for 6 = 0.1 .

Hint: You might find Lecture 11 and 13 notes useful.

(ii)   For best model of (d), give an algebraic expression of its generalization-error bound based on the model’s val_MSE. Evaluate the generalization-error bound numerically for 6 = 0.1 .

(iii) Which of these 4 models looks best, based on val_MSE only?  Which of the 4 models have the largest, and smallest, generalization-error bounds?

(f)  [By hand and computer] We are now going to use the test set to compare the final 4 models.  This is not the standard use of a test set, but we can do it if we take into account the generalization-error bounds.

(i)        Compute the test_MSE of each of the 4 models you evaluated in (e) above. Give the generalization-error bound for each of these test_MSE results, in terms of an algebraic expression, and its numeric value for for 6 = 0.1 .

(ii)        Pick the best model from (f)(i) based on their test_MSE results.  Now what

is the generalization-error bound for this final chosen best model?  Give an  algebraic  expression,  evaluate numerically  for  6 = 0.1 ,  and briefly justify your generalization-error bound answer.

Hint: the generalization-error bound is different here than in (f)(i).   The reason is subtle.  Try to figure out why.

[1] https://en.wikipedia.org/wiki/Random_sample_consensus

[2] http://www.cse.yorku.ca/~kosta/CompVis_Notes/ransac.pdf

[3] https://archive-beta.ics.uci.edu/ml/datasets/bike+sharing+dataset

2. CART,feature types, cost metrics

[created by Thanos Rompokos]

Comment: solving this problem probably isn’t as long as it might first look. Some sections below are repeated with appropriate modificationsfor clarity.

In this problem you will construct a simple decision tree (CART) for classification. You are given the following dataset:

The dataset has 4 features (x1, x2, x3, x4) and the label is either 0 or 1 (Class column). The dataset is attached as a csv file for convenience. The x1 and x4 features are categorical and x2 and x3 features are continuous.

You can use solve this problem either by hand or by computer.

If you are using computer, you are allowed to use only the pandas and NumPy packages, and you must write the decision-tree code yourself; decision-tree code copied (in whole or in part) from the internet will not suffice for this problem and amounts to plagiarism.

a)  We want to use the Gini index to determine how to split the features in the tree. For each branch of the split we compute the corresponding Gini index and we define the cost of the split as the weighted average of the Gini indexes of the branches. For example: if the node A is split in two branches, A1  and A2  with A1  node having NA1 data points and A2 having NA2 data points the cost of split ofA is given by: cost(A)  =

. In general, if A is split in K values, the cost of split ofA is given by:

cost(A) = x1eAi)NAi

probability of the cth class. If N1 data points belong to the 1st class out of N total, then the probability of the class 1 is 几1  = .

In this part, we want to deal only with categorical features, thus we convert x2 and x3 to categorical features as follows:

•   For x2 we set:

o the 5 lowest values to low_x2

o the 5 middle values to mid_x2

o the 4 highest values to high_x2

i.e., we sort the values in ascending order and the 1st 5 are set to low_x2, the next 5 are set to mid_x2 and the last 4 are set to high_x2.

•   For x3 we set:

o the 5 lowest values to low_x3

o the 4 middle values to mid_x3

o the 5 highest values to high_x3

i.e., we sort the values in ascending order and the 1st 5 are set to low_x3, the next 4 are set to mid_x3 and the last 5 are set to high_x3.

Add two new features in the dataset named x2_cat and x3_cat which are the converted to categorical x2 and x3 features respectively.

Construct a decision tree using the Gini index and the cost defined above. For each categorical feature (x1, x2_cat, x3_cat, x4) determine the Gini index and the cost of the split. You are allowed to split the categorical features multiway only. For example, if a categorical feature di has the values {medium, mild, hot}, the di will be split 3-way: one branch for di  = “medium”, one branch for di  = “mild” and one branch for di  = “hot” .

Iterate through all the nodes sequentially and in each node of the tree, calculate the cost of split of each feature. If all the data points for that node have the same value for a feature, no need to report the cost of its split.  Split that node in the feature that gives the lowest cost. Repeat until every branch has depth = 2 or all the leaf nodes are pure. If a node is pure, it requires no further splitting. Depth of 2 in a tree means 3 levels of nodes (1 root node, 1 level of internal nodes, and 1 level of leaf nodes).

For each node (including the root node) report:

•   N, the total number of data points in that node

•   N6   and  N!   the  number  of data  points  that  belong  to  class  0  and  class  1 respectively

•   The cost of split for all the features in the node. (For example, in the first level, you have to choose the split from all the features (x1, x2_cat, x3_cat, x4) thus report the cost for each one of them)

In each level (including the final level) report:

• The error (fraction of points that are misclassified)

In each branch clearly state:

•   The decision (i.e., x4 = W) in this branch

• The Gini index

b)  We  repeat  question  (a)  with  the  continuous  features  x2  and  x3. We  split  in  the continuous variables to denote a branch: If the feature x2 has the value of v2 , the question to ask in the split is x2 >  v2  or x2 ≤ v2 , i.e., we use v2  as the threshold t2 to split x2. To determine the optimal split in the continuous variables we use every possible split as follows: We sort the feature in ascending order and then iteratively we determine the cost of split using as threshold each value. The optimal split of the feature is the one with the lowest cost.

Construct a decision tree using the Gini index and the cost defined in (a). For each feature (categorical or continuous) (x1, x2, x3, x4) determine the Gini index and the cost of the split. You are allowed to split the categorical features multiway only. For example, if a categorical feature di  has the values {medium, mild, hot}, the di  will be split 3-way: one branch for di  = “medium”, one branch for di  = “mild” and one branch for di  = “hot” .

Iterate through all the nodes sequentially and in each node of the tree, calculate the cost of split of each feature. If all the data points for that node have the same value for a feature, no need to report the cost of its split.  Split that node in the feature that gives the lowest cost. Repeat until every branch has depth = 2 or all the leaf nodes are pure. If a node is pure, it requires no further splitting. Depth of 2 in a tree means 3 levels of nodes (1 root node, 1 level of internal nodes, and 1 level of leaf nodes).For each node of the tree (including the root node) report:

•   N, the total number of data points in that node

•   N6  and N!  number of the data points that belong to class 0 and class 1 respectively

•   The cost of split for all the features in the node. (For example, in the first level, you have to choose to split all the features (x1, x2, x3, x4) thus report the cost for each one of them)

In each level (including the final level) report:

•   The error (fraction of points that are misclassified)

In each branch clearly state:

•   The decision (i.e., x4 = W or x2 >v2) in this branch

• The Gini index

c)   We want to use the entropy to determine how to split the features in the tree. For each

branch  of the  split  we  compute  the  corresponding  entropy,  and  we  calculate  the

information gain of each split. If the node A is split in two branches, A1  and A2 , the

entropy ofA1 is defined as: e =   − ∑c(C)=1 几c log2 (几c ),  where 几c is the probability

of the cth  class in the A1 node. The information gain for the split in A is defined as

follows: IG(A)  = e − Li(2)=1 en(A)t(i) , where NAi is the number of points in the Ai

node and NA the number of points in the A node (the parent). In general, if A is split in

K values, the information gain is defined: IG(A)  = e − L1 en(A)t(i) , i.e., we

subtract the weighted sum of the entropy of each child node (Ai ) from the entropy of

the parent node A.

Construct a decision tree using the entropy and the information gain defined above. For each feature (x1, x2, x3, x4) determine the entropy and the information gain of the split. You are allowed to split the categorical features multiway only. For example, if a categorical feature di has the values {medium, mild, hot}, the di will be split 3-way: one branch for di  = “medium”, one branch for di  = “mild” and one branch for di  = “hot” .

Iterate through all the nodes sequentially and in each node of the tree, calculate the cost of split of each feature. If all the data points for that node have the same value for a feature, no need to report the cost of its split.  Split that node in the feature that gives the highest information gain. Repeat until every branch has depth = 2 or all the leaf nodes are pure. If a node is pure, it requires no further splitting. Depth of 2 in a tree means 3 levels of nodes (1 root node, 1 level of internal nodes, and 1 level of leaf nodes).

For each node (including the root node) report:

•   N, the total number of data points in that node

•   N0 and N1 number of the data points that belong to class 0 and class 1 respectively

•   The information gain for all the features in the node. (For example, in the first level, you have to choose to split all the features (x1, x2, x3, x4) thus report the

information gain for each one of them)

In each level (including the final level) report:

•   The error (fraction of points that are misclassified)

In each branch clearly state:

•   The decision (i.e., x4 = W or x2 >v2) in this branch

•   The entropy

Note:

• limx)0 −x logx = 0

•    For the calculations of entropy, we use logarithm with base 2

d)  We repeat question (c), using the gain ratio metric to determine the best split instead of the information gain. For each branch of the split we compute the corresponding entropy and we calculate the gain ratio of each split. If the node A is split in two branches, A1 and A2 , the gain ratio of A is defined as:

GR(A) =

In general, if the node A is split in K branches, A1 … AK , the gain ratio of A is defined

as:

GR(A)  =

where NAi is the number of data points in the Ai split and IG(A) is the information gain defined in (c).

Similar to (c), construct a decision tree using the entropy and the gain ratio defined above. For each feature (x1, x2, x3, x4) determine the entropy and the gain ratio of the split. You are allowed to split the categorical features multiway only. For example, if a categorical feature di has the values {medium, mild, hot}, the di will be split 3-way: one branch for di  = “medium”, one branch for di  = “mild” and one branch for di  = “hot” .

Iterate through all the nodes sequentially and in each node of the tree, calculate the cost of split of each feature. If all the data points for that node have the same value for a feature, no need to report the cost of its split.  Split that node in the feature that gives the highest information gain. Repeat until every branch has depth = 2 or all the leaf nodes are pure. If a node is pure, it requires no further splitting. Depth of 2 in a tree means 3 levels of nodes (1 root node, 1 level of internal nodes, and 1 level of leaf nodes).

For each node (including the root node) report:

•   N, the total number of data points in that node

•   N0 and N1 number of the data points that belong to class 0 and class 1 respectively

•   The gain ratio for all the features in the node. (For example, in the first level, you have to choose to split all the features (x1, x2, x3, x4) thus report the gain ratio for each one of them)

In each level report (including the final level):

• The error (fraction of points that are misclassified)

In each branch clearly state:

•   The decision (i.e., x4 = W or x2 >v2 ) in this branch

•   The entropy

Note:

• limx → 6 −x logx = 0

•    For the calculations of entropy, we use logarithm with base 2

e)  We have the following test set with 4 data points:

Report if each of the tress you designed in parts (b), (c) and (d) would classify correctly or misclassify each data point in the test set. You can report this by adding columns to the table (2 columns for each problem part: one column for class assignment (0/1, Class 0 or Class 1), and one column for entries Y (correct) or N (incorrect) (Y/N)). The final table should look as follows:

Use the following template (on next page) to represent the tree in each question (for reference, the tree in the template has depth of 1).

For each node, report the cost of the split for each feature separately from the tree template.

3. Polynomial regression, in-sample and out-of-sample error, VCdim

[Created by Zhiruo Zhou]

You are given a 1D regression problem. The target function is a polynomial of degree M:

f(x) = L0ai x i

and feature space extends over − 1 ≤ x ≤ +1 .  p(x) is a uniform distribution over the

Each draw of the dataset D consists of N points [xi , y(xi )], i = 1, … , N . y(x) = f(x). The hypothesis set consists of all polynomials of degree K:

ℎK (x) = L0wi x i .

For a given K and use the MSE error measurement, you plan to derive the best hypothesis to fit f(x) using the observations y(x), and check its performance. In (a)-(c), you will draw noiseless data and work on related questions (do not use any regularization). In (d), you will draw noisy data and add in regularization in (e).

For programming  in this problem, you  are  expected to  set  a  fixed random  seed  for reproducible results. For example, the coefficients for f(x) shall be generated on your side and be consistent throughout different questions. To ensure that you use the same ai s as the  solution does, please use the following code to generate  ai . The returned vector corresponds to [aM , aM - 1, aM -2, … , a1, a0 ], i.e., the first element is the coefficient of the highest order term.

(a) [To be done by hand. Your answers can be handwritten or typed.]

(i)        Write the equation that when solved, sill give the best hypothesis ℎ)  in terms of xi , y(xi ), wi . Then state how the equation can be solved.  No need to do further calculation. Assume MSE criterion function.

(ii)       From the result of (i), what relation between K and N is needed for ℎ)  to be a

good estimation?

(iii)      Give    the    expression    of   Ein P ℎ) Q     and    Eout P ℎ) Q    in    terns    of

ℎ xi , y(xi ), N, p(x).

[Parts (b)-(e) below are to be done by computer (except interpretations and comparisons). ]

(b) Suppose N = 30, K = 5. Do a simulation experiment and calculate ℎ)  numerically by linear regression. Plot f(X), ℎ)  and sampled dataset D in one figure. Hint: use plot() for f(X) and ℎ and scatter() for D if you use matplotlib. Useful function: sklearn.linear_model.LinearRegression withfit_intercept=False.

(c) Now you would like to check how good ℎ)  is as K and N change. Ein P ℎ) Q is the error on the training set D . To approximate Eout Pℎ) Q, you always use the dataset drawn from x=np.linspace(- 1, 1, 10000) to measure the MSE. Under this setting, solve the following questions:

(i)        Calculate ED cEin P ℎ) Qd and ED cEout Pℎ) Qd for different N and K , and put the result into the following table.