CS4780_HW1

CS 4780/5780 Homework 1 Due: Tuesday 02/14/23 11:59pm on Gradescope Note: For homework, you can work in teams of up to 3 people. Please include your team- mates’ NetIDs and names on the front page and form a group on Gradescope. (Please answer all questions within each paragraph). Please show all the relevant steps in your solutions to get full credit. Problem 1: Machine Learning Basics 1. Explain why in each of the following scenarios, the trained model may not perform well in testing or deployment. (a) Using a model trained on temperature data from California to predict tomorrow’s temperature in Ithaca. (b) You have the medical record of patients between 21 and 75 years of age, sorted in ascending order by age. You decide to use the first 80% of the data for training, the next 10% of the data for validation, and the last 10% of the data as the test set. (c) Using email data a model is trained to classify emails between spam and not-spam. The data was shuffled uniformly at random and split into 80% of data for training, 10% for validation and 10% for testing. 2. Remember from class that loss functions should always be non-negative and ideally also continuous and differentiable. For the following loss functions, identify if it is a) always non-negative, b) always continuous, c) always differentiable. Briefly justify your answer. (a) L ( h ) = 1 n n X i =1 ( h ( x i ) − y i ) 2 (b) L ( h ) = 1 n n X i =1 | h ( x i ) − y i | (c) L ( h ) = 1 n n X i =1 cos( h ( x i ) − y i ) 3. Consider a training data set D = { ( x i , y i ) : 1 ≤ i ≤ n } . Remember the hypothesis class we discussed in class where each individual hypothesis returns a constant value: h z ∈ H s.t. h z ( x ) = z ∀ z ∈ Q ≥ 0 That is, z can be any rational number greater than or equal to 0. 1

(a) Consider the squared loss: L ( h ) = 1 n n X i =1 ( h ( x i ) − y i ) 2 Prove that the function h m ( x ) minimizes the squared loss when we have that m = 1 n n X i =1 y i (b) Suppose we have the following training data set x (feature) y (label) 5 1 -6 500 2 3 Using the absolute loss, show that h 3 gives the minimum loss on D among all functions h z ∈ H . Problem 2: K-nearest Neighbors/Curse of Dimensionality 1. Robin has been given a dataset and will soon receive many more data points to classify. Unfortunately, Robin has never taken CS 4780 and does not know how to classify the points. However, you are taking CS 4780 and Robin decides to enlist your help. The initial dataset is as follows: • Positive examples (label +1): { (3 , 1) , (4 , 4) , (5 , 2) } • Negative examples (label − 1): { (3 , 2) , (2 , 3) } . Suppose the data lies in the grid [0 , 5] × [0 , 5]. The positive points are labeled in blue and the negative points in red in the following figure. Draw the decision boundary for a 1-NN classifier with the Euclidean distance. 2